Խնդրի ձևակերպում. Գտեք օբյեկտիվ ֆունկցիայի առավելագույնը գրաֆիկական մեթոդով

Օբյեկտիվ ֆունկցիա- մի քանի փոփոխականների իրական կամ ամբողջ թվային ֆունկցիա, որը ենթակա է օպտիմալացման (մինիմիզացման կամ մաքսիմալացման)՝ օպտիմալացման որոշ խնդիր լուծելու համար: Տերմին, որն օգտագործվում է մաթեմատիկական ծրագրավորման, գործառնությունների հետազոտության, գծային ծրագրավորման, տեսության մեջ վիճակագրական լուծումներև մաթեմատիկայի այլ ոլորտներ՝ հիմնականում կիրառական բնույթի, թեև օպտիմալացման նպատակը կարող է լինել նաև բուն մաթեմատիկական խնդրի լուծումը։ Բացի այդ օբյեկտիվ գործառույթՕպտիմալացման խնդրի դեպքում փոփոխականների համար սահմանափակումները կարող են սահմանվել հավասարումների կամ անհավասարությունների համակարգի տեսքով: IN ընդհանուր դեպքԹիրախային ֆունկցիայի արգումենտները կարող են նշվել կամայական բազմությունների վրա:

Օրինակներ

Հարթ ֆունկցիաներ և հավասարումների համակարգեր

Հավասարումների ցանկացած համակարգի լուծման խնդիրը

