Օբյեկտիվ ֆունկցիայի օպտիմալ արժեքը կոչվում է. Գծային ծրագրավորման խնդիրների լուծում գրաֆիկական մեթոդով

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

Մենք ուղիղ գծեր ենք կառուցում 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

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

ՎԵՐԱՀՍԿՈՂԱԿԱՆ ԱՇԽԱՏԱՆՔ ԿԱՐԳԱՊԵՏՈՒԹՅԱՆ ՎՐԱ.

«ՕՊՏԻՄԱԼ ԼՈՒԾՈՒՄՆԵՐԻ ՄԵԹՈԴՆԵՐԸ»

Տարբերակ թիվ 8

1. Որոշեք գրաֆիկական մեթոդգծային ծրագրավորման խնդիր. Տրված սահմանափակումներով գտե՛ք  ֆունկցիայի առավելագույնը և նվազագույնը.

,

.

Լուծում

Սահմանափակումների համակարգի ներքո անհրաժեշտ է գտնել օբյեկտիվ ֆունկցիայի նվազագույն արժեքը և առավելագույնը.

9x 1 +3x 2 ≥30, (1)

X 1 +x 2 ≤4, (2)

x 1 +x 2 ≤8, (3)

Եկեք կառուցենք իրագործելի լուծումների տարածաշրջան, այսինքն. Անհավասարությունների համակարգը գրաֆիկորեն լուծենք։ Դա անելու համար մենք կառուցում ենք յուրաքանչյուր ուղիղ գիծ և սահմանում անհավասարություններով սահմանված կիսահարթությունները (կիսահարթությունները նշվում են պարզով):

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

Կառուցենք F = 0 ֆունկցիայի արժեքին համապատասխանող ուղիղ գիծ՝ F = 2x 1 +3x 2 = 0։ Գրադիենտի վեկտորը, որը կազմված է օբյեկտիվ ֆունկցիայի գործակիցներից, ցույց է տալիս F(X) նվազագույնի հասցնելու ուղղությունը։ Վեկտորի սկիզբը կետն է (0; 0), վերջը կետը (2; 3): Մենք այս ուղիղ գիծը կշարժենք զուգահեռաբար։ Քանի որ մեզ հետաքրքրում է նվազագույն լուծումը, հետևաբար մենք ուղիղ գիծը տեղափոխում ենք այնքան ժամանակ, մինչև այն առաջինը դիպչի նշանակված տարածքին: Գրաֆիկի վրա այս ուղիղ գիծը նշվում է կետավոր գծով:

Ուղիղ
հատում է շրջանը C կետում: Քանի որ C կետը ստացվել է (4) և (1) ուղիղների հատման արդյունքում, դրա կոորդինատները բավարարում են այս ուղիղների հավասարումները.
.

Հավասարումների համակարգը լուծելով՝ ստանում ենք՝ x 1 = 3,3333, x 2 = 0:

Ինչպես կարող ենք գտնել օբյեկտիվ ֆունկցիայի նվազագույն արժեքը.

Եկեք դիտարկենք թիրախային գործառույթառաջադրանքներ.

Կառուցենք F = 0 ֆունկցիայի արժեքին համապատասխանող ուղիղ գիծ՝ F = 2x 1 +3x 2 = 0։ Գրադիենտի վեկտորը, որը կազմված է օբյեկտիվ ֆունկցիայի գործակիցներից, ցույց է տալիս F(X) առավելագույնի հասցնելու ուղղությունը։ Վեկտորի սկիզբը կետն է (0; 0), վերջը կետը (2; 3): Մենք այս ուղիղ գիծը կշարժենք զուգահեռաբար։ Քանի որ մեզ հետաքրքրում է առավելագույն լուծումը, հետևաբար մենք ուղիղ գիծը տեղափոխում ենք մինչև նշանակված տարածքի վերջին հպումը: Գրաֆիկի վրա այս ուղիղ գիծը նշվում է կետավոր գծով:

Ուղիղ
հատում է շրջանը B կետում: Քանի որ B կետը ստացվում է (2) և (3) ուղիղների հատման արդյունքում, դրա կոորդինատները բավարարում են այս ուղիղների հավասարումները.

.

Ինչպես կարող ենք գտնել օբյեկտիվ ֆունկցիայի առավելագույն արժեքը.

Պատասխան.
Եվ
.

2 . Լուծել գծային ծրագրավորման խնդիր՝ օգտագործելով simplex մեթոդը.

.

Լուծում

Եկեք լուծենք ուղղակի գծային ծրագրավորման խնդիր՝ օգտագործելով սիմպլեքս մեթոդը, օգտագործելով սիմպլեքս աղյուսակը։

