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

Введение

1 Глобальный поиск в обратно-выпуклых задачах 20 1.1 Некоторые сведения об обратно-выпуклых задачах. ф 1.2 Методы локального поиска.

1.2.1 Специальный метод локального поиска.

1.2.2 Модифицированный метод Розена.

1.3 Условия глобальной оптимальности.

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

1.5 Стратегия глобального поиска

1.6 Сходимость стратегии глобального поиска.

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

2.1 Постановка задач

2.2 О методах локального поиска.

2.3 Специальный алгоритм глобального поиска.

2.4 Численное решение задач с ограничением типа нормы.

2.4.1 Выбор начального приближения.

2.4.2 Аппроксимация поверхности уровня

2.4.3 Результаты численного эксперимента.

2.5 Численное решение задач с квадратичным ограничением общего вида

2.6 Численное решение задач с другими нелинейными ограничениями

2.7 Анализ вычислительного эксперимента. ф 3 Численное решение задачи о многомерном рюкзаке

3.1 Постановки задач.

3.2 Практические приложения.

3.3 О стратегии глобального поиска для задачи о рюкзаке.

3.4 Построение аппроксимации поверхности уровня.

3.5 Построение оценок.

3.6 Численный эксперимент по решению задачи о рюкзаке

3.6.1 Алгоритм глобального поиска для решения задачи о рюкзаке

3.6.2 О решении линеаризованной задачи.

3.6.3 Локальный поиск для задач о рюкзаке.

3.6.4 Результаты численного эксперимента.

3.7 Метод исключения координат.

3.8 Численное решение задачи о многомерном рюкзаке.

Слово "оптимизация" становится все более популярным и не всегда используется в своем изначальном математическом смысле. А последнее, как известно, означает выбор из множества допустимых альтернатив наилучшей. И такие задачи встречаются в неисчислимом множестве не только в науке, но и во всех прикладных областях человеческой деятельности, о чем свидетельствует, например, научно-техническая революция в XX веке. Экономика и экология, техника и строительство, управление электрическими, газовыми и тепловыми потоками и вообще управление динамическими системами без использования современных математических методов нередко приводят к деградации объектов и процессов управления, авариям и даже катастрофам. Известные аварии в Бхопале (Индия), Чернобыле (СССР), недавние электроэнергетические катастрофы в США и Италии — тому подтверждение.

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

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

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

Достаточно сложно привести полную классификацию задач невыпуклой или, как еще принято говорить, глобальной оптимизации. Тем не менее, в литературе [118]-[120] принято рассматривать следующие четыре класса задач.

1. Задачи выпуклой максимизации (или вогнутой минимизации): f(x) t шах, х е D, (СМ) где /(•) — выпуклая функция на некотором открытом выпуклом множестве i) С IRn, содержащем допустимое множество D.

2. Обратно-выпуклые задачи или задачи на дополнениях выпуклых множеств. Простейшей задачей подобного типа является следующая задача h(x) 4- min, х € S, д(х) > 0, (RC) где д(-) — выпуклая функция на выпуклом открытом множестве О. С Мп, содержащем множество 5, Л(-) — непрерывная функция на Rn.

3. Задачи d.c. минимизации

F(x) = д(х) - f(x) i min, х е D, (DC) где /(•), д(-) — выпуклые функции на некотором открытом выпуклом множестве i) С iRn, D С £1. Функцию F(•), представимую в виде разности двух выпуклых функций, в литературе принято называть d.c. функцией (the difference of two convex functions).

4. Экстремальные задачи с d.c. ограничениями, простейшей из которых является задача следующего вида h(x) I min, х eS, F(x) > 0, (DCC) где F(x) = g(x) — f(x), x € i), а /(•), g(-) являются выпуклыми функциями на выпуклом открытом множестве Q С JR", содержащем множество 5, h(-) — непрерывная функция на IRn.

Нетрудно видеть, что при д(х) = 0 задача с1.с. минимизации (ОС) обращается и задачу выпуклой максимизации (СМ), так что последняя является частным случаем (ОС). Аналогично задача с с1.с. ограничениями (БСС) при /(х) = 0 обращается в задачу (ЯС) на дополнении выпуклого множества, которая, таким образом, оказывается частным случаем (ИСС). Итак, можно сказать, что простейшие задачи (1.с. программирования (ОС) и (ОСС) являются основными согласно предложенной классификации.

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

- отсечений (8, 9, 106, 151];

- ветвей и границ [120, 122, 136, 151];

- внешней и внутренней аппроксимации [8, 122, 151].

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

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

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

Однако, как известно, принцип Лагранжа в самой общей его форме, даже с использованием производных, которых в современной литературе введено достаточное количество [22], не дает условий, достаточных для глобальной оптимальности. И, как следствие, в невыпуклых задачах с использованием традиционных численных методов оптимизации [2, 9,14, 17], [50]-[56], [82] можно гарантировать сходимость, вообще говоря, лишь к стационарной точке или в лучшем случае к локальному экстремуму и то не во всех случаях.

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

Одним из первых оригинальных результатов в этом направлении было необходимое условие локальной оптимальности, полученное Рокафелларом Р. [58] для задачи (СМ). Оно имеет следующий вид: если г G Argшах(/, А'), то df(z) С N(z/X), где df (z) = {х* € lRn : f (х) — f (z) > (х*, х — z) Vx £ IR71} — субдифференциал выпуклой функции / (•) в точке z, а. N (z/X) = {х* G JRn : (х*,х — z) < OVx € IR11} — конус опорных векторов к множеству X в точке г.

Далее, несомненным достижением явилось полученное J.B. Hiriart-Urruty необходимое и достаточное условие глобальной оптимальности [115,116] для задачи выпуклой максимизации {СМ). Развив предварительно технику е - субдифференциалов [114], ему удалось получить следующее условие г 6 Arg тах(/,Х) <=> dj(z) С Ne(z/X) Me > 0, где def(z) - £-субдифферециал функции /, a Ne(z/X) - множество e-опорных функционалов по множеству X в точке z.

Другой подход к характеризации глобального решения был развит в работах A.C. Стрекаловского [60]-[66], [144]-[146]. Предложенные им условия оптимальности характеризуют глобальное решение задач типа (CM)-(DCC), используя поверхность уровня функции, задающей невыпуклость в задаче, а также классическую идею линеаризации.

Полученное в 1987 г. условие оптимальности для задачи выпуклой максимизации (СМ) основано на использовании поверхности уровня выпуклых функций и (при выполнении некоторых условий регулярности) имеет следующий вид:

2 € Arg шах(/, D) df(y) С N(y/D) Vy : f(y) = f(z). (1)

В случае дифференцируемости функции /(•) условие (1) принимает вид:

2€ Argmax(f,D) & <V/(y), х - у) < 0 Wy : f(y) = f(z), Vz € D. (2)

Легко заметить, что при у = z из условия (2) следует классическое условие локальной оптимальности:

Vf(z),x - z) < 0 VxGD, которое обычно [13, 14] доказывается только при предположении выпуклости допустимого множества D, чего не требуется при доказательстве условия (2) [62].

