Линейное программирование. Транспортная задача

ЗАДАНИЕ 4.    Тема:   «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ.

                                                         ТРАНСПОРТНАЯ ЗАДАЧА».

    Задача 4.1

 

В пунктах Аi (i=1, 2, 3)производится однородная продукция в количестве аi единиц. Себестоимость единицы продукции в i-м пункте равна Ci. Готовая продукция поставляется в пункты Вj (j=1, 2, 3, 4), потребности которых составляют bj  ед. стоимость перевозки единицы продукции из пункта Ai в пункт Bj задана матрицей Cij.

 

Данные:

 

Производители Аj		Потребители  Вj
Запасы ai	Себестоимость Ci	146	131	201	178
320	6	2	9	2	3
198	2	9	10	1	2
305	1	10	6	3	4

 

Требуется:

1. Написать математическую модель прямой и двойственной задач с указанием экономического смысла всех переменных;
2. Составить план перевозки продукции, при котором минимизируются суммарные затраты по ее изготовлению и доставке потребителям для условия что продукция произведенная в пункте Ai, где себестоимость её производства наименьшая, распределяется полностью;
3. Вычислить суммарные минимальные затраты Zmin;
4. Узнать в какие пункты развозится продукция от поставщиков;
5. Установить пункты, в которых останется нераспределенная продукция, и указать её объем.

Решение.

3

Σ аi= 320+198+305=823;

i=1

 

4

Σ bj = 146+131+201+178=656;

j=1

так как

3                4

Σ аi ≠Σ bj   , то задача  несбалансированна, излишек продукции у

i=1           j=1-

производителей  в объеме  823-656=167 ед., поэтому в таблицу добавляем фиктивного потребителя. Итоговая стоимость доставки равна сумме себестоимости и расходов на перевозку. У дополнительного потребителя стоимость доставки равна 0, за исключением клетки (1,5). Так как она соответствует пункту А3, в котором себестоимость продукции наименьшая. Стоимость доставки в этой клетке положим равной 100:с35=100.

ПОТРЕБИТЕЛИ ПОСТАВЩЕКИ		В1	В2	В3	В4	В5
		146	131	201	178	167
А1	320	8	15	8	9	0
А2	198	11	12	3	4	0
А3	305	11	7	4	5	100

 

1) Математическая   модель  прямой задачи:

 

Z=8*х11+15*х12+8*х13+9*х14+11*х21+12*х22+3*х23+4*х24+11*х31+

     +7*х32+4*х33+5*х34→min

 

Система ограничений для поставщиков:

х11+х12+х13+х14+х15=320

х21+х22+х23+х24+х25=198

х31+х32+х33+х34+х35=305

 

система ограничений для потребителей:

х11+х21+х31 =146

х12+х22+х32 =131

х13+х23+х33 =201

х14+х24+х34 =178

х15+х25+х35 =167

xij>0,  i=1,3;  j=1,5.

 

Математическая модель двойственной задачи :

Z'=320*u1+198*u2+305*u3+146*v1+131*v2+201*v3+178*v4+167*v5→max

 

                                            ui+vj <cij ,

                      ui , vj  - произвольного знака.

 

где ui – условные оценки поставщиков (i=1,3),

       vj – условные оценки потребителей (j=1,5).

     

 

          Экономический смысл переменных :

 

xij – количество груза перевозимых от i-uj поставщика j-му потребителю;

cij – стоимость перевозки единицы продукции от i-го поставщика j-му потребителю;

Z  – целевая функция прямой задачи (сумма затрат);

Z' – целевая функция двойственной задачи (суммарная потенциальная прибыль от перевозки продукции);

ui  –  потенциал i-го поставщика (условная оплата перевозчику за вывоз единицы груза из i-го пункта отправителя);

vj  –  потенциал j - го потребителя (условная оплата перевозчику за доставку единицы груза в j-ый пункт назначения);

 

 

2) Для построения начального опорного плана применяем метод наименьшего элемента. Количество базисных клеток в невырожденном плане

 r=m+n-1=3+5-1=7.

 

 

ПОТРЕБИТЕЛИ ПОСТАВЩЕКИ		В1	В2	В3	В4	В5	ui
		146	131	201	178	167
