ММДО_МУ по ПЗ(+)

Щоб побудувати пряму ′ = 0 = 7 + 52 з = −1/2 відкладемо на осі абсцис v2, а на осі ординат v1 і через точку М і початок координат проведемо пряму, що перехрещує початок координат, тобто ′ = 0. Далі, преміщуючи її паралельно до себе, знаходимо точку, найдальшу від початку координат і яка є вершиною багатокутника ОПР. Це буде точкою Д з координатами х1* і х2*. Підставивши ці значення у задану систему обмежень і цільову функцію, знайдемо ′ = .

З цих, на перший погляд, простих побудов, маємо дуже важливі висновки:

1.Розвязання ЗЛП, якщо воно існує, не може розташовуватися в середині ОПР, а тільки на її межах.

2.ЗЛП має нескінченну множину оптимальних рішень, якщо перехрещування прямої ′ = при її переміщенні відбувається не в одній точці (вершині), а по всій прямій. Це може статися, копи ′ і грань ОПР паралельні між собою.

3.Розв’язання , що досягає ′ = , завжди відбувається в одній

звершин ОIIР і називається оптимальним. а розв’язання, що розташовується в одній із інших вершин ОПР, називається опорним, а сама вершина - опорною точкою.

4.Якби розглядалася задача, де кількість змінних перевищувала б на три кількість незалежних рівнянь-обмежень, тобто m=n-3, то побудова відбувалася б не на площині, а у тривимірному просторі.

Знайти розв’язок задач 1-8 використовуючи графічний метод.

1.	3.
7 1 + 5 2 →	1 + 2 →
2 1 + 3 2 ≤ 18;	−3 1 + 2 2 ≤ 1;
2 1 + 2 ≤ 13;	1 + 2 2		≤ 14;
0 ≤ 1 ≤ 6;	3 1 − 2		≤ 12;
1 + 2 ≥ 3;	2 1 + 2		≤ 13;
0 ≤ 2 ≤ 5.	1 ≥ 0; 2 ≥ 0;
2.	4.
3 1 + 2 2 − 3 → ;	1 + 2 → ;
− 1 + 2 + 3 = 4;	1 + 2 2			≤ 1;
1 + 2 + 4 = 10;	2 1 + 2			≤ 1;
− 1 + 3 2 − 6 = 3;	1 − 2		≤ 1;
3 1 + 2 − 5 = 9;	1 − 2 2			≤ 1;
≥ 0; = 1, … ,6.	2	−		≤ 1;
	1	2

1 ≥ 0; 2 ≥ 0;

5.		7.
1 − 2 → ;		1 − 2 → ;
1 + 2 2 ≤ 1;		−2 1 + 2 2 ≤ 5;
1 − 2 2 ≤ 1;		2 1 + 2 ≤ 3;
2 1	+ 3 2 ≤ 2;	1 + 2 ≥ −1;
3 1	+ 2 2 ≤ 3;	2 1	+ 2 2 ≤ 5;
1 + 2 ≥ 0,5;		− 1	+ 2 ≥ −1;
1 ≥ 0; 2 ≥ 0.		−2 1 + 2 ≤ 3;
		−1 ≤ 1 ≤ 1.
6.		7.
2 1 + 2 → ;		1 + 2 → ;
1	− 2 ≤ 1;	4 1 − 2 ≤ 3;
2 1 − 2 ≤ 1;		4 1	+ 2 2 ≥ 3;
3 1	+ 2 2 ≤ 0;	2 1	− 2 2	≤ 1;
2 1 − 2 ≤ 0;		4 1	− 4 2	≥ 5;
2 1	− 3 2 ≥ 3;	2 1	− 2 2	≤ 1;
1 ≥ 0; 2 ≥ 0.		4 1 − 2 ≥ 3;
		1 ≥ 0; 2		≥ 0.

1.3 Симплексний метод розв’язання ЗЛП

Мета заняття - вивчення та закріплення теоретичного матеріалу, набуття практичних навичок використання аналітичних методів розв'язання ЗЛП.

Геометричний метод розв'язання загальної ЗЛП обмежений, тому розроблені інші методи розв'язання цих задач, найбільш розповсюдженим з яких є симплекс-метод. Симплекс-метод зустрічається в літературі під назвою «метод послідовного поліпшення плану». Він вперше був розроблений Данцигом у 1947 році. На цьому методі і його модифікаціях розроблені програми для вирішення на ЕОМ, що дозволяють розв'язувати задачі лінійного програмування з кількістю обмежень до декількох тисяч. Саме поняття «симплекс-метод» виникло у результаті ранніх досліджень, коли розглядалася задача оптимізації на симплексі, тобто на множині вигляду

