Вырожденные случаи метода потенциалов. Открытые транспортные задачи

Август 22, 2022

Главная
Математика
Вырожденные случаи метода потенциалов. Открытые транспортные задачи

Содержание

2. Вырожденные случаи метода потенциалов Вырожденные случаи транспортной задачи возникают, когда минимальное значение при нахождении опорного плана
3. Пример 1
4. Пример 1 Такой план является вырожденным для метода потенциалов.
5. Пример 1
6. Пример 1
7. Пример 1
8. Пример 1
9. Пример 1
10. Пример 1 Получен невырожденный план.
11. Пример 1 Попробуем найти невырожденный план с меньшей стоимостью перевозок. Для этого будем сначала заполнять клетки
12. Пример 1
13. Пример 1
14. Пример 1
15. Пример 1
16. Пример 1 Получен невырожденный план с меньшей стоимостью перевозок.
17. Пример 2 Для нахождения невырожденного плана в этом примере необходимо ввести фиктивные величины.
18. Пример 2 Для нахождения невырожденного опорного плана в этом примере необходимо ввести фиктивные величины.
19. Открытые транспортные задачи
20. Пример 60 50
21. Пример
22. Пример
23. Пример
24. Пример
25. Пример
26. Пример
27. Пример Оптимальный план найден.
28. Пример 60 50
29. Транспортная задача с минимизацией времени
30. Транспортная задача с минимизацией времени Эта задача является задачей нелинейного программирования, так как L нелинейна. Для
31. Пример
32. Пример
33. Пример
34. Пример
35. Пример
36. Пример
37. Пример
38. Пример
39. Пример
40. Пример
41. Пример
42. Пример
43. Пример
44. Пример
45. Пример
46. Пример
47. Задание для самоконтроля 1. Минимальное время перевозок равно ... 1) 2, 2) 3, 3) 4, 4)
48. 2. Какое утверждение верно для цикла? 1) несколько клеток, соединенных линией так, чтобы четыре вершины были
50. Скачать презентацию

Слайд 2

Вырожденные случаи метода потенциалов
Вырожденные случаи транспортной задачи возникают, когда минимальное значение

при нахождении опорного плана или пересчёте цикла достигается в нескольких значениях. Преодолеваются вырожденные случаи двумя способами:
1. Можно попытаться выбрать другой опорный план или другой цикл.
2. Ввести в некоторые клетки ε, считая по ходу решения задачи
ε > 0 и меньше всех других величин количества груза в таблице, а
затем положить ε = 0.

Слайд 3

Пример 1

Слайд 4

Пример 1
Такой план является вырожденным для метода потенциалов.

Слайд 5

Пример 1

Слайд 6

Пример 1

Слайд 7

Пример 1

Слайд 8

Пример 1

Слайд 9

Пример 1

Слайд 10

Пример 1
Получен невырожденный план.

Слайд 11

Пример 1
Попробуем найти невырожденный план с меньшей стоимостью перевозок. Для этого

будем сначала заполнять клетки с меньшими стоимостями перевозок, если это возможно.

Слайд 12

Пример 1

Слайд 13

Пример 1

Слайд 14

Пример 1

Слайд 15

Пример 1

Слайд 16

Пример 1
Получен невырожденный план с меньшей стоимостью перевозок.

Слайд 17

Пример 2
Для нахождения невырожденного плана в этом примере необходимо ввести фиктивные

величины.

Слайд 18

Пример 2
Для нахождения невырожденного опорного плана в этом примере необходимо ввести

фиктивные величины.

Слайд 19

Открытые транспортные задачи

Слайд 20

Пример
60
50

Слайд 21

Пример

Слайд 22

Пример

Слайд 23

Пример

Слайд 24

Пример

Слайд 25

Пример

Слайд 26

Пример

Слайд 27

Пример
Оптимальный план найден.

Слайд 28

Пример
60
50

Слайд 29

Транспортная задача с минимизацией времени

Слайд 30

Транспортная задача с минимизацией времени
Эта задача является задачей нелинейного программирования, так

как L нелинейна. Для её решения можно применить метод "вычёркивания клеток". Вычёркиваем из таблицы клетки, в которых tij максимально. Пытаемся найти план, не использующий этих клеток. Если план найти удается, то вычеркиваем следующие клетки. Если нет, то предыдущий полученный план является оптимальным.
Некоторые случаи, когда таблицу заполнить нельзя:
1. В строке (столбце) вычеркнуты все клетки.
2. В строке (столбце) остается одна невычеркнутая клетка и сумма в строке (столбце) больше суммы столбца (строки).
При заполнении таблицы надо рассмотреть все возможные способы заполнения. Можно ограничится только невырожденными, если они есть.
Проще найти план, если начинать заполнение таблицы со строк и столбцов с наименьшим количеством невычеркнутых клеток.

Слайд 31

Пример

Слайд 32

Пример

Слайд 33

Пример

Слайд 34

Пример

Слайд 35

Пример

Слайд 36

Пример

Слайд 37

Пример

Слайд 38

Пример

Слайд 39

Пример

Слайд 40

Пример

Слайд 41

Пример

Слайд 42

Пример

Слайд 43

Пример

Слайд 44

Пример

Слайд 45

Пример

Слайд 46

Пример

Слайд 47

Задание для самоконтроля
1. Минимальное время перевозок равно ...
1) 2,
2) 3,
3)

4,
4) 5.

Слайд 48

2. Какое утверждение верно для цикла?
1) несколько клеток, соединенных линией так,

чтобы четыре вершины были расположены в одной строке.
2) несколько клеток, соединенных замкнутой линией так, чтобы две вершины были расположены либо в одном столбце.
3) несколько клеток, соединенных замкнутой ломаной линией так, чтобы две соседние вершины ломаной были расположены либо в одной строке, либо в одном столбце.
4) несколько клеток, соединенных незамкнутой ломаной линией так, чтобы две соседние вершины ломаной не были расположены в одной строке или в одном столбце.

Задания для самоконтроля