Потоковые методы решения многоиндексных задач транспортного типа тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

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

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

Специальность: 01.01.09 Дискретная математика и математическая кибернетика

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

1 з пар 2т

Нижний Новгород 005546039 2013

005546039

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

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

ПРИЛУЦКИЙ МИХАИЛ ХАИМОВИЧ

доктор технических наук, профессор, заведующий кафедрой информатики и автоматизации научных исследований ФГБОУ ВПО «Нижегородский государственный университет им. Н.И. Лобачевского»

БОНДАРЕНКО ВЛАДИМИР АЛЕКСАНДРОВИЧ доктор физико-математических наук, профессор, заведующий кафедрой дискретного анализа ФГБОУ ВПО «Ярославский государственный университет им. П.Г. Демидова»

ЛАЗАРЕВ АЛЕКСАНДР АЛЕКСЕЕВИЧ

доктор физико-математических наук, профессор, заведующий лабораторией теории расписаний и дискретной оптимизации ФГБУН «Институт проблем управления им. В.А. Трапезникова Российской Академии наук»

МАЗАЛОВ ВЛАДИМИР ВИКТОРОВИЧ

доктор физико-математических наук, профессор, директор ФГБУН «Институт прикладных математических исследований Карельского научного центра Российской академии наук»

Математико-механический факультет ФГБОУ ВПО «Санкт-Петербургский государственный университет»

Защита состоится «Э.? » 2014 года в <£¡00на заседании Диссертационного

совета Д 002.017.02 при Федеральном государственном бюджетном учреждении науки «Вычислительном центре им. A.A. Дородницына Российской академии наук» по адресу: 119333, г. Москва, ул. Вавилова, дом 40, конференц-зал.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН. С текстом автореферата можно ознакомиться на официальном сайте ВЦ РАН http://www.ccas.ru/.

Автореферат разослан «14 ». 2014 года.

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

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

Ученый секретарь

диссертационного совета Д 002.017.02, д.ф.-м.н., профессор

В.В. Рязанов

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

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

Степень разработанности проблемы в литературе. Многоиндексные задачи линейного программирования транспортного типа относятся к полиномиально разрешимому классу задач линейного программирования. Таким образом для решения многоиндексных задач линейного программирования транспортного типа могут быть применены общие методы исследований задач линейного программирования, например, симплекс метод, алгоритм Кармаркара. Существует ряд работ, посвященных непосредственно методам решения многоиндексных задач линейного программирования транспортного типа. Наиболее изученным является класс двухиндексных задач. В многоиндексном случае (число индексов не менее трех) наибольшее внимание уделено двум классам задач: многоиндексные аксиальные задачи и многоиндексные планарные задачи. Известны исследования в смежных

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

Особый интерес представляет решение многоиндексных задач целочисленного линейного программирования транспортного типа, относящихся к классу задач целочисленного линейного программирования. В общей постановке класс целочисленных многоиндексных транспортных задач является МЯ-трудным уже в трехиндексном случае. Более того для задач данного класса не существует полиномиальных г-приближенных алгоритмов, иначе Р=ИР, данный результат также справедлив уже в трехиндексном случае. Класс целочисленных многоиндексных задач, как подкласс задач целочисленного линейного программирования, содержат ряд известных полиномиально разрешимых подклассов: задачи, матрица систем ограничений которых является абсолютно унимодулярной, задачи с фиксированным числом переменных, задачи 14-кратного целочисленного программирования. При отсутствии дополнительных ограничений на параметры для решения многоиндексных задач целочисленного линейного программирования транспортного типа применимы лишь экспоненциальные по верхней оценке вычислительной сложности общие методы целочисленного линейного программирования, например, метод динамического программирования, метод ветвей и границ, метод отсечения Гомори.

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

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

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

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

Из ученых существенный вклад в развитие рассматриваемого в диссертационной работе класса многоиндексных задач внесли Гимади Э.Х., Гольштейн Е.Г., Емеличев В.А., Канторович Л.В., Кириченко И.О., Кравцов М.К., Прилуцкий М.Х., Раскин Л.Г., Сергеев С.И., Сигал И.Х., Цурков В.И., Юдин Д.Б., Burkard R.E., Danzig G.L., De Loera J., Koopmans T.C., Onn S„ Spieksma F.C.R. и др. Существенный вклад в развитие методов сетевой оптимизации, применяемых в работе при исследовании многоиндексных задач, внесли Диниц Е.А., Карзанов A.B., Новикова Н.М., 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. Полученные результаты сводимости обобщаются при исследовании более широкого класса схем сводимости. В рамках схемы сведения с сохранением целочисленности установлен критерий сводимости, справедливый при выполнении известной гипотезы о неравенстве классов Р и ЫР.

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

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

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

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

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

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

Теоретическая и практическая значимость исследования.

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

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

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

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

Результаты диссертационной работы используются в учебном процессе Нижегородского государственного университета им. Н.И. Лобачевского на факультете ВМК при преподавании курсов «Моделирование сложных систем», «Модели и методы эффективного использования распределенных вычислительных систем» и спецсеминара магистров кафедры ИАНИ

Апробация результатов исследования. Полученные в диссертационной работе результаты обсуждались на Всероссийской конференции КоГраф (Н.Новгород, 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 г.); Международной научной конференции «Параллельные вычислительные

' Афраймович Л.Г. Прилуцкий М.Х. Методические указания для самостоятельной работы студентов по курсу «Моделирование сложных систем» при изучении темы «Распределение ресурсов в многоиндексных иерархических системах». - Нижний Новгород: Нижегородский государственный университет. 2006.

Афраймович Л.Г. Прилуцкий М.Х. Распределение ресурсов в иерархических системах транспортного типа. Учебно-методический материал по программе повышения квалификации «Новые подходы в исследованиях и разработках информационно-телекоммуникационных систем и технологий». - Нижний Новгород: Нижегородский госуниверситет. 2007.

Афраймович Л.Г. Учебно-методическое пособие по курсу «Модели и методы эффективного использования распределенных вычислительных систем» при изучении темы «Задачи статической балансировки». - Нижний Новгород: Нижегородский госуниверситет. 2011.

технологии» (Нижний Новгород, 2009 г.); VIII Международной конференции «Дискретные модели в теории управляющих систем» (Москва, 2009 г.); X Международном семинаре «Дискретная математика и ее приложения» (Москва,2010 г.), Одесском семинаре по дискретной математике (Одесса,2011 г.).

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

Структура и объем работы. Работа состоит из введения, пяти глав, заключения, списка литературы и приложений. Общий объем работы составляет 181 страницу, включая 14 рисунков. Список литературы включает 178 наименований.

Публикации. Основные результаты, полученные в ходе выполнения диссертационной работы, отражены в 41 научной работе, в том числе в 11 статьях, опубликованных в ведущих рецензируемых научных журналах (Автоматика и телемеханика, Известия РАН. Теория и системы управления, Управление большими системами, Вестник Нижегородского университета им. Н.И. Лобачевского) из списка, рекомендованного ВАК.

Все основные результаты, выносимые на защиту, получены автором самостоятельно.

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

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

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

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

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

При постановке многоиндексных задач транспортного типа воспользуемся следующей формализацией. Пусть seN и Щ.г) = { 1,2,...,.у}. Каждому числу / поставим в соответствие параметр , называемый индексом, который принимает значения из множества J! = {1,2,...,}, где > 2, I е N(.4).

Там где это не вызывает неоднозначности, будем отождествлять номер индекса / и индекс у',. Пусть / = {к1,к2,...,к,} с N0); / = ¡,¿-1. Набор

значений индексов 7*} = (Л ,Л2'Л,)/ будем называть /-индексом. Множество всех /-индексов, соответствующих /, определим как £у = ^е/* хУ^ Там где это не вызывает неоднозначности,

будем опускать нижний индекс / и записывать /-индекс как л, •

Компоненту у',, набора ^ будем обозначать (0 = Л, г € /. Пусть тогда обозначим /у = (У7/-)/-, если /у е Ту, и

У7/'(0 = /у (/), / е /'. Если 6 Ег, /у е , где /', / ' с Ж*) и /' п /' = 0, то через /у/у обозначим такой набор, что ^>/у е и/" и (Ту/у)/' = 7у, (^./у)/-=7у. Далее определим / = \/, тогда согласно введенному обозначению ЕМ(з)=Е^Еу, если и Еу=(Еыи))у. Пусть

М с , тогда будем обозначать М = {/1 / е М}.

Каждому набору поставим в соответствие действительное число , € Ту. Данное отображение множества /-индексов в множество

действительных чисел назовем /-индексной матрицей и обозначим через {г^}. Рассмотрим ¿-индексную матрицу {¿дг^)} и введем следующее обозначение

Е = X - Е ^гуру^Еу.

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

Пусть М - заданное множество, М с2Л'<5); {аР-}, {Ьг_} - заданные | / |-индексные матрицы свободных коэффициентов, 0 < су ^ Ьр., Еу е Е-;, / еМ; {с^- ^} - заданная ¿-индексная матрица коэффициентов целевой функции; {.у } - ¿-индексная матрица неизвестных. Тогда многоиндексная задача

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

аг_ < X хР/Г_ <Ьр_,Р7еЕ7,/еМ, (3 1)2

F;*Ef

rms) - '

У е., X, —»min.

^0.^(5)6^(5). (3.2)

FF (33>

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

В ряде задач i-ипдексная матрица коэффициентов целевой функции {cFjv( )} имеет декомпозиционную структуру и может быть представлена в виде

подсуммы многоиндексных матриц меньшей размерности. Пусть Н с 2N(S) и заданы | Н | многоиндексных матриц коэффициентов {dFf }, / еН, что

CFmi) = Е d(.FNU))f ' FN(s)eEN(s)-fzH

Тогда рассмотрим целевую функцию следующего вида:

ЕУ"1 dIF ч xF —»min. л\

F fF f?H NU> f (3"4)

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

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

d(Fms))r ^ X diFms))f . FNM е ENU) , /' е Я.

(3.5)

/еЯ\{Я

2 Нумерация формул, определений, теорем, следствий и утверждений в автореферате соответствует принятой в диссертации.

Подкласс задач класса W(M,H), удовлетворяющих условию (3.5), при фиксированных множествах MuH будем обозначать W(M,AH).

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

Будем добавлять нижний индекс X к обозначению класса многоиндексных задач, если дополнительно выполняется условие целочисленности (3.6). Тогда соответствующие классы систем целочисленных линейных неравенств (3.1),(3.6), задач целочисленного линейного программирования (3.1),(3.6),(3.3) и задач целочисленного линейного программирования (3.1),(3.6),(3.4) при фиксированных множествах М и Я будем обозначать через 07 (М), \У7 (М) и 1У2(М,#) соответственно.

Рассмотрим задачу исследования несовместной многоиндексной системы линейных неравенств транспортного типа. Пусть многоиндексная система (3.1),(3.2) несовместна. Введем вспомогательные обозначения. Обозначим через (иьг_.) параметр, принимающий значение 1, если для

соответствующего неравенства (3.1) разрешено изменение нижней (верхней) границы, и значение 0 в противном случае; еаг_ (е\_) - штраф за изменение на единицу нижней (верхней) границы соответствующего неравенства (3.1), еар_,еьг_ >0; уаР_ (уьР_) - неизвестная величина, на которую будет изменена

нижняя (верхняя) граница соответствующего неравенства (3.1), РуеЕу, / е М. Тогда задача исследования несовместной многоиндексной системы заключается в определении многоиндексных матриц неизвестных }, {Уу-}, / еМ и {хГц,,}' являющихся решением следующей задачи линейного программирования:

%s) GZ+' FN(s) eEN(s)-

(3.6)

aF -uaF yaF < X <bF +ubF ybF F-^EjJ^M,

' FfsE/

(3.7)

yaFj,ybFj >0,F7eE-f, feM,

(3.8)

>0, FN(s)zEN,s), (3.9)

Z Z {eaFlu%y%+e%ubF ybF )->rmn. f- 10)

fsM FjgEj 1 ' \ • >

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

Рассмотрим многокритериальную многоиндексную задачу с кусочно-постоянными критериями оптимальности. Пусть М,Н с 2N(S> и множество М определяет систему многоиндексных неравенств транспортного типа (3.1),(3.2), множество Н определяет кусочно-постоянные критерии, формализация которых приводится далее. Пусть P(H) = {(f,F^)\F^ eEj,feH}. Для каждой

из пар (/, Fj-) определим р +1 вложенных сегментов , 1 = 0, р, что

с^», / = 0,р-1, ^ =[-оо,+оо], (/,^)еР(Я). Пара (/,^)еР(Я) определяет следующую функцию предпочтения

[г, еслиIVе и к>£ где г е {1,2,...,/?}, 10, если н> е 5 .

„roí

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

(3.1),(3.2) и минимизирующей функции предпочтения

Е * )^пип, (/,^)еЛЯ). (3.11)

Класс многокритериальных задач (3.1),(3.2),(3.11) будем обозначать и{М,Н). Применим для решения поставленной многокритериальной задачи следующие схемы компромисса: лексикографическое упорядочивание критериев оптимальности, соответствующий класс задач обозначим £/^(М,Н), и максиминную свертку, соответствующий класс задач обозначим ит.Ахтт(М,Н).

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

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

Пусть А е /?"У"\ Ь,Ь~,Ь+ ей", с е /?"! - заданные параметры, .сеГ -вектор неизвестных. Через ы(А,Ь,с) будем обозначать задачу линейного

программирования т1п{(с,л)|Ах<Ь,х>0}-, через \ь{А,Ь~,Ь+ ,с) - задачу линейного программирования тт{(с,л:)|&~ < Ах<Ь+,х>0}. Для удобства через пго\\(А) и псо1(А) будем обозначать количество строк и столбцов матрицы А соответственно. Далее рассмотрим два класса задач линейного программирования V/' и V/". На содержательном уровне под сводимостью класса к классу \У понимается возможность построения для произвольной задачи и>' е IV соответствующей задачи и" е таким образом, чтобы решение задачи н>" определяло решение задачи -м'. При формализации конкретной схемы сведения будем определять временные затраты и (или) конкретные вычислительные процедуры, связанные с:

- построением матрицы системы ограничений задачи м? по исходным параметрам задачи м?;

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

- построением решения задачи м>' по решению задачи .

Определение 3.1. Будем говорить, что класс IV' является \12 -5з сводимым к классу , если для любой задачи

ы - МА\Ь',с') е И7' можно за время 0(/,) с использованием процедуры ^ построить матрицу А", за время 0(Г2) с использованием процедуры s2 построить векторы Ъ", с", что = н>(А",Ь",с")<=\¥" и при этом

- задача и>' совместна (ограничена) тогда и только тогда, когда совместна (ограничена) задача и";

- если известно оптимальное (допустимое) решение х" задачи у/, то оптимальное (допустимое) решение х' задачи и>' может быть построено за время 0(г3) с использованием процедуры 5-3.

Здесь 5], - 52, 53 - строковые обозначения вычислительных процедур, связанных с построением матрицы системы ограничений, свободных

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

Замечания. Опционально будем опускать записи вычислительных затрат {¡, /2> ¡з и (или) записи обозначений вычислительных процедур , л-2, если при сведении не конкретизируются соответствующие вычислительные затраты и (или) вычислительные процедуры. Задачу (см. определение 3.1) будем называть задачей, соответствующей задаче и/. Решение х (см. определение 3.1) будем называть решением, соответствующим решению х". При определении вычислительных затрат , /2, ?3, если не оговорено иного, будем оценивать, количество вычислительных операций на машине с произвольным доступом к памяти. Иногда для удобства функции оценки вычислительной сложности /2, г3 будем заменять обозначениями Ь или Р, подразумевая линейные или полиномиальные функции от размера матрицы А', соответственно. В случае, когда при определении г2, г3 оценивается вычислительная сложность рассматриваемых вычислительных процедур, будем добавлять верхний индекс «*» в записи соответствующих оценок. В частности будем писать или Р*, когда речь идет о линейной или полиномиальной оценках вычислительной сложности как функции размера индивидуальной задачи соответственно.

В работе исследуется возможность сведения класса многоиндексных задач линейного программирования транспортного типа к классу задач поиска потока в сети. В качестве потоковой задачи будем рассматривать задачу поиска потока (циркуляции) минимальной стоимости в сети. Приведем далее известную постановку соответствующей потоковой задачи. Пусть задан ориентированный граф без петель С = (уа,Аа), Ла с Уд. Обозначим через и вц заданные значения нижней пропускной способности, верхней

пропускной способности и стоимости дуги (/,}) соответственно, 0 < < , через Хц обозначим поток вдоль дуги (/,_/), (г,/) е А. Тогда задача заключается в нахождение значений Ху, (г, ]) е А, являющихся решением следующей задачи линейного программирования:

ХЛ' " 2>;« = е ^(7.

а.ЛеА (Л/)еА

Z ^//->min,

(¿J)eAc

обозначаемой далее j) e Лд). Класс задач поиска потока

минимальной стоимости будем обозначать WGraph. Класс задач поиска потока минимальной стоимости в древовидной сети будем обозначать WTree.

Далее в работе исследуются вопросы г, - 112 — s2113 - s3 сводимости классов многоиндексных задач W(M) и W(M,H) к классам задач поиска потока в сети WCraph и WTree. Применяемые при исследовании сводимости вычислительные процедуры 5,, s2, s3 будут определены далее в работе при описании рассматриваемых схем сведения. Результаты исследования сводимости будут применены в работе при построении алгоритмов решения поставленных многоиндексных задач D(M), W{M), W(M,H) (и соответственно DZ(M), W7(M) и WZ(M,H)), а также S(M), UJM,H) и Um3xmjn(M,H).

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

Введем схему f, \t2 - equal] t3 -edge сводимости, которая применяется в данной главе при исследовании сводимости многоиндексных задач к классу задач поиск потока в сети. Основные особенности предлагаемой схемы:

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

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

Таким образом, рассматриваемая схема сведения является частным случаем схемы описанной в определении 3.1, для которой s2 = equal, s3 =edge.

Определение 4.1. Пусть W - класс задач линейного программирования с двусторонней системой линейных неравенств. Будем говорить, что класс W является | t2 -equal | /3 - edge сводимым к классу W' cz WGraph, если класс W

является f[ 112 | f3 сводимым к классу W и дополнительно произвольная задача w = w(A,b~ ,b+,с) eW, а также соответствующая ей задача Z = ZMCC(G',lij,uij,ejj(i,j)BAG)eW' удовлетворяют следующим условиям. Найдутся такие инъективные функции а :{l,...,/iron(A)} Р: {\,...,ncol{A)} -> Aq, что

" la(i)=K>ua(i)=bt> i = l,nrOW(A)- /(„ >у) = 0,U(uv) =Ь*,

(u,v)eAG\[a(i)\i = \,nrow(A)},r№5 Ь* = £ \

к=1

- ^(о = с;. г" = Ьисо/ (А); е(ц v) = 0, (и, v) е Лс \ {/?(г) \ i = 1 ,ncol(A)};

- если Xjj, ((', у) е Лд, является оптимальным (допустимым) решением задачи г, то (хр(\у—>хр(пСо1(А))) будет являться оптимальным (допустимым) решением задачи w, соответствующим решению задачи z ■

Далее в данной главе рассматриваются вопросы f, 112 —equal \ f3 — edge сводимости класса W(M) к классам WGraph и WTree, а также обобщение

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

При исследовании ty 112-equal] t3-edge сводимости класса W(M) к классу WCraph были получены следующие основные результаты.

Определение 4.2. Множество М, М с 2'V(5), называется к-вложенным, если существует разбиение множества М на к подмножеств Mi ={//'',•.•,/„.'}, i = й, ЧТО /f с /Д , j = i=u.

Теорема 4.2. Пусть М с 2'v(s). Для того чтобы класс W(M) являлся L] L-equal\ L-edge сводимым к классу WGraph достаточно, чтобы множество М было 2-вложенным.

Теорема 4.4. Пусть Мс2вд. Для того чтобы класс W(M) являлся ^ 112 - equally- edge сводимым к классу WGmph необходимо, чтобы множество М было 2-вложенным.

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

Утверждение 4.1. Пусть множество М с 2'V(i) является 2-вложенным, тогда существует алгоритм решения задач класса W(M) и класса \VZ(M)

(систем класса D{M) и класса DZ(M)), требующий 0(\ ENis) |2 log21 Еш I)

Enu) I2 '°21 ^N(s) I)) вычислительных операций.

Утверждение 4.4. Пусть множество М с 2'v<!) является 2-вложенным, тогда существует алгоритм решения задач класса S(M), требующий

ENU) I log21 En(s) I) вычислительных операций.

Утверждение 4.5. Пусть А/,йс2вд и множество M^jH является 2-вложенным, тогда существует алгоритм решения задач класса U_,(M, Н),

требующий 0(| ЕЫЬ:] |3 log | EN{s) | logр) вычислительных операций.

Утверждение 4.6. Пусть М,Яс2ад и множество М и Я является 2-вложенным, тогда существует алгоритм решения задач класса Uтмтт(М,Н),

требующий 0(| Ещ^ \2 log | EN(ij \ log р) вычислительных операций.

При исследовании Г, |r2 — equal] t3 -edge сводимости класса W(M) к классу WTree были получены следующие основные результаты.

Следствие 4.4. Пусть М с 2NU]. Для того чтобы класс W(M) являлся L | L — equal ] L - edge сводимым к классу WTree достаточно, чтобы множество М было 1-вложенным.

Теорема 4.5. Пусть М с 2N(S). Для того чтобы класс W(М) являлся ?! 1t2 - equal \ t3 - edge сводимым к классу WTree необходимо, чтобы множество Мб ыло 1-вложенным.

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

Утверждение 4.8. Пусть множество Мс2"(1) является 1-вложенным, тогда существует алгоритм решения задач класса W(M) и класса WZ(M)

(систем класса D(M) и класса DZ(M)), требующий 0(\ ENU) |2) (0(| EN(s) |)) вычислительных операций.

Утверждение 4.10. Пусть М,Яс2вд и множество МиЙ является 1-вложенным, тогда существует алгоритм решения задач класса U^(M,H),

требующий 0(| EN(s) |2 log р) вычислительных операций.

Утверждение 4.11. Пусть М,Яс2W(i) и множество МиН является 1-вложенным, тогда существует алгоритм решения задач класса Um3xmin(M,H), требующий 0(| £V( s) | log р) вычислительных операций.

Введем схему tx\t2-Z\t3-Z сводимости, представляющую собой обобщение рассмотренной ранее схемы ij 112 — equal \ f3 - edge сводимости. Основные особенности предлагаемой схемы:

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

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

Таким образом, рассматриваемая схема сведения является частным случаем схемы, описанной в определении 3.1, для которой s2=Z, s3=Z.

Следствие 4.5. Пусть М с 2NU). Для того чтобы класс W(M) являлся L\ L — Z | L — Z сводимым к классу WGraph достаточно, чтобы множество М было 2-вложенным.

Теорема 4.7. Пусть Мс2вд, Для того чтобы класс W(M) являлся Р* | Р* — Z\ Р* -Z сводимым к классу WCraph необходимо и достаточно, чтобы множество М было 2-вложенным, в противном случае P=NP.

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

Введем схему tx \t2 - equal] t3 —cycle сводимости, которая будет применяться в данной главе при исследовании сводимости многоиндексных задач к классу задач поиск потока в сети. Основные особенности предлагаемой схемы:

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

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

Таким образом, рассматриваемая схема сведения является частным случаем схемы описанной в определении 3.1, для которой s2 = equal, s3= cycle.

Определение 5.1. Пусть W - класс задач линейного программирования с двусторонней системой линейных неравенств. Будем говорить, что класс W является ij \t2 - equal \ f3 -cycle сводимым к классу WGraph, если класс W

является ij | г2 | /3 сводимым к классу WCraph и дополнительно произвольная

задача w= w(A,b~,b+,c) eW, а также соответствующая ей задача

Z = ZMcc(G;lij,uij,eij(i,j)€AG)&WCmtlh удовлетворяют следующим условиям.

Найдутся такие инъективные функции а: {\,...,nrou(Ä)} —> Ас, ß: {l,...,ncol(Ä)} —» C(G), что

- / = I, ЯГО W (А) ; hu.v)=°'UM=b*>

__nrowiA)

(и, v)eAG\ {a(i) \ i = 1, nrow(Ä)}, где b* = ^ bk ;

k=1

— если циркуляция Хц, (г, j) € Л0, является оптимальным (допустимым) решением задачи г и ус, CeC(G), является циклической декомпозицией

данной циркуляции, то (^щ.....^(ю/вд) будет являться оптимальным

(допустимым) решением задачи w, соответствующим решению задачи z.

Далее в данной главе рассматриваются вопросы f, \t2— equal | f3 — cycle сводимости класса W(M,H) к классу WCraph.

Определение 5.2. Пусть Мс2ад и f{,...,fk - разбиение множества N{s). Будем говорить, что множество М является /j,...,/^-декомпозиционным, если М с{/, |i = Щи{/, и/<+11i = U-1}.

Теорема 5.2. Пусть М,Н с2вд, /р—,/* - разбиение множества A^(j).

Для того чтобы класс W(M,H) являлся L | L - equal || EN(s) |2 —cycle сводимым

к классу WCraph достаточно, чтобы множества М и Н были fx,...,fk-

декомпозиционными.

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

Утверждение 5.1. Пусть M,Wc2]V(,), множества М и Н являются /р—.Л-декомпозиционными, fx,...,fk - разбиение множества N(s). Тогда существует алгоритм решения задач класса W(M,H) и класса WZ(M,H)

(систем класса D(M) и класса DZ(M)), требующий 0(\ EN(s.) |2 log21 EN(sj |) (0(1 En(s) Р I I)) вычислительных операций.

Утверждение 5.2. Пусть Мс2вд и множество М является J],...,fk-декомпозиционным, где fx,...,fk - разбиение множества N(s). Тогда существует алгоритм решения задач класса S(M), требующий

EN(s) I2 l°g2 I EiV(J) I) вычислительных операций.

Утверждение 5.3. Пусть М,Яс2вд и множество М kjH является /р..../t-декомпозиционным, где fx,...,fk - разбиение множества N(s). Тогда существует алгоритм решения задач класса £/ч(М,#), требующий

en(s) I I E,vu) I l°giO вычислительных операций.

Утверждение 5.4. Пусть М,Нс2вд и множество MkjH является /¡,...,/д.-декомпозиционным, где fl,...,fk - разбиение множества N(s). Тогда существует алгоритм решения задач класса £/maxmin(A/,H), требующий

0(1

EN(s) I I ^V(.v) I logp) вычислительных операций.

Рассмотрим далее ряд декомпозиционных классов многоиндексных задач, связанные с ними вопросы сложности и вопросы построения приближенных алгоритмов, основанных на полученных результатах tl\t2-equal\t3—cycle сводимости.

Утверждение 5.6. Пусть М ={fi\i = l,k}^{fiKjfi+l\i = l,k-l}, /j,...,/* -разбиение множества N(s), к > 3. Тогда для задач класса WZ(M) не существует полиномиального е -приближенного алгоритма для любых е > 0, иначе P = NP.

В работе строится алгоритм (алгоритм 5.2 с минимизацией максимума относительного отклонения), основанный на результатах г4 112 - equal \ t3 - cycle сводимости и использующий на промежуточном шаге решение следующей задачи линейного программирования:

%„ * X d(FNU)h Z AcF FN(s) е EN(s), (5.15)

/еЯ

A->min, (5.16)

где (С/ад} - заданная многоиндексная матрица стоимостей исходной задачи, {d-Fj} - многоиндексные матрицы неизвестных, /бЯ,

H = {fi\i = l,k}^j[fi ufM |i = fi,...,fk -разбиение множества N(s), A-

неизвестная величина.

Теорема 5.3. Пусть с* - оптимальное значение критерия задачи w, с' -значение критерия задачи w на приближенном решение, найденном

алгоритмом 5.2 с минимизацией максимума относительного отклонения, А -оптимальное значение критерия в задаче (5.15),(5.16), соответствующей задаче w, тогда с'<ДУ, weWz(M), М ={Ji\i = Tjc}u{fi^jfM\i = l,k-l}, где fi,...,fk - разбиение множества N(s), к>Ъ.

Утверждение 5.7. Пусть М = [Jl\i = Tjc}, Н = {/■ ufimoik+i |i = hk), fi,—,fk - разбиение множества N(s), к> 3. Тогда класс задач WZ(M,AH) является /W-трудным.

В работе строится алгоритм (алгоритм 5.3), основанный на результатах h I h ~ equal \ t3 - cycle сводимости.

Теорема 5.4. Пусть M=(f,\i = lk}, H = lf,vfimM+l\i = lk}, /„...,/t -разбиение множества N(s), к>3. Тогда алгоритм 5.3 является (к-2)/к-приближеиным алгоритмом для задач класса WZ(M,АН).

Утверждение 5.8. Пусть = Я ={/) vfinmdk+l |г =1,к],

fi,...,fk - разбиение множества N(s), к>3. Тогда алгоритм 5.3 поиска приближенного решения задач класса WZ(M,AH) требует

0(1 Еш 12 l°g21ENU) I) вычислительных операций.

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

В приложении приведены акты использования результатов диссертационной работы.

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

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

- сводимость с сохранением соответствия ребер \ t2 - equal \t3-edge сводимость),

- сводимость с сохранением соответствия циклов (tl \ t2 - equal \t3 -cycle сводимость).

При исследовании h\h~ equal 113 — edge сводимости класса многоиндексных задач W(M) к классу задач поиска потока минимальной стоимости в сети WG h был получен исчерпывающий ответ вопроса сводимости:

- для того чтобы класс W(M) являлся L\L-equal\ L — edge сводимым к классу WGraph достаточно, чтобы множество М было 2-вложенным,

- для того чтобы класс W(M) являлся t\\t2- equal \ t3 - edge сводимым к классу WGraph необходимо, чтобы множество М было 2-вложенным.

Более того предложенная конструктивная схема сводимости класса W(M) в случае 2-вложенности множества М является оптимальной (сведение с асимптотически меньшими вычислительными затратами невозможно и сколько угодное увеличение вычислительных затрат на сведение не приводится к расширению класса сводимых задач). Были разработаны алгоритмы решения следующих многоиндексных задач, основанные на полученных результатах сводимости:

- задач класса W(M) и систем класса D{M), а также задач соответствующих целочисленных классов WZ(M) и DZ(M), где множество М является 2-вложенным,

- задач класса 5(М), где множество М является 2-вложенным,

- задач класса U^(M,H) и задач класса (7ггшхт1п(М,Я), где множество М uН является 2-вложенным.

При исследовании ti \t2 - equal 113 - edge сводимости класса многоиндексных задач W(M) к классу задач поиска потока минимальной стоимости в древовидной сети WTree был также получен исчерпывающий ответ вопроса сводимости:

- для того чтобы класс W(M) являлся L\L — equal \ L - edge сводимым к классу WTree достаточно, чтобы множество М было 1-вложенным,

- для того чтобы класс W(M) являлся | r2 - equal \ t3 - edge сводимым к классу WTree необходимо, чтобы множество М было 1-вложенным.

Предложенная конструктивная схема сводимости класса W(M) в случае 1-вложенности множества М здесь также является оптимальной. Были разработаны алгоритмы решения следующих многоиндексных задач, основанные на полученных результатах сводимости:

- задач класса W(M) и систем класса D(M), а также задач соответствующих целочисленных классов WZ(M) и DZ{M), где множество М является 1-вложенным,

- задач класса U^(M,H) и задач класса £/maxmin(M,#), где множество MuH является 1-вложенным.

Была предложена схема tl\t2—Z\t3—Z сводимости класса W(M) к классу WGraph, являющаяся обобщением схемы Г, | Г2 - equal | Г3 - edge сводимости. При исследовании tl]t2—Z\t3—Z сводимости класса многоиндексных задач W(M) к классу задач поиска потока минимальной стоимости в сети WGraph были получены следующие результаты:

- для того чтобы класс W(M) являлся L\L — Z\L — Z сводимым к классу WG h достаточно, чтобы множество М было 2-вложенным,

- для того чтобы класс W(M) являлся Р' \Р"-Z\P"-Z сводимым к классу WGraph необходимо и достаточно, чтобы множество М было 2-вложенным, в противном случае P-NP.

Конструктивная схема сводимости класса W(M) в случае 2-вложенности множества М здесь также оказывается оптимальной.

При исследовании t{ 112 — equal | f3 — cycle сводимости класса многоиндексных задач W(M,H) к классу задач поиска потока минимальной стоимости в сети WGmph было установлено: для того чтобы класс W(M,H)

являлся L | L-equal \\ EN(5) |2 -cycle сводимым к классу WGraph достаточно, чтобы множества М и Н были fl,...,fk-декомпозиционными, где /,,...-разбиение множества N(s). Были разработаны алгоритмы решения следующих многоиндексных задач, основанные на полученных результатах сводимости:

27

- задач класса ИГ{М,Н) и систем класса й(М), а также задач соответствующих целочисленных классов \У2( М,Н) и 02(М), где множества М и Я являются /г,...,/к-декомпозиционными,

- задач класса 5(М), где множество М является /,,...,/<.-декомпозиционным;

- задач класса и^(М,Н) и задач класса итахтт(М,Н), где множество Мий является Д,...,/¿-декомпозиционным,

здесь /¡,...,/к - разбиение множества . Результаты сводимости позволили выделить новый полиномиально разрешимый класс (класс ИГ2(М,Н), где множества М и Я являются Д,...,/*-декомпозиционными, Д,...,/. - разбиение множества Л^(л')) в МР-трудном классе многоиндексных задач целочисленного линейного программирования. Полученные результаты сводимости применены также при построении приближенных алгоритмов решения ряда МР-трудных многоиндексных задач, обладающих декомпозиционной структурой:

- рассмотрен класс задач \У2(М), для которого не существует полиномиального а -приближенного алгоритма для любых £>0, иначе Р=ЛГР, М = {/1 ||=1Д}и{/.и/.+1|| = 1,А:-1}; для задач класса 1¥г(М) предложен полиномиальный приближенный алгоритм, находящий допустимое решение, отклоняющееся от оптимума не более чем в А* раз, где Д* является оптимальным значение критерия вспомогательной задачи линейного программирования;

- рассмотрен Л^Р-трудный класс задач ]¥г(М,АН), где М ={/>|/ = \,к), Я = {/и/;.т^+1|/ = й}; для задач класса \Уг(М,АН) предложен полиномиальный (к -2)/к-приближенный алгоритм;

здесь - разбиение множества Ж5), к>3.

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

СПИСОК ПУБЛИКАЦИЙ

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

1.Афраймович Л.Г. Многоиндексные транспортные задачи с 2-вложенной структурой // Автоматика и телемеханика. 2013. № 1. С. 116-134.

2. Афраймович Л.Г. Многоиндексные транспортные задачи с декомпозиционной структурой // Автоматика и телемеханика. 2012. № 1. С. 130-147.

3. Афраймович Л.Г. Катеров A.C. Трех- и четырехиндексные задачи с вложенной структурой // Математическое моделирование. Оптимальное управление. Вестник Нижегородского университета им. Н.И. Лобачевского. 2012. № 3 (1). С. 163-169.

4. Афраймович Л.Г. Трехиндексные задачи линейного программирования с вложенной структурой // Автоматика и телемеханика. 2011. № 8. С. 109-120.

5. Афраймович Л.Г. Циклическая сводимость многоиндексных систем линейных неравенств транспортного типа // Известия РАН. Теория и системы управления. 2010. № 4. С. 83-90.

6. Афраймович Л.Г., Прилуцкий М.Х. Многоиндексные задачи оптимального планирования производства // Автоматика и телемеханика. 2010. №. 10. С. 148-155.

7. Афраймович Л.Г., Прилуцкий М.Х. Поиск потока в несовместных транспортных сетях // Управление большими системами. 2009. Вып. 24. С. 147-168.

8. Прилуцкий М.Х., Афраймович Л.Г., М.С. Куликов. Об одном классе многокритериальных задач квадратичного программирования транспортного типа // Математическое моделирование. Оптимальное управление. Вестник Нижегородского университета им. Н.И. Лобачевского. 2009. № 6 (1). С. 178— 183.

9. Афраймович Л.Г., Прилуцкий М.Х. Многопродуктовые потоки в древовидных сетях // Известия РАН. Теория и системы управления. 2008. № 2. С. 57-63.

10. Афраймович Л.Г., Прилуцкий М.Х. Многоиндексные задачи распределения ресурсов в иерархических системах // Автоматика и телемеханика. 2006. № 6. С. 194-205.

11. Афраймович Л.Г. Потоковые алгоритмы исследования совместности иерархических систем распределения ресурсов с ограничениями // Вестник

Нижегородского государственного университета. Математическое моделирование и оптимальное управление. 2006. 2(31). С. 129-138.

Публикации в других изданиях

12. Афраймович Л.Г. Метод решения целочисленных многоиндексных транспортных задач с декомпозиционной структурой // Доклады Одесского семинара по дискретной математике. №11. 2011. С. 4-14.

13. Афраймович Л.Г. Приближенный алгоритм решения многоиндексных транспортных задач с декомпозиционной структурой // Проблемы теоретической кибернетики. Материалы XVI Международной конференции -Нижний Новгород: изд-во Нижегородского госуниверситета. 2011. С. 42-45.

14. Афраймович Л.Г. Многоиндексные задачи линейного программирования с декомпозиционной структурой // VI Московская международная конференция по исследованию операций (ORM2010): Москва, 19-23 октября 2010 г.: Труды -М.: МАКС Пресс. 2010. С. 280-281.

15. Афраймович Л.Г., Прилуцкий М.Х. Трехиндексные транспортные задачи с вложенной структурой // Материалы X Международного семинара «Дискретная математика и ее приложения» — М.: Изд-во механико-математического факультета МГУ, 2010. С. 286-288.

16. Афраймович Л.Г., Прилуцкий М.Х. Распределение ресурсов в несовместных многоиндексных иерархических системах // Дискретные модели в теории управляющих систем: VIII Международная конференция, Москва, 6-9 апреля 2009 г. Труды.: МАКС Пресс. 2009. С. 18-23.

17. Афраймович Л.Г. Батищев Д.И., Костюков В.Е., Прилуцкий М.Х., Шагалиев P.M. Статическая балансировка параллельных методов моделирования газодинамических процессов // Параллельные вычислительные технологии (ПаВТ'2009): Труды международной научной конференции -Челябинск: Изд. ЮУрГУ, 2009. С. 364-369.

18. Афраймович Л.Г., Куликов М.С., Прилуцкий М.Х. Распределение производительности купола по газовым скважинам // Технологии Microsoft в теории и практике программирования. Материалы конференции. - Нижний Новгород: Изд-во Нижегородского госуниверситета. 2009. С. 350—352.

19. Афраймович Л.Г. Задача поиска потока в несовместной транспортной сети // Проблемы теоретической кибернетики. Тезисы докладов XV международной конференции. 2008. С. 8.

20. Афраймович Л.Г., Прилуцкий М.Х., Бухвалова И.Р., Старостин Н.В., Филимонов A.B. Оптимизационные задачи оперативного управления работой компрессорной станцией // Электронный журнал «Исследовано в России». 2008. 032. С. 375-382. http://zhurnal.ape.relarn.ru/articles/2008/032.pdf

21. Афраймович Л.Г., Прилуцкий М.Х., Шумилов В.Б., Старостин Н.В., Филимонов A.B. Оптимизационные задачи объемно-календарного планирования для предприятий по переработке газового конденсата // Электронный журнал «Исследовано в России». 2008. 031. С. 365-374. http://zhurnal.ape.relarn.ru/articles/2008/031 .pdf

22. Афраймович Л.Г., Прилуцкий М.Х., Шумилов В.Б., Старостин Н.В., Филимонов A.B. Оптимизационные задачи планирования транспорта газа в магистральном газопроводе // Электронный журнал «Исследовано в России». 2008. 033. С. 383-391. http://zhurnal.ape.relarn.ru/articles/2008/033.pdf

23. Afraimovich L.G., Prilutskii M.Kh. Multi-commodity min-cost flow problem in a directed tree structured graph // V Московская международная конференция по исследованию операций (ORM 2007), посвященная 90-летию со дня рождения академика H.H. Моисеева. - М.:Макс Пресс. 2007. С. 233-234.

24. Афраймович Л.Г. Равномерное перераспределение ресурсов в иерархических системах транспортного типа // Технологии Microsoft в теории и практике программирования. Материалы конференции. - Нижний Новгород: Изд-во Нижегородского госуниверситета. 2007. С. 320-321.

25. Афраймович Л.Г., Прилуцкий М.Х. Сводимость задачи распределения ресурсов в иерархических системах древовидной структуры к потоковым задачам // Технологии Microsoft в теории и практике программирования. Материалы конференции. - Нижний Новгород: Изд-во Нижегородского госуниверситета. 2006. С. 25-26.

26. Афраймович Л.Г. Проблема существования решения в многоресурсных иерархических системах // Вестник ВГАВТ. Межвузовская серия Моделирование и оптимизация сложных систем. 2005. Вып. 14. с. 122— 127.

27. Афраймович Л.Г. Распределение ресурсов в иерархических системах транспортного типа с ограничениями. Построение математических моделей и их исследование // Труды НГТУ. Системы обработки информации и управления. 2005. Т. 45. Вып. 23. С. 27-34.

28. Афраймович Л.Г. Сведение системы линейных неравенств транспортного типа к задаче поиска максимального потока в сети при

дополнительных ограничениях // Проблемы теоретической кибернетики. Тезисы докладов XIV Международной конференции. - М.: Изд-во механико-математического факультета МГУ. 2005. С. 13.

29. Прилуцкий М.Х., Афраймович Л.Г. Условия совместности многоиндексных систем транспортного типа // Электронный журнал "Исследовано в России", 70. 2005. С. 762-767. http://zhumal.ape.relarn.ru/articles/2005/070.pdf

30. Afraimovich L.G. Reconstructing hierarchy systems of homogeneous resource distribution // Избранные вопросы современной математики: Тез. Междунар. науч. конф., приуроченной к 200-летию со дня рождения великого немецкого математика Карла Густава Якоби и 750-летию со дня основания г. Калининграда (Кенигсберга). - Калининград: Изд-во КГУ. 2005. С. 64—66.

31. Афраймович Л.Г. Оптимальное распределение однородного ресурса в задачах управления производством // Технологии Microsoft в теории и практике программирования. Труды Всероссийской конференции студентов, аспирантов и молодых ученых. Центральный регион. - М.: Издательство МГТУ им Н.Э. Баумана. 2005. С. 31-32.

32. Афраймович Л.Г. Задачи распределения однородного ресурса в многоуровневых иерархических системах // IX Нижегородская сессия молодых ученых. Технические науки. Тезисы докладов. Нижний Новгород. 2004. С. 5-6.

33. Прилуцкий М.Х., Афраймович Л.Г. Оптимальное распределение однородного ресурса в иерархических системах с доходами // Вестник ВГАВТ. Межвузовская серия Моделирование и оптимизация сложных систем. 2004. Вып. 9. С. 56-63.

34. Afraimovich L.G. Generalized model of homogeneous resource distribution in hierarchy systems // VI International congress on mathematical modeling. Book of abstracts. Nizhny Novgorod. 2004. P. 65.

35. Афраймович Л.Г. Оптимальные преобразования перестраиваемых иерархических систем распределения однородного ресурса // IX Нижегородская сессия молодых ученых. Математические науки. Тезисы докладов. Саров. 2004. С 6-7.

36. Афраймович Л.Г. Задачи распределения однородного ресурса в иерархических системах // VIII Нижегородская сессия молодых ученых. Математические науки. Тезисы докладов. Саров. 2003. С. 41-42.

37. Афраймович Л.Г. Модифицированные потоковые алгоритмы распределения однородного ресурса в иерархических системах // Математика и

кибернетика 2003. Сборник научных статей юбилейной научно-технической конференции факультета ВМК ННГУ и НИИ ПМК. Нижний Новгород. 2003. С. 23-25.

38. Прилуцкий М.Х., Афраймович Л.Г. Параллельные структуры потоковых и итерационных алгоритмов распределения ресурса в иерархических системах // Материалы третьего Международного научно-практического семинара «Высокопроизводительные параллельные вычисления на кластерных системах». - Нижний Новгород: Издательство Нижегородского госуниверситета. 2003. С. 140-145.

39. Афраймович Л.Г. Потоковые алгоритмы распределения ресурсов в иерархических системах // Тезисы докладов НТК «Технические, программные и математические аспекты управления сложными распределенными системами». Нижний Новгород. 2003. С. 6.

40. Афраймович Л.Г. Минимизация затрат при распределении однородного ресурса в иерархических системах с двусторонними ограничениями // КоГраф 2002. Материалы докладов всероссийской конференции. - Нижний Новгород. 2002. С. 81-83.

41. Прилуцкий М.Х., Афраймович Л.Г. Параллельные алгоритмы распределения ресурсов в иерархических системах с лексикографическим упорядочиванием элементов // Материалы второго Международного научно-практического семинара «Высокопроизводительные параллельные вычисления на кластерных системах». - Нижний Новгород: Издательство Нижегородского госуниверситета. 2002. С. 243-248.

Подписано в печать 19.12.2013 г. Формат 60x84 1/16. Бумага офсетная. Печать цифровая. Усл. печ. л. 1. Заказ № 1107. Тираж 150 экз.

Отпечатано с готового оригинал-макета в типографии ННГУ им. Н.И. Лобачевского. 603000, г. Нижний Новгород, ул. Б. Покровская, 37