Математическое програмирование

      Решение.

        Составим математическую модель задачи:

Обозначим - количество груза, перевезенного из пункта отправления i в пункт назначения j.

Получим следующие ограничения (т.к. весь груз должен быть вывезен, и все потребности удовлетворены полностью):

                

    

     

     При этом должна быть минимизирована целевая функция

         Построим опорный план методом  северо-западного угла:

 

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

      Построим  систему потенциалов. U_i - потенциалы, соответствующие поставщикам,  V_i- потенциалы, соответствующие потребителям.

         Полагаем U₁ =0, а далее U_i + V_i = d_ij для занятых клеток таблицы.

 

         Проверим критерий оптимальности  : для свободных клеток.

 

         Из тех условий, где критерий не выполняется, выбираем то условие, где разница максимальна. Это – ячейка (1 , 4). Перебросим в ячейку (1 , 4) 20 единиц груза из ячейки (1 , 1). 
 
 
 

 

         Чтобы компенсировать недостаток  в третьей строке, перебросим те же 20 единиц груза из ячейки (3 , 4) в ячейку (3 , 1).

      Получили новую таблицу, для которой повторяем расчет потенциалов:

         Полагаем U₁ =0, а далее U_i + V_i = d_ij для занятых клеток таблицы.

 

         Проверим критерий оптимальности  : для свободных клеток.

 

         Из тех условий, где критерий  не выполняется, выбираем то  условие, где разница максимальна.  Это – ячейка (2 , 5). Перебросим в ячейку (2 ,5) 20 единиц груза из ячейки (1 , 2).