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

РОССИЙСКАЯ АКАДЕМИЯ НАУК

ИНСТИТУТ СИСТЕМНОГО АНАЛИЗА фд

9 г - г

Специализированный совет Д 003.63.02 ^ *¿1 О

На правах рукописи

Е.ЕЯЕВ Виктор Васильевич

УДК 519.85

МЕТОД ТОЧНЫХ ШГРМНЫХ ШШЦИП ДЛЯ ЛИНЕЕШ СМЕШАННЫХ 1ЩЯ0ЧИСЛЕННЫХ ЗАДАЧ ОПТИМИЗАЦИИ

Специальность: 05.13.01 - Управление в технических системах

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

Москва - 2000 г.

Работа выполнена в Институте системного анализа Российской Академии Наук (ИСА РАН)

Официальные оппоненты: доктор физико-математических наук,

профессор Афанасьев А.П. доктор физико-математических нар, профессор Леонтьев В.К. доктор технических наук Хоботов E.H.

Ведущая организация: Институт проблем управления РАН

Защитз состоится " "_ 2000 г. в_час. на

заседании специализированного совета Д 003.63.02 Института системного анализа РАН по адресу: 117312, г, Москва, проспект 60-летия Октября, д. 9.

С диссертацией можно ознакомиться в библиотеке Института системного анализа РАН.

Автореферат разослан " "_ 2000 г.

Ученый секретарь специализированного совета,

доктор технических наук, профессор Пропой А.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

ми.

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

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

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

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

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

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

Разработанные в диссертации методы могут быть использованы

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

Апробация работы. Результаты настоящей диссертации докладывались на Всесоюзном рабочем совещании по численным методам решения экономических задач (г. Звенигород, Московская обл., 1976 г.), Всесоюзном семинаре "Метода дискретной оптимизации в АСУ" (г. Алушта, 1983 г.), Всесоюзном семинаре "Дискретная оптимизация: метода и приложения" (г. Севастополь, 1984 г.), Всесоюзной конференции "Методы математического программирования и программное обеспечение" (г. Свердловск, 1989 г.), Международной конференции по проблемам управления (г. Москва, 1999 г.), на научных семинарах Вычислительного центра РАН, Института проблем управления РАН, Института системного анализа РАН, Международного научно-исследовательского института проблем управления, Московского государственного университета. Центрального экономико-математического института РАН.

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

Структура и объем работы. Диссертационная работа состоит из введения, шести глав, заключения, списка литературы из 167 наименований, приложения и двух таблиц. Текст диссертации без списка литературы, приложения и таблиц составляет 272 страницы машинописного текста, общий объем - 296 страниц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

В разделе 1.1 рассмотрена следующая задача смешанного целочисленного линейного программирования (СЦЯП):

min <с,х>,

АХ}Ъ, (1.1)

X € zk *

Здесь <v,w> - скалярное произведение произвольных векторов v и w;

А - матрица ограничений размера и * n; « - множество n-мерных векторов, первые k (0 ^ k $ п) компонент которых являются целыми числами, а последние п - k компонент - вещественными числами. Все Еекторы здесь и в дальнейшем предполагаются векторами-столбцами. При k = 0 задача (1.1) является задачей линейного программирования (ЛП), а при k = п - задачей целочисленного линейного программирования (ЦШ).

Всюду в дальнейшем будем предполагать, что при k z 1 все коэффициенты задачи СЦЛП (1.1) (коэффициенты матрицы ограничений А, коэффициенты вектора правых частей системы ограничений Ь, коэффициенты вектора целевой функции с) - рациональные числа. Рассмотрим задачу ЛП

min <с,х>,

Ах>Ъ, (1.2)

xtRn.

полученную из задачи (1.1) заменой при & > 1 условия частичной

целочисленности i f ^ > if1'^' условием х € й". Задача ЛП, являющаяся двойственной к задаче ЛП (1.2), имеет вид:

max <Ь,у>,

АГУ = С, (1.3)

У £ о, у с я*.

где 4Т - матрица, полученная из матрицы А транспонированием.

Будем называть задачу ЛП (1.3) слабо двойственной к задаче СЦЛП (1.1). Такое название вызвано тем, что разность мевду оптимальными значениями задачи СДЯП (1.1) и задачи Ж (1.3) (зазор двойственности) может быть отличной от нуля.

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

Все множество индексов ограничений задачи СЦЛП (1.1) И = = {1,...,п} разобьем на попарно непересекащиеся подмножества

I е Гд, где Г0 = I I) (О) и 0 £ Г, содержащие по элементов. Здесь I ? 0, множество может быть пустым (т0= 0), а кавдое из подмножеств I е Г. не является пустым (я^ > 0). Этому разбиению соответствует разрез по горизонтали матрицы ограничений А на подматрицы А1, I £ 10, и вектора правых частей ограничений Ь на

подвекторы Ь^, I е 10.

