Ո՞ր լուծումն է կոչվում օպտիմալ: Գծային մոդելների գրաֆիկական օպտիմալացման մեթոդ

Ուռուցիկ բազմություններ և դրանց հատկությունները: LPP-ի հատկությունները ուսումնասիրելու համար անհրաժեշտ է տալ ուռուցիկ բազմության խիստ սահմանում։ Ավելի վաղ ուռուցիկ բազմությունը սահմանվում էր որպես բազմություն, որն իր ցանկացած երկու կետերի հետ պարունակում է դրանք միացնող հատված։

Մի քանի կետերի համար հատված հասկացության ընդհանրացումը դրանց ուռուցիկ գծային համակցությունն է:

X կետը կոչվում է ուռուցիկ գծային համադրությունմիավորներ, պայմանները բավարարելու դեպքում

Միավորների հավաքածուն է ուռուցիկ,եթե այն իր երկու կետերից որևէ մեկի հետ պարունակում է նրանց կամայական ուռուցիկ, գծային համակցությունը:

Ուռուցիկ բազմանկյունի ներկայացման վերաբերյալ կարելի է ապացուցել հետևյալ թեորեմը.

Թեորեմ 1.1. Ուռուցիկ n-պոլիտոպը իր անկյունային կետերի ուռուցիկ գծային համակցությունն է:

Թեորեմ 1.1-ից հետևում է, որ ուռուցիկ բազմանիստը ձևավորվում է իր անկյունային կետերով կամ գագաթներով. հատվածը երկու կետով, եռանկյունը երեքով, քառաեդրոնը չորս կետով և այլն: Միևնույն ժամանակ, ուռուցիկ բազմանիստ շրջանը, լինելով անսահմանափակ բազմություն, եզակիորեն որոշված չէ իր անկյունային կետերով. նրա ցանկացած կետ չի կարող ներկայացվել որպես անկյունային կետերի ուռուցիկ գծային համակցություն:

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

Գծային ծրագրավորման խնդրի հատկությունները և դրա լուծման մեթոդները հիմնավորելու համար նպատակահարմար է դիտարկել կանոնական խնդիրը գրելու ևս երկու տեսակ։

Մատրիցային նշում.

Այստեղ ՀԵՏ- տողերի մատրիցա, Ա- համակարգի մատրիցա, X- փոփոխականների մատրիցա-սյունակ, Վ- ազատ անդամների մատրիցա-սյունակ.

Վեկտորային նշում.

որտեղ վեկտորները համապատասխանում են անհայտների գործակիցների սյունակներին:

Հետևյալ թեորեմը ասվել է վերևում, բայց չի ապացուցվել ընդհանուր ձևով.

Թեորեմ 1.2. Գծային ծրագրավորման խնդրի սահմանափակումների համակարգի բոլոր իրագործելի լուծումների ամբողջությունը ուռուցիկ է:

Ապացույց:Թող - LPP-ի երկու թույլատրելի լուծումներ տրված մատրիցային տեսքով: Հետո և . Դիտարկենք լուծումների ուռուցիկ գծային համակցություն, այսինքն.

և ցույց տալ, որ այն նաև (1.3) համակարգի թույլատրելի լուծում է: Իսկապես

այսինքն. լուծում Xբավարարում է համակարգը (1.3). Բայց այդ ժամանակվանից X> 0, այսինքն. լուծումը բավարարում է ոչ բացասական պայմանին։

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

Հարցի պատասխանը, թե լուծումների պոլիտոպի ո՞ր կետում է հնարավոր գծային ծրագրավորման խնդրի օպտիմալ լուծումը, տրված է հետևյալ հիմնարար թեորեմում.

Թեորեմ 1.3. Եթե գծային ծրագրավորման խնդիրն ունի օպտիմալ լուծում, ապա գծային ֆունկցիան իր առավելագույն արժեքը վերցնում է լուծման պոլիտոպի անկյունային կետերից մեկում։ Եթե գծային ֆունկցիան վերցնում է իր առավելագույն արժեքը մեկից ավելի անկյունային կետերում, ապա այն վերցնում է ցանկացած կետում, որն այս կետերի ուռուցիկ գծային համակցությունն է:

Ապացույց:Մենք կենթադրենք, որ լուծույթի պոլիտոպը սահմանափակ է: Նշենք նրա անկյունային կետերը , իսկ օպտիմալ լուծումը անցնում է X *... Հետո F (X *)³ F (X)բոլոր կետերի համար Xլուծույթների բազմանիստ. Եթե X *Անկյունային կետ է, ապա ապացուցված է թեորեմի առաջին մասը:

Եկեք այդպես ձևացնենք X *անկյունային կետ չէ, ապա թեորեմ 1.1 X *կարող է ներկայացվել որպես լուծման պոլիէդրոնի անկյունային կետերի ուռուցիկ գծային համակցություն, այսինքն.

Որովհետեւ F (X)Գծային ֆունկցիա է, մենք ստանում ենք

Այս ընդլայնման մեջ մենք ընտրում ենք առավելագույն արժեքը արժեքներից: Թող այն համապատասխանի անկյունային կետին X k(£ 1 կ£ Հ); նշենք դրանով Մ,դրանք. . (1.5) արտահայտության յուրաքանչյուր արժեք փոխարինեք այս առավելագույն արժեքով Մ.Հետո

Ենթադրությամբ X* Օպտիմալ լուծում է, հետևաբար, մի կողմից, բայց, մյուս կողմից, ապացուցված է, որ
F (X *)£ Մ,հետևաբար, որտեղ X k- անկյունային կետ. Այսպիսով, կա անկյունային կետ X kորտեղ գծային ֆունկցիան վերցնում է իր առավելագույն արժեքը:

Թեորեմի երկրորդ մասը ապացուցելու համար ենթադրենք, որ օբյեկտիվ ֆունկցիան իր առավելագույն արժեքը վերցնում է մեկից ավելի անկյունային կետերում, օրինակ՝ կետերում. , որտեղ , ապա

Թող X- այս անկյունային կետերի ուռուցիկ գծային համադրություն, այսինքն.

Այս դեպքում, հաշվի առնելով, որ գործառույթը F (X)- գծային, մենք ստանում ենք

դրանք. գծային ֆունկցիա Ֆվերցնում է առավելագույն արժեքը կամայական կետում Xորը անկյունային կետերի ուռուցիկ գծային համակցություն է։

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

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

Հաջորդ թեորեմը նվիրված է անկյունային կետերի հայտնաբերման վերլուծական մեթոդին։

Թեորեմ 1.4. Գծային ծրագրավորման խնդրի յուրաքանչյուր թույլատրելի հիմնական լուծումը համապատասխանում է լուծման պոլիէդրոնի անկյունային կետին, և հակառակը, լուծման պոլիէդրոնի յուրաքանչյուր անկյունային կետը համապատասխանում է թույլատրելի հիմնական լուծմանը:

Ապացույց:Թող լինի թույլատրելի հիմնական լուծում LPP սահմանափակումների համակարգի (1.4), որում առաջինը. Տբաղադրիչը հիմնական փոփոխականներն են, իսկ մնացածը n - tբաղադրիչ - հիմնական լուծման մեջ զրոյի հավասար փոքր փոփոխականներ (եթե դա այդպես չէ, ապա համապատասխան փոփոխականները կարող են վերահամարակալվել): Եկեք դա ցույց տանք X

Ենթադրենք հակառակը, այսինքն. ինչ Xանկյունային կետ չէ: Հետո կետը Xկարող է ներկայացվել մի հատվածի ներքին կետով, որը միացնում է երկու տարբեր, որոնք չեն համընկնում X,միավորներ

այլ կերպ ասած՝ կետերի ուռուցիկ գծային համակցություն լուծույթների պոլիեդրոն, այսինքն.

որտեղ (մենք ենթադրում ենք, որ հակառակ դեպքում կետը Xհամընկնում է կետի հետ X 1 կամ X 2).

Վեկտորային հավասարությունը (1.6) գրում ենք կոորդինատային ձևով.

Որովհետեւ բոլոր փոփոխականներն ու գործակիցները ոչ բացասական են, ապա վերջիններից p-tհավասարություններից հետևում է, որ, այսինքն. որոշումներում X 1 , X 2 և Xհավասարումների համակարգը (1.4) արժեքները n - tբաղադրիչներն այս դեպքում հավասար են զրոյի: Այս բաղադրիչները կարելի է համարել որպես փոքր փոփոխականների արժեքներ: Բայց փոքր փոփոխականների արժեքները միանշանակորեն որոշում են հիմնականների արժեքները, հետևաբար.

Այսպիսով, բոլորը Պբաղադրիչ լուծույթներում X 1 , X 2 և Xհամընկնում են, և հետևաբար կետերը X 1 և X 2 միաձուլում, որը հակասում է ենթադրությանը: Հետևաբար, XԼուծման անկյունային կետն է պոլիէդրոն:

