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

ВВЕДЕНИЕ.

Глава I. МЕТОДЫ ПОСЛЕДОВАТЕЛЬНОГО АНАЛИЗА РЕШЕНИЙ

ЧАСТИЧНО ЦЕЛОЧИСЛЕННЫХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

§ I.I. Схема последовательного анализа решений.

§ 1.2. Оператор аппроксимации множества допустимых решений частично целочисленной задачи линейного программирования и его реализация.

§ 1.3. Процедура локализации области оптимума.

Глава 2. АЛГОРИТМЫ СХЕМЫ ПОСЛЕДОВАТЕЛЬНОГО АНАЛИЗА РЕШЕНИЙ И ИХ ПРИМЕНЕНИЕ В УСЛОВИЯХ ФУНКЦИОНИРОВАНИЯ СИСТЕМ ОТРАСЛЕВОГО ПЛАНИРОВАНИЯ

§ 2.1. Алгоритмы последовательного анализа решений частично целочисленных задач линейного программирования.

§ 2.2. Нахождение приближенных решений частично целочисленной задачи линейного программирования.

§ 2.3. Постановка задачи математического программирования выбора годовой производственной программы в отраслевых системах.

§ 2.4. Методы последовательного анализа решений многокритериальных задач отраслевого планирования

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

Глава 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ РЕШЕНИЯ ЧАСТИЧНО ЦЕЛОЧИСЛЕННЫХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

§ 3.1. Программная реализация алгоритмов оптимизации частично целочисленных задач линейного программирования.

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

§ 3.3. Диалоговая система многокритериальной оптимизации (ДИСМОП).

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

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

В настоящее время в области дискретной оптимизации ведутся интенсивные исследования по разработке методов решения различных классов задач. Наиболее изученными являются задачи линейного и выпуклого, в основном сепарабельного, программирования с ограничениями специальной структуры. Развит целый ряд методов нахождения решений (как точных, так и приближенных) различных классов задач дискретной оптимизации. В этой связи следует отметить работы Михалевича B.C., Журавлева Ю.И., Сергиенко И.В., Емеличе-ва В.А., Хачатурова В.Р., Данцига Дж., Бендерса Дж. и других как советских, так и зарубежных ученых.

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

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

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

Опубликованный в I960 году метод Данцига-Вульфа [26 ] положил начало обширным публикациям по математическому программированию в условиях большой размерности. Метод оказался особенно эффективным для решения линейных задач, матрица условий которых имеет блочно-диагональную структуру с небольшим числом связывающих ограничений. Основная идея этого метода - принцип генерации столбцов - в дальнейшем была плодотворно использована для разработки методов решения и более общих классов задач [з,23,53,103, На основе принципа генерации столбцов был разработан и ряд методов решения задач, имеющих целочисленные переменные [пэ]. Основной трудностью этих методов в отличие от метода Данцига

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

Большое число работ, посвященных вопросам целочисленной оптимизации, основано на использовании двойственного подхода. При этом широко используется классический лагранжев подход [22, 37,53,71,85,106,I2l], его обобщение для линейных задач с целочисленными переменными, использующее понятие функций цен [37, 101,123], а также разработанная в последнее время теория суррогатной двойственности ^105,107,108,112]. Одним из основных вопросов интенсивно развивающейся теории двойственности в математическом программировании является установление взаимосвязей между решениями прямой и двойственной задачи [40,53,71,85]. Так для достаточно широких классов задач разработан целый ряд как необ-ходимох, так и достаточных условий совпадения оптимальных значений прямой и двойственной задач, то есть условий, при которых двойственный зазор [53,118] равен нулю или "незначительно" отличается от нуля. Двойственный подход положен в основу целого ряда алгоритмов [юз, 104,118], которые успешно использовались для решения практических задач. Вместе с тем непосредственное использование этого подхода столкнулось с целым рядом трудностей, связанных в основном с наличием ненулевого двойственного зазора, существенно ограничивающих эффективность двойственного подхода. Поэтому во многих работах отмечается целесообразность использования этого подхода в алгоритмах решения задач с целочисленными переменными в качестве их составной части. Так в f106J предлагается использование двойственного подхода в некоторой схеме ветвей и границ для нахождения оценок в задачах - кандидатах.

