Пример 2.7.2

Оглавление | Назад| Глоссарий понятий

Проверить оптимальность ТЗ, определенную таблицей (табл.2.12).

Таблица 2.12

Решение. Ведем построение опорного плана методом наименьшей стоимости (таблица 2.13)

Таблица 2.13

Замечаем, что в результате пересчета по циклу оказалось, что число занятых клеток меньше, чем n + m - 1: 5 + 3 - 1 = 7 > 6, т.е. получен вырожденный план. Следовательно, заполняем числом «0» пустую клетку А2В5 , т.к. она имеет минимальный тариф (с25 = 3), и не образует с занятыми клетками замкнутого прямоугольного контура.

Получаем опорный план:

Вычислим общую сумму затрат на перевозку груза по этому плану:
Z = 10*2+20*3+20*2+40*4+10*7+0*3+50*2 = 550 (ед.).

Составляем систему уравнений потенциалов:

u1 + v1 = 2, Полагая u1 = 0, найдем: v1 = 2, u2 = 1,
u1 + v3 = 3,   v2 = 3, u3 = -4.
u1 + v5 = 2,   v3 = 3,
u2 + v2 = 4,   v4 = 6,
u2 + v4 = 7,   v5 = 2.
u2 + v5 = 3,    
u3 + v4 = 2.    

Проверив свободные клетки, убеждаемся, что по теореме 5 план оптимален, следовательно, Z=Zmin.
Данный оптимальный план не является единственным, так как для клетки А1В4 сумма потенциалов равна стоимости перевозки u1 + v4 = с14 и в нее по циклу, можно переместить 10 ед. груза.

Оглавление | Назад| Глоссарий понятий

Hosted by uCoz