Имя материала: Справочник по математике для экономистов

Автор: В.И. Ермаков

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

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

/ = Хунтах), (9.47)

j=i

Jdai]xj=bi,   і = 1,2,..., т, (9.48)

Xj>0,  j=,2,...,n, (9.49)

Xj — целое,    j=,2,...,n. (9.50)

Метод отсечений опирается на следующее утверждение: если ослабление задачи (9.47)—(9.50) имеет нецелочисленное оптимальное опорное решение а0, то существует неравенство вида

&jXj>A, (9.51)

У=1

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

Неравенство (9.51), обладающее указанными свойствами, называют правильным отсечением. Правильное отсечение, например, можно построить следующим образом.

Симплекс-таблицу для ослабления задачи (9.47)—(9.50) приведем к базису а0, все оценки которого не положительны. В полученной таблице выбираем строку с дробным свободным членом dp:

256

*1

 

 

 

Хп

 

 

 

 

 

 

 

§1

 

 

К

8„

Обозначим через [a'pq] целую часть числа a'pq (a = 1, 2,я), т.е. ближайшее целое число, не превосходящее а', а через [dp] — целую часть числа d . Правильное отсечение в этом случае имеет вид

Так как [1/2] = 0, [-5/2] = -З, [1] = 1, [0] = 0, [3/2] = 1, то по первой строке можно построить правильное отсечение (l/2)Xj + + (1/2)х2 > 1/2. Аналогично по второй строке строится правильное отсечение (l/2)Xj + (2/3)х2 > 1/3. •

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

Для решения целочисленной задачи (9.47)—(9.50) методом отсечений необходимо выполнить ряд последовательных шагов. На каждом шаге решается задача линейного программирования; если эта задача оказывается неразрешимой, то и исходная целочисленная задача неразрешима.

Первый шаг. Находят оптимальное опорное решение Рх = = (х[^ х^ х^) ослабления целочисленной задачи (9.47)—(9.50). Если Pj окажется целочисленным, то оно — искомое. В противном случае строят правильное отсечение, записывают его в виде

^.-хп+1=А®, xn+l>0, и добавляют к системе ограничений исходной задачи.

257

к-й шаг (к > 2). Находят оптимальное опорное решение

$к ~ (ХР> х2®> xnfc)'хл+1' ^п+к-і) ослабления задачи, построенной на предыдущем шаге. Если pfe целочисленно, то ак = (xf

х^) — оптимальное решение исходной задачи (9.47)—(9.50). В противном случае строят правильное отсечение

п+к-1

X -kfx;-xn+k=A« хп+к>0,

 

и добавляют его к системе ограничений исходной задачи, полученной на (к - 1)-м шаге. После этого выполняют (к+ 1)-й шаг.

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

9.18. Метод ветвей и границ

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

Дана оптимизационная задача минимизации (V, /, Q). Предположим, что допустимое множество Q разбито на конечное число непересекающихся подмножеств:

Q = А и А2 и... и Ак и... и 4. (9.52)

Выберем некоторое подмножество Ак и тоже разобьем его на конечное число непересекающихся подмножеств:

А=і^и...иіЄ>. Тогда Q можно представить в виде

Q = 4 и... и А-1 и вік) и - u     ^ Л+1 ^ - ^ 4- (9-53)

Переход от разбиения (9.52) множества Q к разбиению (9.53) того же множества называют ветвлением с помощью подмножества 4.. Схематически процесс ветвления можно изобразить так:

Q

л

4—4t—Л

/

о(к) о(к)

 

258

Если А — некоторое подмножество множества Q, то оценкой подмножества А называется число Е,(А) такое, что f(x) > Ъ,{А) для любого х є А.

Для решения задачи минимизации (V, /, Q) методом ветвей и границ выполняют ряд последовательных шагов.

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

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

А>й шаг (к > 2). Рассматривают разбиение множества Q на подмножества, которое было получено на предыдущем шаге. Для каждого из этих подмножеств находят его оценку и выбирают подмножество с наименьшей оценкой. Если в выбранном подмножестве удается найти элемент а0 такой, что /(а0) совпадает с оценкой этого подмножества, то а0 — оптимальное решение задачи (V, /, Q). В противном случае осуществляют ветвление с помощью выбранного подмножества и переходят к следующему шагу.

Для применения метода ветвей и границ в каждом конкретном случае необходимо:

задать первоначальное разбиение допустимого множества на конечное число непересекающихся подмножеств;

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

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

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

Рассмотрим задачу о коммивояжере с матрицей расстояний С = (с~) порядка и. Обозначим через Q множество всех маршрутов, при которых коммивояжер, выезжая из города Av побывает во всех

259

остальных городах по одному разу и вернется в Av Пусть Qt i2j3,...jk, 2 < к < п - 1, — подмножество множества Q, состоящее из всех маршрутов, при которых коммивояжер, выезжая и.зАр последовательно посещает города Aii,     Ai .

Множество Q можно разбить на непересекающиеся подмножества Qj 2, Qx 3, Qj п. Для осуществления ветвления с помощью подмножества Qx іг ^ 'ік, 2 < к < п - 2, это подмножество разбиваем на подмножества вида ПМг;з/ь у, где у* 1, /2, *'3, ik.

Например, подмножество Qt 2 разбиваем на подмножества

Q

1,2, п'

^1,2,3' ^1,2,1

Множество £/2;/3,...,ік ПРИ к = п — 1 состоит из единственного маршрута, и с помощью него ветвление не выполняется.

Оценку подмножества Ц,^,...,^,^ 2 < к < п - 1, находим по формуле

)

.+ с,

'к-1'к

+ mm

j*l,i2,-,>k

к)  min са

ІФІ,І2>-''к

l*h     к

Если к = п - 1, то оценка подмножества Ц,^^...^ совпадает с длиной единственного маршрута, входящего в это множество.

9

9 *

3 1

О Пример. Если

ю

і

С =

11 4 11

Ґ * 2 11 5 1

 

9.19. Метод Беллмана для решения целочисленных задач линейного программирования

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

 

/ = Хунтах), (9-54)

 

2,gjXj * Ъ, (9.55)

0<Xj<dj,    Xj — целое,   j= 1,2,и, (9.56)

где gj, d. (j - 1, 2,и), b — целые положительные числа.

Обозначим через z - 0, 1, 2, b, множество всех целочисленных решений системы неравенств

л 7=1

О <*,<</., у=1,2,...,и,

Множество Q? состоит из одного нулевого вектора при z - 0 и совпадает с множеством допустимых решений задачи (9.54)—(9.56) при z - Ь. Кроме того, если а = (xv хк, хп) є Qz, то 0<xk<mm(dk,z/gk).

Пусть (yk(z), к - 1, 2,     и, — наибольшее значение функции

к

X      на множестве Q?. Функции ф^г), ф2(г),Ф„(г), определен-

ныеприг = 0,1, 2,называются функциями Беллмана для задачи (9.54)—(9.56). Для этих функций имеют место следующие равенства:

\%(z) = n    max     {у^}, (9.57)

ху - целое

Ф*(*) =       max      (ул+ф^и-сГЛ)}. (9.58)

0<xfc<min(^,z/gfc) Xj. - целое

Обозначим через x°ji(z), к = 1,2, п, то целое значение хк, 0<хк< min (rfL, г/сГо)) при котором достигается максимум выражения, стоящего в правой части соответствующего равенства.

261

Задачу (9.54)—(9.56) решают по следующей схеме:

По формуле (9.57) находят все значения функции ф^г), z = 0,1, 2,Ь. Одновременно определяют х*(г).

Используя рекуррентное соотношение (9.58), последовательно находят функции Беллмана <p2(z), ф„_і(г) и значение функции ф (г) при z = Ъ. Одновременно определяют х^(г), ...jX*^) и х*п(Ь).

Строят оптимальное решение а0 = (xj, х2,хи1, х°п) задачи (9.54)-(9.56), полагая х° = х*(й), = х*_,(Ь - g„x°), х? = = xX(b-g/n-gn_/n_l-...-g1xl).

О Пример. Решить следующую целочисленную задачу: /= 3Xj + 4х2 + 5х3(тах), 2Xj + 5х2 + 4х3 < 12, 0<ху.<3, 7=1,2,3.

В данном случае ф, (z) =     max     {Зх,}. Значения этой функции

О^х^тіпО.г/г)

и соответствующие числа x*(z), z = 0, 1, 2, 12, приведены в табл. 9.8.

Таблица 9.8

 

Z

0

1

2

3

4

5

6

7

8

9

10

11

12

Фі(г)

0

0

3

3

6

6

9

9

9

9

9

9

9

x(z)

0

0

1

1

2

2

3

3

3

3

3

3

3

По определению, ф2(г) =     max    {4х2 + \%(z - 5х2)}.

0<х2^пші(3,г/5)

В табл. 9.9 приведены числа 4х2 + фх(г - 5х2) при z = 0, 1, 2,12 и 0 <х2 < min (3, z/5), все значения функции ф2(г) и числах*(г).

Так как min(3, 12/4) = 3, то <р3(12) = rnax^{5x3 + ф2(12 - 4х3)}, т.е.

ф3(12) = max{0 + 13, 5 + 9, 10 + 6, 15 + 0} = 16. При этом х*(12) = 2. Тогда

х° = х*(12) = 2;  х° = х*(12 - 2 • 4) = х*(4) = 0;

х° = х*(12 - 2 ■ 4 - 0 • 5) = х*(4) = 2.

Следовательно, а0 = (2; 0; 2) является оптимальным решением нашей задачи, причем/(а0) - ф3(12) - 16. •

 

9.20. Задачи нелинейного программирования

