4.6. Мүмкін болу бағыттар әдісі

Сызықтық емес программалау есептерін осы әдістердің тобымен шешудің негізгі идеясы мүмкін болатын жиында мақсатты функциясының минимум нүктесіне тізбекті жуықтаудың құрылуында жатыр [7], [12]:

(51)

Бұл әдістер градиентті әдістермен функциясын шартсыз минимизациялауды еске салады.

нүктесінен нүктесіне дейінгі қозғалыстың бағытын анықтайтын (51) векторы келесі екі талапты қанағаттандыруы тиіс.

1. Жеткілікті аз үшін (51)-дегі нүкте жиынына жатады (яғни мүмкін болу бағытын сұрайды).

2. Жеткілікті аз үшін теңсіздігі орындалады (яғни кему бағытын анықтайды).

Бірінші шарт мүмкін болатын жиынның шекаралық нүктелері үшін векторы жиынының ішіне бағытталғандығын білдіреді.

(51)-дегі шамасы талабын ескере отырып, бағытында мақсатты функцияның көбірек кему шартынан шартынан таңдалады.

Алдымен,

(52)

(53)

(54)

берілген сызықтық шектеулері бар мүмкін болатын жиынына дөңес дифференциалданатын сызықтық емес функцияны минимизациялау есебін шешудің мүмкін болу бағыттар әдісін қарастырайық.

нүктесінде функциясының кемуінің мүмкін болу бағытын анықтайтын (51)-дегі ыекторының таңдалуын сипаттаймыз. Мүмкін болу оқиғаларын қарастырайық.

1. нүктесінде (53) және (54) барлық теңсіздіктер қатаң түрде орындалсын. Мұнда - ықтималды жиынның ішкі нүктесін білдіреді. Онда

(55)

яғни (51)-де кезекті жуықтауды анықтау градиентті әдістің итерациясына сәйкес келеді.

2. (53), (54) теңсіздіктердің біреуі нүктесінде теңдікке айналсын, яғни ықтималды жиынның шекаралық нүкте болып табылады. Онда -ны таңдау (55)-ке сәйкес мүмкін емес, себебі (51)-дегі нүктесі кез-келген болғанда жиынында жатпай қалуы мүмкін ((55)-тегі бағыты нүктесінде мүмкін болу бағыты болып табылмайды).

Осы жағдайда кемуінің мүмкін болу бағытын қалай анықтау керектігін анықтайық.

Нүктеде теңдікке айналатын (53) және (54)-ші шектеулерге сәйкес индекстер жиынын және арқылы белгілейміз, яғни

(56)

үшін векторының компоненттерін

, (57)

түрінде көрсетейік, мұндағы

Барлық үшін , , және =0 екендігі анық.

векторы (51)-ден келесі сызықтық программалау есебінің шешімі ретінде изделінеді:

(58)

, (59)

(60)

(61)

, , , (62)

, =0, , (63)

мұндағы .

(58)-(60) қатынастардың мағынасын ашайық.

1. (59)-(63)-ші шектеулерді ескере отырып, (58)-дегі мақсатты функцияның минимумына нүктесінде -те жылдам кему бағытын анықтайтын антиградиент пен ізделінуші векторының арасындағы минималды мүмкін болу бұрышы сәйкес келеді.

2. Әрбір үшін шектеу (60) вектор мүмкін болатын жиынның гипержазықтығының шекарасына қалыпты және жиынынан тыс бағытталған векторымен бұрыш құратындығын білдіреді.

нүктесі осы гипержазықтыққа тиісті болғандықтан, кез-келген үшін (59)-шы шарт бағыты бастапқы есептің -ші шектеуіне (53) қатысты мүмкінді екендігіне кепілдік береді.

3. (60)-шы шарт векторы ұзындығының шектеуі болып табылады және (32)-дегі мақсатты функциясының төменнен шектелгендігін қамтамасыз етеді.

4. Әрбір үшін (61)-шы теңсіздік ізделінуші векторының бағыты бастапқы есептің -ші шектеуіне (54) қатысты мүмкінді екендігіне кепілдік береді.

5. (62) және (63) қатынастары 57-ші формуладан шығады және - векторының компоненті.

Енді (50)-дегі бағыты бойынша жылжуының шамасын қалай анықтау керектігін сипаттайық. Табылған үшін ол