Отметим, что проверка условия оптимальности (2) сводится к решению серии, так называемых, линеаризованных задач

V/(y),s)tmax, х G D, (PL) зависящих от параметра у, лежащего на поверхности уровня функции /(•), задающей невыпуклость в задаче (СМ). При этом в случае выпуклости множества D задача (PL) оказывается выпуклой, и для ее решения применимы известные методы выпуклого программирования [4, 11, 12, 13, 27, 28, 33, 34, 50, 51, 53, 54, 56, 82]. Таким образом, данный подход принимает во внимание богатый численный опыт решения выпуклых задач.

Позже A.C. Стрекаловским были получены условия оптимальности для обратно-выпуклых задач [62, 64, 144] и задач d.c. программирования [66, 146]. Подчеркнем, что условия оптимальности для задачи выпуклой максимизации (СМ) являются частным случаем условий для задачи d.c. минимизации (DC), а из необходимых и достаточных условий для задач с d.c. ограничениями (DCC) вытекают условия глобальной оптимальности для задач на дополнениях выпуклых множеств (RC). Это гармоничное взаимоотношение между постановками задач и условиями глобальной оптимальности, думается, подчеркивает естественность предложенного подхода.

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

Впоследствии подобные алгоритмы были предложены и для задач обратно-выпуклого программирования [45, 77, 147], и, наконец, для общих задач d.c. оптимизации [66]-[69], [71]-[75], [88, 146].

При этом необходимо отметить, что, насколько известно (8,45, 77, 99,111, 112, 113, 123, 124, 100, 131, 132, 110, 140, 147, 150, 152|, огромное количество работ посвящено решению обратно-выпуклой задачи вида h(x) 4, min, xeS, д{х) > 0. (RC)

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

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

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

Это весьма многочисленный класс задач, возникающих на практике [3, 50J, например, задачи планирования производства [84], размещение предприятий и распределение капиталовложений [10]. В качестве примера здесь рассмотрим задачу транспортного обслуживания [44].

Пусть из некоторого пункта необходимо доставить Ь человек. Транспортное агентство располагает автобусами п типов, вместимостью а; (г = 1,.,п) человек. В зависимости от типа автобуса установлены тарифы на проезд С{. Необходимо определить, какого типа автобусы и в каком количестве следует использовать так, чтобы суммарные издержки были минимальными.

Пусть Xi — количество автобусов г-го типа. Тогда получаем следующую задачу целочисленного программирования: с, х) 4. min, (а,х) > Ь,

• I О

Xi £ i — lj • • • j Tl, где Z+ — множество неотрицательных целых чисел.

Применяя следующее представление для каждой переменной:

Ki t/ij б {0,1}, г = 1,., п, з= о где целое число Я",- — верхняя граница величины log2x,-, и учитывая, что в свою очередь, булевое ограничение у^ € {0,1} эквивалентно ограничениям — ytj > 0

О < Vij < 1» получаем задачу (4) в виде i(y)|min, yeSnll, yfj~Vij> 0, j = l,.Kit i — 1,., n, где = S=\yeIRn \ i=l j=О l i=l j=0 )

П = {y e Rn I 0 < Vij < 1, j = 1,. JTlf i = 1,., n}.

2. Задача о дополнительности.

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

Qx, х) + (с, х) 4 min, Ax>b, х>0.

5)

Если квадратная матрица <3 положительно определена, то целевая функция в задаче (5) выпукла, и условия Куна-Таккера являются достаточными условиями оптимальности в задаче (5). Поэтому, в данном случае для решения задачи (5) достаточно найти точку, удовлетворяющую условиям

2фх - АТХ + с, х) = О, (Ах - Ь, А) = О, Л > О, х б Вп, А € ШГ.

После введения обозначений z —

Л/ М =

2Q -АТ ст\ \~Ь1

Mz + q, г) = О, Mz + q> 0, z>0 или

А О перепишем условия Куна-Таккера следующим образом: у = Мг + ц,

У, 2> = О, у >0, г>0.

Полученная задача (6) называется задачей о дополнительности [5, 119, 120, 135]. Очевидно, что условия (у,г) = 0, у > 0, г > 0 эквивалентны ограничениям п

С тт{уг-, -г, } < 0, у > 0, г > 0, ¿=1 п первое из которых является обратно-выпуклым, поскольку функция £ г,-} = 1 вогнутая функция.

6)

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

Рассмотрим следующую задачу [1]: п т ' И а>цХц 4 min, i=ij=i п xij ^ °> i = l,.,n, j = 1,., m, > i=i n n fiiVi) < B, i = l,.,n,

1=1 1=1 где o,ij — транспортные затраты на перевозку единицы продукции из г-ого пункта производства в j-ый пункт потребления, х^ - объем перевозок, г/j - объем производства в г-ом пункте, fi{yi) - функциональная зависимость стоимости производства одной единицы продукции от объема производства в г-ом пункте производства, bj -объем потребления в j-ом пункте и В - общая сумма средств на производственных пунктах.

