Аналітичний розв’язок задачі
Алгоритм розв’язку задачі (1) – (2) складається з двох етапів.
Етап I.Параметру 
надають фіксоване значення, наприклад
.
Цим задача приводиться до задачі лінійного програмування.
Розв’язуючи отриману ЗЛП симплекс-методом, знаходять вершину, в якій 
досягає максимум.
Етап II. Визначають інтервал зміни параметра , для якого максимум , досягається в одній і тій же вершині многогранника 
.
Знайдений інтервал виключається із відрізка 
для частини відрізка, що залишилася, знову розв’язують ЗЛП симплекс-методом тобто переходимо до етапу I.
Розв’язок продовжується до тих пір поки весь відрізок не буде розбито на частинні інтервали.
Задача. Знайти інтервали зміни параметра t на відрізку , для яких
досягає максимум в одній і тій же вершині області допустимих значень системи обмежень.
Розв’язання.
Етап I.
1. Покладемо
.
Тоді функція прийме вигляд
. (7)
Всі дані задачі заносимо в жорданову таблицю.
В рядок 
цієї таблиці в кожен стовпчик записуємо число, яке рівне сумі чисел 
і 
.
Крім того, додамо до таблиці два рядки для запису функції з довільним параметром (табл. 1).
При цьому в передостанньому рядку записуємо коефіцієнти , а в останньому – 
.
Щоб отримати , потрібно перемножити коефіцієнти останнього рядка на і додати їх до коефіцієнтів передостаннього.
Таблиця 1
| … | 
| ||
 =
| 
| 
| ||
| … | … | |||
 =
