3. Транспортна задача лінійного програмування Формолювання задачі icon

3. Транспортна задача лінійного програмування Формолювання задачі




Скачати 228.39 Kb.
Назва3. Транспортна задача лінійного програмування Формолювання задачі
Дата20.09.2012
Розмір228.39 Kb.
ТипЗадача

3. Транспортна задача лінійного програмування

3.1. Формолювання задачі

Транспортна задача представляє собою задачу ЛП, котру можно вирішувати симплекс-методом. Але специфічна структура умов задачі дозволяє використовувати більш простіший обчислювальний метод, котрий, недивлячись на різнобіжності відтворює кроки сімплекс-алгоритма.

Загальна формуліровка транспортної задачі полягає в наступному:

необхідно скласти план перевозок однорідного грузу із m пунктів відправлення А1, А2, .... Аm, в кожному із яких є в наявності а1, .... аm одиниць грузу пунктів призначення В1, В2, .... Вn з заявками Ь1, Ь2, ..., Ьn одиниць грузу, щоб задовольнити всіх споживачів та мінізувати сумарну вартість перевозок. Вартість Сig перевозки одиниць вантажу із А, в В, відомо. При цьому передбачається, що загальний запас грузу в пунктах відправлення дорівнює сумарній потребі (сумі всіх заявок) пунктів споживання, т.е.

. (3.1)

На мал. 1 показана транспортна модель у вигляді мережи з пунктами відправлення і пунктами призначення.





Пункти відправлення Пункти призначення

Мал. 1

Так як розглядається тільки один вид вантажа, замовлення пункту призначення можуть задовольнятися із деяких пунктів відправлення. Крім того, величина транспортних расходів прямо пропорційна кількості вантажа, яки перевозяться.

3.2. Математична модель

Нехай x,j - кількість вантажа, відправляємого з пункта відправлення А, в пункт В.

Тоді цільова функція

L = - це сумарна вартість

всіх перевезень, котру при складанні плана перевозок необхідно. мінімізувати


Очевидно, що система невідомих зміных хij повинна зодовольняти умовам:

, i=1 , m , (3.2)

j=1 , n , (3.3)


Хijj>0, для всех i uj.

Таким чином, маємо типову задачу лінійного програмувания з mn змінними та m+n обумовленнями в вигляді рівнянь.Якщо выконується умова (3.1), тоді така модель називаеться збалансованною транспортною модел’ю. В сбалансованній моделі не всі m+n рівняннь сформованної задачі є лінійно незалежними. Дійсно, якщо сумуємо всі рівняння (3.2.) и всі рівняння (3.3.), за умовою (3.1.) ми отримуємо те ж саме. Таким чином, одне з m+n рівняннь опиняється залежнимым, тобто сбалансованна транспортна модель вміщує m+n-1 незалежних рівняннь. Тому, як і в сімплекс-методі, базісне допустиме рішення повинне мати m+n-1 базісну зміну. Кількість небазісных змінных дорівнює m-n-(m+n-1)=(m-1)-(n-1).

Приклад складання математичної моделі транспортної задачі.

На трьох базах Аi (i=1.3) сосредоточено а=|| 15, 25, 5|| одиниць вантажу, які необхідно доставити на 4 пункти прийому Bj (j=1,4) у кількості Ь=|| 5, 15, 15, 10||. Вартість перевозок Сij однієй одиниці вантажу з i-ой базы до j пункту прийому задана матрицею:

10 20 0 11

C = 12 7 9 20

0 14 16 18


Необхідно скласти математичну модель данної задачі.

Рішення:

Обозначимо через Хij (i=1,3; j=1,4) - кількість одиниць вантажу, які перевозяться з i-го пункту відтправлення в j пункт призначення.

Тоді необхідно знайти такі xij, щоб мінімізувати цільову функцію виду

L= 10x11+20x13+11 х14+12x21 +7х22+9х23+20х24+14Х32+16Хзз+18Х34, при обумовленнях

X11+X12+X13+X14=15;

X21+X22+X23+X24=25;

X31+X32+X33+X34=5;

X11+X21+X31=5;

X12+X22+X32=15;

X13+X23+X33=15;

X14+X24+X34=10;

XijO для всех i u j

Як видно, основною відмінністю транспортної задачі від загальной задачі ЛП є те, що у всіх обумовленнях невідомі xij входять з коефіцієнтом, якій дорівнює одиниці, та всі обумовлення мають вид рівнянь.

3.3. Рішення транспортної задачі

Рішення транспортної задачі здійснюється покроково за допомогою спеціальної транспортної таблицї (табл. 1). Табл.1


ПН ПО

B1

B2



Bn

ai

A1

c11

c12



c1n

a1

A2

c21

c22



c2n

a2











a..

Am

cm1

cm2



cmn

am

bi

b1

b2



bn




Крок 1.

Пошук оптимального плана перевозок, як і в загальнії задачі ЛП починається з находження початкового базісного рішення (початкова вершина випуклого богатогранніка області допустимих значеннь). Для цього використовують процедуру, яка основана на так званому правелі південно-західного кута. Побудова початкового рішення згідно з цим правилом починається з лівого верхнього кута транспортної таблиці. Розподіл вантажу з першого пункту відтправлення відбувається таким чином, що спочатку максимально задовольняються замовлення першого споживача, потім другого и т.д. до повного розподілу вантажа, який є в А1. Далі подібним чином розподіляється вантаж із другого пункта відправлення, третього і т.д. При виконанні обумовлень на об’ем вантажу у пунктах відправки або попита на пунктах призначення відповідно строка (стовбець) транспортної таблиці виключається з подальшого заповнення. Якщо обумовлення, які подані стовбцом або строкою, виконуються одночасно, то можно виключити його из подальшего заповнення або стовбец або строку, а в клітині, яка відповідає наступному південно-західному куту поставити значення змінної, яка дорівнює нулеві (див. приклад, табл. 2). Це правило автоматично гарантує знаходження нульових базісних змінних, якщо такі зустрічаються.

^ Приклад знаходження початково базісного рішення.

Застосуємо описан процедуру до транспортної таблиці 2. Табл.2



B1

B2



Bn

ai

A1

4

5

2

5

1

4

10

A2

3

1

5

2

0

4

5

A3

2

5

3

8

4

7

15

bj

5

10

8

7




1. Х11=5, стовбец 1 виключаєтся із розглядання. Чим в першому стовчику неможна більше проводити ніяких операцій.

2. В новому південно-західному куті беремо х12=5 та строку 1 висключаємо із розглядання.

3. Новий південно-західний кут x22=5. Стовбец і строка 2 одночасно призводять до виконання відповідних обумовленнь. Якщо виключається із розглядання стовбець 2, тоді на наступному крокі у південно-західному куті змінна х23 опиняється базісною з нульовим значенням, так як величина запропонованного вантажу із другого пункту призначення вже вичерпана. Можна було б виключити із розглядання строку 2, тоді змінна Хзг опиняється нульовою базісною змінною.

4. Хзз=8, стовбець 3 виключається із розглянення.

5. Хз4=7, виключається із розглянення або стовбець 4 або строка 3.

Процес знаходження початкового базісного рішення закінчується, коли залишається не виключеною із розглядання точно одна строка або один стовбець. Зайняті клітини транспортної таблиці, в тому числі і з нулями, називаються базісними, а пусті - небазісними. Початкове рішення в таблиці 2 вміщує необхідну кількість базісних змінних, яке дорівнює m+n-1=3+4-1=6, залишенні (m-1)(n-1)=2-3=6 небазісні змінні, відповідні пустим клітинам транспортної таблиці, дорівнюють нулю. Використання правила південно-західного кута завжди призводить до необхідної кількості базісних змінних.

Так як при побудові початкового плану вартості перевозок не враховувалися, то в загальному випадку отриманний план перевезень, хоча й задовольняє всім обумовленням (є базісним), не є оптимальним. Щоб покращити рішення треба перейти допевним чином обраної другої вершини області допустимих значень, що і виконується на наступному крокі.

Крок 2.

На другому крокі із кількості небазісних змінних визначається та, яка буде вводитися у базісні змінні. Якщо всі небазісні змінні задовольняють умові оптимальності, тоді данна транспортна таблиця є оптимальною. Для знаходження вводимої до базісу небазісної змінної використовується метод потенціалов.

В методі потенціалов строке i та стовбцю j транспортної таблиці ставляться у відповідності числа ui, и vj. Для кажної базісної змінної хij поточного решення потенціали ui vj повинні задовольняти рівнянню

ui + vj = cij. (3.4.)


Ці рівняння призводять до системи, яка вміщує m+n-1 рівняннь (так як всього є m+n-1 базісних змінних), в яких фігурують m+n невідомих. Значення потенціалів легко визначити із цієї системи, надаючи одному із них будь-яке значенне (як завжи ui покладаєтся рівним нулю), а далі вирішуя систему із m+n-1 рівняннь відносно m+n-1 залишившихся потенціалів. Дійсно, так як кожне наступне рівняння системи, який має тільки дві змінні, вміщує одну із змінних, яка входить в попереднє рівняння, а в першому рівнянні змінна u1 =0, то всі залишившиєся змінні знаходяться шляхом підставлення.


Приклад знаходження потенціалів

Стосовно транспортної таблицї 2 маємо:

u1+V1=4;

u1+V2=2;

u2+V2=1;

u2+V3=2;

u3+V3=3;

u3+V4=4.

Прийнявши u1=0, отримаємо значення потенціалів v1=4, v2=2, u2=-1, v3 =3, u3=0, v4=4. Рівняння ui+Vj=Cij мають настільки просту структуру, що їх не треба і записувати у явному вигляді. Потенціали визначаються безпосередньо із транспортної таблиці.

Для включення в базіс обираєтьяс та базісна змінна, для якої величина


Zij=Cij - (ui +Vj) , (3.5)


є від”ємною та самою великою за модулем.


^ Теорема (критерій)оптимальності

Необхідною та достатньою умовою оптимальності плана перевезень є невід’ємність всіх


zij=Cij - (ui + Vj).


Якщо опорний план є оптимальним, то обчислення на цьому закінчуються, в іншому випадку здійснюється перехід до кроку 3.

КрокЗ.

З кількості змінних поточного базісу обирається та, яку необхідно вивести із базісу. Далі знаходиться нове базісне рішення і виконується повернення до кроку 2. Так як кількість вершин області допустимих значннь обумовлено, то за кінцеву кількість кроків отримуємо оптимальне значення транспортної задачі. Крок 3 еквивалентен використанню умови допустимості в сімплекс-методі. Разом з тим, так як всі коефіцієнти в умовленнях транспортної задачі дорівнюють або нулю, або одиниці. Відношення, які використовуються при перевіркі умови допустимості, завжди будуть мати знаменник, рівний одиниці. Тому значеня базісних змінних одразу дають відповідні відношення.

Для визначення мінімального відношення побудуємо замкнутий цикл, якій відповідає вводимій змінній. Цикл складається тільки з горизонтальних та вертикальних відрізків, однією з вершин якого є обранная вводимая небазісная змінна, а залишившимися вершинами - базісниє змінні (зайняті клітини). Табл.3 ілюструє цикл, відповідающий змінній яку вводимо х31 для початкового базісного рішення отриманного методом південно-західного кута. Цей цикл можно відобразити за допомогою змінних наступним чином:

x31 x11 x12 x22 x24 x31


Таблиця 3






B1

B2

B3

B4

ai

ui

A1

10

5(-)

0

10

20

11

15

0

A2

12

7

5 (-)

9

15

20

5 (+)

25

7

A3

0

(+)

14

16



18

5 (-)

5

5

bj

5

15

15

10

45




vj

10

0

2

13







Правило. Несуттєво, в якому напрямку (за часовою або проти часової стрілки ) проходить обхід циклу.

Щоб план перевезень опинився допустимим, необхідино збільшити перевозку в вершинах циклу, які відміченні знаком (+), та зменшити в відмічених знаком (-). Щоб новий план був базісним, в змнну, яку вводимо необхідно загрузити по можливості максимально. Величина вантажа Q, яка задовольняє цій умові, визначається мінімальним значенням перевезень, які стоять у від’ємніх вершинах циклу.

У розглядаємій табл.3 прикладу

Θ = min{5, 5, 5} = 5.

Змінній, яка виводиться із базісу, ставиться та, котра знаходиться у від’ємній вершині та має найменше значення, так як саме вона раніше всіх доходить о нуля, та наступні зменшення роблять її від’ємною.

Нові базісні рішення представлені в табл. 4.





B1

B2

B3

B4

ai

ui

A1

10

(-)

0

(+)

20

11

15

0

A2

12

(+)

7

(-)0

9

15

20

10

25

7

A3

0

(+)

14

16



18

5

5

bj

5

15

15

10

45




vj

10

0

2

13








