9. Определения.

Если v не равно О, то множество точек {х(0) + …v | … принадлежит R} есть прямая, проходящая через точку х(о) в направлении v; {х(о) + …v | … принадлежит R₊} — это луч из х₀ в направлении v.

Точку х называют выпуклой линейной комбинацией или взве­шенным средним точек X1, ..., х(к), если х = сумме а(i)x(i), сумме а(i)=1 и а(i) >либо= 0 для всех i.

Множество всех выпуклых линейных комбинаций векторов х₀ и X1 из R в степени n, называют отрезком с концами х₀ и х1 и обознача­ют [x₀;x1].

Все точки отрезка, кроме его концов, называют внутренними точками отрезка.

Замечание 15. Данное выше определение прямой переносит в R в степени n параметрическое уравнение прямой х(…) = х(о) + …v, известное в R²и R³; когда … пробегает действительную ось, х(…) пробегает прямую. Если зафиксировать x1 не равную х₀ и положить v = x1 — х₀, то получим уравнение прямой, проходящей через точки х₀ и x1: х(…) = х(о) + …(x1 — х(о)) = (1 — …)х(о) + …x1. При … принадлежит [0; 1] это выпуклая линейная комбинация точек х(о) и x1, причем х(0) = х(о) и х(1) = x1. Следовательно, при … принадлежит [0; 1] точка х(…) пробегает отрезок [х₀; x1], а при … принадлежит (0; 1) — его внутренние точки.

Выпуклая линейная комбинация — это коническая линейная комбинация (см. определение на с. 47), сумма коэффициентов которой равна единице. Разделив ненулевую коническую линей­ную комбинацию векторов x1, ..., x_(к) на сумму ее коэффициен­тов, получим, конечно, выпуклую линейную комбинацию тех же векторов.

Определение. Множество M принадлежит R" называется выпуклым, ес­ли любая выпуклая линейная комбинация точек из М принадле­жит этому множеству.

Теорема 14 (свойства вогнутых и выпуклых функций). Пусть М С R" — непустое выпуклое множество, f — функция на М, G — вектор-функция из М в R^m.

1. Вогнутость {выпуклость) G эквивалентна выпуклости (во­гнутости) вектор-функции — G.

2. Если G вогнута (выпукла) на М, то множество М(b) = {х принадлежит М | G(x) >либо= (<либо=) b} выпукло для любого b принадлежит R^m.

3. Если множество М имеет хотя бы одну внутреннюю точку и функция f на нем дважды непрерывно дифференцируема, то для вогнутости (выпуклости) f на М необходимо и достаточно выполнение неравенства………….

4. Если f вогнута (выпукла) на множестве М, то……..

4. Если функции f_lr..., f_mвыпуклы (вогнуты) на М и а принадлежит R в степени m(+), то сумма a(i)f(i)— выпуклая (вогнутая) функция на М.

5. Если функции f1, ..., f_mвыпуклы (вогнуты) на М принадлежит R в степени n, то функция h(x) = max(min) {f(i)(x) | 1 <либо=i <либо= m} выпукла (вогнута) на М

10. Определение. Задачей выпуклого программирования называ­ют задачу минимизации выпуклой функции при ограничениях (2.1.2) — (2.1.3), если функции g(i) линейны для i <либо= m1 и выпуклы для i >m1.

Замечание 20. Если ограничения (2.1.2)-(2.1.3) удовлетво­ряют условиям предшествующего определения, то задача макси­мизации вогнутой функции при этих ограничениях эквивалент­на задаче выпуклого программирования по замечанию 19 (с. 88). Поэтому задачу максимизации вогнутой функции при линей­ных ограничениях-равенствах и заданных выпуклыми функция­ми ограничениях-неравенствах тоже называют задачей выпукло­го программирования. Именно такой вариант задачи выпуклого программирования обычно возникает при формализации эконо­мических задач.

Опираясь на предыдущее замечание, будем записывать задачу выпуклого программирования следующим образом:……………..

где функция f вогнутая, а функции g(i) выпуклые.

Свойства задачи выпуклого программирования

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

Доказательство. Пусть X — множество допустимых реше­ний задачи (3.3.1) - (3.3.3), а Х1 и Х₂— множества решений системы уравнений (3.3.2) и системы неравенств (3.3.3) соответ­ственно. Тогда X = Х1 пересекает Х₂. Но Х1 — многогранное множество, выпуклое по утверждению 6 (с. 87), а Х₂выпукло по замеча­нию 16 на с. 84 и утверждению 2 теоремы 14. Следовательно, мно­жество X выпукло по утверждению 5.

