Полиномиально разрешимые и NP - трудные двухуровневые задачи стандартизации тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Горбачевская, Людмила Евгеньевна

• Горбачевская, Людмила Евгеньевна
• кандидат физико-математических наук
• 1998

Оглавление диссертации кандидат физико-математических наук Горбачевская, Людмила Евгеньевна

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. Двухуровневая задача стандартизации в условиях

однозначности выбора потребителей (ДЗСОВ)

§1. Постановка задачи

§2. Свойство связности

§3. Свойство квазивыпуклости

§4. Свойство согласованности

§5. ДЗСОВ и полиномы от булевых переменных

§6. Свойство обобщенной квазивыпуклости

§7. Подходы к построению оценки оптимума

§8. Дополнительные замечания

8.1. ДЗСОВ при заданных покупательных способностях потребителя

8.2. ДЗСОВ с фиксированным числом выбираемых производителем изделий

8.3. ДЗСОВ с нулевыми начальными затратами производителя

ГЛАВА 2. Кооперативная и антикооперативная двухуровневые задачи

стандартизации (КДЗС и АКДЗС)

§1. Постановка задач

§2. КДЗС и свойство квазивыпуклости

§3. КДЗС и свойство квазивогнутости

§4. КДЗС и свойство связности

§5. Сводимость к задаче минимизации полинома от булевых переменных

§6. АКДЗС и свойство квазивогнутости

§7. АКДЗС и свойство квазивыпуклости

§8. АКДЗС и свойство связности

§9. Подходы к построению оценок оптимумов

ГЛАВА 3. Двухуровневая задача стандартизации с коррекцией

дохода (ДЗСКД)

§1. Постановка задач

§2. Кооперативная ДЗСКД

2.1. Сводимость к задаче с парой матриц

2.2. Свойства квазивыпуклости и квазивогнутости

2.3. Свойство связности

§3. Антикооперативная ДЗСКД

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

Введение диссертации (часть автореферата) на тему «Полиномиально разрешимые и 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 (®ü) ieijeJ

£ Xij = 1, Xij < Xi, Xij G {0,1}, % G /, j G J.

ia

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

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

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

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

свойство согласованности пары матрицы. Показано, что если матрица затрат потребителей и матрица дохода согласованы, то задача решается эффективно. В §5 доказывается эквивалентность рассматриваемой задачи и задачи минимизации полинома от булевых переменных на множестве неединичных векторов. В §6 предлагается полиномиальный алгоритм решения задачи с обобщенно квазивыпуклой матрицей затрат потребителей. В §7 предлагаются подходы к построению нижних оценок оптимума целевой функции. В пункте 1 §8 рассматривается модель выбора номенклатуры изделий при заданных покупательных способностях и показывается, что она сводится к исходной задаче. В пункте 2 §8 рассматривается модель выбора номенклатуры фиксированного числа изделий и доказывается, что свойства квазивыпуклости и связности матрицы затрат потребителей позволяют эффективно ее решать. Если матрицы затрат потребителей и матрица доходов согласованы, то задача остается ЫР-трудной. В пункте 3 §8 рассматривается модель выбора номенклатуры изделий с нулевыми начальными затратами производителя.

Во второй главе рассматриваются двухуровневые задачи стандартизации, в которых единственность оптимального решения в задаче нижнего уровня не предполагается. В §1 вводятся основные определения и предлагаются две постановки, названные "кооперативная"и "антикооперативная". В §2 доказывается, что если матрица затрат потребителей строго квазивыпуклая, то "кооперативная"двухуровневая задача стандартизации (КДЗС) сводится к задаче о "ближайшем соседе". Если матрица затрат потребителей квазивыпукла, а матрица доходов монотонна относительно нее, то КДЗС остается NP-тpyднoй.