Եկեք ապացուցենք հակառակ հայտարարությունը. Թող լինի լուծույթների պոլիտոպի անկյունային կետը և դրա առաջինը Տկոորդինատները դրական են: Եկեք դա ցույց տանք X- թույլատրելի հիմնական լուծում. անկյունային կետ չէ, որը հակասում է պայմանին։ Հետեւաբար, մեր ենթադրությունը սխալ է, այսինքն. վեկտորները գծային անկախ են և XԽնդրի թույլատրելի հիմնական լուծումն է (1.4):

Կարևոր հետևանքը ուղղակիորեն բխում է 1.3 և 1.4 թեորեմներից. եթե գծային ծրագրավորման խնդիրն ունի օպտիմալ լուծում, ապա այն համընկնում է դրա թույլատրելի հիմնական լուծումներից առնվազն մեկի հետ:

Այսպիսով, Գծային ծրագրավորման խնդրի գծային ֆունկցիայի օպտիմալը պետք է փնտրել դրա թույլատրելի հիմնական լուծումների վերջավոր թվով:

Կատարվում է MS Excel-ում գծային մոդելների օպտիմալացում սիմպլեքս մեթոդ- գծային ծրագրավորման խնդրի օժանդակ լուծումների նպատակային թվարկում. Սիմպլեքս մեթոդի ալգորիթմը կրճատվում է ուռուցիկ պոլիէդրոնի կառուցմամբ բազմաչափ տարածության մեջ, այնուհետև կրկնվում է նրա գագաթներով՝ ծայրահեղ արժեքը գտնելու համար։ օբյեկտիվ գործառույթ.

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

Հետագա դասախոսություններում մանրամասն կվերլուծվեն օպտիմիզացման տիպիկ խնդիրների լուծման և կառավարման որոշումներ կայացնելու օրինակներ՝ օգտագործելով «Որոնել լուծում» MS Excel հավելումը: Առաջադրանքները, որոնք լավագույնս կատարվում են այս գործիքի միջոցով, ունեն երեք հիմնական հատկություն.

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

Առաջադրանքի պարամետրերը սահմանափակվում են հետևյալ սահմանային արժեքներով.

անհայտների թիվը՝ 200;
բանաձևի սահմանափակումների քանակը անհայտների վրա՝ 100;
Անհայտների համար սահմանափակող պայմանների թիվը 400 է։

Օպտիմալ լուծումներ գտնելու ալգորիթմը ներառում է մի քանի փուլ.

նախապատրաստական աշխատանք;
լուծումների վրիպազերծում;
լուծման վերլուծություն.

MS Excel-ի միջոցով տնտեսական և մաթեմատիկական մոդելավորման խնդիրների լուծման համար կատարված անհրաժեշտ նախապատրաստական աշխատանքների հաջորդականությունը ներկայացված է Նկար 1.6-ի բլոկային դիագրամում:

Բրինձ. 1.6.

Նախապատրաստական աշխատանքային պլանի հինգ կետերից պաշտոնականացվում է միայն հինգերորդ կետը։ Մնացած աշխատանքը պահանջում է ստեղծագործություն, և դրանք կարող են կատարվել տարբեր ձևերով տարբեր մարդկանց կողմից: Համառոտ բացատրենք պլանի կետերի ձևակերպման էությունը։

Խնդիրը դնելիս հայտնի են թիրախային գործակիցները և նորմալացված գործակիցները: Նախորդ օրինակում օբյեկտիվ ֆունկցիան ձևավորող գործակիցները տիպի մեկ դարակի համար նորմալացված շահույթի արժեքներն էին ( ) և տիպի մեկ դարակ ( ): Նորմալացված գործակիցներն էին յուրաքանչյուր տեսակի նյութի սպառման և մեքենայի ժամանակի տեմպերը: Մատրիցն այսպիսի տեսք ուներ.

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

Այսպիսով, «Որոնել լուծում» օպտիմալացման ծրագրի երկխոսության վանդակում մենք պետք է նշենք հետևյալ թիրախային ալգորիթմը.

Օբյեկտիվ ֆունկցիան հավասար է փոփոխականների ցանկալի արժեքների վեկտորի արտադրյալին օբյեկտիվ գործակիցների վեկտորով

Փոփոխականների փնտրվող արժեքների վեկտորի նորմալացված գործակիցները չպետք է գերազանցեն ռեսուրսների տվյալ վեկտորի արժեքը.

Փոփոխականի արժեքները պետք է լինեն համակարգի սկզբնական տարրերի նշված սահմաններում

Համակարգի սկզբնական տարրերի քանակը

Նշված տեսակի ռեսուրսների քանակը

Լուծման վրիպազերծումը անհրաժեշտ է այն դեպքում, երբ ծրագիրը բացասական արդյունքների մասին հաղորդագրություն է թողարկում (Նկար 1.7).

Բրինձ. 1.7.

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

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

Վերլուծություն օպտիմալ լուծում, ծրագրում ներկառուցված, տնտեսական գործընթացների մաթեմատիկական մոդելավորման վերջնական փուլն է։ Այն թույլ է տալիս ավելի խորը ստուգել մոդելի համապատասխանությունը գործընթացին, ինչպես նաև օպտիմալ լուծման հուսալիությունը: Դա տվյալների վրա հիմնված է օպտիմալ լուծումև հաշվետվություններ, որոնք տրված են «Լուծումների որոնում»-ում։ Բայց դա չի բացառում կամ փոխարինում պլանի ավանդական վերլուծությունը տնտեսական տեսակետից մինչև կառավարման որոշում կայացնելը:

Տնտեսական վերլուծությունը ունի հետևյալ նպատակները.

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

Վերլուծության հնարավոր մեթոդները ներկայացված են գծապատկեր 1.8-ում:

Օպտիմալ լուծում ստանալուց հետո այն վերլուծվում է ըստ ստացված հաշվետվությունների։ Կայունության վերլուծություն- մոդելի առանձին պարամետրերի փոփոխությունների ազդեցության ուսումնասիրություն օպտիմալ լուծման ցուցիչների վրա: Սահմանային վերլուծություն- օպտիմալ պլանում ընդունելի փոփոխությունների վերլուծություն, որում պլանը մնում է օպտիմալ:

Հաշվի առնելով տնտ կառավարման որոշում, ղեկավարը պետք է համոզվի, որ ստացված օպտիմալ պլանը միակ ճիշտն է։ Դա անելու համար անհրաժեշտ է մոդելի հիման վրա ստանալ հետևյալ հարցերի պատասխանները.

"ինչ կլինի եթե…"
«Ինչ է պետք, որ…»

Առաջին հարցին պատասխանելու վերլուծություն կոչվում է տարբերակի վերլուծություն; կոչվում է վերլուծություն երկրորդ հարցին պատասխանելու համար հարմարեցված լուծումներ:

Տարբերակային վերլուծությունը հետևյալ տեսակների է.

Պարամետրիկ- վերլուծություն, որը բաղկացած է որոշակի պարամետրի տարբեր արժեքների համար խնդրի լուծումից:
Կառուցվածքային վերլուծություն- երբ օպտիմալացման խնդրի լուծումը որոնվում է սահմանափակումների այլ կառուցվածքով:
Բազմաչափ վերլուծություն- Սա խնդրի լուծում է տարբեր թիրախային գործառույթների համար:
Վերլուծություն պայմանական մուտքագրման տվյալներով- երբ խնդրի լուծման համար օգտագործվող սկզբնական տվյալները կախված են լրացուցիչ պայմանների պահպանումից.

Վերլուծությունից հետո արդյունքները պետք է ներկայացվեն գրաֆիկական տեսքով և կազմվի հաշվետվություն՝ որոշում կայացնելու առաջարկություններով՝ հաշվի առնելով կոնկրետ տնտեսական իրավիճակը։

Սահմանում... Սահմանափակումների համակարգի ցանկացած լուծում կոչվում է LPP-ի թույլատրելի լուծում:
Սահմանում... Իրագործելի լուծումը, որի դեպքում նպատակային ֆունկցիան հասնում է իր առավելագույն կամ նվազագույն արժեքին, կոչվում է օպտիմալ լուծում:

Այս սահմանումների հիման վրա LP խնդիրը կարող է ձևակերպվել հետևյալ կերպ. ուռուցիկ շրջանի բոլոր կետերից, որը լուծում է սահմանափակումների համակարգի, ընտրեք մեկը, որի կոորդինատները նվազագույնի են հասցնում (առավելագույնի են հասցնում) գծային ֆունկցիան։ Ֆ = Հետ 1 x + Հետ 2 y.
Նշենք, որ փոփոխականները x, y LPP-ում, որպես կանոն, վերցնում են ոչ բացասական արժեքներ ( x≥ 0, y≥ 0), ուստի շրջանը գտնվում է կոորդինատային հարթության I քառորդում։

