Завдання №4
Визначити оптимальний план транспортної задачі:
а) побудувати початковий опорний план методом "північно-західного" напрямку;
б) побудувати оптимальний план методом потенціалів:
Нехай в матриці А міститься інформація про кількість продукту в кожному місці виробництва, який необхідно доставити споживачам в кількості записаній в матриці В. Транспортні витрати, повязані з перевезенням одиниці продукту із одного місця виробництва одному споживачеві, записані в матриці С. Задані матриці і сказане вище для спрощення сприйняття узагальнимо в таблиці4.
Таблиця4-Поставка продукту із різних місць виробництва різним споживачам і повязані з цим витрати
Виробник |
Споживач |
Запаси продукту |
||||
8 |
3 |
3 |
4 |
60 |
||
5 |
2 |
7 |
5 |
20 |
||
5 |
4 |
8 |
2 |
30 |
||
7 |
1 |
5 |
7 |
20 |
||
Потреба в продукті |
40 |
30 |
30 |
15 |
130 115 |
З таблиці4 видно, що запаси продукту у виробника на складах на 15 одиниць більші ніж необхідно споживачу, тобто маємо транспортну задачу з відкритою моделлю. Для розвязку такої задачі введемо фіктивного споживача, якому необхідно отримати одиниць продукту. Всі тарифи на доставку продукту цьому споживачеві будемо вважати рівними нулю, і весь продукт потрібний цьому споживачеві залишаємо у місці виробництва. Для побудови початкового плану перевезень (таблиця5) використаємо метод "північно-західного" напрямку: заповнювати таблицю починаємо з лівого верхнього кута, рухаючись вниз по стовбцю або вправо по рядку (тарифи перевезень напишемо в правому верхньому куту кожної клітини, кількість продукту - в нижньому лівому). В першу клітину заносимо менше з чисел (min(40;60): 40. Тобто потреба в продукті першого споживача повністю задовільнено і інші клітини першого стовпця заповнювати не будемо. Рухаємося далі по першому рядку в другий стовпчик. В цю клітину записуємо менше з 30 і (60-40), тобто пишемо 20. Таким чином перший рядок заповнювати далі не будемо, оскільки запаси першого місця виробництва остаточно вичерпано: з нього ми повністю задовольняємо потребу у продукті першого споживача і частково (20 одиниць, а не 30) другого. Рухаємося по другому стовпчику на другий рядок. Сюди записуємо менше з (30-20) або 20: маємо 10, тобто другому споживачеві ми веземо 20одиниць продукту з першого місця виробництва і 10- з другого. Аналогічно заповнюємо інші клітини.
Таблиця5- Розподіл продукту по споживачам
Виробник |
Споживач |
Запаси продукту |
|||||
8 |
3 |
3 |
4 |
0 |
60 |
||
40 |
20 |
||||||
5 |
2 |
7 |
5 |
0 |
20 |
||
10 |
10 |
||||||
5 |
4 |
8 |
2 |
0 |
30 |
||
20 |
10 |
||||||
7 |
1 |
5 |
7 |
0 |
20 |
||
5 |
15 |
||||||
Потреба в продукті |
40 |
30 |
30 |
15 |
15 |
130 |
Таким чином, в таблиці5 отримали початковий опорний план, транспортні витрати за яким складають:
Недоліком використаного методу знаходження опорного плану є ігнорування величини тарифів на перевезення продукту.
Для визначення оптимального плану перевезень використаємо метод потенціалів. Для цього кожному виробнику Аі (кожному рядку) ставимо у відповідність деяке число а кожному споживачу Ві (кожному стовпчику)- деяке число На основі таблиці5 складемо таблицю6, в якій додамо один стовпчик і один рядок для написання величини параметрів і . Їх знаходимо використовуючи першу умову оптимальності транспортної задачі: (для кожної зайнятої клітини сума потенціалів повинна дорівнювати вартості одиниці перевезення, що записана в цій клітині).
Таблиця6- Перевірка оптимальності опорного плану
Виробник |
Споживач |
Запаси продукту |
||||||
"right">8 | "right">3 | "right">3 | "right">4 | "right">0 |
60 |
0 |
||
40 |
20 |
|||||||
"right">5 | "right">2 | "right">7 | "right">5 | "right">0 |
20 |
-1 |
||
10 |
10 |
|||||||
"right">5 | "right">4 | "right">8 | "right">2 | "right">0 |
30 |
0 |
||
20 |
10 |
|||||||
"right">7 | "right">1 | "right">5 | "right">7 | "right">0 |
20 |
5 |
||
5 |
15 |
|||||||
Потреба в продукті |
40 |
30 |
30 |
15 |
15 |
130 |
Ч |
|
8 |
3 |
8 |
2 |
-5 |
Ч |
Ч |
Систему потенціалів можна побудувати лише для невирожденого опорного плану. Такий план містить m+n-1 лінійно незалежних рівнянь виду з m+n невідомими (де m- кількість постачальників, n- кількість споживачів). Рівнянь на одне менше, ніж невідомих, тому система є невизначеною і для її розвязку одному невідомому (нехай ним буде u1) придамо нульове значення.
Для того, щоб план був оптимальним, повинна виконуватись умова: для кожної незайнятої клітини сума потенціалів повинна бути менша або дорівнювати вартості одиниці перевезення, що стоїть в цій клітині: тобто Робимо перевірку для всіх вільних клітин:
З розрахунків бачимо, що умова оптимальності не виконується для клітин, А1В3, А2В1, А3В1, А4В1, А4В2, і А4В3. Клітину, в якій додатне число отримали максимальним (А2В3, оскільки max(5;2;3;6;7;8)=8) зробимо зайнятою, для цього побудуємо цикл і отримуємо таблицю7.
Таблиця7- Другий крок пошуку оптимального рішення
Виробник |
Споживач |
Запаси продукту |
||||||
"right">8 | "right">3 | "right">3 | "right">4 | "right">0 |
60 |
0 |
||
40 |
20 |
|||||||
"right">5 | "right">2 | "right">7 | "right">5 | "right">0 |
20 |
-1 |
||
10 |
10 |
|||||||
"right">5 | "right">4 | "right">8 | "right">2 | "right">0 |
30 |
0 |
||
15 |
15 |
|||||||
"right">7 | "right">1 | "right">5 | "right">7 | "right">0 |
20 |
-3 |
||
5 |
15 |
|||||||
Потреба в продукті |
40 |
30 |
30 |
15 |
15 |
130 |
Ч |
|
8 |
3 |
8 |
2 |
3 |
Ч |
Ч |
Транспортні витрати при такому плані перевезення складають:
Перевірка всіх вільних клітин:
Отримали відємні значення у всіх клітинах окрім А1В3 (5), А1В5 (3), А2В1 (2), А2В5 (2), А3В1 (3) і А3В5 (3). Максимальне значення max(5;3;2;2;3;3)=5 в клітині А1В3, тому заповнюємо і цикл будуємо для неї (цикл показано в таблиці7, результат дій в таблиці8).
Таблиця8- Третій крок пошуку оптимального рішення
Виробник |
Споживач |
Запаси продукту |
||||||
"right">8 | "right">3 | "right">3 | "right">4 | "right">0 |
60 |
- |
||
40 |
10 |
10 |
||||||
"right">5 | "right">2 | "right">7 | "right">5 | "right">0 |
20 |
-1 |
||
20 |
||||||||
"right">5 | "right">4 | "right">8 | "right">2 | "right">0 |
30 |
5 |
||
15 |
15 |
|||||||
"right">7 | "right">1 | "right">5 | "right">7 | "right">0 |
20 |
2 |
||
5 |
15 |
|||||||
Потреба в продукті |
40 |
30 |
30 |
15 |
15 |
130 |
Ч |
|
8 |
3 |
3 |
-3 |
-2 |
Ч |
Ч |
Транспортні витрати:
тобто при такому плані перевезення товару транспортні витрати знизилися на 50грн. в порівнянні з попереднім планом перевезення. Але, щоб визначити є отриманий план оптимальним чи ні, виконаємо перевірку.
Перевірку всіх вільних клітин зобразимо в таблиці9, в якій для всіх вільних клітин запишемо різницю між сумою потенціалів і транспортними витратами в клітині.
Таблиця9- Перевірка плану отриманого в результаті третього кроку пошуку оптимального рішення задачі
- |
- |
- |
-7 |
-2 |
||
2 |
- |
-5 |
-9 |
-3 |
||
8 |
4 |
- |
- |
3 |
||
3 |
4 |
- |
-8 |
- |
З таблиці9 видно, що додатне значення отримали для клітин А2В1 (2), А3В1 (8), А3В2 (4), А3В5 (3), А4В1 (3) і А4В2 (4). Максимальне значення max(2;8;4;3;3;4)=8 в клітині А3В1, тому заповнюємо і цикл будуємо для неї (цикл показано в таблиці8, результат дій в таблиці10).
Таблиця1- Четвертий крок пошуку оптимального рішення задачі
Виробник |
Споживач |
Запаси продукту |
||||||
"right">8 | "right">3 | "right">3 | "right">4 | "right">0 |
60 |
0 |
||
25 |
10 |
25 |
||||||
"right">5 | "right">2 | "right">7 | "right">5 | "right">0 |
20 |
-1 |
||
20 |
||||||||
"right">5 | "right">4 | "right">8 | "right">2 | "right">0 |
30 |
-3 |
||
15 |
15 |
|||||||
"right">7 | "right">1 | "right">5 | "right">7 | "right">0 |
20 |
2 |
||
5 |
15 |
|||||||
Потреба в продукті |
40 |
30 |
30 |
15 |
15 |
130 |
Ч |
|
8 |
3 |
3 |
5 |
-2 |
Ч |
Ч |
Транспортні витрати:
що на 120грн. економніше попереднього варіанту розвезення продукції від постачальників до споживачів.
Перевірка всіх вільних клітин наведена в таблиці11.
Таблиця11- Різниця між сумою потенціалів і транспортними витратами для вільних клітин
- |
- |
- |
1 |
-2 |
||
2 |
- |
-5 |
-1 |
-3 |
||
- |
-4 |
-8 |
- |
-5 |
||
3 |
4 |
- |
0 |
- |
План, зображений в таблиці10 не є оптимальним, оскільки отримали додатні значення в клітинах А1В4 (1), А2В1 (2), А4В1 (3), А4В2 (4). Заповнюємо клітину А4В2 і будуємо опорний план (таблиця12).
Таблиця12- Пятий крок пошуку оптимального рішення задачі
Виробник |
Споживач |
Запаси продукту |
||||||
"right">8 | "right">3 | "right">3 | "right">4 | "right">0 |
60 |
0 |
||
25 |
5 |
30 |
||||||
"right">5 | "right">2 | "right">7 | "right">5 | "right">0 |
20 |
-1 |
||
20 |
||||||||
"right">5 | "right">4 | "right">8 | "right">2 | "right">0 |
30 |
-3 |
||
15 |
15 |
|||||||
"right">7 | "right">1 | "right">5 | "right">7 | "right">0 |
20 |
-2 |
||
5 |
15 |
|||||||
Потреба в продукті |
40 |
30 |
30 |
15 |
15 |
130 |
Ч |
|
8 |
3 |
3 |
5 |
2 |
Ч |
Ч |
Транспортні витрати за отриманим планом перевезень складають:
що на 20грн. економніше попереднього варіанту розвезення продукції від постачальників до споживачів.
Перевірка всіх вільних клітин здійснена в таблиці 13.
Таблиця13- Різниця між сумою потенціалів і транспортними витратами для вільних клітин
- |
- |
- |
1 |
2 |
||
2 |
- |
-5 |
-1 |
1 |
||
- |
-4 |
-8 |
- |
-1 |
||
-1 |
- |
-4 |
-4 |
- |
Оскільки в результаті розрахунків отримали додатні значення, то знову будуємо цикл і заповнюємо необхідну клітину. В даному випадку це буде або клітина А2В1 або клітина А1В5. Вибираємо останню, оскільки транспортні витрати на перевезення в ній менші. На відємних кутах циклу обєм перевезень становить 10 і 0. Оскільки min(10;0)=0, то всі клітини залишаються незмінними і лише клітина з нульовим перевезенням переходить з А4В5 на А1В5.
Новий план зображено в таблиці14.
Таблиця14- Шостий крок пошуку оптимального рішення задачі
Виробник |
Споживач |
Запаси продукту |
||||||
"right">8 | "right">3 | "right">3 | "right">4 | "right">0 |
60 |
0 |
||
25 |
30 |
5 |
||||||
"right">5 | "right">2 | "right">7 | "right">5 | "right">0 |
20 |
-1 |
||
20 |
||||||||
"right">5 | "right">4 | "right">8 | "right">2 | "right">0 |
30 |
-3 |
||
15 |
15 |
|||||||
"right">7 | "right">1 | "right">5 | "right">7 | "right">0 |
20 |
0 |
||
10 |
10 |
|||||||
Потреба в продукті |
40 |
30 |
30 |
15 |
15 |
130 |
Ч |
|
8 |
1 |
3 |
5 |
0 |
Ч |
Ч |
Транспортні витрати за отриманим планом перевезень складають:
Розрахунки для перевірка всіх вільних клітин здійснені в таблиці 15:
Таблиця15- Різниця між сумою потенціалів і транспортними витратами для вільних клітин
- |
-2 |
- |
1 |
- |
||
4 |
- |
-3 |
1 |
1 |
||
- |
-6 |
-8 |
- |
-3 |
||
1 |
- |
-2 |
-2 |
- |
З таблиці15 видно, що максимальне додатне значення отримали для клітини А2В1, тому заповнюємо її будуючи для неї цикл, який показано в таблиці14. Результат дій в таблиці16.
Таблиця16- Сьомий крок пошуку оптимального рішення задачі
Виробник |
Споживач |
Запаси продукту |
||||||
"right">8 | "right">3 | "right">3 | "right">4 | "right">0 |
60 |
0 |
||
15 |
30 |
15 |
||||||
"right">5 | "right">2 | "right">7 | "right">5 | "right">0 |
20 |
-3 |
||
10 |
10 |
|||||||
"right">5 | "right">4 | "right">8 | "right">2 | "right">0 |
30 |
-3 |
||
15 |
15 |
|||||||
"right">7 | "right">1 | "right">5 | "right">7 | "right">0 |
20 |
-4 |
||
20 |
||||||||
Потреба в продукті |
40 |
30 |
30 |
15 |
15 |
130 |
Ч |
|
8 |
5 |
3 |
5 |
0 |
Ч |
Ч |
Транспортні витрати:
що на 40грн. економніше попереднього варіанту розвезення продукції від постачальників до споживачів.
Перевірка всіх вільних клітин наведена в таблиці17.
Таблиця17- Різниця між сумою потенціалів і транспортними витратами для вільних клітин
- |
2 |
- |
1 |
- |
||
- |
- |
-7 |
-3 |
-3 |
||
- |
-2 |
-8 |
- |
-3 |
||
-3 |
- |
-6 |
-6 |
-4 |
План, зображений в таблиці8 не є оптимальним, оскільки отримали додатні значення в клітинах А1В2 (2) і А1В4 (1). Заповнюємо клітину А1В2 і будуємо опорний план (таблиця18).
Таблиця18- Восьмий крок пошуку оптимального рішення задачі
Виробник |
Споживач |
Запаси продукту |
||||||
"right">8 | "right">3 | "right">3 | "right">4 | "right">0 |
60 |
0 |
||
5 |
10 |
30 |
15 |
|||||
"right">5 | "right">2 | "right">7 | "right">5 | "right">0 |
20 |
-3 |
||
20 |
||||||||
"right">5 | "right">4 | "right">8 | "right">2 | "right">0 |
30 |
-3 |
||
15 |
15 |
|||||||
"right">7 | "right">1 | "right">5 | "right">7 | "right">0 |
20 |
-2 |
||
20 |
||||||||
Потреба в продукті |
40 |
30 |
30 |
15 |
15 |
130 |
Ч |
|
8 |
3 |
3 |
5 |
0 |
Ч |
Ч |
Транспортні витрати за отриманим планом перевезень складають:
що на 20грн. економніше попереднього варіанту розвезення продукції від постачальників до споживачів. Перевірка всіх вільних клітин здійснена в таблиці 19.
Таблиця19- Різниця між сумою потенціалів і транспортними витратами для вільних клітин
- |
- |
- |
1 |
- |
||
- |
-2 |
-7 |
-3 |
-3 |
||
- |
-4 |
-8 |
- |
-3 |
||
-1 |
- |
-4 |
-4 |
-2 |
Оскільки в результаті розрахунків отримали додатне значення в єдиній клітині А1В4, то будуємо цикл і заповнюємо її. Новий план зображено в таблиці20.
Таблиця20- Девятий крок пошуку оптимального рішення задачі
Виробник |
Споживач |
Запаси продукту |
||||||
"right">8 | "right">3 | "right">3 | "right">4 | "right">0 |
60 |
0 |
||
10 |
30 |
5 |
15 |
|||||
"right">5 | "right">2 | "right">7 | "right">5 | "right">0 |
20 |
-2 |
||
20 |
||||||||
"right">5 | "right">4 | "right">8 | "right">2 | "right">0 |
30 |
-2 |
||
20 |
10 |
|||||||
"right">7 | "right">1 | "right">5 | "right">7 | "right">0 |
20 |
-2 |
||
20 |
||||||||
Потреба в продукті |
40 |
30 |
30 |
15 |
15 |
130 |
Ч |
|
7 |
3 |
3 |
4 |
0 |
Ч |
Ч |
Розрахунки для перевірка всіх вільних клітин здійснені в таблиці 21:
Таблиця21- Різниця між сумою потенціалів і транспортними витратами для вільних клітин
-1 |
- |
- |
- |
- |
||
- |
-1 |
-6 |
-3 |
-2 |
||
- |
-3 |
-7 |
- |
-2 |
||
-2 |
- |
-4 |
-5 |
-2 |
Рішення, зображене в таблиці20 є оптимальним, оскільки для кожної незайнятої клітини сума потенціалів менша вартості перевезень, що знаходиться у відповідній клітинці. Транспортні витрати по оптимальному плану перевезень становлять:
Знайдений оптимальний план покращив результат діяльності у порівнянні з початковим (зменшив транспортні витрати) на 685-380=305гривень.
- Симплекс-метод розв’язання задачі лінійного програмування.
- Тема лекції: Задача дробово-лінійного програмування
- Тема 8. Задача лінійного програмування та методи її розв’язування
- 1. Сутність і методи лінійного програмування
- 59. Суть алгоритму графічного методу розв’язання задач лінійного програмування.
- Тема 2. Графічний метод та симплекс метод розв’язування задач лінійного програмування
- 21 .Алгоритм симплексного методу для задач лінійного програмування.
- 29. Властивості розв’язків задачі лінійного програмування. Геометрична інтерпретація задач лінійного програмування.
- 31. Приведення задачі дробово-лінійного програмування до оптимізаційної задачі лінійного програмування.