Методы разделения и фиксации переменных обычно используются в задачах математического программирования, в которых поиск экстремума по некоторой группе переменных при фиксированном значении остальных переменных осуществляется сравнительно просто [з, 50,53,68,92,Пб]. В методе, предложенном Дж.Беццерсом [юо], задача частично целочисленного программирования сведена к задаче целочисленного программирования с очень большим числом ограничений. Решение этой задачи осуществляется с помощью процедуры релаксации Джеофриона [бз], при этом дополнительные ограничения, вводимые на каждом шаге этой процедуры, определяются в результате решения некоторой задачи линейного программирования, то есть в отличие от метода Данцига-Вульфа генерируются не столбцы, а новые переменные. Идеи, использованные в алгоритме Бендерса, развивались в целом ряде работ, посвященных решению частично целочисленных задач. Так, в работах Сергиенко И.В. и его учеников [l,24, 25,74-78] метод Бендерса развит для более общих классов частично целочисленных задач. В работах Лебедева В.Ю., Сергиенко И.В., Лебедевой Т.Т. и Рощин В.А. [49,72,78] были разработаны алгоритмы типа Бендерса для приближенного решения частично целочисленных задач, так как точное решение основной целочисленной задачи при все возрастающем числе ограничений может оказаться весьма трудным.

Универсальной и гибкой схемой решения задач целочисленного программирования является метод ветвей и границ [27,40,44,45,106, 120], представляющий собой направленный перебор с отсеиванием неперспективных подмножеств решений.

Впервые идея метода была использована в работах Лэнда и Дойга [lI4] и позднее Литла и др. [пб]. В настоящее время эти схемы конкретизированы для многих классов задач целочисленной оптимизации, причем количество новых алгоритмов, основанных на методе ветвей и границ, быстро возрастает. Схема ветвей и границ является достаточно мощным средством формирования алгоритмов решения целочисленных задач [б7,79,92,95,96,99,102,117], эффективность которых существенно зависит от соответствующего выбора способов ветвления, пересчета оценок и вычисления допустимых решений.

Одним из ранних методов дискретной оптимизации является опубликованный в 1958 году алгоритм Гомори [l09], реализующий идею методов отсечений. На его основе были построены алгоритмы решения выпуклых целочисленных и некоторых невыпуклых задач [16, 45,86,88,93,97,98,110,III]. При этом рассматривались различные модификации вводимых отсечений: усиленные отсечения ^16,86,88,89, 9з], отсечения Келли [из] и его модификации [l22], отсечения Гловера fl08], учитывалась возможность появления ошибок округления [86,9l]. Методы отсечений используются для решения задач небольших размеров [45]. Дальнейшее усовершенствование методов за счет усиления отсечений и выделения отдельных классов решаемых задач может привести к увеличению их эффективности [4б].

В середине 60-х годов В.А.Емеличевым была предложена схема методов построения последовательности планов, на основе которой был разработан целый ряд как точных, так и приближенных алгоритмов решения задач дискретной оптимизации [29-31,33,34]. Общий формализм метода для решения задач дискретной оптимизации разработан в £29,Зо]. Сущность метода состоит в замене исходной экстремальной задачи более простой вспомогательной задачей, для которой существует алгоритм нахождения не только оптимального плана, но и следующих за ним в порядке ухудшения новой целевой функции с пропуском заведомо неоптимальных. Метод построения последовательности планов представляет собой универсальную схему решения задач дискретной оптимизации, которая объединяет многие известные методы (см. [33,34,40]). На ее основе осуществлена конкретизация алгоритмов решения разнообразных задач дискретного программирования [28,38,41,42], целочисленного линейного программирования [30,34,39], задач размещения производства [э2,34]и другие.

Среди общих методов решения оптимизационных задач отметим локальный подход, предложенный в дискретном анализе Ю.И.Журавлевым [35]. Впервые локальный подход был использован для решения задачи булевого линейного программирования [зб]. В [87] на основе локального подхода были разработаны декомпозиционные алгоритмы решения задач дискретного программирования квазиблочной структуры.

Одной из универсальных схем решения задач оптимизации является также схема последовательного анализа решений (вариантов), общий формализм которой разработан в начале 60-х годов В.С.Миха-левичем [17,54,61-66]. Общая методика этого подхода заключается в необходимости построения операторов анализа множества возможных вариантов решения задачи, которые позволяют отсеивать множества заведомо бесперспективных вариантов по мере того, как; бесперспективность удается обнаружить. Схема последовательного анализа решений (вариантов) является гибкой и общей, в нее вкладываются, например, методы динамического программирования, методы ветвей и границ и другие [61,84]. Вместе с тем, на ее основе был разработан ряд принципиально новых алгоритмов решения различных классов задач дискретного программирования [ 7,17,40,61,80-82].