Դիտարկենք գծային ֆունկցիա Ֆ = Հետ 1 x + Հետ 2 yև ամրագրել դրա որոշ արժեքներ Ֆ... Եկեք, օրինակ, Ֆ= 0, այսինքն. Հետ 1 x + Հետ 2 y= 0. Այս հավասարման գրաֆիկը կլինի ուղիղ գիծ, որն անցնում է կոորդինատների սկզբնակետով (0; 0) (նկ.):
Նկարչություն
Այս ֆիքսված արժեքը փոխելիս Ֆ = դ, ուղիղ Հետ 1 x+ Հետ 2 y = դզուգահեռաբար կշարժվի և «հետք կգա» ամբողջ հարթությունը: Թող Դ- բազմանկյուն - սահմանափակումների համակարգի լուծման տարածք: Երբ այն փոխվում է դուղիղ Հետ 1 x + Հետ 2 y = դ, որոշ արժեքով դ = դ 1-ը կհասնի բազմանկյունին Դ, եկեք կոչենք այս կետը Ա«Մուտքի կետ», իսկ հետո, անցնելով բազմանկյունը, ինչ-որ արժեքով դ = դ 2 դրա հետ կունենանք վերջին ընդհանուր կետը Վ, արի զանգենք Վ«Ելքի կետ».
Ակնհայտ է, որ նրա ամենափոքր և ամենամեծ արժեքի օբյեկտիվ գործառույթը Ֆ=Հետ 1 x + Հետ 2 yկհասնի մուտքի կետերին Աև «Ելք» Վ.
Հաշվի առնելով, որ օբյեկտիվ ֆունկցիան օպտիմալ արժեք է ընդունում շրջանի գագաթներում իրագործելի լուծումների բազմության վրա. Դ, LPP-ի լուծման համար կարելի է առաջարկել հետևյալ պլանը.

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

Նշենք, որ վեկտորը ( Հետ 1 , Հետ 2), ուղիղ գծին ուղղահայաց, ցույց է տալիս օբյեկտիվ ֆունկցիայի աճի ուղղությունը:

LPP-ն գրաֆիկորեն լուծելիս կան երկու հնարավոր դեպքեր, որոնք պահանջում են հատուկ քննարկում.

Դեպք 1
Նկար 6
Ուղիղ շարժվելիս Հետ 1 x + Հետ 2 y= դ«Մուտք» կամ «ելք» (ինչպես նկարում) տեղի կունենա բազմանկյունի կողմում: Դա տեղի կունենա, եթե բազմանկյունն ունի ուղիղ գծին զուգահեռ կողմեր: Հետ 1 X+ Հետ 2 ժամը = դ .
Այս դեպքում «ելքի» («մուտքի») կետերն անհամար են, այն է՝ հատվածի ցանկացած կետ. ԱԲ... Սա նշանակում է, որ օբյեկտիվ ֆունկցիան առավելագույն (նվազագույն) արժեքը վերցնում է ոչ թե մի կետում, այլ պոլիգոնի համապատասխան կողմում գտնվող բոլոր կետերում։ Դ.

Դեպք 2
Դիտարկենք այն դեպքը, երբ թույլատրելի արժեքների շրջանակն անսահմանափակ է:
Անսահմանափակ տարածքի դեպքում օբյեկտիվ ֆունկցիան կարող է սահմանվել այնպես, որ համապատասխան ուղիղ գիծը չունենա «ելքի» (կամ «մուտքի») կետ: Հետո ֆունկցիայի առավելագույն արժեքը (նվազագույնը) երբեք չի հասնում, ասում են, որ ֆունկցիան սահմանափակված չէ։
Նկարչություն
Անհրաժեշտ է գտնել օբյեկտիվ ֆունկցիայի առավելագույն արժեքը Ֆ = 4x + 6y→ մաքս, սահմանափակումների համակարգով
Եկեք կառուցենք իրագործելի լուծումների տարածաշրջանը, այսինքն. մենք գրաֆիկորեն կլուծենք անհավասարությունների համակարգը։ Դա անելու համար մենք կառուցում ենք յուրաքանչյուր տող և սահմանում անհավասարություններով տրված կիսահարթությունները։
x + y = 18

x	12	9
y	6	9

0,5x + y = 12

x	12	18
y	6	3

x= 12 - առանցքի զուգահեռ OY ;
y= 9 - առանցքի զուգահեռ ԵԶ ;
x= 0 - առանցք OY ;
y = 0 - առանցք ԵԶ;
x OY;
y≥ 0 - առանցքից բարձր կիսահավասարություն ԵԶ;
y≤ 9 - կես հարթություն ներքևում y = 9;
x ≤ 12 - կիսատ ինքնաթիռ դեպի ձախ x = 12;
0,5x + yx + y = 12;
x + y x + y = 18.

Նկարչություն
Այս բոլոր կիսահարթությունների խաչմերուկն ակնհայտորեն հնգանկյունն է OAVSD, կետերում գագաթներով Օ(0; 0), Ա(0; 9), Վ(6; 9), ՀԵՏ(12; 6), Դ(12; 0): Այս հնգանկյունը կազմում է խնդրի իրագործելի լուծումների տարածաշրջանը։

Ֆ = 4x + 6y→ մաքս.

x	3	0
y	–2	0

Ֆ = 0: 4x + 6y x+ 6y ՀԵՏ(12; 6): Դա նրա մեջ է Ֆ = 4x + 6y
Հետևաբար, համար x = 12, y= 6 ֆունկցիա Ֆ Ֆ= 4 ∙ 12 + 6 ∙ 6 = 84, հավասար է 84-ի: (12; 6) կոորդինատներով կետը բավարարում է սահմանափակումների համակարգի բոլոր անհավասարությունները, և դրա մեջ օբյեկտիվ ֆունկցիայի արժեքը օպտիմալ է։ Ֆ* = 84 (օպտիմալ արժեքը կնշանակվի «*»-ով):
Խնդիրը լուծված է։ Այսպիսով, անհրաժեշտ է արտադրել I տիպի 12 և II տիպի 6 ապրանք, մինչդեռ շահույթը կկազմի 84 հազար ռուբլի։

Գրաֆիկական մեթոդը օգտագործվում է խնդիրների լուծման համար, որոնք սահմանափակումների համակարգում ունեին ընդամենը երկու փոփոխական։ Այս մեթոդը կարող է կիրառվել նաև երեք փոփոխականներով անհավասարությունների համակարգերի նկատմամբ։ Երկրաչափական առումով իրավիճակը տարբեր կլինի, ուղիղ գծերի դերը կխաղան հարթությունները եռաչափ տարածության մեջ, իսկ երեք փոփոխականներում անհավասարության լուծումը կլինի հարթության մի կողմում գտնվող կիսատ տարածությունը։ Տարածքների դերը կխաղան պոլիեդրաները, որոնք կիսատության հատումներն են։

Օրինակ թիվ 2. Հանքը զարգացնում է երկու կար: Առաջին շերտում կտրվածքի ելքը a1% է; երկրորդում՝ a2%. Առաջին շերտի համար երկարապատի առավելագույն արտադրությունը տարեկան B1 հազար տոննա է, երկրորդ շերտի համար՝ B2 հազար տոննա տարեկան: Աշխատանքի տեխնոլոգիայի համաձայն՝ երկրորդ շերտից արտադրությունը չի կարող գերազանցել առաջին շերտից ստացված արտադրությունը։ Հանքավայրի թողարկումը տարեկան չպետք է գերազանցի C1 հազար տոննան։ Երկու շերտերի տարեկան ընդհանուր ծանրաբեռնվածությունը պետք է լինի տարեկան առնվազն C2 հազար տոննա: Ստեղծեք մաթեմատիկական մոդել և կառուցեք տարեկան առաջին և երկրորդ շերտերի համար թույլատրելի բեռի արժեքների հավաքածու:

Օրինակ թիվ 3. Խանութում վաճառվում է 2 տեսակի զովացուցիչ ըմպելիք՝ կոլա և լիմոնադ։ Մեկ տուփ կոլայից ստացված եկամուտը կազմում է 5 ցենտ, իսկ մեկ տուփ լիմոնադից ստացված եկամուտը՝ 7 ցենտ։ Միջին հաշվով, խանութը օրական վաճառում է ոչ ավելի, քան 500 տուփ երկու խմիչքներից: Չնայած այն հանգամանքին, որ կոլան արտադրվում է հայտնի ապրանքանիշով, գնորդները նախընտրում են լիմոնադը, քանի որ այն շատ ավելի էժան է։ Ենթադրվում է, որ կոլայի և լիմոնադի վաճառքը պետք է լինի առնվազն 2:1, իսկ խանութը հայտնի է, որ օրական վաճառում է առնվազն 100 տուփ կոլա: Յուրաքանչյուր ըմպելիքից քանի՞ տուփ պետք է ունենա խանութը օրվա սկզբին՝ եկամուտը առավելագույնի հասցնելու համար:

Օրինակ թիվ 4. Գծային ծրագրավորման խնդիրը լուծեք մոտավորապես գրաֆիկորեն՝ հետագայում նպատակային ֆունկցիայի արժեքի ճշգրիտ արժեքի և առավելագույն (min) հաշվարկով:

Օրինակ թիվ 5. Տուրիստական գործակալության համար պահանջվում են ոչ ավելի, քան երեք տոննա ավտոբուսներ և ոչ ավելի, քան հինգ տոննա ավտոբուսներ: Առաջին մակնիշի ավտոբուսների վաճառքի գինը 20000 ԱՄՆ դոլար է, երկրորդ մակնիշի 40000 ԱՄՆ դոլար։ Ավտոբուսներ գնելու համար տուրիստական գործակալությունը կարող է հատկացնել 1 դոլարից ոչ ավելի։ Յուրաքանչյուր ապրանքանիշի քանի ավտոբուս պետք է առանձին գնել, որպեսզի դրանց ընդհանուր (ընդհանուր) բեռնատարողությունը լինի առավելագույնը։ Լուծեք խնդիրը գրաֆիկորեն:

Օրինակ թիվ 6. Օգտագործելով գրաֆիկական մեթոդը, գտե՛ք աղյուսակում տրված առաջադրանքի օպտիմալ արտադրության պլանը:

Օրինակ թիվ 7. Լուծե՛ք գծային ծրագրավորման խնդիրը գրաֆիկական մեթոդով՝ խնդրի սահմանափակումների համակարգը ենթարկելով Հորդանան-Գաուս փոխակերպումներին։ Խնդրի սահմանափակումների համակարգը հետևյալն է.
a 11 x 1 + a 12 x 2 + a 13 x 3 + a 14 x 4 + a 15 x 5 = b 1
a 21 x 1 + a 22 x 2 + a 23 x 3 + a 24 x 4 + a 25 x 5 = b 2
a 31 x 1 + a 32 x 2 + a 33 x 3 + a 34 x 4 + a 35 x 5 = b 3
Ուղեցույցներ... Հորդանան-Գաուսի փոխակերպումները կարող են իրականացվել այս ծառայության միջոցով կամ SLAE-ների ուսումնասիրության միջոցով:

Օրինակ թիվ 8. Ձեռնարկությունն արտադրում է երկու տեսակի արտադրանք՝ A և B, որոնց արտադրության համար օգտագործվում է երեք տեսակի հումք։ A արտադրանքի միավորի արտադրության համար պահանջվում է ծախսել յուրաքանչյուր տեսակի հումք՝ համապատասխանաբար a1, a2, a3 կգ, իսկ B միավորի համար՝ b1, b2, b3 կգ: Արտադրությունն ապահովված է յուրաքանչյուր տեսակի հումքով՝ համապատասխանաբար Р1, Р2, Р3 կգ քանակությամբ։ A արտադրանքի միավորի արժեքը C1 ռուբլի է, իսկ B ապրանքի միավորը C2 ռուբլի: Պահանջվում է կազմել A և B արտադրանքի արտադրության պլան, որն ապահովում է պատրաստի արտադրանքի առավելագույն արժեքը։

Օրինակ թիվ 2. Անհրաժեշտ է գտնել օբյեկտիվ ֆունկցիայի առավելագույն արժեքը Ֆ = 4x + 6y→ առավելագույնը, սահմանափակումների համակարգով.

Եկեք կառուցենք իրագործելի լուծումների տարածաշրջանը, այսինքն. մենք գրաֆիկորեն կլուծենք անհավասարությունների համակարգը։ Դա անելու համար ընտրեք 4-ի հավասար սահմանափակումների քանակը (Նկար 1):
Նկար 1

Այնուհետև լրացնում ենք փոփոխականների և բուն սահմանափակումների գործակիցները (Նկար 2):
Նկար 2

Նկար 3
x= 12 - առանցքի զուգահեռ OY;
y= 9 - առանցքի զուգահեռ ԵԶ;
x> = 0 - առանցք OY
y= 0 - առանցք ԵԶ;
x≥ 0 - կես հարթություն առանցքի աջ կողմում OY;
y≥0 - առանցքի վերևում գտնվող կես հարթություն ԵԶ;
y≤ 9 - կես հարթություն ներքևում y = 9;
x≤ 12 - կիսատ ինքնաթիռ դեպի ձախ x = 12;
0,5x + y≤ 12 - ուղիղ գծի տակ գտնվող կես հարթություն 0,5 x + y = 12;
x + y≤ 18 - ուղիղ գծից ներքև կիսահավասարություն x + y = 18.

Այս բոլոր կիսահարթությունների խաչմերուկը հնգանկյունն է ABCDE, կետերում գագաթներով Ա(0; 0), Բ(0;9), Գ(6; 9), Դ(12;6), Ե(12; 0): Այս հնգանկյունը կազմում է խնդրի իրագործելի լուծումների տարածաշրջանը։

Դիտարկենք խնդրի օբյեկտիվ գործառույթը Ֆ = 4x + 6y→ մաքս.

x	3	0
y	–2	0

Մենք կառուցում ենք ֆունկցիայի արժեքին համապատասխանող ուղիղ գիծ Ֆ = 0: 4x + 6y= 0. Մենք այս տողը կտեղափոխենք զուգահեռ ձևով: Տողերի ամբողջ ընտանիքից՝ 4 x + 6y= սահմանում է վերջին գագաթը, որով անցնում է ուղիղ գիծը, երբ բազմանկյունի սահմանից այն կողմ դուրս գալը կլինի գագաթը ՀԵՏ(12; 6): Դա նրա մեջ է Ֆ = 4x + 6yհասնում է իր առավելագույն արժեքին.

Հետևաբար, համար x = 12, y= 6 ֆունկցիա Ֆհասնում է իր առավելագույն արժեքին Ֆ= 4 ∙ 12 + 6 ∙ 6 = 84, հավասար է 84-ի: (12; 6) կոորդինատներով կետը բավարարում է սահմանափակումների համակարգի բոլոր անհավասարությունները, և դրա մեջ օբյեկտիվ ֆունկցիայի արժեքը օպտիմալ է։ Ֆ* = 84.

Թեստ «Օպերացիոն հետազոտություն» առարկայից.

(ճիշտ պատասխաններն առաջինն են)

1. «Օպերացիաների հետազոտություն» տերմինը հայտնվել է ...

երկրորդ համաշխարհային պատերազմի ժամանակ

XX դարի 50-ական թթ

XX դարի 60-ական թթ

XX դարի 70-ական թթ

XX դարի 90-ական թթ

XXI դարի սկզբին

2. Գործառնությունների հետազոտման միջոցներ (ընտրեք ամենահարմար տարբերակը) ...

կազմակերպչական համակարգերի արդյունավետ կառավարման խնդիրների լուծման գիտական մեթոդների մի շարք

որոշակի գործողություններ իրականացնելու համար ձեռնարկված միջոցառումների համալիր

մշակված պլանի իրականացման մեթոդների մի շարք

արտադրության կազմակերպման մեջ ռեսուրսների բաշխման գիտական մեթոդներ

3. Կազմակերպեք այն քայլերը, որոնց միջով սովորաբար անցնում է ցանկացած գործառնական հետազոտություն.

խնդրի ձևակերպում

դիտարկվող օբյեկտի (գործընթացի) իմաստալից (բանավոր) մոդելի կառուցում.

մաթեմատիկական մոդելի կառուցում

կառուցված մաթեմատիկական մոդելի հիման վրա ձևակերպված խնդիրների լուծում

Ստացված արդյունքների ստուգում ուսումնասիրվող համակարգի բնույթի համարժեքության համար

ստացված լուծման գործնականում իրականացումը

4. Գործառնությունների հետազոտության մեջ գործողությունը հասկացվում է ...

ցանկացած իրադարձություն (գործողությունների համակարգ), որը միավորված է մեկ հայեցակարգով և ուղղված է նպատակին հասնելուն

ցանկացած անվերահսկելի իրադարձություն

սպառողական ապրանքների արտադրությունն ապահովելու տեխնիկական միջոցների համալիր

5. Լուծումը կոչվում է օպտիմալ, ...

եթե դա նախընտրելի է այս կամ այն պատճառով

եթե դա ռացիոնալ է

եթե դա համաձայնեցվի իշխանությունների հետ

եթե հաստատվի ընդհանուր ժողովի կողմից

6. Մաթեմատիկական ծրագրավորում ...

զբաղվում է ծայրահեղ խնդիրների ուսումնասիրությամբ և դրանց լուծման մեթոդների մշակմամբ

մաթեմատիկոսների ղեկավարությամբ համակարգչային ծրագրերի ստեղծման գործընթացն է

լուծում է մաթեմատիկական խնդիրներ համակարգչով

7. Գծային ծրագրավորման խնդիրն է ...

գտնել գծային ֆունկցիայի ամենամեծ (ամենափոքր) արժեքը գծային սահմանափակումների առկայության դեպքում

ստեղծելով գծային ծրագիր ընտրված ծրագրավորման լեզվով, որը նախատեսված է խնդիրը լուծելու համար

տրված խնդրի լուծման գծային ալգորիթմի նկարագրությունը

