Output Summary 7 страница

Сформулируйте условия Куна-Таккера для данной задачи и установите требова­ния к функциям, при реализации которых выполняются указанные условия.

ЛИТЕРАТУРА

1. Bazaraa М., Shrali Н. and Shetty С. Nonlinear Programming Theory and Algo­rithms, 2nd ed., Wiley, New York, 1993. (Существует перевод первого издания: Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. — М.:Мир, 1982.)

2. Beightler С, Phillips D. and Wilde D. Foundations of Optimization, 2nd ed., Pren­tice Hall, N. J., 1979.

3. Rardin R. Optimization in Operations Research, Prentice Hall, N. J., 1998.

Литература, добавленная при переводе

1. Банди Б. Методы оптимизации. Вводный курс. — М.: Радио и связь, 1988.

2. Зангвилл У. И. Нелинейное программирование. — М.: Сов. радио, 1973.

3. Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. — М.: Наука, 1986.

4. Поляк Б. Т. Введение в оптимизацию. — М.: Наука, 1983.

5. Химмельблау Д. Прикладное нелинейное программирование. — М.: Мир, 1975.

ГЛАВА 21

АЛГОРИТМЫ НЕЛИНЕЙНОГО ПРО ГРАМ М И РО В АН ИЯ

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

21.1. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БЕЗ ОГРАНИЧЕНИЙ

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

21.1.1. Методы прямого поиска

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

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

В данном разделе рассматривается метод дихотомического поиска¹ и метод зо­лотого сечения. В обоих методах на интервале а<х<Ь ищется максимум функции f(x), имеющей на этом интервале только один максимум. (Такая функция называ­ется одновершинной.) Начальный интервал неопределенности состоит из исходного интервала I₀ = (а, Ь).

¹ В русскоязычной математической литературе этот метод обычно называется методом деле­ния отрезка пополам. — Прим. ред.

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

Пусть = (x_L, x_R) — интервал неопределенности на шаге I (на нулевом шаге x_L = а и x_R = b). Далее определяем х_х и х₂ такие, что

х, <х_х<х₂< х_и.

Следующий интервал неопределенности /, определяется после вычисления зна­чений f(x_x) и f(x₂). При этом возможны три варианта.

1. Если f(x_x) > f(x₂), то точка экстремума х' должна лежать между x_L и х_г: х, < х < х₂. Тогда положим x_R = х_г и получим новый интервал неопределен­ности/,= (х^ х₂) (рис. 21.1, а).

2. Если f(x_x) < f(x₂), то х_х < х" < x_R. Тогда x_L = х_х и 7, = (х_х, х_й) (см. рис. 21.1, б).

3. Если f(x_x) = f(x₂), то х_х<х < х₂. Положим x_L = х_хи х„ = х₂, тогда I, = (х_х, х₂).

а)

Рис. 21.1. Иллюстрации к прямым методам поиска б)

Поскольку здесь на каждом шаге гарантировано I_t < в результате сужается интервал, в котором находится точка максимума функции f(x). Алгоритм заканчи­вается на некотором шаге k, когда будет выполняться неравенство 1_к < Д, где Д — значение заранее заданной точности.

Различие между методами дихотомического поиска и золотого сечения заклю­чается только в способе вычисления точек х_х и х₂. Формулы для вычисления этих точек, представлены в следующей таблице.

Метод дихотомического поиска

Метод золотого сечения

*1 = (x_R + x_L- Д)/2

V5-1 _

X2 = (Xr+Xl + A)/2

^xi=x_L+—^—(x_x-x_L)

21.1. Алгоритмы решения задач без ограничений

В методе дихотомического поиска значения х, и х₂ симметричны относительно средней точки текущего интервала неопределенности. Это означает, что /, = 0,5(7,.,+ Д). Последовательное применение этого равенства доказывает, что длина конечного интервала неопределенности достигнет значения желаемой точности Д.

