автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Некоторые специальные задачи математического программирования и их редукция к выпукло-вогнутым и частично целочисленным задачам

РТ5 Ой

2 3 (Ш В95

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО ВЫСШЕМУ ОБРАЗОВАНИЮ ИРКУТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

Данзангийн Ганхуяг

НЕКОТОРЫЕ СПЕЦИАЛЬНЫЕ ЗАДАЧИ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ И ИХ РЕДУКЦИЯ К ВЫПУКЛО-ВОГНУТЫМ И ЧАСТИЧНО ЦЕЛОЧИСЛЕННЫМ

ЗАДАЧАМ

05.13.16. - Применение вычислительной техники, математического моделирования и математических; методов в научных исследованиях

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Иркутск -1995

Работа выполнена в лаборатории "Исследования операций" Сибирского энергетического института СО РАН.

Научный руководитель: доктор физико-математических наук, Академик РАЕН В.П. Булатов

Официальные оппоненты: доктор физико-математических наук,

профессор В.М. Солсдов

Кандидат физико-математических наук, доцент A.B. Аргучинцев

Ведущая организация: Институт математики и механики УрО РАН

Защита состоится " /С " 1995 г. в /С

часов на заседании диссертационного совета Д 063.32.04 по защитам дисс ертации на соискание ученой степени доктора физико-математических наук в Иркутском государственном университете (664003, бульвар Гагарина 20,1-й корпус ИГУ).

С диссертацией можно ознакомиться в Научной библиотеке Иркутского государственного университета (бульвар Гагарина, 24).

Автореферат разослан " ü " . ) 1995 года.

Ученый секретарь спец. совета, /

к.ф.-м.н., доцент Н.Б. Бельтюков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. При проведении различных теоретических и инженерно - технических работ мы часто сталкиваемся с проблемой решения экстремальных задач. Одним из основных разделов теории экстремальных задач являются методы оптимизации. Такие направления теории оптимизации, как линейное программирование (ЛП), выпуклое программирование (ВП), и дискретное (целочисленное) программирование как теоретически, так и алгоритмически разработаны достаточно давно и имеется обширный набор научных трудов, посвященных этим задачам. Несмотря на это, в настоящее время интенсивно развиваются два направления математического программирования:

1. Развитие и модификация уже разработанных методов и алгоритмов.

2. Создание новых алгоритмов и направлений.

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

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

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

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

а), имеет место выпуклость (в ограниченном и часто нетрадиционном смысле);

б), глобальный оптимум принадлежит подмножеству граничных точек допустимого множества.

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

1). максимизация выпуклых функций при линейных или выпуклых ограничениях (выпуклая максимизация);

2). выпуклая минимизация на пересечении выпуклых и вогнутых множеств (выпукло- вогнутое пограммирование);

3). глобальная оптимизация функций, представимых в виде разности двух выпуклых функций (с!.с. - программирование).

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

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

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

пуклого анализа, и математического программирования.

Научная новизна и практическая ценность результатов, полученных автором, состоит в следующем:

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

- определен класс задач математического программирования с ограничениями в форме равенств и неравенств и получена его редукция к выпукло-вогнутым задачам,

- исследован класс полных квадратичных задач с неопределенной квадратичной матрицей квадратичных форм,

- описаны алгоритмы поиска как локального, так и глобального решений для выпукло-вогнутых задач,

- предложена модификация метода отсечения в Еп,

- Исследована связь модификации с задачами целочисленного, частично- целочисленного, сепарабельного программирований и с задачей с фиксированными затратами,

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

Апробация работы. Результаты работы докладывались на конференции "Методы оптимизации и их приложения"(Иркутск, 1992), на научных семинарах ИМ АН МНР и СЭИ.

Структура работы. Диссертация состоит из введения, трех глав, заключения и списка литературы, содержащего 39 наименовании. Работа изложена на 61 страницах.

Содержание работы

Введение содержит краткое изложение полученных результатов.

В параграфе 1 первой главы рассмотрена задача:

min <р(у) (1)

Дх,у) = 0, iC fi.CE', yCRyCEm (2)

где функции <р : Ет —> Е1, f : RxxRy С Е*хЕп Е1^ непрерывные, вещественные функции и кроме того функция f(x,y) - непрерывно дифференцируема на открытом множестве RxxRy. Обозначиим через

Ly = {yQRf{x,y) = 0,3s С Rx ф 0}

