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

ЗАПОРОЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

^ , на правах рукописи

КОЗИН ИГОРЬ ВИКТОРОВИЧ

ИССЛЕДОВАНИЕ ГЕОМЕТРИЧЕСКОЙ СТРУКТУРЫ РЕШЕНИИ НЕКОТОРЫХ КЛАССОВ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ

05.13.16. - Применение вычислительной техники математического моделирования и математических методов в научных исследованиях.

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

Запорожье - 1993

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

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

математических наук, профессор СЕЕГИЕНКО И.В.

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

профессор ЕМЕЛИЧЕВ В.А. кандидат физико-математических наук, доцент ТУРЧИНА*З.А.

Ведущая организация: Институт информационных технологий и *

прикладной математики СО РАН

Защита диссертации состоится "<с. 1993 г.

на заседании специализированного совета К 063.52.02 при

Запорокском государственном университете по адрэсу: 330600, г.Запорожье, ул. Жуковского, 66 ауд.

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

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

1993 г.

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

к.т.н., доцент ^/Г/СЫСОЕВ Ю.А

Общая характеристика работа

АКТУАЛЬНОСТЬ ПРОБЛЕМЫ. Диссертационная работа посвящена исследованию математических моделей и методов решения оптимизационных задач о векторными целевыми функциями. Такие задачи является математическими моделями шбора наиболее целесообразных вариантов, возникающих в автоматизированном проектировании, планировании, экономике и других областях. Особенностью этих задач является оценка качеества решений при наличии нескольких, как правило несоизмеримых критериев. В зависимости от постановки задачи, различные критерии входят в состав векторной целевой функции (ВЦФ) в различных комбинациях, порождая тем самым многообразие задач векторной оптимизации.

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

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

имеет большое практическое и теоретическое значение.

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

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

ЦЕЛЬ РАБОТЫ - исследование свойств лнохестб сиътернсти& [НА) для многокритериальных задач линейного программирования, целочисленного линейного программирования, теории графов. Основные направления начтоящей работы состоят в следующем:

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

2. Построить алгоритм отыскания ГШ. для многокритериальной задачи линейного программирования.

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

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

5. Исследовать группы движений критериального пространства, сохранящие множества альтернатив.

МЕТОДИКА ШЖШЖБШ- В основу исследований были полонены методология исследования полного множества альтернатив (ПЫА) для дискретных многокритериальных задач на графах. Использовался аппарат теории реберных графов при отыскании оценок мощности ПМА многокритериальных задач покрытия орграфа и аппарат теории груш при анализа геометрических свойств множеств альтернатив.

НАУЧНАЯ НОВИЗНА.' Установлен критерий полноты для

многокритериальной задачи линейного программирования и, в

частности, для транспортной задачи. Построен простой алгоритм

для отыскания полного множества альтернатив двукритериальной

задачи линейного программирования. Предложен метод отыскания « .

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

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ. Разработанные в диссертации метода могут быть использованы для решения ряда практических задач, возникапцих в САПР электронной Аппаратуры на этапе конструкторского проектирования, цри решении экономических задач и задач, возникавдих в области управления.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Предложенные в работе метода использованы при разработке математического обеспечения для расчета эффективности новой техники с учетом многих показателей в Институте трансфэрматоростроения, при разработке

- б -

программного обеспечения для автоматизации банковской деятельности для Агропромбанка "УКРАИНА", при разработке алгоритмов обработки финансовых документов в финотделах райисполкомов.

ПУБЛИКАЦИИ И АПРОБАЦИЯ РАБОТЫ. По теме диссертации опубликовано 16 печатных работ. Основные результаты настоящей диссертации докладывались и обсуждались на VI научной конференции "Методы математического программирования" (Свердловск 1989), на VIII, IX Всесоюзных конференциях "Проблемы теоретической кибернетики" (Горький, 1989, Саратов, 1ЭЭ1), на школах семинарах "Дискретная оптимизация" (Алушта 1988,1991), на Всесоюзном семинаре "Дискретная оптимизация. Метода и прилокения" (Тбилиси 1990), на 11-й Всесоюзной школе "Системы программного обеспечения решения задач оптимального планирования" (Кострома, 1990), Республиканском семинаре по дискретной оптимизации (Ужгород, 1391), на

научно-исследовательских семинарах по теории графов и их приложениям (Одесса 1992,1993), а также на научных семинарах Института кибернетики АН Украины (Киев), Института информационных технологий и прикладной математики СО АН России (Омск) и др.

СТРУКТУРА и ОБЪЕМ РАБОТЫ. Диссертационная работа состоит из введения, четырех глэе, заключения, списка литературы из 32 наименований и приложения, содержащего документ, отражающий внедрение результатов работы. Общий объем работы - 74 страницы (включая приложение). .

- л -

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

В качестве второго критерия брался весовой критерий или критерий "узкого места", т.е. минимаксный критерий.

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

