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

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ им. С.Л.СОБОЛЕВА

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

ПАЩЕНКО Михаил Георгиевич

ЛАГРАНЖЕВЫ РЕЛАКСАЦИИ В ДИНАМИЧЕСКИХ ЗАДАЧАХ ВЫБОРА ОПТИМАЛЬНОГО СОСТАВА СИСТЕМЫ ТЕХНИЧЕСКИХ СРЕДСТВ

(01.01.09 - математическая кибернетика)

Автореферат

диссертации на соискание учёной степени кандидата физико- математических наук

Новосибирск 1998

Работа выполнена в Институте математики им. С.Л.Соболева СО РАН

Научный руководитель - доктор физико-математических наук,

профессор В.Л.Береснев. Официальные оппоненты: доктор технических наук,

В.Н.Павлов,

кандидат физико-математических наук, Р.Ю.Симанчев.

Ведущая организация - Вычислительный центр РАН.

Защита состоится «28» октября 1998 г. в 16 часов на заседании диссертационного совета Д.002.23.03 в Институте математики СО РАН (пр. Коптюга 4,630090 Новосибирск).

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

СО РАН.

Автореферат разослан

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

А.В.Косточка.

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

Актуальность темы. Исследования математических моделей оптимизации состава систем технических средств проводятся в Институте математики им. С.Л.СОБОЛБВА СО РАН с конца 60-х годов. Актуальность этих исследований обусловлена важными практическими приложениями подобных моделей. С математической точки зрения исследуемые задачи относятся к числу NP-трудных1 задач дискретной оптимизации. Для их решения с начала 70-х годов разрабатывались точные алгоритмы типа ветвей и границ, демонстрирующие приемлемую работоспособность в практических расчетах. Примерно тогда же появились первые работы, посвященные выявлению полиномиально разрешимых частных случаев.

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

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

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

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

1 Гэри М., Джонсон Д., Вычислительные машины и труднорешаемые задачи.

Москва: Мир, 1982.

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

3 Fisher M.L. The lagrangian relaxation method for solving integer programming Problems. //Management Science. 1981. V 27, 1-18.

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

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

Апробация работы. Основные результаты диссертации докладывались на III Всесоюзной школе-семинаре "Дискретная оптимизация и компьютеры" (Таштагол, 1987), Всесоюзной школе-семинаре по комбинаторной оптимизации (Алушта, 1991), X Байкальской школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 1995), международной конференция "Проблемы оптимизации и экономические приложения" (Омск, 1997), 16 Европейской конференции по исследованию операций (Брюссель, 1998), на научных семинарах Института математики СО РАН.

Публикации. По теме диссертации автором опубликовано пять работ.

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

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

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

Zp = minea;, Ах > b, Вх > d, х > О,

где х - вектор целочисленных переменных, Ь, с, d - вектора и А, В -матрицы соответствующей размерности.

Лагранжепой релаксацией задачи Р по ограничениям Ах > Ь с множителями А > О называется задача LR(А):

Дсп(Л) = min сх + А (6 — Ах), Вх > d, х > О,

Задача, двойственная к задаче Р относительно ограничений Ах > Ь, по определению, есть задача D, вида

ZD — maxZLR(x), А > 0.

Множество ограничений задачи Р разбито на два подмножества. Для задач линейного программирования справедливо равенство Zp = Zd при любом разбиении множества ограничений. Для дискретной задачи Zp > Zd и разрыв двойственности может существенно зависеть от разбиения. Обозначим через Р линейную релаксацию задачи Р. В дальнейшем чертой сверху (.) всегда будем обозначать переход к линейной релаксации. Рассмотрим также задачу Р*:

Zp* = rain сх, Ах > 6,

х £ Со{х > 0, целые, Вх > d.}

Тогда Zj < Zp* = Zd < Zp.A Оптимальные множители лагранжа обычно вычисляются методами субградиентной оптимизации.5

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