При применении метода штрафных функций к задаче СВДП (1.1) ограничения, индексы которых входят в годашкестЕО М0, будем учитывать непосредственно. Те же ограничения, индексы которых входят в подмножества { е I, будем учитывать путем введения дополнительных штрафных членов в целевую функцию.

Для общих задач СЦЛП еидэ (1.1) использована штрафная функция

Р^ХИ!) = <С,Х> + 2 и(Ф*[(Ъ{ - А)+].

Ш

Здесь и = (и{! I € I), 0 для всех I е I; вектор у+ получается из произвольного вектора у путем замены его отрицательных компонент нулями; функции 3>.[(у), I е Г, могут быть разными

для разных ¿; каждая функция ф|(у), I € I, удовлетворяет условиям:

а) t*(v) > 0 для всякого v Ф О, Ф*(0) = 0;

f mi

б) Ш1(v) - выпуклая, конечная при всех v е R ,

в) (0;v) > 0 для всякого v ? О, где

в}(0 + XV) - ®}(0)

ф{'(0;т) = Ии-

ЦО X

- односторонняя производная функции ®*(v) в точке 0 по направлению V.

Для задач СЦЛП частного вида - задач ЦЛП (к = п) - используется более общая штрафная функция

F2(x;u) = <c,j> + 2 и£ф|{ (Ъ1 - A)+J. t€l

Здесь каждая функция (v), i i I, удовлетворяет только условиям а) и б). Функции ф|(т), i € I, могут быть разными для разных i.

Использование метода точных штрафных функций применительно к общим задачам СЦЛП вида (1.1) заключается в решении задачи

min ?1(х;и),

А°х>Ъ°, (1.4)

I € Zk «

А для общих задач ЦЛП вида (1.1) будем решать задачу

min Р2(х;и),

(1.5)

X е Л

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

Для каждой функции ©{(v), £ с I, определим поляру ф|(я), положив

Ф*(») = sup <W,T> / «{(V). (1.6)

7^0

Лемма 1.4. Каждая из поляр ф|(я), I z Г, удовлетворяет условиям а) и б) и является положительно однородной.

Слабо двойственной к задаче (1.4) назЕанз задача max <b,y>, А1У = с,

у ^ о, (1.7)