Идея метода золотого сечения не такая очевидная. Заметим, что в методе дихото­мического поиска вычисляются два значения f(xA и f(x₂), но после сравнения одно из них отбрасывается. В методе золотого сечения, то значение, которое отбрасывается в методе дихотомического поиска, сохраняется и используется на следующем шаге.

Введем параметр а такой, что 0 < а < 1. Пусть

х, = x_R - a(x_R - хJ, x₂ = x_L+afx_R-x_LJ.

Тогда интервал неопределенности /, на шаге i равен или (x_L, х₂) или (х,, x_R). Рас­смотрим ситуацию, когда l_l = (x_L, х₂). Здесь точка х, содержится в интервале /₍. На шаге i + 1 в качестве точки х₂ выбирается точка х, с предыдущего шага, т.е.

х₂(на шаге i + 1) = х,(на шаге г). Используя формулы для вычисления точек х, и х₂, приведенные выше, это равенст­во можно переписать как

^xl + «/"х/^{на шаге} U - хJ = x_R - a(x_R - xj или, еще раз применяя аналогичную формулу для х₂(на шаге i), в виде

x_L + а[x_L +а(x_R- xj - xj = x_R-a(x_R- xj. Из последнего равенства после несложных преобразований получим

«Vx_R - хJ + a(x_R - xj - (x_R - xj = 0. Поделив последнее выражение на (x_R - x_L), получим уравнение относительно а:

d + а-1 =0.

Это квадратное уравнение имеет корни а = (-1±л/5)/2. Поскольку по условию 0 < а < 1, мы выбираем положительный корень а = (-1 + -Jb)12 = 0,681.

Метод золотого сечения построен таким образом, что каждый последующий ин­тервал неопределенности меньше предыдущего в а раз, т.е. = al_t. По сравнению с методом дихотомического поиска этот метод сходится значительно быстрее (т.е. через меньшее число шагов получается интервал неопределенности заданной дли­ны Д, содержащий х*). Кроме того, метод золотого сечения требует в два раза мень­ше вычислений, чем метод дихотомического поиска, поскольку на каждом шаге используются вычисления, выполненные на предыдущем шаге.

Пример 21.1.1

Имеем следующую задачу.

[Зх, 0<х<2, Максимизировать /(х) = < _х 20

Гз⁺Т' ~^х~

Ясно, что максимум функции Дх) достигается в точке х = 2. В следующей таблице показаны вычисления для двух шагов методов дихотомического поиска и золотого сечения при Д = 0,1.

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

Метод дихотомического поиска	Метод золотого сечения
Шаг 1	Шаг 1
/о = (0, 3) = (xL, xR),	/о = (0, 3) = (xL, xR),
* =0,5(3+ 0-0,1) = 1,45, /(xi) = 4,35,	х, = 3 - 0,618(3 - 0) = 1,146, /(X,) = 3,438,
хг = 0,5(3 + 0 + 0,1) = 1,55, t\x2) = 4,65,	хг = 0 + 0,618(3 - 0) = 1,854, f(x2) = 5,562,
<\x2) > /(*) => xL = 1,45, h = (1,45, 3).	/(x2) > /(X!) => xL = 1,146, /, = (1,146, 3).
Шаг 2	Шаг 2
/, = (1,45, 3) = (xl,xr),	/i =(1,146, 3) = (xL, хд),
Xi = 0,5(3 + 1,45 - 0,1) = 2,175, /(Xi) = 5,942,	Хт = x2 на шаге 1 = 1,854, /(Xi) = 5,562,
x2 = 0,5(3 + 1,45 + 0,1) = 2,275, t\x2) = 5,908,	Хг = 1,146 + 0,618(3 - 1,146) = 2,292, t\x2) = 5,903,
fxi) > f(x2) => xR = 2,275, /, = (1,45, 2,275).	t\x2) > /(Xi) => xL = 1,854, /, = (1,854, 3).

Продолжая вычисления, получим с заданной точностью интервалы, содержащие точку максимума функции f(x).

На рис. 21.2 показан шаблон Excel ch21DichotomousGoldenSection.xls, предназначен­ный для поиска экстремумов функций описанными методами. Входными данными являются функция f(x) и константы a, b и Д. В данном примере функция f(x) зада­ется в ячейке ЕЗ с помощью формулы

=ЕСЛИ(СЗ<=2;3*СЗ;(-СЗ+20)/3) Отметим, что здесь ссылка СЗ играет роль переменной х. Константы а и Ь, введен­ные в ячейки В4 и D4, задают интервал поиска точки экстремума функции f(x). Значение предела точности Д вводится в ячейку ВЗ. Метод поиска задается путем ввода символа х в ячейку D5 (метод дихотомического поиска) или в ячейку F5 (метод золотого сечения).

На рис. 21.2 для сравнения показаны результаты вычислений в соответствии с обо­ими методами. Как видно на рисунке, метод золотого сечения потребовал всего 40 % числа итераций, выполненных методом дихотомического поиска.

УПРАЖНЕНИЯ 21.1.1

1. С помощью шаблона ch21DichotomousGoldenSection.xls решите задачу из примера 21.1.1, положив Д = 0,01. Сравните точность полученных результа­тов с данными, показанными на рис. 21.2.

2. Методом дихотомического поиска найдите максимумы следующих функций, полагая при этом, что Д = 0,05.

a) /(*)=•;—т, 2<х<4;

