Содержание к диссертации
Введение
ГЛАВА 1. Оптимизационные задачи распределения ресурсов в иерархических системах 11
1.1. Место задач распределения ресурсов в классе задач математического программирования 11
1.1.1. Задачи распределения ресурсов как задачи математического программирования 11
1.1.2. Задачи распределения ресурсов как задачи выпуклого программирования 13
1.1.3. Задачи распределения ресурсов как задачи линейного программирования транспортного типа 14
1.2. Задачи распределения ресурсов в иерархических системах 18
1.2.1. Иерархические системы транспортного типа 18
1.2.2. Распределение ресурсов в иерархических системах 19
1.2.3. Эффективность функционирования иерархических систем 20
1.3. Содержательная постановка задач распределения ограниченных ресурсов в иерархических системах транспортного типа 22
1.3.1. Одноресурсные задачи распределения в иерархических ситсемах транспортного типа 22
1.3.2. Многоресурсные задачи распределения в иерархических системах транспортного типа 25
1.3.3. Задачи распределения ресурсов в частных случаях ресурсных ограничений при различных структурах иерархической системы 29
Выводы 35
ГЛАВА 2. Математические модели распределения ограниченных ресурсов в иерархических системах транспортного типа 36
2.1. Одноресурсные иерархические системы 36
2.1.1. Общая математическая модель распределения ресурсов в одноресурсных иерархических системах транспортного типа 36
2.1.2, Исследование общей математической модели распределения ресурсов в одноресурсных иерархических системах транспортного типа 38
2.1.3. Исследование математической модели распределения ресурсов в одноресурсных иерархических системах древовидной структуры 58
2.2. Многоресурсные иерархические системы 62
2.2.1. Общая математическая модель распределения ресурсов в многоресурсных иерархических системах транспортного типа 62
2.2.2. Исследование общей математической модели распределения ресурсов в многоресурсных иерархических системах транспортного типа 64
2.2.3. Исследование математической модели распределения ресурсов в многоресурсных иерархических системах древовидной структуры 66
2.3. Многоиндексные иерархические системы 73
2.3.1. Общая математическая модель распределения ресурсов в многоиндексных иерархических системах транспортного типа 73
2.3.2. Исследование общей математической модели распределения ресурсов в многоиндексных иерархических системах транспортного типа 74
2.3.3. Сводимость математической модели распределения ресурсов в многоиндексных иерархических системах транспортного типа к потоковым моделям 75
Выводы 81
ГЛАВА 3. Многокритериальные задачи распределения ресурсов в иерархических системах транспортного типа и схемы компромисса 84
3.1. Аддитивные схемы компромисса для многокритериальной задачи распределения ресурсов в иерархических системах транспортного типа 85
3.1.1. Сводимость задачи распределения ресурсов в иерархических системах транспортного типа с аддитивными схемами компромисса к потоковым задачам 87
3.1.2. Применение сводимости для построения алгоритмов решения задачи распределения ресурсов в иерархических системах транспортного типа с аддитивными схемами компромисса 93
3.1.3. Алгоритм решения задачи распределения ресурсов в одноресурсных иерархических системах древовидной структуры с аддитивными схемами компромисса 97
3.2. Лексикографическое упорядочивание частных критериев оптимальности при решении многокритериальной задачи распределения ресурсов в иерархических системах транспортного типа 99
3.2.1. Формализация лексикографического упорядочивания частных критериев оптимальности как схемы компромисса при решении задачи распределения ресурсов в иерархических системах транспортного типа 99
3.2.2. Алгоритм поиска оптимальной вершины многомерного многозначного куба при решении задачи распределения ресурсов в иерархических системах транспортного типа с лексикографическим упорядочиванием частных критериев оптимальности 100
3.2.3. Анализ вычислительной сложности алгоритма поиска оптимальной вершины многомерного многозначного куба при решении задачи распределения ресурсов в иерархических системах транспортного типа с лексикографическим упорядочиванием частных критериев оптимальности 102
3.3. Максиминные (минимаксные) схемы компромисса для многокритериальной задачи распределения ресурсов в иерархических системах транспортного типа 104
3.3.1. Алгоритмы решения задачи распределения ресурсов в иерархических системах транспортного типа с максиминными схемами компромисса в случае кусочно-постоянных частных критериев оптимальности 105
3.3.2. Алгоритмы решения задачи распределения ресурсов в иерархических системах транспортного типа с максиминными (минимаксными) схемами компромисса в случае линейных функций предпочтения 106
3.3.3. Алгоритмы решения задачи целочисленного распределения ресурсов в иерархических системах транспортного типа с максиминными (минимаксными) схемами компромисса в случае линейных частных критериев оптимальности 109
Выводы Ill
Заключение ИЗ
Литература
- Задачи распределения ресурсов как задачи линейного программирования транспортного типа
- Многоресурсные задачи распределения в иерархических системах транспортного типа
- Исследование общей математической модели распределения ресурсов в одноресурсных иерархических системах транспортного типа
- Применение сводимости для построения алгоритмов решения задачи распределения ресурсов в иерархических системах транспортного типа с аддитивными схемами компромисса
Введение к работе
В середине XX века появился особый интерес к исследованиям многоиндексных задач линейного программирования транспортного типа. Это было обусловлено широким многообразием прикладных задач, формализуемых в виде данного частного класса задач линейного программирования. Особое место среди подобных прикладных задач занимают задачи распределения ресурсов в сложных системах, моделируемых сетевыми структурами, к которым в частности относятся и рассматриваемые в диссертационной работе задачи распределения ресурсов в иерархических системах транспортного типа. Важной особенностью реальных объектов, для которых актуальны рассматриваемые задачи распределения ресурсов, является большая размерность, что обуславливает поиск эффективных алгоритмов их решения.
В задачах распределения ресурсов в иерархических системах транспортного типа предполагается, что исследуемая система состоит из элементов, которые способны производить, передавать или потреблять ресурсы. Передача ресурсов происходит посредством связей между элементами системы. Кроме того, имеются ограничения на объемы циркулирующих в системе ресурсов, определяемые возможностями системы и требованиями к ее функционированию. Среди элементов системы выделяется подмножество контролируемых элементов, с которыми связаны функции предпочтения, определяющие условия эффективного функционирования иерархической системы. Под распределением ресурсов в рассматриваемом классе задач понимается определение объемов ресурсов, которые должны быть переданы по каждой из связей иерархической системы. Задача заключается в распределения ресурсов в иерархических системах транспортного типа таким образом, чтобы были выполнены ограничения системы и удовлетворены условия эффективного функционирования.
Подобного рода задачи возникают, например, при распределении энергоресурсов между поставщиками и потребителями, базового сырья при производстве строительных материалов, мощностей каналов передачи данных провайдерами сети ИНТЕРНЕТ, нагрузки распределенной вычислительной сети, объема работ производства и так далее.
Важным инструментом при построении эффективных методов решения задачи распределения ресурсов в иерархических системах транспортного типа оказалось исследование сводимости задачи распределения ресурсов к потоковым задачам и связанная с данными исследованиями разработка концепции сводимости.
Из отечественных ученых существенный вклад в развитие рассматриваемого в диссертационной работе класса задач внесли Голынтейн Е.Г., Канторович Л.В., Карзанов А.В., Подчасова Т.П., Юдин Д.Б., Шкурба В.В. и другие. Среди зарубежных ученых развитием этой области занимались Danzig G.L., Hitchcock F.L., Ни Т.С., Koopmans Т.С. и другие. Следует также отметить школу Нижегородского университета и ученых Батищева Д.И., Прилуцкого М.Х., Когана Д.И., Федосенко Ю.С., которые рассматривали подобные проблемы.
Цель работы
Целью диссертационной работы является построение общей математической модели распределения ресурсов в иерархических системах транспортного типа, исследование ее совместности, а также постановка оптимизационных задач распределения ресурсов в иерархических системах транспортного типа, построение методов решения поставленных оптимизационных задач и анализ их вычислительной сложности.
ь> Научная новизна
1. Построены общие математические модели распределения ресурсов в одноресурсной, многоресурсной и многоиндексной иерархических системах транспортного типа.
2. Проведено исследование построенных математических моделей
распределения ресурсов в иерархических системах транспортного типа,
построены алгоритмы проверки совместности и поиска допустимого
варианта распределения ресурсов.
3. Поставлена общая многокритериальная задача распределения ресурсов в
иерархических системах транспортного типа, применены схемы компромисса
решения поставленной многокритериальной задачи.
4. Построены эффективные алгоритмы решения поставленных
оптимизационных задач распределения ресурсов в иерархических системах
транспортного типа.
5. Сформулирована концепция сводимости, применяемая при построении
алгоритмов решения поставленных задач, основанных на сводимости к
потоковым задачам.
Теоретическая и практическая ценности работы
В рамках построенных математических моделей ставятся различные оптимизационные задачи распределения ресурсов в производственных системах, транспортных системах, сетях передачи данных и так далее.
Проведенные исследования выполнены в рамках Задания Минобразования РФ, номер госрегистрации 0120.0 506816 (2003-2006 гг.) -Тема НИР "Математическое моделирование и создание новых методов анализа динамических систем и систем оптимизации ".
Результаты диссертационной работы используются в учебном процессе
Нижегородского государственного университета им. Н.И. Лобачевского на факультете ВМК при преподавании курса «Моделирование сложных систем».
Апробаций результатов
Полученные в диссертационной работе результаты обсуждались на Всероссийской конференции «КоГраф 2002» (Н.Новгород, 2002 г.), Международных научно-практических семинарах «Высокопроизводительные параллельные вычисления на кластерных системах» (Н.Новгород, 2002 и 2003 г.), Нижегородских сессиях молодых ученых (Саров, 2003 и 2004 г.,
9 Нижний Новгород, 2004 г.), Научно-технической конференции ООО ТЕКОМ «Технические, программные и математические аспекты управления сложными распределенными системами» (Н.Новгород, 2003 г.), Юбилейной научно-технической конференции ВМК ННГУ и НИИ ПМК, «Математика и кибернетика 2003» (Н.Новгород, 2003 г.), VI международном конгрессе по математическому моделированию (Н.Новгород, 2004 г.), Конференциях «Технологии Microsoft в теории и практике программирования» (Москва, 2005 г., Н.Новгород, 2006 г.), Международной научной конференции, приуроченной к 200-летию со дня рождения Карла Густава Якоби (Калининград, 2005 г.), XIV международной конференции «Проблемы теоретической кибернетики» (Пенза, 2005 г.), научном семинаре отделения информатики университета г. Падерборна (Германия, г. Падерборн, 2005 г.), а также на научном семинаре кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ (2006 г.).
Разработанная программная система, составляющая прикладную часть диссертационной работы прошла апробацию при составлении план -графиков деятельности отделов ГУП ОКБМ им. И.И. Африкантова. Полученные результаты позволяют говорить об адекватности математических моделей, заложенных в основу созданного программного продукта, условиям реального производства.
Основные результаты, полученные в ходе выполнения диссертационной работы, отражены в 19 научных работах [3-15,56-59,81,82].
Структура и содержание работы
Работа состоит из введения, трех глав, заключения, списка используемой литературы и приложения.
Во введении отражена актуальность задач распределения ресурсов в иерархических системах транспортного типа, сформулированы цели исследования, показана научная новизна работы.
В главе 1 определено место задач распределения ресурсов в классе задач математического программирования. Рассмотрены основные
10 особенности задач распределения ресурсов, свойственные задачам распределения ресурсов в иерархических системах транспортного типа. Приведены содержательные постановки одноресурсной и многоресурсной задач, а также некоторых их частных подзадач, к которым в том числе относится многоиндексная задача распределения ресурсов. Рассмотрены примеры постановок задач распределения ресурсов в одноресурсной, многоресурсной и многоиндексной иерархических системах транспортного типа.
В главе 2 формализуется общая математическая модель распределения ресурсов в одноресурсной, многоресурсной и многоиндексной иерархических системах транспортного типа. Исследуется вопрос совместности математических моделей и предлагаются эффективные алгоритмы поиска допустимого варианта распределения ресурсов.
В главе 3 рассматривается общая многокритериальная задача распределения ресурсов в иерархических системах транспортного типа. В качестве схем компромисса при решении многокритериальной задачи распределения ресурсов рассматриваются аддитивные свертки в случае линейных функций предпочтения; лексикографическое упорядочивание в случае кусочно-постоянных функций предпочтения; а также максиминные (минимаксные) свертки в случае линейных или кусочно-постоянных функций предпочтения. Строятся алгоритмы решения рассматриваемых задач, Определяются классы задач, для которых построенные алгоритмы позволяют находить целочисленное решение.
В заключении подведены основные итоги проведенных в диссертационной работе исследований.
В приложении описана разработанная диалоговая программная система решения задач распределения ресурсов в иерархической системе транспортного типа, в которой реализованы описанные в диссертационной работе методы, приведены результаты вычислительных экспериментов.
Задачи распределения ресурсов как задачи линейного программирования транспортного типа
В случае, когда в задаче распределения ресурсов область допустимых решений представляет собой выпуклый многогранник, а критерий задачи является линейной функцией, задача может быть рассмотрена как задача линейного программирования. Задачи распределения ресурсов, формализуемые в виде задач линейного программирования, рассматривались, например, в работах [2,41,46,47].
Задачи линейного программирования являются частным случаем задач выпуклого программирования и в каноническом виде записываются следующим образом; Q(x) = (х, с) - min, Ax = b, (1.3) х 0, где А = atj шхп - матрица действительных чисел (называемая матрицей ограничений); Ъ m-мерный вектор действительных чисел (называемый вектором правых частей); Q(x) - функция, определяемая как скалярное произведение векторов х и с (называемая целевой функцией); с - -мерные вектор действительных чисел (вектор коэффициентов целевой функции); х j і п-мерные вектор неизвестных.
Особое место в классе задач линейного программирования занимают задачи линейного программирования транспортного типа [23,27]. В задачах данного класса матрица ограничений А такова, что а у є {0,1,-1}, і = \m,j = \,n.
К классу задач линейного программирования транспортного типа в частности относятся и рассматриваемые в данной диссертационной работе задачи распределения ресурсов. Одни из первых работ, посвященные исследованиям задачи распределения ресурсов в иерархических системах транспортного типа, были связаны с классической транспортной задачей [27,87,90,94,99,106,107,112], в более общих постановках подобные задачи распределения ресурсов рассматривались, например, в работах [1,26,37,64,66,73,84,85,97,105].
Важным подклассом задач линейного программирования транспортного типа является класс многоиндексных задач линейного программирования транспортного типа, исследованиям которого посвящены работы [34,68].
Для решения задачи линейного программирования может быть использован, например, симплекс-метод. Работа данного метода основана на следующей теореме:
Теорема [52]. Линейная функция, определенная на выпуклом /7-мерном многограннике, достигает наибольшего значения в вершине этого многогранника; если линейная функция достигает наибольшего значения О более чем в одной вершине, то она достигает такого же значения в любой точке, являющейся выпуклой линейной комбинацией этих вершин.
Таким образом, алгоритм заключается в перемещении по вершинам п-мерного многогранника ограничений. Недостатком данного метода является то, что верхняя оценка вычислительной сложности данного метода является экспоненциальной [118]. Более того, в настоящее время для всех известных модификаций симплекс-метода построены экспоненциальные по числу итераций примеры.
Однако класс задач линейного программирования относится к классу полиномиально разрешимых задач, доказательством чего являются полиномиальные алгоритмы решения задачи линейного программирования, например, метод эллипсоидов, предложенный Хачияном, [70,75], или алгоритм Кармаркара, [70,104]. Отметим, что в общем виде данные алгоритмы не являются сильнополиномиальными. Однако в случае, когда коэффициенты матрицы ограничений задачи линейного программирования по модулю не превосходят некоторого заданного значения (примером является класс задач линейного программирования транспортного типа), данные алгоритмы являются сильнополиномиальными.
Особое место среди задач линейного программирования транспортного типа занимают задачи, в которых матрица ограничений А абсолютно унимодулярна, то есть любой минор матрицы А равен 0, 1 или -1. С задачами данного класса связана следующая теорема:
Теорема [29]. Выпуклый многогранник системы ограничений задачи (1.3) имеет целочисленные крайние точки при любом целочисленном векторе Ь тогда и только тогда, когда матрица А абсолютно унимодулярна.
Существуют различные методы проверки свойства абсолютной унимодулярности матриц [71]. Примером достаточных условий абсолютной унимодулярности матрицы является следующее условие: - каждый элемент матрицы равен 0, 1 или -1; - каждый столбец матрицы содержит не более двух ненулевых элементов; - строки матрицы можно разбить на два непересекающихся множества R; и i?2 таким образом, что если столбец матрицы содержит два ненулевых элемента одного знака, то один из них входит в Rh а другой в Rf, если столбец матрицы содержит два ненулевых элемента с противоположенными знаками, то оба они входят либо в Rj, либо в R2.
Многоресурсные задачи распределения в иерархических системах транспортного типа
Рассмотрим многоресурсную иерархическую систему. В отличие от одноресурсного случая в многоресурсной иерархической системе распределяются ресурсы различных типов. Для каждого из типов ресурсов элементы системы разбиваются на три группы: - производители ресурсов определенного типа, - элементы, передающие ресурсы определенного типа, - потребители ресурсов определенного типа.
Ресурсные ограничения элементов системы в случае многоресурсной иерархической системы заключаются в том, что - производители ресурсов определенного типа способны произвести лишь ограниченный объем ресурсов соответствующего типа, - элементы, передающие ресурсы определенного типа, полностью передают весь полученный ими объем ресурсов соответствующего типа, - потребители ресурсов определенного типа должны получить ограниченный объем ресурсов соответствующего типа.
Таким образом, ресурсные ограничения элементов представляют собой балансные ограничения, связанные с ресурсами каждого определенного типа. Ресурсные ограничения связей между элементами системы разделяются на ограничения двух видов: - пропускные способности, связанные с ресурсами определенного типа, - суммарные пропускные способности.
Ограничения пропускных способностей, связанных с ресурсами определенного типа, заключаются в том, что связи способны передать лишь ограниченный объем ресурсов соответствующего типа. Ограничения суммарной пропускной способности заключаются в том, что связи способны передать лишь ограниченный суммарный объем ресурсов всех типов.
Ограничения суммарных объемов ресурсов, как и в случае одноресурсной иерархической системы, заключаются в ограничениях величин различных суммарных объемов циркулирующих в системе ресурсов.
Как и в одноресурсном случае предполагается, что в системе присутствуют так называемые контролируемые элементы, с которыми связаны функции предпочтения, определяющие условия эффективного функционирования иерархической системы. Однако содержательная интерпретация функций предпочтения может отличаться от одноресурсного случая.
Тогда задача заключается в распределении ресурсов таким образом, чтобы были выполнены все ограничения многоресурсной иерархической системы, и распределение удовлетворяло эффективной схеме функционирования системы.
Заметим, что рассматриваемая задача является обобщением задачи распределения ресурсов в случае одноресурсной иерархической системы.
В качестве примера задачи распределения ресурсов в многоресурсной иерархической системе транспортного типа рассмотрим транспортную задачу с промежуточными пунктами [68,113].
Транспортная задача с промежуточными пунктами
Имеются пункты производства, промежуточные пункты и пункты потребления различных видов продукции. Продукция передается из пунктов производства в пункты потребления через промежуточные пункты посредством связей между пунктами. Необходимо определить план перевозки продукции.
Пусть заданы максимально возможные объемы производства каждого из видов продукции каждым пунктом производства; минимально допустимые и максимально требуемые объёмы потребления каждого из видов продукции каждым пунктом потребления; максимально возможные объёмы перевозки каждого из видов продукции из одного пункта в другой; максимально возможный общий объем всей продукции, который каждый из пунктов потребления способен разместить.
Предполагается, что каждый из пунктов потребления высказывает некоторые предпочтения относительно объемов полученной им продукции каждого из видов, ранжирую отклонение полученного объема продукции от желаемой величины. Требуется определить план перевозки, удовлетворяющий пожеланиям пунктов потребления наилучшим образом.
Пусть S - множество пунктов производства, С - множество промежуточных пунктов, U - множество пунктов потребления, К множество видов продукции, Н - множество связей между пунктами.
Структура сети определяется ориентированным графом G = (SUC JU,H) без петель и контуров, в котором, Яс5хСиСхСиСх(/.
Обозначим через Aik - максимально возможный объем производства продукции вида к пунктом производства /, ieS, кеК; BJk,B k - минимально допустимый и максимально требуемый объёмы потребления продукции вида к пунктом потребления / , і ell, кеК; Д - максимально возможный общий объем всей продукции, который способен разместить пункт потребления І, iell; Еук максимально возможный объём перевозки продукции вида к из пункта і в пункту, (i,j)eH, кеК.
Каждый из пунктов потребления і задает функции предпочтения %ікь определяющие «качество» отклонения объема продукции вида к от некоторой желаемой величины, ie Uj eK.
Тогда будем рассматривать задачу определения плана перевозок, которая заключается в определении таких величин Хук, где Хдк - объем продукции вида к, который будет перевезен из пункта і в пункту, (/,_/)еН, кеК, для которых выполняются ограничения:
Исследование общей математической модели распределения ресурсов в одноресурсных иерархических системах транспортного типа
Система ограничения общей математической модели (2.1)-(2.3) представляет собой систему линейных алгебраических неравенств, поэтому для проверки совместности иерархической системы и поиска допустимого варианта распределения ресурсов могут быть использованы классические результаты общей теории конечных систем линейных неравенств.
Под системой линейных неравенств понимается система /у( )-я, 0,; = 1 , (2.4) где ff(x) - линейные функции со значениями из R, xeRq, а,-- свободные члены, ajeR, j = l,p. При этом система (2.4) может быть записана в следующем виде: fj(x)-aj aj\x\ +aj2x2+... + ajqxq-aj Q, j = l,p, (2.5) гдео єР, j = l,p9 i = l,q.
Заметим, что система ограничений общей математической модели (2.1)-(2.3) соответствует системе линейных неравенств (2.5) при q-mb р - 2(п + т + s).
Теорема [78]. Необходимым и достаточным условием совместности системы линейных неравенств (2.5) ранга г 0 является существование в матрице ее коэффициентов такого отличного от нуля минора . a j\h А = aii aii a Jih r-ro порядка, что выполняются соотношения Jrl\ Jrl2 Jrlr Однако проверка данных условий не может быть использована в качестве эффективного алгоритма проверки совместности иерархической Г/-1Г ЯР системы, так как в матрице коэффициентов системы (2.5) существует С С миноров порядка г.
Теорема [72]. Система (2.5) тогда и только тогда несовместна, когда существуют такие неотрицательные числа Pi,p2,—,Pр, при которых имеют место тождественное относительно х є Rq соотношение ipjfj$) = o и неравенство р Ел«7 0 (2.6) (2.7) Данная теорема также может быть использована в качестве критерия совместности иерархической системы. Однако отсутствие общих эффективных методов решения систем вида (2.6)-(2.7) сужает область практического применения теоремы, как критерия проверки совместности иерархической системы. Применение итерационных методов решения систем линейных неравенств С другой стороны существуют различные итерационные алгоритмы решения систем линейных неравенств, примером которых является метод ортогональных проекций Агмона-Моцкина [83,111]. Метод ортогональных проекций Агмона-Моцкина решения систем линейных неравенств заключается в следующем: пусть нам необходимо найти решение системы ч (2.8) Ф) = а +Ь( 0,1 = 1,р,хеКд. 7=3
Выберем произвольный вектор х{0) eRq. Далее предположим, что известен вектор 5rv\ тогда обозначим через / множество номеров линейных неравенств рассматриваемой системы, которые не выполняются при выбранном векторе х 1 : І = {і\Ц(х(у)) 0,і = її}. Если I = 0, то задача решена, иначе будем вычислять значение индекса /0 по следующей формуле: i0 = argmax ч Тогда очередной вектор итерационного алгоритма определяется следующим образом: :(v+l) _ n(v) X = хк + где h = z(v) о h&v ) а через вектор а{ обозначается вектор с компонентами I J=i (aa,al2,...,aiq). Данный итерационный алгоритм основан на следующей теореме Агмона-Моцкина:
Теорема [83]. Если система (2.8) совместна, то описанный итерационный процесс сходится к решению системы.
Система (2.1)-(2.3) представляет собой систему линейных двусторонних неравенств транспортного типа, для исследования которой Р0ШШШЗ может быть рассмотрена модификация метода ортогональных проекций Агмона-Моцкина, учитывающая данную специфику.
Рассмотрим систему линейных двусторонних неравенств транспортного типа где подмножества N ,Nt определяют компоненты вектора х, которые входят в уравнение / с коэффициентами 1,-1, соответственно, N п ]\ГГ = 0, Nf9N;Q{l92..9q},i = l,p. Выберем произвольный вектор х(0) є Rq. Далее предположим, что известен вектор эгу\ тогда обозначим через s номер первого по порядку ограничения, условия которого нарушены. Если такое ограничение не может быть найдено, то задача решена. Иначе вектор х у+г определяется следующим образом
Применение сводимости для построения алгоритмов решения задачи распределения ресурсов в иерархических системах транспортного типа с аддитивными схемами компромисса
Для решения задачи W\, в случае ее сводимости к задаче Z2, могут быть использованы алгоритмы решения задачи L\, соответствующей задаче L2.
Определение 11. Задачей L\(L2) в канонической транспортной Т\(Т2), соответствующей задаче L2 в транспортной сети Г2, называется задача поиска потока заданной величины v= минимальной стоимости с дуговыми стоимостями, определенными следующим образом; е.. = и.., (ij)eA2, остальные дуги имеют нулевые стоимости.
Теорема 10. Пусть поток / является решением задачи L\(L2), тогда циркуляция g, g.. = /, + b-j, (ij)eA2, будет являться решением задачи L2.
Доказательство. На основании следствия 1 циркуляция g будет являться допустимой циркуляцией транспортной сети Т2. Заметим, что стоимость циркуляции g составляет Г f./u.. + Ь(1-Ыд , а стоимость потока (LJ)eV2 (i.J)eV2 /составляет J] fyU,. Покажем, что построенная циркуляция является оптимальным решением задачи L2. Действительно, если это не так, то существует допустимая циркуляция сети Т2 со стоимостью меньшей, чем ХЛМЇ/+ ХХ У Тогда из конструктивного доказательства теоремы 1 (i,j)eV2 (i,j)eV2 следует, что мы можем построить поток величины v в канонической транспортной сети Т\{Т2) такой, что стоимость данного потока будет меньше fuuij Что противоречит тому, что поток/является решением задачи L\. (iJ)eV2 Таким образом, циркуляция g является решением задачи L2. Теорема доказана.
Обзор методов решения задачи L\ приведен в работах [77,96]. В частности для решения задачи L\ может быть применен сильнополиномиальный алгоритм Галиля и Тардоша [93], который имеет вычислительную сложность 0(1 Ух 2 log Vx ( Ах +1 Vx log Vx )). Таким образом, на основании теоремы 10 и учитывая замечания, сделанные в главе 2 о количестве узлов сети ТХ(Т2), мы приходим к алгоритму решения задачи L2, основанному на решении задачи L\ в канонической транспортной сети Т](Т2), который имеет вычислительную сложность 0(\V2\2\og\V2\(\A2\ + \V2\log\V2\)).
В случае одноресурсной иерархической системы с ограничениями объемов ресурсов, соответствующих элементам системы, решение задачи W\, согласно теореме 7, сводится к решению задачи L2 в транспортной сети T2{G). Тогда, учитывая замечания, сделанные в главе 2 о количестве узлов сети T2{G), мы приходим к алгоритму решения задачи W\, основанному на решении задачи L2 в транспортной сети T2(G), который имеет вычислительную сложность 0(nA\ogn).
В случае многоресурсной иерархической системы с ограничениями объемов ресурсов, соответствующих элементам системы, при отсутствии суммарных пропускных способностей решение задачи W\, согласно следствию 5, связано с решением г независимых задач W\ в одноресурсной иерархической системе с ограничениями объемов ресурсов, соответствующих элементам системы. Таким образом, мы приходим к алгоритму решения задачи W\, который имеет вычислительную сложность 0(rn4 logn).
В случае многоресурсной иерархической системы древовидной структуры с ограничениями объемов ресурсов, соответствующих элементам системы, решение задачи W\, согласно теореме 8, сводится к решению задачи L2 в транспортной сети Т2(г). Тогда, учитывая замечания, сделанные в главе 2 о количестве узлов сети Т2(г), мы приходим к алгоритму решения задачи W\, основанному на решении задачи L2 в транспортной сети T2(G), который имеет вычислительную сложность 0(n3r3 log2(nr)).
В случае многоиндексной иерархической системы при выполнении условий теоремы 9 решение задачи W\(M), согласно теореме 9, сводится к решению задачи Ь2 в транспортной сети Т2(М). Тогда, учитывая замечания, сделанные в главе 2 о количестве узлов сети Т2(М), мы приходим к алгоритму решения задачи W\, основанному на решении задачи Ь2 в транспортной сети Т2(М), который имеет вычислительную сложность 0(1 EtfrS) log [ EN,S) ).
Отметим, что в ходе выполнения диссертационной работы была реализована диалоговая программная система решения задачи W\, в случае ее сводимости к задаче L2 (см. приложение).
Целочисленный случай
Теорема 11. Если задача линейного программирования Р сводится, сохраняя соответствие между переменными, к задаче L2, то матрица ограничений задачи Р абсолютно унимодулярна.
Доказательство. Доказательство проведем от противного. Предположим, что задача линейного программирования Р сводится, сохраняя соответствие между переменными, к задаче Ьъ но матрица ее системы ограничений не абсолютно унимодулярна.
Условия абсолютной унимодулярности, в случае целочисленного вектора правых частей системы ограничения задачи Р, являются необходимыми и достаточными для целочисленности всех вершин многогранника, соответствующего системе ограничений задачи [29]. Тогда можно построить такую линейную целевую функцию, что задача линейного программирования будет иметь единственное оптимальное не целочисленное решение. По условию теоремы задача линейного программирования сводится к задаче L2, для которой, согласно теореме о целочисленности потока, всегда существует оптимальное целочисленное решение (если задача имеет решение) [74]. Полученное противоречие доказывает теорему. Теорема доказана.
Утверждение 6. Абсолютно унимодулярны матрицы, соответствующие следующим системам ограничений: - системе (2.1),(2.2),(2.9); - системе (2.19),(2.20),(2.23); - системе (2.24)-(2.28); - системе D{M) в случае выполнения условий теоремы 9.
