Полиномиально разрешимые и NP — трудные двухуровневые задачи стандартизации

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

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

Теоретическую оценку сложности различных классов задач дает теория КР-полных проблем, основанная на работах Кука [28] и Карпа [25]. В этой теории рассматривается класс КР задач распознавания свойств, разрешимых за полиномиальное время недетерминированной машиной Тьюринга, и класс Р задач распознавания свойств, разрешимых за полиномиальное время детерминированной машиной Тьюринга.

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

Оптимизационную задачу называют NP-трудной, если к ней сводится [22] некоторая NP-полная задача. Основной вывод из этой сводимости заключается в том, что существование полиномиального алгоритма для хотя бы одной NP-трудной задачи влечет существование такого алгоритма для всех задач из NP, и, следовательно, P=NP.

Одной из задач стандартизации и размещения является хорошо известная задача, которую иногда называют «простейшей» задачей размещения (в зарубежной литературе — simple plant location problem). Классическая постановка этой задачи такова: имеется множество J ~ {1 ,., т} потребителей некоторого однородного продукта, который могут производить предприятия из множества I = {1,., п}. Заданы транспортные расходы Cij по перевозке продукта от предприятия г 6 I потребителю j Е J, а также затраты fi на ввод в действие предприятия г G I. Требуется выбрать такое непустое подмножество X С I предприятий, чтобы сумма транспортных расходов и затрат на ввод предприятий г? X была минимальна. Существует несколько эквивалентных математических постановок этой задачи. Например, в работе Гришухина [21] приводится шесть таких постановок в виде задачи целочисленного программирования, задачи определения оптимального параметрического ряда, задачи нахождения оптимальной траектории, задачи минимизации функции множеств, задачи минимизации псевдобулевой функции, задачи о покрытии. Наиболее известна постановка «простейшей» задачи размещения (ПЗР) как задачи целочисленного программирования: min {Е fiVi + Е Е cijXij}.

У1'Хгз iei ieijeJ.

Е xij — 15 J? iei.

Xij < У г, i? I, j e J,.

Vi, x^? {0,1}.

Изучению задач размещения и методов их решения посвящена обширная литература [5,52,58,63]. В общей постановке ПЗР является NP-трудной, поскольку к ней сводится NP-полная задача о покрытии. Согласно работе Крарупа и Прузана [63], сводимость задачи о минимальном покрытии к простейшей задаче размещения отмечалась одним из авторов в 1967 году [62]. Агеев [1] доказал эквивалентность задачи о минимальном покрытии и задачи минимизации полинома от булевых переменных с неотрицательными коэффициентами при нелинейных членах. Для последней задачи в [14], была показана ее эквивалентность ПЗР.

Для изучения задач, оказавшихся NP-трудными, можно указать следующие подходы. Первый подход заключается в учете специфики конкретных задач, поиске и описанию эффективно разрешимых случаев [5,21]. Для ПЗР он осуществляется поиском дополнительных условий на матрицу (%).

В работе Береснева, Гимади, Дементьева [14] было показано, что эффективно решается ПЗР с квазивыпуклой матрицей. Позже в работе Гимади [18] была показана полиномиальная разрешимость ПЗР для более общего случая обобщенно-квазивыпуклых матриц. Трудоемкость предложенного алгоритма оценивается как 0(п3т+гг4). В работе [7] указывается алгоритм решения ПЗР с обобщенно-квазивыпуклыми матрицами трудоемкости 0(пт + гг4). Другой класс матриц, допускающий эффективное решение — связные матрицы [14,20]. В работе Береснева [12] показано, что ПЗР эффективно решается в случае, когда матрица является 2-связной. Другое обобщение было предложено в работе Гимади [17], в которой рассматриваются матрицы, связные относительно ациклической сети. Позднее, Агеевым [3] было показано, что если матрица транспортных затрат связна относительно внешне-планарного графа, то ПЗР полиномиально разрешима.

Другие эффективно разрешимые частные случаи были получены для ПЗР с матрицей транспортных затрат, порожденной расстояниями на графах. Впервые Трубин [33] построил эффективный алгоритм для ПЗР на деревьях с оценкой трудоемкости 0(гг3). В работе Гимади [17] рассмотрен более широкий класс задач и предложен алгоритм, который решает задачу Трубина с оценкой трудоемкости 0(п2). В работе Агеева [4] предлагается полиномиальный алгоритм решения задачи размещения на последовательно-параллельной сети. Результаты, полученные за последние годы и касающиеся эффективно разрешимых случаев ПЗР на некоторых классах графов, обсуждаются в работе Агеева [5].

