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

Академия наук Украины Ордена Ленина Институт кибернетики имени В. М. Глушкова

На правах рукописи ВОЙТИ ШИН Юрий Валентинович

УДК 519.3

АЛГОРИТМЫ РЕШЕНИЯ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ КОМБИНАТОРНОГО ТИПА

01.01.09 — математическая кибернетика

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

Киев 1992

Работа выполнена в Институте кибернетики имени В. М. Глушкова АН Украины.

Научный консультант: академик МИХАЛЕВИЧ В. С.

Официальные оппоненты: член-корреспондент АН Украины

ШОР Н. 3.,

доктор физико-математических наук РОМАНОВСКИЙ И. В.,

доктор физико-математических наук ПЕРЕПЕЛИЦА В. А.

Ведущая организация: Институт математики АН Беларуси. „

Защита состоится «-»--- 1у.7<4\ в ——

часов на заседании специализированного совета Д 016.45.01 при Институте кибернетики имени В. М. Глушкова АН Украины по адресу:

252207 Киев 207, проспект Академика Глушкова, 40.

С диссертацией можно ознакомиться в научно-техническом архиве института.

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

_19 01т.

Ученый секретарь специализированного-совета СИНЯВСКИЙ В. Ф.

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

ï

. ^Диссвртащюшая робота поспящепа разработке влгорлтшв экстрвмалыгпс задач комбшшторггаго типа, т.о. задач "■--'вмбЦв наялучи&го гю олродолецпому критвр;ш лодмттатоствя на заданного конечного икожпстпа допустимых подмножеств. Клпсс задач этого типа чрезвычайно обитрон. Экстремялышв задачи комбинаторного типа появляются в чистом иди усложненном нлдо во многих практических оптимизационных модолях.

Актуальность тс. soi . Значительная часть задач россматри-прймого класса пъ изучена к настоящему нремони в достаточной море, о чем соадето^ьстнуот огромное количество публ'чмгдоЯ, посвященных эти« задачам. Ксслепования по теории сложности даскротных оптимизационных задач и методов их pouimmn, шподнвшыэ Яблонским C.B.. Журанловам П.il., Ловлям А.А., Куком С.Д., Караом PJi. 'л др., лрип&ля к шдал1>;иа двух внжмх классов: NP-трудннх зздяч и задач, для которых суп;с-ст ■ вуит :,ф1октив!шо алгоритмы. В последних трудоемкость рай: о пня растет как полином с ростом длшш »хода задачи. Больг.шстно нетривиальных зкстрональшх задач комбинаторного типа относится к классу NP-труднш, а п&рсп&кггоа создания ос.дих гг^чктншшх (и с рнчислпгз-шюа, н с ииформеционноЯ точек зрения) методов их ре ¡гелия рвсьнз ппссимистична. Б связи с этим особое значешю приобретает разработка точных а прибди-а»!1шх алгоритмов и программного обеспечения рзивния задач определенных типов. .

В работе исследуются следующие задачи: 1 ) задача о максимальном ifpoirrfi ориеятиропушюй сети; _ ' 3) задача о нпиОольдом «ногостш» попарно несравнима верят ориентированного гргфз ;

3) зпдмчз разбиения множества;

4) задача оптимизация варлалтпих мододеЯ.

Понятие» ориентированной сети (частим Л пид

рлзреза )чводено в работах Корниловой Л.Е. в связи с рассмотрением задачи о кишчпльном потоке. Там an показано, что величина милимлльн' г<> потока рання пропускной способности максимального 4р-лгга. С иоодць» известных алгоритмов можно решить зада «у о максимальном фронта допустим соти, т.о.

сета, дая которой задача о минимальном потока вшет хотя бы одно решение, причем дая этих алгоритмов не дана оценки трудоемкости. Вмосте с том, для близкой задачи - задачи о минимальном разреза - в работах Эдмондса Дж. и Карпа P.M., Дячица Е.Д.., Карзянова A.B. и др. разработаны методы, дмею-циэ полиномиальную оцэшсу трудоемкости. Поэтому представляет интерес построчило полиномиалышх алгоритмов для задачи о максимальном фронте донустишх сетей, о такке алгоритмов нахождения максимального Фронта в сетях общего вида и ориентированных графах. Кроме того, как показано в диссертационной работе, техника решения задачи о максимальном фронте мотт Сыть весьма плодотворно использована при разработке алгоритмов решения таких "грандов" комбинаторной оптимлзащиг, кш. задача упаковки вершин графа, задача разбиения мноаества, задача .назначения зкипаа-Й стюлетов и др.

Задачв о наибольшем множество попарно несравнимых (т.о. не принадлежащих одному пути) взвошошшх вершин ориентированного графа рассматривается в двух формулировках. Первая -в обычной постановке, а вторая с дополнительными ограничениям»!, суть которих состоит а следующем. Пусть множество вершин графа разбито на два подмноггаства W и Q. W - эк> множество "обычных" вершин, a Q - множество пар вершин. При этом произвольная вершина может входить лишь в одну пару и вэршшш любой пари должны бить несравнимыми. Для каздоВ пари видается обц^сй вес еэ вершин, а на вес каждой из ша. Требуется, чтобы в искомом множество .табая пара была бы представлена либо двумя вершинами, либо ни одной кз входждах в нее вершин, ß дассертацшшюй рчботе показано, как известная IiP-труднан задача упаковки вершин графа (в литературе часто называемая задачей о наибольшем внутренне устойчивом множество) моаэт быть сведена к исследуемой задаче с дополнительными ограничениями.

Задача разбиения множества принадлежит к классу NP-трудннх задач и мшит быть сформулирована в вида задачи цолочислешюго гтрограмгилрования с булевыми переменными специального вида (каяудой элемент матрицу ограничения имеет значение о либо 1). Свойства задачи и алгоритмы ее решения исследовались в работах Трубила В.А., Балаü:а Е., Падберга М. Пирса Да:., Ласки Дк., Гарфшкеля Р., Исмхаузера Дя., Иэрото-