Можно показать, что если стоимость продукции убывает при возрастании объема производства, то функции /,• (t/j) являются вогнутыми, что отражает экономическую п реальность. Именно эти слагаемые и создают специфику ограничения £ fi{yi) < В i=i его обратную выпуклость, что приводит к обратно-выпуклой задаче.

4. Иерархические системы управления (Многоуровневое программирование).

Разнообразие таких систем необычайно широко и включает в себя, в частности, игры типа центр и т подчиненных производителей (например, федерация — регионы, или регион — муниципалитеты и т.д.).

Рассмотрим простейшую из подобных игр: центр (I игрок) — один производитель (II игрок) (69]. Каждый из участников имеет свой критерий эффективности и связанные ресурсы, но преимущество хода у I игрока.

При выборе "центром" управления х игрок II выбирает свое управление у с целью оптимизировать свой критерий эффективности д(у) на множестве ограничений Y(x) С Ш.п, зависящим от х. Например, может быть, что

Y(x) = {yeRn | G{x, у) < 0, у в Р}, где Р С Rn, G : ]Rm+n -» JR — непрерывная функция.

Итак, ответом игрока II на решение х игрока I будет вектор у = у{х), являющийся решением задачи g(v) t max, v G Y(x). (7)

Естественно предположить, что у лица, принимающего решение на верхнем уровне, имеется свой взгляд на оценку принятия решений, следовательно, свой критерий эффективности, который оценивает и свою стратегию, и стратегию игрока II. Поэтому возникает следующая задача: х, у) | min, (а?, у) es С Ш.т+п, У € Y(x), yeSoli7)

При этом даже в простейшем случае, когда все данные задач (7) и (8) линейны: f(x,y) = (с,х) + (di,у), д{у) = (d2,y), S = {(ж, у) : Aix + Вху < Ьи х € Я™}, > Y{x) = {v : А2х + B2v <b2, у € Щ}, взаимосвязи между верхней и нижней "властью" создают невыпуклости, которые не могут быть преодолены стандартными методами нелинейного программирования. Действительно, обозначим через V(x) оптимальное значение нижней подзадачи

V(x) = sup{p(v) : v € v

Тогда включение у 6 Sol(7) равносильно неравенству g(v)>V(x), у € Y(x). (9)

Довольно часто целевая функция игрока II вогнута, как в линейном случае. Тогда и функция оптимального значения V(-) тоже оказывается вогнутой [151]. При этом ограничение-неравенство в (9) оказывается обратно-выпуклым относительно х. #

В работах [96, 97] показано, что при описании задачи инженерного дизайна участвуют обратно-выпуклые ограничения. В [111] описано, как проблема расширения потока по сетям формалиризуется в виде задачи линейного программирования с одним дополнительным обратно-выпуклым ограничением. Другие интересные практические применения решения исследуемой задачи можно найти в работах [149, 153], где рассмотрена проблема огранения ценных камней, и в статье [31], посвященной формализации экономической задачи о переоборудовании предприятия.

Можно привести дополнительное количество примеров практических задач, если учесть, что задачи выпуклой максимизации (СМ) и задачи d.c. минимизации (DC) могут быть сведены к обратно-выпуклым задачам. Так задача f(x) t max, х G D, очевидно, может быть сведена к следующей задаче (77 € JR.):

771 max, х G D, f(x) - 77 > 0; а задача d.c. минимизации f(x) — g(x) I min, x E D, приводит к обратно-выпуклой задаче (tj £ М) f(х) —т)1 min, х Е D, д(х) — т) > 0, где функции /(•) и <?{•) — выпуклые.

Первая работа, посвященная обратно-выпуклым задачам, насколько нам известно, вышла в 1966 г. [140], где Ж.Б. Розеном была рассмотрена одна задача оптимального управления, для которой в качестве вспомогательной рассматривалась задача обратно-выпуклого программирования (RC) (хотя сам термин "обратно-выпуклая задача" (reverse convex problem) введен был позднее P.P. Мейером в [131]). Для решения задачи (RC) Ж.Б. Розеном была произведена последовательная линеаризация обратно-выпуклого ограничения в точках ук, и затем рассматривались выпуклые задачи h(x) I min, х 6 S, g(yk) + {Vg(yk),x-yk)>0

При этом точка ykJrl последовательности {yh} строилась как точное решение задачи (PL(yk)). Сходимость метода устанавливается теоремой [131, 140], говорящей о том, что если точка у* является предельной для последовательности {ук}, то она является решением линеаризованной задачи (PL(y*)). Кроме того, в точке у* выполнены необходимые условия Куна-Таккера для исходной задачи (RC).

Отметим, что эта теорема доказана в предположении компактности допустимого множества, а также точного решения вспомогательной задачи (PL(yk)). Кроме того,

PL(yk)) не очень понятно какой приближенный критерий останова использовать, и что получаем в случае выполнения этого критерия. Поэтому нами была предложена модификация метода Ж.Б. Розена (см. п. 1.2), в которой допустимое множество не обязательно является компактом, и вспомогательная задача решается приближенно. Удалось доказать теорему сходимости и разработать новый критерий останова. Эффективность предложенного метода проверена численным экспериментом (см. п. 2.2).

В работе [8] В.П. Булатова (1977 г.) задача (RC) была названа задачей минимизации "на дыре", и к ее решению был предложен итеративный процесс последовательной линеаризации "плохого" ограничения д{х) > 0, аналогичный процессу Ж.Б. Розена. Отличие состояло в том, что линеаризация производилась в другой точке ук = ук + A*dk, где dk — направляющий вектор со свойством Vh(yk)dk < 0, а Ajt — некоторое число. Доказана сходимость метода к точке Куна-Таккера в предположении компактности допустимого множества задачи.

