Output Summary 8 страница

Пример 21.2.1

Рассмотрим следующую задачу.

Максимизировать z = х, + х\

при ограничениях

Зх, + 2х; < 9, х_р х₂ > 0.

Точное оптимальное решение этой задачи находится непосредственной проверкой: х, =0, х₂ = 2,12 и г* = 20,25. Чтобы продемонстрировать использование метода ап­проксимации, рассмотрим отдельные функции

/,(*,) = *„

21.2. Алгоритмы решения задач с ограничениями

g;(x₂) = 2xl

Функции/,(*,) и gl(x_t) остаются в исходном виде, поскольку они уже являются ли­нейными. В этом случае х_х рассматривается как одна из переменных. Для функций /₂(дг₂) и g~{x,) полагаем, что количество точек разбиения равно четырем (К_г = 4). Так

как значение*,, не может превышать 3, отсюда следуют данные, приведенные ниже.

к	я'	fM)	**№)

Получаем

fM) = t^lJM)+t\L {4)+'1М^)⁺''Ш) =

= 0 х t\ +1 х /,^: +16 х t\ + 81 х t* = i; +16/₂ + 8 U*.

Аналогично

gf(x₂) = 2t;+Stl + \Stl Следовательно, аппроксимирующая задача принимает вид

максимизировать z = x,+1; +16/, + 8 У*

при ограничениях

Зх,+2/;+8/,³+18/₂⁴<9, t\+t;+tl+l' = \,;* >0, * = 1,2,3,4, х,>0.

Исходная симплекс-таблица (в которой осуществлена перестановка столбцов для получения начального решения) выглядит следующим образом.

Базис	Х1	t;	t}2		S1		Решение
z	-1	-1	-16	-81
S,
/:

Здесь 5, (> 0) — дополнительная (остаточная) переменная. (В этой задаче начальное решение является очевидным. В общем же случае для его получения могут понадо­биться искусственные переменные, см. раздел 3.4.)

Коэффициенты г-строки указывают на то, что в число базисных необходимо ввести переменную /⁴. Поскольку при этом переменная t\ уже входит в базисные в силу

Глава 21. Алгоритмы нелинейного программирования

правила ограниченного ввода в базис, она должна быть выведена из числа базисных перед тем, как базисной станет переменная /,⁴. Вместе с тем, согласно условию до­пустимости при введении в базисные переменной t* переменная s, должна выво­диться из базиса. Это значит, что t\ нельзя сделать базисной. Следующей подхо­дящей для введения в базисные является переменная t\. Снова при этом переменная t\ должна быть выведена из числа базисных. Условие допустимости на этот раз позволяет вывести из числа базисных переменную t\, что и требуется. Та­ким образом, получаем новую симплекс-таблицу.

Базис	Xi	'2	/23		S1	t\	Решение
z	-1			-65
S:		-6				-8
tl

Очевидно, что базисной следует сделать переменную t\. То, что переменная t\ уже

является базисной, не противоречит правилу ограниченного ввода в базис. В соот­ветствии с симплекс-методом переменная s, исключается из числа базисных. Полу­чаем следующую симплекс-таблицу.

Базис	Xi	'2	t\	A	S1	l\	Решение
z	37/2	-24			13/2	-36	45/2
t\	3/10	-6/10			1/10	-8/10	1/10
t\	-3/10	16/10			-1/10	18/10	9/10

Из этой таблицы следует, что в базис могут вводиться переменные t\ иг,². Пере­менная t\ не может быть базисной, поскольку не является смежной с переменными /₂ и /₂, которые уже находятся среди базисных. Далее, переменную г_г также нель­зя сделать базисной, поскольку t* нельзя исключить из числа базисных. Поэтому

процедура решения задачи на этом завершается, и полученное решение является наилучшим допустимым решением аппроксимирующей задачи.

Воспользуемся найденными значениями t\ = 9/10 и('= 1/10, чтобы выразить по­лученное решение через переменные jc, ид:₂. Получаем

х, = 0, х₂~ 2t³₂+3t⁴=2^j+3^j=2,l, z = 0 + 2,1⁴ = 22,5.

Полученное приближенное оптимальное значение для х_г (=2,1) мало отличается от истинного оптимального значения (= 2,12).

Сепарабельное выпуклое программирование. Задача выпуклого сепарабельного программирования возникает в том случае, когда функции #/(х,) являются вы­

21.2. Алгоритмы решения задач с ограничениями

пуклыми, обеспечивая, таким образом, выпуклость области допустимых решений. Кроме того, считаем, что функции f,(x_:) являются выпуклыми в задаче минимиза­ции и вогнутыми в задаче максимизации (см. табл. 20.2 в разделе 20.2.2). При этих условиях можно использовать следующий упрощенный метод аппроксимации.

Рассмотрим задачу минимизации. Пусть функция f_t(x) имеет такой вид, как по­казано на рис. 21.4. Обозначим точки разбиения для функции f^x) через x_t = а_м, k = 0,

1, К,. Пусть x_hi — величина изменения переменной x_t на интервале (а_к_,а_к), k = 1,

2, К,, ap_fc — тангенс угла наклона линейного сегмента на том же интервале.

Тогда

Рис. 21.4. Кусочно-линейная аппроксимация выпуклой функции

Здесь предполагается, что 0 < х_ы < а_ы - a„__u, k = 1, 2, К_г

Так как функция /Дх,) выпуклая, то р„ < р,_; <... < p_Kil. Это означает, что в задаче

минимизации при р < q большее влияние на значение целевой функции оказывает переменная х_р1, чем x_ql. Следовательно, переменная х_р1 всегда будет входить в реше­ние до того, как в него войдет x_ql При этом значения каждой переменной х_к1 должны быть ограничены сверху величиной (a_kl - a_k__hl).

Выпуклые функции ограничений glfa) аппроксимируются аналогичным обра­зом. Пусть p'_tl — тангенс угла наклона А-го линейного сегмента, соответствующего функции g!(x_{). Тогда функция g!(x,) аппроксимируется формулой

Следовательно, рассматриваемая задача принимает вид

■ I (К:

минимизировать z = ^ ^9и-\ + / {a_oi)

при ограничениях

V'-'

0<x_kl<a_ki- а_к__и, к=1, 2,...,#„1=1,2,

где

Глава 21. Алгоритмы нелинейного программирования

, _ g/K)-g/K-u)

Задача максимизации преобразуется аналогично. В этом случае р„ >p_2l >...>p_Kl,

откуда следует, что при р < q переменная х всегда будет входить в решение раньше х_д1 (см. упражнение 21.2.1.7).

Полученную задачу можно решить симплекс-методом, предназначенным для решения задач с ограниченными сверху переменными (раздел 7.3). При этом исче­зает необходимость в соблюдении правила ограниченного ввода в базис, поскольку выпуклость (вогнутость) функций гарантирует надлежащий выбор переменных.

Пример 21.2.2

Рассмотрим задачу

максимизировать z = х_х - х₂

при ограничениях

3x₁⁴+x₂<243, х₁+2х\<Ъ2, х_х > 2,1, jc₂>3,5.

Отдельными (сепарабельными) функциями этой задачи являются

у!(*.) = *.. Ь{^хг) = ~^хг< gl(x,) = 3x*, g\(x₂) = x₂,

gf(*.) = *.. g\{xi) = l£-Эти функции выпуклые, что и требуется в задачах минимизации.

Область допустимых значений переменных х_х и х₂, как следует из ограничений за­дачи, определяется неравенствами 0<x_t<3 и 0<;с₂<4. Разбиваем эти интервалы изменения переменных х, и х₂. Пусть А", = 3 и К₂ = 4 при а₀₁ = а₀₂ = 0. Значения тан­генсов углов наклона, соответствующих отдельным функциям рассматриваемой задачи, приведены в следующих таблицах.

Для i = 1 имеем

к	зил	U (вил) = вил	Ai	*i'(a*i) = 3a*i		S.2(a*i) = ati	P*.	ХкЛ
					—		—	—
								Хц
								*21
								X31

21.2. Алгоритмы решения задач с ограничениями 813

Для i = 2 имеем

к					Pi,			Хк2
			—		—		—	—
		-1	-1
		-2	-1					Х22
		-3	-1					*32
		-4	-1					*42

Теперь задача принимает следующий вид.

Минимизировать z ~ х_п + х₂₁ + х₃₁ - х_п - х₂₂ - х₃₂ - х₄₂ при ограничениях

Зх_и + 45х₂₁ + 195х₃₁ +х₁₂ +х₂₂ + х₃₂ +х₄₂< 243, х_п +х₂₁ +х₃₁ + 2х₁₂ + 6х₂₂ + Юх₃₂ + 14х₄₂ < 32, х_п +х₂₁ "Ьх₃₁ ^ 2,1,

■*12 + ^х22 + х}2 + *л2 ^ 3,5,

0<x_tl < 1, к= 1, 2, 3, 0<x_i2< 1,к= 1,2,3,4. С помощью программы TORA получено следующее оптимальное решение:

z = -0,52, х_и = x_l2 = 1, х₁₃ = 0,98, х₂₁ = х₂₂ = х₂₃ = 1, х₂₄ = 0,5. Отсюда получаем решение исходной задачи (х,, х₂) = (2,98, 3,5).

УПРАЖНЕНИЯ 21.2.1

1. Для следующей задачи постройте аппроксимирующую модель в виде задачи частично-целочисленного программирования.

Максимизировать z = е~^х' + х, + (х₂ +1)²

при ограничениях

х,² + х₂ < 3, х,, х₂>0.

2. Решите аппроксимирующую задачу из предыдущего упражнения, используя правило ограниченного ввода в базис. Затем найдите оптимальное решение исходной задачи.

3. Рассмотрите следующую задачу.

Максимизировать z = х,х₂х₃

при ограничениях

х,² + х, + х₃ < 4, х,, х₂, х₃ > 0.

Постройте аппроксимирующую задачу в виде задачи линейного программирова­ния с учетом дальнейшего использования правила ограниченного ввода в базис.

Глава 21. Алгоритмы нелинейного программирования

4. Покажите, каким образом приведенная ниже задача может быть приведена к сепарабельному виду.

Максимизировать г = х_хх₂ + х₃ + x_tx₃

при ограничениях

x_tx₂ + х_г + х_хх₃ < 10,

5. Покажите, каким образом следующую задачу можно преобразовать в задачу сепарабельного программирования.

Минимизировать z = е²"'*"*² + (х₃ - 2)²

при ограничениях

jc, + х₂ + х₃ < 6, x_itx₂, х₃>0.

6. Покажите, как следующую задачу можно преобразовать в задачу сепара­бельного программирования.

Максимизировать z = e^Vl + х²х₃ + х₄

при ограничениях

л;, + х₂х₃ + х₃< 10,

x_t не ограничена в знаке.

7. Покажите, что при реализации метода выпуклого сепарабельного програм­мирования оптимальное решение не содержит переменной х_к1 > 0, если пере­менная x_k__u не достигает своей верхней границы.

8. Решите представленную ниже задачу как задачу выпуклого сепарабельного программирования.

Минимизировать z = х,⁴ + 2х₂ + х]

при ограничениях

х² + х, + х₃ < 4, |-*,+х,|<0,

х₂ не ограничена в знаке.

9. Решите как задачу выпуклого сепарабельного программирования следую­щую задачу.

Минимизировать г = (л;, - 2)² + 4.(х₂ - б)² при ограничениях

6л:, + 3(х₂ + 1)²< 12, л:,, л:₂>0.

21.2. Алгоритмы решения задач с ограничениями

21.2.2. Квадратичное программирование

Задача квадратичного программирования имеет следующий вид.

Максимизировать (или минимизировать) г = СХ + X^TDX при ограничениях

АХ<Ь, Х>0,

где