на ?., Мулвал Дж., Вебера Дд. и др. С помопью известных алгоритмов иногда удается решить задачу разбиения множества с несколькими сотням* ограничений и несколыими тисяче.'.гл поремешшх, но часто задачи значительно меньших размеров (десятки ограничений и сотни поромвшшх) но реиа.отся за приемлемое время.

- Рассматриваемые в дагосоргацаошюЯ рибото вариантшо модели могут бить сформулировал! в в.чдо задач цзлочислоиного программирования с булош.гмл переменными и (наряду с обеими) узкоблочными ограничениям» вида J z^ < {=) 1. Модели этого типа имеют чрезвычайно широкую область применения. При практическом использовании вариантных жделей число огрожг-адагП moköt достигать несколько тысяч, а число пэромошых -нескольких десятков тысяч. Точное решэнло задач дискретной оптимизации большого размера в настоящее вре?ся требует знячк-тельнях вычислительны* услляЯ. Теоретические асследскония, выполненные ФжодельзтеЯяом D.D., Веягеровой H.A., Дкерос-лоу Р. и др.. показывают. что эта трудности идаот не технический, а принцкпивльннй характер, т.е. при решении дискретных задач сущвствуидая точки;.« методами (или их неггашщкпиалышма модификациями) появляются "патологические" примеры, в которых оогои вычислений близок к полному лоре-бору. Поэтому для задач общего вида большого размера ö;;;cict-вэиао приемлемыми являются приближенна метода. Вычислитель-кий опит показывает, что наиболее часто удается построить "хороший" приближенный алгоритм иа основе метода ветвей и границ. Особый интерес представляет разработав алгоритмов, аспользувдих метода негладкой оптимизации, предложенные ШоромН.З., н двойственные (лвгранжевы) оценки, свойства которых исследовались о рвботах Лебедева С.С., Шапиро Дн., Фишера М., Нортхупв В.

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

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

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

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

йзучыш свойства фронтов сети, проанализировано их взаимное расаолохипиэ. Докапано утверждение о пересечении я объединении какскмкльних фронтов. Получено оценка наибольшого количества ¡.¡эксгаиалышх фронтов и разработан алгората выделения всех максимальных фронтов сети. Известило алгоритма решения задачи о минимальном потоке шдй£кцирова;ш с использованием аппарате справочных, применяемого для решения задача о максимальном потоке. Показана некорректность алгоритма решения задачи о ¡шшмалыюм потоке, првдлогдэшюго Бортам К. Разработан влгоркта с полиномиальной оценкой трудоемкости решения задачи о максимальном фронте произвольной ориентированной сети. а также ориентированного графа. Показана возмозаюсть ислользования максимального фронта сети для решения некоторых задач на ориентированных графах. Доказано утверждение, обобщащее теорему Дялворта на случай пронзволь-шх орЖ) нтщювашшх грефэв.

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

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

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

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

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

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

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

Практическая цонность. Данная работа является составной часть еледущдх исследований, проводимых в Институте кибернетики им. В.И. Глушкова АЛ Украйни:

1. Разработать а юиэстн в эксплуатации ППП для решения на ЕС ЭВМ различных типов задач дискретнойоптимизации (ДИСПРО-З).

2. Разработать и ввести в эксплуатации ППП для решения на ЕС ЭВМ оптимизациошшг задач производственно-транспортного планирования большой размерности (ПЛАНЕР).

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

4. Разработка методов и программного обеспечения ПЭВМ для решения некоторых юмссов экстремальных комбинаторных задач.

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

Апробация. Основные результаты работы были представлены на седьмом Всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования" (г. Нарва-йызсуу, 1982 г.), на втором Всесоюзном совещании "Метода и программу решения оптимизационных задач на графах и сетях" (г. Улан-Удэ, 1982 г.), на республиканской школе -семинаре "Вопросы оптимизации вычислений" (г. Киев, 1ЭЭ0 г.). а также на научных семинарах "Теория оптимальных решений" Института кибернетики ш. В.М. Глушова АН Украины.

Публикации. Основное содержание работы отражено в 24 публикациях.

ООгам и структура работы. Работа состоит из введения, четырех глав, заключения и списка литература из 98 наименований. Общий объем работы 214 страниц, включая один рисунок и 9 таблиц.

СОДЕРХиШЁ РАБОТЫ

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

Первая глава диссертации "Задача о максимальном фронте сети н алгоритмы еэ решения" состоит из шеста параграфов.

.В §1.1 приведена постановка задачи о максимальном фронте сети, состоящая в следующем. Пусть 5 = III,А,С) -ориентированная сеть без петель и кратных дуг, для которой соответствующая неориентированная сеть связная. N = Ш != Г7п, - множество вершин сети, среда которых выделены дво вершшш: Нв - источник, - сток сети. А = J = йр. -

множество дуг сета (дуги будем обозначать либо А у .либо 11к с Н). О = (сЫ^)), J = ГГр,- функция пропускной способности, заданная на дугах сети и принимающая неотрицательные действительные значения.

Пусть X, У с н. Обозначим (Х,У) = е А: И, е X,

€ У>- '

Миозюство дуг R - (Х.Х), где X = ü \ X, «взывается разрезом сета S, разделяющим источник я сток, веля Nß s X и

Пропускной способность» с(Я) разреза Я называется сумма пропускных способностей входящее в иого дуг. т.о. с (Я) =

= Z

■ijin J

Разрез мижшзлыюй пропускной способности называется минимальным разрезом сети. Аналогично определяется максимальны Я разрез.

Если (Х.Х) = то такой разроз познвается Фронтом сета,

разделявшим источник и сток, н обозначается F ~ IXД!,

Будем говорить, что дуга А, и А. срявижги, если о со та существует некоторый путь, проходящий через эти душ. В противном случае дупл А; и /ife ноертглкш.