®{(УС) < ut, С € Г, У с я",

где у = (r/j|Z € if); У{ = (yj|i е iff), I € IQ. Она отличается от слабо двойственной задачи ЛП (1.3) только наличием дополнительных ограничений ф|(у{) ^ Uj, t е I, задающих, нижние границы для значений штрафных коэффициентов u(, i е I,.

Перейдем к описанию задачи, являющейся слабо двойственной к задаче (1.5).

Лемма 1.6. Для каждого i е I существует число Pj > О такое, что

= niin {ф|[(Ь1 - А)+]|(Ь{ - А)+ * 0, х € Л.

Рассмотрим множества уровня ) = {v|®g(7) < v е € Я i € I, где положительные числа р(, i el, определены в формулировке леммы 1.6, и их опорные функции 5*(w| V^Ог)) = sup {<w,v>| т € Vg(j3j)}, t € Г. Для каждого t е I определим функцию $2(я), положив

Ф|(я) = 3*{w| У*ф())/р£. (1.8)

Лемма 1.7. Каадая из функций Фр(и), i € I, удовлетво-

ряет условиям а), б) и является положительно однородной.

Слабо двойственной к задаче (1.5) называна задача

шах <Ь,у>,

А1У = с,

у>0, (1.9)

«lûr'XUf ( € Г»

У € if,

Отметим, что обе слабо двойственные задачи (1.7) и (1.9) всегда являются задачами выпуклого программирования.

В разделе 1.3 рассмотрена выпуклая кусочно-линейная штрафная функция Fj(ï;u) более частного вида, чем штрафные функции F1(х;и) и F2(x;u). Эта функция строится с помощью монотонно неубывающих на неотрицательном ортанте кусочно-линейных октаэдрической и кубической норм

й(

= Е |Wjl и îv|ffi = max |иг|, t=1 НШ,

ml

где v = (i»j|1 < Z ^ îï!j) е R . Специфика функции Fj(x;u) позволяет усилить для нее ряд результатов, справедливых для функций P1(х;и) и F2(x;u). В данном разделе в явном виде выписаны прямая задача минимизации (1.10) штрафной функции ?3(х;и) и слабо двойственная к ней задача (1.15). Специфика этих задач, являющихся частными случаями задач (1.4) и (1.7) соответсвенно, состоит в том, что их можно эквивалентным образом переписать в виде частных случаев задачи СЦЛП (1.1) и слабо двойственной к ней задачи ЛП (1.3) соответственно.

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

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

Через Р1 и Р2 будем обозначать множества допустимых решений задач (1.4) и (1.5) соответственно.

Теорема 2.1. Пусть Р1 ф 0. Если при этом У = 0, то при любых конечных неотрицательных значениях штрафных коэффициентов ц£, I е I, будет 1п1СР1 (х;и)| х е Р^У = - со.

Теорема 2.2. Пусть Р2 ф 0. Если при этом 7 = 0, то при любых конечных неотрицательных значениях штрафных коэффициентов и{, { € I, будет Ш£Рг (х;и) | х е Р2> = - оо.

Теоремы 2.1 и 2.2 выделяют класс задач СЩШ которые нельзя решать методом штрафных функций. Этот класс состоит из тех задач, слабо двойственные задачи ЛП к которым не имеют допустимых решений.

Из теорем 2.1 и 2.2 непосредственно следуют необходимые условия применимости метода штрафных функций к задачам СЩП. Эти условия заключаются в существовании допустимых решений у задач ЛП, являющихся слабо двойственными к соответствующим задачам СЦЛП.

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

Множества допустимых решений слабо двойственных задач (1.7) и (1.9) будем обозначать через (и) и 02(и) соответственно.

Теорема 2.3. Пусть Р1 .Ф 0. Если при этом Д, (и) ф 0, то для любого х е Р1 и для любого у е Д, (и) будет ?1 (х;и) ^ 2 <ь,у>.

Теорема 2.4. Пусть Рг.Ф 0. Если при этом В2(и) Ф 0, то для любого х € Р2 и для любого у € Л2(и) будет Р2(х;и) £

^ <Ь,у>.

Теоремы 2.3 и 2.4 дают достаточные условия ограниченности снизу значений штрафных функций и, следовательно, применимости метода штрафных функций к задачам СЦШ1. Эти условия заключаются в существовании допустимых решений у слабо двойственных задач (1.7) и (1.9) соответственно. От необходимых условий применимости они отличаются только дополнительными неравенствами снизу для значений штрафах коэффициентов.

В случае штрафных функций Р1 (х;и) и Р2(х;и) общего гида между необходимыми и достаточными условиями ограниченности снизу значений этих функций есть разрыв. В необходимых условиях требуется непустота множества Г допустимых решений слабо двойственной задачи ЛП (1.3). А в достаточных условиях - непустота более узких из-за включений (и) с г и £>2 (и) с у множеств Д1 (и) и (и) допустимых решений слабо двойственных задач (1.7) и (1.9) соответственно. В разделе 2.3 показано, что для выпуклой кусочно-линейной штрафной функции Р3(х;и) этот разрыв можно устранить, получив условие ограниченности снизу значений этой функции, которое является одновременные необходимым и достаточным.

За множеством допустимых решений задачи (1.10) минимизации

штрафной функции Р^х'.и) сохраним ранее использованное обозначение Р,. А множество допустимых решений слабо двойственной задачи (1.15) обозначим через гуи).

Теорема 2.5. Пусть Р1 Ф 0. Тогда необходимым и достаточным условием конечности 1пПРз(х;и)| х е ?1) является непустота множества

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

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

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

Через Р*(и) и Р*(и) будем обозначать множества оптимальных

решений задач (1.4) и (1.5) соответственно.

Теорема 3.1. Пусть Р1 ф 0. Если при этом система

/у = с,

у ? О, (3.1)

ф}(у()<и{, 1(1, У € Я»

имеет допустимые решения, то Р*(и) Ф 0.

Теорема 3.2. Пусть Р2 * 0. Если при этом система /у = с,

у > о, (3.3)

фуЬ < { € I,

У

имеет допустимые решения, то Р^(и) ^ 0.

Специфика выпуклой кусочно-линейной штрафной функции Р3(х;и)

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

через Р*(и).

Теорема 3.3. Пусть Р1 1 0. Тогда необходимым и дос-

'з<

таточным условием непустоты множества р£(и) является непустота

множества Е>3(и).

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

название точные штрафе функции.

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

Сначала рассматривается случай задачи ЛП. Через X* и Г* будем обозначать множества оптимальных решений задачи СЩП (1.1) и слабо двойственной задачи ЛП (1.3) соответственно.

Теорема 4.1. Пусть к = 0 и X + 0. Если при зтом система

ф{(у{)<и(, 1 <е I, (4.1)

У € У*

имеет допустимые решения, то X* = Р*(и) Ф 0. Далее рассмотрен случай задачи НТО.

Напомним, что X и Г - это множества допустимых решений задач (1.1) и (1.3) соответственно, а положительные числа { € I, определены в формулировке леммы 1.6.

Теорема 4.2. Пусть к = п. Если при этом система

Ф^У*) + «с,х> - <Ь,У>) / < и£, I е I; (4.2)

х е X; у € 7

имеет допустимые решения, то X* = Р*(и) 1 0.

Штрафная функция Р1(х;и), предназначенная для решения общих

задач СЦЯП, является частным случаем штрафной функции Р2(х;и),

предназначенной для решения только задач ЦЛП. Поэтому свойство точности функции ^(х;и) для задач ЦЛП непосредственно следует из

теоремы 4.2. Однако в разделе 4.3 доказан аналог этой теоремы специально для функции Р.(х;и). При этом получены новые нижние

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

Введем положительные числа

= min щ[[(Ь{ - А)+3|(Ь1 - ?! О, х i Л, I € Г.

Существование таких чисел следует из леммы 1.G.

Теорема 4.3. Пусть к = п. Если при этом система

ф{(у() + «С,х> - <Ь,у>) / |Л{ < u{, ( € I;

х € I; У € У

имеет допустимые решения, то X* = Р*(и) Ф 0.

В разделе 4.4 рассмотрен случай задачи СЩП с непрерывными и целочисленными переменными (1 $ k $ п - 1).

Теорема 4.4. Пусть 1 значения

штрафных коэ(Дициентов удовлетворяют системе строгих неравенств

ф{(о1) < u{, I € Г. (4.5)

Если при этом в случае 2й \ S Ф 0 система

ф}(У() + £<с,х> - <Ь,у>]ф}(т]1) <ut, Ii I; (4.6)

х € X] у е У,

а в случае S = fi система

Ф{(У{) < t£{, { е I; (4.7)

у € У

имеет допустимые решения, то К* = Р*(и) Ф 0.

Здесь S - это проекция множества X на первые k координат,

векторы о^, rf, Iii, определяются условиями исходной задачи СЩП (1.1) и являются постояными. Доказано, что при выполнении предположений теоремы 4.4 эти векторы существуют, все их компоненты конечны и неотрицательны.

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

Для упрощения и сокращения записи нижние индексы у штрафных

функций и ?2(х;и), функций фг), фу), ф|(я) и Ф*(*),

множеств Р1 и Р2 всюду в дальнейшем будем опускать. Под функцией Р(х;и) будем понимать каждую из функций £,(х;и) и Р2(х;и), если

не оговорено противное. Аналогично для других обозначений.

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

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

штрафных слагаемых Ф1[(Ъ{ - 41х)+1 внутри групп, их содержащих.

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

чения:

со^х) = £ <? Ш11(Ъ1 - А)+],

J = 1,

з;

Ш,

^(х) = <с,х> + 2

/ = 1,

э,

где яа(х) = <с,х>, > 0 для всех £ ( I.

В двухэтапном методе последовательной оптимизации штрафной функции Р(х^), где ц = (д{| I е I) с постоянными положительными

значениями штрафах коэффициентов I € Г, предназначенном для решения задачи (1.1), выполняется з итераций. Каждая итерация метода состоит из двух этапов, выполняющихся последовательно и заключающихся в решении соответствующей задачи оптимизации.

На первом этапе первой итерации решается задача

min 10,(1), (5.1)

х € Р.

а на первом этапе каждой следующей J-й итерации, j = 2.....з, -

задача

min Wj(x),

<ot(x) ^ 7j, t = 1, 1; (5.2)

x € P.

где - оптимальное значение задачи первого этапа итерации t, t = 1, ..., з.

На втором этапе каждой /-й итерации, J = 1, .... з, решается задача

min gj{x)

(х) « Tt. t = i, .... /; (5.3)

X € p,

которая на втором этапе последней итерации з тлеет вид min <с,х>

wf(x) $ 7t, i = 1, ..., з; (5.4)

х е Р.

Через Dj и Gj, J = 1, ..,, з, будем обозначать множества оптимальных решений задач (5.1), (5.2) первого этапа и задач (5.3), (5.4) второго этапа каждой J-й итерации соответственно.

Теорема 5.1. Пусть Р Ф 0. Если при этом система ЛтУ = с,

у » 0, (5.9)

ф£ (у£) < qt, i € I,

У с ^

имеет допустимые решения, то Ь^ * 0 и ?! 0 для каждой у-й ите-рзции, где / = 1, ..з.

Напомним, что X и X* - это множества допустимых и оптимальных решений задачи СЦЯП (1.1) соответственно.

Следствие 5.1. Пусть выполняются предположения теоремы 5.1 и дополнительно I Ф 0. Тогда = О для всех 3 = = 1, ..., а и С. = X*.

О

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

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

В предлагаемом варианте метода точных штрафных функций (мультипликативном методе), предназначенном для решения общих задач СЩШ вида (1.1), выполняется не более а итераций. Оптимизация каждый раз производится на одном и том же множестве Р допустимых решений задачи (1.4) или (1.5) соответственно. Начальными значениями штрафных коэффициентов на первой итерации являются введенные выше положительные коэффициенты q^, I е I.

На каждой ,7-й итерации, 1 ^ И э, оптимизируется одна и та же штрафная функция Р(х;и^) с переменными значениями штрафных ко-

эф&щиентов г/ = I с Г). При этом значения штрафных коэффициентов с индексами из группы Г^ и предшествующих ей групп могут

согласованно увеличиваться, а значения остальных штрафных коэффициентов остаются равными начальным значениям. Точнее, оптимизируется штрафная функция gJ(x) + гу^(х), где О, (х) = ы1 (х), П^х) = = о^(х)+ (х), t = 2, Она удовлетворяет равенству

gJ(.x) + = Р(х;иЛ и, следовательно, получается из функции

при значениях штрафных коэффициентов и{ = £ е 1 ^ ^ Из, задаваемых формулой

' ----Г]-\Г] пщ 1 $ I < ] -

= ■ д^ при I =

. д{ при ^ + 1

Здесь множитель считается переменной величиной. Его значение в процессе выполнения /~й итерации может быть увеличено, если это необходимо, от начального значения г^ = 1 до заключительного значения r'j~rJ^ гДе ^ $ 1 - конечное число. Каждый из множителей , где 1 ^ í < J - 1, считается на ¿-Ъ. итерации постоянной величиной. Все они удовлетворяют неравенствам г* > 1, 1 ^ $ X $ / - 1, и являются конечными числами. Кавдый постоянный множитель г* равен заключительному значению переменного множителя при оптимизации на t-Ë. предшествующей итерации штрафной функции ^(х) + г^(х).

Наряду с условием б), которому долша удовлетворять каждая функция (V), { е I, будем рассматривать более сильное условие:

г)Ф{(7) - полиэдральная, Еыпуклая, конечная при всех у í

т1

( Я

Условие г) эквивалентно тому, что каждая из функций Ш1(V),

I € I, имеет вид

!{(7) = тах{<(1г,у> + П^! I е 1{>,

1 и, 1

где <1 е Д и с А для всех I € конечное множество

индексов, т.е. является выпуклой кусочно-линейной функцией.

Всюду в дальнейшем будем предполагать, что при наличии целочисленных переменных (й £ 1) все компоненты векторов д} и числа для любых I ( и ( <е Г являются рациональными числами. Лемма 5.2. Из выполнения для произвольной функции { е Г, условий а) и г) следует выполнение для нее условия

в).

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

+ гу^(х)}, (5.13)

X € Р,

решаемой на ./-й итерации, обозначим через Р^(г^).

Теорема 5.2. Пусть выполняются предположения теоремы 5.1. Пусть дополнительно выполняется одно из следующих двух предположений.

I. Каждая функция (v), { е I, удовлетворяет условиям а) и

г).

II. Каждая функция Ф4(v), I € I, удовлетворяет условиям а), б) и й = п.

Т<згц,а при. шсдадаваталыда увеличении номера итерации } от начального значения ] = 1 до конечного значения J = а для каждой итерации } справедливы утверждения:

1) при любом значении г' ^ 1 соответствующего множителя г^ будет Р^(г') * 0;

2) существует конечное значение г^ > 1 такое, что ^ и да любого конечного значения г' > г^ будет Ру(г') =

Условия а) иг), налагаемые на функции ®1{т), I € I, в предположении I теоремы 5.2, являются значительно более сильными, чем условия а), б) и в), налагаемые на эти функции в общем случае за-

дачи СЦЛП вида (1.1) (0 ^ И п) в формулировке теоремы 5.1. Это означает, что класс штрафных функций, для которого доказана в общем случае 0 < к $ п теорема 5.1, значительно шире класса кусочно-линейных штрафных функций, для которого в этом случае доказана георема 5.2. Такое сужение вызвано существом дела. В разделе 5.2 построен пример задачи СВДП с несовместной системой ограничений, штрафная функция для которой построена с помощью евклидовой нормы, удовлетворяющей условиям а), б) ив), но не удовлетворяющей условию г), такой, что для нее утверждение 2) теоремы 5.2 не является верным.

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

Рассмотрим множество Х(е) = ixl ä°z }> Ь°; А ? b1- е1. i <= I; х € 2й * iP'h, полученное из множества X допустимых решений исходной задачи СЦШ (1.1) ослаблением штрафуемых ограничений. Здесь s = (sJ! £ € I) = = (SjI Z € U \ M0), e{ > 0 для всех l € I. По определению, X с с Х(е) с р.

Пусть у - произвольный m-мерный вектор. Введем обозначения: Х(У,С) = (I! u X, <с,х> < <Ь,у> + о, Х(е,у,С) = ixi х е Х{е), <с,х> < <Ь,у> + о, P(u,y,c) = ixi TL € Р, ?<x;u) < <b,y> + £>. где С > 0. Очевидно, что всегда Ду,С) с Г(е,у,С) и Х{у,£) с с Р(и,у,С).

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

j ^ — а а tj, x

где a^- 1-я строка матрицы ограничений А, bj - Z-я компонента

i М \ М0, для каждого индекса t е Г и I € if{ зададим число

ߣ(i = ш1п{Ш£[(Ь( - А)+1! Ъг - аТх > Ej, х € 2"),

-я строка матрицы ограничен вектора правых частей ограничений Ъ.

Лемма 5.3. Если функции Ф{(7), £ <е I, удовлетворяют условиям а) и б), то для каждого вектора е = (е'| I € I) с положительными компонентами s^, I t М \ MQ, для каждых индексов i € I и 1 ( i( числа ßg(j существуют и являются положительными.

Введем обозначения: т){ = mlnte^l I € и ßeJ = mln{ߣiI! I € > - По определению, т){ > 0 и ߣ{ > О для всех t е I и е > 0.

/ mi Каждую функцию й (w), t € Г, определенную на R , зададим равенством

Д%) = Ф{(») / Tjf, (5.26)

если функции ф'(w), i е I. вычисляются по формулам (1.6), и равенством

Д{(w) = S*(wl Vl(ßei)) / PgjTjf. (5.27)

где 7l(ße() = (71 Ф*(7) $ ße£, V € Я%. ö*(w! ^(рЕ[)) =

= 3Up{<W,7>l 7 € 7l(ßsi)}, если функции Ф{(и), i € I, вычисляются

по формулам (1.8).

Лемма 5.4. Каждая из функций &l(w), 1 е I, удовлетворяет условиям а) и б).

Из леммы 5.4 и из е* t 0 для всех 1 е I непосредственно следует, что каждое из чисел д*(е1). ( <е I, существует и является положительным.

Введем обозначение ff(u,e,C) = {у| у е У, Ф£(У{) + СА{(еЬ < < и( для всех i е Г), где у = (yf| I е 10), а У - множество допустимых решений слабо двойственной задачи ЛП (1.3).

Теорема 5.3. Если у е íf(u,s,C), где s > 0 и С > О, то Р(и,у,С) с Де.у.О-

Теорему 5.3 для вычисления начальных значений q(, ( <= I, штрафных коэффициентов í е I, можно использовать следующим образом. Предположим, что известно некоторое допустимое слабо двойственное решение у = (у*| 1 е IQ) € Y. Для каждого штрафуемого ограничения alx ^ b^, 1 t X \ Н0, зададим величину Sj > 0 приемлемого нарушения этого ограничения, определив тем самым вектор е = (s{| í е I) = (Ej| l е X \ MQ). После задания числа С > О начальные значения штрафных коэффициентов вычислим по формуле

и{ = Ф1(уЬ + С4{(е£), til. (5.30)

Число С не должно быть слишком большим, чтобы не делать значения штрафных коэффициентов излишне большими. Оно должно, если это возможно, обеспечить нецустоту множества уровня Р(и,у,С). Это особенно просто, когда исходная задача СЦЛП (1.1) имеет допустимые решения, а у является оптимальным решением слабо двойственной задачи Ж (1.3). В этом случае число £ должно быть не меньше зазора двойственности между этими задачами. Тогда множество Р(и,у,С) будет непустым из-за принадлежности к нему непустого множества X* оптимальных решений исходной задачи СЦЛП.

Если множество уровня Р(и,у,С) не пусто, то согласно теореме 5.3 для кавдого вектора х принадлежащего к этому множеству, каждое 1-е штрафуемое ограничение не может нарушаться больше, чем на величину Sj > 0. В частности, это будет справедливо и для каждого оптимального решения задач минимизации штрафной функции (1.4) и (1.5) из-за принадлежности множества таких решений к множеству Р(в,у,С).

Сформулируем следствие теоремы 5.3 для задач ЦЛП (й = п). В этом случае в силу сделанного ранее предположения все коэффициенты исходной задачи ЦЛП будут рациональными. Поэтому при любых х <=

е ü1 произведение агх для каждого I с S может принимать значения только вида zQj, где z - целое число, a 9j - наибольший общий делитель компонент строки а1. Следовательно для каждого индекса I €

€ и \ М0 можно вычислить величину

н = ъ1~ Z1Q1>

где Zj = max{2| 29 j < bj, z - целое). Очевидно, что для кавдого

I i Ii \ MQ будет 0 < < öj. Величины цг, I е U \ MQ, описывают

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

Следствие 5.2. Если & = п, у е Я(и,е,С), где > > £j > О для всех I € ¥ \ *0, С > О, то Р(и,у,С) = Ку.О-

Покажем как можно использовать следствие 5.2. Рассмотрим ситуацию, когда исходная задача ЦЛП вида (1.1) имеет допустимые решения (X Ф 0). Предположим, что соответствующая задача минимизации штрафной функции вида (1.5) решается одним из вариантов метода Еетвей и границ. А начальные значения штрафных коэффициентов вычислены по формулам (5.30) с параметрами, удовлетворяющими условиям следствия 5.2. При этом величина С выбрана из условия, что число <Ь,у> + С является начальным значением рекорда.

В процессе решения задачи (1.5) все ноше рекордные решения принадлежат к множеству Р(и,у,О- А в силу следствия 5.2 все они будут допустимыми решениями исходной задачи 1Щ1 вида (1.1). То есть, решая задачу (1.5), мы все время будем получать допустимые решения исходной задачи (1.1). При этом по мере получения новых рекордных решений со все меньшими значениями целевой функции (рекордами) величину С можно уменьшать, считая все время что сумма <Ь,у> + £ равна текущему значению рекорда. Значения штрафных коэффициентов, вычисляемые по формулам (5.30), при этом также уменьшаются. Другими словами, по мере получения все новых рекордных решений с меньшими значениями рекордов значения штрафных коэффициентов можно не только не увеличивать, но можно даже и уленыютъ.

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

Определение 6.1. Пусть f(t) и g(í) - две произвольные функции, определенные на множестве целых неотрицательных

чисел О, 1, ... . Функция ft(t), определенная на том же множестве целых неотрицательных чисел, называется сверткой функций /(t) и £(i) и обозначается

h(t) = /(t) * Sit),

если ее значение в произвольный момент к, È = 0,1,..., задается выражением

Л») = /(0)g№) + /(1)g№ - 1) + ... + /№)«(0).

Известно, что операция свертки коммутативна, ассоциативна и дистрибутивна относительно сложения.

Задачу линейного динамического программирования со свертками (ДДПС) станем рассматривать в дискретном времени на интервале ГО,П, где Т - фиксированное целое положительное число.

Множество индексов искомых функций обозначим через N. Будем считать это множество конечным. Решение задачи станем представлять в виде вектор-функции Ozy(i)| J е N), где каждая компонента Xj(t), Je В, определена на интервале СО, П.

Пусть Jf - это множество индексов ограничений. Предположим, что это множество конечное. Рассмотрим функции Cj(t), J € S, Qlj(t), 1 е К, J с Ji, и bj(t), ( е H, определенные на интервале [О,П.

Для того чтобы иметь возможность перенести на задачу ДДПС результаты глав 1 - 5 с наименьшими изменениями запишем эту задачу в виде

min 2 Cj{T) * Xj{T), UN

S a{J{t) * Xj(t) >bt(t), t i [0,T], i € ». (6.2)

UN

Xj(t) - целое, t € [0,24, J € Nz,

где Ng с ff, возможны случаи Nz = 0 и Nz .= ÏT. Всюду в дальнейшем под задачей ЛДПС будем понимать задачу (6.2).

Подобно тому как это было в предадущих главах, всюду в дальнейшем будем предполагать, что при Nz f 0 все функции Cj(t),

} £ И, I £ 11, из постановки задачи (6.2) в каждый момент времени г с (0.Т1 могут принимать только рациональные значения.

В разделе 6.2 приведены примеры ограничений из задач теории расписаний, календарного и сетевого планирования, которые можно записать с помощью операции свертки в виде частных случаев ограничений задачи ДЦПС (6.2). К ним относятся ограничения, описывающие потребление сырьевых продуктов; ограничения, описывающие выпуск конечных продуктов; ограничения, описывающие потребление и выпуск промежуточных продуктов; ограничения для моментов начал и окончаний работ одного вида; ограничения для количества работ одного вида; сетевые ограничения типа И; сетевые ограничения типа ИЛИ; ограничения по производственным мощностям; ограничения по производственным мощностям с переналадками; ограничения СЕврху на количества переналадочных работ.

В разделе 6.3 в виде частного случая задачи ДЦПС (6.2) описана классическая задача Гифлера-Томпсона о составлении плана обработки деталей на станках согласно своим маршрутам. При этом ми-низируется общее время обработки.

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

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

Аналогичным образом в разделе 6.6 описана задача теории расписаний с квантованным ресурсом. В этой задаче длительности вы-

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

В разделе 6.7 с помощью операции свертки сформулирована слабо двойственная задача ДЦПС, которая имеет вид:

тах 2 Ь{(Г) » у{(Г), Ш

2 • = 1 е Ю,!П, ] е Я, (6.5)

у^) > 0^), í € ГО,Г], I £

где ОШ - это функция, тождественно равная нулю.

Далее в этом разделе предложена более компактная (Еекторно-матричная) запись прямой и слабо двойственной задач ДЦПС.

Пусть Н = {1, .... тУ и N = {1.....пУ. Все рассматриваемые

в дальнейшем вектор-функции предполагаются вектор-функциями-столбцами. Через сЦ) и х(£) обозначим п-мерныа вектор-функции, компоненты с^СО, / е и Xj{t), / ? N. которых являются функциями, определенными на интервале [О,Г], т-мерные вектор-функции Ь(0 = (Ь£(П! { е V) и у(Л = СугС^>I I € М) задаются аналогично. Матрица ограничений определяется как т * п - мерная матрица-функция, компоненты а^Ц), I £ У, J а Н, которой являются

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

использовать знак ' (штрих). Через » й^и) обозначим мно-

жество п-мерных вектор-функций с компонентами, определенными на [О,Г], первые к (0 к 4 гг) компонент которых являются функциями,

принимающими на [0,7] только целочисленные значения, а последние п - к компонент - вещественные значения.

С учетом всего предыдущего задачу ЩЮ (6.2) запишем в виде:

min с' (T) * х(Ï1), 4(t) * x(i) ? b(i), t e [О.П, (6.6)

x(t) € Z^(t) « tP-~k(t). A слабо двойственную к ней задачу ДЦПС (6.5) - в виде:

max b'(Т) * у(Т), Л*(t) * y(i) = c(i), î e [0.Г], (6.7)

y(t)>0(t), t € [0,7], y (t) € rf*(t),

где 0(i) - это m-мерная вектор-функция, все компоненты которой тождественно равны нулю.

В разделе 6.8 сформулированы задача минимизации точного штрафного функционала для задачи ДЦПС и слабо двойственная к ней задача.

Как и в разделе 1.2, все множество индексов ограничений задачи ДЩ1С (6.6) M = (1.....m> разобьем на попарно непересекающиеся подмножества t € IQ, где Г0 = I U {0} и 0 i I, содержащие по элементов. Здесь Г Ф 0, множество ¡f0 может быть пустым (mQ = 0), а каждое из подмножеств Jf{, 1 ç I, не является пустым (п{ > 0). Этому разбиению соответствует разрез по горизонтали матрицы-функции ограничений ) на подматрицы-функции Al{t), I е € Iq, и вектора-функции правых частей ограничений b(t) на подвек-торы-функции bl(t), t £ Г0.

Для общих задач ДЦПС вида (6.6) будем использовать штрафной функционал

P(x(t);uJ = с'(Т) * х(Т) + 2 ut®l{tbl(t) - Al(t) * x(t)J+).

tel

Здесь u = (u{! t e I), u{ ^ 0 для всех t e Г; вектор-функция v(t)+ получается из произвольной вектор-функции y(t) путем замены

отрицательных значений ее компонент нулями; каждый функционал

, mf

ffl Cv(t>], i e Г, задан не множестве R (t) и(-мерных вектор-

функций с компонентами, которые определены на [О,Г] и принимают вещественные значения; функционалы I i I, могут быть

разными для разных i; каждый функционал Cv(i)3, I ç. Г, удовлетворяет условиям:

а) fl^ivit)] > 0 для всякого v(t) ф 0(t), Ф{[0(î)l = О, где 0(t) - это nj-мерная ьектор-функция, все компоненты которой

на ГО.ГЗ тождественно равны нулю;

I nf

б) Ф fv(i)] - выпуклый, конечный при всех v(t) с Я (i);

в) [0(t);v(t)] > О для всякого v(i) / 0(t), где

,, ®l[0(i) + Xv(t)] - ®{[0(i)] r C0(i);v(f)] = Ilm-

Ц0 \

- односторонняя производная функционала ®4v(i)] в точке 0(t) по

направлению v[(t)l.

Использование метода точных штрафных функционалов применительно к общим задачам ДЦПС вида (6.6) заключается в решении задачи

min Tlx(t);u],

A°(t) * x(i) >b°(i), t e CO,Fl, (6.8)

z(i) e Zft(i) *

По аналогии с разделом 1.3 для каждого функционала $lCv(i)]

определим функционал ${[w(t)], положив

®tEw(t)] = sup *'(Г) * v(T) / ®{(v(i)l. v(fM0(t)

Слабо двойственной к задаче (6.8) будем называть задачу шах Ь'(Г) * у(Г), A'(t) * y(t) = с (t), t е fO,!Г], y(î) ^ O(t). t € [0,73, (6.9)

Ф{[у{(i)3 < и,, i € I.

где = (г/^Щ I € М), У{Ш = (уг(П| I € М{), £ € 10,

0(0 - т-мерная вектор-функция, все компоненты которой тождественно равны нулю.

Раздел 6.8 посвящен теоретическому аспекту метода точных штрафных функционалов для задач ЛДПС. в нем получены аналоги основных результатов глав 2-4.

Доказано, что если слабо двойственная задача ДЦПС (6.7) не имеет допустимых решений, то значения штрзфного функционала Р[х(0;и] в задаче (6.8) не ограничены снизу при любых значениях штрафных коэффициентов.

Также доказано, что значение штрафного функционала ИхШ;и]

на произвольном допустимом решении прямой задачи (6.8) всегда не меньше значения слабо двойственного целевого функционала Ь'(Г) * * у(Г) на произвольном допустимом решении слабо двойственной задачи (6.9).

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

Для задачи ДЦПС (6.6) получены достаточные условия непустоты и совпадения множества оптимальных решений этой задачи с множеством оптимальных решений задачи минимизации штрафного функционала (6.8). Эти условия являются аналогами таких же условий для статических задач СЦЛП.

В разделе 6.10 рассматривается вычислительный аспект метода точных штрафных функционалов для задач ДЦПС. Для динамической задачи (6.8) построены аналоги двухэтапного метода последовательной оптимизации и мультипликативного метода. Установлены связи между этими методами, аналогичные тем, что имели место в статическом случае. Выведены формулы для начальных значений штрафных коэффициентов, также являющиеся аналогами таких же формул для статического случая.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

оптимизации.

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

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

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

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

СПИСОК ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

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

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

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

5. Шелев В.В. Динамическая задача межцехового планирования // Моделирование и управление в развивающихся системах. М.: Наука, 1978. С. 120-125.

6. Уздемир А.П., Шмелев В.В. Целочисленные динамические задачи экономического планирования с сетевыми ограничениями. I // Автоматика и телемеханика. 1978. Л 7. С. 106-115.

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

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

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

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

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

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

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

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

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

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

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

18. Уздемир А.П., Шмелев В.В. Обобщенная задача календарного планирования дискретного производства. II // Автоматика и телемеханика. 1999. J6 4. С. 103-110.

19. Шмелев В.В. Теория метода точных штрафных функционалов для задач календарного планирования // Международная конференция по проблемам управления. Тезисы докладов. Т. 2. М. : Фонд "Проблемы управления", 1999. С. 269.

20. Шелев В.В. Точные штрафные функционалы в задачах календарного планирования // Автоматика и телемеханика. 1999. J6 9. С. 107-114.

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. Для динамических задач минимизации точных штрафных функционалов построены, двухэтапный метод последовательной оптимизации, мультипликативный метод, доказана их. эквивалентность, выведены формулы для начальных значений штрафных коэффициентов.

ЗАКЛЮЧЕНИЕ

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.