2 курс. Ден. ФК, УП, ЕП 12 / Економіко математичні методи та моделі (Оптимізаційні методи) Ч.1 Ден. 2010

2.7. z = -2x1 - 5x2 (extr),

2.8. z = -3x1 + 6x2 (extr),

5x

+ 6x

2

≥120,

4x1 + 2x2 ≥ 25,

1

x1 +3x2 ≤ 6,

2x

−3x

≤ 60,

2

1

x

− 2x

2

= 0,

x1 ≥ 0,

1

x ,

x

≥ 0.

0 ≤ x2 ≤ 7.

2

1

2.10. z = -x1 - 2x2 (extr),

2.9. z = 5 - 4x1 + 3x2 (extr),

7x

+12x

≤ 49,

5x

+8x

≤ 80,

1

2

1

2

x1 − x2 ≤ 0,

− x1 + x2 ≥ 0,

0 ≤ x

≤ 3,

4x

+3x

2

≤12,

1

1

x

2

≥ 0.

x

, x

2

≥ 0.

1

Питання для самоконтролю

1.У чому полягає загальна задача ЛП?

2.Який склад математичної моделі задачі ЛП?

3.Записати математичну модель загальної задачі ЛП?

4.Як звести задачу ЛП до канонічної форми?

5.Які є форми запису задач лінійного програмування.

6.Що таке цільова функція задачі ЛП ?

7.Яка область називається областю допустимих планів ?

8.Який план називається опорним ?

9.Який опорний план називається невиродженим ?

10.Сформулювати основні властивості розв’язків задачі лінійного програмування.

11.За яких умов у задачі ЛП з необмеженою областю допустимих планів існує розв’язок.

12.Що означає умова несумісності допустимих планів ?

Бібліографічний список до практичного заняття

[1], [3], [4], [5], [6], [7], [9], [12], [13], [14], [15] .

90

Практичне заняття № 3

Поточний модульний контроль з двох тем:

Тема 2. Оптимізаційні економіко-математичні моделі Тема 3. Задача лінійного програмування та методи її розв'язування.

Мета заняття: перевірити практичні навички побудови математичних моделей задач лінійного програмування, розв’язання ЗЛП графічним методом.

План заняття

1.Розв’язання практичних ЗЛП - побудова математичних моделей ЗЛП.

2.Розв’язання практичних ЗЛП графічним методом.

Методичні рекомендації до практичного заняття

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

тем.

Практичне заняття № 4

Тема 3. Задача лінійного програмування та методи її розв'язування

Мета заняття: Набути практичні навички розв'язання задачі лінійного програмування симплексним методом.

План заняття

1.Алгоритм симплексного методу розв’язання ЗЛП.

2.Розв’язання ЗЛП симплекс-методом.

3.Алгоритму метода штучного базису.

4.Розв’язання М-задач.

91

Методичні рекомендації до практичного заняття

При виконанні завдань необхідно звернутися до методичних рекомендацій до самостійної роботи з даної теми.

Завдання для практичного заняття

Навчальні завдання

1.Виконайте навчальні завдання, переконайтеся у тому, що отриманий результат вірний.

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

обмежень-рівностей, увівши додаткові змінні x3, x4 , x5 ≥ 0.

x + 2x	2	+ x	3	= 32
1
x1 + x2 + x4 = 20
		+ x5 = 50
3x1 + x2
xi ≥ 0	i =1..5

F(x1, x2 ) = 4x1 + 2x2 + 0x3 + 0x4 + 0x5 → max

Симплекс-таблиця складається так. У графі Базис записуються вектора змінних, прийняті за базисні. На першому етапі це – A3, A4, A5. Базисними будуть змінні, кожна з яких входить тільки в одне рівняння системи, і немає такого рівняння, у яке не входила б хоча б одна з базисних змінних.

У наступний стовпець Cδ записуються коефіцієнти цільової функції, що відповідають кожної змінній. Стовпець В – стовпець вільних членів. Далі йдуть стовпці коефіцієнтів Аi при i -й змінної. Під стовпцем вільних членів записується початкова оцінка

F0 = Cδ B = 0 32 + 0 20 + 0 50 = 0

Інші оцінки записуються під стовпцями відповідних векторів Аi .

F1 −C1 =Cδ A1 −C1 = 0 1+0 1+0 3 −4 = −4

92

F2 −C2 = Cδ A2 −C2 = 0 2 + 0 1 + 0 1 − 2 = −2

Слід зазначити, що оцінки для базисних векторів завжди дорівнюють нулю.

Перетворення симплекс-таблиці ведеться в такий спосіб:

1. Перевіряється критерій оптимальності, суть якого полягає в тому, що всі оцінки Fi −Ci повинні бути не невід'ємні. У нашім випадку цей критерій не виконаний, тому переходимо до другого кроку.

2. Для невід'ємних оцінок обчислюються величини:

	B			32			20		50			50
θ1	= min	i		= min		;		;			=
					1		1					3
	Ai								3

3. Третій рядок таблиці ділиться на 3 і віднімається з першого й другого рядків. По суті, застосовується метод виключення невідомих, відомий як метод Жордана - Гаусса. Таким чином, новими базисними змінними стають A3, A4, A1. Вертаємося до кроку 1 і повторюємо весь процес. Під стовпцем вільних членів записується початкова оцінка F0 = Cδ B = 0 463 + 0 103 + 4 503 = 2003 . Інші оцінки записуються під

стовпцями відповідних векторів Аi .

F2 −C2 =Cδ A2 −C2 = 0 53 +0 23 +4 13 −2 = −23 .

								1				1				1				4
F5 −C5	=Cδ A5 −C5
						= 0	−			+0	−				+4			−0	=		.
												3				3				3
								3

Слід зазначити, що оцінки для базисних векторів завжди дорівнюють нулю.

	Знову перевіряється критерій			оптимальності. Від’ємна оцінка
	тільки одна – у стовпці x2.
		46
	Обчислюємо: θ2 = min		;5;50		=5.
		5

93

Розв'язувальним елементом буде другий елемент другого стовпця - 2/3. Новими базисними змінними стають x3, x2, x1. Ділимо другий рядок на 2 і віднімаємо із третьої. Множимо другий рядок на 5/2 і віднімаємо з першої.

F0 = Cδ B = 0 7 + 2 5 + 4 15 = 70

F1 −C1 =Cδ A1 −C1 = 0 0 +2 0 +1 4 −4 = 0

F2 −C2 =Cδ A2 −C2 = 0 0 +2 1+0 4 −2 = 0

F3 −C3 = Cδ A3 −C3 = 0 1+ 0 2 + 0 4 −0 = 0

F4 −C4 = Cδ A4 −C4 = 0 − 52 + 2 32 + 4 − 12 − 0 =1 F5 −C5 =Cδ A5 −C5 = 0 12 +2 12 +4 12 −0 =3.

Цього разу від’ємних оцінок немає, тобто критерій оптимальності виконаний. Таким чином, шукане значення цільової функції F(15; 5; 7; 0; 0) = 70, тобто вертаючись до системи нерівностей, дістаємо:

F(15;5) = 60 +10 = 70 .

Таблиця 4.1

№	Базис	Cδ	B	4	2			0	0	0
етапу				x1		x2		x3	x4	x5
1	x3	0	32	1	2			1	0	0
2	x4	0	20	1	1			0	1	0
3	x5	0	50	3	1			0	0	1
4	∆j=F	i - Ci	0	-4	-2			0	0	0
1	x3	0	46/3	0	5/3			1	0	-1/3
2	x4	0	10/3	0		2/3		0	1	-1/3
3	x1	4	50/3	1		1/3		0	0	1/3
4	∆j=F	i - Ci	200/3	0	-2/3			0	0	4/3
1	A3	0	7	0	0			1	-5/2	1/2
2	A2	2	5	0	1			0	3/2	1/2
3	A1	4	15	1	0			0	-1/2	1/2
4	∆j=F	i - Ci	70	0	0			0	1	3

94

Відповіді, отримані різними методами, збігаються.

2.2.Знайти максимальне значення функції

F = 8x1 +10x2 −5x3 → max

за умов:

	2x1 + 3x2 + 4x3 + 2x4 ≤ 450,
		+ 2x2 + x3 + 2x4 ≤ 380,
	3x1
		x j ≥ 0, j =1,4.