Ml

b) f(x) = х cosx, 0 < х < я;

c) f(x) = хsinnx, 1,5<х<2,5;

d) f(x) = -(х - З)², 2<х<4;

_,.. \Ах, 0<*<2, ^W [4-х, 2<*<4.

21.1. Алгоритмы решения задач без ограничений

в с d в

Dichotomoirs'Golden Section Seaich

Input data: Type f(C3) in E3, where C3 represents x m ■)

0000000 1 450000 1 450000 1 812500 1.812500 1 903125 1 948438 1 971094 1 982422 1.988086 1 988086 1 989502 1 989502 1 969856 1 969856 1 989944 1 989989 1 9899B9 1990000 1 990000 3OXO00 3OXO00 2 275000 2 275000 2093750 2 093750 2093750 2093750 2.093750 2.093750 2 090918 2 090918 2 090210 2 090210 2 090033 2 0900ЭЗ 2 090033 2 090011 2 090011 2090005 1 450000 2.175000 1 812500 1 99Э750 1 903125 1 948438 1 971094 1 982422 1 988086 1 990918 1 989502 1 990210 1 989856 1 990033 1 989944 1 9899B9 1 990011' 1 990000 1.990005^; 1 990003 1 550000 2.275000

1 912500

2 093750 2X3125 2 048438 2.071094 2 082422 2088086 2 090918 2 089502 2 090210 2089856 2 090033 2 089944 2089989 209X11 20900X 2090005 2 09X03

4 3500X

5 941667 5 4375X 5981250 5 709375 5 845313 5913281 5 947266 5 964258 5 972754 5968506 5.9706X 5969568 5.970099 5 969833 5 9699Б6 5 97X33 5 969999 5 97X16 5 9700X 4650X0 5 9X333 5 7Э75Х 5 968750 5 998958 5 983854 5 976X2 5 972526 5 970638 5 969694 5 970166 59699X 5 970048 5 969969 5 97X19 5.97X04 5 969996 5 9700X 5 969996 5 969999

ВС D ¹ E

Dichotomou&'Golden Section Seaich

F

Input data: Type t{C3) in E3. *ajatg СЗ гедч.-ents и in f v>

0 000000

1 145898 1 854102 1 854102 1 854102 1 854102 1957428 1 957428 1 996894 3O0OOX 30000X 30000X 2 562306 2 291796 2124612 2124612 2 0X753 2 0X753 1 145898

1 854102

2 291796 2124612 2 021286

1 957428 2021286 1.996894"

2 021286

1 854102

2 291796 2 562306 2 291796 2124612 2 021286 2060753 2.021286 2 036361 3 437694 5 562306 5 902735 5 958463 5 992905 5 872283 5 992905 5 990683 5992905 5 5623X 5.902735 5 812565 5 902735 5 958463 5 992905 5.979749 5 992905 5X7X0

Рис. 21.2. Реализация методов прямого поиска в Excel

Получите формулу для определения максимального числа итераций, выпол­няемых в методе дихотомического поиска при заданной величине Д и длине начального интервала неопределенности 1₀ = Ь- а.

21.1.2. Градиентный метод

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

Одним из градиентных методов является изложенный в разделе 20.1.2 метод Нью­тона-Рафсона, который ориентирован на решение систем уравнений. Здесь рассматри­вается еще один метод, который называется методом наискорейшего подъема².

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

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

Согласно градиентному методу вычисления завершаются при нахождении точ­ки, в которой градиент функции равен нулю. Но это лишь необходимое условие для того, чтобы в данной точке находился оптимум. Чтобы удостовериться, что найде­на именно точка оптимума, обычно привлекаются свойства вогнутости или выпук­лости функции f(x).

Рассмотрим задачу максимизации функции f(X). Пусть Х° — начальная точка, с которой начинается реализация метода, УДХ*) — градиент функции f в fc-й точке X*. Идея метода сводится к определению в данной точке направления р, вдоль ко­торого производная по направлению df/dp достигает своего максимума. Это проис­ходит в том случае, когда последовательные точки X* и Х*⁺¹ связаны соотношением

где г* — параметр, называемый длиной шага в точке X*.

Обычно значение параметра г выбирается из условия, чтобы в точке Х*^¹ наблюдалось максимальное увеличение значения целевой функции /. Другими словами, если функция Л(г) определяется соотношением

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

Описанная процедура заканчивается, когда две последовательные точки X* и X**¹ близки. Это эквивалентно тому, что rVf(X^k) = 0. Поскольку г Ф 0, последнее соотноше­ние означает, что в точке X* выполняется необходимое условие экстремума V/(X*) = 0.

Пример 21.1.2

Рассмотрим задачу максимизации функции

f(x_l,x₂) = 4х₁ + 6х₂ -2х] -2х_хх_г -2х₂. Функция Дх,, х₂) является квадратичной, и нам известно, что ее абсолютный мак-

Решим эту задачу методом наискорейшего подъема. На рис. 21.3 изображена после­довательность получаемых точек. Градиенты в двух последовательных итерацион­ных точках с необходимостью являются ортогональными (перпендикулярными) друг к другу. Для данной функции градиент вычисляется по формуле

■ k+l

X" + r^kVf(X^k),

h(r) = f(X^k + rVf(X^k)),

УДХ) = (4 - 4х, - 2x₂, 6 - 2x, - 4x₂). Пусть начальной точкой является Х° = (1, 1).

X = (l, l) + r(-2, 0) = (l-2r, 1).

21.1. Алгоритмы решения задач без ограничений

ДХ) = 4х, + 6х₂ - 1х_х^г-2х_хх₂ - 2х₂²

1 1 3 2 ^х1

2 2

Рис. 21.3. Последовательность точек, ведущая к оп­тимуму функции

Отсюда получаем выражение для функции 1г(г):

h(r) =Д1 - 2r, 1) = -2(1 - 2rf + 2(1 - 2г) + 4.

Оптимальная длина шага г, при которой функция h(r) достигает максимума, равна 1/4. Таким образом, мы нашли, что X¹ = (1/2, 1).

Итерация 2.

УДХ') = (0, 1).

Теперь следующая точка X² определяется выражением

Х = (1,1) + К0,1) = (|,1+/-).

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

h(r) = -2(1 + rf + 5(1 + г) + |.

Отсюда получаем г = 1/4 и X² = (1/2, 5/4). Итерация 3.

УДХ²) = (-1,0). Точка X³ определяется выражением

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

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

/i(r) = --(l-r)²+ -а-г)+ — 2 4 8

Отсюда получаем г = 1/4 и X = (3/8, 5/4). Итерация 4.

V/(X³) = (0, -).

Точка X⁴ определяется выражением

x=|VWa^nГ35+Г

,8 4J I. А) 1,8 4 Поэтому

*(0 = -|(5 ₊ r)^s₊g(5 ₊ r) ₊ g.

Отсюда имеем г = 1/4 и X⁴ = (3/8, 21/16). Итерация 5.

удх⁴) = (-1,0).

о

Точка X⁵ определяется выражением

³²¹V-i,oi=fc:^

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

^Х,8'l6j ' Л &") { 8 '16

Л(Н =--(3-г) +— (3-г) +-.

^v ' 32^{v ;} 64^v 128

Отсюда получаем г = 1/4 и X^й = (11/32, 21/16). Итерация 6.

V/(X⁵) = (0, -^).

Так как V/(X°) = 0, вычисления можно закончить. Получена приближенная точ­ка максимума X⁵ = (0,3437, 1,3125). Точный максимум достигается в точке Х* = (0,3333, 1,3333).

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

/(X) = 4,v, + 6х₂ - 2.x² - 2х,х, - 2х;.

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

2. Выполните не более пяти итераций метода наискорейшего спуска (подъема) для каждой из следующих задач. Во всех случаях положите Х° = О.

a) min/(X) = (*₂-*?)*+(1-х,)*.

b) max/(X) = сХ + Х^ГАХ, где

с = (1,3, 5),

		Р 2
-5	-3
-3	-2	• 0
	~2j