Утверждение 8. Если переменная Xj на множестве X допусти­мых решений задачи выпуклого программирования принимает значения а и b (а <b), то она принимает на этом множестве лю­бое значение х принадлежит [а; b].

Теорема 19 ([19, с. 131, теорема 2.2]).

Если в регулярной точке задачи (З.ЗЛ) -(3.3.3) функции f и gi для всех i дифференцируемы, то эта точка является оптималь­ным решением задачи.

11. Условия регулярности для задачи нелинейного программиро­вания общего вида (самое простое, которое сформулировано в тео­реме 6 на с. 46, и другие, см. [1, §5.2]) неудобны тем, что для проверки регулярности подозрительной точки нужно ее снача­ла найти. Однако для задач выпуклого программирования суще­ствуют условия регулярности, проверяемые до решения задачи.

Теорема 20 (условия регулярности в выпуклом программиро­вании). Пусть х* —локальное решение задачи (3.3.1) -(3.3.3), функция f дифференцируема в точке х* и выполнено хотя бы од­но из следующих условий:

1. функции gi дифференцируемы в точке х* и существует до­пустимая точка х такая, что g(i)(x) < bi для всех i >m1;

2. все функции gi линейны. Тогда х* —регулярная точка задачи.

Эта теорема является следствием утверждений 2 и 3 теоре­мы 2.3 из [19, с. 137]. Доказательство не использует вогнутость функции /, т. е. теорема справедлива для любой ЦФ, дифферен­цируемой в точке х*.

Ясно, что условия регулярности, сформулированные в теоре­ме 20, можно проверить, не вычисляя точку х*. Основное содер­жание первого из них — условие Слеитера: должно существовать допустимое решение, в котором ни одно ограничение-неравенс­тво (включая требования неотрицательности переменных, если в задаче есть такие ограничения) не активно. Условие Слеитера — самый употребительный признак регулярности задачи выпук­лого программирования.

12. Теорема 21 (дифференциальная форма теоремы Куна-Такке-ра). Пусть функция f дифференцируема в допустимой точке х* задачи (3.3.1) -(3.3.3) и выполнено одно из условий регулярно­сти, указанных теоремой 20. Тогда х* является решением зада­чи, если и только если существует вектор (множителей Лагран-жа) у*, удовлетворяющий условиям (2.4.5), (2.4.2), (2.4.3).

Таким образом, условия Куна-Таккера дают необходимый и достаточный признак оптимальности для регулярной (удовлетво­ряющей условию регулярности) задачи выпуклого программи­рования. Если в задаче выпуклого программирования на пере­менную Xj наложено прямое ограничение (это часто встречает­ся в экономических приложениях), то связанные с этой перемен­ной условия теоремы Куна—Таккера принимают вид (2.4.19) при 2/о = 1 (^см* замечание 13 на с. 52). В частности, если некоторые переменные ограничены по знаку, теорема Куна-Таккера моди­фицируется следующим образом.

Теорема 22 (следствие теоремы 2.4 из [19, с. 139]). Предполо­жим, что функция f дифференцируема в допустимой точке х* за­дачи (3.3.1) -(3.3.3) с дополнительными ограничениями X(j) > 0 при 1<либо=j<либо=n(1) при n1 < j^;<либо=n₂<либо=n. Допустим также, что выполнено хотя бы одно из следующих условий:

1. функции gi дифференцируемы в точке х* и существует до­пустимая точка х такая, что x(j)> 0 при 1 <либо=j <либо=n₂и gi(x) <bi для i >m1

2. все функции g(i) линейны.

Тогда х* является решением задачи, если и только если суще­ствует вектор (множителей Лагранжа) у* = (у*)в степени m1 такой, что……….

13.

14. Геометрическая интуиция подсказывает важные выводы: ес­ли задача ЛП разрешима, то среди ее решений всегда есть вер­шина (многогранного) множества допустимых решений; из лю­бой неоптимальной вершины исходит ребро, вдоль которого ЦФ растет (в задаче максимизации). В некоторыми уточнениями эти утверждения справедливы и в общем случае.

15. Пример 13 (планирование производства). Предприятие мо­жет производить п продуктов. Для каждого продукта j фиксирована….