Розв’язання. Записуючи систему нерівностей у канонічному вигляді, вводимо додаткові змінні:

2x1 + 3x2 + 4x3 + 2x4 + x5 = 450,

3x1 + 2x2 + x3 + 2x4 + x6 = 380,
	x j ≥ 0, j =1,4.

Складемо симплексну таблицю для першого опорного плану:

Таблиця 4.2

Базис	Сбаз	План	8			10			0		-5	0	0
				x1		x2			x3		x4	x5	x6
x5	0	450	2				3		4		2	1	0	150
x6	0	380	3				2		1		2	0	1	190
	j	0	-8			-10			0		5	0	0
Будуємо нові симплексні таблиці:
													Таблиця 4.3
Базис	Сбаз	План	8			10			0		-5	0	0
				x1		x2			x3		x4	x5	x6
x2	10	150	2/3			1			4/3		2/3	1/3	0	225
x6	0	80				2			1		2	0	1	48
				5/3
	j	1500	-4/3			-10			0		5	0	0
Базис	Сбаз	План	8			10			0		-5	0	0
				x1		x2			x3		x4	x5	x6
x2	10	118	0			1			2		2/5	3/5	-2/5
x1	8	48	1			0			-1		2/5	-2/5	3/5
	j	1564	0			0			12		64/5	14/5	4/5

Відповідь: Fmax=1564, при x1=48, x2=118.

95

2.3.Знайти найбільше значення функції (M-задача)

F =34x1 − x2 −3x3 +3x4 → max

(29)

за умов

3x

−2x

2

+3x + 2x

4

= 9,

1

3

x1

+ 2x2 − x3 + x4 = 0,

x

+ x

2

−

2x

− x

4

= −6,

(30)

1

3

Розв'язання. Очевидно, що

x1, x2 , x3, x4 ≥ 0.

(31)

матриця

системи

рівнянь

(30) не

містить одиничних вектор-стовпців. Тому помножимо третє рівняння системи (30) на (– 1), введемо в систему три штучні невідомі x5, x6, x7 ,

і складемо розширену задачу:

F1 =34x1 − x2 −3x3 +3x4 −M (x5 + x6 + x7 ) → max,														(32)
3x		−2x			2	+3x	+2x		4	+ x		5	= 9,
	1					3
x1 +2x2 − x3 + x4 + x6 = 0,														(33)
− x			− x	2		+2x	+ x	4	+ x		7	= 6,
	1					3
						x1,..., x7 ≥ 0.								(34)
Вектор Xr(p1)	= (0;0;0;0;9;0;6) - початковий опорний вироджений

