Некоторые вопросы поиска глобального решения обратно-выпуклых задач тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Цэвээндоржийн Идэр

• Цэвээндоржийн Идэр
• кандидат физико-математических наук
• 1996

Оглавление диссертации кандидат физико-математических наук Цэвээндоржийн Идэр

Введение

1 Теория методов решения задач обратно-выпуклого программирования

1.1 Необходимые и достаточные условия глобальной оптимальности

1.2 Минимизирующие последовательности.

1.3 Теоретический метод глобального спуска в задаче (Р11).

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

2.1 Построение алгоритма, решения задачи (РЯ)

2.2 Сходимость Л-алгоритма.

2.3 Пример разрешающего набора для одной частной задачи

3 Численные эксперименты

3.1 Численное решение В- ал гор и т мом одной квадратичной тестовой задачи

3.1.1 Постановка тестовой задачи.

3.1.2 Метод локального спуска.

3.1.3 К решению задачи (ЬР8).

3.1.4 К решению линеаризованной задачи

3.1.5 Численные результаты и их анализ.

3.2 К решению задачи о рюкзаке И-алгоритмом.

3.2.1 Постановка задачи и переход от целочисленной к непрерывной задаче.

3.2.2 Метод локального подъема в задаче о рюкзаке.

3.2.3 О связи задач (Рз),(РК).

3.2.4 Метод решения "линеаризованной задачи"в задаче

3.3 Численное решение задачи о рюкзаке Я-алгоритмом.

Введение диссертации (часть автореферата) на тему «Некоторые вопросы поиска глобального решения обратно-выпуклых задач»

В последние два десятилетия проблемы глобальной оптимизации приобретают все большее и большое значение. Это связано, во-первых, с бурным ростом интереса к многоэкстремальным задачам со стороны экономистов, экологов и специалистов, занимающихся проблемами обработки информации, во-вторых, с тем, что с появлением быстродействующих ЭВМ стало возможным эффективное решение многих важных прикладных задач, которое ранее из-за своей сложности представлялось недоступным [1, 15, 44, 46].

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

Если в задаче (1) все фигурирующие при ее описании функции /(•), (1, т)выпуклы, то такая задача называется выпуклой и к настоящему времени разработано и исследовано большое число методов ее решения (см. напр. литературу в [15]).

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

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

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

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

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

1) начальных точек весьма ограничены.

Теоретически обоснованные методы глобальной оптимизации разработаны только для задач со специальной структурой. Желательно, чтобы эти методы должны учитывать специфику задания как целевой функции, так и допустимого множества.

В литературе [124, 125, 134] принято различать следующие классы простейших задач невыпуклой оптимизации.

• а) Вогнутая минимизация, то есть минимизация вогнутой функции или, что равносильно, максимизация выпуклой функции на допустимом множестве: f(x) -» max, х € D\ (Р)

• b) Задачи обратно-выпуклого программирования. Например, таковой является следующая задача f(x) min, g(x) > О, .г € А, (PR) где д(-)-выпуклая, а /(-)-непрерывная функции.

• с) d.c.- программирование г(ж)min, ж G D, (PDC) где функция h(-) представлена как разность двух выпуклых функций: = f{x) -g(x).

При этом d.c.- (разность выпуклых) функции могут входить также в ограничения типа равенств и неравенств.

• d) Минимизация Липшицевых функций.

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

Достаточное число работ посвящено теории и численным методам решения таких задач [127, 147] (особенно (Р)). Из них можно выделить три основных направления:

1. методы отсечений;

2. методы ветвей и границ;

3. методы внешней и внутренной аппроксимации.

Благодаря работам в этих направлениях, в последним два десятилетия значительного прогресса достигли исследования невыпуклых задач, о чем свительствует большой поток публикаций по глобальной оптимизации, (см. напр. [124, 147, 150])

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

Как известно, принцип' Лагранжа в самой общей его форме даже с использованием производных, которых в современной литературе введено достаточное количество [24], не дает условий достаточных для глобальной оптимальности, например, в задачах (Р), {PR), (PDC)M как следствие, в традиционных численных методах оптимизации [3,11,12,15], в невыпуклых задачах, вообще говоря, можно гарантировать сходимость лишь к стационарной точке, или в лучшем случае к локальному экстремуму.

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

