37 Условия Куна- Таккера. Теорема Куна - Таккера. Условие дополняющей нежесткости

Условия Куна-Таккера являя-ся необходимыми усл-ми сущ-ния реш-ния з-чи (максимизации):

f(x)max (1)

g_i(x)<=b_i, i=1,m (2)

Это сл-ет из теоремы.

Теорема К-Т

Необх-ми усл-ми сущ-ия стацин-й т. ф-ии Лагранжа: L(x, )=f(x)+ ^т(b-g(x)) задачи (1)-(2),явл-ся след-е усл-ия:

Эти усл-ия м.б. записаны в алгебраической форме:

Замечание 1

Из 1 и 3 усл-й К-Т след-ет,что либо множ-ль Лагранжа =0,либо соот-ие огр-ие-нер-во должно вып-ся как строгое рав-во,либо то и др-е вып-ся одноврем-но. З-е усл-е К-Т _i(b_i-g_i(x))=0 наз-ся усл-ем дополняющей нежесткости

Замечание2

Усл-ия (3) и (4) применимы также и к з-че мин-ции:

f(x)min (5)

g_i(x)<=b_i, i=1,m (6)

За тем лишь искл-ем, что для з-чи (5)-(6) вектор мн-лей Л д б пол-ным, т.е. <=0. Однако, как в з-че (1)-(2), так и в з-че (5)-(6) мн-ли Л., соотв-щие активным огр-ям, по знаку не ограничены.

38 Понятие выпуклой (строго выпуклой) и вогнутой (строго вогнутой) ф-ии. Св-ва выпуклых (вогнутых) ф-ий. З-ча выпукло-вогнутого программирования

Ф-ия f(x) наз-ся выпуклой (вогнутой) на множ-ве D, если x,уД [0,1] справ-во:

Если нер-ва (1) строгие, то ф-ия f(x) наз-ся строго выпуклой(строго вогнутой) на мн-ве Д.

Св-ва:

1) Если ф-ия f(x) выпукла, то ф-ия g(x)=-f(x) вогнута и наоборот.

2) Сумма выпуклых ф-ий чвл-ся выпуклой ф-ей, сумма вогнутых-вогнутой.

Задача f(x)max(min)

хД

наз-ся з-чей выпукло-вогнутого программирования, если цел-ая ф-ия f(x) выпукла или вогнута, а обл-ть огр-ний Д есть выпуклое мн-во.

39 Достаточность условий Куна-Таккера в з-чах выпукло-вогнутого программирования. Т-ма о единств-ти экстр-ма строговыпуклой (строговогнутой) ф-ии

Достат-ть усл-й К-Т

если целевая ф-ия f(x) задачи:

f(x)max(min)

хД

обладает св-ми, указанными ниже в таблице, то тогда необходимые усл-ия К-Т оказываются достат-ми.

Т-ма о единств-ти экстр-ма строговыпуклой (строговогнутой) ф-ии:

Строго выпуклая(строго вогнутая) ф-ия на вып-м множ-ве Д не может иметь >1 т. глоб-го min-ма(max)

40 Метод Куна- Таккера решения задач выпукло-вогнутого программирования. Методы реш-я плохо обусловленных знлп. Теорема Вейерштрасса

Метод К-Т:

Метод основан на теореме о единственности экст-ма строго выпуклой (вогнутой) ф-ии и достаточночти усл-ий К-Т при нек-ых постановках з-чи:

f(x)max(min)

хД

Метод реализуется в 2 шага:

1) Поовер-ся св-ва цел-ой ф-ии f(x) (выпуклая или вогнутая) и тип оптимизации (максимизация или мин-ция) исходной з-чи. Если рез-ты проверки соответствуют св-ам цел-ой ф-ии, то сл-ет перейти к шагу 2.

2) Решается сис-ма необходимых усл-ий К-Т. Полученное ед-ное реш-е при этом и явл-ся опт-ным планом исходной з-чи.

Методы реш-я плохо обусл-ых ЗНЛП:

Назовем плохо обусл-ой ЗНЛ:

f(x)max(min) (1)

хД (2)

если цел-ая ф-ия f(x) в (1) не достаточно гладкая (не диф-ма или даже не непрерывная, разрывная, а обл-ть огр-ний Д в (2) имеет сложную стр-ру.

Ввиду большого разнообразия конкретных постановок плохо обусл-ых ЗНЛП общих методов их реш-ия не сущ-ет. В каждом конкретном сл-е сл-ет применять свой, наиболее подходящий приэтом подход к реш-ю з-чи. Тем не менее можно рекомендовать к вып-ю след-щие шаги:

1) Если возможно разбить обл-ть огр-ний Д На подмн-ва, во всех точках кот-ых цел-ая ф-ия диф-ма, и за темдля каждой такой обл-ти применить методы, применяемые для нормально-обусловленных ЗНЛП. В противном сл-е реализовать шаг 2.

2)Если возможно разбить обл-ть Д на подм-ва, во всех точках кот-ых целевая ф-ия непрерывна, а сами эти подм-ва - компактны (замкнуты и ограничены), то на каждом из таких подмн-в цел-ой ф-ии f(x) будет иметь локальный экстремум. Что явл-ся сл-ем теоремы:

Теорема Вейерштрасса:

Пусть область ограничений Д, задачи f(x)→max(min) является не пустым и компактным множ-м ,тогда непрерывная целевая функция f(x),заданная на этом множестве достигает глобального условного max-ма (min) на внутренней или граничной точки области Д.