В разделе 1.1 приводится постановка задачи. Пусть I = {1,...,/} -список образцов технических средств, J = {1,..., J} - множество работ области применения системы, L = {1,... ,¿} - множество этапов. Считаем, что множество работ области применения разбито на L непересекающихся подмножеств J¡, I £ L и для каждого i £ I определены следующие параметры

v¡ — число изделий, уже имеющихся в составе системы;

4 Shapiro J.F. A servey of Lagrangian techniques for discrete optimization. // Annals of discrete mathematics. 1979. Vol.5. P.113-138.

5 Fisher M.L., Nortrup W.D., Shapiro J.F. Using duality to solve discrete optimization problems: Theory and Computational experience. // Mathematical Programming Study. 1975. V 3, 56-94.

lACpCiViCXl

— í1' ~ \ O

c° — затраты на НИОКР и подготовку производства; d — затраты на производство одного изделия; su — доля потерь на ¿-ом этапе;

Vi — максимально возможный объем производства изделий; Pij — число изделий, требующихся для выполнения j-й работы; dj — стоимость выполнения j-й работы. Переменные (zi),(v¡),(xij) имеют следующий смысл: если г-й образец включен в состав системы, О в противном случае; Vi > 0 — объем производства i-го изделия; x¡j >0 — доля j-й работы, выполняемая изделиями г-го образца. Исцользуя введенные обозначения задача выбора оптимального состава системы может быть записана в виде задачи Р частично-целочисленного программирования:

ZP = ruin ]Г(с° z¡ + c¿ Vi + £ a¡ хц) (L)

¿el ieJ

при ограничениях:

X>ü =1, j£j; (2)

iei

<K, (3)

iei

i-i

£ Pij xij < V; +v,~ £ Sil' E Pij Zij, i el, leL; (4)

jeJ¡ i'=i jeJ,t

0 < Vi < Ц, i€l; (5)

o < Xij < zí, i ei,jeJ-, (6)

z¡e{0,i}, ieJ. (7)

Целевая функция выражает суммарные затраты на создание и функционирование системы. Равенства (2) гарантируют выполнение всех работ области применения. Ограничение (3) устанавливает потолок на число типов используемых технических средств (не более К типов, К— целое число). В левой части неравенства (4) стоит выражение для объема средств i-го образца, требующегося на 1-м этапе, а в правой части - выражение для имеющегося в наличии объема с учетом

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

Во разделе 1.2 изучаются различные нижние оценки для целевой функции задачи (1)-(7). Традиционно для получения нижних оценок в задачах частично-целочисленного программирования используется линейная релаксация. Приводится эквивалентная формулировка задачи Р, обозначенная которая позволяет существенно улучшить оценку линехшого программирования. Доказано, что для любого натурального N существует семейство исходных данных, на котором одновременно Zpx > Zp • N и Zp > ЕРх • N.

Рассматриваются две Лагранжевых релаксации задачи Р. В первой из них в целевую функцию с коэффициентами А;, ] £ Л, заносятся ограничения (2). Полученная задача обозначается Ь{А), а соответствующая ей двойственная оценка - 2ц. Во втором случае релакси-руются ограничения (4), (5). Релаксированная задача обозначается Ы1, а соответствующая ей двойственная оценка - Показано, что 2рх = Хо < < гР.

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

С точки зрения теории ИР-полноты задачи ЬН и Р одинаково трудны, но практически задачу ЬН решать проще и в первую очередь потому, что при фиксированных булевых переменных 2 значения непрерывных переменных в задаче ЬВ, определяются за линейное время, а в задаче Р для этого приходится решать задачу линейного программирования. Кроме того, для задачи ЬП в монографии Береснева, Гимади, Дементьеваприводится алгоритм ветвей и границ, хорошо работающий на задачах средней размерности.

Задача Ь{А) распадается на I подзадач вида а,- = шах { £ (А, - с,-,-) хц - с,- V, -с?};

Ш

при ограничениях (4),(5) и