Обозначим А() множество выюиз ворашш дуг сети, a B(tt{) - множество входлсдах в М( дуг. Предположим, что для сети S вылолняатся условия

A{St) » (1.1)

Й(Яо) = 0. (1.2)

Заметим, что в этом случае сеть содержит хотя бы один фронт.

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

УтперздЕошг» . Для того чтобы множество дуг 9 е А' было фронтом сети удовлетворяя;;^ условиям (1.1) -необходимо и достаточно, чтобы ff было полным fмножеством попарно несравнимых дуг сета.

Это свойство приставляется наиболее важным с точ?щ зрения использования фронта для реиотая некоторых задач комбинаторной оптимизации.

В J1.2 рассматривается алгоритм нахоздьния допустимого петляя для задачи о минимальном потоке. Алгоритм имеет трудоемкость Щпр).

В j 1.3 п^казпно, как меюю модифицировать алгоритм методу m-меток ркшгия задачи о минимальном потоке для того, чтгбы использовать аппарат справочных, разработашшП Диви-[цм H.A. л Карзанаоым A.B. для зодпча о.максимальном потоке.

Модифицированный алгоритм же от трудоемкость О (гг3). Приведен пример, показывающий ошибочность алгоритма рошешя задачи о минимальном потоке, описанного в монографии Еержа К. "Теория графов"(1962).

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

Утварздание 1 .2. Если IX,Л и [У,У) - максимальные

фронты сети, то IX П УД П Л и II и У.Х и У1 - также максимальные Фронты сети.

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

3 при р = 3£.

[р/зЗ-1

4 '3 при р = ЗЙ+-1,

I р/Э) .

2-3 при р = ЗйкТ.

где * = 0, 1, 2.....

В $1.5 предложены алгоритмы радения задачи о максимальном фронте произвольной (не обязательно допустимой) ориентированной сети.

В §1.0 указан способ сведения задачи о максимальном фронта ориентированного графа к задаче о максимальном фронте допустимой сети. Доказано, что мощность минимального покрывающего множества путей для подмножества >шкоитур;шх дуг ориентировашюго гра:{а равна числу дуг максимального "1{юнта соотвотствугацей сети. Это утверздегае является обобщением известной теоремы ^длворта на случай произвольных ориентированных графов.

"Алгоритмы реаения задачи о наибольшем множестве попарно несравнимых версии ориентированное ¡"раф®" состоит из пяти параграф.

В 1 сформулированы дао задачи исследуемого тиля. Пусть О = IV,Е] - ковочный ориентированный граф боа петель.

кратных дуг и контуров, У = (и.), £ .-- - м'.юз;естио вер-

шзи, В = {(?_,>. / = Пга. - шозюство дуг. Каздой вершина орграфа О соответствует некоторое положительное число р(о{) - ее вес. Вершины и и^ называеются сравнимыми, если в £> существует некоторый путь, проходящий чорэз эти вершины, В противном случае и( и - несравнимее вершили. Первая задача состоит в нахоздешм наибольшего по сумме весов множества попарно несравнимых вершил орграфа О,

Рассмотрим теперь задачу о наибольшем ^тожестве попарно несравнимых вершин с дополнительны*®! ограничениями, суть которых состоит в слздунщэм. Пусть тас.тоство верзшн V. разбито на два подмножества 1! и 0. V - это гаокество "обнчнчх" вершин, а С} - ) - божество пар вершин. При этом произвольная верщшэ мойят входить лишь в одну пару и веришш любой пары дол^аш быть несравнимые. Для ка.-вдоЯ пери д^ задается общ!й вас с > > 0 двух Г'9 вершин, а но вес каздой из них. Требуется, чтоб;; в искомом шюжэства каждая нура была представлена либо двумя вершками, либо ¡ш оддоа из них.

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

В §2.2 обсуядавтся дна алгоритма реыэшп задачи о наибольшем кноз.встве попарно несравнимых веракн боз дополни-гельгшх ограничений. В первом из них, основэшюм на работе Корниловой Л.Е. и автора (1978 г.), эта задача сводится к задаче о максггмалыюм фронте некоторого орграфа, состоящего зз 2п вэропш и п>Р1 дуг. Во втором алгоритме техника метода зокэток применяется непосредственно к исходному орграфу В.

В $2.3 рассматривается алгоритм иетода Еотвей и границ решения задачи о наибольшем (люкостве попарно несравнимых зершян ориентировашого графа с дополнительными )гра!сгч01гля?.'.1, использувдий эвристические оценки. В этом алгоритма для вычисления верхних оценок значения целевой функции применяется эвристическая процедура, основашмя на юдафикации второго алгоритма из §2.2 с учетом того, что для саждоа пары ц е <) задается общий вес ее вершин, а не вес саадой из вершин, входящих в эту пару.

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

В §2.5 обсуздаются результаты вычислительного эксперимента с алгоритмами, описанными в 52.3 и §2.< (алгоритмы А2.2 и А2.3 соответственно).

Алгоритмы AZ.2 и АЛ.З реализованы в вида программ m языке Турбо-Паскаль (версия 5.5). Вычислительный экслерямегг проводился не ПЭВМ тала PC А? (тактовая частота в рею&к Турбо 12.5 МГц).

Множестве дуг орграфов без контуров, петель и кратны; дуг генерировались о помощью процедуры Р2.1, в которо] исиользуется процедура Турбо-Паскаля randcmín), возврадавда: целое "случайной" число из интервала 10,п). Входными пара метрами процедуры Р2.1 язлявтся: nu - число вершин орграфа, djsfijmx - максимальная степень вершины (сумма полустепене исхода и захода), nlajnax - мик имальное количество ду орграфа. Выходные параметры: nia - количество дуг орграфа, - множество дуг орграфа, deg - массив степеней вершин.

Процедура Р2.1. '¿'яг 0. Положить Е ■= 0, nia = 0, úegtv{} = 0, ¿ = TTw, J=nv Шаг !. Положить i = 1.

Шаг Z. Если d£?g(t>t) = dezmar, то пзрейти на шаг 5, противном случае - на шаг 3.

Шаг 3. Положить к - randcm(J). При выполнении каждого v условий к ¿ 0, tu^.u^] fi Е, cfcg(vk) < úegjmxc, ctogtUj) < < degjmx выполнит', следуодк» действия. Положить deg(Vj) = = cleg(Vj) + 1, üeg(vh) = <i?g(ufc) + 1, nia - nîa + 1. bkjsni дугу Iv^vjh в множество E. Если nia =* nlajnix, то закончи: выгюлноние процедуры.

