Транспортная задача в сетевой постановке

2.2 Пример решения транспортной задачи. 

             В городе N имеется 4 склада А_i, на которых хранится ткань (в рулонах) и 5 магазинов B_j, занимающихся продажей ткани. Ниже, в таблице, приведены данные по количеству рулонов на каждом складе, запросы магазинов и стоимость перевозки одного рулона из А_i в B_j. Необходимо составить такой план перевозок, при котором запросы магазинов будут удовлетворены при минимальной суммарной стоимости перевозок. 
 

 

    В данном случае Σa_i=225 >Σb_j=220 => имеем дело с открытой моделью транспортной задачи. Сведем ее к закрытой введением фиктивного магазина B₆ с потребностью b₅=225-220=5 и стоимостью перевозок с_i6=0.Имеем таблицу: 

 

    Математическая  модель: обозначим x_ij – количество товара, перевозимого из А_i в B_j. Тогда

             x₁₁ x₁₂ x₁₃ x₁₄ x₁₅ x₁₆

             x₂₁ x₂₂ x₂₃ x₂₄ x₂₅ x₂₆

       X =   x₃₁ x₃₂ x₃₃ x₃₄ x₃₅ x₃₆  - матрица перевозок.

             x₄₁ x₄₂ x₄₃ x₄₄ x₄₅ x₄₆

min(x₁₁+2x₁₂+3x₁₃+2,5x₁₄+3,5x₁₅+0,4x₂₁+3x₂₂+x₂₃+2x₂₄+3x₂₅+0,7x₃₁+x₃₂+x₃₃+0,8x₃₄+1,5x₃₅++1,2x₄₁+2x₄₂+2x₄₃+1,5x₄₄+2,5x₄₅)                (1)  

x₁₁+x₁₂+x₁₃+x₁₄+x₁₅+x₁₆=50

x₂₁+x₂₂+x₂₃+x₂₄+x₂₅+x₂₆=20

x₃₁+x₃₂+x₃₃+x₃₄+x₃₅+x₃₆=75

x₄₁+x₄₂+x₄₃+x₄₄+x₄₅+x₄₆=80

x₁₁+x₂₁+x₃₁+x₄₁=40               (2)

x₁₂+x₂₂+x₃₂+x₄₂=50

x₁₃+x₂₃+x₃₃+x₄₃=15

x₁₄+x₂₄+x₃₄+x₄₄=75

x₁₅+x₂₅+x₃₅+x₄₅=40

x₁₆+x₂₆+x₃₆+x₄₆=5

x_ij≥0  (i=1,2,3,4 ; j=1,2,3,4,5,6 )    (3) 

    Двойственная  ЗЛП:

max(50u₁+20u₂+75u₃+80u₄+40v₁+50v₂+15v₃+75v₄+40v₅+5v₆)               (1*)

u₁+v₁≤1               

u₁+v₂≤2                               

u₁+v₃≤3                                                       (2*)

u₁+v₄≤2,5

u₁+v₅≤3,5

u₁+v₆≤0                

u_i,v_j – произвольные (i=1,2,3,4 ; j=1,2,3,4,5,6 )                                                  (3*) 

    Будем искать первоначальный план по методу наименьшей стоимости:

1) x₂₁=20 и 2-ую строку исключаем.2) x₃₁=20 и 1-ый столбец исключаем.

3) x₃₄=55 и 3-ю строку исключаем.4) x₄₄=20 и 4-ый столбец исключаем.

5) x₁₂=50 и 1-ю строку и 2-ой столбец исключаем и x₃₂=0. 6) x₄₃=150 и 3-ий столбец исключаем.7) x₄₅=40 и 5-ый столбец исключаем.x₄₆=5.Составим таблицу. Здесь и далее в нижнем правом углу записываем значение перевозки. 

 

Стоимость 1-ого плана: 

D₁=2•50+0,4•20+0,7•20+0,8•55+2•15+1,5•20+2,5•40=326.

Будем улучшать этот план методом потенциалов: u_i- потенциал А_i ,v_j- потенциал B_j. Тогда u₁+v₂=2,u₂+v₁=0,4, u₃+v₁=0,7, u₃+v₂=1, u₃+v₄=0,8, u₄+v₃=2, u₄+v₄=1,5, u₄+v₅=2,5 ,u₄+v₆=0.Положим u₁=0,тогда v₂=2,u₃=-1,v₁=1,7,v₄=1,8, u₂=-1,3,u₄=-0,3, v₃=2,3,v₅=2,8,v₆=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. Составим таблицу: