Output Summary 9 страница

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

JC, + х₂< 1, 2х_х + Зх₂ < 4, x_t, х_г> 0.

Покажите, что г — строго вогнутая функция, и решите задачу, используя алгоритм квадратичного программирования.

2. Дана следующая задача.

Минимизировать z = 2х,² + 2х\ + Ъх] + 2х_хх₂ + 2х₂х_} +х,- Ъх₂ - 5х₃

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

X, + X, + X > 1,

1 2 d

Зх_х + 2х₂ + х_а<6, X) ~ 0»

Покажите, что функция г — строго выпуклая, и найдите решение задачи ме­тодом квадратичного программирования.

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

21.2.3. Геометрическое программирование

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

Методами геометрического программирования решаются нелинейные задачи, в которых как целевая функция, так и функции ограничений имеют следующий вид:

г = /(х) =

где

^uj^=cjfl*?> У' = Ь2,...,М

(=1

Предполагается, что здесь все с\ > 0, а число N является конечным. Показатели степени а,, по знаку не ограничены. Функция /(X) имеет вид полинома, если не учи­тывать того, что показатели степени a_tj могут принимать отрицательные значения. По этой причине, а также в связи с тем, что все коэффициенты с_; > 0, функция /(X) называется позиномом.

В этом разделе будут рассмотрены задачи геометрического программирования без ограничений. Исследование задач геометрического программирования с огра­ничениями выходит за рамки настоящей главы. Детальное рассмотрение излагае­мых здесь вопросов содержится в книге [2], глава 6.

Рассмотрим задачу минимизации позиномиальной функции /(X). Будем назы­вать эту задачу прямой. Предполагается, что переменные х, принимают строго по­ложительные значения, т.е. область х, < 0 недопустима. Далее будет показано, что требование х, * 0 является существенным при получении основных результатов.

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

ол, _;г1 ол_к, _{= 1}

Поскольку по предположению все х_к > 0, имеем

Г- = 0 = -Хв^, А =1.2,..., я.

Эх x,

■к у-1

Пусть z — минимальное значение функции z. Очевидно, что z > 0, так как z — по-зином, и все х_к > 0. Обозначим

Из определения следует, что у₁ > 0 и X^-i-^vj ⁼' ■ В^еличина y_t характеризует относи­тельный вклад у'-го слагаемого V' в оптимальное значение целевой функции z'. Не­обходимые условия экстремума теперь можно записать в следующем виде.

I>V,=n. к = \,2.....п.

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

Z-Уу ⁼ У) ^> 0 ^{для всех} J-

Эти уравнения, именуемые условиями ортогональности и нормировки, определя­ют единственное решение для у при условии, что все уравнения независимы и п + 1 = N. Задача усложняется при N > п + 1, так как в этом случае решение для I/. не является единственным. Ниже показано, что и в этом случае существует воз­можность однозначно определить у. для минимизации функции z.

Пусть y'j — элементы единственного решения представленной выше системы

уравнений. Тогда величины г* и х], i = 1, 2,п, определяются следующим образом. Рассмотрим величину

Поскольку z* = -г, то

П Пс')"

В последнем выражении учтено условие X"-i^av-^vj ⁼ ^ • Следовательно, значение г" можно вычислить, как только будут определены все у_г При известных у] и z мож­но определить U] = y'jZ ■ Значения х] находятся как решение системы уравнений

Рассмотренная процедура показывает, что исходная задача минимизации позино-ма z может быть сведена к решению системы линейных уравнений относительно у. При этом значения всех у' определяются из необходимых условий существования

минимума. Можно показать, что эти условия являются также и достаточными. До­казательство этого приводится в книге [2].

Фактически переменные y_t определяют двойственные переменные, соответст­вующие прямой задаче минимизации z. Чтобы установить эту зависимость, запи­шем целевую функцию прямой задачи в виде

Определим теперь функцию

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

Поскольку yj = 1 и y_j > О, в силу неравенства Коши^[1] имеем w<z.

Функция w с переменными у_х, у₂, y_N определяет задачу, двойственную к ис­ходной. Поскольку w является нижней границей значений z и рассматривается за­дача минимизации г, то, максимизируя функцию w, мы получим

w = max w = min z = z ■

У) *:

Это значит, что максимальное значение w (= w) на множестве допустимых значений г/, совпадает с минимальным значением z (= z") на множестве допустимых значений x_t.

Пример 21.2.4

В этом примере рассматривается задача, где N = п + 1, так что решение, получаемое из условий ортогональности и нормировки, является единственным. (Следующий пример иллюстрирует случай, когда N > п + 1.)

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

минимизировать z = 7х,х;' + Зх,х₃~^[2] + 5х~³х,х₃ + х,х,х₃.

Эту функцию можно записать в виде

z = 7х!х,~'х° + Зх?х\х,^[3] + 5х7³х\х\ + х\х\х\,

так что здесь

(с,, с₂, с₃, c_t) = (7, 3, 5, 1), 'а,, а,, а,₃ а₁₄ ^ (1 0-3 Г

а,. а„ а,, а,.

-1111 0-211

ya_3l я₃, а_п а_{м /}

Условия ортогональности и нормировки приводят к системе уравнений

(1		-3 Г	V		'о4
-1		1 1	-v:
	-2	1 1	л
ч [4]		1 К

Эта система имеет единственное решение

.1.1

Следовательно,

	>
		v

= 15,23.

21.2. Алгоритмы решения задач с ограничениями 823 Из уравнения U) = y)z' следует, что

7л,х,' =(/, = ^(15,23) = 7,615,

3.v,jt,² = {/, =-(15,23) = 2,538,

5л,³х_Л=(/₃=^(15.23) = 3,173,

x,x₂x, = =—(15.23) = 1,904. 8

Эта система имеет решение =1,316. х\ =1,21,.vj =1,2, которое является оптималь­ным решением прямой задачи.

Пример 21.2.5

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

минимизировать с = 5.v,.v,' + 2.v, '.v, + 5.v, +.vj¹. Условия ортогональности и нормировки приводят к системе уравнений

1-11 (У 1 10-1 \\ 11 1

V,

У}

\У*

о

Поскольку N > п + 1, эти уравнения не позволяют непосредственно определить ис­комые значения» Выражая у_и у₂ и у, через у₄, имеем

' 1	-1 п	f-v'l		' 0 1
-1	1 0	1 V, 1 ' -	=	у4
, 1	1 b			У-у,,

или

v, =-

I - 3 \-

Двойственную задачу можно записать в следующем виде.

Максимизировать iv =

-.0.5(1

0-5(1-vj

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

Максимизация w эквивалентна максимизации функции lnw, переход к которой уп­рощает вычисления. Получим

lnw = 0,5(1 - 3y₄){lnl0 - 1п(1 - Зу₄)} + 0,5(1 - у₄){1п4 - 1п(1 - у₄)} + у₄{1п5 - lny₄ + lnl - 1пу₄}.

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

+ln 5-{1+1пу₄}+1п 1-{1+1пу₄} = 0. После упрощений получаем

^ ^Г (1-3,у₄)?(1-у₄)?

у]

	(3 ^
In	2х102	+ 1п
	\)

или

_>/(1-Зу₄)³(1-,у₄)

у:

= 12,6,

откуда у* =0,16. Следовательно, yj=0,16, yj=0,42 и у,* = 0,26. Значение г* вычисляется по формуле

Следовательно,

, \0.26/ \0.42 /, _ч0.16

= _W=,-5-l ^ =9,661.

,0,26, 10,42 J l0,16J

с/₃ = 0,16х9,661 = l,546 = 5xi, U₄ =0,16x9,661 = 1,546 = х₂.

Отсюда имеем х* =0,309 и xj =0,647,

УПРАЖНЕНИЯ 21.2.3

1. Решите следующую задачу методом геометрического программирования. Минимизировать z = 2xj 'xj + х\х~₂ + 4x,² п ри x,, x₂ > 0.

2. Решите следующую задачу методом геометрического программирования. Минимизировать z = 5х_{х₂х] + х, ²х₃~' + 10х₂ + 2x_x'x₂xf при x_v х₂, х₃ > 0.

3. Решите следующую задачу методом геометрического программирования. Минимизировать z = 2х}х₂ + 8х,"³х₂ + Зх,х₂ при x_lt х₂ > 0.

4. Решите следующую задачу методом геометрического программирования. Минимизировать z = 2х]х~₂ + 4х,"²х₂ + х,х, при х,, х₂ > 0.

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

21.2.4. Стохастическое программирование

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

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

Максимизировать z = 'Y_Jc_jx_j

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

^|Х^аЛ - ^| - ' ~^ai' 1 = 1.2, Xj>0 для всех j.

Название "вероятностные ограничения" обусловлено тем, что каждое ограни­чение задачи должно выполняться с вероятностью не меньшей, чем 1 - а,, О < a_t < 1. Предполагается, что все коэффициенты a_:j и Ь₁ являются случайными величинами. Далее рассматриваются три варианта. Первые два соответствуют предположениям о том, что только или а_(у, или 6 являются случайными величинами, а третий объе­диняет эти два случая. Во всех трех ситуациях предполагается, что параметры яв­ляются нормально распределенными случайными величинами с известными мате­матическими ожиданиями и дисперсиями.

Ситуация 1. Предполагается, что все а_ц являются нормально распределенными случайными величинами с математическими ожиданиями М{а₍.} и дисперсиями D{a_:j}. Также известны ковариации covfa^a..} случайных величин а_; и а...

Рассмотрим i-e ограничение задачи

и введем обозначение

рЩа,_Л<Ь,\>1-_а!

h_i=Y_ja,_jx_j.

Случайная величина Л. имеет нормальное распределение с математическим ожида­нием M{h_l} = ^_j"._=iM{a_ij}x_j и дисперсией D{h} = X^rD,X, где Х = (x_v х₂,...,х_п)^т,

I), = /-я матрица ковариации

Теперь имеем 'D{a_n} ■■■ cov{a_n,a_hlY cov{a,„,a_a} ••• D{a_ll)

\h-M(k) h-M(h)\

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

h-M(h)

где ' - — стандартная нормально распределенная случайная величина с ну-

левым математическим ожиданием и единичной дисперсией. Это означает, что

P\h <!>,} = Ф

b,-M(h,)

где через Ф обозначена функция распределения стандартного нормального распре­деления.

Пусть К_а — значение стандартной нормально распределенной случайной вели­чины, определяемое из уравнения

Ф(К„.) =!-«,

В этом случае неравенство P{h. < b) > 1 - a_t выполняется тогда и только тогда, когда

b,-M{h,)

1т

Это приводит к детерминированному нелинейному ограничению, которое эквива­лентно исходному вероятностному

В частности, если а_ц — независимые нормально распределенные случайные вели­чины, тогда cov{a_v,a = 0, и последнее неравенство принимает вид

i-i \ г'

Данное ограничение можно записать в виде ограничений задачи сепарабельного программирования (раздел 21.2.1), для чего используется замена переменных

>' = ^/; К Y, ^{лля всех} '•

Таким образом, исходное ограничение эквивалентно неравенству

£м{_а,,}.г_{/ +} к„у,<г>,

и уравнению

el

Ситуация 2. Здесь предполагается, что только b_t является нормально распреде­ленной случайной величиной с математическим ожиданием М{Ь) и дисперсией D{b). Анализ этой ситуации проводится аналогично предыдущей. Рассмотрим сто­хастическое ограничение

p\b_l>Y_da_ilx\>a,.

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

Как и в первом случае, имеем

Y_ja_iix_j-M{b_i)

>а..

Это ограничение выполнимо лишь при выполнении неравенства

4т

■<к„.

Итак, исходное вероятностное ограничение эквивалентно детерминированному линейному

у=1

Ситуация 3. Теперь предположим, что все параметры a_tj и b_t являются нормаль­но распределенными случайными величинами. Перепишем ограничение

в виде

Так как все a_tj и b_t распределены по нормальному закону, в соответствии с из­вестными результатами математической статистики величина ^"^fyXj-b_f также

имеет нормальное распределение. Отсюда следует, что данный вариант подобен ва­рианту 1 и может быть рассмотрен аналогичным образом.

Пример 21.2.6

Рассмотрим задачу с вероятностными ограничениями

максимизировать г = 5х, + 6х₂ + Зх,

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

Р{а_их, + а₁₂х₂ + ацх_} < 8} > 0,95,

Р{5х, +х₂ + 6х_ъ<Ь₂\ > 0,10,

причем все х_;>0. Пусть — независимые нормально распределенные случайные величины со следующими значениями математических ожиданий и дисперсий

M{a_n} = l,M{a_l2} = 3,M{aJ = 9,

D{a_u) = 25, D{aJ = 16, D{aJ = 4.

Пусть параметр Ь_г является нормально распределенной случайной величиной с ма­тематическим ожиданием 7 и дисперсией 9.

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

По таблице функции распределения стандартного нормального закона (приложение В) находим

К_щ=К_от~ 1,645, tf_Qj =*„.,„ = 1,285. Первое ограничение задачи эквивалентно детерминированному неравенству

х, + Зх, + 9х₃ +1,645_N/25x₁² + 16x;+4x; < 8,

а второе ограничение — неравенству

5х, +х_г + 6х₃< 7 + 1,285 х 3 = 10,855.

Если положить

у² = 25 х² + 16х, + 4х₃, исходная задача принимает следующий вид:

максимизировать г = 5х, + 6х₂ + Зх₃

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

х, + Зх₂ + 9х₃ + 1,645у < 8, 25х,² + 16х;+4х₃²-у² =0, 5х, + х₂ + 6х₃< 10,855,

*1> ^х2' ^х3'У~⁰'

и может быть решена методами сепарабельного программирования.

На рис. 21.6 показано решение рассматриваемой задачи стохастического програм­мирования в Excel (файл ch21SolverStochasticProgramming.xls). В данном случае нели­нейной является только левая часть второго ограничения, которая вводится в ячейку F7 в виде формулы

=25 *В 12^Л2+16С12^A2+4*D 12^Л2-Е 12^л2

УПРАЖНЕНИЯ 21.2.4

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

Максимизировать z = х_х + 2x₂ + 5д:₃

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

P{a,x, + Зх₂ + а₃х₃ < 10} > 0,9,

Р{7х_г + 5х₂ + х₃<Ь₂}>0,1, х_1г х₂, х₃ > 0.

Пусть а, и а₃ являются независимыми нормально распределенными случай­ными величинами с математическими ожиданиями М{а₁) = 2 и М[а₃} = 5 и дисперсиями D{a_l) = 9 и D{a₃) = 16. Предполагается также, что Ь₂ — нор­мально распределенная случайная величина с математическим ожиданием 15 и дисперсией 25.

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

	F7		=25*B 12Л2+16*C 12A2+4*D12Л2-Е12Л2
	А	В	С	D	E	___F J G	H
		Stochastic Programming Model
	Input data:
		x1	x2	x3	У
						Totals		Limits
	Objective					4.66129 i
	Constraint 1				1.646	2.529435	<=
	Constraint 2	NL	NL	NL	NL	7.4E-11	=
	Constraint 3					о		10.856
		>=0			>=0
	Output results:
		x1	x2	x3	У	z
	Solution	' 7И9ч			1 37096»	4 66129

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

Установить целевую ячейку: |$F$5 ]4J Равной: максимальному значению <~ значению' |о~

минимальному значению

Изменяя ячейки:

|$В$12:$Е$12 Ограничения:

Предположить |

$В$12:$Е$12 >= О $F$6 <= $Н$6 $F$7 = JH$7 $Н8 <= $Н$в

~2

J

Добавить

Изменить

Удалить

| Вь ипнить ] Закрыть

Параметрь-

Восстановить

Справка

Рис. 21.6. Решение задачи стохастического программирования в Excel 2. Дана следующая задача стохастического программирования.

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

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

PJxf + а₂х\ + а_ЗЛ/х7 < 10} > 0,9,

х_г, х₂, х₃ > 0.

Пусть параметры а₂ и а₃ — независимые нормально распределенные случай­ные величины с математическими ожиданиями 5 и 2 и дисперсиями 16 и 25 соответственно. Преобразуйте данную задачу в детерминированную задачу сепарабельного программирования.

21.2.5. Метод линейных комбинаций

Этот метод ориентирован на решение задач, в которых все ограничения являют­ся линейными:

максимизировать z = f (X)

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

АХ<Ь,Х>0.

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

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

Пусть X* — допустимая точка, полученная на fe-й итерации. Разложим целе­вую функцию /(X) в окрестности точки X* в ряд Тейлора. В результате получим

/(X)«/XX*) + V/(X*)(X - X*) = /(X*) - V/XX*)X* + V/XX*)X. Нам необходимо определить допустимую точку X = X", в которой достигается мак­симум функции /XX) при выполнении (линейных) ограничений задачи. Так как /XX) - V/XX)Х — постоянное слагаемое, задача определения X сводится к реше­нию следующей задачи линейного программирования:

максимизировать w_k(X) = Vf(X^k)X

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

АХ<Ь,Х>0.

Так как целевая функция w_k определяется градиентом функции /XX) в точке X*, улучшение имеющегося решения может быть обеспечено лишь тогда, когда шДХ") > шДХ*). Из разложения Тейлора следует, что выполнение этого условия не гарантирует, что /XX*) > /(X*), так как X* не обязательно находится в малой окрестности точки X*. Однако при выполнении условия w_t(X") > w_k(X.^k) на от­резке (X*, X") должна существовать такая точка X**¹, что /XX**¹) > /XX*). Следо­вательно, задача сводится к определению такой точки X**¹. Найдем эту точку следующим образом:

X^k" = (1 - r)X^k + гХ* = Х^к + г(Х* - Х^к), 0 < г < 1.

Отсюда следует, что точка X**¹ является линейной комбинацией точек X* и X*. Так как X* и X* — точки выпуклой области допустимых решений, точка X**¹ также яв­ляется допустимой. Если сравнить эту процедуру с методом наискорейшего подъе­ма (подраздел 21.1.2), параметр г можно рассматривать как длину шага.

Точка X**¹ определяется из условия максимума функции /XX). Так как X*⁴¹ зави­сит лишь от переменной г, то Х*^и определяется путем максимизации функции