Որոշենք օբյեկտիվ ֆունկցիայի նվազագույն արժեքը
հետևյալ պայմաններով` սահմանափակումներով.
.

Առաջին հղման պլանը կառուցելու համար մենք անհավասարությունների համակարգը վերածում ենք հավասարումների համակարգի՝ ներմուծելով լրացուցիչ փոփոխականներ:

Իմաստի 1-ին անհավասարության մեջ (≥) ներկայացնում ենք հիմնական փոփոխականը x 3 մինուս նշանով. Իմաստի 2-րդ անհավասարության մեջ (≤) ներկայացնում ենք հիմնական փոփոխականը x 4 . Իմաստի 3-րդ անհավասարության մեջ (≤) ներկայացնում ենք x 5 հիմնական փոփոխականը։

Ներկայացնենք արհեստական ​​փոփոխականներ 1-ին հավասարության մեջ ներմուծում ենք փոփոխական x 6 ;

Խնդիրը նվազագույնի հասցնելու համար օբյեկտիվ ֆունկցիան գրում ենք հետևյալ կերպ.

Օբյեկտիվ ֆունկցիայի մեջ ներմուծված արհեստական ​​փոփոխականների օգտագործման համար սահմանվում է այսպես կոչված M-ի տույժ, շատ մեծ դրական թիվ, որը սովորաբար չի նշվում։

Ստացված հիմքը կոչվում է արհեստական, իսկ լուծման մեթոդը՝ արհեստական ​​հիմքի մեթոդ։

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

Հավասարումներից մենք արտահայտում ենք արհեստական ​​փոփոխականներ՝ x 6 = 4-x 1 -x 2 +x 3, որոնք փոխարինում ենք օբյեկտիվ ֆունկցիայի՝ or.

Գործակիցների մատրիցա
Այս հավասարումների համակարգը ունի ձև.
.

Եկեք լուծենք հիմնական փոփոխականների հավասարումների համակարգը. x 6 , x 4 , x 5.

Ենթադրելով, որ ազատ փոփոխականները հավասար են 0-ի, մենք ստանում ենք առաջինը տեղեկանք պլան:

X1 = (0,0,0,2,10,4)

Հիմնական լուծումը կոչվում է թույլատրելի, եթե այն ոչ բացասական է:

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Ներկայիս հղման պլանը օպտիմալ չէ, քանի որ ինդեքսի տողում կան դրական գործակիցներ: Որպես առաջատար սյունակ՝ մենք կընտրենք x 2 փոփոխականին համապատասխանող սյունակը, քանի որ սա ամենամեծ գործակիցն է։ Եկեք հաշվարկենք արժեքները Դ ես և դրանցից ընտրում ենք ամենափոքրը՝ min(4: 1, 2: 2, 10: 2) = 1:

Հետեւաբար, 2-րդ տողը առաջատարն է։

Լուծող տարրը հավասար է (2) և գտնվում է առաջատար սյունակի և առաջատար շարքի խաչմերուկում:

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Մենք կազմում ենք սիմպլեքս աղյուսակի հաջորդ մասը։ x 4 փոփոխականի փոխարեն պլան 1-ը կներառի x 2 փոփոխականը:

Պլան 1-ում x 2 փոփոխականին համապատասխանող տողը ստացվում է 0 պլանի x 4 շարքի բոլոր տարրերը RE = 2 լուծող տարրի բաժանելով: Լուծող տարրի տեղում ստանում ենք 1. x 2 սյունակի մնացած վանդակներում գրում ենք զրոներ։

Այսպիսով, նոր պլան 1-ում լրացվում են x 2 տողը և x 2 սյունակը: Նոր պլան 1-ի մյուս բոլոր տարրերը, ներառյալ ինդեքսային շարքի տարրերը, որոշվում են ուղղանկյունի կանոնով:

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 2
x 5
		1 1/2 +1 1/2 Մ

Ներկայիս հղման պլանը օպտիմալ չէ, քանի որ ինդեքսի տողում կան դրական գործակիցներ: Որպես առաջատար սյունակ՝ մենք կընտրենք x 1 փոփոխականին համապատասխանող սյունակը, քանի որ սա ամենամեծ գործակիցն է։ Եկեք հաշվարկենք արժեքները Դ եսըստ շարքի՝ որպես բաժանման գործակից. և դրանցից ընտրում ենք ամենափոքրը՝ min (3: 1 1/2, -, 8: 2) = 2:

Հետեւաբար, 1-ին տողը առաջատարն է։

Լուծող տարրը հավասար է (1 1/2) և գտնվում է առաջատար սյունակի և առաջատար շարքի խաչմերուկում։

		x 1	x 2	x 3	x 4	x 5	x 6
x 6		1 1 / 2
x 2
x 5
		-1 1 / 2 +1 1 / 2 Մ

Մենք կազմում ենք սիմպլեքս աղյուսակի հաջորդ մասը։ x 6 փոփոխականի փոխարեն պլան 2-ը կներառի x 1 փոփոխականը:

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

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Ինդեքսի լարային արժեքների մեջ դրական արժեքներ չկան: Հետևաբար, այս աղյուսակը որոշում է խնդրի օպտիմալ պլանը:

Սիմպլեքս աղյուսակի վերջնական տարբերակը.

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Քանի որ օպտիմալ լուծման մեջ արհեստական ​​փոփոխականներ չկան (դրանք հավասար են զրոյի), այս լուծումը թույլատրելի է։

Օպտիմալ պլանը կարելի է գրել հետևյալ կերպ՝ x 1 = 2, x 2 = 2:

Պատասխանել:
,
.

3. Three Fat Men ընկերությունը քաղաքի տարբեր հատվածներում գտնվող երեք պահեստներից միս պահածոներ է առաքում երեք խանութ։ Պահեստներում առկա պահածոների պաշարները, ինչպես նաև խանութների պատվերների և առաքման սակագների ծավալները (սովորական դրամական միավորներով) ներկայացված են տրանսպորտային աղյուսակում:

Գտեք տրանսպորտային պլան, որն ապահովում է նվազագույն դրամական ծախսեր (կատարեք փոխադրման սկզբնական պլանը՝ օգտագործելով «հյուսիսարևմտյան անկյուն» մեթոդը):

Լուծում

Եկեք ստուգենք խնդրի լուծելիության անհրաժեշտ և բավարար պայմանը.

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

Բալանսային պայմանը պահպանված է։ Ապահովում է հավասար կարիքներ: Հետեւաբար, մոդելը տրանսպորտի խնդիրփակ է։

Եկեք մուտքագրենք նախնական տվյալները բաշխման աղյուսակում:

Կարիքներ

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

Պլանը սկսում է լրացնել վերին ձախ անկյունից:

Պահանջվող տարրը 4-ն է: Այս տարրի համար պաշարները 300 են, պահանջները՝ 250: Քանի որ նվազագույնը 250 է, մենք այն հանում ենք.

			300 - 250 = 50
250 - 250 = 0

Պահանջվող տարրը հավասար է 2-ի: Այս տարրի համար պաշարները 50 են, պահանջները՝ 400: Քանի որ նվազագույնը 50 է, մենք այն հանում ենք.

			50 - 50 = 0
	400 - 50 = 350

Պահանջվող տարրը 5 է: Այս տարրի համար պաշարները 300 են, պահանջները՝ 350: Քանի որ նվազագույնը 300 է, մենք այն հանում ենք.

			300 - 300 = 0
	350 - 300 = 50

Ձեր փնտրած տարրը 3 է: Այս տարրի համար պաշարները 200 են, պահանջները՝ 50: Քանի որ նվազագույնը 50 է, մենք այն հանում ենք.

			200 - 50 = 150
	50 - 50 = 0

Պահանջվող տարրը 6 է: Այս տարրի համար պաշարները 150 են, պահանջները՝ 150: Քանի որ նվազագույնը 150 է, մենք այն հանում ենք.

			150 - 150 = 0
		150 - 150 = 0

Կարիքներ

Լաբորատոր աշխատանք թիվ 1. Գծային ծրագրավորման խնդիրների լուծում

Աշխատանքի նպատակըԳրաֆիկական, սիմպլեքս և Էքսել մեթոդներով գծային ծրագրավորման խնդիրների լուծման հմտությունների ձեռքբերում։

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

Երկրաչափական լուծման մեթոդ ԻԵկեք նայենք գծային ծրագրավորման խնդիրներին՝ օգտագործելով օրինակ:

Օրինակ. Գտեք նպատակային ֆունկցիայի առավելագույն արժեքը Լ=2x 1 +2x 2-ը նշված սահմանափակումների ներքո

Լուծում.Եկեք կառուցենք սահմանափակումների համակարգի լուծման տիրույթը՝ փոխելով անհավասարությունների նշանները ճշգրիտ հավասարության նշանների.

լ 1: 3x 1 -2x 2 +6=0,

լ 2: 3x 1 +x 2 -3=0,

լ 3:x 1 -3=0.

ԴՀԵՏ

2 0 1 3 X 1

(լ 1) (լ 3)

Ուղիղ լ 1-ը բաժանում է ինքնաթիռը XՄԱՍԻՆ ժամըերկու կիսահավասարության մեջ, որոնցից պետք է ընտրել մեկը, որը բավարարում է (3) համակարգի առաջին անհավասարությունը: Դա անելու համար վերցնենք տ. ՄԱՍԻՆ(0; 0) և այն փոխարինիր անհավասարությամբ: Եթե ​​դա ճիշտ է, ապա դուք պետք է ստվերեք կիսահավասարությունը այն ուղիղ գծից, որում գտնվում է այսպես կոչված. ՄԱՍԻՆ(0; 0): Նույնն արեք ուղիղ գծերով։ լ 2 և լ 3. Անհավասարությունների լուծումների տիրույթը (3) բազմանկյուն է ABCԴ. Հարթության յուրաքանչյուր կետի համար ֆունկցիան Լվերցնում է ֆիքսված արժեք Լ=Լ 1 . Բոլոր ընթացիկ կետերի բազմությունը ուղիղ գիծ է Լ=գ 1 x 1 +գ 2 x 2 (մեր դեպքում Լ=2x 1 +2x 2), ուղղահայաց վեկտորին ՀԵՏ(Հետ 1 ;Հետ 2) (ՀԵՏ(2; 2)), ծագումով: Եթե ​​այս ուղիղը տեղափոխվի վեկտորի դրական ուղղությամբ Հետ, ապա օբյեկտիվ ֆունկցիան Լկավելանա, հակառակ դեպքում՝ կնվազի։ Այսպիսով, մեր դեպքում ուղիղ գիծը բազմանկյունից ելքի վրա ABCԴորոշումներն անցնելու են այսպես կոչված IN(3; 7.5), և, հետևաբար, ներառյալ. INօբյեկտիվ ֆունկցիան վերցնում է առավելագույն արժեքը, այսինքն. Լառավելագույնը =2ּ3+2ּ7.5=21. Նմանապես, որոշվում է, որ ֆունկցիան վերցնում է նվազագույն արժեքը Դ(1; 0) և Լ min =2ּ1+2ּ0=2.

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

1. Ընդհանուր առաջադրանքԳծային ծրագրավորումը վերածվում է կանոնական խնդրի (սահմանափակումները պարունակում են հավասար նշաններ)՝ ներմուծելով այնքան օժանդակ փոփոխականներ, որքան անհավասարություններ կան սահմանափակումների համակարգում։

2. Նպատակ ֆունկցիան արտահայտվում է հիմնական և օժանդակ փոփոխականների միջոցով։

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

4. Յուրաքանչյուր սիմպլեքս աղյուսակ տալիս է գծային ծրագրավորման խնդրի լուծում՝ ազատ փոփոխականները հավասար են զրոյի, հիմնական փոփոխականները՝ համապատասխանաբար ազատ անդամների։

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

6. Լուծումը բարելավելու համար անհրաժեշտ է մի սիմպլեքս աղյուսակից անցնել մյուսը։ Դա անելու համար նախորդ աղյուսակում գտեք առանցքային սյունակ, որը համապատասխանում է առավելագույն խնդրի աղյուսակի վերջին շարքի ամենափոքր բացասական տարրին և նվազագույն խնդրի ամենամեծ դրական գործակցին: Այնուհետև հայտնաբերվում է առանցքային տող, որը համապատասխանում է ազատ տերմինների նվազագույն հարաբերակցությանը հիմնական սյունակի համապատասխան դրական տարրերին: Հիմնական սյունակի և առանցքային տողի խաչմերուկում հիմնական տարրն է:

7. Մենք սկսում ենք լրացնել հետևյալ սիմպլեքս աղյուսակը՝ լրացնելով հիմքը. հիմնական տողին համապատասխան փոփոխականը բխում է հիմքից, իսկ դրա տեղում մուտքագրվում է առանցքային սյունակին համապատասխան փոփոխականը։ Նախկին բանալի տողի տարրերը ստացվում են նախկին տարրը առանցքայինի բաժանելով։ Նախկին հիմնական սյունակի տարրերը դառնում են զրո, բացառությամբ հիմնական տարրի, որը մեկն է: Բոլոր մյուս տարրերը հաշվարկվում են ուղղանկյունի կանոնով.

8. Սիմպլեքս աղյուսակների փոխակերպումն իրականացվում է մինչև օպտիմալ պլանի ստացումը:

Օրինակ. Գտեք ֆունկցիայի առավելագույն արժեքը
, եթե փոփոխականներ
բավարարել սահմանափակումների համակարգը.

Լուծում. 1. Ներկայացրե՛ք նոր փոփոխականներ
, որի օգնությամբ համակարգի անհավասարությունները վերափոխում ենք հավասարումների.

Փոխում ենք օբյեկտիվ ֆունկցիայի գործակիցների նշանը կամ գրում ենք ձևի մեջ
. Լրացնում ենք առաջին սիմպլեքս աղյուսակը, զրոյական տողում գրում ենք X 1 ,X 2 և (անվճար հավանականություն): Զրոյական սյունակում - X 3 ,X 4 ,X 5 և Ֆ. Մենք լրացնում ենք այս աղյուսակը՝ օգտագործելով ստացված հավասարումների համակարգը և փոխակերպված օբյեկտիվ ֆունկցիան։

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

2. Առաջին աղյուսակի լուծող տարրը գտե՛ք հետևյալ կերպ. Վերջին շարքի տարրերից մենք ընտրում ենք մեծության ամենամեծ բացասական գործակիցը (սա -3 է) և որպես լուծվող ընդունում ենք երկրորդ սյունակը։ Եթե ​​սյունակի բոլոր գործակիցները ոչ դրական են, ապա
.

Լուծվող տողը որոշելու համար ազատ գործակիցները բաժանում ենք լուծվող սյունակի համապատասխան տարրերի և ընտրում նվազագույն հարաբերակցությունը, մինչդեռ բացասական գործակիցներ չենք վերցնում։ Մենք ունենք
, երկրորդ տողը թույլատրելի է։ Լուծվող տողի և սյունակի հատումը տալիս է լուծվող տարրը` սա 3 է:

