Файл: Иоффе, А. Д. Теория экстремальных задач [учеб. пособие].pdf

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

Комментарий к гл. 5. Различные аксиоматические схемы для экстремальных задач, близких в том или ином отношении к выпук­ лым, разрабатывались Гамкрелидзе [5], [7], [8], Гамкрелидзе и Харатишвили [1]—[3], Нойштадтом [2], Халкиным [4] и др. Теорема 1 из § 5.1 написана под влиянием результатов Халкина. Думается, что эта теорема может оказаться полезной при доказательстве принципа максимума и для более широкого круга задач.

Первый вариант принципа максимума для задач с фазовыми ограничениями был доказан Гамкрелидзе [3]. Теорема 1 § 5.2 была доказана Дубовицким и Милютиным с помощью замены времени. Интересные проблемы возникают в задачах со смешанными ограни­ чениями вида g(x(t), u(t)) — 0 или g(x(t), u(t)) ^ 0 . Первые ре­ зультаты для таких задач получены Дубовицким и Милютиным [3], [51.

Г л а в а 6

СПЕЦИАЛЬНЫЕ ЗАДАЧИ

§ 6.1. Линейное программирование

Здесь доказываются теорема существования и тео­ рема двойственности для задач линейного программи­ рования.

6.1.1. Существование решений. Рассмотрим задачу линейного программирования:

Символ х ^ у означает, что координаты вектора у не превосходят соответствующих координат вектора х. Мы будем рассматривать пространства R” и Rm только со стандартными базисами. Это позволяет нам отождест­ вить оператор А с его матрицей в этих базисах. Обо­ значим через а\.........ап векторы, стоящие в столбцах

ном пространстве, порожденный конечным множеством точек, замкнут.

Доказательство его замкнутости проведем индукцией по числу k. При k = 1 лемма очевидна, ибо тогда К — по­ лупрямая. Допустим, что лемма верна для k = s — 1, и предположим, что k = s. Рассмотрим два случая.

пример, —zs, не принадлежит конусу К. Обозначим че­ рез К1 конус, порожденный векторами zh ... , 2s_t. По индуктивному предположению конус Кi замкнут. С дру­

Остается допустить, что имеет место случай б). Тогда

нус К порожден конечным множеством векторов. В са­ мом деле, если й[, ... , ап суть (т + ] ) -мерные векторы вида (с*, а,), где с\— /-я компонента вектора с, at — век­ тор, координаты которого суть элементы i-ro столбца матрицы А, а е0= (1, 0.........0), . . . , ет= (0, ... , 0, 1) —

стандартный базис в Rm+1, то, как легко видеть, конус,

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

S (z) = inf (a е R |(a, z) e /(} .

отличающейся от задачи (1) тем, что вектор b заменен некоторым вектором г. Задачу (3) мы называем воз­ мущением задачи (1). Найдем функцию, сопряженную с S ( z ). (Дальнейшие выкладки в более общей ситуации

270 ГЛ. 6. СПЕЦИАЛЬНЫЕ ЗАДАЧИ

встретятся в § 7.3.) Имеем

S* (г/) = sup ((г/ \г) — S{z)) =

Z

Задача (4) называется двойственной с задачей (1). Нетрудно видеть, что она имеет, по существу, ту же форму, что и задача (1). Поэтому двойственной с за­ дачей (4) будет снова задача (1), и имеет смысл гово­ рить о паре двойственных задач линейного программи­ рования. Читатель без труда обнаружит те формальные правила, с помощью которых строится двойственная задача.

Т е о р е м а 2 (теорема двойственности). Для пары двойственных задач линейного программирования спра­ ведлива следующая альтернатива-, либо значения задач конечны и равны и в обеих задачах существует реше­ ние, либо в одной из задач множество допустимых эле­ ментов пусто, а в другой или множество допустимых элементов пусто, или значение задачи бесконечно.