Глубокие исследования в этой области провели Р.Ж. Хиллестад, С.И. Якобсен и П.П. Бенсел [99, 111, 112, 113]. Р.Ж. Хиллестадом в [111] рассмотрена задача линейного программирования с одним дополнительным обратно-выпуклым ограничением (ЛЗОВП — линейная задача обратно-выпуклого программирования) и к решению этой задачи предложен один метод, основанный на переборе вершин многогранника. В [99] П.П. Бенсел и С.И. Якобсен исследовали также ЛЗОВП и получили для нее специфичные необходимые и достаточные условия локального решения. На основе полученных условий предложили алгоритм решения данной задачи, но его практическое применение встречает серьезные трудности, хотя и доказана сходимость за конечное число шагов. Далее в [112, 113] Р.Ж. Хиллестад и С.И. Якобсен для решения рассматриваемой задачи развили идею комбинирования метода отсечений и перебора вершин многогранника, а также доказали, что выпуклой оболочкой допустимого множества ЛЗОВП является выпуклый многогранник. Ими был предложен алгоритм глобального поиска, в основе которого лежит метод отсечений. В настоящий момент исследование и решение ЛЗОВП продолжается С. Якобсеном и К. Мо-ширвазири [123, 124, 132].

Исследования задачи обратно-выпуклого программирования связаны также с именем X. Туя. [150,152]. Для ее решения им и его учениками разработано семейство методов отсечения, основанное на введенной X. Туем двойственности задач вогнутой минимизации (выпуклой максимизации) и обратно-выпуклого программирования и на идее ранее примененного для задачи вогнутой минимизации метода отсечений для задачи вогнутого программирования. Одним из недостатков метода отсечений в этом случае является отсутствие гарантии нахождения глобального решения. Другим существенными недостатками методов отсечения являются рост числа ограничений на каждом шаге алгоритма и тот факт, что отсекающие плоскости становятся почти параллельными через определенное количество шагов. Неэффективность метода отсечения обсуждалась в работах [100, 101, 102, 110] и подтверждена численными экспериментами в [110].

В данной работе для решения задач обратно-выпуклого программирования предложен другой подход, который основан на необходимых и достаточных условиях глобального минимума, полученных A.C. Стрекаловским в [64]. Однако, до работ [45, 147[ было не совсем ясно, является ли условие глобальной оптимальности (УГО) конструктивным для построения численных методов решения задачи (RC). Чтобы ответить на этот вопрос, заметим, что проверка УГО сводится к рассмотрению семейства задач, называемых линеаризованными:

Vg{y),x) t шах, xeS, h{x) < h(z), (LQ) где параметр у 6 Rn "бегает" по поверхности уровня функции <?(•) уе{уемп I д(у) = 0}, (10) а также к последующей проверке условия фд{у),х-у)< 0, (11) где х — решение задачи (LQ).

УГО, очевидно, сохраняет алгоритмическое свойство классических условий оптимальности, заключающееся в следующем. Если нарушено неравенство (11), то есть возможность построить точку, лучшую, чем исследуемая. Можно сказать, что обратно-выпуклая задача (RC) "стоит" семейства линеаризованных задач (LQ), зависящих от параметров, поэтому задача (RC) — несравнимо более трудная, чем выпуклая задача f(x) I min, X € D, (12) где функция /(•) выпукла и дифференцируема, а множество D выпукло, поскольку задача (12) "стоит", если так можно сказать, лишь одной линеаризованной задачи

V/(z), х) 4 nun, х € D. (10)

К тому же нетрудно заметить, что линеаризованная задача (LQ) является более трудной, нежели линеаризованная задача (10),при условии, что множества D и S будут приблизительно одинаковой структуры и сложности.

Алгоритмы глобального поиска, разработанные на основе УГО, для решения обратно-выпуклых задач были предложены в [45, 147].

В последние четыре десятилетия предметом интенсивного исследования также является перспективный и бурно развивающийся раздел оптимизации — дискретная оптимизация. Здесь разработано большое количество интересных методов поиска решения, которые получили широкое распространение (см., например, [3, 7, 23, 37, 38, 39, 83, 120]). Количество и разнообразие публикаций в этом направлении резко возросло. Существенно расширился и круг специалистов, занимающихся практическими приложениями в этой области. Можно перечислить большое количество разнообразных задач планирования экономики, управления и организации производства, проектирования техники, которые сводятся к выбору лучших в каком-то смысле значений дискретных параметров из некоторого допустимого множества [3, 7, 23, 83, 120]. Заметим, что формально математические модели, отвечающие этим разнообразным по своему содержанию задачам, мало отличаются между собой.

К точным методам в дискретной оптимизации традиционно относятся методы полного перебора, методы ветвей и границ, методы отсечений. Кроме того, в последние время возникают новые подходы к решению дискретных задач. Среди них можно выделить метод регулярных разбиений, предложенный A.A. Колоколовым [26, 38, 39], на основе которого создан метод перебора L-классов для решения задач целочисленного программирования (ЦП). Данный подход основан на лексикографическом упорядочении элементов L-разбиения релаксационного многогранника П исходной дискретной задачи и заключается в последовательном переборе и исключении L-классов с помощью решения линейных подзадач. В частности, разработаны алгоритмы перебора L-классов для задачи о многомерном рюкзаке [30], а также задач

ЦП с интервальными исходными данными [21].

Разработка точных и приближенных алгоритмов с гарантированными оценками точности для решения задач комбинаторной оптимизации, таких как дискретные задачи размещения (20, 42], задачи двухуровневого программирования [57, 126], задачи календарного планирования [18, 43], и упаковки [15, 16, 29], очень интенсивно проводится в Новосибирском научном центре по следующим направлениям:

- исследование комбинаторной сложности и построение эффективных алгоритмов, например, алгоритмов муравьиной колонии (Ant colony algorithms), основу которых составляют вероятностью жадные алгоритмы, использующие в своей работе накопленную статистическую информацию о процессе поиска [19, 95];

- разработка методов локального поиска и построение метаэвристик;

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

В данной работе рассматривается также одна задача дискретной оптимизации

- задача о многомерном рюкзаке (multiconstraint (multidimentsional) 0-1 knapsack problem) с, x) t max, а*,х)<%, j = 1,. ,m, (MKP) x G {0,l}n.

Известно [103, 129, 130, 138], что она является ./VP-трудной даже при m = 1.

