Москвин Б.В. Теория принятия решений

Подождите немного. Документ загружается.

переменных ограничены некоторым числом, можно свести к бу-

левой задаче путем замены переменных. Действительно, пусть x

∈ Z, x

= 0,...,v

, тогда x

можно заменить совокупностью перемен-

ных x

∈{0,1}. При этом

,1x,xx

ijj

∑∑

∈{0,1}

Специфика задач целочисленного (дискретного) програм-

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

ловий двойственности в каждой точке Δ, вследствие чего усло-

вия теоремы Куна-Таккера не выполняются, и для задачи (5.1) не

существует двойственной задачи. В этой связи методы, развитые

для задач линейного и нелинейного программирования, не при-

менимы

в общем случае для задач целочисленного программи-

рования.

Наиболее изученным классом задач целочисленного про-

граммирования являются задачи целочисленного линейного про-

граммирования, обладающие рядом свойств, позволяющих стро-

ить эффективные алгоритмы решения

x* = arg

max

x Δ∈

f(x), где ∆ = {x∈Z

│

∑

jij

xa ≤ b

, i = 1,…, m } .

Используемые в настоящее время методы решения задач

целочисленного программирования, можно разбить на пять групп.

1 группа методов. Используется традиционный математиче-

ский аппарат решения непрерывных задач. Целочисленность

достигается округлением результата до ближайшего целого из

области допустимых решений. Несмотря на кажущуюся простоту

метода, при округлении возникают трудности, связанные, прежде

всего, с тем, что количество вариантов округления может быть

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

чить допустимое решение, а

это при большом числе компонент

вектора, описывающего решение, довольно не тривиальная за-

дача. Кроме того, произвольное округление компонент может

привести к довольно значительным отклонениям от оптимального

решения. Более того, при округлении можно не обнаружить до-

пустимого решения, которое на самом деле существует.

2 группа методов. Выделяется класс задач, в которых ис-

пользование методов решения непрерывных задач математиче-

ского программирования автоматически приводит к получению

целочисленных решений.

3 группа методов. Методы отсечения. Решается задача без

ограничения на целочисленность, по результатам решения кото-

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

ния, отсекающие нецелочисленные решения. Процесс продолжа-

ется до получения оптимального целочисленного решения.

4 группа методов. Комбинаторно-эвристические методы.

Все множество альтернатив разбивается на подмножества, и

вводятся оценки, позволяющие отбрасывать подмножества, в

которых не содержится оптимального решения. Процесс продол-

жается до выявления оптимума.

5 группа методов. Приближенные методы. Здесь объединя-

ется большая группа методов, связанных с приближенной опти-

мизацией (неточное нахождение оптимума, приближенное удов-

летворение целочисленности, и т.п.). Здесь же рассматриваются

методы случайного поиска оптимального решения.

Далее рассмотрим более подробно методы второй, третьей

и четвертой групп.

5.2. Целочисленные и почти целочисленные многогранники

решений

Рассмотрим задачу целочисленного линейного программи-

рования в виде

L = c

x → max, (5.2)

A x ≤ b, (5.3)

x ≥ 0, (5.4)

x = (x

,...,x

)

, ∀x

- целое. (5.5)

Как было показано в 3.2, оптимальное решение х

задачи

линейного программирования (5.2)-(5.4) соответствует вершине

выпуклого многогранника M(A,b), задаваемого ограничениями

(5.3), (5,4). Тогда, если все решения, соответствующие вершинам

многогранника M(A,b) целочисленны (говорят, что вершины це-

лочисленны, или многогранник - ц е л о ч и с л е н н ы й), то и оп-

тимальное решение х

будет целочисленным.

Пусть M(A,b) - выпуклый многогранник, определяемый (5.3),

(5,4). Обозначим через G множество целочисленных решений,

удовлетворяющих (5.3), (5.4), т.е. принадлежащих M(A,b). Тогда

в ы п у к л о й о б о л о ч к о й G - M(G) называется пересечение

всех выпуклых множеств, содержащих G.

Утверждение. Пусть G множество целочисленных точек,

принадлежащих M(A,b). Тогда множество решений задачи (5.2)-

(5.5) содержится в выпуклой оболочке M(G).

M(A,b)

M(G)

рис. 5.1

Очевидно, что M(G) ⊆ M(A,b). Следовательно, если выде-

лить класс задач целочисленного линейного программирования,

для которых M(G) = M(A,b), то для нахождения оптимального ре-

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

программирования.

Матрица A называется а

б с о л ю т н о у н и м о д у л я -

