Розв’язання лінійних задач методами лінійного програмування
З таблиці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 | 5 | 15 | ||||
|
|
5 | 2 | 7 | 5 | 0 | 20 | -2 |
| 20 | |||||||
|
|
5 | 4 | 8 | 2 | 0 | 30 | -2 |
| 20 | 10 | ||||||
|
|
7 | 1 | 5 | 7 | 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гривень.
Список використаних джерел
Кузнецов Ю.Н. Математическое программирование. Учебное пособие для вузов– М.: Высшая школа, 1976.– 352с.
Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию.– Мн.: Высш. школа, 1978.– 256с.