̅̅̅̅̅

∑ 1 = 1; ≥ 0; = 1,

=1

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

Основою алгоритму симплекс-методу є ідея цілеспрямованого перебору вершин багатогранника планів задачі, за яким ·забезпечується збільшення або

зменшення цільової функції. Оскільки кількість вершин опуклого багатогранника завжди скінченна і не перевищує С = !/ ! ( − )!, то забезпечується скінченність алгоритму; винятком є випадок так званого зациклення. Обстеження вершин починається після визначення однієї з них, тобто після знаходження початкового опорного плану ЗЛП. Опорний план має задовольняти не менш ніж n лінійно незалежним обмеженням, враховуючи і обмеження на знак, перетворюючи їх у рівняння. Опорний план буде не виродженим, якщо він містить m додаткових компонент. Якщо ж він містить менше за m додаткових компонент, план називають виродженим. Базою опорного плану = (1, 2, … , )називають m лінійно-незалежних векторів.

Алгоритм симплекс-методу поділяють на два етапи знаходження; початкового опорного плану задачі і оптимального плану, або встановлення факту необмеженості цільової функції на множині планів задачі.

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

Для того щоб зрозуміти, як розв’язувати ЗЛП за допомогою симплексметоду, розглянемо будь-який простий приклад. Спочатку наведемо загальну

постановку ЗЛП.
Визначити величини	̅̅̅̅̅
	≥ 0, = 1, , які максимізують лінійну форму
	= ∑	(1.30)
	=1
за умов існування обмежень вигляду
	AX<=B,	(1.31)

Як підкреслювалося раніше, симплекс-метод застосовується лише для канонічної форми ЗЛП. Тому, щоб почати розв'язання за допомогою симплексметоду, необхідно перетворити систему нерівностей (1.3.1) на еквівалентну систему рівнянь шляхом введення нових невід'ємних змінних+1, +2, … , + . Внаслідок цього система (1.3.1 ) набуває вигляду

		+		+ +		+		=
	11	1	12	2	1		+1	1
		+		+ +	2	+		=
	21	1	22	2			+1	2	(1.32)
	--------------------------------------------------
	+			+ +		+		=
	1 1		2 2				+1

Введення канонічної форми запису дозволяє автоматично отримати початковий план. Перетворимо систему виразів (1.3.0)-(1.3.2) на векторну форму. Для цього введемо такі позначення:

11

1

21

2

1

=

‖

‖ ; … ; = ‖

‖

; = ‖

‖.

…

…

2

1

0

…

1

Система (1.3.2) набуває вигляду

+

+

+ + + ∑

= ,

(1.33)

1 1

2 2

0

= +1

або

+1

∑

+

∑ =

(1.34)

0

=1

= +1

Щоб цільова функція залишалася незмінною при введенні додаткових

змінних, запишемо її у вигляді

= ∑ + 0 ×

+ 0 ×

+ + 0 ×

(1.35)

+1

+2

+

=1

Тепер задачу (1.33)(1.35) запишемо у вигляді симплекс-таблиці. Для цього введемо у початкову таблицю параметри, які відповідають початковому

не

виродженому опорному

плану

=

(

, , … , , 0, … ,0)

з

базою

1

2

,

, … , : коефіцієнти при змінних

у

цільовій

функції

(рядок С);

1

2

коефіцієнти при базисних змінних і, (стовпчик C);

базисні змінні (стовпчик

Х); вектори, які входять в базу (стовпчик Б); елементи |

̅̅̅̅̅̅

̅̅̅̅̅

|, = 1, ,

= 1, ;

матриці

умов

задачі,

де

=

;

̅̅̅̅̅̅

оцінки ∆

,

̅̅̅̅̅

= , = 1, ;

= 1, , що

відповідають векторам , , … ,

(останній цільовий рядок),

1

2

∆ = − ;

= ∑

̅̅̅̅̅

(1.36)

, = 1,

=1

Проаналізуємо таблицю початкового плану (таб. 1.1).

Таблиця 1.1 – Початковий план

Ci

C1

C2

…

Cj

…

Cn

Cn+1

…

Cn+m

і

Ci

X=Pi

P1

P2

Pj

Pn

Pn+1

…

Pn+m

1/x2

1

Pn+m

0

x1

x11

x12

x1j

x1n

1

…

0

1

2

Pn+m

0

x2

x21

x22

x2j

x2n

0

…

0

2

…

…

…

…

…

…

…

…

…

…

…

…

…

…

Pn+i

0

xi

xi1

xi2

