Лабораторне заняття № 13. Мкр 1.

Тема 6.Нелінійні оптимізаційні моделі економічних систем. Лабораторне заняття №14

Тема заняття: Розв’язання задач параметричного програмування.

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

Методичні рекомендації: Вивчити лекцію №5 та ознайомиться з наступною літературою [2 с. 183-208],[3 с. 252-294].

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

(1)

(2)

(3)

допустимо, що

. (4)

Усі ж інші коефіцієнти і вільні члени залишаються сталими величинами.

Запишемо параметричну задачу такого виду в загальній формі:

(5)

(6)

. (7)

За деякого фіксованого значення задача (5)—(7) перетворюється в звичайну задачу лінійного програмування. Зміни коефіцієнтів цільової функції в процесі реалізації симплексного методу впливатимуть на значення оцінкового ряду ( ).

Для оптимального плану задачі лінійного програмування в постановці (1)—(3), як відомо, оцінки векторів розраховують так:

.

Якщо цільова функція має вигляд (5), то оцінки векторів розраховуватимуться за формулою:

Позначимо перетворені методом повних виключень Жордана—Гаусса в процесі перерахунку початкової симплексної таблиці через , аналогічно — як . Остання симплексна таблиця набуде такого вигляду:

Таблиця1.

і	Базис	Сбаз	План	с1 + t0 p1	...	cm + t0 pm	...	cn + t0 pn
				x1	...	xm	...	xn
1	x1	с1 + t0 p1		a11	...		...
2	x2	с2 + t0 p2		a21	...		...
…	…	…	…	…	…	…	…	…
m	xm	cm + t0 pm		am1	...		...
m + 1
m + 2					...		...
m + 3	Fj – cj  0				...		...

Таблиця (аналогічно випадку параметричної зміни вектора обмежень —табл.1) містить два додаткових рядки, що дає змогу стежити за перетвореннями величин після кожної ітерації.

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

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	1	0	0	0	0
			x1	x2	x3	x4	x5	x6
x3	0	10	3	2	1	0	0	0
x4	0	–2	–1	–1	0	1	0	0
x5	0	3	–2	1	0	0	1	0
x6	0	5	3	–2	0	0	0	1	—
 j		0	3	–2	0	0	0	0
pj		0	–2	1	0	0	0	0
Fj – cj  0		0	1	–1	0	0	0	0
x3	0	4	7	0	1	0	–2	0
x4	0	1	–3	0	0	1	1	0
x2	1	3	–2	1	0	0	1	0
x6	0	11	–1	0	0	0	2	1
 j		6	–1	0	0	0	2	0
pj		–3	0	0	0	0	–1	0
Fj – cj  0		3	–1	0	0	0	1	0
x1	–1	4/7	1	0	1/7	0	–2/7	0
x4	0	19/7	0	0	3/7	1	1/7	0
x2	1	29/7	0	1	2/7	0	3/7	0
x6	0	81/7	0	0	1/7	0	12/7	1
 j		46/7	0	0	1/7	0	12/7	0
pj		–3	0	0	0	0	–1	0
Fj – cj  0		25/7	0	0	1/7	0	5/7	0

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

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

і при .

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

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

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

.

При .

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

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

Задача 1.

Задача 2.