шартынан табылады, яғни

, (64)

мұндағы - (51)-дегі үшін сәйкес -ші шектеу (53) және шектеу (54) орындалатын максималды жылжу, демек

(65)

(66)

Ал (53), (54) шектеулерін есеруінсіз векторының бағыты бойынша жылдам түсу шартынан табылады, яғни

мұндағы

(67)

(52) - (54) есептерін шешудің қадамдарының сипаттамаларын келтірейік.

1. -ны (53) және (54) теңсіздіктеріне қою және (56)-шы формула бойынша индекстерінің жиынын анықтау.

2. Егер , (55)-тен векторын табу, қарама-қарсы жағдайда формуланың көмегімен (58) - (62)-ші сызықтық программалау есептерін шешуден -ны анықтау.

3. Табылған вектор үшін (63) - (66)-шы формулалардан -ны анықтау.

4. (51)-ші формула бойынша кезекті жуықтауын табу.

немесе шарттарының бірін орындау кезінде есеп деп аяқтайды, мұндағы - есептің нақты шешімін анықтайтын сан.

Теңдеулердің кез-келгені

жиынындағы функциясының минимум нүктесі нақты табылғандығын білдіреді.

Мысалы 8. Сызықтық емес программалау есебін

мүмкін болу бағыттар әдісімен кезінде есепті аяқтау арқылы шешу.

Шешімі. функциялары -де дөңес және дифференциалданатын болып табылады, сондықтан мүмкін болу бағыттар әдісін қолдануға болады. бастапқы жуықтауын таңдайық. болатындығы анық.

Қадам 1. 1. Так как болғандықтан, нүктесі жиынының ішкі нүктесі болып табылады және .

2. векторын формуласы бойынша табылады.

3. Максималды мүмкінді жылжу -ді

шартынан табылады, бұдан .

(67)-ден -ді анықтай отырып, ==-2-1 функциясы кезінде шексіз кемитін болғандықтан аламыз. Бұдан жылжу шамасын бірінші қадамда табамыз: .

4. (51)-ші формуласы бойынша келесі жуықтауды табамыз:

Қадам 2. 1. Поскольку , то болғандықтан, жиынының шекаралық нүктесі .

2. Вектор векторын сызықтық программалау есебін (47) шешуден табамыз:

Оны симплекс-әдіс арқылы шешеміз:

3. жылжу шамасын алдыңғы қадамдағыдай табамыз: .

4. (51)-ден кезекті жуықтауын табамыз:

=(3;4)+.

Қадам 3. болғандықтан, нүктесі шекаралық болып табылады. Жалпы ереже бойынша және таба отырып, келесіні аламыз:

Бұдан .

Келесі қадамға өте отырып, табамыз, яғни талап етілген дәлдік орындалады және

Мысал 9. Келесі сызықтық емес есепті мүмкін болу бағыттар әдісімен сызықты шектеулерімен немесе кезінде есептеуді аяқтап, шешу.

Шешімі. Алғашқы жуықтау ретінде, мысалы, (0,4; 1,4) нүктесін ( екендігіне көз жеткізіңіз) таңдаймыз.

Қадам 1. 1. нүктесінде (53) және (54) шектеуері қатаң теңсіздік ретінде орындалады, яғни - жиынының ішкі нүктесі, яғни .

2. Сәйкесінше (55)-тен табатынымыз

. (68)

3. (65), (66)-шы формулалардан

аламыз.

минимум шартын =0 қолдана отырып, (67)-ге сәйкес анықталады:

==(0,4+72-4)²+(1,4+1,2-2)²,

=107,04-53,52=0,

бұдан =1/2.

(64)-тен соңғы табатынымыз

=min(1/7,1/12,1/2,)=1/12. (69)

4. (51), (67) және (68) теңдеулерді қолданып, алатынымыз

. (70)

Қадам 2. 1. (70)-тегі нүктесінде есептің шектеулерінің екіншісі теңдеу ретінде орындалады, сондықтан - жиынының шекаралық нүктесі, мұнда .

2. анықтауға арналған (58) - (62) есептер келесі түрде болады:

Осы есепті қосымша айнымалылар арқылы канондық түрде жазып және осы айнымалыларды базистық ретінде таңдап, екі қадамның нәтижесінде симплекс-әдісті аламыз: , яғни.