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

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

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

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

Cl=A1[)A2J...jAi[)...)Al. (9-52)

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

Ak = BP{J...jB$.

Тогда П можно представить в виде

о=A U - U    U *Р U - U в& U Л+, U - U ^ (9.53)

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

 

Если А — некоторое подмножество множества £2, то оценкой подмножества А называется число £ (А) такое, что f (х)^£, (А) для любого хеА.

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

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

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

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

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

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

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

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

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

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

О Рассмотрим задачу о коммивояжере с матрицей расстояний С=(с,у) порядка п. Обозначим через Q множество всех маршрутов, при которых коммивояжер, выезжая из города Аъ побывает во всех остальных городах по одному разу и вернется в А. Пусть і j3 ( , 2^к^п— 1, — подмножество множества С1, состоящее из всех маршрутов, при которых коммивояжер, выезжая из Аи последовательно посещает города А,, А^.

Множество Q можно разбить на непересекающиеся подмно-

жества 0[, 2< Йі, 3) i п- Для осуществления ветвления с помо-

щью подмножества £ї)г t   ,, 2^fc^n —2, это подмножество раз-

биваем на подмножества вида     ,■ ,       ^р где}ф, і2, ц         і*.

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

Й], 2, З» Пі. 2, 4>       2, if-

Множество і, _ і        , при k=n~ 1 состоит из единственного

маршрута, и с помощью него ветвление не выполняется.

