Транспортная задача

 bn+1 = å аi - å bj ( где i=1,...,m ; j=1,...,n ) ,

а стоимость перевозок из всех пунктов отправления в фиктивный пункт назначения bn+1 будем считать равной нулю. Введением фиктивного пункта назначения B n+1 с его заявкой bn+1 мы сравняли баланс транспортной задачи, и теперь ее можно решать, как обычную транспортную задачу с правильным балансом.

 

4 Транспортная задача с избытком заявок

 

Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления Am+1 с запасом am+1 равным недостающему запасу, и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равной нулю.

Задача, двойственная к транспортной.

Построим задачу, двойственную к транспортной. С этой целью вспомним, что каждому пункту отправления Ai и назначения Bj отвечает определенное ограничение

                                          (6.1)

В то же время каждому ограничению из (6.1) сопоставляется определенная неизвестная в двойственной задаче. Тем самым устанавливается соответствие между всеми пунктами Ai и Bj и всеми неизвестными двойственной задачи.

Обозначим неизвестную в двойственной задаче, отвечающую пункту отправления Ai, через ui(i=1,..,n), а пункту назначения Bj – через vj(j,…m).

Каждому неизвестному в транспортной задаче соответствует ограничение, связывающее неизвестные в двойственной задаче. Неизвестное xij входит ровно в два ограничения системы (6.1): одно из них отвечает пункту Ai, а другое – пункту Bj. В обоих этих уравнениях коэффициент при xij равен 1. Поэтому соответствующее xij ограничение в двойственной задаче имеет вид

 

  .                               (6.2)

Правая часть неравенства (6.2) равна cij, потому что именно с этим коэффициентом неизвестная xij входит в минимизируемую формулу (2.4).

Оптимизируемая форма двойственной задачи имеет вид

                                          (6.3)

Таким образом, задача двойственная к транспортной формулируется следующим образом. При ограничениях (6.2) максимизировать формулу (6.3). Подчеркнем, что знак значений неизвестных ui(i=1,…,n) и vj(j,…,m) может быть произвольным.

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

В итоге приходим к соотношению:

ui + vj ≤ cij (для всех свободных неизвестных xij)                     (6.4)

Тем самым мы убеждаемся, что признак оптимальности в работе по методу потенциалов совпадает с необходимым и достаточным условием оптимальности.

 

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

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

 

Магазины Склад	B1 (b1=40)	B2 (b2=50)	B3 (b3=15)	B4 (b4=75)	B5 (b5=40)
А1 (а1=50)	1,0	2,0	3,0	2,5	3,5
А2(а2=20)	0,4	3,0	1,0	2,0	3,0
А3(а3=75)	0,7	1,0	1,0	0,8	1,5
А4(а4=80)	1,2	2,0	2,0	1,5	2,5

В данном случае Σai=225 >Σbj=220 => имеем дело с открытой моделью транспортной задачи. Сведем ее к закрытой введением фиктивного магазина B6 с потребностью b5=225-220=5 и стоимостью перевозок сi6=0.Имеем таблицу:

 

Магазины Склад	B1 (b1=40)	B2 (b2=50)	B3 (b3=15)	B4 (b4=75)	B5 (b5=40)	B6 (b6=5)
А1 (а1=50)	1,0	2,0	3,0	2,5	3,5	0
А2(а2=20)	0,4	3,0	1,0	2,0	3,0	0
А3(а3=75)	0,7	1,0	1,0	0,8	1,5	0
А4(а4=80)	1,2	2,0	2,0	1,5	2,5	0

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

 x11 x12 x13 x14 x15 x16

x21 x22 x23 x24 x25 x26

X = x31 x32 x33 x34 x35 x36 - матрица перевозок.

x41 x42 x43 x44 x45 x46

min(x11+2x12+3x13+2,5x14+3,5x15+0,4x21+3x22+x23+2x24+3x25+0,7x31+x32+x33+0,8x34+1,5x35++1,2x41+2x42+2x43+1,5x44+2,5x45)

 

 

 

 

 

(1)

x11+x12+x13+x14+x15+x16=50

x21+x22+x23+x24+x25+x26=20

x31+x32+x33+x34+x35+x36=75

x41+x42+x43+x44+x45+x46=80

x11+x21+x31+x41=40 (2)

x12+x22+x32+x42=50

x13+x23+x33+x43=15

x14+x24+x34+x44=75

x15+x25+x35+x45=40

x16+x26+x36+x46=5

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

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

max(50u1+20u2+75u3+80u4+40v1+50v2+15v3+75v4+40v5+5v6) (1*)

u1+v1≤1

u1+v2≤2

u1+v3≤3 (2*)

u1+v4≤2,5

u1+v5≤3,5

u1+v6≤0

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

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

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

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

5) x12=50 и 1-ю строку и 2-ой столбец исключаем и x32=0. 6) x43=150 и 3-ий столбец исключаем.7) x45=40 и 5-ый столбец исключаем.x46=5.Составим таблицу. Здесь и далее в нижнем правом углу записываем значение перевозки.

 

 

 

 

 