Использование последовательной декомпозиции в схеме последовательного анализа вариантов позволило снять некоторые ограни

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

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

Конкретные декомпозиционные алгоритмы этой схемы применялись для решения динамических задач дискретной оптимизации [83, 84]. Одной из наиболее распространенных конкретизаций схемы последовательного анализа решений в дискретном программировании является метод пошагового конструирования решений [17,40,65]. Наряду с известными достоинствами алгоритмы пошагового конструирования решений обладают и определенными недостатками. Так, они, как правило, предъявляют чрезмерные требования к оперативной памяти ЭВМ, с ростом числа ограничений задачи резко возрастает объем вычислительной работы для поиска оптимального решения.

Эти факты подтверждаются как результатами вычислительных экспериментов, так и теоретическими оценками [48].

В работах В.Л.Волковича и А.Ф.Волошина [б,7,11-13,15,56] предложена схема решения задач дискретной оптимизации, в которой и -»-» о не используется идея пошагового конструирования решении. В этой схеме правила отсева применяются по всем частичным решениям единичной длины. Тем самым исчезает необходимость в запоминании на кавдом шаге множества "недоминируемых" частичных решений, устраняется "несимметричность" в анализе компонент решений.

Вычислительные эксперименты и решение практических задач продемонстрировали эффективность этого метода при решении задач достаточно большой размерности [7,7б], а также показали необходимость их дальнейшего совершенствования. Дальнейшее развитие этого метода за счет увеличения длины анализируемых частичных решений привело к декомпозиционному методу последовательного анализа решений [в,9,10,57,58,69,70]. Следует отметить, что некоторые элементы декомпозиционной схемы последовательного анализа решений (ветвление исходной задачи по целевой функции и связанный с этим ветвлением критерий оптимизации) близки в идейном отношении известному аппроксимационно-комбинаторному методу, развиваемому в работах Хачатурова В.Р. [36,43,90]. Основу этого метода составляет построение (ввбор) аппроксимирующей функции (или нескольких функций) и построения с ее помощью множества всех решений, которые отличаются значениями на аппроксимирующей функции от ее оптимума не более, чем на определенную заранее величину. Экстремум целевой функции ищется затем на указанном множестве решений.

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

Ее основной целью является;

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

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

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

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

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

Разработан и реализован на ЭВМ комплекс программ, из базисных модулей которого в автоматическом или диалоговом режиме осуществляется формирование ряда алгоритмов данной схемы решения указанных задач.

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

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

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

Разработанные алгоритмы включены в пакет прикладных программ "Диалоговая система многокритериальной оптимизации", разработанной в Ж АН УССР в рамках темы "Разработать и ввести в эксплуатацию комплекс прикладных программ на ЕС ЭВМ для решения задач многокритериальной оптимизации" по постановлению ГКНТ СССР от 12.12.80 г. № 472/248 в соответствии с программой работ по проблеме 0.80.21 (задание 02.09, номер государственной регистрации 81085927) и распоряжением Президиума АН УССР № 353 от 3.03.1981 г. Результаты, полученные в диссертационной работе, внедрены в научно-исследовательской организации одной из машиностроительных отраслей промышленности при выполнении работ по теме "Разработка программных модулей решения задач оптимизации структурного подразделения отрасли в многокритериальной и одно-критериальной постановках" в рамках опытно-конструкторской работы "Разработка и внедрение комплексных типовых прикладных программных средств общесистемного и функционального назначения, прогрессивной технологии создания программных средств и автоматизированных систем проектирования АСУ" для решения задач оптимизации в структурных подразделениях отрасли, обеспечивают экономию машинного времени, улучшают качество принимаемых решений, обеспечивают сбалансированность плановых решений по многим критериям. Экономический эффект от внедрения результатов диссертации составляет 92,137 тыс.рублей.

Диссертационная работа состоит из трех глав, заключения, списка литературы и приложения.

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

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

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

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

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

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

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

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

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

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

В третьей главе описывается разработанный и реализованный на ЭВМ программный комплекс (§ 3.1), который обеспечивает формирование некоторого подмножества алгоритмов схемы последовательного анализа решений из набора базисных программных модулей.

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