Так як в розглянутому прикладі три змінні x11,x22 и x32 , які знаходться у від’ємних вершинах мають одне й те ж мінімальне значення, равноє 5, то в цьому випадку будь-яку з них можна виключити із базіса. В таблиці 4 виключено із базісу змінну х34.

Базісне рішенне в табл.4 вироджене, так як маються нульові базісні змінні x11 и х22. Але виродженність не потребує додаткових засобір безпечності, з нульовими базісними змінними опрують також як і зі змінними, які мають додатні значення.

Підкреслимо, що для кожного базісного рішення та відповідній небазісній змінній можна побудувати лише один цикл.

Оптимальність нового базісного рішення (табл 4.) перевіряється обчисленням нових потенціалів.

Найбільша по модулю від’ємна величина zij відповідає небазісній змінній х21. Замкнутий цикл для х21 показує, що змінною, яку виключають із базіса може бути як х11 так і х22. Оберемо за таку змінну х11. В табл.5 показано нове базісне рішення. Значення потенціалів обчислюється знову.


Таблиця 5




B1

B2

B3

B4

ai

ui

A1

10


0

15 (-)

20

11

(+)

15

0

A2

12

0

7

0 (+)

9

15

20

10 (-)

25

7

A3

0

5

14

16



18



5

5

bj

5

15

15

10

45




vj

5

0

2

13








^ В таблиці 5 змінною, яку вводять в базіс, та змінній, яку виключають є x14 и x24, відповідно. Нове решення показано в таблиці 6.

Tаблиця 6.




B1

B2

B3

B4

ai

ui

A1

10


0

5

20

11

10

15

0

A2

12

0

7

10

9

15

20



25

7

A3

0

5

14

16



18



5

5

bj

5

15

15

10

45




vj

5

0

2

11







Так як всі Zij в таблиці 6 невід’ємні, то отримуємо рішення, яке оптимально. Максимальні сумарні транспортні витрати складають: minL=5*0+10*11+10*7+15*9+5*0=315.

3.4. Метод найменьшої вартості

Метод південно-західного кута, який використовується для визначення початкового рішення, не обов’язкоов надає початкове рішення, близьке до оптимального. Для зменшення кількості кроків, які необхідно зробити від початкового рішення до оптимального, використовують метод нийменьшої вартості. Цей метод дає можливість отримати поліпшенне початкове рішення. Побудова початкового рішення по цьому методу виконується наступним чином. Обирається змінна, якій відповідає найменьша вартість по всій таблиці , та їй надається можливість більшого значення. Якщо таких змінних декілька, то береться будь – яка з них. Виключається із подальшого заповнення відповідна строка (стовбець) транспортної таблиці. Якщо обумовлення по стовбцю та стокі виконуються одночасно, то як і в методі південно-західного кута, викреслюється або стовбець, або строка. Процес повторюється при можливо більшому значенні тієї змінної, якій відповідає мінімальна вартість між викресленних.

Проілюструємо метод на прикладі транспортної задачі із табл. 3.

В табл. 7 початкове рішення отримане методом наіменьшої вартості.


Таблиця 7





B1

B2

B3

B4

ai

ui

A1

10

0

0

5

20

11


15

0

A2

12


7

0

9

15

20

10

25

7

A3

0

5

14

16



18



5

-10

bj

5

15

15

10

45




vj

10

0

2

13








Ця таблиця дорівнює таблиці 4, яка отримана при використанні метода південно-західного кута тільки на другому крокі. Далі рішення продовжується за алгоритмом, який розглянуто вище.. Очевидно, що при методі наіменьшої вартості оптимальне рішення буде знайденне за меньшу кількість кроків.


3.5. Інші різновідності транспортних моделей

У випадку несбалансованої транспортної моделі замовлення перевищують кількість вантажа на пунктах відправлення або навпаки, кількість вантажа більше суми всіх замовленнь. Тоді задача зводиться до збалансованої транспортної задачі, шляхом введення додаткового фіктивного шляха призначення або пункта відправлення з замовленням (запасом вантажа), який дорівнює не вистачающої величини. Так як насправді такого пункту немає, то ніякі перевозкі, пов’язанні з цим пунктом в дійсності не виконаються і відповідна вартість перевезення одиниці продукції приймається рівною нулю.

ТЕСТИ

(вірно (В) или невірно (Н)?)

1. В методі вирішення транспортної задачі, фактично, використовиваються кроки сімплекс-метода.

2. Якщо до всіх коефіцієнтів cij додати одне і теж число, то оптимальне значення xij змінюється.