3. Լրացրե՛ք երկրորդ սիմպլեքս աղյուսակը: Փոփոխականները, որոնց խաչմերուկում մենք ստանում ենք լուծող տարր, փոխանակվում են, այսինքն. Եվ . Մենք փոխարինում ենք լուծող տարրը իր հակադարձով, այսինքն. վրա։ Լուծող տողի և սյունակի տարրերը (բացառությամբ լուծվող տարրի) բաժանվում են լուծվող տարրի։ Այս դեպքում մենք փոխում ենք լուծման սյունակի գործակիցների նշանը։

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

.

Մենք շարունակում ենք լրացնել աղյուսակները այս կանոնների համաձայն, մինչև չափանիշը բավարարվի: Մենք ունենք ևս երկու սեղան մեր առաջադրանքի համար:

	X 1	X 4					X 3	X 2
X 3						X 1
X 2						X 2
X 5						X 5

4. Այս ալգորիթմի կատարման արդյունքը գրված է հետեւյալ կերպ. Վերջնական աղյուսակում տարրը տողի խաչմերուկում
և սյունակ բ, տալիս է օբյեկտիվ ֆունկցիայի առավելագույն արժեքը։ Մեր դեպքում
. Տողերի փոփոխականների արժեքները հավասար են ազատ գործակիցներին: Մեր խնդրի համար մենք ունենք
.

