«ПОТОКОВЫЕ МЕТОДЫ РЕШЕНИЯ МНОГОИНДЕКСНЫХ ЗАДАЧ ТРАНСПОРТНОГО ТИПА ...»

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

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

им. Н.И. ЛОБАЧЕВСКОГО

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

Афраймович Лев Григорьевич

ПОТОКОВЫЕ МЕТОДЫ РЕШЕНИЯ

МНОГОИНДЕКСНЫХ ЗАДАЧ ТРАНСПОРТНОГО ТИПА

Специальность: 01.01.09 Дискретная математика и математическая кибернетика Диссертация на соискание ученой степени доктора физико-математических наук

Научный консультант:

доктор технических наук, профессор Прилуцкий М.Х.

Нижний Новгород Содержание Введение

Глава 1. Многоиндексные задачи распределения ресурсов

1.1. Транспортная задача с промежуточными пунктами

1.2. Задача формирования портфеля заказов

1.3. Объемно-календарное планирование переработки газового конденсата

1.4. Задача составления расписания занятий

Глава 2. Методы исследования транспортных задач

2.1. Поток в сети с двусторонними ограничениями

2.2. Поток в древовидной транспортной сети

2.3. Поток в несовместной транспортной сети

2.4. Циклическая декомпозиция потока

2.5. Метод ортогональных проекций при решении транспортных систем

2.6. Многокритериальные транспортные задачи

Глава 3. Многоиндексные задачи транспортного типа

3.1. Постановки многоиндексных задач транспортного типа

3.2. Задачи распределения ресурсов как многоиндексные задачи

3.3. Общая концепция сводимости многоиндексных задач

Глава 4. Сводимость с сохранением соответствия ребер

4.1. Концепция t1 | t 2 equal | t3 edge сводимости

4.2. Многоиндексные задачи с 2-вложенной структурой

4.3. Многоиндексные задачи с 1-вложенной структурой

4.4. Условия t1 | t2 Z | t3 Z сводимости

Глава 5. Сводимость с сохранением соответствия циклов

5.1. Концепция t1 | t2 equal | t3 cycle сводимости

5.2. Многоиндексные задачи с декомпозиционной структурой

5.3. Декомпозиционные NP-трудные многоиндексные задачи

Заключение

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

Приложения

Приложение 1

Приложение 2

Приложение 3

Приложение 4

Приложение 5

Приложение 6

Приложение 7

Приложение 8

Введение многоиндексных задач (целочисленного) линейного программирования транспортного типа. Примерами таких задач являются задачи распределения ресурсов в иерархических системах: задача объемно-календарного планирования, задача формирования портфеля заказов, задача переработки газового конденсата, задача распределения мощностей каналов передачи данных, транспортная задача с промежуточными пунктами и др. [27, 28, 29, 32, 65, 83, 84, 85]. Многоиндексные задачи транспортного типа возникают также в области статистики и в смежной области защиты статистических данных [138, 140, 142, 168], в задаче целочисленного сбалансирования многоиндексных матриц [94, 95, 101].

Многоиндексные задачи о назначениях (подкласс многоиндексных транспортных задач целочисленного линейного программирования) возникают в теории расписаний при планировании изготовления скоропортящейся продукции, при планировании прохождения практики студентами, при планировании учебы клинических ординаторов по отделениям, при составлении расписания занятий, при планировании спортивных матчей и др. [118, 123, 132, 145, 147, 154, 164]; в области технического анализа данных при сопровождении объектов в многосенсорных системах [175, 176, 184]; в военной области при назначении военной техники на цели [116, 162]. Известны результаты, посвященные исследованию вопросов сводимости задач линейного и целочисленного линейного программирования к многоиндексным транспортным задачам [136, 137], что также расширяет область применения методов решения многоиндексных задач.

Многоиндексные задачи линейного программирования транспортного типа относятся к классу задач линейного программирования, который согласно [108] является полиномиально разрешимым. Таким образом, для решения многоиндексных задач линейного программирования транспортного типа могут быть применены общие методы исследований задач линейного программирования – симплекс метод [133], алгоритм Кармаркара [158]. Выделим также следующие работы, посвященные алгоритмам решения задач линейного программирования, [39, 41, 47, 50, 61, 62, 81, 160, 166]. Существует ряд работ, посвященных непосредственно методам решения многоиндексных задач линейного программирования транспортного типа. Наиболее изученным является класс двухиндексных задач [43, 48]. В многоиндексном случае (число индексов не менее трех) наибольшее внимание уделено двум классам задач: многоиндексные аксиальные задачи и многоиндексные планарные задачи. Вопросы исследования совместности и построения алгоритмов решения данных задач обсуждаются в [49, 57, 67, 93, 121, 177, 186]. В общей многоиндексных задач рассматривается в [93]. Условия, при которых удается понизить размерность и (или) сократить количество индексов многоиндексных транспортных задач, обсуждаются в [42, 157]. Геометрические свойства множества допустимых решений многоиндексных транспортных задач обсуждаются в [57, 58, 68, 135]. Вопросы оценки числа нецелочисленных вершин многогранника многоиндексных транспортных задач рассматриваются в [66, 70–72]. В ряде работ исследуются многоиндексные задачи транспортного типа с нелинейными критериями [96, 97, 103, 124, 139, 183], в том числе с минимаксными [79, 80, 141, 152, 161, 185] и c квадратичными [73, 99, 125, 126, 130] критериями. Многокритериальные многоиндексные задачи транспортного типа обсуждаются в [55, 77, 78, 83, 84, 90–92]. Игровые постановки, связанные с многоиндексными транспортными задачами, рассматриваются в [75, 148, 178].

Особый интерес представляет решение многоиндексных задач целочисленного линейного программирования транспортного типа, относящихся к классу задач целочисленного линейного программирования [102]. В общей постановке класс целочисленных многоиндексных транспортных задач является NP-трудным уже в трехиндексном случае [52]. Более того, для задач данного класса не существует полиномиальных -приближенных алгоритмов, иначе P=NP, данный результат также справедлив уже в трехиндексном случае [131]. Класс целочисленных многоиндексных задач, как подкласс задач целочисленного линейного программирования, содержит ряд известных полиномиально разрешимых подклассов: задачи, матрица систем ограничений которых является абсолютно унимодулярной [51], задачи с фиксированным числом переменных [144, 163], задачи N-кратного целочисленного программирования [134].

Приведем далее примеры соответствующих полиномиально разрешимых классов целочисленных многоиндексных задач. Как хорошо известно, матрица системы ограничений двухиндексной транспортной задачи является абсолютно унимодулярной, и тем самым класс двухиндексных задач целочисленного линейного программирования транспортного типа разрешим за полиномиальное время [43]. Класс многоиндексных задач целочисленного линейного программирования с фиксированным количеством индексов, каждый из которых принимает фиксированное количество значений, является полиномильно разрешимым согласно [163]. Примером полиномиально разрешимого трехиндексных планарных задач, в котором два из трех индексов принимают фиксированное количество значений [134]. При отсутствии дополнительных ограничений на параметры для решения многоиндексных задач целочисленного линейного программирования транспортного типа применимы лишь экспоненциальные по верхней оценке вычислительной сложности общие методы целочисленного линейного программирования, например, метод динамического программирования, метод ветвей и границ, метод отсечения Гомори [100, 102, 105].

Среди целочисленных многоиндексных транспортных задач наиболее изученным является класс многоиндексных задач о назначениях. Обзор результатов, связанных с анализом вычислительной сложности и построением приближенных алгоритмов решения специальных подклассов многоиндексных задач о назначениях приведен в [126, 174, 182].

Особое внимание уделяется двум классам многоиндексных задач о назначениях: класс Многоиндексные аксиальные задачи о назначениях рассматриваются, например, в работах [45, 46, 119, 120, 127, 128, 131], планарные в [44, 56, 69, 98, 146, 167].

Одним из перспективных направлений при разработке эффективных алгоритмов исследования многоиндексных задач линейного программирования является нахождение подклассов задач, для решения которых применимы потоковые методы. Важное влияние на развитие данного направления оказывают активные исследования в области сетевой оптимизации [1, 38, 53, 54, 63, 76, 104, 106, 107, 115, 122, 143, 149, 151, 169, 172, 173, 180].

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

Рассматриваемая в диссертационной работе проблема сводимости многоиндексных транспортных задач линейного программирования к потоковым задачам является менее исследованной. Ранее было известно о сводимости двухиндексных задач к задаче поиска потока в сети [43]. Вопрос сводимости многоиндексных задач с произвольным числом индексов и произвольными многоиндексными подсуммами системы ограничений впервые рассматривался в работах [8, 9, 20, 22, 25, 28, 32], которые легли в основу диссертационной работы.

Из ученых существенный вклад в развитие рассматриваемого в диссертационной работе класса многоиндексных задач внесли Гимади Э.Х., Гольштейн Е.Г., Емеличев В.А., Канторович Л.В., Кириченко И.О., Кравцов М.К., Прилуцкий М.Х., Раскин Л.Г., Сергеев С.И., Сигал И.Х., Цурков В.И., Юдин Д.Б., Burkard R.E., Danzig G.L., De Loera J., Koopmans T.C., Onn S., Spieksma F.C.R. и др. Существенный вклад в развитие методов сетевой оптимизации, применяемых в работе при исследовании многоиндексных задач, внесли Диниц Е.А., Карзанов А.В., Новикова Н.М., Edmonds J., Ford L.R., Fulkerson D.R., Goldberg A.V., Karp R.M., Orlin J.B., Rao S., Skutella M., Tardos E., Tarjan R. E. и др.

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

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

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

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