8. Քառակուսի ծրագրավորման խնդիրում ...

օբյեկտիվ ֆունկցիան քառակուսի է

թույլատրելի լուծույթների մակերեսը քառակուսի է

սահմանափակումները պարունակում են քառակուսի ֆունկցիաներ

9. Ամբողջ թվով ծրագրավորման խնդիրներում ...

անհայտները կարող են վերցնել միայն ամբողջական արժեքներ

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

նպատակային ֆունկցիան թվային հաստատուն է

10. Պարամետրային ծրագրավորման առաջադրանքներում ...

Օբյեկտիվ ֆունկցիան և/կամ սահմանափակող համակարգը պարունակում է պարամետր (ներ)

թույլատրելի լուծույթների տարածքը զուգահեռագիծ է կամ զուգահեռատիպ

փոփոխականների թիվը կարող է լինել միայն զույգ

11. Դինամիկ ծրագրավորման խնդիրներում ...

լուծում գտնելու գործընթացը բազմափուլ է

անհրաժեշտ է ռացիոնալացնել դինամիտի արտադրությունը

ցանկանում եք օպտիմալացնել բարձրախոսների օգտագործումը

12. Դրված է գծային ծրագրավորման հետեւյալ խնդիրը.

Ֆ(X 1, X 2) = 5X 1 + 6X 2→ առավելագույնը

0.2X 1 + 0.3X 2 ≤ 1.8,

0.2X 1 + 0.1X 2 ≤ 1.2,

0.3X 1 + 0.3X 2 ≤ 2.4,

X 1 ≥ 0, X 2 ≥ 0.

Ընտրեք առաջադրանք, որը համարժեք է այս առաջադրանքին:

Ֆ(X 1, X 2)= 5X 1 + 6X 2 → առավելագույնը,

2X 1 + 3X 2 ≤ 18,

2X 1 + X 2 ≤ 12,

X 1 + X 2 ≤ 8,

X 1 ≥ 0,

X 2 ≥ 0.

Ֆ(X 1, X 2)= 6X 1 + 5X 2 → րոպե,

2X 1 + 3X 2 ≤ 18,

2X 1 + X 2 ≤ 12,

X 1 + X 2 ≤ 8,

X 1 ≥ 0,

X 2 ≥ 0.

Ֆ(X 1, X 2)= 50X 1 + 60X 2 → առավելագույնը,

2X 1 + 3X 2 ≤ 18,

2X 1 + X 2 ≤ 12,

X 1 + X 2 ≤ 8,

X 1 ≥ 0,

X 2 ≥ 0.

Ֆ(X 1, X 2)= 5X 12 + 6X 22 → առավելագույնը,

2X 1 + 3X 2 ≤ 18,

2X 1 + X 2 ≤ 12,

3X 1 + X 2 ≤ 2.4,

X 1 ≥ 0,

X 2 ≥ 0.

13. Գծային ծրագրավորման խնդրի օբյեկտիվ ֆունկցիա կարող է լինել ֆունկցիան.

Ֆ=12x1+20x2-3 0x3→ր

Ֆ= →ր

Ֆ=→առավելագույնը

14. Գծային ծրագրավորման խնդրի սահմանափակումների համակարգը կարող է լինել համակարգը.

15. Սիմպլեքս մեթոդը հետևյալն է.

գծային ծրագրավորման հիմնական խնդրի լուծման վերլուծական մեթոդ

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

գծային ծրագրավորման հիմնական խնդրի լուծման գրաֆիկական մեթոդ.

Ընդհանուր գծային ծրագրավորման խնդիրը կանոնական ձևի վերածելու մեթոդ:

16. Գծային ծրագրավորման խնդիրն է.

գտնել գծային ֆունկցիայի ամենամեծ կամ ամենափոքր արժեքը գծային սահմանափակումների առկայության դեպքում

գծային ալգորիթմի մշակում և դրա իրականացում համակարգչում

գծային հավասարումների համակարգի կազմում և լուծում

սահմանափակումների տվյալ համակարգով նկարագրված գործընթացի զարգացման գծային հետագծի որոնումը։

17. Գծային ծրագրավորման խնդրի իրագործելի լուծումների տիրույթ չի կարողնայեք այսպես.

18. Գծային ծրագրավորման խնդրի թիրախային ֆունկցիան կարող է լինել.

Ֆ=12x1+20x2-3 0x3→ր

Ֆ= →ր

Ֆ=→առավելագույնը

19. Գծային ծրագրավորման խնդրի սահմանափակումների համակարգը կարող է լինել համակարգը.

20. Գծային ծրագրավորման խնդրի իրագործելի լուծումների շրջանը հետեւյալն է.

Ֆ(X 1, X 2)= 3X 1 + 5X 2 հավասար...

21. Գծային ծրագրավորման խնդրի իրագործելի լուծումների շրջանն ունի ձև.

Այնուհետև ֆունկցիայի առավելագույն արժեքը Ֆ(X 1, X 2)= 5X 1 + 3X 2 հավասար...

22. Գծային ծրագրավորման խնդրի իրագործելի լուծումների շրջանն ունի ձև.

Այնուհետև ֆունկցիայի առավելագույն արժեքը Ֆ(X 1, X 2)= 2X 1 - 2X 2 հավասար...

23. Գծային ծրագրավորման խնդրի իրագործելի լուծումների շրջանն ունի ձև.

Ֆ(X 1, X 2)= 2X 1 - 2X 2 հավասար...

24. Ոչ գծային ծրագրավորման խնդրի իրագործելի լուծումների շրջանն ունի ձև.

Այնուհետև ֆունկցիայի առավելագույն արժեքը Ֆ(X 1, X 2)= X 2 – X 12 հավասար...

25. Օբյեկտիվ ֆունկցիայի առավելագույն արժեքը Ֆ(X 1, X 2)= 5X 1 + 2X 2 սահմանափակումներով
X 1 + X 2 ≤ 6,

X 1 ≤ 4,

X 1 ≥ 0, X 2 ≥ 0, հավասար է ...

26. Փոքր բիզնեսը արտադրում է երկու տեսակի արտադրանք. A տիպի մեկ արտադրանքի արտադրության համար սպառվում է 2 կգ հումք, B տիպի մեկ ապրանքի արտադրության համար՝ 1 կգ։ Ընդհանուր առմամբ կա 60 կգ հումք։ Պահանջվում է կազմել արտադրության պլան, որն ապահովում է ամենամեծ հասույթի ստացումը, եթե Ա տեսակի մեկ ապրանքի վաճառքի արժեքը 3 միավոր է, Բ տիպը՝ 1 միավոր։ Այսինքն՝ Ա տիպի արտադրանքը պետք է պատրաստվի ոչ ավելի, քան 25, իսկ Բ տիպը՝ ոչ ավելի, քան 30։

Այս առաջադրանքը...

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

խնդիրը լուծված է դինամիկ ծրագրավորման մեթոդով

ցանցի պլանավորման խնդիր.

27. Փոքր բիզնեսը արտադրում է երկու տեսակի արտադրանք. A տիպի մեկ արտադրանքի արտադրության համար սպառվում է 2 կգ հումք, B տիպի մեկ ապրանքի արտադրության համար՝ 1 կգ։ Ընդհանուր առմամբ կա 60 կգ հումք։ Պահանջվում է կազմել արտադրության պլան, որն ապահովում է ամենամեծ հասույթի ստացումը, եթե Ա տեսակի մեկ ապրանքի վաճառքի արժեքը 3 միավոր է, Բ տիպը՝ 1 միավոր։ Այսինքն՝ Ա տիպի արտադրանքը պետք է պատրաստվի ոչ ավելի, քան 25, իսկ Բ տիպը՝ ոչ ավելի, քան 30։

Այս առաջադրանքի օբյեկտիվ գործառույթը գործառույթն է ...

Ֆ(x1, x2)=3x1+x2→առավելագույնը

Ֆ(x1, x2)=25x1+30x2→առավելագույնը

Ֆ(x1, x2)=2x1+x2→առավելագույնը

Ֆ(x1, x2)=60 -2x1 - x2→ր

28. Փոքր բիզնեսը արտադրում է երկու տեսակի արտադրանք. A տիպի մեկ արտադրանքի արտադրության համար սպառվում է 2 կգ հումք, B տիպի մեկ ապրանքի արտադրության համար՝ 1 կգ։ Ընդհանուր առմամբ կա 60 կգ հումք։ Պահանջվում է կազմել արտադրության պլան, որն ապահովում է ամենամեծ հասույթի ստացումը, եթե Ա տեսակի մեկ ապրանքի վաճառքի արժեքը 3 միավոր է, Բ տիպը՝ 1 միավոր։ Այսինքն՝ A տիպի արտադրանքը պետք է պատրաստվի ոչ ավելի, քան 25, իսկ B տիպը՝ ոչ ավելի, քան 30:

Այս առաջադրանքի համար վավեր պլանը պլանն է.

X =(20, 20)

X =(25, 15)

