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

• Шмелев, Виктор Васильевич
• доктор физико-математических наук
• 2000

Оглавление диссертации доктор физико-математических наук Шмелев, Виктор Васильевич

54 П ТГ ТТ и* "н Т/Г И' Ь,

1 д. .2/1 аев«*вв«ввве«««»«в««ее*«хв«еев«««ес**«е««е«««в« /

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

1.1. Задачи смешанного целочисленного линейного программирования и их классификация.

1.2. Задачи минимизации точных штрафных функций----.

1.3. Задачи, слабо двойственные к задачам минимизации точных штрафных функций.

1.4. Задача минимизации выпуклой кусочно-линейной штрафной функции, ее линейный эквивалент и слабо двойственные к

Й.^ЛУ! СЗ .¿^ С.1 '^.Х'Х «еееееагеввесеевсгевггФесавевееевеваввесааеевес« '—' I

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

2.1. Необходимые условия применимости.

2.2. Достаточные условия применимости.

2.3. Необходимые и достаточные условия применимости для выпуклой кусочно-линейной штрафной функции.

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

МИНИМИЗАЦИИ ТОЧНЫХ ШТРАФНЫХ ФУНКЦИИ. задачи минимизации точной штрафной функции, предназначенной для решения задачи смешанного целочисленного линейного программирования.

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

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

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

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

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

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

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

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

5.1. Двухэтапный метод последовательной оптимизации.

5.2. Общая схема мультипликативного метода.

5.3. Начальные значения штрафных коэффициентов.

Глава 6. ЗАДАЧИ ЛИНЕШНОГО ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ СО п.ъ-Г'.-пттг д 1гт/г Ч -г-рг

6.1. Общая постановка задачи линейного динамического программирования со свертками.

6.2. Примеры ограничений, описываемых с помощью свертки.

6.3. Задача Гифлера—Томпсона.2>îfo

С A QQTTCITTQ тэхтчгптптл'ттгпг'^РПТ'П тттго-тлгпгчтэаттгл'а тпдрvmГРГГг\-пп ^шфтгчшлтп^ произведет

6.5. Задача внутрицехового планирования непрерывного (поточного ) производства.

6.6. Задача теории расписаний с квантованным ресурсом.

6.7. Слабо двойственная задача линейного динамического программирования со свертками.

6.8. Задача минимизации точного штрафного функционала для

Введение диссертации (часть автореферата) на тему «Метод точных штрафных функций для линейных смешанных целочисленных задач оптимизации»

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

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

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

