Пример 3.4.1

Найти оптимальный план перевозок для транспортной задачи из примера 3.1.1.

Решение.

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

Таблица 3.4.1

Число заполненных клеток равно 4+3-1=6, т.е. данный план невырожденный. Определим потенциалы производителей и потребителей, составив уравнения для заполненных клеток.

, , ,

, ,

, . ,

, .

,

.

Составим разности для свободных клеток

,

,

,

,

,

.

Получена положительная разность . Заполним клетку первой строки и четвертого столбца. Строим цикл, начинающийся и заканчивающийся в этой клетке. Вершинами цикла являются клетки: (3,4), (3,3), (1,3) (на первом месте стоит номер строки, на втором – столбца). В клетке (1,4) ставим "+", в клетке (3,4) "-", в клетке (3,3) "+", в клетке (1,3) "-". Перераспределяем продукцию по циклу. Минимальное значение для клеток со знаком "-" находится в клетке (3,4) =90. Отнимаем 90 от значений, стоящих в клетках со знаком "-", и прибавляем к значениям, стоящим в клетках со знаком "+". Получаем новый план перевозок, представленный в следующей транспортной таблице (табл. 3.4.2):

Таблица 3.4.2

Новый план невырожденный. Проверим его на оптимальность.

, , ,

, ,

, . ,

, .

,

.

,

,

,

,

,

.

Положительная разность . Заполним клетку (2,2). Цикл будет содержать клетки: (2,2), (3,2), (3,3), (1,3), (1,4), (2,4), (2.2).

Минимальное значение для клеток со знаком "-". Перераспределив продукцию по циклу, получим новый план перевозок, представленный в табл. 3.4.3.

Таблица 3.4.3

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

, , ,

, ,

, . ,

, .

,

Составляем

,

,

,

,

,

.

Все разности отрицательные, следовательно, получен оптималь­ный план.

Заметим, что этот план совпадает с начальным планом, найденным по методу Фогеля.

Оптимальные затраты:

.

После изучения данного раздела целесообразно выполнить контрольную работу № 4.

Дата добавления: 2014-01-04