Рассмотрим двукритериальнув задачу покрытия взвешенного орграфа С цепями. В качестве критериев выберем число компонент связности покрытия и весовой критерий. Обозначим через Х={х> множество всех покрытий орграфа С, и через Х° - полное мнохэство альтернатив рассматриваемой задачи. Положим g(x) -число компонент покрытия х.

Получена следующая оценка мощности ША в классе двукритеризльных задач покрытия сильносвязного орграфа цепями:

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

|Х°| 5 в(х*) - \ Е |<Ми) - С1_(и)|,

где i* - оптимальное решение задачи о покрытии орграфа G с одним весовым критерием, йт(и) и d_(u) -соответственно полустепени захода и исхода вершины и в вершшном орграфе S(G), суммирование ведется по всем вершинам и орграфа S(G).

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

Теорема 2.5. Для зздачи с<5 иерархическом остовном дереве сильносзязного орграфа G имеет место оценка модности ПМА :

|Х°| < L - max Ud^(u) - 1)/d_(u)C, (5)

гдэ максимум берется по всем вершинам орграфа S(G), как и правде, dr (u), d_(u) - соответственно степени захода и исхода вершины и орграфа S(G), ]at - наименьшее целое в множестве i х е R : х > а}.

ТРЕТЬЯ ГЛАВА посвящена оценке разрешапцей способности сигоритлов линейной свертка (ЛЛС) для некоторых классов дискретных многокритериальных задач. МО является наиболее распространенным алгоритмом отыскания элементов ПЫ для многокритериальных задач с линейной ВЦФ. Естественно, возникзат воцрос о возможности отыскания всех элементов ПМ (или ПМА) в той или другой многокритериальной задаче с помощью АЛО. В частности, для ЗЛП с помощью ДЛС могут быть найдены все точки ПЫ (ПМА). К сожалению, далеко не для всех задач проблема отыскания ПМ (или ПМА) разрешима с помощью АЛС. Актуальным является обоснование ответа на следущий вопрос: если для данной задачи проблема нахождения ПМА Х° неразрешима с помощыз

АЛС, то какой наибольшей мощности может достигать подмножество Ха с х°, выделяемое из X с помощью МО. В работе получены следующие оценки разрешающей способности АЛС для отдельных классов дискретных многокритериальных задач:

Теорема 3.1. Для 2-критериальной задачи Ъг об остовных деревьях разрешающая способность АЛС ограничена полиномом четвертой степени от числа вершин п:

р (2,п) < (п*- 2 п3- пЧ 2 п) + 1.

Теорема З.Й.Если для всех х <s X мощность |Ех | < п и

max w (е) < nck , где с = const, k=I,2, то разрешающая е«Е

способность АЛС нэ превосходит величины

