Добавил:

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

Вуз:

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

Предмет:

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

Файл:

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

.pdf

Скачиваний:

Добавлен:

07.03.2016

Размер:

1.89 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 7 8 910 / 1110 11 > Следующая >>>

Якщо

серед

базисних

компонент

i ={1,2,...,m}

xki =αi0 ,

псевдоплану

знайдеться принаймні одна

αl0 така,

що αl0 < 0 і

αlj ≥ 0 ,

j =

, то пряма задача (10.1) не має допустимих розв’язків.

1, n

Теорема 10.3 (Достатні умови поліпшення псевдоплану).

Нехай

(x1, x2 ,..., xn )

− деякий псевдоплан прямої задачі (10.1),

{Aki }i=

− відповідний йому спряжений базис системи {Aj}j=

, відомі

1,m

1,n

розклади (10.4), (10.5)

векторів Aj і A0 по спряженому базису і для

будь-якого псевдоплану задачі (10.1) всі небазисні оцінки додатні:

∆ j >0 ,

j =

1, n

, j ≠ ki

( i =

1, m

(10.7)

Якщо

серед

базисних

компонент

i {1,2,...,m}

xki =αi0 ,

псевдоплану

знайдеться принаймні одна

αl0 така,

що αl0 <0 і

αlj <0 ,

j ≠ ki ,

i =

j {1,2,...,n} , то заміна

у спряженому базисі

1, m

{Aki }i=

вектора Akl

небазисним вектором Ak , знайденим з умови

1,m

∆

∆j

, αlk

,αlj ≤ 0

(10.8)

приведе до нового спряженого базису, якому відповідає псевдоплан з меншим значенням цільової функції задачі (10.1).

Зауваження 10.1. За умов теореми 10.3 вектор				Ak	для введення в базис
визначається однозначно. Якщо зняти умову (10.7), то множина
Arg	min	}	∆j			(10.9)
			∆j
			αlj
	{j:αlj <0		αlj
може виявитись неодноелементною, тобто				k	може	визначатись
неоднозначно. У цьому випадку за k можна					приймати,	наприклад,
найменший елемент множини (10.9).

10.2. Алгоритм двоїстого симплекс-методу.

1. Знайти спряжений базис прямої задачі (10.1), а також відповідний

йому початковий псевдоплан x(0) . Це можна зробити за означенням або методом штучного базису для двоїстої задачі знайти деякий базисний допустимий розв’язок та визначити ті з обмежень двоїстої задачі, які він обертає в рівності; відповідні їм вектори умов прямої задачі Aki і утворюють

спряжений базис.

Поточний псевдоплан позначимо через x(s) (зауважимо, що відповідну форму задачі ЛН, яка його визначає, називають псевдоканонічною).

Перейти до наступного пункту.

2. Перевірити умову: α0(s) ≥0 . Якщо умова виконується, то − кінець

обчислень, розв’язок x(s) − оптимальний.			В іншому випадку перейти до
наступного пункту.				l такий, що αl(0s) <0 і всі
3. Перевірити умову: Існує номер рядка
αlj(s) ≥0 , j =		. Якщо умова виконується,	то −	кінець обчислень, задача
	1, n

(10.1) допустимих розв’язків немає. В іншому випадку перейти до наступного пункту.

4. Визначити номер направляючого рядка l для перетворення Жордана-Гаусса:

l =arg min{αi(0s)} .
{i:αi(0s ) <0}
Перейти до наступного пункту.
5. Визначити номер направляючого стовпця k для перетворення
Жордана-Гаусса:
k = arg min	∆(js)	.
k = arg min	αlj(s)	.
{ j:αlj( s ) <0}	αlj(s)

Перейти до наступного пункту.

6. Виконати крок повного виключення методу Жордана-Гаусса на розширеній матриці коефіцієнтів поточної псевдоканонічної форми з ведучим

елементом αlk( s) :

			α(s)
αij(s+1) =αij(s)		−	lj		αik(s)		, i =	1, m	, i ≠ l , j =	0, n
αij(s+1) =αij(s)		−	α(s)		αik(s)		, i =	1, m	, i ≠ l , j =	0, n
			lk
	α(s)
αlj(s+1) =	lj	, j =		0, n		.
αlj(s+1) =	α(s)	, j =		0, n		.
	lk

Перейти до пункту 2.

Зауваження 10.2. Симплекс-таблиця для двоїстого симплекс-методу має той же самий вигляд, що і для звичайного симплекс-методу, тільки замість θ - стовпця таблиця обрамляється рядком γ - відношень:

γ j =	∆j	.
	αlj
		{j:αlj <0}

10.3. Приклади.

Приклад 1. Для даної задачі ЛП

z = 8x1 +6 x2 → max,

2x1 + 5x2 ≤11,4x1 + x2 ≤10,

x1, x2 ≥0

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

z = 8x1 +6 x2 → max,

+ 5x

+ x

=11,

(10.10)

+ x4 =10,

4x1 + x2

≥0, j = 1,4.

x j

Відповідно до обмежень-рівностей даної задачі вводимо вільні за

знаком двоїсті змінні

y1, y2

і записуємо двоїсту задачу:

yT b → min,

11y1 +10 y2 → min,

yT A ≥ c ,

2 y

+ 4 y

≥ 8,

A ≥ c ,

або

+ y

≥6,

5 y

yT A3 ≥ c3 ,

y1 ≥ 0,

A4 ≥ c4 ,

≥ 0.

Перевіримо

базис

{A1, A3}

на

спряженість. Обертаючи відповідні

цим векторам нерівності-обмеження двоїстої задачі у рівняння, отримаємо систему

2 y			+4 y		= 8,	y		= 2,
	1			2			2
y1		=0,				y1 =0.

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

тому базис {A1, A3} не				є спряженим. Розглянемо тепер базис {A2 , A3} .
Відповідна йому система лінійних рівнянь має вигляд:
5 y		+ y		=6,	y		=6,
	1		2			2
y1	=0,				y1 =0.
							93

Всі обмеження двоїстої задачі цим розв’язком задовольняються,
тому {A2 , A3} є спряженим базисом системи векторів {A1, A2 , A3 , A4} .
Зауважимо, що {A3 , A2} також буде спряженим базисом.
Методом повного виключення Жордана-Гаусса зводимо стандартну
задачу (10.10) до псевдоканонічної форми							відносно базису {A2 , A3} іі
розв’язуємо її двоїстим симплекс-методом (див. таблицю 19).									Таблиця 19.

№ кр.	cбаз	xбаз	A0		8		6	0	0
					A1		A2	A3	A4

0		x3	11		2		5	1	0
		x2	10		4		1	0	1

1	0	← x3	-39	-18			0	1	-5
	6	x2	10		4		1	0	1

	∆ j	L	60	16			0	0	6
	γ			8	9	↑			6	5

2	8	x1	39 18		1		0
	6	x2	4 3		0		1

	∆ j	L	76 3

Пояснення до таблиці. У таблиці кроку 0 записані коефіцієнти

стандартної задачі		(10.10). За		початковий вибраний спряжений базис
{A3 , A2} .	Вектор A3		одиничний	і перетворень	не потребує. Вектор A2
потрібно	привести	до	вигляду	(0, 1)T , ведучим	елементом перетворення

Жордана-Гаусса, що це здійснює, є елемент a22 =1 таблиці кроку 0.

Таблиця кроку 1 містить коефіцієнти псевдоканонічної форми задачі, яка відповідає одиничному спряженому базису {A3 , A2} і визначає її

початковий псевдоплан x0 = (0, 10, −39, 0)T . Псевдоплан x0 має від’ємну

компоненту і не задовольняє ознаку оптимальності двоїстого симплексметоду. За цією від’ємною компонентою визначається направляючий рядок, а за мінімумом γ − відношень − направляючий стовпчик (позначені

стрілками) перетворення Жордана-Гаусса, за допомогою якого здійснюється перехід до нового спряженого базису {A1, A2} і нового псевдоплану задачі

x1 = (39 18 , 4 3 , 0, 0)T , Цей псевдоплан є оптимальним. Оптимальне значення

задачі L( x1 ) =76 3 .

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

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

Приклад 2. Розв’язати двоїстим симплекс-методом задачу ЛП:

−x1 − x2 → max,

3x1 + x2 ≥ 8, x1 − x2 ≤ 3,x1 + 2x2 ≥6, x1,2 ≥0.

Розв’язування. Введенням у обмеження-нерівності вихідної задачі балансних змінних x1, x2 , x3 ≥ 0 з відповідними знаками зводимо загальну задачу до

стандартної, при цьому змінюємо знаки коефіцієнтів двох перших рівнянь на протилежні. Отримаємо:

−x1 − x2 → max,
−3x			− x	+ x			= −8,
	1		2	3
	− x1 − 2x2				+ x4		= −6,	(10.11)
	x		− x			+ x	= 3,
	1		2	5
	x		≥ 0, j =			.
	x	j	≥ 0, j =		1,5	.
		j

Задачу (10.11) розв’язуємо двоїстим симплекс-методом (див. таблицю 20). Пояснення до таблиці. Всі симплекс-оцінки ∆j в таблиці кроку 0

невід’ємні, тому за критерієм спряженості базису задача (10.11) має

псевдоканонічну	форму.	Вона визначає	початковий	псевдоплан
x0 = (0, 0, −8,−6, 3)T ,	який	відповідає спряженому базису		{A3 , A4 , A5} .
Початковий псевдоплан		x0 неоптимальний,	оскільки він	має від’ємні

компоненти. Для переходу до нового спряженого базису за направляючі рядок і стовпчик перетворення Жордана-Гаусса вибираємо перший рядок і перший стовпчик таблиці кроку 0 (позначені стрілками). Направляючий рядок вибираємо за мінімальним номером рядка з від’ємною компонентою

псевдоплану у	стовпчику	A0 , направляючий стовпчик − за мінімумом
γ − відношень.	Виконуємо	перетворення повного виключення з ведучим

елементом a11 = −3 на таблиці кроку 0 і заповнюємо таблицю кроку 1. 95

									Таблиця 20.
№ кр.	cбаз		xбаз	A0	−1	−1	0	0	0
№ кр.	cбаз		xбаз	A0	A1	A2	A3	A4	A5
					A1	A2	A3	A4	A5
	0		← x3	−8	−3	−1	1	0	0
0	0		x4	−6	−1	−2	0	1	0
	0		x5	3	1	−1	0	0	1
	∆j		L	0	1	1	0	0	0
	γ				13 ↑	1
	−1		x1	8 3	1	1 3	−13	0	0
1	0		← x4	−10 3	0	−5 3	−13	1	0
	0		x5	13	0	−4 3	13	0	1
	∆j		L	−8 3	0	2 3	13	0	0
	γ					2 5 ↑	1
	−1		x1	2	1	0			0
2	−1		x2	2	0	1			0
	0		x5	3	0	0			1
	∆j		L	−4
	Новий псевдоплан			x1 = (8 3 , 0, 0,−10 3 , 13 )T , який відповідає спряженому
базису	{A1, A4 , A5} , також неоптимальний. Тому виконуємо ще одне
перетворення повного виключення з ведучим							елементом		a22 = − 5 3	на
таблиці кроку 1 і заповнюємо таблицю кроку 2.
	Елементи цієї таблиці є коефіцієнтами псевдоканонічної форми
задачі (10.11), яка є водночас і канонічною і яка визначає невід’ємний, тобто
оптимальний,		псевдоплан		x2 = (2, 2, 0, 0, 3)T з відповідним				йому спряженим
базисом {A , A , A } . Оптимальне значення задачі (10.11) рівне L( x 2 ) = −4.
	1	2	5

10.4. Вправи.

Розв'язати дані задачі двоїстим симплекс-методом, при необхідності початковий спряжений базис знайти за означенням або прямим перебором базисних розв’язків методом Жордана-Гаусса з перевіркою за критерієм спряженості базису:

1)L = x1 + 2x2 → max,

2x1 + 3x2 ≤ 8,

2x1 + x2 ≤ 6,x1 + x2 ≥1,x1,2 ≥0.

3)L =6 x1 + 4x2 → min,

2x1 + x2 ≥ 8,

x1 − x2 ≤ 1,− x1 + 2x2 ≥1,x1,2 ≥0.

5)L = x1 + 3x2 → max,

x1 + x2 ≥ 3,

6 x1 + x2 ≤ 42,2x1 −3x2 ≥6,

x1,2 ≥0.

7)L = 2x1 −3x2 → min,

5x1 + 2x2 ≥10,x1 + 3x2 ≤12,

x1,2 ≥0.

9)L = 2x1 − x2 → max,

3x1 + x2 ≥18,x1 + 2x2 ≤ 12,

x1,2 ≥0.

11)L = −x1 −10x2 → max,

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

2)L = −2x1 + x2 → min,

2x1 + x2 ≤ 8,

x1 + 3x2 ≥ 6,3x1 + x2 ≥ 3,x1,2 ≥0.

4)L = 4x1 + 3x2 → max,

5x1 + 2x2 ≥ 20,x1 + 3x2 ≤15,

x1,2 ≥ 0.

6)L = −x1 − 2x2 → min,

5x1 − 2x2 ≤ 4,

− x1 + 2x2 ≤ 4,x1 + x2 ≥ 4,x1,2 ≥0.

8)L = x1 + x2 → min,

2x1 + x2 ≥ 8,

x1 + 3x2 ≥6,x1,2 ≥0.

10)L = x1 + x2 → max,

2x1 + x2 ≤18,x1 + 2x2 ≤16,

x1,2 ≥ 0.

12) L =			− x2	− 2x4		→ max,
−6 x			+ 3x			= −1,
		1	2			= −2,
			−3x2 + x3 −3x4			= −2,
			+6 x2	−12x4 + x5 = − 2,
			+6 x2	−12x4 + x5 = − 2,
	x		≥0, j =		.
	x	j	≥0, j =	1,5	.
		j

13)

L =

− 2x3 − x4 → max,

2x1

− 2x3 − 2x4

= −1,

−32x

= −7,

8x3 −16 x4 + 4x5 = −1,

≥ 0, j =

1,5

15)

L =

− x3

− 2x4 → max,

2x3 + 8x4 + 2x5 = −1,

6 x

−4x

+ 2x

= −3,

+ 2x

−6 x

= −1,

≥0, j =

1,5

14)	L = −x1								−5x4 → max,
	−12x1								+ 3x4 + 3x5 = −8,
			3x			+	3x		−9x		= −8,
				1			3		4
			x		+ 3x				−3x		= −3,
				1		2			4
			x		≥ 0, j =					.
			x	j	≥ 0, j =			1,5		.
				j
16)	L =				− 2x2				−3x4 → max,
				4x2 + 4x3 −8x4							= −3,
	2x		+		4x				−6 x		= −1,
		1			2				4
			−8x						+ 2x		+ 4x = −7,
					2				4		5
			x		≥ 0, j =					.
			x	j	≥ 0, j =			1,5		.
				j

Література.

1. Калихман И.Л.	Сборник	задач	по	математическому
программированию. − М.: Высш. шк., 1975. − 270 с.

2.Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях, − М.: Наука, 1991.− 447 с.

3.Зайченко Ю.П., Шумилова С.А. Исследование операций. Сборник задач.− К.: Вища шк., 1990. − 239 с.

4.Капустин В.Ф. Практические занятия по курсу математического программирования. − Л.: Изд-во Ленингр. ун-та, 1976. − 192 с.

5.Попов Ю.Д., Тюптя В.І., Шевченко В.І. Методи оптимізації.

Навчальний посібник для студентів спеціальностей «Прикладна математика», «Інформатика», «Соціальна інформатика». − К.:

Абрис, 1999. − 217 с.

Зміст

1.	ВСТУП. .............................................................................................................	3
2.	БАЗИСНІ РОЗВ'ЯЗКИ СИСТЕМИ ЛІНІЙНИХ РІВНЯНЬ, ЇХ ОБЧИСЛЕННЯ.
ОПОРНІ РОЗВ'ЯЗКИ ТА СИМПЛЕКС-ПЕРЕТВОРЕННЯ.................................		3
	2.1. ОСНОВНІ ФАКТИ. ...........................................................................................	3
	2.2. ПРИКЛАДИ. ...................................................................................................	7
	2.3. ВПРАВИ......................................................................................................	11
3.	ПОБУДОВА МАТЕМАТИЧНИХ МОДЕЛЕЙ ЛІНІЙНОГО
ПРОГРАМУВАННЯ. ..........................................................................................		13
	3.1. ОСНОВНІ ПРАВИЛА. .....................................................................................	13
	3.2. ПРИКЛАДИ. .................................................................................................	13
	3.2. ВПРАВИ......................................................................................................	19
4.	ЗАГАЛЬНА, СТАНДАРТНА ТА КАНОНІЧНА ФОРМИ ЗАДАЧІ ЛП. .........	23
	4.1. ОСНОВНІ ФАКТИ. .........................................................................................	23
	4.2. ПРИКЛАДИ. .................................................................................................	26
	4.3. ВПРАВИ......................................................................................................	32
