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

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

МУЗАЛЕВСКИЙ ФЕДОР АЛЕКСАНДРОВИЧ

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ФУНКЦИЙ ВЫБОРА В ОБОБЩЕННОМ ДИНАМИЧЕСКОМ ПРОГРАММИРОВАНИИ

05.13.18 — Математическое моделирование, численные методы и комплексы программ

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

16 МАЙ 2013

Воронеж —2013

005058035

Работа выполнена в ФГБОУ ВПО «Воронежский государственный университет инженерных технологий»

Научный руководитель:

Официальные оппоненты:

доктор физико-математических наук, доцент Бугаев Юрий Владимирович (ФГБОУ ВПО «Воронежский государственный университет инженерных технологий»)

Провоторов Вячеслав Васильевич

доктор физико-математических наук, доцент (ФГБОУ ВПО «Воронежский государственный университет», профессор кафедры дифференциальных уравнений в частных производных и теории вероятностей)

Белокуров Сергей Владимирович

доктор технических наук, доцент (ФКОУ ВПО «Воронежский институт ФСИН России», профессор кафедры управления информационно-технического обеспечения)

ФГБОУ ВПО «Воронежская государственная лесотехническая академия»

Ведущая организация:

Защита состоится «16» мая 2013 г. в 13 час. 30 мин. на заседании диссертационного совета Д 212.035.02 при ФГБОУ ВПО «Воронежский государственный университет инженерных технологий» по адресу: 394036, г. Воронеж, проспект Революции, д. 19 (конференц-зал).

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

Текст автореферата и объявление о защите размещены в сети интернет на сайте Минобрнауки РФ http://vak.ed.gov.ru «15» апреля 2013 года.

С диссертацией можно ознакомиться в научной библиотеке ФГБОУ ВПО ВГУИТ.

Автореферат разослан «16» апреля 2013 г.

Ученый секретарь диссертационного совета кандидат технических наук, доцент

И.А. Хаустов

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

Актуальность работы. В традиционном динамическом программировании (ДП) оптимальность понимается в смысле экстремального значения выбранного скалярного критерия. Многие практически важные задачи не удается свести к однокритериальной постановке, поэтому в последнее время вопросу обобщения метода ДП на многокритериальный, нечёткий и иные случаи уделяется большое внимание. Этой теме посвящены работы Д. И. Батищева, С. П. Вовк, В. А. Емеличева, С. С. Мазуренко, А. Г. Ченцова, В. А. Перепелицы, В. И. Струченкова и др. Однако наиболее общей трактовкой понятия оптимальности является понятие выбора, а самым универсальным и удобным для анализа языком его описания признана функция выбора (ФВ). Использование такого подхода к совершенствованию методов ДП позволит значительно расширить круг решаемых задач.

Диссертационная работа выполнена в соответствии с планом госбюджетных научно-исследовательских работ ВГУИТ по теме «Математическое и компьютерное моделирование в задачах проектирования и оптимизации функционирования информационных технологических систем» (ГК № 01.2006.06298), а также в рамках гранта ФЦП «Научные и научно-педагогические кадры инновационной России на 2009-2013 гг.» на тему «Разработка открытых информационных систем перерабатывающих производств» (ГК № П947).

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

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

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

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

3. Проверка адекватности разработанных моделей и эффективности предлагаемых методов.

4. Создание программных модулей, реализующих данные модели и методы.

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

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

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

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

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

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

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

Достоверность и полнота результатов исследований подтверждена их практической реализацией при оптимизации загрузки оборудования и персонала ООО Ринг Авто (акт внедрения от «01 » декабря 2012 года).

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на I Международной научно-практической интернет-конференции "Моделирование энергоинформационных процессов", Воронеж 2012; в рамках программы У.М.Н.И.К. на Региональной конференции "Инновационные технологии и материалы", Воронеж 2011; на III Международной научной конференции «Современные проблемы прикладной математики и математического моделирования», Воронеж 2009.

Публикации. По теме диссертации опубликовано 8 печатных работ, из них 4 - в изданиях, рекомендуемых ВАК РФ, и получено одно свидетельство о регистрации программы для ЭВМ.

Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 113 наименований. Основной текст изложен на 110 страницах без списка литературы. Работа содержит 14 таблиц, 17 рисунков. Приложения на двух страницах.

