Контрольная работа: Применение методов линейного программирования для оптимизации стоимости перевозок

U₄ =-0,3

В верхнем левом углу здесь и далее записываем значение u_i +v_j -c_ij . Имеем: u₁ +v₁ --c₁₁ =0,7>0, u₁ +v₆ -c₁₆ =0,3>0, u₃ +v₃ -c₃₃ =0,3>0, u₃ +v₅ -c₃₅ =0,3>0,

u₄ +v₁ -c₄₁ =0,2>0. => По критерию оптимальности, первый план не оптимален. Далее max(0,7;0,3;0,3;0,3;0,2)=0,7. => Поместим перевозку в клетку А₁ В₁ ,сместив 20=min(20,50) по циклу, указанному в таблице штрихом. Получим новую таблицу. Найдем потенциалы: u₁ +v₁ =1,u₁ +v₂ =2,u₂ +v₁ =0,4,u₃ +v₂ =1, u₃ +v₄ =0,8, u₄ +v₃ =2, u₄ +v₄ =1,5, u₄ +v₅ =2,5 , u₄ +v₆ =0. Положим u₁ =0,тогда v₁ =1,u₂ =-0,6,v₂ =2,v₄ =1,8, u₃ =-1, u₄ =-0,3,v₃ =2,3,v₅ =2,8,v₆ =0,3. Составим таблицу 3. :

Таблица 3. - Проведение итераций