Օպտիմալացումն օգնում է ձեզ գտնել լավագույն արդյունքը, որը բերում է շահույթ, նվազեցնում ծախսերը կամ սահմանում է այնպիսի պարամետր, որն առաջացնում է բիզնես գործընթացների ձախողումներ:
Այս գործընթացը կոչվում է նաև մաթեմատիկական ծրագրավորում։ Այն լուծում է սահմանափակ ռեսուրսների բաշխման որոշման խնդիրը, որն անհրաժեշտ է օպտիմալացման խնդրի ղեկավարի կողմից սահմանված նպատակին հասնելու համար: Բոլոր հնարավոր տարբերակներից ցանկալի է գտնել մեկը, որը առավելագույնի է հասցնում (կամ նվազեցնում) վերահսկիչ պարամետրը, օրինակ՝ շահույթը կամ արժեքը։ Օպտիմալացման մոդելները կոչվում են նաև հանձնարարական կամ նորմատիվ, քանի որ նրանք ձգտում են գտնել իրագործելի ռազմավարություն բիզնեսի համար:
Զարգացման պատմություն
Գծային ծրագրավորումը (LP) աշխատում է օպտիմալացման խնդիրների դասի հետ, որտեղ բոլոր սահմանափակումները գծային են:
Ներկայացնելով LP-ի զարգացման համառոտ պատմությունը:
- 1762 թվականին Լագրանժը լուծեց օպտիմալացման պարզ խնդիրներ՝ հավասարության սահմանափակումներով:
- 1820 թվականին Գաուսը որոշեցվերացման օգտագործմամբ հավասարումների գծային համակարգ։
- 1866 թվականին Վիլհելմ Ջորդանը կատարելագործեց նվազագույն քառակուսիների սխալները գտնելու մեթոդը՝ որպես համապատասխան չափանիշ: Սա այժմ կոչվում է Գաուս-Հորդանանի մեթոդ:
- Թվային համակարգիչը հայտնվել է 1945 թվականին:
- Danzig-ը 1947 թվականին հորինել է սիմպլեքսի մեթոդները։
- 1968 թվականին Ֆիակոն և ՄակՔորմիկը ներկայացրեցին Inside Point մեթոդը:
- 1984 թվականին Կարմարկարը կիրառեց ներքին մեթոդը գծային ծրագրերը լուծելու համար՝ ավելացնելով իր նորարարական վերլուծությունը:
LP-ն ապացուցել է, որ չափազանց հզոր գործիք է ինչպես իրական աշխարհի խնդիրների մոդելավորման, այնպես էլ որպես լայնորեն կիրառվող մաթեմատիկական տեսություն: Այնուամենայնիվ, շատ հետաքրքիր օպտիմալացման խնդիրներ ոչ գծային են:
Ի՞նչ անել այս դեպքում. Նման խնդիրների ուսումնասիրությունը ներառում է գծային հանրահաշվի, բազմաչափ հաշվարկի, թվային վերլուծության և հաշվողական մեթոդների բազմազան խառնուրդ: Գիտնականները մշակում են հաշվողական ալգորիթմներ, ներառյալ գծային ծրագրավորման ներքին կետերի մեթոդները, երկրաչափությունը, ուռուցիկ բազմությունների և ֆունկցիաների վերլուծությունը և հատուկ կառուցվածքային խնդիրների ուսումնասիրությունը, ինչպիսին է քառակուսի ծրագրավորումը::
Ոչ գծային օպտիմալացումը ապահովում է մաթեմատիկական վերլուծության հիմնարար ըմբռնում և լայնորեն օգտագործվում է տարբեր ոլորտներում, ինչպիսիք են ճարտարագիտությունը, ռեգրեսիոն վերլուծությունը, ռեսուրսների կառավարումը, երկրաֆիզիկական հետախուզությունը և տնտեսագիտությունը:
Օպտիմալացման խնդիրների դասակարգում
Կարևոր քայլՕպտիմալացման գործընթացը մոդելների դասակարգումն է, քանի որ դրանց լուծման ալգորիթմները հարմարեցված են որոշակի տեսակի:
1. Դիսկրետ և շարունակական օպտիմալացման հետ կապված խնդիրներ: Որոշ մոդելներ իմաստ ունեն միայն այն դեպքում, եթե փոփոխականները արժեքներ են վերցնում ամբողջ թվերի դիսկրետ ենթաբազմությունից: Մյուսները պարունակում են տվյալներ, որոնք կարող են վերցնել ցանկացած իրական արժեք: Դրանք սովորաբար ավելի հեշտ է լուծել: Ալգորիթմների բարելավումները, զուգորդված համակարգչային տեխնոլոգիաների առաջընթացի հետ, կտրուկ մեծացրել են գծային ծրագրավորման օպտիմալացման խնդրի չափն ու բարդությունը:
2. Անսահմանափակ և սահմանափակ օպտիմալացում: Մեկ այլ կարևոր տարբերություն այն առաջադրանքներն են, որտեղ փոփոխականների վրա որևէ սահմանափակում չկա: Այն կարող է լայնորեն տատանվել՝ պարզ գնահատողներից մինչև հավասարումների և անհավասարությունների համակարգեր, որոնք մոդելավորում են տվյալների միջև բարդ հարաբերությունները: Նման օպտիմիզացման խնդիրները կարող են հետագայում դասակարգվել ըստ ֆունկցիաների բնույթի (գծային և ոչ գծային, ուռուցիկ և հարթ, տարբերվող և ոչ տարբերվող):
3. Իրագործելիության առաջադրանքներ. Նրանց նպատակն է գտնել փոփոխական արժեքներ, որոնք բավարարում են մոդելի սահմանափակումները՝ առանց օպտիմալացման հատուկ նպատակի:
4. Կոմպլեմենտար առաջադրանքներ. Դրանք լայնորեն կիրառվում են տեխնիկայի և տնտեսագիտության մեջ։ Նպատակը փոխլրացման պայմաններին բավարարող լուծում գտնելն է։ Գործնականում մի քանի նպատակներով առաջադրանքները հաճախ վերակազմակերպվում են մեկ նպատակի:
5. Դետերմինիստական ընդդեմ ստոխաստիկ օպտիմալացման: Դետերմինիստական օպտիմալացումը ենթադրում է, որ տվյալներըառաջադրանքները լիովին ճշգրիտ են. Այնուամենայնիվ, շատ արդիական հարցերի վերաբերյալ դրանք չեն կարող հայտնի լինել մի շարք պատճառներով:
Առաջինը կապված է պարզ չափման սխալի հետ: Երկրորդ պատճառն ավելի հիմնարար է. Այն կայանում է նրանում, որ որոշ տվյալներ ներկայացնում են տեղեկատվություն ապագայի մասին, օրինակ՝ ապրանքի պահանջարկը կամ գները ապագա ժամանակահատվածի համար: Ստոխաստիկ օպտիմալացման պայմաններում օպտիմալացնելիս մոդելում ներառված է անորոշությունը:
Հիմնական բաղադրիչներ
Օբյեկտիվ ֆունկցիան այն է, որը պետք է նվազագույնի հասցնել կամ առավելագույնի հասցնել: Օպտիմալացման խնդիրների շատ տեսակներ ունեն մեկ նպատակային ֆունկցիա. Եթե ոչ, ապա դրանք հաճախ կարող են վերաձեւակերպվել, որպեսզի աշխատեն:
Այս կանոնից երկու բացառություն.
1. Թիրախային որոնման առաջադրանք. Բիզնես ծրագրերի մեծ մասում մենեջերը ցանկանում է հասնել որոշակի նպատակի՝ բավարարելով մոդելի սահմանափակումները: Օգտագործողը առանձնապես չի ցանկանում ինչ-որ բան օպտիմալացնել, ուստի անիմաստ է սահմանել օբյեկտիվ գործառույթ: Այս տեսակը սովորաբար կոչվում է բավարարվածության խնդիր:
2. Շատ օբյեկտիվ հատկանիշներ: Հաճախ օգտատերը ցանկանում է օպտիմիզացնել միանգամից մի քանի տարբեր նպատակներ: Նրանք սովորաբար անհամատեղելի են: Փոփոխականները, որոնք օպտիմալացնում են մեկ նպատակի համար, կարող են լավագույնը չլինել մյուսների համար:
Բաղադրիչների տեսակները՝
- Վերահսկվող մուտքը որոշման փոփոխականների մի շարք է, որոնք ազդում են օբյեկտիվ ֆունկցիայի արժեքի վրա: Արտադրական առաջադրանքում փոփոխականները կարող են ներառել տարբեր հասանելի ռեսուրսների բաշխումը կամ դրա համար պահանջվող աշխատուժըյուրաքանչյուր գործողություն։
- Սահմանափակումները հարաբերություններ են որոշման փոփոխականների և պարամետրերի միջև: Արտադրության խնդրի դեպքում իմաստ չունի շատ ժամանակ ծախսել որևէ գործունեության վրա, ուստի սահմանափակեք բոլոր «ժամանակավոր» փոփոխականները։
- Հնարավոր և օպտիմալ լուծումներ. Փոփոխականների որոշման արժեքը, որոնց համաձայն բոլոր սահմանափակումները բավարարված են, կոչվում է բավարար: Ալգորիթմների մեծ մասը սկզբում գտնում է այն, հետո փորձում է բարելավել այն: Ի վերջո, նրանք փոխում են փոփոխականները՝ մի իրագործելի լուծումից մյուսը անցնելու համար: Այս գործընթացը կրկնվում է այնքան ժամանակ, մինչև օբյեկտիվ ֆունկցիան հասնի իր առավելագույնին կամ նվազագույնին: Այս արդյունքը կոչվում է օպտիմալ լուծում:
Օպտիմիզացման խնդիրների ալգորիթմները, որոնք մշակվել են հետևյալ մաթեմատիկական ծրագրերի համար, լայնորեն կիրառվում են.
- ուռուցիկ.
- բաժանելի.
- քառորդական.
- Երկրաչափական.
Google Linear Solvers
Գծային օպտիմիզացում կամ ծրագրավորում այսպես է կոչվում խնդրի օպտիմալ լուծման հաշվողական գործընթացին։ Այն մոդելավորվում է որպես գծային հարաբերությունների մի շարք, որոնք առաջանում են բազմաթիվ գիտական և ճարտարագիտական առարկաներից:
Google-ն առաջարկում է գծային օպտիմալացման խնդիրները լուծելու երեք եղանակ՝
- Glop բաց կոդով գրադարան։
- Գծային օպտիմիզացման հավելում Google Sheets-ի համար:
- Գծային օպտիմիզացման ծառայություն Google Apps Script-ում։
Glop-ը ներկառուցված է Google-ումգծային լուծիչ. Այն հասանելի է բաց կոդով: Դուք կարող եք մուտք գործել Glop OR-Tools գծային լուծիչի փաթաթման միջոցով, որը հանդիսանում է Glop-ի փաթաթան:
Գծային օպտիմիզացման մոդուլը Google Sheets-ի համար թույլ է տալիս կատարել օպտիմալացման խնդրի գծային հայտարարություն՝ տվյալներ մուտքագրելով աղյուսակ:
Քառակուսի ծրագրավորում
Premium Solver հարթակն օգտագործում է Simplex մեթոդի ընդլայնված LP/Quadratic տարբերակը՝ LP և QP խնդիրների մշակման սահմանաչափերով մինչև 2000 որոշման փոփոխականներ:
SQP Լուծիչը լայնածավալ խնդիրների համար օգտագործում է ակտիվ հավաքածուի մեթոդի ժամանակակից ներդրումը նոսրությամբ՝ քառակուսի ծրագրավորման (QP) խնդիրներ լուծելու համար: XPRESS Solver շարժիչը օգտագործում է «Interior Point» կամ Newton Barrier մեթոդի բնական ընդլայնումը QP խնդիրները լուծելու համար:
MOSEK Լուծիչը կիրառում է ներկառուցված «Inside Point» և ավտոմատ կրկնակի մեթոդներ: Սա հատկապես արդյունավետ է թույլ զուգակցված QP խնդիրների դեպքում: Այն կարող է նաև լուծել Scale Quadratic Constraint (QCP) և Երկրորդ կարգի Կոն Ծրագրավորման (SOCP) խնդիրները:
Բազմաֆունկցիոնալ հաշվարկներ
Դրանք բավականին հաջողությամբ օգտագործվում են Microsoft Office-ի հնարավորությունների կիրառմամբ, օրինակ՝ Excel-ում օպտիմալացման խնդիրների լուծում:
Վերոնշյալ աղյուսակում խորհրդանիշներն են՝
- K1 - K6 - հաճախորդներ, ովքեր պետք է ապրանքներ տրամադրեն:
- S1 - S6-ը պոտենցիալ արտադրական տեղամասեր են, որոնք կարող են կառուցվել դրա համար: Կարող է ստեղծվել1, 2, 3, 4, 5 կամ բոլոր 6 վայրերը։
Կան հաստատուն ծախսեր յուրաքանչյուր հաստատության համար, որը թվարկված է I սյունակում (Fix):
Եթե գտնվելու վայրը ոչինչ չփոխի, այն չի հաշվվի: Այդ դեպքում ֆիքսված ծախսեր չեն լինի։
Նշեք պոտենցիալ վայրերը՝ նվազագույն ծախսերը ստանալու համար:
Այս պայմաններում գտնվելու վայրը կա՛մ հաստատված է, կա՛մ ոչ: Այս երկու վիճակներն են՝ «ՃԻՇՏ - ՍՈՒՏ» կամ «1 - 0»: Վեց տեղակայման համար կա վեց վիճակ, օրինակ՝ 000001-ը դրված է միայն վեցերորդին, 111111-ը՝ բոլորին:
Երկուական թվային համակարգում կա ուղիղ 63 տարբեր տարբերակ 000001 (1)-ից մինչև 111111 (63):
L2-L64-ն այժմ պետք է կարդա {=ԲԱԶՄԱԿԱՆ ՕՊԵՐԱՑԻԱ (K1)}, սրանք բոլոր այլընտրանքային լուծումների արդյունքներն են: Այնուհետև նվազագույն արժեքը=Min (L) է, իսկ համապատասխան այլընտրանքը INDEX (K):
CPLEX Ամբողջական ծրագրավորում
Երբեմն գծային հարաբերությունները բավարար չեն բիզնես խնդրի էության մեջ մտնելու համար: Սա հատկապես ճիշտ է, երբ որոշումները ներառում են դիսկրետ ընտրություններ, օրինակ՝ բացել պահեստ որոշակի վայրում, թե ոչ: Այս իրավիճակներում պետք է օգտագործվի ամբողջ թվով ծրագրավորում։
Եթե խնդիրը ներառում է ինչպես դիսկրետ, այնպես էլ շարունակական ընտրություններ, ապա դա խառը ամբողջական ծրագիր է: Այն կարող է ունենալ գծային, ուռուցիկ քառակուսի խնդիրներ և նույն երկրորդ կարգի սահմանափակումներ։
Ամբողջ թվային ծրագրերը շատ ավելի բարդ են, քան գծային ծրագրերը, բայց նրանք ունեն կարևոր բիզնես ծրագրեր: Ծրագրային ապահովումCPLEX ծրագրաշարը օգտագործում է բարդ մաթեմատիկական մեթոդներ՝ ամբողջ թվով խնդիրներ լուծելու համար: Նրա մեթոդները ներառում են դիսկրետ փոփոխականների հնարավոր համակցությունների համակարգված որոնում՝ օգտագործելով գծային կամ քառակուսի ծրագրային հանգստացումներ՝ օպտիմալ լուծման արժեքի սահմանները հաշվարկելու համար:
Նրանք նաև օգտագործում են LP և այլ օպտիմալացման խնդիրների լուծման մեթոդներ՝ սահմանափակումները հաշվելու համար:
Ստանդարտ Microsoft Excel Լուծիչ
Այս տեխնոլոգիան օգտագործում է հիմնական Simplex մեթոդի հիմնական ներդրումը LP-ի խնդիրները լուծելու համար: Այն սահմանափակվում է 200 փոփոխականով: «Premium Solver»-ը օգտագործում է առաջնային սիմպլեքսի բարելավված մեթոդ՝ փոփոխականների համար երկկողմանի սահմաններով: Premium Solver հարթակը օգտագործում է LP/Quadratic Simplex Solver-ի ընդլայնված տարբերակը՝ օպտիմալացման խնդիր լուծելու համար մինչև 2000 որոշման փոփոխականներով:
Լայնածավալ LP-ն Premium Solver պլատֆորմի համար կիրառում է պարզ և կրկնակի սիմպլեքս մեթոդի ժամանակակից ներդրում, որն օգտագործում է LP մոդելի սակավությունը՝ խնայելու ժամանակ և հիշողություն, թարմացման առաջադեմ ռազմավարություններ և refactoring matrices, բազմակի և մասնակի գնագոյացումներ և ռոտացիաներ և դեգեներացիա հաղթահարելու համար: Այս շարժիչը հասանելի է երեք տարբերակով (կարող է կառավարել մինչև 8000, 32000 կամ անսահմանափակ փոփոխականներ և սահմանափակումներ):
MOSEK Լուծիչը ներառում է առաջնային և երկակի սիմպլեքս, մեթոդ, որը նաև օգտագործում է սակավությունը և օգտագործում է առաջադեմ ռազմավարություններ մատրիցների թարմացման և «վերագործարկման» համար: Այն լուծում է անսահմանափակ չափի խնդիրներ, եղել էփորձարկվել է գծային ծրագրավորման խնդիրների վրա՝ միլիոնավոր որոշման փոփոխականներով:
Քայլ առ քայլ օրինակ EXCEL-ում
Excel-ում օպտիմալացման խնդրի մոդելը սահմանելու համար կատարեք հետևյալ քայլերը՝
- Խնդիրի տվյալները կազմակերպեք աղյուսակում տրամաբանական ձևով:
- Ընտրեք բջիջ յուրաքանչյուր փոփոխական պահելու համար:
- Բջջում ստեղծեք օպտիմիզացման խնդրի թիրախային մաթեմատիկական մոդելը հաշվարկելու բանաձև։
- Ստեղծեք բանաձևեր յուրաքանչյուր սահմանափակումի ձախ կողմը հաշվարկելու համար:
- Օգտագործեք երկխոսություններ Excel-ում՝ Solver-ին պատմելու որոշման փոփոխականների, թիրախների, սահմանափակումների և այդ պարամետրերի ցանկալի սահմանների մասին:
- Գործարկեք «Solver»-ը՝ օպտիմալ լուծումը գտնելու համար:
- Ստեղծեք Excel թերթ:
- Կազմակերպեք խնդրի տվյալները Excel-ում, որտեղ հաշվարկված է նպատակային ֆունկցիայի և սահմանափակման բանաձևը:
Վերոհիշյալ աղյուսակում B4, C4, D4 և E4 բջիջները վերապահված են X 1, X 2, X 3 և X 4 որոշման փոփոխականները ներկայացնելու համար: Որոշման օրինակներ՝
- Ապրանքների խառնուրդի մոդելը ($450, $1150, $800 և $400 շահույթ մեկ ապրանքի համար) մուտքագրվել է համապատասխանաբար B5, C5, D5 և E5 բջիջներում: Սա թույլ է տալիս թիրախը հաշվարկել F5=B5B4 + C5C4 + D5D4 + E5E4 կամ F5:=SUMPRODUCT (B5: E5, B4: E4):
- B8-ում մուտքագրեք յուրաքանչյուր տեսակի արտադրանքի արտադրության համար անհրաժեշտ ռեսուրսների քանակը:
- Բանաձև F8:=SUMPRODUCT(B8:E8, $B$4:$E$4).
- Պատճենել սաբանաձևը F9-ում. $B$4:$E$4 դոլարի նշանները ցույց են տալիս, որ այս բջիջների միջակայքը մնում է հաստատուն:
- G8-ում մուտքագրեք յուրաքանչյուր տեսակի ռեսուրսների առկա քանակությունը, որը համապատասխանում է աջ կողմում գտնվող սահմանափակումների արժեքներին: Սա թույլ է տալիս դրանք արտահայտել այսպես. F11<=G8: G11:
- Սա համարժեք է չորս սահմանների F8<=G8, F9 <=G9, F10 <=G10 և F11=0
Մեթոդի գործնական կիրառման ոլորտները
Գծային օպտիմիզացիան ունի բազմաթիվ գործնական կիրառություններ՝ որպես օպտիմալացման խնդրի օրինակ:
Ընկերությունը կարող է արտադրել մի քանի ապրանքներ՝ հայտնի ներդրման մարժայով: Յուրաքանչյուր ապրանքի միավորի արտադրությունը պահանջում է հայտնի քանակությամբ սահմանափակ ռեսուրսներ: Խնդիրն է՝ ստեղծել արտադրական ծրագիր՝ որոշելու համար, թե յուրաքանչյուր ապրանքից որքան պետք է արտադրվի, որպեսզի ընկերության շահույթը առավելագույնի հասցվի՝ առանց ռեսուրսների սահմանափակումների խախտման։
Խառնուրդի խնդիրները օպտիմալացման խնդիրների լուծումն է, որը կապված է վերջնական արտադրանքի մեջ բաղադրիչները համատեղելու հետ: Դրա օրինակն է 1947 թվականին Ջորջ Դանցիգը ուսումնասիրած սննդակարգի խնդիրը։ Տրվում են մի շարք հումք՝ վարսակ, խոզի միս և արևածաղկի ձեթ, սննդային պարունակությամբ՝ սպիտակուցներ, ճարպեր, վիտամին A և դրանց մեկ կիլոգրամի գինը։ Խնդիրը հումքից մեկ կամ մի քանի վերջնական արտադրանքի խառնուրդն է հնարավորինս ցածր գնով` պահպանելով դրանց սննդային արժեքի նվազագույն և առավելագույն սահմանները:
Գծային օպտիմալացման խնդրի դասական կիրառումը կարիքների համար երթուղի որոշելն էերթևեկությունը հեռահաղորդակցության կամ տրանսպորտային ցանցերում. Միևնույն ժամանակ, հոսքերը պետք է ուղղորդվեն ցանցով այնպես, որ երթևեկության բոլոր պահանջները բավարարվեն առանց թողունակության պայմանների խախտման:
Մաթեմատիկական տեսության մեջ գծային օպտիմալացումը կարող է օգտագործվել երկու հոգու համար զրոյական գումարով խաղերում օպտիմալ ռազմավարությունները հաշվարկելու համար: Այս դեպքում յուրաքանչյուր մասնակցի համար հաշվարկվում է հավանականության բաշխումը, որը նրա ռազմավարությունների պատահական խառնման գործակիցն է։
Աշխարհում ոչ մի հաջող բիզնես գործընթաց հնարավոր չէ առանց օպտիմալացման: Կան բազմաթիվ օպտիմիզացման ալգորիթմներ: Որոշ մեթոդներ հարմար են միայն որոշակի տեսակի խնդիրների համար: Կարևոր է, որ կարողանանք ճանաչել դրանց բնութագրերը և ընտրել լուծման համապատասխան մեթոդը։
