Рішення транспортної задачі лінійного програмування

курсовая работа

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

А22=20)

0,4

3,0

1,0

2,0

3,0

А33=75)

0,7

1,0

1,0

0,8

1,5

А44=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

А22=20)

0,4

3,0

1,0

2,0

3,0

0

А33=75)

0,7

1,0

1,0

0,8

1,5

0

А44=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

А22=20)

0,4

3,0

1,0

2,0

3,0

0

А33=75)

0,7

1,0

1,0

0,8

1,5

0

А44=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

А22=20)

U2=-1,3

0,4

3,0

1,0

2,0

3,0

0

А33=75)

U3=-1

0,7

1,0

1,0

0,8

1,5

0

А44=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

А22=20)

U2=-0,6

0,4

3,0

1,0

2,0

3,0

0

А33=75)

U3=-1

0,7

1,0

1,0

0,8

1,5

0

А44=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

А22=20)

U2=-0,6

0,4

3,0

1,0

2,0

3,0

0

А33=75)

U3=-1

0,7

1,0

1,0

0,8

1,5

0

А44=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

А22=20)

U2=-0,6

0,4

3,0

1,0

2,0

3,0

0

А33=75)

U3=-1

0,7

1,0

1,0

0,8

1,5

0

А44=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

Делись добром ;)