 |
Альтернативний оптимум
|
|
|
|
Задачі, які мають множину оптимальних розв’язків, мають так званий альтернативний оптимум. Геометрично це відповідає випадку, коли залежність 
йде паралельно межі многогранника, на якій лежить оптимум. При цьому всі точки, які перебувають на цій грані, мають одне й те саме значення цільової функції . Ознакою такої множини оптимальних розв’язків є існування нульового елемента в індексному рядку хоча б для однієї вільної змінної 
.
Розглянемо інтерпретацію такого випадку.
Припустимо, що знайдено оптимальний розв’язок, в якому перші т змінних 
є базисними, решта (п – т) змінних 
є вільними.
Тоді 
а через коефіцієнти індексного рядка
Оскільки будь-який допустимий розв’язок припускає, що 
то 
Це може бути у двох випадках:
– якщо 
, то має бути 
, щоб 
;
– якщо 
то умова можлива також при відповідній змінній 
, а це означає, що умова можлива також при іншій сукупності базисних змінних, тобто існує другий розв’язок з одним і тим же значенням цільової функції , що й вказує на альтернативний оптимум.
Щоб знайти другий оптимальний розв’язок, у кінцевій симплекс-таблиці оптимального розв’язку потрібно вибрати головну колонку за вільною змінною з нульовою оцінкою 
та побудувати нову симплекс-таблицю згідно з алгоритмом перетворення. У результаті таких перетворень буде знайдено другий базисний оптимальний розв’язок.
Множину оптимальних розв’язків задачі знаходять, використовуючи вираз для лінійної комбінації векторів.
Якщо відомі крайні точки відрізка, то решту точок цього відрізка знаходять так:
де
Таку властивість використовують для знаходження інших оптимальних розв’язків:
де 
– значення 
-ї змінної нового оптимального розв’язку згідно з вибраною величиною t; 
– значення -ї змінної відповідно першого та другого базисних оптимальних розв’язків.
|
|
|
Задачі, в яких існує альтернативний оптимум, на практиці мають значні переваги перед задачами (ситуація (а не задача), коли існує множина оптимумів, є з практичної точки зору кращою ніж... з одноваріантним оптимальним розв’язком. Річ у тому, що на практиці треба враховувати одночасно кілька критеріїв. Створити єдиний комплексний критерій надто складно, а іноді неможливо. А задачі з альтернативним оптимумом мають змогу враховувати кілька критеріїв, використовуючи метод послідовних критеріїв. При цьому з множини оптимальних розв’язків Р за одним критерієм вибирають укладену множину 
оптимальних розв’язків з урахуванням другого критерію і т.д. Такий підхід цілком допустимий, якщо існує загальна область допустимих розв’язків для всіх узятих критеріїв, тобто перетин областей допустимих розв’язків за кожним критерієм не повинен бути порожнім.
Розглянемо приклад задачі з альтернативним оптимумом.
Нехай задано таку математичну модель:
2 Використовуючи графічний метод, переко-
В 
наємося, що ця модель має множину опти-
оптимальних розв’язків.
Графічно задачу зображено на рис.1.13.
Геометрично пряма паралельна стороні
А АВ, де лежить максимум:
0 С точка 
та 
точка 
та 
.
Рис.1.13
Решта точок на прямій АВ: точка 
та 
точка 
та 
і так далі. Розв’яжемо задачу симплекс-методом. Стандартна форма математичної моделі задачі така:
Спочатку складаємо першу симплекс-таблицю:
| 
| 
| 
| |||
|
| ||||||
|
| -1 | |||||
| -1 | -1 |
Потім складаємо другу симплекс-таблицю:
|
|
|
|
| |||
|
| ||||||
|
| ||||||
|
|
|
|
Знайдено оптимальний розв’язок: 
.
Оскільки вільна змінна 
має нульову оцінку в індексному рядку, то задача має не один оптимальний розв’язок.
Щоб дістати другий базисний оптимальний розв’язок, головною колонкою треба вибрати колонку вільної змінної , тобто 
. Потім перетворити симплекс-таблицю:
|
|
|
|
| |||
|
| 1/2 | -1/2 | ||||
|
| 1/2 | 1/2 | ||||
|
|
Знайдено другий базисний оптимальний розв’язок:
.
Маючи дві крайні точки прямої (перший та другий базисний оптимальні розв’язки), дістаємо інші розв’язки за допомогою виразу
де 
.
Задаючи значення 
, знаходимо кілька оптимальних розв’язків:
Цілком зрозуміло, що всі ці варіанти розв’язків мають одне й те саме значення .
|
|
|