3. Збалансованна транспортна задача може не мати допустимих рішень.

4. Транспортну задачу завжди можно сбалансувати.

5. Для сбалансування однієї і тієї же транспортной задачі можуть знадобитися як фиктивні пункти відправлення, так і фиктивні пункти призначення.

6. Якщо в сімплекс-методі і методі рішення транспортної задачі використовується одне і теж початкове базісне рішення, то итераціі в обох випадках, фактично, співпадають.

7. Для кожної свободної клітини транспортної таблиці може існувати декілько ціклів, одна вершина якого лежить в данній свободній клітинці, а решта - в базісних клітинах.

8. Коефіцієнти при невідомих в рівняннях транспортної задачі дорівнюють одинице.

9. Метод південно-західного кута і метод наіменьшої вартості використовиваються тільки на першому крокі рішення транспортної задачі.

10. Метод наименьшої вартості в загальному випадку дозволяє вирішити транспортну задачу за меньшу кількість кроків, ніш метод південно-ззахідного кута.

11. Метод потенціалів дозволяє полегшити процедуру находження змінної, яка вводиться в базіс.

12. Кількість базісних змінних в транспортнії задачі дорівнює (т-1 )(п-1).

13. Кількість небазісних змінних в транспортнії задачі дорівнює m+n-1.

14. Перевірка кількості базісних змінних в початковому рішенні особливо важливо при використанні метода наіменьшої вартості.

15. Вартості перевезень із фіктивних пунктів відправлення або в фіктивні пункти призначения приймаються рівними одиниці.

Відповіді

I-В; 2-Н; 3-Н; 4-В; 5-Н; 6-В; 7-Н; 8-8; 9-В; 10-В; II-В; 12-Н; 13-Н; 14-В; 15-Н

ЗАДАЧІ

Решіть транспортну задачу

1. a =; b =

Схожі:

3. Транспортна задача лінійного програмування Формолювання задачі icon3. Транспортна задача лінійного програмування Формулювання задачі
Транспортна задача представляє собою задачу лп, котру можно вирішувати симплекс-методом. Але специфічна структура умов задачі дозволяє...
3. Транспортна задача лінійного програмування Формолювання задачі icon2. Двоїста задача лінійного програмування Тема Транспортна задача
Операція, основні поняття І якості. Прямі та зворотні задачі. Управління операцією, оцінка якості. Математичні моделі операцій. Допустимі...
3. Транспортна задача лінійного програмування Формолювання задачі iconФормат опису модуля
Лп симплекс-методом, транспортна задача лп, задачі оптимізації на мережах, задачі з цілочисельними змінними, ігрові задачі до, моделі...
3. Транспортна задача лінійного програмування Формолювання задачі iconПитання на екзамен з дисципліни «Економіко математичне моделювання». Модуль «Математичне програмування»
Перша стандартна форма задачі лп. (Основна задача лінійного програмування з обмеженнями-рівностями)
3. Транспортна задача лінійного програмування Формолювання задачі iconЗведення матричної гри до задачі лінійного програмування
Актуальність теми дослідження. У статті обґрунтовується можливість застосування математичного апарату теорії ігор для задач лінійного...
3. Транспортна задача лінійного програмування Формолювання задачі iconСіра О. В. Національний технічний університет «хпі» (м. Харків)
Вступ. Транспортна задача лінійного програмування в традиційній постановці формулюється наступним чином. Маємо постачальників однорідного...
3. Транспортна задача лінійного програмування Формолювання задачі iconЗадача динамічного програмування. Загальний випадок
Але у відмінності від лінійного програмування динамічне програмування не зводиться до якийсь стандартної обчислювальної процедури;...
3. Транспортна задача лінійного програмування Формолювання задачі iconЗавдання І. Вирішить графічно наступні задачі лінійного програмування

3. Транспортна задача лінійного програмування Формолювання задачі iconЗадача динамічного програмування. Загальний випадок Загальна ідея динамічного програмування: пошагова оптимізація, що проходить в одному напрямі,"умовно", в іншому- "безумовно".
Але на відміну від лінійного програмування, динамічне програмування не зводиться до будь-якої стандартної обчислювальної процедури;...
3. Транспортна задача лінійного програмування Формолювання задачі icon3 Формулювання задачі
Транспортна задача являє собою задачу лп, що можна вирішувати симплексом-методом. Однак специфічна структура умов задачі дозволяє...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи