ИсследованиеОпераций

Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Киевский национальный университет им. Т. Шевченко

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

+ x3 + x4 − 2x5 =6,

+ x3 + x4 − 2x5 =6,

.pdf

Скачиваний:

Добавлен:

07.03.2016

Размер:

2 Мб

Скачать

☆

<<< < Предыдущая 1 2 3 4 56 / 116 7 8 9 10 11 > Следующая >>>

1)z = 2x1 − x2 +3x3 −2x4 + x5 (max)

− x1 + x2 + x3								=1,
	x1 − x2					+ x4		=1,
	x1 − x2					+ x4		=1,
	x	1	+ x	2		+ x	5	= 2,
		1		2			5
x		≥ 0, j			=
x	j	≥ 0, j			=	1,5.
	j

3)z = 2x1 +3x2 − x4 (max),

2x		1	− x	2			−2x	4		+ x	5	=16,
		1		2				4			5
3x1 +2x2 + x3 −3x4												=18,
− x			+3x		2		+4x		4		+ x	= 24,
		1			2				4		6
x		≥0, j			=		.
x	j	≥0, j			=	1,6	.
	j

5)z = 3x1 +2x3 −6 x6 (max),

2x			+ x		−3x									+6 x	=18,
−3x1				2	+2x					3	+ x	4		−2x6	= 24,
		1							3			4		6
		x		+3x				3			+ x		5	−4x	= 36,
		1						3					5	6
x		≥0, j =					.
x	j	≥0, j =				1,6	.
	j

7)z = x1 + x2 + x3 (min),

x1				− x4					−2x6 = 5,
		x	2	+2x		4	−3x	5	+ x	= 3,
			2			4		5	6
				x3 +2x4 −5x5 +6 x6						= 5,
				x3 +2x4 −5x5 +6 x6						= 5,
x		≥0, j =					.
x	j	≥0, j =			1,6		.
	j

9)z = x1 +3x2 −5x4 (max),

2x1 +4x2 + x3 +2x4										= 28,
−3x			+5x	2		−3x	4	+ x	5	= 30,
		1		2			4		5
						+8x4		+ x6 = 32,
4x1 −2x2						+8x4		+ x6 = 32,
x		≥0, j =
x	j	≥0, j =			1,6.
	j

11)z = x1 − 2x2 + 3x3 − x4 (max),

2x		− x	+ 2x	−3x	≤ 5,
	1	2	3	4
	x1	+ 2x2 − x3		+ x4 ≤ 3,
	x1	+ 2x2 − x3		+ x4 ≤ 3,

x ≥0, j = 1,4.

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

	2x	1	+ x	2	≤14,
		1		2
−3x1 +2x2 ≤ 9,
	3x		+4x			2	≤ 27	,
		1				2
x	1,2	≥0.
	1,2

4)z = 2x1 +3x2 (max),

−3x			+2x			≤6,
		1			2
	x1 −4x2 ≤ 2,
	x	1	− x	2		≤ 5,
		1		2
x	1,2	≥0.
	1,2

6)z = 4x1 +2x2 (max),

− x1 +2x2 ≤6,
	x1		+ x2	≤ 9,

	3x1		− x2	≤ 15,

x	1,2	≥ 0.

8)z = x1 + x2 (max),

5x1 −2x2 ≤7,
− x		+ x	2	≤ 5,
	1		2
	x	+ x	2	≤6,
	1		2
x		≥0.
	1,2

10)z = x1 + x2 (max),

2x1 +11x2			≤ 38,
	x1	+ x2	≤7,

		−5x2	≤ 5,
4x1
x	1,2	≥ 0.

12)z = 3x2 − x4 (max),

x		− 2x	+ x	= 8,
	1	2	4
		x2 + x3 −3x4 =6,
		x2 + x3 −3x4 =6,

		≥0, j = 1,4.
x j		≥0, j = 1,4.

13)z = 2x1 − x2 +3x3 −2x4 + x5 (max)

− x1 + x2 + x3										=1,
	x		− x	2		+ x		4		=1,
		1		2				4
	x		+ x	2			+ x		5	= 2,
		1		2					5
x		≥0, j			=		.
x	j	≥0, j			=	1,5	.
	j

15)z = 8x2 +7 x4 + x6 (max),

x1 − 2x2						− 3x4					− 2x6 = 12,
		4x	2	+ x	3	− 4x			4		− 3x		= 12,
			2		3				4			6
		5x	2			+ 5x		4		+ x	5	+ x	= 25,
			2					4			5	6
x
x	j	≥ 0, j =			1,6		.
	j

17)z = 3x1 +2x5 −5x6 (max),

2x1 + x2

−3x5 +5x6 = 34,

4x1

+ x3

+2x5 −4x6 = 28,

−3x

+ x

−3x

+6 x

= 24,

≥ 0, j =

1,6.

19)z = −2x2 + x4 + 3x5 (max),

x ≥0, j = 1,5.

14)z = x1 −2x2 (max),

−3x1 +2x2 ≤ 6,
	x1		−4x2	≤ 2,

	x1		− x2	≤ 5,

x	1,2	≥ 0.

16)z = 2x1 − x2 +3x3 + x4 (max),

2x1 + x2 −3x3									=10,
		x1		+ x3 + x4					=7,
		x1		+ x3 + x4					=7,
−3x			1	−2x		3	+ x	5	= 4,
			1			3		5
x		≥ 0, j =
x	j	≥ 0, j =			1,5.
	j

18)z = 8x1 + 2x2 (max),

	x	−4x		≤ 4,
	1		2
−4x1 + x2 ≤ 4,
	x		+ x	≤6,
	1		2
	x		≥0.
	1,2

20)z = 3x1 + x2 (max),

− x		+ 2x	+ x		= 4,
	1	2	3
	x1	− x2		+ x4 = 3,
	x1	− x2		+ x4 = 3,

x ≥0, j = 1,4.

7. Методи штучного базису

Основна ідея методів штучного базису полягає у побудові та розв'язуванні симплекс-методом допоміжної канонічної задачі, по розв'язку якої можна або відновити допустимий чи оптимальний розв'язок вихідної задачі, або встановити її нерозв'язність.

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

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

7.1Метод штучного базису у найпростішій формі

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

Нехай вихідна задача зведена до вигляду

L = ∑c j x j → max ,

(7.1)

j=1

= a10 ,

a11x1 +... + a1r xr + xr +1

a21x1 +... + a2r xr

+ xr +2

= a20 ,

...............................................................

+ akr xr

+ xn

= ak0 ,

(7.2)

ak1x1 +...

+ +... a

= a

k +1,0

k +1,1 1

k +1,r r

...............................................................

x +

+ a

= a

m1 1

mr r

x j

≥ 0, j =

(7.3)

1, n

ai0 ≥ 0,i =

(7.4)

1, m

Припустимо, що rangA = m , що загальності не обмежить.

Очевидно,

що змінні

xr+1 ,..., xn

можна вважати базисними, оскільки

відповідні їм вектори умов одиничні:

Ar +1 = e1,..., An = ek .

Внаслідок того,

що

rangA = m ,

довільний базис системи векторів

{A1, A2 ,..., An}

повинен складатися з m векторів, однак

k < m .

Додамо у ліву частину кожного з рівнянь системи (7.2), починаючи з

k +1 -го, відповідні штучні змінні:

y1 ≥ 0

– в

(k +1) -е,

y2 ≥ 0 – в (k + 2) -е, і

т.д., ym−k ≥ 0

– в m -е рівняння. Отримаємо таку канонічну лінійну систему

обмежень

+ + a1r xr + xr +1

= a10 ,

a11x1

a21x1 +... + a2r xr

+ xr +2

= a20 ,

...............................................................

+ + akr xr

+ xn

= ak0 ,

(7.5)

ak1x1

x + +... a

+ y

= a

k +1,0

k +1,1 1

k +1,r r

...............................................................

+ + a

+ y

= a

−k

m1 1

x j

≥ 0, j =

(7.6)

1, n

ai0 ≥ 0,i =

(7.7)

1, m

Система (7.5)−(7.7) має опорний план

= (0,...,0, a

,...,a

) , якому

123

відповідає одиничний базис {Ar+1 , Ar+2 ,..., An , An+1 ,..., An+mr −k }.

Допоміжна задача у найпростішому випадку полягає у мінімізації суми штучних змінних або максимізації суми штучних змінних зі знаком “мінус”, тобто

~	m−k
L∂( x) = − ∑yi → max ,		(7.8)
	i=1

за виконання умов (7.5)−(7.7).

Вкажемо на ту особливість задачі (7.8), (7.5)−(7.7), що вона завжди має оптимальний розв'язок, оскільки вона допустима і її цільова функція обмежена зверху

m−k

L∂ ( x)

= − ∑yi ≤ 0 .

(7.9)

i=1

Теорема 7.1 (про розв'язок допоміжної задачі у методі штучного базису).

Нехай:

Задача

(7.8),

(7.5)−(7.7)

розв'язана

симплекс-методом і

– її оптимальний розв'язок.

= (x1

,..., xn

, y1 ,..., ym−k )

Тоді:

1) якщо серед чисел y1* ,..., ym* −k

є відмінні від нуля, то вихідна

задача (7.1)−(7.4) не має допустимих розв'язків;

2) якщо y1* = y2* =... = ym* −k =0

і серед векторів базису розв'язку

немає штучних,

то вектор

є опорним планом

= (x1

, x2 ,..., xn )

задачі (7.1)−(7.4);

3) якщо y1* = y2* =... = ym* −k =0 і серед векторів базису розв'язку

~*	є l штучних, то вектор	x	*	*	*	*	T	є допустимим
x	є l штучних, то вектор	x		= (x1	, x2	,..., xn )		є допустимим

виродженим розв'язком задачі (7.1)−(7.4), для якого існує базис, що складається лише із векторів системи {A1, A2 ,..., An} який можна

отримати шляхом l однократних замін штучних векторів у базисі.

7.1.1. Приклади.

Приклад 1. Розв'язати задачу ЛП:

L = x1 +4x2 + x3 → max,

− x

+ x

= 3,

2x1 −5x

2 − x3 = 0,

≥ 0, j

=1,3.

x j

Розв'язування. Задача

має стандартну форму.

Матриця

A коефіцієнтів

A = [A1

−1

системи обмежень

, A2

не має жодного одиничного

, A3 ]=

−5

−1

стовпця,

тому вводимо повний штучний базис. З цією метою доповнюємо A

двома штучними базисними векторами A4

; отримаємо таку

матрицю

коефіцієнтів

системи

обмежень

допоміжної

задачі

−1

−5

−1

. Записуємо допоміжну задачу:

L∂ = −y1 − y2 → max,

x1 − x2 + x3 + y1

= 3,

−5x

− x

+ y

=0,

≥0, j = 1,3,

x j

y , y

≥0

−штучнізмінні.

Ця задача має канонічну форму, тому розв’язуємо її розглянутим вище симплекс-алгоритмом. Результати обчислень заносимо до симплекстаблиці (див. таблицю 7).

Пояснення

до

змісту таблиці.

Нульовий

крок:

= (0,0,0,3,0)

=[ A4 , A5 ] ,

) =

= 6

L∂ ( x

(cб , α0 ) = −3

∆1

= (cб,α0 ) −c1

= −3 , ∆2

= (cб,α2 ) −c2

∆0

= (c

α0 )

−c

=0 ,

∆0

= ∆0 = 0 .

Таблиця 7.

№

cб

xб

–1

кр.

–1

-1

3 1

–1

← y2

-5

-1

0 2

∆ j

L∂

-3

−3 ↑

-1

← y1

3 2

−5 2

−1 2

∆ j

L∂

-3

−3 2 ↑

−3 2

∆ j

L∂

∆0 = −3

< 0 , тому

A вводиться в базис.

A – ведучий стовпчик для

симплекс-перетворення.

= 0 ,

тому

виводиться з

базису.

Другий

θ0 = min(θ1 ,θ2 ) =θ2

рядок є ведучим для симплекс-перетворення.

Після симплекс-перетворення кроку 0

стовпчик

відкинутий,

оскільки штучна змінна y2

вже не є базисною.

Перший крок:

= (0,0,0,3,0)

=[ A4

, A1] ,

L∂ ( x

) = (cб , α0 ) = −3 ,

∆12 = (c1б,α12 ) −c2 = −3 2

∆13

= (cб1 , α31 ) − c3

= −3 2 .

При

симплекс-

перетворенні кроку 1

в базис вводиться вектор

A3 ,

з базису виводиться

вектор

A4 .

Отже, вектор

є оптимальним розв'язком допоміжної

= (5,2,0,0,0)

задачі. Серед векторів його базису немає штучних. Тому обведена жирною

лінією частина таблиці кроку 2 містить коефіцієнти канонічної форми вихідної задачі, яка визначає її початковий опорний план x0 = (5,2,0)T .

Заносимо знайдену канонічну форму вихідної задачі у симплекстаблицю (див. таблицю 8) і розв'язуємо вихідну задачу.

												Таблиця 8.
№	cб	xб	A0	0		0	0			θ		Пояснення
кр.				x1		x2	x3

0	4	x2	2	0		1	1					x0 = (5,2,0)T ,
	1	x1	5	1		0	2					L( x0 ) = (cб,α0 ) =13,

	∆ j	L	13	0		0	5					∆1 = ∆2 = 0,
											∆3 = (cб,α3 ) −c3 = 5 > 0.

	Всі	симплекс-різниці			∆ j ≥ 0 ,		j =		. Тому			опорний план x0 є
								1,3

оптимальним розв'язком вихідної задачі. Йому відповідає оптимальне

значення цільової функції L( x0 ) = 13 .

Приклад 2. Розв'язати задачу лінійного програмування.

L = −x1 + 2x2 − 3x3

→ max,

− 2x

+ x

+ 3x

= 2,

2x1

+ 3x2 + 4x3 = 1,

x j ≥ 0, j = 1,3.

Розв'язування. Задача

має

стандартну

форму.

Доповнюємо

матрицю

−2

коефіцієнтів

A = [ A1

, A2 , A3 ] =

двома

штучними

векторами

A4 = (1, 0)T ,

A5 = (0, 1)T

та записуємо допоміжну канонічну задачу:

L∂ = −y1 − y2 → max,

− 2x

+ x

+ 3x

+ y

= 2,

+ 3x2 + 4x3

+ y2 = 1,

2x1

j = 1,3,

yi ≥

0,i = 1,2 −штучнізмінні,

x j ≥

яку розв'язуємо симплекс методом (див. таблицю 9).	x	= (0,0,0,2,1)		,
Пояснення до змісту таблиці. На нульовому кроці			T
	~(0 )

Lд ( x(0 ) ) = −3, ∆4 = ∆5 =0 ∆1 =0 , ∆2 = (cб ,α2 ) −c2 = −4 , ∆3 =(cб ,α3 ) −c3 = −7 <0 . 57

Таблиця 9.

№

cб

xб

–1

кр.

–1

–2

2 3

–1

←

∆j

L∂

–3

–4

−7 ↑

–1

−7

− 5

1 2

3 4

x 3

∆ j

L∂

− 5

На першому кроці

= (0,0,

14 , 5 4 ,0)

~(1)

) = −5 4 ,

∆3

= ∆4

=0 ,