р н о й, если любой минор (любого порядка) матрицы A равен

0,1,-1.

Утверждение. Многогранник M(A,b), задаваемый ограни-

чениями (5.3), (5.4), является целочисленным при любом цело-

численном b тогда и только тогда, когда матрица A абсолютно

унимодулярна [58].

В настоящее время не сформулировано конструктивных

(легко проверяемых) необходимых и достаточных условий абсо-

лютной унимодулярности матриц, тем не менее, определенные

критерии, которым должны удовлетворять такие матрицы, можно

задать. Так, в частности, из

определения абсолютной унимоду-

лярности следует, что элементы A должны принадлежать мно-

жеству {-1,0,1}. Сформулированы также достаточные условия

абсолютной унимодулярности A [58].

Достаточные условия абсолютной унимодулярности.

Матрица A ={ a

} с элементами a

∈ {-1,0,1} является абсо-

лютно унимодулярной, если

1) каждый столбец A содержит не более двух отличных от 0

элемента;

2) множество строк матрицы A можно разбить на два непере-

секающихся подмножества строк R

и R

такие, что

а) отличные от 0 элементы некоторого столбца A одного

знака принадлежат разным подмножествам строк;

б) отличные от 0 элементы некоторого столбца A разного

знака принадлежат одному из подмножеств строк.

Сформулированные достаточные условия абсолютной унимоду-

лярности являются в известной степени строгими, тем не менее,

для ряда моделей принятия решений они выполняются. Так для

рассмотренных в 2.2 транспортной модели и модели назначений

приведенные достаточные условия выполняются. Действительно,

пусть в транспортной модели (см. 2.2) s=2, q=3, тогда матрица A

условий такой задачи будет иметь вид

1 11000

0 00111

A = 1 00100

0 10010

0 01001

В каждом столбце содержится 2 отличных от 0 элемента. Строки

такой матрицы можно разбить на два подмножества R

= {1, 2} и

= {3,4,5}, которые удовлетворяют предъявляемым требовани-

ям.

Многогранник M(A,b) называется п о ч т и ц е л о ч и с -

л е н н ы м, если все целочисленные точки M(A,b) являются его

вершинами, и множество целочисленных вершин связно [29].

Тогда для нахождения оптимального решения с использо-

ванием симплекс-метода на каждой итерации

необходимо анали-

зировать целочисленность вершины, в которую осуществляется

переход. Если она целочисленна, то переход осуществляется;

если нет, то ищется другая смежная целочисленная вершина,

позволяющая повысить значение целевой функции. Процесс за-

канчивается, когда не найдется целочисленной вершины, позво-

ляющей увеличить целевую функцию.

Утверждение. Многогранник M(A,e), где e - вектор, все

компоненты которого равны 1, а элементы матрицы A принимают

значения 0 или 1, является почти целочисленным.

5.3. Методы отсечения в задачах дискретного

программирования. Алгоритм Р.Гомори

Основная идея методов отсечения [42, 49, 50, 84] состоит в

том, что решается задача без ограничения на целочисленность,

по результатам анализа решения которой в исходную постановку

вводятся дополнительные ограничения, отсекающие нецелочис-

ленные и оставляющие целочисленные решения. Процесс про-

должается до получения оптимального целочисленного решения

(т.е. целочисленная точка становится крайней). Методы отсече-

ния позволяют

решать как задачи целочисленного, так и задачи

частично целочисленного программирования; они применимы в

тех случаях, когда требование целочисленности распространяет-

ся и на целевую функцию; данные методы позволяют получить

решение за конечное число шагов.

Рассмотрим задачу целочисленного линейного программи-

рования в виде

L =

∑

→ max (5.6)

∑

= b

, i = 1,…,m, (5.7)

j .

≥ 0, j = 1,...,n, (5.8)

- целое, j = 1,...,n. (5.9)

Методы отсечения связаны с систематическим введением

дополнительных ограничений (отсечений), целью которого явля-

ется сведение допустимой области, определяемой (5.7),(5.8), к

выпуклой оболочке ее целочисленных точек в окрестности опти-

мального решения. Вводимое ограничение (отсечение) должно

удовлетворять требованиям:

- ограничение должно отсекать нецелочисленную точку;

- ограничение должно оставлять в допустимой области все це-

лочисленные

точки;

- ограничение, соответствующее отсечению, должно быть ли-

нейным, чтобы задача оставалась в классе задач линейного про-

граммирования;

- ограничение проходит через целочисленную точку (хотя и не

обязательно в допустимой области).

Первый алгоритм такого рода был предложен Р.Гомори.

Рассмотрим основные идеи этого алгоритма [84].

Отсечение Р.Гомори

Решается задача (5.6)-(5.8). Находится решение x, соответ-

ствующее вершине М(A,b).

x = (

, x

)

, где x

- базисные переменные;

- небазисные переменные;

= ║ x

║, i ∈ J

, J

- номера базисных переменных;

║

║,

j ∈ J

, J

- номера небазисных переменных.

Матрицу условий A можно представить в виде A = || S Q ||, тогда

S x

+ Q x

= b или x

+ S

-1

Q x

= S

-1

откуда

= S

-1

b - S

-1

Q x

, причем x

≥ 0, x

= 0.

Пусть i-я компонента x

нецелочисленна. Скомпенсировать

дробную часть x

можно за счет придания компонентам x

отлич-

ных от 0 значений. Обозначим

-1

b =β, β = ║β

║, S

-1

Q = α, α = ║ α

║.

Тогда

= β

∑

∈

Итак, i-ая компонента x

= β

- нецелочисленна. Предста-

вим β

, а соответственно и α

в виде суммы целой и дробной

части

= [β

] + {β

}; α

= [α

] + {α

где [β

] - целая часть β

, не превосходящая β

(соответственно, [α

]

- целая часть α

); {β

} - дробная часть β

(соответственно {α

} -

дробная часть α

); ∀ {β

} > 0, ∀ {α

} > 0.

Тогда

= [β

] + {β

} -

∑

∈

[α

] x

∑

∈

{α

} x

Необходимо скомпенсировать дробную часть x

, тогда не-

которые (или все) x

будут целые и больше 0. Перепишем по-

следнее уравнение в виде

- [b

] +

∑

∈

] x

= {β

} -

∑

∈

{α

} x

. (5.10)

Здесь левая часть представляет собой целое число, соот-

ветственно правая часть должна быть целым числом. При этом

возможны две ситуации

- первая: {β

} -

∑

∈

{α

} x

. > 0;

- вторая: {β

} -

∑

∈

{α

} x

. ≤ 0

Рассмотрим эти ситуации, начнем с первой. Так как {β

} > 0

и {α

} > 0, то эта ситуация возможна только, если левая часть

менее 1, т.е. она является дробью, что невозможно, т.к. левая

часть равенства (5.10) - целое число. Следовательно, имеет ме-

сто вторая ситуация, т.е.

{β

} -

∑

∈

{α

} x

. ≤ 0 . (5.11)

Отметим, что вершина с {β

} > 0 не удовлетворяет послед-

нему неравенству, т.е. она отсекается. Следовательно, выраже-

ние (5.11) представляет собой уравнение отсечения. Приведем

его к каноническому виду

∑

∈

{α

} x

. - x

n+1

= {β

} . (5.12)

Рассмотрим алгоритм решения задач целочисленного про-

граммирования (5.6)-(5.9), который сходится за конечное число

шагов.

1). Решается задача линейного программирования (5.6) - (5.8)

без ограничений на целочисленность. Если полученное решение

целочисленно, то процесс заканчивается, если нет, то осуществ-

ляется переход на шаг 2.

2). Выделяется нецелочисленная компонента x

, если таких

компонент несколько, то выбирается та, у которой меньший но-

мер i.

3). В систему ограничений вводится дополнительное (m+1)-е

ограничение вида

∑

∈

{α

} x

. - x

n+1

= {β

} ,

которое отсекает нецелочисленное решение и оставляет в допус-

тимой области все целочисленные решения.

4). m = m+1; n = n+1. Переход на шаг 1.

Как это видно из алгоритма, размерность решаемой задачи

растет на каждом шаге. Для устранения этого недостатка доволь-

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

ственной задачи линейного программирования (методы последо-

вательного уточнения оценок).

5.4. Методы типа "ветвей и границ" в задачах

дискретного программирования

Наряду с методами отсечения в дискретном программиро-

вании широко используются методы, основанные на последова-

тельном анализе некоторых подмножеств допустимых решений,

рассмотрении лишь тех подмножеств решений, которые оказы-

ваются перспективными по определенным признакам, и отбрасы-

вании подмножеств решений, являющихся неперспективными.

Такие переборные методы принято называть к о м б и н

а т о р -

н ы м и методами [50, 83]. Одним из наиболее известных мето-

дов такого типа является метод ветвей и границ. Следует отме-

тить, что под этим названием объединяется целая группа мето-

дов, построенных на идее анализа подмножеств решений, объе-

диняемых в одном ветвлении ("ветви") на дереве поиска, и оцен

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

