Розв’язання лінійних задач методами лінійного програмування
![]()
![]()
Таким чином, в таблиці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 | 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– Другий крок пошуку оптимального рішення
| Виробник | Споживач | Запаси продукту |
|
||||
|
|
|
|
|
|
|||
|
|
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 |
| 15 | 15 | ||||||
|
|
7 | 1 | 5 | 7 | 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– Третій крок пошуку оптимального рішення
| Виробник | Споживач | Запаси продукту |
|
||||
|
|
|
|
|
|
|||
|
|
8 | 3 | 3 | 4 | 0 | 60 | - |
| 40 | 10 | 10 | |||||
|
|
5 | 2 | 7 | 5 | 0 | 20 | -1 |
| 20 | |||||||
|
|
5 | 4 | 8 | 2 | 0 | 30 | 5 |
| 15 | 15 | ||||||
|
|
7 | 1 | 5 | 7 | 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– Четвертий крок пошуку оптимального рішення задачі
| Виробник | Споживач | Запаси продукту |
|
||||
|
|
|
|
|
|
|||
|
|
8 | 3 | 3 | 4 | 0 | 60 | 0 |
| 25 | 10 | 25 | |||||
|
|
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 | Ч | Ч |
Транспортні витрати:
![]()
що на 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– П’ятий крок пошуку оптимального рішення задачі
| Виробник | Споживач | Запаси продукту |
|
||||
|
|
|
|
|
|
|||
|
|
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 |
|
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.),
обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus.
Помогаем в публикации. Правки вносим бесплатно.
Похожие рефераты: |