Розв'язок задачі лінійного програмування
.
Зрозуміло, що покупці ресурсів прагнуть здійснити операцію якнайдешевше, отже необхідно визначити мінімальну вартість одиниці кожного виду ресурсів за якої їх продаж є більш доцільним ніж виготовлення продукції. Загальна вартість ресурсів виражається величиною
.
Отже в результаті маємо двоїсту задачу:
Визначити,
які мінімальні
ціни можливо
встановити
для одиниці
кожного і-го
виду ресурсу
,
щоб продаж
ресурсів був
більш доцільним
ніж виробництво
продукції.
Причому відомі:
загальна кількість
ресурсів –
,
нормативи
використання
кожного і-го
виду ресурсу
на кожен j-ий
вид продукції
–
,
а також
– ціна реалізації
одиниці продукції.
Для побудови
двоїстої задачі
необхідно
звести початкову
до стандартного
виду. Задача
лінійного
програмування
подана у стандартному
вигляді, якщо
для відшукання
максимального
значення цільової
функції всі
нерівності
системи обмежень
приведені до
вигляду «
»,
а для задачі
відшукання
мінімального
значення – до
вигляду «
».
Якщо пряма задача лінійного програмування подана в стандартному вигляді, то двоїста задача утворюється за такими правилами:
1. Кожному обмеженню прямої задачі відповідає змінна двоїстої задачі. Кількість невідомих двоїстої задачі дорівнює кількості обмежень прямої задачі.
2. Кожній змінній прямої задачі відповідає обмеження двоїстої задачі, причому кількість обмежень дорівнює кількості невідомих прямої задачі.
3. Якщо цільова функція прямої задачі задається на пошук найбільшого значення (max), то цільова функція двоїстої задачі — на визначення найменшого значення (min), і навпаки.
4. Коефіцієнтами при змінних в цільовій функції двоїстої задачі є вільні члени системи обмежень прямої задачі.
5. Правими частинами системи обмежень двоїстої задачі є коефіцієнти при змінних в цільовій функції прямої задачі.
6. Матриця
,
що складається з коефіцієнтів при змінних у системі обмежень прямої задачі, і матриця коефіцієнтів в системі обмежень двоїстої задачі

утворюються одна з одної транспонуванням, тобто заміною рядків стовпчиками, а стовпчиків — рядками.
Теорема
(перша теорема
двоїстості).
Якщо одна з
пари спряжених
задач має оптимальний
план, то і інша
також має розв’язок,
причому для
оптимальних
розв’язків
значення цільових
функцій співпадають
.
Якщо цільова функція однієї із задач не обмежена, то інша задача також не має розв’язку.
Між розв’язками спряжених задач крім рівності значень цільових функцій, існує більш тісний взаємозв’язок. Для його дослідження розглянемо дві симетричні задачі лінійного програмування.
Пряма задача: Двоїста задача:
![]()
![]()
Для розв’язування задач симплексним методом необхідно привести їх до канонічної форми, для чого в систему обмежень задачі необхідно ввести m невід’ємних змінних, а в систему обмежень – n невід’ємних змінних. Поставимо обмеженням кожної задачі у відповідність змінні двоїстої.
![]()

Аналогічно:

Отримали наступну відповідність між змінними спряжених задач:
Основні змінні прямої задачі Додаткові змінні прямої задачі
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
Додаткові змінні двоїстої задачі Основні змінні двоїстої задачі
Наступна теорема в літературі як правило має назву теореми про доповнюючу нежорсткість.
Теорема
(друга теорема
двоїстості
для симетричних
задач). Для того,
щоб плани
та
відповідних
спряжених задач
були оптимальними,
необхідно і
достатньо щоб
виконувалися
умови доповнюючої
нежорсткості:
.
Більш очевидно взаємозв’язок між оптимальними планами прямої та двоїстої задач встановлює наслідок другої теореми двоїстості.
Наслідок. Якщо в результаті підстановки оптимального плану однієї із задач (прямої чи двоїстої) в систему обмежень цієї задачі і-те обмеження виконується як строга нерівність, то відповідний і-ий компонент оптимального плану спряженої задачі дорівнює нулю.
Якщо і-ий компонент оптимального плану однієї із задач додатний, то відповідне і-те обмеження спряженої задачі виконується для оптимального плану як рівняння.
Побудуємо двоїсту:

Побудуємо симплекс таблиці для прямої задачі:
| 1 | 3 | 0 | 0 | 0 | ||||
| x1 | x2 | x3 | x4 | x5 | B | T | ||
| x3 | 4 | 3 | 1 | 0 | 0 | 12 | 4 | |
| x4 | -1 | 2 | 0 | 1 | 0 | 4 | 2 | ** |
| x5 | 2 | -1 | 0 | 0 | 1 | 4 | ### | |
| F | -1 | -3 | 0 | 0 | 0 | 0 | 0 | |
| ** | ||||||||
| 1 | 3 | 0 | 0 | 0 | ||||
| x1 | x2 | x3 | x4 | x5 | B | T | ||
| x3 | 5,5 | 0 | 1 | -1,5 | 0 | 6 | 1,09 | ** |
| x2 | -0,5 | 1 | 0 | 0,5 | 0 | 2 | ### | |
| x5 | 1,5 | 0 | 0 | 0,5 | 1 | 6 | 4 | |
| F | -2,5 | 0 | 0 | 1,5 | 0 | 6 | 0 | |
| ** | ||||||||
| 1 | 3 | 0 | 0 | 0 | ||||
| x1 | x2 | x3 | x4 | x5 | B | T | ||
| x1 | 1 | 0 | 0,18 | -0,27 | 0 | 1,09 | 1,09 | |
| x2 | 0 | 1 | 0,09 | 0,36 | 0 | 2,55 | ### | |
| x5 | 0 | 0 | -0,27 | 0,91 | 1 | 4,36 | 4 | |
| F | 0 | 0 | 0,45 | 0,82 | 0 | 8,73 | 0 |
Отже, максимум F дорівнює 8,73 в точці (1,09, 2,55).
Тоді мінімум К(у) дорівнює також 8,73. у* = (0, 2,33, 1,67)Т.
Задача 4
Методом потенціалів розв’язати ТЗ.
Розв’язання:
| Q1 | Q2 | Q3 | Q4 | Q5 | a | |
| P1 | 7 | 3 | 1 | 5 | 4 | 30 |
| P2 | 7 | 5 | 8 | 3 | 2 | 25 |
| P3 | 6 | 4 | 8 | 3 | 2 | 45 |
| P4 | 3 | 1 | 7 | 6 | 2 | 20 |
| b | 10 | 35 | 15 | 25 | 35 |
10 +35+15+25+35 = 120
30+ 25+ 45+ 20 = 120.
Отже, ТЗ є закритою.
Знайдемо початковий план методом пн-зх кута.
|
|
Q1 | Q2 | Q3 | Q4 | Q5 | a | |||||
| P1 | 7 |
|
3 |
|
1 |
|
5 |
|
4 |
|
5 |
|
|
10 |
|
20 |
|
|
|
|
|
|
||
| P2 | 7 |
|
5 |
|
8 |
|
2 |
|
2 |
|
25 |
|
|
|
|
15 |
|
10 |
|
|
|
|
||
| P3 | 6 |
|
4 |
|
8 |
|
2 |
|
2 |
|
10 |
|
|
|
|
|
|
5 |
|
25 |
|
15 | ||
| P4 | 3 |
|
1 |
|
7 |
|
2 |
|
2 |
|
20 |
|
|
|
|
|
|
|
|
|
|
20 | ||
| b | 10 | 10 | 15 | 25 | 10 | ||||||
Поетапно проведемо методом потенціалів розв’язок задачі:
|
|
Q1 | Q2 | Q3 | Q4 | Q5 | u | |||||
| P1 | 7 |
|
3 | - | 1 | + | 5 |
|
4 |
|
4 |
|
|
10 |
|
20 | -5 |
|
5 |
|
4 |
|
||
| P2 | 7 |
|
5 | + | 8 | - | 2 |
|
2 |
|
6 |
| -2 |
|
|
15 |
|
10 | 0 |
|
0 |
|
||
| P3 | 6 |
|
4 |
|
8 |
|
2 |
|
2 |
|
6 |
| -3 |
|
-1 |
|
|
5 |
|
25 |
|
15 | ||
| P4 | 3 |
|
1 |
|
7 |
|
2 |
|
2 |
|
|
| 0 |
|
2 |
|
5 |
|
6 |
|
|
20 | ||
| v | 3 | -1 | 2 | -4 | -4 | ||||||
|
|
Q1 | Q2 | Q3 | Q4 | Q5 | u | |||||
| P1 | 7 | - | 3 |
|
1 | + | 5 |
|
4 |
|
4 |
|
|
10 |
|
10 |
|
10 | 10 |
|
9 |
|
||
| P2 | 7 |
|
5 |
|
8 |
|
2 |
|
2 |
|
6 |
| -2 |
|
|
25 | 5 |
|
5 |
|
5 |
|
||
| P3 | 6 |
|
4 |
|
8 | - | 2 |
|
2 | + | 11 |
| -8 |
|
-6 |
|
|
5 |
|
25 |
|
15 | ||
| P4 | 3 | + | 1 |
|
7 |
|
2 |
|
2 | - | 11 |
| -11 |
|
-9 |
|
-1 |
|
0 |
|
|
20 | ||
| v | 3 | -1 | -3 | -9 | -9 | ||||||
|
|
Q1 | Q2 | Q3 | Q4 | Q5 | u | |||||
| P1 | 7 |
|
3 |
|
1 |
|
5 |
|
4 |
|
5 |
|
|
5 |
|
10 |
|
15 | 7 |
|
7 |
|
||
| P2 | 7 |
|
5 |
|
8 |
|
2 |
|
2 |
|
7 |
| 2 |
|
|
25 | 7 |
|
7 |
|
7 |
|
||
| P3 | 6 |
|
4 |
|
8 |
|
2 |
|
2 |
|
1 |
| 7 |
|
7 |
|
7 |
|
|
25 |
|
20 | ||
| P4 | 3 |
|
1 |
|
7 |
|
2 |
|
2 |
|
1 |
|
|
5 | 7 |
|
7 |
|
7 |
|
|
15 | ||
| v | 2 | -2 | -4 | 1 | 1 | ||||||
Всі оцінки Сij – vi – uj на 3 етапі невід’ємні, тому оптимальний розв’язок знайдено.
| 5 | 10 | 15 | 0 | 0 | |
| X = | 0 | 25 | 0 | 0 | 0 |
| 0 | 0 | 0 | 25 | 20 | |
| 5 | 0 | 0 | 0 | 15 |
Вартість перевезень дорівнює: 7 * 5 + 3 * 10 + 1 * 15 + 5 * 25 + 3 * 5 + 2 * 25 + 2 * 20 + 2 * 15 = 340.
Список використаних джерел
Бурий В.В., Шевченко І.В. Математичне програмування. — К.: НАУ, 2007. — 168с.
Єгоршин О.О., Малярець Л.М. Математичне програмування. — Х.: ВД "ІНЖЕК", 2006. — 383с.
Жильцов О.Б., Кулян В.Р., Юнькова О.О. Математичне програмування (з елементами інформаційних технологій) / Міжрегіональна академія управління персоналом / Олена Олександрівна Юнькова (ред.). — К.: МАУП, 2006. — 184с.
Зеленський К.Х. Математичне програмування. — К.: Університет "Україна", 2007. — 241c.
Лебідь М.Т., Синявіна ЮВ. Математичне програмування. — Х., 2007. — 72с.