xij

xin

0

…

0

i

…

…

…

…

…

…

…

…

…

…

…

…

…

…

m

Pn+m

0

xm

xm1

xm2

xmj

xmn

0

…

m

m+1

zi

m+2

Zi-ci=∆

Відповідно до введеної раніше термінології у таблиці 1.1 ми маємо початковий план, який виражається базовими векторами Pn+1, Pn+2,…,Pn+m і значеннями p0.

Коли ми маємо початковий план, то виникає запитання, чи не можна

отримати вигіднішого плану. Можливий лише один з таких варіантів:
1) max = ∞,	тобто		максимальне	значення	цільової		функції
необмежено велике, тобто необмежене зверху.
Це базується на теоремі,		яка стверджує: якщо < 0 для деякої j=k і
серед чисел ,	̅̅̅̅̅̅	нема додатних,		тобто всі		< 0, то цільова
	= 1,
функція необмежена на множині її планів;
2) max Z кінцева, тобто ∞ і отримана з даного плану. Цьому
відповідає теорема, що стверджує: опорний план = (					,	, … ,	, 0, … ,0) є
				1	2
			̅̅̅̅̅
оптимальним, якщо ∆ ≥ 0 для = 1, ;
3) оптимальний план ще не отриманий і можна досягнути ще більшого
значення Z.
Цьому варіантові відповідає теорема: якщо опорний план хЗЛП не
вироджений і ∆ ≥ 0, але серед			є такі, що більше О, то існує опорний план

такий, що Z(x’)>Z(x).

Симплекс-метод дає можливість за кінцеву кількість кроків встановити має місце 1 чи 2. Окрім того, симплекс-метод дає можливість на базі таблиці

1.1визначити:

1)якщо існує будь-який від’ємний елемент − < 0, то має місце 1

або. Якщо всі ≤ 0 в цьому стовпчику (для якого − < 0 ), то справедливо 1. Якщо деякі > 0, то необхідні подальші обчислення, тобто справедливе 3;

2)якщо всі − ≥ 0, то достигнутий max Z, тобто отримано

оптимальне розв’язання.

Сформулюємо ітеративний алгоритм обробки симплекс-таблиць. Припустимо, що розглядається випадок, коли − < 0, окрім того, деякі

> 0. Отже, відповідно до умови 1 необхідні подальші обчислення, тобто виконується умова 3.

Аналізуємо рядок m+2 таблиці 1.1, в якій здійснюється оцінка плану. Із усіх ∆ = − < 0 обираємо найбільш від'ємне число. Тим самим визначається вектор Pj=Pk , який потрібно ввести до стовпчика Б. Стовпчик, де знаходиться Pj, називають провідним. Вектор, який слід виключити із базису, знаходять з умови

	= min{		/	> 0} =	/	(1.37)
	1	1		1

Із базису виводять вектор р1, на якому досягається найменше значення Рядок 1 таблиці та елемент хik називають ведучими. Далі починається перерахування елементів симплекс-таблиці і заповнюється нова таблиця, що відповідає новому базису Pn+1, Pn+2,…,Pk,…,Pn+m.

Всі елементи нової таблиці знаходять із співвідношень

	1	=	1			̅̅̅̅̅̅̅̅̅̅̅
			1		, якщо = 1, = 0, +
	= − (	1		)		̅̅̅̅̅̅̅̅̅̅̅
						, якщо ≠ 1, = 0, +
		1

а елемент цільового рядка – із співвідношення

10 = 0 − ( 1 ) ∆ ,

∆ = ∆ − (		̅̅̅̅̅
	1	) ∆ , = 1, .

(1.38)

(1.39)

Черговий опорний план перевіряють за цільовим, тобто т+2рядком.

Якщо в цьому рядку всі ̅̅̅̅̅, то знайдено оптимальний план. У

∆ ≥ 0 = 1,

протилежному випадку переходимо до наступної ітерації.

Покращення плану від однієї ітерації до іншої відповідає зміні цільової функції на Θ(zk-ck). Процес закінчується, коли виконується одна із умов 1 або 2.

Якщо потрібно відшукати мінімум лінійної форми ЗЛП, то умовою оптимального

плану буде ̅̅̅̅̅ у цільовому рядку.

∆ ≤ 0 = 1,

Під час підготовки до заняття необхідно самостійно вивчити теоретичний матеріал у [1, с. 95-104; 2, с.63-69; 3, с. 31-40].

. Максимізувати Z=3x1+4x2 за умов обмежень

2 1 + 2 ≤ 16,1 + 4 2 ≤ 10,2 ≤ 6,

