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

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

§ 7.2. геометрия задачи линейного программирования

 

Рассмотрим задачу линейного программирования по отысканию максимума (или минимума) линейной функцииДх) = (с, х) на допустимом множестве X, заданном с помощью системы S линейных ограничений (уравнений или нестрогих неравенств). Напомним, что множество X, заданное с помощью системы линейных ограничений

в пространстве R", называется выпуклой многогранной областью

в R". Таким образом, геометрический смысл задачи линейного программирования состоит в отыскании максимума (минимума) заданной линейной функции f(x) на заданном выпуклом множестве

X С R".

Скажем, что целевая функция в задаче линейного программирования ограничена, если в задаче на максимум целевая функция ограничена на допустимом множестве сверху, а в задаче на минимум — снизу.

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

Доказательство теоремы 1 будет дано ниже.

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

внутренней точкой ни для какого отрезка АВ, целиком содержащегося в X.

Теорема!. Если в задаче линейного программирования fix) —> max(min) при условии х Є X допустимое множество X имеет хотя бы одну угловую точку, а целевая функция/{х) ограничена, то угловая точка X, в которой fix) принимает наибольшее (наименьшее) значение среди всех угловых точек X, является оптимальным решением данной задачи.

Доказательство теоремы 2 также будет дано ниже.

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

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

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

В §§ 8.1-8.3 мы ознакомимся с так называемым симплекс-методом, представляющим собой целенаправленную процедуру перебора вершин.

Для доказательства теорем 1 и 2 потребуется ряд вспомогательных лемм. Оставшуюся часть параграфа, до теоремы 2', при первом чтении можно пропустить.

Лемма 1. Если множество X, заданное системой линейных уравнений, содержит две различные точки А и В, то X содержит и всю прямую А В.

Доказательство. Предположим, что А1 задано системой двух линейных уравнений (число уравнений для доказательства несущественно)

(Р,х)=р0, (q, х) = <70.

Всякая точка прямой А В имеет вид

x(t) = A + tAB=(i-t)A + tB,

где t — произвольное число.

Докажем, что х(0 Є X при любом t. Действительно,

(р. *(')) = (р. (1-ОЛ + 'В) = (1-0(р, А) + lip. В) = (1-ОРо + 'Ра =Ро

Точно так же доказывается, что для точки x(t) выполняется каждое уравнение системы, задающей множество X. Следовательно, произвольная точка х прямой А В принадлежит X.

Лемма 2. Пусть fix) — линейная функция, X — множество, заданное системой линейных уравнений. Ecnafix) ф const на X, то fix) принимает на X все значения от -со до + °о.

Доказательство. Пусть А и В — такие точки X, что fiA) *fiB). Рассмотрим_прямую, соединяющую А и В. Всякая ее точка_имеет вид x(t) = A + tAB,t ЄЛ. Пусть f{x) = (с, х). Тогда fix(t)) = (с,А) + 1(с,АВ). Так как fiA)* fiB), то (с,АВ)*0. Следовательно, на прямой АВ функция f(x) принимает любое значение от - аз до + со. По лемме 1 прямая А В целиком содержится в X, поэтому если fix) * const на X, то fix) принимает на X все значения

от - со до + со.

Пусть снова А и В — две различные точки. Обозначим 1АВ луч с началом в А, проходящий через В. Другими словами, 1АВ — это множество точек x(t) вида x(t) = А + tA В, где / £ 0.

Лемма 3. Если линейная функция fix) = (с, х) принимает в точке В большее значение,чем в точке А, то fix) не ограничена сверху на луче 1АВ.

Доказательство. Рассмотрим линейную функцию от /: fix(t)) = = (с, A) + t(c,AB). В зависимости от знака числа (с,АВ) эта функция либо возрастает, либо убывает, либо принимает постоянное значение при любых t Є R. Так как хф) = А, х() = В nfiB) >fiA), то (с, АВ) >0. Следовательно, при увеличении t от - аз до + со функция fix(t)) неограниченно возрастает. Таким образом, fix) не ограничена сверху на луче 1АВ.

Лемма 4. Пусть fix) = (р,х)+р0 — линейная функция и fiA) > О, fiB) < 0 для некоторых точек А и В. Тогда на отрезке А В найдется точка С, для которой ДС) = 0.

Доказательство. Всякая точка отрезка АВ имеет вид x(t) =

             /Г4Л

= А + tA В = (-t)A + tB , где 0 < / ^ 1. Пусть с = д^.дду Так как с Є [0, 1 ], то С = х(с) — точка отрезка АВ. Имеем:

fiQ = (р,(1 - с)А + сВ) + р0=( - сХр, А) + с(р, В) + Ро =

= (1 - с) [(р, А) + р0] + с [<р, В) + р0] = (1 - сЖА) + cfiB) =

-AB)fiA)    fiA) fiB) ~ fiA) -fiB) + fiA) -fiB)

Пусть множество ЛГзадано системой линейных ограничений S. Назовем гранью множества X всякое непустое множество F, заданное системой линейных ограничений S,, которая получена из 5 заменой знака неравенства на знак равенства в одном из неравенств системы S.

Лемма 5 Пусть множество X задано системой линейных ограничений S; А и В — различные точки из X. Тогда либо луч 1АВ целиком содержится в X, либо луч 1АВ пересекает некоторую грань множества X в точке, отличной от А.

Доказательство. Будем, для определенности, считать, что все неравенства системы S имеют вид ft(x) > 0. Если для некоторого і неравенство ft(x) > 0 обращается в точке В в равенство, то точка В и есть точка пересечения луча 1АВ с ;'-й гранью множества X. В этом случае лемма 5 доказана. Поэтому далее считаем, что для всех неравенств системы 5 выполняется строгое неравенство^!5) > 0. Пусть fk(x) = 0 — какое-либо уравнение системы S. Так как fk(A) = 0 и /к(В) = 0, то по лемме 1 и вся прямая А В содержится в гиперплоскости, заданной уравнением fk(x) = 0. Следовательно, для любой точки С луча 1АВ все уравнения системы S выполняются. Пусть некоторая точка С луча 1АВ не принадлежит множеству X. Тогда в точке С нарушается одно или несколько неравенств системы S, т. е. для некоторого номера і mtesMffjC) < 0. Для каждого такого/по лемме 4 на отрезке ВС найдется такая точка Qj = В + q( ВС, что /<б;) = 0. Для каждого нарушенного неравенства функция f{x) убывает на отрезке ВС, поэтому если qm — это минимальное среди всех чисел qjt то f{ (£? ) > 0. Следовательно, Qm принадлежит множеству X. Более того, Qm принадлежит «7-й грани множества X, так как ft (qm) = 0. Поскольку/Jx) убывает на луче lAB, to/JA) >/т(в) > 0-с ДРУГОЙ стороны,/т (£>т) = 0, поэтому А * Qm.

Доказательство теоремы 1. Всякая задача линейного программирования на минимум сводится к задаче на максимум, поэтому достаточно рассмотреть только случай максимума.

Итак, пусть X — непустое допустимое множество, заданное системой S линейных ограничений;fix) — линейная функция, ограниченная сверху на X. Предположим, что S содержит только уравнения. Тогда по лемме 2 fix) = const и всякая точка X будет оптимальным решением. Поэтому для X, заданного одними уравнениями, теорема 1 доказана.