В §3 рассматривается КДЗС с квазивогнутой матрицей затрат потребителей. Доказывается, что если матрица доходов квазивыпукла относительно матрицы затрат производителей, то КДЗС полиномиально разрешима. Если матрица доходов квазивогнута относительно матрицы затрат производителей, то КДЗС остается КР-трудной. В §4 рассматривается КДЗС с сильно связной матрицей затрат потребителей и выделяется полиномиально разрешимый случай. В §5 показано, что " кооперативная" и " антикооперативная" задачи сводятся к задаче минимизации полинома от булевых переменных. В §6 доказывается, что если матрица затрат потребителей обладает свойством квазивогнутости, то "антикооперативная"двухуровневая задача стандартизации (АКДЗС) решается эффективно. В §7 доказывается, что если матрица затрат потребителей строго квазивыпуклая, то АКДЗС сводится к задаче о "ближайшем соседе". Если матрица затрат потребителей квазивыпукла, а матрица доходов монотонна относительно нее, то АКДЗС остается КР-трудной. В §8 рассматривается АКДЗС с сильно связной матрицей затрат потребителей и выделяется полиномиально разрешимый случай. В §9 предлагаются подходы к построению нижних оценок оптимумов целевых функций КДЗС и АКДЗС.

В третьей главе рассматривается двухуровневая задача стандартизации с коррекцией дохода (ДЗСКД). В §1 предлагаются две постановки с корректирующими переменными: "кооперативная"и "антикооперативная". В §2 изучаются свойства "кооперативной" ДЗСКД. В пункте 1 указываются оптимальные значения корректирующих переменных для любого подмножества видов изделий, выбираемых производителем. Показывается сводимость этой задачи к задаче с "парой матриц". В

пункте 2 доказывается, что если матрица затрат потребителей квазивыпуклая, а матрица доходов квазивогнутая, то рассматриваемая задача остается NP-тpyднoй. В пункте 3 рассматривается случай, когда матрица, определенная как разность матрицы затрат потребителей и матрицы дохода, является связной. Доказывается, что если матрица затрат потребителей связная, то рассматриваемая задача остается КР-трудной, а если она сильно связная и перестановка, порожденная этой матрицей, совпадает с перестановкой порожденной разностью матриц, то задача решается эффективно. В §3 рассматривается "антикооперативная" ДЗСКД и показывается, что найдутся значения корректирующих переменных, позволяющие получить оптимальное значение целевой функции сколь угодно близкое к оптимальному значению целевой функции "кооперативной"ДЗСКД.

В заключении коротко формулируются основные результаты.

Основные результаты диссертации опубликованы в работах [70-76] и докладывались на Международной конференции по проблемам оптимизации и экономическим приложениям (Омск, 1997 г.), на Международной Сибирской конференции по исследованию операций (Новосибирск, 1998 г.), на семинарах Института математики СО РАН и Института вычислительной математики и математической геофизики СО РАН.

Автор выражает искреннюю признательность научным руководителям В. Т. Дементьеву и Ю. В. Шамардину за постоянное внимание и всестороннюю поддержку.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Горбачевская, Людмила Евгеньевна

ЗАКЛЮЧЕНИЕ

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

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

Исследованы двухуровневые задачи стандартизации с "коррекцией дохода". Доказана сводимость рассматриваемой "кооперативной" за м }} ч/ V "ГТ дачи к задаче с парой матриц , изучаются свойства последней. Доказано, что задача остаются КР-трудной, если матрицы затрат квазивыпуклые. Доказано, что если матрицы связные, то задача остаётся КР-трудной. Указаны дополнительные условия, позволяющие решать эту задачу эффективно.

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

Отмечено, что рассмотренные в работе "кооперативные" двухуровневые задачи стандартизации, как и простейшая задача размещения, являются частными случаями однопараметрической задачи.

Список литературы диссертационного исследования кандидат физико-математических наук Горбачевская, Людмила Евгеньевна, 1998 год

Литература

1. Агеев А. А. О сложности задач минимизации полиномов от булевых переменных // Экстремальные задачи исследования операций (Управляемые системы). Новосибирск, 1983. Вып. 23. С. 3-11.

2. Агеев А. А. Приближенные алгоритмы минимизации полиномов от булевых переменных // Управление и оптимизация (Управляемые системы). Новосибирск, 1985. Вып. 26. С. 3-19.

3. Агеев А. А. Графы, матрицы и простейшая задача размещения // Модели дискретной оптимизации (Управляемые системы). Новосибирск, 1989. Вып. 29. С. 3-10.

4. Агеев А. А. Полиномиальный алгоритм решения задачи размещения на последовательно-параллельной сети // Целочисленная оптимизация и ее приложения (Управляемые системы). Новосибирск, 1990. Вып. 30. С. 3-16.

