Задача на условный экстремум 61 нелинейное программирование 72 метод Ньютона в нелинейном программировании 88 выпуклое программирование 96
 Скачать 0.96 Mb.
|
|
? m , µ ? 1 , . . . , µ ? r ) ? L(x ? , ? ? 1 , . . . , ? ? m , µ ? 1 , . . . , µ ? r )+ +h?L(x ? , ? ? 1 , . . . , ? ? m , µ ? 1 , . . . , µ ? r ), x ? x ? i. С другой стороны, несложно заметить, что, что если x ? точка минимума в задаче (18), то линейная независимость векторов (19) представляет собой первое условие регулярности для этой задачи (см. џ2). Поэтому необходимость условий теоремы 12 непосредственно следует из теоремы 4. ¤ џ4. Выпуклое программирование 109 Замечание. Теорема 12 представляет собой классиче- ский вариант теоремы Куна Таккера для классической зада- чи выпуклого программирования (18). Ее формулировка столь проста и элегантна, что, как тонко заметил Л. Янг, ее в скором будущем наверняка будут изучать уже в средней школе (см. [28]). Единственый недостаток этой теоремы необходимость проверки линейной независимости векторов (19) в точке ми- нимума, заранее неизвестной. Это, впрочем, недостаток всех теорем, использующих какие-либо условия регулярности (см. теоремы 2, 4 и 5). Упражнения. (1) Покажите, что выпуклая функция f : R n ? R непрерывна в каждой точке множества D(f) 0 (2) Покажите, что пересечение конечного числа выпуклых множеств само есть выпуклое множество. (3) Пусть Q ? R n выпуклое множество и пусть f : R n ? R выпуклая функция. Покажите, что функция f выпукла на множестве Q. (4) Докажите, что если множество Q ? = {x ? R n : f (x) ? ?} непусто и ограничено для некоторого действительного числа ? с выпуклой функцией f : R n ? R и Q ? ? D(f ) 0 , то множество Q ? ограничено при всех значениях ? < ?. (5) Пользуясь теоремой Куна Таккера, найдите решения следующих задач: N X i=1 (x i ) 2 ? min, N X i=1 x i ? 1, (A) hQx, xi/2 ? hp, xi ? min, Ax ? b, (B) где Q симметрическая положительно определенная мат- рица. (6) Напишите задачи, двойственные к задачам hc, xi ? min, |x| ? 1 и hc, xi ? min, |x| 2 ? 1. (7) Покажите, что прямые задачи в упражнении 6 эквива- лентны, хотя задачи, двойственные к ним, различны. 110 Гл. 2. Математическое программирование (8) Пусть все функции f, h 1 , . . . , h r выпуклы, а множество Q выпукло и замкнуто. Предположим, что для множества S , S = {x ? Q : h i (x) ? 0, i = 1, . . . , r}, выполнены условия S ? D(f ) 0 , S ? D(h 1 ) 0 , . . . , S ? D(h r ) 0 и множество R = {x ? S : f (x) ? ?} непусто и ограничено для некоторого значения ?. Пока- жите, что в этом случае задача (3) имеет по крайней мере одно решение. Указание: Используйте упражнения 1 и 4. џ5. Линейное программирование Задачи линейного программирования возникли достаточ- но давно и в первую очередь были связаны с задачами опти- мального планирования в экономике, в частности, оптималь- ного производственного планирования. Оказалось, что задачи линейного программирования представляют достаточно боль- шой интерес сами по себе и, более того, имеют огромное прак- тическое значение в экономических, технических и других прикладных проблемах. Математическая теория задач линейного программирова- ния проста, красива и в настоящее время, видимо, может считаться полностью завершенной. Базируется эта теория на основных результатах теории выпуклого программирования и, вместе с тем, на некоторых важных результатах выпуклого анализа. Ниже, собственно, приводятся основы теории линей- ного программирования. Общие положения. Задача линейного программирова- ния является частным случаем задачи выпуклого программи- рования, когда минимизируемая функция и ограничения ли- нейны. Другими словами, задача линейного программирова- ния заключается в минимизации функции f (x) = hc, xi џ5. Линейное программирование 111 при ограничениях ha i , xi ? b i , i = 1, . . . , m. Принимая очевидные обозначения, перепишем эту задачу в следующем эквивалентном виде: hc, xi ? min, Ax ? b, (1) где x ? R n , A прямоугольная (mЧn)-матрица, c и b вектора в пространствах R n и R m соответственно. Во многих практических ситуациях на координаты векто- ра x накладывается условие неотрицательности. При этом ча- сто оказывается удобно не вводить эти ограничения в матрицу A , а выделять их отдельно. В этом случае задача линейного программирования записывается в виде hc, xi ? min, Ax ? b, x ? 0. (2) Линейная функция скалярного переменного, конечно, не достигает на действительной прямой R ни максимума, ни ми- нимума. Ситуация, однако, в корне меняется, если искать ми- нимум (или максимум) такой функции на отрезке: решение в этом случае обязательно лежит в одной из крайних точек от- резка. Это обстоятельство оказывается существенно важным и в многомерном случае, поскольку приводит к эффективной процедуре нахождения решения задачи (1). Определим множество Q ? R n как множество решений системы линейных неравенств ha i , xi ? b i , i = 1, . . . , m, (3) т.е. Q = {x ? R n : ha i , xi ? b i , i = 1, . . . , m, }. Определенное таким способом множество называется много- гранным множеством или симплексом. При этом соотноше- ния (3) задают грани множества Q. Определим теперь верши- ну (или крайнюю точку) множества Q. Точка x называется крайней точкой многогранного мно- жества Q ? R n , если она не является внутренней точкой 112 Гл. 2. Математическое программирование какого-либо отрезка, целиком лежащего внутри Q. Оказыва- ется, что крайние точки многогранных множеств можно легко описать алгебраически. Предложение 1. Крайними точками любого многогран- ного множества Q являются те и только те точки, для которых имеется ровно n линейно независимых активных ограничений. Доказательство. Пусть x 0 некоторая точка множе- ства Q. Обозначим через I 0 множество активных ограни- чений в этой точке: I 0 = {i = 1, . . . , m : ha i , xi = b i }. Если среди векторов a i , где i ? I 0 , менее n линейно независи- мых, то система однородных уравнений ha i , si = 0, i ? I 0 имеет нетривиальное решение s 0 . Тогда вектора x 1 = x 0 + ?s 0 и x 2 = x 0 ? ?s 0 при всех достаточно малых значениях ? > 0 также принадле- жат Q. Следовательно, точка x 0 = x 1 + x 2 2 не может быть крайней точкой множества Q. Предположим теперь, что среди векторов a i , где i ? I 0 , имеется n линейно независимых векторов. Для некоторых век- торов x 1 ? Q и x 2 ? Q обозначим через x 0 вектор x 0 = x 1 + x 2 2 . Тогда при i ? I 0 b i = ha i , x 0 i = ha i , x 1 i + ha i , x 2 i 2 ? b i + b i 2 = b i . Поэтому ha i , x 1 i = ha i , x 2 i = b i . џ5. Линейное программирование 113 Но система ha i , xi = b i , i ? I 0 не может иметь двух различных решений, поскольку ее ранг равен n. Последнее означает, что x 1 = x 2 , т.е. x 0 крайняя точка множества Q. ¤ Из предложения 1 непосредственно следует, что число крайних точек многогранного множества конечно. С геомет- рической точки зрения представляется уместным называть крайние точки вершинами многогранного множества. Тогда предложение 1 показывает, что вершина многогранного мно- жества есть 0-мерная грань этого множества и число таких вершин конечно. При этом следует иметь ввиду, что много- гранное множество может вообще не иметь вершин. Существо- вание же вершин оказывается весьма важным для задачи ли- нейного программирования, поскольку имеет место следующее предложение, приводимое здесь без доказательства. 6 Предложение 2. Если допустимое многогранное мно- жество Q не содержит прямых, а решение задачи (1) суще- ствует, то среди ее решений найдется вершина множества Q . Более того, если решение задачи (1) единственно, то оно достигается именно в вершине. Условия экстремума. Предложение 2 хотя и указыва- ет на то, где следует искать решение задачи линейного про- граммирования, но, очевидно, не дает непосредственного кон- структивного способа поиска решения. Последнее обстоятель- ство оказывается особенно важным, поскольку даже в случае задач небольшой размерности число вершин может оказаться огромным и полный их перебор становится делом совершенно нереальным. Как уже отмечалось ранее, задача (1) (или (2)) является частным случаем задачи выпуклого программирования. При 6 См., например, [16]. 114 Гл. 2. Математическое программирование этом целевая функция и ограничения определены и диффе- ренцируемы в каждой точке пространства R n . Поэтому пред- ставляется уместным провести анализ этой задачи на экстре- мум с помощью результатов, приведенных ранее в џ4. Для это- го, прежде всего, заметим, что ограничения в этой задаче име- ют специальный вид, позволяющий отказаться от требования выполнения условия Слейтера. Поэтому из теоремы 9 немед- ленно вытекает следующее условие минимума в задаче (1). Теорема 13. Для того, чтобы точка x ? ? Q была ре- шением задачи (1) необходимо и достаточно существование множителей Лагранжа µ ? ? R m + , таких, что hµ ? , Ax ? ? bi = 0 и c + A T µ ? = 0, где T операция транспонирования. По аналогии с теоремами 9 и 10 из теоремы 13 следует необходимое и достаточное условие экстремума в терминах седловой точки. Теорема 14. Для того, чтобы точка x ? ? Q была реше- нием задачи (1) необходимо и достаточно существование та- кого вектора µ ? ? R m + , что для всех значений (x, µ) ? QЧR m + выполнены неравенства L(x, µ ? ) ? L(x ? , µ ? ) ? L(x ? , µ), где L(x, µ) = hc, xi + hµ, Ax ? bi. Продолжая применять результаты џ4 к задаче линейного программирования, выпишем задачу, двойственную к задаче (1), и сформулируем соответствующую теорему двойственно- сти. Для этого, прежде всего, положим ?(µ) = inf x?R n L(x, µ) = inf x?R n (hc + A T µ, xi ? hb, µi). Тогда имеем ?(µ) = Ѕ ??, hc + A T µ, xi 6= 0, ?hb, µi, hc + A T µ, xi = 0. џ5. Линейное программирование 115 Таким образом, задача, двойственная к задаче (1), пред- ставляет собой задачу о максимизации функции F (µ) = ?hb, µi при ограничениях hc + A T µ, xi = 0 и µ ? 0, или, что эквивалентно, задачу hb, µi ? min, hc + A T µ, xi = 0, µ ? 0. (4) Другими словами, задача (4) представляет собой специальный вариант задачи линейного программирования, который всегда может быть сведен к задаче (1) и обратно. При этом из теоремы 11 немедленно вытекает следующая Теорема 15. Решения (x ? , µ ? ) пары двойственных задач (1) и (4) существуют или не существуют одновременно. При этом для всех допустимых значений x и µ справедливо нера- венство hc, xi ? hb, µi, (5) причем равенство в (5) имеет место тогда и только тогда, когда x = x ? и µ = µ ? Каноническая форма задачи линейного програм- мирования. Легко видеть, что сформулированные выше тео- ремы 13 и 14 не дают ничего принципиально нового для поиска решения задачи (1). Вместе с тем, теорема 15 и предложения 1 и 2 наводят на мысль о целесообразности изучения следующей новой задачи hc, xi ? min, Ax = b, x ? 0, (6) весьма близкой к задаче (2). Задача (6) известна как каноническая форма задачи ли- нейного программирования. Она всегда может быть получена 116 Гл. 2. Математическое программирование из задачи (2) и, обратно, задача (6) всегда может быть сведена к задаче (2). В самом деле, в задаче (2) введем новые вспомогательные переменные y ? R m + и запишем hc, xi ? min, Ax + y = b, x ? 0, y ? 0. (7) Тогда, полагая z = (x, y), g = (c, 0) и H = (A | E), где E единичная (m Ч n)-матрица, можем переписать задачу (7) в следующем виде hg, ci ? min, Hz = b, z ? 0, очевидно, совпадающим с (6) с точностью до обозначений. Обратно, перепишем задачу (6) в следующем эквивалнент- ном виде: hc, xi ? min, ha i , xi = b i i = 1, . . . , m, x ? 0. (8) Но так как каждое из равенств ha i , xi = b i эквивалентно, например, двум неравенствам ha i , xi ? b i и ?ha i , xi ? b i . Поэтому задача (8) превращается в задачу hc, xi ? min, ha i , xi ? b i , i = 1, . . . , m, ?ha i , xi ? b i , i = 1, . . . , m, x ? 0, очевидно, представляющую собой задачу вида (2). џ5. Линейное программирование 117 Важность канонической формы задачи линейного про- граммирования трудно переоценить, поскольку именно форма (6) приводит к эффективной вычислительной процедуре ре- шения задачи (2), известной под названием симплекс-метода и состоящей в оптимальном просмотре последовательности вер- шин многогранного множества (см. џ6). Пример 10. В качестве одного из возможных приложе- ний продолжим разбор примера 9. Именно, предположим, что в задаче об оптимальном распределении ресурсов, заключаю- щейся в минимизации функции f (x 1 , . . . , x n ) = f 1 (x 1 ) + · · · + f n (x n ) (9) при ограничениях x 1 + · · · + x n ? 1 = 0 (10) и x i ? 0, i = 1, . . . , n, (11) все функции f i линейны. В этом случае минимум функции (9) достигается в одной из вершин симплекса заданного ограни- чениями (10) и (11). Этих вершин, очевидно, всего n, и они имеют вид {1, 0, . . . , 0}, {0, 1, 0, . . . , 0}, . . . . . . , {0, 0, . . . , 0, 1}. Поэтому достаточно просто найти величину j = arg min 1?j?n f j n (?) и выбрать в качестве решения x ? j = 1 и x ? i = 0 при i 6= j. Таким образом, в случае линейных функций весь ресурс следует сосредоточить на одном объекте, хотя, как известно, нельзя хранить все яйца в одной корзине. Последнее достаточ- но красноречиво говорит о реалистичности некоторых линей- ных моделей экономики. |