А1	320	146 86	7-W 15	+W 8	9	167 0	u1=0
А2	198	11	12	198 3	4	0	u2=-9
А3	305	11	124+W 7	3-W 4	178 5	100	u3=-8
vj		v1=8	v2=15	v3=12	v4=13	v5=0	W=3

 

        Применим метод потенциалов. Для базисных клеток составим систему управлений

ui+vj=cij получаем  систему управлений:

u1+v1=c11=8       u1+v2=c12=15         u1+v5=c15=0        u2+v3=c23=3    

u3+v2=c322=7         u3+v3=c33=4            u3+v4=c34=5     

       Так как переменных на 1 больше, чем уравнений, то обнулим переменную

u1=0. Тогда система уравнений имеет следующее решение: v1=8, v2=15, v3=12,

v4=13, v5=0, u2= -9, u3= -8.

        Проверим условие оптимальности, т.е. выполнение неравенства

ui+vj <cij  для свободных клеток:

 

u1+v3<с13    0+12=12>8            - ∆13= -4

u1+v4<с14    0+13=13>9            - ∆13= -4

u2+v1<с21    -9+8= -1<11         +         

u2+v2<с22    -9+15=6<12          +

u2+v4<с24    -9+13=4=4

u2+v5<с25    -9+0=-9<0            +         

u3+v1<с31    -8+8=0<11            +         

u3+v5<с35    -8+0=-8<100          +         

           В клетке (1;3) неравенство  не выполняется на 4, а в клетке (1;4)-на 4.

Ставим в клетку (1;3) коэффициент W со знаком «+».

           Контур перераспределения груза  проходит через клетки (1;3); (3;3); (2;3); (1;2).

W=min {3,7}=3.

 

     Вычисляем  новую таблицу с учетом перераспределения  груза и проверяем ее на  оптимальность.

 

ПОТРЕБИТЕЛИ ПОСТАВЩЕКИ		В1	В2	В3	В4	В5	ui
		146	131	201	178	167
А1	320	146 8	4-W 15	3+ W 8	9	167 0	u1=0
А2	198	11	12	198-W 3	+W 4	0	u2=-5
А3	305	11	127+W 7	4	178-W 5	100	u3=-8
vj		v1=8	v2=15	v3=8	v4=43	v5=0	W=4

 

 

       Для  базисных  клеток составим систему уравнений ui+vj <cij . Получаем систему уравнений:

 

u1+v1=c11=8       u1+v2=c12=15         u1+v3=c13=8        u1+v5=c15=0    

u2+v3=c23=3         u3+v2=c32=7              u3+v4=c34=5     

 

       Так как переменных на 1 больше, чем уравнений, то обнулим переменную

u1=0.  Тогда система уравнений имеет следующее решение: v1=8, v2=15, v3=8,

v4=13, v5= 0, u2= -5, u3= - 8.

 

       Проверим  условие оптимальности, т.е. выполнение  неравенства ui+vj <cij  для свободных клеток:

 

u1+v4<с14    0+13=13>9            -    ∆24=-4                       

u2+v1<с21    -5+8= 3<11           +    

u2+v2<с22    -5+15=10<12        +              

u2+v4<с24    -5+13=8>4            -       ∆24=-4             

u2+v5<с25    -5+0= -5<0            +

u3+v1<с31    -8+8=0<11           +

u3+v3<с33    -8+8=0<4              +

u3+v5<с35    -8+0= -8<100       +

 

            В клетке (1;3) и (1;4 ) неравенство  не выполняется на 4, Ставим в клетку (1;3) коэффициент W со знаком «+».

 

           Контур перераспределения груза проходит через клетки (1;3); (3;3); (2;3); (1;2).

W=min {3;7}=3.

          

 

 

         Вычисляем новую таблицу с учетом перераспределения груза и проверяем ее на оптимальность.

 

ПОТРЕБИТЕЛИ ПОСТАВЩЕКИ		В1	В2	В3	В4	В5	ui
		146	131	201	178	167
А1	320	146 8	15	7 8	9	167 0	u1=0
А2	198	11	12	194 3	4 4	0	u2= -5
А3	305	11	131 7	4	174 5	100	u3= -4
vj		v1=8	v2=11	v3=8	v4=9	v5=0