5. Агеев А. А. Точные и приближенные алгоритмы для задач размещения: обзор последних достижений// Тез. докл. межд. конф. «Сибирская конференция по исследованию операций ». - Новосибирск, 1998. С. 4-10.

6. Агеев А. А., Береснев В. Л. Алгоритмы минимизации для некоторых классов полиномов от булевых переменных // Труды ИМ СО РАН. Новосибирск: Наука, 1988. Т. 10. С. 5 — 17.

7. Агеев А. А., Гарагулов М. М. Новые менее трудоемкие алгоритмы для некоторых частных случаев задачи размещения // Тез. докл. межд. конф. «Сибирская конференция по исследованию операций ». -Новосибирск, 1998. С. 96.

8. Адельсон-Вельский Г. М., Диниц Е. А., Карзанов А. В. Потоко-

вые алгоритмы. М.: Наука, 1975. 119 с.

9. Алексеев О. Г. Комплексное применение методов дискретной оптимизации М.: Наука, 1987. 248 с.

10. Белинская И. Г.Об одном классе полиномов от булевых переменных // Целочисленные экстремальные задачи (Управляемые системы). Новосибирск, 1981. Вып. 21. С. 6-12.

11. Беллман Р. Динамическое программирование М.: Изд-во иностр. лит., 1960. 400 с.

12. Береснев В. JI. Алгоритмы минимизации полиномов от булевых переменных //Проблеммы кибернетики. М.: Наука, 1979. Вып. 36. С. 225-246.

13. Береснев В. JI. Эффективный алгоритм для задачи размещения производства с вполне уравновешенной матрицей //Дискретный анализ и исследование операций. Новосибирск, 1998. Сер. 1, Т. 5, № 1. С. 20-31.

14. Береснев В. JL, Гимади Э. X., Дементьев В. Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978. 333 с.

15. Береснев В. Л., Давыдов А. И. О матрицах, обладающих свойством связности // Дискретные экстремальные задачи (Управляемые системы). Новосибирск, 1979. Вып. 19. С. 3-21.

16. Гермейер Ю. Б. Игры с непротивоположными интересами. М.: Наука, 1976.

17. Гимади Э. X. Эффективный алгоритм решения задачи размещения с областями обслуживания, связными относительно ациклической сети // Экстремальные задачи исследования операций (Управляемые системы). Новосибирск, 1983. Вып. 23. С. 12-23.

18. Гимади Э. X. Задача стандартизации с данными произвольного знака и связными, квазивыпуклыми и почти квазивыпуклыми матрицами // Методы целочисленной оптимизации (Управляемые системы). Новосибирск, 1987. Вып. 27. С. 3-11.

19. Гимади Э. X. Обоснование априорных оценок качества приближенного решения задачи стандартизации // Методы целочисленной оптимизации (Управляемые системы). Новосибирск, 1987. Вып. 27. С. 12-27.

20. Гимади Э. X., Дементьев В. Т. Некоторые задачи выбора оптимальных параметрических рядов и методы их решения (задачи стандартизации) // Проблемы кибернетики. 1973. Вып. 27. С. 19-32.

21. Гришухин В. П. Полиномиалъность в простейшей задаче размещения М., 1987. 64 с. (Препринт / АН СССР. Центр, экон.-мат. ин-т).

22. Гэри М., Джонсон Д. Вычислительные машины и труднореша-емые задачи. М.: Мир, 1982. 416 с.

23. Дементьев В. Т. Производство экологического оборудования

в условиях рыночной экономики и госдотаций // Тр. 3-й междунар. конф. «Математические проблемы экологии». Новосибирск, 1996. С. 100-102.

24. Дементьев В. Т. Новый класс задач стандартизации и размещения/ / Тез. докл. межд. конф. «Проблемы оптимизации и экономические приложения». - Омск, 1997. С. 57-58.

25. Карп Р. Сводимость комбинаторных проблем // Кибернетический сборник. М.: Мир, 1975. Вып. 12. С. 16-58

26. Корбут А. А., Финкельштейн Ю. Ю. Дискретное программиро-

вание. М.: Наука, 1969. 368 с.

27. Кочетов Ю. А., Плясунов А. В. Полиномиально разрешимый класс задач двухуровневого линейного программирования //Дискретный анализ и исследование операций. Новосибирск, 1997. Сер. 2, Т. 4, № 2. С.23-33.

28. Кук С. Сложность процедур вывода теорем // Кибернетический сборник. М.: Мир, 1975. Вып. 12. С. 5-15

29. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. 512 с.

30. Плясунов А. В. Полиномиально - разрешимая задача двухуровневого вогнутого программирования// Тез. докл. межд. конф. «Сибирская конференция по исследованию операций ». - Новосибирск, 1998. С. 94.

31. Современное состояние теории исследования операций (ред. Моисеев ). М.: Наука, 1979.

32. Трубин В. А. Универсальность одного класса квадратичных целочисленных задач // Кибернетика. 1977. № 2. С. 147.

33. Трубин В. А. Эффективный алгоритм размещения на сети в форме дерева // Докл. АН СССР. 1976. Т. 231, № 3. С. 547-550.

34. Финкелыитейн Ю. Ю. Приближенные методы и прикладные задачи дмскретного программирования. М.: Наука, 1976. 264 с.

35. Шамардин Ю. В. Трехуровневые задачи размещения производства. Новосибирск, 1998. 18 с. (Препринт / РАН. Сиб. отд-ние. Ин-т математики; № 47).

36. Юдин Д. Б., Гольдштейн Е. Г. Линейное программирование. М.: Наука, 1969. 424 с.

37. Anandalingam G., Friesz T. L. Hierarchucal optimization: an introduction // Ann. Oper. Res. 1992. V. 34, № 1. P. 1-11.

38. Anandalingam G., White D. J. A Solution Method for the linear static Stackelberg problem using penalty functions // IEEE Transactions on Automatic Control. 1990. V.35, № 10. P. 1170-1173.

39. Audet C., Hansen P., Jaumard B., Savard G. Links between Linear Bilevel and Mixed 0-1 Programming Problems // Journal of Opt. Theory and Appl. 1997. V. 93, № 2. P. 273-300.

40. Bard J. F. An efficient point algorithm for a linear two-stage optimization problem // Oper. Res. 1983. V. 31, № . P. '670- 684.

41. Bard J. F., Moore J. T. A branch and bound algorithm for the bilevel programming problem // SIAM J. Sci. Stat. Comput. 1990. V. 11, № 2. P. 281-292.

42. Ben-Ayed O. Bilevel linear programming // Comput. Ops. Res. 1993. V. 20, № 5. P. 485-501.

43. Ben-Ayed O., Blair C. T. Computational difficulties of bilevel linear programming // Oper. Res. 1990. V. 38. P. 556-560.

44. Bialas W., Karwan M. Two-level linear programming // Manag. Sci. 1984. V. 30. P. 1004-1020.

45. Blair C. The computational complexity of multi-level linear programs // Ann. Oper. Res. 1992. V. 34, № 1. P. 13-19.

46. Bracken J., McGill J. T. Mathematical Programs with Optimization Problems in the Constraints // Oper. Res. 1973. V.21, № 1. P. 37-44.

47. Burkard R. E. Efficiently solvable special cases of hard combinatorial optimization problems // Mathematical programming. Ser. B. 1997. V. 79, № 1-3. P. 55-70.

48. Calamai P. H., Vicente L. N. Generating linear and linear-quadratic bilevel programming problems // ACM Transactions on Mathematical Software. 1994. V. 20. P. 103-119.

49. Candler W., Norton R. Multilevel programming // Technical Report 20, World Bank Development Research Center, Washington D. C., 1977.

50. Cassidy R. G., Kirby M. J. L., Raike W. M. Efficient distribution of resources through three levels of government // Manag. Sei. Ser. B. 1971. V.17, № 8. P.462-473.

51. Cornuejols G., Fisher M. L., Nemhauser G. L. Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms // Manag. Sei. 1977. V.23, № 8. P. 789-810.

52. Daskin M. S. Network and Discrete Location: models, algorithms and applications John Wiley and Sons, New York, 1995.

53. Dempe S. A Simple Algorithm for the Linear Bilevel Programming Problem // Optimization. 1987. V. 18, № 3. P. 373-385.

54. Dempe S. Discrete Bilevel Optimization Problems // Report № 12. University Leipzig. 1996.

55. Dudas T., Klinz B., Woeginger G. J. The computational complexity of multi-level programming problems revisited // Reports from the Optimization Group at the TU Graz. 1995. № 49.

56. Efroymson M. E., Ray T. L. A Branch-bound algorithm for plant location // Oper. Res. 1966. V.14, № 3. P. 361-368.

57. Erlenkotter D. A. A dual-based procedure for uncapacitated faciliti location // Oper. Res. 1978. V.26, № 6. P. 992-1009.

58. Facility Location: a survey of applications and methods Zvi Drezner ed., Springer-Verlag, New York. 1995.

59. Hochbaum D. S. Heuristics for the fixed cost median problem // Math. Progr. 1982. V.22, № 2. P. 148-162.

60. Hoffman A. J., Kolen A. W. J., Sakarovitch M. Totally- balanced and greedy matrices // SIAM J. Alg. Dis. Meth. 1985. V. 6, № 4. P. 721-730.

61. Jeroslow R. The polynomial hierarchy and a simple model for competitive analysis // Math. Prog. 1985. V. 32. P. 146-164.

62. Krarup J. Fixed-cost and other network flow problems // Ph. D. thesis, IMSOR, Technical University of Denmark. 1967.

63. Krarup J., Pruzan P. M. The simple plant location problem: survey and synthesis // European J. Oper. Res. 1983. V. 12, № 1. P. 36-81.

64. Moore J. T., Bard J. F. The mixed integer linear bilevel programming problem // Oper. Res. 1990. V. 38, № 5. P. 911-921.

65. Narula S. C., Nwosu F. D. Two-level hierarchical programming problem // Essays and surves on multiple criteria decision making. P.Hansen ed., Springer-Verlab, Berlin. 1983. P. 290-299.

66. Stackelberg H. V. The Theory of the Market Economy. Oxford: Oxford Univ. Press. 1952.

67. Vicente L. N., Calamai P. H. Bilevel and Multilevel Programming: A Bibliography Review // Journal of Global Opt. 1994. V. 5. P. 291-306.

68. Vicente L. N., Savard G., Judice J. Discrete Linear Bilevel Programming Problem // Journal of Opt. Theory and Appl. 1996. V. 89, № 3. P. 597-614.

69. Wen U., Hsu S. A note on a linear bilevel programming algorithm based on bicriteria programmimg problem // Computers and Oper. Res. 1989. V.16, № 1. P. 79-83.

70. Горбачевская Л. Е., Дементьев В. Т., Шамардин Ю. В. Двухуровневая экстремальная задача выбора номенклатуры изделий. Новосибирск, 1997. 26 с. (Препринт / РАН. Сиб. отд-ние. Ин-т математики; № 41).

71. Горбачевская Л. Е. К двухуровневой экстремальной задаче выбора номенклатуры изделий. Новосибирск, 1998. 29 с. (Препринт / РАН. Сиб. отд-ние. Ин-т математики; № 48).

72. Горбачевская Л. Е. Об одной задаче размещения// Тез. докл. межд. конф. «Проблемы оптимизации и экономические приложения». - Омск, 1997. С. 49.

73. Дементьев В. Т., Шамардин Ю. В., Горбачевская Л. Е. Многоуровневое программирование в задачах размещения и стандартизации // Материалы межд. конф. «Сибирская конференция по исследованию операций ». - Новосибирск, 1998. С. 12-15.

74. Горбачевская Л. Е. Об одной задаче стандартизации // Материалы межд. конф. «Сибирская конференция по исследованию операций ». - Новосибирск, 1998. С. 93.

75. Горбачевская Л. Е., Кочетов Ю. А. Вероятностная эвристика для двухуровневой задачи размещения // Труды 11 межд. Байкальской школы-семинара «Методы оптимизации и их приложения ». - Иркутск, 1998. С. 249-252.

76. Горбачевская Л. Е., Шамардин Ю. В. Задачи двухуровневого программирования в стандартизации // Труды 11 межд. Байкальской школы-семинара «Методы оптимизации и их приложения ». - Иркутск, 1998. С. 253-256.