Дробово-лінійне програмування

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

1. Систему обмежень приводять до канонічного виду:

де	─ основні змінні;
	─ додаткові змінні;
	─ штучні змінні.

2. Знаменник цільової функції позначають через , це приводить до наступного:

§ з’явиться додаткове обмеження або ;

§ функція цілі стане такою .

3. Всі обмеження множать на і до них додають додаткове співвідношення.

 

4. Впроваджують позначення:

; ; ;

; ; ; .

Упорядковують систему щодо нових змінних, переносячи з правої частини елементи, пов’язані з . Крім того, у додаткове обмеження вводять штучну змінну з наступним номером, у даному випадку вводять . Це необхідно для формування початкового базису. У результаті зазначених перетворень задача здобуває вигляд:

 

5. Задача придбала канонічну форму, її рішення може бути виконано симплексним методом. З огляду на те, що індекси векторів повинні відповідати індексам змінних (, , і т.д.), вектор вільних членів позначають через - це позбавить від плутанини.

 

 

Таблиця 1

Початкове симплекс-рішення

 

Б	С											С.В.
			-6			-1
			-14				-1
			-5
												1/5
-рядок			-3	-2
-рядок		-20			-1	-1

 

 

Даній таблиці відповідають такі значення змінних:

; ; ; ; ; ; ; ; .

Це рішення не оптимальне.

У таблиці 1 отримано три однакових симплексних відношення, – усі вони дорівнюють нулю. При виборі ключового рядка керуються правилом: беруть той, що відповідає більшому елементу ключового стовпця. У даному випадку вибирають перший рядок, і генеральний елемент дорівнює 6.

Таблиця 2

Друга симплексна таблиця

 

Б	С										С.В.
			-1	1/6		-1/6
			-12	40/6		2/6	-1
			-4	5/6		1/6
				19/6		5/6					6/19
-рядок		-2	-16/6		-2/6
-рядок		-7	59/6		7/6	-1

 

Друге рішення виглядає так:

; ; ; ; ; ; ; ; .

Воно не оптимальне.

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

Таблиця 3

Третє симплексне рішення

 

Б	С									С.в.
			-28/40			-7/40	1/40			-
			-72/40			2/40	-6/40			-
			-100/40			5/40	5/40			-
			428/40			27/40	19/40			40/428
-рядок		-272/40			-8/40	-16/40
-рядок		428/40			27/40	19/40

 

 

Третє рішення:

.

Умова оптимальності все ще не виконується, переходять до наступної таблиці.

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

Таблиця 4

Четверте симплексне рішення

 

Б	С								С.о.
		28/428				-56/428	24/428		-
		72/428				70/428	-30/428		72/70
		100/428				121/428	101/428		100/121
		40/428				27/428	19/428		40/27
-рядок	272/428				98/428	-42/428

 

Рішення, що відповідає таблиці 4, має вигляд:

, , , , .

Воно не оптимальне, знаходять слідуюче симплекс-перетворення.

Таблиця 5

П’яте симплексне рішення

 

Б	С
		21/121					20/121	56/121
		4/121					-25/121	-70/121
		100/121					101/121	428/121
		5/121					-1/121	-27/121
-рядок	54/121					-35/121	-98/121

 

У таблиці 5 отримане рішення, що задовольняє умові оптимальності:

, , , , .

 

6. Визначають значення вихідних змінних:

; ; .

Таким чином, рішення задачі дробово-лінійного програмування буде наступним:

.

7. Дають, якщо можливо, геометричну інтерпретацію задачі:

§ знаходять область припустимих значень;

§ відзначають точки, що відповідають симплекс-таблицям.

 

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

Зауваження. Дробово-лінійну задачу з двома змінними можна вирішувати графічним методом, ґрунтуючись на таких правилах:

1. По системі заданих обмежень будують область припустимих рішень.

2. Вибирають довільне значення і будують відповідну пряму – вона обов'язково пройде через початок координат.

3. Позначимо

§ якщо , то, повертаючи пряму проти годинникової стрілки до опорного положення, одержимо точку мінімуму (для одержання максимуму пряму повертають по годинній стрілці);

§ якщо , то для одержання мінімуму пряму повертають по годинній стрілці до опорного положення (для максимуму – проти годинниковій стрілки).

4. Визначивши оптимальні точки, знаходять їх координати – це і будуть оптимальні значення змінних, після чого обчислюють величину функції цілі.

Приклад. Знайти рішення дробово-лінійної задачі.

, розглянемо 2 варіанти функції

а)

б)

1. Будуємо область припустимих рішень – вона визначається трьома нерівностями і являє собою трикутник .

2. Будуємо пряму

а)

б)

; ;

а) ; ; ; ;

б) ; ; ; ;

 

 

Параметричне програмування

 

Існує значна група економічних задач, у яких до складу лінійної цільової функції чи правої частини обмежуючих умов входить параметр. Наприклад, якщо ефективність або доход залежать від сезонних коливань, тоді критерій оптимальності повинний цю залежність відображати. Якщо постачання ресурсів також змінюється під впливом якихось причин, то в системі обмежень це повинно відобразитися. Якщо продукція, що виготовлена підприємством, повинна якийсь час зберігатися, то її вартість складається з двох частин: постійної – це вартість продукції на момент виготовлення – і змінної частини, що залежить від терміну зберігання, причому ця залежність, як правило, лінійна. Цільова функція задачі оптимального планування такого виробництва буде мати коефіцієнти, що лінійно залежать від параметра (від часу).

