автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Оптимизация управления производственными процессами при дискретных множествах управляющих воздействий

ВВЕДЕНИЕ

ГЛАВА I. ОПТИМИЗАЦИЯ УПРАВЛЕНИЯ НА ДИСКРЕТНЫХ МНОЖЕСТВАХ

1.1. Дискретные множества и их свойства

1.2. Особенности оптимизации на дискретных множествах

1.3. Задача оптимального управления на дискретных множествах

1.4. Устранение фазовых ограничений.

1.5. Метод ветвей и границ.

1.6. Приближенные методы на основе схемы ветвей и границ

1.7. Метод последовательных приближений на основе функциональных соотношений Веллмана

1.7.1. Описание метода

1.7.2. Особенности программной реализации

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

1.9. Метод покомпонентного варьирования . 63 1.10. Основные результаты и выводы

ГЛАВА П. РЕШЕНИЕ ЗАДАЧИ КОММИВОЯЖЕРА И НЕКОТОРЫХ ЕЕ ОБОБЩЕНИЙ МЕТОДАМИ ТЕОРИИ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ

2.1. Формулировка проблемы

2.2. Алгоритм сведения

2.3. Сокращение размерности

2.4. Алгоритм решения задачи коммивояжера

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

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

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

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

Применение математических методов для решения задач оперативного управления производством вызвало развитие таких разделов математики, как линейное и нелинейное программирование [13, 15, 16, 69, 129J ; дискретное программирование [51, 105, 124] ; теория расписаний [42, 48, 116, 118] ; экстремальные задачи на графах и сетях [67, 101, 105, 123, 124] .

Отметим вкратце основные методы, используемые при решении задач ОУП.

На первых этапах применения матметодов исследователи в большинстве случаев использовали модели линейного программирования, которые хорошо отражают объемные характеристики производственных процессов [3, 14, 25, 35, 43] . В последующие годы,в связи с проработкой проблем планирования, работы участков и бригад, большое развитие получили модели нелинейного программирования, содержащие целочисленные и булевы переменные, теории расписаний и сетевого планирования [I, 27, 42, 53, 62, 73, 78, 97, 104, 106, 112, ИЗ, 127] .

Из книги Финкелыптейна Ю.Ю. [122] видно, что большая группа проблем ОПП была решена методами дискретного программирования, В этой работе отмечена необходимость развития приближенных алгоритмов при решении большинства практических задач, содержащих дискретные переменные, и приведен обзор таких методов, применяемых в дискретном программировании. Более поздние результаты, полученные в этом направлении, отражены в обзоре Корбута А.А., Финкелынтейна Ю.Ю. [52 J .

Широкое применение при решении задач дискретной оптимизации, и, в частности, задач ОГПТ, получили алгоритмы, разработанные на основе схемы последовательного анализа и отсева вариантов. Эта схема была обоснована в работе Михалевича B.C. [80]. Дальнейшее развитие этого подхода изложено в серии статей [17, 81, 82, 83, 84, 86, 107] .

Большая группа алгоритмов решения дискретных задач оптимизации разработана на основе последовательного построения планов, предложенного Емеличевым В. А. в работах [28, 29, 30] . Последующее развитие этого метода отражено в работах [31, 32] .

Следует особо отметить широкое применение при решении задач оптимизации производственных процессов метода ветвей и границ. Описание некоторых конкретных задач ОПП, решенных этим методом, можно найти в работах [8, 10, 22, 55, 65, 74, 101, 118, 120, 121].

Точное решение задач теории расписаний во многих случаях удается получить с помощью метода ветвей и границ или метода последовательного анализа вариантов. Однако, как отмечено в работах [48, 118] , математические модели, рассматриваемые в рамках этой теории, носят сильно упрощенный характер и не применимы для многих производственных ситуаций.

Исследование более сложных моделей календарного планирования привело к развитию приближенных методов решения, основанных на локальных критериях [I, 38, 42, 53, 62, 78, 97, 106, 112, 127, 130]. Во многих случаях эти методы имеют эвристический характер и тесно связаны со спецификой рассматриваемых производственных процессов.

Для некоторых задач дискретного программирования, теории расписаний и сетевого планирования предложены алгоритмы решения, использующие идеи динамического программирования [5, 6, 51, 83, 93, 101]. Рассмотрим этот подход более подробно. В настоящей работе динамическое программирование рассматривается как раздел теории оптимального управления, связанный с принципом оптимальности Беллмана и соответствующими ему функциональными соотношениями [о, 18] . Поэтому в данном случае можно говорить о некотором применении теории оптимального управления для решения задач дискретной оптимизации.

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

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

С нашей точки зрения постановка исходной дискретной задачи на языке теории оптимального управления дает дополнительные преимущества. Действительно, принцип оптимальности Беллмана является только одним из принципов, используемых при изучении оптимальных процессов. Имея формулировку задачи в виде задачи теории оптимального управления можно разрабатывать методы ее решения, основанные на принципе оптимальности Кротова [57] или на основе принципа максимума Понтрягина [60, 70, 71, 89, 98] .

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

Применения теории оптимального управления к решению задач ОУП встречались гораздо реже. Так, например, некоторые проблемы оптимизации производственных процессов рассмотрены в книге Беллмана Р. и Дрейфуса С. [б]; в работе Непомнящих В.А. [91] разработан подход к решению одной задачи теории расписаний; в работе Зимина И.Н., йванилова Ю.П. [39 J проведено сведение задачи сетевого управления к задаче теории оптимального управления; в книге Моисеева [89J описан метод сведения некоторого класса проблем теории расписаний к задачам теории оптимального управления; в работе Себастьяна и Густафсона [145] приведен пример использования теории оптимального управления для решения конкретной задачи управления режимами работы автотранспорта.

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

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

Как отмечено выше, большинство применений теории оптимального управления связано с работой технических устройств, имеющих непрерывное регулирование. Поэтому вполне естественными были ограничения на управляющие воздействия, которые записывались в виде неравенств cl^ и (к) г 4 , где и (к) - Уп - вектор управляющих воздействий; Л , / - векторы в пространстве R т .

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

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

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

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

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

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

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

Целесообразность такого подхода к решению задач ОУП была осознана автором под влиянием М.Г. Дмитриева, В.Я. Глизера, Г.А. Доррера в процессе совместной работы над решением задачи оптимального объемно-календарного планирования производства пиломатериалов на экспорт. По нашему мнению, в полном виде этот подход был впервые применен именно при решении этой проблемы. Результаты, полученные в ходе ее решения, опубликованы в серии работ [92, 96, 149, 150, 151, 164, 165] .

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

Отметим, что задачи с дискретными множествами управляющих воздействий уже встречались при оптимизации управления техническими устройствами. Так, например, в книге Табака А. и Куо Б. [105] описана линейная система управления антенной, имеющая конечные множества управляющих воздействий.

Работа Михалевича B.C., Попадинца В.И. и др. [85] посвящена изучению задач оптимального управления, описываемых обыкновенными дифференциальными уравнениями с дискретными множествами управляющих воздействий. Задачи такого рода встречаются при оптимизации движения летательного аппарата. В работе Ермолаева A.M. [33] рассмотрена дискретная во времени система, у которой часть управляющих воздействий дискретна. Такая система встречается при работе с цифровыми вычислительными устройствами.

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

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

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

Поясним это на следующем примере.

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

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

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

Если все множества управляющих воздействий конечны, то для этой задачи остаются справедливыми функциональные соотношения Беллмана. Поэтому можно в принципе применить метод решения, основанный на восстановлении функции Беллмана [18, 51, 101] . Однако, как неоднократно отмечалось в литературе, практически использовать этот подход удается при небольшой размерности вектора фазовых переменных, что крайне редко встречается при решении производственных задач.

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

Принцип оптимальности Кротова [57] применим для этой задачи в случае произвольных дискретных множеств управляющих воздействий. Предложенный В.Ф. Кротовым [56] метод решения задач оптимального управления был применен в работе Кротова В.3>., Сергеева С. И. [ 58] для решения некоторых задач дискретной оптимизации. Однако, для систематического решения задач ОУП этот метод может оказаться неприемлемым в силу того, что получаемые на его основе приближенные решения не всегда являются допустимыми решениями исходной задачи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

При наличии жестких ограничений на время решения задачи полная реализация метода ветвей и границ может оказаться невозможной. Поэтому в шестом параграфе изложены методы приближенного решения на основе схемы ветвей и границ. Как и в случае традиционного использования этого метода [8, 137] , рассмотрены два варианта приближенных алгоритмов: с априорной и апостериорной оценкой точности.

Алгоритм ветвей и границ, рассмотренный до момента получения первого допустимого решения, является обобщением схемы селекции. Эта схема успешно применялась ранее как высокоэффективный эвристический прием при решении разнообразных технических и научных проблем [19, 41, 100].

В седьмом параграфе рассмотрен метод последовательных приближений на основе функциональных соотношений Беллмана. Этот метод позволяет экономить оперативную память ЭВМ за счет увеличения времени счета и формировать приближенное программное управление не восстанавливая функции Беллмана во всех множествах достижимости. Похожие по технике алгоритмы последовательного приближения рассмотрены для непрерывных во времени систем в работах [40, 9lJ и для дискретных автономных систем в работах [49, 50]. Показана сходимость предложенного алгоритма за конечное число шагов.

Предложенный алгоритм основан на методе последовательных приближений в пространстве управлений [18]• Отмеченные выше результаты справедливы также для метода последовательных приближений в пространстве функций Беллмана [18].

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

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

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

Методы последовательных приближений на основе принципа максимума Понтрягина подробно описаны в работах [60, 70, 71]. Техника этих методов не требует существенных изменений для рассматриваемого случая. Но в большинстве задач ОУП их обоснованность остается открытой.

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

В настоящей работе для этих целей используется метод покомпонентного варьирования и некоторые его модификации. Этот метод является естественным обобщением таких хорошо известных методов как покоординатный спуск [15], метод локальных вариаций Крыло-ва-Черноусько [61] , групповой покоординатный спуск [9, 142] . Показано, что такой подход позволяет получить локально-оптимальное решение. Исследован вопрос о корректности соединения этого метода с методом штрафных функций.

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

Задача коммивояжера и ее разнообразные обобщения часто встречаются при решении проблем оперативного управления производственными процессами [48, 88, 93, 63, 64, 75, НО, 112, 128, 149, 163] .

Традиционная задача коммивояжера заключается в следующем. Коммивояжер находится в городе d0 . Ему необходимо посетить по одному разу все города из множества М и вернуться в город

О-о • Решением задачи является кратчайший маршрут, удовлетворяющий этим условиям.

Обобщения задачи коммивояжера изучаются в различных направлениях. Работы [26, 37, 97, 99] посвящены задаче нескольких коммивояжеров. В работах [65, 112, 141] изучаются обобщения традиционной задачи, связанные с количеством посещений городов и проходов по дугам. Задачи коммивояжера с ограничениями по срокам изучались в работах [105, 133] . В работе [63] обобщение состоит в том, что расстояние между городами тоже является переменной величиной; а в работе [III] меняется список городов, которые должен посетить коммивояжер. В работах [64, 149, 153, 157] изучается задача коммивояжера с ограничениями на маршрут движения, связанными с порядком прохождения городов.

Точные методы решения обобщенных задач коммивояжера состоят обычно в следующем: решением обобщенной задачи сводят к решению традиционной [ 54, 112, 157] ; или разрабатывают оригинальный способ решения на основе упомянутых выше общих подходов к решению дискретных оптимизационных задач (метод ветвей и границ, метод динамического программирования и т.д.).

Точные алгоритмы решения традиционной задачи коммивояжера в основном используют схему метода ветвей и границ [51, 63, 64, 65, 68, 101] . Однако, для специальных случаев матрицы расстояний удается разрабатывать и другие подходы к решению [ИЗ, 128, 14б] . Более полный обзор точных методов можно найти в работе [107] .

Приближенные методы решения задачи коммивояжера основаны на самых разнообразных идеях [21, 24, 47, 77, 122, 135, 136, 139, 143] . Систематизированные обзоры приближенных методов с результатами вычислительных экспериментов содержатся в работах [II, 122, 139, 143, 147].

В первом параграфе второй главы содержится математическая постановка изучаемой задачи коммивояжера с ограничениями на маршрут движения, которая является обобщением задач, рассмотренных в работах [64, 149, 163].

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

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

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

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

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

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

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

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

На первых этапах применения математических методов задачи формирования производственной программы формулировались как задачи линейного программирования[3, 4, 20, 25, 35, 43, 45, 62, 66, 75, 88, 97, 106, 114, 125]. Однако уже в работе Первозванского А.А.[93] показано, что при специфических условиях на поступление сырья линейная модель становится не адекватной производственной ситуации.

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

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

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

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

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

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

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

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

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

Описанные результаты получены автором и опубликованы в работах [149 - 165].

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

Автор выражает глубокую признательность научному руководителю М.Г. Дмитриеву за постоянную помощь на всех этапах выполнения работы, многочисленные указания и замечания, а также за обсуждение всех полученных результатов. Автор благодарен В.И. Гурману за неоднократные указания на целесообразность применения принципа оптимальности Кротова при решении задач ОУП, за прочтение предварительных материалов по диссертации и высказанные замечания. Автор выражает благодарность А.А. Первозванскому за плодотворное обсуждение широкого круга вопросов, связанных с темой диссертации, и высказанные замечания по предварительным результатам.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

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

3. Обоснован метод последовательных приближений на основе функциональных соотношений Беллмана для задачи Майера-Больца на дискретных множествах.

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

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

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

Формирование оптимальной производственной программы выработки экспортных пиломатериалов".

Оптимальное управление потреблением активной мощности".

Оптимальное управление потреблением реактивной мощности".

3.5. Основные результаты и выводы

В этой главе приведены математические модели для задач: формирование оптимального программного управления системы с параллельной обработкой входов (оптимальной производственной программы); оптимального объемно-календарного планирования производства пиломатериалов; оптимального управления потреблением активной мощности; оптимального управления потреблением реактивной мощности. Все матмодели являются новыми в соответствующих областях.

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

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

Штематическая модель задачи оптимального объемно-календарного планирования производства пиломатериалов была разработана автором совместно с М.Г. Дмитриевым, Г.А. Доррером, В.Я. Глизе-ром, А.С. Погребняковым в работах [163, 165]. Дальнейшее ее обобщение в виде задачи формирования производственной программы приведено автором в работе £159].

Разработана математических моделей для задач оптимального управления потреблением активной и реактивной мощности проведена автором в работах [160, 161, 162].

Описанные в диссертации алгоритмы решения этих задач были разработаны автором и опубликованы в работах [149, 150, 151, 159-165].

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

Конкретная специфика задачи проявляется:

- при выборе ограничений, которые устраняются с помощью штрафных добавок к критерию;

- выборе штрафных функций;

- в разработке оценок для метода ветвей и границ;

- в выборе начального приближения функции Беллмана;

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

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

1. Аронович А.Б, 0 выборе оптимальных комбинаций локальных правил календарного планирования. - Экономика и математические методы, 1970, т. У1,Р4, с. 548-557.

2. Бабаев Ш.В. Оптимальный раскрой материалов с помощью ЭВМ.--М., Машиностроение, 1982, 167 с.

3. Барсов А.С. Линейное программирование в технико-экономических задачах. М.: Наука, 1964, - 278 с.

4. Бахрах В.П. Опыт построения рациональной производственной программы предприятий машиностроения и приборостроения. Л.: Знание, 1970, - 32 с.

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

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

7. Березнев В. А. Система автоматизированного планирования раскроя в производстве трикотажного полотна с применением ЕС ЭВМ.- В кн.: Вопросы оптимизации и управления. М.: МГУ, 1979, с. 16-25.

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

9. Богданов Д. Покомпонентные методы выпуклого программирования.- В кн.: Прикладные проблемы больших систем управления: Тр. 6-го Польско-болгарского симпоз. Приморско. София, 1980, с. 32-39.

10. Большаков В.А., Уздемир А.П., Шмелев В.В. Задачи планирования дискретного (штучного) производства и численные методы их решения. Ш. Автоматика и телемеханика, 1976, № I, с.146-156.

11. Бородин В.В., Ловецкий С.Е., Меламед И.И., Плотницкий Ю.М. Экспериментальное исследование эффективности эвристических алгоритмов решения задачи коммивояжера. Автоматика и телемеханика, 1980, № II, с. 76-84.

12. Букреев В.З., Розенблат Г.М. Приближенный синтез оптимального управления для дискретных систем. Автоматика и телемеханика, 1976, Р I, с. 90-93.

13. Дулавский В.А., Звягина Р.А., Яковлева М.А. Численные методы линейного программирования. М.: Наука, 1977, - 368 с.

14. Бункин В.А., Курицкий Б.Я., Сокуренко Ю.А. Решение задач оптимизации в управлении машиностроительным производством. -Л.: Машиностроение, 1976. 231 с.

15. Васильев 5>.П. Численные методы решения экстремальных задач.- М.: Наука, 1980. 520 с.

16. Васильев Ф. П. Методы решения экстремальных задач. М.: Наука, 1981. - 400 с.

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

18. Габасов Р., Кириллова Ф.Н. Основы динамического программирования. Минск, Изд-во БГУ, 1975, - 262 с.

19. Габор Д. Перспективы планирования. Автоматика (Киев), 1972,- 2, с. 84-89.

20. Герман В.А., Илюкович А.А., Кондауров Н.Н. Основные типы задач оптимизации производственной программы предприятия. В кн.: Автоматизированные системы управления. Тр. ЦНИЙТУ. Вып. 9. - Минск, ЦНИЙТУ, 1972, с. 89-98.

21. Горбунцов В. В. Пошаговая процедура решения задачи коммивояжера, вложенной в метрическое пространство. В кн.: Прикладные задачи динамики управляемого движения. - Киев: Наукова думка, 1981, с. 26-37.

22. Грибов А.Б. Алгоритм решения задачи плоского раскроя. Кибернетика, 1973, с. II0-115.

23. Гроссман К., Каплан А.А. Нелинейное программирование на основе безусловной оптимизации. Новосибирск: Наука, Сибирское отделение, 198I. - 183 с.

24. Гудович А.Н., Каплинский А.И., Чернышева Г.Д. О реализации алгоритма выбора очередности при решении набора задач на ЭВМ (задача коммивояжера). Проблемы случайного поиска, 1983,10, с. 100-105.

25. Данилин В.И. Экономико-математические модели годового планирования на предприятии. М.: Наука, 1975. - 149 с.

26. Долодаренко В.А., Матчук В.М. Один локальный метод решения задачи YI коммивояжеров большой размерности. - Докл. АН УССР, 1983, А, Ш I, с. 66-67.

27. Дончак Л.Я., Романовский М.В. Оптимизация планирования в промышленности. Л.: Лениздат, КТО. - 225 с.

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

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

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

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

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

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

34. Завельский М.Г. Оптимальное планирование на предприятии.- M.s Наука, 1970, 396 с.

35. Завельский М.Г., Коробов В.А. Оптимальный раскрой металла.- Вестник машиностроения, 1966, \1- 10, с. 56-60.

36. Зак Ю.А. Алгоритмы решения задач " -коммивояжеров". Кибернетика, 1972, № I, с. 99-112.

37. Зак Ю.А., Рейдман P.M., Рувинский а.А. Методы оптимизации и применение их в целлюлозобумажной промышленности. М.: Лесная промышленность, 1973, - 248 с.

38. Зимин Й.Н., Иванилов 10. П. Решение задач сетевого планирования сведением их к задачам оптимального управления. Журнал вычислительной математики и математической физики, 1971,т. II, № 3, с. 632-641.

39. Зубов В.Й. Математические методы исследования систем автоматического регулирования. Л.: Машиностроение, (Ленингр. отд-ние), 1974, 336 с.

40. Ивахненко А.Г., Зайченко Ю.П., Димитров В.Д. Принятие решений на основе самоорганизации. -М.: Советское радио, 1976.-280с.

41. Календарное планирование. М.: Прогресс, 1966, - 466 с.

42. Канторович JI.В. Экономический расчет наилучшего использования ресурсов. М.: Изд-во АН СССР, I960, - 348 с.

43. Корн Г., Корн Т.-Справочник по математике для научных работников и инженеров. М.: Наука, 1977, 832 с.

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

45. Канторович Л.В., Залгаллер В.А. Рациональный раскрой промышленных материалов. Новосибирск: Наука, 1971. - 299 с.

46. Каплинский А.И., Чернышева Г.Д., Хлявич О.А. Об одном подходе к построению приближенных алгоритмов решения задачи коммивояжера. В кн.: Эвристические алгоритмы оптимизации. -Ярославль, 198I, с. 32-38.

47. Конвей Р.В., Максвелл В.А., Миллер Л.В. Теория расписаний.- М.: Наука, 1975, 359 с.

48. Кондратьев В.В., Савельев В.П., Шорохов О.С. Оптимизация дискретного управления методом последовательных приближений.- Автоматика и телемеханика, 1980, № 6, с. 48-57.

49. Кондратьев В.В., Савельев В.П., Шорохов О.С. Построение оптимального регулятора для линейных систем с запаздыванием.- В сб.: Оптимизация и математическое обеспечение САПР. -Горький: Горьк. госуниверситет, 1982, с. 125-133.

50. Корбут А.А., Шинкельштейн Ю.Ю. Дискретное программирование.- М.: Наука, 1969, 366 с.

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

52. Коробкин А.Д., Мироносецкий Н.В. Оптимизация планирования на предприятии. Новосибирск: Наука, Сибирское отд-ние, 1978,- 335 с.

53. Коробков В.К., Кричевский Р.Е. Некоторые алгоритмы для решения задачи коммивояжера. В сб.: Математические модели и методы оптимального планирования. - Новосибирск: Наука. Сибирское отд-ние, 1966, с. 106-108.

54. Косарев Н.Г., Уздемир А.П. Динамическая задача планирования научных исследований и разработок и метод ее решения. Автоматика и телемеханика, 1977, № I, с. 62-73.

55. Кротов В.5>. Вычислительные алгоритмы решения и оптимизации управляемых систем уравнений. I, П. Изв. АН СССР, сер. Техн. кибернетика, 1975, №5, с. 3-15; 1976, № 6, с. 3-13.

56. Кротов В.Ф., Гурман В. И. Методы и задачи оптимального управления. М.: Наука, 1973. - 446 с.

57. Кротов В.Ф., Сергеев С.И. Вычислительные алгоритмы решения некоторых задач линейного и линейного целочисленного программирования. 1,П,Н1,1У. Автоматика и телемеханика, 1980, № 12, с. 86-96, 198I, № I, с. 86-96, 1981, № 3, с. 83-94; 198I,4, с. I03-II2.

58. Кротов В.Ф., Фельдман И.Н. Итерационный метод решения задач оптимального управления. Изв. АН СССР, сер. Техн. кибернетика, 1983, № 2, с. 160-168.

59. Крылов И.А., Черноусько Ф.Л. О методе последовательных приближений для решения задач оптимального управления. Журнал вычисл. математики и мат. физики, 1962, т. 2, № 6, с.1132-1139.

60. Крылов И.А., Черноусько Ф.Л. Решение задач оптимального управления методом локальных вариаций. Журнал вычисл. математики и мат. физики, 1966, т. 6, № 12, с. 203-207.

61. Кузин Б.И., Дуболазов В.А. Организация и оперативно-календарное планирование машиностроительного производства в АСУП. Л.: Изд-во ЛГУ, 1978. - 239 с.

62. Кузин Б.Й., Тютюкин В.К. Обобщенная задача коммивояжера, ее алгоритм и применение к определению порядка запуска предметов на переменно-поточных линиях. В сб.: Применение математики в экономике. Вып. 5. - Л.: Изд-во ЛГУ, 1969, с. 56-67.

63. Кузин Б.И., Тютюкин В.К. Задача о коммивояжере с ограничениями на передвижение, ее алгоритм и экономические приложения.- В сб.: Применение математики в экономике. Вып. 6, Л.: Изд-во ЛГУ, 1970, с. 53-67.

64. Лабезник Д.И., Хранович И.Л. Решение обобщенной задачи коммивояжера методом ветвей и границ. Экономика и мат. методы, 1973, т. IX, № 2, с. 363-364.

65. Левицкий В.М. Математические модели оптимального объемно-календарного планирования производства машиностроительного предприятия. М.: Статистика, 1972. - 64 с.

66. Леонтьев В.К. Дискретные экстремальные задачи. В кн.: Теория вероятностей. Мат. статистика. Теоретич. кибернетика. (Итоги науки и техники, т. 16). - М.: Наука, 1978, с. 39-101.

67. Литл Дж., Мурти К., Суини Д., Карел К. Алгоритм для решения задачи о коммивояжере. Экономика и мат. методы, 1965, т. I, № I, с. 94-107.

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

69. Любушин А.А. О применении модифицированного метода последовательных приближений для решений задач оптимального управления.-Журнал вычисл. математики и мат. физики, 1982, т. 22, Р I,с. 30-35.

70. Любушин А.А., Черноусько Ф.Л. Метод последовательных приближений для расчета оптимального управления. Изв. АН СССР, сер. Техн. кибернетика, 1983, Ш 12, с. 147-159.

71. Максименко В.П. О применений эволюционной программы для решения задачи коммивояжера. Автоматика (Киев); 1981, № 4, с. 10-14.

72. Максимов Ю.Б. Модели и методы объемно-динамического распределения ресурсов. Харьков: ХПИ, 1982. - 73 с.

73. Максимов Ю.Б., Криворученко Е.И. Применение ветвей и границк решению дискретных задач объемно-календарного планирования. В кн.: Автоматизированные системы управления и приборы автоматизации. - Харьков: Вища школа, 1980, вып. 54, с. 74-80.

74. Математические методы в планировании отраслей и предприятий М.: Экономика, 1982. 335 с.

75. Милышгейн Г.Н. Применение последовательных приближений для решения одной оптимальной задачи. Автоматика и телемеханика, 1964, Р 3, с. 321-329.

76. Минина Т.Р., Перекрест В.Т. Аппроксимация рещения задачи коммивояжера С циклами. - Автоматика и телемеханика, 1975, Р 10, с. 79-89.

77. Мироносецкий Н.Б. Экономико-математические методы календарного планирования. М.: Наука, 1973. - 139 с.

78. Мирошниченко В.В., Пономаренко B.C. Основные подходы к решению задач невыпуклого программирования. Донецк, 1979. - 25с. Рукопись представлена Донецким ун-том в ВИНИТИ. Р 1915-80 ДЕЛ.

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

80. Михалевич B.C., Волкович В.Л., Волошин А.3>., Поздняков Ю.М. Алгоритмы последовательного анализа и отсеивания вариантов в задачах дискретной оптимизации. Кибернетика, 1980, Р 3, с. 76-85.

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

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

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

84. Михалевич B.C., Попадинец В.И., Голодников А.Н., Ищенко А.В. Об одном классе задач оптимального управления, описываемом обыкновенными дифференциальными уравнениями с дискретным множеством управлений. Кибернетика, 1983, Р 4, с. 63-70.

85. Михалевич B.C., Шкурба В.В. Последовательные схемы оптимизации в задачах упорядочения выполнения работ. Кибернетика,1966, Р 2, с. 34-40.

86. Меламед И.И. К задаче нескольких коммивояжеров. Тр. Моск. ин-та инженеров железнодорожного транспорта, 1981,- № 647, с. II7-II9.

87. Моделирование производственных процессов на предприятии. -M.s Црогресс, 1972. 333 с.

88. Моисеев Н.Н. Элементы теории оптимальных систем. М.: Наука, 1975. - 526 с.

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

90. Непомнящих П.А. Црименение теории оптимального управленияс помощью метода штрафных функций к одной задаче теории расписаний. Журн. вычислит, математики и мат. физики, 1970, т. 10, Р 4, с. 908-921.

91. Оптимальное объемно-календарное планирование и регулирование производства пиломатериалов на экспорт по предприятию, цеху на год, квартал, месяц, декаду: Техно-рабочий проект комплекса задач. Красноярск: ПКТБ п/о "Красноярсклесоэкспорт", 1978* - 516 с.

92. Первозванский А.А. ^тематические модели в управлении производством.- М.: Наука, 1975, 615 с.

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

94. Плотников В.Н., Галкин А. В. Приближенный метод решения задачи о коммивояжере. Экономика и мат. методы, 1973, т. IX,6, с. II42-II46.

95. Португал В.М., Семенов А.Й. Модели планирования на предприятии. М.: Наука, 1979. - 269 с.

96. Пропой А.И. Элементы теории оптимальных дискретных процессов.- М.: Наука, 1973. 255 с.

97. Пчелинцев Л.А. Об одном решении задачи коммивояжера. Журн. вычисл. математики и мат. физики, 1966, т. 6, № 3, с. 597- 599.

98. Розенблат Ф. Цринципы нейродинамики: Перцептроны и теория механизма мозга. М.: Мир, 1965. - 480 с.

99. Романовский Н.В. Алгоритмы решения экстремальных задач. -М.: Наука, 1977. 352 е.102. рубинов А.P. О сводимости обобщенной задачи коммивояжера к задаче коммивояжера меньшей размерности. ДАН СССР, 1982, т. 264, № 5, с. 1087-1090.

100. Рубинштейн М.й. О симметрической задаче коммивояжера. -Автоматика и телемеханика, 1971, Р 9, с. 126-133.

101. Г^винский А.А., Зак Ю.А., Рейдман P.M. Математические модели и алгоритмы в системах управления картонно-бумажным производством. М.: Лесная промышленность, 1971. - 232 с.

102. Саати Т. Целочисленные методы оптимизации и связанные с ними экстремальные проблемы. М.: Мир, 1973. - 302 с.

103. Семенов А.И., Португал В.М. Задача теории расписаний в календарном планировании мелкосерийного производства. М.: Наука, 1972. - 183 с.

104. Сергеев С.й. Алгоритмы решения задачи коммивояжера. В сб.: Моделирование технико-экономических процессов. - М.:1. МЭСИ, 198I, с. 3-37.

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

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

107. НО. Сихуралидзе Г.Г. Об одном обобщении задачи коммивояжера. I, П. Автоматика и телемеханика, 1971, № 8, с. II6-I23, 1971, Р 10, с. 142-147.

108. I. Скворцов В.В., Нуриев Н.К. Поведение коммивояжера при изменяющимся перечне городов. В сб.: Исследование операций и аналитическое проектирование в технике. Казань, 1979, Р 2, с. 51-54.

109. Смоляр Л.И. Модели оперативного планирования в дискретном производстве. М.: Наука, 1978. - 320 с.

110. Смоляр Л.И. Оперативно-календарное планирование. М.: Экономика, 1979. - 135 с.

111. Соболев И.В. Управление производством пиломатериалов. -Петрозаводск: Карелия, 1976. 173 с.

112. Табак А., Куо Б. Оптимальное управление и математическое программирование. М.: Наука, 1975. - 280 с.

113. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. М.: Наука, 1975. - 280 с.

114. Телемтаев М.М. К вопросу о решении задачи коммивояжера. -Изв. АН СССР, сер. Техн. кибернетика, 1972, № 6, с. 94-100.

115. Теория расписаний и вычислительные машины. М.: Наука, 1984. - 334 с.

116. Томский Г.В. Об одном методе последовательных приближений функции Беллмана. Журн. вычисл. математики и мат. физики, 1984, т. 24, № 8, с. 1264-1265.

117. Уздемир А.П. Задачи планирования дискретного (штучного) производства и численные методы их решения. I, П. Автоматика и телемеханика, 1975, W 9, с. II5-I22, 1975, № 10,с. 90-104.

118. Уздемир А.П., Шмелев В.В. Целочисленные динамические задачи экономического планирования с сетевыми ограничениями. I, П. Автоматика и телемеханика, 1978, № 7, с. I06-II5; 1978,9, с. II0-120.

119. Финкельштейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1976. - 264 с.

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

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

122. Шейнман Р.П. Оптимизация производственной программы предприятии и объединений. Экономика и мат. метода, 1974, т. X, № 3, с. 554-567.

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

124. Шубкина И.П. Моделирование механизма принятия решений. -М.: Наука, 1976. 275 с.

125. Экономико-математические модели. -М.: Мель, 1969. 512 с.

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

127. Яхно В.М. Об одном классе линейных динамических моделей календарного планирования. Автоматика и телемеханика, 1979, № 5, с. 121-126.

128. Balash Egon, Cristofid.es Nicos. A restrected Lagrangean approach to the traveling salesman problem.-Math.Program.,1981, 21,N1,p.19-46.

129. Beal E.M. Branch and bound method for numerical optimization of non-convex functions.-C0MPSTAT,1980,Proc.Comput.Statist. 4-th Symp. Edinburgh980, Wien,1980,p.11-20.

130. Pox Kenneth R.,Gavish Bezalel,Graves Stephen C. An n-constra-int formulation of the (time-dependent) traveling salesman problem.-Oper.Res.,1980,N28,N 4,p.1018-1021.

131. Prieze A.M.,Galbiati G.,Maffioli P. On the worst-case perfo ,-mance of some algorithms for the asymmetric traveling salesman problem.-Networks, 1982, 12, N 1, p.23-39.

132. Ibaraki T. ,Muro S. ,Mukarami T. ,Hasegawa T. Using branch-and-bound algorithms to obtain suboptimal solution.- 2. Oper. Res., 1983, A27, U 5, p. 177-202.

133. Jonker R.,Deleve G.,Van der Velder J.A., Volgenant A.Rounding symmetric traveling salesman problem with an asymmetric assignment problem.-Oper.Res.,1980,28,IT 3,Part 1,p. 623-627.

134. Kanellakis Paris C.,Papadimitrious Christos H. Local search for the asymmetric traveling salesman problem.- Oper. Res., 1980, 28, N 5, p. 1086-1099.

135. Karp Richard M. A patching algorithm for the traveling salesman problem.- SIAM J.Comput.,1979, 8, N 4, p. 561-573.

136. Laporte Gilbert, Nobert Yves. Generalized- traveling salesman problem through n sets of nodes: an integer programming approach.- INJ?0R, 1983, 21, U 1, p. 61-75.

137. Oetti Wi. Einzelschrittverfaren zur i^zung konvexer und dual-konvexer Minimizierungsprobleme.- ZAMM, 1974, v.54, N 6,p. 343-351.

138. Padberg Manfred W., Hong Saman. On The symmetric traveling salesman problem : a computational study.- Math. Program. Study, 1980, 12, p. 78-107.

139. Ra0 A note on the multiple traveling salesman problem.-Oper. Res., 1980, 28, Ж 3, Part 1, p. 628-632.

140. Sebastian Hans-Jurgen, Gustafson Tore K. An approximative method for discrete optimal control problem and its application to a special class of transportation.- Math. Operationsforsch.und Statist. Ser. Optiiniz. ,1981, 12,N 4, p. 535-554.

141. Shoch Robert G. An exact algorithm for the small scale traveling-salesman problem.- Trans. III. State Acad. Sci., 1979, 72, N 1, p. 73-83.

142. Steward William R.Jr. A coputational comparision of five heuristic algorithms for the Euclidean traveling salesman problem.-bee.Notes Econ. and Math.Syst., 1982, 199, p.104-116.

143. Syslo M.M. Generalization of the standart traveling salesman problem.- Zast, math., 1980, 16, H 4, p. 621-629.

144. Работы автора по теме диссертации.

145. Герасимов В.А. Оптимальное объемно-календарное планирование производства экспортных пиломатериалов: Метод селекции. Красноярск, 1980. - 10 с. - Рукопись представлена ЦНИИ механ. обработки древесины. Деп. в ВНИПИЭИлеспром 29 мая 1980 г., № 556 д.

146. Герасимов В.А. Об одном методе оптимизации при оптимальном объемно-календарном планировании производства пиломатериалов на экспорт. В кн.: Применение математических методови ЭВМ в управлении лесной промышленностью. М.: ВНИПИЭИлеспром, 1980, с. 62-66.

147. Герасимов В.А. Оптимизация управления на дискретных множествах.- Красноярск, 1982. 17 с. - рукопись представлена Сибир. технологическим ин-том. Деп. в ВИНИТИ 22 января 1982г.,316.82 ДЕП.

148. Герасимов В.А. Решение задачи коммивояжера и некоторых ее обобщений методами оптимального управления. Красноярск, 1982. - 17 с. Рукопись представлена ВЦ СО АН СССР в г. Красноярске. Деп. в ВИНИТИ 4 августа 1982 г., Р 4266-82 ДЕП.

149. Герасимов В.А. Об одной модификации задачи коммивояжера.-В сб.: Методы и программы решения оптимизационных задач на графах и сетях: Тез. докл. П Всесоюзн. совещания 24-26 августа 1982 г. Улан-Удэ. Ч. 2. Новосибирск: ВЦ СО АН СССР,1982, с. 29-30.

150. Герасимов В.А. Принцип максимума Понтрягина для одного класса дискретных систем. В сб.: Информационно-оперативный материал.- Красноярск: Препринт ВЦ СО АН СССР в г. Красноярске,1983, № I, с. 43-44.

151. Герасимов В.А. Метод последовательных приближений для решения задач дискретного оптимального управления. В сб.: Информационно-оперативный материал. - Красноярск: Препринт ВЦ СО АН СССР в г. Красноярске, 1983, Р I, с. 45-46.

152. Герасимов В.А. Об одной модификации задачи коммивояжера. -Автоматика и телемеханика, 1983, Р 9, с. 161-164.

153. Герасимов В. А. Методы оптимизации дискретного управления. -Красноярск, 1984. 32 с. - Рукопись представлена ВЦ СО АН СССР в г. Красноярске. Деп. в ВИНИТИ 22 февраля 1984 г.,1. Р 1027-84 ДЕП.

154. Герасимов В.А. Формирование оптимальной производственной программы при ограничениях на поток вырабатываемой продукции. Красноярск, 1984. - 23 с. рукопись представлена

155. ВЦ СО АН СССР в г. Красноярске. Деп. в ВИНИТИ 2 июля 1984 г., № 4527г-84ДЕП.

156. Герасимов В.А., Зекцер Л.Д., Богачева Н.Н. Оптимальное управление потреблением реактивной мощности.- Красноярск, 1984.-18 е.- ^копись представлена ВЦ СО АН СССР в г. Красноярске. Деп. в ВИНИТИ 19 июля 1984 г., № 5254-84ДЕП.

157. Герасимов В.А., Зекцер Л.Д., Богачева Н.Н. Оптимальное управление потреблением активной мощности.-Красноярск,1984. 25 е.- Рукопись представлена ВЦ СО АН СССР в г. Красноярске. Деп. в ВИНИТИ 19 июля 1984 г., № 5255-84ДЕП.

158. Герасимов В.А., Погребняков А.С. Оптимальное планирование раскроя.- Красноярск, 1981.- 20 е.- Рукопись представлена ЦНИИ механ. обработки древесины. Деп. в ВНИПИЭИ леспром 9 января 1981 г., № 613 д.

159. Герасимов В.А., Погребняков А.С. Алгоритм решения задачи оптимального оперативно-календарного планирования (ОКП) производства пиломатериалов на экспорт.- Экономика и управление в лесной и деревообрабатывающей промышленности, 1979, № 3, с. 5-6.

160. Pogrebnjakov A.S.,Gerasimov W.A.,Dorrer G.A.,Glizer W.Ja., Dmitriev M.G. Optimal control of cutting proceses.-Proc. of the 3-rd IFAC/IFIP/IFORS Conferehce on System approach for development. Nov.1980.Rabat (Marocco).-Rabat,1980, p. 225-230.