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

Академия наук Беларуси Институт технической кибернетики

КРАВЦОВ Михаил Константинович

ргВ од

- 2 ЯНВ 1Вйз

УДК 519.10

ПОЛИЭДРАЛЬНЫЕ АСПЕКТЫ ТРАНСПОРТНЫХ ЗАДАЧ И СПОЖН(ХЛЪМНОК)КРИГЕРИАЛЬНЬ1Х ЗДЦАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ

05.13.16 - применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

АВТОРЕФЕРАТ

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

Минск -1994

Работа выполнена в Белорусском научно-исследовательском институте (экономики и информации АПК Академии вграрних неук РБ

Научный консультант! доктор физико-математических наук»

профессор ЕМЕЛИЧЕВ В. А.

Официальные оппоненты! доктор физико-математических наук,

профессор СОТСКОВ Ю. Н., доктор физико-математических наук, профессор ШЕВЧЕНКО В. Н., доктор физико-математических наук, профессор ПЕРЕПЕЛИЦА В. А.

Ведущая организация! Институт математики Академии наук Беларуси

Зеэдтв состоится " 16 " рО. А $ 1995 г. в

чаеов на заседании специализированного совета Д 006.24.01 при Институте технической кибернетики Академии наук Беларуси по адресу! 220012, Минск, ул. Сурганова, 6.

С диссертацией можно ознакомиться в библиотеке Института технической кибернетики Академии неук Беларуси.

Общая характеристика работы

Актуальность темы. Полиэдральная комбинаторика (ПК) - один из наиболее перспективных и бурно развивающихся разделов дискретной математики, возникший на стыке комбинаторной геометрии, теории графоь и оптимизации. Ее проблематика и первоначальные результаты восходят к Р. Декарту, Л.Эйлеру, 0.Ковш, А. Пуанкаре, Г. Минковскому, А.Д. Александрову и Г. Вейлю. В ПК наряду с классическими проблемами - перечисление и классификация многогранников, характеризация остовных комплексов, рассматриваются новые - построение выпуклы* оболочек и изучение метрических свойств графов многогранников. Популярность ПК в наше время, превде всего, объясняется возможностью применения ее аппарата для оценки трудоемкости методов оптимизации и перспективами построения на ее основе эффективных алгоритмов.

Графы (реберные остовы) многогранника исследуются как для абстрактных многогранников, задаваемых системой линейных неравенств общего вида (работы Г. Бартельса, А. Бренотедя, Б.Грюнбаума, Д. Данцига, И.И. Еремина, Л.В. Канторовича, В. Кли, П. Макмюллена, Л. Г. Хачияна,' В. С. Чарина, С. Н. Черникова, Н. 3. Шора и др.), так и для многогранников конкретных задач оптимизации: коммивояжера, стандартизации, проблемы выбора, транспортной и комбинаторной оптимизации (работы М. Белинского, Е. Болкера, Ж. Дюбуа, В. А. ЕХ»еличева, В. Кли, М. М. Ковалева, А-П. Крачковского, В.Н. Шевченко и др.). При втом подсчитыввютоя или оцениваются такие характеристики многогранников, как число вершин, диаметр, радиус, обхват и др. Некоторые из них определенным образом связаны с оценкой числа итераций и эффективностью алгоритмов симплексного типа в задачах линейного программирования (ЛП). Действительно, если, например, требуется определить екстремун линейной функции не многограннике, то максимальное количество его вершин можно считать верхней границей числа итераций. Диаметр многогранника есть число итераций наилучшего симплексного алгоритма (если, конечно, такой Лудет построен) при наихудшем расположении стартовой и оптимальной вершин. Относительно радиуса можно сказать следующее! если радиус многогранника равен р. то существует такая стартовая вершина, что при любом расположении оптимальной вершины число итераций наилучшего симплексного алгоритма не превосходит числа г.

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

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

Толчком к исследованию задач ДО послужила необходимость решения задач оптимального развития и размещения производительных сил, автоматизации проектирования и компьютерной графики, интегрированных производственных систем и оптимального управления. Для их решения в однокритериальной постановке были созданы универсальные схемы последовательного анализа вариантов (В.С.Ми-халевич и Н. 3. Шор), метод построения последовательности планов (В.А. Емеличев), метод вектора спада (И.В. Сергиенко), локальные алгоритмы (Ю. И. Журавлев и С. В. Яблонский). Существенный прогресс в решении экстремальных задач на подстановках связан с алгебраическим подходом Д. А. Супруненко, Дальнейшее развитие качественная теория ДО получила в работах Э. Н. Гордеева, В. С. Гордона, М. М. Ковалева, В.К. Леонтьева, H.H. Метельского, В.А. Перепелицы, В.П. Солтана, П.С. Солтана, В. И. Сарванова, Ю. Н. Сотскова, В. С. Танаева, В. А. Трубина, Я. М. Шафранского, В. Н. Шевченко и др. Среди работ зарубежных математиков в области теории ДО следует отметить работы Р. Беллмана, П. Брук-кера, Р. Буркарда, Э. Гирлиха, М. Гари, Д. Джонсона, А. Джоффри-она, Р. Карпа, Е. Лоулера, Д. Фулкерсона, Ж. Эдмондса.

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

- исследовать структуру и свойства множества допустимых решений разнообразных транспортных задач (ТЗ) ЛП (как

- з -

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

- провести анализ вычислительной сложности поиска паретовс-кого множества и некоторых его подмножеств разнообразных МКЗ ДО;

- исследовать вопрос о разрешимости МКЗ на системах подмножеств в классе алгоритмов линейной свертки критериев (АЛСК);

- исследовать отношение между паретовским множеством дискретной МКЗ и множеством оптимальных решений соответствующей параметрической задачи оптимизации с одним агрегированным критерием;

- изучить особенности подхода к решению МКЗ на системах подмножеств с упорядоченной совокупностью критериев.

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

Научная новизна. В диссертации получены следующие результаты:

- доказана гипотеза Болкера (Bolker Е. (transportation polytopes// J. of Comb. Th. - 1972. - V. 13. - P. 251 - 262) о степени полинома в представлении максимального числа вершин классического транспортного многогранника (КТМ);

- найдены критерии принадлежности невырожденного KIM с заданным числом фасет (т. е. граней максимальной размерности) к классу многогранников с минимальным и максимальным числом k-граней всех размерностей, и выяснено асимптотическое поведение указанных классов при возрастании порядка многогранника;

- выведена формула для минимального числа k-граней и разработан аппарат для подсчета максимального числа k-граней КТМ;

- указаны достижимые нижние оценки диаметра и радиуса, а также оценки сверху для максимального диаметра и радиусе в классе КТМ о заданным числом фасет:

- доказана гипотеза Дюбуа (Dubois J. Polytopee de tmnoport eyntmetrigues// Discrete Mathematics. - 1973- - 7, 4, N 1. » P. 1 - 27) о максимальном числе вершин симметрического транспортного многогранника:

- выведены формулы для подсчета числа базисов многогряннш«

ТЗ о запретами, обобщающие известные формулы Симмонарда-Хедли (Simmonard M.. Hadley G. The maximum number of iterations in the transportation problem// Naval Research Quarterly. - 1959. - V. 6, N2. -P. 125 -129) и Кононенко-Трухановского (Кононенко A. M., Трухановский H. H. Перечисление максимальных деревьев одного класса двудольных графов// Изв. АН БССР. Сер. физ.-мат. наук. -1978. - N 6. - С. 111 - 113):

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

- найден критерий принадлежности многоиндексного планерного транспортного многогранника к классу многогранников с максимальным числом вершин;

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

- найдены критерии минимальности и максимальности числа целых точек многоиндексного аксиального транспортного многогранника;

- получено обобщение теоремы Емеличева-Крачковского И, с. 2531, касающейся асимптотического поведения КТМ, на случай многоиндексных аксиальных транспортных многогранников:

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

- установлено, что МКЗ на системах подмножеств с линейными критериями и критериями "узкого места" в произвольном сочетании при некоторых дополнительных условиях на системы подмножеств неразрешимы с помощью классического приема - алгоритмов линейной свертки критериев (АЛСК). Этот результат включает в качестве частных случаев вое ранее известные теоремы, касающиеся неразрешимости МКЗ ДО, которые были ранее получены В. А. Емеличевым и В. А. Перепелицей (Емеличев В. А., Перепелица В. А. Сложность дискретных многокритериальных задач// Дискрет, мат. -1994. - Т. 6. Вып. 1. - С. 3 - 33);

- доказано, что всякий лексикографический оптимум в МКЗ на конечном множестве допустимых решений с критериями произвольной

- 5 -

природы может быть получен с помощью АЛСК;

- показана принципиальная возможность использования АЛСК для нахождения паретовского множества в МКЗ на системах подмножеств с одним критерием произвольной природы и несколькими критериями "узкого места";

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

- найдены критерии устойчивости, КЕазиустойчивости и стабильности МКЗ на системах подмножеств с линейными критериями.

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

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

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

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

Часть материалов диссертации вошла в спецкурс

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

Публикации, ЛИЧНЫЙ вклад. По результатам дисссертации опубликовано 75 научных работ, в том числе одна монография [1], переведенная на английский язык издательством "Cambridge University Press" (Великобритания) в 1984 году и на немецкий -издательством "VEB Deuteoher Verlag der Wissenschaften" (Гермзния) в 1985 году, и пять обзоров [2 - 6].

Основные результаты получены автором лично. Конкретный вклад соавторов публикаций указан во введении к диссертации и в автореферате.

Апробация работы. Результаты, изложенные в диссертации, докладывались на Международных конференциях по исследованию операций (София, 1980: Минск, 1993), на Всесоюзных семинарах по комбинаторному анализу, дискретной математике и ее приложениям (Москва, 1978, 1981, 1987, 1990), на Всесоюзных семинарах по дискретной математике и по графам, гиперграфам и алгебраическим системам (Одесса, 1976, 1979, 1980), на Одесском научно-исследовательском семинаре по дискретной математике Южного научного центра АН УССР (Одесса, 1991), на IV, V и VI конференциях математиков Беларуси (Минск, 1975; Гродно, 1980, 1992), на научно-технической конференции "Моделирование сельскохозяйственных процессов и машин (Минск, 1994), на семинарах лаборатории математической кибернетики в ИМ АН Беларуси и кафедры МО САПР Белгосуниверситета.

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

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

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

Первая глава диссертации "Классические транспортные многогранники" посвящена исследованию области определения классической ТЗ, т. е. множества

n m

M(a, b) = (x - Uijl^t £ xld - at vi * *m. £ x^ = bj

vj € Nn, Xjj i о v(i, J) € Nm X Nn>, где a = (a1..... am),

b = (b1#..., b ) - векторы с действительными положительными m n

компонентами, £ a, = £ b.,, = {1, 2,—, k), m, n > 1.

1=1 1 3=1 J K

Множество M(a, b) будем называть классическим транспортным

многогранником (КТМ) порядка mxn.

В §1 проводится классификация КТМ по числу фасет. Под

фасетой КТМ порядка mxri будем понимать грань максимальной

размерности, т. е. (d - 1)-грань, где d = (m - 1)(n - 1).

Показано, что для всякого t = О, 1,____ п справедливо

утверждение: если число фасет невырожденного КТМ порядка mxn, 3«

s m s п, равно (m - 1)n + t, то среди них имеется не более t

симплексов.

В §2 введены новые понятия, такие как эквивалентность, регулярность и спектр, позволившие разработать аппарат для подсчета числа к-граней любой- размерности КТМ.

Спектром двух КТМ М(а°, Ь°) и М(а1, Ь1) одного и того же

порядка назовем множество S(a°, b°, a1, b1) всех чисел X €(0,1),

для каждого из которых М((1 - Х)а° + Ха1, (1 - X)b° + Xb1) -вырожденный многогранник.

В 1968 г. В. Кли и X. Витцгалл высказали гипотезу о том, _ g £ $

что КТМ М(а , b ) порядка туп, определенный векторами а = (п, *

..., п) и b = (m.....m), при взаимно простых числах тип имеет

максимальное число f>(m, п) вершин. В 1972 г. Е. Болкер (ссылку см. на с. 3) доказал ету гипотезу. В § 3 этот результат обобщается и указывается следующий критерий.

Теорема 1. '

КТМ М(а, Ь) порядка шхп имеет максимальное

число f>(m, п) вершин тогда и только тогда, -огда он невырокден и $ *

спектр S(a, b, а , b ) = я.'

Разработаны два способа вычисления п), которые

*) Нумерация теорем в автореферате не совпадает с нумерацией в диссертации.

сводятся к подсчету количестве вершин нескольких КТМ меньшего порядка. С помощью одного из них доказана (совместно с В.А. Еме-личевым и А. П. Крачковским) следующая теорема, высказанная в 1972 г. Е. Болкером (ссылку см. на с. 3) в виде предположения. Теорема 2. ц>(т, п) - —!1—P(q, m, г),

(q'.)m

где m s n, n = mq + г, г - остаток от деления п на m, P(q,m,r) -

многочлен от q со старшим членом mm~2qm-r~1.

В терминах спектра получен критерий принадлежности невырожденного КТМ с заданным числом фасет к классу многогранников с максимальным числом вершин (§4).

Теорема 3. Пусть msn, t s t î п - 2, Если t s n / m(t > > n / m), то максимальное число вершин невырожденного КТМ порядка mxn с (т - 1)п + t фасетами равно (больше) m (n - t) ~ .

В §5 найден критерий принадлежности многогранника порядка mxn к классу Я1^(т, п) невырожденных КТМ с максимальным числом к-

граней vk «(0,1,... ,<1-1) и разработан аппарат для подсчета этого числа. Отправной точкой при их доказательстве служит понятие спектра двух КТМ.

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

Теорема 4. Я10(т, п) = й^т, п) = ... = ^(т, п) с JUj^im,

п) = n) s ... с Bd_.|(m, п), где г = [Зтп / 4] - m - п+1.

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

Как следствие последней теоремы получаем следующее существенное обобщение теоремы Крачковского (см. [1, с. 254]), которая опровергает известную гипотезу Болкера (ссылку см. на о. 3) об асимптотике КТМ с максимальным числом вершин: для всякого k е {О, 1,..., г} почти нет КТМ с максимальным числом к-граней.

С помощью неравенства Чебышева для вероятности случайной величины совместно с В. А. БХлеличевым и А. П. Крачковским доказана

Теорема 5. Почти все КТМ имеют максимальное число (d - 1)-граней, где 1 = min ([2m / ln m], [2n / ln n]}.

С учетом теоремы 4 отсюда получаем утверждения: 1) для

любого q с Nj почти вое КТМ имеют максимальное число (d - q)-

гряней; 2) ТЗ с запретами порядка mxn почти всегда разрешима, если количество запретов не превосходит числа 1.

Ранее утверждение 1) было известно лишь для q = 1 (см. теорему 10.1 гл. VI [1]).

Основными результатами §6 являются следующие две теоремы, первая из них получена совместно с А. П. Крачковским, а вторая -самостоятельно.

Теорема 6. Пусть и s n, п г 5, 1 « t t п. Невыроаденннй КТМ М(е, Ь) порядка туп о (т - 1)n + t фасетами тогда и только

тогда имеет минимальное число nm_1 + t(mn - ra - п) вершин, когда выполняются неравенства

i) при m = 2

bn-U1 < а2 < rain íbn-f bn-1 + bn>!

ii) при 3 s m < n

n-1

Vui - bn < jS - а1 < mln {V Vt - (1)

ill) при m = n г 5 либо (1), либо m-1

Vt+1 " ftm < ai " b1 < min {V am-t " V'

РД9 8, г ÍJ г ... г ащ, b1 г г ... 2 bn> aQ = bQ = «о.

Теорема 7. Пусть 3smsn, п г 5. Тогда для всякого числа t € Nn справедливо утверждение! среди фасет невырожденного КТМ

порядке mxn с (m - 1)n + t фасетами имеется ровно t симплексов тогда и только тогда, когда этот многогранник имеет минимальное число вершин.

Тем самым теорема 7 дает утвердительный ответ на вопрос, поставленный в [1, с. 266].

В §7 получены критерии принадлежности невырожденного КТМ порядка mxn с заданным числом фасет к классу многогранников с минимальным числом k-граней vk е {0, 1,..., d - 2} и выведена формула для подсчета этого числа. Отправной точкой доказательства етих результатов являются принцип включения и исключения и понятие спектра двух КТМ.

Широкую известность получила гипотеза Гирша о максимальном диаметре A(d, ц) выпуклого й-многогранника с 7 фасетами.

приведенная Данцигом в 1957 г., согласно которой A(d, 7) * > - d (см. [1, с. 60]). Доказательство втой гипотезы означало бы по крайней мере принципиальную возможность существования такого симплексного алгоритма, который решает задачу ЛП с числом итераций, не превосходящим у - d.

В настоящее время гипотеза Гирша доказана для двух частных случаев: 1) jrsd + 5. 2) d s 6 (Кли и Валкуп, 1967). Она также доказана для многогранников, порожденных задачами о кратчайшем пути (Сайгал, 1969),о назначениях (Белинский и Руссакоф, 1974), о коммивояжере (Подберг и Pao, 1974), задачей двойственной к транспортной (Белинский, 1984) и транспортной задачей (Кравцов М. К. Доказательство гипотезы о максимальном диаметре для транспортного многогранника// Кибернетика. - 1985. - N 4. - С. 79 - 82).

Заметим, что проведенное нами доказательство гипотезы Гирша для КТМ является чрезвычайно громоздким и мы (из-за недостатка места) вынуждены были не включать этот результат в состав диссертации. Вместо него в работе приведен несколько более слабый результат, для которого найдено настолько простое и прозрачное доказательство, что оно заслуживает изложения.

В §§8 - 10 исследуются метрические характеристики графа КТМ такие как диаметр, радиус и обхват. Среди результатов, полученных здесь, значительный интерес представляют, на наш взгляд, следующие утверждения:

1) минимальный диаметр в классе невырожденных КТМ порядка mxn, m s п, с числом фасет (m - 1)п + t равен числу m + t - 1, если t = О, 1, и числу m + 1, если 2 s t s n;