Головна ідея методу рішення таких задач складається з двох частин:

§ беруть фіксовану величину параметра (а саме дорівнює найменшому значенню ); тоді всі коефіцієнти функції цілі будуть постійними; вирішують задачу для цього випадку, тобто знаходять вершину, у якій досягнуто екстремум;

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

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

1. Задачу готують до рішення: функцію спрямовують до мінімуму; нерівності перетворять у рівняння, вводячи додаткові змінні; вводять штучні змінні, якщо потрібно.

2. Надають параметру найменше значення з відрізка . Відповідно з цим конкретизують цільову функцію.

3. Будують І симплексну таблицю відповідно до правил.

4. Доповнюють І симплекс-таблицю двома рядками. В -рядку записують із протилежним знаком коефіцієнти цільової функції, не зв'язані з параметром . В -рядок вносять із протилежним знаком коефіцієнти функціонала, що знаходяться перед параметром .

5. Проводять розрахунки всіх елементів таблиці відповідно до правил симплексного методу, перевіряючи оптимальність на основі М-рядка, а потім -рядка.

6. Виписують оптимальне рішення, якщо критерій ефективності виконався. Після цього рядок в увагу не береться.

7. Знаходять для інтервал сталості рішення, розглядаючи такі випадки ( - початок інтервалу, - кінець інтервалу):

а) усі додатні – у цьому випадку частковий інтервал визначається таким способом:

б) усі від’ємні – у цьому випадку інтервал сталості рішення знаходиться так:

в) приймають як додатні, так і від’ємні значення – у цьому випадку інтервал сталості рішення буде таким:

для

для

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

9. Наступний етап полягає у виборі ключового стовпця – їм буде стовпець, у якому отримане значення . Далі виконують симплекс-перетворення і визначають новий частковий інтервал для нового рішення. Цю процедуру повторюють доти, поки буде вичерпаний весь відрізок .

Приклад.

Знайти рішення задачі параметричного програмування

Підготуємо задачу до рішення:

де	- основні змінні,
	- додаткові змінні,
	- штучна змінна.

Надамо параметру найменше значення з його інтервалу і конкретизуємо цільову функцію:

Сформуємо 1 симплекс-таблицю з додатковими рядками:

Таблиця 1

 

Базис	С		– 6	– 3				М	С.в.
	М						– 1
-рядок
М- рядок						-1
-рядок
-рядок		-1

Критерій оптимальності не виконується.

У таблиці 1 ключовими будуть стовпець і третій рядок. У базис входить вектор , виходить штучний вектор . Генеральний елемент дорівнює 1.

Таблиця 2

 

Базис	С		– 6	– 3				С. В.
				– 2
	– 6						– 1	–
-рядок	– 12		– 3
-рядок	– 14		– 5
-рядок						– 1

 

У таблиці 2 критерій оптимальності не виконується. У новий базис входить , виходить з базису . Генеральної елемент дорівнює 5.

Таблиця 3

 

Базис	С		– 6	– 3				С.В.
				16/5		– 3/5		15/8
				– 2/5		1/5		–
	– 6			3/5		1/5
-рядок	– 18		– 3/5		– 6/5
-рядок	– 21		– 11/5		– 7/5
-рядок			8/5		1/5

 

У таблиці 3 досягнуто мінімум і максимум . Оптимальні значення основних змінних такі:

.

Це рішення визначає вершину . Воно буде зберігатися для деяких значень . Оскільки усі позитивні, то ми маємо випадок а) пункту 7:

.

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

Таблиця 4

 

Базис	С		– 6	– 3				С.В.
	-3	30/16			5/16	– 3/16		–
		28/16			2/16	2/16
	– 6	30/16			-3/16	5/16
-рядок	– 270/16			3/16	– 21/16
-рядок	– 270/16			11/16	– 29/16
-рядок				-8/16	8/16

 

У таблиці 4 отримане нове рішення:

.

Воно визначає вершину . Ця вершина буде забезпечувати оптимальність для інших значень , що знаходяться на основі случаю в) пункту 7, тому що величини мають різні знаки:

.

Таким чином, у точці досягається максимум, якщо . Цей інтервал теж не охоплює значення відрізка , необхідно рухатися далі, шукати рішення для значень , що залишилися. Ключовим стане стовпець , вектор ввійде в базис, вийде з базису вектор , генеральний елемент дорівнює . Одержимо таблицю 5.

Таблиця 5

 

Базис	С		– 6	-3
	– 3		3/5		1/5
			– 2/5		1/5
			16/5		– 3/5
-рядок	– 9	21/5		– 3/5
-рядок	– 6	29/5		– 3/5
-рядок	– 3	– 8/5		– 1/5

 

У таблиці 5 отримане таке рішення: . Воно відповідає вершині . Оскільки всі від’ємні, то вершина , у відповідності з випадком б) пункту 7, буде оптимальною для наступних значень :

.

Підводячи підсумки, конкретизуємо висновки:

§ якщо належить інтервалу , то цільова функція досягає максимуму в точці ;

§ якщо приймає значення з інтервалу , то максимум буде у вершині ;

§ якщо змінюється від до 5, то максимум досягається в точці .

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

 

3. ЗаВдання для самостійного рішення