0<ху<1, j€J,i£I, каждая из которых решается эффективно. Величины а,- можно рассматривать как выигрыш от включения 1-го изделия в состав систе-мыю. В оптимальное решение задачи /,(А) входит К изделий с макси-

мальными значениями а;.. В разделе 1.3 для задачи L{\) приводится точный полиномиальный алгоритм решения с оценкой трудоемкости 0(IlogI + JJ(L + \ogJ)).

В разделе 1.4 приводится алгоритм построения допустимого решения задачи Р. Пусть (z*)(v*)(a:*) — оптимальное решение задачи L(А)

и Дj(A) = J2xij ~~ J £ Если АДА) = 0, т.е. равенства (2) ¿е/

верны для (х*), то (z*)(v*)(x*) — оптимальное решение исходной задачи и Zl(А) совпадает с Zp . Выполнение условий (2) означает, что в задаче Р отсутствует разрыв двойственности. Чаще оказывается, что Zi(\") = Zq < Zp, но величина 5 ~ | А) | достаточно мала

УеУ

и решение (z*)(u*)(r*) удается достроить до допустимого решения исходной задачи с помощью процедур координатного спуска. Алгоритм Но применяет эту процедуру в ходе субградиентной оптимизации и выбирает наилучшее из полученных решений. Алгоритм Но рассматривает различные наборы (z*), что, разумеется, не гарантирует получения оптимального набора задачи Р. Более осторожной стратегией, чем в алгоритме Но , является схема покомпонентного составления набора (z*), на каждом шаге которой одна из переменных полагается равной 1. Ниже приводится четыре правила выбора такой переменной:

1. Положить Z{ — 1, если а,-(А*) = таха^А*).

2. Определить работу г, для которой x'ir = тах 1С ХЬ и положить

■ е/ ieJ iei

Zi = 1, если = max{E4j ! * € I,x*kr > 0}.

jeJ jeJ

3. Положить Zi — 1, если С x*ij = maxj^ xlj

j&J keI jeJ

4. Положить Zi = 1, если номер i наиболее часто входил в состав оптимального набора (х) задачи L(A) в ходе субградиентной оптимизации.

Обозначим через Не аналог алгоритма Но, основанный на релаксации LR. Понятно, что алгоритм Не уже не будет иметь полиномиальную трудоемкость, но т.к. Zq > Zo, то проигрывая во времени, он может выигрывать в точности.

В разделе 1.5 приводятся результаты численного эксперимента. Наилучшие результаты по точности принадлежат алгоритму Не- Алгоритм Но может сильно ошибаться. Любой из алгоритмов покомпо-

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

В второй главе рассматривается двухуровневая многоэтапная задача.

Особенностью предлагаемой постановки по сравнению с задачей, рассмотренной в первой главе, является то, что технические средства, образующие систему, состоят из некоторых унифицированных составных частей (узлов). Обозначим через К = {1,..., К) — множество различных видов узлов, используемых для комплектации средств рассматриваемых образцов. Для ! 6 I обозначим через К{ перечень видов узлов, входящих в состав г-го образца. Положим с1°к — стоимость разработки узла к-го вида. И введем новые переменные

если узлы к-го вида включены в состав системы ,

У к :

1 " в противном случае. Используя введенные обозначения исследуемая задача может быть записана в виде задачи Р частично-целочисленного программирования:

ZP = min{XXci zi + vi + E CH хч) +22 dk Ук} (8)

«е/ jeJ кек

при ограничениях:

2>*i =1, j€J; (9)

iei

l-1

Л Pij хц < v°Zi -f Vi - £ sii' 12 Pa xHi i G I, I &L\ (10)

jeJi i'=l jeJii

0 < Vi < ViZi, i € f; (11)

о < Xij <Zi, i el, jeJ; (12)

Ук > Zi, i elk, kE K; (13)

i£i, keK. (14)

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

Ук > £кек, jeJ. (15)

i&k

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

Рассматриваются две Лагранжевые релаксации Ы¥ и ЬБ. В первой в целевую функцию заносятся ограничения (9), а во второй ■— ограничения (9) и (15). Соответствующие им двойственные задачи обозначены ПШ? и ОЬБ. Задача ЬБ с точностью до коэффициентов совпадает с задачей Ь из первой главы и решается аналогично. Задача Ь\У сводится к задаче о минимизации полинома от булевых переменных с неположительными коэффициентами при нелинейных членах. Агеев показал, что решение этой задачи может быть получено путем сведения ее к задаче о минимальном разрезе в двудольной сети.6 Построен точный полиномиальный алгоритм решения задачи Ы¥ с оценкой трудоемкости 0{РК + Л(Ь + 1од1)).

Показано, что нижние оценки БЫУ и ПЬБ несравнимы между собой. Приводятся результаты численного эксперимента, подтверждающие, что что оценка ОЬ]¥ имеет некоторые преимущества при жестких ограничениях (10), (11) и хуже оценки ОЬБ в остальных случаях.

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