2) минимальный радиус в классе невырожденных КТМ порядка mxn, m s п, с числом фасет (m - 1)n +• t равен числу m - 1, если Os t su - 1, и числу m, если m s t s n;

3) максимальный радиус в классе невырожденных КТМ порядка mxn, m s п, с числом фасет (m - 1)n + t равен числу т + t - 1, если О s t í п - 2, и числу т + п - 3, если t = п - 1;

4) максимальный диаметр в классе КТМ порядка mxn не превосходит числа mn;

5)граф всякого невырожденного КТМ порядка mxn, ) s л s n, содержит цикл любой длины t е {3, 4,..., ш};

6) граф всякого невырожденного КТМ порядка mxn, m s п, п*5, с (m - 1)n + t фасетами и минимальным числом вершин является

- 11 -

паговдклическим, т. е. содержит цикл любой длины.

§11 посвящен изучению свойств числе целых точек (ЦТ) КТМ М(а, Ъ) порядка mxn в случае, когда компоненты векторов а и Ь

m п

являются целочисленными. Число k = Е а, = £ Ь. будем

1=1 1 j=1 •>

называть весом многогранника М(а, Ь). Для любого целого числа ka

* max {m, п) получены критерии принадлежности КТМ порядка im о

весом к к классу многогранников с минимальным и максимальным

