Имя материала: Математика в экономике

Автор: Солодовников А.С.

§ 7.3. строение множества оптимальных решений

 

Напомним, что допустимое множество X в задаче линейного программирования задается системой линейных ограничений в R" и поэтому является выпуклой многогранной областью. Напомним также, что ограниченная выпуклая многогранная область называется выпуклым многогранником. Справедлива следующая теорема о строении выпуклых многогранников.

Теорема 1. Выпуклый многогранник совпадает с выпуклой оболочкой своих угловых точек.

Доказательство. Применим тот же прием, который мы неоднократно уже использовали в § 7.2. Пусть к — число неравенств в системе линейных ограничений S, задающих выпуклый многогранник X. Докажем теорему 1 последовательно в случаях к = 0, 1, 2 и т. д.

Случай к = 0. Если X содержит две различные точки, то по лемме 1 из § 7.2 А' содержит и всю соединяющую их прямую. Это противоречит ограниченности X Поэтому X состоит из одной точки. Выпуклая оболочка одной точки совпадает с этой точкой. В случае к = 0 теорема доказана.

Случай к= Пусть А и В — различные точки X. Напомним, что 1АВ — это луч с началом в А, проходящий через В. Так как имеется не более одной грани, то один из лучей 1АВ или 1ВА не пересекает грани множества X. Но тот луч, который не пересекает грани, целиком содержится в X, что противоречит ограниченности X. Следовательно, и в случае к = 1 множество X состоит из одной точки.

Случай к > 2. Пусть М Є X—произвольная точка. Мы должны доказать, нто М является выпуклой комбинацией угловых точек X. Если М — угловая точка множества X, то это утверждение очевидно. Если М — неугловая точка, то найдется отрезок АВ, содержащийся в X, для которого М — внутренняя точка. Продолжим отрезок А В в обе стороны до пересечения с гранями множества X. Пусть С — пересечение прямой А В с гранью Fx, D — пересечение прямой АВ с гранью F2. Пусть Vv V2,Vt — угловые точки Гранив,; И7,, Wv .... И^ —угловые точки грани ¥г. Так как множества/^, nF2 ограничены и задаются меньшим числом неравенств, чем X, то для них тео-рема доказана. Поэтому для подходящих неотрицательных чисел С,, с2,сГ с единичной суммой имеем:С=с, К, + c2V2 + ■■• + ctVt. Аналогично для подходящих неотрицательных чисел d,, d2, ds с единичной суммой имеем:/) = dxW] + d2W2 + ... + dsWs. Далее, точка М принадлежит отрезку CD. поэтому для некоторых а>0иР=1-а>0 имеем:Л/ = аС + р/). Отсюда получаем, что

М = ас, К, + ас2У2 + ... + acrVr + (Ц W, + fta2W2 + ... + $dsWr

Все числа а с,, а с2,а с,, р dv Р d2    р ds неотрицательны, а их сумма

ас, +ac2 + ... + acr + prfI +pd2 + ... + P4 = = а (с, + с2 + ... + cr) + Р Ц + d2 + ... + ds) = а + р = I.

Следовательно, точка М — выпуклая комбинация точек К,, У2,Уг Wx, W2,W Эти точки являются угловыми точками граней, а по лемме 7 из § 7.2 они являются и угловыми точками X. Теорема доказана.

Теорема 2. Если в задаче линейного программирования допустимое множество X непусто и ограничено, то задача разрешима, а множество всех оптимальных решений X * является вътуклой оболочкой оптимальных угловых точек X.

Доказательство. Так как X ограничено, то найдется такое число М, что для любой точки х Є X все ее координаты по модулю не превосходят М: х{ < М, х2 < М,.... рс„| < М. ПустьДх) = (с, х) — линейная целевая функция; С = max {|с,|, |с2|,|с„|} — наибольшее значение модуля ее коэффициентов. Имеем неравенство:

= |с,х, + с2х2 + ... + с^п < сх\х{ + |с2|-|*2| +    + |с„ІКІ < п-СМ.

Следовательно./^) ограничена и сверху, и снизу на X. По теореме I из § 7.2 имеется хотя бы одно оптимальное решение, т. е. задача

145 разрешима. Пусть А'* — множество всех оптимальных решений. Так как X* подмножество X, то X* — ограниченное множество. По теореме 1 множество X* совпадает с выпуклой оболочкой своих угловых точек. Угловые точки X* по лемме 6 из § 7.2 являются и угловыми точками множества X. Теорема доказана.

Следующий пример показывает, что утверждение теоремы 2, по крайней мере в некоторых случаях, остается в силе и при неограниченном допустимом множестве.

Рассмотрим стандартную задачу о диете. Пусть имеются три продукта: Л|, Л2, Л3, содержащие три питательных вещества: А, В и С.

Система ограничений записывается так:

0|дг| + а    + аъхъ ^ а, + bjX2 + 63X3 > Ъ, СХ + С+ с3х3 > с,

хх>0,х2>0,х3>0.

где а, Ь, с — минимальные нормы веществ А, В и С; jc,, jc2, jc3 — количество продуктов 77,, Пг, Л3; а-, bt, с, (/ = 1, 2, 3) — содержание питательных веществ в единице продукта Я,. Минимизируем целевую функцию/(л:)-РХ{ +Р2Х2+РуХг, где Р,рг,ръ — цены продуктов. Далее считаем, что рх > 0,р2 > 0,р3 > 0. Из условия положительности цен следует, что в допустимых точках f(x) > 0. Следовательно, J{x) ограничена снизу на допустимом множестве. В то же время само допустимое множество не ограничено. Это следует из того, что Х, х2 и х3 можно неограниченно увеличивать, не нарушая ограничений задачи. Несмотря на это, по теореме I из § 7.2 минимальное значение /mjn достигается в некоторой допустимой точке.

Каждое оптимальное решение х* удовлетворяет системе ограничений:

, Plxl+p2x2 + p3x2>fmin, х, >0, x2>0,x3>0,

из которой вытекают следующие неравенства:

0<лг, <^,0<х,<^,0<х,<^.

Р         2    Р2  3 РЪ

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

 

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