Теорема, дающая условия глобальной разрешимости уравнения (2) относительно х доказана Никайдо(Никайдо," Выпуклые структуры и математическая экономика",1972) Следующая теорема дает условие выпуклости функции х(у).

Теорема 1. Пусть функция f{x,y) выпуклая и непрерывно дифференцируема на ДгхДу. Предположим что, уравнение f(x, у) = 0 имеет единственное непрерывно дифференцируемое решение х = х{у), Vy С Lv и матрица Якоби Vr/(x, у) имеет неотрицательную обратную матрицу для любого (х,у) С RxxRy, т.е (Va/(z,y))-1 > 0. Тогда функция х = х(у) выпукла на Ly.

Если множество Rx определено неравенством х(у) < с, с С Еп и <р(у)- выпуклая функция, тогда в силу теоремы 1 задачу (1) — (2) можно представить в виде:

min{<p(y) : х(у) < с, у С Щ}

Если множество Ry- выпуклое, то последняя задача -задача выпуклого программирования. Если функция <р(х,у) явно зависит от х, выпукла по совокупности переменных (г, у) и монотонно по х = х{у) и выполняются условия теоремы 1, тогда функция (р = ip(x(y), у) очевидно по у С Ry выпукла и в свою очередь рассматриваемая проблема (1) — (2) тоже выпукла. Если множество Rx определено неравенствам d. < г (у) < с, где d, с С В" то задача (1) - (2) при предположениях, приведенных выше, становится задачей многоэкстремальной.

Рассмотрим некоторые другие подходы редуцирования общих задач математического программирования к выпукло-вогнутым задачам. Для этого рассмотрим задачу:

min f(x) (3)

т С R = {х С Е* : hj(x) < 0, j = l,...,m} (4)

где f : Ея Е1 м hj : Еч Е1, j = I,... ,тп- скалярные непрерывные функции векторного аргумента, а R- некоторое подмножество Еп, R С Е\

Определение-1. Если хотя бы одна из функции / : -» Е1 и hj : Е" -+ Е1, j = 1,...,m- вогнута, когда другие функции выпуклые, задачу (3) - (4) назовем задачей выпукло-вогнутого программирования.

Предположим теперь, что нам удалось представить данную задачу в виде:

min /(s)=(/i(*)+/2(*))

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

iCR = {ta": hj(x) = h}(x) 4- h){x) < 0, j = 1,... ,m}

где fi : En —► E\ Щ : En E1, j — 1,... ,m- вьшуклые и /2 : En —► El, hj : En E1, j = 1,... ,m- вогнутые функции. Тогда, вводя дополнительные переменные ¿о» ¿ь • • •. задачу (3) - (4) представим в следующем виде:

min ip(x) = fi (х) + f0 (5)

при условиях:

-/з(*) + «о<0, (6)

h)-tj = 0, з = 1,...,т, (7)

h* + tj<0, j= 1,...,т (8)

Очевидно, что задача (5)-(8) есть задача выпукло-вогнутого программирования. Рассмотрим теперь задачу математического программирования с ограничениями в форме равенств: Найти

min f(x) (9)

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

ф) =0, t= l,...,fc (10)

Здесь, не уменьшая общности, считаем что, функции / : Еп —► Е1, д,- : Ел —► Е1, i= 1,... ,к -выпуклые. Тогда, как доказано В.П.Булатовым,

при достаточно большом N > О, задача (9) — (10) эквивалентна следующей:

к

min <р{х) = /(¡г) + N 9i( »=1

при условии

9i(x)> 0, » = 1,— ,fc

Если функции gi : ЕЛ —► Е1,» = 1 ,...,fc- выпукло-вогнутые и пред-ставимы в виде: gi(x) = д}{х) + gf,i - 1,... где д} : Ел Е1 -выпуклые, gf : Еп —► Е1, i = 1 ,...,fc -вогнутые, то введением дополнительных переменных з;,» = 1,... ограничения задачи можно представить в следующем виде:

9i(«) - * = 0, » = 1,...,*,

-9?(х) ~ - °>

что и показывает возможности редуцирования задачи с ограничениями в виде равенств к выпукло-вогнутым задачам математического программирования.

Во втором параграфе описана вычислительная схема поиска локального минимума выпукло-вогнутых задач и обоснована сходимость процедуры решения. Рассматривается задача:

min /(х) (11)

при условиях:

я(*) = 0,| = 1,...,1, (12)

hj(x)< 0,j = l,...,m, (13)

а <х <ß (14)

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

min хп+х

<р(х) - жп+1 < 0, hj{x) <0, j = l,...,m,

Alx < bi, i = 1,...,/,

a<x<ß

Здесь <p{x) = f(x) + N L;=1ff;(z)> А'(ж) = -Vgi(x),i = 1,...,/, и b¡ = Vgi(x) — Vg¡{x) x, i = 1,...,J, где г- некоторая допустимая точка этой задачи.

1. Найти нижние ограничения для дополнительных переменных, если в задаче присутствуют выпукло-вогнутые ограничения. Для этого последовательно решается задача выпуклого программирования следующего вида:

min t¡ 6¡{x) - U < О,

X < X < X

где £ -индекс ¿-ой выпукло-вогнутой функции-ограничении задачи. Решение этой задачи является нижним пределом изменения для дополнительного переменного í¿.

2. Вычислить верхние пределы изменения для дополнительных переменных. Строится n-мерный симплекс Sn, содержащий допустимую область задачи:

Sn = {х С Еп : х = ¿ a¡xj, ¿ ctj = 1, a¡ < 0} ;'=0 j=0

где x°,xl,... ,xn- вершины симплекса. Вычисляется максимальное значение данного г-ого выпукло-вогнутого ограничения на вершинах симплекса и присваивается это значение как верхний предель изменения к i -ой переменной.

3. Найти допустимую точку 2Г. При этом решается следующая задача:

3.1. min f(x)

х С В С Еп

где функция / : Еп —► Е1 -выпуклая и подмножество В С Еп образуется выпуклыми ограничениями задачи (11) — (14). Пусть х°- решение этой задачи.

1С

3.2. Определяем индексное множество вогнутых ограничений I =

3.3. Вычисляем д{х°) = maxic/£fi(®°)- Если д(х°) < 0 то -решение задачи (11) — (14). В противном случае решаем задачу:

3.4. min Vg(5°)'x

х С В

Пусть х -решение последней задачи. Проверяем д(х) < 0. Если это условие выполняется, то г- допустимая точка для задачи (11) - (14), в противном случае = х и переходим к пункту 3.4. После этого, для решения задачи (11) - (14) мы применяем метод опорного конуса.

Параграф 1.3 посвящен исследованию задачи полного неопределенного квадратичного программирования. Рассматривается задача:

min f(x) = xCx + b'x (15)

gi{x) = xD'x + dfx + pl = 0, г = 1,... ,k, (16)

hj{x) = xQjx 4- q>'x + tj < 0, j = 1,... ,m (17)

где C,D\i = 1 Q' ,j = 1,..., пг-симметричные, вещественные

матрицы порядка (пхп), b,d?,i — 1, q>,j = 1 ,...,m- п мерные

векторы, р\ i = 1,..., к, V, j — 1,..., m -скалярные величины. Используя представление J — ü'CU вещественной сииметрической матрицы С, где U -ортонормированная матрица, т.е U' = С/-1, и J- диагональная матрица, елементы главной диагонали которой есть собственные числа матрицы С и делая замену переменных х = U у выражение (15) представим в виде: f{Uy) = f\(y) + /2(у). Делая, обратную замену переменных у = U'x мы получаем представление функции f(x) в виде суммы выпуклых и вогнутых функции, т.е.

/(*) = Ми'х) + MU'x) = /,(«) + f2(x)

Повторяя эту же процедуру для квадратичных функции в-(16) — (17) мы также сможем представить их в виде суммы выпуклых и вогнутых функции. Применяя подходы , описанные в предыдущих пунктах, задачу (15)—(17) мы редуцируем к задаче выпукло-вогнутого программирования.

В параграфе 1.4 описал метод поиска глобального решения выпукло-вогнутых задач. Рассматривается задача:

min f(x) (18)

х С Д, hi{x) =0, » = 1,...,г (19)

где / : Еп —» Е1 -выпуклая, Л,- : Еп -> Б1, i = 1,...,г - сильновыпуклые функции и множество R С Еп -выпуклое. Идея поиска глобального минимума задачи собтоит в последовательном отсечении точек локального минимума, т.е строится последовательность усеченных множеств {Д*}, таких что, Rk+1 С Д\ причем Jk- точка локального минимума f(x) на Rk не принадлежит Rk+1 и f(x) > f(xk),Vx С Rk\Rk+l. Пусть на к- ом шаге построена последовательность ..., хк- локальных минимумов и определено множество