Таковыми являются, например, следующие условия: i) Если min(//D)=min(<^/D), где функция </?(•) и множество D выпуклые и fix) > ф), Ух е D, то z = argmin((<5 / D) является решением задачи типа (Р).(см. напр. [125]) ii) Пусть z£DhS = {x<eD/ S{x) < /(<?)}• Тогда из того, что

KS) = о, где ¿¿(-)-мера, следует г является решением задачи (Р).(см. напр.[125]) iii) Пусть /(х) >0 Ух 6 D и z £ D. Тогда z является решением выше названной (Р), тогда и только, тогда когда последовательность [101] ограничена. iv) Пусть D-выпуклое, int D ф 0, и функция /(•) непрерывна. Тогда предельная точка последовательности к JDxekf^dx Х ~ fDekf{x)dx является решением задачи (Р)(см. напр. [134]).

Проверка этих условий становится трудоемкой (или в большинстве случаев безнадежной) из-за построения функции </?(•) в первом, вычисления меры Лебеговского множества во втором и вычисления интеграла по заданному множеству D в послед-ных условиях.

Соответственно, и методы построенные на основе этих критериев оказываются малоэффективными.

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

Одним из первых оригинальных результатов в этом направлении было необходимое условие оптимальности, полученное Р. Рокафелларом для задачи выпуклой максимизации (z £ Argmax(ffD))[58]: df(z)cN(z/ D), где д f(z) = {x* G X* / f(x) —f(y) > {x*, x — у) Vx, у}- субдифференциал выпуклой функции, a N(z / D)- конус опорных функционалов ко множеству D в точке г, так что условие Рокафеллара может быть записано в более простом виде:

V2* € df{z) : (z*, х - z) < 0 \/xeD.

Далее, несомненным достижением явилось полученное в 1988 году, Ж.-Б. Ириарт-Уррути, необходимое и достаточное условие глобальной оптимальности [121]. Развив предварительно технику е-субдифференциалов [119] ему удалось получить следующее условие для задачи выпуклой максимизации (z Е Arg max( / / D)) : де f{z) С Ne(z / D), Ve > 0, где де f(z)- е-субдифференциал функции /, а Ne(z / D) — е-конус опорных функционалов ко множеству D в точке z.

Другой подход был развит в работах Стрекаловского А. С. [63-74]. Полученное им в 1987, условие оптимальности для задачи (Р), основанное на использовании поверхностей уровня выпуклых функций, имеет вид: д f(z) С N{z / D), Уу : f(y) = /(*). (2) z <Е Arg max( / / D))

Нетрудно видеть, что при у = z из этого условия следует условия Рокафеллара, а для дифференцируемой функции /(■) классическое условие оптимальности f'(z),x-z) < 0, VxeD

Отметим, что классическое и условие Рокафеллара доказаны только при предположении выпуклости допустимого множества D, чего не требуется при доказательстве условия (2). К тому же, отмеченные условия являются только частным случаем условия Стрекаловского.

Данная диссертация посвящена решению задачи: f(x) min, д(х) >0, х £ А, (PR)

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

Вначале напомним вкратце несколько практических задач, которые могут быть сформулированы в виде (PR).

1. Задача целочисленного программирования.

Бесспорно, это весьма существенный класс экстремальных задач, возникающих на практике [4,45]. f(x) min, х £ D, Xi £ Z+, г = l,n (3)

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

R'i

Xi = Vifi^ Ун e {°> !}> * = 1, n, j=o где целое число Ki -верхняя граница величины log2 я,-. Тогда задача (3) принимает вид

7(у) min, у £ D, угз £ {0,1}, j = 1, Ki, г = 1~п

В свою очередь булевое ограничение yij £ {0,1} эквивалентно ограничениям:

У1-ун> 0, О<^<1.

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

7(у) min, у £ D П П, у2г] - уг] >0, j = 1 ,Kit i = ТТгё, где П = {у / 0 < у^ <1, j = 1 ,I<i, i = 1 ,n}.

2. Задача о дополнительности [59,124,125,146]

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

Qx,x) + (с, х) ->■ min, Ах>Ь, ж > О (4)

В случае положительной определенности квадратичной формы <5, целевая функция выпуклая и условия Куна-Таккера являются достаточными условиями оптимальности в задаче (4). Таким образом, в этом случае для решения задачи (4) достаточно найти точку, удовлетворяющую условиям Куна-Таккера, которые для сформулированной задачи могут быть записаны (см. [59]) в виде: (2(^х- Ат\ + с,х) = О, (Ах -Ь,Х) = О, хеЯп, Л € Ят > 0.

Введя обозначения

П М-ЬН-* запишем условия Куна-Таккера в новых обозначениях / (Мг + д,г) = 0 и ^ ^ г. ^ п и ли Мг + д> 0, г > 0 у = Мг + д у,г) = 0 у > 0, г>0.