Оптимизационная задача (К, /, Q) называется задачей нелинейного программирования, если целевая функция/является функцией л переменных (F= R"), а допустимое множество Q — множеством решений некоторой системы уравнений и неравенств с л неизвестными.

Так как любое уравнение равносильно системе двух неравенств

Шх1,х2,...,хп)<0,

-Ф(х1,х2,...,хп)<0,

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

Таким образом, задача нелинейного программирования — это задача максимизации или минимизации целевой функции

/=/(х1,х2,...,хя) (9.59)

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

ГФДдсі,дс2,...,дсв)^0, і = ,2,...,т, (9.60) [xj >0,   jeJczN = {l,2,...,n}, (9.61)

где Ф/Xj, х2, хи) — некоторые функции, определенные на всем пространстве R".

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

 

263

Кроме того, класс задач нелинейного программирования включает в себя задачи линейного программирования.

Введем следующие обозначения:

(R")+ = {M(xv х2,хп) є R" | Xj > 0J= 1, 2,и},

Щ = {M(xv x2,..., xn) є R" I x. > 0,j є /},

гдє/с:уУ= {1, 2,и}. Очевидно, что:

eani/=0,ToR}=R";

eaiH/=7V,ToR}=(R")+.

Функция

т

ЦМ,Р) = ДМ)-^уіФі(М)

 

(где M(xv х2,хп) є R", P(yv у2,yj є (Rm)+) называется функцией Лагранжа для задачи максимизации (9.59)—(9.61). Для задачи минимизации функция Лагранжа имеет вид

т

ЦМ,Р) = -ДМ)-^уіФі(М).

i=l

Точка MQ(x[°,Xj,х®) є R" является точкой Куна — Тиккера для задачи (9.59)—(9.61), если существует точка Р0(ух, у®, у^) є (Rm)+ такая, что справедливы условия Куна — Таккера:

|^(ilf0,P0)<0,         j є/, |^(ilf0,P0)>0,

dXj дуі

—Ш0,Р0) = 0,        jeNJ,     y°?-(M0,P0) = 0, i = l,2,...,m,

dXj дУі

x°^-(M0,P0) = 0, j<=J.

 

О Пример. Найти точки Куна — Таккера для задачи

f=x1x2(max), (9.62)

т+т-1> (9-63)

х2 > 0. (9.64)

 

264

Подпись: (2 х   , х2 j
9
Функция Лагранжа в данном случае имеет вид Цх1,х2,у1) = х1х2-у1' "

 

J

Подпись: 2ххух дЬ 4  ' Эх,
Так как ЭХ

дхх

 

 

= х,

 

2х2ух дЬ

 

 

9

то для отыскания точек Куна — Таккера имеем систему

Подпись: х2
9
Подпись: +    -1 < 0;
2 >
Подпись: f 2 х1   , л2 і

<0,

х2     4   - и,

2х2уу

 

■^2

4 ~9

4

Уі

х2>0, ^>0

 

= 0;

Решив ее, найдем точки М^х^ 0), где -2 < хх < 0, и М2(уі2; з/у/2), которые являются искомыми точками Куна — Таккера. •

Необходимое условие оптимальности для задачи нелинейного программирования можно сформулировать следующим образом. Пусть М0 — оптимальное решение задачи (9.59)—(9.61), причем функции ДМ), Ф((М), і = 1, 2, т, дифференцируемы в этой точке. Если MQ — неособая точка допустимого множества задачи (9.59)—(9.61), то она является точкой Куна — Таккера этой задачи.

Таким образом, если допустимое множество Q задачи (9.59)-(9.61) не имеет особых точек, а функции ДМ), Ф,(М), і = 1,2,т, дифференцируемы во всех точках Q, то оптимальное решение этой задачи следует искать среди точек Куна — Таккера.

О Пример. Оптимальное решение задачи (9.62)—(9.64) находится среди точек Куна — Таккера этой задачи: Мх(хх 0), где -2 < Xj < 0, и М2(у/2; 3/V2). Так как /(МЛ = 0, a ДМ2) = 3, то М2(лІ2; з/л/2) — оптимальное решение задачи (9.62)—(9.64). •

Следует отметить, что необходимое условие оптимальности малопригодно для решения большинства задач нелинейного программирования, так как лишь в редких случаях удается найти все точки Куна — Таккера задачи нелинейного программирования.

 

265

Пара точек М0 є R", Р0 є (Rm)+ называется седловой точкой функции Лагранжа, если

ЦМ,Р0)<ЦМ0,Р0)<ЦМ0,Р)

для всех Me Щи Ре (Rm)+.

Достаточное условие оптимальности для задачи нелинейного программирования: если (М0, Р0) — седловая точка функции Лагранжа для задачи (9.59)—(9.61), то М0 является оптимальным решением этой задачи.

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

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

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | 101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 | 126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 | 151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 | 176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 |