Шаг 4. Положить ¿ = < +■ 1. Если ( > У, то перейти на шаг ! в противном случае - на шаг 2.

Шаг 5. Положить J = J - 1. Если J > J, то перейти на иаг ; в противном случае - завершить выполнение процедуры.

Множества пар вэршш, входящих в дополнительные огр ничения, а также веса гонерировахлсь с помацы) процоду

randan, при этом вес вершин (пары вершш) выбирался из интервала {l,nvl.

Результаты вычислительного эксперимента представлены в табл. 2.1 и 2.2 (для алгоритмов А2.2 и А2.3 соответственно). В таблицах использована следующие обозначения: пг -количество вершин; входящих в дополнительные ограничения. d(

- максимальная степень вершины,- d¿ - мжммалышя степень вершины. Для каждого из представленных в таблицах наборов параметров (nu, nia, df, <32, пг) орграфов было решено по пять задач с разними веез'/з и парами веражг. Числа внутри таблиц обозначают: верхнее - среднее значешэ величины (estí

- record) / record, где osi1 - значение первой оценки, среднее - среднее количество вершин дерево вотвлэний, нижнее

- среднее время решения задач;! (сек ), прочерк означает, что задача не била сгенерирована.

Из табл. 2.1 и 2.2 м-.«но сдолсть слодупцде выводи:' о) оба алгорптмэ "зЗДектишо" (по крайней море по количеству Eopmoi дорева ветвлений) решают рассматриваемые задачи;

б) двойственные оценки является более точными;

в) .для подавляющего числа задач алгоритм А2.2 работает быстрее, чем алгоритм Д2.3 (для некоторых - более чем ь два раза).

Рассмотрим теперь результаты эксперимента,проведенного для исследования гффекглвностл метода роиепия задачи упаковки верами графа путем с поде шля ее к зядзчо о наибольшем множестве попарно носрйвгш-'К ' вэрешн орграфа с дополни-талышмя ограшпенияка. Эксперимент, так го кок и предыдущий, проводился на ПЭВМ тала PC А? (тактовая частота в режима Турбо 12.5 ИГц). Решались задача упаковки взвешенных вершин однородных графов степени четыре. Ребрэ графов генерировались следующим образом: проводился генальтогюв (т.е. содержащий Dee веригаш) цикл, а к ному случайным образом добавлялось необюдаше количество ребер. В качестве весов вераяа выбирались целив числа, равномерно распределенные на отрезке Í20, 40!.

Результата вычислительного эксперимента приведены в табл. 2.3 и 2.4 (для алгорипюв Д2.2 и ¿2.3 соответственно), в которых приняты еледуыдке обозначешя: л - число вер-

Таблица 2.1

G TIT nv ~ 50 nv = 100 • nv - 150

nia = »22 d =5 4=2 nia = 2ЛЛ d. = IO d2=6 nia = 61',> d.=25 d^-16 nia = 499 ci =»0 <Ï£=9 nia = S 92 d,-20 d2=16 nia = 2<J79 d -50 nia = ) 120 d =15 d] = 11 nia = 1500 d.=30 4-r nia = ISOO d =75 d'2=S

20 0.03 2 3 0.04 1 3 0.01 0 4 0.01 0 6 0 0 5 0 0 16 0 0 21 0 0 3 0 0 3

30 0.04 2 4 0.04 г 4 0.01 0 4 0.01 0 13 0 0 7 . 0 0 12 0.01 1 28 0 0 4 0 0 4

38.. 40 0.04 5 7 0.09 2 6 _ 0.04 4 33 0 0 9 0 0 18 0.01 ; 1 ; 31 0 0 4 0 0 5

60 . _ ■ - _ 0.04 2 21 0 0 13 0.03 1 39 0.01 ! 2 46 0 0 4 0 0 5

80 - - 0.08 , 6 64 0.02 3 35 0.04 4 106 0 0 5 0 0 5

118.. - — • - - — - ' — 0.09 0 0

120 - . - . - - - 8 226 0 7 0 6

cu

M

a —

м

n о

аз С-«

Il Q И Ù) N d - il и - - t\i g -4 ^ ooco OOifl ooio OOul aof- ooco

s n Э si Il § о ïiriN а - ii. »■* fvj с « 4 oo«o OOt- aot- ooco оэо oom

0 H <\j Irt — d - 'i ~ — CM e t) сой C\ OOcu о oat 5 (M ci t~ • w.O CJ o — d*" t

Ol «son •j 1Л V в IV '1 i ~ - <\ e ч -s cri со- Ю oo- гм OOC4J о OOCM 1 1 1 i i i

8 » ë IV » Ц Ol О C1J ~ 0 if il - - Л; С V ГЗ о oo*- o oo- ooS t- Q- Ю i i i

Ol a •ч Il : « Ol El il ¡I - ~ (M t ч 4 оосз Ö IS) о о О Ю o t i i

s Il ~ Ifl 4 •0 <v¿ - 0 il il - Aj с 4 -0 OO-f oo-t 1 1 1 1 1 1 1 1 1 1 1 !

S il 4 *r Il о. о - *> lî II .. - - l\ e -ou 8 • — О o I- 1Л 13 40 о I 1 1 1 1 1 i i i

с ГЧ l\l « 1 1 С 4 ' а г, • см О Ö dcg? 1 1 1 1 1 1 ! 1 1

о Ь ____ Cj о п • о s о o œ • O ' <\l CC T -

Й О О - ф - о О Ci о о Со S » W е» a n a W (M i

-J -4 -4 О G О г s s s s g g § а

f» t» ООО Г\! fVJ Г\> tV) M О О О О О 8 8 8 я