Используя возможность представления задачи (МКР) в виде задачи обратно-выпуклого программирования [45, 120], для ее решения применяется стратегия глобального поиска, основанная на условиях глобальной оптимальности (УГО). Частный случай задачи (МКР) при m = 1 — задача о рюкзаке — рассмотрен в работе [45], где на впервые основе УГО проведены ее теоретические и численные исследования. Перейдем к описанию содержания диссертации.

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

Основные результаты работы заключаются в следующем.

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

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

3. На основе общей стратегии решения обратно-выпуклых задач разработан новый алгоритм приближенного решения задачи о многомерном рюкзаке, доказавший свою эффективность во время успешного вычислительного эксперимента на серии задач из ОЯ-ГЛЬгагу.

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

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

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

Заключение

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

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

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

1. Алейников В.Н. Задача оптимального размещения производства продукции одного вида // Экономика и математические методы. — 1966. — Т. 2, Вып. 2. — С. 272-282.

2. Алексеев В.М., Тихомиров В. М., Фомин С. В. Оптимальное управление. — М.: Наука, 1979.

3. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. — М.: Наука, 1987.

4. Ашманов С.А. Линейное программирование. — М.: Наука, 1981.

5. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. — М.: Мир, 1982.

6. Бахвалов Н.С. Численные методы. — М.: Наука, 1975.

7. Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. — Новосибирск: Наука, 1978.

8. Булатов В.П. Методы погружения в задачах оптимизации. Новосибирск: Наука, 1977.

9. Булатов В.П., Касинская Л.И. Некоторые методы минимизации вогнутой функции на выпуклом многограннике и их приложение // Методы оптимизации и их приложения. — Новосибирск: Наука, 1982. — С. 71-80.

10. Вагнер Г. Основы исследования операций. Т. 1. — М.: Мир, 1973.llj Васильев O.B. Лекции по методам оптимизации. — Иркутск: Изд-во Иркут. унта, 1994.12j Васильев Ф.П. Методы решения экстремальных задач. — М.: Наука, 1981.

11. Васильев Ф.П. Численные методы решения экстремальных задач — 2-е изд. перераб. и доп. — М.: Наука, 1988.

12. Васильев Ф.П. Методы оптимизации. — М.: Факториал Пресс, 2002.

13. Гвоздев С.Е. О двух задачах дискретной оптимизации // Управляемые системы.

14. Новосибирск: Институт математики СО РАН, 1979. — Вып. 19. — С. 22—30.

15. Гвоздев С.Е. Об eps-оптимальном решении некоторых дискретных экстремальных задач // Управляемые системы. — Новосибирск: Институт математики СО РАН, 1979. Вып. 19. - С. 31-39.

16. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. — М.: Мир, 1985.

17. Гимади Э.Х., Залюбовский В.В., Севастьянов C.B. Полиномиальная разрешимость задач календарного планирования с ограниченными ресурсами и директивными сроками // Дискретный анализ и исследование операций. — 2000. — Сер. 2. Т. 7, № 1. - С. 9-34.

18. Гончаров E.H., Кочетов Ю.А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения // Дискретный анализ и исследование операций. 1999. - Сер. 2. - Т. 6, № 1. - С. 12-32.

19. Гончаров E.H., Кочетов Ю.А. Вероятностный поиск с запретами для дискретных задач безусловной оптимизации // Дискретный анализ и исследование операций.- 2002. Сер. 2. - Т. 9, № 2. - С. 13-30.

20. Девятерикова М.В., Колоколов A.A. Алгоритмы перебора L-классов для задачи о рюкзаке с интервальными исходными данными // Препринт ОмГУ. — 2001.

21. Демьянов В.Ф.,Васильев Л.В., Недифференцируемая оптимизация. — М.: Наука, 1981.

22. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. — М.: Наука, 1982.

23. Евтушенко Ю.Г., Жадан В.Г. Барьерно-проективные и барьерно-ньютоновские численные методы оптимизации (случай линейного программирования). — М.: ВЦ РАН, 1992.

24. Еремеев A.B. Генетический алгоритм для задачи о наименьшем покрытии множества // Дискретный анализ и исследование операций. — Сер. 2. — 2000. — Т. 7, N 1. С. 47-60.

25. Еремеев A.B., Заозерская JI.A., Колоколов A.A. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискретный анализ и исследование операций. — Сер. 2. — 2000. — Т. 7, № 2. С. 22-46.

26. Еремин И.И. Теория линейной оптимизации. — Екатеринбург: Изд-во ИММ УрО РАН, 1998.

27. Еремин И.И., Астафьев H.H. Введение в теорию линейного и выпуклого программирования. — М.: Наука, 1976.

28. Ерзин А.И. Решение одной задачи о ранце // Управляемые системы. — Новосибирск: Институт математики СО РАН, 1989. — Вып. 29. — С. 41—56.

29. Заикина Г.М., Колоколов A.A., Леванова Т.В. Экспериментальное сравнение некоторых методов целочисленного программирования // Методы решения и анализа задач дискретной оптимизации. — Омск, 1992. — С. 25-41.

30. J31. Залесский А.Б. Невыпуклость допустимых областей и оптимизация хозяйственных решений // Экономика и математические методы. — 1980. — Т. 16, № 6. — С. 1069-1081.

31. Зангвилл И. Нелинейное программирование. Единый подход. — М.: Советское радио, 1973.

32. Иоффе А.Д., Тихомиров В.М. Теория экстремальных задач. — М.: Наука, 1974.

33. Карманов В.Г. Математическое программирование. — М.: Физматлит, 2000,

34. Касинская JI.И. Алгоритм и программа решения общей задачи выпуклого программирования методом опорного конуса. — В кн.: Алгоритмы и программы. Вып. 1. — Иркутск, 1974.

35. Кларк Ф. Оптимизация и негладкий анализ. — М.: Наука, 1988.

36. Колоколов A.A. Методы дискретной оптимизации // Учебное пособие. — Омск: Изд-во Ом ГУ, 1984.