h(r) = f[X^k + r(X* - X^k)].

Процедура повторяется до тех пор, пока на fe-й итерации не будет выполнено условие м>_А(Х*) < шДХ*). В этой точке дальнейшее улучшение существующего ре­шения невозможно, процесс вычислений завершается, точка X* считается наи­лучшим решением.

Задачи линейного программирования, которые решаются на каждой итерации описанной процедуры, отличаются друг от друга лишь коэффициентами целевой функции. Поэтому для повышения эффективности вычислений можно использо­вать методы анализа чувствительности, рассмотренные в разделе 4.5.

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

Пример 21.2.7

Рассмотрим задачу квадратичного программирования из примера 21.2.3.

Максимизировать z = 4дг, + бх, - 2х^г - 2х_хх₂ - 2х\

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

х, + 2дг, < 2,

лг,,дг₂>0.

Пусть Х° = (1/2, 1/2) — начальная точка, которая является допустимой для рас­сматриваемой задачи. Имеем

удх) = (4 - 4х, - 2х₂, 6 - 2дг, - 4х₂).

Итерация 1.

удх°) = (i,3).

Соответствующая задача линейного программирования сводится к максимизации функции и>, =х, + Здг₂ с учетом ограничений исходной задачи. Ее оптимальным ре­шением есть точка X* = (0, 1). Значения функции и>, в точках Х° и X* равны 2 и 3 со­ответственно. Следовательно, новая точка ищется в виде

х'=|!.-| ₊ г

Л 2

(«НИ

Максимизация функции

\-г 1+г

2 ' 2

•w-4₂₂

дает г = 1. Таким образом, X¹ = (0, 1) и ДХ¹) = 4. Итерация 2.

удх¹) = (2, 2).

Целевой функцией новой задачи линейного программирования является w₂ = 2х_х + 2х_г. Оптимальное решение этой задачи — X = (2, 0). Поскольку значения и>₂ в точках X¹ и X* равны 2 и 4, следует найти новую точку. Рассматриваем точку

X² = (0, 1) + г[(2, 0) - (0, 1)] = (2г, 1 - г).

Максимизация функции

А(г) =Д2г, 1 - г)

дает г = 1/6. Таким образом, X² = (1/3, 5/6), при этом ДХ²) = 4,16. Итерация 3.

удх²) = (1,2).

Здесь целевая функция имеет вид w₃ = дг, + 2х₂. Оптимальным решением задачи линей­ного программирования будут альтернативные точки X* = (0,1) и X* = (2, 0). Значение и>₃ в обоих случаях совпадает со значением w₃ в точке X². Следовательно, улучшить имею­щееся решение невозможно. Получено приближенное оптимальное решение задачи: X² = (1/3, 5/6) сДХ²) = 4,16. В данном случае оно совпадает с точным оптимумом.

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

УПРАЖНЕНИЕ 21.2.5

1. Решите следующую задачу методом линейных комбинаций.

Минимизировать /(X) = х\ + х\ -Зхх,

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

Зле, + х₂ < 3, 5х, - Зх₂ < 5, x_lt х₂ > 0.

21.2.6. Алгоритм последовательной безусловной максимизации

В этом разделе приводится описание градиентного метода более общего вида. Предполагается, что целевая функция /(X) является вогнутой, а каждая функция ограничений g/X) — выпуклой. Кроме того, допустимая область задачи должна содержать внутренние точки. Это исключает как явное, так и неявное использова­ние ограничений в виде равенств.

Алгоритм последовательной безусловной максимизации основан на преобразо­вании исходной задачи с ограничениями в эквивалентную задачу без ограничений. Процедура в некоторой степени подобна применению метода множителей Лагран­жа. Преобразованная задача затем может быть решена методом наискорейшего подъема (раздел 21.1.2).

Введем новую целевую функцию

p(x,,)=/(x)₊/(x-7i_FT-I-^L.

Ui*,(X) >i*J

где t — неотрицательный параметр. Наличие второй суммы обусловлено учетом тре­бований неотрицательности переменных исходной задачи, которые следует записать в виде -x_t<0 для их согласования с остальными ограничениями вида g,(X)<0. По­скольку функция g/X) является выпуклой, будет вогнутой. Отсюда следует, что р(К, t) является вогнутой функцией от переменных X. Следовательно, функция р(Х, t) имеет единственный максимум. Поэтому решение исходной оптимизационной задачи с ограничениями эквивалентно максимизации функции р(Х, t).