Оглавление | Назад| Глоссарий понятий
Проверить оптимальность ТЗ, определенную таблицей (табл.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 ед. груза.
Оглавление | Назад| Глоссарий понятий