Предположим, что система S содержит какое-то количество уравнений и одно неравенство. Пусть А & X — произвольная точка. Если А — точка максимума, то доказывать нечего. Если А не является точкой максимума, то найдется такая точка В, что fiB) >fiA). По лемме 2 fix) не ограничена сверху на луче 1АВ. Следовательно, луч 1АВ не может целиком содержаться в X. По лемме 5 луч 1АВ пересекает какую-то грань F множества X. Так как система S содержит только одно неравенство, то F — единственная грань X и, кроме того, система линейных ограничений, задающая грань F, неравенств не содержит. Поэтому для функции Л*) на F теорема 1 уже доказана. Пусть А — точка максимумаДх) на F. Докажем, что А — точка максимумаДх) на всем X. Действительно, если существует такая точка В £ X, что fiB) >fiA), то fix) не ограничена сверху на луче 1АВ, и 1АВ должен пересекать какую-то грань множества Хв точке С, отличной от А. Так как F— единственная грань X, то С Є F, что противоречит тому, что А — точка максимума fix) на F и fix) возрастает на луче 1АВ. Итак, А — точка максимума на X. Теорема I в случае одного неравенства доказана.

Предположим, что система ограничений S содержит два неравенства (и сколько-то равенств). Если на всем X функцияДх) принимает постоянное значение, то для X теорема доказана. Если это не так, то, как и в случае одного неравенства, доказывается, что X имеет хотя бы одну грань. Так как X задается двумя неравенствами, то грани X задаются одним неравенством (каждая грань — своим). Поэтому для граней ^теорема у же доказана. Пусть F— грань, на которой достигается наибольшее значение fix) на гранях А". Пусть А Є F — точка максимума fix) на F. Докажем, что А — точка максимума на X. Предположим противное: существует точка В Є X, fiB) >fiA). Тогда луч 1АВ должен пересечь какую-то грань F' множества X в точке С* А. Так как функцияДх) возрастает на луче lAB, wfiC) >fiA). Это противоречит тому, что А — точка максимума fix) на гранях множества X. Следовательно, А — точка максимума на всем X. Теорема 1 доказана в случае двух неравенств. Если среди линейных ограничений, задающих множество X, три или большее количество неравенств, то теорема 1 доказывается аналогичным образом. Итак, теорема 1 доказана полностью.

Пусть выпуклая многогранная область X задается системой линейных ограничений 5. Рассмотрим задачу линейного программирования^*) —► max при условии х Є X. Пусть X' — множество всех оптимальных решений данной задачи. Если задача разрешима, то множество X* непусто и fiX') = /тях. Пусть 5* — система линейных ограничений, полученная из S добавлением уравнения fix) =/max. Множество X' задается системой S* и поэтому является выпуклой многогранной областью. Ясно, что и в случае разрешимой задачи на минимум X* также является выпуклой многогранной областью.

Лемма 6. Пусть X' — множество всех оптимальных решений задачи линейного программирования fix) = (с, х) -* max при условии х Е X. Тогда всякая угловая точка X* является угловой точкой допустимого множества X.

Доказательство. Предположим противное: х° — угловая точка X' их0 — неугловая точка X. Тогда найдутся такие точки А, В Є X, что х° — внутренняя точка отрезка А В. Так как х° — угловая точка X*, то А и В не могут одновременно принадлежать X*. Следовательно, из двух неравенств ДА) <,/тіХнДВ) </таххотя бы одно должно быть строгим. Следовательно, для любого числа а из интервала (0; 1) выполняется неравенство

аЛА) + (1-аЖВ)</тлх.

С другой стороны, хй = аА + (1 - а)В для некоторого а Є (0; 1), так как х° — внутренняя точка отрезка А В. Поэтому

/■пах =Л*°) = (с, х°) = (с, а А + (I - а) В) =

= а (с, А) + (1 - а)(с, В) = а ДА) + (I - а.)ДЯ),

что противоречит полученному выше неравенству. Следовательно, всякая угловая точка множества X * является одновременно и угловой точкой X.

Лемма 7. Пусть F — грань выпуклой многогранной области X. Тогда всякая угловая точка грани Fявляется угловой точкой множества X.

Доказательство. Пусть 5 — система линейных ограничений, задающих множество X. Не уменьшая общности, считаем, что одно из ограничений системы S имеет видДдг) < Ь, а грань Fзадается системой St, полученной из S заменой неравенства Дх) < Ь на уравнение fix) = b. Грань F является множеством оптимальных решений задачи линейного программирования: J[x) -* max при условии хЄ X Поэтому лемма 7 следует из леммы 6.

Лемма 8. Если множество X, заданное системой линейных ограничений S, содержит точку А + tV при любом t Є (0; I ], то А Є X.

Доказательство. Можно считать, что Xзадано системой Sвида

<р,х) + р0*0

(g, x) + gQ>0.

Рассмотрим первое неравенство. Так как оно выполняется при х = А + / К со сколь угодно малыми положительными /, то (р, А) + р0 > 0. Аналогично

доказывается, что точка А удовлетворяет и другим неравенствам системы S.

Лемма 9. Если множество X, заданное системой линейных ограничений, содержит целиком некоторую прямую L, то вместе со всякой точкой А Є X множество X содержит и прямую, параллельную L, проходящую через точку А.

Доказательство. Представим прямую L в виде L= { С, = В + tW, t Є R), где В — точка на прямой L, W — направляющий вектор L. Так как X— выпуклое множество, то при любом t отрезок АС, содержится целиком в X. Для любого / > 1 точка D, = (1 - Г )А + Г С, принадлежит отрезку А С,.

Следовательно, Z), Є X при tZl. Далее, Z), = (1 - г')Л + г'в + W =

= A + W+r[V, где V = В-А. Так как /"'принимает любое значение из полуинтервала (0; 1], то по лемме 8 A + W Є X. Для любого числа 5*0 вектор sW также является направляющим вектором прямой L, поэтому А + sW&X при любом s. Другими словами, множество X целиком содержит прямую {Ах = А + sW,s& R }, проходящую через точку А.

 

Лемма 10. Если непустое множество X, заданное системой линейных ограничений S, не имеет угловых точек, то X содержит целиком некоторую прямую.

Доказательство. Пусть к — число неравенств в S. Докажем лемму 10 последовательно для к = 0, 1, 2 и т. д.

Случай к = 0. Если Х= (А) состоит из одной точки А, то А—угловая точка X, и доказывать нечего. Пусть А и В — две различные точки из X. Тогда по лемме 1 ^содержит прямую Л5.

Случай к - 1. Если X состоит из одной точки, то опять доказывать нечего. Пусть А и В — две различные точки. Если лучи 1АВ и 1ВА целиком содержатся в А то в А* содержится и их объединение — прямая А В. В этом случае все доказано. Поэтому далее считаем, что либо луч 1АВ, либо луч 1ВА не содержится теликом в X. По лемме 5 луч 1АВ (или 1ВА) пересекает какую-то грань F множества X. По лемме 7 всякая угловая точка F является угловой точкой X. Поэтому F, так же как и X, не имеет угловых точек. Кроме того, F задана меньшим числом неравенств, чем X. Следовательно, для клемма 10 уже доказана и ^"содержит некоторую прямую L. Так как F С X, то и L С X.

Случай к = 2 сводится к случаю к = 1. Случай к = 3 сводится к случаю к = 2 и т. д.

Доказательство теоремы 2. По теореме 1 множество всех оптимальных решений X' непусто. Предположим, что X* не имеет угловых точек. Тогда по лемме 10 X* содержит целиком некоторую прямую L. Так как X' С X, то и L С X. По лемме 9 множество X в этом случае вместе со всякой точкой А Є X содержит и прямую, содержащую А. Следовательно, X не имеет угловых точек, что противоречит условию теоремы 2. Итак, X имеет хотя бы одну угловую точку х°. Пусть А — угловая точка X, в которой целевая функция принимает наибольшее (наименьшее) значение среди всех угловых точек X. По лемме 6 х° также является угловой точкой X. Следовательно,^) =Д*°) и А — оптимальное решение. Теорема 2 доказана.

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

Теорема 2'. Если в задаче линейного программирования все переменные имеют условие неотрицательности и целевая функция f(x) ограничена на допустимом множестве X, то угловая точка X, в которой f(x) принимает наибольшее (наименьшее) значение среди всех угловых точек X, является оптимальным решением данной задачи.

 

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