Сызықты емес программалау есебінің қойылымы

6 7 8 9 10 11 12

13. Сызықты емес программалау есебінің қойылымы

Есептің қойылымы:

J(u)→inf (1)

u U={ u Eⁿ / u g_i(u)≤0, i=1,m; g_i(u)=0, i=m+1,s }, (2)

мұндағы J(u), g_i(u), i=1,s Eⁿ – дегі дөңес U₀ жиынында анықталған берілген функциялар. Белгілеу енгізейік

U_i = { u Eⁿ / (u)≤0}, i=1,m

U_m+1= {u Eⁿ / (u)≤0}, i=m+1,s (3)

Енді U жиынын мына түрде жаза аламыз:

U= U₀∩ U₁,…, U_m∩ U_m+1 (4)

Сонда (1)-(2) есеп төмендегіше жазылады: J(u)→inf, u U. Мәселен

J_* = infJ(u)>-∞, U_*= { u_* Eⁿ/ u_* U, J(u_*) = min J(u), u U } ≠ делік. Егер U_*≠ , онда J(u_*) = min J(u) екенін байқаймыз. Енді u_* U_* нүктесін және J_*= J(u_*) шамасын табу керек.

Лагранждың жалпыланған функциясы (1)-(2) есебі үшін

L(u, ) = ₀J(u) + _ig_i(u), u U₀; = ( ₀, ₁,…, _s) ˄₀ = { E^s+1/ ₀≥0} (5) түрінде өрнектеледі.

Теорема.

Егер J(u) C¹(U₀₁), g_i(u) C¹(U₀₁), int U₀₁≠0, U₀ – дөңес жиын, ал U_*≠ онда әрбір u_** U нүктесі үшін

| ^* | ≠0, ₀^*≥ 0, ₁^*≥0,…, _m^*≥0,〈 L_u(u_*, ^*), u-u_*〉=〈 ₀^*J’(u_*) + _i^*g_i^f(u_*), (6)

u-u_*〉 ≥0, u U₀ (7)

₀^*g_i(u_*) = 0, i=1,s (8)

шарттары орындалатын Лагранж көбейткіштері ^* = ( ^*₀, ^*_{1, ….}, ^*_s) ˄₀ табылуы қажетті.

Теорема шарттары:

1) Дөңес программалауесептеріндегі теоремалардан айырмашылық:

(u_*, ^*) U₀˟ ˄₀ жұбы Лагранж функциясының қайқы нүктесі деп кесіп айтылмайды, яғни негізгі теорема шарты орындалып тұрған жоқ

2) Жалпы жағдайда (u_*, ) жұбы қайқы нүкте болмағандықтан (6)-(8) шарттарынан u_*^* U_* нүктесі (1)-(2) есебінің шешімі деген тұжырым шықпайды.

3) Егер ₀^* > 0, онда (1)-(2) есебі ерекшеленбеген деп аталады, бұл жағдайда ₀^* =1 деп қабылдауға болады, себебі Лагранж функциясы: -ға қатысты сызықты функция.

14. Сызықты емес программалау есебін шығару алгоритмі

Сызықты емес программалаудың келесі есеп шешудің орындалу тәртібі:

мұндағы ал ашық, -дегі дөңес жиынын қамтитын жиын,дербес жағдайда

1. екендігіне көз жеткіземіз.Ол үшін Вейршстрасстың теоремаларына сүйенеміз.

2.1-2 есебі үшін жалпыланған Лагранж функциясын құрамыз

3. (3)

(5)

Шарттарынан нүктелерін табамыз.мұндағы берілген сан дербес жағдайда.

a)Егер немесе ,онда(4) шартты алмастырамыз:

(6)

бұл жағдайда түріндегі n+1+s белгісіздерді анықтау үшін ((3),(5),(6))алгебралық теңдеулердің n+1+s жүйесін аламыз.

б)Егер алгебралық теңдеулерді ((3),(5),(6))немесе(3)-(5) жүйелерін шешкен соң болса,онда(1)-(2) есебі ерекшеленбеген деп аталады.Ерекшеленбеген есептегі (3)шартты неғұрлы қарапайым шарттымен алмастыруға болады.Егер ерекшеленбеген есептегі жұбы

Лагранж функциясының қайқы нүктесі болса,онда нүктесі глобальдік мин нүктесі.

4. Сызықты емес программалаудың келесі есебі

Бұл(7)(8)есебі (1)(2) есебінің дербес жағдайы. .Егер векторлары сызықты тәуелсіз болса,онда (7)-(8)есебіндегі нүктесі қалыпты минимум нүктесі делінеді.