, Lд( x

∆1 =

2 ,∆2 =

4 .

Всі

оцінки

∆ j

>0 ,

тому

вектор

~(1)

= (0,0,

4 ,

4 ,0)

оптимальним розв'язком допоміжної задачі.

у цьому розв'язку відмінне від

Оскільки значення штучної змінної y1

нуля: y1(1) = 5 4 ≠ 0 , то вихідна задача допустимих розв'язків немає.

Приклад 3. Розв'язати задачу ЛП.

L = x1 + 2x2 → max,

+ 2x

≤ 4, − x

− x

≤ −4,

− x1 + x2 ≤ 4,

x1, x2 ≥0.

Розв'язування. Задача має загальну форму. Зводимо її до стандартної

форми

L = x1 +2x2

→ max,

x1 +2x2 + x3

= 4,

+ x4

= 4,

− x1 + x2

− x

= −4,

≥ 0, j =1,5.

Матриця коефіцієнтів при невідомих

											1	2		1	0	0
	A =		[ A , A , A , A , A ] =								−1 1 0 1					0
	A =		[ A , A , A , A , A ] =								−1 1 0 1					0
			1	2	3			4	5
											1	1		0	0	−1
має два	одиничних			вектори:					A3 = (1, 0, 0)T ,					A4 = (0, 1, 0)T . Доповнюємо
матрицю вектором			A6 = (0, 0, 1)T . Відповідну йому штучну змінну позначимо
через x6 ≥ 0 . Отримаємо таку матрицю
											1	2		1	0	0	0
	[ A , A , A , A , A , A ] =										−1	1		0 1 0 0
	[ A , A , A , A , A , A ] =										−1	1		0 1 0 0				.
		1	2	3	4			5	6		1	1		0 0 −1 1
											1	1		0 0 −1 1
Як система векторів-умов									Aj ,		j =		,	вона має одиничний базис
Як система векторів-умов									Aj ,		j =	1,6	,	вона має одиничний базис
[ A3 , A4 , A6 ] ,	в якому		A6	– штучний базисний вектор. Записуємо допоміжну
канонічну задачу
	Lд = −x6 → max,
	x1 + 2x2 + x3									= 4,
	− x + x			2	+ x					= 4,
			1	2			4
	x		+ x					− x	+ x	= 4,
	1		2					5	6
	x		≥0, j =					−штучназмінна,
	x	j	≥0, j =		1,6	; x		−штучназмінна,
		j			6

яку розв’язуємо симплекс-методом (див. таблицю 10).

Пояснення до змісту таблиці.

~(1)

= (4,0,0,8,0,0)

На першому кроці x

~(1)

і всі оцінки

∆ j

≥ 0 ,

j =1,6 ,

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

розв'язок допоміжної

тому x

задачі. Відповідний йому базис B1 =[ A

, A

, A ] містить штучний вектор A .

Вибираємо перший не штучний вектор, який має ненульову третю

компоненту

A2 = (2; 3; −1)T і виконуємо крок повного виключення з ведучим

елементом

α32 = −1 .

При цьому штучний вектор A6

виводиться з базису.

Новий базис B

=[ A1

, A4 , A2 ]

розв'язку

~(1)

не містить штучних векторів.

Отже,

вектор

~(1)

= (4,0,0,8,0,0)

є початковим опорним планом

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

									Таблиця 10.
№	cб	xб	A0	0	0	0	0	0	–1	θ
кр	cб	xб	A0	x1	x2	x3	x4	x5	x6	θ
кр				x1	x2	x3	x4	x5	x6
	0	← x3	4	1	2	1	0	0	0	4
0	0	x4	4	–1	1	0	1	0	0
	–1	x6	4	1	1	0	0	–1	1	4
	∆ j	Lд	–4	–1 ↑	–1	0	0	1	0
	0	x1	4	1	2	1	0	0	0
1	0	x4	8	0	3	1	1	0	0
	–1	x6	0	0	–1	–1	0	–1	1
	∆ j	Lд	0	0	1	1	0	1	0
	0	x1	4	1	0	–1	0	–2
2	0	x4	8	0	0	–2	1	–3
	0	x2	0	0	1	1	0	1
	∆ j	Lд	0	0	0	0	0	0
	Записуємо цю канонічну форму у симплекс-таблицю (див. таблицю
11) та розв'язуємо вихідну задачу.									Таблиця 11.
									Таблиця 11.
№	cб	xб	A0	0	0	0	0	0		θ
кр	cб	xб	A0	x1	x2	x3	x4	x5
кр				x1	x2	x3	x4	x5
	1	x1	4	1	0	–1	0	–2
	0	x4	8	0	0	–2	1	–3
	2	x2	0	0	1	1	0	1
	∆ j	L	4	0	0	1	0	0

~1	Всі елементи			∆ -рядка невід'ємні, тому початковий опорний план
	= (4,0,0,8,0)	T	є і	оптимальним розв'язком стандартної		задачі. Її
x
				~1	) = 4 .
оптимальне значення рівне L( x
	Якщо повернутись до вихідної загальної задачі, то її оптимальним
розв'язком та оптимальним значенням будуть відповідно вектор						x* = (4,0)T
та число Lmax = 4 .
					60

<<< < Предыдущая 1 2 3 4 56 / 116 7 8 9 10 11 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
01.03.2025854 Кб1Информатика, модуль 2.doc
#
19.03.201545 Кб13Информационные.docx
#
08.07.20192 Мб4Иоанна Хмелевская -- (Nie)Boszczyk maz_POL.doc
#
01.05.2025175 Кб1ИОГП 3 контрольная.doc
#
19.03.201573 Кб6иппв.docx
#
07.03.20162 Мб20ИсследованиеОпераций.pdf
#
28.04.2019198 Кб6Историография. Шпоры.docx
#
23.12.2018333 Кб7история 2 - 2003.doc
#
01.05.202579 Кб1История гидрологии.doc
#
19.03.2015199 Кб6история дипломатии том 2 ГЛАВА 7.doc
#
07.03.20162 Мб53История Медицины. Т.1..pdf