Սիմպլեքս աղյուսակները կազմելու և լրացնելու այլ եղանակներ կան: Օրինակ՝ 1-ին փուլի համար բոլոր փոփոխականները և ազատ գործակիցները գրանցվում են աղյուսակի զրոյական տողում։ Ստորև բերված աղյուսակի նույն կանոններով լուծելու տարրը գտնելուց հետո մենք փոփոխականը փոխարինում ենք զրոյական սյունակում, բայց ոչ տողում։ Թույլ տողի բոլոր տարրերը բաժանում ենք թույլատրելի տարրի վրա և գրում նոր աղյուսակում։ Որոշման սյունակի մնացած տարրերի համար մենք գրում ենք զրոներ։ Հաջորդը, մենք կատարում ենք նշված ալգորիթմը, հաշվի առնելով այս կանոնները:

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

Excel-ի միջոցով գծային ծրագրավորման խնդիրների լուծումն իրականացվում է հետևյալ կերպ.

Գծային ծրագրավորման խնդիրները լուծելու համար օգտագործեք Solution Search հավելումը: Նախ պետք է համոզվեք, որ այս հավելումը առկա է «Վերլուծություն» խմբի «Տվյալներ» ներդիրում (2003թ.-ի համար տե՛ս Գործիքներ): Եթե ​​«Գտնել լուծում» հրամանը կամ «Վերլուծություն» խումբը բացակայում է, դուք պետք է ներբեռնեք այս հավելումը:

Դա անելու համար սեղմեք Microsoft Office File (2010), ապա սեղմեք Excel Options կոճակը: Excel Ընտրանքներ պատուհանում, որը երևում է, ձախ կողմում ընտրեք Հավելումներ տուփը: Պատուհանի աջ կողմում Control դաշտի արժեքը պետք է սահմանվի Excel Add-ins, սեղմեք «Գնալ» կոճակը, որը գտնվում է այս դաշտի կողքին: Հավելումների պատուհանում ընտրեք «Գտնել լուծում» վանդակը և սեղմեք «OK»: Այնուհետև կարող եք աշխատել տեղադրված «Search for Solutions» հավելման հետ:

Նախքան Լուծման Որոնում կանչելը, դուք պետք է աշխատաթերթի վրա պատրաստեք տվյալներ գծային ծրագրավորման խնդիր (մաթեմատիկական մոդելից) լուծելու համար.

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

2) Ներկայացրե՛ք կախվածություն փոփոխական բջիջներից՝ օբյեկտիվ ֆունկցիայի համար և կախվածություն փոփոխական բջիջներից՝ սահմանափակման համակարգի ձախ մասերի համար մնացած ազատ բջիջներում: Կախվածության բանաձևեր ներմուծելու համար հարմար է օգտագործել SUMPRODUCT մաթեմատիկական ֆունկցիան։

Հաջորդը, դուք պետք է օգտագործեք «Որոնել լուծում» հավելումը: «Տվյալներ» ներդիրում «Վերլուծություն» խմբում ընտրեք «Գտնել լուծում»: Լուծման որոնման երկխոսության տուփը կհայտնվի, որը պետք է լրացվի հետևյալ կերպ.

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

2) «Փոփոխվող փոփոխական բջիջների» դաշտում մուտքագրեք փոփոխվող բջիջները: Հաջորդ դաշտում՝ «Սահմանափակումների համաձայն», մուտքագրեք նշված սահմանափակումները՝ օգտագործելով «Ավելացնել» կոճակը: Հայտնվող պատուհանում մուտքագրեք սահմանափակման համակարգի բանաձևերը պարունակող բջիջները, ընտրեք սահմանափակման նշանը և սահմանափակման արժեքը (անվճար գործակից).

3) Նշեք «Անսահմանափակ փոփոխականները դարձնել ոչ բացասական» վանդակը: Ընտրեք լուծման մեթոդը «Գծային խնդիրների լուծումների որոնում սիմպլեքսի մեթոդով»: «Գտնել լուծում» կոճակը սեղմելուց հետո սկսվում է խնդրի լուծման գործընթացը: Արդյունքում հայտնվում են «Լուծումների որոնման արդյունքներ» երկխոսության տուփը և փոփոխական արժեքների և նպատակային ֆունկցիայի օպտիմալ արժեքի համար լցված բջիջներով բնօրինակ աղյուսակը:

Օրինակ։Լուծեք գծային ծրագրավորման խնդիր՝ օգտագործելով Excel Solution Add-in. գտեք ֆունկցիայի առավելագույն արժեքը
սահմանափակումների տակ

,

;

,
.

Լուծում.Մեր խնդիրը լուծելու համար եկեք գործարկենք նշված ալգորիթմը Excel-ի աշխատաթերթում: Մուտքագրեք նախնական տվյալները աղյուսակի տեսքով

Մենք ներկայացնում ենք կախվածություն օբյեկտիվ ֆունկցիայի և սահմանափակումների համակարգի համար: Դա անելու համար C2 բջիջում մուտքագրեք =SUMPRODUCT(A2:B2;A3:B3) բանաձևը: C4 և C5 բջիջներում, համապատասխանաբար, բանաձևերն են՝ =SUMPRODUCT(A2:B2,A4:B4) և =SUMPRODUCT(A2:B2,A5:B5): Արդյունքում մենք ստանում ենք սեղան:

Գործարկեք «Որոնել լուծում» հրամանը և լրացրեք «Որոնել լուծում» պատուհանը, որը հայտնվում է հետևյալ կերպ. «Օպտիմալացնել օբյեկտի գործառույթը» դաշտում մուտքագրեք C2 բջիջը: Ընտրեք թիրախային բջիջի արժեքի օպտիմալացում «Առավելագույնը»:

«Փոփոխվող փոփոխական բջիջների փոփոխություն» դաշտում մուտքագրեք A2:B2 փոփոխվող բջիջները: «Համաձայն սահմանափակումների» դաշտում մուտքագրեք նշված սահմանափակումները՝ օգտագործելով «Ավելացնել» կոճակը: Հղումներ դեպի $C$4:$C$5 բջիջ Հղումներ դեպի սահմանափակումներ =$D$4:$D$5 նրանց միջև նշան<= затем кнопку «ОК».