Личный вклад автора. Личный вклад автора заключается в постановке задач и их решении. Так, в работе [1] им разработана модель выбора, а так же доказана её корректность. В работах [2,4] автором поставлены задачи и предложены варианты их решения. После выбора одного из предложенных вариантов соавтором, автором доказаны необходимые теоремы и интерпретированы результаты. В работе [3] автором самостоятельно соединены в единый подход модели поэтапного принятия решений и механизм функций выбора. Полностью разработана и отлажена программа для ЭВМ [5]. В работах [6,8] автором сформулированы условия применения обобщенных методов, в [7] - предложена иерархическая структура задач ДП.

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

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

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

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

Пусть G = (F, E) - произвольный ориентированный граф, \ V\ = п, и Q - некоторое множество ориентированных маршрутов в нём. Введём в рассмотрение Г = 71(E, g)ç 2е \ 0 - семейство непустых подмножеств множества дуг графа G, такое, что VИеТ 3 qsQ: h с q. Иными словами, Т— это некоторое множество маршрутов из g и их фрагментов.

Пусть X сТ. Рассматривая каждый элемент реХ как допустимое альтернативное решение некоторой задачи выбора маршрутов, а X - как предъявление, введем ФВ С(Х), определяющую набор в некотором смысле лучших маршрутов и/или их фрагментов.

Определение 1. Назовем С-оптгшальными все решения из предъявления, попавшие в выбор.

Пусть s и t - две фиксированных вершины графа G. Определим Q как множество маршрутов, связывающих s vi t к рассмотрим задачу поиска С-оптимальных альтернатив на множестве Т, соответствующем введённому Q.

Определение 2. Пусть все маршруты из некоторого множества Y с Т имеют общую конечную вершину и, и ЬеТ- произвольный маршрут, начинающийся в и. Будем говорить, что ФВ обладает свойством слабой аддитивности, если для любого множества Y и любого маршрута Ъ, удовлетворяющих условиям, приведённым выше, справедливо равенство

C(Y&b)= С(У) & Ь.

Символ "&" означает "склеивание" или соединение маршрутов.

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

Модель 1 позволяет получить множество С-оптимальных маршрутов для бесконтурного орграфа:

Begin D(s) := 0; for у е Г"0?) do D(y) := {(s, у)}; for X = s + 1 to t do

/ \

D(x) := С

End.

iKW&Cy.*))

Здесь Г " (и) и Г +(м) - множества вершин, являющихся, соответственно, конечными для дуг (н, у) и начальными для дуг (V, г/); .V -начальная вершина искомых маршрутов.

Корректность процедуры определяет следующая теорема.

Теорема 1. Если ФВ С( ), определенная на множестве маршрутов и их всевозможных фрагментов в бесконтурном орграфе й = (V, Е), обладает свойствами наследования, отбрасывания и слабой аддитивности, то множество Б (х), полученное посредством реализации модели 1, совпадает с множеством С-оптимальных маршрутов из 5 в х, где х - произвольная вершина.

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

Пусть теперь имеем орграф общего вида, т.е. содержащий контуры. Предлагается следующая модель 2 поиска С-оптимальных путей в таком графе, представляющая собой обобщение алгоритма Форда-Беллмана:

Ве&п £>0) := 0; /огх е У\Ж) й(х) := /ог у е Г"(5) Оо £>0) := {(я,у)}; /ог к := 1 Го п - 2 Ыо

/огх е У \ {б} с1о

М;

£)(х):=С

и О(а-)

Еп<Л.

Здесь символом "оо" обозначена "бесконечно плохая" альтернатива, заведомо не попадающая в выбор.

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

Определение 3. Пусть X - произвольное множество маршрутов; IV - произвольный маршрут, содержащий контуры; -маршрут, полученный из исключением контуров. Будем говорить, что в графе С любой маршрут, содержащий контуры, заведомо хуже того же маршрута после исключения из него контуров, если для любых IV и X справедливо соотношение

л* еС(х и МIIМ).

Теорема 2. Пусть для ориентированного графа С = (У, Е), ¡У| = п, выполнены следующие условия.

1. Задана вершина уи множество Q маршрутов, содержащих л в качестве начальной вершины.

