ПЗ4 Маслобойникова ЭБ(с)-92 7 вариант. Решение Так как суммарная мощность поставщиков равна суммарному спросу потребителей, то есть
 Скачать 315.79 Kb.
|
|
Найдем предварительные потенциалы Ui, Vj по занятым клеткам таблицы (выделены серым) по формуле  , полагая, что U1 = 0  U1 + V2 = 6; 0 + V2 = 6; V2 = 6 U1 + V5 = 10; 0 + V5 = 10; V5 = 10 U2 + V4 = 4; -1 + V4 = 4; V4 = 5 U2 + V5 = 9; 10 + U2 = 9; U2 = -1 U3 + V5 = 9; 10 + U3 = 9; U3 = -1 U3 + V3 = 6; -1 + V3 = 6; V3 = 7 U4 + V5 = 7; 10 + U4 = 7; U4 = -3 U4 + V1 = 5; -3 + V1 = 5; V1 = 8 После того, как будут рассчитаны потенциалы всех строк и всех столбцов, находятся характеристики свободных клеток по нижеприведенной формуле (из лекции):  ∆11=8-(0+8) = 0 ∆21=6-(-1+8) = -1 ∆31=7-(-1+8) = 0 ∆22=9-(-1+6) = 4 ∆32=8-(-1+6) = 3 ∆42=7-(-3+6) = 4 ∆13=10-(0+7) = 3 ∆23=8-(-1+7) = 2 ∆43=6-(-3+7) = 2 ∆14=5-(0+5) = 0 ∆34=5-(-1+5) = 1 ∆44=9-(-3+5) = 7 Характеристики свободных клеток занесены в таблицу выше. Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij, то есть ∆21 = 8 +(- 1)= 7 > -1 Для перехода к лучшему плану строится цикл пересчета той свободной клетки, которую требуется занять поставкой в первую очередь. В первую очередь заполняется свободная клетка с максимальной по модулю отрицательной характеристикой. А2В1
В свободную клетку перемещается минимальная величина, выбранная из поставок, отмеченных знаком «-» (по вершинам цикла пересчета), все остальные вершины по циклу пересчета увеличиваются или уменьшаются на эту величину в зависимости от знака вершины  Переменные, не вошедшие в цикл пересчета, переносятся в новый план без изменений.∆21 = 50 ∆25 = 50-50= 0 ∆45 = 80+50=130 ∆41 = 490-50=440
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