Նշեք «Անսահմանափակ փոփոխականները դարձնել ոչ բացասական» վանդակը: Ընտրեք լուծման մեթոդը «Գծային խնդիրների լուծումների որոնում սիմպլեքսի մեթոդով»:

Սեղմելով «Գտնել լուծում» կոճակը, սկսվում է խնդրի լուծման գործընթացը: Արդյունքում հայտնվում են «Լուծումների որոնման արդյունքներ» երկխոսության տուփը և փոփոխական արժեքների և նպատակային ֆունկցիայի օպտիմալ արժեքի համար լցված բջիջներով բնօրինակ աղյուսակը:

«Լուծումների որոնման արդյունքներ» երկխոսության վանդակում պահպանեք արդյունքը x1=0.75, x2=0.75, F=1.5 - հավասար է օբյեկտիվ ֆունկցիայի առավելագույն արժեքին:

Անկախ աշխատանքի առաջադրանքներ

Վարժություն 1.Օգտագործելով գրաֆիկական, սիմպլեքս մեթոդները և Excel գործիքները, գտե՛ք ֆունկցիայի առավելագույն և նվազագույն արժեքը Ֆ(x) սահմանափակումների տվյալ համակարգի ներքո:

1. Ֆ(x)=10x 1 +5x 2 2. Ֆ(x)=3x 1 -2x 2

3. Ֆ(x)=3x 1 +5x 2 4. Ֆ(x)=3x 1 +3x 2

5. Ֆ(x)=4x 1 -3x 2 6. Ֆ(x)=2x 1 -x 2

7. Ֆ(x)=-2x 1 +4x 2 8. Ֆ(x)=4x 1 -3x 2

9. Ֆ(x)=5x 1 +10x 2 10. Ֆ(x)=2x 1 +x 2

11. Ֆ(x)=x 1 +x 2 12. Ֆ(x)=3x 1 +x 2

13. Ֆ(x)=4x 1 +5x 2 14. Ֆ(x)=3x 1 +2x 2

15. Ֆ(x)=-x 1 -x 2 16. Ֆ(x)=-3x 1 -5x 2

17. Ֆ(x)=2x 1 +3x 2 18. Ֆ(x)=4x 1 +3x 2

19. Ֆ(x)=-3x 1 -2x 2 20. Ֆ(x)=-3x 1 +4x 2

21. Ֆ(x)=5x 1 -2x 2 22. Ֆ(x)=-2x 1 +3x 3

23. Ֆ(x)=2x 1 +3x 2 24. Ֆ(x)=4x 1 +3x 2

25. Ֆ(x)=-3x 1 -2x 2 26. Ֆ(x)=-3x 1 +4x 2

27. Ֆ(x)=-2x 1 +4x 2 28. Ֆ(x)=4x 1 -3x 2

29. Ֆ(x)=-x 1 -x 2 30. Ֆ(x)=-3x 1 -5x 2

Վերահսկիչ հարցեր.

1. Ո՞ր խնդիրներն են կոչվում գծային ծրագրավորման խնդիրներ:

2. Բերե՛ք գծային ծրագրավորման խնդիրների օրինակներ:

3. Ինչպե՞ս է լուծվում գծային ծրագրավորման խնդիրը գրաֆիկական մեթոդով:

4. Նկարագրե՛ք գծային ծրագրավորման խնդիրների լուծման սիմպլեքս մեթոդի ալգորիթմը:

5. Նկարագրեք Excel-ի միջոցով գծային ծրագրավորման խնդիրների լուծման ալգորիթմ:

Դաշնային կրթության գործակալություն

Պետական ​​բյուջետային ուսումնական հաստատություն

բարձրագույն մասնագիտական ​​կրթություն

«Օմսկի պետական ​​տեխնիկական համալսարան»

ՀԱՇՎԱՐԿԱՅԻՆ ԵՎ ԳՐԱՖԻԿԱԿԱՆ ԱՇԽԱՏԱՆՔ

ըստ կարգապահության»ՕՊՏԻՄԱԼ ՎԵՐԱՀՍԿՈՂՈՒԹՅԱՆ ՏԵՍՈՒԹՅՈՒՆ »

թեմայի շուրջ «ՕՊՏԻՄԻՄԱՑՄԱՆ ՄԵԹՈԴՆԵՐ ԵՎ ԳՈՐԾԱՌՆՈՒԹՅՈՒՆՆԵՐԻ ՀԵՏԱԶՈՏՈՒԹՅՈՒՆ »

տարբերակ 7

Ավարտված:

հեռակա ուսանող

