Алгоритм розв’язування параметричної задачі

1. Слід зафіксувати деяке значення і розв’язати задачу (5)—(7) як звичайну задачу лінійного програмування симплексним методом.

2. Оптимальний план з останньої симплексної таблиці 1 є сумою двох доданків, значення яких знаходяться в рядках та , причому має виконуватися умова невід’ємності всіх компонент вектора, що є оцінками параметрів останньої симплексної таблиці, тобто

.

3. Встановлюємо границі значень параметра t, для яких вектор залишатиметься оптимальним планом. Для цього з останньої симплексної таблиці складаємо систему нерівностей

. (8)

а) Якщо існують такі значення j, для яких , тоді розв’язками відповідних нерівностей будуть:

. (9)

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

Якщо немає , тобто всі , то значення t, для яких знайдений буде оптимальним, знизу не обмежені, тобто .

б) Якщо існують такі значення і, для яких , то розв’язками відповідних нерівностей будуть:

. (10)

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

.

4. Індексна строка визначає вектор, який необхідно вивести з базису. Припустимо, що за деякого , де , мінімальне значення в (10), яке визначає верхню границю інтервалу , досягається для . Отже, порушується k -та нерівність із (8), і з базису необхідно виводити вектор, що відповідає змінній . Тому при необхідно провести заміну базису, для чого виконують один крок двоїстого симплекс-методу і визначають нове значення .

5. Розглядаємо знову систему нерівностей (8). Для визначаємо верхню границю тих значень t, для яких відшуканий план буде оптимальним.

6. Процедуру повторюємо доти, поки не отримаємо значення верхньої границі чергового інтервалу, що дорівнює або перевищує верхню границю заданого інтервалу можливих значень t, тобто

. (11)

Співвідношення (11) і є ознакою того, що задачу розв’язано.

Отже, заданий проміжок поділяють на ряд інтервалів , для кожного з яких максимум цільової функції досягається за відповідного йому одного оптимального плану.

Приклад. Розв’язати параметричну задачу

Нехай . Розв’яжемо задачу модифікованим симплексним методом, використовуючи таблицю з двома додатковими рядками.

Базис	Сбаз	План	–1
x 1	x 2	x 3	x 4	x 5	x 6
x 3
x 4		–2	–1	–1
x 5			–2
x 6				–2					—
D j			–2
pj		–2
Fj – cj ³ 0			–1
x 3							–2
x 4			–3
x 2			–2
x 6			–1
D j		–1
pj	–3					–1
Fj – cj ³ 0		–1
x 1	–1	4/7			1/7		–2/7
x 4		19/7			3/7		1/7
x 2		29/7			2/7		3/7
x 6		81/7			1/7		12/7
D j	46/7			1/7		12/7
pj	–3					–1
Fj – cj ³ 0	25/7			1/7		5/7

Остання симплексна таблиця містить перший оптимальний план задачі

Верхня границя першого проміжку згідно з (10) дорівнює . Отже, на інтервалі план буде оптимальним, причому оптимальне значення цільової функції буде такою лінійною функцією параметра t:

і при .

Оскільки при елемент m + 2 рядка та п’ятої колонки буде нульовим, беремо п’яту колонку за розв’язувальну і, відкинувши m + 2 рядок, здійснюємо одну ітерацію. Отримаємо таку таблицю:

Базис	Сбаз.	План	–1
х 1	х 2	х 3	х 4	х 5	х 6
х 1	–1	5/2			1/6			1/6
х 4		7/4			5/12			–1/12
х 2		5/4			1/4			–1/4
х 5		81/12			1/12			7/12
Δ j	–5						–1
pj	15/4			1/12			7/12

В m + 3 рядку цієї таблиці немає від’ємних елементів, а тому згідно з формулою (10) знайдений план буде оптимальним для всіх значень t, що лежать на інтервалі . Оптимальне значення цільової функції є такою лінійною функцією параметра t:

.

При .

Отже, задача розв’язана повністю.

 

Розв’язати задачі параметричного програмування з параметром у цільовий функції

Задача 1.

 

Задача 2.