числом ЦТ. Выведена формула для минимального числа ЦТ. Найдены

условия, при выполнении которых всякая ЦТ КТМ является его

вершиной.

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

В § 1 получены критерии принадлежности сишетрического транспортного многогранника М(а, а) порядка шл к классу многогранников с максимальным числом ip(n) вершин и разработан аппарат для подсчета этого числа, с помощью которых доказана гипотеза Дюбуа (ссылку см. на с. 3), согласно которой р(п) г

2 V А (к2 + 1).

J=0 к=0

§ 2 посвящен изучению области определения широко известной ТЗ с запретами и ограниченными пропускными способностями, т. е. множества М(а, b, D), состоящего из матриц х, элементы которых удовлетворяют условиям

1!1хивЪа ¿1Iijeai vl€V <2>

xid • du = 0 vtl- e HD Í Nm * V <3>

0 s *1J 5 diy dij > v(i' í> e <Nm * V 4 HD-

где векторы а = (а,..... am), b = ¿b.,,..., b ) имеют

действительные положительные, а матрица D = ¡'.Ь J¡

-1- yj [UXÍ i

действительные неотрицательные компоненты; HD - множество нулевых ш п

элементов матрицы D, £ а, = V ь.,, m, п > 1. 1-1 1 3=1

Непустое множество М(а, Ъ, D) будем называть усеченным транспортным многогранником (УТМ) порядка mxn.

УТМ называется регулярным, если: 1) у него существует внутренняя точка х, т. е. точка с условиями

0 < < diJ v(1- J) « <Nm * Mn> 4 HD! 2) ранг системы уравнений (2) и (3) равен m + n + |HD|-1.

Из этого определения следует, что размерность всякого регулярного УТМ порядка mxn равна числу (гп - 1)(п - 1) - |HD|.

Теорема 8. УТМ М(а, b, D) порядка mxn является регулярным тогда и только тогда, когда выполняются условия

¿/ij > ai vl € V

m

Z min Ía1, £d1i}> £ Ц vJ с L. 1=1 1 JeJ 13 JcJ 3 n

Пусть Ed - евклидово d-мерное пространство. Произведением

двух многогранников М1 в Е^ и М2 в Е^ называется множество

