Транспортна задача
Формулювання класичної транспортної задачі лінійного програмування. Необхідність зведення відкритої транспортної задачі до закритої. Умови цілочисельності, оптимальності та методи побудови опорного плану транспортної задачі. Алгоритм методу потенціалів.
| Рубрика | Экономико-математическое моделирование |
| Вид | лекция |
| Язык | украинский |
| Дата добавления | 08.02.2015 |
| Размер файла | 243,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
ТРАНСПОРТНА ЗАДАЧА (ТЗ)
29. Економічна і математична постановка ТЗ
Класична транспортна задача лінійного програмування формулюється так: деякий однорідний продукт, що знаходиться у m постачальників Аі в обсягах одиниць відповідно необхідно перевезти n споживачам в обсягах одиниць. При цьому виконується умова, що загальний наявний обсяг продукції у постачальників дорівнює загальному попиту всіх споживачів. Відомі вартості перевезень одиниці продукції від кожного Аі-го постачальника до кожного Вj-го споживача, що подані як елементи матриці виду:
Необхідно визначити план перевезень, за якого вся продукція була б вивезена від постачальників, повністю задоволені потреби споживачів і загальна вартість всіх перевезень була б мінімальною.
У такій постановці задачі ефективність плану перевезень визначається його вартістю і така задача має назву транспортної задачі за критерієм вартості перевезень.
Позначимо через обсяг продукції, що перевозиться від постачальника до споживача .
|
Споживачі |
В1 |
В2 |
... |
Вn |
||
|
Постачальники |
b1 |
b2 |
... |
bn |
||
|
A1 |
а1 |
с11x11 |
с12x12 |
... |
с1nx1n |
|
|
A2 |
а2 |
с21x21 |
с22x22 |
… |
с2nx2n |
|
|
… |
… |
… |
… |
… |
… |
|
|
Am |
аm |
сm1xm1 |
сm2xm2 |
… |
сmnxmn |
Мають виконуватися такі умови:
сумарний обсяг продукції, що вивозиться з кожного і-го пункту, має дорівнювати запасу продукції в даному пункті:
сумарний обсяг продукції, що ввезений кожному j-му споживачеві, має дорівнювати його потребам:
сумарна вартість всіх перевезень повинна бути мінімальною:
Очевидно, що .
У скороченій формі запису математична модель транспортної задачі за критерієм вартості перевезень має такий вигляд:
(5.1)
за обмежень:
; (5.2)
; (5.3)
. (5.4)
У розглянутій задачі має виконуватися умова:
. (5.5)
Транспортну задачу називають збалансованою, або закритою, якщо виконується умова (5.5). Якщо ж така умова не виконується, то транспортну задачу називають незбалансованою, або відкритою.
Домовимося планом транспортної задачі називати будь-який невід'ємний розв'язок системи обмежень (5.2)--(5.4), який позначають матрицею . Значення невідомих величин -- обсяги продукції, що мають бути перевезені від i-х постачальників до j-х споживачів, називатимемо перевезеннями.
Оптимальним планом транспортної задачі називають матрицю , яка задовольняє умови задачі, і для якої цільова функція (5.1) набирає найменшого значення.
30. Умова існування розв'язку ТЗ
Теорема: необхідною і достатньою умовою існування розв'язку транспортної задачі (5.1)--(5.4) є її збалансованість: .
Доведення. Необхідність. Нехай задача (5.1)--(5.4) має розв'язок , тоді для нього виконуються рівняння-обмеження (5.2) і (5.3). Підсумуємо відповідно ліві та праві частини систем рівнянь (5.2) і (5.3). Матимемо:
, (5.6)
(5.7)
Оскільки ліві частини рівнянь (5.6) та (5.7) збігаються, то праві також рівні одна одній, отже, виконується умова:
. (5.8)
Достатність.
За умовою = W > 0. Розглянемо величини (). Підставивши значення в систему обмежень задачі (5.1)--(5.4), матимемо:
;
.
Оскільки умови (5.2) та (5.3) виконуються, то є планом наведеної транспортної задачі.
Виберемо з елементів найбільше значення і позначимо його через . Якщо замінити в цільовій функції (5.1) всі коефіцієнти на , то, враховуючи (5.2), матимемо:
.
Виберемо з елементів найменше значення і позначимо його через . Якщо замінити в цільовій функції (5.1) всі коефіцієнти на , то, враховуючи (5.2), матимемо:
.
Тобто цільова функція на множині допустимих планів транспортної задачі є обмеженою:
.
Теорему доведено.
31. Зведення відкритої задачі до закритої
Якщо при перевірці збалансованості (5.5) виявилося, що транспортна задача є відкритою, то її необхідно звести до закритого типу.
Це здійснюється введенням фіктивного (умовного) постачальника у разі перевищення загального попиту над запасами із ресурсом обсягом .
Якщо ж загальні запаси постачальників перевищують попит споживачів , то до закритого типу задача зводиться введенням фіктивного (умовного) споживача з потребою .
Вартість перевезення одиниці продукції від фіктивного постачальника (або фіктивного споживача ) до кожного зі споживачів (виробників) має дорівнювати нулю або бути набагато більшою за реальні витрати . Як правило, у такому разі використовують нульові значення вартостей перевезень, що дає змогу спростити обчислення.
Всі коефіцієнти при змінних у рівняннях (5.2), (5.3) дорівнюють одиниці, а сама система в канонічній формі. Система обмежень (5.2), (5.3) складається з mn невідомих та m + n рівнянь, які пов'язані між собою співвідношенням (5.8). Якщо додати відповідно праві та ліві частини систем рівнянь (5.2) та (5.3)
; .
Це свідчить про лінійну залежність системи.
Якщо одне з цих рівнянь відкинути, то в загальному випадку система обмежень буде містити m + n - 1 лінійно незалежне рівняння, отже, їх можна розв'язати відносно m + n - 1 базисних змінних.
32. Опорний план ТЗ, цикл послідовності клітин
Назвемо опорним планом транспортної задачі такий допустимий її план, що містить не більш ніж m + n - 1 додатних компонент, а всі інші його компоненти дорівнюють нулю. Такий план є невиродженим.
Якщо ж кількість базисних змінних менша ніж m + n - 1, то маємо вироджений опорний план.
Якщо умови транспортної задачі і її опорний план записані у вигляді табл. 5.1, то клітини, в яких (ненульові значення поставок), називаються заповненими, всі інші -- пустими.
Заповнені клітини відповідають базисним змінним і для невиродженого плану їх кількість дорівнює m + n - 1.
Назвемо циклом таку послідовність заповнених клітин таблиці 5.1, яка задовольняє умову, що лише дві сусідні клітини містяться або в одному рядку, або в одному стовпці таблиці, причому перша клітина циклу є і його останньою клітиною.
Якщо для певного набору заповнених клітин неможливо побудувати цикл, то така послідовність клітин є ациклічною.
Лема. Кількість клітин, які утворюють будь-який цикл транспортної задачі, завжди парна.
Доведення. Якщо позначити кожну клітину циклу двома індексами , то довільний цикл, що складається з n клітин, можна записати одним із двох способів:
, (5.9)
або
. (5.10)
Оскільки перша та остання клітини циклу є однією клітиною, то виключимо з розгляду останній елемент (i1, j1) наведених послідовностей. Кількість клітин, що залишилась, парна, бо кожній клітині виду в (5.9) та (5.10) відповідає наступна або . Саме такими клітинами закінчуються наведені послідовності. Передостанньою клітиною є клітина виду , де . Отже, цикл утворюється клітинами, які містяться в l рядках та l стовпцях, тобто загальна їх кількість n = 2l. Лему доведено.
33. Критерій опорного плану
Теорема 5.1. Щоб деякий план транспортної задачі був опорним, необхідно і достатньо його ациклічності.
Доведення. Необхідність. Нехай у таблиці 5.1 міститься опорний план транспортної задачі, тобто не більше ніж m + n - 1 клітин будуть заповненими. Якщо заповнених клітин менше, ніж m + n - 1, то решта базисних клітин знаходиться серед незаповнених.
Довести необхідність умови теореми означає довести ациклічність опорного плану.
Допустимо протилежне. Нехай деяка підсистема з даної системи базисних векторів утворює цикл, а саме:
. (5.11)
Складемо лінійну комбінацію таких векторів, що дорівнює нулю. Оскільки кожна змінна входить у систему обмежень лише двічі, то базисні вектори матимуть вид:
Лінійною комбінацією базисних векторів буде:
Або
. (5.12)
Проте рівність (5.12) суперечить умові лінійної незалежності базисних векторів, отже, послідовність (5.11) є ациклічною.
Достатність. За умовою деякий план транспортної задачі є ациклічним. Потрібно показати, що він є опорним планом, тобто довести лінійну незалежність векторів, що відповідають ненульовим компонентам плану.
Всякий план не може містити від'ємних компонент, а кількість лінійно незалежних між собою векторів у обмеженнях транспортної задачі завжди дорівнює m + n - 1, так що кількість відмінних від нуля компонент плану, якщо він опорний, не перевищує цієї величини.
Позначимо множину всіх заповнених клітин через Н, а відповідні вектори -- . Доведемо достатність, міркуючи від супротивного. Нехай вектори лінійно залежні. Розглянемо нульову лінійну комбінацію цих векторів:
. (5.13)
Деякі з коефіцієнтів можуть відрізнятися від нуля. Нехай один з таких коефіцієнтів відповідає індексам , тобто . Тоді відповідний доданок у рівності (5.13) можна перенести в ліву частину рівняння:
, (5.14)
де .
Оскільки і1-ша компонента в лівій частині (5.14) відмінна від нуля, то в правій частині також має бути хоча б один доданок з і-ою компонентою, що відмінна від нуля. Припустимо, що . Відповідний доданок також можна перенести в ліву частину (5.14):
, (5.15)
де .
Оскільки (інакше клітина входила б у суму (5.13) двічі) і компонента лівої частини (5.15) відмінна від нуля, то серед доданків правої частини знайдеться хоча б один, для якого . Перенесемо його також в ліву частину рівняння. Отримаємо:
, (5.16)
де .
Оскільки кількість заповнених клітин, що входять у множину Н, а отже, і кількість векторів скінченна і не перевищує числа , то через N кроків описаний процес перенесень обов'язково закінчиться.
Після деякої непарної кількості кроків дістанемо рівність:
, (5.17)
де .
Якщо кількість кроків була парною, матимемо:
, (5.18)
де .
Розглянемо співвідношення (5.17). При деякому значенні серед доданків другої суми лівої частини знайдеться такий, що має індекс . Тоді всі клітини, що були перенесені в ліву частину після -го кроку, утворюють цикл.
Аналогічні міркування стосуються також (5.18).
Покажемо, що до закінчення процесу, виходячи з рівності (5.17), обов'язково матимемо цикл. Для цього припустимо, що . Тоді, згідно з попередніми міркуваннями, в правій частині (5.17) обов'язково знайдеться доданок з індексами , для якого , бо інакше б рівність (5.17) не справджувалась. Отже, процес перенесення у разі, якщо , буде продовжуватись. Проте, внаслідок згаданої скінченності процесу перенесень (N ? m · n) умова виконання рівностей (5.17) та (5.18) рівносильна тому, що випадок обов'язково матиме місце, що означатиме побудову циклу.
Отже, припущення лінійної залежності векторів , що описується рівнянням (5.13), означає, що серед відповідних клітин існує цикл, але це суперечить умові теореми.
Отже, базисні клітини опорного плану завжди утворюють ациклічну послідовність клітин.
Теорема 5.2. (Наслідок теореми 5.1.) Будь-яка сукупність з клітин матриці транспортної задачі утворює цикл.
Доведення. Як зазначалось, сукупність лінійно незалежних векторів задачі не перевищує . Отже, всяка сукупність з векторів буде лінійно залежною. Як випливає з доведення попередньої теореми, відповідні клітини завжди утворюють цикл.
Отже, сукупність усіх базисних клітин та однієї вільної клітини таблиці транспортної задачі завжди утворює цикл.
34. Умова цілочисельності опорного плану
Теорема 5.3. Якщо всі запаси і всі потреби є невід'ємними цілими числами, то будь-який опорний план складається із значень, що є цілими числами.
Доведення. Компоненти кожної системи із лінійно незалежних (базисних) векторів можуть бути подані у вигляді трикутної матриці. Нехай розглядається задача (5.1)--(5.4). Матриця з перших компонент базисних векторів системи (5.2), (5.3) матиме вигляд:
(5.19)
m n - 1
Розв'язування системи, що визначається (5.19), включатиме лише дії додавання та віднімання, і, оскільки та у постановці транспортної задачі є цілими числами, то значення змінних також будуть цілими числами.
35. Методи побудови опорного плану ТЗ
Ідея методу північно-західного кута полягає в тому, що заповнення таблиці починають, не враховуючи вартостей перевезень, з лівого верхнього (північно-західного) кута. У клітину записують менше з двох чисел а1 та b1. Далі переходять до наступної клітини в цьому ж рядку або у стовпчику і заповнюють її, і т. д. Закінчують заповнення таблиці у правій нижній клітинці. У такий спосіб значення поставок будуть розташовані по діагоналі таблиці.
|
Постачальники |
Запаси |
Споживачі |
||||
|
B1 |
B2 |
B3 |
B4 |
|||
|
Потреби |
||||||
|
b1 = 110 |
b2 = 50 |
b3 = 60 |
b4 = 80 |
|||
|
А1 |
а1 = 150 |
4 110 |
4 40 |
2 |
5 |
|
|
А2 |
а2 = 60 |
5 |
3 10 |
1 50 |
2 |
|
|
А3 |
а3 = 90 |
2 |
1 |
4 10 |
2 80 |
Метод північно-західного кута є найпростішим, однак і найменш ефективним.
Визначимо загальну вартість перевезень згідно з початковим опорним планом.
(ум. од.).
Теорема 5.4. Опорний план транспортної задачі, знайдений методом північно-західного кута, завжди ациклічний.
Доведення. Скористаємося методом індукції числа . Для теорема очевидна: план ациклічний, оскільки складається з елемента. Так само ациклічним є план для , оскільки він складається лише з двох клітин.
Нехай теорема справедлива для деякого довільного . Доведемо її справедливість для числа .
Допустимо для визначеності, що в транспортній задачі (5.1)--(5.4) , тобто після першого кроку за методом північно-західного кута отримаємо , всі інші . Дальші кроки методу пов'язані із його застосуванням до таблиці розмірністю , де , а , причому всі запаси і потреби нової таблиці збігаються з запасами і потребами попередньої, крім . За припущенням індукції план, знайдений методом північно-західного кута для , тобто в новій таблиці, ациклічний. Очевидно, що приєднання до цього плану першого рядка з єдиним ненульовим елементом не утворить циклу, але відшуканий у такий спосіб план буде планом початкової задачі для , чим і доводиться теорема.
Ідея методу мінімальної вартості полягає в тому, що на кожному кроці заповнюють клітинку таблиці, яка має найменшу вартість перевезення одиниці продукції. Такі дії повторюють доти, доки не буде розподілено всю продукцію між постачальниками та споживачами.
|
bj ai |
b1 = 110 |
b2 = 50 |
b3 = 60 |
b4 = 80 |
|
|
а1 = 150 |
4 70 |
4 |
2 |
5 80 |
|
|
а2 = 60 |
5 |
3 |
1 60 |
2 |
|
|
а3 = 90 |
2 40 |
1 50 |
4 |
2 |
В результаті таких міркувань отримали початковий опорний план, загальна вартість перевезень для якого становить:
(ум. од.).
Значення цільової функції менше за попередній варіант, значить цей план ближчий до оптимального
Метод подвійної переваги. Якщо розмірність задачі досить велика, то перебір за методом мінімальної вартості ускладнюється. В такому разі спростити пошук клітин з найменшими вартостями можна, застосовуючи метод подвійної переваги.
Згідно з процедурою цього методу перед початком заповнення таблиці необхідно позначити будь-якими символами клітинки, які містять найменшу вартість у рядках, а потім -- у стовпчиках. Таблицю починають заповнювати з клітинок, позначених двічі (які містять вартості, що є мінімальними і в рядку, і в стовпчику). Далі заповнюють клітинки, позначені один раз (що містять мінімальні вартості або в рядку, або в стовпчику), а вже потім -- за методом мінімальної вартості.
Таблиця 5.4
|
bj ai |
b1 = 110 |
b2 = 50 |
b3 = 60 |
b4 = 80 |
|
|
а1 = 150 |
4 110 |
4 |
V 2 |
5 40 |
|
|
а2 = 60 |
5 |
3 |
VV 1 60 |
V 2 |
|
|
а3 = 90 |
V 2 |
VV 1 50 |
4 |
V 2 40 |
(ум. од.).
Застосування для побудови опорного плану даного методу уможливлює отримання найменшого у зіставленні з розглянутими вище значення цільової функції. Отже, такий план є найближчим до оптимального.
Метод апроксимації Фогеля. За цим методом на кожному кроці визначають різницю між двома найменшими вартостями в кожному рядку і стовпчику транспортної таблиці. Ці різниці записують у спеціально відведених місцях таблиці -- знизу та справа у кілька рядків та стовпчиків, що відповідають крокам заповнення таблиці. З-поміж усіх різниць вибирають найбільшу і у відповідному рядку чи стовпчику заповнюють клітинку з найменшою вартістю. Якщо ж однакових найбільших різниць кілька, то вибирають будь-який відповідний рядок або стовпчик. Коли залишається незаповненим лише один рядок або стовпчик, то обчислення різниць припиняють, а таблицю продовжують заповнювати за методом мінімальної вартості.
Даний метод побудови опорного плану враховує не лише маршрути з мінімальними витратами перевезень продукції, але й співвідношення витрат у рядку чи стовпчику, тобто розраховується наскільки, може збільшитися вартість постачання на наступних кроках процедури, якщо не здійснити на поточному кроці постачання в клітину з мінімальною вартістю.
Метод апроксимації Фогеля дає змогу особливо для задач великих розмірностей скласти найкращий опорний план.
Таблиця 5.5
|
bj ai |
b1 = 110 |
b2 = 50 |
b3 = 60 |
b4 = 80 |
Різниці по рядках |
|||
|
а1 = 150 |
4 110 |
4 40 |
2 |
5 |
2 |
2 |
0 |
|
|
а2 = 60 |
5 |
3 |
1 60 |
2 |
1 |
2 |
||
|
а3 = 90 |
2 |
1 10 |
4 |
2 80 |
1 |
1 |
1 |
|
|
Різниці по стовпцях |
2 |
2 |
1 |
3 |
||||
|
2 |
2 |
1 |
||||||
|
2 |
3 |
У таблиці 5.5. навпроти кожного рядка і стовпчика записані величини, які знайдені як різниці між мінімальним значенням вартості та наступним за ним по рівню. Максимальне значення такої різниці на першому кроці відповідає четвертому стовпчику і означає, що у разі, коли не буде задоволена потреба четвертого споживача перевезенням продукції від третього постачальника за ціною 2 ум. од. за одиницю, то на наступних кроках вартість перевезення може бути на 3 ум. од. більшою. Тобто інакше може статися, що потребу четвертого споживача необхідно буде задовольняти перевезенням продукції від першого постачальника, що призведе до збільшення вартості цього перевезення в 2,5 рази. Водночас для всіх інших споживачів та постачальників такі різниці є меншими. Отже, найдоцільніше на першому кроці заповнити клітину А3В4. Після цього потреби В4 повністю задоволені, і всі клітини четвертого стовпчика виключаються з наступного розрахунку різниць по рядках і стовпцях.
На другому кроці максимальна різниця дорівнює 2 і відповідає першому і другому рядкам та першому і другому стовпчикам, тому можна заповнювати будь-яку їх клітину з мінімальною вартістю, наприклад, А2В3. Після цього з розгляду виключаються одразу всі клітини другого рядка та третього стовпця, оскільки потреби третього споживача повністю задоволені, а запаси другого постачальника вичерпані.
Останній розрахунок різниць (найбільше значення 3 відповідає другому стовпчику) свідчить про доцільність введення поставки від третього постачальника до другого споживача. Решту клітин заповнимо методом мінімальної вартості та визначимо загальну вартість перевезень:
(ум. од.).
Результат збігся із значенням цільової функції для опорного плану, що складений за попереднім методом. Ефективність методу апроксимації Фогеля, як вже згадувалось, є очевидною для задач більшої розмірності.
Зазначимо, що ефективність наведених методів можна оцінювати лише в середньому, оскільки можлива ситуація, що методом мінімальної вартості отримано опорний план транспортної задачі кращий, ніж методом подвійної переваги.
36. Випадок виродження опорного плану ТЗ
Опорний план транспортної задачі, як зазначалося раніше, має містити не більше ніж (m + n - 1) відмінних від нуля компонент. Якщо їх кількість дорівнює (m + n - 1), то такий опорний план називають невиродженим. Якщо ж кількість додатних компонент менша ніж (m + n - 1), то опорний план є виродженим. Вироджений план може виникати не лише за побудови опорного плану, але і при його перетвореннях у процесі знаходження оптимального плану.
Щоб позбутися виродженості опорного плану, в деякі клітини таблиці вводять нульові постачання.Нульова клітина має вибиратись, щоб неможливо було побудувати замкнений цикл.
Таблиця 5.6
|
bj ai |
b1 = 7 |
b2 = 10 |
b3 = 6 |
|
|
а1 = 8 |
0 7 |
5 1 |
2 |
|
|
а2 = 7 |
2 |
3 7 |
4 |
|
|
а3 = 6 |
1 |
2 |
0 6 |
|
|
а4 = 2 |
0 |
0 2 |
0 |
Кількість постачальників , а кількість споживачів . Для невиродженого опорного плану кількість заповнених клітин таблиці 5.6 має дорівнювати . У наведеному опорному плані кількість заповнених клітин на одну менше (п'ять), отже, він вироджений. Враховуючи необхідність збереження ациклічності опорного плану, не можна заповнювати клітини А2В1 та А4В1, оскільки це призведе до утворення циклів, які зображені в табл. 5.7. та 5.8.
Очевидно введення нульової поставки в будь-яку іншу пусту клітинку не дає змоги утворити цикл. Отже, можна заповнити нулем одну з клітин А1В3, А2В3, А3В1, А3В2, А4В3. Наприклад, виберемо клітину А3В2.
Таблиця 5.7
|
bj ai |
b1 = 7 |
b2 = 10 |
b3 = 6 |
|
|
а1 = 8 |
0 7 |
5 1 |
2 |
|
|
а2 = 7 |
2 0 |
3 7 |
4 |
|
|
а3 = 6 |
1 |
2 |
0 6 |
|
|
а4 = 2 |
0 |
0 2 |
0 |
Таблиця 5.8
|
bj ai |
b1 = 7 |
b2 = 10 |
b3 = 6 |
|
|
а1 = 8 |
0 7 |
5 1 |
2 |
|
|
а2 = 7 |
2 |
3 7 |
4 |
|
|
а3 = 6 |
1 |
2 |
0 6 |
|
|
а4 = 2 |
0 0 |
0 2 |
0 |
Таблиця 5.9
|
bj ai |
b1 = 7 |
b2 = 10 |
b3 = 6 |
|
|
а1 = 8 |
0 7 |
5 1 |
2 |
|
|
а2 = 7 |
2 |
3 7 |
4 |
|
|
а3 = 6 |
1 |
2 0 |
0 6 |
|
|
а4 = 2 |
0 |
0 2 |
0 |
Зазначимо, що необхідність введення нульової поставки є очевиднішою на наступних етапах розв'язування транспортної задачі.
37. Умова оптимальності опорного плану ТЗ
Розглянемо транспортну задачу (5.1)--(5.4).
Позначимо змінні двоїстої задачі, які відповідають рівнянням (5.2), через , а для рівнянь (5.3) -- через . Оскільки всі обмеження транспортної задачі є рівняннями, то пара спряжених задач є несиметричною і ніякі обмеження на знаки змінних двоїстої задачі та не накладаються.
Для побудови двоїстої задачі поставимо у відповідність обмеженням початкової задачі змінні двоїстої:
(5.20)
(5.21)
.
Згідно з загальними правилами побудови двоїстих задач маємо:
(5.22)
за умов:
, (5.23)
.
Змінні ui та vj задачі (5.22), (5.23) двоїстої до транспортної мають назву потенціалів.
Теорема (умова оптимальності опорного плану транспортної задачі). Якщо для деякого опорного плану Х* = (xij*) існують числа ui та vj, для яких виконуються умови:
1) ui + vj = cij, xij > 0,
2) ui + vj cij, xij = 0
для всіх та , то він є оптимальним планом транспортної задачі.
Сформулюємо другу теорему двоїстості для задач (5.1)--(5.4) та (5.22)--(5.23).
Для того, щоб плани відповідних спряжених задач були оптимальними, необхідно і достатньо, щоб виконувалися умови доповнюючої нежорсткості:
1) ; (5.24)
2) (5.25)
Зауважимо, що друга група умов для транспортної задачі виконується автоматично, оскільки всі обмеження задачі є рівняннями.
Перша умова виконується у двох випадках:
a) якщо . Другий співмножник , бо за умовою (5.23) ();
b) якщо , то за умовою транспортної задачі , тоді ().
Необхідність і достатність виконання таких умов для оптимальності планів прямої та двоїстої задач було доведено в розділі 3. Отже, як наслідок другої теореми двоїстості для транспортної задачі отримали необхідні та достатні умови оптимальності плану.
транспортний задача лінійний програмування
38. Метод потенціалів
Алгоритм методу потенціалів:
Визначення типу ТЗ (відкрита чи закрита). За необхідності слід звести задачу до закритого типу.
Побудова першого опорного плану ТЗ одним з методів.
Перевірка опорного плану задачі на виродженість. За необхідності вводять нульові постачання.
Перевірка плану ТЗ на оптимальність.
4.1. Визначення потенціалів для кожного рядка і стовпчика таблиці транспортної задачі. Потенціали опорного плану визначають із системи рівнянь ui + vj = cij, які записують для всіх заповнених клітинок транспортної таблиці, кількість яких дорівнює , а кількість невідомих -- . Кількість рівнянь на одне менша, ніж невідомих, тому система є невизначеною, і одному з потенціалів надають нульове значення. Після цього всі інші потенціали розраховують однозначно.
4.2. Перевірка виконання умови оптимальності для пустих клітин. За допомогою розрахованих потенціалів перевіряють умову оптимальності ui + vj cij для незаповнених клітинок таблиці. Якщо хоча б для однієї клітини ця умова не виконується, тобто ui + vj > cij, то поточний план є неоптимальним, і від нього необхідно перейти до нового опорного плану.
4.3. Вибір змінної для введення в базис на наступному кроці. Перехід від одного опорного плану до іншого виконують заповненням клітинки, для якої порушено умову оптимальності. Якщо таких клітинок кілька, то для заповнення вибирають таку, що має найбільше порушення, тобто .
4.4. Побудова циклу і перехід до наступного опорного плану. Вибрана порожня клітина разом з іншими заповненими становить , отже, з цих клітин обов'язково утвориться цикл. У межах даного циклу здійснюють перерахування, які приводять до перерозподілу постачань продукції. Кожній вершині циклу приписують певний знак, причому вільній клітинці -- знак «+», а всім іншим -- за черговістю знаки «-» та «+». У клітинках зі знаком «-» вибирають значення і переносять його у порожню клітинку. Одночасно це число додають до відповідних чисел, які містяться в клітинках зі знаком «+», та віднімають від чисел, що позначені знаком «-».
Якщо значенню відповідає кілька однакових перевезень, то при відніманні залишаємо у відповідних клітинках нульові величини перевезень у такій кількості, що дає змогу зберегти невиродженість опорного плану.
Загальна сума перевезень по всіх колонках і рядках залишається незмінною.
Отже, клітинка, що була вільною, стає заповненою, а відповідна клітинка з мінімальною величиною xij вважається порожньою. У результаті такого перерозподілу перевезень продукції дістанемо новий опорний план транспортної задачі.
5. Перевірка умови оптимальності наступного опорного плану. Якщо умова оптимальності виконується -- маємо оптимальний план транспортної задачі, інакше необхідно перейти до наступного опорного плану (тобто повернутися до пункту 3 даного алгоритму).
Зауважимо, що аналогічно з розв'язуванням загальної задачі лінійного програмування симплексним методом, якщо за перевірки оптимального плану транспортної задачі для деяких клітин виконується рівність , то це означає, що задача має альтернативні оптимальні плани. Отримати їх можна, якщо побудувати цикли перерозподілу обсягів перевезень для відповідних клітин.
39. Монотонність і скінченність методу потенціалів
Вислів: Кожний новий опорний план надає меншого у зіставленні з попереднім планом значення цільової функції Z, тобто за невироджених опорних планів метод потенціалів уможливлює строго монотонне зменшення значення цільової функції ТЗ.
Доведення. Нехай план знайдено з плану однією ітерацією методом потенціалів; при цьому було використано цикл
К
та приєднаною клітиною , для якої спостерігалось найбільше порушення умови оптимальності .
З першої теореми двоїстості .
Зв'язок між послідовними значеннями цільової функції і , що відповідають опорним планам та :
.
величина - на яку змінено значення вздовж циклу
(5.26)
Враховуючи додатність величини у разі невиродженості плану і від'ємне значення виразу в дужках (), висновуємо, що . Цим і доведена строга монотонність алгоритму, яка у разі виродженості плану не є строгою, оскільки величина може дорівнювати нулю.
Обґрунтування способу вибору клітини, яка вводиться в базис за максимумом абсолютної величини є те, що це дасть найбільше зменшення цільової функції.
Скінченність алгоритму випливає з його монотонності і скінченності кількості опорних планів задачі; однак це є обґрунтованим лише для невироджених задач.
У разі виродження, коли строга монотонність не є безумовною, теоретично можливе зациклення алгоритму так само, як це може мати місце у разі застосування симплексного методу.
40. Приклади розв'язування транспортних задач методом потенціалів
Компанія контролює три фабрики А1, А2, А3, здатні виготовляти відповідно 150, 60 та 80 тис. од. продукції щотижня. Вона уклала договір із чотирма замовниками В1, В2, В3, В4, яким потрібно щотижня доставляти відповідно 110, 40, 60 та 80 тис. од. продукції. Вартість транспортування 1000 од. продукції замовникам з кожної фабрики наведена в табл. 5.10.
Таблиця 5.10
Вартість транспортування продукції
|
Фабрика |
Вартість транспортування |
||||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
4 |
4 |
2 |
5 |
|
|
А2 |
5 |
3 |
1 |
2 |
|
|
А3 |
2 |
1 |
4 |
2 |
Визначити оптимальний план перевезень продукції від кожної фабрики до замовників, що мінімізує загальну вартість транспортних послуг.
Побудова математичної моделі. Нехай xij -- кількість продукції, що перевозиться з і-ї фабрики до j-го замовника . Оскільки транспортна задача за умовою є збалансованою, закритою , то математична модель задачі матиме вигляд:
Економічний зміст записаних обмежень полягає в тому, що вся вироблена на фабриках продукція має вивозитися до замовників повністю.
Аналогічні обмеження можна записати відносно замовників: продукція, що може надходити до споживача від трьох фабрик, має повністю задовольняти його попит. Математично це записується так:
Загальні витрати, пов'язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування 1000 од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:
min Z = 4x11 + 4x12 + 2x13 + 5x14 + 5x21 + 3x22 + x23 + 2x24 + 2x31 + + x32 +4x33 +2x34.
Загалом математична модель сформульованої задачі має вигляд:
min Z = 4x11 + 4x12 + 2x13 + 5x14 + 5x21 + 3x22 + x23 + 2x24 + 2x31 + x32 ++ 4x33 +2x34
за умов:
Розв'язання. Запишемо умови задачі у вигляді транспортної таблиці (табл. 5.11) та складемо її перший опорний план у цій таблиці методом мінімальної вартості.
Таблиця 5.11
|
Ai |
Bj |
ui |
||||
|
b1 = 110 |
b2 = 40 |
b3 = 60 |
b4 = 80 |
|||
|
а1 = 150 |
4 110 |
4 |
2 2 |
5 40 |
u1 = 5 |
|
|
а2 = 60 |
5 |
3 |
1 60 |
2 0 |
u2 = 2 |
|
|
а3 = 80 |
2 |
1 40 |
4 |
2 40 |
u3 = 2 |
|
|
vj |
v1 = -1 |
v2 = -1 |
v3 = -1 |
v4 = 0 |
Загальна вартість перевезень продукції згідно з першим опорним планом визначається у такий спосіб:
Z1 = 4 110 + 5 40 + 1 60 + 1 40 + 2 40 = 820 (ум. од.).
Перший опорний план транспортної задачі вироджений, оскільки кількість заповнених клітинок у таблиці дорівнює п'яти, а (m + n - 1) = 3 + 4 - 1 = 6.
Для дальшого розв'язування задачі необхідно в одну з порожніх клітинок записати «нульове перевезення» так, щоб не порушити опорності плану, тобто можна зайняти будь-яку пусту клітинку, яка не утворює замкненого циклу із заповненими клітинами. Наприклад, заповнимо нулем клітинку А2В4. Тепер перший план транспортної задачі є невиродженим, і його можна перевірити на оптимальність методом потенціалів.
На основі першої умови оптимальності ui + vj = cij складемо систему рівнянь (для заповнених клітин таблиці) для визначення потенціалів першого опорного плану:
Записана система рівнянь є невизначеною, і один з її розв'язків дістанемо, узявши, наприклад, v4 = 0. Тоді всі інші потенціали однозначно визначаються з цієї системи рівнянь: u1 = 5, u2 = 2, u3 = 2, v1 = - 1, v2 = - 1, v3 = - 1. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.
Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui + vj ? cij (для порожніх клітинок таблиці):
А1B2 : u1 + v2 = 5 + (-1) = 4 = 4;
А1B3 : u1 + v3 = 5 + (-1) = 4 > 2;
А2B1 : u2 + v1 = 2 + (-1) = 1 < 5;
А2B2 : u2 + v2 = 2 + (-1) = 1 < 3;
А3B1 : u3 + v1 = 2 + (-1) = 1 < 2;
А3B3 : u3 + v3 = 2 + (-1) = 1 < 4.
Умова оптимальності не виконується для клітинки А1B3. Порушення 13 = (u1 + v3) - c13 = 4 - 2 = 2 записуємо в лівому нижньому кутку відповідної клітинки.
Отже, перший опорний план транспортної задачі неоптимальний. Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці.
Потрібно заповнити клітинку А1B3, в якій є єдине порушення умови оптимальності. Ставимо в ній знак «+». Для визначення клітинки, що звільняється, будуємо цикл, починаючи з клітинки А1B3, та позначаємо вершини циклу почергово знаками «-» і «+». Тепер необхідно перемістити продукцію в межах побудованого циклу. Для цього у порожню клітинку А1B3 переносимо менше з чисел хij, які розміщені в клітинках зі знаком «-». Одночасно це саме число хij додаємо до відповідних чисел, що розміщені в клітинках зі знаком «+», та віднімаємо від чисел, що розміщені в клітинках, позначених знаком «-».
У даному разі , тобто . Виконавши перерозподіл перевезень продукції згідно із записаними правилами, дістанемо такі нові значення: для клітинки А1B3 -- 40 од. продукції, а для А2B3 - (60 - 40) = 20 од., а для А2B4 - (0 + 40) = 40 од. Клітинка А1B4 звільняється і в новій таблиці буде порожньою. Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n + m - 1).
Отже, другий опорний план транспортної задачі матиме такий вигляд (табл. 5.12):
Таблиця 5.12
|
Ai |
Bj |
ui |
||||
|
b1 = 110 |
b2 = 40 |
b3 = 60 |
b4 = 80 |
|||
|
a1 = 150 |
4 110 |
4 |
2 40 |
5 |
u1 = 0 |
|
|
a2 = 60 |
5 |
3 |
1 20 |
2 40 |
u2 = -1 |
|
|
a3 = 80 |
2 1 |
1 40 |
4 |
2 40 |
u3 = -1 |
|
|
vj |
v1 = 4 |
v2 = - 2 |
v3 = 2 |
v4 = 3 |
Розрахуємо значення цільової функції відповідно до другого опорного плану задачі:
Z2 = 4 110 + 2 40 + 1 20 + 2 40 + 1 40 + 2 40 = 740 (ум. од.).
Новий план знову перевіряємо на оптимальність, тобто повторюємо описані раніше дії. Другий опорний план транспортної задачі також неоптимальний (має місце порушення для клітинки А3B1). За допомогою побудованого циклу, виконавши перехід до третього опорного плану транспортної задачі, отримуємо табл. 5.13:
Таблиця 5.13
|
Ai |
Bj |
ui |
||||
|
b1 = 110 |
b2 = 40 |
b3 = 60 |
b4 = 80 |
|||
|
a1 = 150 |
4 90 |
4 |
2 60 |
5 |
u1 = 2 |
|
|
a2 = 60 |
5 |
3 |
1 |
2 60 |
u2 = 0 |
|
|
a3 = 80 |
2 20 |
1 40 |
4 |
2 20 |
u3 = 0 |
|
|
vj |
v1 = 2 |
v2 = 1 |
v3 = 0 |
v4 = 2 |
Визначимо загальну вартість витрат на транспортування продукції згідно з третім опорним планом:
Z3 = 4 90 + 2 60 + 2 60 + 2 20 + 1 40 + 2 20 = 720 (ум. од.).
Перевірка останнього плану на оптимальність за допомогою методу потенціалів показує, що він оптимальний. Тому:
.
За оптимальним планом перевезень перший замовник отримує 90 тис. од. продукції з першої фабрики та 20 тис. од. -- з третьої. Другий споживач задовольняє свій попит за рахунок виробництва та перевезення 40 тис. од. продукції з третьої фабрики і т. д. При цьому загальна вартість перевезень всієї продукції є найменшою і становить 720 ум. од.
Размещено на Allbest.ru
...Подобные документы
Поняття задачі лінійного програмування та різні форми її задання. Загальна характеристика транспортної задачі, її математична модель. Графічний метод для визначення оптимального плану задач лінійного програмування. Правило побудови двоїстої задачі.
контрольная работа [1,5 M], добавлен 04.09.2015Розробка оптимізаційної моделі бюджету доходів та витрат на прикладі ВАТ "ІнГЗК". Теоретичні аспекти застосування моделі транспортної задачі в економічних процесах. Економічна і математична постановки транспортної задачі та методи її розв'язання.
курсовая работа [585,1 K], добавлен 19.04.2011Оптимальні обсяги виробництва електроплит різних моделей, що максимізують дохід фірми. Оптимальний план двоїстої задачі до поставленої задачі лінійного програмування. Побудова математичної моделі транспортної задачі. Мінімальне значення цільової функції.
контрольная работа [274,1 K], добавлен 28.03.2011Побудова математичної моделі плану виробництва, який забезпечує найбільший прибуток. Розв’язок задачі симплекс-методом, графічна перевірка оптимальних результатів. Складання опорного плану транспортної задачі. Пошук екстремумів функцій графічним методом.
контрольная работа [286,4 K], добавлен 28.03.2011Математична модель задачі лінійного програмування та її розв’язок симплекс-методом. Опорний план математичної моделі транспортної задачі. Оптимальний план двоїстої задачі. Рішення графічним методом екстремумів функції в області, визначеній нерівностями.
контрольная работа [290,0 K], добавлен 28.03.2011Побудова опорного плану систему нерівностей. Постановка задачі на максимум. Індексний рядок та негативні коефіцієнти. Задача лінійного програмування. Рішення задачі симплексним методом. Введення додаткових змінних. Оптимальний план двоїстої задачі.
контрольная работа [278,4 K], добавлен 28.03.2011Розробка програмного комплексу для розв’язання задачі цілочисельного програмування типу "Задача комівояжера". Класифікація задач дослідження операцій. Вибір методу розв’язання транспортної задачі; алгоритмічне і програмне забезпечення, тести і документи.
курсовая работа [807,7 K], добавлен 07.12.2013Задачі лінійного програмування. Побудова першого опорного плану системи нерівностей. Введення додаткових змінних. Індексний рядок та негативні коефіцієнти. Побудова математичної моделі. Визначення потенціалів опорного плану. Область допустимих значень.
контрольная работа [232,3 K], добавлен 28.03.2011Побудова математичної моделі плану перевезення зерна на елеватори, який мінімізує транспортні витрати. Розв’язок задачі симплексним методом. Знаходження графічним методом екстремумів функцій, визначеній нерівностями. Порядок рішення транспортної задачі.
контрольная работа [326,2 K], добавлен 28.03.2011Загальна характеристика методів оптимізації для рішення економічних задач. Аналіз виконання плану перевезень в Донецькому АТП. Використання мереженого планування для рішення транспортної задачі. Організація управління охорони праці на робочому місці.
дипломная работа [3,3 M], добавлен 09.11.2013Поняття логістичних ланцюгів. Методи побудови початкового опорного плану. Визначення та розрахунок потенціалу кожної вершини. Методи пошуку оптимального рішення. Алгоритм оптимізації транспортної задачі: логістичного ланцюга за допомогою симплекс-методу.
дипломная работа [1,1 M], добавлен 20.11.2013Багатокритеріальність, існуючі методи розв’язку задач лінійного програмування. Симплекс метод в порівнянні з графічним. Вибір методу розв’язання багатокритеріальної задачі лінійного програмування. Вирішення задачі визначення максимального прибутку.
курсовая работа [143,7 K], добавлен 15.12.2014Математична модель задачі лінійного програмування, її вирішення за допомогою симплекс-методу. Побудова екстремумів функцій в області, визначеній нерівностями, за допомогою графічного методу. Математична модель транспортної задачі та її опорний план.
контрольная работа [241,7 K], добавлен 28.03.2011Загальна модель задачі математичного програмування, задача лінійного програмування та особливості симплекс–методу для розв’язання задач лінійного програмування Економіко–математична модель конкретної задачі, алгоритм її вирішення за допомогою Exel.
контрольная работа [109,7 K], добавлен 24.11.2010Побудування математичної моделі задачі. Розв'язання задачі за допомогою лінійного програмування та симплексним методом. Наявність негативних коефіцієнтів в індексному рядку. Основний алгоритм симплексного методу. Оптимальний план двоїстої задачі.
контрольная работа [274,8 K], добавлен 28.03.2011Приклади задач математичного програмування (на добір оптимальної суміші сплавів, складання оптимального раціону, транспортна, про оптимальний добір). Економічна модель задачі. Геометрична інтерпретація стандартної задачі, її розв’язання симплекс-методом.
курсовая работа [8,3 M], добавлен 28.11.2010Загальна характеристика підприємства, аналіз виконання плану перевезень та планування показників діяльності. Оптимізація грузоперевезень за допомогою транспортної задачі. Використання мереженого планування та симплекс-методу для рішення даної задачі.
дипломная работа [1,5 M], добавлен 20.11.2013Задача на максимізацію прибутку компанії, визначення оптимального обсягу виробництва, що приносить компанії оптимальний прибуток. Економіко-математична модель оптимізаційної транспортної задачі. Задача мінімізації витрат на доставку і збереження товару.
контрольная работа [63,4 K], добавлен 02.02.2011Норми затрат ресурсів. Математична модель задачі. Рішення прямої задачі лінійного програмування симплексним методом. Основний алгоритм симплекс-методу. Область допустимих рішень. Розв’язок методом симплексних таблиць. Мінімальне значення цільової функції.
контрольная работа [234,6 K], добавлен 28.03.2011Визначення оптимальних обсягів виробництва, що максимізують дохід фірми, та розв'язання транспортної задачі за допомогою математичного моделювання та симплекс-методу. Знайдення графічним методом екстремумів функції в області, визначеній нерівностями.
контрольная работа [280,6 K], добавлен 28.03.2011
