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

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ

Институт математики им. С. Л. Соболева

;м О ОД

.-/--Г

1 и • •; -5 На правах рукописи

УДК 519.854

ГОРБАЧЕВСКАЯ Людмила Евгеньевна

ПОЛИНОМИАЛЬНО РАЗРЕШИМЫЕ И ^-ТРУДНЫЕ ДВУХУРОВНЕВЫЕ ЗАДАЧИ СТАНДАРТИЗАЦИИ

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

АВТОРЕФЕРАТ

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

Новосибирск - 1998

Работа выполнена в Институте матаматики им. С. Л. Соболева СО РАН

Научные руководители:

доктор физико-математических наук В. Т. Дементьев, кандидат физико-математических наук 10. В. Шамардин

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

доктор физико-математических наук А. А. Колоколов, кандидат технических наук А. С. Кузнецов

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

Институт вычислительной математики и математической геофизики СО РАН

Защита состоится « 28 » 1998г. в. /6

часов на заседании специализированного совета Д 002.23.03 в Институте математики имени С. Л. Соболева СО РАН по адресу: 630090, Новосибирск 90, проспект Академика Коптюга, 4.

С диссертацией можно ознакомится в библиотеке Института матаматики им. С. Л. Соболева СО РАН.

Автореферат разослан «_ 22 » СеНлъХё^А_ 1998 г.

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

А. В. Косточка

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

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

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

В последние 10-15 лет интерес к задачам многоуровневого программирования значительно возрос [2]. В настоящее время это интенсивно развивающееся направление математического программирования имеет обширную область применения для решения задач проектирования транспортных сетей, управления, планирования, технического проектирования. В публикациях рассматриваются, в основном, непрерывные задачи двухуровневого программирования. В последние годы появились работы, посвященные изучению дискретных задач двухуровневого и многоуровневого программирования, но в целом эта область математического программирования мало исследована.

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

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

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

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

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

Публикации. По теме диссертации опубликовано 7 работ.

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

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

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

В первой главе исследуется двухуровневая задача стандартизации в условиях однозначности оптимального решения задачи нижнего уровня. В §1 предлагаются эквивалентные постановки двухуровневой задачи стандартизации «на максимум» и «на минимум».

Пусть I — {1,..., п} — множество видов изделий, 3 = {1,..., тп) — множество потребителей.

Производство изделий характеризуется следующими величинами: — затраты на разработку и подготовку производства г-го вида изделий, с,-; — затраты на производство г-го вида изделий для ;-го потребителя, г, — переменные выбора производителем г-го вида изделий (г, € {0,1}, г = (г,-)).

Потребительская сторона описывается следующими параметрами: — закупочно-эксплуатационные затраты на г'-й вид изделий у ^-го потребителя, г,-,- — переменные выбора ¿-м потребителем г-го вида изделий (г,^- 6 {0,1}).

Обозначим через Е = {0,1}", Е0 = Е\ {0} и Ег = Е\ {1}.

Рассматривается задача: найти

Я?1? + X) (!)

вЕа г€Г

где (жу) — оптимальное решение задачи:

(2)

¡6/

У^ ж»; = 1, < хц € {0,1}, г € /, У 6 <7. (3)

Отметим, что если с^- = сц для всех I € I, j € J, то рассматриваемая задача равносильна простейшей задаче размещения [1] и, следовательно, NP-тpyднa.

Абстрагируясь от содержательной интерпретации, считаем параметры с?, с,^-, произвольными числами.

В первой главе задача (1)-(3) рассматривается в предположении, что выполняется условие

¿у ф для всех з е 3 и г,к € /, таких, что г ф к. (4)

В §2 предлагается полиномиальный алгоритм решения рассматриваемой задачи в случае, когда матрица Б = (сД^) обладает свойством связности.

Матрица О называется связной, если для любых г, к 6 I разность

— меняет знак не более одного раза при монотонном изменении 3 = 1,...,т.

Теорема 1.1. Если матрица D связная, то задача (1)-(4) сводится к задаче: найти

S

min J~]{f(ik,jk-i,ik) + Hik, »fc+i, jfc)}

при ограничениях

1 < »i < ... < г, < j',4-1 = га 4-1, 0 = j0 < ji < ■ ■ ■ < j> = m,