Магазины Склад	B1 (b1=40)	B2 (b2=50)	B3 (b3=15)	B4 (b4=75)	B5 (b5=40)	B6 (b6=5)
А1 (а1=50)	1,0	2,0	3,0	2,5	3,5	0
А2(а2=20)	0,4	3,0	1,0	2,0	3,0	0
А3(а3=75)	0,7	1,0	1,0	0,8	1,5	0
А4(а4=80)	1,2	2,0	2,0	1,5	2,5	0

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

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

Будем улучшать этот план методом потенциалов: ui- потенциал Аi ,

vj- потенциал Bj. Тогда u1+v2=2, u2+v1=0,4, u3+v1=0,7, u3+v2=1, u3+v4=0,8, u4+v3=2, u4+v4=1,5, u4+v5=2,5, u4+v6=0.  Положим u1=0,тогда v2=2,

u3=-1,v1=1,7,v4=1,8, u2=-1,3,u4=-0,3, v3=2,3,v5=2,8,v6=0,3.Составим таблицу:

 

Магазины Склад	B1 (b1=40) v1=1,7	B2 (b2=50) v2=2	B3 (b3=15) v3=2,3	B4 (b4=75) v4=1,8	B5 (b5=40) v5=2,8	B6 (b6=5) v6=0,3
А1 (а1=50) U1=0	1,0	2,0	3,0	2,5	3,5	0
А2(а2=20) U2=-1,3	0,4	3,0	1,0	2,0	3,0	0
А3(а3=75) U3=-1	0,7	1,0	1,0	0,8	1,5	0
А4(а4=80) U4=-0,3	1,2	2,0	2,0	1,5	2,5	0

 

В верхнем левом углу здесь и далее записываем значение ui+vj-cij. Имеем: u1+v1--c11 =0,7>0, u1+v6-c16 =0,3>0, u3+v3-c33 =0,3>0, u3+v5-c35 =0,3>0,

u4+v1-c41 =0,2>0. => По критерию оптимальности, первый план не оптимален. Далее max(0,7;0,3;0,3;0,3;0,2)=0,7. => Поместим перевозку в клетку А1В1, сместив 20=min(20,50) по циклу, указанному в таблице штрихом. Получим новую таблицу. Найдем потенциалы: u1+v1=1,u1+v2=2,u2+v1=0,4,u3+v2=1, u3+v4=0,8, u4+v3=2, u4+v4=1,5, u4+v5=2,5 , u4+v6=0. Положим u1=0,тогда v1=1,u2=-0,6,v2=2,v4=1,8, u3=-1, u4=-0,3,v3=2,3,v5=2,8,v6=0,3. Составим таблицу:

 

Магазины Склад	B1 (b1=40) v1=1	B2 (b2=50) v2=2	B3 (b3=15) v3=2,3	B4 (b4=75) v4=1,8	B5 (b5=40) v5=2,8	B6 (b6=5) v6=0,3
А1 (а1=50) U1=0	1,0	2,0	3,0	2,5	3,5	0
А2(а2=20) U2=-0,6	0,4	3,0	1,0	2,0	3,0	0
А3(а3=75) U3=-1	0,7	1,0	1,0	0,8	1,5	0
А4(а4=80) U4=-0,3	1,2	2,0	2,0	1,5	2,5	0

 

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

D2=1•20+2•30+0,4•20+1•20+0,8•55+2•15+1,5•20+2,5•40=312.

Имеем:u1+v6-c16 =0,3>0, u2+v3-c23 =0,7>0, u3+v3-c33 =0,3>0,

u3+v5-c35 =0,3>0. => По критерию оптимальности, второй план не оптимален. Далее max(0,3;0,7;0,3;0,3)=0,7 => Поместим перевозку в клетку А2В3, сместив 15=min(20,30,55,15) по циклу, указанному в таблице штрихом. Получим новую таблицу. Найдем потенциалы: u1+v1=1,u1+v2=2,u2+v1=0,4,u3+v2=1, u3+v4=0,8, u2+v3=1, u4+v4=1,5, u4+v5=2,5 , u4+v6=0. Положим u1=0,тогда v1=1,u2=-0,6,v2=2,v4=1,8, u3=-1, u4=-0,3,v3=1,6, v5=2,8, v6=0,3. Составим таблицу:

 

 

 

 

 

 

 

 

 

 

 

Магазины Склад	B1 (b1=40) v1=1	B2 (b2=50) v2=2	B3 (b3=15) v3=1,6	B4 (b4=75) v4=1,8	B5 (b5=40) v5=2,8	B6 (b6=5) v6=0,3
А1 (а1=50) U1=0	1,0	2,0	3,0	2,5	3,5	0
А2(а2=20) U2=-0,6	0,4	3,0	1,0	2,0	3,0	0
А3(а3=75) U3=-1	0,7	1,0	1,0	0,8	1,5	0
А4(а4=80) U4=-0,3	1,2	2,0	2,0	1,5	2,5	0