X =(20, 25)

X =(30, 10)

29. Երկու Ա1 և Ա2 կետերում առկա են համապատասխանաբար 60 և 160 միավոր ապրանքներ: Բոլոր ապրանքները անհրաժեշտ է տեղափոխել B1, B2, B3 կետեր՝ համապատասխանաբար 80, 70 և 70 միավոր: Սակագնային մատրիցը հետևյալն է. Պլանավորեք տրանսպորտը այնպես, որ արժեքը նվազագույն լինի:

Այս առաջադրանքը...

տրանսպորտային առաջադրանք

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

ճանապարհորդող վաճառողի խնդիր

հանձնարարական առաջադրանք

30. Երկու Ա1 և Ա2 կետերում առկա են համապատասխանաբար 60 և 160 միավոր ապրանքներ: Բոլոր ապրանքները անհրաժեշտ է տեղափոխել B1, B2, B3 կետեր՝ համապատասխանաբար 80, 70 և 70 միավոր: Սակագնային մատրիցը հետևյալն է. Պլանավորեք տրանսպորտը այնպես, որ արժեքը նվազագույն լինի

Այս առաջադրանքի հիմնական պլանը պլանն է.

;

31. Երկու Ա1 և Ա2 կետերում առկա են համապատասխանաբար 60 և 160 միավոր ապրանքներ: Բոլոր ապրանքները անհրաժեշտ է տեղափոխել B1, B2, B3 կետեր՝ համապատասխանաբար 80, 70 և 70 միավոր: Սակագնային մատրիցը հետևյալն է. Պլանավորեք տրանսպորտը այնպես, որ արժեքը նվազագույն լինի:

Այս առաջադրանքի նպատակային գործառույթը գործառույթն է.

Ֆ=4x11+6x12 + 8x13+5x21+8x22+7x23→ր

Ֆ= →ր

Ֆ=60x1+160x2 + 80x3+70x4+705 →առավելագույնը

Ֆ=60x1+160x2– 80x3– 70x4– 705 →ր

32. Երկու Ա1 և Ա2 կետերում առկա են համապատասխանաբար 60 և 160 միավոր ապրանքներ: Բոլոր ապրանքները անհրաժեշտ է տեղափոխել B1, B2, B3 կետեր՝ համապատասխանաբար 80, 70 և 70 միավոր: Սակագնային մատրիցը հետևյալն է. Պլանավորեք տրանսպորտը այնպես, որ արժեքը նվազագույն լինի:

Այս առաջադրանքի օպտիմալ պլանը պլանն է.

;

33. Տրանսպորտային խնդիր

կփակվի, եթե...

34. Տրանսպորտային խնդիր

մի…

բացել

փակված

անլուծելի

35. Տրանսպորտային խնդիր

մի…

փակված

բացել

անլուծելի

36. Լուծել տրանսպորտային հետեւյալ խնդիրը

դուք պետք է մուտքագրեք ...

ֆիկտիվ սպառող

ֆիկտիվ մատակարար;

արդյունավետ սակագին

37. Լուծել տրանսպորտային հետեւյալ խնդիրը

դուք պետք է մուտքագրեք ...

ֆիկտիվ մատակարար;

ֆիկտիվ սպառող

արդյունավետ սակագին

արդյունավետ տոկոսադրույք:

38. Այս տրանսպորտային խնդիրների շարքում

փակ են...

39. Տրանսպորտային խնդրի նախնական ելակետային պլանը կարող է կազմվել ...

վերը նշված բոլոր մեթոդներով

Հյուսիսարևմտյան անկյունի մեթոդ

նվազագույն սակագնի մեթոդով

կրկնակի նախապատվության մեթոդ

Ֆոգելի մոտավոր մեթոդով

40. Եթե գծային ծրագրավորման խնդրի օբյեկտիվ ֆունկցիան դրված է առավելագույնի, ապա ... երկակի խնդրի օբյեկտիվ ֆունկցիան սահմանվում է նվազագույնի.

երկակի խնդրի մեջ օբյեկտիվ ֆունկցիա չկա

երկակի խնդիրը լուծումներ չունի

երկակի խնդիրը անսահման շատ լուծումներ ունի

41. Տրված է գծային ծրագրավորման խնդիր.

Ֆ(X 1, X 2)= 2X 1 + 7X 2 → առավելագույնը,

2X 1 + 3X 2 ≤ 14,

X 1 + X 2 ≤ 8,

X 1 ≥ 0, X 2 ≥ 0.

Այս առաջադրանքի համար հետևյալը կրկնակի կլինի...

Զ *(y1, y2) = 14y1 + 8y2 → ր,

3տ 1 + y2 ³ 7,

y 1 ≥ 0, y2 ≥ 0:

Զ *(y1, y2) = 2y1 + 7y2 → ր,

2y1 + 3y2 ³ 14,

y 1 + y2 ³ 8,

y 1 £ 0, y2 £ 0:

Զ *(y1, y2) = 2y1 + 7y2 → ր,

3 y 1 + y2 ³ 7,

y 1 £ 0, y2 £ 0:

Զ *(y1, y2) = 14y1 + 8y2 → ր,

y 1 + y2 ³ 7,

y 1 ≥ 0, y2 ≥ 0:

42. Եթե զույգ խնդիրներից մեկն ունի օպտիմալ պլան, ապա ...

իսկ մյուսն ունի օպտիմալ պլան

մյուսը չունի օպտիմալ պլան

մյուսը իրագործելի լուծումներ չունի

43. Եթե զույգ խնդիրներից մեկն ունի օպտիմալ պլան, ապա ...

իսկ մյուսն ունի օպտիմալ պլան, և դրանց օպտիմալ պլանների համար օբյեկտիվ գործառույթների արժեքները հավասար են միմյանց

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

մեկ այլ խնդիր կարող է չունենալ օպտիմալ պլան, բայց ունենալ իրագործելի լուծումներ

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

մեկ այլ առաջադրանք չունի վավեր պլաններ

մեկ այլ խնդիր ունի իրագործելի պլաններ, բայց չունի օպտիմալ պլան

Մեկ այլ առաջադրանքի օբյեկտիվ գործառույթը նույնպես սահմանափակված չէ

45. Ոչ գծային ծրագրավորման որոշ խնդիրներ լուծելիս օգտագործվում է ...

Լագրանժի բազմապատկիչ մեթոդ

Գաուսի մեթոդ

Ֆոգելի մոտարկման մեթոդ

Գոմորի մեթոդ

46. Սահմանված է ոչ գծային ծրագրավորման խնդիրը

Ֆ(X 1, X 2)= X 12 + X 22 → առավելագույնը,

X 1 + X 2 =6,

X 1 ≥ 0, X 2 ≥ 0.

Ֆ(X 1, X 2) …

անհասանելի (+ ¥)

47. Դրված է ոչ գծային ծրագրավորման խնդիրը

Ֆ(X 1, X 2)= X 12 + X 22 → մմեջ,

X 1 + X 2 =6,

X 1 ≥ 0, X 2 ≥ 0.

Ֆ(X 1, X 2) …

48. Դրված է ոչ գծային ծրագրավորման խնդիրը

Ֆ(X 1, X 2)= X 12 + X 22 → առավելագույնը,

X 1 + X 2 =6,

X 1, X 2 - ցանկացած:

Օբյեկտիվ ֆունկցիայի ամենաբարձր արժեքը Ֆ(X 1, X 2) …

անհասանելի (+ ¥)

49. Դրված է ոչ գծային ծրագրավորման խնդիրը

Ֆ(X 1, X 2)= X 12 + X 22 → մմեջ,

X 1 + X 2 =6,

X 1, X 2 - ցանկացած:

Օբյեկտիվ ֆունկցիայի ամենափոքր արժեքը Ֆ(X 1, X 2) …

անհասանելի (- ¥)

50. Ոչ գծային ծրագրավորման խնդրի իրագործելի լուծումների շրջանն ունի ձև.

Այնուհետև ֆունկցիայի առավելագույն արժեքը Ֆ(X 1, X 2)= X 12 +X 22 հավասար է ...

51. Ոչ գծային ծրագրավորման խնդրի իրագործելի լուծումների շրջանն ունի ձև.

Այնուհետև ֆունկցիայի նվազագույն արժեքը Ֆ(X 1, X 2)= X 12 +X 22 հավասար է ...

52. Տրանսպորտային խնդրի լուծման համար կարող են կիրառվել ...

պոտենցիալ մեթոդ

Լագրանժի բազմապատկիչ մեթոդ

Գաուսի մեթոդ

ապակողմնորոշման մեթոդ

53. Ընդհանուր գծային ծրագրավորման խնդրի սահմանափակումների համակարգում ...

54. Ստանդարտ (սիմետրիկ) գծային ծրագրավորման խնդրի սահմանափակումների համակարգում ...

կարող են լինել միայն անհավասարություններ

կարող են լինել և՛ հավասարումներ, և՛ անհավասարություններ

կարող են լինել միայն հավասարումներ