KQ SO — СЛ 43 О ■ 8 2 8 8 ß S S S s

-•МЛ N го го го M W f- О СГ> -t» 2 2 8 -А

8 9 8 — -5 О S S S R S ¡л W vû -3 -j S 8 w л ш

03 CD О s s s —3 —Í —J —3 —} M (Í N M со -» — aj о § 1 § Л й

0.17 I 0.18 0.18 i a о о о о r j, '-» '-» — Ы J» (Г, А о\ '■V a p о r\> b О ® О 1 « о ч а ** i i ч О

PO p. -» С? 1Я «3 О ON 0> to -Э — go CD ~ * N3 -» Ol g ° s сГ'

5 g fe И rj î $ si s n m и N Ol m СЛ га

Ol (Ti ON 1 1 1 yi о о о — í>. M -» -» 1 1 1 1 1 — M C" ON CD 4* О О r ? ? W D u «». О

ON 1 8 IM 1 A œ 0 1 л ON и

ч а

О

ь п а

, * N W

Таблица 2.4

î-раф ni eat I - i-ec Л.

п я п1 est? rec rao «0 t Г

С, 50 100 69 106 708 651 0.09 33 40 2-57

% 50 ICQ 69 104 694 652 O.OT 6 12 2-10 4-45

Сз 50 100 69 101 750 627 0.20 0 96 9-18

G4 60 120 82 124 az7 720 0.15 12 93 16-10

С5 60 120 82 126 816 723 0.12 56 74 14-09

60 120 90 129 785 711 0.10 10 60 17-15 20-59

50 120 84 124 847 Т51 0.13 23 64 15-33

СЯ 60 120 83 123 860 723 0.19 232 250 41-53

С9 70 UC 1С0 144 1020 ? ? ? ? ?

а,а 70 140 9Э 142 1007 ? ? ? ? ? 7

Сп 70 140 95 141 1014 ? ? ? ? ?

вши графа G, гя - число ребер графа G, Ш - число вэрзшн

орграфа G, га/ - число дуг орграфа С, esti - целая часть значения первой оценка, гес - оптимальное значение целевой функции задачи упаковки верашн, VQ - число вершин дерева ветвлений, просмотренных к моменту получения оптимального решения, Н - o6ai.ee число просмотрена»! веракн дерева ветвлений, í - процессорное время (копи- сек.) решения задачи, Т -среднее процессорное время (кан.- сек.) решения, во при с;:-тельный знак,означает, что бил исчерпан лимит времени (60 МИН.)

Из табл. 2.3 и 2.4 следует, что для рассмотренных задач эвристические оценки лишь незначительно уступают двойственным оценкам. Что ss касается времени счета, то алгоритм А2.3 практически неконкурентоспособен с алгоритмом А2.2.

Необходимо отметить, что выбранные для эксперимента задачи являются довольно трудными для алгоритмов метода ветвей и границ. Об атом свидетельствуют приведенные в монографии Шора Н.Э. и Стеценко С.И. "Квадратичные экстремальные задачи и надвффэренцпруемая оптимизация" (1°89) результаты экспериментального исследованая оффективности использования чрезвычайно точных квадратичных двойственных оценок б r-^to-дь ветвей и границ решении задач упаковки вершин графов. Расчеты проводились по программа на языке Сортрзн на ЭВМ ЕС 1060 с ординарной точностью ыа "случайных" графах аналогичного класса. В качества весов Бершин такле выбирались "случайные" целые числа из интервала (20, 401. Среднее время решения ддя графов типа Gf - G3 (решоны три задачи) составило 23 мин., для графов типа С4 - Сд (решены пять задач) - 53 млн., для графов типа Gg - Gf) (решоны три задачи) - 76 мин.

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

нескольким!! тысячам;! переменных, но часто задачи значительно меньших размеров (десятки ограничения и сотни перемвшшх) но решаются за ириамлемое вромя. Глава состоит из пяти параграфов.

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

Задача целочисленного программирования с булевыш! пэ-ремешшми

J Сj 2j ~> ИИ (Win),

la x - 1. £ - 1,

ij

J=>

Zj *■ 0 v 1, J = 1 ,n,

где Cj $ 0; a{J » Ov I, i = 1 J = 1 ,n, известна в специальной литературе под названием "задача разбиения множества" (сокращенно ЗРМ). Это' название вытокает из плодущей интерпретация. Имеется шгсжество И, состоящее из и элементов, которое необходимо разбить на подогножества из

данного семейства С11,, П., И ) подмножеств множества ,'/. * с п

Каядое подмногэство lij, J 1 ,п, характеризуется булевым вектором Aj = t и 1.я, где atJ = 1, если элемент £ множества Я принадлежит подмножеству Uji a{J = 0 - в противном случае. Допустаяш решением задачи разбиения множества И является подсемейство ill, , Ч , .... И >=(i?,, U„, .... i/ },

j, j г Js> 7 г n

которое образует разбионш M (т.е. U. Л U = 0, если р" -V

г / а и U И. * i/). Требуется найти разбиение, которое мак-J»=I Jh

n _

симизирует (минимизирует) J с} xJt где Cj > О, J = 1 ,n, -

J=t

гва i

данное разбиение множества И, ~х = 0 - в противном случае.

некоторый "вес" подмнозевства Ну, х} = \, если И} входит

в

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

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

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

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

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

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

непосредственно (или после добввления сравнительно небольшого числа отсечений) получить решение исходной задачи разбиения шкшэства.

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

Разработанный алгоритм генерирует последовательность решений задачи разбивши множества. таку», что:

1) соседнио решения этой последовательности соответствуют смежным вершинам многогранника Р;

2) значение целевой функции на данной последовательности монотонно улучшается;

3) последнее решение из полученной последовательности является оптимальным ' ревенном задачи (в случав ее разрешимости).

Алгоритм реализован на языке Фортран-17 ОС ЕС ЭВМ в виде модуля пакета прикладных программ ДИСПРО - 3. Имеется возможность использовать модуль в режиме диалога, изменяя максимальное количество переменных, индексы которых могут быть зафиксированы на ветви дерева ветвлений.