2. ФВ С(), определенная на множестве Т = Т(Е, 0, обладает свойствами наследования, отбрасывания и слабой аддитивности.

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

Тогда О (х), полученное посредством модели 2, совпадает с множеством С-оптимальных маршрутов из .у в х.

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

В третьей главе предложена модель многоэтапного выбора на основе бинарного отношения (БО), содержащего вербальные оценки альтернативных вариантов. Её использование позволит решить слабо структурированные задачи, часто возникающие в приложениях и не решаемые традиционным методом ДП. Данная модель получена посредством конкретизации абстрактной ФВ, свойства которой были обоснованы в теоремах 1 и 2.

В основе модели положено понятие составного объекта. Пусть имеем конечное множество элементов £/ = {щ, иг,-.-, щ), на котором заданы два БО:

- I - антисимметричное, полное и транзитивное БО, которое позволяет упорядочить члены любой последовательности элементов {и,} с и, так что отношение (г//, г/;)е I означает, что элемент г/, предшествует элементу и/,

- Р, определяющее предпочтение одного элемента перед другим; его свойства укажем ниже.

Будем производить попарное сравнение объектов, составленных из конечных наборов элементов множества С/, предполагая при этом, что выполняются следующие допущения.

1) Объекты состоят из конечного числа элементов, которые могут повторяться.

2) Порядок следования и частота чередования разных элементов не имеет значения при оценке объекта.

3) Короткий объект, т.е. состоящий из меньшего числа элементов, предпочтительнее более длинного, состоящего из таких же элементов.

4) Существует «пустой» элемент '0', для которого по определению выполняется условие

V и, е и ('0', и,) е Р, ('0', и,) е I. (1)