p(2,n) < min { nCl+1,nCl+1,vt где vk= 0(n2lc_1), k=1,2.

Заключительная ЧЕТВЕРТАЯ ГЛАВА работы посвященапроблемы ЕЫбора в условиях многокритериальности. Проблема выбора наиболее целесообразного решения в услових многокритериальности практически всегда возникает в процессе создания автоматизированных систем управления, систем

автоматизированного проектирования, прогнозирования и т.д.

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

индуцируется ВЦ® Р: X —» R".

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

Наиболее распространенными МА является множество Парето

»V

X, ПЫА ir и ленсиногрсфачеасое лнахзаа&о алапернатиЗ {МЛ)

Xlex ' Х1ех = X £ X.

Одним из часто встречавшихся приемов получения решения

является следующий. Строится некоторая свертка критериев ила, в

более общем случае, выбирается порядок на ЩР более слабый, чем

порядок, порождаемый ВЦ® Определяются точки оптимума по этой

свертке или порядку. Этп точки и берутся в качэстге искомого

решения. Очень часто при задании отдельных критериев ВЦФ

присутствует некоторая доля неопределенности. Например, не

опрадалаш начала отсчета координат в критериальном

пространстве или не опредэлэн масттаб измерения того или иного

критерия. В таких случаях неопределенность, которая да

сказываотся на ПИ, ыожэт существенно повлиять на решение,

получаемое в результате сгертки критериев.

Ыэру неопределенности при задании векторной целевой

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

порядка, поровдаомоэ этой целезой функцией на множестве X.

. В работе вычислены группы преобразований критериального

пространства Р", сохренящиа наиболее распространенные

множества альтернатив. В частности имеют место:

Теорема 4.S. Группа преобразований на Rn, сохраняющих множество Парето, изоморфна прямому произведении SnxD, где Sn - груша перестановок п элементов и D - группа преобразований вида

(Vх*.....xj —► (Ф4 (Xt),фа (х2).....Ф„ (*„>).

где фi ) ,ф, (х4),... ,фп (хп) - возрастающие функции соответствующих переменных.

Теорема 4.7-9. Группа сдвигов пространства Rn сохраняет множество альтернатив, порождаемое алгоритмами линейной свертки, лексикографическое множество альтернатив и лексиминный порядок.

В ЗАКЛЮЧЕНИИ сформулированы основные результаты и еыводы диссертации, которые выносятся на защиту:

1. Свойство полноты (квазиполноты) обобщено на случай многокритериальной задачи линейного программирования. Исследована геометрическая структора множеств альтернатив многокритериальной ЗЛП. Доказана квазиполнота N-критериальной ЗЛП при №s2.

2. lía основе результатов исследования геометрической структуры ПМА многокритериальной ЗЛП предложен простой симплекс-алгоритм отыскания ПМА двукритериальной ЗЛП с удельно-полиномиальной трудоемкостью.

3. Исследованы свойства реберных и вершинных орграфов. Установлен ряд связей мекду свойствами орграфа и свойствами его реберного и вершинного орграфа.

4. На основе полученных свойств орграфов построены оценки

- re -

мощности ПМА для некоторых классов двукритериальных задач на орграфах.

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

6. Рассмотрена .проблема принятия решения в услових

* ч

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

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

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

1. Козин И.В., П8репелица В.А. Об оценках разрешапцей способности алгоритмов линейной свертки // Основы теории вычислеий: Сб. аннат. докладов VI Международной конференции -Казань: Казанский ун-т, 1987. - 0. 2S.

2. Козин И.В. Признаки существования гамильтоновых циклов в орграфах // Проблемы теоретической кибернетики: Тезисы докладов VIII Всесоюзной конференции, Горький, 1988. - С. 173.

3. Козин И.В. Алгебраические модели зацеплений в R9 // Тезисы докладов IX Всесоюзной геометрической конференции, Кишинев, 1988. - 0. 42.

4. Козин И.В., Перепелица В.А. 00 оценках разрешающей способности алгоритмов линейной свертки. Два. в УкрНИИНТИ, 1989. Р.ГАСНГИ 27.47.19. - 16 с.

5. Козин И.В., Максишко Н.К. Исследование одного класса многокритериальных задач об остовных деревьях // Теория и программная реализация методов дискретной оптимизации: Об. науч. тр. - Киев: Ин-т кибернетики им. В.Ы. Глушкова АН УССР, 1989. - С. 40-43.

6. Козин И.В., Максишко Н.К., Перепелица В.А. К проблеме нахождения множеств альтернатив для многокритериальных задач дискретного программирования // Методы и программы решения оптимизационных задач на графах и сетях: Тез. докл. IV Всесоюз. совет. - Новосибирск: ВЦ СО АН СССР, 1989. - 4.2, - С. 51 - 53.

7. Козин И.В. Задача коммивояжера как задача целочисленного квадратичного программирования // Республ. семинар по дискретной оптимизации : Тезисы докладов - Киев: Ин-т кибернетики км. В.М. Глушкова АН УССР, 1990. - С.39-40.

8. Козин И.В., Перепелица В.А. Алгоритм нахождения полного множества альтернатив двукритериальной задачи линейного программирования // Системы программного обеспечения решения задач оптимального планирования: Тезисы докладов 11 Всесоюзной школы, г.Кострома, 1990 - М: ЦЭМИ АН СССР, 1990. - С. 62-63.

9. Kozin, I.V. About cvasicompletness of multicrlterlal problen of linear prograirroing. XV International conference Mathematical Optimization - Theory and Application. Eisenach, Germany, 1990, pp. 10-14.

10. Perepelitsa V.A., and Kozin, I.V. About solving

capability of tha linear agregation algorithm. Techalsche Hochschule Ilnenau, DDR, Intern, tagung, Hath, optlm. rod anrendrmgen, Eisenach, 1939, pp. 137-140.

11. Козин И.В., Перепелица В.А. Об алгоритмах о оценками для задача о лэсах с дрсбко-лпнвйной целевой функцией // Проблемы теоретической; кибернетики: Тез. докл. XI Всесоюзн. конф. - Еслгогрвд: Еолгогр. гос. ун-т, 1ЭЭС. - 0.56.

12. Козш И.В. О квазшгалноте многокритериальной задачи линейного программирования // Математическое программирование и прялсзэтая: Тезиса докладов научной конферзвдпи - СЕэрдловск: Из-т математика и механики УО АН СССР, 19Э1. - С. 82-33.

12. Козин И.В. Проблема .выбора решения в задачах многокритериальной оптимизации' // САПР-93: Нов. инф. технологии в науке, образования и бизнеса: Тез. докл. 22 Международной кснф. - Гурзуф, 1Э93. - С.63-64. .

14. Козин И.В., Баштанник О.И. Автоматизированное документирование баз данных // САПР-93: Нов. инф. технологии в науке, образовании и бизнэсе: Тез. докл. IX Ыеадународной конф. - Гурзуф, 1993. - 0.92.

15. Kozln, I.Y. Problem of the Optimal Solution Choice In Multlobjectlve Optimization Models // International 93 LtIy Conference "Applied Modelling & Simulation". Summaries of accepted concanicationa. Lviv, 1993, pp. 10-11.

. 16. Коз1н I.В. Про оц!нки потукност1 TOBHOl мцожини альтернатив для дэяких двокритер1альних задач на графах // ДАН УкраХнп, в печати.