Для проверки эффективности алгоритма и его программной реализации бил проведен вычислительный эксперимент на 16 случайных задачах, данные для которых были получены с помощью генератора псевдослучайных чисел, равномерно распределенных на отрезке 10, 1!. Результаты эксперимента приведены в таблице 3.1. В ней использованы следующие обозначения: я - количество ограничений задачи, п - число переменных, й -

Таблица 3.1

Номер задачи m п (1 К я, "г £

1 30 200 O.'i 7 3 205 610 0-3)

2 30 200 0.43 2 85 6167 1-08

3 30 200 0.28 3 5836 16182 6-20

4 зп 600 0.85 4 2408 4776 4-35

5 'за 600 0.43 1 0 18175 7-49

б 30 600 0.39 6 107435 139059 40-23

7 30 600 0.29 8

0 30 1000 0.87 3 ,76 7361 11 -24

9 30 1000 0.49 ъ 9406 78266 33-13

10 30 1000 ■0.39 1 0 79629 36 -41

11 100 800 0.79 6 4075 7646 23-09

12 100 800 0.61 4 35060 76849 42-24

13 100 G00 0.44 Í- 340 98364 42-45

14 100 1000 0.81 4 5176 13611 35-39

15 100 1000 0.63 г 261 67025 48-28

16 100 1000 0.45 2

плотность матраца ограничений, X - число найденных допусти шх решений, - количество вершин дерева ветвлений, просмотренных к моменту получения оптимального решения, Нг -общее число просмотренных вершин, t - процессорное время (мин.-сек.) ЭВМ ЕС 1040 (шаг G0). Незаполненные клетки означают. что был исчерпан лимит времени (60 минут) до получения оптимального решения.

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

В четвертой главе "Оптимизация вариантных моделей" рассматриваются алгоритмы оптимизация вариантянх ?.юдэлэЗ, которые могут бить сформулированы в ваде задач целочисленного программирования с булевыми переменными а узкоблочными ограничениями вида < <«> 1. Модели этого типа имеют

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

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

Едва ли не наиболее широко известной моделью такого типа является тек называемая "вариантная" модель:

Группы переменных с одинаковыми значениями верхнего

называются блоками. Векторы (с*, а^......а^), .МТп,

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

Чаще всего эта модель применяется для планирования производства группы предприятий (отрасли, концерна и т.д.). Индекс Ш при этом - номер предприятия, I - номер вида выпускаемой продукции, / - номер технологически допустимого вектора затрат-випуска, а^- объем выпуска, с^- затраты, соответствующие /-ну варианту плана.

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

.М,п.

V

индекса а такке другие элементы с тем ко индексом

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

В §4.3 обсуждается использование двойственных оценок в алгоритмах оптимизации вариантных моделей. Из обзора, приведенного в }4.2, можно сделать вывод о том, что в большинстве программных реализаций метод« ветвей и границ, которые могут быть использованы для оптимизации вариантных моделей, при вычислении оценок решаются с помощью симплекс-метода релак-сировашше задачи линейного программирования. Этот прием обладает двумя существенными недостатками:

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

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

Альтернативным подходом является использование двойственных (лЕгрангавых) оценок. В $4.2 на примере практически важной задачи перспективного внутриотраслевого распределения капитальных вложений локазенв возможность учета спетшГики задачи при создании алгоримов метода ветвей и границ, использующих двойстваншэ оценки. В разработанном алгоритме для вычисления верхних оценок применяется эвристическая процедура, в которой мноаество двойственных переменных разбивается на две группы и оптимизеция производится при помоями г-алгоритма по одной группа и о бойце иного градиентного спуска - по другой. Приводятся результата вычислительного эксперимента на тестовых примерах о 111 ограничениями и 250 переменными. Для некоторых примеров удовлетворительные целочисленные релеяия получены быстрее, чем решения ролгжеи-ронашшх задач линейного программирования (последний оказались сильно рырождешшми).

0 5-5.4 обоуэдяотся некоторые проблемы приближенной

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

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

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

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

^ = 1Л1=1

Т1 К

J=1Ь=I

п

I

J-t)i-t

f > TTp.

Ej ___

¿ i* =. i, J-ри ,n,

íj »0*1. >1 ,n. k^.Kj.

Пусть ü-(ü м-пй,- вычислэнлоэ с некоторой точность!) даиьнив двойственной задачи вида

i я л к. i

^^ i=í t = l+» l-t я

+1 иЛ »•

■дп область D, как обычно,задается слвдуодей системой огря-игшшй:

2 í}<i.

л-г

к,

¿ У* * J-P^ñ, a* i

у* -Ovi,

Используя значения üt, i =T7i, мозгю различными способа-ы определить для каадого блока "няилучяшЯ" столбец и шсстоя-шя столбцов данного блока от "иеилучшэго" столбца. В ■окролоннуо задачу включается заданное количество столбцов, шимрний удаленных от "наилучших* столбцов.

Об<»значим с* « с* - V ii.a* + ) ti,а* , ./=ПИ, ЫХ.

J J « 'J 1---Y+» ' J .Hin , ___

•j - ra ir <c*>, r,^ = mín (á*), J--4,n. к > .Kj &~7,Kj

При пронедонии экспериментальных расчетов в качество наилучшего" иибирялгя столбец бгока, имеясиЯ максимальное

значение ckf, о в качестве расстояния величина dy вычисляемая по формуле

5*

4

-■> , если б7аз>0.

_

J j=i,n. ft=m .

Iкм ,

ij - Cj иначе. Пусть H J >- n -кшшальное, o И > Н . - максимальное

Witt яюх rain

количество переменных сокращенной задачи. Выбор переменных, включаемых в сокрсщенну») задачу, осуществляется в два этапа. На ш>рвом атапе с помощью процедуры Р4.1 определяются í>retn переменных сокращенной задачи.

Процедура Р4.1.