Rk = {г : х С Д, а> х < ßjt j = 1 1}

причем, отсекающее полупространство а1 х < ßj,j = 1,...,к — 1 не содержит точки х3 -локального минимума функции f(x) на Д;. Если Де = 0,е > 1, тoi = argmini<j<ef(xi) разрешает задачу. В противном случае вектор 1£к представим в виде: zk = {¡Д^}, где ук С ET*,~zk С Er\ ri + г2 = я. Тогда

hi(yk,zk) = Iрк(ук) или ук{ук) = 0. Определим конус с вершиной в точке хк содержащий все решения этой системы: Lk = {х : Vtpk(yk)'y < Vipk(yk)'yk}. Предполагая невырожденность

| Viрк{ук) из уравнений ребер конуса: у' = ук - \'sk>,j = 1,п и из уравнений - AJsk'\zk) = f(yk,~k) найдем точки хк> пересечения этих лучей с границей множества <р(у, ~2к) < f(yk, ~Zk) и соответствующие им параметры Хк>. Предполагая невырожденность задачи получаем, что \к> > 0. В силу линейной независимости векторов sk>,j = 1,...,« точки yk',j = 1,...,п единственным образом определяют плоскость ак у < ßk и полупространство, не содержащее хк. Тогда

Rk+1 = {x:xCRk, ак'у < ßk} (20)

и xi+1 есть локальное решение следующей задачи:

min<p(z) (21)

hj(x) > 0, j = 1.....г, f{x) < xn+u х С Rk+l (22)

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

f{x) max (23)

Ах < Ь, (24)

где f : Еп —*■ Е1- непрерывная и квазивыпуклая функция, 6 С Еш, А- матрица размерности (гохге). Обозначим через L непустое, ограниченное множество L = {х : Ах < Ь}. Пусть го -вершина L, то каким нибудь методом математического программирования найдем невырожденное базисное решение г0. Если хо -невырожденное решение, тогда хо = Xq. Пусть С'0 = Со -максимальное значение целевой функции на отрезке Если х0 - невырожденное базисное решение, то мы можем рассмотреть эквивалентную (23) — (24) задачу:

f(x0 - A^ly) max (25)

У > 0 (26)

А3у < ¿з, (27)

где у = b\ - А\х, Aixo = b\, Л2г0 < Ь2, А3 = -A^Ai1, fa = b2 - А2х0. Если го -невырожденное решение, то при у = 0 в задаче (25) — (27) будет точно п соседних экстремальных точек: aiei,... ,anen, где a;- > О (j = 1,... ,п). Обозначим через

Со — тах{С^, тгис fix - a;/4^'e;)}, (28)

и через tj- максимальное число (может быть и = оо) для которого выполняется неравенство:

/(*o ~ tjA^ej) < Со, j = 1, • • •, п (29)

Обозначим через

«* = (1/«1.....!/<»)•

Пусть

(О 1<т,

(и) |*М,|>Т, где Т- положительная константа. В случае (¿) мы рассмотрим задачу:

/(Уо - -+ тах

при условиях

Секущее неравенство

У >0, г*у < 1

4*у > 1 или < ко,

(30)

(31)

(32)

(33)

где Л* = ¿'Л! и Но = - 1 исключает часть множества Ь, где /(я) < Со. В случае (И) обозначим через

сГ = (1/аг,...,1/а„)

и рассмотрим неравенство

<САхх < ¿*Ь 1 - 1 (34)

Легко показать, что неравенство (34) отсекает симплекс с вершинами:

Хо.го — ахА^в!,... ,£о -«„А^е»

Присоединив неравенство (34) к первоначальным ограничениям, мы сужаем допустимое множество Ь. Ясно что, после выполнения некоторых шагов выполняется:

Ь0 Э 1ц Э ... Э Ьк Э ...

Со < Сг < ... < С к < • •.

Теорема 2. Процесс заканчивается, если для некоторого индекса р > 1, L„ = 0. Тогда яр - решение (23) - (24), если f[xp) = Во втором параграфе рассмотрена задача:

где / : Еа —► Е1 - непрерывна и квазивыпукла, множество Ь = {х : Ах < 6}- непусто и ограниченно, компоненты (тхп) -матрицы А и (тх1) -вектора Ь - целые.

Пусть известна какая-нибудь допустимая точка задачи (35)-(37). Если такой точки не существует то задача не имеет решения. Обозначим допустимое множество задачи на шаге к через

Шаг к. а/. Находим точку(вершину) локального максимума Хк С

б/. Делаем преобразование подобное (25) — (27) и определяем ^ как максимальное положительное число, удовлетворяющее неравенству:

где Ац- неособая подматрица А\ и С\- максимальное значение целевой функции на решетке точек Ь. Формируем вектор ^ как в §2.1 и проверяем неравенство 11'кА\\ |< Т. Если оно выполняется при <4 или заделов, то мы сужаем Ь-К с помощью сечения (33). Если хь имеет хотя бы одну нецелую компоненту и | ИКАп |> Т, тогда сужаем Ьк с помощью сечения Гомори. Получаем Ь^+г новое допустимое множество и переходим к следующему шагу.

Теорема 3. После конечного числа шагов получаем, что Ьр = 0 для некоторого р > 1.

В параграфе 2.3 рассмотрена задача смешанного булевского программирования с максимизируемой выпуклой целевой функцией:

f(x) max

Ах <Ь, х - целый,

(35)

(36)

(37)

Lk{L, = L).

f(xк - tAife) < Ск + £, е > 0, j = 1,..., п,

F(x) max

(38)

при условиях

О < < 1, Xj — целые(з = 1,... ,р), р > 1 (39)

0<Xj<Kj, / = р+1,...,п, (40)

я

Т, ai)xi < Ь>, г = 1,..., т (41)

;'=i

где F : Еп —► Е1 -выпуклая, матрица А- имеет размерность (тхп), Ь-(roxl).

Теорема 4. Среди оптимальных точек (38)—(41) есть по крайне мере одна, которая является крайней точкой L{ L -множество точек, удовлетворяющих условиям (38) — (41) без условия целочисленности). Наша цель- применить методы раздела 2 для (38)—(41) для ускорения метода полного перебора. Следующая теорема дает непрерывный эквивалент задачи (38) - (41).

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

F{x) - A jr Xj(l - xj) max(A > 0) (42)

;'=i

при условии

х С L (43)

Существует действительное число Ао > 0 такое что, для любых А > Ао множества оптимальных точек (38) — (41) и (42) — (43) совпадают.

Мы будем называть решение (38) — (41) " 8 допустимым" "е- опти-мальным( 6 > 0,е > 0 ), если у- может нарушать условие a;jXj < bi, i = 1,... ,m не больше, чем на S и F(y) > F{z) - с, где z- оптимальное решение (38) - (41). Для практических вычислений мы нуждаемся в оценке А0. Следующая теорема дает оценку для А0. Теорема 6. Допустим, что (i). Va;i, 22 Q Т, где

Т = {х :0 < xj < 1, j = 1,...,р, 0 < Xj < kjt j =р+ l,...,n}

выполняется неравенство:

\F(XI)-F(X2)\< МЦх^хгЦ ,

где М, а- положительные константы,

(»). ка < ад < кг,

где г - какое-нибудь допустимое решение (38) - (41). (ш). А = [а,-;-] не имеет нулевых строк и столбцов. Если Л удовлетворяет неравенству:

д > кг~к° а0(1 - а0)

тогда любой вектор, полученный из оптимальной точки задачи (42) — (43) заменой первых р компонент ближайшими целыми есть " <5-допустимое", " е - оптимальное" решение (38) — (41), где ао = тт(а,5:); а < тт{£, }, а > 0;

я = min{ min г, -},гг > 0.

_6_ 1

lw<»Ej=1| ац |»2

В параграфе 2.4 исследована задача:

/(*) = -Е/i(*i) - max (44) j=i

0<xj<kjt j = l,...,n, (45)

iCt, (46)

где L - выпуклый многогранник и f(x)=l 0. еслих; =0, 1 ' I 9j(xj), если Xj > 0, j = 1,... ,n 1шц_о gj(xj) = Aj > 0, j = 1,... ,n

Здесь g}(xj) - вогнутая, монотонно возрастающая функция. Теорема 7. Рассмотрим задачу:

/(г, г) —► max (47)

при условии

0 <xj <*,-, j = l,...,n (48)

xCL, (49)

где г* = (гь..., гп), (г > 0)- вектор параметров и ; J' J 1 9j(xj)y «ели >r¡,j = l,...,n

3 Ti

Существует вектор го > 0 такой что, для любого г, 0 < г < го множества оптимальных точек задач (44) — (46) и (47) - (49) совпадают.

Параграф 2.5 посвящен исследованию задачи селарабельного нелинейного программирования с линейными ограничениями.

Л*) = £ /;(*;) - тах (50) i

4<х<к,(к>0), (51)

Ах< Ь (52)

где матрица А имеет размерность (rnxn), 6 -(mxl). Предположим, что (i). L={x: 0 < х < Jfc, Ах < b} ф 0

(ii). Для любых xj,xj, таких что, 0 < xrj < k'ej (j = 1,2) выполняется неравенство:

I f¿x}) - №}) ¡< Mj I г) - xj I (j = 1,...,n)