В § 3.3 описывается пакет прикладных программ "диалоговая Система Многокритериальной оптимизации" (ППП ДИСМОП), в состав которого включен описанный в настоящей работе программный комплекс. При этом основное внимание уделено описанию тех частей ППП ДИСМОП, в разработке и реализации которых автор принимал непосредственное участие.

В заключении формулируются основные результаты, полученные в работе.

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

Основные результаты диссертационной работы докладывались и обсуждались на следующих республиканских семинарах Научного совета АН УССР по проблеме "Кибернетика": в Институте кибернетики им. В.М.Глушкова АН УССР "Системные методы в задачах проектирования сложных управляющих комплексов", "Математическое обеспечение автоматизированных систем обработки данных и пакетов прикладных программ", в Киевском госуниверситете "Моделирование и оптимизация систем управления", а также на республиканском семинаре "Meтоды дискретной оптимизации и их программное обеспечение (Ужгород, 1983 г.), на П Всесоюзной конференции по проблемам управления развитием систем (Таллин, 1982 г.), на республиканской конференции молодых ученых по проблемам технической кибернетики (Киев, 1984 г.) и опубликованы в работах [б!,52,59,60,7о].

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

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

2. На основе алгоритмической схемы разработаны и исследованы алгоритмы (в том числе и декомпозиционные) поиска решений указанного класса задач математического программирования. Исследовано применение этих алгоритмов в режиме диалоговой оптимизации.

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

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

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

5. Созданный программный комплекс включен в состав пакета прикладных программ "Диалоговая система многокритериальной оптимизации" как часть его математического обеспечения. Полученные в работе результаты внедрены в научно-исследовательской организации одной из машиностроительных отраслей промышленности. Экономический эффект от внедрения результатов диссертационной работы составляет 92,137 тыс.рублей.

ЗАКЛЮЧЕНИЕ

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

1. Артеменко В.И. Об одном методе поиска приближенных решений задач частично целочисленного линейного программирования.- Кибернетика, 1981, № 1. с.82-85.

2. Бункин В.А., Колев Данго, Курицкий Б.Я., Максименко А.Н., Сокуренко Ю.А., Стоев Александр. Справочник по оптимизационным задачам в АСУ.- "Машиностроение", Л., 1984.- 212 с.

3. Верина Л.Ф., Танаев B.C. Декомпозиционные подходы к решению задач математического программирования.- Эконом, и ма-тем.методы, 1975, т.XI, J£ 6, с.1160-1172.

4. Волкович В.Л., Волошин А.Ф. Об одном алгоритме решения задачи дискретного сепарабельного программирования.- В кн.: Исследование операций и АСУ. К.: Вища школа, 1977, вып.9, с.33-41.

5. Волкович В.Л., Волошин А.Ф. Об одной схеме метода последовательного анализа и отсеивания вариантов.- Кибернетика, 1978, № 4, с.98-105.

6. Волкович В.Л., Волошин А.Ф., Поздняков Ю.М. Декомпозиция в задачах дискретного сепарабедьного программирования.- К., 1979.- 22 с. (Препринт ИК АН УССР, № 79-18).

7. Волкович В.Л., Волошин А.Ф., Поздняков Ю.М. Декомпозиция в задачах структурного проектирования сложных систем по критерию надежности.- В кн.: Тезисы докладов Ш Всесоюзной конференции по исследованию операций. Горький, 1978, с.29-30.

8. Волкович В.Л., Волошин А.Ф., Мальцев В.В., Даргейко Л.Ф., Горлова Т.М. Методы и алгоритмы автоматизированного проектирования сложных систем управления.- Наукова думка, Киев, 1984.- 208 с.

9. Волошин А.Ф. Алгоритмы решения задач линейного программирования с булевыми переменными.- В кн.: Вычислительная математика в современном научно-техническом прогрессе. К.: ИК АН УССР, 1974, с.96-101.

10. Волошин А.Ф. Об одном методе оптимизации целочисленных моделей.- В кн.: Моделирование и оптимизация систем управления. К.: Вища школа, 1974, с.58-65.

11. Волошин А.Ф., Поздняков Ю.М. Алгоритмы диалоговой оптимизации проектирования сложных систем по критерию надежности. В кн.: Ш Всесоюзная конференция по оптимальному управлению в механических системах. Тезисы докладов. Киев, 1979, с.129-130.