1 ≤ 7, 1 ≥ 0, 2 ≥ 0.

Перетворимо початкову задачу до канонічного вигляду

2 1 + 2 + 3 = 16,1 + 2 + 4 = 10,2 + 5 = 6,

1 + 6 = 7.

Лінійна форма має вигляд

= 3 1 + 4 20( 3 + 4 + 5 + 6) → .

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

6

													∑										=
																									0
													=1
			2			1					1									0							0		0				16
	де = ‖1‖ , = ‖1‖ , = ‖0‖ , = ‖1‖ , = ‖0‖ , = ‖0‖ , = ‖10‖
	1		0		2	1		3			0		4							0					5		1	6	0		0		6
			1			0					0									0							0		1				7		̅ =
	Початковим				планом на						базисі								одиничних									векторів			буде		план
||0,0,16,10,6,7||, а базис складається із векторів P3, P4, P5, P6. Складемо таблицю
початкового плану (табл. 1.2)
	Таблиця 1.2 – Початковий план
					Cj						3									4							0	0			0		0
i			Б		Ci			X1			P1								P2								P3	P4			P5		P6
1			P3		0			16			2									1							1	0			0		0		16
2			P4		0			10			1									1							0	1			0		0		10
3			P5		0			6			0									1							0	0			1		0		6
4			P6		0			7			1									0							0	0			0		1		∞
5			Z1					0			0									0							0	0			0		0
6			Z-Ci=∆i								-3									-4							0	0			0		0
	Оскільки у шостому (m+2) рядку є від’ємні елементи, тобто < 0, а у
відповідних стовпчиках є елементи																			> 0, то ми маємо випадок 3, тобто цей
план не є оптимальним і його можна покращити. Найменше значення у
шостому рядку -4, яке належить стовпчику P2. Він і буде ведучим. Отже, c
											16		10				6			7					6
	Знаходимо min{								} =	{		;				;			;			} =
											1		1				1								1
																				0
	Цьому значенню відповідає рядок, де знаходиться P5. Отже, цей рядок
буде ведучим, тобто P5 = P1.
	Ведучий елемент х52=1.
	Формуємо новий базис і складаємо нову таблицю (табл. 1.3).
	Таблиця 1.3 – Проміжний план
					Cj						3									4							0	0			0		0
i			Б		Ci			X2			P1								P2								P3	P4			P5		P6
1			P3		0			10			2									0							1	0			-1		0		16
2			P4		0			4			1									0							0	1			-1		0		10
3			P5		4			6			0									1							0	0			1		0		6
4			P6		0			7			1									0							0	0			0		1		∞
5			Z1					24			0									4							0	0			4		0
6			Z-Ci=∆i								-3									0							0	0			4		0

Проаналізуємо таблицю 1.3.

Новий план ̅̅̅ = ||0,6,10,4,0,7||

2

Оцінюючи елементи (m+2) рядка в таблиці 1.3, ми бачимо, що вектор P1=Pk, тобто є ведучим. Після відповідних обчислень відшукуємо ведучий рядок, це P4=P1 ведучий елемент P41=Pik.

Використовуючи (1.37) і (1.38), складаємо таблицю 1.4.

Таблиця 1.4 – Оптимальний план

		Cj		3	4	0	0	0	0
i	Б	Ci	X3	P1	P2	P3	P4	P5	P6
1	P3	0	2	0	0	1	-2	1	0	–
2	P4	3	4	1	0	0	1	-1	0
3	P5	4	6	0	1	0	0	1	0
4	P6	0	3	0	0	0	-1	1	1
5	Z1		36	3	4	0	3		0
6	Z-Ci=∆i			0	0	0	3	4	0

Аналізуючи (m+2) рядок цієї таблиці, ми бачимо, що він містить тільки

	̅	є оптимальним.
невідємні елементи. Висновок: новий план Х3
= (4,2,6,0,0,3)	= = 36
3		опт

1.4 Розв’язання ЗЛП з будь-яким видом обмежень

Мета заняття - закріплення теоретичного матеріалу та набуття практичних навичок розв’язання ЗЛП за допомогою симплекс-алгоритму з штучною базою.

Якщо система обмежень складається з нерівностей будь-якого вигляду, то початковий опорний план не можна знайти так, як розглядалося вище. У даному випадку вводять так звані «штучні змінні». Тут можливі такі випадки:

( ) = ∑	→	(1.40)
=1
за умов
≥ ,		(1.41)
≥ 0,		(1.42)

або якщо до А находять одиничні вектори, то їх вводять до базису і тоді ЗЛП називається ЗЛП з «неповною штучною базою».

