3 Формулювання задачі icon

3 Формулювання задачі




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

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

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

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

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

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

. (3.1.)

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




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

Мал. 1



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


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

Нехай xij - кількість вантажу, що відправляється з пункту відправлення Аi у пункт Bj.

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

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

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

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

, i=1, , m, (3.2.)

, j=1, , n, (3.3.)

xij 0, для всіх i і j.

Таким чином, маємо типову задачу лінійного програмування з 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).

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

На трьох базах Ai (i=1,3) зосереджене а=||15, 25, 5|| одиниць вантажу, що необхідно доставити на 4 пункти прийому Вj (j=1,4) у кількості b=||5, 15, 15, 10||. Вартість перевезень Cij однієї одиниці вантажу з i-ой бази на j пункт прийому задані матрицею:

.

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

Рішення:

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

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

L=10x11+20x13+11x14+12x21+7x22+9x23+20x24+14x32+16x33+18x34,


при обмеженнях

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.

xij0 для всіх i і j

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


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

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


Таблиця 1



Крок 1.

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

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

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

Таблиця 2



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

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

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

4. х33=8, стовпець 3 виключається з розгляду.

5. х34=7, виключається з розгляду або стовпець 4 або рядок 3.

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

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

Крок 2.

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

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

ui+vj=сij. (3.4.)

Ці рівняння приводять до системи, що перебуває з m+n-1 рівнянь (оскільки усього є m+n-1 базисних перемінних), у яких фігурує m+n невідомих. Значення потенціалів легко визначити з цієї системи, надаючи одному з них довільні значення (звичайно u1 покладається рівним нулю) і потім вирішуючи систему з 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=сij мають настільки просту структуру, що їх не потрібно і записувати в явному виді. Потенціали визначаються безпосередньо з транспортної таблиці.

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

zij=cij-(ui+vj) (3.5.)

є негативної і найбільший по модулі.

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

Необхідна і достатня умова оптимальності плану перевезень полягає в позитивності всіх zij=cij-(ui+vj).

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

Крок 3.

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

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

Таблиця 3



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

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

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

=min{5, 5, 5}=5.

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

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

Таблиця 4



Оскільки в розглянутому прикладі три перемінні х11, х22 і х32, що знаходяться в негативних вершинах мають те саме мінімальне значення, рівне п'ятьох, то в цьому випадку будь-яку з них можна виключити з базису. У таблиці 4 виключено з базису перемінних х34.

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

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

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

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

Таблиця 5



У таблиці 5 перемінної, вводимої у базис, і що виключається перемінної, є х14 і х24, відповідно. Нове рішення подане в таблиці 6.

Таблиця 6



Оскільки усі zij у таблиці 6 позитивні, то отримане рішення оптимально. Максимальні сумарні транспортні витрати складають

min L=.


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

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

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

У таблиці 7 початкове рішення отримане методом найменшої вартості

Таблиця 7



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


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

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

ТЕСТИ


(вірно (У) або невірно (Н)? )


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Відповіді


1-В;

2-Н;

3-Н;

4-В;

5-Н;

6-В;

7-Н;

8-В;

9-В;

10-В;

11-В;

12-Н;

13-Н;

14-В;

15-Н





ЗАВДАННЯ

Розв’язати транспортну задачу


1. a=||10, 15, 7||;

b=||3, 5, 10, 14||;

.

2. a=||40, 23, 20||;

b=||20, 20, 43||;


.


3. a=||40, 30, 20||;

b=||40, 30, 40, 10||



4. a=||10, 20, 10, 30||;

b=||20, 10, 10, 20||





5. a=||10, 80, 15||;

b=||75, 20, 50||



6. a=||20, 40, 30||;

b=||30, 20, 20||





7. a=||7, 12, 11||;

b=||10, 10, 10||



8. a=||12, 14, 4||;

b=||9, 10, 11||





9. a=||20, 10, 15, 15||;

b=||5, 10, 15||



10. a=||5, 18, 12, 25||;

b=||1, 16, 18, 24||





11. a=||3, 17, 8, 16||;

b=||4, 16, 8, 17||



12. a=||10, 10, 20, 10||;

b=||20, 10, 10, 20||





13. a=||20, 10, 30, 30||;

b=||30, 30, 20, 30||



14. a=||10, 20, 40, 10||;

b=||20, 20, 50, 20||





15. a=||80, 40, 80, 80||;

b=||90, 60, 20, 40||



16. a=||5, 6, 7, 5||;

b=||4, 8, 3, 7||





17. a=||18, 12, 16, 24||;

b=||4, 15, 25, 36||



18. a=||10, 20, 10, 15||;

b=||10, 20, 10, 20||





19. a=||10, 10, 12, 18||;

b=||10, 10, 15, 15||



20. a=||10, 12, 10, 18||;

b=||17, 13, 15, 25||





21. a=||30, 48, 20, 30||;

b=||18, 27, 42, 15, 26||



22. a=||6, 12, 12, 13||;

b=||8, 10, 12, 13||








Схожі:

3 Формулювання задачі icon3. Транспортна задача лінійного програмування Формулювання задачі
Транспортна задача представляє собою задачу лп, котру можно вирішувати симплекс-методом. Але специфічна структура умов задачі дозволяє...
3 Формулювання задачі iconПротокол № від 20
Проведення літературного огляду за темою дисертації. Формулювання мети та задачі досліджень, вибір методів досліджень. Визначення...
3 Формулювання задачі iconВимоги до оформлення текстів доповідей матеріали можуть бути підготовлені українською, російською або англійською мовами. Текст слід готувати в редакторі Microsoft Word 97/2000/ХР/2003. Необхідно надіслати
Сті нерозв’язаних задач з обов’язковими посиланнями на літературні джерела; формулювання задачі, що розглядається; характеристику...
3 Формулювання задачі iconВісник львів. Ун-ту visnyk LVIV univ серія прикладна математика та Ser. Applied Mathematiсs and
Описано відповідний фізичний процес, математичне формулювання задачі та схему її чисельного розв’язування. Одержаний розв’язок відповідає...
3 Формулювання задачі iconВісник львів. Ун-ту visnyk LVIV univ серія прикладна математика та Ser. Applied Mathematiсs and інформатика. 2002. Вип C.8 Computer Science. 2002. No. P.8
Розглянуто варіаційне формулювання оберненої задачі з подальшим зведенням її до знаходження розв’язків нелінійних операторних рівнянь...
3 Формулювання задачі iconФормат опису модуля
Лп симплекс-методом, транспортна задача лп, задачі оптимізації на мережах, задачі з цілочисельними змінними, ігрові задачі до, моделі...
3 Формулювання задачі iconНіколаєнко С. О. кандидат психол наук, доцент кафедри соціально-гуманітарних дисциплін двнз «Українська академія банківської справи Національного банку України»
Сугестивно-педагогічні задачі доцільно розділяти, по-перше, на стратегічні, тактичні й оперативні сугестивно-педагогічні задачі,...
3 Формулювання задачі iconТип модуля: обов’язковий Семестр: V обсяг модуля
Задачі, які зводяться до лінійних І нелінійних систем алгебричних рівнянь, до обчислення многочленів Тейлора І фур'є та їх похідних,...
3 Формулювання задачі iconІ задачі Сумду щодо впровадження кредитно-модульної системи організації навчального процесу
Розділ ісутність Болонського процесу та задачі реформування Вищої школи в Україні
3 Формулювання задачі iconІ задачі Сумду щодо впровадження кредитно-модульної системи організації навчального процесу
Розділ ісутність Болонського процесу та задачі реформування Вищої школи в Україні
Додайте кнопку на своєму сайті:
Документи


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