fcik < + ^{кЗк+1 > + + к — 1,в 1,

1 < в < П.

Задача, указанная в теореме, решается методом динамического программирования.

Трудоемкость алгоритма решения задачи (1)-(4) в этом случае определяется трудоемкостью вычисления значений функций /(г, ц,з) и /г(г, и равна 0(т3гг + тп3) при объеме памяти 0(т2гг+ тп2).

В §3 показывается, что если матрица Б обладает свойством квазивыпуклости, то задача (1)-(4) решается эффективно.

Вектор Ь называется квазивыпуклым, если для любой тройки индексов г < к < I выполняется неравенство Ь^ < шах{6,-, &;}. Матрица О называется квазивыпуклой, если каждый ее вектор-столбец является квазивыпуклым.

Теорема 1.3. Если матрица О квазивыпуклая, то задача (1)-(4) сводится к задаче о "ближайшем соседе": найти

о

min У^/(4-1,4)

при ограничениях

О = г'0 < ¿1 < ... < г» < п, 1 < в < п.

Алгоритм её решения методом динамического программирования приведен, например, в [1].

В §4 рассматривается свойство согласованности пары матриц.

Матрицы С = (сц) и В называются согласованными (не согласованными), если из неравенства ё^ < с?^- следует неравенство Су < е^ (с,^ > си]) при всех 6 «/ и г, к & I таких, что г ф к.

Если матрицы С и £> согласованы, то задача (1)-(4) равносильна простейшей задаче размещения и, следовательно, МР-трудна.

Здесь ач С I, q € Q, п у = (у.) в Е.

Теорема 1.4. Если матрицы С и £) не согласованы, то задача (1)-(4) сводится к задаче минимизации (на множестве неединичных 0-1 векторов у) полинома Р(у) с неположительными коэффициентами при нелинейных членах.

Известно, что задача, упомянутая в теореме, решается эффектнв-

В §5 рассматривается взаимосвязь задачи (1)-(4) и задачи минимизации полинома Р(у) в случае произвольных матриц С и £>.

Основной результат §5 представляет

Теорема 1.5. Задача (1)-(4) эквивалентна задаче минимизации на множестве неединичных 0-1 векторов у полинома Р(у) с произвольными коэффициентами.

В §6 предлагается полипомиальный алгоритм решения задачи (1)~(4) в случае, когда матрица Э удовлетворяет свойству обобщенной квазивыпуклости [4].

Пусть < < 2 < •. • < —- упорядоченные по неубыванию элементы ]-го столбца матрицы О и = {г 6 I | > ¿¡}, I = 1,..п;

Компонентой связности множества Ц называется максимальный по включению целочисленный отрезок, содержащийся в этом множестве.

Матрица £) называется обобщенно-квазивыпуклой, если каждое множество Ц состоит не более чем из двух компонент связности.

Лемма 1.8. Если матрица Р обобщенно-квазивыпуклая, то задача (1)-(4) сводится к задаче: найти

Пусть

НО [3].

j = 1,...,т.

где 0 < Гд < — 1 < кч < еч — 1 < гг.

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

'я ~

Теорема 1.6. Если матрица D обобщенно-квазивыпуклая, то задача (1)-(4) решается эффективно алгоритмом с оценкой трудоемкости 0(тп log2 п + п4).

В §7 предлагаются подходы к построению нижних оценок оптимума целевой функции (1).

Пусть Sjj = {k 6 I\dkj < dij}. Выпишем неравенства

У) zk< |5,j|(l - scy). i 6 j 6 J. (5)

keSij

Лемма 1.9. При любом векторе z ф 0 условия (2), (3) определяют те же величины что и (3), (5).

Рассмотрим неравенства

Zi < Xij + zb> г s I, i £ j. (6)

kesu

Лемма 1.10. При любом векторе z ф 0 условия (2), (3) определяют те же величины Xij, что и (3), (6).

Кроме того, показывается, что (гу) является оптимальным решением задачи (2),(3) тогда и только тогда, когда

Xij — тт{.г;, min (1 - zu)}, i £ I, j £ J.

k£Sij

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

Еще один подход к построению нижней оценки оптимума заключается в сведении задачи (1)-(4) к задаче "с парой матриц":

mm + Y^ min hü + У •inax /«'i l

и использовании так называемых тупиковых матриц [1].

В §8 рассматривается двухуровневая задача стандартизации при заданных покупательных способностях и показывается, что она сводится к задаче (1)-(4). Там же для задачи (1)-(4) с фиксированным

числом выбираемых изделий доказывается, что свойства квазивыпуклости и связности матрицы £) позволяют построить эффективные алгоритмы её решения, а в случае, когда матрицы О и С не согласованы, задача остается ИР-трудной.

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

В §1 предлагаются "кооперативная" и "антикооперативная" постановки, соответствующие оптимистической и пессимистической оценке поведения потребителей по отношению к производителю. Пусть/(г) = {г £ I\zi = 1}, /¿(гг) = {г € Г(г) | = ттАе/(г) Кооперативная задача:

В §2 рассматривается задача (7) со свойством квазивыпуклости.

Матрица £) называется строго квазивыпуклой, если для каждого столбца ] 6 / найдется индекс tj такой, что с/у > ... > и

< ¿1^ + 1,3 < • • • < ¿пз-

Теорема 2.1. Если матрица В строго квазивыпуклая, то задача (7) сводится к задаче о "ближайшем соседе".

Вектор а .= (а\,...,ап) называется монотонным относительно вектора 6, если для любого множества {¿1,.. -,г3} С I такого, что ¿1 < ... < г3 и = 6,-2 = ... = Ь,г, вектор (а,-,,..., а,-,) является монотонным.

Матрица С называется монотонной относительно матрицы О, если её _/-й вектор-столбец монотонный относительно ]-то вектор-столбца матрицы Б, j € 3■

Теорема 2.2. Задача (7) с квазивыпуклой матрицей И и матрицей С, монотонной относительно матрицы является ЫР -трудной.

Доказательство этой теоремы и формулируемой ниже теоремы 2.6 строится на сведении №-трудной задачи минимизации квадрат-чного полинома от булевых переменных [5] к задаче (7).

Аптикооперативная задача:

В §3 рассматривается кооперативная задача со свойством квазивогнутости.

Вектор b = . .,bn) называется квазивогнутым, если для любой тройки индексов г < k < I выполняется неравенство b^ > min{&,-,

Вектор а = (ах, ...,ап) называется квазивыпуклым (квазивогнутым) относительно вектора Ь, если для любого множества {¿х,..., г3} С / такого, что ¿1 < ... < г5 и = 6,-2 = ... = 6;,, вектор (о,'1(..., аг-е) является квазивыпуклым (квазивогнутым).

Матрица С называется квазивыпуклой (квазивогнутой) относительно матрицы О, если её ¿-й вектор-столбец квазивыпуклый (квазивогнутый) относительно j-ro вектор-столбца матрицы Д ] £ 3.

Теорема 2.5. Если матрица И квазивогнутая, матрица С квазивогнутая относительно матрицы £) и существует оптимальное решение г* задачи (7) с условием \1{г*)\ > 3, то эта задача сводится к серии задач о "ближайшем соседе": найти

где 1 < и < V — 1 < п — 1.

Теорема 2.6. Задача (7) с квазивогнутой матрицей £> и матрицей С квазивыпуклой относительно матрицы £) является ЫР-трудной.

В §4 рассматривается кооперативная задача со свойством связности.

Связная матрица О называется сильно связной, если для любых индексов г < к, разность (1,у — d|tj не убывает при возрастании

Матрица С называется связной относительно матрицы О, если для любых индексов г < & и ^ < ... < таких, что ^^ = с^-,,..., = ¿к],, разность — Ск]г меняет знак не более одного раза, причем с минуса на плюс, при монотонном изменении г — 1,..., 5.

Теорема 2.7. Если матрица Б сильно связная, а матрица С

М-

S

при ограничениях

U = ll < 12 < ■ Ь-1 <»»=«:

связная относительно D, то задача (7) сводится к задаче: найти

i

min {Л(г'0) h,j0) + У](/(4, jfc-Ь jfc) + H^kJk+iJk)) }

при ограничениях

О = г'о < ¿1 < ... < г3 < jä+i = п + 1,

О = ¿о < h < • • • < i» = т, ditjk < d{k+1jk, dikjk+i > k = l,s - 1,

1 < s < n .

Трудоемкость алгоритма решения задачи (7) в этом случае определяется трудоемкостью вычисления значений функций f(i,q,j) и h(i, k,j) и равна 0(т3п + тп3) при объеме памяти 0(т2п + тп2).

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

В §6 рассматривается антикооперативная задача со свойством квазивогнутости.

Лемма 2.12. Если матрица D квазивогнутая, то задача (8) сводится к задаче:

п п-Ь1

min а,- (1 - yi) + Ъч П Vi + Yh aikVl '''ViVk '''Уп

У Jl iel q£Q ¡6«, ¿-0 k=i+1

где bq < 0, а,-¡, > 0, aq С I.

Теорема 2.11. Если матрица D квазивогнутая и существует оптимальное решение z* задачи (8) с условием |/(.z*)| > 3, то она сводится к серии задач минимизации полинома от булевых переменных с отрицательными коэффициентами при нелинейных членах.

В §7 рассматривается антикооперативная задача со свойством квазивыпуклости.

Теорема 2.12. Если матрица D строго квазивыпуклая, то задача (8) сводится к задаче о "ближайшем соседе".

Далее рассматривается NP-трудная задача о минимальном вершинном покрытии кубического графа [6].

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

п — 2 п п — 1

min _ У») + Е Е ккШУк + ащцуц-i }

УВЕ i£I ¡=1 k=i+2 1=1

где bik < 0, с,- > 0.

Для доказательства используется сводимость задачи поиска минимального вершинного покрытия к задаче минимизации квадратичного полинома с разделяющимися переменными, полученная в [3].

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

Теорема 2.14. Задача (8) с квазивыпуклой матрицей D и матрицей С, монотонной относительно D, является NP-трудной.

В §8 рассматривается антикооперативная задача со свойством связности.

Матрица С называется сильно связной относительно матрицы D, если для любых индексов г < к и ji < ... < js таких, что dij1 = dkji> • • ^¡j, = dkj,, разность c,Jr — Ckjr не убывает при монотонном изменении г — 1,..., s.

Теорема 2.15. Если матрица D сильно связная, а матрица (—С) сильно связная относительно D, то задача (8) сводится к задаче: найти

S

min {h(io, г'ъ jo) + , jfc-i.ifc) + h(ik, ü+i, jk)) }

(nj*),« f^i

при ограничениях

О = г0 < г'а < ... < г, < г3+1 = п + 1,

0 = jo < ji < ■ ■ ■ < 3> - т, Ч £ Uik+lh, ik+i £ Uikjk+1, k = 1, s.

1 < s < n .

Оценки тредоемкости и объема памяти алгоритма решения задачи (8) в этом случае равны 0(т3п + тп3) и 0(т2п + тп2) соответственно.

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

Набор (х^), удовлетворяющий условиям (3), называется г-оп-тимальиым в кооперативной (антикооперативной) задаче, если из того, что = 1 следует г € /¿(г) и су = гшп*6/у(г) с^- ( су = шас/,]).

Пусть = {к 6 / | либо ¿/у < с?у, либо d|tj = с/у и сду < су}.

Лемма 2.18. Для любого вектора г ф 0 набор (жу) является г-оптимальным в кооперативной задаче тогда и только тогда, когда

У^ гк < |%|(1 - жу) 4- Zi - ху , г € I, 1 е 3, квУ,,

^а;у = 1, губ {0,1}.

Пусть 1Уу = {к £ I | либо dkj < с!у, либо dkj = dij и с/у > су}.

Лемма 2.19. Для любого вектора г ^ 0 набор (жу) является г-оптималъным в антикооперативной задаче тогда и только тогда, когда

^ *к< Щэ |(1 - ху) + 2,- - жу , i<=I,j(= 3,

Е!

¡6/

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

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

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

Пусть U = {(«у) | «у > 0}.

Кооперативная задача состоит в том, чтобы найти:

max { шах > > (о,-7- — иц)хц — > с? ¿Л, (9) J€J iti

где R(z, и) множество оптимальных решений задачи:

mm V Uij)xij, (10)

ïtifti

m = l, xij <zit xij e {o,l}, i ei, j e J. (ii)

iei

Антикооперативная задача:

ma* {, min _ "У)1« ~ (12)

где множество R(z, и) то же, что и выше.

Обозначим через G(z, м) и 5"(.г, и) целевые функции кооперативной и антикооперативной задач соответственно.

В §2.1 показывается сводимость задачи (9)—(11) к задаче "с парой матриц" [1].

Набор V называется z-оптимальньш, если G(z, v) = maxuecrG(z,u). Теорема 3.1. Для всякого z S Eq набор (tiy) с компонентами iifj — dij — minjg/fj) dij, i E l{z), j € J, является z-оптимальным.

С помощью теоремы 3.1 доказывается, что задача (9)—(11) сводится к задаче

min {J2 chi + J2 ~9ij) + Y,

И поэтому может быть исследована методами работы [1].

В §2.2 доказывается, что если матрица (dij) квазивыпуклая, а матрица (gij) квазивогнутая, то задача (9)—(11) остается NP-трудной. В §2.3 рассматривается задача (9)—(11) со свойством связности. Рассмотрим задачу " с парой матриц" :

S CU + £ ® + £ &(?) fit}' (13)

*€J Je«

где с? > 0, |Г| = w.

Теорема 3.3. Задача (13) со связными матрицами (hij) и (¡и) является NP-трудной.

Доказательство строится на сведении NP-трудной задачи о минимальном вершинном покрытии кубического графа к задаче (13).

Обозначим Н — (Л,j), F = (fa).

Перестановка (i'i ... ,in) множества I называется перестановкой порожденной матрицей Н, если при г < s, разность h{rj — hij либо неположительна для всех j £ J, либо меняет знак с минуса на плюс при монотонном изменении j = 1,... ,m.

Теорема 3.4. Если матрица Н связная, а матрица (-F) сильно связная и перестановка порожденная матрицей Н совпадает с перестановкой пороокденной матрицей (-F), то задача (13) решается алгоритмом с оценкой трудоемкости О(nwm2{w2 + n2m2)) при объеме памяти 0(nwm?(w 4- п)).

В §3 рассматривается антикооперативная задача (12).

Пусть г £ Ео, u £ U. Положим

Jo = {j £ J \ max (Sij - [d{j - min dij)) > min дц].

ig 1(г) »€-fj('z)

Пусть G*(z) = тахцес; G(z,u).

Лемма 3.5. Если множество Jq непустое, то для любого е > О найдется элемент и £U такой, что

G*(z) — е < S(z,u).

С помощью леммы 3.5 устанавливается справедливость следующей теоремы.

Теорема 3.6. При любом z £ Ео верно равенство

sup S(z,u) = max G(z, и).

u еи «ее/

Лемма 3.6. Если найдется элемент и £ U такой, что S(z, и) = С*(г), то Jo = Ь и 5(^,0) = max„6[7 G{z,u).

В заключении сформулированы основные результаты диссертации, которые состоят в следующем:

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

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

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

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

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

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

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

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

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

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

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

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

Цитированная литература:

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

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

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

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

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

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

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ

Институт математики им. С. Л. Соболева

ПОЛИНОМИАЛЬНО РАЗРЕШИМЫЕ И КР-ТРУДНЫЕ ДВУХУРОВНЕВЫЕ ЗАДАЧИ СТАНДАРТИЗАЦИИ

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

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

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

Научные руководители: доктор физико-математических наук, профессор В. Т. Дементьев, кандидат физико-математических наук

Ю. В. Шамардин

Новосибирск - 1998

Горбачевская Людмила Евгеньевна

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ ........................................................ 4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ.................................................. 122

ЛИТЕРАТУРА ................................................... 124

ВВЕДЕНИЕ

Одним из классов прикладных задач дискретной оптимизации, получивших широкое распространение, являются задачи стандартизации и размещения. К задачам стандартизации относятся, например, задачи выбора оптимальных параметрических рядов [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}т показано, что ее оптимальное решение может быть получено как предел последовательности оптимальных решений некоторого семейства линейных задач двухуровневого программирования.

В работе [