12. Волошин А.Ф. Нахождение субоптимальных решений в дискретных оптимизационных задачах методом последовательного анализа и отсева вариантов.- В кн.: Вычислительные аспекты в пакетах прикладных программ. К.: ИК АН УССР, 1980, с.25-35.

13. Вотяков А.А. Целочисленное программирование. Сравнение отсечений. Экономика и матем.методы, 1972, т.УШ, № I,с.107-117.

14. Вычислительные методы выбора оптимальных решений. / Под общей редакцией Михалевича B.C.- К.: Наукова думка, 1977.178 с.

15. Глушков В.М. Дисплан - новая технология планирования.- Управляющие системы и машины, 1980, № 6, с.5-11.

16. Глушков В.М. 0 системной оптимизации.- Кибернетика, 1980, № 5, с.89-90.

17. Глушков В.М., Михалевич B.C., Волкович B.JI., Доленко Г.А. К вопросу системной оптимизации в многокритериальных задачах линейного программирования.- Кибернетика, 1982, № 3, с.4-9.

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

19. Голыитейн Е.Г., Юдин Д.Б. Новые направления в линейном программировании.- М.: Советское радио, 1966.- 524 с.

20. Гуляницкий Л.Ф. Об одном семействе итерационных алгоритмов дискретной оптимизации.- В кн.: Разработка математических и технических средств АСУ. Киев: ИК АН УССР, 1978, с.25-30.

21. Гуляницкий Л.Ф., Сергиенко И.В., Ходзинский А.И. Диалоговый пакет программ ВЕКТОР-2. Киев: 1981. - 55 с. (Препринт

22. АН УССР, Ин-т кибернетики, 81-63).

23. Данциг Дж., Вульф П. Алгоритм разложения для задач линейного программирования.- Математика, 1964, т.8, № I, с.151-160.

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

25. Емеличев В.А. Вогнутое программирование с сепарабель-ной функцией цели при линейных ограничениях.- Изв.АН БССР, Сер. Физ.-мат.наук, 1969, № 6, с.25-28.

26. Емеличев В.А. К задачам дискретной оптимизации.- ДАН СССР', 1970, т. 192, № 5, с.1002-1003.

27. Емеличев В.А. К теории дискретной оптимизации. ДАН СССР, 1971; т.198, № 2, с.273-276.

28. Емеличев В.А. Дискретная оптимизация. Последовательные схемы решения. 1,П. Кибернетика, 1971, № 6, с.109-121, 1972, 2, с.92-103.

29. Емеличев В.А., Комлик В.И. К многопродуктовой задаче размещения.- Вестник Белорусского ун-та. Серия I, 1970, I, с.21-22.

30. Емеличев В.А., Колмик В.И. Метод пострвения последовательности планов для решения задач дискретной оптимизации.-М.: Наука, 1981.- 208 с.

31. Емеличев В.А., Супруненко Д.А., Танаев B.C. О работах белорусских математиков в области дискретной оптимизации.- Изв. АН СССР. Техн.кибернет., 1982, № 6, с.25-45.

32. Журавлев Ю.И., Финкельштейн Ю.Ю. Локальные алгоритмы для задач линейного целочисленного программирования.- В кн.: Проблемы кибернетики, вып.14.- М.: Наука, 1965, с.289-295.

33. Калдыбаев С.У., Хачатуров В.Р. Алгоритм решения распределительных задач большой размерности с булевыми переменными.- В кн.: Автоматизация научных исследований.- Алма-Ата: Наука, 1982, с.110-125.

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

35. Ковалев М.М. Алгоритмы решения одной нелинейной задачи псевдобулевого программирования.- Вестник Белорусского ун-та. Серия I, 1973, № 3, с.3-9.

36. Ковалев М.М. Об одной задаче целочисленного программирования с выпуклой симметрической функцией цели.- Вестник Белорусского ун-та. Серия I, 1974, № I, с.64-65.

37. Ковалев М.М. Дискретная оптимизация.- Минск: ЕГУ, 1977.- 192 с.

38. Ковалев М.М. Метод частичных порядков.- Докл. АН БССР, 1980, т.24, C.II3-II6.

39. Ковалев М.М., Чинь Д. Анализ градиентного алгоритма максимизации дискретно-вогнутой функции.- Изв.АН БССР. Сер. физмат, наук, 1980, № 2, с.69-76.

