Թույլատրելի արժեքների բազմություն
Օպտիմալացման տեսության մեջ թույլատրելի տիրույթը, թույլատրելի հավաքածուն, որոնման տարածքը կամ լուծման տարածքը օպտիմալացման խնդրի բոլոր հնարավոր կետերի (փոփոխականների արժեքների) բազմությունն է, որոնք բավարարում են խնդրի սահմանափակումներին։ Այդ սահմանափակումները կարող են ներառել անհավասարություններ, հավասարություններ և լուծման ամբողջ թիվ լինելու պահանջ[1][2]։ Թույլատրելի արժեքների բազմությունը խնդրի լուծման համար թեկնածուների որոնման նախնական տարածքն է, բայց որոնման ընթացքում այդ ոլորտը կարող է նեղացվել։
Օրինակ՝ վերցնենք առաջադրանք
Հնարավորինս փոքրացնենք նշված արտահայտությա արժեքը․
Ունենալով և համար նշված սահմանափակումները՝ և ։
Այդ դեպքում թույլատրելի արժեքների բազմությունը՝ (x1, x2) թվազուգերի բազմությունն է, որոնց համար x1-ի արժեքը 1-ից ոչ պակաս է և 10-ից ոչ ավել, իսկ x2-ի արժեքը` 5-ից պակաս և 12-ից ոչ ավելի է։ Նկատենք, որ թույլատրելի արժեքների բազմությունն դիտարկվում է նպատակային ֆունկցիայից անջատ։
Բազմաթիվ խնդիրներում թույլատրելի արժեքների բազմությունը ներառում է սահմանափակում, որ մեկ կամ մի քանի փոփոխականները պետք է լինեն ոչ բացասական։ Ամբողջաթիվ ծրագրավորման խնդիրներում թույլատրելի արժեքների բազմությունը բաղկացած է ամբողջ թվերից (կամ նրա ինչ-որ ենթաբազմությունից)։ Գծային ծրագրավորման խնդիրներում թույլատրելի արժեքների բազմությունը ուռուցիկ պոլիտոպ է՝ տարածք բազմաչափ տարածության մեջ, որի սահմանները ձևավորվում են հիպերհարթությունների[1] միջոցով։
Սահմանափակումները բավարարելը, թույլատրելի արժեքների բազմությունից կետ գտնելու գործընթացն է։
Հարակից սահմանումներ խմբագրել
Անհավասարման տեսքով սահմանափակումների դեպքում կետը կարող է լինել կամ ներքին կետ (թույլատրելի կետ), կամ սահմանային կետ (թույլատրելի կետ), կամ արտաքին կետ (ոչ թույլատրելի կետ)։ Ակտիվ կամ պարտավորեցնող այն սահմանափակումն է, որը տվյալ պահին վերածվում է հավասարության[1]։ Որոշ ալգորիթմներ կարող են օգտագործել ակտիվ սահմանափակումներ հայեցակարգը` ավելի արդյունավետ ալգորիթմ կառուցելու համար (տե՛ս փոփոխական հիմքի մեթոդը)։
Եթե առաջադրանքի համար չկա թույլատրելի կետ, առաջադրանքը կոչվում է ոչ թույլատրելի։
Պայմանական օպտիմալը՝ տեղային օպտիմալն կետն է, որը ընկած է թույլատրելի բազմության սահմանին[1]։
Թույլատրելի լուծումների ուռուցիկ տիրույթ խմբագրել
Թույլատրելի լուծումների ուռուցիկ տիրույթը լուծումների մի բազմություն է, որում երկու թույլատրելի լուծումներ կապող հատվածը պարունակում է միայն թույլատրելի կետեր և չի անցնում որևէ ոչ թույլատրելի կետով։
Ուռուցիկ թույլատրելի արժեքների բազմություն առաջանում է տարբեր տիպի խնդիրների լուծման ժամանակ, այդ թվում ՝ գծային ծրագրավորման խնդիրների, այդպիսի խնդիրները որոշակի հետաքրքրություն են առաջացնում, քանի որ եթե խնդիրը ուռուցիկ նպատակային ֆունկցիան օպտիմալացնելն է, ընդհանուր դեպքում, այդպիսի խնդիրն ավելի հեշտ է լուծել լուծումների ուռուցիկ հավաքածուով, և ցանկացած տեղային օպտիմալ կլինի նաև գլոբալ օպտիմալ։
Թույլատրելի արժեքների բազմության բացակայություն խմբագրել
Եթե օպտիմալացման խնդրի սահմանափակումները համատեղելիս պարզվում է, որ նրանք իրարամերժ են, գոյություն չունի կետ, որը կբավարարի բոլոր սահմանափակումներին, ապա թույլատրելի լուծումների տիրույթը դատարկ է։ Այս պարագայում խնդիրը լուծումներ չունի, ասում են, որ այն ոչ թույլատրելի է[1]։
Սահմանափակ և անսահմանափակ թույլատրելի լուծումների բազմություն խմբագրել
Թույլատրելի լուծումների բազմությունը կարող է լինել սահմանափակ կամ անսահմանափակ։ Օրինակ․ {x ≥ 0, y ≥ 0} այսպիսի սահմանափակումներով սահմանված թույլատրելի լուծումների բազմությունն անսահմանափակ է, քանի որ որոշ ուղղություններով կարելի է անվերջ գնալ, մնալով թույլատրելի լուծումների բազմության շրջանակում։ Ի տարբերություն դրա, {x ≥ 0, y ≥ 0, x + 2y ≤ 4} սահմանափակումներով ձևավորված թույլատրելի լուծումների բազմությունը սահմանափակ է, քանի որ ցանկացած ուղղությամբ շարժումը սահմանափակ է։ Գծային ծրագրավորման n փոփոխականներ պարունակող խնդիրների թույլատրելի լուծումների բազմության սահմանափակության համար անհրաժեշտ, բայց ոչ բավարար պայման է առնվազն n + 1 սահմանափակումների առկայությունը։
Եթե թույլատրելի լուծումների բազմությունն անսահմանափակ է, ապա օպտիմալ լուծումը կարող է գոյություն ունենալ կամ չունենալ՝ կախված նպատակային ֆունկցիայի վարքից։ Օրինակ, եթե բազմությունը սահմանվում է {x ≥ 0, y ≥ 0} սահմանափակումներով, ապա x+y օպտիմալացման խնդիրը լուծումներ չունի, քանի որ ցանկացած արժեք կարող է բարելավվել x-ի կամ y-ի արժեքը մեծացնելով, բայց x+y-ը նվազագույնի հասցնելու խնդիր ունի օպտիմալ լուծում մասնավորապես՝ (x, y) = (0, 0)):