9.21. задачи выпуклого программирования

9.21. задачи выпуклого программирования: Справочник по математике для экономистов, В.И. Ермаков, 2009 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Содержит материал, позволяющий анализировать экономические задачи и осуществлять расчеты. Отражены разделы линейной алгебры, математического программирования, сетевое программирование и планирование, обработка результатов измерений, статистический анализ.

9.21. задачи выпуклого программирования

Задача максимизации (9.59)—(9.61) называется задачей выпуклого программирования в том случае, когда все функции Ф,(АГ) являются выпуклыми, а целевая функция f{M) — вогнутой на R".

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

Г. Любая точка условного максимума целевой функции на допустимом множестве является оптимальным решением задачи выпуклого программирования.

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

Говорят, что множество

Q = {Me Щ | Ф.(уМ) < О, /= 1, 2,т}

удовлетворяет условию Слейтера, если существует точка М є Q такая, что для всех нелинейных функций Ф{(М) Ф, (Af) < 0.

266

О Пример. Множество Q = {М(хр х2, х3) є R31 ФХ(М) х1 + х + + Xі 4 < О, Ф2(М) Xj + х2 + хг 3 < 0} удовлетворяет условию Слейтера, так как если М(1; 1; 1), то ФХ(М) -1 < 0, Ф2(М) 0. •

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

Предположим, что допустимое множество задачи выпуклого программирования (9.59)—(9.61) удовлетворяет условию Слейтера. Тогда имеют место следующие утверждения:

Точка MQ є R" является оптимальным решением задачи (9.59)—(9.61) тогда и только тогда, когда существует точка Р0 є (Rm)+ такая, что (MQ, PQ) будет седловой точкой функции Ла-гранжа для этой задачи.

На основании этого утверждения построена теория двойственности в выпуклом программировании.

Если функции /(Af) и Ф((М), 1=1,2,т, дифференцируемы в точке М0 є R", то эта точка является оптимальным решением задачи (9.59)—(9.61) тогда и только тогда, когда она является точкой Куна — Таккера для этой задачи.

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

(9.65)

(9.66) (9.67)

О Пример. Рассмотрим задачу выпуклого программирования /= 5jCj + 2х2 + 4х3 -х-хх (max),

Ъх + 6х32 -15 < 0, [ху + 2х2 + х3 5 < 0, хх>0, х3>0

иточкуА/дЦ; 1; 1).

Функция Лагранжа для задачи (9.65)—(9.67) имеет вид

L(xvx2,xvyvy2) = = 5xj + 2х2 + 4х3-Xі-х-хj1(9xj + 6х3 15) ~У2(Х + 2х2 + х3 5).

267

Запишем условия Куна — Таккера:

S-7xl-lSy^l-y2^0, 9х2 + 6х2-15<0,

2 2х2 2у2 = О, Xj + 2х2 + х3 5 < 0,

4 2х3 12уЛ-у2<0, (9х2 + 6х32 15)^ = О,

(5 2xj 18j1x1 у2)хх = О, (Xj + 2х2 + х3 5)j>2 = 0.

(4 2х3 12ухх3 у2)х3 = О,

Полагая xt = 1, х2 = 1, х3 = 1, найдем ух = 1/6, у2 = 0. Поэтому Af0(l; 1; 1) является точкой Куна — Таккера для задачи (9.65)—(9.67). Следовательно, Af0(l; 1; 1) — оптимальное решение этой задачи. •

Справочник по математике для экономистов

Справочник по математике для экономистов

Обсуждение Справочник по математике для экономистов

Комментарии, рецензии и отзывы

9.21. задачи выпуклого программирования: Справочник по математике для экономистов, В.И. Ермаков, 2009 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Содержит материал, позволяющий анализировать экономические задачи и осуществлять расчеты. Отражены разделы линейной алгебры, математического программирования, сетевое программирование и планирование, обработка результатов измерений, статистический анализ.