4-րդ կուրսի խումբ ԶԱ-419

Ամբողջական անուն: Կուզելև Ս. Ա.

Ստուգվում:

Դևյատերիկովա Մ.Վ.

Օմսկ – 2012 թ
^

Առաջադրանք 1. Գծային ծրագրավորման խնդիրների լուծման գրաֆիկական մեթոդ.

7) 7x 1 + 6x 2 → մաքս 20x 1 + 6x 2 ≤ 15 16x 1 − 2x 2 ≤ 18 8x 1 + 4x 2 ≤ 20 13x 1 + 3x 2 ≤ 4 x 1 , x 2 ≥ 0.

Քայլ 1. Իրագործելի շրջանի կառուցում

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

Մոդելի առաջին սահմանափակումն ունի ձևը . Դրանում ≤ նշանը փոխարինելով = նշանով՝ ստանում ենք հավասարումը . Նկ. 1.1 այն սահմանում է ուղիղ գիծ (1), որը հարթությունը բաժանում է երկու կիսահարթությունների՝ այս դեպքում գծից վեր և դրանից ներքև։ Ընտրել, թե որն է բավարարում անհավասարությանը , դրա մեջ փոխարինեք տվյալ գծի վրա չգտնվող ցանկացած կետի կոորդինատները (օրինակ՝ սկզբնաղբյուր X 1 = 0, X 2 = 0): Քանի որ մենք ստանում ենք ճիշտ արտահայտությունը (20 0 + 6 0 = 0 ≤15), ապա կոորդինատների սկզբնակետ պարունակող կիսահավասարությունը (նշված է սլաքով) բավարարում է անհավասարությունը։ Հակառակ դեպքում՝ եւս մեկ կիսապլան։

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

Քայլ 2. Նկարել մակարդակի գիծ Մակարդակի գիծ Օբյեկտիվ ֆունկցիան հարթության այն կետերի բազմությունն է, որտեղ օբյեկտիվ ֆունկցիան ստանում է հաստատուն արժեք: Նման բազմություն տրված է հավասարմամբ զ ( x) = հաստատ. Դնենք, օրինակ. հաստատ = 0 և գծեք գիծ մակարդակի վրա զ ( x) = 0, այսինքն. մեր դեպքում ուղիղ գիծ 7 x 1 + 6x 2 = 0.

Այս ուղիղն անցնում է սկզբնակետով և ուղղահայաց է վեկտորին։ Այս վեկտորը (0,0) կետում օբյեկտիվ ֆունկցիայի գրադիենտն է։ Ֆունկցիայի գրադիենտը տվյալ ֆունկցիայի մասնակի ածանցյալների արժեքների վեկտորն է տվյալ կետում: LP խնդրի դեպքում օբյեկտիվ ֆունկցիայի մասնակի ածանցյալները հավասար են գործակիցներին. Գես, ժ = 1 , ..., n.

Գրադիենտը ցույց է տալիս ֆունկցիայի ամենաարագ աճի ուղղությունը։ Օբյեկտիվ ֆունկցիայի մակարդակի գիծը տեղափոխելը զ ( x) = հաստատ. ուղղահայաց գրադիենտի ուղղությանը, մենք գտնում ենք վերջին կետը, որտեղ այն հատվում է շրջանի հետ: Մեր դեպքում դա D կետն է, որը կլինի օբյեկտիվ ֆունկցիայի առավելագույն կետը (տե՛ս նկ. 2):

Այն գտնվում է (2) և (3) գծերի խաչմերուկում (տես նկ. 1) և սահմանում է օպտիմալ լուծումը:

^ Նկատի ունեցեք, որ եթե ցանկանում եք գտնել օբյեկտիվ ֆունկցիայի նվազագույն արժեքը, մակարդակի գիծը տեղափոխվում է գրադիենտի ուղղությամբ հակառակ ուղղությամբ:

^ Քայլ 3. Օբյեկտիվ ֆունկցիայի առավելագույն (նվազագույն) կետի կոորդինատների և օպտիմալ արժեքի որոշում.

Գ կետի կոորդինատները գտնելու համար անհրաժեշտ է լուծել ուղիղ գծերին համապատասխանող հավասարումներից բաղկացած համակարգ (այս դեպքում՝ 2 և 3 հավասարումներ).

16x 1 − 2x 2 ≤ 18

8x 1 + 4x 2 ≤ 20

Մենք ստանում ենք օպտիմալ լուծում = 1.33:

^ Օբյեկտիվ ֆունկցիայի օպտիմալ արժեքը զ * = զ (X*) = 7 * 0 + 6 * 1,33 = 7,8