Помощь в учёбе, очень быстро...
Работаем вместе до победы

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

Диссертация: Методы последовательного анализа решений в частично целочисленных задачах линейного программирования и их применение
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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

Содержание

  • Глава 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, номер государственной регистрации 81 085 927) и распоряжением Президиума АН УССР № 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., 180, 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.
Заполнить форму текущей работой

Пора сдавать?