Задачи линейного программирования с целочисленными переменными имеют много разнообразных применений для оптимизации и моделирования технических, социально-экономических, вычислительных и других систем. Укажем лишь некоторые из них. Так в [681 сформулирована задача оптимального планирования работы производственно-технического комплекса, выпускающего дискретную продукцию; в [1661 предложена задача моделирования и проектирования производственных систем; в [381 описаны задача выбора масок для интегральных схем и задача синтеза телеинформационных сетей и т. д.

Динамические задачи, в которых присутствуют функции времени, принимающие только целочисленные значения, используются для описания задач теории расписаний, календарного и сетевого планирования. Такого рода описания можно найти в [30, 703. Перечисленные выше задачи используются для оптимизации функционирования производственно-технических систем, в том числе и гибких автоматизированных производств (см., например, [63-651), а также вычислительных систем [661.

Задаче линейного программирования посвящены ставшие уже классическими работы Л.В. Канторовича [323, Дж. фон Неймана [1343, Дж. Данцига [1063, Д. Гейла, Г. Куна, А. Таккера [111]. В этих работах получены необходимые и достаточные условия оптимальности, сформулирована теория двойственности, развит симплекс-метод, являющийся в настоящее время наиболее популярным методом решения задач линейного программирования.

Новый импульс для своего развития методы решения задач линейного программирования получили после выхода в свет широко известных работ Л.Г. Хачияна [77, 783 и Н. Кармаркара [1261, посвященные полиномиальным алгоритмам. С современным состоянием методов решения задач линейного программирования можно познакомиться в обзорах, сборниках и книгах [8, 10, 44, 47, 48, 62, 114, 120, 129, 131, 132, 135, 1383. Теории и методам решения задач линейного программирования посвящено много книг разного уровня, из которых упомянем лишь книги [1, 11, 62, 953.

История целочисленного линейного программирования фактически началась с работ Р. Гомори [117-1193, посвященных методу отсечения. Однако наиболее широко распространенным в настоящее время методом решения практических задач целочисленного линейного программирования является метод ветвей и границ, первая формулировка которого была дана в известной работе А. Ленд и А. Дойг И 283. С тех пор методы решения задач целочисленного линейного программирования бурно развивались. С их современным состоянием можно познакомиться в обзорах, сборниках и книгах ЕЗ, 43, 44, 62, 122, 123, 129, 133, 135, 136, 139, 1441.

В настоящее время существует несколько различных подходов к теории двойственности для задач целочисленного линейного программирования. Это минимаксный подход [98, 993, суррогатная двойственность [115, 116, 121, 127, 1403, двойственность по Лагранжу [100, 107-110, 112, 127, 141-1433, субаддитивная двойственность [41, 80, 81, 102, 104, 124, 125, 1453 и др. Ш один из этих подходов не является общепринятым. Среди книг и обзоров, посвященных целочисленному программированию и дискретной оптимизации, отметим книги и обзоры [34, 37, 38, 58, 62, 79, 1673.

Под линейными динамическими конечномерными задачами оптимизации будем понимать линейные динамические задачи, записанные в дискретном времени на конечных фиксированных интервалах. Наиболее простой и известной задачей такого рода является задача линейного динамического программирования, теорию и метода решения которой можно найти в [26-29, 39, 54, 553. Существуют постановки задач и с более сложными запаздываниями [42, 543.

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

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

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

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

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

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

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

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

На первом этапе, начавшемся с работы [1051, изучались гладкие штрафные функции применительно к задачам оптимизации с непрерывными переменными. Использование таких функций требует неограниченного увеличения штрафных коэффициентов. При этом оптимальные решения исходных задач получаются как пределы в общем случае бесконечных последовательностей промежуточных решений. Неограниченное увеличение значений штрафных коэффициентов приводит к плохой обусловленности решаемых задач, что делает практически невозможным их решение при больших значениях штрафных коэффициентов. Поэтому метод штрафных функций в таком варианте используется прежде всего для быстрого получения приближенных решений. Большое количество материала, посвященного гладким штрафным функциям, можно найти в книгах [75, 147 3 ив обзоре С1033. А о применении квадратичной штрафной функции для решения задач линейного программирования написано в книгах Е51, 953.

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

Метод точных штрафных функций применительно к задачам линейного программирования описан в книгах С20, 25]. Применению же этого метода к задачам нелинейного программирования посвящено довольно большое число работ. Среди них отметим работы [156, 164, 1651, посвященные получению необходимых и достаточных условий точности штрафных функций. Точные штрафные функции весьма общего вида рассматривались в [23, 148, 159, 1601 и других работах. В книге [1533 отмечено, что условия регулярности в выпуклом программировании есть не что иное, как условия точного решения задачи математического программирования методом штрафных функций при использовании негладкой штрафной функции. В работе [1583 теория точных штрафных функций используется как основа для развития теории условной оптимизации. Обзор современного состояния метода штрафных функций, в том числе и точных, применительно к задачам нелинейного программирования с непрерывными переменными можно найти в [103, 1483.

В работах автора [83, 903 было показано,что штрафные функции весьма общего вида являются точными для задач линейного целочисленного программирования. Поэтому метод штрафных функций для этих задач фактически всегда является точным. Недифференцируемые точные штрафные функции для задач смешанного целочисленного линейного программирования изучались в £1013. Точные штрафные функции для задач выпуклого целочисленного программирования рассматривались в [51, а для нелинейного целочисленного программирования - в [1631. Применительно к задачам математического программирования с булевыми перемеными точные штрафные функции использовались в С157, 161, 1621. Обзор метода штрафных, функций для задач дискретной оптимизации содержится в [1501.

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

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

Несобственные и противоречивые задачи линейного и выпуклого программирования интенсивно изучались И.И. Ереминым [13-251. Он построил теорию двойственности, предложил ряд методов решения и коррекции таких задач. Несобственные и противоречивые задачи линейного программирования, содержащие целочисленные переменные, ранее не изучались.

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

В диссертационной работе представлены:

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

- общая и простая постановка задачи линейного динамического программирования со свертками и ее применения к описанию конкретных задач календарного планирования;

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

Изложим содержание диссертационной работы по главам.

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

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

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

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

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

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

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

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

Для формул, теорем, лемм, определений и таблиц в диссертационной работе использована нумерация, где первым индексом является

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Шмелев, Виктор Васильевич

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

Список литературы диссертационного исследования доктор физико-математических наук Шмелев, Виктор Васильевич, 2000 год

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

2. Белоусов Е.Г. Введение в выпуклый анализ и целочисленное программирование. М.: Изд. МГУ, 1977.3= Белоусов Е.Г., Широнин В.М. Геометрия чисел и целочисленное программирование. М.: Знание, 1990.

3. Большаков В.А., Уздемир А.П., Шмелев В.В. Задачи планирования дискретного производства и численные методы их решения. М.: МПУ, 1976.

4. Большаков В.А., Уздемир А.П., Шмелев В.В. Задачи планирования дискретного (штучного) производства и численные метода их решения. III .// Автоматика и телемеханика. 1976. J6 1. С. 146156.

5. Большаков В.А., 1Шлелев В.В. Планирование мелкосерийного (штучного) производства // Проблемы управления в технике, экономике и биологии. М.: Наука, 1976. 0. 57-61.

6. Бугров Я.С., Никольский С.М. Дифференциальное и интегральное исчисление. М.: Наука, 1988.

7. Габасов Р., Кириллова Ф.М. Методы линейного программирования. 4.1. Общие задачи. Минск: Изд-во БГУ, 1977.

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

9. Голыптейн Е.Г.» Немировский A.C., Нестеров Ю.Е. О некоторых последних достижениях в оптимизации .// Экономика и математические методы. 1990. Т. 26. № 1. С. 178-190.

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

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

12. Еремин И.И. О методе штрафов в выпуклом программировании // Тезисы кратких научных сообщений Международного математического конгресса. Секция 14, Вычислительная математика. М.,1. А Г \ Г» Г1 Г": А1. Уоо = у. ¿54.

13. Еремин И.И. Метод штрафов в выпуклом программировании /7 Доклады АН СССР. 1967. Т. 173. Л 4. С. 748-751.

14. Еремин И.М. О задачах выпуклого программирования с противоречивыми ограничениями // Кибернетика. 1971. № 4. С. 124-129.

15. Еремин И. И. О задачах последовательного программирования // Сибирский математический журнал. 1973. Т. XI?. I 1. С. 53-63.

16. Еремин И.И. Двойственность для несобственных задач линейного и выпуклого программирования /7 Доклады АН СССР. 1981. Т. 256. Ш 2. С. 272-276.

17. Еремин И.М. Двойственность для несобственных задач линейного и выпуклого программирования и методы их коррекции // Известия АН СССР. Техническая кибернетика. 1983. * 1. 0. 20-32.

18. Еремин И.И. Противоречивые модели экономики. Свердловск: Средне Уральское изд-во, 1986.

19. Еремин И.И. Противоречивые модели оптимального планирования. М.: Наука, 1988.

20. Еремин И.И. Несобственные задачи оптимизации // Оптимизация: модели, методы, решения. Новосибирск: Наука, 1992. С. 69-81.

21. Еремин И.И. Двойственность в несобственном программировании

22. Кибернетика и системный анализ. 1996. J6 6. С. 125-137.

23. Еремин И.И. К методу штрафов в математическом программировании // ДАН. 1996. Т. 346. Ш 4. С. 459-461.

24. Еремин И.И., Мазуров В.Д. Нестационарные процессы математического программирования. М.: Наука, 1979.

25. Еремин И.И., Мазуров В.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983.

26. Иванилов Ю.П., Малашенко Ю.Е. О методе решения линейной динамической задачи .// Кибернетика. 1973. * 5. С. 42-49.

27. Иванилов 3D.П., Пропой A.M. О задачах линейного динамического программирования. /7 Доклады АН СССР. 1971. Т. 198. M 5.1. С. 1011-1014.

28. Иванилов Ю.П., Пропой A.M. Соотношения двойственности для задач линейного динамического программирования // Автоматика и телемеханика. 1973. » 12. С. 100-108.

29. Иванилов Ю.П., Пропой A.M. Задачи динамического линейного программирования. М.: МЦНТИ, 1973.

30. Иванов Ю.Н., Токарев В.В., Уздемир А.П. Математическое описание элементов экономики. М.: Физматлит, 1994.

31. Ицкович Э.Л., Соркш Л.Р. Оперативное управление непрерывным производством: задачи, методы, модели. М.: Наука, 1989.

32. Канторович Л.В. Математические методы организации и планирования производства. Л.: Мзд-во ЛГУ, 1939.

33. Кириллов А.А., Гвишиани А.Д. Теоремы и задачи функционального анализа. М.: Наука, 1979.

34. Ковалев М.М. Дискретная оптимизация. Минск: Изд-во БГУ, 1977.

35. Колмогоров А.Н., Фомин C.B. Элементы теории функций и функциопального анализа. М.: Наука, 1981.

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

37. Корбут A.A., Финкильштейн Ю.Ю. Дискретное программирование. М.: Наука, 1969.

38. Кофман А., Анри-Лабордер А. Методы и модели исследования операций. Т. 3. Целочисленное программирование. М.: Мир, 1977.

39. Кривоножко В.Е., Пропой A.M. Метод последовательного улучшения управления в задачах динамического линейного программирования. ч. I, II /./ Известия АН СССР. Техническая кибернетика. 1978. # 3. С. 5-16; X 4. С. 5-14.

40. Кудрявцев Л.Д. Краткий курс математического анализа. М.: Наука, 1989.

41. Лебедев С.С., Шейнман O.K. Двойственный подход в целочисленном программировании /./ Известия АН СССР. Техническая кибернетика. 1983. JM. С. 181-187.

42. Малашенко Ю.Е. Задачи линейного динамического программирования с запаздыванием /./ Журнал вычислительной математики и математической физики. 1972. Т. 12. iß 6. С. 1572-1578.

43. Меламед И.И. Нейронные сети и комбинаточная оптимизация // Автоматика и телемеханика. 1994. 1 11. С. 3-40.

44. Методы оптимизации в экономико-математическом моделировании / Под ред. Е.Г. Голыптейна. М.: Наука, 1991.

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

46. Моисеев H.H. Численные методы в теории оптимальных систем.1. М.: Наука, 1971,

47. Муртаф Б. Современное линейное программирование. М.: Мир, 1984.

48. Нестеров Ю.Е. Эффективные методы в нелинейном программировании. М.: Радио и связь, 1989.

49. Плискин Л.Г. Оптимизация непрерывного производства. М.: Энергия, 1975.

50. Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критериям. М.: Советское радио, 1975.

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

52. Понтрягин Л.С. Непрерывные группы. М.: Наука, 1973.

53. Проблемы оптимизации планирования в производственных объединениях / Отв. ред. В.И. Данилин. М.: ЦЭМИ, 1987.

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

55. Пропой А.И. Задачи и методы динамического линейного программирования /./ Известия АН СССР. Техническая кибернетика. 1983. Л 1. С. 127-142.

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

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

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

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

60. Смоляр Л.й. Оперативно-календарное планирование: модели и методы . М.: Экономика, 1979.

61. Суворов Б. П. Оптимизация текущего планирования нефтеперерабатывающего производства. IL: Наука, 1974.

62. Охрейвер А. Теория линейного и целочисленного программирования. Т. 1, 2. М.: Мир, 1991.

63. Танаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний. Одностадийные системы. М.: Наука, 1984.

64. Танаев B.C., Оотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. М.: Наука, 1989.

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

66. Теория расписаний и вычислительные машины / Под. ред. Э.Г. Кофмана. М.: Наука, 1984.

67. Титов В.В. Оптимизация функционирования промышленного предприятия. Вопросы методологии и моделирования. Новосибирск; Наука. Оиб. отд-ние, 1987.

68. Уздемир А.П. Задачи планирования дискретного (штучного) производства и численные методы их решения. I // Автоматика и телемеханика. 1975. J6 9. С. 115-122.

69. Уздемир А.П. Задачи планирования дискретного (штучного) производства и численные методы их решения. II // Автоматика и телемеханика. 1975. Л 10. С. 90-104.

70. Уздемир А.П. Динамические целочисленные задачи оптимизации в экономике. М.: Физматлит, 1995.

71. Уздемир А.П., Большаков В.А. Система планирования дискретного производства. Препринт. М.: ВНИИСИ, 1983.

72. Уздемир А.П., Шмелев В.В. целочисленные динамические задачи экономического планирования с сетевыми ограничениями. I .//

73. Автоматика и телемеханика. 1978. М 7. С. 106-115.

74. Уздемир А.П., Шмелев В.В. Целочисленные динамические задачи экономического планирования с сетевыми ограничениями. II // Автоматика и телемеханика. 1978. J 9. 0. 110-120.

75. Феллер В. Введение в теорию вероятностей и ее приложения. Т. 1, М.: Мир, 1984.

76. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. М.: Мир, 1972.

77. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. Т. 1. М.: Физматгиз, 1962.

78. Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании // Доклады АН ССОР. 1979. Т. 244. №5. С. 1093-1096.

79. Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании /У Журнал вычислительной математики и математической физики. 1980. Т. 20. № 1. С. 51-68.

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

81. Шейман O.K. Двойственность в некоторых дискретных задачах минимизации /./ Успехи математических наук. 1978. Т. 33. №2. С. 211.

82. Шейнман O.K. Двойственность и субаддитивные функции в целочисленном программировании /./ Экономика и математические методы. 1980. Т. 26. I 4. С. 808-810.

83. Шенброт И.М., Антропов М.В., Ромм B.C. Оперативно-календарное планирование химических производств в автоматизированных системах управления. М.: Химия, 1977.

84. Шмелев В.В. Штрафные функции в целочисленном линейном программировании /7 Автоматика и телемеханика. 1975, & 9. С. 203206.

85. Шмелев В.В. Динамическая задача межцехового планирования //

86. Моделирование и управление в развивающихся системах. М.: Hay А i Г*?-: П >~\ -' С"1. КИ, I VI О. \j. t&U—t&Q.

87. Шмелев В.В. Решение задач целочисленного линейного программирования методом штрафных функций // Автоматика и телемеханика. 1978. * 11. С. 149-157.

88. Шмелев В.В. Метод упорядочения в задачах календарного планирования. Препринт. М.: ВНИИСИ, 1983.

89. Шмелев В.В. Метод точных штрафных функций для решения задач линейного и целочисленного линейного программирования // Журнал вычислительной математики и математической физики. 1988. Т. 28. M 10. С. 1594-1595.

90. ПМелев В.В. Метод точных штрафных функций для решения задач линейного и целочисленного линейного программирования. М., 1988. Деп. в ВИНИТИ 9.03.88, M 1904-В88.

91. Емелев В.В. Метод точных штрафных функций для решения задач линейного и целочисленного линейного программирования // Методы математического программирования и программное обеспечение. Свердловск: ИММ УрО АН СССР, 1989. С. 220-221.

92. Шмелев В.В. Точные штрафные функции в линейном и целочисленном линейном программировании // Автоматика и телемеханика. 1992. M 5. С. 106-115.

93. Шмелев В.В. Динамические задачи календарного планирования. М., 1995. Деп. в ВИНИТИ 16.08.95, ü 2463-В95.

94. ПМелев В.В. Мультипликативный метод точных штрафных функцийдля задач линейного и целочисленного линейного программирования /7 Автоматика и телемеханика. 1996. il 1. 0. 128-138.

95. Шмелев В.В. Динамические задачи календарного планирования /./ Автоматика и телемеханика. 1997. J6 1. С. 121-125.

96. Экономико-математические модели в системе управления предприятиями / Под ред. Н.П. Федоренко, И.П. Щубкиной. М.: Наука,1983.

97. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование (теория, методы и приложения). М.: Наука, 1969.

98. Ядыкин А.Б. Нелинейная параметрическая оптимизационная система Омега большой размерности // Сборник трудов ВНИИ системных исследований. 1984. M 13. С. 55-67.

99. Abadie J. Une methodLe arborescente pour les programmes nonli-neaires partiellement discrets /7 Revue française d'informa-tiqe et de recherche opérâtlonelle. 1969. v. 3. p. 24-50.

100. Balas E. Duality in discrete programming // Proceedings of the Princeton Symposium on Mathematical Programming / Ed. H. W. Xuim. Princeton: Princeton University Press, 1970. P. 179197.

101. Balas E. linimax and duality for linear and nonlinear mixed-integer programming // Integer and Nonlinear Programming / Ed. J. Abadie. Amsterdam: North-Holland, 1970. P. 385-418.

102. Bell D.E., Shapiro J.P. A convergent duality theory for integer programming // Operations Research. 1977. V. 25. No. 3. P. 419-434.

103. Blair O.E., Jeroslow R.G. An exact penalty method for mixed-integer programs // Mathematics of Operations Research.1981. V. 6. No. 1. P. 14-18.

104. Blair C.E.t Jeroslow R.G. The value function of an integer program // Mathematical Programing. 1982. V. 23. No. 3. P.1. OTT OTO C.O i — C. i <> .

105. Boukari P., Piacco A.Y. Survey of penalty, exact-penalty and multiplier methods from 1968 to 1993 // Optimisation. 1995. Y. 32. No. 4. P. 301-334.

106. Burdet O.A., Johnson E.I. A subadditive approach to solve linear Integer programs // Studies in Integer Programming / Ed. P.I. Hammer et al. Annals of Discrete Mathematics. 1977. Y. 1. P. 117-143.

107. Courant R. Yariational methods for the solution of problems of equilibrium and vibrations /'/ Bulletin of American Mathematical Society. 1943. V. 49. No. 1. P. 1-23.

108. Bantzig G.B. Maximization of a linear function of variables subject to linear Inequalities /7 Activity Analysis of Production and Allocation / Ed. T.G. Koopmans. New York : Wiley, 1951. P. 339-347.

109. Everett H. Generalized Lagrange multiplier method for solving problems of optimum alocation of resources /7 Operations Research. 1963. V. 11. No. 3. P. 399-417.

110. Fisher M.L. The Lagrangian relaxation method for solving integer programming problems // Management Science. 1981. Y.01 T> P,1 • JL • I I •

111. Fisher M.L., Shapiro J.P. Constructive duality in integer programming // SIAM Journal on Applied Mathematics. 1974. V.on- Wr, 1 V -RO- OQA ~

112. Plippo O.E. Stability, duality arid decomposition in general mathematical programming. Amsterdam : Stiching Mathematisch Centrum, 1991.

113. Gale D., Kuhn H.W., Tucker A.W. Linear programing -and the theory of games // Activity Analysis of Production and Allocation / Ed. T.G. Koopmans. New York : Wiley, 1951. P. 317329.

114. Geffrion A.M. Lagrangean relaxation for integer programming /'/ Mathematical Programming Study. 1974. V. 2. P. 82-114.

115. Giffler B., Thompson G.L. Algoritlims for solving production-scheduling problems // Operation Research. 1960. V. 8. No. 4. P. 487-503.

116. Gill P.E., Murray W., Wright M.H. Numerical linear algebra and optimisation. V. 1. Redwood City : Addison-Wesly,1991.

117. Glover f. Surrogate constrains // Operations Research. 1968. V. 16. P. 741-749.

118. Glover P. Surrogate constraint duality in mathematical programming // Operations Research. 1975. V. 23. P. 434-451.

119. Gomory R.E. Outline of an algorithm for integer solution to linear programs // Bulletin of the American Mathematical So-1 ORP. XT Kl In R V OVR-OVa- U.y « ./ '■-J '-J tt « c v s 1H * • c j. * { ' i i »-/ *

120. Gomory R.E. An algorithm for the mixed integer problem. RAND Report. P-1885. Santa Monica : 1960.

121. Gomory R.E. An all-integer programming algorithm // Industrial Scheduling / Ed. J.?. Muth, G.L. Thompson. New Jersey : Prentice-Hall, Englewood Cliffs, 1963. P. 193-206.

122. Gonsaga 0.0. Path-following methods for linear programming // SIM Review. 1992. Y. 34. No. 2. P. 167-224.

123. Greenberg H.J., Pierskalla W.P. Surrogate mathematical programming // Operations Research. 1970. Y. 18. P. 924-939.

124. Handbook of convex geometry. V. А, В / Ed. P.M. Gruber, J.M. Wills. Amsterdam : North-Holland, 1993.

125. Ibaraki T. Enumerative approaches to combinatorial optimisation. P. 1, 2. Basel : Baltzer AG, 1988.

126. Jeroslow R.G. Outting-plane theory: algebraic methods // Discrete Mathematics. 1978. V. 23. P. 121-150.

127. Jeroslow R.G. Minimal inequalities /7 Mathematical Programming. 1979. V. 17. P. 1-15.

128. Karmarkar N. A new polynomial-time algorithm for linear programming // Oombinatorica. 1984. Y. 4. No. 4. P. 373-395.

129. Karwan M.H., Rardin R.L. Some relationships between Lagran-gian and surrogate duality in integer programming. // Mathematical Programming. 1979. V. 17. No. 3. P. 320-334.

130. Land A.H., Doig A.G. An automatic method of solving discrete programming problems /7 Econometrica. 1960. Y. 28. No. 3. P. 497-520.

131. Mathematical programming. Recent development and. applications / Ed. M. Iri, K. Tanabe. Dordrecht : Kluwer Academic Publishers, 1989.

132. Meyer R.R. On the existence of optimal solutions to integer and mixed-integer programming problems // Mathematical Programming. 1974. V. 7. No. 2. P. 223-235.

133. Murray W. Methods for large-scale linear programming // Algorithms and Model Formulations / Ed. S.W. Wallace. Berlin etc. : Springer-"Verlag, 1989. P. 115-137.

134. Nazareth J.L. Computer solution of linear programs. Oxford : Oxford University Press, 1987.

135. Nemhauser G.L., Wolsey L.A. Integer and combinatorial optimisation. New York etc. : Wiley, 1988.

136. Yon Neuman J. Discusión of a maximum problem // John топ Neuman, Collected Works / Ed. A.H. Taub. Oxford : Pergamon Press, 1963. V. VI. P. 89-95.

137. Optimization / Ed. G.L. Nemhauser, A.H.G. Hinnooy Kan, M.J. Todd. Amsterdam : North-Holland, 1989.

138. Parker G.R., Rardin R.L. Discrete optimisation. London : Academic Press, 1988.

139. Parker R.G. Deterministic shedullng theory. London : Chapman and Hall, 1995.

140. Progress in mathematical programming. Interior-point and related methods / Ed. Megiddo N. Berlin : Spriger-Verlag, 1989.

141. Salkin H.M., Mathur K. Foundations of Integer programming. Amsterdam etc. : North-Holand, 1991.

142. Sarin S., Karwan M.H., Rardin R.L. A new surrogate dual multiplier search procedure // Naval Research Logistics. 1987. V. 34. No. 3. P. 431-450.

143. Shapiro J.F. Generalised Lagrange multipliers in integer programming /7 Operations Reaseareh. 1971. V. 19. No. 1. P. 68-76.

144. Shapiro J.F. A survey of bagrangean techniques for discreteoptimization // Discrete Optimization II / Ed. P.L. Hammer, E.L. Johson, B.H. Korte. Annals of Discrete Mathematics.1Q7Q V R P 1 -i Qp

145. I d Ч с W e X 9 { W I UL• a

146. Tind J., Wolsey L.A. An elementary survey of general duality theory in mathematical programming // Mathematical Programming. 1981. V. 21. No. 3. P. 241-261.

147. Walukiewicz S. Integer programming. Dordrecht etc. : Kluwer Academic Publishers, 1991.

148. Wolsey L.A. Integer programming duality : price functions and sensitivity .analysis // Mathematical Programming. 1981. V. 20. No. 2. P. 173-195.

149. Zangwill W. Non-linear programming via penalty function /7 Management Science. 1967. V. 13. No. 5. P. 344-358.

150. Гроссман К., Каплан А.А. Нелинейное программирование на основе безусловной минимизации. Новосибирск : Наука. 1981.

151. Евтушенко Ю.Г., Жадан В.Г. К вопросу о систематизации численных методов нелинейного программирования. М. : ВЦ АН СССР, 1988.

152. Левин В.И. Структурно-логические метода исследования сложных систем с применением ЭВМ. М. : Наука, 1987.

153. Сергеев С.И. Условия оптимальности в задачах дискретной оптимизации // Автоматика и телемеханика. 1997. J№ 3. 0. 3-19.

154. Уздемир А.П., Шмелев В.В. Обобщенная задача календарного планирования дискретного производства. I // Автоматика и телемеханика. 1999. М 2. С. 103-111.

155. Уздемир А.П., Окелев В.В. Обобщенная задача календарного планирования дискретного производства. II /7 Автоматика ителемеханика. 1УУ9. Л 4. С. 103-110.

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

157. Bertsekas D.P. Necessary and sufficient conditions for a penalty method to be exact // Mathematical Programming. 1975. V. 9. No. 1. P. 87-99.

158. Borchardt M. An exact penalty approach for solving a class of minimisation problems with boolean variables // Optimization. 1988. V. 19. No. 6. P. 829-838.

159. Burke J.V. An exact penalisation viewpoint of constrained optimization // SI AM Journal on Control and Optimisation. 1991. V. 29. No. 4. P. 968-998.

160. Han S.P., Mangasarian O.L. Exact penalty function in nonlinear programming // Mathematical Programming. 1979. V. 17. No. 3. P. 251-269.

161. Han S.P., Mangasarian O.L. A dual differentiable exact penalty function // Mathematical Programming. 1983. V. 25. P. 293-306.

162. Kalantari В., Rosen J.B. Penalty for sero-one integer equivalent problems // Mathematical Programming. 1982. V. 24. No. 2. P. 229-232.

163. Kalantari В., Rosen J.В. Penalty formulation for sero-one nonlinear programming // Discrete Applied Mathematics. 1987. Y. 16. No. 2. P. 179-182.

164. Sinclair M. En exact penalty function approach for nonlinear integer programming problems // European Journal of Operational Research. 1986. Y. 27. No. 1. P. 50-56.

165. Zang Lian-sheng. A sufficient and necessary condition for globally exact penalty function // Chinese Annals of Mathematics. Ser. A. 1997. Y. 18. No. 5. P. 579-586.

166. Zang Lian-sheng. A necessary and sufficient condition for global exactness of penalty functions // Chinese Journal of Contemporary Mathematics. 1998. Y. 18. No. 4. P. 415-424.

167. Хоботов E.H. Использование оптимизаццонно-имитационного подхода для моделирования и проектирования производственных систем. Ч. 1, II /./ Автоматика и телемеханика. 1999. Л 8. С. 163-176; £ 9. С. 154-161.

168. Леонтьев В.К. Дискретные экстремальные задачи // Итоги науки и техники. Сер. Теория вероятностей. Математическая статистика. Теоретическая кибернетика. 1979. Вып. 16. С. 39-101.