Шаг JL- Вычислить с^. J=í7ñ, к--TjLy . J^7ñ,

- max min

О = mar' Сßj - ö ). Шаг 2. Положить 0=6/2.

Шаг J?. Пусть W - множество индексов переменных сокращенной задачи. Положить £cjhi | N |-tf . , то закончить

J min

вшю-ыошз процедуру.

Шаг 4. Если !N|>//wlii, то перейти на шаг 5. Положить C-ß*

+(0-С)/2. Если СС'Д, где Д - параметр процедуру,то перейти на шаг 5, в противном случае перейти на шаг 3.

Шяг_5. Положить 6-Ö, 0=С/2. Если C-GíA, то прейти на шаг 6, в противном случае перейти на шаг 3.

Шаг G. Положить И Л (j.kjul* С). Закончить выполнение процедуры.

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

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

2) Закрытие вершины происходит, лишь в том случае, если количество переменных, имевдих ^иксироиашюе значение, равно N

max

5)Выбор переменной ветвления х^, шввдей наибольшее течение с*, осуществляется среда всех свободных переменных 1С х одно Я задачи. Если (},1г)0, то и {(,/,£)>. Если то процесс ветвлешч завершается.

Для проверки эффективности предлагаемого подхода был гроведен вычислительный эксперимент на ПЭВМ типа РС Л. Данные для тестовых задач- генерировались с помощью ■енератора псевдослучайных чисел, равномерно распределенных [а отрезке С О, П. При атом ск} £ [0,5001 - целые числа, е 0,5001 - целые числа, целая часть где р с ГО.7,

тг

|.9] - псевдослучайное число, = £ < т1п +

аи {о^))/2, (=Т7Т, = целая часть где ¡5 е

__

0.3,0.5) - псевдослучайное число, £=Т+Т7й, п=10, Я^=10,

*Т7я,1=5, гд=10, р= 5. Все задачи решались с относительной огрешностыо, не превосходящей 0.000, для вычисления начений и{ использовался г-алгоритм, число итераций оторого задавалось равным 5т, точность по переменным -.01. Результата эксперимента представлены в табл. 4.1, в оторой приняты следущиэ обозначения: д - отношение эличества ненулевых к общему числу элементов , г - вели-гаа первой оценки, 2*- оптимальное значение целевой функции эзулътвте реаения сокращенной задачи, прочерк означает, что мращенная задача оказалась недопустимой.

Анализ результатов эксперимента позволяет сделать сле-?нцио выводы:

) При включении 20-40% переменных в сокращенную задачу были >чяо решеш? 13 из 15 тестовых задач. Два задачи (<?-0.7) Ш! решены с относительными погрешностями 0.01 и О.04. | Использование второго этана выбора переменных сокращений задачи, по-видимому, целесообразно лишь для задач с ¡0.5 (учитывая данные по решешщ задачи Я 9). ' На эффективность предлагаемого подхода в большей мере гияет не значение "относительного разрыва двойственности" .= Сг-г* )/г*), а отно&эцие количества ненулевых к общему слу элементов а^. Причем с уменьшением значения д

Таблице 4.1

Номэр задачи Я г -я* Z* z%-z 2

H*tn=20 Я =20 Jsax V =30 пах Я =30 яаг И . -40 ein В =40 «шгх Я . =20 Tai« Р =40 тал W30 W40

1 0.3 0.17 - - - 0 - 0

2 0.3 0.18 0 0 0 0 - 0 0

3 0.3 0.14 - 0.01 - 0 - 0.01

4 0.3 0.13 0 0 0 0 0 0

5 0.3 0.10 0 0 0 0 0 0

6 0.5 0.15 0 0 0 0 0 0

7 0.5 0.13 - 0 0.07 0 . 0.07 0

8 0.5 0.01 0 0 .. 0.J '•• о . 0 0

9 0.5 0.12 - - 0 .■ - 0 0.02

10 0.5 0.28 - - - 0 - -

. 11 0.7 0.10 - - 0.04 - 0.04 0.32

12 0.7 0.05 - 0,13 0.01 0.04 0.01

13 0.7 0.05 - - 0.04 0 0.04 0

и 0.7 0.05 - - - о.ог - 0

15 0.7 0.05 0.С2 о.ог 0.02 0.02 0 0.01

уменьшается необходимое количество перемшвшх сокращенной

задачи. Лз десяти задач с q = 0.3 - 0.5, а = 0.01 - 0.Z8

пять били решены при 20, три - при 30 (одна из

них с относительной погрешностью 0.01) и лишь две - при

W « 4.0. Из пяти задач с q = 0.7, а = 0.05 - 0.10 ни одна гсал 4

задача не была решена точно при У < 30.

Этот подход прч фиксированном количестве переменных сокращенной задачи может лишь показать неразрешимость последней. Однако в принципа на основе предлагаемого подхода гкшю построить алгоритм решения исходной задачи с заданной погрешностью, например, решая серию сокращенных задач с увеличением количества переменных в квздой последующей задаче. Для использования информации о решении предыдущей задачи можно применить "дизъквштшмша" итсечютя, предложенные Балашем Е.

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

ветвлений новый вариант (J.,ft. ), такой, что ск.*> тих ск.,

J* и.ъ)ен 3

где ¡ïc Я - множество пар индексов свободных в данной вершине переменных. Будем говорить, что опыт положительной, если такой шриант бал получен.

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

процедура Р4.2. Шаг 0. Пусть задано некоторое множество N вариантов, ~ - ¡/V!, максимальное количество вариантов,

используемых в модели, У^- максимальное^количество опытов, ПрОВОДЙМЫХ в одной серию •

Шаг 1. Положить п = 0, п = IВыполнить шдкфяцироваяную

Т а ö л и ц а 4.2

Нокэр задачи л к г - г Я*- Z

q

К . =30 nin V =50 «m* W30 В ~бО ЛОЖ W =70 ЧАХ ¡aln В -70 пах Я , =50 «In Gl&X Я . ~70 mtn Л =70 ягсьх

