Особенности решения открытой транспортной задачи

Цикл- это замкнутая ломаная линия, состоящая из горизонтальных и вертикальных отрезков, соединяющих некоторые занятые клетки.

Такой цикл всегда существует и только один!

б) размечаем вершины цикла знаками - + - … считая от исходной клетки.

в) находим, по всем клеткам, помеченным знаком - наименьшую перевозку. Обозначим ее α. У нас α = 20.

г) двигаясь по циклу, прибавляем α к клеткам со знаком + и вычитаем ее из клеток со знаком -.

Получающийся “лишний нуль” стираем.

Результаты записываем в новую таблицу.

Потр.						U
Пост.
						-1
V

Не забываем проверять условие: число занятых клеток = m+n -1.

4. Проверка опорного плана на оптимальность.

Вновь находим потенциалы и проверяем условие (2).

Условие оптимальности выполнено.

Получен оптимальный план перевозок!

F_min = 20*4 + 80*2 + 100*4 + 50*6 + 50*4 + 150*2 + 50*5 = 1690

х₁₂ = 20

х₁₃ = 80

х₁₅ = 100

х₂₁ = 50

х₂₂ = 50

х₂₄ = 150

х₃₁= 50

Напомним, что в открытой транспортной задаче сумма запасов не равна сумме спроса:

1) пусть , т.е.сумма запасов превышает суммарный спрос.

Вводим фиктивного потребителя - в таблице это означает добавление в таблицу столбца. Приписываем этому потребителю спрос . В соответствующих клетках тарифы равны нулю. Задача становится закрытой.

2) пусть , т.е. сумма запасов меньше суммарного спроса.

Вводим фиктивного поставщика - в таблице это означает добавление в таблицу строки. Приписываем этому поставщику запасы . В соответствующих клетках тарифы равны нулю. Задача становится закрытой.

Пример:

Решить транспортную задачу:

Потр.					ЗАПАСЫ
Пост.
СПРОС

Задача открытая, т.к. суммарные запасы меньше суммарного спроса.

Следуя рекомендации, введем фиктивного поставщика.

Потр.					ЗАПАСЫ
Пост.
4^*
СПРОС

1. Нахождение начального опорного плана (угловой точки).

Отметим, что фиктивные клетки следует рассматривать в последнюю очередь.

Потр.					ЗАПАСЫ
Пост.
4^*
СПРОС

Проверяем условие m+n-1.

2. Проверка опорного плана на оптимальность.

Проверка на оптимальность осуществляется с помощью потенциалов во вновь составленной таблице.

Потр.					U
Пост.
4^*					-2
V

Условие оптимальности выполнено!

Получен оптимальный план перевозок!

F_max = 35*1 + 5*2 + 20*3 + 40*3 + 25*4 + 65*2 + 0 =455

х₁₂ = 35

х₂₁ = 20

х₂₃ = 40

х₃₁ = 25

х₃₄ = 65

х₄₃ = 10

Заметим, что третий потребитель ничего не получит!

Выполнить вычисления в EXCEL.

Дата добавления: 2014-12-27