Построение приближенных методов для некоторых классов задач нелинейной оптимизации с применением теории двойственности тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ.

Глава I. ИСХОДНАЯ ОЦЕНОЧНАЯ И ДВОЙСТВЕННАЯ ЗАДАЧИ

МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ.

§ I.I. Определения, основные обозначения, геометрическая интерпретация

§ 1.2. Некоторые свойства функции f(u)

§ 1.3. Общая схема метода решения оценочной задачи в случае конечности множества.^?

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

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

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

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

Алгоритм будем характеризовать оценками (сверху) для количества операций и объема памяти, необходимыми для решения задачи. Указанные оценки естественно рассматривать в зависимости от размерности задачи, причем важен лишь вид этих зависимостей с точностью до постоянного множителя.Далее оценку числа операций будем обозначать через Ж , а объема памяти через 01 . При этом, если оценка Ж имеет вид 3C=cf(L), где СУ0 - константа, Z - некоторый параметр, то будем писать X^f(L) или X-Olfat Аналогичные обозначения будем использовать и для объема памяти .

Оценки трудоемкости и объема памяти назовем эффективными, если они являются степенными выражениями относительно размерности задачи. Под размерностью задачи понимается число битов, необходимых для записи исходных данных задачи. Если не оговорено противное, то под знаком toy понимается логарифм по основанию два. Алгоритм будем называть эффективным, если он имеет эффективные оценки трудоемкости.

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

Будем говорить, что приближенный алгоритм решения экстремальной задачи математического программирования имеет оценку точности £ (является ъ-приближенным), £ > О если абсолютная погрешность допустимого (т.е. удовлетворяющего всем ограничениям рассматриваемой задачи) решения х , получаемого посредством данного алгоритма, не превышает величины 8 ; решение X при этом будем называть £-оптимальным (или £-приближенным). Под абсолютной погрешностью понимается величина \^{Хопг) -F(x)\, где F - целевая функция рассматриваемой задачи, а Я0пт~ оптимальное решение.Ясно,что чем меньше величина В , тем алгоритм точнее.

Далее через хпр будем обозначать приближенное (субоптимальное) решение; если хпр является £-оптимальным решением, то его будем обозначать через . Соответствующее значение целевой функции будем также обозначать через 1-пЛх) г или F&{cc) .

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

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

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

Неявное использование наряду с исходной экстремальной задачей двойственной к ней, можно найти еще в работах П.Л.Че-бышева, посвященных задаче наилучшего приближения заданной функции линейными комбинациями фиксированных функций. В настоящее время теорию двойственности можно считать в основном завершенной. Помимо схем, пригодных для исследования отдельных классов задач С14,17,22,31,42,4911, имеется универсальная схема принципа двойственности С5Щ. Применение теории двойственности душ анализа и корректировки несобственных (т.е. не имеющих решения) задач исследуется в С2И.

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

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

Д.