Оценку подмножества 01і ( ,         ,    ,,2^к^п — 1, вычисляем

по формуле

£(*V („і,. - К ,. 0 = с", + - + 4 Л +    min <V+ + (п—к)    тій    с j.

 

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

 

Подпись: (' 4
/   2 *
Если

 

С=

9 6   1 9 2 10 11 11 * 8 1 5  4 3 *8 1 11 1 8 *

 

то f (П,. 2)=4 + 2 + (5-2)-1=9, I (П, 2,3)=4 + 9+1+(5-3)-1 = 16, г(П,,1,4.з)=4+2 + 3 + 1 + 1-1 = 11.

Решение задачи о коммивояжере с данной матрицей подведено на следующей схеме:

 

S** Sb"

 

Оптимальный маршрут: Ах-*Аг-*А^-*Аъ-*А^А^

 

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

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

/= І У,*; (max): (9-54>

 

0«Sx^4, л> — целое, j= 1, 2,     л, (9.56)

где g,, ^ {j— 1, 2,     л), і — целые положительные числа.

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

O^Xj^dj,       2, n.

 

Множество £lz состоит из одного нулевого вектора при z=0 и совпадает с множеством допустимых решений задачи (9.54)—(9.56) нри z=b. Кроме того, если а=(хи хк, .... хл)е£1г, то 0 ^ хк ^ min (dk, z/gk).

Пусть (рк (г), fc = l, 2,     п, — наибольшее значение функции

к

£ У/Л) на множестве Ог. Функции <pi (г), <р2 (г), <рв (г), определенные при z = 0, 1, 2, 6, называются функциями Беллмана для задачи (9.54)—(9.56). Для этих функций имеют место следующие равенства:

(Рі (г)=      max       {^д-,}, (9.57)

xj — целое;

 

(pk(z)=      max      {y***+pt_i (z-#tJt*)}. (9-58)

— пелое.

 

Обозначим через x^(z), fc = l, 2, и, то целое значение xk, 0^;c*^niin (db г/g*), при котором достигается максимум выражения, стоящего в правой части соответствующего равенства.

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

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

Используя рекуррентное соотношение (9.58), последовательно находят функции Беллмана ср2 (z), (р„_| (z) и значение функции (р„ (z) при z^b. Одновременно определяют x'2(z), ...

х'„_, (г)их'я (Ь).

Строят оптимальное решение а =(*;; хг хп_\ х„) задачи (9,54)—(9.56), полагая х°„=х'п (b), х°„_, =*п_, (b-g„x\%

х? = *1 (*-уих!-г—iJcS_i---ft*S)-

О Рассмотрим следующую целочисленную задачу:

/= Зл, 4-4д:2 + 5хъ (max),

їх і + 5x2 + 4jc3^ 12,

0^jc,<3,7=1, 2, 3.

В данном случае <pl (z) =     max      {З*]}. Значения этой фун-

кции и соответствующие числа х (г), z = 0, 1,2, 12, приведены в табл. 9.7.

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

Так как min (3,  12/4) = 3, то <ръ (12)= max {5х3 + <р2 (12 —

-4х,)}, т. е. ф) (12)=шах {0 + 13, 5 + 9, 10+6,15 + 0} = 16. При этом jc э (12) = 2. Тогда

х°ъ = х! (12)=2; х°г = х'г (12-2-4) = *; (4)=0, (12-2 4-0 5)=jc; (4) = 2.

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

 

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

Оптимизационная задача (V, f, ІЇ) называется задачей нелинейного программирования, если целевая функция / является

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

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

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

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

f~f(Xi, х2, хл)

(9.59)

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

Подпись:  (9.60) (9.61)

где Ф, (jc,, х2,     х„) — некоторые функции, определенные на всем

пространстве R".

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

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

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

(ЯУ={М (Xli xz;     xn)eRnxj>0J= 1, 2, л},

RJ={A/(jc,;x2;    хя)еЪпх^Ъ, jeJ),

где J £ N={, 2, л}. Очевидно, что если J=0, то R}=R*; если J=N, toRJ=(R") + .

Функция

 

(где А/(л,; jc,; jc,)eRI, P (уп Уг ■»; У^е(йГ)+) называется функцией Лагранжа для задачи максимизации (9.59)—(9.61) (для задачи минимизации функция Лагранжа имеет вид

Ь(М,Р)=-/(М)-£У1Ф>(М))-1-1

Точка А/0 (г?; ...; х°; ...; *J)eRJ является точкой Куйр—Таккера для задачи (9.59)—(9.61), если существует точка Р0 (у?; ...;у[! ...; у0т)е(1С)+ такая, что справедливы условия Куна—Таккера:

^ (М0, Р0)^0,;є/,       ^ (А/о, Р„)>О,

Эх,

~ (А/с P0)=*0,jeNJ, у?- (А/0, Р0) = 0, /= 1, 2, /и,

х°- (А/0, P0)=0,jej.

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

/=jc,x2 (max), (9.62)

-Ч-Ul, (9.63)

4 9

Jt2^0. (9.64) Функция Лагранжа в данном случае имеет вид

L (хи хг, У)=ХХ2-У (- +      1 }

Так как

BL       Іхіуі  3L Іхгуі

— ~х2            ; — ~Х          ;

З*,       4    дх2 9

3L ду}

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

Таккера имеем систему

Xі Xі

 

l)=0;.

 

Решив ее, найдем точки М {х\ 0), — 2-^jcj ^0, и А/г (^/2; 3/-v/2)> которые являются искомыми точками Куна—Таккера. 0

Необходимое условие оптимальности для задачи нелинейного программирования можно сформулировать следующим образом. Пусть Л/0 — оптимальное решение задачи (9.59)—^-(9.61), причем функции f (М), <bj(M), 1-1, 2, т, дифференцируемы в этой точке. Если Мй — неособая точка допустимого множества задачи (9.59)—(9.61), то она является точкой Куна—Таккера этой задачи.

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

О Оптимальное решение задачи (9.62)—(9.64) находится среди точек Куна—Таккера этой задачи: Мх (хи 0), где —2^х(^0,

и Мг(ф. Ъф). Так как /(Л/,)=0, a f(M2) = 2, то Мг(ф

3/^/2) — оптимальное решение задачи (9.62)—(9.64). #

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

.Пара точек Л/0еК}, Poe(R™)+ называется седловой точкой функции Лагранжа, если

L (М, РоН L (М0, Р0) s£ L Шо, Р)

 

для всех MeRjH Pe(Rmy.

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

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

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

 

Страница: | 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 |