М, * М2» {(х1, х2): х1 с Hj. i = 1, 2>.

Для нерегулярного УТМ М(а, b, D) порядка mxn введем в рассмотрение множества

Р = (U. jb xi;j = d1;I * 0 vx « М(а, b, D)},

Q s ((i. i) « HD: x13 =0 vx € U(a, b, D)J.

Через D[I, J] обозначим подматрицу матрицы D расположенную в строках I с Nffl и столбцах J s Nn.

Теорема 9. Всякий нерегулярный непустой и не вырождающийся в точку УТМ М(а, b, D) порядка mxn представим в виде произведения регулярных УТМ и точки, причем единственным

образом, т. е. М(а, b, D) = М(а1, Ь1, Dfl.,. J.,]) » Mía2, b2,

Dtl2. J21) ® ... ® M(ak, bk, D[Ik, Jkl) e R(P, Q), где ^.....Ik

(J1.....Jk) - попарно непересекающиеся подмножества множества

Nm (Nn), R(P, Q) - точка о координатами

ГО, воли (1. 3) € Q и (Hn \ и (1р у Jp)).

= i Р=1

(Д^, если (1, 3) € Р.

к

Теоремы 8 и 9 получены совместно с А. Д. Корзниковым.

Для регулярных УТМ указаны пределы изменения числа фасет, получены достижимые нижние оценки для числа вершин и диаметра, выделены многогранники, являющиеся симплексами.

В 3 изучается (к, ^-усеченный транспортный многогранник ((k, t)-5TTM) Мк t(a, b) = (i « М(а, b)s х^ = О v(i, J) « Н}

порядка mxn, где О s k, t s min {ш, n} - 1, k, t - целые числа, H= = ((i, 3):3-i>n-t-1vi-3>m-k-1).

Теорема 10. Пусть k + t г 1. (k, t)-yiM Mk t(a, b) порядка mxn непуст тогда и только тогда, когда выполняются неравенства

в e+n-t-1

£ а, л £ Vfl с при t > О, (4)

1=1 " 1

в e+m-k-1

£ b4 s £ a., V8 б при к > О. (5)

J=1 " 1=1 К

Отметим, что в случае когда m = n, k = t = п - 2, вта теорема превращается в теорему Лева (Lev В. A noniteratlve algorithm for trldlagonal transportation problem and Its generalisation// Oper. Res. - 1972. - V. 20, N 1. - P. 105-125).

Теорема 11. Пусть k + t*1,m+n-k-t>3. (к, t)-yTM M^ t(a, b) порядка mxn имеет максимальную размерность d = (m -

- 1)(п - 1) - [k(k + 1) + t(t + 1)] / 2 тогда и только тогда, когда все неравенства (4) и (5) являются строгими.

Показано, что среди (k, t)-yTM порядка mxn, k + t г 1, максимальной размерности d существуют d-симплексы лишь в случаях: 1) m + n - k- t = 3; 2) (к - 1)(t - 1) = 0; 3) mln {m, n) « з, max {к, t> = 2; 4) m = n = 4, min (k, t} = 0, max (k, t} = 3.

На основе матричной теоремы Кирхгофа о числе остовных деревьев графа выведены три новые формулы для подсчета числа базисов ТЗ с запретами в случаях, когда множество запретов устроено некоторым специальным образом (§4). Эти формулы обобщают известные формулы Симмонарда-Хедли и Кононенко-Трухановского (ссылки см. на с. 4), предназначенные для числа

Оазисов соответственно ТЗ и ТЗ с запретами. Кроме того, совместно о А. А. Гладким с помощь» метода Прюфера найдена достаточно точная оценка сверху для числа базисов ТЗ с произвольной конфигурацией множества запретов и получен критерий принадлежности ТЗ порядка mxn с к запретами (1 * к s min {m, n)) к классу задач с максимальным числом базисов и выведена формула для подсчета этого числа.

В § 5 исследуется область определения обобщенной ТЗ (Х-задачи), т. е. множество:

М(Л. а. Ь) = {х = Д хи = ах vi * Nm. Д Х^ -

= bj V3 в Nn. z^ г О V(l, J) с Nm v Nn>,

где векторы а = (а^..., ащ), b = (b.,,..., Ьд) и матрица А ■

= |Xjj|mJín имеют действительные положительные компоненты.

Непустое множество М(Л, а, Ь) будем называть Л-обобщенным транспортным многогранником (А-ОТМ) порядка mxn, если оно не является КТМ.

Теорема 12. Пусть min {m, Ii) г 4. Тогда для всякого числа t= = 2,..., m + п - 1 справедливо утверждение: максимальный диаметр в классе невырожденных А-ОТМ порядка mxn с (га - 1)(п - 1) + t фасетами не меньше числа t + 1.

Тем самым опровергнута гипотеза 2 обзора 15], так как установлено существование А-ОТМ порядка mxn, min {m, n> г 4, о диаметром, не меньшим числа m + п.

Теорема 13, Всякое целое число от 1 до m + п - 2 . реализуется как диаметр некоторого невырожденного А-ОТМ порядка mxn, min {m, n) г 4.

Эта теорема обобщает и углубляет соответствующий результат В. М. Лихачева (Лихачев В. М. Качественные исследования обобщенных и многоиндексных транспортных задач// Автореф. дие. на соиск. уч. с. к. ф.-м. н. - Минск: ИМ АН БССР. -1981. -19 е.).

Третья глава посвящена изучению многогранника р-индаксной аксиальной ТЗ (р-АТМ) терминологию см. в [1]. Для таких многогранников получены следующие результаты: найдены критерии минимальности и максимальности числа ЦТ и критерий минимальности числа целочисленных вершин (ЦВ) (§2)j указаны оценки снизу для максимального числа вощин (§1) и ЦВ (§2); выведена рекуррентная

формула для минимального числа ЦТ (§ 2); указаны достижимые нижние оценки диаметра и радиуса, а также оценки снизу для максимального диаметра и радиуса в классе многогранников с заданным числом фасет (§3); установлена гамильтоновоеть графа невырожденного многогранника с минимальным числом вершин (тем самым доказана гипотеза 32 [1, с. 321]); выяснено асимптотическое поведение некоторых классов при возрастании порядка многогранника (§4), т. е. показано, что с ростом порядка многогранника отношение числа многогранников с максимальным количеством фасет к общему числу многогранников стремится к единице, а отношение числа многогранников с минимальным количеством вершин - к нулю (тем самым получено существенное обобщение теоремы ЕМеличева-Крачковского [1, е. 253], касающейся асимптотического поведения КТМ).

В главе IV изучается р-индексный пленарный транспортный

многогранник (р-ПШ) М(А.....Ар) = {|х< , |: Е г, ' * =

X А • • • 1— X 4 • • • 1-

1 р =1 1 р

= а. , , , VI «Н У8 « К \ ш, VI € N .

1Г"П-111:+Г-,1р 8 "в р р

где

Г-"р "а * ' *

А*

- ------- ■ -р

действительными элементами.

Для двух р-ПТМ М1 = М(А1..... Ар) и М2 = 1КВ1..... Вр)

одного и того же порядка рассмотрим матрицы: а£ = ХА*' + (1 - Х)В*

уг € х с [о, 1].

Спектром многогранников М1 и М2 назовем множество Б(А1,...,АР;

В1.....Вр) всех чисел X € (0,1), для каждого из которых

А^) - вырожденный многогранник.

Используя аппарат симплициальной геометрии (комбинаторной топологии), а также понятие спектра двух многогранников (§§ 1-3), получен следующий критерий (§4).

Теорема 14. пусть пг ^ г з, 4 г, г = э.4,....р. р-пта

1Г..1 20 € Мп * ув * порядка П1 «... х Пр,

= ¡а1 , , 1 I - заданная матрица с положительными

^••■П-ТП+Г- р

- 1b -

М(А1.....Ap) порядка n^ ... x Пр имеет максимальное число

вершин тогда и только тогда, когда он невырожден и спектр S(A1,...,

А»« XV.... ip> = в, где елементы матрицы Ä определяются

следующим образом: а, . > 1 = nt vl„ с N„ vscNA{t).

1' t-1 t+1*'•1p 1 8 ne' p

Следствием этой теоремы является следующий результат Болкера

(Bolker E.D. Slaipliolal geometry and transportation polytopes//

Transactlons of the Amer. Math. Soo. - 1976. - V. 217. -P. 121 -

142): невыроаденный р-ПТМ M(A1,..., iP) имеет максимальное число вершин, если он принадлежит некоторой достаточно малой

окрестности многогранника М(Г.....Р>).

Совместно с В. А. йлеличевым и А. П. Крачковским доказано, что всякий р-ПТМ с максимальным числом вершин имеет максимальное число граней всех размерностей (от 1 и выше).

Установлено (§5), что предположение 33. высказанное в [1,

с. 321], относительно максимальности числа вершин 3-ПТМ М(Х1,

I2, Í?) порядка n-jxrigxnj, не имеет места при п.,, п2 а 3.

Кроме тога, получен ряд результатов, касающихся строения 3-ПТМ порядка mxnx2. В частности, доказаны следующие оценки для

числа фасет 3-ПТМ М(А1, А2, А?) порядка m х n х 2.

Теорема 15. Пусть dlm М(А1, А2, А3) = d, d > 1. Тогда d+t *

s í^ímuV A2, A3)) s 6(d-l), причем верхняя и нижняя оценки

являются достижимыми.

Эта теорема обобщает результат П.Гибсона (Glbson Р. Facete of faces of transportation polytopes// Proo. Seventh. Oonf. on Combinatorio Graph Theory. Oomput. Louisiana. 1976. - P. 323 - 333), касающийся оценки числа (d-D-граней, содержащихся в d-грани КТМ.

В главе V "Дискретные задачи многокритериальной оптимизации" проведен анализ вычислительной сложности поиска паретовского 1 множества разнообразных МКЗ ДО и разрешимости етих задач в классе алгоритмов линейной свертки критериев (АЛСК). Оказалось, что рассматриваемые дискретные' МКЗ охватывают основную часть шкалы оценок вычислительной сложности: полиномиально разрешимые, полиномиально сводимые к классу NP и труднорешаемые.

Постановка г-критериальной задачи Zr = (X, Р) предполагает, что задано множество допустимых решений (МДР) X = {х}, на котором определена векторная целевая функция (ВЦФ) Р(х) . (Р 1 (х), Р 2 (х)..... Р г (х)),

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

Р „ (х) -* min ve е N „ , (6)

а х г

где Р„(х) « R va « N , vx « X.

В "

Допустимое решение х с X называется парето-оптимальным или

паретовским оптимумом (ПО), если эх* « X: Р(х*) s Р(х), Р(х*) #

* Р(х). Через X обозначаем паретовское множество (ПМ), состоящее

из всех ПО задачи Zp.

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

всех элементов ПМ X.

Подмножество X с X называется полным множеством альтернатив

(ПМА), если его мощность |Х| минимальна и выполняется равенство

Р(Х) в Р(Х), где Р(Х*) = (Р(х): х с X*), X* с X.

Задачу Zr - (X, Р) назовем r-критериальной целочисленной

задачей Сг-КЦЗ). если X с Z^. В таких задачах критерии (6),

как правило, имеют вид широко известных критериев

п

M1NSUM Р (х) = £ —*■ min

в Л=1 X

в.

J=1 j J X

(линейный или стоимостный критерий),

в

MINMAX F„(x) - max е., sign —► min 8 jeN J -> X

n

(критерий "узкого места"). Здесь с^ е УЗ е чз е Лг.

Говоря о г-КЦЗ г1*, будем подразумевать задачу нахождения и

«V А

представления в явном виде ПМ X или ГШ X. При этом под г-КЦЗ

понимается массовая задача. Наряду с массовой задачей будем использовать и понятие индивидуальная задача. Всякая индивидуальная г-КЦЗ характеризуется фиксированным порядком п и задается конкретной парой (X. Р), т. е. ВДР X и все параметры ВЦФ ?(х) фиксированы. Множество X в втом случае называется индивидуальным МДР, а функция Р(х) - индивидуальной ВЦф.

Пусть X - индивидуальное МДР некоторой массовой г-КЦЗ Zp, для которой задан лишь вид каждого из критериев Р„(х), в с N.

о Г

Эту задачу назовем полной на МДР X, если существует такая индивидуальная ВЦФ F(x), что для задачи (X, F) выполняется

л

равенство X = X. Массовая г-КЦЗ, г г 2, называется полной, если она является полной на любом своем индивидуальном МДР-

К настоящему времени свойство полноты установлено лишь для небольшого, числа МКЗ. Долгое время оставался открытым вопрос о полноте целочисленной ТЗ и задачи землепользования (см. обзор В. А. Еиеличева и В. А. Перепелицы).

Индивидуальное МДР X с назовем однородным, если

существует такое число k(X) е И, что выполняются равенства п

£ %3 = к(Х) vx = (хг х2.....Хд) с X.

Массовую г-КЦЗ будем называть однородной, если однородно всякое ее индивидуальное МДР.

Теорема 16. Всякая однородная г-КЦЗ, г г 2, является полной, если ВЦФ содержит хотя бы два критерия вида MINSUM.

Выделен класс задач (§2), для которых наличие в ВЦФ двух критериев MINSW является и необходимым условием полноты задачи.

Теорема 16 позволила выявить новые классы МКЗ ДО, которые являются полными. К их числу относятся широко известные многокритериальные целочисленные задачи стандартиз ации и землепользования, а также разнообразные задачи транспортного типа.

Среди методов нахождения ПО в МКЗ заметное место занимает АЛCK, в основе которого лежит следующий хорошо известный

результат: для любого вектора i « Ар = {X = d1t Ц,..., 1р):

х* *

Е = 1Л„ > О vs € N„} елемент х , минимизирующий на в=1 8 8 г