В разделе 3.1 приводится постановка задачи. Пусть I = {1,...,/} - список образцов технических средств, I = {1,...,/} - множество работ области применения системы, множество Т = {1,..., Т} задает плановый промежуток. Считаем, что множество работ области применения разбито на Т непересекающихся подмножеств £ € Т. Для ] Е Л через обозначен номер, I 6 Т такой, что ] £

Для каждого г £ I определены с°1 — затраты на разработку средств г-го образца, если разработка завершается в £-м году;

да — стоимость производства одного средства г-го образца в £-м году; Су — затраты на выполнение средствами г-го образца ¿-ой работы; Ру — количество средств г-го образца одновременно необходимых для выполнения ^-ой работы;

Pi —■ длительность эксплуатации одного изделия;

6 Агеев А.А. О минимизации некоторых полиномов от булевых переменных. // Целочисленные экстремальные задачи (Управляемые системы). Новосибирск, 1981. Вып. 21, 3-5.

v°t — количество средств г-го образца из начального состава системы, пригодное для эксплуатации в t-м году;

Vu — ограничения сверху на возможный объем производства средств i-го образца в i-м году.

Определены следующие переменные: zu 6 {0,1}, г е f € Т. Переменная zu принимает значение 1, если в t-м году закончена разработка средства г-го образца, и гц = 0 в противном случае.

