Рішення транспортної задачі лінійного програмування
6. Приклад рішення транспортної задачі
У місті 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 |
Вартість 3-його плани:
D3=1* 35+2* 15+0,4* 5+1* 15+0,8* 40+1* 35+1,5* 35+2,5* 40=301,5.
Маємо:u1+v6-c16 =0,3>0,u3+v5-c35 =0,3>0. => За критерієм оптимальності, третій план не оптимальний. Далі max(0,3;0,3)=0,3. => Помістимо перевезення в клітку А3У5, змістивши 40=min (40,40) по циклі, зазначеному в таблиці штрихом. Одержимо нову таблицю. Щоб 4-й план був не виродженим, залишимо в клітці А4У5 нульове перевезення. Знайдемо потенціали: u1+v1=1,u1+v2=2,u2+v1=0,4,u3+v2=1, u4+v5=2,5, u2+v3=1, u4+v4=1,5, u3+v5=1,5 , u4+v6=0. Покладемо u1=0,тоді v1=1,u2=-0,6,v2=2,v4=1,5, u3=-1,u4=0, v3=1,6, v5=2,5, v6=0. Складемо таблицю:
Магазини Склад |
B1 (b1=40) v1=1 |
B2 (b2=50) v2=2 |
B3 (b3=15) v3=1,6 |
B4 (b4=75) v4=1,5 |
B5 (b5=40) v5=2,5 |
B6 (b6=5) v6=0 |
|
А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 |
1,2 |
2,0 |
2,0 |
1,5 |
2,5 |
0 |
Вартість 4-ого плани: D4=1* 35+2* 15+0,4* 5+1* 15+1* 35+1,5* 40+1,5* 75=289,5.
Для всіх кліток останньої таблиці виконані умови оптимальності:
1)ui+ vj-сij=0 для кліток, зайнятих перевезеннями;
2)ui+ vj-сij ?0 для вільних кліток.
Незмістовні відповіді:
Прямій ЗЛП:
35 15 0 0 0 0
5 0 15 0 0 0
X = 0 35 0 0 40 0
0 0 0 75 0 5
min=289,5.
Двоїстої ЗЛП:
U1=0 ; U2=-0,6 ; U3=-1 ; U4=0 ; V1=1 ; V2=2 ; V3=1,6 ; V4=1,5 ; V5=2,5 ; V6=0.
max=289,5.
Тому що min=max, те за критерієм оптимальності знайдені оптимальні рішення прямої й двоїстої ЗЛП. Змістовна відповідь: Оптимально перевозити так:
З А1 в B1 - 35 рулонів полотна;
З А1 в B2 - 15 рулонів полотна;
З А2 в B1 - 5 рулонів полотна;
З А2 в B3 - 15 рулонів полотна;
З А3 в B2 - 35 рулонів полотна;
З А3 в B5 - 40 рулонів полотна;
З А4 в B4 - 75 рулонів полотна.
При цьому вартість мінімальна й складе Dmin=289,5.5 рулонів полотна необхідно залишити на складі А4 для їхнього наступного перевезення в інші магазини.
7. Висновки
У курсовій роботі викладені основні підходи й методи рішення транспортної задачі, що є однієї з найпоширеніших задач лінійного програмування. Рішення даної задачі дозволяє розробити найбільш раціональні шляхи й способи транспортування товарів, усунути надмірно далекі, зустрічні, повторні перевезення. Все це скорочує час просування товарів, зменшує витрати підприємств і фірм, повязані зі здійсненням процесів постачання сировиною, матеріалами, паливом, устаткуванням і т.д.
Алгоритм і методи рішення транспортної задачі можуть бути використані при рішенні деяких економічних задач, що не мають нічого загального із транспортуванням вантажу. У цьому випадку величини тарифів cij мають різний сенс залежно від конкретної економічної задачі.
Література
1. Ковальов А.В., Сакович В.А., Холод Н.І. Вища математика. Математичне програмування. - К., 2001
2. Красс М.С., Чупринов Б.П. Основи математики. - К., 2001
3. Єрмаков В.І. Загальний курс вищої математики для економістів - К., 2006
4. Акулич І.Л. Математичне програмування в прикладах і задачах. - К., 1993.
5.Воробйов Н.Н. Основи теорії ігор. - К., 1984.
6.Прохоров Г.В., Колбєєв В.В., Желнов К.І., Леденев М.О..Математичний пакет Maple V Release 4. - К., 1998