40. Коваленко А.Г., Хачатуров В.Р. Алгоритмы решения некоторых задач оптимизации многошаговых процессов аппроксимаци-онно-комбинаторным методом.- Изв.АН СССР. Техн.кибернет., 1982, № 2, с.46-55.

41. Корбут А.А., Малков У.Х., Сигал И.Х., Финкелышгейн Ю.Ю. 0 современном состоянии и перспективах развития вычислительных методов и программ решения задач ЦДЛ. В сб.: Принятие оптимальных решений в экономических системах. Горький, 1983, с.3-30.

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

43. Корбут А.А., Финкельштейн Ю.Ю. Приближенные методы дискретного программирования.- Изв.АН СССР. Техн.кибернет., 1983, & I, с.165-176.

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

45. Кукса А.И., Шор Н.З. О методе оценки количества условно-оптимальных траекторий сепарабельного динамического программирования.- Кибернетика, 1972, № 6, с.18-87.

46. Лебедев В.Ю. Схема решения частично целочисленной задачи математического программирования.- ЖВМ и МФ, 1977, т.II,1. Аь 5, c.II89-II93.

47. Левин Г.М., Танаев B.C. Декомпозиционные методы оптимизации проектных решений.- Минск: Наука и техника, 1978.-240 с.

48. Мащенко С.О. Декомпозиционный алгоритм решения частично целочисленных задач линейного программирования.- В сб.: Исследование задач многокритериальной оптимизации, Киев, Институт кибернетики имени В.М.Глушкова АН УССР, 1984, с.49-63.

49. Мащенко С.О. Последовательный алгоритм решения задач смешанного линейного программирования.- В кн.: Исследование операций и АСУ, вып.21.- Киев: Вища школа, 1981, с.33-39.

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

51. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение, 1,П.- Кибернетика, 1965, № I, с.45-55, № 2,с.85-89.

52. Михалевич B.C., Войналович В.М., Волкович В.Л. Методпоследовательного анализа при согласовании решений оптимизационных задач в двухуровневых системах.- Киев: 1981.- 27 с. /Препринт, АН УССР, Ин-т кибернетики, 81-45/.

53. Михалевич B.C., Волкович В.Л. Вычислительные методы исследования и проектирования сложных систем.- М.: Наука, 1982. 286 с.

54. Михалевич B.C., Волкович B.JI., Волошин А.Ф., Поздняков Ю.М. Алгоритмы последовательного анализа и отсеивания вариантов в задачах дискретной оптимизации.- Кибернетика, 1980, ЖЗ, с.76-85.

55. Михалевич B.C., Волкович В.Л., Волошин А.Ф., Мащен-ко С.О. Последовательный подход к решению смешанных задач линейного программирования.- Кибернетика, 1983, № I, с.34-39.

56. Михалевич B.C., Ермольев Ю.М., Шкурба В.В., Шор Н.З. Сложные системы и решение экстремальных задач.- Кибернетика, 1967, № 5, с.29-39.

57. Михалевич B.C., Кукса А.И. Методы последовательной оптимизации и дискретных сетевых задачах оптимального распределения ресурсов.- М.: Наука, 1983,- 208 с.

58. Михалевич B.C., Сергиенко И.В., Лебедева Т.Т. и др. Пакет прикладных программ ДИСПРО, предназначенный для решения задач дискретного программирования.- Кибернетика, 1981, № 3, с.117-137.

59. Михалевич B.C., Сергиенко И.В., Шор Н.З. Исследование методов решения оптимизационных задач и их приложения.-Кибернетика, 1981, № 4, с.89-113.

60. Михалевич B.C., Шор Н.З. Численные решения многовариантных задач по методу последовательного анализа вариантов.- В кн.: Научно-методические материалы экономико-математического семинара. М.: ЛЭМИ и ВЦ АН СССР, 1962, вып.1, с.15-42.

61. Михалевич B.C., Шор Н.З., Галустова Л.А. и др. Вычислительные методы выбора оптимальных проектных решений.- Киев: Наукова думка, 1979.- 344 с.

62. Нгуен Нгок Тю, Черникова Н.В. Новый алгоритм решения задачи дискретного программирования.- ЖВМ и МФ, 1981, 16 2,с.329-338.

63. Первозванский А.А., Гайцгори В.Г. Декомпозиция, агрегирование и приближенная оптимизация.- М.: Наука, 1979.-342 с.

