Введение к работе
Актуальность темы. Полиэдральная комбинаторика (ПК) - один из наиболее перспективных и бурно развивающихся разделов дискретной математики, возникший на стыке комбинаторной геометрии, теории графоь и оптимизации. Ее проблематика и первоначальные результати восходят к Р. Декарту, Л.Эйлеру, 0.Ковш, А. Пуанкаре, Г. Минковскому, А.Д. Александрову и Г. Вейлю. В ПК наряду с классическими проблемами - перечисление и классификация многогранников, характеризация остовных комплексов, рассматриваются новые - построение выпуклых оболочек и изучение метрических свойств графов многогранников. Популярность ПК в наше время, преаде всего, объясняется возможностью применения ее аппарата для оценки трудоемкости методов оптимизации и перспективами построения на ее основе эффективных алгоритмов.
Графы (реберные остовы) многогранника исследуются как для абстрактных многогранников, задаваемых системой линейных неравенств общего вида (работы Г. Бартельса, А. Бренстеда, Б.Грюнбаума, Д. Данцига, И.И. Еремина, Л.В. Канторовича, В. Кли, П. Макмюллена, Л. Г. Хачияна,' В. С. Чарина, С. Н. Черникова, Н. 3. Шора и др.), так и для многогранников конкретных задач оптимизации: коммивояжера, стандартизации, проблемы выбора, транспортной и комбинаторной оптимизации (работы М. Белинского, Е. Болкера, Ж. Дюбуа, В. А. Емеличева, В. Кли, М. М. Ковалева, А-П. Крачковского, В.Н. Шевченко и др.). При втом подсчитыввются или оцениваются такие характеристики многогранников, как число вершин, диаметр, радиус, обхват и др. Некоторые из них определенным образом «вязаны с оценкой числа итераций и эффективностью алгоритмов симплексного типа в задачах линейного программирования (ЛП). Действительно, если, например, требуется определить ексфремуи линейной функции на многограннике, то максимальное количество его вершин можно считать верхней границей числа итераций. Диаметр многогранника есть число итераций наилучшего симплексного алгоритма (если, конечно, такой Лудет построен) при наихудшем расположении стартовой и оптимальной вершин. Относительно радиуса мокно сказать следующее і если радиус многогранника равен г. то существует такая стартовая вершина, что при любом расположении оптимальной вершины число итераций наилучшего симплексного алгоритма не превосходит числа г.
Все ети обстоятельства стимулировали исследования, связанные с проблемой отыскания верхних и нижних границ для числа . вершин, диаметра и радиуса как абстрактных, так и конкретных многогранников, представляющих собой . области определения некоторых задач ЛП.
Реферируемая работа посвящена исследованию комбинаторных характеристик многогранников, широко распространенных в приложениях задач транспортного типа. В ней решается ряд известных проблем и гипотез комбинаторной теории транспортных многогранников и достаточно полно изучена также новая проблематика, касающаяся сложности многокритериальных задач (МКЗ) дискретной оптимизации (ДО).
Толчком к исследованию задач ДО послужила необходимость решения задач оптимального развития и размещения производительных сил, автоматизации проектирования и компьютерной графики, интегрированных производственных систем и оптимального управления. Для их решения в однокритериальной постановке были созданы универсальные схемы последовательного анализа вариантов (В.С.Ми-халевич и Н. 3. Шор), метод построения последовательности планов (В.А. йлеличев), метод вектора спада (И.В. Сергиенко), локальные алгоритмы (Ю. И. Журавлев и С. В. Яблонский). Существенный прогресс в решении экстремальных задач на подстановках связан с алгебраическим подходом Д. А. Супруненко, Дальнейшее развитие качественная теория ДО получила в работах Э. Н. Гордеева, В. С. Гордона, М. М. Ковалева, В.К. Леонтьева, Н.Н. Метельского, В.А. Перепелицы, В.П. Солтана, П.С. Солтана, В. И. Сарванова, Ю. Н. Сотскова, В. С. Танаева, В. А. Трубина, Я. М. Шафранского, В. Н. Шевченко и др. Среди работ зарубежных математиков в области теории ДО следует отметить работы Р. Беллмана, П. Брук-кера, Р. Буркарда, Э. Гирлиха, М. Гери, Д. Джонсона, А. Джоффри-она, Р. Карпа, Е. Лоулера, Д. Фулкерсона, Ж. Эдмондса.
Цель И задачи диссертационной работы. Целью исследования является разработка новых методов решения проблем и гипотез полиедральной комбинаторики в задачах оптимизации с ограничениями транспортного типа, а также проблем сложности и устойчивости МКЗ ДО. Цель обусловила постановку и решение следующих основных задач:
- исследовать структуру и свойства множества допустимых решений разнообразных транспортных задач (ТЗ) ЛП (как
двухиндексных, так и многоиндексных), а также возможность применения полученных теоретических результатов в практике решения таких задач;
провести анализ вычислительной сложности поиска паретовс-кого множества и некоторых его подмножеств разнообразных МКЗ ДО;
исследовать вопрос о разрешимости МКЗ на системах подмножеств в классе алгоритмов линейной свертки критериев (АЛСК);
- исследовать отношение между паретовским множеством
дискретной МКЗ и множеством оптимальных решений соответствующей
параметрической задачи оптимизации с одним агрегированным
критерием;
- изучить особенности подхода к решению МКЗ на системах
подмножеств с упорядоченной совокупностью критериев.
йеТОДЫ исследования. В работе используются методы комбинаторного анализа, теории графов, комбинаторной топологии, дискретной и многокритериальной оптимизации, теории вероятности.
Научная НОВИЗНа. В диссертации получены следующие результаты:
- доказана гипотеза Болкера (Bolker Е. Transportation
polytopes// J. оГ Comb. Th. - 1972. - V. 13. - P. 251 - 262) о
степени полинома в представлении максимального числа вершин
классического транспортного многогранника (КТМ);
- найдены критерии принадлежности невырожденного КТМ с
заданным числом фасет (т. е. граней максимальной размерности) к
классу многогранников с минимальным и максимальным числом
k-граней всех размерностей, и выяснено асимптотическое поведение
указанных классов при возрастании порядка многогранника;
- выведена формула для минимального числа k-граней и
разработан аппарат для подсчета максимального числа k-граней
КТМ;
указаны достижимые нижние оценки диаметра и радиуса, а также оценки сверху для максимального диаметра и радиуса в классе КТМ о заданным числом фасет:
доказана гипотеза Дюбуа (Dubois J. Polytopee <1е ЪгапярогЧ ejrotmetriguee// Discrete Mathematics. - 1973- - V. 4, N 1. - P. 1 - 27) о максимальном числе вершин симметрического транспортного многогранника:
выведены формулы для подсчета числа базисов многограннике
- 4 -ТЭ о запретами, обобщающие известные формулы Симмонарда-Хедли (Simmonard М.. Hadley G. The maximum number ol iterations in the transportation problem// Naval Research Quarterly. - 1959. - V. 6, N2. -P. 125 - 129) и Кононенко-Трухановского (Кононенко A. M., Трухановский Н. Н. Перечисление максимальных деревьев одного класса двудольных графов// Изв. АН БССР. Сер. физ.-мвт. наук. -1978. - N 6. - С. 111 - 113):
доказана теорема о представлении многогранника ТЗ с запретами и ограниченными пропускными способностями в виде произведения многогранников меньшего порядка;
найден критерий принадлежности многоиндексного планерного транспортного многогранника к классу многогранников с максимальным числом вершин;
указаны достижимые нижние оценки диаметра и радиуса, а также оценки снизу для максимального диаметра и радиуса в классе многоиндексных аксиальных транспортных многогранников о заданным числом фасет;
найдены критерии минимальности и максимальности числа целых точек многоиндексного аксиального транспортного многогранника;
получено обобщение теоремы Емеличева-Крачковского И, с. 2531, касающейся асимптотического поведения КТМ, на случай многоиндексных аксиальных транспортных многогранников:
доказана экспоненциальная сложность (труднорешаемость) многокритериальных целочисленных задач стандартизации и землепользования, а также разнообразных задач транспортного типа;
установлено, что МКЗ на системах подмножеств с линейными критериями и критериями "узкого места" в произвольном сочетании при некоторых дополнительных условиях на системы подмножеств неразрешимы с помощью классического приема - алгоритмов линейной свертки критериев (АЛСК). Этот результат включает в качестве частных случвев вое ранее известные теоремы, касающиеся неразрешимости МКЗ ДО, которые были ранее получены В. А. Емеличевым и В. А. Перепелицей (Емеличев В. А., Перепелица В. А. Сложность дискретных многокритериальных задач// Дискрет, мат. -1994. - Т. 6. Вып. 1. - С. 3 - 33);
доказано, что всякий лексикографический оптимум в МКЗ на конечном множестве допустимых решений с критериями произвольной
- 5 -природа может быть получен с помощью АЛСК;
показана принципиальная возможность использования АЛСК для нахождения паретовского множества в МКЗ на системах подмножеств с одним критерием произвольной природы и несколькими критериями "узкого места";
предложена общая алгоритмическая схема нахождения решения МКЗ на системах подмножеств с упорядоченной совокупностью критериев, позволившая разработать полиномиальные алгоритмы для задач об остовных деревьях и цепях, о совершенных паросочетаниях и назначениях, о маршрутизации и целочисленной ТЗ;
- найдены критерии устойчивости, КЕазиустойчивости и
стабильности МКЗ на системах подмножеств с линейными критериями.
Результаты диссертационной работы можно квалифицировать как направление в дискретной оптимизации, связанное с разработкой новых методов решения проблем и гипотез ПК в задачах транспортного типа, а также проблем сложности и устойчивости МКЗ на системах подмножеств.
Практическая цеННОСТЬ. Прикладное значение полученных в диссертации результатов обусловлено тем обстоятельством, что исследованные в ней задачи являются математическими моделями многих практических задач икономики, техники и естествознания. Теоретические разработки реферируемой работы служат в качестве методологической основы при исследовании и создании эффективных алгоритмов и программных средств решения оптимизационных задач рассматриваемого вида.
Выявленные в диссертации комбинаторные и метрические свойства, а также разработанный аппарат для подсчета числа k-граней любой размерности транспортных многогранников могут нейти широкое применение при решении практических ТЗ и дальнейшем изучении свойств многогранников в задачах ЛП.
Некоторые результати проведенных исследований нашли применение при решении практических задач по рациональному использованию топливно-энергетических ресурсов и местных стройматериалов в РБ в трех кандидате тх работах ученикоз автора. В настоящее время в БелНШШ АПК Академии аграрных наук РБ ка основе предложенных алгоритмов под научным руководством автора разрабатываются программные средства для решения задач перевозки сельскохозяйственных грузов (молока, кормов, скота).
Часть материалов диссертации вошла в спецкурс
"Многокритериальная оптимизация", читаемый автором на факультете прикладной математики и информатики Белгоеуниверситета.
Публикации, ЛИЧНЫЙ вклад. По результатам дисссертации опубликовано 75 научных работ, в том числе одна монография [1], переведенная на английский язык издательством "Cambridge University Press" (Великобритания) в 1934 году и на немецкий -издательством "VEB Deuteoher Verlag der (Wssenechaften*' (Гермзния) в 1985 году, и пять обзоров [2 - 6].
Основные результаты получены автором лично. Конкретный вклад соавторов публикаций указан во введении к диссертации и в автореферате.
Апробация работы. Результаты, изложенные в диссертации, докладывались на Международных конференциях по исследованию операций (София, 1980: Минск, 1993), на Всесоюзных семинарах по комбинаторному анализу, дискретной математике и ее приложениям (Москва, 1978, 1981, 1987, 1990), на Всесоюзных семинарах по дискретной математике и по графам, гиперграфам и алгебраическим системам (Одесса, 1976, 1979, 1980), на Одесском научно-исследовательском семинаре по дискретной математике Южного научного центра АН УССР (Одесса, 1991), на IV, V и VI конференциях математиков Беларуси (Минск, 1975; Гродно, 1980, 1992), на научно-технической конференции "Моделирование сельскохозяйственных процессов и машин (Минск, 1994), на семинарах лаборатории математической кибернетики в ИМ АН Беларуси и кафедры МО САПР Белгоеуниверситета.
Структура И Объем рабОТЫ. Диссертация состоит из введения, пяти глав (содержащих 34 параграфа), заключения, списка цитированной литературы из 258 наименований. Общий объем работы 303 страницы машинописного текста.