Научная новизна 1. Формализованы схемы сведения задач линейного программирования к классу задач поиска потока в сети. В рамках построенных схем сведения исследованы вопросы сводимости многоиндексных задач транспортного типа к классу задач поиска потока в сети.

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

– установлен критерий сводимости многоиндексных задач;

– на основе критерия сводимости выделен класс сводимых многоиндексных задач – класс многоиндексных задач с 2-вложенной структурой, возникающий в ряде прикладных задач;

– предложена конструктивная схема сведения класса многоиндексных задач с 2вложенной структурой являющаяся оптимальной (сведение с асимптотически меньшими вычислительными затратами невозможно, любое увеличение вычислительных затрат на сведение не приводит к расширению класса сводимых многоиндексных задач);

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

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

– установлен критерий сводимости многоиндексных задач;

– на основе критерия сводимости выделен класс сводимых многоиндексных задач – класс многоиндексных задач с 1-вложенной структурой, возникающий в ряде прикладных задач;

– предложена конструктивная схема сведения класса многоиндексных задач с 1вложенной структурой также являющаяся оптимальной;

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

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

5. В рамках схемы сведения с сохранением соответствия циклов исследованы вопросы сводимости к классу задач поиска потока в сети:

– найдено достаточное условие сводимости многоиндексных задач;

– на основе условия сводимости выделен класс сводимых многоиндексных задач – класс многоиндексных задач с декомпозиционной структурой, возникающий в ряде прикладных задач;

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

– выделен новый полиномиально разрешимый подкласс в NP-трудном классе целочисленных многоиндексных задач;

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

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

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

Предложенные в диссертационной работе методы исследования многоиндексных задач транспортного типа были использованы при разработке следующих программных систем: программное обеспечение «Заказ-О», программное обеспечение «Нагнетатель», программное обеспечение «Проектировщик-1», программное обеспечение «Проектировщик-2», заказчик ФГУП «РФЯЦ-ВНИИЭФ», г. Саров; «Модуль расчета оптимального плана производства для диалоговой системы объемно-календарного планирования производственных мощностей, функционирующей на предприятии», заказчик ОАО «ОКБМ Африкантов», г. Нижний Новгород; программная система ПО «Кристалл», заказчик ФГУП «ФНПЦ НИИИС им. Ю.Е. Седакова», г. Нижний Новгород, (см. приложения 1-7).

Проведенные исследования выполнены в рамках заданий Минобразования РФ номер госрегистрации 0120.0506816, тема НИР «Математическое моделирование и создание новых методов анализа динамических систем и систем оптимизации », номер госрегистрации 01.2.00 1 07703, тема НИР «Математическое моделирование и создание новых методов анализа динамических систем и систем оптимизации», номер госрегистрации 01201252499, тема НИР «Математическое моделирование и создание новых методов анализа эволюционных систем и систем оптимизации»; гранта Президента Российской Федерации для государственной поддержки молодых российских ученых кандидатов наук, МК-3473.2010.1, тема «Быстрые алгоритмы решения задач глобальной оптимизации и их приложения»; ФЦП при финансовой поддержке Минобрнауки России, гос. соглашение 14.B37.21.0878., тема «Высокоточные супервычисления и решение задач глобальной оптимизации на основе информационного подхода».

Нижегородского государственного университета им. Н.И. Лобачевского на факультете ВМК при преподавании курсов «Моделирование сложных систем», «Модели и методы эффективного использования распределенных вычислительных систем» и спецсеминара магистров кафедры ИАНИ [21, 26, 31] (см. приложение 8).

Апробация результатов Полученные в диссертационной работе результаты обсуждались на Всероссийской конференции КоГраф (Н.Новгород, 2002 г.); Международных научно-практических семинарах «Высокопроизводительные параллельные вычисления на кластерных системах» (Н.Новгород, 2002, 2003 г.); Нижегородских сессиях молодых ученых (Саров, 2003 г., 2004 г., Нижний Новгород, 2004 г.); Научно-технической конференции ООО ТЕКОМ «Технические, программные и математические аспекты управления сложными распределенными системами» (Н.Новгород, 2003 г.); Юбилейной научно-технической конференции ВМК ННГУ и НИИ ПМК, «Математика и кибернетика 2003» (Н.Новгород, 2003 г.); VI международном конгрессе по математическому моделированию (Н.Новгород, 2004 г.); Конференциях «Технологии Microsoft в теории и практике программирования»

(Москва, 2005 г., Н.Новгород, 2006 г., 2007 г., 2009 г.); Международной научной конференции, приуроченной к 200-летию со дня рождения Карла Густава Якоби (Калининград, 2005 г.); XIV, XV, XVI Международных конференциях «Проблемы теоретической кибернетики» (Пенза, 2005 г., Казань 2008 г., Нижний Новгород 2011 г.); V, VI Московских международных конференциях по исследованию операций (Москва 2007 г., 2010 г.); Международной научной конференции «Параллельные вычислительные Международном семинаре «Дискретная математика и ее приложения» (Москва, 2010 г.), Одесском семинаре по дискретной математике (Одесса, 2011 г.).

