[ Розвязання лінійних задач методами лінійного програмування ] | 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– Перевірка оптимальності опорного плану
Виробник | Споживач | Запаси продукту | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
8 | 3 | 3 | 4 | 0 | 60 | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 40 | 20 |
|
|
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
5 | 2 | 7 | 5 | 0 | 20 | -1 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
| 10 | 10 |
|
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
5 | 4 | 8 | 2 | 0 | 30 | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
| 20 | 10 |
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
7 | 1 | 5 | 7 | 0 | 20 | 5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
| 5 | 15 |
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Потреба в продукті | 40 | 30
Систему потенціалів можна побудувати лише для невирожденого опорного плану. Такий план містить 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– Другий крок пошуку оптимального рішення
Транспортні витрати при такому плані перевезення складають:
Перевірка всіх вільних клітин:
Отримали від’ємні значення у всіх клітинах окрім А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– Третій крок пошуку оптимального рішення
Транспортні витрати:
тобто при такому плані перевезення товару транспортні витрати знизилися на 50грн. в порівнянні з попереднім планом перевезення. Але, щоб визначити є отриманий план оптимальним чи ні, виконаємо перевірку. Перевірку всіх вільних клітин зобразимо в таблиці9, в якій для всіх вільних клітин запишемо різницю між сумою потенціалів і транспортними витратами в клітині. Таблиця9– Перевірка плану отриманого в результаті третього кроку пошуку оптимального рішення задачі
З таблиці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– Четвертий крок пошуку оптимального рішення задачі
Транспортні витрати:
що на 120грн. економніше попереднього варіанту розвезення продукції від постачальників до споживачів. Перевірка всіх вільних клітин наведена в таблиці11. Таблиця11– Різниця між сумою потенціалів і транспортними витратами для вільних клітин
План, зображений в таблиці10 не є оптимальним, оскільки отримали додатні значення в клітинах А1В4 (1), А2В1 (2), А4В1 (3), А4В2 (4). Заповнюємо клітину А4В2 і будуємо опорний план (таблиця12). Таблиця12– П’ятий крок пошуку оптимального рішення задачі
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
8 | 3 | 3 | 4 | 0 | 60 | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 25 | 5 | 30 |
|
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
5 | 2 | 7 | 5 | 0 | 20 | -1 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
| 20 |
|
|
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
5 | 4 | 8 | 2 | 0 | 30 | -3 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 15 |
|
| 15 |
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
7 | 1 | 5 | 7 | 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– Шостий крок пошуку оптимального рішення задачі
Виробник | Споживач | Запаси продукту | |||||
|
|
| |||||
8 | 3 | 3 | 4 | 0 | 60 | 0 | |
| 25 |
| 30 |
| 5 |
|
|
5 | 2 | 7 | 5 | 0 | 20 | -1 | |
|
| 20 |
|
|
|
|
|
5 | 4 | 8 | 2 | 0 | 30 | -3 | |
| 15 |
|
| 15 |
|
|
|
7 | 1 | 5 | 7 | 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– Сьомий крок пошуку оптимального рішення задачі
Виробник | Споживач | Запаси продукту | |||||
|
|
| |||||
8 | 3 | 3 | 4 | 0 | 60 | 0 | |
| 15 |
| 30 |
| 15 |
|
|
5 | 2 | 7 | 5 | 0 | 20 | -3 | |
| 10 | 10 |
|
|
|
|
|
5 | 4 | 8 | 2 | 0 | 30 | -3 | |
| 15 |
|
| 15 |
|
|
|
7 | 1 | 5 | 7 | 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– Восьмий крок пошуку оптимального рішення задачі
Виробник | Споживач | Запаси продукту | |||||
|
|
| |||||
8 | 3 | 3 | 4 | 0 | 60 | 0 | |
| 5 | 10 | 30 |
| 15 |
|
|
5 | 2 | 7 | 5 | 0 | 20 | -3 | |
| 20 |
|
|
|
|
|
|
5 | 4 | 8 | 2 | 0 | 30 | -3 | |
| 15 |
|
| 15 |
|
|
|
7 | 1 | 5 | 7 | 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– Дев’ятий крок пошуку оптимального рішення задачі
Виробник | Споживач | Запаси продукту | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
8 | 3 | 3 | 4 | 0 | 60 | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
| 10 | 30
Розрахунки для перевірка всіх вільних клітин здійснені в таблиці 21: Таблиця21– Різниця між сумою потенціалів і транспортними витратами для вільних клітин
Рішення, зображене в таблиці20 є оптимальним, оскільки для кожної незайнятої клітини сума потенціалів менша вартості перевезень, що знаходиться у відповідній клітинці. Транспортні витрати по оптимальному плану перевезень становлять:
Знайдений оптимальний план покращив результат діяльності у порівнянні з початковим (зменшив транспортні витрати) на 685-380=305гривень. Список використаних джерел
|