Для построения эффективного алгоритма частного случая ПЗР в работе Трубина [33] использовалось g-cвoйcтвo вполне уравновешенных матриц ограничений в задаче, двойственной к линейной релаксации задачи о покрытии. В дальнейшем в работе [60] предложен эффективный алгоритм решения задачи о покрытии тт{сж + йу | Ах + у > 1, х? {0,1}п, у? {0,1}т} в случае, когда матрица, А является вполне уравновешенной. В работе Береснева [13] предлагается эффективный алгоритм решения задачи минимизации полинома от булевых переменных при условии, когда его характеристическая матрица является вполне уравновешенной.

Другое направление исследований состоит в создании приближенных малотрудоемких алгоритмов решения ПЗР в общей постановке и ее частных случаев [14,52,58,59,63]. Особый интерес представляют алгоритмы с гарантированными оценками точности [2,5,51] и асимптотически точные алгоритмы [19].

Для поиска точного решения NP-тpyдныx задач используются комбинаторные методы [9,29,31,34]. В первую очередь — метод ветвей и границ [26]. Основная идея этих методов состоит в замене полного перебора решений сокращенным. Алгоритмы на основе метода ветвей и границ для решения задач размещения разрабатывались в работах [14,56,57]. Главную роль в сокращении перебора играет нижняя оценка оптимума целевой функции на подмножествах решений. В работе [14] предлагается нижняя оценка, для построения которой используются так называемые тупиковые матрицы. Показывается их преимущество перед оценочными матрицами, используемыми в работе [56].

В последнее время в литературе все чаще появляются разного рода обобщения простейшей задачи размещения. Некоторые из них можно найти в книге [52]. В настоящей работе рассматривается одно из таких обобщений, возникающее при моделировании процессов принятия решений в иерархических системах, когда каждый уровень иерархии принимает свое решение, зная решения вышестоящих уровней, но руководствуясь своими целями и используя свои возможности. Задача состоит в поиске решения верхнего уровня, которое приводит всю иерархическую систему к достижению определенной цели. Постановки такого рода получили название задач многоуровневого программирования. Задачи с двумя уровнями иерархии называют задачами двухуровневого программирования. Впервые такие задачи в игровой постановке рассматривались в [66] в 1952 году. Среди отечественных работ можно указать книгу Гермейера [16], в которой иерархические системы рассматривались, как один из примеров игр с непротивоположными интересами. В последние 10−15 лет интерес к задачам многоуровневого программирования значительно возрос. Обзор результатов, полученных для задач многоуровневого программирования, можно найти, например, в работах [37, 67], где приводятся постановки задач двухуровневого программирования, дается классификация и обзор алгоритмов решения, указываются области применения иерархических моделей принятия решений и соответствующие работы.

Первыми работами в которых появились постановки задач двухуровневого программирования и термины «двухуровневое» и «многоуровневое» программирование были работы [46, 49].

В ряде работ [37−39,41,53,54,67] под задачей двухуровневого программирования понимается задача вида: гшп Р (х, у) при условии: д (х, у) < О, где у — оптимальное решение задачи: тш /(ж, у) при условии: И (х, у) < 0.

Для каждого значения переменной х верхнего уровня, ограничения нижнего уровня определяют допустимое множество задачи нижнего уровня: Ь (х) — {у | Н (х, у) < 0}. Если обозначить через М (х) = агдтт{/(х, у) | у Е £>(х)} множество оптимальных решений задачи нижнего уровня, то задачу верхнего уровня можно записать в виде: тп1 Р (х, у) при условии: д (х, у) <0, у е М (х).

Её допустимое множество {(х, у) д (х, у) < 0, у Е М (х)}, как правило, не выпуклое, может быть даже не связным.

В других работах [23,24,27,30,42,64,65] задачей двухуровневого программирования называется постановка вида: пип Р (х, у) при условии: д (х, у) < 0, где у — оптимальное решение задачи: пип /(ж, у) 10 при условии: h (x, y) < 0.

Отличие от предыдущей постановки состоит в том, что если множество М (х) содержит не менее двух элементов, то функционал F{x, y) становится неоднозначным и следует либо определить искомое решение задачи верхнего уровня специальным образом [27,42], либо можно понимать оптимальное решение в обычном смысле, заменяя функционал F (x, y) на один из следующих:

Fi (x) = min Fix, у), F^ix) = max Fix, у). n — уем (х) K y > Уем (х) v.