55. Կանոնական (հիմնական) գծային ծրագրավորման խնդրի սահմանափակումների համակարգում ...

կարող են լինել միայն հավասարումներ (պայմանով, որ փոփոխականները ոչ բացասական են)

կարող են լինել միայն անհավասարություններ (պայմանով, որ փոփոխականները ոչ բացասական են)

և՛ հավասարումները, և՛ անհավասարությունները կարող են ներկա լինել (պայմանով, որ փոփոխականները ոչ բացասական են)

56. Գծային ծրագրավորման խնդիրը

Ֆ(X 1, X 2)= 2X 1 + 7X 2 → առավելագույնը,

2X 1 + 3X 2 ≤ 14,

X 1 + X 2 ≤ 8,

X 1 ≥ 0, X 2 ≥ 0.

արձանագրված է...

ստանդարտ (սիմետրիկ) ձև

կանոնական (հիմնական) ձև

բանավոր ձև

57. Առաջադրանք արձանագրելու համար

Ֆ(X 1, X 2)= 2X 1 + 7X 2 → առավելագույնը,

2X 1 + 3X 2 ≤ 14,

X 1 + X 2 ≤ 8,

X 1 ≥ 0, X 2 ≥ 0.

կանոնական ձևով...

58. Առաջադրանք արձանագրելու համար

Ֆ(X 1, X 2)= 2X 1 + 7X 2 → առավելագույնը,

2X 1 + 3X 2 ≤ 14,

X 1 + X 2 ≤ 8,

X 1 + 4X 2 ≥ 10,

X 1 ≥ 0, X 2 ≥ 0.

կանոնական ձևով...

անհրաժեշտ է ներմուծել երեք լրացուցիչ ոչ բացասական փոփոխականներ

անհրաժեշտ է ներմուծել երկու լրացուցիչ ոչ բացասական փոփոխականներ

անհրաժեշտ է ներմուծել չորս լրացուցիչ ոչ բացասական փոփոխականներ

59. Առաջադրանք արձանագրելու համար

Ֆ(X 1, X 2)= 2X 1 + 7X 2 → առավելագույնը,

2X 1 + 3X 2 = 14,

X 1 + X 2 ≤ 8,

X 1 + 4X 2 ≥ 10,

X 1 ≥ 0, X 2 ≥ 0.

կանոնական ձևով...

անհրաժեշտ է ներմուծել երկու լրացուցիչ ոչ բացասական փոփոխականներ

անհրաժեշտ է ներմուծել երեք լրացուցիչ ոչ բացասական փոփոխականներ

անհրաժեշտ է ներմուծել չորս լրացուցիչ ոչ բացասական փոփոխականներ

անհրաժեշտ է ներդնել հինգ լրացուցիչ ոչ բացասական փոփոխականներ

60. Ամբողջ թվային ծրագրավորման խնդիրներ լուծելիս կարելի է օգտագործել ...

Գոմորի մեթոդ

Լագրանժի բազմապատկիչ մեթոդ

Գաուսի մեթոդ

Ֆոգելի մոտարկման մեթոդ

61. Դինամիկ ծրագրավորման մեթոդով խնդիրների լուծման հիմքում ընկած է ...

Օքամի ածելի

«ատամ ատամի դիմաց, աչք աչքի դիմաց» սկզբունքը.

Հայզենբերգի սկզբունքը

62. Իրավիճակը, որում ներգրավված են կողմեր, որոնց շահերը լրիվ կամ մասնակի հակառակ են, կոչվում է ...

(հակամարտություն, կոնֆլիկտ, կոնֆլիկտ, կոնֆլիկտ)

63. Փաստացի կամ ֆորմալ հակամարտությունը, որտեղ կան առնվազն երկու մասնակից (խաղացողներ), որոնցից յուրաքանչյուրը ձգտում է հասնել իր նպատակներին, կոչվում է ...

(խաղ, խաղ)

64. Խաղացողներից յուրաքանչյուրի թույլատրելի գործողությունները, որոնք ուղղված են որոշակի նպատակին, կոչվում են ...

(խաղի կանոններ, խաղի կանոններ)

65. Խաղի արդյունքների քանակական գնահատումը կոչվում է ...

(վճարմամբ, վճարմամբ, վճարմամբ)

66. Եթե խաղին մասնակցում է միայն երկու կողմ (երկու հոգի), ապա խաղը կոչվում է ...

(դուբլ, դուբլ, դուբլ, դուբլ)

67. Եթե զուգախաղում վճարումների գումարը հավասար է զրոյի, այսինքն՝ մի խաղացողի կորուստը հավասար է մյուսի շահին, ապա խաղը կոչվում է խաղ ...

(զրոյական գումար)

68. Խաղացողի ընտրության միանշանակ նկարագրությունը հնարավոր իրավիճակներից յուրաքանչյուրում, երբ նա պետք է անձնական քայլ կատարի, կոչվում է ..

(խաղացողի ռազմավարություն, խաղացողի ռազմավարություն, ռազմավարություն, ռազմավարություն)

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

(օպտիմալ, օպտիմալ, օպտիմալ ռազմավարություն, օպտիմալ ռազմավարություն)

70. Թողեք a-ն լինի ցածր գինը, իսկ b-ը՝ զրոյական գումարով կրկնապատկված խաղի: Հետո հայտարարությունը ճշմարիտ է...

71. Թողեք a-ն լինի ցածր գինը, իսկ b-ը՝ զրոյական գումարով կրկնապատկված խաղի: Եթե a = b = v, ապա v թիվը կոչվում է ...

խաղի գնով

հավասարակշռության կետ

օպտիմալ ռազմավարություն

խառը ռազմավարություն

72. Թողեք a-ն լինի ցածր գինը, իսկ b-ը՝ զրոյական գումարով կրկնապատկված խաղի: Եթե a = b, ապա խաղը կոչվում է ...

թամբի կետ խաղ

անլուծելի հակամարտություն

խաղ առանց կանոնների

73. Վեկտորը, որի բաղադրիչներից յուրաքանչյուրը ցույց է տալիս խաղացողի կողմից համապատասխան մաքուր ռազմավարության կիրառման հարաբերական հաճախականությունը, կոչվում է ...

խառը ռազմավարություն

ուղղության վեկտոր

նորմալ վեկտոր

գրադիենտ

74. Վճարային մատրիցով տրված մատրիցային խաղի ավելի ցածր գինը հավասար է ...

Ավելի ցածր գին

հավասար է ստորին գնին

գոյություն չունի

81. Մատրիցային խաղ, որը տրվում է վճարման մատրիցով, ...

ունի թամբի կետ

թամբի կետ չունի

զուգակցված չէ

82. Խաղի գինը, որը տրվում է վճարման մատրիցով, կազմում է ...

83. Մատրիցային խաղ, որը տրվում է վճարման մատրիցով ...

զուգակցված է

ունի թամբի կետ

զուգակցված չէ

84. Զրոյական գումարով կրկնակի խաղը, որը տրված է իր վճարման մատրիցով, կարող է կրճատվել մինչև ...

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

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

ամբողջ թվով գծային ծրագրավորման խնդիր

դասական օպտիմալացման խնդիր

85. Վճարային մատրիցով տրված մատրիցային խաղի ավելի ցածր գինը կազմում է ...

Ավելի ցածր գին

հավասար է ստորին գնին

գոյություն չունի

92. Մատրիցային խաղ, որը տրվում է վճարման մատրիցով ...

թամբի կետ չունի

ունի թամբի կետ

զուգակցված չէ

93. Վճարային մատրիցով տրված խաղի գինը գտնվում է ...

94. Եթե իրադարձությունների հոսքում իրադարձությունները հաջորդում են միմյանց կանխորոշված և խիստ սահմանված ժամանակային ընդմիջումներով, ապա այդպիսի հոսքը կոչվում է ...

կանոնավոր

կազմակերպված

95. Եթե որևէ թվով իրադարձությունների՝ ժամանակային միջակայքում ընկնելու հավանականությունը կախված է միայն այս ինտերվալի երկարությունից և կախված չէ նրանից, թե որքան հեռու է այդ միջակայքը ժամանակի սկզբից, ապա իրադարձությունների համապատասխան հոսքը կոչվում է.

ստացիոնար

հոսք առանց հետևանքների

ամենապարզը

Պուասոն

96. Եթե կամայականորեն ընտրված ժամանակային ընդմիջումներից մեկի վրա ընկած իրադարձությունների թիվը կախված չէ մեկ այլ, նաև կամայականորեն ընտրված ժամանակային միջակայքի վրա ընկած իրադարձությունների քանակից, պայմանով, որ այդ միջակայքերը չհատվեն, ապա իրադարձությունների համապատասխան հոսքը կոչվում է. ...

հոսք առանց հետևանքների

կանոնավոր

ցուցիչ

նորմալ