1 0.3 0.17 0.06 0 0 0 0 -

г 0.3 0.22 0.18 0.18 0.18 о ■ - -

3 0.3 0.80 - - - 0 0 -

4 0.3 0.08 0.01 0 0 0.01 0.01 0.18

5 0.3 0.19 0.02 о.ог 0.02 0.CK 0.02 0.29

б 0.5 0.17 0.10 0.01 0 0 0 -

7 0.5 0.16 0 0 0 0 •0

8 0.5 0.03 . 0.09 0.СГ7 0.07;-1 - о.от 0.07 0.84

9 0.5 0.13 0 0 0 0 0 0.56

10 0.5 0.05 0 0 0 0 0 0.14

11 О.Т 0.07 0.01 с 0 ' 0 0 0.08

12 0.7 0 .ОТ 0.04 0.01 0.01 0 0 0.03

13 0.7 0.03 0 0 0 0 0 0.22

14 0.7 0.04 0 0 0 0 0 0.17

15 0.7 0.05 ,..,., i - о.ог ------ 0 0 0 0 0.22

процедуру ветвления, выполяяя пра проведении кяздого опыта следующие действия. Еслп опит положительный, то вклотить вариант (J^.ft^) в мпозйство Я и зафиксировать переменную х^а

в дереве ветвлений со значением 1. .Если !//! = N , то аэ-

л VUX3C

кончить выполнение процодури. Положить nQ = п0+-1. Если nQ = U0, то перайта на ваг 2.

Шаг 2. Если ÜV! п^, то закончить виполлонкэ процедуры, в противном случае - перейти на aar 1.

Для проверки эффокт^гокости предлагаемого подхода бил проведен вычислительный эксперимент па ПЭВМ типа ?С AT. Тестовые задачи генерировались опяоашшм виио способом. В ио-гвство У на шага 0 вкличплись.по Nn(n / п порвих варишггов из кяздого блока. Во в cor расчетах HQ принималось рап;шм 50. Пра проведении опытов значения определялись сладуо-

d^îm образом: (J= arg enz с1!, гдо !' - ино^оство пар

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

Анализ результатов эксперимента показывает, что, используя 30-40% всех возмоянйх вариантов в к а час те у начального множества л выбирая оце 40-30% вариантов гтрп помощи предлагаемого подхода, 13 тестовых зядач били рошеш точно. Лое оставшиеся зодачп (.''5 и Гй) были решена с относительными погрешностями, не гсрогасходядаа 0.02 а

0.07 соответственно. Эффективность подхода практически m зависит от значения относительного рппршш двойственности (для тестовых задач ата вэлжчшп колобапясь от 0.03 до р.ПО) и отношения количества ¡тонуловнх к общему количеству зле№!ггоп ah(j. Для подавлямщего болыгинствя задач предплагае *ый способ выбора • вариантов позтюляот получить решении, JOTopue гораздо лучше, чем решения, получаегаю при включении в модель Яплх / п поршх вариантов из коядого блока (см. последний столбец табл. 4.2).

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

1. Войтишян C.B. Зядяча о минимальном потоке и алгоритмы ее решения/УКибернотакя. - 1980. - » 1. - 0.116 -• 118.

?.. Войтишин В.В. Об одном способе внчислонин оцпнки в зада-

че разбиения множества//ХиО&рнотика. - 1980. - й 6. - С. 129

- 130.

3. ЛоЛтишии Ю.В. Алгоритмы для решения задачи о максимальном фронт» произвольной сета'/Теория оптимальных решений. -Киев: Кя-т кибернетики им. B.'.t. Глушкова АН УССР, 19U0. -

С.19 - 25.

4. ТруОнн З.А., Гюйтииин D.B. Алгоритм решения задачи раз-б'.юшы мдазшсгва/'/Киб&рнетака. - 1УЗ!. - Л 2. - С. 136.

5. !.ЪЯт;«ш» В.В. Алгоритм решения задачи о максимальном A ренте ориентнровшшой нота/УМитоды и программа решения опта ми:.£|Дион5ШХ задач на графах и сетях: Тез. докл. 2-го Все сова сове;;;, (г. Улан-Удэ, 24 - 26 авг. 1982 г.). - Новосибирск: ВЦ СО АН СССР, 1SS3. Ч. ?,.- С.?А-27.

6. Войтиаин Ь.В. Сетевой подход к решению задачи разбашш множества. - Киев, 1036, - 33 с. - (Презр./дН УССР, '."и-т га борнетики им. В.М. Глушкова; US-13).

7. Войтишки D.B., Трубда В.А.. Оптимизация вариантных модели! развития производства. - Ки&а, 1937. - 19 е.- (Ilpenp./AIi УССР. Ия-т кибернетики им. В.М. Глуакова; 87-50).

£]. ЕойТиЗШ D.B., Шарковская Е.А. 3;;ш»рж.:ентелыюе сравнение методов сведе.тая задачи разбиения множостоа к сетевы? юд&лям//Яакаты прикладных программ и чисгсешшо метода. ■ Киев: Ин-т кибернетики им. В.М. Глушкова АЛ УССР, 1SS3. -C.&S - 61.

9. Войтиаиш Г. В. Вычисление оценок при сетевом подходе : рашениэ задачи разбиения шюз:ества//К;!бррнетика. - iyii8. -№ 3. - С.117 - 1 Ш.

Ю. иойгаган Ю.В. Алгоритмы решения задачи о наибольшем мгю згестве попарно несравним« взвешенных вершин ориентирован кого графа без контуров//Кибернэтака и систомнлй анализ. 1991. - J5 4. - С.5 11 .

11. йойтианш П.В., Марковская Е.А. Алгоритм решения задач упаковки вершин rpaJia/ZTaM же. - Jf G. - C-.lfffl.

12. Войтишин Ю.В. Приближенная оптимизация вариантных моде Д£!й развития прсизводствчшшх систем. - Киев, ;'ot. - 1? с

- (Препр./ЛН УССР. Ии-т кибернетики им. L'.M. Глумова; 91-Е