( F 1 (x 1 , x 2 , … , x M) = 0 F 2 (x 1 , x 2 , … , x M) = 0 … F N (x 1 , x 2 , … , x M) = 0 ( \ցուցադրման ոճ \ձախ\((\սկիզբ(մատրիցան)F_(1)(x_(1),x_(2),\ldots,x_(M))=0\\F_(2)(x_(1),x_ (2),\ldots,x_(M))=0\\\ldots \\F_(N)(x_(1),x_(2),\ldots,x_(M))=0\վերջ (մատրիցան) )\ճիշտ.)

կարող է ձևակերպվել որպես օբյեկտիվ ֆունկցիան նվազագույնի հասցնելու խնդիր

S = ∑ j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) (\displaystyle S=\sum _(j=1)^(N)F_(j)^(2)( x_ (1), x_ (2), \ ldots , x_ (M)) \ qquad (1))

Եթե ​​գործառույթները հարթ են, ապա նվազագույնի հասցնելու խնդիրը կարող է լուծվել գրադիենտ մեթոդների միջոցով:

Ցանկացած հարթ օբյեկտիվ ֆունկցիայի համար մասնակի ածանցյալները բոլոր փոփոխականների նկատմամբ կարող են հավասարվել 0-ի (\displaystyle 0): Օբյեկտիվ ֆունկցիայի օպտիմալը կլինի հավասարումների նման համակարգի լուծումներից մեկը։ (1) ֆունկցիայի դեպքում (\displaystyle (1)) սա կլինի մեթոդի հավասարումների համակարգը. նվազագույն քառակուսիները(MNC): Սկզբնական համակարգի յուրաքանչյուր լուծում նվազագույն քառակուսիների համակարգի լուծում է: Եթե ​​սկզբնական համակարգը անհամապատասխան է, ապա նվազագույն քառակուսիների համակարգը, որը միշտ լուծում ունի, թույլ է տալիս ստանալ սկզբնական համակարգի մոտավոր լուծումը։ Ամենափոքր քառակուսիների համակարգում հավասարումների թիվը համընկնում է անհայտների քանակի հետ, ինչը երբեմն հեշտացնում է համատեղ սկզբնական համակարգերի լուծումը։

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

Ուրիշներին հայտնի օրինակՕբյեկտիվ ֆունկցիան գծային ֆունկցիա է, որն առաջանում է գծային ծրագրավորման խնդիրներում։ Ի տարբերություն քառակուսի նպատակային ֆունկցիայի, գծային ֆունկցիայի օպտիմալացումը հնարավոր է միայն այն դեպքում, եթե կան սահմանափակումներ գծային հավասարումների կամ անհավասարությունների համակարգի տեսքով։

Համակցված օպտիմալացում

Համակցված նպատակային ֆունկցիայի տիպիկ օրինակ է ճանապարհորդող վաճառողի խնդրի օբյեկտիվ ֆունկցիան։ Այս ֆունկցիան հավասար է գրաֆիկի Համիլտոնյան ցիկլի երկարությանը։ Այն սահմանվում է գրաֆիկի n − 1 (\displaystyle n-1) գագաթների փոխարկումների բազմության վրա և որոշվում է գրաֆիկի եզրերի երկարությունների մատրիցով։ Նման խնդիրների ճշգրիտ լուծումը հաճախ հանգում է տարբերակների թվարկմանը։

Գլուխ 1. Հիմնական գծային ծրագրավորման խնդրի շարադրանք

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

Գծային ծրագրավորումը մաթեմատիկական ծրագրավորման ճյուղ է, որն ուսումնասիրում է էքստրեմալ խնդիրների լուծման մեթոդները, որոնք բնութագրվում են գծային կախվածությունփոփոխականների և գծային թեստի միջև: Նման խնդիրները լայն կիրառություն են գտնում մարդկային գործունեության տարբեր ոլորտներում։ Այս տեսակի խնդիրների համակարգված ուսումնասիրությունը սկսվել է 1939–1940 թթ. ստեղծագործություններում Լ.Վ. Կանտորովիչ.

Գծային ծրագրավորման մաթեմատիկական խնդիրները ներառում են կոնկրետ արտադրական և տնտեսական իրավիճակների ուսումնասիրություններ, որոնք այս կամ այն ​​ձևով մեկնաբանվում են որպես սահմանափակ ռեսուրսների օպտիմալ օգտագործման խնդիրներ:

Գծային ծրագրավորման մեթոդներով լուծվող խնդիրների շրջանակը բավականին լայն է, օրինակ.

արտադրության պլանավորման մեջ ռեսուրսների օպտիմալ օգտագործման խնդիրը.

խառնուրդի խնդիր (արտադրանքի կազմի պլանավորում);

օպտիմալ համադրություն գտնելու խնդիր տարբեր տեսակներապրանքներ պահեստներում պահեստավորման համար (գույքագրման կառավարում կամ);

տրանսպորտային առաջադրանքներ (ձեռնարկության գտնվելու վայրի վերլուծություն, ապրանքների տեղաշարժ):

Գծային ծրագրավորումը մաթեմատիկական ծրագրավորման ամենազարգացած և լայնորեն կիրառվող բաժինն է (ի լրումն, սա ներառում է` ամբողջ թվեր, դինամիկ, ոչ գծային, պարամետրային ծրագրավորում): Սա բացատրվում է հետևյալ կերպ.

Մեծ թվով տնտեսական խնդիրների մաթեմատիկական մոդելները գծային են՝ կապված պահանջվող փոփոխականների հետ.

Այս տեսակի խնդիրը ներկայումս ամենաուսումնասիրվածն է: Նախատեսված է նրա համար հատուկ մեթոդներ, որոնց օգնությամբ լուծվում են այս խնդիրները, և համապատասխան համակարգչային ծրագրերը;

գծային ծրագրավորման բազմաթիվ խնդիրներ, լուծված լինելով, լայն կիրառություն են գտել.

Որոշ խնդիրներ, որոնք սկզբնական ձևակերպման մեջ գծային չեն, մի շարք լրացուցիչ սահմանափակումներից և ենթադրություններից հետո կարող են դառնալ գծային կամ կրճատվել այն ձևի, որ հնարավոր լինի լուծել գծային ծրագրավորման մեթոդներով:

Ցանկացած գծային ծրագրավորման խնդրի տնտեսական և մաթեմատիկական մոդելը ներառում է. օպտիմալ արժեքորը (առավելագույնը կամ նվազագույնը) պետք է գտնել. սահմանափակումներ համակարգի տեսքով գծային հավասարումներկամ անհավասարություններ; փոփոխականների ոչ բացասականության պահանջը:

IN ընդհանուր տեսարանմոդելը գրված է հետևյալ կերպ.

օբյեկտիվ գործառույթ

(1.1) սահմանափակումներով

(1.2) ոչ բացասական պահանջներ

(1.3) որտեղ x ժ- փոփոխականներ (անհայտ);

- գծային ծրագրավորման խնդրի գործակիցները.

Խնդիրը (1.1) ֆունկցիայի օպտիմալ արժեքը գտնելն է, որը ենթակա է սահմանափակումների (1.2) և (1.3):

Սահմանափակումների համակարգը (1.2) կոչվում է խնդրի ֆունկցիոնալ սահմանափակումներ, իսկ սահմանափակումները (1.3)՝ ուղղակի։

Վեկտորը, որը բավարարում է (1.2) և (1.3) սահմանափակումները, կոչվում է գծային ծրագրավորման խնդրի թույլատրելի լուծում (պլան): Այն պլանը, որի դեպքում (1.1) ֆունկցիան հասնում է իր առավելագույն (նվազագույն) արժեքին, կոչվում է օպտիմալ:

1.2. Գծային ծրագրավորման խնդիրների լուծման պարզ մեթոդ

Սիմպլեքս մեթոդը մշակվել և առաջին անգամ կիրառվել է խնդիրներ լուծելու համար 1947 թվականին ամերիկացի մաթեմատիկոս Ջ.Դանցիգի կողմից։

Երկչափ գծային ծրագրավորման խնդիրները լուծվում են գրաֆիկորեն։ N=3 դեպքի համար կարող ենք դիտարկել եռաչափ տարածությունիսկ օբյեկտիվ ֆունկցիան կհասնի իր օպտիմալ արժեքին պոլիէդրոնի գագաթներից մեկում։

Ստանդարտ ձևով տրված LP խնդրի թույլատրելի լուծումը (թույլատրելի պլանը) սահմանափակումները բավարարող թվերի (x1, x2, ..., xn) դասավորված շարքն է. դա մի կետ է n-չափ տարածության մեջ:

Ընդունելի լուծումների բազմությունը կազմում է ԼՊ խնդրի թույլատրելի լուծումների (ԱԹՍ) շրջանը։ ODR-ը ուռուցիկ բազմանկյուն է (բազմանկյուն):

Ընդհանրապես, երբ խնդիրը ներառում է N-անհայտներ, կարելի է ասել, որ սահմանափակող պայմանների համակարգով սահմանված իրագործելի լուծումների շրջանը ներկայացված է ուռուցիկ բազմանկյունով n-չափ տարածության մեջ և օբյեկտիվ ֆունկցիայի օպտիմալ արժեքը ձեռք է բերվում մեկում: կամ ավելի շատ գագաթներ:

Հիմնական լուծումը լուծում է, որտեղ բոլոր ազատ փոփոխականները հավասար են զրոյի:

Աջակցման լուծումը հիմնական ոչ բացասական լուծում է: Աջակցման լուծումը կարող է լինել ոչ այլասերված և այլասերված: Հղման լուծումը կոչվում է ոչ այլասերված, եթե դրա ոչ զրոյական կոորդինատների թիվը հավասար է համակարգի աստիճանին, հակառակ դեպքում այն ​​այլասերված է:

Թույլատրելի լուծումը, որի դեպքում օբյեկտիվ ֆունկցիան հասնում է իր ծայրահեղ արժեքին, կոչվում է օպտիմալ և նշվում .

Այս խնդիրները գրաֆիկորեն լուծելը շատ դժվար է, երբ փոփոխականների թիվը 3-ից ավելի է։ Գոյություն ունի գծային ծրագրավորման խնդիրների լուծման ունիվերսալ միջոց, որը կոչվում է սիմպլեքս մեթոդ։

Սիմպլեքս մեթոդը LP խնդիրների լուծման ունիվերսալ մեթոդ է, որը կրկնվող գործընթաց է, որը սկսվում է մեկ լուծումից և լավագույն տարբերակի որոնման համար շարժվում է իրագործելի լուծումների շրջանի անկյունային կետերով մինչև այն հասնում է օպտիմալ արժեքին:

Այն կարող է օգտագործվել գծային ծրագրավորման ցանկացած խնդիր լուծելու համար։

Սիմպլեքս մեթոդը հիմնված է ստացված լուծման հաջորդական բարելավման գաղափարի վրա:

Սիմպլեքսի մեթոդի երկրաչափական իմաստը սահմանափակման բազմաեզրության մեկ գագաթից հաջորդական անցում է հարևանին, որի դեպքում օբյեկտիվ ֆունկցիան վերցնում է լավագույն (կամ գոնե ոչ վատագույն) արժեքը, մինչև գտնվի օպտիմալ լուծումը. օպտիմալ արժեքը ձեռք է բերվում նպատակի գործառույթը (եթե խնդիրն ունի վերջնական օպտիմալ):

Այսպիսով, ունենալով կանոնական ձևի իջեցված սահմանափակումների համակարգ (բոլոր ֆունկցիոնալ սահմանափակումներն ունեն հավասարության ձև), նրանք գտնում են այս համակարգի որևէ հիմնարար լուծում՝ հոգալով միայն այն հնարավորինս պարզ գտնելու մասին: Եթե ​​հայտնաբերված առաջին հիմնարար լուծումը պարզվում է, որ իրագործելի է, ապա այն ստուգվում է օպտիմալության համար: Եթե ​​դա օպտիմալ չէ, ապա անցում է կատարվում մեկ այլ, պարտադիր թույլատրելի, հիմնարար լուծման։ Սիմպլեքս մեթոդը երաշխավորում է, որ այս նոր լուծումով օբյեկտիվ ֆունկցիան, եթե չհասնի օպտիմալին, կմոտենա դրան (կամ գոնե չի հեռանա դրանից): Նույնը արվում է նոր իրագործելի հիմնային լուծույթով, մինչև գտնվի օպտիմալ լուծում:

Սիմպլեքս մեթոդի կիրառման գործընթացը ներառում է դրա երեք հիմնական տարրերի իրականացումը.

խնդրի ցանկացած նախնական իրագործելի հիմնարար լուծում որոշելու մեթոդ.

լավագույն (ավելի ճիշտ, ոչ ավելի վատ) լուծմանն անցնելու կանոնը.

Գտնված լուծման օպտիմալությունը ստուգելու չափանիշ:

Սիմպլեքս մեթոդը ներառում է մի շարք փուլեր և կարող է ձևակերպվել հստակ ալգորիթմի տեսքով (հաջորդական գործողություններ կատարելու հստակ հրահանգ): Սա թույլ է տալիս հաջողությամբ ծրագրավորել և իրականացնել այն համակարգչում: Փոքր թվով փոփոխականների և սահմանափակումների հետ կապված խնդիրները կարող են լուծվել ձեռքով` օգտագործելով simplex մեթոդը:

6.1.Ներածություն

Օպտիմալացում. Մաս 1

Օպտիմալացման մեթոդները թույլ են տալիս ընտրել լավագույն տարբերակդիզայն բոլորից հնարավոր տարբերակները. IN վերջին տարիներըտրվել են այս մեթոդները մեծ ուշադրություն, և արդյունքում մշակվեցին մի շարք բարձր արդյունավետության ալգորիթմներ, որոնք հնարավորություն են տալիս համակարգչի միջոցով գտնել դիզայնի օպտիմալ տարբերակը։ Այս գլուխը ուրվագծում է օպտիմալացման տեսության հիմունքները, ուսումնասիրում է օպտիմալ լուծումների համար ալգորիթմների կառուցման հիմքում ընկած սկզբունքները, նկարագրում է ամենահայտնի ալգորիթմները և վերլուծում դրանց առավելություններն ու թերությունները:

6.2.Օպտիմալացման տեսության հիմունքներ

Գրականության մեջ «օպտիմալացում» տերմինը վերաբերում է գործողությունների գործընթացին կամ հաջորդականությանը, որը թույլ է տալիս ստանալ հստակ լուծում: Թեև օպտիմալացման վերջնական նպատակը լավագույն կամ «օպտիմալ» լուծումը գտնելն է, սովորաբար պետք է բավարարվել հայտնի լուծումների բարելավմամբ, այլ ոչ թե կատարելագործելով դրանք: Հետևաբար, օպտիմիզացիան ավելի շուտ ընկալվում է որպես կատարելության ցանկություն, որին հնարավոր չէ հասնել:

Հաշվի առնելով որոշ կամայական համակարգեր, որոնք նկարագրված են m հավասարումներով n անհայտներով, մենք կարող ենք առանձնացնել խնդիրների երեք հիմնական տեսակ: Եթե ​​m=n խնդիրը կոչվում է հանրահաշվական։ Այս խնդիրը սովորաբար ունի մեկ լուծում. Եթե ​​m>n, ապա խնդիրը գերորոշված ​​է և, որպես կանոն, լուծում չունի։ Վերջապես, մ

Նախքան օպտիմալացման հարցերի քննարկումը սկսելը, մենք ներկայացնում ենք մի շարք սահմանումներ:

Դիզայնի պարամետրեր

Այս տերմինը նշանակում է անկախ փոփոխական պարամետրեր, որոնք ամբողջությամբ և միանշանակորեն որոշում են լուծվող նախագծային խնդիրը: Դիզայնի պարամետրերը անհայտ մեծություններ են, որոնց արժեքները հաշվարկվում են օպտիմալացման գործընթացում: Ցանկացած հիմնական կամ ածանցյալ մեծություններ, որոնք ծառայում են համակարգի քանակական նկարագրությանը, կարող են ծառայել որպես նախագծման պարամետրեր: Այո, դա կարող է լինել անհայտ արժեքներերկարությունը, զանգվածը, ժամանակը, ջերմաստիճանը: Դիզայնի պարամետրերի քանակը բնութագրում է տվյալ նախագծային խնդրի բարդության աստիճանը: Սովորաբար նախագծման պարամետրերի թիվը նշվում է n-ով, իսկ նախագծման պարամետրերն իրենք՝ x-ով՝ համապատասխան ինդեքսներով: Այսպիսով, այս խնդրի n նախագծային պարամետրերը կնշանակվեն

X1, x2, x3, ..., xn.

Օբյեկտիվ ֆունկցիա

Դա արտահայտություն է, որի արժեքը ինժեները ձգտում է առավելագույնը կամ նվազագույնը դարձնել: Օբյեկտիվ ֆունկցիան թույլ է տալիս քանակապես համեմատել երկու այլընտրանքային լուծումներ։ Մաթեմատիկական տեսանկյունից օբյեկտիվ ֆունկցիան նկարագրում է որոշ (n+1)-չափ մակերեսներ։ Դրա արժեքը որոշվում է դիզայնի պարամետրերով

M=M(x 1, x 2,...,x n):

Ինժեներական պրակտիկայում հաճախ հանդիպող օբյեկտիվ գործառույթների օրինակներն են՝ ծախսը, քաշը, ուժը, չափերը, արդյունավետությունը: Եթե ​​կա միայն մեկ նախագծային պարամետր, ապա օբյեկտիվ ֆունկցիան կարելի է ներկայացնել հարթության վրա կորով (նկ. 6.1): Եթե ​​կան նախագծման երկու պարամետր, ապա օբյեկտիվ ֆունկցիան կպատկերվի որպես մակերես եռաչափ տարածության մեջ (նկ. 6.2): Երեք կամ ավելի դիզայնի պարամետրերով, օբյեկտիվ ֆունկցիայի կողմից նշված մակերեսները կոչվում են հիպերմակերևույթներ և չեն կարող պատկերվել:

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

Օբյեկտիվ ֆունկցիան որոշ դեպքերում կարող է ընդունել ամենաանսպասելի ձևերը։ Օրինակ, միշտ չէ, որ հնարավոր է դա արտահայտել

Նկ. 1. Միաչափ օբյեկտիվ ֆունկցիա:

Նկար 6.2 Երկչափ օբյեկտիվ ֆունկցիա:

փակ մաթեմատիկական ձև, այլ դեպքերում կարող է

ներկայացնում է հատվածական հարթ ֆունկցիա: Օբյեկտիվ ֆունկցիան նշելու համար երբեմն կարող է պահանջվել տեխնիկական տվյալների աղյուսակ (օրինակ՝ ջրի գոլորշիների վիճակի աղյուսակ) կամ կարող է պահանջվել փորձ: Որոշ դեպքերում նախագծման պարամետրերը վերցնում են միայն ամբողջական արժեքներ: Օրինակ կարող է լինել ատամների քանակը հանդերձում փոխանցումկամ եզրի պտուտակների քանակը: Երբեմն դիզայնի պարամետրերը միայն երկու նշանակություն ունեն՝ այո կամ ոչ: Որակական պարամետրերը, ինչպիսիք են ապրանքը գնած գնորդի գոհունակությունը, հուսալիությունը, գեղագիտությունը, դժվար է հաշվի առնել օպտիմալացման գործընթացում, քանի որ դրանք քանակականորեն բնութագրելը գրեթե անհնար է: Այնուամենայնիվ, անկախ նրանից, թե ինչպես է ներկայացվում օբյեկտիվ գործառույթը, այն պետք է լինի դիզայնի պարամետրերի միանշանակ գործառույթ:

Օպտիմալացման մի շարք խնդիրներ պահանջում են մեկից ավելի օբյեկտիվ ֆունկցիաների ներդրում: Երբեմն նրանցից մեկը կարող է անհամատեղելի լինել մյուսի հետ։ Օրինակ է ինքնաթիռի դիզայնը, որտեղ միաժամանակ պահանջվում են առավելագույն ուժ, նվազագույն քաշ և նվազագույն ծախսեր: Նման դեպքերում նախագծողը պետք է ներդնի առաջնահերթությունների համակարգ և յուրաքանչյուր օբյեկտիվ ֆունկցիայի նշանակի որոշակի չափազերծող բազմապատկիչ: Արդյունքում հայտնվում է «փոխզիջումային ֆունկցիա», որը թույլ է տալիս օպտիմալացման գործընթացում օգտագործել մեկ կոմպոզիտային օբյեկտիվ ֆունկցիա:

Գտեք նվազագույնը և առավելագույնը

Որոշ օպտիմալացման ալգորիթմներ նախատեսված են առավելագույնը գտնելու համար, մյուսները՝ նվազագույնը: Այնուամենայնիվ, անկախ լուծվող ծայրահեղ խնդրի տեսակից, դուք կարող եք օգտագործել նույն ալգորիթմը, քանի որ նվազագույնի հասցնելու խնդիրը հեշտությամբ կարող է վերածվել առավելագույն որոնման խնդրի՝ հակադարձելով օբյեկտիվ ֆունկցիայի նշանը: Այս տեխնիկան ներկայացված է Նկար 6.3-ում:

Դիզայնի տարածք

Սա այն տարածքի անվանումն է, որը սահմանված է բոլոր n դիզայնի պարամետրերով: Դիզայնի տարածքը այնքան էլ մեծ չէ, որքան կարող է թվալ, քանի որ այն սովորաբար սահմանափակվում է մի շարքով

պայմաններ՝ կապված խնդրի ֆիզիկական էության հետ. Սահմանափակումները կարող են այնքան ուժեղ լինել, որ խնդիրը չի ունենա

Նկ.6.3.Օբյեկտիվ ֆունկցիայի նշանը փոխելով հակառակի

առավելագույն առաջադրանքը վերածվում է նվազագույն առաջադրանքի։

բավարար լուծում. Սահմանափակումները բաժանվում են երկու խմբի՝ սահմանափակումներ՝ հավասարություն և սահմանափակումներ՝ անհավասարություն։

Սահմանափակումներ - Հավասարություններ

Սահմանափակումները՝ հավասարությունները, նախագծային պարամետրերի միջև կախվածությունն է, որը պետք է հաշվի առնել լուծում գտնելիս: Դրանք արտացոլում են բնության, տնտեսագիտության, իրավունքի, գերակշռող ճաշակի և մատչելիության օրենքները անհրաժեշտ նյութեր. Սահմանափակումների քանակը - հավասարությունները կարող են լինել ցանկացած: Նրանք նման են

C 1 (x 1, x 2,..., x n)=0,

C 2 (x 1, x 2,..., x n)=0,

..................

C j (x 1, x 2,...,x n)=0:

Եթե ​​այս հարաբերություններից որևէ մեկը կարող է լուծվել նախագծման պարամետրերից մեկի նկատմամբ, ապա դա թույլ է տալիս այս պարամետրը բացառել օպտիմալացման գործընթացից: Սա նվազեցնում է դիզայնի տարածքի չափսերը և հեշտացնում խնդրի լուծումը:

Սահմանափակումներ - անհավասարություններ

Սա սահմանափակումների հատուկ տեսակ է, որն արտահայտվում է անհավասարություններով: Ընդհանրապես, դրանք կարող են լինել այնքան, որքան ցանկանում եք, և նրանք բոլորն ունեն ձևը

z 1 r 1 (x 1, x 2,..., x n) Z 1

z 2 r 2 (x 1, x 2,..., x n) Z 2

.......................

z k r k (x 1 , x 2 ,...,x n) Z k

Հարկ է նշել, որ շատ հաճախ, սահմանափակումների պատճառով, օբյեկտիվ ֆունկցիայի օպտիմալ արժեքը ձեռք է բերվում ոչ այնտեղ, որտեղ դրա մակերեսը ունի զրոյական գրադիենտ: Հաճախ լավագույն լուծումը համապատասխանում է դիզայնի տարածքի սահմաններից մեկին:

Տեղական օպտիմալ

Սա նախագծային տարածության այն կետի անվանումն է, որտեղ ունի օբյեկտիվ ֆունկցիան ամենաբարձր արժեքըհամեմատած դրա արժեքների հետ իր անմիջական հարևանությամբ գտնվող բոլոր մյուս կետերում:

Նկ. 6.4. Կամայական օբյեկտիվ ֆունկցիան կարող է ունենալ մի քանիսը

տեղական օպտիմա.

Նկ. Նկար 6.4-ը ցույց է տալիս միաչափ օբյեկտիվ ֆունկցիա, որն ունի երկու տեղային օպտիմա: Հաճախ նախագծային տարածքը պարունակում է բազմաթիվ լոկալ օպտիմա, և պետք է ուշադրություն դարձնել, որպեսզի առաջինը չշփոթվի որպես խնդրի օպտիմալ լուծում:

Համաշխարհային օպտիմալ

Գլոբալ օպտիմալը օպտիմալ լուծում է դիզայնի ողջ տարածքի համար: Դա ավելի լավ է, քան բոլոր այլ լուծումները, որոնք համապատասխանում են տեղական optima-ին, և դա այն է, ինչ փնտրում է դիզայները: Հնարավոր է, որ կան մի քանի հավասար գլոբալ օպտիմա, որոնք տեղակայված են տարբեր մասերդիզայնի տարածք. Ինչպես է դրված օպտիմալացման խնդիրը, լավագույնս երևում է օրինակով:

Օրինակ 6.1

Ենթադրենք, պետք է նախագծել 1 մ ծավալով ուղղանկյուն տարա, որը նախատեսված է չփաթեթավորված մանրաթել տեղափոխելու համար։ Ցանկալի է, որ հնարավորինս քիչ նյութ ծախսվի նման տարաների արտադրության վրա (ենթադրելով մշտական ​​պատի հաստություն, դա նշանակում է, որ մակերեսը պետք է լինի նվազագույն), քանի որ այն ավելի էժան կլինի: Որպեսզի բեռնարկղը հարմար կերպով վերցվի բեռնատարով, դրա լայնությունը պետք է լինի առնվազն 1,5 մ:

Եկեք այս խնդիրը ձևակերպենք օպտիմալացման ալգորիթմը կիրառելու համար հարմար ձևով:

Դիզայնի պարամետրերը `x 1, x 2, x 3:

Օբյեկտիվ գործառույթը (որը պետք է նվազագույնի հասցվի) տարայի կողային մակերեսի տարածքն է.

A=2(x 1 x 2 +x 2 x 3 +x 1 x 3), m2:

Սահմանափակում - հավասարություն.

Ծավալը = x 1 x 2 x 3 = 1 մ 3:

Սահմանափակում - անհավասարություն.

Գծային ծրագրավորման խնդիրներ

Գծային ծրագրավորում (LP)մաթեմատիկական ծրագրավորման ճյուղերից մեկն է - դիսցիպլին, որն ուսումնասիրում է էքստրեմալ (օպտիմալացման) խնդիրները և մշակում դրանց լուծման մեթոդներ։

Օպտիմալացման խնդիրմաթեմատիկական խնդիր է, որը բաղկացած է նպատակային ֆունկցիայի օպտիմալ (այսինքն՝ առավելագույն կամ նվազագույն) արժեքը գտնելուց, իսկ փոփոխականների արժեքները պետք է պատկանեն ընդունելի արժեքների որոշակի տիրույթին (APV):

Ընդհանուր առմամբ, մաթեմատիկական ծրագրավորման էքստրեմալ խնդրի ձևակերպումը բաղկացած է ամենամեծ կամ ամենացածր արժեքըֆունկցիան կանչված է թիրախային գործառույթ, պայմաններում (սահմանափակումներ), որտեղ և տրվում են ֆունկցիաներ, և տրվում են հաստատուն արժեքներ։ Այս դեպքում հավասարությունների և անհավասարությունների ձևով սահմանափակումները որոշում են թույլատրելի լուծումների բազմությունը (տարածքը) և կոչվում են. նախագծման պարամետրեր.

Կախված ֆունկցիաների տեսակից՝ մաթեմատիկական ծրագրավորման խնդիրները բաժանվում են մի շարք դասերի (գծային, ոչ գծային, ուռուցիկ, ամբողջ թիվ, ստոխաստիկ, դինամիկ ծրագրավորում և այլն)։

IN ընդհանուր տեսարան LP խնդիրն ունի հետևյալ ձևը.

, (5.1)

, , (5.2)

, , (5.3)

որտեղ , , տրվում են հաստատուն արժեքներ:

Ֆունկցիան (5.1) կոչվում է օբյեկտիվ ֆունկցիա. համակարգեր (5.2), (5.3) – սահմանափակումների համակարգ. պայման (5.4) – նախագծային պարամետրերի ոչ բացասական լինելու պայման:

Սահմանափակումները (5.2), (5.3) և (5.4) բավարարող նախագծային պարամետրերի բազմությունը կոչվում է. ընդունելի լուծումկամ պլան.

Օպտիմալ լուծումկամ օպտիմալ պլան LP խնդիրը կոչվում է թույլատրելի լուծում, որի դեպքում օբյեկտիվ ֆունկցիան (5.1) վերցնում է օպտիմալ (առավելագույն կամ նվազագույն) արժեքը:

Ստանդարտ առաջադրանք LP-ն օբյեկտիվ ֆունկցիայի (5.1) առավելագույն (նվազագույն) արժեքը գտնելու խնդիրն է (5.2) և (5.4) պայմաններում, որտեղ , , այսինքն. դրանք. սահմանափակումները միայն անհավասարությունների ձևով (5.2) և նախագծման բոլոր պարամետրերը բավարարում են ոչ բացասականության պայմանը, և հավասարությունների տեսքով պայմաններ չկան.

,

, , (5.5)

.

Կանոնական (հիմնական) առաջադրանք LP-ն օբյեկտիվ ֆունկցիայի (5.1) առավելագույն (նվազագույն) արժեքը գտնելու խնդիրն է (5.3) և (5.4) պայմաններում, որտեղ , , այսինքն. դրանք. սահմանափակումները միայն հավասարումների տեսքով (5.3) և նախագծման բոլոր պարամետրերը բավարարում են ոչ բացասականության պայմանը, և անհավասարությունների տեսքով պայմաններ չկան.

,

.

Կանոնական LP խնդիրը կարող է գրվել նաև մատրիցային և վեկտորային ձևով:

Կանոնական LP խնդրի մատրիցային ձևն ունի հետևյալ ձևը.

Կանոնական LP խնդրի վեկտորային ձևը.

Եկեք հարթության վրա կառուցենք գծային անհավասարությունների համակարգի իրագործելի լուծումների մի շարք և երկրաչափորեն գտնենք օբյեկտիվ ֆունկցիայի նվազագույն արժեքը:

Մենք ուղիղ գծեր ենք կառուցում x 1 x 2 կոորդինատային համակարգում

Մենք գտնում ենք համակարգի կողմից սահմանված կիսահարթությունները։ Քանի որ համակարգի անհավասարությունները բավարարվում են համապատասխան կիսահարթության ցանկացած կետի համար, բավական է դրանք ստուգել ցանկացած մեկ կետի համար։ Մենք օգտագործում ենք կետը (0;0): Փոխարինենք դրա կոորդինատները համակարգի առաջին անհավասարության մեջ: Որովհետեւ , ապա անհավասարությունը սահմանում է կիսահարթություն, որը չի պարունակում (0;0) կետը։ Մենք նմանապես սահմանում ենք մնացած կիսալեզուները: Մենք գտնում ենք իրագործելի լուծումների հավաքածուն, որպես ստացված կիսահրթիռների ընդհանուր մաս. սա ստվերված տարածքն է:

Մենք կառուցում ենք վեկտոր և զրոյական մակարդակի ուղիղ նրան ուղղահայաց:

Շարժվելով ուղիղ գիծը (5) վեկտորի ուղղությամբ և տեսնում ենք, որ շրջանի առավելագույն կետը կլինի ուղիղ (3) և ուղիղ գծի (2) հատման A կետում: Մենք գտնում ենք հավասարումների համակարգի լուծումը.

Սա նշանակում է, որ մենք ստացել ենք կետը (13;11) և.

Շարժվելով ուղիղ գիծը (5) վեկտորի ուղղությամբ և տեսնում ենք, որ շրջանի նվազագույն կետը կլինի ուղիղ (1) և ուղիղ գծի (4) հատման B կետում: Մենք գտնում ենք հավասարումների համակարգի լուծումը.

Սա նշանակում է, որ մենք ստացել ենք կետը (6;6) և.

2. Կահույքի ընկերությունը արտադրում է համակցված պահարաններ և համակարգչային սեղաններ: Դրանց արտադրությունը սահմանափակվում է հումքի (բարձրորակ տախտակներ, կցամասեր) առկայությամբ և դրանք մշակող մեքենաների գործարկման ժամանակով։ Յուրաքանչյուր պահարանի համար պահանջվում է 5 մ2 տախտակ, սեղանի համար՝ 2 մ2։ Կցամասերն արժեն 10 դոլար մեկ պահարանի համար, իսկ 8 դոլար մեկ սեղանի համար: Ընկերությունն իր մատակարարներից կարող է ստանալ ամսական մինչև 600 մ2 տախտակ և 2000 դոլար արժողությամբ պարագաներ։ Յուրաքանչյուր պահարան պահանջում է 7 ժամ մեքենայի շահագործում, իսկ սեղանին` 3 ժամ: Ամսական կարող է օգտագործվել ընդհանուր առմամբ 840 մեքենաների աշխատանքային ժամ:

Քանի՞ համակցված պահարան և համակարգչային սեղան պետք է արտադրի ընկերությունը ամսական շահույթը առավելագույնի հասցնելու համար, եթե մեկ կաբինետը բերում է $100 շահույթ, իսկ յուրաքանչյուր գրասեղանը՝ $50:

• 1. Կազմել մաթեմատիկական մոդելխնդիրը և լուծել այն՝ օգտագործելով simplex մեթոդը:
• 2. Ստեղծի՛ր երկակի խնդրի մաթեմատիկական մոդել, գրի՛ր դրա լուծումը՝ հիմնվելով սկզբնականի լուծման վրա:
• 3. Սահմանել օգտագործվող ռեսուրսների սակավության աստիճանը և հիմնավորել օպտիմալ պլանի շահութաբերությունը:
• 4. Հետազոտել արտադրական արտադրանքի հետագա ավելացման հնարավորությունները՝ կախված յուրաքանչյուր տեսակի ռեսուրսի օգտագործումից:
• 5. Գնահատեք ապրանքի նոր տեսակի՝ գրադարակների ներդրման իրագործելիությունը, եթե մեկ դարակի արտադրությունն արժե 1 մ 2 տախտակներ և աքսեսուարներ 5 դոլար արժողությամբ, և անհրաժեշտ է ծախսել 0,25 ժամ մեքենայի շահագործման և վաճառքից ստացված շահույթը։ մեկ դարակը 20 դոլար է։
• 1. Եկեք այս խնդրի համար կառուցենք մաթեմատիկական մոդել.

x 1-ով նշանակենք պահարանների արտադրության ծավալը, իսկ x 2-ով՝ սեղանների արտադրության ծավալը։ Եկեք ստեղծենք սահմանափակումների համակարգ և նպատակային գործառույթ.

Մենք խնդիրը լուծում ենք սիմպլեքս մեթոդով։ Գրենք այն կանոնական ձևով.

Առաջադրանքի տվյալները գրենք աղյուսակի տեսքով.

Աղյուսակ 1

Որովհետեւ Այժմ բոլոր դելտաները զրոյից մեծ են, ապա նպատակային ֆունկցիայի արժեքի հետագա աճն անհնար է, և մենք ստացել ենք օպտիմալ պլան:

Ներածություն

Մարդկային զարգացման ներկա փուլն առանձնանում է նրանով, որ էներգիայի դարաշրջանը փոխարինվում է համակարգչային գիտության դարով։ Կատարվում է նոր տեխնոլոգիաների ինտենսիվ ներդրում մարդկային գործունեության բոլոր ոլորտներում։ Տեղեկատվական հասարակությանն անցնելու իրական խնդիր կա, որի համար կրթության զարգացումը պետք է առաջնահերթություն դառնա։ Փոխվում է նաև հասարակության մեջ գիտելիքի կառուցվածքը։ Ավելի ու ավելի կարևոր է գործնական կյանքձեռք բերել հիմնարար գիտելիքներ, որոնք նպաստում են անհատի ստեղծագործական զարգացմանը. Կարևոր է նաև ձեռք բերված գիտելիքների կառուցողականությունը և այն նպատակին համապատասխան կառուցապատելու ունակությունը։ Գիտելիքի հիման վրա ձևավորվում են նորերը տեղեկատվական ռեսուրսներհասարակությունը։ Նոր գիտելիքների ձևավորումն ու ձեռքբերումը պետք է հիմնված լինի համակարգային մոտեցման խիստ մեթոդաբանության վրա, որի շրջանակներում առանձնահատուկ տեղ է զբաղեցնում մոդելային մոտեցումը։ Մոդելային մոտեցման հնարավորությունները չափազանց բազմազան են ինչպես կիրառվող ֆորմալ մոդելների, այնպես էլ մոդելավորման մեթոդների կիրառման մեթոդների առումով։ Ֆիզիկական մոդելավորումը թույլ է տալիս հուսալի արդյունքներ ստանալ բավականին պարզ համակարգերի համար:

Ներկայումս անհնար է անվանել մարդկային գործունեության մի ոլորտ, որտեղ մոդելավորման մեթոդներն այս կամ այն ​​չափով չեն կիրառվի: Սա հատկապես ճիշտ է կառավարման ոլորտում տարբեր համակարգեր, որտեղ հիմնական գործընթացները ստացված տեղեկատվության հիման վրա որոշումների կայացումն է։

1. Խնդրի հայտարարություն

նվազագույն նպատակային գործառույթ

Լուծման բազմանկյունով սահմանված սահմանափակումների համակարգի համար օբյեկտիվ ֆունկցիայի նվազագույնի գտնելու խնդիրը լուծել առաջադրանքի թիվ 16 տարբերակին համապատասխան։ Լուծման բազմանկյունը ներկայացված է Նկար 1-ում.

Նկար 1 - Խնդրի լուծումների բազմանկյուն

Սահմանափակումների համակարգը և խնդրի օբյեկտիվ գործառույթը ներկայացված են ստորև.

Անհրաժեշտ է խնդիրը լուծել հետևյալ մեթոդներով.

LP խնդիրների լուծման գրաֆիկական մեթոդ;

LP խնդիրների լուծման հանրահաշվական մեթոդ;

LP խնդիրների լուծման պարզ մեթոդ;

LP խնդիրների թույլատրելի լուծում գտնելու մեթոդ;

Երկակի LP խնդրի լուծում;

Ամբողջ թվով LP խնդիրների լուծման ճյուղային և կապող մեթոդ;

Գոմորի մեթոդ ամբողջ LP խնդիրների լուծման համար;

Բուլյան LP խնդիրների լուծման Բալազի մեթոդ.

Համեմատեք լուծման արդյունքները տարբեր մեթոդներհամապատասխան եզրակացություններ անել աշխատանքից.

2. Գծային ծրագրավորման խնդրի գրաֆիկական լուծում

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

Բրինձ. 2 LP խնդրի գրաֆիկական լուծում

Նվազագույն միավոր

A1 և A2 երկու կետերով անցնող ուղիղի հավասարումը.

AB: (0;1); (3;3)

VS: (3;3); (4;1)

CD: (4;1); (3;0)

EA: (1;0); (0;1)

CF: (0;1); (5;2)

սահմանափակումներով.

Գծային ծրագրավորման խնդրի լուծում հանրահաշվական սիմպլեքս մեթոդով

Խնդիր լուծելու հանրահաշվական մեթոդի կիրառումը պահանջում է LP խնդրի ներկայացման ընդհանրացում։ Սահմանափակումների սկզբնական համակարգը, որը նշված է անհավասարությունների տեսքով, փոխակերպվում է ստանդարտ նշումի, երբ սահմանափակումները նշված են հավասարումների տեսքով: Սահմանափակման համակարգի փոխակերպումը դեպի ստանդարտ տեսքներառում է հետևյալ քայլերը.

Անհավասարությունները փոխակերպե՛ք այնպես, որ ձախ կողմում լինեն փոփոխականներ և ազատ անդամներ, իսկ աջում՝ 0, այսինքն. դեպի ձախ կողմմեծ էր կամ հավասար էր զրոյի;

Ներդրեք լրացուցիչ փոփոխականներ, որոնց թիվը հավասար է սահմանափակումների համակարգի անհավասարությունների թվին.

Ավելացված փոփոխականների ոչ բացասականության վերաբերյալ լրացուցիչ սահմանափակումներ մտցնելով, անհավասարության նշանները փոխարինեք խիստ հավասարության նշաններով։

Հանրահաշվական մեթոդով LP խնդիր լուծելիս ավելացվում է պայման՝ նպատակային ֆունկցիան պետք է ձգտի նվազագույնի։ Եթե այս պայմանըբավարարված չէ, անհրաժեշտ է համապատասխանաբար վերափոխել օբյեկտիվ ֆունկցիան (բազմապատկել -1-ով) և լուծել նվազագույնի հասցնելու խնդիրը։ Լուծումը գտնելուց հետո փոփոխականների արժեքները փոխարինեք սկզբնական ֆունկցիայի մեջ և հաշվարկեք դրա արժեքը:

Հանրահաշվական մեթոդով խնդրի լուծումը համարվում է օպտիմալ, երբ բոլոր հիմնական փոփոխականների արժեքները ոչ բացասական են, իսկ օբյեկտիվ ֆունկցիայի հավասարման ազատ փոփոխականների գործակիցները նույնպես ոչ բացասական են: Եթե ​​այս պայմանները չկատարվեն, ապա անհրաժեշտ է վերափոխել անհավասարությունների համակարգը՝ որոշ փոփոխականներ արտահայտելով մյուսներով (փոխելով ազատ և հիմնական փոփոխականները), որպեսզի հասնենք վերը նշված սահմանափակումների կատարմանը: Բոլոր ազատ փոփոխականների արժեքը համարվում է հավասար զրոյի:

Գծային ծրագրավորման խնդիրների լուծման հանրահաշվական մեթոդը ամենաշատերից է արդյունավետ մեթոդներփոքրածավալ խնդիրներ ձեռքով լուծելիս, քանի որ չի պահանջում մեծ թվով թվաբանական հաշվարկներ. Այս մեթոդի մեքենայական իրականացումը ավելի բարդ է, քան, օրինակ, սիմպլեքս մեթոդի համար, քանի որ Հանրահաշվական մեթոդով լուծման ալգորիթմը որոշ չափով էվրիստիկ է և լուծման արդյունավետությունը մեծապես կախված է անձնական փորձից:

Ազատ փոփոխականներ

Սբ - լրացուցիչ հավաքածու

Ոչ բացասական պայմանները բավարարված են, հետևաբար՝ գտնվել է օպտիմալ լուծում։

3. Գծային ծրագրավորման խնդրի լուծում սիմպլեքս աղյուսակի միջոցով

Լուծում. Սիմպլեքս աղյուսակի միջոցով խնդիրը բերենք ստանդարտ ձևի լուծման:

Եկեք կրճատենք համակարգի բոլոր հավասարումները հետևյալ ձևի.

Մենք կառուցում ենք սիմպլեքս աղյուսակ.

Աղյուսակի յուրաքանչյուր բջիջի վերին անկյունում մենք մուտքագրում ենք գործակիցները հավասարումների համակարգից.

Մենք ընտրում ենք առավելագույն դրական տարրը F տողում, բացառությամբ, որ սա կլինի ընդհանուր սյունակը.

Ընդհանուր տարրը գտնելու համար մենք հարաբերություններ ենք կառուցում բոլոր դրականների համար։ 3/3; 9/1;- նվազագույն հարաբերակցությունը x3 տողում: Հետևաբար՝ ընդհանուր տողը և =3՝ ընդհանուր տարրը։

Մենք գտնում ենք =1/=1/3: Մենք այն բերում ենք բջիջի ստորին անկյունում, որտեղ գտնվում է ընդհանուր տարրը.

Ընդհանուր գծի բոլոր դատարկ ստորին անկյուններում մենք մուտքագրում ենք բջիջի վերին անկյունում գտնվող արժեքի արտադրյալը.

Ընտրեք ընդհանուր գծի վերին անկյունները;

Ընդհանուր սյունակի բոլոր ստորին անկյուններում մենք մուտքագրում ենք վերին անկյունում գտնվող արժեքի արտադրյալը - և ընտրում ենք ստացված արժեքները.

Աղյուսակի մնացած բջիջները լրացվում են որպես համապատասխան ընտրված տարրերի արտադրյալներ.

Այնուհետև մենք կառուցում ենք նոր աղյուսակ, որում փոխվում են ընդհանուր սյունակի և տողի տարրերի բջիջների նշանակումները (x2 և x3);

Այն արժեքները, որոնք նախկինում եղել են ստորին անկյունում, գրված են նախկին ընդհանուր տողի և սյունակի վերին անկյունում.

Նախորդ աղյուսակում այս բջիջների վերին և ստորին անկյունների արժեքների գումարը գրված է մնացած բջիջների վերին անկյունում:

4. Գծային ծրագրավորման խնդրի լուծում՝ թույլատրելի լուծում գտնելով

Թող տրվի գծային հանրահաշվական հավասարումների համակարգ.

Կարելի է ենթադրել, որ ամեն ինչ կա, հակառակ դեպքում համապատասխան հավասարումը բազմապատկում ենք -1-ով։

Մենք ներկայացնում ենք օժանդակ փոփոխականներ.

Ներկայացնում ենք նաև օժանդակ գործառույթ

Մենք նվազագույնի կհասցնենք համակարգը սահմանափակումների (2) և պայմանների ներքո:

ԹՈՒՅԼԱՏԱՐ ԼՈՒԾՈՒՄ ԳՏՆԵԼՈՒ ԿԱՆՈՆ. (1) համակարգի համար ընդունելի լուծում գտնելու համար մենք նվազագույնի ենք հասցնում (3) ձևը (2), ընդունելով xj-ը որպես ազատ անհայտ և xj-ին որպես հիմք ընդունելով:

Սիմպլեքս մեթոդով խնդիր լուծելիս կարող է առաջանալ երկու դեպք.

min f=0, ապա ամբողջ i-ը պետք է հավասար լինի զրոյի: Եվ xj-ի ստացված արժեքները կկազմեն համակարգի թույլատրելի լուծում (1):

min f>0, այսինքն. սկզբնական համակարգը իրագործելի լուծում չունի։

Աղբյուրի համակարգ.

Օգտագործված է խնդրի պայմանը նախորդ թեմայից։

Ներկայացնենք լրացուցիչ փոփոխականներ.

Գտնվել է սկզբնական խնդրի թույլատրելի լուծում՝ x1 = 3, x2 = 3, F = -12: Ստացված իրագործելի լուծման հիման վրա մենք կգտնենք սկզբնական խնդրի օպտիմալ լուծումը սիմպլեքս մեթոդով։ Դա անելու համար մենք վերը ստացված աղյուսակից կկառուցենք նոր սիմպլեքս աղյուսակ՝ հեռացնելով օժանդակ խնդրի թիրախային ֆունկցիայով տողը և տողը.

Կառուցված սիմպլեքս աղյուսակը վերլուծելով՝ տեսնում ենք, որ սկզբնական խնդրի օպտիմալ լուծումն արդեն գտնվել է (օբյեկտիվ ֆունկցիային համապատասխանող շարքի տարրերը բացասական են)։ Այսպիսով, օժանդակ խնդիրը լուծելիս հայտնաբերված իրագործելի լուծումը համընկնում է սկզբնական խնդրի օպտիմալ լուծման հետ.

6. Երկակի գծային ծրագրավորման խնդիր

Սահմանափակումների սկզբնական համակարգը և խնդրի օբյեկտիվ գործառույթը ներկայացված են ստորև նկարում:

սահմանափակումներով.

Լուծում. Եկեք սահմանափակումների համակարգը բերենք ստանդարտ ձևի.

Այս խնդրի կրկնակի խնդիրը կունենա հետևյալ ձևը.

Երկակի խնդրի լուծումը կկատարվի պարզ սիմպլեքս մեթոդով։

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

y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)

y7 = 5 - (-3y1 - y2 + y3 + y4)

Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ??min

Եկեք կառուցենք նախնական սիմպլեքս աղյուսակ երկակի LP խնդիրը լուծելու համար:

Սիմպլեքս մեթոդի երկրորդ քայլը

Այսպիսով, սիմպլեքս մեթոդի երրորդ քայլում նվազագույնի հասցնելու խնդրի օպտիմալ լուծումը գտնվեց հետևյալ արդյունքներով. y2 = -7 /8, y1 = -11/8, Ф = 12: երկակի խնդրի օբյեկտիվ ֆունկցիան, մենք հիմնական և ազատ փոփոխականների գտած արժեքները փոխարինում ենք առավելագույնի հասցնելու ֆունկցիայի մեջ.

Фmax = - Фmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12

Քանի որ ուղիղ և երկակի խնդիրների օբյեկտիվ ֆունկցիայի արժեքը համընկնում է, ուղղակի խնդրի լուծումը գտնված է և հավասար է 12-ի։

Fmin = Фmax = -12

7. Ամբողջ թվով գծային ծրագրավորման խնդրի լուծում՝ ճյուղային և կապող մեթոդով

Եկեք վերափոխենք սկզբնական խնդիրը այնպես, որ սովորական մեթոդներով լուծելիս ամբողջ թվի պայմանը չբավարարվի:

Ամբողջ թվային ծրագրավորման խնդրի լուծումների սկզբնական բազմանկյուն:

Լուծումների փոխակերպված բազմանկյունի համար մենք կառուցում ենք նոր համակարգսահմանափակումներ.

Գրենք սահմանափակումների համակարգը հավասարումների տեսքով, որոնք պետք է լուծվեն հանրահաշվական մեթոդով։

Լուծման արդյունքում գտնվել է խնդրի օպտիմալ պլանը՝ x1 = 9/4, x2 = 5/2, F = -41/4: Այս լուծումը չի համապատասխանում խնդրի ամբողջ թվի պայմանին: Բաժանենք սկզբնական լուծման բազմանկյունը երկու տարածքի` դրանից բացառելով 3-րդ տարածքը

Փոփոխված խնդրի լուծման բազմանկյուն

Եկեք ստեղծենք սահմանափակումների նոր համակարգեր լուծումների բազմանկյունի ստացված տարածքների համար։ Ձախ հատվածը քառանկյուն է (տրապեզոիդ): Լուծման պոլիգոնի ձախ շրջանի սահմանափակումների համակարգը ներկայացված է ստորև։

Ձախ տարածքի սահմանափակման համակարգ

Ճիշտ տարածքը ներկայացնում է C կետը:

Ճիշտ որոշման տարածաշրջանի սահմանափակումների համակարգը ներկայացված է ստորև։

Սահմանափակման նոր համակարգերը ներկայացնում են երկու օժանդակ խնդիրներ, որոնք պետք է լուծվեն միմյանցից անկախ: Լուծենք լուծման բազմանկյունի ձախ հատվածի ծրագրավորման ամբողջական խնդիր։

Լուծման արդյունքում գտնվել է խնդրի օպտիմալ պլանը՝ x1 = 3, x2 = 3, F = -12: Այս պլանը բավարարում է պայմանին, որ խնդրի փոփոխականները ամբողջ թվեր են և կարող են ընդունվել որպես սկզբնական ամբողջական գծային ծրագրավորման խնդրի օպտիմալ հղման պլան: Ճիշտ լուծման տարածաշրջան լուծելու իմաստ չկա. Ստորև բերված նկարը ցույց է տալիս ծառի տեսքով ամբողջ թվային գծային ծրագրավորման խնդրի լուծման առաջընթացը:

Գոմորի մեթոդով ամբողջ թվային գծային ծրագրավորման խնդրի լուծման առաջընթացը:

Շատ գործնական կիրառություններում մեծ հետաքրքրություն է ներկայացնում ամբողջ թվային ծրագրավորման խնդիրը, որտեղ տրված է գծային անհավասարությունների համակարգ և գծային ձև:

Պահանջվում է (1) համակարգի ամբողջական լուծում գտնել, որը նվազագույնի է հասցնում F ֆունկցիան, և բոլոր գործակիցները ամբողջ թվեր են:

Ամբողջական ծրագրավորման խնդրի լուծման մեթոդներից մեկն առաջարկել է Գոմորին։ Մեթոդի գաղափարը շարունակական գծային ծրագրավորման մեթոդների օգտագործումն է, մասնավորապես՝ սիմպլեքս մեթոդը։

1) Սիմպլեքս մեթոդով որոշվում է (1), (2) խնդրի լուծումը, որի համար հանվում է ամբողջ թվի լուծման պահանջը. եթե լուծումը պարզվի, որ ամբողջ թիվ է, ապա կգտնվի նաև ամբողջ թվի խնդրի ցանկալի լուծումը.

2) Հակառակ դեպքում, եթե որոշ կոորդինատներ ամբողջ թիվ չեն, ապա խնդրի լուծումը ստուգվում է ամբողջ թվի լուծման հնարավորության համար (թույլատրելի բազմանկյունում ամբողջական կետերի առկայություն).

եթե կոտորակային ազատ անդամ ունեցող որևէ շարքում մնացած բոլոր գործակիցները ստացվում են ամբողջ թվեր, ապա թույլատրելի բազմանկյունում չկան ամբողջ թվեր կամ կետեր, և ծրագրավորման ամբողջ խնդիրը լուծում չունի.

Հակառակ դեպքում, ներմուծվում է լրացուցիչ գծային սահմանափակում, որը կտրում է թույլատրելի բազմանկյունի մի մասը, որն անհեռանկարային է ամբողջ թվային ծրագրավորման խնդրի լուծում գտնելու համար.

3) Լրացուցիչ գծային սահմանափակում կառուցելու համար ընտրեք 1-րդ շարքը կոտորակային ազատ անդամով և գրեք լրացուցիչ սահմանափակում.

որտեղ և համապատասխանաբար գործակիցների կոտորակային մասերն են և ազատ

անդամ. Եկեք օժանդակ փոփոխական ներմուծենք սահմանափակում (3).

Եկեք որոշենք գործակիցները և ներառված սահմանափակման մեջ (4).

որտեղ և են համապատասխանաբար ներքևից մոտակա ամբողջ թվերը:

Գոմորին ապացուցեց, որ նման քայլերի վերջավոր թիվը հանգեցնում է գծային ծրագրավորման խնդրի, որի լուծումն ամբողջ թիվ է և, հետևաբար, ցանկալի:

Լուծում. Եկեք գծային սահմանափակումների համակարգը և նպատակային ֆունկցիան բերենք կանոնական ձևի.

Եկեք որոշենք գծային սահմանափակումների համակարգի օպտիմալ լուծումը՝ ժամանակավորապես հրաժարվելով ամբողջ թվի պայմանից։ Դրա համար մենք օգտագործում ենք simplex մեթոդը: Ստորև, աղյուսակներում հաջորդաբար ներկայացված է խնդրի սկզբնական լուծումը, և տրված են սկզբնական աղյուսակի փոխակերպումները՝ խնդրի օպտիմալ լուծումը ստանալու համար.

Բուլյան LP խնդիրների լուծում Բալազի մեթոդով:

Ստեղծեք ձեր սեփական տարբերակը Բուլյան փոփոխականներով ամբողջ թվով գծային ծրագրավորման խնդրի համար՝ հաշվի առնելով հետևյալ կանոնները. մի եղանակ, որով սահմանափակումների համակարգը համատեղելի է: Խնդիրն է լուծել LCLP-ն բուլյան փոփոխականներով՝ օգտագործելով Բալազի ալգորիթմը և որոշել հաշվարկների բարդության նվազումը՝ կապված խնդրի լուծման հետ՝ օգտագործելով սպառիչ որոնման մեթոդը:

Սահմանափակումների իրականացում

F արժեք

Զտման սահմանափակում.

Հաշվարկային ջանքերի կրճատման որոշում

Հարցի լուծումը սպառիչ որոնման մեթոդով 6*25=192 հաշվարկված արտահայտությունն է։ Բալազի մեթոդով խնդրի լուծումը 3*6+(25-3)=47 հաշվարկված արտահայտությունն է։ Համապարփակ որոնման մեթոդով խնդրի լուծման հետ կապված հաշվարկների բարդության ընդհանուր կրճատումը հետևյալն է.

Եզրակացություն

Մշտապես կատարելագործվում է նոր տեղեկատվական տեխնոլոգիաներ ներդրող տեղեկատվական համակարգերի նախագծման գործընթացը: Համակարգերի ինժեներների ուշադրությունը գնալով ավելի է կենտրոնանում բարդ համակարգերի վրա, ինչը դժվարացնում է ֆիզիկական մոդելների օգտագործումը և մեծացնում մաթեմատիկական մոդելների և համակարգերի մեքենայական մոդելավորման կարևորությունը: Մեքենայի սիմուլյացիան դարձել է բարդ համակարգերի ուսումնասիրման և նախագծման արդյունավետ գործիք: Մաթեմատիկական մոդելների արդիականությունը շարունակաբար աճում է` շնորհիվ դրանց ճկունության, իրական գործընթացներին համապատասխանության և ժամանակակից ԱՀ-ների հիման վրա ներդրման ցածր գնի: Ավելի ու ավելի շատ հնարավորություններ են տրվում օգտագործողին, այսինքն՝ համակարգչային տեխնոլոգիաների օգտագործմամբ համակարգերի մոդելավորման մասնագետին: Մոդելավորման օգտագործումը հատկապես արդյունավետ է ավտոմատացված համակարգերի նախագծման վաղ փուլերում, երբ ամենաէական է սխալ որոշումների արժեքը:

Ժամանակակից հաշվողական գործիքները հնարավորություն են տվել զգալիորեն մեծացնել համակարգերի ուսումնասիրության մեջ օգտագործվող մոդելների բարդությունը, հնարավոր է դարձել կառուցել համակցված, վերլուծական և սիմուլյացիոն մոդելներ, որոնք հաշվի են առնում իրական համակարգերում տեղի ունեցող գործոնների ամբողջ բազմազանությունը, այսինքն. , ուսումնասիրվող երեւույթներին առավել համարժեք մոդելների օգտագործում։

Գրականություն:

1. Լյաշչենկո Ի.Ն. Գծային և ոչ գծային ծրագրավորում / I.N. Lyashchenko, E.A. Karagodova, N.V. Chernikova, N.Z. Shor. - Կ.: «Բարձրագույն դպրոց», 1975, 372 էջ.

2. «Կիրառական մաթեմատիկա» առարկայի դասընթացի նախագիծ ավարտելու ուղեցույցներ «Համակարգչային համակարգեր և ցանցեր» մասնագիտության ուսանողների համար լրիվ դրույքով և հեռակա ուսուցման ձևերի համար / Կազմող՝ Ի.Ա. Բալակիրևա, Ա.Վ. Սկատկով - Սևաստոպոլ. Publishing House, 2003. - 15 p.

3. «Կիրառական մաթեմատիկա» առարկայի ուսումնասիրության ուղեցույց, «Գլոբալ որոնման մեթոդներ և միաչափ մինիմիզացիա» բաժինը / Համ. A.V. Skatkov, I.A. Balakireva, L.A. Litvinova - Sevastopol: SevGTU Publishing House, 2000. - 31 p.

4. «Կիրառական մաթեմատիկա» առարկայի ուսումնասիրության ուղեցույց «Համակարգչային համակարգեր և ցանցեր» մասնագիտության ուսանողների համար «Ամբողջ թվային գծային ծրագրավորման խնդիրների լուծում» լրիվ դրույքով և հեռակա կրթության համար / Կազմող՝ Ի.Ա. Բալակիրևա, Ա.Վ. Սկատկով - Սևաստոպոլ ՍևՆՏՄ հրատարակչություն, 2000. - 13 էջ.

5. Ակուլիչ Ի.Լ. Մաթեմատիկական ծրագրավորում օրինակներով և խնդիրներով.

6. Դասագիրք նպաստ տնտեսագիտության ուսանողների համար. մասնագետ։ համալսարաններ.-Մ.՝ Բարձր. դպրոց, 1986.- 319 p., ill.

7. Անդրոնով Ս.Ա. Դիզայնի օպտիմալ մեթոդներ. Դասախոսությունների տեքստ / SPbSUAP: Սանկտ Պետերբուրգ, 2001 թ. 169 էջ: հիվանդ.

Նմանատիպ փաստաթղթեր

Սիմպլեքս մեթոդով գծային ծրագրավորման խնդիրների լուծման ալգորիթմ. Գծային ծրագրավորման խնդրի մաթեմատիկական մոդելի կառուցում. Excel-ում գծային ծրագրավորման խնդրի լուծում. Գտեք շահույթ և օպտիմալ արտադրության պլան:

դասընթացի աշխատանք, ավելացվել է 21.03.2012թ


Գրաֆիկական խնդիրների լուծում. Մաթեմատիկական մոդելի կազմում: Օբյեկտիվ ֆունկցիայի առավելագույն արժեքի որոշում: Լուծում սիմպլեքս մեթոդով՝ կանոնական գծային ծրագրավորման խնդրի արհեստական ​​հիմքով։ Լուծման օպտիմալության ստուգում:

թեստ, ավելացվել է 04/05/2016


Գծային ծրագրավորման տեսական հիմքերը. Գծային ծրագրավորման խնդիրներ, լուծման մեթոդներ. Օպտիմալ լուծման վերլուծություն. Մեկ ինդեքսով գծային ծրագրավորման խնդրի լուծում. Խնդրի հայտարարություն և տվյալների մուտքագրում: Մոդելի կառուցման և լուծման փուլերը.

դասընթացի աշխատանք, ավելացվել է 12/09/2008 թ


Մաթեմատիկական մոդելի կառուցում. Ուղղակի գծային ծրագրավորման խնդրի լուծման մեթոդի ընտրություն, հիմնավորում և նկարագրություն սիմպլեքս մեթոդով, սիմպլեքս աղյուսակի կիրառմամբ: Երկակի խնդրի ձևակերպում և լուծում. Մոդելի զգայունության վերլուծություն:

դասընթացի աշխատանք, ավելացվել է 31.10.2014թ


Ձեռնարկության համար առավելագույն շահույթ ստանալու համար մաթեմատիկական մոդելի կառուցում, խնդրի գրաֆիկական լուծում։ Խնդրի լուծում՝ օգտագործելով SOLVER հավելումը: Ռեսուրսների պաշարների փոփոխությունների վերլուծություն. Օբյեկտիվ ֆունկցիայի գործակիցների փոփոխման սահմանների որոշում.

դասընթացի աշխատանք, ավելացվել է 17.12.2014թ


Մաթեմատիկական ծրագրավորում. Գծային ծրագրավորում. Գծային ծրագրավորման խնդիրներ. Գծային ծրագրավորման խնդիրների լուծման գրաֆիկական մեթոդ. Գծային ծրագրավորման խնդրի տնտեսական ձևակերպում. Մաթեմատիկական մոդելի կառուցում.

դասընթացի աշխատանք, ավելացվել է 13.10.2008թ


Գծային ծրագրավորման խնդրի լուծում գրաֆիկական մեթոդով, ստուգում MS Excel-ում։ Ծրագրում խնդրի լուծման ներքին կառուցվածքի վերլուծություն: Արտադրության պլանի օպտիմալացում: Խնդիրը լուծել սիմպլեքս մեթոդով: Բազմալիքային հերթերի համակարգ.

թեստ, ավելացվել է 05/02/2012


Գծային ծրագրավորման խնդրի լուծում սիմպլեքս մեթոդով` խնդրի ձևակերպում, տնտեսական և մաթեմատիկական մոդելի կառուցում: Տրանսպորտային խնդրի լուծում՝ օգտագործելով պոտենցիալ մեթոդը. նախնական հղման պլանի կառուցում, դրա օպտիմալ արժեքի որոշումը:

թեստ, ավելացվել է 04/11/2012


Ոչ գծային ծրագրավորման խնդրի ձևակերպում. Անշարժ կետերի և դրանց տեսակի որոշում. Մակարդակի գծերի կառուցում, օբյեկտիվ ֆունկցիայի եռաչափ գրաֆիկ և սահմանափակումներ։ Խնդրի գրաֆիկական և վերլուծական լուծում. Օգտագործողի ձեռնարկ և ալգորիթմի դիագրամ:

դասընթացի աշխատանք, ավելացվել է 17.12.2012թ


Գծային ծրագրավորման խնդրի լուծման վերլուծություն: Սիմպլեքս մեթոդ՝ օգտագործելով սիմպլեքս աղյուսակներ: LP խնդիրների մոդելավորում և լուծում համակարգչով: Խնդրի օպտիմալ լուծման տնտեսական մեկնաբանություն. Տրանսպորտային խնդրի մաթեմատիկական ձևակերպում.

Երրորդ շարքը բաժանում ենք 5-ի հավասար հիմնական տարրի վրա, ստանում ենք նոր աղյուսակի երրորդ շարքը։

Հիմնական սյունակները համապատասխանում են միավորի սյունակներին:

Աղյուսակի այլ արժեքների հաշվարկ.

«BP – Հիմնական պլան».

; ;

«x1»: ; ;

«x5»: ; .

Ինդեքսային տողի արժեքները ոչ բացասական են, հետևաբար մենք ստանում ենք օպտիմալ լուծում. .

Պատասխան.Արտադրված արտադրանքի վաճառքից առավելագույն շահույթը՝ 160/3 միավոր, ապահովվում է միայն երկրորդ տեսակի արտադրանքի արտադրությամբ՝ 80/9 միավորի չափով։

Առաջադրանք թիվ 2

Տրված է ոչ գծային ծրագրավորման խնդիր։ Գրաֆիկա-վերլուծական մեթոդով գտե՛ք օբյեկտիվ ֆունկցիայի առավելագույնը և նվազագույնը։ Կազմեք Լագրանժի ֆունկցիան և ցույց տվեք, որ ծայրահեղ կետերում բավարարված են նվազագույնի (առավելագույնի) համար բավարար պայմաններ։

Որովհետեւ գաղտնագրի վերջին թվանշանը 8-ն է, ապա A=2; B=5.

Որովհետեւ գաղտնագրի նախավերջին նիշը 1-ն է, այնուհետև պետք է ընտրել թիվ 1 առաջադրանքը։

Լուծում:

1) Նկարենք անհավասարությունների համակարգով սահմանված տարածքը.

Այս տարածքը ABC եռանկյունին է՝ գագաթային կոորդինատներով՝ A(0; 2); B(4; 6) և C(16/3; 14/3):

Օբյեկտիվ ֆունկցիայի մակարդակները շրջաններ են, որոնց կենտրոնը գտնվում է (2; 5): Շառավիղների քառակուսիները կլինեն օբյեկտիվ ֆունկցիայի արժեքները: Այնուհետև նկարը ցույց է տալիս, որ նպատակային ֆունկցիայի նվազագույն արժեքը ձեռք է բերվում H կետում, առավելագույնը՝ կամ A կետում, կամ C կետում:

Օբյեկտիվ ֆունկցիայի արժեքը A կետում.

Օբյեկտիվ ֆունկցիայի արժեքը C կետում:

Սա նշանակում է, որ ֆունկցիայի ամենաբարձր արժեքը ձեռք է բերվում A(0; 2) կետում և հավասար է 13-ի:

Գտնենք H կետի կոորդինատները.

Դա անելու համար հաշվի առեք համակարգը.

ó

ó

Ուղղը շոշափում է շրջանագծին, եթե հավասարումն ունի եզակի լուծում: Քառակուսային հավասարումը ունի եզակի լուծում, եթե դիսկրիմինանտը 0 է:

Հետո ; ; - ֆունկցիայի նվազագույն արժեքը.

2) Եկեք կազմենք Lagrange ֆունկցիան՝ նվազագույն լուծումը գտնելու համար.

ժամը x 1 =2.5; x 2 =4.5 մենք ստանում ենք.

ó

Համակարգը լուծում ունի ժամը , այսինքն. բավարարված են ծայրահեղության համար բավարար պայմաններ.

Եկեք կազմենք Lagrange ֆունկցիան առավելագույն լուծումը գտնելու համար.

Բավարար պայմաններ ծայրահեղության համար.

ժամը x 1 =0; x 2 =2 մենք ստանում ենք.

ó ó

Համակարգն ունի նաև լուծում, այսինքն. բավարարված են ծայրահեղության համար բավարար պայմաններ.

Պատասխան.Նպատակային ֆունկցիայի նվազագույնը ձեռք է բերվում, երբ ; ; նպատակային ֆունկցիայի առավելագույնը ձեռք է բերվում ; .

Առաջադրանք թիվ 3

Երկու ձեռնարկության գումար է հատկացվել դմիավորներ. Առաջին ձեռնարկությունը մեկ տարով հատկացնելիս xդրամական միավորներ, որոնք ապահովում են եկամուտ կ 1 xմիավորներ, և երբ հատկացվում են երկրորդ ձեռնարկությանը yդրամական միավորներ, այն ապահովում է եկամուտ կ 1 yմիավորներ. Միջոցների մնացորդը տարեվերջին առաջին ձեռնարկության համար հավասար է nx, իսկ երկրորդի համար իմ. Ինչպե՞ս բաշխել բոլոր միջոցները 4 տարվա ընթացքում, որպեսզի ընդհանուր եկամուտը լինի ամենամեծը: Լուծեք խնդիրը դինամիկ ծրագրավորման մեթոդով:

i=8, k=1.

A=2200; k 1 =6; k 2 =1; n=0.2; մ=0,5.

Լուծում:

4 տարվա ամբողջ ժամանակահատվածը բաժանված է 4 փուլի, որոնցից յուրաքանչյուրը հավասար է մեկ տարվա։ Թվարկենք փուլերը՝ սկսած առաջին կուրսից։ Թող X k և Y k-ը համապատասխանաբար A և B ձեռնարկություններին հատկացվեն k-րդ փուլում: Այնուհետև X k + Y k = a k գումարը k - այդ փուլում օգտագործված միջոցների ընդհանուր գումարն է, իսկ նախորդ փուլից k - 1 մնացածը: Առաջին փուլում օգտագործվում են բոլոր հատկացված միջոցները և a 1 = 2200 միավոր: . եկամուտը, որը կստացվի k – այդ փուլում, X k և Y k միավորների տեղաբաշխմամբ կկազմի 6X k + 1Y k: թող k-ից սկսած վերջին փուլերում ստացված առավելագույն եկամուտը լինի f k (a k) միավոր: Եկեք գրենք օպտիմալության սկզբունքն արտահայտող ֆունկցիոնալ Բելմանի հավասարումը. ինչպիսին էլ լինի սկզբնական վիճակն ու սկզբնական լուծումը, հաջորդ լուծումը պետք է օպտիմալ լինի սկզբնական վիճակի արդյունքում ստացված վիճակի նկատմամբ.

Յուրաքանչյուր փուլի համար անհրաժեշտ է ընտրել X k արժեքը և արժեքը Յ կ=ակ- Xկ. Սա հաշվի առնելով՝ k-րդ փուլում կգտնենք եկամուտը.

Բելմանի ֆունկցիոնալ հավասարումը կլինի.

Դիտարկենք բոլոր փուլերը՝ սկսած վերջինից։

(քանի որ գծային ֆունկցիայի առավելագույնը հասնում է հատվածի վերջում՝ x 4 = a 4);