5.	ГЕОМЕТРИЧНА ІНТЕРПРЕТАЦІЯ ТА ГРАФІЧНИЙ СПОСІБ
РОЗВ’ЯЗУВАННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ. ........................		33
	5.1. ГЕОМЕТРИЧНА ІНТЕРПРЕТАЦІЯ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ.................	33
	5.2. ГРАФІЧНИЙ СПОСІБ РОЗВ’ЯЗУВАННЯ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ. ........	34
	5.3. ПРИКЛАДИ. .................................................................................................	37
	5.4. ВПРАВИ......................................................................................................	42
6.	СИМПЛЕКС-АЛГОРИТМ ДЛЯ РОЗВ'ЯЗУВАННЯ КАНОНІЧНИХ ЗАДАЧ
ЛІНІЙНОГО ПРОГРАМУВАННЯ.......................................................................		43
	6.1 ОСНОВНІ ФАКТИ. ..........................................................................................	43
	6.2. АЛГОРИТМ СИМПЛЕКС-МЕТОДУ.....................................................................	46
	6.3. ПРИКЛАДИ. .................................................................................................	48
	6.4.ВПРАВИ.......................................................................................................	50
7.	МЕТОДИ ШТУЧНОГО БАЗИСУ ...................................................................	52
	7.1 МЕТОД ШТУЧНОГО БАЗИСУ У НАЙПРОСТІШІЙ ФОРМІ.........................................	53
	7.1.1. Приклади...........................................................................................	55
	7.2 М-МЕТОД ПОБУДОВИ ДОПОМІЖНОЇ ЗАДАЧІ. .....................................................	61
	7.2.1. Приклади...........................................................................................	62
	7.3. ВПРАВИ......................................................................................................	66
	99

8. РОЗВ'ЯЗУВАННЯ ЗАДАЧ ЛП МОДИФІКОВАНИМ СИМПЛЕКС-
МЕТОДОМ..........................................................................................................	67
8.1. ОСНОВНІ ФАКТИ. .........................................................................................	67
8.2. АЛГОРИТМ МОДИФІКОВАНОГО СИМПЛЕКС-МЕТОДУ. ........................................	69
8.3. ПРИКЛАДИ. .................................................................................................	70
8.4. ВПРАВИ......................................................................................................	72
9. ПОБУДОВА ДВОЇСТИХ ЗАДАЧ ТА ЗАСТОСУВАННЯ ТЕОРЕМ
ДВОЇСТОСТІ У ЛІНІЙНОМУ ПРОГРАМУВАННІ .............................................	74
9.1. ЕКОНОМІЧНА ІНТЕРПРЕТАЦІЯ ДВОЇСТОСТІ. ВЗАЄМОДВОЇСТІ ЗАДАЧІ ЛП............	74
9.1.1. Приклади...........................................................................................	77
9.1.2. Вправи. ..............................................................................................	79
9.2. ТЕОРЕМИ ДВОЇСТОСТІ..................................................................................	80
9.2.1. Приклади...........................................................................................	81
9.2.2. Вправи. ..............................................................................................	87
10. РОЗВ’ЯЗУВАННЯ ЗАДАЧ ЛП ДВОЇСТИМ СИМПЛЕКС-МЕТОДОМ.......	89
10.1. СПРЯЖЕНИЙ БАЗИС, ПСЕВДОПЛАН ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ.........	89
10.2. АЛГОРИТМ ДВОЇСТОГО СИМПЛЕКС-МЕТОДУ..................................................	91
10.3. ПРИКЛАДИ. ...............................................................................................	93
10.4. ВПРАВИ....................................................................................................	96
ЛІТЕРАТУРА......................................................................................................	98
ЗМІСТ.................................................................................................................	99

100

<<< < Предыдущая 1 2 3 4 5 6 7 8 910 / 1110 11 > Следующая >>>

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

#
19.03.201558.07 Кб184Инструкция по учету Агентуры.docx
#
07.03.2016577.32 Кб15Интроверт.pdf
#
19.03.201545.04 Кб9Информационные.docx
#
08.07.20191.67 Mб1Иоанна Хмелевская -- (Nie)Boszczyk maz_POL.doc
#
19.03.201573.33 Кб5иппв.docx
#
07.03.20161.89 Mб17ИсследованиеОпераций.pdf
#
19.03.201554.77 Кб6Исторія модуль 2.docx
#
28.04.2019197.84 Кб1Историография. Шпоры.docx
#
23.12.2018332.8 Кб4история 2 - 2003.doc
#
19.03.2015199.17 Кб5история дипломатии том 2 ГЛАВА 7.doc
#
07.03.20162.04 Mб52История Медицины. Т.1..pdf