Полученная задача называется задачей о дополнительности. Очевидно, что условие у,г) = 0, у > 0, г>0, эквивалентно ограничениям п тт{^,г;}<0, у > 0, г>0. г= 1

Первое из них является обратно-выпуклым, так как функция т1п{Уь 2г} вогнутая.

3. Задача об описанном контуре минимальной длины (Упаковки шаров).

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

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

Переменными оптимизации здесь являются х,у,г € В2 -центры кругов, а целевой функцией- периметр описанного прямоугольника 2(а 4- Ь), где а, Ь-длины его сторон. Известны радиусы кругов гх,гу,гг.

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

Xi - гх > 0 i Xi + rx < а ( х2 + гх <Ъ yi-ry> 0 , i = 1,2; < yi + гу < а , < у2 + гу < Ъ . Zi - rz>0 { Zi + rz < а [ z2 + rz < b

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

- у||2 > (гх + Гу)2 z ~ yf > (rz + ryf

4. Задача о потоке на сетях

Рассматриваем задачу максимизации потока на сетях при ограниченном бюджете В [93,114]. Затраты на прохождении единицы потока по г-ой дуге составляют с,(сг- > 0). Функции с4(-) такие, что £¿(0) = 0, сДоо) = оо предполагаются вогнутыми или линейными. А их сумма-функция с(:г) = Y^-\ci{xi) строго вогнута. v max, Ef - V = 0, f - х < U, с(х)<В, f,x> 0, где [/-вектор начальной мощности дуг сети, V = (t>, 0,., 0, — v), ^-матрица инцидентности сети, и /, х вектора соответсвенно истекаемого и притекаемого потока по дугам. При изменения объема ветвей от щ до щ + жг-, жг- > 0, как правило функция затрат Ci(xi) вогнутая и следовательно, ограничение д(х) = —J2 Ci(xi) + В > 0 является обратно-выпуклым .

5. Задача размещения

Рассматривается следующая задача [1] п т п

X/ X aijx4 = hj, Xij >0, г = 1, n, j = 1, т

1j=1 г=1 п п

X Mvi) ^ Vi ^ X) г = м» ¿=i j=1 где aij- транспортный расход перевозки единицы из г'-го пункта производства, в j-ый пункт потребления, ж^-объем перевозок, объем производства г-ом пункте, bj- объем потребления j-ом пункте и 5-общая сумма наличных средств на производственных пунктах.

При этом функция затрат Ya=i fi(Vi)i как правило, предполагается вогнутой.#

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

Задача f(x) max, х € D; очевидно, равно следующей (rj 6 R) г] max, xGD, f(x) — rj > 0; a d.c.-задача f(x) — g(x) —> min, x € D, равносильно задаче (77 £ R) f(x) — 7] -)• min, iGÖ, <7 (ж) — 7/ > 0, где функции /(•), ^(-)-выпуклые.

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

Первые работы, посвященные обратно-выпуклым задачам появились, насколько нам известно, в середине 60-х годов у Розена и Булатова.

В работе [11] Булатова такая задача названа задачей минимизации "на дыре", далее, к ее решению был предложен итеративный процесс последовательной линеаризации "плохого"ограничения д{х) > 0 и доказана его сходимость к точке Куна-Таккера. Также было отмечено, что для решения рассматриваемой задачи данный метод локального поиска существенно более эффективен, чем итерационные процессы, разработанные для решения задач выпуклого программирования.

