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

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

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

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

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

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

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

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

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

Специальность: 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, 61, 78, 79, 80]. Многоиндексные задачи транспортного типа возникают также в области статистики и в смежной области защиты статистических данных [133, 135, 137, 162], в задаче целочисленного сбалансирования многоиндексных матриц [89, 90, 96].

Многоиндексные задачи о назначениях (подкласс многоиндексных транспортных задач целочисленного линейного программирования) возникают в теории расписаний при планировании изготовления скоропортящейся продукции, при планировании прохождения практики студентами, при планировании учебы клинических ординаторов по отделениям, при составлении расписания занятий, при планировании спортивных матчей и др. [113, 118, 127, 140, 142, 148, 158]; в области технического анализа данных при сопровождении объектов в многосенсорных системах [168, 169, 176]; в военной области при назначении военной техники на цели [111, 156]. Известны результаты, посвященные исследованию вопросов сводимости задач линейного и целочисленного линейного программирования к многоиндексным транспортным задачам [131, 132], что также расширяет область применения методов решения многоиндексных задач.

Многоиндексные задачи линейного программирования транспортного типа относятся к классу задач линейного программирования, который согласно [103] является полиномиально разрешимым. Таким образом, для решения многоиндексных задач линейного программирования транспортного типа могут быть применены общие методы исследований задач линейного программирования – симплекс метод [128], алгоритм Кармаркара [152]. Выделим также следующие работы, посвященные алгоритмам решения задач линейного программирования, [39, 40, 46, 48, 76, 154, 160]. Существует ряд работ, посвященных непосредственно методам решения многоиндексных задач линейного программирования транспортного типа. Наиболее изученным является класс двухиндексных задач [42, 47]. В многоиндексном случае (число индексов не менее трех) наибольшее внимание уделено двум классам задач: многоиндексные аксиальные задачи и многоиндексные планарные задачи. Вопросы исследования совместности и построения алгоритмов решения данных задач обсуждаются в [55, 63, 88, 116, 170, 178]. В общей многоиндексных задач рассматривается в [88]. Условия, при которых удается понизить размерность и (или) сократить количество индексов многоиндексных транспортных задач, обсуждаются в [41, 151]. Геометрические свойства множества допустимых решений многоиндексных транспортных задач обсуждаются в [55, 56, 64, 130]. Вопросы оценки числа нецелочисленных вершин многогранника многоиндексных транспортных задач рассматриваются в [62, 66–68]. В ряде работ исследуются многоиндексные задачи транспортного типа с нелинейными критериями [91, 92, 98, 119, 134, 175], в том числе с минимаксными [74, 75, 136, 146, 155, 177] и c квадратичными [69, 94, 120, 121, 125] критериями. Многокритериальные многоиндексные задачи транспортного типа обсуждаются в [53, 72, 73, 78, 79, 85–87].

Особый интерес представляет решение многоиндексных задач целочисленного линейного программирования транспортного типа, относящихся к классу задач целочисленного линейного программирования В общей постановке класс целочисленных многоиндексных транспортных задач является NP-трудным уже в трехиндексном случае [50]. Более того, для задач данного класса не существует полиномиальных -приближенных алгоритмов, иначе P=NP, данный результат также справедлив уже в трехиндексном случае [126]. Класс целочисленных многоиндексных задач, как подкласс задач целочисленного линейного программирования, содержит ряд известных полиномиально разрешимых подклассов: задачи, матрица систем ограничений которых является абсолютно унимодулярной [49], задачи с фиксированным числом переменных [139, 157], задачи N-кратного целочисленного программирования [129].

Приведем далее примеры соответствующих полиномиально разрешимых классов целочисленных многоиндексных задач. Как хорошо известно, матрица системы ограничений двухиндексной транспортной задачи является абсолютно унимодулярной, и тем самым класс двухиндексных задач целочисленного линейного программирования транспортного типа разрешим за полиномиальное время [42]. Класс многоиндексных задач целочисленного линейного программирования с фиксированным количеством индексов, каждый из которых принимает фиксированное количество значений, является полиномильно разрешимым согласно [157]. Примером полиномиально разрешимого трехиндексных планарных задач, в котором два из трех индексов принимают фиксированное количество значений [129]. При отсутствии дополнительных ограничений на параметры для решения многоиндексных задач целочисленного линейного программирования транспортного типа применимы лишь экспоненциальные по верхней оценке вычислительной сложности общие методы целочисленного линейного программирования, например, метод динамического программирования, метод ветвей и границ, метод отсечения Гомори [95, 97, 100].

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

Особое внимание уделяется двум классам многоиндексных задач о назначениях: класс Многоиндексные аксиальные задачи о назначениях рассматриваются, например, в работах [44, 45, 114, 115, 122, 123, 126], планарные в [43, 54, 65, 93, 141, 161].

Одним из перспективных направлений при разработке эффективных алгоритмов исследования многоиндексных задач линейного программирования является нахождение подклассов задач, для решения которых применимы потоковые методы. Важное влияние на развитие данного направления оказывают активные исследования в области сетевой оптимизации [1, 38, 51, 52, 59, 71, 99, 101, 102, 110, 117, 138, 143, 145, 163, 166, 172].

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

Рассматриваемая в диссертационной работе проблема сводимости многоиндексных транспортных задач линейного программирования к потоковым задачам является менее исследованной. Ранее было известно о сводимости двухиндексных задач к задаче поиска потока в сети [42]. Вопрос сводимости многоиндексных задач с произвольным числом индексов и произвольными многоиндексными подсуммами системы ограничений впервые рассматривался в работах [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 г., руководитель семинара профессор Monien B.), научных семинарах Кафедры информатики и автоматизации научных исследований факультета Вычислительной математики и кибернетики Нижегородского государственного университета им. Н.И.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения математической модели Допустимым портфелем заказов будем называть набор значений xijt, i I, j J, t T, удовлетворяющий следующей системе ограничений:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Варьируемые параметры Обозначим через xijkpt объем сырья, который из емкости i поступит на установку j для изготовления продукта k, который будет отправлен потребителю p в такт t, i I, j J, k K, p P, t T.

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

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

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

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

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

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

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

Тогда задача максимизации суммарного дохода предприятия от реализации продукции заключается в определении такого плана xijkpt, i I, j J, k K, p P, t T, для которого выполняются ограничения (1.19)-(1.22) и принимает оптимальное значение критерий Задача минимизации суммарных затрат технологических установок на переработку сырья в готовую продукцию заключается в определении такого плана xijkpt, i I, j J, k K, p P, t T, для которого выполняются ограничения (1.19)-(1.22) и принимает оптимальное значение критерий Задача минимизации суммарных затрат на перемещение сырья из емкостей в технологические установки заключается в определении такого плана xijkpt, i I, j J, k K, p P, t T, для которого выполняются ограничения (1.19)-(1.22) и принимает оптимальное значение критерий Задача минимизации суммарных затрат на закупку предприятием сырья заключается в определении такого плана xijkpt, i I, j J, k K, p P, t T, для которого выполняются ограничения (1.19)-(1.22) и принимает оптимальное значение критерий Задача минимизации суммарных затрат на доставку предприятием готовой продукции потребителям заключается в определении такого плана xijkpt, i I, j J, k K, p P, t T, для которого выполняются ограничения (1.19)-(1.22) и принимает оптимальное значение критерий Задача максимизации суммарной прибыли предприятия заключается в определении такого плана xijkpt, i I, j J, k K, p P, t T, для которого выполняются ограничения (1.19)и принимает оптимальное значение критерий i I j Jk Kp Pt T 1.4. Задача составления расписания занятий Для каждого из преподавателей известны занятия, которые он может провести, и время, в которое он может провести занятия. Для каждой из аудиторий известно время, когда она доступна. Необходимо составить допустимое расписание проведения занятий учебного заведения, т.е. определить время проведения занятий, преподавателя и выделить аудиторию с учетом описанных ограничений.

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

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

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

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

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

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

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

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

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

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

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

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

Критерий оптимальности Задача составления оптимального расписания, максимизирующего суммарные предпочтения заключается в определении расписания xijkt, i I, j J, k K, t T, для которого выполняются ограничения (1.29)–(1.35) и принимает оптимальное значение критерий Несложно увидеть, что проблема составления допустимого расписания (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, 78, 80]. Строятся алгоритмы решения рассматриваемых транспортных задач, проводится анализ их вычислительной сложности. Далее в работе, если не оговорено иного, при анализе сложности алгоритмов будем оценивать, как и в [77], количество вычислительных операций (арифметических операции, логических операции, элементарных операций с памятью) на машине с произвольным доступом к памяти. Полученные в данной главе результаты будут использованы далее при построении алгоритмов решения многоиндексных задач транспортного типа, основанных на сводимости к классу задач поиска потока в сети.

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

множество вершин и дуг графа G соответственно. Там, где это не вызывает неоднозначности, будем опускать нижний индекс G при записи множества вершин и множества дуг графа. Среди множества вершин графа выделены специальные вершины s, t, называемые истоком и стоком соответственно, s V. Обозначим через aij, bij и cij заданные значения нижней пропускной способности, верхней пропускной способности Тогда задача поиска максимального потока заключается в нахождение значений xij, программирования:

англоязычному названию max flow problem).

параметра v, будем называть потоком величины v.

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

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

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

циркуляцией.

циркуляцией минимальной стоимости.

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

Определение 2.5. Пусть задана проблема поиска допустимой циркуляции следующим образом:

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

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

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

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

операций, где n и m количество вершин и дуг графа G, соответственно. Отсюда:

(O(| V |), O(| V | Определение 2.6. Пусть задана задача поиска циркуляции минимальной стоимости zMCC (G; aij bij, cij, (i, j ) zMCF (G ; s; t; v; bij, cij (i, j ) совместна и xij, (i, j ) A – поток минимальной стоимости заданной величины задачи zMCC.

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

проблема zFC совместна, то перейти на шаг 2; иначе задача zМСС несовместна и алгоритм завершен.

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

задачи zMCF. Перейти на шаг 3.

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

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

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

вершин дерева выделена специальная вершина s – корень дерева, s V, и подмножество пропускной способности, верхней пропускной способности и стоимости вершины i Тогда задача поиска потока минимальной стоимости в древовидной сети заключается в нахождение значений xi, 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, которые определяются с помощью рекуррентных соотношений:

основан на следующей теореме о приведенных границах [80].

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

рекуррентных соотношений (2.10), в случае выполнения условий теоремы, следует, что определяются из следующих соотношений:

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

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

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

Шаг 1. Используя рекуррентные соотношения (2.10), вычислить приведенные несовместна и алгоритм завершен.

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

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

Граф G имеет древовидную структуру поэтому, используя обход дерева в ширину, операций. При вычислении приведенных границ aip, bip, i V, на шаге 1 алгоритма 2.3, основанном на рекуррентных соотношениях (2.10), необходимо просматривать вершины гарантированна корректность вычисления приведенных границ по данным рекуррентным соотношениям. При обработке каждый из вершин 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. Легко увидеть, что задачи 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 и v V. Тогда для удобства будем обозначать v t, если путь t проходит через 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). Далее рассмотрим два h, то для оптимального решения xi, i V, выполняется соотношение (2.14), и лемма xi* доказана. Если xi* h, то xi, i V, не удовлетворяет системе (2.7),(2.8), однако это противоречит тому, что xi, i V, – оптимальное решение задачи zMCFT(G; ai, bi, ci, i V ).

min (bvpj xv j ). Тогда построим поток xi, i V, по следующему алгоритму соотношение построению Определим 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).

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

Доказательство данного случая можно провести по аналогии с доказательством дереве G от v до некоторого листа из T, что 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), вычислить приведенные zMCFT(G; ai, bi, ci, i V ) несовместна, и алгоритм завершен.

Шаг 2. Упорядочить множество листьев T по невозрастанию модуля стоимости, T {i1,..., i|T | }, | ci | | ci |, j 1, | T | 1. Далее пусть j 1, переход на шаг 3.

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

определить 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. Поток в несовместной транспортной сети Рассматривается проблема исследования несовместной сетевой потоковой модели, представляющей собой систему линейных неравенств транспортного типа. Вопросы исследования несовместных систем линейных неравенств обсуждаются в [57, 104, 112, 149, 153]. Ряд работ посвящен исследованию несовместных потоковых моделей. Так, в [164] несовместных потоков для различных мер несовместности. Проблема поиска потока в сети сводится к поиску максимального потока, величина которого определяется величиной минимального разреза и служит критерием несовместности исходной сети. В [108] рассматривается задача поиска разреза минимальной мощности, являющегося причиной несовместности сети. В данном разделе рассматривается задача поиска потока (циркуляции) в несовместной сети, заключающаяся в поиске потока, удовлетворяющего изменения/нарушения пропускных способностей дуг [2, 12, 30, 106].

(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 ) изменены нижняя и верхняя пропускные способности дуги (i, j ), соответственно, (i, j ) Пусть система (2.5),(2.6) несовместна. Тогда задача поиска потока в несовместной следующей задачи линейного программирования:

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

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

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

(i, j ) противоречит условию леммы. Таким образом, предположение неверно. Случай, когда b) Доказательство от противного. Предположим, что выполняются условия леммы, (i, j ) 0 рассматривается по аналогии с пунктом (a).

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

d) Доказательство от противного. Предположим, что выполняются условия леммы, (i, j ) противоречит условию леммы. Таким образом, предположение неверно. Лемма доказана.

которые будем интерпретировать следующим образом. Для заданного ориентированного (см. рис. 2.1):

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

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

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

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

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

w* z ij образом, предположение неверно. Лемма доказана.

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

(i, j ) Доказательство. Пусть выполняются условия леммы. Тогда рассмотрим набор ограничения (2.19)-(2.22).

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

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

xij, и ограничение (2.20) выполняется;

aij, и ограничение (2.20) выполняется;

bij, и ограничение (2.20) выполняется.

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

выполняются условия (2.20). Отсюда ограничение (2.22) выполняется.

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

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

Доказательство. Пусть выполняются условия леммы. Тогда рассмотрим набор ограничения (2.15)-(2.17).

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

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

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

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

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

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

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

Z FSIN (G; aij, bij, d ij, eij, i V ).

Доказательство. Доказательство от противного. Пусть выполняются условия оптимальным решением задачи zFSIN (G; aij, bij, dij, eij, i V ). Из леммы 2.5 следует, что f ( p, q) Предположение неверно. Теорема доказана.

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

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

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

(2.19)-(2.23), используя алгоритм 2.2.

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

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

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

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

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

Далее для удобства простой цикл графа G будем обозначать как C (i1,..., ik 1 ), где (u, v) случае будем обозначать (u, v) C. Легко увидеть, что число простых циклов в графе простых циклов в графе является конченым. Множество всех простых циклов графа G будем обозначать через C (G ).

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

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

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 ) можно выбрать, так как циркуляция ненулевая. Далее необходимо доказать, что на каждом из xik 1ik алгоритма следует из конечности множества вершин графа. По построению, если Лемма доказана.

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

Доказательство. Докажем теорему конструктивно. Пусть выполняются условия теоремы, тогда построим алгоритм нахождения циклической декомпозиции yC, C C (G ), Шаг 1. Если z ij, (i, j ) A – нулевая циркуляция, то алгоритм завершен. Иначе, переход на шаг 2.

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

По построению для каждого из шагов 3 найдется (u, v) C, что к началу шага zuv возрастает минимум на единицу к концу каждого из шагов 3. Отсюда следует конечность построенного алгоритма. Кроме того, каждый из циклов C C (G ) может встретиться не более одного раза на шаге 2. Далее по построению, если алгоритм завершил свою работу, то найденный набор yC, 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) абсолютно унимодулярна [49]. Отсюда в случае целочисленных исходных параметров и совместной системы (2.5),(2.6), существует целочисленная допустимая циркуляция, а тем самым и ее целочисленная циклическая декомпозиция.

2.5. Метод ортогональных проекций при решении транспортных систем Одним из методов решения систем линейных неравенств является итерационные метод ортогональных проекций Агмона-Моцкина [109, 165]. В данном разделе описывается естественная модификация данного алгоритма при решении систем линейных неравенств транспортного типа, предложенная в [78]. Метод ортогональных проекций Агмона-Моцкина решения систем линейных неравенств заключается в следующем. Пусть необходимо найти решение системы предположим, что известен вектор x ( ), тогда обозначим через I множество номеров линейных неравенств рассматриваемой системы, которые не выполняются при выбранном векторе x ( ) :

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

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

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

При исследовании двусторонних систем линейных неравенств транспортного типа двусторонних неравенств транспортного типа вектора неизвестных, которые входят в уравнение i с коэффициентами 1 и – соответственно. Тогда для удобства запишем систему линейных неравенств (2.25) в следующем виде тогда обозначим через s номер первого по порядку ограничения, условия которого нарушены. Если такое ограничение не может быть найдено, то система неравенств решена. Иначе вектор x ( 1) определяется следующим образом:

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

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

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

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

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

Формализация схемы компромисса рассматриваемой многокритериальной задачи множество вершин a 1 -ичного b -мерного куба. Далее введем p 1 -ичный k -мерный куб, на котором определим порядок. Каждой вершине куба v V p,k поставим в соответствие систему (v ). Система (v ) содержит не зависящие от вершины куба ограничения (2.25) и ограничения, зависящие от вершины v следующим образом:

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

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

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

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

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

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

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

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

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

Работа алгоритма 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).

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

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

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

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

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

Шаг 2. Определим оптимальное значение компонент вершины как решение следующей оптимизационной задачи.

Оптимальное решение y 0 задачи (2.35)–(2.37) находится при помощи бинарного поиска на множестве {0,1,..., p}, на каждой итерации которого вычисляется соответствующее значение g ( y, y,..., y ). Пусть vi0 y 0, i 1, k. Алгоритм завершен.

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

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

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

Выводы Рассмотрены методы решения ряда задач транспортного типа, построены оценки операций, требуемых для решения задачи поиска максимального потока и потока минимальной стоимости заданной величины соответственно, где n и m – количество вершин и дуг сети. Описана и обоснована процедура поиска потока в сети с двусторонними пропускными способностями:

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

Описана и обоснована процедура поиска потока в древовидной сети с двусторонними пропускными способностями:

– поиск допустимого потока требует O (| V |) вычислительных операций, – поиск потока минимальной стоимости требует O(| V |2 ) вычислительных операций.

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

Описан и обоснован метод решения k-критериальных задач транспортного типа с кусочно-постоянными (p+1)-значными критериями:

– при лексикографической свертки алгоритм требует O(k log p ) проверок совместности систем транспортного типа, совместности систем транспортного типа.

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

Глава 3. Многоиндексные задачи транспортного типа Глава посвящена постановкам исследуемых многоиндексных задач транспортного типа. Постановки задач приведены с использованием введенной в [88] и далее развитой в [8, 9, 20] схемы формализации многоиндексных задач. Данная формализация используется в работе при описании результатов исследования многоиндексных задач. Описывается общая формализация схем сводимости, разработанная в [8, 9, 20], применяемая далее при классификации схем сведения многоиндексных задач к классу задач поиска потока в сети.

3.1. Постановки многоиндексных задач транспортного типа При постановке многоиндексных задач транспортного типа воспользуемся следующей формализацией, основанной на обозначении, введенном в [88]. Пусть s N и N ( s ) {1,2,...,s}. Каждому числу l поставим в соответствие параметр jl, называемый Там где это не вызывает неоднозначности, будем отождествлять номер индекса l и индекс ( jk1, jk2,..., jkt ) f будем называть t-индексом. Множество всех t-индексов, соответствующих неоднозначности, будем опускать нижний индекс f и записывать t-индекс как jk1 jk2... jkt.

Данное отображение множества t-индексов E f в множество действительных чисел назовем t-индексной матрицей и обозначим через {z F f }. Рассмотрим s-индексную матрицу {z N (s ) } и введем следующее обозначение Введенное обозначение подсумм s-индексной матрицы будем использовать при формализации многоиндексных транспортных задач.

индексная матрица коэффициентов целевой функции; {x FN ( s ) } – s-индексная матрица неизвестных. Тогда многоиндексная задача линейного программирования транспортного типа формализуется следующим образом:

многоиндексных задач линейного программирования (3.1)-(3.3) при фиксированном множестве M будем обозначать W (M ). Систему ограничений (3.1),(3.2) будем линейных неравенств (3.1),(3.2) при фиксированном множестве M будем обозначать D (M ).

d ( w, f, F f ). Матрицу системы ограничений задачи w обозначим через Matr (w). Строку матрицы Matr (w), определяемую двусторонним неравенством d ( w, f, F f ), обозначим образованную элементами матрицы Matr (w), находящимися на пересечении строк Matr( w; ( f (i ), F ((ii)) ), i 1, k1 ; FN (j s ), j 1, k2 ).

В ряде задач s-индексная матрица коэффициентов целевой функции {cFN ( s ) } имеет Тогда рассмотрим целевую функцию следующего вида:

Класс всех многоиндексных задач задача линейного программирования (3.1),(3.2),(3.4) при фиксированных множествах M и H будем обозначать W ( M, H ). Справедливы следующие утверждения.

что справедливо следующее утверждение.

Дополнительно среди задач класса W ( M, H ) выделим задачи, удовлетворяющие следующему обобщенному неравенству треугольника.

фиксированных множествах M и H будем обозначать W ( M, H ).

целочисленности переменных Задачу (3.1)-(3.3),(3.6) будем обозначать wZ ( s; M ; n1,..., ns ; {a F }, {bF }, f M ). Также будем добавлять нижний индекс Z к обозначению класса многоиндексных задач, если дополнительно выполняется условий целочисленности (3.6). Тогда соответствующие классы систем целочисленных линейных неравенств (3.1),(3.6), задач целочисленного линейного программирования (3.1),(3.6),(3.3) и задач целочисленного линейного программирования (3.1),(3.6),(3.4) при фиксированных множествах M и H будем обозначать через DZ (M ), WZ (M ) и WZ ( M, H ) соответственно.

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

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

принимающий значение 1, если для неравенства d ( w, f, F f ) разрешено изменение нижней (верхней) границы, и значение 0 в противном случае; eFf ( eFf ) – штраф за изменение на неизвестная величина, на которую будет изменена нижняя (верхняя) граница неравенства несовместна и w w( s; M ; n1,...,ns ;{aF },{bF }, f M ;{cFN ( s ) }). Тогда задача исследования несовместной многоиндексной системы заключается в определении многоиндексных задачи линейного программирования:

Класс всех задач задача линейного программирования (3.7)-(3.10) при фиксированном множестве M будем обозначать S (M ).

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

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

многоиндексных неравенств транспортного типа (3.1),(3.2). Множество H определяет ( f, Ff ) P( H ). Каждая из пар ( f, Ff ) определяет следующую функцию предпочтения Тогда рассмотрим многокритериальную задачу определения s-индексной матрицы минимизирующей функции предпочтения Класс многокритериальных задач (3.1),(3.2),(3.11) будем обозначать U ( M, H ). Пусть множество P(H ) упорядочено по значимости соответствующих критериев. Тогда в качестве схемы компромисса при решении поставленной многокритериальной задачи (3.1),(3.2),(3.11) оптимальности, соответствующий класс оптимизационных задач при фиксированных множествах M и H будем обозначать U ( M, H ). Также в качестве схемы компромисса будем рассматривать максиминную свертку критериев оптимальности, соответствующий класс оптимизационных задач при фиксированных множествах M и H будем обозначать U max min (M, H ).

3.2. Задачи распределения ресурсов как многоиндексные задачи Введенную схему формализации многоиндексных задач транспортного типа проиллюстрируем на примере прикладных многоиндексных задач распределения ресурсов, описанных в главе 1. Определим место описанных прикладных задач в классе многоиндексных задач транспортного типа.

Транспортная задача с промежуточными пунктами Рассмотрим транспортную задачу с промежуточными пунктами, описанную в ограничение (1.1) соответствует множеству { j, k}, ограничение (1.2) – множеству {i, j}, ограничение (1.3) – множеству {k }, ограничение (1.4) – множеству {i}.

Тогда поставленные многоиндексные задачи линейного программирования (1.1)задача (1.1)-(1.5),(1.7) и задача (1.1)-(1.5),(1.8) относятся к классу W (M ).

Можно заметить, что коэффициенты целевых функций (1.6), (1.7) и (1.8) имеют декомпозиционную структуру – они определены в виде суммы многоиндексных матриц коэффициентов. Так для критерия (1.6) коэффициенты целевой функции имеют вид При постановке многокритериальной задачи выбора плана перевозок (1.1)в качестве показателей плана, определяющих критерии задачи, выбраны объемы продукта соответствующего потребителям системы. Объем продуктов потребленный {{i}, {k}, {i, j}, { j, k}} – определяет жесткие показатели, формализуемые в виде системы ограничений (1.1)-(1.5), H {{k}} – определяет желательные показатели, формализуемые в виде критериев (1.9). Если множество потребителей K упорядочено с точки зрения их приоритета, то при решении многокритериальной задачи (1.1)-(1.5),(1.9) может быть рассмотрена лексикографическая свертка критериев. Соответствующая задача относится к классу U ( M, H ). В случае равнозначности потребителей в качестве схемы компромисса при решении многокритериальной задачи (1.1)-(1.5),(1.9) может быть рассмотрена максиминная свертка. Соответствующая задача относится к классу U max min (M, H ).

Задача формирования портфеля заказов Рассмотрим задачу формирования портфеля заказов, описанную в разделе 1.2. Для соответствует множеству { j, t}, ограничение (1.11) – множеству { j}, ограничение (1.12) – множеству {i, t}, ограничение (1.13) – множеству. Тогда поставленная проблема определения допустимого портфеля заказов (1.10)-(1.14) относится к классу D(M ).

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

Задача формирования портфеля заказов с возможными нарушениями требуемых объемов работ по заказам ставится как задача (1.10),(1.11),(1.13)-(1.17). В поставленной задаче разрешены нарушения ограничения (1.12), определяемого множеством {i, t}.

Задача формирования портфеля заказов с возможными нарушениями сроков (1.12),(1.14),(1.18).

Объемно-календарное планирование переработки газового конденсата Рассмотрим задачу объемно-календарного планирования переработки газового {{i, j}, {i, p}, { j, k, p, t}}. Здесь ограничение (1.19) соответствует множеству { j, k, p, t}, ограничение (1.20) – множеству {i, p}, ограничение (1.21) – множеству {i, j}. Тогда поставленные многоиндексные задачи линейного программирования (1.19)-(1.22),(1.23), задача (1.19)-(1.22),(1.24), задача (1.19)-(1.22),(1.25), задача (1.19)-(1.22),(1.26), задача (1.19)-(1.22),(1.27) и задача (1.19)-(1.22),(1.28) относятся к классу W (M ).

Можно заметить, что коэффициенты целевых функций рассматриваемых задач имеют декомпозиционную структуру. Отсюда задача (1.19)-(1.22),(1.23) относится к классу W ( M, H ), где H {{k, p, t}}. Задача (1.19)-(1.22),(1.24) относится к классу W ( M, H ), где H {{ j, k}}. Задача (1.19)-(1.22),(1.25) относится к классу W ( M, H ), где (1.19)-(1.22),(1.27) относится к классу W ( M, H ), где H {{k, p}}. Задача (1.19)-(1.22), Задача составления расписания занятий Рассмотрим задачу составления расписания занятий, описанную в разделе 1.4. Для (1.29) соответствует множеству { j, k }, ограничение (1.30) – множеству {i, k, t}, ограничение (1.35) эквивалентно совокупности ограничений (3.12) и дополнительного ограничения целочисленности переменных, при этом ограничение (3.12) также Отсюда система целочисленных линейных неравенств (1.29)–(1.35) относится к классу DZ (M ), задача целочисленного линейного программирования (1.29)–(1.36) относится к классу WZ (M ).

Заметим, что с учетом ограничения неотрицательности переменных ограничения (1.32), (1.33), (1.34) могут быть записаны в следующей эквивалентной форме k KtT j Jk K iI jJ Кроме того, ограничение (3.12) автоматически выполняется при выполнении ограничения (1.29) и ограничения неотрицательности переменных. Отсюда система целочисленных функции (1.36) имеют декомпозиционную структуру. Отсюда задача (1.29)–(1.36) 3.3. Общая концепция сводимости многоиндексных задач При описании результатов сводимости одного класса задач к другому удобно требуемые вычислительные затраты и применяемые процедуры при сведении. Приведем формализацию концепции сводимости, которую далее будем использовать при исследовании сводимости классов многоиндексных задач к классу задач поиска потока в сети.

неизвестных. Через w( A, b, c) будем обозначать задачу линейного программирования min{( c, x) | b количество строк и столбцов матрицы A соответственно. Отметим, что задача w( A, b, b, c) может быть описана с использованием обозначения вида w( A, b, c). Тем не менее будем использовать обозначение w( A, b, b, c) в случае, когда хотим подчеркнуть, что система ограничений задачи представляет собой систему двусторонних неравенств.

Также будем рассматривать задачи целочисленного линейного программирования. Если w( A, b, c) – задача линейного программирования, то через wZ обозначим задачу W – произвольный класс задач линейного программирования. Соответствующий класс задач целочисленного линейного программирования определим как WZ {wZ | w W }.

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

– построением матрицы системы ограничений задачи w по исходным параметрам – построением свободных коэффициентов и коэффициентов целевой функции задачи w по исходным параметрам задачи w ;

– построением решения задачи w по решению задачи w.

Предлагаемое далее обозначение схемы сведения вводится по аналогии с нотацией Р. Грэхема (R. Graham), используемой при классификации задач теории расписаний [124].

Определение 3.1. Будем говорить, что класс W является t1 s1 | t2 s2 | t3 s сводимым к классу W, если для любой задачи w w( A, b, c ) W можно за время O (t1 ) с использованием процедуры s1 построить матрицу A, за время O (t 2 ) c использованием процедуры s 2 построить векторы b, c, что w w( A, b, c ) W и при этом – задача w совместна (ограничена) тогда и только тогда, когда совместна (ограничена) – если известно оптимальное (допустимое) решение x задачи w, то оптимальное (допустимое) решение x задачи w может быть построено за время O(t3 ) с использованием процедуры s3.