64. Поздняков Ю.М. Декомпозиционная схема решения задач целочисленного линейного программирования.- ЖВМ и МФ, 1982, т.22, Ш I, с.57-67.

65. Поздняков Ю.М., Мащенко С.О. Об оптимизации декомпозиции.- В кн.: Исследование операций и АСУ, вып.18. К.: Вища школа, 1981, с.27-35.

66. Пшеничный Б.Н. Необходимые условия экстремума.- М.:) Наука, 1969,- 151 с.

67. Рощин В.А., Семенова Н.Ф., Сергиенко И.В. Вопросы решения задач частично целочисленного программирования специального вида.- В сб.: Теория оптимального решения. Киев, 1982, с.20-28.

68. Рощин В.А., Сергиенко И.В, Семенова Н.В. 0 решении частично целочисленных оптимизационных задач, выпуклых по непрерывным переменным.- Кибернетика, 1981, № 5, с.62-66.

69. Сергиенко И.В. 0 некоторых направлениях в развитии методов дискретной оптимизации и их программного обеспечения.-Кибернетика, 1982, № 6, с.45-53.

70. Сергиенко И.В. 0 применении метода вектора спада для решения задач оптимизации комбинаторного типа.- Управляющие системы и машины, 1975, № 2, с.86-94.

71. Сергиенко И.В., Волкович В.Л., Рощин В.А. и др. 0 результатах машинного эксперимента по решению задач целочисленного линейного программирования с булевыми переменными.- УС и М, 1979, № 6, с.66-69.

72. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации.- Киев: Наукова думка, 1981.- 288 с.

73. Сергиенко И.В., Лебедева Т.Т., Рощин В.А. Приближенные методы решения дискретных задач оптимизации.- К.: Наукова думка, 1980.- 273 с.

74. Середа А.В. Метод ветвей и границ для решения одной сепарабельной задачи смешанно-целочисленного программирования.-В сб.: Методы прикладной и вычислительной математики в судостроении. Л., 1980, с.II9-I27.

75. Сигал И.Х. Алгоритм решения задачи коммивояжера с оценкой точности.- В кн.: Алгоритмы и алгоритмические языки. М., ВЦ АН СССР, 1973, с.49-61.

76. Сигал И.Х. Последовательный анализ вариантов в задаче о нахождении на графе ограниченного по длине пути с максимальным весом.- Изв.АН СССР. Техн.кибернетика, 1970, 6,с.41-47.

77. Сигал И.Х. Последовательный анализ вариантов при решении экстремальных задач.- В кн.: Системы распределения ресурсов на графах. М.: ВЦ АН СССР, 1970, с.63-84.

78. Уздемир А.П. Динамическое размещение производства. 1,П.- Автоматика и телемеханика, 1979, № II, с.142-154, № 12, с.146-158.

79. Уздемир А.П. Схема последовательной декомпозиции в задачах оптимизации.- Автоматика и телемеханика, 1980, № II, с.94-105.

80. Федоров В.В. Численные методы максимина.- М.: Наука, 1979.- 278 с.

81. Ферстер В.Б. Построение усиленных отсечений полностью целочисленного алгоритма Гомори.- В кн.: Исследования по дискретной оптимизации. М.: Наука, 1976, с.53-67.

82. Финкелынтейн Ю.Ю. Об одном классе задач дискретного программирования.- Эконом, и матем. методы, 1968, т.1У, вып.4, с.652-655.

83. Фридман А.А. О некоторых современных направлениях в дискретной оптимизации.- Экономика и математ.методы, 1977, т.Ж, в 5, c.III5-II3I.

84. Фридман А.А., Вотяков А.А. Дискретные задачи и метод ветвей и границ.- Экономика и матем.методы, 1974, т.Х, № 3,с.611-620.

85. Хачатуров В.Р. Аппроксимадионно-комбинаторшй метод и некоторые его приложения. ЖВМ и МФ, 1974, т.14, 8 № 6, с.1464-1487.

86. Ху Т. Целочисленное программирование и потоки в сетях.-М.: Мир, 1974. 520 с.

87. Цурков В.И. Декомпозиция в задачах большой размерности.- М.: Наука, I98I.-.352 с.

88. Червак Ю.Ю. Об одном усиленном варианте алгоритма Го-мори.- Экономика и матем.методы, 1977, т.ХШ, №2, с.391-394.