Здесь (j{a) - вектор-функция с неотрицательными компонентами [tr), i>=f,rn; f[ir), (ji {$), ограниченные функции; h - пъ —вектор. Под решением задачи понимается элемент множества Q . Пусть Rm- евклидово пространство размерности/71 . Определим множество Х-{иеКт\ 0} ; функцию Лаг-ранжа, соответствующую исходной задаче, [сейи функцию f(u)=triах {f(ir)-U-^(iJ)){aeX)^ тогда двойственная задача запишется в виде: тип [ф[и) + и* к). ие£

Так как функция if [и) - выпукла (§ 1.2), то отыскание ГТШ1 [}f{LL) \tt'k ) является задачей выпуклого программирования. Основная схема, по которой строятся методы решения задач выпуклого программирования, состоит из итеративных процедур, представляющих собой правила построения конечной (или бесконечной) последовательности точек UK[UK^R ), относительно которой можно утверждать, что она в том или ином смысле сходится к решению задачи выпуклого программирования. Для большинства известных методов каждая итерация, т.е. первую кч ход от и к U » состоит из двух этапов: I) выбор направления рк ,2) выбор шага оск вдоль направления рк , так,что LL = U + оск рк , Предложенный в диссертационной работе переход от ик к U**1 состоит из разбиения области неопределенности, локализующей решение задачи и содержащей ик , на две части и определения части, содержащей И

Для некоторого класса задач решение двойственной задачи может быть осуществлено алгоритмом наискорейшего спуска,сходимость этого алгоритма для случая, когда /(•) - выпукла и дифференцируема, а #.(•) {С-/, пъ) - непрерывна на замкнуfl том ограниченном множестве S $ являющемся подмножеством "R , доказана в [78]. При этом на каждой итерации метода приходится определять длину шага, применяя каждый раз процедуру одномерного поиска для наховдения минимума функции ip{U)\U- h на некотором однопараметрическом множестве. Наряду с алгоритмом наискорейшего спуска, учитывая ту или иную специфику исходной задачи, для решения двойственной могут быть применены градиентные методы [24,48,59,63,65,82].

Если относительно функции ipia) предполагать, что она определена на выпуклой замкнутой области G с/?'1 объема $-(G), то число точек области G , в которых требуется вычислить значение этой функции для уменьшения 9 до некоторой минимальной подобласти объема А , содержащей точку минимума / л » функции (р(и) + U'A , имеет вид — [36, 43] . Однако, эта оценка числа точек имеет скорее качественный характер, так как при т ^ Z для определения точек множества G-в которых требуется вычислить функцию ф{и) , необходимо выполнить ряд трудоемких вычислений.

В [64] описан алгоритм решения задач выпуклого программирования, гарантирующий уменьшение объема области,в которой локализуется оптимум, со скоростью геометрической прогрессии.

Если т —1 , то существует эффективный алгоритм Кифера

9 №

Джонсона [74l,L 4, с.54J, реализующий оценку ** C0(j —— . Если же, кроме того, ср(и) удовлетворяет некоторым дополнительным условиям (например, условию Липшица), то эффективные алгоритмы, обобщающие алгоритм Кифера-Джонсона, описаны в [613.

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

Для целочисленных задач имеет место "разрыв двойственности" - несовпадение оптимальных значений целевых функций исходной и двойственной задач. В [39,403 предлагается рассматривать функцию Лагранжа, нелинейную по двойственным переменным (переменным И ), что позволяет ликвидировать "разрыв двойственности". ^

Определим множества ^{(V^Wk/^ 14=f[ff),№g((r),<reQ} и Q&[U)= {(v,W)e£>\ip(U)-(4-U-W]^&}. Предлагаемый в диссертационной работе метод решения двойственной задачи не требует вычисления производных и непрерывности функции Лагранжа по tfzQ , он может быть использован для любой задачи математического программирования, для которой известен эффективный алгоритм нахождения элемента множества £>.{и). о

Опишем кратко содержание разделов работы и дадим характеристику их основных результатов.

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

§ 1.2 посвящен изучению некоторых свойств функции ip(u). Показано, что функция tplu) - выпукла, непрерывна.

Пусть tr£ - элемент множества {^е тогда справедливо

СВОЙСТВО I. Если и - некоторый /7£-вектор, l'={l\Uz<0}, то решение и^ исходной задачи является Ь-оптимальным решением задачи

Следующая теорема выделяет класс задач, для которых "разрыв двойственности" отсутствует. Пусть rain max L[a'4u)shoo и элемент [lf*,L?) множества Q х X является оптимальным решением двойственной задачи, т.q.L(IF*U*)=mifl max L (ir4U).

1 ue£ ireQ

Имеет место

ТЕОРЕМА I. Если для любых оптимальных решений [W, LL ) двойственной задачи значения функций константы, то каждое из решений If* исходной задачи является оптимальным.

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

Пусть число элементов множества Q - конечно, перенумеруем элементы множества Q индексом j=J,24,.п, Введем оценочную задачу: max

В § 1.3 показано, что если множество конечно, то оценочная и двойственная задачи являются задачами линейного программирования, причем эти задачи находятся в отношении взаимной двойственности (в смысле двойственности задач линейного программирования). Описывается алгоритм решения оценочной задачи, основанный на симплекс-методе [503 и методе генерации столбцов [423. Трудоемкость решения оценочной задачи определяется трудоемкостью симплекс-метода,а число ячеек памяти, требуемой для решения оценочной, а, следовательно, и двойственной задачи 0(mz),

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

С/ ва I, является £-оптимальным решением задачи п%ax{f(ir)\^(irkg(^),ecjm ^tir^fcw"), если U-<o}.

Таким образом, так как исходные данные практических задач часто задаются неточно [44], то последовательность и может быть полезна для изучения зависимости решений исходной задачи от вектора Of^^) » если же glv") "близко" к А , то тО. решение и^ практически можно считать приемлемым по точности.

Вторая глава является основной в диссертационной работе.

В ней изложен метод решения двойственной задачи для исходной задачи вида max {v|w^/l} при достаточно общих предположен? жениях. Получена оценка числа точек и€<£ , в которых требуется искать элемент множества [и) для приближенного решения двойственной задачи, и доказана оценка отклонения приближенного решения от оптимального.

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

Ограничение W^ А исходной задачи max будем называть правильным, если введение его в целевую функцию задачи max V , относящейся к какому-либо классу, с помощью множителя Лагранжа, не выводит эту новую задачу из упомянутого класса. Во второй главе рассмотрены некоторые достаточные условия, которые при /п=/ позволяют эффективно получить при-женное решение исходной задачи с правильным ограничением,после того как получено решение двойственной.

Пусть т= / , если из каких-либо априорных соображений можно задать число иъО , при котором тьп Ы{и)\а>А) = г ^иъо hun \(piU)+U' л ), то, в силу выпуклости функции ipiu), для ие£ приближенного нахождения пил 1(р{и)^и-А) может быть примеflZUZO нена процедура одномерной оптимизации. В [54] приведено несколько эффективных процедур одномерного поиска, позволяющих определить интервал значений переменной, внутри которого лежит минимум унимодальной функции. Процедуры одномерного поиска, приспособленные для алгоритма наискорейшего спуска [78] изложены в [69, 76].

В § 2.1 приведены предварительные замечания. § 2.2 посвящен описанию процедуры одномерного поиска приближенного решения задачи тип {ipiuhU'A)(яг=/), если изfl-zllzO вестен эффективный метод нахождения элемента [%t{U), yt(U)) множества Qt{iL).

Идейно эта процедура опирается на метод дихотомии (поиск Больцано). Суть этого метода состоит в том, что начальный интервал неопределенности [Orfi] делится на две равные части. В зависимости от соотношения между значением ас (U)

М А ^ в точке деления Ul=— и числом л левая или правая часть берется в качестве нового интервала. Если имеет место неравенство А , то в качестве нового интервала берется правая половина, в случае ljs(U) < А - левая. Если то точка деления является £-оптимальным решением задачи min, {tpiUW'A).

-iza^o

Таким образом, при поиске получаются интервалы, длина каждого из которых равна половине длины его предшественника. Так как выбранный интервал содержит точку приближенного решения, то, очевидно, процедура дихотомии сходится к приближенному решению задачи mm (iplul+ll-A) , причем, в силу специфики функции ip [и) , удается оценить точность решения задачи тип (ip (и)+и• А) через длину текущего интервала.

Оценка скорости сходимости метода дихотомии для исходной задачи транспортного типа (линейного программирования) при одном дополнительном линейном ограничении доказана в [56] . Эта оценка является частным случаем оценки, полученной в § 2.2.

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

Вернемся к описанию метода решения двойственной задачи в общем случае, который изложен в § 2.4. Предполагается, что из каких-либо априорных соображений известна верхняя граница для 1-й (и=17гп) компоненты вектора /и , при котором mm [ip(u) +U-А)= тип (Ф(и) + и- А).

Достаточным условием существования вектора ju. с компонентами U:<o° U=/,/77), при котором тип (ip[u)+u-A)-' //гаг-0 тш (ip {и W• А) является

ПРЕДПОЛОЖЕНИЕ. Пусть существует решение исходной задачи такое, что д((Г^)<А (условие Слейтера).

Тогда справедлива

ЛЕММА I. Пусть компоненты вектора и определены из соf(tr)-furj отношения ц-= --- Iu-Lm), тогда область неопределенности, в которой находится решение двойственной задачи mia (<fiи) А- и-к), ограничена т -мерным параллелепипедом иеХ ае Rn | pi •> /тг}.

Алгоритм решения двойственной задачи основан на следующем свойстве функции

СВОЙСТВО 2. Если при некотором т -векторе R имеют место соотношения: ' )>0, l-L' [ljslU)-A}<0, lei'; f.»{y [U)-A)=0, (через iL обозначен я-вектор с единственной ненулевой координатой L , величина которой равна единице), то для любого гя -вектора и. с компонентами U'^U-, . справедяиво неравенство it it I/O ip{u) + u-A > ipwj+U-A-s.

Идея метода решения двойственной задачи состоит в следующем: исходная область неопределенности разбивается на две равные части и определяется часть, содержащая приближенное решение двойственной задачи и т.д. В результате приходим к некоторой конечной области, содержащей приближенное решение задачи тип [(рШ)+и*А)» Имеет место

ТЕОРЕМА 5. Априорная оценка числа Т точек, в которых требуется найти элемент множества £3 {и) для получения у}-оптимального решения двойственной задачи, имеет вид: Т cj (hyi)m^ где t=max\пг,р[ max {//., max (ir)}}; при объеме требуемой памяти ячеек, где (к - объем памяти, используемый для нахождения элемента множества £?(и).

В § 2.3 доказывается ряд теорем, которые в случае /71=/, учитывая специфику множества Q некоторых задач, позволяют получить приближенное решение исходной задачи после того как получено решение двойственной.

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

В работах [2,9,10,57,77,81] предлагаются £-приближенные ( любое положительное число) методы решения некоторых дискретных задач. В [9] проведен анализ приближенных алгоритмов, определен класс быстрых алгоритмов, т.е. &-приближенных алгоритмов, трудоемкость и память которых ограничены сверху полиномами от числа переменных и &ч . Построение быстрых алгоритмов для большинства дискретных оптимизационных задач является проблематичным делом. Так, например, для двумерной задачи о ранце специального вида (§ 3.6) существование быстрого алгоритма ее решения означало бы совпадение классов задач, решаемых за полиномиальное время, и классов задач, решаемых с помощью перебора конечномерных булевых векторов [19]. В настоящее время вопрос о совпадении этих классов не решен. Следует отметить работу [34], в которой изучаются возможности приближенных алгоритмов градиентного типа для решения задач дискретной оптимизации.

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

В § 3.1 приведены предварительные замечания.

В §§ 3.2-3.7 приведен перечень основных задач, для которых получена оценка точности и трудоемкости приближенного решения. Точность решения является оценкой сверху для "разрыва двойственности" рассматриваемых дискретных задач. Алгоритмы решения приведенных задач основаны на теоремах § 2.3.

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

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

Основные результаты диссертации опубликованы в работах

С83-89Ц и докладывались на 1У, У Всесоюзных конференциях по проблемам теоретической кибернетики (г.Новосибирск,1977,1980), на 1У, У Всесоюзных семинарах по комбинаторному анализу (г.Москва, 1978,1981), на ЗУ Сибирской школе-семинаре по методам оптимизации и их приложениям (оз.Байкал, 1978), на Семинаре по дискретной оптимизации (г.Симферополь, 1983), на Всесоюзной конференции по проблемам теоретической кибернетики (г.Саратов, 1983), а также на семинарах в Институте математики СО АН СССР.

Автор выражает искреннюю признательность научному руководителю Э.Х.Гимади за постоянное внимание и всестороннюю поддержку, и Н.И.Глебову за советы и критические замечания, оказанные при выполнении данной работы.

1. Ахо А., Хонкрофт Дж., Ульям Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979. - 535 с.

2. Бабат Л.Г. Линейные функции на /г-мерном единичном кубе,-Докл.АН СССР, 1975, т. 221, № 4, с. 761-762.

3. Бабат Л.Г. Приближенное вычисление линейной функции на вершинах единичного /У-*лерного куба. В сб.: Исследования по дискретной оптимизации. М.: Наука, 1976, с.156-169.

4. Беллман Р. Динамическое программирование. М.: Иностран. лит., I960. - 400 с.

5. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М.: Наука, 1965. - 458 с.

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

7. Вагнер Г. Основы исследования операций, т. 2. М.: Мир, 1973. - 488 с.

8. Гвоздев С.Е. Об одном обобщении задачи о ранце. В кн.: Управляемые системы. Новосибирск, 1976, вып.15, с.16-31.

9. Гене Г.В., Левнер Е.В. Дискретные оптимизационные задачи и эффективные алгоритмы (обзор). Изв. АН СССР.Техн.ки-бернет., 1979, №6, с. 9-20.

10. Гене Г.В., Левнер Е.В. Эффективные приближенные алгоритмы для комбинаторных задач. Препринт ЦЭМИ АН СССР, М., 1981. - 66 с.

11. Глебов Н.И. Об одном классе задач выпуклого целочисленного программирования. В кн.: Управляемые системы. Новосибирск, 1973, вып. II, с. 38-42.

12. Глебов Н.И. О применимости метода покоординатного спуска к некоторым задачам выпуклого целочисленного программирования. В кн.: Управляемые системы. Новосибирск, 1978, вып. 17, с. 52-59.

13. Голыптейн Е.Г. Выпуклое программирование. Элементы теории. М.: Наука, 1979. - 68 с.

14. Голыптейн Е.Г. Теория двойственности в математическом программировании и ее приложения. М.: Наука, 1971.-352 с.

15. Гурин Л.С., Дымарский Я.С., Меркулов А.Д. Задачи и методы оптимального распределения ресурсов. М.: Сов.радио, 1968. - 464 с.

16. Гэри М., Джонсон Д. Вычислительные машины и труднореша-емые задачи. М.: Мир, 1982. 416 с.

17. Данциг Дж. Линейное программирование, его приложения и обобщения. М.: Прогресс, 1966. - 600 с.

18. Демьянов В.Ф. Задачи негладкой оптимизации и квазидифференциалы. -Изв. АН СССР. Техн.кибернет., 1983, № I, с. 9-19.

19. Диниц Е.А. Задача булева программирования при ограничениях одного знака. В сб.: Системы программного обеспечения решения задач оптимального планирования. М.: ЦЭМИ АН СССР, 1978.

20. Диниц Е.А., Кронрод М.А. Один алгоритм решения задачи о назначении. Докл.АН СССР, 1969, т. 189, № I, с. 23-25.

21. Еремин И.И. Двойственность для несобственных задач линейного и выпуклого программирования и методы их коррекции.-Изв. АН СССР, Техн.кибернет., 1983, № I, с. 20-32.

22. Зангвилл JI.С. Нелинейное программирование. Единый подход. М.: Сов.радио, 1973. - 312 с.

23. Зойтендейк Г. Методы возможных направлений. М.:Иностр. лит., 1963. - 176 с.

24. Зуховицкий С.И., Авдеев Л.И. Линейное и выпуклое программирование. М.: Наука, 1967. - 460 с.

25. Зыков А.А. Теория графов, т. I. Новосибирск:Наука,1969. 544 с.

26. Ильин В.А., Садовский В.А., Сендов Бл.Х. Математический анализ. М.: Наука, 1979. - 720 с.

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

28. Канторович Л.В., Горстко А.Б. Оптимальные решения в экономике. М.: Наука, 1972. - 232 с.

29. Канторович Л.В., Михалевич B.C., ^бинштейн Г.Ш. и др. XI Международный симпозиум по математическому программированию. -Изв. АН СССР. Техн.кибернет., 1983, № I,c.I97-201.

30. Карзанов А.В. Экономные реализации алгоритмов Эдмондса нахождения паросочетания максимальной мощности и максимального веса. В сб.: Исследования по дискретной оптимизации. М.: Наука, 1976, с. 306-327.

31. Карлин С. Математические методы в теории игр, программировании и экономике. М.: Наука, 1964. - 838 с.

32. Карп P.M. Сводимость комбинаторных проблем. Кибернетический сборник, новая серия, вып. 12, М., 1975, с.16-38.

33. Корбут А.А., Финкелынтейн Ю.Ю. Дискретное программирование. М.: Наука, 1969. - 368 с.

34. Котов В.М. Анализ градиентных алгоритмов в дискретной оптимизации. Дис. . канд.физ.-мат.наук. - Минск, 1983. 114 с.

35. Кронрод М.А. Оптимальный алгоритм упорядочения без рабочей памяти. Докл. АН СССР, 1969, т. 186, № 6, с. 12561258.

36. Кузовкин А.И., Тихомиров В.М. О количестве вычисления для нахождения минимума выпуклой функции. Экономика и математич. методы, 1967, т. 3, вып. I, с. 95-103.

37. Кук С.А. Сложность процедур вывода теорем. Кибернетический сборник, новая серия, вып. 12, М., 1975, с. 5-15.

38. Лебедев С.С. Целочисленное программирование и множители Лагранжа. Экономика и математич. методы, 1974, т. 10, вып. 3, с. 592-610.

39. Лебедев С.С., Шейман O.K. Двойственность в целочисленном программировании. Экономика и математич.методы, 1981, т. 17, вып. 3, с. 593-608.

40. Лебедев С.С., Шейман O.K. Двойственный подход в целочисленном программировании. Изв. АН СССР. Техн.кибернет., 1983, № I, с. I8I-I87.

41. Левин А.Ю. Об одном алгоритме минимизации выпуклых функций. Докл. АН СССР, 1965, т. 160, № 6, с. 1244-1247.

42. Лесдон Л.С. Оптимизация больших систем. М.: Наука,1975. - 432 с.

43. Математика и кибернетика в экономике. Словарь-справочник. 2-е изд., перераб. и доп.- М.: Экономика, 1975. 700 с.

44. Моргенштерн 0. О точности экономико-статистических наблюдений. М.: Статистика, 1968. - 296 с.

45. Морозов С.А. О задаче нахождения кратчайшего связывающего дерева с ограничением. В кн.: Управляемые системы. Новосибирск, 1976, вып. 15, с. 40-47.

46. Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование. Новосибирск: Наука, 1977. - 320 с.

47. Прим Р.К. Кратчайшие связывающие сети и некоторые обобщения. Кибернетический сборник, 1961, № 2, с. 16-38.

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

49. Рокафеллар Р. Выпуклый анализ М.: Мир, 1973. - 470 с.

50. Рубинштейн Г.Ш. Конечномерные модели оптимизации. Новосибирск: НГУ, 1970. - 230 с.

51. Рубинштейн Г.Ш. Двойственные экстремальные задачи. Докл. АН СССР, 1963, т. 152, № 2, с. 288-291.

52. Саати Т.Л. Математические методы исследования операций.-М.: Воениздат, 1963. 420 с.

53. Саати Т.Л. Целочисленные методы оптимизации и связанные с ними проблемы. М.: Мир, 1963. - 304 с.

54. Уайлд Д.Дж. Методы поиска экстремума. М.: Наука,1967. -268 с.

55. Фиакко А., Мак-Кормик Г. Нелинейное программирование. -М.: Мир, 1972. 240 с.

56. Финкелыптейн Ю.Ю. Итеративный метод дщя решения транспортной задачи с дополнительным ограничением и оценка числа . итераций. Журн. вычислит, математики и мат. физики,1963, т. 3, № 6, с. II03-IIII.

57. Финкелыптейн Ю.Ю. О полиномиальном алгоритме «^-оптимизации в многомерной задаче о ранце. Журн. вычислит.математики и мат. физики, 1980, т. 20, № 3, с. 800-802.

58. Хачиян Л.Г. Полиномиальный алгоритм в линейном программировании. Докл. АН СССР, 1979, т. 244, В 5, с. 10931096.

59. Хедли Д. Нелинейное и динамическое программирование. -М.: Мир, 1967. 506 с.

60. Чернов Ю.П. О задачах дробного программирования с линейными, сепарабельными и квадратичными функциями. Экономика и математич. методы, 197I, т. 7, вып. 5, с.721-732.

61. Черноусько Ф.Л. Об одном поиске экстремума унимодальных функций. Журн. вычислит, математики и мат. физики,1970, т. 10, № 4, с. 922-933.

62. Шварцман А.И. Об одном алгоритме дробно-линейного программирования. Экономика и математич. методы, 1965, т. I, вып. 4, с. 558-565.

63. Шор Н.З. Обобщенные градиентные методы минимизации негладких функций и их применение к задачам математического программирования (обзор). Экономика и математич.методы, 1976, т. 12, вып. 2, с. 337-356.

64. Шор Н.З. Метод отсечения с растяжением пространства для решения задач выпуклого программирования. Кибернетика, 1977, В I, с. 94-95.

65. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наук.думка, 1979. - 199 с.

66. Эрроу К., Гурвиц Л., Удзава X. Исследования по линейному и нелинейному программированию. М.: Иностр. лит.,1962.-334 с.-к # *

67. Edmonds J., Karp R.M. Theoretical impruvements in algo-rithmik efficiency for network flow problems. J. of ACM, 1972, v. 19» N 2, p. 248-264.

68. Everett H. Generalized langrange multiplier method for solving problems of optimum allocation of resources.Operations Res., 1963, 11, p. 399-417.

69. Fletcher R., Powell M.J. A rapidly convergent discent method for minimization. Computer. J., v. 6, July 1963, p. 163-168.

70. Fletcher R., Reeves C.M. Function minimization by conjugate gradients. Computer. J., July 1964.

71. Gilmore P.C., Gomory R.E. A Linear Programming Approach to the Cutting Stock Problem. Part II. Operations Res., Nov.-Dec. 1963, p. 863-888.

72. Goldfarb D. Extention of Davidonfs variable metric method to maximization under linear equality and inequality constraints. J. SIAM Appl. Math., 1969, 17» N 4,p. 739-764.

73. Ibarra O.H., Kim C.E. Fast algorithms for the knapsack problem and some subset problems. J. ACM, 1975, v. 22, N 4, p. 463-468.

74. Kiefer J. Sequential minimax search for a maximum.-Proc. Amer. Math. Soc., 1953, 4, N 3, P. 502-506.

75. Kruskal J.B. On the Shortest Spanning Subtree of a Graph and the Travelling Salesman Problem. Proc. Amer. Math. Soc., 1956, 7, P. 48-50.

76. Lasdon L.S., Y/aren A.D. Mathematical programming for optimal Dezign. Electro-Technology, Nov, 1967, p. 53-71.

77. Lawler E.L. Past approximation algorithms for knapsack problems. Math, of Oper. Res., 1979, v. 4, p.339-356.

78. Rosen J.B. The gradient projection method for programming, parts I and II. J. Coc. Industr. Appl. Math., 1960, 8, p. 181-217; 1961, 9, p. 514-532.

79. Sahni S. Approximate algorithms for the 0/1 knapsack problem. J. Assoc. Comput. Math., 1975, v. 22,p.115-124.

80. Sahni S. Algorithms for scheduling independent tasks. -J. ACM, 1976, v. 23, U 1, P.

81. Sahni S. General techniques for combinatorial approximation. Oper. Res., 1977, v. 25, p. 920-936.

82. Гвоздев С.Е. Об одном алгоритме с оценками дош решения некоторых задач математического программирования.I.-В кн.: Управляемые системы. Новосибирск, 1977, вып. 16, с.47-62; П,Ш В кн.: Управляемые системы. Новосибирск,1978,вып.17, с. 13-45.

83. Гвоздев С.Е. О двух задачах дискретной оптимизации.В кн.: Управляемые системы. Новосибирск, 1979, вып. 19, с. 22-30.

84. Гвоздев С.Е. Об &-оптимальном решении некоторых дискретных экстремальных задач. В кн.: Управляемые системы. Новосибирск, 1979, вып. 19, с. 31-39.

85. У Всесоюзная конференция по проблемам теоретической кибернетики (18-20 июня 1980): Тез. докл./ Академ.наук СССР. Сиб.отдел. Ин-т матем. Новосибирск: 1980. - 202 с.

86. ХХУ Областная научно-техническая конференция (15-16 алр.1982): Тез. докл. секции "Вычислит.техн. и систем.анализ" /Науч.-техн. общество радиотех., электрон, и связи им.А.С. Попова. Новосибирск: 1982. - 95 с.

87. Региональная научно-техническая конференция (22-23 апр.1983): Тез. докл. секции "Вычислит.техн. и дискретная ма-темат."/Науч.-техн. общество радиотех., электрон, и связи им. А.С.Попова. Новосибирск: 1983. - 90 с.