Ոչ գծային ծրագրավորում

Ոչ գծային ծրագրավորումը(NLP, անգլ.՝ NonLinear Programming) մաթեմատիկական ծրագրավորման այն դեպքն է, երբ նպատակային ֆունկցիան կամ սահմանափակումները հանդիսանում են ոչ գծային ֆունկցիաներ։

Ոչ գծային ծրագրավորման խնդիրը դրվում է որպես որոշակի $F(x_{1},\ldots x_{n})$ նպատակային ֆունկցիայի օպտիմալ լուծումը գտնելու խնդիր հետևյալ պայմանների դեպքում՝

$g_{j}(x_{1},\ldots x_{n})\geq 0$

որտեղ $x_{i},i=1,\ldots ,n$ — պարամետրեր են, $g_{j},j=1,\ldots ,s$ — սահմանափակումներն են, $n$ — Պարամետրերի քանակն է, $s$ —սահմանափակումների քանակն է։

Ի տարբերություն գծային ծրագրավորման խնդիրների, ոչ գծային ծրագրավորման խնդիրների օպտիմալ լուծումը որոշակի սահմանափակումների դեպքում պարտադիր չէ, որ լինի տիրույթի եզրին։

Խնդիրների լուծման եղանակները

Եղանակներից մեկը, որը թույլ է տալիս գտնել ոչ գծային ծրագրավորման խնդրի լուծումը բերել հավասարումների համակարգի լուծմանը,Լագրանժի բազմապատիկների մեթոդն է։

Եթե $F$ նպատակային ֆունկցիան գծային տեսքի է, իսկ սահմանափակումները և՛ գծային են,և՛ ոչ գծային,այդ դեպքում խնդիրը հանդիսանում է գծային ծրագրավորման խնդիր, որը կարող է լուծվել գծային ծրագրավորման խնդիրների լուծման հայտնի եղանակներով։

Եթե նպատակային ֆունկցիան գոգավոր է(մաքսիմումի խնդիր) կամ ուռուցիկ(մինիմումի խնդիր) և սահմանափակումների մեծամասնությունը ուռուցիկ տեսքի են,այդ դեպքում խնդիրը անվանում են ուռուցիկ, և մեծ մասամբ կարող են օգտագործվել ուռուցիկ օպտիմալացման մեթոդները։

Եթե նպատակային ֆունկցիան հանդիսանում է գոգավոր և ուռուցիկ ֆուկցիաների հարաբերություն (մաքսիմումի դեպքում) և սահմանափակումները գոգավոր են, խնդիրը կարող է բերվել ուռուցիկ օպտիմալացման խնդրի կոտորակային ծրագրավորման մեթոդների օգնությամբ։

Գոյություն ունի ոչ ուռուցիկ խնդիրների լուծման մի քանի մեթոդներ։ Մի մոտեցումը գծային ծրագրավորման խնդիրների հատուկ ձևակերպումների օգտագործումն է։ Մյուս մեթոդը ճյուղավորումների մեթոդի օգտագործումն է,որ դեպքում խնդիրտ բաժանվում է դասերի, որպեսզի լուծվի կա՛մ ուռուցիկ, կա՛մ գծային մոտարկումներով, որոնք ձևավորում են ներքևի սահմանի տիրույթները այդ բաժնում։ Մյուս բաժիններում որոշակի պահին կարող ենք ստանալ փաստացի լուծումները, որոնց արժեքը լավագույնն է ներքևի սահմանի համար, և ստացվել է մոտակա լուծումներից ցանկացածից։Այդ լուծումը օպտիմալ լուծում է, բայց հնարավոր է նաև, որ միակը չէ։ Ալգորիթմը կարելի է դադարացնել, երբ համոզված ենք,որ օպտիմալ լուծումը գտնվում է գտնված կետի թույլատրելի արժեքների տիրույթի սահմաններում․ այդպիսի կետերը անվանում են ε-օպտիմալներ։ Որպես կանոն, ε-օպտիմալ կետերի հայտնաբերումը անհրաժեշտ է լուծումների վերջավոր թվով լինելու համար։ Դա հատկապես օգտակար է երկար,բարդ խնդիրների համար անորոշ սպառումով կամ նշանակությամբ, որտեղ անորոշությունը կարող է որոշվել հուսալիության աստիճանի որոշմամբ։

Դիֆերենցումը և անընդհատության պայմանը՝ Կարուշ-Կուն-Տակերի պայմանը ապահովում է օպտիմալ լուծման անհրաժեշտ պայմանը։ Ուռուցիկության դեպքում դա նաև համարվում է բավարար։

Արտաքին հղումներ

• Օպտիմալ լուծման առցանց հաշվիչ

Տես նաև

• Գծային ծրագրավորում