37. Колоколов A.A. Регулярные разбиения в целочисленном программировании // Методы решения и анализа задач дискретной оптимизации. — Омск: Изд-во Ом-ГУ, 1992. С. 67-93.

38. Колоколов A.A. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журн. исслед. операций. — 1994. — Т. 1, JV» 2. — С. 18-39.

39. Колоколов A.A., Адельшин A.B., Чередова Ю.Н. Применение L-разбиения к исследованию некоторых задач выполнимости // Труды XII Байкальской международной конференции. Т. 1. — Иркутск, 2001. — С. 166-172.

40. Колоколов A.A., Девятерикова М.В. Анализ устойчивости L-разбиения множеств в конечномерном пространстве // Дискретный анализ и исследование операций. Сер. 2. - 2000. — Т. 7, № 2. — С. 47-53.

41. Кочетов Ю. А., Пащенко М.Г. Динамические задачи выбора оптимального состава системы технических средств // Дискретный анализ и исследование операций. 1995. - Сер. 2. - Т. 2, № 1. - С. 36-49.

42. Кочетов Ю.А., Столяр A.A. Поиск с запретами и чередованием окрестностей для задачи календарного планирования с ограниченными ресурсами (Принята к публикации в журнал "Дискретный анализ и исследование операций", 2004).

43. Кофман А., Анри-Лабордер А. Методы и модели исследования операций. — М.: Мир, 1977.

44. Кузнецова A.A., Стрекаловский A.C., Цэвээндорж И. Об одном подходе к решению целочисленных задач оптимизации // Журн. вычисл. матем. и матем. физики. 1999. - Т. 39, № 1. - С. 9-16.

45. Кузнецова A.A., Яковлева T.B. Численное решение задачи о рюкзаке алгоритмом с построением оценок // Информационный бюллетень JV« 10, Тезисы докладов конференции "Математическое программирование и приложения". — Екатеринбург, 2003. С. 166.

46. Кузнецова A.A., Яковлева Т.В. Об одном подходе к решению задачи о рюкзаке с построением оценок // Материалы Всероссийской научной молодежной конференции "Под знаком "Сигма"". Омск: ОНЦ СО РАН 2003. - С. 19.

47. Ландис Е.М. О функциях, представимых в виде разности двух выпуклых // Доклады Академии Наук СССР. — 1951. — Т. 80, № 1. С. 9-11.

48. Левитин Е.С. Теория возмущений в математическом программировании и ее приложения. — М.: Наука, 1992.

49. Мину М. Математическое программирование. Теория и алгоритмы. — М.: Наука, 1990.

50. Моисеев H.H., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. — М.: Наука, 1978.

51. Полак Э. Численные методы оптимизации. Единый подход. — М.: Мир, 1974.

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

53. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. — М.: Наука, 1980.

54. Пшеничный Б.Н. Метод линеаризации. — М.: Наука, 1983.

55. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. М. Наука, 1975.

56. Плясунов A.B. Об одном подходе к решению задач двухуровневого программирования // Труды XII Байкальской международной конференции, 24 июня 1 июля, 2001 г. - Т. 1. - Иркутск: Изд-во ИСЭМ СО РАН, 2001. - С. 227-231.

57. Рокафеллар Р. Выпуклый анализ. — М.: Мир, 1973.

58. Романовский И.В. Алгоритмы решения экстремальных задач. — М.: Наука, 1977.60J Стрекаловский A.C. К проблеме глобального экстремума // ДАН СССР. — 1987. Т. 292, № 5. - С. 1062-1066.

59. Стрекаловский A.C. К проблеме глобального экстремума в невыпуклых задачах оптимизации // Изв. вузов. Математика. — 1990. — № 8. — С. 74-80.

60. Стрекаловский A.C. К проблемам глобального максимума в невыпуклых экстремальных задачах // Вопросы кибернетики. Анализ больших систем /под. ред. В.В. Федорова и В.Г. Карманова. М.: АН СССР, 1992. - С. 178-197.

61. Стрекаловский А. С. К теории глобального экстремума в невыпуклых задачах оптимизации // Приближенные методы анализа и их приложения. — Иркутск: Изд-во СЭИ СО РАН СССР, 1989. С. 76-85.

62. Стрекаловский A.C. Об экстремальных задачах на дополнениях выпуклых множеств // Кибернетика и системный анализ. — 1993. — № 1. — С. 113-126.

63. Стрекаловский A.C. О поиске глобального максимума выпуклого функционала на допустимом множестве // Журн. вычисл. матем. и матем. физ. — 1993. — Т. 33, № 3. С. 349-364.

64. Стрекаловский A.C. Условия глобальной оптимальности в задачах d.c. программирования // Иркутский государственный университет, серия: Оптимизация и управление. — Иркутск, Изд-во ИГУ, 1997. — Вып. 1.

65. Стрекаловский A.C. Об экстремальных задачах с d.c. ограничениями. // Журн. вычисл. матем. и матем. физ. — 2001. — Т. 41, № 12. — С. 1833-1843.

66. Стрекаловский A.C. О минимизации разности двух выпуклых функций на допустимом множестве // Журн. вычисл. матем. и матем. физ. — 2003. — Т. 43, JY» 3. С. 399-409.

67. Стрекаловский A.C. Элементы невыпуклой оптимизации. — Новосибирск: Наука, 2003.

68. Стрекаловский A.C., Кузнецова A.A. О сходимости алгоритма глобального поиска в задаче выпуклой максимизации на допустимом множестве // Журнал Известия Вузов. Серия Математика. — 1999. — № 12. — С. 74-81.

69. Стрекаловский А.С. , Кузнецова А.А., Яковлева Т.В. О численном решении задач невыпуклой оптимизации // Сибирский журнал вычислительной математики. 2001. - Т. 4, № 2. - С. 185-199.

70. Стрекаловский А.С., Яковлева Т.В. Алгоритм глобального поиска для задач D.C.-минимизации // Информационный бюллетень № 8, Тезисы докладов конференции "Математическое программирование и приложения". — Екатеринбург. 1999. С. 257-258.