Чуть позже в [142] Мейером был предложен метод, суть которого заключается в последовательном решении задачи: min, х £ А, {д'(у),х-у)> 0, (R(y)) следующим образом: a) выбирается у0 £ А, д(у°) > 0 b) для некоторого уг решается задача R(yl) и решение этой задачи обозначается yt+1.

И в [142] доказан результат, что если оператор линеаризации Г(у) полунепрерывен снизу в предельной точке у* последовательности {уг}, то у* является решением задачи R(y*), где

Т(у) = {х£ А/ д{у) + (д' {у),х-у)> 0}.

Если заметить, что утверждение Мейера эквивалентно условиям Куна-Таккера, то результаты Булатова и Мейера, по-видимому, очень близки.

Ценность предложенного этими авторами метода локального поиска, безусловно велика, но для поиска глобального решения задачи (PR) недостаточно этого метода.

Кроме того, впервые Мейером был введен термин "обратно-выпуклое ограничение" и с тех пор задача (PR) называется обратно-выпуклой (reverse convex).

Далее, в работах [89, 90] Эвриэла и Уильямса показано, что при описании задачи инженерного дизайна участвуют обратно-выпуклые ограничения. Другие интересные практические применения решения исследуемой задачи можно найти в работах [170, 159], где рассмотрена проблема огранения ценных камней и в статье Залесского [38] посвященной формализации экономической задачи о переоборудовании предприятия.

Наиболее глубокое исследование в этой области нашло место в серии работ Хил-лестада, Якобсена и Бенсела.

Хиллестадом в [114] рассмотрена задача линейнего программирования с одним дополнительным обратно-выпуклым ограничением (ЛЗОВП-линейная задача обратно-выпуклого программирования) и показано, что проблема расширения потока по сетям формалиризуется в этом виде (см. напр. задачу о потоке). К решению этой задачи предложен один метод, основанный на переборе вершин многогранника.

В [93] Бенсел и Якобсен исследовали также ЛЗОВП и для нее получили специфичные необходимые и достаточные условия локального решения. На основе полученных условий предложили алгоритм решения данной задачи, но его практическое применение встречает серьезные трудности, хотя и доказана сходимость за конечное число шагов.

Далее в [115, 116] Хиллестад и Якобсен для решения рассматриваемой задачи развивали идею комбинирования отсечения и перебора вершин многогранника. Прежде всего доказали, что выпуклой оболочкой допустимого множества ЛЗОВП является выпуклый многогранник. Затем предложен алгоритм глобального поиска, состоящий из следующих, стандартных для метода отсечения процедур:

- решать задачу ЛП игнорируя обратно-выпуклое ограничение,

- если решение задачи ЛП удовлетворяет игнорированному ограничению, то оно является решением исходной задачи,

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

Нужно заметить что, хотя также доказана конечная сходимость данного метода, заметного практического успеха он не приносил.

Следующий этап исследования задачи обратно-выпуклого программирования связан с именем X. Туя. [165, 168] Для ее решения им и его учениками разработано семейство методов отсечения, основанное на введенной Туем двойственности задач вогнутой минимизации и обратно-выпуклого программирования и на идее ранее примененного для задачи вогнутой минимизации метода отсечений для задачи вогнутого программирования. Одним из недостатков метода отсечения для данной задачи является отсутсвие гарантии нахождение глобального решения.

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

Неэффективность метода отсечения обсуждалась в работах [94-96, 112]. Здесь как тестовая, рассматривалась задача

Х\ —> min, 0 < Х{ < 1, г = 1,га

5)

7(z) = £-=i*?-(n-0.5) >0

Методом отсечения задача (5) размерности п = 2, 3 решается. Когда п = 4 глобальное решение найдено через 75 итераций. А начиная с размерности п—5 метод останавливается в некоторой допустимой точке, которая не является глобальным решением. Причиной этого вновь являются паралельность отсекающих плоскостей, что потверждается численными экспериментами в [112].

В данной диссертации предложен другой подход решения задач обратно-выпуклого программирования, который основан на необходимых и достаточных условиях глобального минимума, полученных в [70], подобных условиям (2) для выпуклой максимизации.

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

Если z является глобальным решением задачи (PR) и кроме того, выполнено предположение

Agrmm(PR) П {х / д(х) > 0} = 0, характеризующее обратно-выпуклую задачу, то

Уу : g(y) = g(z) = 0, g'(y),x-y}< 0, Ухе А, f(x)<f(z). )

Е)

При у = г, если функция /(•) выпуклая и дифференцируемая и множество А выпуклое, то из (Е)следует известное условие оптимальности

Х/'(г)-1лд'(г),х-г)>0, Ух € А. / Кроме того, при выполнении следующих дополнительных предположений:

-оо < ш% / X) < д(г) = 0, Уу е А: д(у) — 0, 3 к = к(у) € с1со А, (у),к-у)> 0; следующее усиление условия {Е):

Уу 9(у) = = О, д'(у),х-у)< О,

1)

УхеЫсоА, /(ж) </(*); „ становится и достаточным для того, чтобы г было глобальным решением.

Однако является ли данное условие конструктивным для построения численных методов решения задачи {РВ) ?