с) min/(X) = X[-х₂ + xf-х,х₂.

21.2. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ С ОГРАНИЧЕНИЯМИ

Общая задача нелинейного программирования с ограничениями записыва­ется в виде:

максимизировать (или минимизировать) z = /(X) при ограничениях

g(X) <0.

Условия неотрицательности переменных X > 0 составляют часть заданных ограни­чений общего вида. Предполагается также, что по крайней мере одна из функций f(X) или g(X) является нелинейной, и все функции непрерывно дифференцируемы.

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

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

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

21.2.1. Сепарабельное программирование

Функция /(ж,, х₂.....х_п) называется сепарабельной (разделимой), если она пред­ставляется в виде суммы п функций одной переменной /,(*,), f₂(x₂), /„(*„), т.е. ffx,, х₂,хJ = f,(x,) + f/xj +... + f/xj.

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

К примеру, линейная функция

h(х,, х_г,хJ = а,х, + арс_г +... + а.х,, (здесь a_t, i = 1, 2, п — константы) является сепарабельной. Функция же

h(x_l,x₂,x_i) = х\ +х, sin (лг₂ +х_}) + х₂е*'

таковой не является.

Некоторые нелинейные функции сепарабельными непосредственно не являют­ся, однако могут быть приведены к такому виду путем соответствующих подстано­вок. Рассмотрим, к примеру, задачу максимизации функции z = x_tx₂. Если ввести обозначение у = х₁х₂, то 1пу = \пх₁ + 1пх₂ и задача принимает следующий вид.

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

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

\щ = lnx, + lnx₂,

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

В случае, когда переменные x_i и х₂ принимают и нулевые значения (т.е. х,, х₂ > 0), можно поступить следующим образом. Пусть <5j и 8₂ — положитель­ные константы, введем новые переменные w_l = лс, + 8_Х и и>₂ = х₂ + 5₂. Эти переменные принимают только положительные значения. Теперь имеем

х_хх_г = w₁w₂ - S₂w₁ - 8jv₂ +

Пусть у = w_xw₂, тогда исходная задача эквивалентна следующей.

Максимизировать2 = у - S₂w₁ - 8jv₂ + S,S₂

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

lni/= lnu\ + lnu>₂, w_x>S_v w₂>S₂.

В этой задаче все функции сепарабельные.

Примерами других функций, которые в результате замены переменных приво­дятся к сепарабельным, могут служить е''*'- и х['-. В этих случаях для реализации

свойства сепарабельности следует применить соответствующий вариант описанной выше процедуры.

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

Функцию одной переменной f(x) можно аппроксимировать кусочно-линейной функцией с помощью методов частично-целочисленного программирования (глава 9). Пусть требуется аппроксимировать функцию f(x) на интервале [а, Ь]. Обозначим через а_к, k=l, 2, К, k-ю точку разбиения интервала [а, Ь], причем а = а, < а₂ <... < а_К = Ъ. Тогда функция f(x) аппроксимируется следующей кусочно-линейной функцией:

к к

/<■*) - *=Z<v».

*=1 *=i

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

где t_k — неотрицательный весовой коэффициент, связанный с fe-й точкой разбие­ния интервала. Весовые коэффициенты удовлетворяют условию

к

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

1. Если не больше двух весовых коэффициентов t_k имеют положительные значения.

2. Если значение t_k больше нуля, то положительным может оказаться лишь один из смежных весовых коэффициентов t_k+1 или t_k__x.

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

Максимизировать (минимизировать) z = (х>)

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

Эту задачу можно привести к задаче частично-целочисленного программирования следующим образом. Обозначим через К, число точек разбиения для i-й переменной х,, а через а- — k-ю точку разбиения. Пусть t. — весовой коэффициент, ассоции­руемый с k-й точкой разбиения для i-й переменной. Тогда эквивалентная задача частично-целочисленного программирования имеет вид

максимизировать (или минимизировать) г = (^а'* К

:=1 *=1

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

1=1 t=l

О<// <у', i=l, 2,...,п,

Q<t4 <у1^л+у¹, к = %Ъ.....АГ,- — I,

0<г*' <у*'~\

К,-\

*=i

yf =0 или 1, it = 1,2.....К,, 1 = 1,2,...,п.

В аппроксимирующей задаче переменными являются /' и у*.

Данное представление свидетельствует о том, что в принципе любая задача се­парабельного программирования может быть решена методами частично­

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

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

Для решения аппроксимирующей задачи можно использовать также обычный симплекс-метод (глава 3), дополненный правилом ограниченного ввода в базис. В этом случае игнорируются вспомогательные ограничения, содержащие у*. Со­гласно данному правилу в базисе может находиться не более двух положительных весовых коэффициентов if. Более того, два коэффициента if могут быть положи­тельными лишь тогда, когда они являются смежными. Таким образом, строгое ус­ловие оптимальности симплекс-метода только тогда используется для выбора пе­ременной /*, подлежащей введению в число базисных, когда она удовлетворяет

указанным выше требованиям. В противном случае анализ разностей (z* -с*) по­зволяет выбрать следующую переменную if, которая может быть сделана базис­ной. Процесс повторяется до тех пор, пока не будет выполнен критерий оптималь­ности или же установлена невозможность введения в базис новой переменной /* без

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

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