X — (х,, х₂.....xJ^T,

О = (с,, с₂, с_ь), b = (b,,b₂,...,b_m)^T,

А =

D =

d,-d

Функция X DX, где D — симметрическая матрица, является квадратичной фор­мой (см. раздел А.З). Матрица D будет отрицательно определенной в задаче максими­зации и положительно определенной — в задаче минимизации. Это означает, что функция z является строго выпуклой по переменным X в задаче минимизации и строго вогнутой — в задаче максимизации. Ограничения в этой задаче предполага­ются линейными, что гарантирует выпуклость области допустимых решений.

Решение сформулированной задачи основано на использовании необходимых условий Куна-Таккера. Так как целевая функция z строго выпуклая (или вогну­тая) и область допустимых решений задачи является выпуклым множеством, эти условия (как показано в разделе 20.2.2) также достаточны для установления нали­чия глобального оптимума.

Задачу квадратичного программирования рассмотрим для ситуации, когда це­левая функция подлежит максимизации. Изменение формулировки задачи при минимизации целевой функции является тривиальным. Общая постановка задачи имеет следующий вид.

Максимизировать г = СХ + X^TDX

при ограничениях

G(X) =

<0.

Обозначим через X = (Я,, Я₂, Я_п)^Т и U = (//,, р.₂, р._п)^т множители Лагранжа, свя­занные с ограничениями АХ - b < 0 и -X < 0 соответственно. Применяя условия Куна-Таккера, получаем

X>0,U>0, Vz - (Х\ U^T)VG(X) = 0,

Глава 21. Алгоритмы нелинейного программирования

= 0, I = 1, 2,т,

PjXj = 0,j = l, 2,...,п, АХ<Ь, -Х<0.

Отсюда имеем

VG(X) =

Vz = С + 2X^TD,

Обозначим через S = b - АХ > 0 вектор дополнительных (остаточных) переменных. Тогда приведенные выше условия принимают следующий вид.

-2X^TD + Х^ТА - U^T = С, AX + S=b, UjXj = 0 = X_iS_i для всех i и j, X,U,X,S>0.

Так как D^T = D, в результате транспонирования первой системы уравнений получим

-2DX + А^ТХ - U = С^т. Следовательно, необходимые условия можно записать в виде

-2D А -I 0 АО 0 1

X U г_с>л

= 0 = X_iS_i для всех i и j, X, U, X, S > 0.

Все уравнения, за исключением p.x_j = 0 = ЯД, являются линейными относи­тельно переменных X, X, U и S. Следовательно, исходная задача сводится к поиску решения системы линейных уравнений, удовлетворяющему дополнительным ус­ловиям fipc_! = 0 = ЯД. Поскольку функция z строго вогнутая, а область допустимых решений представляет собой выпуклое множество, допустимое решение, удовле­творяющее всем этим условиям, должно быть единственным и оптимальным.

Решение рассматриваемой системы находится путем реализации этапа I двух-этапного метода (раздел 3.4.2). При этом единственным ограничением является не­обходимость удовлетворения условий ЯД = 0 = цх. Выполнение этого условия оз­начает, что если переменная Я₍ в базисном решении принимает положительное значение, то переменная S, не может быть базисной и принимать положительное значение. Аналогично переменные ц. и x_j не могут одновременно принимать поло­жительные значения. Это обстоятельство подобно правилу ограниченного ввода в базис, которое было использовано в разделе 21.2.1.

Этап1 завершается обращением в нуль всех искусственных переменных только в том случае, если исходная задача имеет непустое множество допустимых решений.

21.2. Алгоритмы решения задач с ограничениями

Пример 21.2.3

Рассмотрим следующую задачу.

Максимизировать г = 4х, + 6х, - 2х\ - 2х,х, - 2х\

при ограничениях

х, + 2х₂ < 2, х,,х₂>0.

Эту задачу можно записать в матричной форме

^r-2 -iy*

максимизировать г = (4, 6) ' +(х,,х₂)

-1

при ограничениях

(1,2)^|,₂, х„х₂>0.

Условия Куна-Таккера принимают следующий вид.

(4 2 1 2 4 2 1 2 О

-1 0 0^ 0-10 0 0 I,

х\
	=
		А
Ч51)

Начальная симплекс-таблица для этапа I строится путем введения искусственных переменных /?, и R₂. Имеем

Базис	*1	хг			Рг	Я,	Я2	S1	Решение
г				-1	-1
Я				-1
я2					-1
S1

Итерация 1. Поскольку //, = 0, вводимой в базис переменной может быть х,, при этом из числа базисных исключается переменная R_r Получаем следующую сим­плекс-таблицу.

Базис	Х1	хг	Хл		Рг	я.	Я2	S1	Решение
г			3/2	1/2	-1	-3/2
		1/2	1/4	-1/4		1/4
я2			3/2	1/2	-1	-1/2
S1		3/2	-1/4	1/4		-1/4

Глава 21. Алгоритмы нелинейного программирования

Итерация 2. Так как /и₂ = О, вводимой в базис переменной является х₂. В результате приходим к следующей таблице.

Базис	Х1	хг		А1	М2	Я,	я2	Si	Решение
г					-1	-1		-2
*1			1/3	-1/3		1/3		-1/3	2/3
Я1					-1			-2
х2			-1/6	1/6		-1/6		2/3	2/3
Итерация 3.	Так как	*i =	0, в число базисных можно ввести переменную Яг В ре-
зультате получаем симплекс-таблицу.
Базис	х,	хг	Л:			я.	Я2	Si	Решение
г						-1	-1
				-1/3	1/6	1/3	-1/6		1/3
					-1/2		1/2	-1
Хг				1/6	-1/12	-1/6	1/12	1/2	5/6

Последняя таблица дает оптимальное решение рассматриваемой на этапе I задачи. Так как г = О, полученное решение х_х = 1/3, х_г = 5/6 является допустимым. Опти­мальное значение z вычисляется подстановкой полученного решения в выражение для целевой функции исходной задачи и равняется 4,16.

Средство Excel Поиск решения можно использовать для решения задач квадратич­ного программирования. На рис. 21.5 показано решение задачи из данного примера (файл ch21SolverQuadraticPrograinrning.xls). Исходные данные для задачи представле­ны в таком же виде, как и в задачах линейного программирования (см. раз­дел 2.4.2). Основное отличие состоит в том, что целевая функция сейчас нелинейна. Поскольку в данном примере целевая функция имеет вид

z = 4х, + 6х₂ - Ix¹ ~ ^х,х₂ - 2x1,

в ячейку D5 записывается формула

=4*В10+6*С10-2*В1 (^2-2*810*С10-2*С10*2

Здесь в ячейках В10 и СЮ записаны значения x_t и х₂. Отметим, что ячейки В5:С5 не используются (в отличие от задач линейного программирования), поэтому мы ввели в них значения NL, показывающие, что ограничения нелинейны. Чтобы ука­зать, что переменные неотрицательны, надо или установить соответствующую оп­цию в диалоговом окне Параметры или задать нужные ограничения непосредствен­но в диалоговом окне Поиск решения.

21.2. Алгоритмы решения задач с ограничениями

D5

* =4*В10+6*С10-2*В10^Л2-2"В10*С10-2*С10^Л2

	А	В		el.	i	F
I	Quadratic Programming Model
	Input data:
		x1	x2			-
				Totals		Limits
	Objective	NL	NL	4 16P6R7
	Constraint			2,	<=
		>=0	>=0 |
8 '	Output results:
		x1	x2	z
	Solution	0 333333	0 833333	4 166667
	____ __

Поиск. ешения

хстансеить целевую ячейку |$D$5 Равной. минимальному значению ^г

г" минимальному значению изменяя ячейки

Рис. 21.5. Решение в Excel задачи примера 21.2.3

УПРАЖНЕНИЯ 21.2.2

1. Дана задача, в которой требуется

максимизировать z = 6х, + Ъх₂ - 4jc,x₂ - 2х² - Ъх\