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

Значение целевой функции для этого опорного плана равно:

 

1.2.2. Построение  опорного плана методом минимальной  стоимости

Используя метод минимальной стоимости, построю опорный план транспортной задачи.

Выбираю ячейку 21, т.к. данная ячейка содержит наименьшую транспортную издержку 6, и делаю поставку 70. Затем закрываю 2 строку, т.к. предложение полностью исчерпано. (Таблица 8)

Таблица 8

 

 
Выбираю ячейку 44 с наименьшей транспортной издержкой 7 и делаю поставку 85. Затем закрываю 4 строку, т.к. предложение полностью исчерпано. (Таблица 9)

 
 
 
 
 
 
 
 
 
 
 
 
Таблица 9

 

 
Выбираю ячейку 31 с наименьшей транспортной издержкой 10 и делаю поставку 25. Закрываю 1 столбец, т.к. потребности полностью удовлетворены. (Таблица 10)

 
Таблица 10

 

 
Выбираю ячейку 12 с наименьшей издержкой 12 и делаю поставку 105. Закрываю 1 строку, т.к. предложение полностью исчерпано. (Таблица 11)

 
Таблица 11

 
Выбираю ячейку 32 с наименьшей издержкой 19 и делаю поставку 55. Выбираю ячейку 33 с наименьшей издержкой 22 и делаю поставку 135. Делаю поставку 25 в ячейку 34. (Таблица 12)

 
Таблица 12

 

 
Матрица перевозок:

 

 
В результате получен опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

Значение целевой функции для этого опорного плана равно:

 

1.2.3. Построение  опорного плана методом Фогеля

Используя метод Фогеля, построю опорный план транспортной задачи. Для каждой строки и столбца таблицы условий найду разности между двумя минимальными тарифами, записанными в данной строке или столбце.

Нахожу разности по строкам:

1 строка: минимальная издержка 12, ближайшая к ней 17. 

 

 
2 строка: минимальная издежка 6, ближайшая  к ней 11.

 

 
3 строка: минимальная издежка 10, ближайшая к ней 19.

 

 
4 строка: минимальная издежка 7, ближайшая к ней 14.

 

 
Нахожу разности по столбцам:

1 столбец: минимальная издержка  6, ближайшая к ней 10.

 

 
2 столбец: минимальная издержка  11, ближайшая к ней 12

 

 
3 столбец: минимальная издержка  17, ближайшая к ней 20.

 

 
4 столбец: минимальная издержка  7, ближайшая к ней 21.

 

 
14 – максимальная разность, поэтому  выбираю 4 столбец и делаю поставку 85 в ячейку 44 с минимальной издержкой 7. Закрываю 4 строку, т.к. предложение  исчерпано. (Таблица 13)

Таблица 13

 

 
Нахожу разности по строкам:

1 строка: минимальная издержка 12, ближайшая к ней 17. 

 

 
2 строка: минимальная издежка 6, ближайшая  к ней 11.

 

 
3 строка: минимальная издежка 10, ближайшая  к ней 19.

 

 
Нахожу разности по столбцам:

1 столбец: минимальная издержка 6, ближайшая к ней 10.

 

 
2 столбец: минимальная издержка 11, ближайшая  к ней 12

 

 
3 столбец: минимальная издержка 17, ближайшая  к ней 20.

 

 
4 столбец: минимальная издержка 21, ближайшая  к ней 27.

 

 
9 – максимальная разность, поэтому  выбираю 3 строку и делаю поставку 95 в ячейку 31 с минимальной издержкой 10. Закрываю 1 столбец, т.к. потребности полностью удовлетворены. (Таблица 14)

Таблица 14

 

 
Нахожу разности по строкам:

1 строка: минимальная издержка 12, ближайшая к ней 17. 

 

 
2 строка: минимальная издежка 11, ближайшая  к ней 20.

 

 
3 строка: минимальная издежка 19, ближайшая  к ней 22.

 

 
Нахожу разности по столбцам:

2 столбец: минимальная издержка 11, ближайшая к ней 12

 

 
3 столбец: минимальная издержка 17, ближайшая  к ней 20.

 

 
4 столбец: минимальная издержка 21, ближайшая  к ней 27.

 

 
9 – максимальная разность, поэтому  выбираю 2 строку и делаю поставку 70 в ячейку 22 с минимальной издержкой 11. Закрываю 2 строку, т.к. предложение исчерпано. (Таблица 15)

Таблица 15

 

 
Нахожу разности по строкам:

1 строка: минимальная издержка 12, ближайшая к ней 17. 

 

 
3 строка: минимальная издежка 19, ближайшая  к ней 22.

 

 
Нахожу разности по столбцам:

2 столбец: минимальная издержка  12, ближайшая к ней 19

 

 
3 столбец: минимальная издержка 17, ближайшая  к ней 22.

 

 
4 столбец: минимальная издержка 21, ближайшая  к ней 27.

 

 
7 – максимальная разность, поэтому выбираю 2 столбец и делаю поставку 90 в ячейку 12 с минимальной издержкой 12. Закрываю 2 столбец, т.к. потребности удовлетворены. (Таблица 16)

Таблица 16

 

 
Нахожу разности по строкам:

1 строка: минимальная издержка 17, ближайшая к ней 21. 

 

 
3 строка: минимальная издежка 22, ближайшая  к ней 27.

 

 
Нахожу разности по столбцам:

3 столбец: минимальная издержка 17, ближайшая к ней 22.

 

 
4 столбец: минимальная издержка 21, ближайшая  к ней 27.

 

 
6 – максимальная разность, поэтому  выбираю 4 столбец и делаю поставку 15 в ячейку 14 с минимальной издержкой 21. Закрываю 1 строку, т.к. предложение  исчерпано. (Таблица 17)

Таблица 17

 

 
Выбираю ячейку 33 с минимальной транспортной издержкой 22 и делаю поставку 135. В ячейку с издержкой 27 делаю поставку 10. (Таблица 18)

 
 
 
 
 
 
 
 
 
 
 
 
 
 
Таблица 18

 

 
Матрица перевозок:

 

 
В результате получен опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

Значение целевой функции для этого опорного плана равно:

 

1.3. Оптимизация  транспортной модели открытого  типа

1.3.1. Метод  потенциала на основе опорного  плана, построенного методом северо-западного  угла

Проверю опорный план (таблица 19) на вырожденность: всего заполненных клеток:

 
,

имею заполненных клеток: 7, тогда опорный план невырожденный. Поэтому применяю метод потенциалов.

Таблица 19

 
 

 

Проверю оптимальность опорного плана. Найду предварительные потенциалы по занятым клеткам таблицы, в которых , полагая, что .(Таблица 20)

 

 

 

 

 

 

 

 
Таблица 20

 
 

Работаю с пустыми клетками (Таблица 21):

 

 

 

 

 

 

 

 

 

Таблица 21

 
Так как существуют , то опорный план неоптимальный.

Перепланировка опорного плана

Выбираю клетку 31 с минимальной разностью -14. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак «+». Знаки остальных вершин чередуются. (Таблица 22)

Таблица 22

 

 
Среди отрицательных вершин выбираю наименьшую поставку 80. Эту поставку прибавляю к поставкам с положительной вершиной и отнимаю  от поставок с отрицательной вершиной. Выбранную минимальную поставку зануляю, а в пустую клетку записываю минимальную поставку. (Таблица 23)

Таблица 23

 

 
Значение целевой функции для этого опорного плана равно:

 

, из этого следует, что оптимизация прошла успешно.

Проверяю опорный план на оптимальность

 

 

 

 

 

 

 

Таблица 24

 

 
Работаю с пустыми клетками (Таблица 25):

 

 

 

 

 

 

 

 

 

 

Таблица 25

 

 
Так как существуют , то опорный план неоптимальный.

Перепланировка опорного плана

Выбираю клетку 14 с минимальной разностью -13. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак «+». Знаки остальных вершин чередуются. (Таблица 26)

Таблица 26

 

 
Среди отрицательных вершин выбираю наименьшую поставку 15. Эту поставку прибавляю к поставкам с положительной вершиной и отнимаю  от поставок с отрицательной вершиной. Выбранную минимальную поставку зануляю, а в пустую клетку записываю минимальную поставку. (Таблица 27)

