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

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

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

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

Специальность: 01.01.09

Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

доктора физико-математических наук

Нижний Новгород 2014

Работа выполнена в Нижегородском государственном университете им. Н.И.

Лобачевского.

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

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

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

Лобачевского

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

БОНДАРЕНКО ВЛАДИМИР АЛЕКСАНДРОВИЧ

доктор физико-математических наук, профессор, заведующий кафедрой дискретного анализа, ФГБОУ ВПО «Ярославский государственный университет им. П.Г. Демидова»

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

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

ЩЕРБИНА ОЛЕГ АЛЕКСАНДРОВИЧ

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

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

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

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

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

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

Ученый секретарь диссертационного совета Д 002.017.02, д.ф.-м.н., профессор В.В. Рязанов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

«Модуль расчета оптимального плана производства для диалоговой системы объемно-календарного планирования производственных мощностей, функционирующей на предприятии» при решении задач объмно-календарного планирования, заказчик ОАО «ОКБМ Африкантов», г. Нижний Новгород;

программная система ПО «Кристалл» при планировании процесса изготовления сложных изделий, заказчик ФГУП «ФНПЦ НИИИС им. Ю.Е. Седакова», г.

Нижний Новгород.

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

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

Апробация результатов исследования. Полученные в диссертационной работе результаты обсуждались на Всероссийской конференции КоГраф (Н.Новгород, 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 B.), научных семинарах Кафедры информатики и автоматизации научных исследований факультета Вычислительной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского (2006 г., 2011 г., 2013 г., руководитель семинара профессор Прилуцкий М.Х.), научном семинаре Кафедры исследования операций Математико-механического факультета СанктПетербургского государственного университета (2012 г., руководитель семинара профессор Романовский И.В.), научном семинаре центра исследования операций и бизнес статистики университета г. Левен (Бельгия, г.

Левен, 2012 г., руководитель семинара профессор Spieksma F.C.R.), научном семинаре Вычислительного центра имени А.А. Дородницына Российской академии наук (2012 г., руководитель семинара академик Евтушенко Ю.Г.).

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

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

Н.И. Лобачевского) из списка, рекомендованного ВАК.

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

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

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

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

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

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

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

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

При постановке многоиндексных задач транспортного типа воспользуемся следующей формализацией. Пусть s N и N (s) {1,2,..., s}.

Каждому числу l поставим в соответствие параметр jl, называемый индексом, который принимает значения из множества J l {1,2,..., nl }, где nl 2, l N (s).

Там где это не вызывает неоднозначности, будем отождествлять номер индекса значений индексов F f = ( jk1, jk 2,..., jkt ) f будем называть t-индексом. Множество E f {Ff | F J k1 J k 2... J kt }. Там где это не вызывает неоднозначности, ( Ff Ff ) f Ff. Далее определим f N (s) \ f, тогда согласно введенному обозначению M 2 N ( s ), тогда будем обозначать M { f | f M }.

Каждому набору Ff поставим в соответствие действительное число z F f, Ff E f. Данное отображение множества t-индексов E f в множество действительных чисел назовем t-индексной матрицей и обозначим через {zF f }.

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

Пусть М – заданное множество, M 2 N ( s ) ; {aFf }, {bFf } – заданные | f | индексные матрицы свободных коэффициентов, 0 aF f bF f, F f E f, f M ;

{cFN (s ) } – заданная s-индексная матрица коэффициентов целевой функции;

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

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

В ряде задач s-индексная матрица коэффициентов целевой функции {cFN (s ) } имеет декомпозиционную структуру и может быть представлена в виде подсуммы многоиндексных матриц меньшей размерности. Пусть H 2 N ( s ) и заданы | H | многоиндексных матриц коэффициентов {d Ff }, f H, что Тогда рассмотрим целевую функцию следующего вида:

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

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

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

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

Особый интерес представляет решение целочисленной многоиндексной транспортной задачи, когда дополнительно необходимо выполнение ограничения целочисленности переменных Будем добавлять нижний индекс Z к обозначению класса многоиндексных задач, если дополнительно выполняется условие целочисленности (3.6). Тогда соответствующие классы систем целочисленных линейных неравенств (3.1),(3.6), задач целочисленного линейного программирования (3.1),(3.6),(3.3) и задач целочисленного линейного программирования (3.1),(3.6),(3.4) при фиксированных множествах M и H будем обозначать через DZ (M ), WZ (M ) и WZ (M, H ) соответственно.

Рассмотрим задачу исследования несовместной многоиндексной системы линейных неравенств транспортного типа. Пусть многоиндексная система (3.1),(3.2) несовместна. Введем вспомогательные обозначения. Обозначим соответствующего неравенства (3.1) разрешено изменение нижней (верхней) границы, и значение 0 в противном случае; eF ( eF ) – штраф за изменение на единицу нижней (верхней) границы соответствующего неравенства (3.1), eFf, eFf 0 ; yF f ( yF f ) – неизвестная величина, на которую будет изменена нижняя (верхняя) граница соответствующего неравенства (3.1), F f E f, f M. Тогда задача исследования несовместной многоиндексной системы заключается в определении многоиндексных матриц неизвестных { yF f }, { y F f }, f M и {x FN (s ) }, являющихся решением следующей задачи линейного программирования:

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

Рассмотрим многокритериальную многоиндексную задачу с кусочнопостоянными критериями оптимальности. Пусть M, H 2 N ( s ) и множество M определяет систему многоиндексных неравенств транспортного типа (3.1),(3.2), множество H определяет кусочно-постоянные критерии, формализация которых приводится далее. Пусть P( H ) {( f, Ff ) | Ff E f, f H }. Для каждой из пар ( f, Ff ) определим p 1 вложенных сегментов S (fl,)Ff, l 0, p, что определяет следующую функцию предпочтения Тогда рассмотрим многокритериальную задачу определения s-индексной матрицы неизвестных {x FN (s ) }, удовлетворяющей системе ограничений (3.1),(3.2) и минимизирующей функции предпочтения Класс многокритериальных задач (3.1),(3.2),(3.11) будем обозначать U (M, H ).

Применим для решения поставленной многокритериальной задачи следующие схемы компромисса: лексикографическое упорядочивание критериев оптимальности, соответствующий класс задач обозначим U (M, H ), и максиминную свертку, соответствующий класс задач обозначим U max min (M, H ).

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

вектор неизвестных. Через w( A, b, c) будем обозначать задачу линейного программирования линейного программирования min{(c, x) | b Ax b, x 0}. Для удобства через nrow(A) и ncol(A) будем обозначать количество строк и столбцов матрицы A соответственно. Далее рассмотрим два класса задач линейного программирования W и W. На содержательном уровне под сводимостью класса W к классу W понимается возможность построения для произвольной задачи w W соответствующей задачи w W таким образом, чтобы решение задачи w определяло решение задачи w. При формализации конкретной схемы сведения будем определять временные затраты и (или) конкретные вычислительные процедуры, связанные с:

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

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

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

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

– если известно оптимальное (допустимое) решение x задачи w, то оптимальное (допустимое) решение x задачи w может быть построено за время O(t3 ) с использованием процедуры s3.

Здесь s1, s3 – строковые обозначения вычислительных процедур, связанных с построением матрицы системы ограничений, свободных коэффициентов и коэффициентов целевой функции и с построением решения задачи соответственно.

Замечания. Опционально будем опускать записи вычислительных затрат t1, t2, t3 и (или) записи обозначений вычислительных процедур s1, s2, s3, если при сведении не конкретизируются соответствующие вычислительные затраты и (или) вычислительные процедуры. Задачу w (см. определение 3.1) будем называть задачей, соответствующей задаче w. Решение x (см. определение 3.1) будем называть решением, соответствующим решению x. При определении вычислительных затрат t1, t2, t3, если не оговорено иного, будем оценивать, количество вычислительных операций на машине с произвольным доступом к памяти. Иногда для удобства функции оценки вычислительной сложности t1, t2, t3 будем заменять обозначениями L или P, подразумевая линейные или полиномиальные функции от размера матрицы A, соответственно. В случае, когда при определении t1, t2, t3 оценивается вычислительная сложность рассматриваемых вычислительных процедур, будем добавлять верхний индекс «*» в записи соответствующих оценок. В частности будем писать L* или P*, когда речь идет о линейной или полиномиальной оценках вычислительной сложности как функции размера индивидуальной задачи соответственно.

В работе исследуется возможность сведения класса многоиндексных задач линейного программирования транспортного типа к классу задач поиска потока в сети. В качестве потоковой задачи будем рассматривать задачу поиска потока (циркуляции) минимальной стоимости в сети. Приведем далее известную постановку соответствующей потоковой задачи. Пусть задан ориентированный граф без петель G (VG, AG ), AG VG. Обозначим через lij, u ij и eij заданные значения нижней пропускной способности, верхней пропускной способности и стоимости дуги (i, j ) соответственно, 0 lij uij, xij обозначим поток вдоль дуги (i, j ), (i, j ) A. Тогда задача через заключается в нахождение значений xij, (i, j ) A, являющихся решением следующей задачи линейного программирования:

обозначаемой далее zMCC (G; lijuij, eij, (i, j ) AG ). Класс задач поиска потока минимальной стоимости будем обозначать WGraph. Класс задач поиска потока минимальной стоимости в древовидной сети будем обозначать WTree.

Далее в работе исследуются вопросы t1 s1 | t2 s2 | t3 s3 сводимости классов многоиндексных задач W (M ) и W (M, H ) к классам задач поиска потока в сети WGraph и WTree. Применяемые при исследовании сводимости вычислительные процедуры s1, s2, s3 будут определены далее в работе при описании рассматриваемых схем сведения. Результаты исследования сводимости будут применены в работе при построении алгоритмов решения поставленных многоиндексных задач D(M ), W (M ), W (M, H ) (и соответственно DZ (M ), WZ (M ) и WZ (M, H ) ), а также S (M ), U (M, H ) и U max min (M, H ).

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

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

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

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

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

Определение 4.1. Пусть W – класс задач линейного программирования с двусторонней системой линейных неравенств. Будем говорить, что класс W является t1 | t2 equal | t3 edge сводимым к классу W WGraph, если класс W является t1 | t2 | t3 сводимым к классу W и дополнительно произвольная задача : {1,..., ncol( A)} AG, что – если xij, (i, j ) AG, является оптимальным (допустимым) решением задачи z, то ( x (1),..., x (ncol( A)) ) будет являться оптимальным (допустимым) решением задачи w, соответствующим решению задачи z.

Далее в данной главе рассматриваются вопросы t1 | t2 equal | t3 edge сводимости класса W (M ) к классам WGraph и WTree, а также обобщение соответствующих результатов сводимости для некоторого более широкого класса схем сводимости.

При исследовании t1 | t2 equal | t3 edge сводимости класса W (M ) к классу WGraph были получены следующие основные результаты.

Определение 4.2. Множество M, M 2 N ( s ), называется k-вложенным, если существует разбиение множества M на k подмножеств M i { f1,..., f mi }, Теорема 4.2. Пусть M 2 N ( s ). Для того чтобы класс W (M ) являлся L | L equal | L edge сводимым к классу WGraph достаточно, чтобы множество M было 2-вложенным.

Теорема 4.4. Пусть M 2 N ( s ). Для того чтобы класс W (M ) являлся t1 | t2 equal | t3 edge сводимым к классу WGraph необходимо, чтобы множество M было 2-вложенным.

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

Утверждение 4.1. Пусть множество M 2 N ( s ) является 2-вложенным, тогда существует алгоритм решения задач класса W (M ) и класса WZ (M ) (систем класса D(M ) и класса DZ (M ) ), требующий O(| EN ( s ) | log | EN ( s ) |) ( O(| EN ( s ) | log | EN ( s ) |) ) вычислительных операций.

Утверждение 4.4. Пусть множество M 2 N ( s ) является 2-вложенным, тогда существует алгоритм решения задач класса S (M ), требующий O(| EN ( s ) |2 log2 | EN ( s ) |) вычислительных операций.

Утверждение 4.5. Пусть M, H 2 N ( s ) и множество M H является 2вложенным, тогда существует алгоритм решения задач класса U (M, H ), требующий O(| EN ( s ) | log | EN ( s ) | log p) вычислительных операций.

Утверждение 4.6. Пусть M, H 2 N ( s ) и множество M H является 2вложенным, тогда существует алгоритм решения задач класса U max min (M, H ), требующий O(| EN ( s ) | log | EN ( s ) | log p) вычислительных операций.

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

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

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

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

Утверждение 4.8. Пусть множество M 2 N ( s ) является 1-вложенным, тогда существует алгоритм решения задач класса W (M ) и класса WZ (M ) (систем класса D(M ) и класса DZ (M ) ), требующий O(| EN (s ) | ) ( O(| EN (s ) |) ) вычислительных операций.

Утверждение 4.10. Пусть M, H 2 N ( s ) и множество M H является 1вложенным, тогда существует алгоритм решения задач класса U (M, H ), требующий O(| EN ( s ) | log p) вычислительных операций.

Утверждение 4.11. Пусть M, H 2 N ( s ) и множество M H является 1вложенным, тогда существует алгоритм решения задач класса U max min (M, H ), требующий O(| EN ( s ) | log p) вычислительных операций.

Введем схему t1 | t2 Z | t3 Z сводимости, представляющую собой обобщение рассмотренной ранее схемы t1 | t2 equal | t3 edge сводимости.

Основные особенности предлагаемой схемы:

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

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

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

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

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

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

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

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

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

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