Изучению вопросов сложности рассматриваемых задач посвящены работы [45,48,55]. Установлено, что задачи многоуровневого программирования оказываются труднорешаемыми даже в линейном случае [45]. В работах [27,43,55,61] содержатся доказательства NP-трудности некоторых специальных линейных задач двухуровневого программирования. В работе [27] рассматривается полиномиально разрешимый случай линейной задачи двухуровневого программирования, когда задача нижнего уровня — непрерывная задача о ранце (в работе [30] этот результат обобщается).

Линейные иерархические модели принятия решений имеют достаточно большую область применений. К первым работам, касающимся использования таких моделей, можно отнести работы [46,50]. Обзору полученных результатов для линейных задач двухуровневого программирования посвящена работа [42]. В ней задачей двухуровневого линейного программирования (ДЛП) называется задача вида: max (сх + dy) где у — оптимальное решение задачи: тах (¡-х + ку) при условии Ах + Ву <6, ж, у > 0.

В работе проводится анализ структуры допустимого множества решений, обсуждается связь рассматриваемой задачи с другими оптимизационными моделями, такими как задачи линейного программирования, частично целочисленного программирования (см. также работу [39]), линейными тах-тш задачами, теорией игр, двухкритериальными линейными задачами (см. также работы [40,69]), задачами билинейного программирования.

Для решения линейной задачи двухуровневого программирования предлагается ряд алгоритмов, использующих метод ветвей и границ [41], симплекс-метод [53,65], метод штрафных функций [38]. В работе [44] предлагается алгоритм, основанный на замене задачи нижнего уровня условиями оптимальности Куна-Таккера.

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

В работе [64] рассматривается задача: найти тах (сх + /у) при условиях Ах < а, х1 > 0, х2 = 0,1,2,., где у — оптимальное решение задачи: тах йу у=(уу2) при условиях Еу < е, Dx + Gy < b, у1 > 0, у2 = 0,1,2,., для решения которой предлагается алгоритм, основанный на методе ветвей и границ. Существенной особенностью задачи является то, что оптимальное значение целевой функции в линейной релаксации этой задачи не всегда дает оценку сверху на ее оптимум. Поэтому для получения верхней оценки используется специальная задача линейного программирования. Оптимальность найденного решения гарантируется только для некоторых частных случаев этой задачи.

В работе [68] рассматривается задача: найти min (сх + fy) при условиях х Е X, Ах + Ву > а, где у — оптимальное решение задачи: min dy у у при условиях у Е У, Dx + Еу > Ь.

В зависимости от структуры множеств X и Y рассматриваются: линейная задача (JI3), если X = Rn и Y = Rmдискретная линейная задача (ДЛЗ), если X, Y конечные дискретные множествадискретно-непрерывная (ДНЛЗ), если X конечное дискретное множество, У = Rm] непрерывно-дискретная (НДЛЗ), если X = Rn, Y конечное дискретное множество.

В работе изучаются структура допустимых множеств и обсуждается вопрос существования оптимальных решений в рассматриваемых задачах. Доказывается сводимость задачи ДНЛЗ с X = {0,1}п к линейной задаче двухуровневого программирования. Задача ДЛЗ с.

X = {0,1}п и Y = {0,1}т сводится к линейной задаче трехуровневого программирования. Для задачи НДЛЗ с У = {0,1}т показано, что ее оптимальное решение может быть получено как предел последовательности оптимальных решений некоторого семейства линейных задач двухуровневого программирования.

В работе [54] рассматривается задача вида: min (сх + dy) при условии Ах > а, где у — оптимальное решение задачи: max ху при условии By >6, у > 0, у — целый, для решения которой предлагается алгоритм, состоящий из решения серии непрерывных задач двухуровневого программирования и аппроксимации допустимого множества дискретной задачи нижнего уровня с помощью отсечений Гомори.

В настоящей работе рассматриваются дискретные линейные задачи двухуровневого программирования вида: max {? ? 9ijx*j ~ Е c°ixi } IXi> iei je J iei.

Xi e {0,1}, % G ж^О, где (x*j) — оптимальное решение задачи: min? Е dijXij (®u) ieijeJ Xij = 1, Xij < Xi, Xij G {0,1}, % G /, j G J. ia.

Эта задача является обобщением простейшей задачи размещения. Впервые такие задачи рассматривались в работах [23,24,35]. На верхнем уровне рассматривается задача выбора производителем подмножества видов изделий из заданного множества. При этом он максимизирует свой доход, который зависит от решения потребителей и определяется матрицей доходов = (д^) и вектором начальных затрат (с?). На нижнем уровне рассматривается задача потребителей, выбирающих те изделия из предлагаемых производителем, которые минимизируют их закупочно-эксплуатационные затраты (определяются матрицей затрат потребителей И = (.