Таблица 27

 

 
Значение целевой функции для этого опорного плана равно:

 

, из этого следует, что оптимизация прошла успешно.

Проверяю опорный план на оптимальность

 

 

 

 

 

 

 

 
 
 
 
Таблица 28

 

Работаю с пустыми клетками (Таблица 29):

 

 

 

 

 

 

 

 

 

Таблица 29

 

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию .

Минимальные затраты составят: .

1.3.2. Метод  потенциала на основе опорного  плана, построенного методом минимальной  стоимости

Таблица 30

 

 
Проверю опорный план (таблица 30) на вырожденность: всего заполненных клеток:

,

имею заполненных клеток: 7, тогда опорный план невырожденный. Поэтому применяю метод потенциалов.

Проверю оптимальность опорного плана. Найду предварительные потенциалы по занятым клеткам таблицы, в которых , полагая, что .(Таблица 31)

 

 

 

 

 

 

 

 
 
 
 
 
 
 
 
Таблица 31

 

 
Работаю с пустыми клетками (Таблица 32):

 

 

 

 

 

 

 

 

 

Таблица 32

 

 
Так как существуют , то опорный план неоптимальный.

Перепланировка опорного плана

Выбираю клетку 22 с минимальной разностью -4. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак «+». Знаки остальных вершин чередуются. (Таблица 33)

Таблица 33

 

 
Среди отрицательных вершин выбираю наименьшую поставку 55. Эту поставку прибавляю к поставкам с положительной вершиной и отнимаю  от поставок с отрицательной вершиной. Выбранную минимальную поставку зануляю, а в пустую клетку записываю минимальную поставку. (Таблица 34)

Таблица 34

Значение целевой функции для этого опорного плана равно:

 

, из этого следует, что оптимизация прошла успешно.

Проверю оптимальность опорного плана. Найду предварительные потенциалы по занятым клеткам таблицы, в которых , полагая, что .(Таблица 35)

 

 

 

 

 

 

 

Таблица 35

 
Работаю с пустыми клетками (Таблица 36):

 

 

 

 

 

 

 

 

 

Таблица 36

 
Так как существуют , то опорный план неоптимальный.

Перепланировка опорного плана

Выбираю клетку 14 с минимальной разностью -3. Из выбранной пустой клетки строю контур, остальные вершины которого лежат в заполненных клетках. Вершина в пустой клетке имеет знак «+». Знаки остальных вершин чередуются. (Таблица 37)

Таблица 37

 
Среди отрицательных вершин выбираю наименьшую поставку 15. Эту поставку прибавляю к поставкам с положительной вершиной и отнимаю  от поставок с отрицательной вершиной. Выбранную минимальную поставку зануляю, а в пустую клетку записываю минимальную поставку. (Таблица 38)

 
Таблица 38

 
Значение целевой функции для этого опорного плана равно:

 

, из этого следует, что оптимизация прошла успешно.

Проверю оптимальность опорного плана. Найду предварительные потенциалы по занятым клеткам таблицы, в которых , полагая, что .(Таблица 39)

 

 

 

 

 

 

 

Таблица 39

 
Работаю с пустыми клетками (Таблица 40):

 

 

 

 

 

 

 

 

 

Таблица 40

 
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию .

Минимальные затраты составят: .

1.3.3. Метод  потенциала на основе опорного  плана, построенного методом Фогеля

 
 
 
 
 
 
 
 
 
 
 
Таблица 41

 

Проверю опорный план (таблица 41) на вырожденность: всего заполненных клеток:

,

имею заполненных клеток: 7, тогда опорный план невырожденный. Поэтому применяю метод потенциалов.

Проверю оптимальность опорного плана. Найду предварительные потенциалы по занятым клеткам таблицы, в которых , полагая, что .(Таблица 42)

 

 

 

 

 

 

 

 
 
 
 
 
 
 
 
 
 
 
Таблица 42

 
Работаю с пустыми клетками (Таблица 43):

 

 

 

 

 

 

 

 

 

Таблица 43

 

 
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию .