МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
Національний університет “Львівська політехніка”
Особливості розв’язку транспортної задачі
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 3
з курсу “Методи синтезу та оптимізації”
для студентів базового напряму 6.08.04 “Компютерні науки”
ЗАТВЕРДЖЕНО
На засіданні кафедри САП
Протокол № 1 від 28.08.2008 р.
ЛЬВІВ 2008
Особливості розв’язку транспортної задачі. Методичні вказівки до лабораторної роботи № 3 з курсу “Методи синтезу та оптимізації” для студентів базового напряму 6.08.04 “Компютерні науки” /Укл. Теслюк В. М., Андрійчук М. І. – Львів: НУ “ЛП”, 2008 р.
Укладачі: Теслюк Василь Миколайович, к. т. н., доцент;
Андрійчук Михайло Іванович, к. ф.-м., доцент.
Відповідальний за випуск: Ткаченко С. П., к. т. н., доцент.
Рецензенти: Каркульовський В. І., к.т. н., доцент,
Стех Ю. В., к.т. н., доцент.
1. МЕТА РОБОТИ
Ознайомитися з особливостями розв’язування транспортної задачі.
2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Транспортна задача (модель) відноситься до задач лінійного програмування. Під транспортною моделлю розуміють задачу, яка використовується для вирішення задачі побудови найбільш економічного плану перевозок одного виду продукції з декількох пунктів (для прикладу склади, заводи тощо) в пункти призначення (торгові організації, ті ж склади та ін). Разом з тим, дану модель з успіхом використовують при вирішенні ряду інших задач зокрема: керування запасами, побудови сіткових графіків, призначенням службовців на посади, регулюванні витрат води та ін.
Оскільки транспортна задача відноситься до задач ЛП, то для її розв’язку можна використати симплекс-метод, який розглянуто вище. Однак специфічна структура цієї задачі дозволяє розробити більш простіші та ефективні методи для її вирішення. Хоча, при розв’язку транспортної задачі використовується такий же алгоритм як і при використанні симплекс-методу.
2.1 Постановка транспортної задачі
Отже, як було зазначено вище, при постановці транспортної задачі необхідно побудувати найбільш економічний план перевозок одного виду продукції з декількох пунктів (кількість яких позначимо через I, а кількість продукції, яка виробляється в кожному пункті - ) в пункти призначення (кількість яких позначимо через J, а кількість продукції, яку необхідно обов’язково підвести до кожного пункта - ), вартість перевезення однієї одиниці продукції з пункта i в пункт j позначимо через , а через - позначимо кількість продукції, яку необхідно перевести з пункта i в пункт призначення j. Тепер усі вхідні дані є і сформулюємо транспортну задачу в загальному випадку:
, (2.1)
при виконанні наступних обмежень:
, , (2.2)
, ,
, для всіх i та j.
В даній постановці перша група обмежень вказує на те, що сумарна кількість продукції вивезеної з певного пункта-джерела не може перевищувати кількість продукції, яка в ньому вироблена, а друга – вимагає щоб сумарні перевезення в деякий пункт повністю задовільнями попит цього пункта.
2.2 Поняття збалансованою та незбалансованої транспортної задачі
З наведеної постановки транспортної задачі (2.1, 2.2) слідує, що сумарний об’єм виготовлення продукції в пунктах не має бути меншим сумарного попиту в пунктах призначення . У випадку, коли , то така транспортна задача називається збалансованою, а транспортна задача в якої називається незбалансованою. Вона відрізняється від вищенаведеної тим, що всі обмеження перетворюються в рівності, а саме:
, , (2.3)
, .
Збалансованість реальної транспортної задачі є дуже важливою ознакою, яка значно спрощує розв’язок задачі. Тому, на практиці, завжди стараються збалансувати транспортну задачу. Наведемо приклад транспортної задачі.
Нехай автомобілі певної марки виготовляють на заводах З1, З2 і З3. Об’єми виробництва складають відповідно 300, 400, 700 автомобілів кожного місяця. Параметри щомісячного попиту на автомобілі даної марки в магазинах М1 і М2 складають 1000 і 400 шт. відповідно. Вартість перевезення одного автомобіля на один кілометер складає 1 грн. Відстань між заводами і магазинами наведено в Табл.2.1. Необхідно побудувати план перевозок автомобілів таким чином щоб мінімізувати витрати на їх перевезення.
Побудуємо таблицю вартостей перевозок від заводів до магазинів. Відповідна процедура виконується досить просто, необхідно перемножити кількість кілометрів на вартість перевезення одного кілометра. В результаті, отримаємо значення, які наведені в Табл.2.2.
Табл.2.1
Заводи / Магазини
М1 (км.)
М2 (км.)
З1
350
830
З2
500
200
З3
550
420
Табл.2.2
Заводи / Магазини
М1 (грн.)
М2 (грн.)
З1
350
830
З2
500
200
З3
550
420
Оскільки сумарний об’єм виробництва (300+400+700=1400) рівний сумарному об’єму продаж (1000+400=1400), то відповідна транспортна задача є збалансованою і відповідно ця задача, при її формулюванні, буде містити обмеження у формі рівностей.
Отже, транспортна задача для вище наведеного завдання формулюється так:
Мінімізувати
, (2.4)
при забезпеченні наступних обмежень:
,
,
,
,
,
, для всіх i, j.
Більш компактний метод представлення транспортної задачі пов’язаний з використанням так званої транспортної таблиці, яка має вид матриці в якій стрічки відповідають пунктам-джерелам продукції (заводи), а стовпчики – пунктам призначення (магазини). Коефіцієнти вартості перевезень розміщені в правому верхньому куті кожної комірки (i, j).
Наведемо приклад транспортної таблиці (Табл.2.3) для вище сформульованої задачі.
Табл.2.3
Пункти призначення
Пункти - джелера
М1 (1)
М2 (2)
З1 (1)
350
830
300
З2 (2)
500
200
400
З3 (3)
550
420
700
1000
400
Розглянемо ситуацію, коли транспортна задача є не збалансованою і її необхідно модифікувати таким чином, щоб для її вирішення можна було використати ефективні алгоритми для розв’язку збалансованих транспортних задач. Отже, візьмемо за основу попередню транспортну задачу з деякою модифікацієї, яка полягає в тому, що завод З3 виготовляє в місяць не 700 автомобілів, а - 600. В даному випадку маємо дефіцит автомобілів в 100 одиниць (1400 – 1300 = 100) і його необхідно оптимально розподілити між центрами продажу.
Оскільки попит перевищує пропозицію, то небхідно в умову задачі ввести фіктивний завод по виготовленню 100 автомобілів в місяць, вартість перевезення в усі магазини має бути рівною нулю, так як реально завод відсутній і, відповідно, відсутні й перевезення. Приклад представлення вже збалансованої транспортної задачі в табличній формі наведено нижче (Див. Табл. 2.4).
Табл.2.4
Пункти призначення
Пункти - джелера
М1 (1)
М2 (2)
З1 (1)
350
830
300
З2 (2)
500
200
400
З3 (3)
550
420
600
Фіктив.
0
0
100
завод
1000
400
Можлива цілком протилежна ситуація, коли маємо перевиробництво товару. Для наочності розглянемо приклад, знову ж, за основу, візьмемо попередню транспортну задачу з припущенням, що завод З3 виготовляє не 700 автомобілів, а – 900. Задача є не збалансованою і, в даному випадку, маємо перевиробництво на 200 одиниць продукції (1600-1400=200). Для приведення цієї задачі до збалансованої необхідно ввести фіктивний пункт продажу з нульовою вартістю за перевезення в даний магазин. Запис отриманої збалансованої транспортної задачі в табличній формі наведено в Табл. 2.5.
Табл.2.5
Пункти призначення
Пункти - джелера
М1 (1)
М2 (2)
Фікт.пункт прод.
З1 (1)
350
830
0
300
З2 (2)
500
200
0
400
З3 (3)
550
420
0
900
1000
400
200
2.3 Алгоритм розв’язку транспортної задачі
Процес розв’язку транспортної задачі передбачає ряд кроків, які детально описані нижче, а алгоритм наведено на рис. 2.1.
Отже, перший крок алгоритму передбачає визначення початкового допустимого рішення з визначенням значення цільової функції. Кількість базисних змінних визначається як I+J-1. При наявності побудованої транспортної таблиці для задач даного типу досить зручно використати один зі спеціальних методів по визначенню початкового базисного рішення, зокрема: правило північно-західного кута, метод мінімальної вартості чи наближений метод Фогеля, які детально будуть розглянути нижче.
Наступний крок алгоритму передбачає визначення змінної зі списку не базисних, яку, для покращення рішення задачі, необхідно ввести в список базисних. Знаходження цієї змінної базується на умові оптимальності і можна використати метод потенціалів. У випадку відсутності такої змінної процес знаходження рішення транспортної задачі завершується і отриманий розв’язок вважається оптимальним. В іншому випадку проводиться визначення змінної, яку необхідно виключити зі списку базисних з допомогою методу побудови цикла. Після цього вираховуємо нове значення цільової функції і цикл починається з початку та продовжується доти, поки не буде викона умова виходу з циклу.
Рис.2.1 Алгоритм розв’язку транспортної задачі
2.4 Методи визначення початкового допустимого рішення транспортної задачі
Правило північно-західного кута. Визначення початкового базисного рішення з допомогою правила північно-західного кута починається з того, що змінній (розміщеній в північно-західному куті транспортної таблиці звідси і пішла назва) присвоюється максимально можливе значення, яке допускають обмеженнями на попит та об’єм виробництва товару. Після цього викреслюють відповідний стовпчик (чи стрічку), для яких виконується обмеження, фіксуючи цим, що змінні даного стовпчика (стрічки) рівні нулю. У випадку виконання обмежень для стовпчика і стрічки можна викреслити або стовпчик, або стрічку. Після того, як попит і об’єм виробництва в усіх викреслених стрічках та стовпчиках приведені до відповідності з встановленим значенням змінної, максимально можливе значення приписується першому невикресленому елементу нового стовпчика (стрічки). Процес завершується, коли залишається один не викреслений стовпчик чи стрічка. Для кращого розуміння даного правила наведемо приклад знаходження початкового допустимого рішення для транспортної задачі (Табл. 2.3).
Отже, для змінної , згідно алгоритму, присвоюємо максимально можливе значення 300 і викреслюємо з розгляду першу стрічку, при розрахунках, присвоюючи змінній - 0, оскільки для стрічки виконується обмеження (змінна =300 та об’єм виготовлений першим заводом також рівний 300). Змінна вноситься в список базисних, а - до списку не базисних. Необхідно зауважити, що умова для першого стивпчика не виконується оскільки =300 (значення інших змінних цього стовпчика, на даний момент, вважаємо рівними нулю), а сума по стовпчику має бути рівною 1000 (Див. Табл. 2.6).
Табл. 2.6
1
2
1
350
X12
830
300
2
500
X22
200
400
3
550
X32
420
700
1000
400
Наступною змінною розглядаємо , максимальне значення для цієї змінної ми можемо присвоїти 400 і необхідно викреслити другу стрічку (Див. Табл. 2.7). В результаті, залишається остання третя стрічка, в якій, для змінної можемо присвоїти максимальне значення 300 (для виконання обмеження-рівності по першому стовпчику), а змінній - 400 (для виконання рівності по другому стовпчику, див. Табл.2.8). Отже початкове базисне рішення включає змінні , , , , а в список не базисних входять змінні , .
Табл. 2.7
1
2
1
350
X12
830
300
2
500
X22
200
400
3
550
X32
420
700
1000
400
Визначення початкового базисного рішення для транспортної задачі з допомогою методу найменшої вартості. Вхідними даними для визначення початкового базисного рішення є інформація записана у формі транспортної таблиці. Обчислення проводяться наступним чином. Вибирається змінна, якій відповідає найменше значення вартості в усій таблиці і цій змінній присвоюється найбільш можливе значення. Якщо таких змінних декілька, то береться будь-яка з них. Викреслюється відповідний стовпчик чи стрічка (для яких виконується обмеження у формі рівності). Після обчислень нових значень попиту та об’єму виробництва для всіх невикреслених стрічок та стовпчиків процес продовжується при присвоєнні найбільш можливого значення для тої змінної, якій відповідає мінімальна вартість серед невикреслених. Процедура завершується, коли залишається одна стрічка чи один стовпчик.
Табл. 2.8
1
2
1
350
X12
830
300
2
500
X22
200
400
3
550
420
700
1000
400
Для кращого розуміння ідеї методу розглянемо приклад. Вхідні дані для нього розміщені в Табл.2.3. Згідно вище наведеного алгоритму змінною з найменшою вартістю перевезення 200 одиниць є X22. Присвоюємо їй найбільш можливе значення 400 і викреслюємо з розгляду другу стрічку (Див. Табл.2.9). Наступною змінною є X11 (350),
Табл.2.9
1
2
1
X11
350
X12
830
300
2
X21
500
X22 = 400
200
400
3
X31
550
X32
420
700
1000
400
якій присвоюємо 300 і викреслюємо першу стрічку (Див. Табл. 2.10). В кінцевому випадку залишається не викресленою третя стрічка і для виконання обмежень рівностей змінній X32 слід присвоїти 0, а змінній X31 – 700. Базисними змінними є X11, X22, X31 та X32, всі інші є небазисними.
Табл.2.10
1
2
1
X11=300
350
X12
830
300
2
X21
500
X22 = 400
200
400
3
X31 = 700
550
X32 = 0
420
700
1000
400
Еврістичний метод Фогеля. Цей метод, як правило, дозволяє отримати кращі результати, ніж два розглянуті вище (метод північно-західного кута та метод найменшої вартості).
Алгоритм застосування методу Фогеля передбачає виконання наступних кроків:
Крок 1. Визначити штрафи для кожної стрічки (стовпчика). Віднімаючи значення найменшої вартості перевезення для даного елемента цієї стрічки (стовпчика) з наступним значенням вартості за ним по величині елемента тієї ж стрічки (стовпчика).
Крок 2. Відмітити стрічку чи стовпчик з найбільшим штрафом. Визначити в ній елемент з найменшою вартістю і присвоїти змінній цього елемента найбільш можливе значення враховуючи накладені обмеження. Викреслити з розгляду стрічку чи стовпчик, для яких виконується накладене обмеження. Якщо обмеження по стовпчику і стрічці виконуються одночасно, то викреслити стовпчик чи стрічку, а невикресленій стрічці або стовпчику присвоїти нуль для попиту чи об’єму виробництва. Стрічки чи стовпчики з нульовим попитом чи об’ємом виробництва надалі з розгляду виключають.
Крок 3. Якщо залишається невикресленою одна стрічка чи стовпчик, то завершити обчислення.
У випадку, коли залишається одна стрічка чи стовпчик з додатнім об’ємом виробництва (попитом), то до цієї стрічки необхідно застосувати метод найменшої вартості.
Якщо всім невикресеним стрічкам та стовпчикам відповідають нульові об’єми виробництва і величини попиту – застосувати метод найменшої вартості.
В інших випадках обчислити нові значення штрафів для невикреслених стрічок і стовпчиків та перейти до кроку 2.
Приклад застосування даного методу наведено нижче. Обчислення штрафів подано в Табл.2.11. Найбільший штраф присвоєно другій стрічці, а елемент X22 має найменше значення вартості, тому йому присвоюємо найбільш можливе значення 400. При цьому, виконується умова як по стовпчику, так і по стрічці. Викреслимо другу стрічку, а в графі попит для другого стовпчика поставимо 0 (Див. Табл.2.12). Знову вираховуємо штрафи, найбільший штраф має перша стрічка (280), вибираємо елемент змінної X11 оскільки для цієї змінної найменша величина вартості, присвоюємо їй значення 300 і викреслюємо з розгляду першу стрічку (Див.Табл. 2.13). Згідно вище наведеного алгоритму до третьої стрічки застосовуємо метод найменшої вартості, який передбачає присвоння змінній X32=0, а змінній X31=700. В результаті застосування методу Фогеля отримано початкові базисні змінні X11, X22, X31 та X32 (Див.Табл.2.14).
Табл. 2.11
1
2
Штрафи
1
X11
350
X12
830
300 830-350=280
2
X21
500
X22
200
400 500-200=300
3
X31
550
X32
420
700 550-420=130
1000
400
Штрафи
500-350=150
420-200=220
Порахуємо значення цільової функції для списків базисних змінних отриманих з допомогою різних методів.
Правило північно-західного кута
Ц.Ф.=300*350+400*500+300*550+400*420=638000
Метод найменшої вартості
Ц.Ф.=300*350+400*200+700*550=570000
Еврістичний метод Фогеля
Ц.Ф.=300*350+400*200+700*550=570000
Отримані дані дозволяють стверджувати, що методи найменшої вартості та Фогеля дозволяють отримати значно краще початкове базисне рішення у порівнянні з алгоритмом північно-західного кута.
Табл. 2.12
1
2
Штрафи
1
X11
350
X12
830
300 830-350=280
2
X21
500
X22=400
200
400
3
X31
550
X32
420
700 550-420=130
1000
0
Штрафи
500-350=200
Табл. 2.13
1
2
Штрафи
1
X11=300
350
X12
830
300 830-350=280
2
X21
500
X22=400
200
400
3
X31
550
X32
420
700 550-420=130
1000
0
Штрафи
500-350=200
Табл. 2.14
1
2
Штрафи
1
X11=300
350
X12
830
300
2
X21
500
X22=400
200
400
3
X31=700
550
X32=0
420
700 550-420=130
1000
0
Штрафи
500-350=200
2.5 Метод потенціалів
Метод потенціалів призначений для визначення змінної зі списку не базисних, яку необхідно ввести в список базисних і яка дозволяє покращити рішення оптимізаційної задачі.
В методі потенціалів кожній стрічці i та стовпчику j транспортної таблиці ставляться у відповідність числа та . Для кожної базисної змінної, яка розміщена на перетині стрічки i та стовпчика j має виконуватися вираз:
,
де - вартість перевезення для даної комірки, - потенціали для i–ї стрічки та j-го стовпчика.
В результаті, отримуємо систему з рівнянь, де фігурує невідомих (- базисних змінних). Значення потенціалів можна визначити із цієї системи, присвоюючи одному з них випадкове значення (як правило присвоюють рівним нулю) потім вирішують систему з рівнянь відносно решти потенціалів.
Як тільки рішення отримане, оцінки для небазисних змінних визначаються у відповідності з співвідношенням:
.
Після цього, для включення в базис вибирається та небазисна змінна, яка має найбільшу додатну оцінку , а у випадку відсутності додатньої оцінки процес покращення рішення завершується і отримане рішення вважається оптимальним.
Наведемо приклад застосування методу потенціалів для визначення змінної, яку необхідно включити в список базисних. За основу візьмемо вище наведену траспортну задачу (Табл.2.3). Початкові базисні змінні та їх значення отримано з допомогою методу північно-західного кута (Див.параграф 2.4.1). Отже, початкові базисні змінні , , , , а значення цільової функції рівне 638000.
Визначимо оцінки для базисних змінних:
,
,
,
.
Визначимо оцінки для стовпчиків та стрічок, вважаючи, що. Тоді , , і . Не базисними змінними є , . Визначимо оцінки для цих змінних.
,
.
Отже, змінною, яку необхідно ввести в базис є .
2.6 Алгоритм побудови замкнутого циклу
Алгоритм побудови замкнутого циклу призначений для визначення змінної зі списку базисних, яку необхідно виключити. Дана процедура еквівалентна використанню умови допустимості в симплекс-методі.
Крок 1. Побудувати цикл починаючи і завершуючи на змінній, яку слід ввести в список базисних. Він складається з послідовності горизонтальних та вертикальних (зв’язаних) відрізків, кінцями яких мають бути базисні змінні за виключенням тих кінців, які відносяться до змінної, що вводиться в список базисних. Це означає, що кожна комірка, яка розміщена на згині цикла має містити базисну змінну. Не має значення в якому напрямку від змінної, що вводиться в список базисних відбувається побудова циклу (Продовження розв’язку транспортної задачі див. Табл.2.15).
Крок 2. Поставити плюси та мінуси чергуючи між собою біля базисних змінних, які розміщені на згинах циклу. Біля змінної, що вводиться в список базисних необхідно поставити плюс. Це випливає з того, що якщо до змінної, що вводиться додати одиницю, то для виконання умови допустимості рішення базисних змінних, які розміщені на згинах необхідно зменшити на одиницю і так далі (Див. Табл.2.15) чергуючи плюс і мінус біля базисних змінних побудованого цикла. В даному випадку, біля змінної X22 ставимо плюс, X32 – мінус, X32 – плюс, X12 ставимо мінус.
Крок 3. Змінна, яка раніше за інші досягає нуля і буде тою змінною, яку необхідно перевести в список не базисних. Для виконання цієї операції необхідно вибрати базисну змінну, що розміщена на згині цикла зі знаком мінус і найменшим значенням. У випадку двох однакових вибирається будь-яка зних. Для прикладу виберемо X21 (Див. Табл.2.15).
Крок 4. Величину змінної, яка виводиться зі списку базисних необхідно відняти від величин базисних змінних, де розміщений мінус і додати до величин базисних змінних, де розміщено плюс (Див. Табл.2.16).
Крок 5. Вирахувати значення цільової функції для нового списку базисних змінних (Ц.Ф.=300*350+400*200+700*550=570000).
Табл. 2.15
1
2
1
X11=300
350
830
300
2
X21=400 (-)
500
X22(+)
200
400
3
X31=300 (+)
550
X32=400 (-)
420
700
1000
400
Табл. 2.16
1
2
1
X11=300
350
830
300
2
X21 (-)
500
X22=400(+)
200
400
3
X31=700 (+)
550
X32=0 (-)
420
700
1000
400
Для перевірки, чи отримане рішення оптимальне слід застосувати знову метод потенціалів для нового списку базисних і не базисних змінних.
Визначаємо оцінки для базисних змінних:
,
,
,
.
Визначимо оцінки для стовпчиків та стрічок, вважаючи, що. Тоді , , і . Не базисними змінними є , . Визначимо оцінки для цих змінних.
,
.
Оскільки додатні оцінки для не базисних змінних відсутні, то отримане рішення транспортної задачі оптимальне, яке передбачає, що з заводу 1 перевезти 300 автомобілів і з заводу 3 700 автомобілів перевести в М1, а з заводу 2 -400 автомобілів в М2.
3. КОНТРОЛЬНІ ЗАПИТАННЯ
3.1. Вкажіть на основні переваги розв’язування транспортної задачі методом північно-західного кута.
3.2. Якими недоліками володіє евристичний метод Фотеля.
3.3. Вкажіть на відмінності методу північно-західного кута і методу найменшої вартості.
4. ЛАБОРАТОРНЕ ЗАВДАННЯ
4.1. Набрати, скомпілювати та запустити програму, задану викладачем.
4.2. Пояснити дії, які виконує програма.
4.3. Перевірити достовірність одержаного результату.
5. ЗМІСТ ЗВІТУ
5.1. Титульний лист.
5.2. Мета роботи, теоретичні відомості.
5.3. Лабораторне завдання.
5.4. Програма і результат її роботи.
5.5. Висновок.
6. ЛІТЕРАТУРА
1. Д. Химмельблау. Прикладное нелинейное программирование. Пер. с англ. М.: Мир, 1975. – 536 с.
2. Г. Реклейтис, А. Рейвиндран, К. Рэгсдел. Оптимизация в технике: В 2-х кн. Кн. 1. Пер. с англ. – М.: Мир, 1986. – 352 с.
3. Г. Реклейтис, А. Рейвиндран, К. Рэгсдел. Оптимизация в технике: В 2-х кн. Кн. 2. Пер. с англ. – М.: Мир, 1986. – 320 с.
4. О. Коссак, О. Тумашова, О. Коссак. Методи наближених обчислень. Навчальний посібник. НУ «Львівська політехніка», 2003. - 168 с.