б) Якщо , то нерівність (3) буде справджуватись для тих значень параметра .

в) Якщо , то .

Позначимо через

(4)

(5)

Очевидно, що план буде оптимальним ??? ??? параметра t які . Щоб повністю дослідити задачу (2) ми повинні дослідити її для . Дослідимо для і допустимо, що , а це означає, що є хоча б одно . Якщо декілька, то знайдемо (6).

Не важко показати, що .

, тому очевидно, що якщо рухатись вправо від , тобто розглядати значення параметра більшої від , то першою від’ємною оцінкою стане оцінка . Проаналізуємо елементи k-того стовпця відповідної ??? таблиці. Тут знову можуть зустрітись два випадки:

а) всі елементи k-того стовпця є ??? рівні 0. .

б) хоча б один.

У а) можна показати, що ЛФ є необмеженою в області R для всіх параметрів .

У випадку б) введемо вектор у базис, а з базису виведемо той вектор, для якого виконується умова , не важко показати, що одержаний таким чином базис буде оптимальний для всіх значень параметра t, які будуть лежати правіше від точки . Отже ми одержали слідуючий результат, який можна сформулювати у вигляді теореми.

Теорема. Нехай , а індекс k визначається умовою (6). Тоді а), якщо всі елементи k-того стовпця , то ЛФ (2) є необмежена в області R для всіх .

б) Серед елементів k-того стовпця декілька додатних елементів, тоді вивівши вектор з базису по відомих правилах симплекс-методами перейдемо до нового базису, лівий кінець множини оптимальності якого буде співпадати з . Отже процес розв’язку задачі параметричного програмування зводиться до руху по базисах її сусідніх планів, при чому права границя множини оптимальності попереднього базису співпадає з лівою границею множини оптимальності послідуючого базису. Процес закінчується побудовою променя, в кожній позиції якого план оптимальний або лінійна форма не обмежена на множин своїх планів.

Проведені викладки можуть бути повторені для , для цього лишень потрібно ??? право вибору і ??? буде визначатися:

Зробимо тепер аналіз задачі параметричного програмування в тому випадку , тобто (8) .

При аналізі (8)може зустрітись три випадки.

І . Це означає, що (8) виконується при будь-якому , а отже ЛФ (2) є необмеженою на множині своїх планів в любій точці t, а значить і по всій осі.

ІІ .

ІІІ .

В ІІ випадку нерівність (8) вірна при .

В ІІІ випадку (8) вірна для , отже у випадку ЛФ (2) необмежена справа від точки . А ПРИ зліва від точки , для проведення детального аналізу задачі у випадку необхідно за параметр взяти і провести ті викладки, які ми робили у І.

За кінцеву кількість кроків ми завжди проведемо повністю аналіз (2). Оскільки коми з проміжків оптимальності зв’язані з одним із базисів задачі. то число базисних розв’язків є завжди кінцеве.

Висновок. Процес розв’язку задачі (2) зводиться до наступного:

Вибираємо довільний параметр і для вибраного розв’язуємо задачу звичайним симплекс-методом. Вся різниця в симплексній таблиці буде полягати в тому, потрібно обчислити два індексні рядки. Кінці проміжку оптимальності знаходимо за допомогою (4) і (5).

Приклад.

Знайти

Розв’язування задачі параметричного програмування і випадку залежності від параметра вектора обмежень.

Нехай нам потрібно знайти (1) при чому .

Розв’язування задачі параметричного програмування виду (1) базується на приміненні двоїстого симплексного методу.

Означення 1.

Псевдо базисом називають систему m-лінійно-незалежних векторів , відносно яких всі вектори умов задачі (1) мають невід’ємні оцінки.

Означення 2. Якщо для деякого коефіцієнти розкладу вектора обмежень задачі (1) по векторах псевдо базисах є невід’ємними, то псевдо план задачі (1) при ??? називається оптимальним.

Означення. Сукупність значень параметра t, при яких даний псевдо план оптимальний називається множиною оптимальності псевдо плану. Вибираємо довільне і для вибраного розв’яжемо задачу (1). В результаті може трапитися два випадки:

а) при вибраному ми отримали оптимальний план задачі ;

б) при вибраному значенні умови задачі (1) не сумісні;

в) ми одержали оптимальний план задачі (1), з деякою базою то це означає, що для даного плану повинні виконуватись умови:

1)

2)

Позначимо

Тоді (1) має вигляд

Отже, якщо при ми маємо оптимальний план задачі, то має місце нерівність (2).

Розглянемо ті значення параметра t, при яких , інакше

В координатній формі

Замітимо, що оцінки задачі (1) не залежать від параметра t, тому необхідною і достатньою умовою оптимальності є виконання нерівності (3’). Визначимо ??? оптимальності даного псевдо плану.

А для цього розв’яжемо систему нерівностей (3’). Система нерівностей (3’) є сумісною, оскільки точка задовольняє її. Множину оптимальності плану шукаємо аналогічно як і в попередньому параграфі, тобто точки при яких база буде оптимальною буде множиною розв’язків системи нерівностей (3).

??? , якщо .

Отже псевдо план буде оптимальним для всіх тих значень параметра .

Дослідимо тепер поведінку розв’язку.

Дослідимо тепер поведінку розв’язку задачі для (цілком аналогічно можна було б поступати для ).

Нехай . Це означає, що серед ??? вектора є хоча б одна від’ємна.

Очевидно система нерівностей (3’) не буде задовольнятись по крайній мірі для індексу тієї нерівності, з якої ми визначали .

Нехай границя визначалась з умови (5). Виберемо 2-ий рядо за розв’язковий рядок і перейдемо від бази до бази з допомогою двоїстого симплексного методу, вибравши за розв’язковий стовпець той стовпець, для якого виконується умова

і виконуємо відносно стовпця симплекс перетворення, при чому відрізок оптимальності бази визначається цілком аналогічно, як бази . Лівий кінець відрізка оптимальності шукати не варто, так як він завжди буде співпадати з правим кінцем оптимальності