г

множестве X линейную свертку критериев Ф(х, X) = Г Х„Р„(х),

а=1 8 8

является ПО задачи Zr.

К сожалению, АЛСК не всегда гарантирует нахождение всего ПМ. Это означает, что существует такая индивидуальная задача (X, Р), в которой некоторый ПО никакой линейной сверткой критериев выловить не удается. Другими словами, для такой индивидуальной

задачи (X. Р) выполняется условие: эх с X: Ф(х, X) > min {Ф(х, X): х « X) vX « Лр.

В атом случае принято говорить, что массовая МКЗ неразрешима с помощью АЛСК.

В. А. Емеличев и В. А. Перепелица (ссылку см. на с. 4 > показали, что МКЗ на графах (об остовных деревьях и цепях, о совершенных паросочетаниях и коммивояжере) неразрешимы с помощью АЛСК, если ВЦФ состоит из критериев MINSUM или из критериев MINMAX. Ими же установлена неразрешимость и многокритериальной целочисленной ТЗ с критериями, вида MINSUM.

В §3 доказано, что МКЗ на графах (коммивояжера, об остовных деревьях и цепях, о совершенных паросочетаниях и р-медиане, о покрытии графа цепями, звездами и циклами), а также разнообразные целочисленные задачи транспортного типа с * ВЦФ, представляющей собой любую комбинацию критериев вида МПШ.Х и MINSUM, неразрешимы с помощью АЛСК.

Показано, что всякий лексикографический оптимум в МКЗ с конечным МДР X и критериями произвольной природы может быть получен с помощью АЛСК (§4).

Отметим, .что ато утверждение ранее было доказано В. А. Перепелицей и И. В. Сергиенко (Перепелица В. А., Сергиенко И. В. Исследование одного класса целочисленных многокритериальных задач// Журн. вычиел. математики и мат. физики. - 1988. - Т. 28, N 3. - С. 400 - 419) лишь для целочисленной задачи землепользования с линейными критериями.

В исследуется возможность применения АЛСК для нахождения ПМ в МКЗ на системах подмножеств с одним критерием произвольной природы и несколькими критериями "узкого места". Совместно с В.А. Емеличевым и O.A. Янушкевичем разргкзотан алгоритм с оценкой сложности, который позволяет любую такую задачу сводить к задаче с тем же ПМ, но разрешимую с помощью АЛСК. При этом в некоторых

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

В §6 предложена общоя схеме решения однокритериальной задачи на системах подмножеств с критерием MINMAX, на основе которой построены полиномиальные алгоритмы нахождения оптимального решения для задач об остовных деревьях и цепях, о совершенных паросочетаниях и назначениях, маршрутизации и целочисленной ТЗ. В частности, разработанный алгоритм решения прямоугольной задачи о назначениях порядка mxn, гп « п, с критерием MINMAX имеет

£ ур р

оценку сложности 0(пг log2 га + m log2 n + mn). В то время, как

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

задачи составляет Q(m^/'2log2 п) или 0(m^ + mn logg п) действий.

(Рубинштейн М. И. Алгоритм решения минимаксной задачи о назначениях со слабо заполненной прямоугольной матрицей// Автоматика и телемеханика. - 1986. - N 1. - С. 81 - 89).

С использованием разработанных алгоритмов для решения . однокритериальных задач построены алгоритмы полиномиальной трудоемкости для нахоадения ША в 2-критериальных задачах об остовных деревьях и цепях, о совершенных паросочетаниях и назначениях, маршрутизации и целочисленной ТЗ в случае, когда ВЦФ состоит лишь из критериев вида MINMAX.

В § 7 выявлены классы МКЗ о назначениях и целочисленной ТЗ с критериями вида MINSUM и MINMAX в произвольном сочетании, для которых удалось построить статистически аффективные алгоритмы поиска ПМА, т. е. приближенные алгоритмы, которые решают задачи в типичном случае ("почти всегда"). Для решения МКЗ на графах (коммивояжера, об остовных деревьях и цепях, о. совершенных паросочетаниях) с критериями вида MINSUM такие алгоритмы впервые были предложены В. А. Емеличевым и В. А. Перепелицей (ссылку см. на с. 4).

Разработана алгоритмическая схема нахождения одного ПО в МКЗ на системах подмножеств о упорядоченной совокупностью критериев, содержащей критерии вида MINSUM и MINMAX (§8). На основе етой схемы осуществлена конкретизация алгоритмов решения разнообразных задач ДО с такими критериями и найдены новые классы задач, допускающие полиномиальные алгоритмы.

- ¿1 -

В §9 исследуется устойчивость МКЗ на системах подмножеств о критериями вида MINSUM и MINMAX. Необходимость исследования устойчивости задачи оптимизации к возмущениям некоторых ее параметров вызвана такими факторами, квк неточность исходных данных, неадекватность математической модели реальным процессам, погрешность вычислений на ЭВМ, потребность в разработке алгоритмов для решения последовательности "близких" задач и др. Найдены необходимые и достаточные условия, при выполнении которых "малые" изменения коэффициентов функций, составляющих векторный критерий, не приводят к появлении новых ПО задачи. Рассмотрены и другие типы устойчивости многокритериальной дискретной задачи к возмущениям коэффициентов целевых функций: квазиустойчивость, при которой допускается возможность появления новых ПО при сохранении старых, и стабильность, которая понимается как неизменность всего множества ПО задачи. Выведены формулы для вычисления радиусов устойчивости и квазиустойчивости МКЗ с критериями вида MINSUM.

Ранее подобные исследования проводились как для однокритериальных задач (Э. Н. Гордеев, В. К. Леонтьев, Ю. Н. Сотсков и др.), так и для МКЗ целочисленного и частично целочисленного ЛП (Л. Н. Козерацкая, Т. Т. Лебедева, И. В. Сергиенко, Т. И. Сергиенко), а также задач на графах и системах подмножеств о линейными критериями и критериями "узкого места" (А. В. Бакурова, В. А. Емеличев, В. А. Перепелица).

Основные результаты

1. Получен критерий максимальности числа вершин КТМ и разработан аппарат для подсчета этого числа, с помощью которых доказана известная гипотеза Болкера (ссылку см. на с. 3) о степени полинома в представлении максимального числа вершин КТМ.

2. Дана классификация КТМ по числу фасет. Найдены критерии принадлежности невырожденного КТМ с заданным числом фасет к кляесу многогранников с минимальным и максимальным числом к-гра-ней всех размерностей, и выяснено асимптотическое поведение указанных классов ггри возрастании порядка многогранника. В частности, обобщена теорема Крачковского (см. [1, с. 254]), которая опровергает гипотезу Болкера об асимптотике КТМ с максимальным числом вершин. Выведена формула для минимального числа k-граней и разработан аппарат для подсчета максимального

числа к-граней КТМ.

3. Указаны достижимые нижние оценки диаметра и радиуса, а также оценки сверху для максимального диаметра и радиуса в классе КТМ с любым заданным числом фасет. Установлена панцикличнооть графа невырожденного КТМ с заданным числом фасет и минимальным числом вершин. Показано, что обхват всякого невырожденного КТМ порядка mxn, Э s т s п, равен трем.

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

5. Доказана теорема о представлении многогранника ТЗ с запретами и ограниченными пропускными способностями в виде произведения многогранников меньшего порядка. Выведены формулы для числа базисов ТЗ с запретами, обобщающие известные формулы Симмонарда-Хедли и Кононенко-Трухановского (ссылки см. на с. 4). Найдена достаточно точная оценка сверху для числа базисов ТЗ о произвольной конфигурацией множества запретов и получен критерий принадлежности ТЗ порядка mxn с к запретами (1 * к s min {m, n>) к классу задач с максимальным числом базисов и выведена формула для подсчета етого числа.

6. Найден критерий принадлежности р-ПТМ к классу многогранников с максимальным числом вершин. Показано, что всякий такой многогранник имеет максимальное число k-граней всех размерностей. Установлено, что предположение 33, высказанное в [1, с. 321] относительно максимальности числа вершин так называемого центрального 3-ПТМ не имеет места.

7. Получены критерии минимальности и максимальности числа ЦТ р-АТМ. Выведена рекуррентная формула для минимального числа ЦТ и указана оценка снизу для максимального числа ЦВ р-АТМ.

в. Указаны достижимые нижние оценки диаметра и радиуса, а также оценки снизу для максимального диаметра и радиуса в классе р-АТМ с любым заданным числом фасет. Установлена гамйльтоновость графа невырожденного р-АТМ с минимальным числом вершин (тем самым доказана гипотеза 32 [1, с. 321]).

9. Выяснено асимптотическое поведение некоторых классов р-АТМ при возрастании порядка многогранника. В частности, доказано, что с ростом порядка многогранника отношение числа

многогранников о'максимальным количеством фасет к общему числу многогранников стремится к единице. Тем самым получено существенное обобщение теоремы £Х«еличева-Крачковского (1, с.253), касающейся асимптотического поведения КТМ.

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

11. Выявлен широкий класс МКЗ ДО, которые неразрешимы о помощью АЛСК. В етот класс, в частности, попадают хорошо известные задачи оптимизации на графах (коммивояжера, об остовных деревьях и цепях, о совершенных паросочетаниях и р-медиане, о покрытии графа звездами, цепями, циклами), а также разнообразные целочисленные задачи транспортного типа с ВЦФ, представляющей собой любую комбинацию линейных критериев и критериев "узкого места". Доказано, что всякий лексикографический оптимум в МКЗ на конечном множестве допустимых решений о критериями произвольной природа может быть получен с помощью АЛСК. Найдено условие разрешимости с помощью АЛСК МКЗ на системах подмножеств с любым количеством критериев "узкого места" и одним критерием произвольной природы и рязрнботан алгоритм, позволяющий сводить неразрешимую н этом смысле МКЗ к эквивалентной задаче (о тем же ПМ), для которой укапанное условие выполняется. В частности, если все критерии "узкого места", то оценка сложности сведения оказывается полиномиальной относительно размерности задачи.

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

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

~ и -

тз.

14. Выявлены случаи, когда для решения МКЗ о назначениях и целочисленной ТЗ существуют статистически эффективные алгоритмы, т. е. приближенные алгоритмы, которые решают задачи в типичном случае ("почти всегда").

15. Найдены критерии устойчивости, квазиустойчивости и стабильности МКЗ на системах подмножеств с линейными критериями. Выведены формулы для вычисления радиусов устойчивости и квазиустойчивости задачи.

Основные результаты диссертации опубликованы в следующих работах:

1. Вделичев В. А., Ковалев М. М., Кравцов М. К. Многогранники,- графи, оптимизация. - М.: Наука. - 1981. - 342 е.; англ. перевод.: Yemelichev V. A., Kovalev М. М., Kravteov М.К. Polytopea, graphs and optimisation. - Cambridge University Press. - 1984. - 423 p.; нем. перевод.: Bnelioev V. A., Kovalev M. M., Kravoov M. K. Polyeder, graphen, optlmierung. -Berlin.: Wissensohaften. - 1985. - 356 s.

2. Jemeliteohew W. A., Krawzow M. K. Kombinatorik der Transport polyeder// Porschungeergebnisse der FSU. - Yena. -1980. - N 27. - 16 e.

3. Емеличев В. А., Кравцов M. К. Транспортные многогранники// В кн.: Алгебраические системы. - Иваново: Иван, гос. у-т. - 1981. - С. 134 - 152.

4. Bnelioev V. A., Kravzov М. К. Combinatorioal theory of transportation polyhedrons// Math. Oper. Statist. -Ser. Optimization. - 1983.'- V. 14, N 1. - P. 77 - 89.

5. Емеличев В. А., Кравцов M. К. Комбинаторные задачи на транспортных многогранниках// Экономика и мат. методы. - 198Э. -Т. 19. Вып. 2. - С. 301 - 320.

6. Емеличев В. А., Кравцов М. К. Полиэдральные аспекты многоиндексных аксиальных транспортных задач// Дискрет, мат. -1991. - Т. 3. Вып. 2. - С. 3 - 24.

7» Виеличев В. А., Кравцов М. К. О некоторых свойствах транспортных многогранников с максимальным числом вершин// Докл. АН СССР. ■- 1976. - Т. 228. N 5. - С. 1025 - 1028.

8. Влеличев В. А., Кравцов М. К., Авербух Н. Д. О мккеих'йльном числе вершин транспортного многогранника// Докл. АН

- 25 -

БССР. - 1976. - Т. 20, N 6. - С. 509 - 512.

9. Кравцов М. К., Емеличев В. А. О транспортных многогранниках с заданным числом граней// Изв. АН БССР. Сер. физ.-мат. наук. - 1976. - N 5. - С. 97 - 98.

10. Кравцов М. К. Перечислительные задачи на вырожденных транспортных многогранниках// Изв. АН БССР. Сер. физ.-мат. наук.

- 1976. - N 6. - С. 122 - 123: К оценке сверху числа вершин вырожденного транспортного многогранника// Там же. - С. 124.

11. Jemelitsohew И. A., Krawzow М. К. Transportpolyeder// 21 Intern. WIsb. Roll. Teohnieohe Hochschule. - Ilmenau. - 1976.

- S. 97 - 99.

12. Емеличев В. А., Кравцов М. К., Крачковский А. П. Доказательство гипотезы Болкера// Докл. АН БССР. - 1977- - Т. 21, N 9. - С. 788 - 790.

13. Емеличева В. С., Кравцов М. К. О гранях вырожденного транспортного многогранника// Изв. АН БССР. Сер. физ.-мат. наук.

- 1977. - N 5. - С. 23 - 26.

14. Виеличев В. А., Кравцов М. К., Крачковский А. П. Минимальное число вершин невырожденного транспортного многогранника с фиксированным числом граней// Докл. АН БССР. 1978. - Т. 22. N 1. - С. 15 - 17.

15. Емеличев В. А., Кравцов М. К. О транспортных многогранниках о максимальным числом вершин// В кн.: Вопросы кибернетики. - М.: АН СССР. - 1978. Вып. 26. - С. 120 - 142.

16. Емеличев В. А., Кравцов М. К., Крачковский А. П. О некоторых классах транспортных многогранников// Докл. АН СССР. -1978. - Т. 241. N 3. - С. 532 - 535.

17. Кравцов М. К. О (d - 2)-мерных гранях транспортного многогранника размерности d// Изв. АН БССР. Сер.-физ.-мат. наук.

- 1979. - N 3. - С. 5 - 8.

18. Кравцов М. К., Корзников А. Д. Перечислительные задачи на усеченных транспортных многогранниках// Изв. АН БССР. Сер. физ.-мат. наук. - 1979. - N 4. - С. 12 - 19.

19. Кравцов М. К. О максимальном числе целочисленных вершин аксиального транспортного многогранника// В кн.: Вопросы математического обеспечения в автоматизированных системах. -Минск: НИИЭМП при Госплане БССР. - 1979. - С. 39 - 42.

20. Кравцов М. К. Об одном классе гамильтоновых графов// Изв. АН БССР. Сер. физ.-мат. наук. - 1980. - N 6. - С. 118 - 119

(статья деп. в ВИНИТИ, per. N 3118 - 80. - 15 е.).

21. Кравцов М. К. Транспортные многогранники с заданным числом граней и минимальным числом вершин// Тез. докл. междун. конф. "Математические методы в исследовании операций". - София: Болгарская Академия Наук. - 1980. - С. 60-61.

22. Кравцов М. К. К оценке сверху диаметра транспортного

многогранника// Тез. докл. V всесоюз. конф. по проблемам *

теоретической кибернетики. - Новосибирск. - 1980. -С. 145 - 146.

23. Кравцов М. К. К комбинаторной теории транспортных многогранников// Тез. докл. V респуб. конф. математиков Белоруссии. - Гродно: Града, гос. ун-т. - 1980. Ч 1. - С. 61 -62.

24. Кравцов М. К., Е^еличев В. А., Шилкин В. Г. Транспортные многогранники специальной структуры// В кн.: Вопросы кибернетики. - М.: АН СССР. 1980. Вып. 64. - С. 29 -47.

25. Емеличев В. А., Кравцов М. К. К оценке сложности алгоритмов решения транспортной задачи// Кибернетика. - 1.981. -N 6. - С. 124 - 126.

26. Кравцов M. К., Вделичев В. А. Циклы на транспортных многогранниках// Докл. АН БССР. - 1981. - Т. 25, N 12. - С. 1067 - 1069.

27. Кравцов М. К. Диаметр и радиус транспортного многогранника// Докл. АН СССР. - 1983. - Т. 270. N 2. - С. 278 - 281.

28. Кравцов М. К. Радиус транспортного многогранника// Изв. АН БССР. Сер. физ.-мат. наук. - 1983- - N 6. - С. 33 - 39.

29- Кравцов М. К.' К оценке сверху радиуса транспортного многогранника// Вестн. Б1У. Сер. 1. - 1984. - N 2. - С. 49 - 53.

30. Кравцов М. К., Емеличев В. А. О транспортных многогранниках с максимальным числом граней всех размерностей//• Докл. АН БССР. - 1984. - Т. 28, N 8. - С. 698 - 701.

31. Кравцов М. К., Емеличев В. А. О гранях, диаметре и радиусе транспортного многогранника// Докл. АН БССР. - 1984. -Т. 28, N 11. - С. 965 - 967.

32. Кравцов М. К. К оценке сложности алгоритмов решения задач транспортного типа// X Intern. Kongreß über Anwendungen der Mathematik in den IngenieurwiBsensohaften. Berichte 2. -Weimar. - 1984. - 77 - 80.

33. Еиеличвш В. А., Кравцов М. К., Крачковский А. П. Транспортные многогранники с максимальным числом к-граней// Докл. АН СССР. - 1985- - Т. 282, N 4. - С. 784 - 788.

34. önelioev W. А., Kravzov Ii. К., Kratsohkovaki А. Р. Kombinatorische und Extrems! prob lerne auf Trensportpolyedern// Diskrete Optimierung. - Jena: Friedrich - Schiller Universität. - 1985. - P. 31 - 35.

35. Кравцов M. К. О структуре множества допустимых решений транспортной задачи с ограниченными пропускными способностями// Экономика и мат. методы. - 1986. - Т. 22. Выгг. 3- - С. 524 - 531.

36. Емвличев В. А., Кравцов М. К., Крачковский А. П. О разрешимости транспортных задач с запретами// Кибернетика. -1987. - N 1. - С. 42 - 46.

37. Кравцов М. К., Галактионова Е. С. Число целых точек в целочисленных транспортных многогранниках// Изв. АН БССР. Сер. физ.-мат. наук. - 1987. - N 4. - С. 39 - 45.

38. Кравцов М. К., йлеличев В. А. Некоторые вопросы полиедральной комбинаторики в обобщенных транспортных задачах// Экономика и мет. методы. - 19аЭ. - Т. 24. Вып. 2. - С. 319 -3?6.

39. Кравцов М. К. Доказательство гипотезы Дюбуа о максимальном числе вершин симметрического транспортного многогранника// Докл. АН БССР. - 1989. - Т. 33, N 1. -С. 9 - 12.

40. Кравцов М. К., Шерман А. X. О решении комбинаторных задач оптимизации с минимаксными критериями// Кибернетика. -

1989. - N 3. - С. 71 - 77.

41. Кравцов М. К. Полиэдральные аспекты транспортных задач// Докл.'АН СССР. - 1989. - Т. 309, N 2. - С. 271 - 275.

42. Кравцов М. К. Полиэдральные аспекты многоиндексных транспортных задач о аксиальными суммами// Докл. АН СССР. -

1990. - Т. 315, N 6. - С. 1298 - 1301.

43. Кравцов М. К. Транспортные многогранники с минимальным числом k-граней// Докл. АН БССР. - 1990. - Т. 34, N 11. - С. 965 - 969.

44. Кравцов М. К. Вопросы полиэдральной комбинаторики в транспортных.задачах с запретами// Кибернетика. - 1990. - N 6. -С. 63 -.71, 84.

45- Кравцов М. К. Диаметр и радиус многоиядексного аксиального транспортного многогранника// Изв. АН БССР. Сер.

физ.-мат. наук. - 1991- - N 6. - С. 103 - Юб.

46. Кравцов М. К. Полиэдральная комбинаторика в многоиндексных аксивльных транспортных задачах// Тез. докл. конф. "Математическое программирование и приложения". Свердловск: УрО АН СССР. - 1991. - С. 93 - 94.

47. Емеличев В. А., Кравцов М. К., Крачковский А. П. Многоиндексные пленарные транспортные многогранники с максимальным числом вершин// Дискрет, мат. - 1992. - Т. 4. Вып. 1. - С. 3 - 18.

48. Кравцов М. К. О транспортных многогранниках о минимальным числом k-граней// Дискрет, мат. - 1992. - Т. 4. Вып. 3. - С. 108 - 117.

49- Кравцов М. К. О некоторых алгоритмических проблемах многокритериальной оптимизации// Тез. докл. VI конф. математиков Беларуси. - Гродно: Гродн. гос. ун-т. - 1992. - Ч. 4. - С. 80.

50. Кравцов М. К. Усеченные транспортные многогранники с максимальным числом вершин// Изв. АН Беларуси. Сер. физ.-мат. наук. - 1993. - N 3. - С. 30 - 34.

51. Bneliohev V. A., GIrlioh Е., Kravtsov M. К. On some algorithmic problems in veotor discrete optimization// Workshop on Dlsorete Optimization. Abstracts. - Minsk - Magdeburg. -

1993. - P. 10.

52. Кравцов M. К. К вычислительной сложности многокритериальных транспортных задач// Изв. АН Беларуси. Сер. физ.-мат. наук. - 1994. - N 1. - С. 46 - 51.

53. Емеличев В. А., Кравцов М. К. О неразрешимости векторных задач дискретной оптимизации на системах подмножеств в классе алгоритмов линейной свертки критериев// Докл. РАН. -

1994. - Т. 334. N 1. - С. 9 - 11.

54. Емеличев В. А., Кравцов М. К. О полноте многокритериальных задач на системах подмножеств// Докл. АН-Беларуси. - 1994. - Т. 38, N 3. - С. 25 - 28.

55. ЗДеличев В. А., Кравцов М. К. О задачах векторной дискретной оптимизации на системах подмножеств, неразрешимых с помощью алгоритмов линейной свертки// Журн. вычисл. математики и мат. физики. - 1994. - Т. 34, N 7. - С. 1082 - 1094.

56. Emeliohev V. A., Kravtsov M. К. On stability in trajectory problems of veotor optimization// Workshop on Wöctvte 0fitimi2arior!. Abstraots. - Weimar. - 1994. - P. 5.

57. Кравцов iM. К. О неразрешимости с помощью алгоритма линейной свертки многокритериальных задач рягжо:<ки// Т^э. докл. науч.-техн. конф. "М'чл"Лиронянис овльскохозяйствешшх процессов и машин". - Минскг РАТУ.. - 1994. - 0. 86 - 87; Многокритериальная модель размещения товаров ня складе базы снабжения// Там же. - С. 85.

58. РХарличнв В. А., Кравцов М. К. Полнота яадчч векторной дискретной оптимизации// Кибернетика и системный анализ. - 1994.

- N 5. - 0. 75 - 83.

59. Емеличев В. А., Краьцоь М. Н.. ЯнушкоЕИЧ 0. А. Нахождини« лексикографического множества векторной задачи дискретной оптимизации// Тез. докл. междун. конф. "Проблемы математики и информатики". Ч. 2. - Гомель: Гомельский гос. ун-т.

- 1994. - С. 42.

60. Oirltoh Е., Emelioev V. A., Kravtzov М. К. Lexikographieehe OptJma In diskreten VektoroptlmierungBproble-men// Preprint/ Otto-VorHJuerloke-Unlvereltat Vtigdeburx- - '99-!.

- N ?7. - e.

T7

- 30 -РЭЗЮМЭ

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

Ключавыя словы: шматгранн!к, вяршыня, к-грань, дыяметр, радиус, многакрытврыяльная аптым1зация, выл1чальная складанасць, алгарытм, парвтауск1 оптымум, уетойл1васць.

Праведзены якасныя даследаванн! камб1наториых характерыстик шматгранн1кау, широка распаусюджаних у прыкладаннях задач транспартнага тылу. У прнватнасц1, даказана г1потеза Волкера аб ступен! пал!нома у прывядзенн1 макс!мальнага л1ку вяршынь клас1чнага транбпартнага шматгранн1ка (КТШ), атрыманы крытэри! прыналежнасц! невыраджанага КТШ з зададзеным л!кам фасет (гэта значыць граней макс!мальнай размернасц!) да клаеу шматгранн1кау з м1н!мальным 1 макс1мальным л1кам к-граняу ус1х размернасцей 1 высветляны 8с1мптвтычныя паводз!ны указаных класау пры узрастанн1 парадку шматгранн!ка, выведзена формула для м1н!мальнага л1ку к-граняу 1 распрадаваны апарат для падл1ку макс!мальнага л1ку к-граняу КТШ, указаны дасягальныя н1жн!я аценк! дыяметра 1 радиуса, а таксама ацвнк1 зверху для макс!мальнага дыяметра 1 радыуса у класе КТШ э зададзеным л1кам фасет, даказана г1потаза Дэюбуа аб макс1мальным л!ку вяршынь с1метрычнага транспартнага шматгранн!ка, выведзены формулы для л1ку баз!сау транспартнай задачи з заоаронам1, даказана теарема аб прывядзенн1 шматгранн1ка транспартнай задачы з абмежаваным1 прапускным1 здольнасцям1 у выглядзе здабытку шматгранн!кау меншага парадку, знойдзены крытэрый прыналежнасц! многа1ндекснага планарнага транспартнага шматгракн1ка да класу шматгранн1кау з макс1мальным л!кам вяршынь, указаны крытвры! м1н1мальнасц! 1 макс1мальнасц1 л1ку цэлых кропак миога1ндакснага акс1яльнага транспартнага шматгранн1ка, атрымана абагульненне тваремы Ямел1чава-Крачкоускага, якая датычыцца яс1мптйтычных ппводз1н КТШ, на выпадак многа1ндвксных акс!яльных сранспар'/'ннх шмат1'ранн1кау

Даствткова поуна вывучана таксама новая праблематыка, якая Чятычыццн склчдчнясц! многакрытерыяльных задач дыскрэтнай «»ишчГччцы!.

- 31 -РЮШЕ

диссертационной работы Кравцова Михаила Константиновича "Полирлралышч Аспекты транспортных задач и сложность многокритериальных задач дискретной оптимизации"

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

Проведены качественные исследования комбинаторных характеристик многогранников, широко распространенных в приложениях задач транспортного типа. В частности, доказана гипотеза Болкера о степе™ полинома в представлении максимального числа вершин классического транспортного многогранника (КТМ), получены критерии принадлежности невырожденного КТМ с заданным числом фасет (т. е. граней максимальной размерности) к классу многогранников с минимальным и максимальным числом к-граней всех размерностей и выяснено асимптотическое поведение указанных классов при возрастании порядка многогранника, выведена формула для минимального числа к-граней и разработан аппарат для подсчета максимального числа к-граней КТМ, указаны достижимые тшше оценки диаметра и радиуса, а также оценки сверху для максимального диаметра и радиуса в классе КТМ с заданным числом фасет, доказана гипотез? Дюбуа о максимальном числе вершин симметрического транспортного многогранника, выведены формулы для числа базисов транспортной задачи о запретами, доказана теорема о представлении многогранника транспортной задачи а ограниченными пропускными способностями'в виде произведения многогранников меньшего порядка, найден критерий принадлежности многоиндексного планерного транспортного многогранника к классу многогранников с максимальным числом вершин, указаны критерии минимальности и максимальности числа целых точек многоиндексного аксиального транспортного многогранника, получено обобщение теоремы ®<елкчева-Крачксвского, касающейся асимптотического поведения КТМ, на случай многоиндексннх аксиальных транспортам многогранников.

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

- 32 -RESUME

of the thesis "Polyhedral Aepeots of Transportation Problems

and Complexity of Veotor Discrete Optimization Probleme" by Kravtsov Mikhail Konstantinovioh

Key Words: polytop, vertex, k-faoe, diameter, radius, veotor optimization, computational complexity, algorithm, Pareto optimum, stability.

Qualitative investigations of oombinatorio oharaoterlatioa for poly tope widely used in apjilioat Jons of transportation-type problems are oarried out. In particular, a Bolker hypothesis on polynom's degree in a fomila for a maximum number of vertioes for classical transport polytop (OTP) is prooved, oriteria for a nondegenerate OTP with a given number of faoeta (faoes of maximal dimension) to belong to a olaes of polytope with a minimal and maximal number of k-faoes of all dimensions are obtained and the asymptotio behaviour of named olasses is cleared out when polytop*b order inoreses, a formula for a minimal number of k-faoes is deduoed and an apparatus to calculate a maximal number of k-faoes of OTP is developed, attained lower estimates for a diameter and a radius are stated, bo are the upper estimates for a maximal diameter and radius in a olass of OTPs with a given number of faoets, a Dubois hypothesis on a maximal number of vertioes or a Byrnmetrio transport polytop is proved, formulae for a number of bases for a transport problem with prohibitions are deduoed, a representation theorem for a transport problem polytop with №h trio ted communication oapaoitiee as a produot of lower order polytope is proved, a oriterion for a multi-index planer transport polytop to belong to a olaes of polytops with a maximal number of vertioes la found, oriteria for minimality and maximality of a number or interger points of multi-index axial transport polytop are stated, the Emeliohev-Kraohkovski theorem, oonoerning «eymptotlo behaviour or OTPs is generalised to the case of wiHi-ln.lex axial transport polytope.

New problems oonoerning complexity of veotor discrete opUmlWitIon problems are thoroughly investigated.