Чтобы ответить на этот вопрос, заметим, что проверка условия (Е1) сводится к рассмотрению семейства задач, называемых линеаризованными: где х° решение задачи (6).

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

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

Глава 2 посвящена построению алгоритмов глобальной оптимизации для задачи с квадратичным обратно-выпуклым ограничением, основанных на результатах первой главы. Основной целью проведенных исследований было построение алгоритма, комбинирующего хорошо разработанные традиционные численные методы локального поиска для задачи {РВ) и вычислительные процедуры, вытекающие из необходимых и достаточных условий глобальной оптималности [Е1).

При этом для задачи ЛП с дополнительным квадратичным обратно-выпуклым ограничением удалось построить достаточно простую аппроксимацию поверхности уровня II{г), состоящую из гп + 1 легко строящихся точек, где т- количество линейных ограничений и доказано, что с помощью этой аппроксимации теоретически можно сделать заключение о глобальности рассматриваемой точки г или "выходить"из локального экстремума.

Более того, построен алгоритм минимизации для задачи {РВ) с квадратичным обратно-выпуклым ограничением, который удалось, во-первых проинтерпретировать д'{у), х) -»• тах, х <Е с1со А, /{х) < /(г), где у € и {г) = {у / д(у) = д(г) = 0}, с последующей проверкой условия

6) д'{у), х°-у)< 0, как частный случай теоретического метода, предложенного в параграфе 1.3; во-вторых, удалось доказать с помощью теоремы сходимости из параграфа 1.3, что последовательность генерируемая этим алгоритмом, является минимизирующей.

Таким образом, результаты главы 2 удалось представить как конкретизацию теоретических результатов главы 1.

Построенный алгоритм называем /¿-алгоритмом. Эффективность применения Я-алгоритма при численном решении задачи (РН) на практике будет зависеть, в основном от качества решения следующих подзадач:

• построение аппроксимации поверхности уровня функции обратно-выпуклого ограничения;

• выбор метода локального поиска;

• выбор метода решения линеаризованной задачи.

В третьей главе излагается экспериментальная часть исследования, проведенного на основе предложенного нами подхода. Вычислительный эксперимент был проведен на компьютере класса IBM PC 386SX. Программа для эксперимента реализована на языке программирования Pascal.

Параграф 3.1 посвящен численному решению тестовой задачи:

1 - у\\2 min, 2 1<жг<1, г = 1,та,

ЕГ-1 0.5) > 0.

7)

Эта задача отличается от задачи (5), которая была рассмотрена в [112] в качестве тестовой задачи метода отсечений, нелинейностью целевой функции и паралелепи-педным ограничением.

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

Анализ проведенного первого эксперимента показывает, что предложенный Д-алгоритм обладает довольно хорошими свойствами, заключающимися в следующем: а) время решения для задач большой размерности является сравнительно небольшим (для п=100 около 5 минут, ?г=400 почти 4 часа) и приемлемым для практики;

Ь) появляется возможность использования существующих пакетов прикладных программ стандартных методов оптимизации с учетом специфики каждой конкретной задачи.

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

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

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

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

Результаты диссертации докладывались

- на 17-ой конференции 1ИР-95 по моделированию систем и оптимизации

Прага, Чехия, июль 1995 г.)[76],

- на Международной 10-ой Байкальской школе-семинаре "Методы оптимизации и их приложения"(Иркутск, август 1995 г.)[75],

- в Ш-ом совещании по глобальной оптимизации

Зегед, Венгрия, декабрь 1995 г.)[77],

- на 8-ой совместной Франко-Германской конференции по оптимизации

Триер, ФРГ, июль 1996 г.)[79]. и на семинарах

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

ВМ и К Московского университета им. М.В. Ломоносова ( руководитель профессор Васильев Ф.П.),

- по методом оптимального управления кафедр методов оптимизации и вычислительной математики ИГУ (руководители профессора Васильев О.В. и Срочко В.А.)

- кафедры высшей математики ИГЭА (руководитель профессор Дыхта В.А.)

- лаборатории исследования операции СЭИ СО РАН (руководитель профессор Булатов В.П.)

- лаборатории проблем управлении ВЦ ИГУ ( руководитель профессор Стрекаловский A.C.)

Автор выражает глубокую благодарность своиму научному руководителю - профессору Стрекаловскому А. С. за постановки задачи и постоянное внимание к работе, а также руководителям и участникам семинаров, где автору удалось докладывать, -за ценные замечания и советы.