рых оценок ("границ"). Такое построение алгоритма выбора наи-

лучшего решения позволяет учесть специфические особенности

конкретных моделей принятия решения и на этой основе повы-

сить их эффективность.

Будем рассматривать применение метода ветвей и границ

для задачи линейного целочисленного программирования, по-

ставленной в стандартной форме (5.2)-(5.5).

L(x) = c

x → max, (5.2)

A x ≤ b, (5.3)

x ≥ 0, (5.4)

x - целое. (5.5)

В результате решения данной задачи находится оптимальное

решение x

и L

= L(x

). Несмотря на большое разнообразие при-

менений метода ветвей и границ для различных моделей приня-

тия решений, ряд операций является общими.

В е т в л е н и е. Так как значения переменных, описываю-

щих решение в ограниченной области, принимают дискретные

значения

(пусть x

i-я переменная принимает значения из {1,...,v

}),

то можно построить дерево поиска решений.

________________________

0 1 v

________ . . . . . . . . . . .

0 v

_____ … … . . . . . . …

. . . . . . . . . . . . . . . . . . . . . . . . . . .

___ . . . . . . . . . . . . . . . . . . .

x=(0,0,...,0)

(3,1,...,6,...,0)

,..,v

)

Рис. 5.2.

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

ставляю собой различные решения. Часть этих решений может

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

дачи. Все множество допустимых решений задачи (5.2)-(5.5) обо-

значим через Δ, тогда ветвления соответствуют разбиению Δ на

подмножества можно представить в виде Δ = Δ

∪ Δ

∪ … ∪ Δ

Наибольшее распространение получили два вида ветвления.

Первый вид ветвления соответствует разбиению некоторо-

го множества решений Δ

на два непересекающихся подмноже-

ства. Например, Δ

k+1

∪ Δ

k+2

, где Δ

k+1

={ x ∈ Δ | x

≤ 4}; Δ

k+2

={ x

∈ Δ | x

> 4.

Второй вид ветвления реализует покомпонентное ветвле-

ние, которое проводится путем фиксации значений переменных;

например, Δ

{x ∈ Δ | x

= 4}. В частности, на рис. 5.2 представ-

лен именно этот вид ветвления.

100

В ы ч и с л е н и е г р а н и ц. Используется два вида гра-

ниц.

Р е к о р д L

- значение целевой функции оптимальное

для всех допустимых решений, соответствующих ветвлению Δ

Рекорд L

достигается на решении x

, т.е. L

= L(x

L(x) Max arg x

Δ∈

О ц е н к а g(Δ

). Для вычисления оценки g

= g(Δ

) реша-

ется оценочная задача. Как правило, это оптимизационная зада-

ча более простой структуры, чем исходная задача. К оценочной

задаче обычно предъявляется два требования:

- если оценочная задача не имеет допустимых решений, то и

исходная задача не имеет допустимых решений;

- оценка g(Δ

) должна превышать значение рекорда для Δ

т.е. g(Δ

) ≥ L

Вычисление границ является основой для исключения из

рассмотрения неперспективных подмножеств решений (ветвле-

ний). Так, если для некоторого ветвления Δ

оценка g(Δ

) будет

меньше, чем значение рекорда L

= L(x

) для ветвления Δ

, то

это означает, что в ветвлении Δ

не содержится целочисленных

решений, лучших, чем решение x

∈Δ

, и, следовательно, ветв-

ление Δ

можно исключить из дальнейшего рассмотрения.

Приведем один из возможных алгоритмов решения общей

задачи целочисленного линейного программирования (5.2)-(5.5),

основанных на методе ветвей и границ. В качестве оценочной

задачи может выступать задача линейного программирования

вида (5.2)-(5.4). В процессе решения задачи формируется список

кандидатов Q, т.е. ветвлений, которые необходимо проанализи-

ровать; Q = {Δ

, Δ

, ... , Δ

}. В начале решения задачи Q = {Δ}, q =

1; Δ - множество допустимых решений исходной задачи; значе-

ние рекорда L

= - ∞. Итак, алгоритм заключается в выполнении

последовательности итераций, каждая итерация состоит из четы-

рех шагов.

Шаг 0.- Исходное состояние. Список кандидатов Q = {Δ}; ре-

корд L

= -∞; x

= (-1,...,-1)

Шаг 1.- Выбор кандидата. Из списка Q выбирается один из

элементов, пусть это Δ

- кандидат (ветвление).

Шаг 2.- Анализ кандидата. Если оценка g

не известна, то ре-

шается оценочная задача и вычисляется оценка g

= g(Δ