план розширеної задачі (32)–(34). Хід розв'язування задачі відображено в таблиці 4, яка складається з п'яти послідовних симплексних таблиць (розв'язувальні елементи в них виділено). Із базисів у таблицях

послідовно вилучаємо штучні невідомі x6, x5, x7 відповідно.

Із першої з таблиць, в якій нема штучних невідомих, отримуємо

початковий

опорний

план

задачі

Xr(4) = (0;1;3;1).

Цей план не

оптимальний,

бо

1

= −2 < 0.

Ще

одне симплексне

перетворення

3

приводить

до

частини,

з

якої

отримуємо оптимальний план

r

3

27

57

r

48

X

( 5 ) =

;

;

;0

і найбільше значення функції F(X (5) )= −

.

14

14

14

7

96

Таблиця 4.4

Баз	C		баз				В							34												-1							-3	3			- М	- М	- М		bi
ис																																									aij
																х1												х2					х3		х4		х5	х6	х7
х5		- М					9							3												-2							3	2			1	0	0	9
																																								2
х6		- М					0							1												2							-1	1			0	1	0	0
х7		- М					6							-1												-1							2	1			0	0	1	6
	j			-15М											-3М-34											М+1							-4М+3	-4М-3			0	0	0
х5		- М					9							1												-6							5	0			1		0			9
																																								5
х4		3					0							1												2							-1	1			0		0	-
х7		- М					6							-2												-3							3	0			0		1			6
																																								3
	j			-15М											М-31											9М+7							-8М	0			0		0
х3		-3					9										1									−			6				1	0					0	-
							5							5
																										5
х4		3					9							6												4							0	1					0	9
							5							5												5														4
х7		- М					3								−			13										3					0	0					1	1
							5																				5
														5
				−			3 M								13M						−31					−	3M+7
	j						5							5												5							0	0					0
х3		-3					3							-5												0							1	0
х4		3					1									14										0							0	1
																3
х2		-1					1								−				13							1							0	0
														3
	j						-7									−					2					0							0	0
														3
х3		-3			57									0												0							1		15
				14																														14
х1		34					3							1												0							0		3
				14																														14
х2		-1			27									0												1							0		3
				14																														14
	j			−				48						0												0							0		23
							7																											7

Відповідь: X = (	3	;	27	;		57	;0)- розв’язок ЗЛП, F	= −	48	.
14 14					14		max	7

97

2.4.Розв'язати ЗЛП, застосувавши двоїстий симплексний метод

F = −2x1 −3x2 − x3 − x4 → max

	2x	+ x	2	− x =3,
	1				3
− x1 + x2 + x4 =1,
	x	−5x		2	≤ −1.
	1

Розв'язання. Перемножимо першу нерівність на (−1) і введемо додаткові змінні. Перепишемо обмеження в вигляді:

− 2x1 − x2 + x3 = −3,

− x1 + x2 + x4 =1,− x1 −5x2 + x5 = −1.

													x j	≥ 0( j =
																	1,5) .
Початковий						базис–вектори													A3 , A4 , A5 ,											Псевдоплан
X =( x3 = −3; x4 =1; x5 = −1) . Складемо симплексну таблицю 4.5:
																														Таблиця 4.5
	Базис					Cбаз	В							-2	-3									-1					-1		0
														х1			х2							х3					х4		х5
	х3					-1	-3							-2	-1									1					0		0
	х4					-1	1							-1	1									0					1		0
	х5					0	-1							1	-5									0					0		1
				j			2							5	3									0					0		0
	θ j = min			j		( aij < 0 )	-							5	3									-					-		-
			aij
														2	1
	х1					-2		3						1				1						−		1			0		1
							2								2											2
	х4					1	5							0	3									−		1			1		0
							2								2											2
										5															1
	х5					0	−							0		−			11										0		0
									2															2
																2
				j			−		11					0	1									5					0		0
									2						2									2

98

х1	-2	14				1	0	−			5			0		1
		11								11					11
х4	-1		20			0	0	−			4			1		3
		11								11					11
															2
х2	- 3			5		0	1	−			1			0	−
																	11
		11								11
		−		63		0	0		28					0		1
j				11
								11							11

Відповідь: X = (1411;115 ;0; 1120 ;0) - розв'язок ЗЛП, Fmax = −1163 .

Завдання для самостійного розв'язання

2.Самостійно виконайте завдання:

2.1.Знайдіть розв'язок таких задач лінійного програмування симплексметодом:

2.1.1.

z = 2x1 − x2 +3x3 −4x4 (min),
x1 + 2x2 −3x3 + 4x4 ≤ 5,
4x		− x	2	+ 2x		−3x	4	≥ 2,
	1				3
2x		+3x		2	−5x	+ x	4	=8,
	1				3
	x j ≥ 0,				j =1,2,3,4;

2.1.2.

z = −3x1 −4x2 (min),

x ≥		10,	x			≥ 5,
	1				2
	x1 + 2x2 ≤ 20,
	− x	+ 4x	2	≤ 20,
	1
		x2 ≥ 0;

2.2. Використовуючи М-метод,

2.2.1.

Z = x1 + 3x2 + 2x3 → min

3x1 − 2x2 + x3 ≥ 5x1 + x2 + 2x3 ≥10

− 2x1 + 3x2 − x3 ≥ 2

x j ≥ 0, j =1,3.

знайдіть розв'язок задач:

2.2.2.

Z = x1 + 2x2 + 2x3 → max

x1 + x2 + 2x3 ≤122x1 + 3x2 + 4x3 =19

x1 + 2x2 + 4x3 =14

x j ≥ 0, j =1,3.

99