vit > 0, г € i € Т. Величина vlt равняется количеству средств г-го образца, производимых для пополнения состава системы в i-м году; Xij > 0, г 6 I, j G J■ Величина X{j равняется доле j-й работы, выполняемой средствами г-го образца.

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

ZP = min Е Е{сй z» + 9it vu + E c{j r,7}; (16)

t&r i ei jeJt

при следующих ограничениях:

E*y =1, ieJ; (17) •е/

E Pij x{j < + E Vir, i 61, tET; (18) jeJt г=(-р;+1

0 < vu < VH ma.KziT, i£l, 16 T; (19)

0 < Xij < max ZiT, i G I, j G J; (20)

T<t(j)

2Й€{0,1}, i€l, t Z.T. (21)

В разделе 3.2 рассматривается Лагранжева релаксация задачи Р по ограничениям (17). Показано, что релаксированная задача LR{\) полиномиально разрешима. При фиксированных значениях \j, j & J задача LR(\) распадается на I независимые подзадачи 5,- вида:

Zi - ЕКг zit -i-git vit + E (су - \i) z.;} teT jeJ,

при соответствующих условиях (18) - (21). В оптимальном решении задачи 5; не более одной переменной ztl равно 1, поэтому значение Zi может быть найдено следующим образом

Zi = min(0,mm(^ff + с°й)), где Zm решение задачи линейного программирования

т

Ziff = min £ [да vu + E (c>j - -\>) xij} i=o jeЛ

при ограничениях

(

£ Pij x<j < vit + £ u»-> t = 9,...,T;

jeJt r=t-p+i

0 < vit < Vu, t=0,...,T; о<х0-<1, jeJut = e,...,T.

Величину Z,- можно рассматривать как выигрыш от включения г-го образца в состав системы. Построены строго-полиномиальные алгоритмы решения задачи LR(X) при pi = 1, г £ I, и pi > Т, г £ I. Установлено, что при pi = 1, i £ I, двойственная нижняя оценка совпадает с оценкой линейной релаксации.

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

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

В разделе 3.6 приводятся результаты тестовых расчетов.

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

max ykT > £ Xfj, k£ К, j £ J (22)

TS<0) ¡ef*

или

шахуд.г > zit, k£Ki,i£l,t£T. (23)

Рассматриваются три Лагранжевых релаксации LW, LS, LBS. Первая производится по ограничениям (17), вторая и третья — по ограничениям (17) и (22). Третья отличается от второй тем, что к множеству ограничений добавлены избыточные ограничения (23). Задача LS с точностью до коэффициентов совпадает с задачей LR(А) и решается аналогично. Показано, что задачи LW и LBS сводятся к задаче о минимальном разрезе в сети.

Основные результаты диссертации опубликованы в работах:

1. Пащенко М.Г. Алгоритм вычисления нижней границы для динамической задачи оптимального выбора состава систем технических средств с ограничениями на объемы производства. //Модели дискретной оптимизации (Управляемые системы). Новосибирск, 1989. Вып. 29, 57-71.

2. Кочетов Ю.А., Пащенко М.Г. Лагранжевы релаксации в задаче выбора оптимального состава системы технических средств. // Оптимизация дискретных структур (Управляемые системы). Новосибирск, 1993. Вып. 31., 26-39.

3. Кочетов Ю.А., Пащенко М.Г. Динамические задачи выбора оптимального состава системы технических средств. //Дискретный анализ и исследование операций. 1995. Т 2, N 1, 36-49.

4. Кочетов Ю.А., Пащенко М.Г. Нижние оценки в задаче выбора состава двухуровневой системы технических средств. //Дискретный анализ и исследование операций. 1995. Т 2, N 4, 32-41.

5. Пащенко М.Г. Нижние оценки для целевой функции в динамической задаче выбора оптимального состава двухуровневой системы технических средств. //Дискретный анализ и исследование операций. Серия 2. Новосибирск, 1997. Т 4, N 1, 40-53.

АКАДЕМИЯ НАУК РОССИИ СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ им. С.Л.СОБОЛЕВА

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

ПАЩЕНКО Михаил Георгиевич

ЛАГРАНЖЕВЫ РЕЛАКСАЦИИ В ДИНАМИЧЕСКИХ ЗАДАЧАХ ВЫБОРА ОПТИМАЛЬНОГО СОСТАВА СИСТЕМЫ ТЕХНИЧЕСКИХ СРЕДСТВ

(01.01.09 - математическая кибернетика)

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель д.ф.-м.н., профессор В.Л.Береснев

Новосибирск - 1998 г.

ОГЛАВЛЕНИЕ

стр.

Введение............................................................3

Глава 1. Многоэтапная задача ............. .......................12

§ 1.1. Постановка задачи .......................................12

§ 1.2. Нижние оценки................. ..........................14

§ 1.3. Алгоритм решения релаксированной задачи..............21

§ 1.4. Построение допустимого решения многоэтапной задачи . .27

§ 1.5. Численный эксперимент..................................29

Глава 2. Двухуровневая многоэтапная задача .....................34

§ 2.1. Постановка задачи .......................................34

§ 2.2. Нижние оценки...........................................36

§ 2.3. Соотношение оценок ИЬШ и ИЬБ .......................42

§ 2.4. Результаты тестовых расчетов...........................44

Глава 3. Динамические задачи ....................................46

§ 3.1. Постановка задачи .......................................46

§ 3.2. Нижние оценки...........................................48

§ 3.3. Общая схема алгоритма.................................. 53

§ 3.4. Динамические задачи с ограничениями на номенклатуру

изделий .......................................................54

§ 3.5. Динамические задачи с фактором серийности ............56

§ 3.6. Результаты численных расчетов .........................58

Глава 4. Двухуровневая динамическая задача.....................61

§ 4.1. Постановка задачи .......................................61

§ 4.2. Нижние оценки...........................................64

§ 4.3. Алгоритмы решения релаксированных задач.............66

Список литературы ...............................................73

Введение

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

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

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

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

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

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

Использовать обобщенные множители Лагранжа в задачах дискретной оптимизации впервые предложил Everett [31] в 1963 г. Однако бум в этой области начался после выхода в свет статьи Held и Кагр, посвященной задаче коммивояжера [42], которая послужила толчком для теоретических и прикладных исследований в этой области. В 1973 г. опубликована статья Fisher [32], в которой используется этот подход для задач теории расписаний. В этом же году выходит в свет статья Shapiro [52], а в 1974 Shapiro и Fisher [34], в которых метод лагран-жевых релаксаций развивается применительно к общей задаче целочисленного программирования. Сам термин "Лагранжева релаксация" был предложен Geoffrion в 1974 г. [39]. В этой работе сформулированы и доказаны основные теоремы. Однако центральный вопрос: "Каким образом вычислять множители Лагранжа?" - оставался открытым и в 1975 г. Fisher, Northup и Shapiro в [35] дали подробнейшее разъяснение и по этому поводу. В 1979 г. Shapiro опубликовал обзор, в котором содержится обширная библиография по применению техники лагран-жевой релаксации в задачах целочисленного программирования [53]. В 1981 г. вышел аналогичный обзор Fisher [33]. С тех пор этот метод успешно применялся при решении многих сложных задач дискретной оптимизации.

Поскольку применение метода Лагранжевых релаксаций занимает

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

Zp = mincx, Ах > 6, Вх > d, х > О,

где х - вектор целочисленных переменных, 6, с, d - вектора и А, В -матрицы соответствующих размерностей.

Лагранжевой релаксацией задачи Р по ограничениям Ах > b с множителями Л > 0 называется задача LR(Л):

Zlr(а) = min сх + Л(6 - Ах), Bx>d, х > О,

Задача, двойственная к задаче Р относительно ограничений Ах > 6, по определению, есть задача D, вида

ZD = max Zir(\) , Л > 0.

Множество ограничений задачи Р разбито на два подмножества. Для задач линейного программирования Zp = Zp> для любого разбиения множества ограничений. Для дискретной задачи ZP > ZD, и разрыв двойственности может существенно зависеть от разбиения. Обозначим через Р линейную релаксацию задачи Р. В дальнейшем чертой сверху (.) всегда будем обозначать переход к линейной релаксации. И рассмотрим также задачу Р*:

Zp* -- min сх,

Ах > Ъ,

х е Со{х > 0, целые, Вх > й.}

Тогда ^р < ^р* = < Zp.

Среди методов решения задачи В наиболее широкое распространение получили методы субградиентной оптимизации. Это итеративные процедуры, формирующие последовательность векторов (А*), начиная с некоторого начального значения (А0), по следующему правилу:

А*+1 = А к + гк(Ахк-Ь),

где хк - оптимальное решение задачи ЬЯ{Хк), а tk - размер шага. Фундаментальный теоретический результат заключается в том, что хк) —* ^в, если 4 —> 0 и Tli=Qtk —оо [43],[18]. Размер шага на практике обычно выбирают следуя [18],

_ек(г*-гщх>))

4 ~ » Ахк - Ь ||2 '

где <дк - скаляр, 0 < 0* < 2, и - верхняя граница для ZD^ В качестве Z~к берется значение целевой функции задачи Р на некотором допустимом решении. Посследовательность О*, как правило, начинается с 0° = 2 и затем делится пополам, через фиксированное число итераций, зависящее от размерности задачи.

Если на некотором шаге невязка Ахк — Ь равна 0, то хк будет решением исходной задачи Р. К сожалению, такое равенство возможно только при отсутствии разрыва двойственности. Тем не менее, если невязка достаточно мала, то вектор хк является решением достаточно "близкой" задачи Рк, отличающейся от исходной тем, что вектор Ь заменяется на вектор Ахк. Решение хк часто удается достроить до допустимого решения исходной задачи с помощью различных эвристических процедур. Это позволяет строить приближенные алгоритмы с апостериорной оценкой точности.

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

Многие задачи выбора оптимального состава системы могут интерпретироваться как задачи размещения производства. Динамические задачи размещения производства впервые были сформулированы Ballou в 1968 году [22]. В работе Wesolowssky [57] рассматривалась модель оптимального размещения одного предприятия и его перемещения в течении планового периода . Задачи с несколькими предприятиями впервые рассмотрел Scott в [51]. В этих моделях предусматривалась возможность закрытия существующих предприятий и открытия новых без учета ограничений на мощности и количество работающих предприятий. Первые модели динамических задач о "р-медиане" (или задач размещения с ограничениями на число работающих предприятий) представленны в [58]. Последующие исследования данных моделей размещения производства связаны с адаптацией алгоритмов, хорошо зарекомендовавших себя на статических моделях [56, 49]. В частности, в [56] представлен вариант метода ветвей и границ для нескольких постановок динамических задач, который фактически является вариантом наилучшего на сегодняшний день алгоритма Erlenkotter [29] для

простейшей задачи размещения производства. Метод Лагранжевых релаксаций применяется в [37] для поиска приближенного решения задачи о "р-медиане". В работе исследуются две релаксации, и их поведение сравнивается на тестовых задачах средней размерности. В работах [50, 24] применялись методы локального поиска. Сравнение эффективности метода Лагранжевых релаксаций и одной из так называемых мета-эвристик (эитДайг^ аппШгщ) проведено в [24]. Более подробно с обзором результатов в данной области можно познакомиться в [45].

Большое количество работ посвящено статической задаче размещения с ограничениями на объемы. Для ее решения разработаны как точные алгоритмы ветвей и границ, так и различные эвристические алгоритмы, в том числе и использующие лагранжевы релаксации. В 1995 г. вышел обзор ЗпсШагап [54] посвященный алгоритмам решения ограниченной задачи размещения производства, в котором приводится обширная библиография.

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

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

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

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

Первые математические модели выбора состава двухуровневых систем технических средств были рассмотрены в [2]. Наиболее полно такие системы изучались в монографии [3], где, в частности, установлена сведимость наиболее простой линейной задачи выбора состава двухуровневых систем к задаче минимизации полинома от булевых переменных. В [6] приводится описание метода ветвей и границ для статического случая с модифицированным алгоритмом вычисления нижней оценки целевой функции. Большинство статей (см., например, [15, 48, 55, 23]) посвящено исследованию частного случая рассматриваемой задачи, так называемой двухуровневой задачи размещения производства. Для двухуровневых задач размещения производства вопрос построения нижних границ и их взаимосвязь изучались в [23].

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

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

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

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

Результаты приведенные в теоремах 2, 4, 8 и 9 получены совместно с Кочетовым Юрием Андреевичем.

Основные результаты диссертации опубликованы в работах [16, 12, 14, 13, 17] и докладывались на III Всесоюзной школе-семинаре "Дискретная оптимизация и компьютеры" (Таштагол, 1987), Всесоюзной школе-семинаре по комбинаторной оптимизации (Алушта, 1991), X Байкальской школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 1995), международной конференция "Проблемы оптимизации и экономические приложения" (Омск, 1997), 16 Европейской конференции по исследованию операций (Брюссель, 1998). Полученные результаты использовались при выполнении различных НИР.

Автор выражает искренюю признательность научному руководителю В.Л.Бересневу и Ю.А.Кочетову за постоянное внимание и всестороннюю поддержку при выполнении данной работы.

Глава 1

Многоэтапная задача

1.1 Постановка задачи

Пусть множество I = {1,2,...,/} задает исходный ряд образцов технических средств. Исходный ряд включает в себя номера образцов, которые выпускаются серийно, либо могут быть выпущены в ближай