97. Եթե երկու կամ ավելի իրադարձությունների՝ միանգամից շատ կարճ ժամանակամիջոցի դիպչելու հավանականությունը չնչին է միայն մեկ իրադարձության հարվածելու հավանականության համեմատ, ապա իրադարձությունների համապատասխան հոսքը կոչվում է ...

սովորական

արտասովոր

նորմալ

Պուասոն

98. Եթե իրադարձությունների հոսքը միաժամանակ տիրապետում է կայունության, սովորականության և հետևանքների բացակայության հատկություններին, ապա այն կոչվում է.

ամենապարզ (Poisson)

նորմալ

99. Խափանումներով միակողմանի համակարգը ավտոլվացման համար նախատեսված ամենօրյա սպասարկման կայան է: Դիմում - մեքենա, որը ժամանել է այն պահին, երբ պաշտոնը զբաղեցված է, ստանում է ծառայության մերժում: Ավտոմեքենայի հոսքի արագությունը λ = 1.0 (մեքենան մեկ ժամում): Սպասարկման միջին ժամանակը 1,8 ժամ է: Ավտոմեքենաների հոսքը և սպասարկման հոսքը ամենապարզն են: Այնուհետև, կայուն վիճակում, հարաբերական թողունակությունը քհավասար է...

100. Խափանումներով մեկ ալիքային համակարգը ավտոլվացման ամենօրյա սպասարկման կետ է: Դիմում - մեքենա, որը ժամանել է այն պահին, երբ պաշտոնը զբաղեցված է, ստանում է ծառայության մերժում: Ավտոմեքենայի հոսքի արագությունը λ = 1.0 (մեքենան մեկ ժամում): Սպասարկման միջին ժամանակը 1,8 ժամ է: Ավտոմեքենաների հոսքը և սպասարկման հոսքը ամենապարզն են: Այնուհետև կայուն վիճակում սպասարկման մերժում ստացած մեքենաների տոկոսը կազմում է ...

Գծային ծրագրավորման խնդրի (LPP) ընդհանուր ձևակերպում. LPP-ի օրինակներ

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

- արտադրության պլանավորման մեջ ռեսուրսների օպտիմալ օգտագործման խնդիրը.
- խառնուրդների խնդիրը (արտադրանքի կազմի պլանավորում);
- պահեստներում պահեստավորման համար տարբեր տեսակի ապրանքների օպտիմալ համադրություն գտնելու խնդիրը (գույքագրման կառավարում կամ «պայուսակի խնդիր»);
- տրանսպորտային առաջադրանքներ (ձեռնարկության գտնվելու վայրի վերլուծություն, ապրանքների տեղաշարժ): Գծային ծրագրավորումը մաթեմատիկական ծրագրավորման ամենազարգացած և լայնորեն կիրառվող ճյուղն է (ի լրումն, սա ներառում է` ամբողջ թվեր, դինամիկ, ոչ գծային, պարամետրային ծրագրավորում): Սա պայմանավորված է հետևյալով.
- մեծ թվով տնտեսական խնդիրների մաթեմատիկական մոդելները գծային են փնտրվող փոփոխականների նկատմամբ.
- այս տիպի խնդիրը ներկայումս ամենաուսումնասիրվածն է: Նրա համար մշակվել են հատուկ մեթոդներ, որոնց օգնությամբ լուծվում են այս խնդիրները, և համապատասխան համակարգչային ծրագրեր;
- գծային ծրագրավորման բազմաթիվ խնդիրներ, լուծված լինելով, լայն կիրառություն են գտել.
- որոշ խնդիրներ, որոնք սկզբնական ձևակերպման մեջ գծային չեն, մի շարք լրացուցիչ սահմանափակումներից և ենթադրություններից հետո կարող են դառնալ գծային կամ կրճատվել այնպիսի ձևի, որ դրանք լուծվեն գծային ծրագրավորման մեթոդներով: Գծային ծրագրավորման ցանկացած խնդրի տնտեսական և մաթեմատիկական մոդելը ներառում է՝ օբյեկտիվ ֆունկցիա, որի օպտիմալ արժեքը (առավելագույնը կամ նվազագույնը) պետք է գտնել. սահմանափակումներ գծային հավասարումների կամ անհավասարությունների համակարգի տեսքով. փոփոխականների ոչ բացասականության պահանջը: Ընդհանուր առմամբ, մոդելը գրված է հետևյալ կերպ.
- նպատակային գործառույթ.

C1x1 + c2x2 + ... + cnxn> max (min); - սահմանափակումներ.

a11x1 + a12x2 + ... + a1nxn (? =?) b1,

a21x1 + a22x2 + ... + a2nxn (? =?) b2

am1x1 + am2x2 + ... + amnxn (? =?) bm;

Ոչ բացասական պահանջ.

Այս դեպքում aij, bi, cj () հաստատուններ են տրվում: Խնդիրը (2.1) ֆունկցիայի օպտիմալ արժեքը գտնելն է, որը ենթակա է սահմանափակումների (2.2) և (2.3): Սահմանափակումների համակարգը (2.2) կոչվում է խնդրի ֆունկցիոնալ սահմանափակում, իսկ սահմանափակումները (2.3)՝ ուղղակի։ Վեկտորը, որը բավարարում է սահմանափակումները (2.2) և (2.3) կոչվում է գծային ծրագրավորման խնդրի իրագործելի լուծում (պլան): Դիզայնը, որտեղ ֆունկցիան (2.1) հասնում է իր առավելագույն (նվազագույն) արժեքին, կոչվում է օպտիմալ:

Ստորև բերված են գծային ծրագրավորման մեթոդներով լուծված որոշ բնորոշ խնդիրների օրինակներ: Նման առաջադրանքները իրական տնտեսական բովանդակություն ունեն։ Այժմ դրանք կձևակերպենք միայն LPP-ի մասով, իսկ նման խնդիրների լուծման մեթոդները կդիտարկենք ստորև։

1. Արտադրության պլանավորման մեջ ռեսուրսների օպտիմալ օգտագործման խնդիրը. Այս դասի առաջադրանքների ընդհանուր իմաստը հետևյալն է. Ձեռնարկությունն արտադրում է n տարբեր ապրանքներ։ Դրանց արտադրությունը պահանջում է տարբեր տեսակի ռեսուրսներ (հումք, նյութեր, աշխատաժամանակ և այլն): Ռեսուրսները սահմանափակ են, դրանց պաշարները պլանավորման ժամանակաշրջանում համապատասխանաբար b1, b2, ..., bm պայմանական միավորներն են: Հայտնի են նաև aij տեխնոլոգիական գործակիցները, որոնք ցույց են տալիս, թե քանի միավոր i-րդ ռեսուրս է պահանջվում j-րդ տեսակի արտադրանքի միավոր արտադրելու համար (): j-րդ տեսակի արտադրանքի վաճառքից ձեռնարկության ստացած շահույթը հավասար է cj. Պլանավորման ժամանակաշրջանում aij, bi և cj արժեքները մնում են հաստատուն: Պահանջվում է այնպիսի արտադրական պլան կազմել, որի իրականացման դեպքում ձեռնարկության շահույթը կլինի ամենամեծը։ Ստորև բերված է այս դասի առաջադրանքի պարզ օրինակ:

Ընկերությունը մասնագիտացած է հոկեյի ձողիկների և շախմատի հավաքածուների արտադրության մեջ։ Յուրաքանչյուր ակումբ ընկերության համար ստանում է 2 դոլար շահույթ, իսկ յուրաքանչյուր շախմատային հավաքածուի համար՝ 4 դոլար: A-ում մեկ ակումբ ստեղծելու համար պահանջվում է չորս ժամ, իսկ B-ում` երկու ժամ: Շախմատի հավաքածուն պատրաստվում է վեց ժամով A կայքում, վեց ժամով` B կայքում և մեկ ժամով` C կայքում: 120 Նմ - օրական ժամ, հատված B - 72 n-ժամ և հատված C - 10 n-ժամ: Քանի՞ ակումբ և շախմատային հավաքածու պետք է արտադրի ընկերությունը օրական՝ առավելագույն շահույթ ստանալու համար:

Այս դասի խնդիրների պայմանները հաճախ ներկայացված են աղյուսակային տեսքով (տես Աղյուսակ 2.1):

Այս պայմանով մենք ձևակերպում ենք գծային ծրագրավորման խնդիր։ Նշանակենք՝ x1՝ օրական արտադրվող հոկեյի ձողիկների քանակը, x2՝ օրական արտադրվող շախմատի հավաքածուների քանակը։ ZLP ձևակերպում.

4x1 + 6x2? 120,

Ընդգծենք, որ ֆունկցիոնալ սահմանափակումների համակարգում յուրաքանչյուր անհավասարություն այս դեպքում համապատասխանում է այս կամ այն արտադրամասին, այն է՝ առաջինը՝ A տեղանքին, երկրորդը՝ B տեղամասին, երրորդը՝ C տեղամասին։

Ցանքատարածությունների կառուցվածքի օպտիմալացման խնդրի փոփոխականների համակարգը՝ հաշվի առնելով ցանքաշրջանառությունը