Поставим в соответствие каждому набору А = {хь д^,..., х1 е II отсортированный объект Ая = {х,( ,..., х^ } , состоящий из

тех же элементов, что и А, но при этом V от, 1 < т < к-1

Введём для отсортированных объектов следующее бинарное отношение Л*. Если два сравниваемых объекта и Я1 имеют одинаковое число элементов - к, т.е. Аь•= (о|, а2,..., щ), В = (Ь\, Ь2,..., Ьь), то положим по определению

(А Яч')е Л* О (V/= (о,. Ь)еР) л (А* (2)

Если же сравниваемые объекты А и

В" имеют разное число элементов, то более «короткий» из них дополним сначала «пустыми» элементами '0' с соблюдением (1) и далее их сравнение будем производить согласно (2).

Примем по определению для неотсортированных объектов

(А. В) е Л* <=(А5,В1!)еЛ*

Пусть теперь задан некоторый граф С = (V, Е). Для того чтобы применить построенное бинарное отношение Я* к задаче поиска оптимальных маршрутов в графе, предположим, что на рёбрах графа заданы два бинарных отношения. Первое позволяет упорядочить рёбра, второе - сравнить их между собой по предпочтению. Для этого введём некоторое множество С/ элементов {и,}, на котором заданы отношения I и Р, и установим сюръективное отображение /: Е -> и, так что два одинаковых по предпочтению ребра отображаются в один элемент. Иными словами, щ можно ассоциировать с именами классов рёбер графа. Тогда маршруты и их фрагменты (элементы множества Т\Е, ())) будем отождествлять с объектами, составленны-

ми из элементов {г//}, а пустое множество рёбер - с пустым элементом 'О'.

Для сравнения маршрутов из Т будем использовать БО Л**, определяемое соотношением:

V Р,деТ (р, д) е Я** » №,М) е Д*.

а в качестве правила выбора будем использовать механизм блокировки по Л**:

С(Х) = С*"(Х) = {хеХ| УуеХ (у,х)еЯ**}.

Определение 4. Пусть на множестве Т определено БО Я. Пусть х, у, де Г- произвольные маршруты, инцидентные одной вершине и, причём х и у имеют и в качестве концевой вершиной, а д — начальной. И пусть

(х,у)еЯ о (х&д, у&д)еЯ.

Тогда будем говорить, что Я обладает свойством инвариантности относительно добавления общего фрагмента.

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

Теорема 4. Отношение Я** транзитивно, асимметрично и инвариантно относительно добавления общего фрагмента.

Известно, что ФВ, порождённая транзитивным и асимметричным БО, обладает свойствами наследования и отбрасывания. Кроме того, согласно теоремам 3 и 4, ФВ, порождённая БО Я**, обладает свойством слабой аддитивности. В силу теорем 1 и 2 это означает, что ФВ, порожденную Л**, можно применять в обобщённой схеме ДП на основе моделей 1 и 2.

Соответствующий алгоритм выбора приведен на рис. 1.

Рис. 1. Алгоритм выбора из множествах на основе И**

Далее в третьей главе описывается метод сокращения МНА при использовании обобщённого ДП. Одной из проблем, присутствующей уже в скалярном ДП, является наличие траекторий с совпадающими оценками. В этом случае среди них оставляется первая по порядку альтернатива, а остальные исключаются. Такой подход может при сложных механизмах поэтапного выбора привести к утере хороших альтернатив. Поэтому для обоснованного сокращения МНА вводится понятие лексикографии бинарных отношений, когда некоторое БО Я, порождающее ФВ, модифицируется по следующей формуле:

^ = йи(/пХ) = Ьех(Я, 5), (3)

где I - отношение эквивалентности на множестве альтернатив, отрицающее наличие БО /? в паре (х, у) (для скалярного случая х!у означает совпадение значений критериев решений х и у)', 5 - некоторое новое БО, введённое для ужесточения выбора.

Необходимые свойства отношения (3) определяются следующей теоремой.

Теорема 5. При следующих условиях БО Л и (/ п 5) анти-рефлексивно и транзитивно:

1°. $ антирефлексивно и транзитивно.

2°. Выполняется хотя бы одно из условий:

- Я транзитивно относительно / или 5;

- оба отношения I и Б транзитивны относительно К.

Для однозначности выбора, т.е. чтобы построенная ФВ позволяла из каждого класса эквивалентных решений выбирать единственного представителя, БО Я4 должно быть слабо полным на каждом классе эквивалентности. Иными словами,

Ух, уеА ((х,у)е/лх^у) => ((х,у)е V (у,х)е /Г* ).

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

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

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

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

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

Рис. 2. Граф задачи об оптимальной загрузке

Сравнение альтернатив сводится к получению количества исполнителей каждого разряда. Так, путь из вершины 5 в вершину 9 возможен по траектории 5-7-9 или 5-8-9, которые имеют по одному исполнителю 3-го - высшего разряда, но при этом первая альтернатива содержит исполнителя второй категории, а вторая — низшей. Следовательно, предпочтительнее первая траектория. В случае, когда по разрядности траектории идентичны (как например, 0-1-4 и 0-2-4) сравниваем суммарный стаж исполнителей (2322 и 2081 соответственно). В этом случае траектория 0-1-4 предпочтительнее.

В итоге получаем путь 0-1-4-6-9. Однозначность выбора определяется наличием вторичного признака - стажа.

Для апробации представленных моделей и алгоритмов разработан программный продукт, генерирующий заданный граф и вычисляющий оценки оптимальных путей по модели 2 как с использованием лексикографии бинарных отношений (LEX), так и без неё. Проводилось определение времени расчета графа в секундах в зависимости от числа его вершин и длины шкалы - количества качественных классов, к которым можно отнести ребра графа. При расчетах использовалась ПЭВМ с ЦП AMD Turion II М520 2,3 ГГц, ОЗУ 3 Гб. Результаты вычислительных экспериментов приведены на рис. 3.

150 -

100

50 -

о -

10

300

500

750 1000

■«•»»Длина шкалы 10 пунктов

Длина шкалы 30 пунктов

«■».'с—Длина шкалы 10 пунктов (с LEX) —Длина шкалы 30 пунктов (с LEX)

Рис. 3. Результаты вычислительных экспериментов

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

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

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

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

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ

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

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

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

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

Публикации в изданиях, рекомендованных ВАК РФ

1. Бугаев Ю.В. Механизм выбора вариантов при заданных отношениях для компонент объектов сравнения / Ю.В. Бугаев, И.Е. Медведкова, C.B. Чикунов, Ф.А. Музалевский // Вестник ВГУИТ, серия: информационные технологии, моделирование и управление 2012. - № 3(53). _ Воронеж, 2012. - С. 70-74.

2. Бугаев Ю. В. Многокритериальный поэтапный выбор: алгоритмический подход / Ю. В. Бугаев, С. В. Чикунов, Ф. А. Музалевский // Вестник ВГТА, серия: информационные технологии, моделирование и управление 2011. - № 2 (48). - Воронеж, 2011. - С. 21-24.

3. Бугаев Ю. В. Обобщение схемы динамического программирования на основании лексикографии бинарных отношений / Ф. А. Музалевский, Ю. В. Бугаев И Вестник ТГТУ. Тамбов, 2012. -Т. 18,№2.-С. 333-344.

4. Бугаев Ю. В. Решение задач маршрутизации распределенных вычислительных сетей / Ю. В. Бугаев, С. В. Чикунов, Ф. А. Музалевский // Вестник ВГТА. Серия: информационные технологии, моделирование и управление. - 2010. - № 2 (44). - Воронеж, 2010. -С. 81-84.

Статьи и материалы конференций

5. Программа для ЭВМ «Расчет оптимального пути в графе на основе вектора критериев при сравнении полных путей». Свидетельство о регистрации № 2012616635 от 24 июля 2012 г.

6. Бугаев Ю. В. Некритериальное динамическое программирование (Тезисы) / Ю. В. Бугаев, С. В. Чикунов, Ф. А. Музалевский //Современные проблемы прикладной математики и математического моделирования. Материалы III Международной научной конференции. Воронеж 2009. Ч. 2. С. 52-53.

7. Бугаев Ю.В. Динамическое программирование/ Ю. В. Бугаев, С. В. Чикунов, Ф. А. Музалевский // Международная научно-практическая интернет-конференция "Моделирование энергоинформационных процессов". Воронеж 2012. С. 100-102.

8. Бугаев Ю.В. Некритериальная оптимизация при поэтапном выборе/ Ю.В. Бугаев, Ф.А. Музалевский // «Информационные технологии. Автоматизация. Актуализация и решение проблем подготовки высококвалифицированных кадров (ИТАП-2012)»: международная научно-практическая конференция, сборник трудов. Набережные Челны 2012. - С. 23-26.

Подписано в печать 15.04.2013. Формат 60 х 84/16. Усл. печ л. 1,0. Тираж 100 экз. Заказ №65 ФГЮУ ВПО «Воронежский государственный университет инженерных технологий» (ФГБОУВПО«ВГУИГ») Отдел оперативной полиграфии ФГБОУ ВПО «ВГУИТ» Адрес университета и отдела оперативной полиграфии: 394036, Воронеж, пр. Революции, 19.

4.5. Вычислительные эксперименты.................................................................112

4.6. Выводы по главе....................,......................................................................113

ЗАКЛЮЧЕНИЕ...................................................................................................114

СПИСОК ЛИТЕРАТУРЫ..................................................................................115

ции программы для ЭВМ.

Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 113 наименований. Основной текст изложен на 110 страницах без списка литературы. Работа содержит 14 таблиц, 17 рисунков. Приложения на двух страницах.

Изменим условия задачи, положив, что участок категории / в маршруте А имеет длину 23 км, а остальные данные не изменились. Казалось бы, от этого маршрут А только улучшится, однако легко заметить, что он удлинился, что, разумеется, не приветствуется.

Будем считать, что при прочих равных условиях более короткая дорога предпочтительней. Рассмотрим первые 2] км пути. Эти отрезки эквивалентны у обоих маршрутов. Следующие 25 км лучше в маршруте А, т.к. этот его участок содержит 2 км дороги категории /, в маршруте же В он целиком состоит из дороги категории II. Следующие 3 км будут лучше на маршруте А, т.к. состоят из дороги категории II против категории III в маршруте В. И рассмотрим конечные участки обоих маршрутов. Они состоят из дороги с покрытием категории III, но в маршруте В этот отрезок пути на 1 км короче, а значит - предпочтительнее. Следовательно, при новых данных отдать предпочтение нельзя ни одному маршруту.

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

1) Объекты сравнения состоят из конечного числа элементов, которые могут повторяться.