Определение 5.1. Пусть W – класс задач линейного программирования с двусторонней системой линейных неравенств. Будем говорить, что класс W является t1 | t2 equal | t3 cycle сводимым к классу WGraph, если класс W является t1 | t2 | t3 сводимым к классу WGraph и дополнительно произвольная z zMCC (G; lij, uij, eij (i, j) AG ) WGraph удовлетворяют следующим условиям.

: {1,..., ncol( A)} C(G), что – если циркуляция xij, (i, j ) AG, является оптимальным (допустимым) решением задачи z и yC, C C(G), является циклической декомпозицией данной циркуляции, то ( y (1),..., y ( ncol( A)) ) будет являться оптимальным (допустимым) решением задачи w, соответствующим решению задачи z.

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

Определение 5.2. Пусть M 2 N ( s ) и f1,..., f k – разбиение множества N (s). Будем говорить, что множество M является f1,..., f k -декомпозиционным, Теорема 5.2. Пусть M, H 2 N ( s ), f1,..., f k – разбиение множества N (s).

Для того чтобы класс W (M, H ) являлся L | L equal || EN ( s ) |2 cycle сводимым к классу WGraph достаточно, чтобы множества M и H были f1,..., f k декомпозиционными.

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

Утверждение 5.1. Пусть M, H 2 N ( s ), множества M и H являются f1,..., f k -декомпозиционными, существует алгоритм решения задач класса W (M, H ) и класса WZ (M, H ) ( O(| EN ( s ) | log | EN ( s ) |) ) вычислительных операций.

O(| EN ( s ) |2 log2 | EN ( s ) |) вычислительных операций.

Утверждение 5.3. Пусть M, H 2 N ( s ) и множество M H является f1,..., f k -декомпозиционным, где f1,..., f k – разбиение множества N (s). Тогда O(| EN ( s ) |3 log | EN ( s ) | log p) вычислительных операций.

Утверждение 5.4. Пусть M, H 2 N ( s ) и множество M H является f1,..., f k -декомпозиционным, где f1,..., f k – разбиение множества N (s). Тогда существует алгоритм решения задач класса U max min (M, H ), требующий O(| EN ( s ) |2 log | EN ( s ) | log p) вычислительных операций.

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

разбиение множества N (s), k 3. Тогда для задач класса WZ (M ) не существует полиномиального -приближенного алгоритма для любых 0, иначе P NP.

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

где {сFN (s ) } – заданная многоиндексная матрица стоимостей исходной задачи, {d F f } неизвестная величина.

Теорема 5.3. Пусть c* – оптимальное значение критерия задачи w, c – значение критерия задачи w на приближенном решение, найденном алгоритмом 5.2 с минимизацией максимума относительного отклонения, – оптимальное значение критерия в задаче (5.15),(5.16), соответствующей задаче – разбиение множества N (s), k 3.

f1,..., f k – разбиение множества N (s), k 3. Тогда класс задач WZ (M, H ) является NP-трудным.

В работе строится алгоритм (алгоритм 5.3), основанный на результатах t1 | t2 equal | t3 cycle сводимости.

разбиение множества N (s), k 3. Тогда алгоритм 5.3 является (k 2) / k приближенным алгоритмом для задач класса WZ (M, H ).

f1,..., f k – разбиение множества N (s), k 3. Тогда алгоритм 5.3 поиска O(| EN ( s ) |2 log2 | EN ( s ) |) вычислительных операций.

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

диссертационной работы.

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

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

– сводимость с сохранением соответствия ребер ( t1 | t2 equal | t3 edge сводимость), – сводимость с сохранением соответствия циклов ( t1 | t2 equal | t3 cycle сводимость).

многоиндексных задач W (M ) к классу задач поиска потока минимальной стоимости в сети WGraph был получен исчерпывающий ответ вопроса сводимости:

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

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

– задач класса W (M ) и систем класса D(M ), а также задач соответствующих целочисленных классов WZ (M ) и DZ (M ), где множество M является 2вложенным, – задач класса S (M ), где множество M является 2-вложенным, – задач класса U (M, H ) и задач класса U max min (M, H ), где множество M H является 2-вложенным.

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

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

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

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

Была предложена схема t1 | t2 Z | t3 Z сводимости класса W (M ) к многоиндексных задач W (M ) к классу задач поиска потока минимальной стоимости в сети WGraph были получены следующие результаты:

– для того чтобы класс W (M ) являлся L | L Z | L Z сводимым к классу WGraph достаточно, чтобы множество M было 2-вложенным, – для того чтобы класс W (M ) являлся WGraph необходимо и достаточно, чтобы множество M было 2-вложенным, в противном случае P=NP.

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

многоиндексных задач W (M, H ) к классу задач поиска потока минимальной стоимости в сети WGraph было установлено: для того чтобы класс W (M, H ) являлся L | L equal || EN ( s ) |2 cycle сводимым к классу WGraph достаточно, чтобы множества M и H были f1,..., f k -декомпозиционными, где f1,..., f k – разбиение множества N (s). Были разработаны алгоритмы решения следующих многоиндексных задач, основанные на полученных результатах сводимости:

– задач класса W (M, H ) и систем класса D(M ), а также задач соответствующих целочисленных классов WZ (M, H ) и DZ (M ), где множества M и H являются f1,..., f k -декомпозиционными, – задач класса S (M ), где множество M является f1,..., f k -декомпозиционным;

– задач класса U (M, H ) и задач класса U max min (M, H ), где множество M H является f1,..., f k -декомпозиционным, здесь f1,..., f k – разбиение множества N (s). Результаты сводимости позволили выделить новый полиномиально разрешимый класс (класс WZ (M, H ), где множества M и H являются f1,..., f k -декомпозиционными, f1,..., f k – разбиение множества N (s) ) в NP-трудном классе многоиндексных задач целочисленного линейного программирования. Полученные результаты сводимости применены также при построении приближенных алгоритмов решения ряда NP-трудных многоиндексных задач, обладающих декомпозиционной структурой:

– рассмотрен класс задач WZ (M ), для которого не существует полиномиального -приближенного алгоритма для любых 0, иначе P=NP, допустимое решение, отклоняющееся от оптимума не более чем в * раз, где * является оптимальным значение критерия вспомогательной задачи линейного программирования;

– рассмотрен NP-трудный класс задач WZ (M, H ), где M { fi | i 1, k}, полиномиальный (k 2) / k -приближенный алгоритм;

здесь f1,..., f k – разбиение множества N (s), k 3.

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

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

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

Публикации в журналах, рекомендованных ВАК России 1. Афраймович Л.Г. Многоиндексные транспортные задачи с 2вложенной структурой // Автоматика и телемеханика. 2013. 1. С. 116–134.

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

130–147.

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

2012. 3 (1). С. 163–169.

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

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

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

. 10. C. 148–155.

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

147–168.

8. Прилуцкий М.Х., Афраймович Л.Г., М.С. Куликов. Об одном классе многокритериальных задач квадратичного программирования транспортного типа // Математическое моделирование. Оптимальное управление. Вестник Нижегородского университета им. Н.И. Лобачевского. 2009. 6 (1). C. 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.

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

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

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

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

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

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

20. Афраймович Л.Г., Прилуцкий М.Х., Бухвалова И.Р., Старостин Н.В., Филимонов А.В. Оптимизационные задачи оперативного управления работой компрессорной станцией // Электронный журнал «Исследовано в России».

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

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

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-летию со дня рождения академика Н.Н. Моисеева. – М.:Макс Пресс. 2007. С. 233–234.

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

Изд-во Нижегородского госуниверситета. 2007. С. 320–321.

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

Материалы конференции. – Нижний Новгород: Изд-во Нижегородского госуниверситета. 2006. С. 25–26.

многоресурсных иерархических системах // Вестник ВГАВТ. Межвузовская серия Моделирование и оптимизация сложных систем. 2005. Вып. 14. с. 122– 127.

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

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

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

29. Прилуцкий М.Х., Афраймович Л.Г. Условия совместности многоиндексных систем транспортного типа // Электронный журнал http://zhurnal.ape.relarn.ru/articles/2005/070.pdf 30. Afraimovich L.G. Reconstructing hierarchy systems of homogeneous resource distribution // Избранные вопросы современной математики: Тез.

Междунар. науч. конф., приуроченной к 200-летию со дня рождения великого немецкого математика Карла Густава Якоби и 750-летию со дня основания г.

Калининграда (Кенигсберга). – Калининград: Изд-во КГУ. 2005. C. 64–66.

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

Баумана. 2005. C. 31–32.

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

33. Прилуцкий М.Х., Афраймович Л.Г. Оптимальное распределение однородного ресурса в иерархических системах с доходами // Вестник ВГАВТ.

Межвузовская серия Моделирование и оптимизация сложных систем. 2004.

Вып. 9. C. 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.

C 6–7.

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

Математические науки. Тезисы докладов. Саров. 2003. C. 41–42.

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

C. 23–25.

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

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

Нижний Новгород. 2003. C. 6.

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

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