| 
| |||
|
| 
| … | 
| |
|
| 
| … | 
| |
| … | 
|
2. Знаходимо оптимальний план задачі звичайним симплекс-методом, здійснюючи перетворення і елементів останніх двох рядків.
Припустимо, що план, представлений в таблиці 2, є оптимальним.
Таблиця 2
| 
| 
| 
|
|
| ||
| 
| ||||||
|
|
| ||||||
| 
| ||||||
| 
| 
| |||||
| 
| ||||||
|
| 
|
| 
| 
|
| 
| 
|
|
| 
|
| 
| 
|
| 
| 
|
|
| 
| 
|
| 
| 
|
Тоді всі коефіцієнти рядка 
– невід’ємні:
.
Оскільки оптимальний план знайдено, переходимо до виконання дій другого етапу.
Етап II.
1. Знаходимо значення параметра , при яких план в табл. 2 буде залишатись оптимальним (максимум досягається в тій самій вершині).
Для цього необхідно, щоб всі коефіцієнти функції були невід’ємні:
(8)
Із системи (8) видно, що у всіх випадках, крім 
(при нерівність 
виконується при будь-яких значеннях ; відповідно, на стовпчик, в якому знаходиться , можна не звертати уваги), границею зміни параметра служить відношення
.
Тому передивляємось останні елементи останнього рядка таблиці:
· якщо всі вони більші нуля, переходимо до пункту 2;
· якщо всі вони менші нуля – до пункту 3;
· якщо ж серед елементів є і додатні, і від’ємні – до пункту 4.
2. Нехай всі 
.
Серед відношень
вибираємо найбільше.
Верхньої межі для в цьому випадку не існує.
Таким чином,
(9)
В інтервалі 
функція досягає максимум в тій самій вершині, що й при ; відповідно, 
.
3. Нехай всі 
.
Серед відношень
вибираємо найменше.
Якщо взяти
,
то всі умови (8) будуть задоволені.
Нижньої межі для в цьому випадку не існує, тому його можна зменшувати нескінченно.
Отже,
(10)
Як і раніше, 
.
4. Нехай серед елементів є як додатні, так і від’ємні.
Розділимо систему нерівностей (8) на дві підсистеми відповідно до знаків коефіцієнтів .
Тоді із підсистеми нерівностей з
отримаємо
,
а з другої підсистеми з
будемо мати
.
Відповідно, вся система нерівностей (8) буде задовольнятись, якщо буде приймати значення:
(11)
В цьому випадку виділений інтервал, в якому функція досягає максимум в тій самій вершині, що й при , є відрізком
.
5. Зрівняємо отриманий інтервал 
з заданим .
Незалежно від значення 
лівою границею першого інтервалу буде 
, так як 
більше бути не може.
Якщо
,
то весь інтервал попадає всередину інтервалу , і задача розв’язана.
Для будь-якого значення параметра 
максимум функції досягається в одній і тій самій вершині (рис. 4).
Рис. 4 Рис. 5
6.Якщо 
, то в інтервалі 
максимум функції буде в знайденій вершині (рис. 5).
Виключаємо цей інтервал із розгляду і розв’язуємо задачу для інтервалу, що залишився 
.
Для цього надаємо значення 
і замінюємо рядок рядком 
.
В результаті заміни отримаємо нову таблицю (табл. 3).
Таблиця 3
|
|
|
|
|
|
| ||
|
|
| ||||||
|
|
| ||||||
|
|
| ||||||
|
|
|
| |||||
|
| ||||||
| 
|
| 
|
|
|
| 
|
|
| 
|
|
|
|
|
|
|
|
|
|
|
|
| 
|
|
За розв’язуючий стовпчик в новій таблиці вибирається той, по якому визначено значення (в цьому стовпчику на перетині з – рядком знаходиться елемент, рівний нулю).
Якщо нулі знаходяться в кількох стовпцях, то за розв’язуючий можна брати будь-який з них.
Розв’язуючий елемент знаходимо по найменшому симплексному відношенню і робимо один крок модифікованих жорданових виключень.
Отримаємо наступний по порядку оптимальний розв’язок, так як всі коефіцієнти в стрічці при перетворенні не зміняться.
Для знайденого розв’язку знову визначаємо інтервал зміни параметра , для чого переходимо до пункту 1.
Якщо в розв’язуючому стовпчику не виявиться невід’ємних коефіцієнтів, то функція при 
необмежена; задача на інтервалі 
, що залишився розв’язку не має.
Зауваження. При відшуканні оптимального розв’язку для (при виконанні пункту 2 етапу І алгоритму) може виявитися, що функція зверху необмежена.
В цьому випадку в розв’язуючому стовпчику 
коефіцієнт - стрічки від’ємний 
, а всі інші коефіцієнти стовпчика недодатні.
При значенні 
на перетині стрічки і стовпчика буде елемент
.
Нас цікавить значення цього елемента, так як вони визначають поведінку функції при
.
Виберемо таке значення 
, при якому коефіцієнт
.
Звідси отримуємо, що
.
Якщо значення елемента 
, то для всіх 
коефіцієнт розв’язуючого стовпчика в стрічці буде від’ємним
.
Отже, на всьому заданому відрізку цільова функція необмежена (задача розв’язку не має).
Якщо елемент 
, то при 
коефіцієнт, що знаходиться в розв’язуючому стовпчику та -стрічці, буде від’ємним.
Значить і в цьому випадку цільова функція необмежена і задача розв’язку не має.
При значенні коефіцієнт
,
а при подальшому збільшенні він буде додатнім.
До відрізку 
застосовуємо послідовно весь алгоритм розв’язку задачі.
Приклад 3. Знайти розв’язок задачі з прикладу 1 при зміні параметра на відрізку [0,12].
Розв’язок. Припускаємо 
.
Тоді
.
Заносимо умову задачі в таблицю 4 і розв’язуємо її симплекс-методом.
Опускаючи подробиці, наводимо оптимальний розв’язок (табл. 5.):
.
Визначаємо значення параметра 
, при яких оптимальний розв’язок в тій самій вершині, що й при 
.
Так як в останньому рядку елемент
, а 
,
то для визначення значень , при яких максимум буде досягатись в знайденій вершині, підставимо відповідні значення в відношення (11), отримаємо
Таблиця 4. Таблиця 5
|
| 
| 
| 
| |||||
| -5 | 
| 14/3 | 1/30 | 7/30 | |||
|
| -5 | -1 | -1 |
| 25/3 | 1/6 | 1/6 | |
| -1 |
| 3/10 | 1/10 | ||||
| 
| 4/3 | -2/15 | 1/15 | ||||
| -4 | -2 |
| 2/5 | 4/5 | |||
|
| -4 | -2 |
| 2/5 | 4/5 | |||
| -1 | 4/3 | -2/15 | 1/15 |
Тут 
, а 
.
Отриманий інтервал менший заданого 
, тому його виключаємо з подальшого розгляду і розв’язуємо задачу для інтервалу, що залишився 
.
Для цього даємо значення 
і обчислюємо для нього рядок 
.
Занесемо елементи - рядка в табл. 6. Всі інші елементи таблиці залишаємо без змін.
Таблиця 6 Таблиця 7
|
|
| 
|
| |||||
|
| 14/3 | 1/30 | 7/30 |
| 31/9 | |||
|
| 25/3 | 1/6 | 1/6 |
| 20/9 | |||
|
| 3/10 | 1/10 |
| 110/3 | ||||
|
| 4/3 | -2/15 | 1/15 |
| 56/9 | |||
|
|
| |||||||
|
| 2/5 | 4/5 |
| 64/3 | -4/3 | 2/3 | ||
| 4/3 | -2/15 | 1/15 | 56/9 | 4/9 | 1/9 |
В першому стовпчику і - рядку табл. 6. знаходиться нуль, тому цей стовпець беремо за розв’язуючий (при 
на місце нуля першим з’явиться від’ємне число і план перестане бути оптимальним).
Знаходимо розв’язуючий елемент по найменшому симплексному відношенню і переходимо до нової таблиці (табл. 7).
План
в табл. 7 оптимальний, так як всі елементи - рядка невід’ємні.
В останньому рядку всі елементи , відповідно, застосовуємо формулу (7) і визначаємо, що
,
тобто 
.
Так як значення 
, то задача розв’язана.
Отже, при
максимальне значення функції досягається у вершині 
, при
максимальне значення функції досягається у вершині 
(рис. 3). При значенні оптимум досягається у вершинах 
і 
, а також в їх випуклій лінійній комбінації.