Якщо всі = і нема одиничних векторів, то ЗЛП називається ЗЛП з «повною штучною базою».

По відношенню до початкової задачі, це так звана розширена М-задача, Вона також розв'язується за допомогою симплекс-методу.

До цільової функції вводиться наперед задане велике число М зі знаком «+» у випадку мінімізації чи зі знаком «-» у випадку максимізації, як коефіцієнт при невідомих.

Якщо ≥ , то перехід до канонічного вигляду створює таку истему обмежень:

+

+ +

− 1

= ,

11

1

12

2

1

+1

1

+

+ +

− 1

= ,

21

1

22

2

2

+2

2

(1.43)

− − − − − − − − − − − − − − − − − −

+

+ +

− 1

=

1 1

2 2

+

Додаткові зміни у цій системі не можна використовувати як початковий

базис, оскільки

, … ,

< 0. Тому ми змушені ввести ще один всктор

+1

+

додаткових змінних

, … ,

, знаки елементів якого співпадають зі

+ +1

+ +

знаками вільних членів, тому ці змінні входять до системи завжди зі знаком «+». Ці змінні не мають нічого спільного з реальною задачею і їх слід вивести із базису якнайшвидше. Щоб гарантувати їх швидке виведення після початку ітерацій, штучним змінним у цільовій функції приписують дуже великі коефіцієнти М.

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

За оптимальним планом Х*=(0,0,…,0,b1,…,bm) розширеної задачі значення

лінійної		функції є		= −		∑	, а	значення ∆ = − дорівнюють
				0		=1
∑			− . Отже,		=	і різниці		− складають			дві незалежні
=1				0	0

частини, одна з яких залежить від М, а інша – ні.

Після обчислення Fo і ∆ всі дані заносять до таблиці, що містить на один рядок більше, ніж звичайна симплекс-таблиця. При цьому до даного рядка вписують коефіцієнти при М, а в (m+2) рядка - складові, що не містять М, тобто

∆ = ∆ + ∑ х +1.

Xn+1- це звичайні bi стовпчика xi.

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

Початковий план поч = (0,0, … ,0, +1, … , + ), = 0 + ∑ =1 +1

у (m+2) рядку обирають Pj з максимальним елементом (у разі мінімізації цільової функції). Далі діють відповідно до симплекс-алгоритму. Тоді отримуємо таблицю 1.5.

Таблиця 1.5 – План М-задачі

Ci

C1

C2

…

Cj

…

Cn

Cn+1

…

Cn+m

і

Ci

X=P0

P1

P2

…

Pj

…

Pn

Pn+1

…

…

Pn+m

Pn+1

M

Xn+1

x11

x12

…

x1j

…

x1n

1

…

…

0

2

Pn+2

M

Xn+2

x21

x22

…

x2j

…

x2n

0

1

…

0

…

…

…

…

…

…

…

…

…

…

…

…

…

…

Pn+m

M

Xn+m

xm1

xm2

…

xmj

…

xmn

0

0

0

1

m+1

zi

m+2

Zi-ci=∆

m+3

Σxn+i

Коли всі змінні виведені з базису, перевіряють (m+2) рядок і якщо ∆ > 0 за мінімізацією або ∆ < 0 за максимізацією цільової функції, здійснюють пошук оптимального пл<1НУ відповідно до звичайного симплекс-методу.

Наведемо приклад розвязання ЗЛП з штучною базою. Знайти

= 15 1 + 33 2 → ,

за умов

3 1 + 2 2 ≥ 6,

6 1 + 2 ≥ 6,2 ≥ 1,1,2 ≥ 0

Введемо додаткові змінні з метою утворити канонічну форму:

3 1 + 2 2 − 3 = 6, 6 1 + 2 − 4 = 6,2 − 5 = 1.

Змінні x3, x4, x5 створюють недопустиме базове розв’язання

3 = −6 < 0; 4 = −6 < 0; 5 = −1 < 0.

Тому вводимо до обмежень і цільової функції штучні змінні x6, x7, x8 Задача приймає такий вигляд

= 15 1 + 33 2 + 6 + 7 + 8 → , 3 1 + 2 2 − 3 + 6 = 6, 6 1 + 2 − 4 + 7 = 6,

2 − 5 + 8 = 1.

Очевидно, початкове базове розв’язання x6*=6, x7*=6, x8*=1. Оскільки Р6, Р7 ,Р8 створюють одиничний базис, а всі > 0, то для розв’язання задачі використовують симплекс-метод. Складаємо таблицю початкового плану (табл.

1.6).

Таблиця 1.6 – Початковий план М-задачі