71. Стрекаловский А.С., Яковлева Т.В. О методах локального поиска для задач обратно-выпуклого программирования // Тезисы докладов. Ляпуновские чтения и презентация информационных технологий, Иркутск, 25-27 ноября 2002 г.- С. 32.

72. Стрекаловский A.C., Яковлева Т.В. О методах локального поиска для задач обратно-выпуклого программирования // Всероссийская конференция "Проблемы оптимизации и экономические приложения". Материалы конференции (Омск, 1-5 июля 2003). С. 136.

73. Стрекаловский A.C., Яковлева Т.В. О невыпуклых задачах оптимизации // Автоматика и телемеханика. — 2004. — № 3 (Принята к публикации).

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

75. Схрейвер А. Теория линейного и целочисленного программирования. Ч. 2. — М.: Мир, 1991.

76. Taxa X. Введение в иследование операций. — М.: Мир, 1985.

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

78. Цэвээндоржийн И. Некоторые вопросы поиска глобального решения обратно-выпуклых задач: Дис. канд. физ.-мат. наук. — Иркутск, 1996.

79. Экланд И., Темам Р. Выпуклый анализ и вариационные проблемы. — М.: Мир, 1979.

80. Яковлева Т.В. О численном решении задач d.c. минимизации // Оптимизация. Управление. Интеллект. — 2000. — № 5. — С. 403-413.

81. Яковлева Т.В. О численном решении задачи о рюкзаке // Труды XII Байкальской международной конференции, 24 июня 1 июля, 2001 г. — Т. 1. — Иркутск: Изд-во ИСЭМ СО РАН, 2001. - С. 296-302.

82. Яковлева Т.В., Кузнецова А.А. Решение задачи о многомерном рюкзаке // Тезисы докладов школы-семинара молодых ученых "Математическое моделирование и информационные технологии", Иркутск-Ангасолка, 23-28 сентября, 2003 г. — С. 33-34.

83. Aarts Е., Lenstra J.К. Local search in combinatorial optimizationio. — Wiley, Chichester, 1997.

84. Alexandrov D., Kochetov Y. Behavior of the ant colony algorithm for the set covering problem // Proc. of Symp. on Oper. Res. — 2000. — Springer Verlag. — P. 255-260.

85. Avriel M. Methods for Solving Signomial and Reverse Convex Programming Problems //In Avriel et al. eds., Optimization an Disign. — Prentice-Hall Inc., Englewood Cliffs, N. J., 1973. P. 307-320.

86. Avriel M., Williams A.C. Complementary Geometric Programming // SIAM Journal of Applied Mathematic. 1970. — V. 19. — P. 125-141.

87. Balas E. An Additive Algorithm for Solving Linear Programms with zero-one Variables // Operational Research Quarterly. — 1965. — V. 13. — P. 517-546.

88. Bansal P.P., Jacobsen S.E. Algorithm for Optimizing Network Flow Capacity under Economies of Scale // Journal of Optimization Theory and Applications. — 1975. — V. 15. P. 565-586.

89. Bansaad S. A Cutting Plane Algorithm for Class of Nonlinear/ 0-1 Integer Programms / in Resent Advances in Global Optimization. — Princeton University Press, 1992. P. 152-164.

90. Bansaad S., Jacobsen S.E. A Level Set Algorithm for Class of Reverse Convex Programms // Annals of Operations Research. — 1990. — V. 25. — P. 19-42.

91. Bansaad S., Jacobsen S.E. Comments on a Reverse Convex Programms // Journal of Global Optimization. 1995. - V. 5, J№ 1. - P. 95-97.

92. Chu P.C., Beasley J.E. A Genetic Algorithm for the Multidimentional Knapsack Problem // Journal of Heuristics. — 1998. — № 4. — P. 63-86.

93. Diffe W., Hellman M.E. New Directions in Cryptography // IEEE Trans. Inf. Theory, IT-36. 1976. - P. 644-654.

94. Falk J.E. Conditions for Global Optimality in Nonlinear Programming // Operations Research. 1973. — V. 21. — P. 337-310.

95. Floudas C.A., Visweswaran V. Quadratic Optimization // Handbook of Global Optimization / Ed. by Horst. R., Pardalos P. — Dordrecht: Kluwer Academic Publishers, 1995. P. 217-269.

96. Gavish B., Pirkul H. Allocation of Data Bases and Processors in a Distributed Computer System // In Akoka J. ed., Management of Distributed Data Processing, 1982. P. 215-231.

97. Gavish B., Pirkul H. Efficient Algorithms for Solving Multiconstraint zero-one Knapsack Problem to Optimality // Mathematical Programming. — 1985. — V. 31. P. 78-105.

98. Gilmore A., Gomory R. Theory and Computation Of Knapsack Problems // Operations. 1966. - V. 14. - P. 1045-1074.

99. Gurlitz M., Jacobsen S.E. On the use of Cuts in Reverse Convex Programms // Journal of Optimization Theory and Applications. 1991. - V. 68, № 2. - P. 257-274.

100. Hillestad R.J. Optimization Problems Subject to a Budget Constraint with Economies of Scale // Operations Research. — 1975. — V. 23. — P. 1091-1098.

101. Hillestad R.J., Jacobsen S.E. Reverse Convex Prigramming // Applied Mathematics and Optimization. — 1980. — № 6. — P. 63-78.

102. Hillestad R.J., Jacobsen S.E. Linear Programming with an Additional Reverse Convex Constraint // Applied Mathematics and Optimizations. — 1980. — № 6. -- P. 257-269.

103. Hiriart-Urruty J.B. e- subdifferential calculus in Convex Analysis and Optimization // Research Notes in Mathematics Series. — 1982. — V. 57. — P. 43-92.

104. Hiriart-Urruty J.B. From convex optimization to nonconvex optimization. Part I: Necessary and sufficient conditions for optimality. // Nonsmooth Optimization and Related Topics. — Plenum Press, 1989. P. 219-239.

105. Hirriart-Urruty J.B., Ledyaev Y.A. Note on the characterization of the global maxima of a (tangentialy) convex function over a convex set // Journal of Convex Analysis. 1996. - V. 3, № 1. - P. 55-61.