где Mj - констант.

(¡ii). fj(xj) = -oo для Xj < 0 и x¡ > k'ej, j = 1,... ,n

Для определения " е- оптимального" допустимого решения предлагаем итерационный процесс. Пусть xq = экстремальная точка множества £ = Lo. Допустим, что имеется "хорошее" аппроксимированное решение у0 С L. Положим Ко = /(уо) и определим f{x): J(x) = E"=17j(®j) гДе 7j(«/) - выпукла, 7jíxj) > fj(xi) Для всех Xj, Jj{x°j) = fj(xj),j = l,...,n. Как и раньше, рассмотрим преобразованную задачу:

J(x0 - A^ly) тах (53)

У > 0 (54)

A3 у< b3

(55)

Пусть tj - максимальное число, удовлетворяющее неравенству

7(*о - < Ко + е, ] = 1,..., п

для любого > 0, т.к. /(го) < Кц,У(х)- непрерывно. Пусть = (1/<1, •.. ,1/1п)- Для положительного числа Т сделаем сечение

если | t'Ai |< Т. Этим мы исключаем область, где 7(®о - А 1у) < Ко + е. Если | t*A\ |> Г, тогда примем сечение

где Г = (1/aii,... ,l/ai„), и а выбирается из соотношения

| 7|= Т. В этом случае для любых у, принадлежащих в исключаемой области