2) Порядок следования и частота чередования элементов разного типа не имеет значения при оценке объекта - так, объект (а, Ь, с) эквивалентен объектам (с, а, b), (а, с, Ь) и т.д.

3) Короткий объект, т.е. состоящий из меньшего числа элементов, предпочтительнее более длинного, состоящего из таких же элементов: (Ь, Ь, b) лучше, чем (b, b, b, b).

Итак, пусть имеем конечное множество элементов U = {и/, г<2,-.-, и/ч}, на котором задано БО Р, определяющее предпочтение одного элемента перед

ми от (п , 2п + п - 1) до (2" + п - 1, п). Это значит, что мощность ПМА равна 2".

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

Щ) = (Лк+ 1 )5-(¿к)5.

Для простоты анализа заменим Ь(к) её асимптотической оценкой

Ь(к) ~ ОЩМ)*'1). При модификации ПМА для вершины х используем формулу

(3.11)

£>(*) := С

};еГ' (х)

и £>(*)

В многодольном графе с не более чем т вершинами в слое мощность Г +(х), очевидно, не более т. Следовательно, мощность анализируемого множества

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

на каждую вершину. Эту величину надо умножить на число вершин в слое -т и просуммировать по всем к от 1 до п. Общая вычислительная сложность не более

т2(3.12) При 5 = 1 получим 0(п-т2). Такой же результат получим при анализе скалярного алгоритма. Следовательно, оценка (3.12) не является завышенной, улучшить её нельзя.

должны обладать параметры модели для её применения в методе ДП, а также для получения единственного решения.

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