Результаты работы также обсуждались на научных семинарах отделения информатики университета г. Падерборна (Германия, г. Падерборн, 2005 г., 2007 г., информатики и автоматизации научных исследований факультета Вычислительной математики и кибернетики Нижегородского государственного университета им. Н.И.

Лобачевского (2006 г., 2011 г., 2013 г., руководитель семинара профессор Прилуцкий М.Х.), научном семинаре Кафедры исследования операций Математико-механического факультета Санкт-Петербургского государственного университета (2012 г., руководитель семинара профессор Романовский И.В.), научном семинаре центра исследования операций и бизнес статистики университета г. Левен (Бельгия, г. Левен, 2012 г., руководитель семинара профессор Spieksma F.C.R.), научном семинаре Вычислительного центра имени А.А. Дородницына Российской академии наук (2012 г., руководитель семинара академик Евтушенко Ю.Г.).

Основные результаты, полученные в ходе выполнения диссертационной работы, отражены в 41 научной работе [2–20, 22–25, 27–30, 32–37, 86–90, 110–112], в том числе в 11 статьях, опубликованных в ведущих рецензируемых научных журналах (Автоматика и телемеханика, Известия РАН. Теория и системы управления, Управление большими системами, Вестник Нижегородского университета им. Н.И. Лобачевского) из списка, рекомендованного ВАК [8, 9, 13, 20, 22, 25, 27, 28, 29, 30, 90], а также в 3 учебнометодических работах [21, 26, 31].

самостоятельно.

Структура и содержание работы

Работа состоит из введения, пяти глав, заключения, списка литературы и приложения.

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

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

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

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

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

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

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

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

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

Глава 1. Многоиндексные задачи распределения ресурсов Широкий класс прикладных задач распределения ресурсов относится к классу многоиндексных задач транспортного типа [24, 27–29, 32, 35–37, 65, 83, 84]. В главе приводятся содержательные постановки подобных прикладных задач и строятся их математические модели. Далее в главе 3 будет определена общая схема формализации многоиндексных задач и определено соответствие между рассмотренными прикладными задачами и классами многоиндексных задач транспортного типа. Полученные в главах 4 и 5 теоретические результаты сводимости многоиндексных задач к классу задач поиска потока в сети также будут проиллюстрированы на примере приведенных в данной главе прикладных задач.

1.1. Транспортная задача с промежуточными пунктами Содержательная постановка Имеются пункты производства, промежуточные пункты и пункты потребления однородного продукта. Заданы максимально возможные объемы производства продукта каждым пунктом производства, минимально допустимые объемы потребления продукции каждым пунктом потребления, ограничения на объемы перевозки продукта от каждого пункта производства до каждого промежуточного пункта, ограничения на объемы перевозки продукта от каждого промежуточного пункта до каждого пункта потребления.

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

Исходные параметры Пусть I – множество пунктов производства, J – множество промежуточных пунктов, K – множество пунктов потребления. Обозначим через Ai максимальный объем производства продукта пунктом производства i; Bk – минимально допустимый объем продукта, который необходимо доставить в пункт потребления k; C ij - максимальное количество продукта, которое может быть доставлено из пункта производства i в пункт потребления k; D jk - максимальный объем продукта, который может быть доставлен из промежуточного пункта j в пункт потребления k, iI, jJ, kK.

Варьируемые параметры Обозначим через xijk количество продукта, которое будет перевезено из пункта производства i через промежуточный пункт j в пункт потребления k, iI, jJ, kK.

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

jJ kK (объем производства продукта пунктом производства не должен превышать максимально возможного объема);

iI jJ (пункт потребления должен получить объем продукта не ниже минимально допустимого объема);

(объем перевозки продукта от пункта производства до промежуточного пункта не должен превышать максимально допустимого объема);

(объем перевозки продукта от промежуточного пункта до пункта потребления не должен превышать максимально допустимого объема);

(естественные ограничения на переменные).

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

Рассмотрим стоимостные показатели плана. Обозначим через себестоимость производства единицы продукции пунктом производства i; bk – цену реализации единицы продукции пункту потребления k; cij – стоимость доставки единицы продукции из пункта производства i в промежуточный пункт j; d jk – стоимость доставки единицы продукции из промежуточного пункта j в пункт потребления k. Задача минимизации расхода заключается в определении такого плана перевозок xijk, iI, jJ, kK, для которого выполняются ограничения (1.1)-(1.5), и принимает оптимальное значение критерий iI jJ kK Задача максимизации дохода заключается в определении такого плана перевозок xijk, iI, jJ, kK, для которого выполняются ограничения (1.1)-(1.5), и принимает оптимальное значение критерий iI jJ kK Задача максимизации прибыли заключается в определении такого плана перевозок xijk, iI, jJ, kK, для которого выполняются ограничения (1.1)-(1.5), и принимает оптимальное значение критерий iI jJ kK В качестве показателей плана могу быть рассмотрены показатели, основанные на контролируемыми элементами системы являются пункты потребления. С каждым из определяющую предпочтение потребителя k относительно объема потребляемого им свои предпочтения относительно каждого из возможного объема потребленного ими продукта. Такие предпочтения обычно задаются путем ранжирования интервалов соответствующих объемов продукта. Формализация такого рода предпочтений связана с определением конечной вложенной последовательности интервалов соответствующих объемов продукта. Пусть каждый из потребителей задает p+1 вложенных интервалов [ Bkl, Bkl ], l 0, p, k K. Вложенность интервалов означает выполнение следующих условий [ Bkl, Bkl ] [ Bkl 1, Bkl 1 ], l 0, p 1, k K. Так интервал [ Bk 0, Bk 0 ] является наиболее предпочтительным для потребителя k, интервал [ Bk1, Bk1 ] менее предпочтителен и т.д.

следующего вида:

где u R, k K. Тогда задача выбора наиболее предпочтительного плана перевозок определить план перевозок xijk, iI, jJ, kK, для которого выполняются ограничения (1.1)-(1.5) и принимают оптимальные значения критерии, определяющие предпочтения пунктов потребления:

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

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

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

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

Исходные параметры Пусть I – множество подразделений предприятия, J – множество заказов, T {1,2,..., p} – множество номеров тактов планирования. Обозначим через Ai и Ai минимально допустимый и максимально возможный объем работ, который подразделение i способно выполнить в течение всего периода планирования; Bit и Bit – минимально допустимый и максимально возможный объем работ, который подразделение i способно выполнить в такт планирования t ; C и C – минимально возможный и максимально требуемый объем работ по заказу j; t и t – минимально раннее время начала выполнения работ и максимально позднее время окончания выполнения работ по заказу j, iI, jJ, tT.

Варьируемые параметры Обозначим через xijt объем работ, выполненный подразделением i по заказу j в такт планирования t, iI, jJ, tT.

Ограничения математической модели Допустимым портфелем заказов будем называть набор значений xijt, iI, jJ, tT, удовлетворяющий следующей системе ограничений:

(объем работ, выполненный подразделением в течение всего периода планирования, должен удовлетворять заданным двусторонним ограничениям);

(объем работ, выполненный подразделением в течение такта планирования, должен удовлетворять заданным двусторонним ограничениям);

(объем выполненных работ по заказу должен удовлетворять заданным двусторонним ограничениям);

(работы по заказу могут выполняться лишь в течение заданного периода);

(естественные ограничения на переменные).

Критерий оптимальности Пусть система (1.10)-(1.14) несовместна. Несовместность может быть вызвана несогласованностью внутренних ограничений предприятия. Вопрос о несогласованности (1.10),(1.11),(1.14). В общем случае несовместность обусловлена тем, что ограниченные мощности предприятия не позволяют выполнить требуемые работы по поступившим заказам в заданные сроки.

Разобьем ограничения на «жесткие» и «желательные» и будем рассматривать задачу определения плана выполнения работ, удовлетворяющего жестким ограничениям и минимизирующего штрафы за нарушения желательных ограничений. Далее рассмотрим две задачи: задачу с возможными нарушениями требуемых объемов работ по заказам (соответствует случаю, когда ограничение (1.12) является желательным) и задачу с возможными нарушениями сроков выполнения работ по заказам (соответствует случаю, когда ограничение (1.13) является желательным).

Рассмотрим задачу формирования портфеля заказов с возможными нарушениями требуемых объемов работ по заказам. Обозначим через c и c штрафы за нарушение на единицу минимально возможного и максимально требуемого объем работ по заказу j ; y и y – искомые величины, на которые будут нарушены нижняя и верхняя границы объема работ по заказу j, j J. Введем дополнительные ограничения (объем выполненных работ по заказу с учетом возможных нарушений должен удовлетворять заданным двусторонним ограничениям);

(естественные ограничения на переменные). Тогда задача формирования портфеля заказов с возможными нарушениями требуемых объемов работ по заказам заключается в определении величин xijk, iI, jJ, kK и y, y, j J, удовлетворяющих системе ограничений (1.10),(1.11),(1.13)–(1.16) и минимизирующих суммарный штраф за нарушение требуемых объемов работ Рассмотрим задачу формирования портфеля заказов с возможными нарушениями сроков выполнения работ по заказам. Обозначим через d и d штраф за нарушение начального и конечного сроков выполнения работ на один такт, на одну единицу объема.

Тогда задача заключается в определении величин xijk, iI, jJ, kK и y, y, j J, суммарный штраф за нарушение сроков выполнения работ Замечание. Предложенная задача формирования портфеля заказов может быть использована руководством предприятий при заключении договоров с заказчиками на начальном этапе планирования, когда еще не определены детальные планы выполнения заказов, и планируемые работы оцениваются лишь в объемных показателях. На данном этапе возникает предложенная задача формирования портфеля заказов, которая заключается в согласовании (во времени) требуемых объемов работ по заказам с обязательств) не может в заданные сроки выполнить требуемые объемы работ по заказам, ставится задача поиска компромиссного решения.

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

– емкости резервуарного парка, – технологические установки, – потребители продукции.

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

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

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

Исходные параметры Пусть I – множество емкостей под сырье, J – множество технологических установок, K – множество различных видов готовой продукции, выпускаемой предприятием, P – множество потребителей готовой продукции, T – множество тактов планирования. Обозначим через Ai максимальную вместимость емкости i; B и B jk jk минимальная и максимальная производительность технологической установки j по продукции k; C ptk и C ptk – минимально возможный и максимально требуемый для потребителя p в такт t объемы продукта k, iI, jJ, kK, pP, tT.

Варьируемые параметры Обозначим через xijkpt объем сырья, который из емкости i поступит на установку j для изготовления продукта k, который будет отправлен потребителю p в такт t, iI, jJ, kK, pP, tT.

Ограничения математической модели Общая математическая модель объемно-календарного планирования процесса переработки газового конденсата представляет собой следующую систему ограничений:

jJ k K pP tT (объем сырья помещенные в емкость не должен превышать ее вместимости);

(в каждый из тактов времени объем производимой продукции должен удовлетворять ограничениям на производительность установки);

(объем каждого из видов продукции, получаемый потребителями в каждый из тактов времени, должен удовлетворять заданным двусторонним ограничениям);

(естественные ограничения на переменные).

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

akpt – ожидаемый доход от реализации единицы продукции k потребителю p в такт t; b jk – затраты технологической установки j на переработку единицы сырья в продукцию k; cij – затраты на перемещения единицы сырья из емкости i в технологическую установку j; d t – ожидаемая стоимость сырья в такт t; ekp – затраты на доставку единицы готовой продукции k потребителю p, iI, jJ, kK, pP, tT.

Тогда задача максимизации суммарного дохода предприятия от реализации продукции заключается в определении такого плана xijkpt, iI, jJ, kK, pP, tT, для которого выполняются ограничения (1.19)-(1.22) и принимает оптимальное значение критерий Задача минимизации суммарных затрат технологических установок на переработку сырья в готовую продукцию заключается в определении такого плана xijkpt, iI, jJ, kK, pP, tT, для которого выполняются ограничения (1.19)-(1.22) и принимает оптимальное значение критерий Задача минимизации суммарных затрат на перемещение сырья из емкостей в технологические установки заключается в определении такого плана xijkpt, iI, jJ, kK, pP, tT, для которого выполняются ограничения (1.19)-(1.22) и принимает оптимальное значение критерий Задача минимизации суммарных затрат на закупку предприятием сырья заключается в определении такого плана xijkpt, iI, jJ, kK, pP, tT, для которого выполняются ограничения (1.19)-(1.22) и принимает оптимальное значение критерий Задача минимизации суммарных затрат на доставку предприятием готовой продукции потребителям заключается в определении такого плана xijkpt, iI, jJ, kK, pP, tT, для которого выполняются ограничения (1.19)-(1.22) и принимает оптимальное значение критерий Задача максимизации суммарной прибыли предприятия заключается в определении такого плана xijkpt, iI, jJ, kK, pP, tT, для которого выполняются ограничения (1.19)-(1.22) и принимает оптимальное значение критерий iI jJ kK pP tT Замечание. Предложенная постановка задачи планирования переработки газового планирования, когда требуется согласовать обобщенные мощности предприятия с требованиями потребителей. При этом производительности установок, определяющие функционирования. Установка устроена таким образом, что при выбранном режиме ее работы известны интервальные границы по каждому из видов готовой продукции на выходе установки, что определяет комплексную природу работы таких установок.

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

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

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

максимизирующее суммарные предпочтения.

Исходные параметры Пусть I – множество преподавателей, J – множество занятий, K – множество аудиторий, T – множество непересекающихся интервалов времени, в которые занятия могут проходить. Обозначим через Ai – множество занятий, которые могут быть проведены преподавателем i, Ai J ; Bi – множество интервалов времени, в которые преподаватель i может провести занятия, Bi T ; Ck – множество интервалов времени, в течение которых аудитория k доступна, Ck T, iI, jJ, kK. Предпочтения будем связывать с весовыми коэффициентами. Тогда дополнительно обозначим через aij – предпочтение преподавателя i относительно занятия j ; bit – предпочтения преподавателя i относительно интервала времени t ; ckt – предпочтение для аудитории k относительно интервала времени t, iI, jJ, kK, tT.

Варьируемые параметры Обозначим через xijkt переменную, принимающую значение равное 1, если преподаватель i проводит занятие j в аудитории k в интервал времени t, и принимающую значение равное 0, иначе, iI, jJ, kK, tT.

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

(преподаватель может провести не более одного занятия в каждый из интервалов времени);

iI k K tT (занятие должно быть проведено);

iI jJ (в каждый интервал времени аудитория может быть выделена не более чем под одно занятие);

(преподаватель не проводит занятия, которые не может провести);

(преподаватель не проводит занятия, в интервалы времени, в которые не может провести);

(аудитория не может быть выделена в тот интервал времени, когда она недоступна);

(естественные ограничения на переменные).

Критерий оптимальности Задача составления оптимального расписания, максимизирующего суммарные предпочтения заключается в определении расписания xijkt, iI, jJ, kK, tT, для которого выполняются ограничения (1.29)–(1.35) и принимает оптимальное значение критерий iI jJ k K tT Несложно увидеть, что проблема составления допустимого расписания (1.29)-(1.35) сводится к задаче составления оптимального расписания (1.29)-(1.31),(1.35),(1.36).

Действительно, пусть Тогда система ограничений (1.29)-(1.35) совместна тогда и только тогда, когда оптимальное значение критерия в соответствующей задаче (1.29)-(1.31),(1.35),(1.36) равно нулю.

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

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

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

Выводы Рассмотрены примеры постановок прикладных задач распределения ресурсов, относящихся к классу многоиндексных задач транспортного типа:

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

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

Глава 2. Методы исследования транспортных задач Глава посвящена изложению методов исследования ряда задач транспортного типа, рассмотренных в [13, 29, 30, 32, 83, 85]. Строятся алгоритмы решения рассматриваемых транспортных задач, проводится анализ их вычислительной сложности. Далее в работе, если не оговорено иного, при анализе сложности алгоритмов будем оценивать, как и в [82], количество вычислительных операций (арифметических операции, логических операции, элементарных операций с памятью) на машине с произвольным доступом к памяти. Полученные в данной главе результаты будут использованы далее при построении алгоритмов решения многоиндексных задач транспортного типа, основанных на сводимости к классу задач поиска потока в сети.

2.1. Поток в сети с двусторонними ограничениями Многие работы посвящены методам решения классических потоковых задач – задачи поиска максимального потока и задачи поиска потока минимальной стоимости заданной величины в сети с односторонними пропускными способностями. Обзор и оценки вычислительной сложности разработанных методов решения данных задач приводятся в [115, 151, 156]. В данном разделе рассматриваются задачи поиска потока в сети с двусторонними пропускными способностями. Приводится схема, позволяющая сводить задачи поиска потока в сети с двусторонними пропускными способностями к классическим задачам поиска потока в сети (с односторонними пропускными способностями). Формальное описание и доказательство корректности данной схемы были описаны в [13, 18, 86], сама схема основана на идеи, предложенной в [106]. Также отметим, что алгоритмы решения потоковых задач с двусторонними пропускными способностями применялись ранее при исследовании задач распределения ресурсов в иерархических системах [3, 4, 6, 10, 11, 14, 16, 17, 19, 23, 33, 87, 88, 110].

Задан ориентированный граф без петель G (VG, AG ), AG VG. Здесь VG и AG – множество вершин и дуг графа G соответственно. Там, где это не вызывает неоднозначности, будем опускать нижний индекс G при записи множества вершин и множества дуг графа. Среди множества вершин графа выделены специальные вершины s, t, называемые истоком и стоком соответственно, s t, s, t V. Обозначим через aij, bij и cij заданные значения нижней пропускной способности, верхней пропускной способности и стоимости дуги (i, j ), соответственно, (i, j ) A. Здесь 0 aij bij, (i, j ) A. Через xij обозначим поток вдоль дуги (i, j ), (i, j ) A ; через v – величину потока.

Тогда задача поиска максимального потока заключается в нахождение значений xij, программирования:

Далее задачу (2.1)-(2.3) будем обозначать через zMF (G; s; t; bij, (i, j ) A) (MF соответствует англоязычному названию max flow problem).

Определение 2.1. Набор значений xij, (i, j ) A, удовлетворяющих системе ограничений (2.1),(2.2) задачи zMF (G; s; t; bij, (i, j ) A) при фиксированном значении параметра v, будем называть потоком величины v.

максимальным потоком; а значение v – величиной максимального потока.

При фиксированном значение параметра v задача поиска потока минимальной стоимости заданной величины заключается в нахождении значений xij, (i, j ) A, являющихся решением задачи линейного программирования с системой ограничений (2.1),(2.2) и критерием соответствует англоязычному названию min cost flow problem).

Проблема поиска допустимой циркуляции заключается в нахождении величин xij, (i, j ) A, удовлетворяющих системы линейных неравенств Проблему (2.5),(2.6) будем обозначать через zFC (G; aij bij, (i, j ) A) (FС соответствует англоязычному названию feasible circulation problem). Задача поиска циркуляции минимальной стоимости ставится как задача линейного программирования (2.5),(2.6),(2.4) и обозначается через названию min cost circulation problem).

Определение 2.3. Набор значений xij, (i, j ) A, удовлетворяющих системе ограничений (2.5),(2.6) проблемы zFC (G; aij bij, (i, j ) A), будем называть допустимой циркуляцией.

Определение 2.4. Решение задачи zMCC (G; aij bij, cij, (i, j ) A) будем называть циркуляцией минимальной стоимости.

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

Определение 2.5. Пусть задана проблема поиска допустимой циркуляции максимального потока будем называть задачу zMF (G; s; t; bij, (i, j ) A), определяемую следующим образом:

zFC (G; aij bij, (i, j ) A) необходимо и достаточно, чтобы величина максимального потока соответствующей задачи zMF (G; s; t; bij, (i, j ) A) равнялась Z FC Z FC (G; aij bij, (i, j ) A) и соответствующую ей задачу поиска максимального потока Z MF Z MF (G; s; t; bij, (i, j ) A).

Пусть xij, (i, j ) A, допустимая циркуляция проблемы z FC. Тогда покажем, что конструктивное доказательство, основанное на построении максимального потока задачи Z MF. Определим значения xij, (i, j ) A, следующим образом:

случаи. Пусть i s, тогда Пусть i t, тогда Пусть i V, тогда согласно (2.5) Отсюда xij, (i, j ) A, удовлетворяет ограничению (2.1), при фиксированном значении 0 xij bij aij bij, (i, j ) A. Таким образом, xij, (i, j ) A, удовлетворяет ограничению максимальном потоке и минимальном разрезе [107] величина максимального потока не превосходит пропускной способности любого из разрезов сети. Рассмотрим разрез Тогда покажем, что существует допустимая циркуляция проблемы z FC. Приведем здесь также конструктивное доказательство, основанное на построении допустимой циркуляции Отсюда согласно (2.1) Таким образом, xij, (i, j ) A, удовлетворяет ограничению (2.5) и является циркуляцией.

Далее рассмотрим величины xij xij aij, (i, j ) A. Так как bij bij aij, (i, j ) A, то в aij xij xij aij bij aij bij, (i, j ) A. Таким образом, xij, (i, j ) A, удовлетворяет ограничению (2.6). Следовательно, построенная циркуляция является допустимой циркуляцией проблемы z FC. Теорема доказана.

На основании конструктивного доказательства теоремы 2.1 можно сформулировать следующее следствие.

zMF zMF (G; s; t; bij, (i, j ) A), соответствующей проблеме поиска допустимой циркуляции Z MF, то xij xij aij, (i, j ) A, является допустимой циркуляцией проблемы z FC.

Алгоритм 2.1. Поиск допустимой циркуляции.

Вход. Проблема zFC zFC (G; aijbij, (i, j ) A).

zMF zMF (G; s; t; bij, (i, j ) A), соответствующую проблеме z FC. Перейти на шаг 2.

Шаг 2. Найти максимальный поток xij, (i, j ) A, в задаче zMF. Перейти на шаг 3.

на шаг 4; иначе проблема z FC несовместна и алгоритм завершен.

правилу xij xij aij, (i, j ) A, алгоритм завершен.

Согласно определению (2.5), количество вершин и дуг в графе G задачи zMF zMF (G; s; t; bij, (i, j ) A), соответствующей задаче zFC zFC (G; aijbij, (i, j ) A), равно | V | 2 O(| V |) и 2 | V | | A | O(| V | | A |) соответственно. Применим для решения задачи поиска максимального потока zMF алгоритм, требующий (n, m) вычислительных операций, где n и m количество вершин и дуг графа G, соответственно. Отсюда:

Утверждение 2.1. Алгоритм 2.1 решения проблемы zFC (G; aij bij, (i, j ) A) требует (O(| V |), O(| V | | A |)) вычислительных операций.

Определение 2.6. Пусть задана задача поиска циркуляции минимальной стоимости zMCC (G; aijbij, cij, (i, j ) A), где G (V, A), тогда соответствующей задачей поиска потока zMCF (G; s; t; v; bij, cij (i, j ) A), определяемую следующим образом. Здесь граф G (V, A), вершины s, t следующим образом: cij cij, (i, j ) A ; cij 0, (i, j ) A \ A.

Следствие 2.2. Если задача zMCF zMCF (G; s; t; v; bij, cij (i, j ) A), соответствующая задаче поиска циркуляции минимальной стоимости совместна и xij, (i, j ) A – поток минимальной стоимости заданной величины задачи zMCF, то xij xij aij, (i, j ) A, является циркуляцией минимальной стоимости задачи zMCC.

Алгоритм 2.2. Поиск циркуляции минимальной стоимости.

Шаг 1. Используя алгоритм 2.1, решить проблему zFC zFC (G; aijbij, (i, j ) A). Если проблема z FC совместна, то перейти на шаг 2; иначе задача zМСС несовместна и алгоритм завершен.

Шаг 2. Построить задачу поиска потока минимальной стоимости заданной величины zMCF (G; s; t; v; bij, cij (i, j ) A), соответствующую задаче zМСС. Перейти на шаг 2.

Шаг 3. Найти поток минимальной стоимости заданной величины xij, (i, j ) A, задачи zMCF. Перейти на шаг 3.

следующему правилу xij xij aij, (i, j ) A, алгоритм завершен.

Как уже было установлено, количество вершин и дуг в графе G равно O(| V |) и O(| V | | A |) соответственно. Применим для решения задачи поиска потока минимальной стоимости заданной величины zMCF алгоритм, требующий (n, m) вычислительных операций, где n и m количество вершин и дуг графа G соответственно. Отсюда:

Утверждение 2.2. Алгоритма 2.2 решения задачи поиска циркуляции минимальной (O(| V |), O(| V | | A |)) + (O(| V |), O(| V | | A |)) вычислительных операций.

2.2. Поток в древовидной транспортной сети В данном разделе будут рассмотрены специальные потоковые алгоритмы анализа древовидных сетевых моделей, предложенные независимо в работах [85, 150]. Вопросы исследования древовидных сетевых моделей рассматривались также в [112].

Задано корневое ориентированное дерево G (V, A), V A 2. Среди множества вершин дерева выделена специальная вершина s – корень дерева, s V, и подмножество T – множество листьев, T V. Обозначим через ai, bi и ci заданные значения нижней пропускной способности, верхней пропускной способности и стоимости вершины i соответственно, i V. Здесь 0 ai bi, i V. Через xi обозначим поток через вершину i, Тогда задача поиска потока минимальной стоимости в древовидной сети заключается в нахождение значений x i, i V, являющихся решением следующей задачи линейного программирования:

соответствует англоязычному названию min cost flow problem in tree-like network).

Проблему исследования совместности системы (2.8), (2.9) будем обозначать через zFFT (G; ai, bi, i V ) (FFT соответствует англоязычному названию feasible flow problem in tree-like network).

ограничений (2.8), (2.9) проблемы zFFT (G; ai, bi, i V ), будем называть допустимым потоком древовидной сети.

Определение 2.8. Набор значений xi, i V, являющийся решением задачи zMCFT (G; ai, bi, ci, i V ), будем называть потоком минимальной стоимости древовидной сети.

Рассмотрим приведенные величины aip, bip, i V, которые определяются с помощью рекуррентных соотношений:

где Q(i) { j | (i, j ) A}, i V. Метод исследования совместности системы (2.8), (2.9) основан на следующей теореме о приведенных границах [85].

Теорема 2.2. Система (2.8), (2.9) совместна тогда и только тогда, когда aip bip, Доказательство. Необходимость условий теоремы очевидна. Доказательство достаточности проведем конструктивно. Покажем, что при выполнении условий теоремы специальным образом построенный набор значений неизвестных x i, i V, является допустимым решением системы (2.8), (2.9).

Так как по условию теоремы a sp bsp, то найдется значение xs [asp, bsp ]. Далее пусть для некоторого i V найдено значение переменной x i, что xi [aip, bip ]. Из рекуррентных соотношений (2.10), в случае выполнения условий теоремы, следует, что определяются из следующих соотношений:

является решением системы (2.8), (2.9). Теорема доказана.

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

Алгоритм 2.3. Поиск допустимого потока древовидной сети.

Шаг 1. Используя рекуррентные соотношения (2.10), вычислить приведенные границы aip, bip, i V. Если aip bip, i V, перейти на шаг 2; иначе проблема Z FFT несовместна и алгоритм завершен.

Шаг 3. Если найдется i V \ T, что величина x i найдена и не найдены величины x j, j Q(i), то перейти на шаг 4; иначе построенный набор xi, i V, является допустимым потоком древовидной сети проблемы z FFT, алгоритм завершен.

(2.11),(2.12), для чего воспользуемся следующей процедурой. Определить начальные значения переменных x j a jp, j Q(i). Просмотреть в произвольном порядке элементы элементу множества Q(i) ; иначе система (2.11),(2.12) решена, и перейти на шаг 3.

Граф G имеет древовидную структуру поэтому, используя обход дерева в ширину, можно упорядочить вершина графа таким образом, что V {i1,..., i|V | } и при этом операций. При вычислении приведенных границ aip, bip, i V, на шаге 1 алгоритма 2.3, основанном на рекуррентных соотношениях (2.10), необходимо просматривать вершины упорядоченного множества {i1,..., i|V | } в обратном порядке, тем самым будет гарантирована корректность вычисления приведенных границ по данным рекуррентным соотношениям.

При обработке каждый из вершин il просматриваются приведенные границы вершин множества Q(il ). Так как то шаг 1 алгоритма 2.3 требует O(| V |) вычислительных операций. Выбирать вершины на шаге 3 алгоритма 2.3 следует, просматривая упорядоченное множество {i1,..., i|V | } в прямом порядке. Тогда для каждой из просматриваемых вершин il (кроме вершин множества T ) будет выполнены соответствующие шаги 4 алгоритма. На шаге 4 предложенная процедура решения системы (2.11),(2.12) требует | Q(il ) | вычислительных операций. В силу (2.13) выполнение цикла шаг 3-4 алгоритма 2.3 требует O(| V |) вычислительных операций.

Отсюда:

Утверждение 2.3. Алгоритм 2.3 решения задачи поиска допустимого потока z FFT (G; ai, bi, i V ) требует O(| V |) вычислительных операций.

При исследовании задачи zMCFT (G; ai, bi, ci, i V ), не уменьшая общности, будем считать, что ci 0, i V \ T. Действительно, если это не так, то для каждой из вершин i T рассмотрим путь j1,..., jt, соединяющий лист i с корнем дерева, здесь ( jl, jl 1 ) A, l 1, t 1, и j1 s, jt i ; тогда определим модифицированную стоимость вершины i как ci ci. Модифицированные стоимость остальных вершин определим равными нулю, ci 0, i V \ T. Легко увидеть, что задачи zMCFT (G; ai, bi, ci, i V ) и zMCFT (G; ai, bi, ci, i V ) эквивалентны.

Введем ряд вспомогательных обозначений необходимых далее при исследовании задачи поиска потока минимальной стоимости в древовидной сети. Обозначим через t (i ) путь из корня s к листу i в дереве G, таким образом, t (i) (v0,..., vk ), где k – длина пути путей из корня к листьям в графе G, T (G) {t (i) | i T }. Пусть t (v0,..., vk ) – путь в графе G и v V. Тогда для удобства будем обозначать v t, если путь t проходит через вершину v, т.е. найдется j {0,..., k}, что v j v ; в противном случае будем обозначать zMCFT (G; ai, bi, ci, i V ) совместна, то существует оптимальное решение xi*, i V, задачи zMCFT (G; ai, bi, ci, i V ) такое, что выполняется следующее соотношение где t (i * ) (v0,..., vk ).

Доказательство. Пусть задача zMCFT (G; ai, bi, ci, i V ) совместна, и xi, i V, ее оптимальное решение задачи zMCFT (G; ai, bi, ci, i V ). Обозначим через i * T лист дерева, для которого выполняется | ci || ci* |, i T. Покажем, что можно построить оптимальное решение задачи, для которого выполняется соотношение (2.14). Далее рассмотрим два случая: ci* 0 и ci* 0.

xi* h, то для оптимального решения xi, i V, выполняется соотношение (2.14), и лемма доказана. Если xi* h, то xi, i V, не удовлетворяет системе (2.7),(2.8), однако это противоречит тому, что xi, i V, – оптимальное решение задачи zMCFT (G; ai, bi, ci, i V ).

Далее рассмотрим случай xi* h.

Если ci* 0, то ci 0, i T, и тогда произвольное допустимое решение задачи zMCFT (G; ai, bi, ci, i V ) будет являться оптимальным решением. Тогда, если xv j bvpj, j 0, k, то пусть min (bv j xv j ) и модифицируем решение xi, i V, по следующему правилу xi : xi, i t (i * ). Если ci* 0, то покажем от противного, что существует min (bvpj xv j ). Тогда построим поток xi, i V, по следующему алгоритму Несложно увидеть, что xi, i V, удовлетворяет системе (2.7),(2.8). Т.к. 0, то j max{ j | xv j bvpj, j {0,..., k}}. При этом j k, т.к. в противном случае xi* h.

Далее покажем от противного, что найдется j { j,..., k 1} и v Q(v j ) \ {v j1}, что xv avp. Предположим, что xv avp, v Q(v j ) \ {v j 1}, соотношение v Q(v j ) \ {v j1} и xv avp. Тогда найдется путь t в дереве G от v до некоторого листа из T, что min{xv av } 0. Обозначим через t путь в дереве G от v j1 до i *. По построению min{bv xv } 0.

Определим xi*, i V, по следующему алгоритму По построению xi*, i V, удовлетворяет системе (2.7),(2.8). Кроме того, т.к. | ci || ci* |, оптимальности решения xi, i V, набор xi, i V, также является оптимальным решением задачи соотношение (2.14) выполняется. В противном случае определим xi : xi, i V, и повторим построение, описанное выше. Несложно увидеть, что такое повторение возможно не более |V | раз. Следовательно, за конечное число шагов будет построено оптимальное решение xi, i V, удовлетворяющее соотношению (2.14).

xi* h, то для оптимального решения xi, i V, выполняется соотношение (2.14), и лемма доказана. Если xi* h, то xi, i V, не удовлетворяет системы (2.7),(2.8), однако это противоречит тому, что xi, i V, – оптимальное решение задачи zMCFT (G; ai, bi, ci, i V ).

Далее рассмотрим случай xi* h.

Доказательство данного случая можно провести по аналогии с доказательством случая 1. По аналогии можно показать, что существует j {0,..., k} такой, что xv j avpj, и тогда обозначим j max{ j | xv j avpj, j {0,..., k}}. Также по аналогии можно показать, что найдется j { j,..., k 1} и v Q(v j ) \ {v j1}, что xv bv. Тогда существует путь t в дереве G от v до некоторого листа из T, что min{bv xv } 0. Через t обозначим путь в дереве G от v j1 до i *. По построению min{xv av } 0. Далее определим xi, i V, по следующему алгоритму По построению xi, i V, удовлетворяет системе (2.7),(2.8). Кроме того, т.к. | ci || ci* |, оптимальности решения xi, i V, набор xi, i V, также является оптимальным решением задачи соотношение (2.14) выполняется. В противном случае определим xi : xi, i V, и повторим построение, описанное выше. Как и в случае 1, такое повторение возможно не более |V | раз. Следовательно, за конечное число шагов будет построено оптимальное решение xi, i V, удовлетворяющее соотношению (2.14). Лемма доказана.

Доказанная лемма позволяет предложить следующий алгоритм поиска потока минимальной стоимости в древовидной сети.

Алгоритм 2.4. Поиск потока минимальной стоимости древовидной сети.

Шаг 1. Используя рекуррентные соотношения (2.10), вычислить приведенные границы ai, zMCFT (G; ai, bi, ci, i V ) несовместна, и алгоритм завершен.

стоимости, T {i1,..., i|T | }, | ci j || ci j 1 |, j 1, | T | 1. Далее пусть j 1, переход на шаг 3.

Шаг 3. Определить xi*j, используя соотношение (2.14). Если j | T |, перейти на шаг 4; иначе пересчитать пропускные способности вершин пути t (i j ) по следующему правилу ai : max( 0, ai xi*j ), bi : bi xi*j, i t (i j ), удалить из графа G вершину i j, j : j 1, пересчитать приведенные границы ai, bi, i V, и переход на шаг 3.

Шаг 4. Используя найденные значения определить xi, i V \ T. Алгоритм завершен.

Как уже отмечалось выше, расчет приведенных границ на шаге 1 может быть осуществлен, используя O(| V |) вычислительных операций. Сортировка на шаге 2 требует O(| V |2 ) вычислительных операций. Выполнение вычислений, используя соотношение (2.14) и пересчет приведенных границ на шаге 3 может быть выполнено, используя O(| V |) вычислительных операций. Шаг 3 повторяется O(| V |) раз. Выполнение расчета на шаге 4 требует O(| V |) вычислительных операций. Отсюда:

Утверждение 2.4. Алгоритм 2.4 поиска потока минимальной стоимости древовидной сети zMCFT (G; ai, bi, ci, i V ) требует O(| V | ) вычислительных операций.

2.3. Поток в несовместной транспортной сети Рассматривается проблема исследования несовместной сетевой потоковой модели, представляющей собой систему линейных неравенств транспортного типа. Вопросы исследования несовместных систем линейных неравенств обсуждаются в [59, 109, 117, 155, 159]. Ряд работ посвящен исследованию несовместных потоковых моделей. Так, в [170] несовместных потоков для различных мер несовместности. Проблема поиска потока в сети сводится к поиску максимального потока, величина которого определяется величиной минимального разреза и служит критерием несовместности исходной сети. В [113] рассматривается задача поиска разреза минимальной мощности, являющегося причиной несовместности сети. В данном разделе рассматривается задача поиска потока (циркуляции) в несовместной сети, заключающаяся в поиске потока, удовлетворяющего изменения/нарушения пропускных способностей дуг [2, 12, 30, 111].

Рассмотрим проблему поиска допустимой циркуляции Z FC (G; aij bij, (i, j ) A), где G (V, A). Система ограничений проблемы представляет собой систему ограничений (2.5),(2.6). Здесь условия (2.5) описывают балансные ограничения, (2.6) – ограничения параметры, определяющие дуги, для которых разрешены изменения пропускных способностей, так u ij ( u ij ) равно 1, если для дуги (i, j ) разрешено изменение нижней (верхней) пропускной способности, и равно 0 в противном случае, u ij, u ij {0,1} ; d ij, eij – штрафы за изменение на единицу нижней и верхней пропускных способностей дуги (i, j ) соответственно, dij,eij 0, (i, j ) A ; pij, qij – неизвестные величины, на которые будут изменены нижняя и верхняя пропускные способности дуги (i, j ), соответственно, Пусть система (2.5),(2.6) несовместна. Тогда задача поиска потока в несовместной сети заключается в нахождение значений xij, pij, qij, (i, j ) A, являющихся решением следующей задачи линейного программирования:

Далее задачу (2.15)-(2.18) будем обозначать через z FSIN (G; aij, bij, uij, uij dij, eij, (i, j ) A) (FSIN соответствует англоязычному названию flow search problem in infeasible network).

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

Будем предполагать, что uij uij 1, (i, j ) A, соответствующую задачу будем обозначать через zFSIN (G; aij, bij, dij, eij, i V ). Далее будет показано, как обобщить предлагаемый алгоритм на случай, когда часть параметров uij, uij, (i, j ) A, могут принимать нулевые значения.

Лемма 2.2. Пусть xij, pij, qij, (i, j ) A – решение задачи zFSIN (G; aij, bij, dij, eij, i V ).

Тогда для каждой из дуг (i, j ) A выполняются следующие условия:

a) если aij xij bij, то pij 0, qij 0 ;

b) если xij aij, то pij aij xij, qij 0 ;

c) если bij xij, то pij 0, qij xij bij ;

d) pij aij.

выполняются условия леммы, но существует дуга (i, j ) A, что aij xi*j bij и pi*j 0.

Тогда из условия (2.17) следует, что pi*j 0. Построим набор значений xij xij, qij qij, (i, j ) A ; pij pij, (i, j ) A \ {(i, j )}, pij 0. Легко увидеть, что построенный набор значений удовлетворяет системе ограничений (2.15)-(2.17) и f ( p, q) f ( p *, q * ), что противоречит условию леммы. Таким образом, предположение неверно. Случай, когда aij xi*j bij и qi*j 0, рассматривается по аналогии.

b) Доказательство от противного. Предположим, что выполняются условия леммы, но существует дуга (i, j ) A, что xi*j aij и pi*j aij xi*j. Тогда из условия (2.16) следует, что aij xi*j pi*j. Построим набор значений xij xij, qij qij, (i, j ) A ; pij pij, удовлетворяет системе ограничений (2.15)-(2.17) и f ( p, q) f ( p *, q * ), что противоречит условию леммы. Таким образом, предположение неверно. Случай, когда xi*j aij и qi*j 0 рассматривается по аналогии с пунктом (a).

с) Доказательство аналогично доказательству пункта (b).

d) Доказательство от противного. Предположим, что выполняются условия леммы, но существует дуга (i, j ) A, что pi*j aij. Построим набор значений xij xij, qij qij, (i, j ) A ; pij pij, (i, j ) A \ {(i, j )}, pij aij. Легко увидеть, что построенный набор значений удовлетворяет системе ограничений (2.15)-(2.17) и f ( p, q) f ( p *, q * ), что противоречит условию леммы. Таким образом, предположение неверно. Лемма доказана.

Введем для каждой из дуг (i, j ) A вспомогательные переменные y ij, z ij, wij, которые будем интерпретировать следующим образом. Для заданного ориентированного множеством вершин V, в котором для каждой из дуг (i, j ) A заданного графа строятся (см. рис. 2.1):

– обратная дуга из вершины j в вершину i, поток вдоль которой обозначается через – две мультидуги из вершины i в вершину j, поток вдоль которых обозначается через y ij и z ij, соответственно.

Построенный мультиграф будет определять сеть, в которой – нижняя и верхняя пропускные способности дуги, связанной с переменной w ji, составляют 0 и aij соответственно, стоимость дуги равна d ij ;

составляют aij и bij соответственно, стоимость дуги равна 0;

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

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

выполняются условия леммы, но существует дуга (i, j ) A, что w*i 0 и z i*j 0. Тогда из условия (2.22) следует, что w*i 0, z i*j 0. Рассмотрим цикл, образуемый парой дуг, связанных с переменными w*i и z i*j. Пусть min( w*i, zi*j ), по предположению 0.

Уменьшим поток вдоль рассматриваемого цикла на величину, т.е. рассмотрим набор zij zi*j. Легко увидеть, что построенный набор значений удовлетворяет системе ограничений (2.19)-(2.22) и g ( z, w) g ( z *, w* ), что противоречит условию леммы. Таким образом, предположение неверно. Лемма доказана.

несовместной сети сводится к вспомогательной задаче (2.19)-(2.23) поиска потока минимальной стоимости.

zFSIN (G; aij, bij, dij, eij, (i, j ) A), тогда набор значений w ji pij, yij xij pij qij, zij qij, (i, j ) A, удовлетворяет системе ограничений (2.19)-(2.22), и при этом g ( z, w) f ( p *, q * ).

Доказательство. Пусть выполняются условия леммы. Тогда рассмотрим набор значений w ji pij, yij xij pij qij, z ij qij, (i, j ) A. Подставим данные значения в ограничения (2.19)-(2.22).

Рассмотрим ограничение (2.19):

Таким образом, ограничение (2.19) выполняется.

Далее рассмотрим ограничение (2.20) для фиксированной дуги (i, j ) A :

– если aij xij bij, то из пункта (a) леммы 2.2 следует, что pij 0, qij 0, тогда yij xij, и ограничение (2.20) выполняется;

– если xij aij, то из пункта (b) леммы 2.2 следует, что pij aij xij, qij 0, тогда yij aij, и ограничение (2.20) выполняется;

– если xij bij, то из пункта (с) леммы 2.2 следует, что pij 0, qij xij bij, тогда yij bij, и ограничение (2.20) выполняется.

Выполнимость ограничения (2.21) автоматически следует из пункта (d) леммы (с).

Неотрицательность величин w ji, z ij, (i, j ) A, непосредственно следует из условия (2.17). Величины выполняются условия (2.20). Отсюда ограничение (2.22) выполняется.

Наконец рассмотрим значение целевой функции (2.23):

Лемма доказана.

Лемма 2.5. Пусть w*ji, y ij, z ij, (i, j ) A – решение задачи (2.19)-(2.23), тогда набор ограничений (2.15)-(2.17), и при этом f ( p, q) g ( z *, w* ).

Доказательство. Пусть выполняются условия леммы. Тогда рассмотрим набор значений xij yij zij w*, pij w*, qij zij, (i, j ) A. Подставим данные значения в ограничения (2.15)-(2.17).

Рассмотрим ограничение (2.15):

Таким образом, ограничение (2.15) выполняется.

Далее рассмотрим ограничение (2.16) для дуги (i, j ) A. Из леммы 2.3 следует, что выполняется хотя бы одно из двух условий: z ij 0 или w* 0. Из ограничения (2.20) следует, что образом, ограничение (2.16) выполняется;

– если w* 0, то aij pij aij aij zij yij zij xij bij zij bij qij, таким образом, ограничение (2.16) выполняется.

Рассмотрим ограничение (2.17) для дуги (i, j ) A. Воспользуемся здесь также леммой 2.3. Тогда – если z ij 0, то xij yij w*, и из условий (2.20), (2.21) следует, что xij 0 ;

– если w* 0, то xij yij zij, и из условия (2.22) следует, что xij 0.

Неотрицательность величин pij, qij, (i, j ) A, непосредственно следует из условия (2.22).

Таким образом, ограничение (2.17) выполняется.

Наконец рассмотрим значение целевой функции (2.18):

Лемма доказана.

Теорема 2.3. Пусть w*ji, y ij, z ij, (i, j ) A – решение задачи (2.19)-(2.23), тогда набор значений xij yij zij w*, pij w*, qij zij, (i, j ) A, является решением задачи Z FSIN (G; aij, bij, d ij, eij, i V ).

Доказательство. Доказательство от противного. Пусть выполняются условия теоремы, но набор значений xij yij zij w*, pij w*, qij zij, (i, j ) A, не является оптимальным решением задачи zFSIN (G; aij, bij, dij, eij, i V ). Из леммы 2.5 следует, что zFSIN (G; aij, bij, dij, eij, i V ), следовательно, f ( p *, q * ) f ( p, q). Тогда из леммы 2.3 следует, что можно построить набор значений wji, y ij, z ij, (i, j ) A, удовлетворяющий системе (2.19)-(2.22), Предположение неверно. Теорема доказана.

Теорема 2.3 позволяет предложить алгоритм решения задачи поиска потока в несовместной сети, основанный на решении вспомогательной задачи поиска циркуляции минимальной стоимости (2.19)-(2.23).

Алгоритм 2.5. Поиск потока в несовместной сети.

Шаг 1. Построить вспомогательную задачу (2.19)-(2.23).

Шаг 2. Найти циркуляцию минимальной стоимости w*ji, y ij, z ij, (i, j ) A, задачи (2.19)-(2.23), используя алгоритм 2.2.

Шаг 3. Построить решение задачи правилу xij yij zij w*, pij w*, qij zij, (i, j ) A, алгоритм завершен.

Транспортная сеть, связанная с задачей (2.19)-(2.23), содержит мультидуги. Для Преобразуем рассматриваемую транспортную сеть: для всех мультидуг произведем последовательных дуги. Соответствующие преобразования необходимо выполнить перед zFSIN (G; aij, bij, dij, eij, i V ), где G (V, A), мы приходим к задаче поиска циркуляции минимальной стоимости в сети, содержащей O(| V | | A |) вершин и O(| A |) дуг. Тогда, согласно утверждению 2.2:

Утверждение 2.5. Алгоритма 2.5 решения задачи поиска потока в несовместной (O(| V | | A |), O(| V | | A |)) вычислительных операций.

параметров uij, uij, (i, j ) A, может принимать нулевые значения. Тогда необходимо модифицировать схему построения вспомогательной сети, определяемой мультиграфом.

Для каждой из дуг (i, j ) A исходного графа G введем дуги мультиграфа, связанные с переменными Модифицируем соответствующим образом схему построения вспомогательной задачи на шаге 1 алгоритма 2.5. Тогда алгоритм 2.5 может быть применен при решении общей задачи zFSIN (G; aij, bij, uij, uij dij, eij, (i, j ) A) поиска потока в несовместной сети.

2.4. Циклическая декомпозиция потока Рассмотрим задачу поиска циркуляции минимальной стоимости (2.5),(2.6),(2.4).

Далее циркуляцией графа G будем называть набор неотрицательных значений xij, (i, j ) A, удовлетворяющих системе ограничений (2.5). Если дополнительно xij Z, (i, j ) A, то циркуляцию будем называть целочисленной. Допустимой циркуляцией (как уже было введено ранее) будем называть набор значений xij, (i, j ) A, удовлетворяющих системе ограничений (2.5),(2.6). Циркуляцией минимальной стоимости будем называть набор значений xij, (i, j ) A, являющийся решением задачи (2.5),(2.6),(2.4). Далее в данном разделе исследуется проблема декомпозиции циркуляции на потоки вдоль простых циклов сети [22, 40].

Далее для удобства простой цикл графа G будем обозначать как C (i1,..., ik 1 ), где считать, что i1 i j, j 2, k (здесь будем также предполагать, что V {1,..., | V |} ). Пусть (u, v) A, C (i1,..., ik 1 ). Тогда для удобства будем обозначать (u, v) C, если цикл C проходит через дугу (u, v), т.е. найдется j {1, 2,..., k}, что u i j, v i j 1 ; в противном случае будем обозначать (u, v) C. Легко увидеть, что число простых циклов в графе простых циклов в графе является конченым. Множество всех простых циклов графа G будем обозначать через C (G).

Определение 2.9. Пусть xij, (i, j ) A – циркуляция графа G. Циклической декомпозицией циркуляции будем называть такой набор неотрицательных значений y C, циклическую декомпозицию будем называть целочисленной.

Лемма 2.6. Пусть xij, (i, j ) A, – ненулевая циркуляция. Тогда существует простой цикл C C (G), что min xuv 0.

Доказательство. Докажем лемму конструктивно. Пусть выполняются условия леммы, тогда построим алгоритм нахождения требуемого простого цикла C (далее Алгоритм 2.6):

Шаг 1. Выберем произвольную дугу (u, v) A, что xuv 0. Пусть i1 u, i2 v, k 2. Переход на Шаг 2.

j {1,2,....k}, что i j Q, то ik 1 : i j, C : (i j,..., ik 1 ), алгоритм завершен. Иначе выберем произвольный i Q, далее ik 1 : i, k : k 1 и переход на Шаг 2.

Покажем корректность построенного алгоритма. На шаге 1 дугу (u, v) можно выбрать, так как циркуляция ненулевая. Далее необходимо доказать, что на каждом из шагов 2 множество Q. По построению для каждого из шагов 2 выполняется условие алгоритма следует из конечности множества вершин графа. По построению, если алгоритм завершил свою работу, то C будет являться простым циклом и min xuv 0.

Лемма доказана.

Теорема 2.4. Для произвольной циркуляции существует ее циклическая декомпозиция.

Доказательство. Докажем теорему конструктивно. Пусть выполняются условия теоремы, тогда построим алгоритм нахождения циклической декомпозиции yC, C C (G), для заданной циркуляции xij, (i, j ) A.

Изначально пусть yC 0, C C (G). Введем вспомогательный набор значений z ij xij, (i, j ) A. Рассмотрим следующий алгоритм (далее Алгоритм 2.7):

Шаг 1. Если z ij, (i, j ) A – нулевая циркуляция, то алгоритм завершен. Иначе, переход на шаг 2.

Шаг 2. При помощи алгоритма 1 выберем простой цикл C C (G), что q : min zuv 0. Переход на шаг 3.

Покажем корректность построенного алгоритма. Покажем, что к концу каждого из неотрицательность величин z ij, (i, j ) A, непосредственно следует из выбранного значения q ; выполнение условий (2.1) следует из того, что C является циклом.

По построению для каждого из шагов 3 найдется (u, v) C, что к началу шага z uv 0, и z uv 0 к концу шага 3. Таким образом, величина | (i, j ) | (i, j ) A, zij 0 | возрастает минимум на единицу к концу каждого из шагов 3. Отсюда следует конечность построенного алгоритма. Кроме того, каждый из циклов C C (G) может встретиться не более одного раза на шаге 2. Далее по построению, если алгоритм завершил свою работу, то найденный набор y C, C C (G), является циклической декомпозицией исходной циркуляции. Теорема доказана.

При работе алгоритма 2.7 можно потребовать удаление всех дуг с нулевым потоком. Соответствующие действия необходимо выполнить перед началом работы алгоритма 2.7 и на каждом из его шагов 3. Тогда алгоритм 2.6, используемый на шаге алгоритма 2.7, будет требовать O(| V |) вычислительных операций. Действительно, при своевременном удалении дуг с нулевым потоком шаги 1 и 2 алгоритма 2.6 будут требовать O(1) вычислительных операций; а общее число циклов шаг 1, шаг 2 алгоритма 2.6 не превышает | V |. Каждый раз после выполнения шага 3 алгоритма 2.7 поток вдоль как минимум одной из дуг становится нулевым. Отсюда общее число циклов шаг 1, шаг 2, шаг 3 алгоритма 2.7 не превышает | A |. Таким образом, можно сформулировать следующее утверждение.

циркуляции требует O(| V || A |) вычислительных операций.

Согласно схеме работы алгоритма 2.7, в случае целочисленности исходной циркуляции ее циклическая декомпозиция, построенная алгоритмом 2.7, также будет являться целочисленной. Действительно, величина q, определяемая на шаге 2 алгоритма 2.7, будет целочисленной и, следовательно, величины zij, (i, j ) C и yC на шаге 3 также будут целочисленными. Отсюда справедливо следующее следствие.

Следствие 2.3. Для произвольной целочисленной циркуляции ее циклическая декомпозиция, построенная алгоритмом 2.7, также целочисленна.

Заметим, что полученные результаты о циклической декомпозиции справедливы для произвольной циркуляции. В частности результаты справедливы, когда речь идет о допустимой циркуляции или циркуляции минимальной стоимости. Как известно, матрица системы ограничений (2.5),(2.6) абсолютно унимодулярна [51]. Отсюда в случае целочисленных исходных параметров и совместной системы (2.5),(2.6), существует целочисленная допустимая циркуляция, а тем самым и ее целочисленная циклическая декомпозиция.

2.5. Метод ортогональных проекций при решении транспортных систем Одним из методов решения систем линейных неравенств является итерационные метод ортогональных проекций Агмона-Моцкина [114, 171]. В данном разделе описывается естественная модификация данного алгоритма при решении систем линейных неравенств транспортного типа, предложенная в [83]. Метод ортогональных проекций Агмона-Моцкина решения систем линейных неравенств заключается в следующем. Пусть необходимо найти решение системы Здесь x j, j 1, n, – неизвестные; bi, aij, i 1, m, j 1, n, – заданные параметры.

Обозначим Li ( x ) aij x j bi, i 1, m. Выберем произвольный вектор x (0) R n. Далее предположим, что известен вектор x ( ), тогда обозначим через I множество номеров линейных неравенств рассматриваемой системы, которые не выполняются при выбранном векторе x ( ) :

Если I, то задача решена, иначе будем вычислять значение индекса i0 по следующей формуле:

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

[114] было показано, что если система (2.24) совместна, то описанный итерационный процесс сходится к решению системы.

При исследовании двусторонних систем линейных неравенств транспортного типа двусторонних неравенств транспортного типа N i { j | aij 1, j 1, n}, i 1, m. Здесь подмножества N i и N i определяют компоненты вектора неизвестных, которые входят в уравнение i с коэффициентами 1 и – соответственно. Тогда для удобства запишем систему линейных неравенств (2.25) в следующем виде Выберем произвольный вектор x (0) R n. Далее предположим, что известен вектор x ( ), тогда обозначим через s номер первого по порядку ограничения, условия которого нарушены. Если такое ограничение не может быть найдено, то система неравенств решена. Иначе вектор x ( 1) определяется следующим образом:

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

В данном случае возможно введение управляющих параметров: – точности и H – количества шагов. Тогда для решения системы (2.24) можно воспользоваться следующей эвристикой: если за H шагом мы с -точностью не получили решение системы, то считаем, что система несовместна.

2.6. Многокритериальные транспортные задачи При решении прикладных задач распределении ресурсов в сложных системах возникает задача определения плана работы системы по различным показателям: группам оборудования, периодам планирования, этапам изготовления, потребляемым ресурсам, видам продукции и т.д [83]. Показатели делятся на жесткие, требующие обязательного выполнения, и желательные, к достижению которых нужно стремиться. Жесткие показатели формализуются в виде ограничений, а желательные – в виде критериев оптимальности. Тогда задача ставится как многокритериальная задача учета желательных показателей с ограничениями в виде учета жестких показателей. Ограничения учета жестких показателей формализуются в виде системы линейных двусторонних неравенств оптимальности. Как показывает опыт решения прикладных транспортных задач [84, 91], формализация критериев в виде непрерывных функция для пользователя часто предпочтительней оценить заданные показатели, указав границы для величин отклонения, в которых эти величины являются «отличными», «очень хорошими», «хорошими», «удовлетворительными» и др. Тогда формализуемые критерии могут быть представлены в виде кусочно-постоянных функций, разбивающих множество величин отклонения по каждому критерию на области «качества» отклонений. В данном разделе приводится постановка многокритериальной задачи транспортного типа с кусочно-постоянными критериями оптимальности и описывается метод ее решения, основанный на подходе, предложенном в [83].

Пусть определены k показателей, формализуемых в виде линейных функций совокупность из p 1 вложенных друг в друга сегментов S i, l 0, p, что S i S i, l 0, p 1, S i( p ) [,], i 1, k. С каждым из таких показателей будем связывать функцию предпочтения i (w), i 1, k, которая определена следующим образом:

Рассмотрим задачу поиска допустимого плана x j, j 1, n, удовлетворяющего системе ограничений (2.25) и минимизирующего функции предпочтения для выбранных показателей:

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

Формализация схемы компромисса рассматриваемой многокритериальной задачи требует введения некоторых вспомогательных величин. Пусть множество Va,b {(v1, v2,..., vb ) | vi 0, a, i 1, b}. Тогда через Va,b будем обозначать множество вершин a 1 -ичного b -мерного куба. Далее введем p 1 -ичный k -мерный куб, на котором определим порядок. Каждой вершине куба v V p,k поставим в соответствие систему (v ). Система (v ) содержит не зависящие от вершины куба ограничения (2.25) и ограничения, зависящие от вершины v следующим образом:

Таким образом, (v ) представляет собой систему ограничений (2.25), (2.27). На множестве вершин куба зададим двузначную функцию g (v ), принимающую значение 1, V {v | v V p,k, g (v ) 1} обозначим множество вершин p 1 -ичного k -мерного куба, на которых функция g принимает значение, равное 1. Не уменьшая общности, будем считать, что показатели плана упорядочены исходя из их приоритетов. В качестве порядка рассмотрим лексикографическое отношение порядка: v 1v 2 тогда и только тогда, когда для некоторого l {1,2,..., k} выполняется условие vl vl и одновременно v1 vr2, Тогда будем рассматривать следующую задачу поиска оптимальной вершины куба v 0 :

Оптимальная вершина v 0, являющаяся решением задачи (2.28), (2.29), определяет оптимальное решение многокритериальной задачи (2.25), (2.26) при лексикографической схеме компромисса.

функция g обладает следующим свойством монотонности.

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

Алгоритм 2.8. Поиск оптимальной вершины куба (лексикографическая свертка).

Вход. Задача (2.28), (2.29).

Шаг 1. Вычислить g ( p, p,..., p), если g ( p, p,..., p) 1, то пусть t : 1 и переход на шаг 2; иначе задача (2.28), (2.29) несовместна, и алгоритм завершен.

Шаг 2. Пусть v1, v2,..., vt 1 найденные первые t 1 компоненты вектора v 0.

Определим t - ую компоненту как решение следующей оптимизационной задачи:

g (v10, v2,..., vt01, y, p, p,..., p) 1, Оптимальное решение y 0 задачи (2.30)-(2.32) находится при помощи бинарного поиска на множестве {0,1,..., p}, на каждой итерации которого вычисляется соответствующее значение g (v1, v2,..., vt1, y, p, p,..., p). Пусть vt y, переход на шаг 3.

Шаг 3. Если t k, то t : t 1, переход на шаг 2; иначе алгоритм завершен.

Работа алгоритма 2.8 связана с вычислением k компонент вершины v 0. Каждая из компонент находится при помощи бинарного поиска на множестве мощности p 1. На каждой итерации бинарного поиска вычисляется значение функции g, а следовательно проверяется на совместность система вида (v ). Отсюда:

Утверждение 2.8. Алгоритм 2.8 требует O(k log p) проверок совместности систем ограничений вида (v ).

Дополнительно при решении многокритериальной задачи (2.25), (2.26) будем рассматривать максиминную свертку критериев оптимальности. Возникающая при этом оптимизационная задача ставится как задача (2.25), (2.33).

i 1, k Данная задача может быть поставлена как задача (2.28), (2.34) поиска оптимальной вершины куба v 0.

Монотонность функции g позволяет предложить алгоритм поиска оптимальной вершины куба, основанный на вычислении минимально возможного общего значения компонент вершины v 0. Общее значение компонент вычисляется при помощи бинарного поиска, на каждом шаге которого вычисляется значение функции g.

Алгоритм 2.9. Поиск оптимальной вершины куба (максиминная свертка).