/(«о - АГ1!/) < 7{хо ~ Aily) < тах. J(xa - atjA^ej) = Р0.

На практике, если мы достигаем вектора, который дает большее значение целевой функции чем Ко, тогда начав с этой точки мы можем найти лучшую точку локального максимума со значением К\ > Ко и заменить Ко на К\. Когда достигается ситуация, что Lv = 0, получаем наилучшее решение уТ, поскольку оно удовлетворяет неравенству: /Ы < тах0<£<р_1 Rk где Я* = Kk + £, если на шаге к использовалось сечение (56) и Rk = Pit, если применялось сечение (57).

В параграфе 3.1 описана экономико-математическая модель задачи оптимизации режимов электро-энергетических систем(ЭЭС). Приведен краткий анализ исследования задачи.

Параграф 3.2 посвящен описанию модели задачи выбора оптимального состава работающих агрегатов ЭЭС. Обоснованы возможности решения этих задач методами, предложенными в данной работе.

t*V> 1

(56)

Ту> 1

(57)

Автор выражает искреннюю благодарность В.П.Булатову, под руководством которого была выполнена эта работа.

ПУБЛИКАЦИИ

- Батсурэн С., Ганхуяг Д. Одно обобщение теоремы о неявной функции. Труды института математики АН МНР. N6. с. 34-37. -1988.

- Ганхуяг Д. О приведении некоторых задач неопределенного квадратичного программирования к задачам выпукло-вогнутого программирования. // Методы оптимизации и их лриложениа(тезисы докладов ). -Иркутск, с. 34, -1992.

- Ганхуяг Д. Один способ приведения задачи глобальной оптимизации к задачам выпукло-вогнутого программирования и поиск локального и глобального решений. // Методы математического программирования и программное обеслечение( тезисы докладов). -Свердловск: УНЦ АН СССР, с.28-29. -1993.

- Ганхуяг Д. К модификации одного метода отсечений в вогнутом программировании.// Методы оптимизации и их приложения(тезисы докладов). -Иркутск, с.49-50, -1995.

Отпечатано в СЭИ СО РАН Заказ 433. Тирад 100 экз.