106. Horst R., Tuy H. Global Optimization (Deterministic Approach). — Berlin. Springer-Verlag, 1993.

107. Horst R., Pardalos P.M. (eds.) Handbook of global optimization. — Kluwer, 1995.

108. Horst R., Pardalos P.M., Thoai V. Introduction to Global Optimization. — Dordrecht: Kluwer Academic Publishers, 1995.

109. Horst R., Thoai N. V. D.C. Programming: Overview // Journal of Optimization Theory and Applications. — 1999. — V. 103, № 1. — P. 1-43.

110. Horst R., Tuy H. Global Optimization. Deterministic Approaches. — Second. Revised Edition. — Berlin: Springer-Verlag, 1993.

111. Jacobsen S., Moshirvaziri K. Computational Experience Using an Edge Search Algorithm for Linear Reverse Convex Program // Journal of Global Optimization. -1996. V. 9, № 2. - P. 153-167.

112. Jacobsen S., Moshirvaziri K. Computational Experience Using an Edge Search Algorithm for Linear Reverse Convex Programs. (To appear in Journal of global optimization).

113. Johnson D.S. Approximation Algorithms for Combinatorial Problems//J. Computer, and System Science. 1974. — V.9. - P.256-278.

114. Kochetov Yu., Plyasunov A. Efficient algorithm for a class of bilevel linear programming problems // Operations Research Proceedings 1996. — Berlin: Springer Verlag, 1997. P. 10-13.

115. Loulou R., Michaelides E. New Greedy-like Heuristic for the Multidimentional 0-1 Knapsack Problem // Operations Research. — 1979. — V. 27, № 6. P. 1101-1114.

116. Magazine M., Oguz O. A Heuristic Algorithm for the Multidimentional zero-one Knapsack Problem // European Journal of Operational Research. — 1984. — V. 16.- P. 319-326.

117. Martello S., Toth P. Knapsack Problems: Algorithms and Computer Implementations. — Chichester, UK: Wiley, 1990.

118. Martello S., Pisinger D., Toth P. New Trends in Exact Algorithms for the 0-1 Knapsack Problem // European Journal of Operational Research. — 2000. — V. 123.- P. 325-332.

119. Meyer R. The Validity of a Family of Optimization Methods // Journal SIAM Control. 1970. - V. 8, № 1. - P. 41-54.

120. Moshirvaziri K. A Cutting Plane Algorithm for Linear Reverse Convex Programs // Annals of Operations Research. 2002. - V. 105. — P. 201-212.

121. Nemhauser G., Ullmann Z. Discrete Dynamic Programming nd Capital Allocation // Management Science. 1969. - V. 15. - P. 494-505.

122. Padberg M.W., Rijal M.P. Location, scheduling, design and integer programming.

123. Boston: Kluwer Academic Publisher, 1996.

124. Pardalos P., Cupta S. A Note on a Quadratic Formulation for Linear Complementarit Problems // Journal of Optimization Theory and Applications. — 1988. V. 57. - P. 197-202.

125. Pardalos P.M., Rosen J.B. Constrained Global Optimization: Algorithms and Applications // Lecture Notes in Computer Science, 1987. — Berlin: Springer Verlag.- V. 268.

126. Pirkul H. A Heuristic Solution Procedure for the Multicinstraint Zero-one Knapsack Problem // Naval Research Logistics. — 1987. V. 34. - P. 161-172.

127. Pisinger D. Algorithms for Knapsack Problems: Ph.D. thesis. — Copenhagen, Denmark, 1995.

128. Rosen J.B. Convex Partition Programming / in R.L.Graves, P.Wolfe eds. Resent Advances in Mathematical Programming.-New York: McGraw Hill,1963.-P. 159-176.

129. Rosen J.B. Iterative Solution of Nonlinear Optimal Control Problems // Journal SIAM Control. 1966. — V. 4, 1. — P. 223-244.

130. Sinuany-Stern Z., Winer I. The one Dimentional Cutting Stock Problem Using two Objectives //Journal of the Operational Research Society. 1994. - V. 45. - P.231-236.

131. Sinha A., Zoltners A.A. The Multiple-Choice Knapsack Problem // Operations Research. 1979. - V. 27. - P. 503-515.

132. Shih W. A Branch and Bound Method for the Multicinstraint Zero-one Knapsack Problem //Journal of the Operational Research Society. 1979. - V. 30. - P.369-378.

133. Strekalovsky A.S., Tsevendorj I. Testing the ^-strategy for a Reverse Convex Problem // Journal of Global Optimization. — 1998. — V.13, № 1. — P. 61-74.

134. Strekalovsky A.S., Yakovleva T.V. On a Solving of Reverse Convex Problems // The International Conference on Optimization and Optimal Control, August 13-17, 2002, Mongolia, Ulaanbaatar. — P. 120-121.

135. Thach P.T. The Design Centering Problem as a Programming Problem // Mathemtical Programming. 1988. — V. 41. — P. 229-248.

136. Tuy H. Convex Programs with an additional Reverse Convex Constraint // Journal of Optimization Theory and Applications. — 1987. — V. 52. — P. 463-485.

137. Tuy H. D. C. Optimization: Theory, Methods and Algorithms // Handbook of Global Optimization / Ed. by Horst. R., Pardalos P. — Dordrecht: Kluwer Academic Publishers, 1995. P. 149-216.

138. Tuy H., Thuong N.V. Minimizing a Convex Function over the Complement of a Convex Set // Methods of Operations Research. — 1985. V. 49. - P. 85-89.

139. Vidigal L.M., Director S.W. A Design Centering Algorithm for Nonconvex Regions of Acceptability // IEEE Trans, on Computer Aided - Design of Integrated Circuits and Systems, CAD-I. - 1982. - P. 13-24.

140. Weingartner H., Ness D. Methods for the Solution of the Multi-dirnentional 0/1 Knapsack Problem // Operational Research Quarterly. — 1967. — V. 15. — P. 83-103.