89. Юдин Д.Ю., Голыптейн Е.Г. Линейное программирование. Теория, методы и приложения.- М.: Наука, 1969.- 487 с.

90. Agrawal S.C. An alternate method on integer solutions to linear fractional by a branch and bound technique.- ZAMM, 1977, N57, p.52-53.

91. Agrawal S.C. On integer solutions to quadratic program by a branch and bound technique.- Trab. estadist. invest, oper. 1974, v.25, nI-2, p.65-70.

92. Balas E. Duality in discrete programming. The quadratic case.- Management Sci., 1969, v.l6,NI, p.14-32.

93. Balas E., Jeroslow Robert G. Strengthing cuts for mixed integer programs.- Eur. J. Oper. Res., 1^80, N4, p.224-234.

94. Barthers J., Henley E. Branch and bound methods as decompositions tools.- In: Decomposition of large-scale problems. Ed. Himmelblau D.- Amsterdam, 1973, p. 15-42.

95. Benders J.P. Partitioning procedures for solving mixed' variable programming problems.- Numeriche Mathematics I, 1977, p.117-144.

96. Burdet J., Jonhson E.L. A subadditive approach to solve linear programsAnals of discrete mathematics X, 1977» p.II7— 144.

97. Decompositions of large-scale problems /Ed. Himmelblau D.- Amsterdam, 1973, -632 p.

98. Dzielinski B.P., Gomory R.E. Optimal Programming of lot sizes inventory and labor allocations.- Management Sci., 1965 N9, p.874-890.

99. Everett H. Generalized Lagrange Multiplier Method for solving Problems of Optimum Allocation of Resourses.- Oper. Res., 1963, v.II, p.399-417.

100. Forgo P. Shadow prices and decomposition for integer programs.- Dep. Math. K. Marx Univ. Econ. Budapest, 1974, N 6, p.I-31.

101. Geofrion A.M. Lagrangean relaxation and its uses in integer programming.- Math. Programming Study 2, Amsterdam, 1974, p.82-114.

102. Glover P. A new foundation for a simplified primal integer programming algorithm.- Oper. res., 1968, v.16, N 4, p.727-740.

103. Supportage constraint duality in mathematical programming.- Oper. res., 1975, N 3, p.434-451.

104. Gomory R.E. Outline of an algorithm for integer solution to linear programs.- Bui. Amer. Math. Soc., 1958, v.64,p.275-278.

105. Integer programming and related areas. A classified-bibliografy /Ed. Hausmann Dirk.- Lect. Notes. Econ. and Math. Syst., 1976, v.128, -459p•

106. Integer programming and related areas. A classified bibliografy /Ed. Hausmann Dirk.- Lect. Notes Econ. and Math, Syst., 1978, v.160, -3I4p.

107. Karwan M.H., Rarrin R.L. Some relationship between lagrangian and surrogate duality in integer programming.- Math. Program., 1979, N 3, p.320-334.

108. Kelley/J.E. The cutting-plane method for solving convex programs.- J. Soc. Industr. Appl. Math., I960,v.8, p.70-71

109. Land A.H., Doig A.G. An automatic method of solving descrete programming problems.- Econometrica, I960, N3»P.497-520.

110. Little J., Murty K., Sweney D., Karel C. An algorithm for the travelling salesman problem.- Oper. Res., 1963, N 6,p.972-989.

111. Magnanty T.L., Wong R.T. Asselerating Benders decomposition: algorithmic enhancement and model selection criteria.- Oper. Res., 1981, N 3, p.464-484.

112. Marsten R.E., Morin T.L. A hybrid approach to discrete mathematical programme.- Math. Program., 1978, N1, p.24-33.

113. Nemhauser G.L., Ullman Z. A note of the generalized lagrange multiplier solution to an integer programming problem. Oper. Res., 1968, n2, p.450-453.

114. Sweeney D.J., Murphy R.A. A method of decomposition for integer programs.- Oper. Res., 1979, v.27, N6, p.II28-II4I.12.0. Tomlin J.A. Large scale mathematical programming systems.- Compute and Chem. Eng., 1983, N5, p.575-582.

115. Van Roy Tony J. Cross decomposition for mixed integer programming.- Math. Program., 1983, N1, p.46-63.

116. Veinott A.F. The supporting hyperplane method for uni-modal programming.- J. Oper. Res., 1967, v.15, N2, p.147-152.