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

Ծառայության նպատակը. Ծառայությունը նախատեսված է առցանց գծային ծրագրավորման խնդիրներ (LPP) լուծելու համար՝ օգտագործելով simplex մեթոդը հետևյալ նշագրման ձևերով.

• սիմպլեքս աղյուսակի տեսքով (Հորդանանի փոխակերպման մեթոդ); հիմնական ձայնագրման ձև;
• փոփոխված սիմպլեքս մեթոդ; սյունակի տեսքով; տողային տեսքով։

Հրահանգներ. Ընտրեք փոփոխականների քանակը և տողերի քանակը (սահմանափակումների քանակը): Ստացված լուծումը պահվում է Word և Excel ֆայլերում: Այս դեպքում հաշվի մի առեք այնպիսի սահմանափակումներ, ինչպիսիք են x i ≥0: Եթե ​​առաջադրանքում որևէ սահմանափակում չկա x i-ի համար, ապա ZLP-ը պետք է փոխարկվի KZLP-ի կամ օգտագործեք այս ծառայությունը: Լուծելիս օգտագործումը ինքնաբերաբար որոշվում է M-մեթոդ(պարզ մեթոդ արհեստական ​​հիմքով) և երկաստիճան սիմպլեքս մեթոդ.

Այս հաշվիչի հետ օգտագործվում են նաև հետևյալը.
ZLP-ի լուծման գրաֆիկական մեթոդ
Տրանսպորտային խնդրի լուծում
Մատրիցային խաղի լուծում
Օգտագործելով առցանց ծառայությունը՝ կարող եք որոշել մատրիցային խաղի գինը (ներքևի և վերին սահմանները), ստուգել թամբի կետի առկայությունը, լուծում գտնել խառը ռազմավարության համար՝ օգտագործելով հետևյալ մեթոդները՝ մինիմաքս, սիմպլեքս մեթոդ, գրաֆիկական (երկրաչափական): ) մեթոդ, Բրաունի մեթոդ։
Երկու փոփոխականի ֆունկցիայի ծայրահեղություն
Դինամիկ ծրագրավորման խնդիրներ
Տարածեք 5 միատարր խմբաքանակ ապրանքներ երեք շուկաների միջև՝ դրանց վաճառքից առավելագույն եկամուտ ստանալու համար: Յուրաքանչյուր շուկայում G(X) վաճառքից եկամուտը կախված է X ապրանքի վաճառված խմբաքանակներից և ներկայացված է աղյուսակում:

Ապրանքի ծավալը X (լոտերով)	Եկամուտ G(X)
	1	2	3
0	0	0	0
1	28	30	32
2	41	42	45
3	50	55	48
4	62	64	60
5	76	76	72

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

1. Առաջին հիմնական պլանի կազմումը. Անցում գծային ծրագրավորման խնդրի կանոնական ձևին՝ ներմուծելով ոչ բացասական հավելյալ հաշվեկշռի փոփոխականներ։
2. Պլանի օպտիմալության ստուգում. Եթե ​​կա առնվազն մեկ ինդեքսի գծի գործակից զրոյից պակաս, ապա պլանը օպտիմալ չէ և պետք է բարելավվի:
3. Առաջատար սյունակի և տողի որոշում. Ցուցանիշի գծի բացասական գործակիցներից ընտրվում է ամենամեծը բացարձակ արժեքով։ Այնուհետև սիմպլեքս աղյուսակի ազատ անդամի սյունակի տարրերը բաժանվում են առաջատար սյունակի նույն նշանի տարրերի։
4. Նոր հղման պլանի կառուցում. Անցումը նոր պլանի իրականացվում է սիմպլեքս աղյուսակի վերահաշվարկի արդյունքում՝ օգտագործելով Հորդանան-Գաուսի մեթոդը։

Եթե ​​անհրաժեշտ է գտնել օբյեկտիվ ֆունկցիայի էքստրեմումը, ապա մենք խոսում ենքնվազագույն արժեքը գտնելու մասին (F(x) → min, տե՛ս ֆունկցիան նվազագույնի հասցնելու լուծման օրինակը) և առավելագույն արժեքը (F(x) → max, տե՛ս ֆունկցիան առավելագույնի հասցնելու լուծման օրինակը)

Ծայրահեղ լուծումը ձեռք է բերվում իրագործելի լուծումների շրջանի սահմանին պոլիգոնի անկյունային կետերից մեկում կամ երկու հարակից անկյունային կետերի միջև ընկած հատվածում:

Գծային ծրագրավորման հիմնարար թեորեմ. Եթե ​​ZLP-ի օբյեկտիվ ֆունկցիան իրագործելի լուծումների տարածաշրջանի ինչ-որ կետում հասնում է ծայրահեղ արժեքի, ապա այն վերցնում է այս արժեքը անկյունային կետում: Եթե ​​ZLP օբյեկտիվ ֆունկցիան հասնում է ծայրահեղ արժեքի մեկից ավելի անկյունային կետերում, ապա այն վերցնում է նույն արժեքը այս կետերի ուռուցիկ գծային համակցություններից որևէ մեկում:

Սիմպլեքս մեթոդի էությունը. Շարժումը դեպի օպտիմալ կետ իրականացվում է մի անկյունային կետից դեպի հարևան կետ տեղափոխելով, որն ավելի ու ավելի արագ է մոտեցնում X opt-ին: Միավորների թվարկման այսպիսի սխեման, կոչվում է սիմպլեքս մեթոդ, առաջարկել է Ռ.Դանցիգը։
Անկյունային կետերը բնութագրվում են m հիմնական փոփոխականներով, ուստի անցումը մի անկյունային կետից հարակից կետին կարող է իրականացվել՝ հիմքում ընկած միայն մեկ հիմնական փոփոխական փոխելով փոփոխականի՝ ոչ հիմքից:
Գործող սիմպլեքս մեթոդի ներդրում տարբեր հատկանիշներև խնդրի հայտարարությունները, LP-ն ունի տարբեր փոփոխություններ:

Սիմպլեքս աղյուսակների կառուցումը շարունակվում է այնքան ժամանակ, մինչև ստացվի օպտիմալ լուծում։

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

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

Ծանոթագրություն 2. Թող որևէ ծայրահեղ կետում սիմպլեքսի բոլոր տարբերությունները լինեն ոչ բացասական D k³ 0 (k = 1..n+m), այսինքն. ստացվում է օպտիմալ լուծում և գոյություն ունի A k - ոչ հիմքային վեկտոր, որի համար D k = 0: Այնուհետև առավելագույնը ձեռք է բերվում առնվազն երկու կետում, այսինքն. կա այլընտրանքային օպտիմալ. Եթե ​​այս x k փոփոխականը ներմուծենք հիմք, ապա օբյեկտիվ ֆունկցիայի արժեքը չի փոխվի։

Ծանոթագրություն 3. Երկակի խնդրի լուծումը գտնվում է վերջին սիմպլեքս աղյուսակում։ Սիմպլեքս տարբերությունների վեկտորի վերջին m բաղադրիչները (հավասարակշռության փոփոխականների սյունակներում) երկակի խնդրի օպտիմալ լուծումն են։ Օպտիմալ կետերում ուղիղ և երկակի խնդիրների օբյեկտիվ գործառույթների արժեքները համընկնում են:

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

Եթե ​​նշված է «Անհրաժեշտ է, որ III տիպի հումքը ամբողջությամբ սպառվի», ապա համապատասխան պայմանը հավասարություն է։

Սիմպլեքս մեթոդի վերլուծական ներածություն

Սիմպլեքս մեթոդը ունիվերսալ գծային ծրագրավորման մեթոդ է։

Այսպիսով, եթե ZLP-ն լուծենք կանոնական ձևով, ապա սահմանափակումների համակարգը գծային հավասարումների սովորական համակարգ է: LP խնդիրները լուծելիս ստացվում են գծային հավասարումների համակարգեր, որոնք, որպես կանոն, ունեն անսահման շատ լուծումներ։

Օրինակ, թող համակարգը տրվի

Այստեղ հավասարումների թիվը 2 է, իսկ անհայտներինը՝ 3, ավելի քիչ են հավասարումները։ Եկեք x 1 և x 2-ը արտահայտենք x 3-ով.

Սա համակարգի ընդհանուր լուծումն է։ եթե x 3 փոփոխականին տրվեն կամայական թվային արժեքներ, ապա մենք կգտնենք համակարգի մասնակի լուծումները։ Օրինակ՝ x 3 =1 → x 1 =1 → x 2 =6. Մենք ունենք (1, 6, 1) - կոնկրետ լուծում: Թող x 3 =2 → x 1 =-3, x 2 = 1, (-3, 1, 2) - մեկ այլ կոնկրետ լուծում: Նման կոնկրետ լուծումներ անսահման շատ են։

Փոփոխականներ x 1 և x 2 կոչվում են հիմնական, և փոփոխականը x 3 - ոչ հիմնական, անվճար.

Փոփոխականների հավաքածու x 1 և x 2 հիմք է կազմում. Բ (x 1 , x 2). Եթե x 3 = 0, ապա ստացված կոնկրետ լուծումը (5, 11, 0) կոչվում է հիմքին համապատասխանող հիմնական լուծում. Բ (x 1 , x 2).

Հիմնական լուծումը ազատ փոփոխականների զրոյական արժեքներին համապատասխանող լուծումն է.
Այլ փոփոխականներ կարող էին ընդունվել որպես բազային. x 1 , x 3) կամ ( x 2 , x 3).
Ինչպես շարժվել մեկ հիմքից Բ(x 1 , x 2) մեկ այլ հիմքի վրա Բ(x 1 , x 3)?
Դրա համար անհրաժեշտ է փոփոխական x 3 փոխարկել հիմնականի, և x 2 - ոչ հիմնականներին, այսինքն հավասարումների մեջ դա անհրաժեշտ է x 3 արտահայտել միջոցով x 2 և փոխարինել 1-ին.

Բ(x 1 , x 3), է` (-19/5; 0; 11/5):

Եթե ​​հիմա հիմքից Բ(x 1 , x 3) մենք կցանկանանք գնալ դեպի հիմք Բ(x 2 , x 3), ապա

Հիմքին համապատասխան հիմնական լուծում Բ (x 2 , x 3): (0;19/4; 7/8).
Գտնված երեք հիմքի լուծումներից՝ հիմքին համապատասխան լուծում Բ (x 1 , x 3) - բացասական x 1 < 0, нас в ЗЛП интересуют только неотрицательные решения.

Եթե ​​LP խնդիրը լուծում ունի, ապա այն ձեռք է բերվում կանոնական ձևի սահմանափակումների համակարգի հիմնական ոչ բացասական լուծումների բազմության վրա։

Հետևաբար, սիմպլեքս մեթոդի գաղափարը հաջորդաբար մեկ հիմքից մյուսն անցնելն է, որն ավելի լավ է օբյեկտիվ ֆունկցիայի արժեքի առումով:

Օրինակ. Լուծեք LP-ի խնդիրը:

Գործառույթ Ֆ= x 2 - x 1 → րոպեն պետք է նվազագույնի հասցվի սահմանափակումների տվյալ համակարգի ներքո.
-2x 1 + x 2 + x 3 = 2
x 1 + x 2 + x 5 = 5
x 1 - 2x 2 + x 4 = 12
xես ≥ 0, ես = 1, 5

Այս սահմանափակումները կարող են դիտվել որպես անհավասարություններից և փոփոխականներից բխող x 3 , x 5 , x 4 - որպես լրացուցիչ:
Եկեք գրենք սահմանափակումները՝ փոփոխականներից հիմք ընտրելով Բ{ x 3 , x 4 , x 5 }:

Այս հիմքը համապատասխանում է հիմնական ոչ բացասական լուծմանը
x 1 = 0, x 2 = 0, x 3 = 2, x 4 = 2, x 5 = 5 կամ (0, 0, 2, 2, 5):
Այժմ մենք պետք է արտահայտվենք Ֆոչ հիմնական փոփոխականների միջոցով, մեր դեպքում սա արդեն արվել է. Ֆ= x 2 - x 1 .
Եկեք ստուգենք, արդյոք գործառույթը հասել է Ֆդրա նվազագույն արժեքը. Այս հիմնական լուծման համար Ֆ= 0 - 0 = 0 - ֆունկցիայի արժեքը 0 է: Բայց այն կարող է կրճատվել, եթե x 1-ը կաճի, քանի որ ֆունկցիայի գործակիցը ժամը x 1-ը բացասական է: Այնուամենայնիվ, աճի հետ x 1 փոփոխական արժեքներ x 4 , x 5 նվազում (տես սահմանափակումների համակարգի երկրորդ և երրորդ հավասարությունը): Փոփոխական x 1-ը չի կարող ավելացվել 2-ից ավելի, հակառակ դեպքում x 4-ը կդառնա բացասական (հավասարության պատճառով 2), իսկ 5-ից ոչ ավելի, հակառակ դեպքում x 5 - բացասական: Այսպիսով, հավասարումների վերլուծությունից հետևում է, որ փոփոխականը x 1-ը կարելի է հասցնել 2-ի, իսկ ֆունկցիայի արժեքը կնվազի:
Անցնենք B 2 նոր հիմքին՝ ներմուծելով փոփոխականը xՓոխարենը 1 հիմքի վրա x 4 .
Բ 2 {x 1 , x 3 , x 5 }.
Եկեք արտահայտենք այս հիմնական փոփոխականները ոչ հիմնականների առումով: Դա անելու համար մենք նախ արտահայտում ենք x 1-ը երկրորդ հավասարումից և այն փոխարինիր մնացածով՝ ներառյալ ֆունկցիան:

Հիմքին համապատասխան հիմնական լուծում Բ 3 {X 1 , X 2 , X 3 ), գրված է (4, 1, 9, 0, 0), և ֆունկցիան ընդունում է արժեքը Ֆ= -3. Նշենք, որ արժեքը Ֆնվազել է, այսինքն՝ բարելավվել է նախորդ հիմքի համեմատ։
Նայելով օբյեկտիվ ֆունկցիայի ձևին , նշեք, որ բարելավելու համար, այսինքն, նվազեցնել արժեքը Ֆհնարավոր չէ և միայն այն ժամանակ, երբ x 4 = 0, x 5 = 0 արժեք Ֆ= -3. հենց որ x 4 , x 5-ը կդառնա դրական, արժեքը Ֆմիայն կավելանա, քանի որ գործակիցները համար x 4 , x 5-ը դրական են: Այսպիսով, գործառույթը Ֆհասել է իր օպտիմալ արժեքին Ֆ* = -3. Այսպիսով, ամենափոքր արժեքը Ֆ, հավասար է -3-ի, ձեռք է բերվում ժամը x 1 * = 4, x 2 * = 1, x 3 * = 9, x 4 * = 0, x 5 * = 0.

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

Երեք տեսակի վերնաշապիկներ պատրաստելու համար օգտագործվում են թել, կոճակներ և գործվածք։ Թելի, կոճակների և գործվածքի պաշարները, մեկ վերնաշապիկը կարելու համար դրանց սպառման նորմերը նշված են աղյուսակում: Գտեք առավելագույն շահույթը և այն ապահովող արտադրանքի արտադրության օպտիմալ պլանը (գտեք):

վերնաշապիկ 1

վերնաշապիկ 2

վերնաշապիկ 3

Պահուստներ

թելեր (մ.)

1

9

3

96

կոճակներ (հատ.)

20

10

30

640

տեքստիլ (

1

2

2

44

Շահույթ (r.)

2

5

4

Խնդրի լուծում

Մոդելային շենք

Թողարկման համար նախատեսված 1-ին, 2-րդ և 3-րդ տեսակների վերնաշապիկների միջոցով և քանակով։

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

Բացի այդ, ըստ առաջադրանքի իմաստի

Ստացված շահույթն արտահայտող օբյեկտիվ ֆունկցիա.

Ստանում ենք հետևյալ գծային ծրագրավորման խնդիրը.

Գծային ծրագրավորման խնդիրը կանոնական ձևի իջեցում

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

Խնդիրը լուծել սիմպլեքս մեթոդով

Լրացրե՛ք սիմպլեքս աղյուսակը.

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

Մենք անցնում ենք հաջորդ կրկնությանը հետևյալ կերպ.

առաջատար սյունակը համապատասխանում է

Հիմնական տողը որոշվում է ազատ տերմինների և առաջատար սյունակի անդամների նվազագույն հարաբերակցությամբ (պարզ հարաբերություններ).

Հիմնական սյունակի և առանցքային տողի խաչմերուկում մենք գտնում ենք միացնող տարրը, այսինքն. 9.

Այժմ մենք անցնում ենք 1-ին կրկնության կազմմանը. միավոր վեկտորի փոխարեն ներկայացնում ենք վեկտորը:

Նոր աղյուսակում միացնող տարրի փոխարեն գրում ենք 1, առանցքային սյունակի մնացած բոլոր տարրերը զրո են։ Հիմնական լարային տարրերը բաժանված են enable տարրի: Աղյուսակի մյուս բոլոր տարրերը հաշվարկվում են ուղղանկյունի կանոնով:

1-ին կրկնության հիմնական սյունակը համապատասխանում է

Լուծող տարրը 4/3 թիվն է։ Մենք հիմքից վերցնում ենք վեկտորը և փոխարենը ներկայացնում վեկտորը: Ստանում ենք 2-րդ կրկնության աղյուսակը։

2-րդ կրկնության հիմնական սյունակը համապատասխանում է

Մենք գտնում ենք հիմնական գիծը, դրա համար մենք սահմանում ենք.

Լուծող տարրը 10/3 թիվն է։ Մենք հիմքից վերցնում ենք վեկտորը և փոխարենը ներկայացնում վեկտորը: Ստանում ենք 3-րդ կրկնության աղյուսակը։

№

BP

գ Բ

Ա ո

x 1

x 2

x 3

x 4

x 5

x 6

Սիմպլեքս

2

5

4

0

0

0

հարաբերություններ

0

x 4

0

96

1

9

3

1

0

0

32/3

x 5

0

640

20

10

30

0

1

0

64

x 6

0

44

1

2

2

0

0

1

22

F j - c j

0

-2

-5

-4

0

0

0

1

x 2

5

32/3

1/9

1

1/3

1/9

0

0

32

x 5

0

1600/3

170/9

0

80/3

-10/9

1

0

20

x 6

0

68/3

7/9

0

4/3

-2/9

0

1

17

F j - c j

160/3

-13/9

0

-7/3

5/9

0

0

2

x 2

5

5

-1/12

1

0

1/6

0

-1/4

--

x 5

0

80

10/3

0

0

10/3

1

-20

24

x 3

4

17

7/12

0

1

-1/6

0

3/4

204/7

F j - c j

93

-1/12

0

0

1/6

0

7/4

3

x 2

5

7

0

1

0

1/4

1/40

-3/4

x 1

2

24

1

0

0

1

3/10

-6

x 3

4

3

0

0

1

-3/4

-7/40

17/4

F j - c j

95

0

0

0

1/4

1/40

5/4

Ինդեքսի տողում բոլոր տերմինները ոչ բացասական են, ուստի ստացվում է գծային ծրագրավորման խնդրի հետևյալ լուծումը (մենք այն դուրս ենք գրում ազատ տերմինների սյունակից).

Անհրաժեշտ է կարել 1-ին տեսակի 24 շապիկ, 2-րդ տեսակի 7 շապիկ և 3-րդ տեսակի 3 վերնաշապիկ։ Այս դեպքում ստացված շահույթը կլինի առավելագույնը և կկազմի 95 ռուբլի:

LP խնդիրների լուծման ունիվերսալ մեթոդը կոչվում է սիմպլեքս մեթոդ: Այս մեթոդի կիրառումը և դրա ամենատարածված փոփոխությունը՝ երկփուլ սիմպլեքս մեթոդը:

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

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

Ըստ որոշակի կանոնի՝ հայտնաբերվում է նախնական հղման պլանը (սահմանափակման տարածքի որոշ գագաթ): Այն ստուգում է, թե արդյոք պլանը օպտիմալ է: Եթե ​​այո, ապա խնդիրը լուծված է։ Եթե ​​ոչ, ապա մենք անցնում ենք մեկ այլ բարելավված պլանի՝ մեկ այլ գագաթնակետի: Այս հարթության վրա (այս գագաթին) օբյեկտիվ ֆունկցիայի արժեքը ակնհայտորեն ավելի լավն է, քան նախորդում: Անցումային ալգորիթմն իրականացվում է որոշակի հաշվարկային քայլի միջոցով, որը հարմար գրված է աղյուսակների տեսքով, որը կոչվում է. սիմպլեքս սեղաններ . Քանի որ կան վերջավոր թվով գագաթներ, վերջավոր թվով քայլերով մենք հասնում ենք օպտիմալ լուծմանը։

Դիտարկենք սիմպլեքս մեթոդը՝ օգտագործելով պլանի կազմման խնդրի կոնկրետ օրինակ։

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

Դիտարկենք արտադրության պլանի խնդիրը՝ նախապես մոդել կառուցելով և այն հատուկ ձևի բերելով։

Առաջադրանք.

Արտադրանքի արտադրության համար ԱԵվ INՊահեստը կարող է բաց թողնել ոչ ավելի, քան 80 միավոր հումք։ Ավելին, արտադրանքի արտադրության համար Ասպառվում է երկու միավոր, իսկ արտադրանքը IN- մեկ միավոր հումք. Պահանջվում է արտադրություն պլանավորել այնպես, որ առավելագույն շահույթ ապահովվի, եթե արտադրանքը Ապահանջվում է արտադրել 50 հատից ոչ ավելի, իսկ արտադրանք IN- ոչ ավելի, քան 40 հատ: Ընդ որում՝ մեկ ապրանքի վաճառքից ստացված շահույթը Ա- 5 ռուբլի, իսկ սկսած IN- 3 ռուբ.

Կառուցենք մաթեմատիկական մոդել՝ նշելով X 1 քանակի ապրանք Ա պլանում, համար X 2 - ապրանքների քանակը IN. ապա սահմանափակման համակարգը կունենա հետևյալ տեսքը.

x 1 ≤50
x 2 ≤40
2x 1 +x 2 ≤80
x 1 ≥0, x 2 ≥0
5x 1 +3x 2 → առավելագույնը

Եկեք խնդիրը հասցնենք կանոնական ձևի՝ ներմուծելով լրացուցիչ փոփոխականներ.

x 1 + x 3 =50
x 2 + x 4 =40
2x 1 +x 2 +x 5 =80
x 1 ≥0, x 2 ≥0
5x 1 +3x 2 → max
-F = -5x 1 - 3x 2 → min.

Այս խնդիրն ունի հատուկ ձև (հիմքով, աջ կողմերը ոչ բացասական են)։ Այն կարելի է լուծել սիմպլեքս մեթոդով։

Իփուլ.Խնդիրի գրանցում սիմպլեքս աղյուսակում: Խնդիրի սահմանափակումների համակարգի (3.10) և սիմպլեքս աղյուսակի միջև առկա է մեկ առ մեկ համապատասխանություն: Աղյուսակում այնքան տող կա, որքան հավասարություններ կան սահմանափակումների համակարգում, և այնքան սյունակ, որքան ազատ փոփոխականներ: Հիմնական փոփոխականները լրացնում են առաջին սյունակը, ազատ փոփոխականները լրացնում են աղյուսակի վերին տողը: Ներքեւի տողը կոչվում է ինդեքսի գիծ, ​​դրանում գրված են օբյեկտիվ ֆունկցիայի փոփոխականների գործակիցները։ Ներքևի աջ անկյունում սկզբում գրվում է 0, եթե ֆունկցիայի մեջ ազատ անդամ չկա. եթե կա, ապա գրի՛ր հակառակ նշանով։ Այս վայրում (ներքևի աջ անկյունում) կլինի օբյեկտիվ ֆունկցիայի արժեքը, որը մի սեղանից մյուսը տեղափոխելիս պետք է բացարձակ արժեքով մեծանա։ Այսպիսով, Աղյուսակ 3.4-ը համապատասխանում է մեր սահմանափակումների համակարգին, և մենք կարող ենք անցնել լուծման II փուլ:

Աղյուսակ 3.4

հիմնական			անվճար

IIփուլ. Հղման պլանի օպտիմալության ստուգում:

Այս աղյուսակ 3.4-ը համապատասխանում է հետևյալ հղման պլանին.

(X 1 , X 2 , X 3 , X 4 , X 5) = (0, 0, 50, 40, 80).

Ազատ փոփոխականներ X 1 , X 2-ը հավասար է 0-ի; X 1 = 0, X 2 = 0. Եվ հիմնական փոփոխականները X 3 , X 4 , X 5 վերցրեք արժեքներ X 3 = 50, X 4 = 40, X 5 = 80 - ազատ պայմանների սյունակից: Օբյեկտիվ ֆունկցիայի արժեքը.

-Ֆ = - 5X 1 - 3X 2 = -5 0 - 3 0 = 0:

Մեր խնդիրն է ստուգել, ​​թե արդյոք տվյալ հղման պլանը օպտիմալ է: Դա անելու համար դուք պետք է նայեք ինդեքսի գիծը՝ թիրախային ֆունկցիայի գիծը Ֆ.

Հնարավոր են տարբեր իրավիճակներ.

1. Ցուցանիշում Ֆ- Լարի մեջ բացասական տարրեր չկան: Սա նշանակում է, որ պլանը օպտիմալ է, և խնդրի լուծումը կարելի է գրել: Օբյեկտիվ ֆունկցիան հասել է իր օպտիմալ արժեքին, որը հավասար է հակառակ նշանով վերցված ստորին աջ անկյունի թվին: Անցնենք IV փուլին։

2. Ինդեքսի տողը ունի առնվազն մեկ բացասական տարր, որի սյունակը չունի դրական տարրեր: Հետո եզրակացնում ենք, որ օբյեկտիվ ֆունկցիան Ֆ→∞ նվազում է առանց սահմանի:

3. Ինդեքսի տողն ունի բացասական տարր, որն իր սյունակում ունի առնվազն մեկ դրական տարր: Այնուհետև անցնում ենք երրորդ փուլին: Մենք վերահաշվարկում ենք աղյուսակը՝ բարելավելով հղման պլանը։

IIIփուլ. Հղման պլանի կատարելագործում.

Ցուցանիշի բացասական տարրերից Ֆ- տողեր, ընտրեք ամենամեծ մոդուլն ունեցողը, կանչեք համապատասխան սյունակը լուծող և նշեք այն «»-ով:

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

Մեր օրինակում տարր 2-ը թույլատրելի է: Այս տարրին համապատասխան տողը կոչվում է նաև լուծում (Աղյուսակ 3.5):

Աղյուսակ 3.5

Ընտրելով թույլատրելի տարրը, մենք վերահաշվարկում ենք աղյուսակը կանոնների համաձայն.

1. Նախկին չափի նոր աղյուսակում փոխվում են լուծվող տողի և սյունակի փոփոխականները, ինչը համապատասխանում է նոր հիմքի անցմանը: Մեր օրինակում. XՓոխարենը հիմքում ներառված է 1 X 5, որը թողնում է հիմքը և այժմ ազատ է (Աղյուսակ 3.6):

Աղյուսակ 3.6

2. Լուծող տարր 2-ի փոխարեն գրի՛ր դրա հակադարձ թիվը ½:

3. Բանաձեւի գծի տարրերը բաժանում ենք բանաձեւի տարրի վրա։

4. Բանաձեւի սյունակի տարրերը բաժանում ենք բանաձեւի տարրի վրա եւ գրում հակառակ նշանով։

5. Աղյուսակ 3.6-ի մնացած տարրերը լրացնելու համար մենք վերահաշվարկում ենք՝ օգտագործելով ուղղանկյունի կանոնը։ Ենթադրենք, ուզում ենք հաշվել տարրը 50-րդ դիրքում:

Մենք մտովի կապում ենք այս տարրը լուծվողի հետ, գտնում ենք արտադրյալը, հանում այն ​​տարրերի արտադրյալը, որոնք գտնվում են ստացված ուղղանկյան մյուս անկյունագծով։ Տարբերությունը բաժանում ենք լուծվող տարրի վրա։

Այսպիսով, . Մենք գրում ենք 10 այն տեղում, որտեղ 50-ը կար: Նմանապես.
, , , .

Աղյուսակ 3.7

Մենք ունենք նոր աղյուսակ 3.7, հիմնական փոփոխականներն այժմ փոփոխականներն են (x 3, x 4, x 1): Օբյեկտիվ ֆունկցիայի արժեքը դարձավ -200, այսինքն. նվազել է. Այս հիմնական լուծումը օպտիմալության համար ստուգելու համար մենք պետք է նորից գնանք II փուլ: Գործընթացն ակնհայտորեն վերջավոր է.

Ամբողջացնենք խնդրի լուծումը։ Դա անելու համար եկեք ստուգենք ինդեքսի գիծը և դրանում տեսնելով -½ բացասական տարր, կանչենք համապատասխան սյունակը լուծող և, ըստ III փուլի, վերահաշվարկենք աղյուսակը։ Կազմելով հարաբերությունները և դրանցից ընտրելով նվազագույնը = 40-ը, մենք որոշեցինք լուծվող տարրը 1: Այժմ վերահաշվարկն իրականացնում ենք 2-5 կանոնների համաձայն:

Աղյուսակ 3.8

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

IVփուլ. Օպտիմալ լուծում գրելը.

Եթե ​​սիմպլեքս մեթոդը դադարել է II փուլի 1-ին կետի համաձայն, ապա խնդրի լուծումը գրվում է հետևյալ կերպ. Հիմնական փոփոխականները համապատասխանաբար վերցնում են կեղծ տերմինների սյունակի արժեքները: Մեր օրինակում X 3 = 30, X 2 = 40, X 1 = 20: Ազատ փոփոխականները 0 են, X 5 = 0, X 4 = 0. Օբյեկտիվ ֆունկցիան ընդունում է ազատ տերմինների սյունակի վերջին տարրի արժեքը հակառակ նշանով. Ֆ = -220 → Ֆ= 220, մեր օրինակում ֆունկցիան ուսումնասիրվել է min, և սկզբում Ֆ→ max, այնպես որ նշանը իրականում փոխվել է երկու անգամ: Այսպիսով, X* = (20, 40, 30, 0, 0), Ֆ* = 220. Խնդրի պատասխանը.

Արտադրության պլանում անհրաժեշտ է ներառել այդ տեսակի 20 ապրանք Ա, B տիպի 40 ապրանք, մինչդեռ շահույթը կլինի առավելագույնը և կկազմի 220 ռուբլի։

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

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

Օրինակ. Լուծե՛ք հետևյալ LP խնդիրը կանոնական ձևով՝ օգտագործելով simplex մեթոդը.
f(x)=x 1 +9x 2 +5x 3 +3x 4 +4x 5 +14x 6 → րոպե
x 1 + x 4 = 20
x 2 + x 5 =50
x 3 + x 6 = 30
x 4 + x 5 + x 6 =60
x i ≥ 0, i = 1,…,6
LP խնդիրը համարվում է կանոնական ձև, եթե բոլոր սահմանափակումները (բացառությամբ փոփոխականների ոչ բացասական լինելու պայմանների) ունեն հավասարությունների ձև, և բոլոր ազատ տերմինները ոչ բացասական են: Այսպիսով, մենք խնդիր ունենք կանոնական ձևով:
Սիմպլեքս մեթոդի գաղափարը հետևյալն է. Նախ անհրաժեշտ է գտնել իրագործելի լուծումների պոլիէդրոնի որոշ (նախնական) գագաթ (նախնական իրագործելի հիմնական լուծում): Ապա դուք պետք է ստուգեք այս լուծումը օպտիմալության համար: Եթե ​​դա օպտիմալ է, ապա լուծում է գտնվել; եթե ոչ, ապա անցեք պոլիէդրոնի մեկ այլ գագաթ և նորից ստուգեք օպտիմալությունը: Բազմեյդոնի գագաթների վերջավորության պատճառով (LP խնդրի սահմանափակումների վերջավորության հետևանք) վերջավոր թվով «քայլերի» մեջ կգտնենք նվազագույնի կամ առավելագույնի պահանջվող կետը։ Հարկ է նշել, որ մի գագաթից մյուսը անցնելիս օբյեկտիվ ֆունկցիայի արժեքը նվազում է (նվազագույն խնդրի դեպքում) կամ մեծանում (առավելագույն խնդրի դեպքում)։
Այսպիսով, simplex մեթոդի գաղափարը հիմնված է LP խնդրի երեք հատկությունների վրա.
Լուծում.Նախնական իրագործելի հիմքի լուծումը գտնելու համար, այսինքն. Հիմնական փոփոխականները որոշելու համար (5.6) համակարգը պետք է վերածվի «անկյունագծային» ձևի: Օգտագործելով Գաուսի մեթոդը (անհայտների հաջորդական վերացման մեթոդ) մենք ստանում ենք (5.6).
x 2 + x 1 + x 3 =40
x 4 + x 1 =20
x 5 -x 1 -x 3 =10
x 6 + x 3 =30
Հետևաբար, հիմնական փոփոխականներն են x 2, x 4, x 5, x 6,Մենք նրանց տալիս ենք արժեքներ, որոնք հավասար են համապատասխան տողերի ազատ անդամներին. x 2 =40, x 4 =20, x 5 =10, x 6 =30,. Փոփոխականներ x 1Եվ x 3ոչ հիմնական են. x 1 =0, x 3 =0.
Եկեք կառուցենք նախնական իրագործելի հիմնական լուծումը
x 0 = (0,40,0,20,10,30) (5,9)
Գտնված լուծման օպտիմալությունը ստուգելու համար x 0անհրաժեշտ է բացառել հիմնական փոփոխականները թիրախային ֆունկցիայից (օգտագործելով համակարգը (5.8)) և կառուցել հատուկ սիմպլեքս աղյուսակ։
Փոփոխականները վերացնելուց հետո նպատակային ֆունկցիան հարմար է գրել հետևյալ ձևով.
f(x) = -7x 1 – 14x 3 +880 (5.10)
Այժմ, օգտագործելով (5.8)–(5.10), մենք կազմում ենք նախնական սիմպլեքս աղյուսակը.

Զրոյական տողը պարունակում է օբյեկտիվ ֆունկցիայի համապատասխան փոփոխականների հակառակ նշանով գործակիցները: Օպտիմալության չափանիշ (նվազագույն որոնման խնդրի համար). թույլատրելի հիմնական լուծում ( x 0) օպտիմալ է, եթե զրոյական տողում չկա մեկ խիստ դրական թիվ (չհաշված օբյեկտիվ ֆունկցիայի արժեքը (880)): Այս կանոնը վերաբերում է նաև հետագա կրկնություններին (աղյուսակներին): Զրոյական շարքի տարրերը կկոչվեն սյունակի գնահատումներ:
Այսպիսով, նախնական իրագործելի հիմքի լուծումը (5.9) ոչ օպտիմալ է. 7>0, 14>0 .
Զրոյական սյունակը պարունակում է հիմնական փոփոխականների արժեքները: Դրանք պետք է լինեն ոչ բացասական (տես հավասարումը (5.7)): Համակարգից (5.8) փոփոխականների գործակիցները գրվում են առաջինից չորրորդ տողերից։
Որովհետև x 0օպտիմալ չէ, ապա մենք պետք է անցնենք թույլատրելի լուծումների պոլիէդրոնի մեկ այլ գագաթ (կառուցենք նոր d.b.r.): Դա անելու համար դուք պետք է գտնեք առաջատար տարրը և կատարեք որոշակի փոխակերպում (սիմպլեքս փոխակերպում):
Նախ, մենք գտնում ենք աղյուսակի առաջատար տարրը, որը կանգնած է առաջատար սյունակի (ամենաբարձր դրական գնահատական ​​ունեցող սյունակի) և առաջատար տողի (զրոյական սյունակի տարրերի և զրոյական սյունակի տարրերի նվազագույն հարաբերակցությանը համապատասխանող տողի խաչմերուկում): առաջատար սյունակի համապատասխան տարրեր (խիստ դրական):
Աղյուսակ 1-ում առաջատար սյունակը երրորդ սյունակն է, իսկ առաջատար տողը չորրորդ տողն է: (min(40/1.30/1)=30/1)նշվում են սլաքներով, իսկ առաջատար տարրը նշվում է շրջանով: Առաջատար տարրը ցույց է տալիս, որ հիմքում ընկած փոփոխականը x 6անհրաժեշտ է փոխարինել ոչ հիմնականով x 3. Այնուհետև կլինեն նոր հիմնական փոփոխականները x 2, x 3, x 4, x 5,և ոչ հիմնական - x 1, x 6,. Սա նշանակում է անցում դեպի թույլատրելի լուծումների պոլիէդրոնի նոր գագաթին։ Գտնել նոր իրագործելի հիմքի լուծման կոորդինատային արժեքները x00դուք պետք է կառուցեք նոր սիմպլեքս աղյուսակ և դրանում տարրական փոխակերպումներ կատարեք.
Ա)բաժանեք առաջատար գծի բոլոր տարրերը առաջատար տարրով, դրանով իսկ առաջատար տարրը վերածելով 1-ի (հաշվարկի հեշտության համար);
բ)օգտագործելով առաջատար տարրը (հավասար է 1-ի), առաջատար սյունակի բոլոր տարրերը վերածեք զրոների (անհայտները վերացնելու մեթոդի նման);
Արդյունքում, նոր հիմնական փոփոխականների արժեքները ստացվում են զրոյական սյունակում x 2, x 3, x 4, x 5,(տես աղյուսակ 2) - նոր գագաթի հիմնական բաղադրիչները x00(ոչ հիմնական բաղադրիչներ x 1 =0, x 6 =0,).

Ինչպես ցույց է տալիս Աղյուսակ 2-ը, նոր հիմնական լուծումը x 00 =(0,10,30,20,40,0)ենթաօպտիմալ (զրոյական տողը պարունակում է 7 ոչ բացասական միավոր): Հետևաբար, առաջատար տարր 1-ով (տես Աղյուսակ 2) մենք կառուցում ենք նոր սիմպլեքս աղյուսակ, այսինքն. կառուցել նոր իրագործելի հիմնական լուծում

Աղյուսակ 3-ը համապատասխանում է ընդունելի հիմնական լուծմանը x 000 =(10,0,30,10,50,0)և դա օպտիմալ է, քանի որ զրոյական գծում դրական գնահատականներ չկան։ Ահա թե ինչու f(x 000)=390օբյեկտիվ ֆունկցիայի նվազագույն արժեքն է:
Պատասխան. x 000 =(10, 0, 30, 10, 50, 0)- նվազագույն միավոր, f(x 000)=390.

Պայմանականորեն ստանդարտ գծային ծրագրավորման խնդիր

Դուք պետք է կատարեք հետևյալ առաջադրանքները նշված հերթականությամբ:

1. Գտեք ուղիղ խնդրի օպտիմալ պլանը.
   ա) գրաֆիկական մեթոդ.
   բ) սիմպլեքս մեթոդի կիրառմամբ (նախնական հղման պլանը կառուցելու համար խորհուրդ է տրվում օգտագործել արհեստական ​​հիմքի մեթոդը):
2. Կառուցեք երկակի խնդիր.
3. Ուղիղ գծի գրաֆիկական լուծումից գտե՛ք երկակի խնդրի օպտիմալ պլանը՝ օգտագործելով փոխլրացնող թուլության պայմանները։
4. Գտեք երկակի խնդրի օպտիմալ պլանը՝ օգտագործելով երկակիության առաջին թեորեմը, օգտագործելով վերջնական սիմպլեքս աղյուսակը, որը ստացվել է ուղղակի խնդիրը լուծելով (տես բաժին 1բ): Ստուգեք «զույգ երկակի խնդիրների օբյեկտիվ գործառույթների արժեքները համընկնում են դրանց օպտիմալ լուծումներում» հայտարարությունը:
5. Լուծե՛ք երկակի խնդիրը սիմպլեքսի մեթոդով, այնուհետև, օգտագործելով երկակի խնդրի վերջնական սիմպլեքս աղյուսակը, գտե՛ք ուղիղ խնդրի օպտիմալ պլանը՝ օգտագործելով երկակիության առաջին թեորեմը։ Համեմատեք արդյունքը գրաֆիկական ձևով ստացված արդյունքի հետ (տե՛ս պարբերություն 1ա):
6. Գտեք օպտիմալ ամբողջական լուծում.
   ա) գրաֆիկական մեթոդ.
   բ) Գոմորի մեթոդ.
   Համեմատեք ամբողջ և ոչ ամբողջ թվային լուծման գործառույթների արժեքները

Հարցեր ինքնատիրապետման համար

1. Ինչպե՞ս է կառուցվում սիմպլեքս աղյուսակը:
2. Ինչպե՞ս է հիմքի փոփոխությունն արտացոլված աղյուսակում:
3. Ձևակերպեք սիմպլեքս մեթոդի դադարեցման չափանիշ:
4. Ինչպե՞ս կազմակերպել սեղանի վերահաշվարկը:
5. Ո՞ր տողն է հարմար աղյուսակի վերահաշվարկ սկսելու համար:

Դիտարկվում է սիմպլեքս մեթոդով խնդրի լուծման օրինակ, ինչպես նաև երկակի խնդրի լուծման օրինակ։

Բովանդակություն

Խնդրահարույց պայման

Երեք խումբ ապրանքներ վաճառելու համար առևտրային ձեռնարկությունն ունի երեք տեսակի սահմանափակ նյութական և դրամական ռեսուրսներ՝ b 1 = 240, b 2 = 200, b 3 = 160 միավոր: Միաժամանակ 1 հազար ռուբլով ապրանքների 1 խմբի վաճառքի համար։ ապրանքաշրջանառությունը, առաջին տեսակի ռեսուրսը սպառվում է 11 = 2 միավորի չափով, երկրորդ տեսակի ռեսուրսը 21 = 4 միավոր, երրորդ տեսակի ռեսուրսը 31 = չափով. 4 միավոր. 1 հազար ռուբլով 2 և 3 խմբերի ապրանքների վաճառքի համար: շրջանառությունը սպառվում է ըստ առաջին տեսակի ռեսուրսի՝ 12=3, ա 13=6 միավոր, երկրորդ տեսակի ռեսուրսը 22=2, ա 23=4 միավոր, ռեսուրսը՝ երրորդ տեսակը՝ 32 = 6, 33 = 8 միավորի չափով։ Երեք խմբի ապրանքների վաճառքից շահույթ 1 հազար ռուբլով: շրջանառությունը համապատասխանաբար c 1 = 4, c 2 = 5, c 3 = 4 (հազար ռուբլի): Որոշեք առևտրաշրջանառության պլանավորված ծավալը և կառուցվածքը, որպեսզի առևտրային ձեռնարկության շահույթը առավելագույնի հասցվի:

Շրջանառության պլանավորման ուղղակի խնդրին. լուծվում է սիմպլեքս մեթոդով, շարադրել երկակի խնդիրգծային ծրագրավորում.
Տեղադրեք միավորել փոփոխականների զույգերըուղղակի և երկակի խնդիրներ.
Ըստ փոփոխականների խոնարհված զույգերի՝ ուղղակի խնդրի լուծումից ստանում ենք երկակի խնդրի լուծում, որում այն ​​արտադրվում է ռեսուրսների գնահատում, ծախսվել է ապրանքների վաճառքի վրա։

Խնդիրը լուծել սիմպլեքս մեթոդով

Թող x 1, x 2, x 3 լինի վաճառված ապրանքների քանակը, հազար ռուբլով, համապատասխանաբար 1, 2, 3 խմբեր: Այնուհետև խնդրի մաթեմատիկական մոդելն ունի ձև.

F = 4 x 1 + 5 x 2 + 4 x 3 -> մաքս

0)))(~)" title="delim(lbrace)(matrix(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

Մենք լուծում ենք սիմպլեքս մեթոդը.

Մենք ներկայացնում ենք լրացուցիչ փոփոխականներ x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 անհավասարությունները հավասարության վերածելու համար:

Որպես հիմք ընդունենք x 4 = 240; x 5 = 200; x 6 = 160:

Մենք մուտքագրում ենք տվյալները սիմպլեքս սեղան

Սիմպլեքս թիվ 1 աղյուսակ

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

0 240 + 0 200 + 0 160 = 0

Մենք հաշվարկում ենք հաշվարկները՝ օգտագործելով բանաձևը.

Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0

Քանի որ կան բացասական գնահատականներ, պլանը օպտիմալ չէ: Նվազագույն միավոր.

Մենք հիմք ենք դնում x 2 փոփոխականը:

Մենք սահմանում ենք հիմքից բխող փոփոխական: Դա անելու համար մենք գտնում ենք x2 սյունակի ամենափոքր ոչ բացասական հարաբերակցությունը:

= 26.667

Ամենափոքր ոչ բացասական՝ Q 3 = 26.667: Մենք հիմքից հանում ենք x 6 փոփոխականը

3-րդ տողը բաժանեք 6-ի։
1-ին տողից հանել 3-րդ տողը՝ բազմապատկելով 3-ով
2-րդ տողից հանել 3-րդ տողը՝ 2-ով բազմապատկած

Մենք հաշվարկում ենք.

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

Սիմպլեքս թիվ 2 աղյուսակ

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

0 160 + 0 440/3 + 5 80/3 = 400/3

Մենք հաշվարկում ենք հաշվարկները՝ օգտագործելով բանաձևը.

Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6

Քանի որ կա բացասական գնահատական ​​Δ 1 = - 2/3, պլանը օպտիմալ չէ:

Մենք հիմք ենք դնում x 1 փոփոխականը:

Մենք սահմանում ենք հիմքից բխող փոփոխական: Դա անելու համար մենք գտնում ենք x 1 սյունակի ամենափոքր ոչ բացասական հարաբերակցությունը:

Ամենափոքր ոչ բացասականը. Q 3 = 40: Մենք հիմքից հանում ենք x 2 փոփոխականը

3-րդ տողը բաժանեք 2/3-ի։
2-րդ տողից հանել 3-րդ տողը՝ բազմապատկված 8/3-ով

Մենք հաշվարկում ենք.

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

Սիմպլեքս թիվ 3 աղյուսակ

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

0 160 + 0 40 + 4 40 = 160

Մենք հաշվարկում ենք հաշվարկները՝ օգտագործելով բանաձևը.

Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1) + 4 1/4 - 0 = 1

Քանի որ բացասական գնահատականներ չկան, պլանը օպտիմալ է:

Խնդրի լուծում.

x 1 = 40; x2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x6 = 0; F max = 160

Այսինքն՝ անհրաժեշտ է վաճառել առաջին տեսակի ապրանքը 40 հազար ռուբլու չափով։ 2 և 3 տեսակի ապրանքներ վաճառելու կարիք չկա։ Այս դեպքում առավելագույն շահույթը կլինի F max = 160 հազար ռուբլի:

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

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

Z = 240 y 1 + 200 y 2 + 160 y 3 -> րոպե

Title="delim(lbrace)(matrix(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0))) (~)">!}

Մենք ներմուծում ենք լրացուցիչ փոփոխականներ y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 անհավասարությունները հավասարության վերածելու համար:

Ուղղակի և երկակի խնդիրների փոփոխականների խոնարհված զույգերն ունեն ձև.

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

Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;

Y 1 = 0; y2 = 0; y 3 = 1; Z min = 160;

>> >> >> Սիմպլեքս մեթոդ

Սիմպլեքս մեթոդ

Ցանկացած լուծում կարելի է գտնել սիմպլեքս մեթոդ. Մինչ սիմպլեքս մեթոդն օգտագործելը պետք է սկզբնական խնդիրը գրել հիմնական գծային ծրագրավորման խնդրի տեսքով, եթե այն չունի նման ձև։

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

Թող անհրաժեշտ լինի գտնել ֆունկցիայի առավելագույն արժեքը

պայմաններով

Այստեղ և - տրված հաստատուն թվեր

Այս խնդրի վեկտորային ձևը հետևյալն է՝ գտնել ֆունկցիայի առավելագույնը

պայմաններով

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

Թող դնենք – Քանի որ վեկտորները

միայնակ, ապա և

Թեորեմ 5 (հղման պլանի օպտիմալության նշան): (22) – (24) Հիմնական առաջադրանքի պլան օպտիմալ է, եթե

ցանկացած j-ի համար

Թեորեմ 6. Եթե , որոշ j=k-ի համար և թվերի մեջ դրական թվեր չկան(22) ապա օբյեկտիվ ֆունկցիան (22) – (24) առաջադրանքներ

սահմանափակված չէ իր բազմաթիվ ծրագրերով:

Թեորեմ 7. (22) – (24)Եթե ​​առաջադրանքի տեղեկատու պլանըոչ այլասերված , Եվ Բայցթվերի շարքումկան դրական (ոչ բոլորը

Ձևակերպված թեորեմները հնարավորություն են տալիս ստուգել հայտնաբերված հղման պլանի օպտիմալ լինելը և բացահայտել նոր հղման պլանին անցնելու իրագործելիությունը:

Առավել հարմար է ուսումնասիրել հղման պլանը օպտիմալության համար, ինչպես նաև հետագա հաշվողական գործընթացը, եթե խնդրի պայմանները և նախնական հղման պլանը որոշելուց հետո ստացված նախնական տվյալները գրված են այնպես, ինչպես ցույց է տրված Աղյուսակում: 3.

Այս աղյուսակի Գ 6 սյունակում գրված են անհայտ օբյեկտիվ ֆունկցիաների գործակիցները՝ ունենալով նույն ինդեքսները, ինչ տվյալ հիմքի վեկտորները։

Սյունակում գրվում են սկզբնական հղման պլանի դրական բաղադրիչները, իսկ հաշվարկների արդյունքում դրանում ստացվում են օպտիմալ պլանի դրական բաղադրիչները։ Վեկտորների սյունակները ներկայացնում են այս վեկտորների ընդլայնման գործակիցները տվյալ հիմքի վեկտորների մեջ:

Աղյուսակում 3 առաջին մտողերը որոշվում են խնդրի սկզբնական տվյալներով, և հաշվարկվում են (m+1)-րդ շարքի ցուցանիշները։ Այս տողում վեկտորային սյունակում գրեք օբյեկտիվ ֆունկցիայի արժեքը, որը նա վերցնում է տվյալ տեղեկատու պլանի համար, իսկ վեկտորային սյունակում. – իմաստը

Z j-ի արժեքը հայտնաբերվում է որպես վեկտորի և վեկտորի սկալյար արտադրյալ

Արժեքը հավասար է P 0 վեկտորի և վեկտորի սկալյար արտադրյալին.

Աղյուսակ 3-ը լրացնելուց հետո սկզբնական հղման պլանը ստուգվում է օպտիմալության համար: Դա անելու համար նայեք աղյուսակի րդ շարքի տարրերին: Արդյունքում կարող է առաջանալ հետևյալ երեք դեպքերից մեկը.

1) j=m+1-ի համար, (ժամը): Հետեւաբար, այս դեպքում թվեր բոլորի համար ժ 1-ից մինչև n;

2) ոմանց համար ժև այս ցուցանիշին համապատասխանող բոլոր արժեքները

3) որոշ ցուցանիշների համար ժ, և յուրաքանչյուր այդպիսին ժԹվերից գոնե մեկը դրական է:

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

Հիմքից բացառվող վեկտորը որոշելու համար գտնել բոլորի համար Թող այս նվազագույնը հասնի i=r. Այնուհետև վեկտորը բացառվում է հիմքից, և թիվը կոչվում է թույլատրելի տարր.

Կոչվում է այն սյունը և տողը, որոնց խաչմերուկում կա լուծող տարր ուղեցույցներ.

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

(25)

և նոր հղման պլանին համապատասխանող նոր հիմքի վեկտորների միջոցով վեկտորների ընդլայնման գործակիցները՝ ըստ բանաձևերի.

(26)

Հաշվարկից հետո և ըստ (25) և (26) բանաձևերի, դրանց արժեքները մուտքագրվում են աղյուսակում: 4. Այս աղյուսակի րդ շարքի տարրերը կարելի է հաշվարկել կամ բանաձևերի միջոցով

(27)

(28)

կամ հիմնվելով դրանց սահմանման վրա:

Աղյուսակ 3

ես

Հիմք

Գ բ

P0

գ 1

գ 2

...

գ ռ

...

գ մ

c m+1

...

գ k

...

c n

Պ 1

P2

...

Պ ր

...

Ժամ

P m+1

...

Պկ

...

Պ ն

1

Պ 1

գ 1

բ 1

1

0

...

0

...

0

ա 1մ+1

...

ա 1կ

...

ա 1n

2

P2

գ 2

բ 2

0

1

...

0

...

0

ա 2մ+1

...

մի 2կ

...

a 2n

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

r

Պ ր

գ ռ

բ ռ

0

0

...

1

...

0

ա ռմ + 2

...

ա րկ

...

առն

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

մ

Ժամ

գ մ

բ մ

0

0

...

0

...

1

am + 1

...

մի մկ

...

մի մն

մ+1

Ֆ մ

0

0

...

0

...

0

Δm+1

...

Δk

...

Δn

Աղյուսակ 4

ես

Բազ է

Գ բ

P0

գ 1

գ 2

...

գ ռ

...

գ մ

c m+1

...

գ k

...

c n

Պ 1

P2

...

Պ ր

...

Ժամ

P m+1

...

Պկ

...

Պ ն

1

Պ 1

գ 1

բ 1

1

0

...

ա «1ր

...

0

ա «1մ+1

...

0

...

ա «1n

2

P2

գ 2

բ 2

0

1

...

ա «2ր

...

0

ա «2մ+1

...

0

...

ա «2n

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

r

Պ ր

գ ռ

բ ռ

0

0

...

ա «rr

...

0

ա «rm+2

...

1

...

ա «ռն

:

:

:

:

:

:

:

:

:

:

:

:

:

:

:

մ

Ժամ

գ մ

բ մ

0

0

...

մի «պրն

...

1

ա «մմ+1

...

0

...

մի «մն

մ+1

Ֆ մ

0

0

...

z "r -c r

...

0

z «m+1 -c m+1

...

0

...

z "n -c n

Երրորդ շարքի տարրերը գտնելու երկու եղանակների առկայությունը թույլ է տալիս վերահսկել կատարված հաշվարկների ճիշտությունը:

Բանաձևից (27) հետևում է, որ մի հղման պլանից մյուսին անցնելիս առավել նպատակահարմար է հիմքում ներդնել ինդեքս ունեցող վեկտոր. ժ, որի բացարձակ արժեքով առավելագույնը թիվն է . Այնուամենայնիվ, հաշվողական գործընթացը պարզեցնելու համար ապագայում մենք կորոշենք հիմքում ներդրված վեկտորը՝ հիմնվելով բացասական թվերի առավելագույն բացարձակ արժեքի վրա։ Եթե ​​կան մի քանի նման թվեր, ապա մենք հիմք կներկայացնենք մի վեկտոր, որն ունի նույն ցուցանիշը, ինչ այս թվերով որոշված ​​թվերի առավելագույնը:

Այսպիսով, մի հղման պլանից մյուսին անցումը հանգում է մի սիմպլեքս աղյուսակից մյուսին անցմանը: Սիմպլեքս նոր աղյուսակի տարրերը կարող են հաշվարկվել ինչպես կրկնվող (25)-(28) բանաձևերի, այնպես էլ դրանցից ուղղակիորեն բխող կանոնների միջոցով։ Այս կանոնները հետևյալն են.

Հիմքում ներառված վեկտորների սյունակներում, համանուն վեկտորների տողերի և սյունակների հատման կետում տեղադրվում են միավորներ, և այս սյունակների բոլոր մյուս տարրերը հավասարվում են զրոյի։

Վեկտորների տարրերը և նոր սիմպլեքս աղյուսակի տողում, որում գրված է հիմքում մուտքագրված վեկտորը, ստացվում են սկզբնական աղյուսակի նույն տողի տարրերից՝ դրանք բաժանելով լուծվող տարրի արժեքի վրա։ Մուտքային վեկտորի տողում գտնվող սյունակում մուտքագրեք արժեքը, որտեղ կ – մուտքային վեկտորի ինդեքսը:

Վեկտորային սյունակների և նոր սիմպլեքս աղյուսակի մնացած տարրերը հաշվարկվում են եռանկյունու կանոնի միջոցով: Այս տարրերից որևէ մեկը հաշվարկելու համար հայտնաբերվում են երեք թվեր.

1) թիվ, որը կանգնած է սկզբնական սիմպլեքս աղյուսակում նոր սիմպլեքս աղյուսակի ցանկալի տարրի փոխարեն.

2) նոր սիմպլեքս աղյուսակի ցանկալի տարրը պարունակող տողի և հիմքում մուտքագրված վեկտորին համապատասխան սյունակի հատման կետում սկզբնական սիմպլեքս աղյուսակում.

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

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

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

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

Այս դեպքը շատ հազվադեպ է, ուստի մենք չենք անդրադառնա դրա վրա:

Այսպիսով, սիմպլեքս մեթոդով օպտիմալ պլան գտնելը ներառում է հետևյալ քայլերը.

1. Գտեք հղման պլան:

3. Պարզեք, թե արդյոք կա առնվազն մեկ բացասական թիվ: Եթե ​​ոչ, ապա գտնված հղման պլանը օպտիմալ է: Եթե ​​թվերի մեջ կան բացասական թվեր, ապա դրանք կա՛մ հաստատում են խնդրի անլուծելիությունը, կա՛մ անցնում են նոր հղման պլանի։

4. Գտեք սյունակների և տողերի ուղեցույցները:

Ուղղորդող սյունակը որոշվում է բացարձակ արժեքով ամենամեծ բացասական թվով, իսկ ուղեցույցի տողը որոշվում է վեկտորի սյունակի բաղադրիչների և ուղեցույցի դրական բաղադրիչների հարաբերակցությունների նվազագույն չափով: 5. Օգտագործելով (25) – (28) բանաձևերը, որոշվում են նոր հղման պլանի դրական բաղադրիչները և վեկտորի ընդլայնման գործակիցները.Պջ

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

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

Օրինակ 9. Պատրաստման համար Ա,տարբեր ապրանքներ IN իսկ C ձեռնարկությունը օգտագործում է երեքտարբեր տեսակներ Ա,տարբեր ապրանքներհումք. Յուրաքանչյուր տեսակի մեկ ապրանքի արտադրության համար հումքի սպառման դրույքաչափերը, մեկ ապրանքի գինը ԵվՀԵՏ

, ինչպես նաև յուրաքանչյուր տեսակի հումքի ընդհանուր քանակը, որը կարող է օգտագործել ձեռնարկությունը, բերված են աղյուսակում: 5.

Աղյուսակ 5	Հումքի տեսակը			Հումքի արժեքը (կգ) մեկ ապրանքի համար
Հումքի ընդհանուր քանակը (կգ)

Մեկ ապրանքի գինը (RUB) Ա,տարբեր ապրանքներհումք. Յուրաքանչյուր տեսակի մեկ ապրանքի արտադրության համար հումքի սպառման դրույքաչափերը, մեկ ապրանքի գինը ԵվԱպրանքներ

կարող է արտադրվել ցանկացած համամասնությամբ (վաճառքը երաշխավորված է), սակայն արտադրությունը սահմանափակվում է ձեռնարկությանը հատկացված յուրաքանչյուր տեսակի հումքով։

Լուծում.Կազմեք արտադրանքի արտադրության պլան, որում ձեռնարկության կողմից արտադրված բոլոր ապրանքների ընդհանուր արժեքը առավելագույնն է: ԱԵկեք ստեղծենք խնդրի մաթեմատիկական մոդելը։ Պահանջվող արտադրանքի թողարկում նշանակել x 1, արտադրանքներս - միջոցով , ապրանքներՀԵՏ -

(29)

միջոցով . Քանի որ ձեռնարկությանը հատկացված յուրաքանչյուր տեսակի հումքի ֆոնդի վրա կան սահմանափակումներ, փոփոխականները պետք է բավարարեն անհավասարությունների հետևյալ համակարգը. ԱՁեռնարկության կողմից արտադրված արտադրանքի ընդհանուր արժեքը՝ x 1 արտադրանքի թողարկման պայմանով IN, ապրանքներ և ապրանքներՀԵՏ

կազմում է

Ըստ իրենց տնտեսական բովանդակության՝ փոփոխականները կարող են ընդունել միայն ոչ բացասական արժեքներ.

Այս խնդիրը գրենք հիմնական գծային ծրագրավորման խնդրի տեսքով։ Դա անելու համար եկեք անհավասարության սահմանափակումներից անցնենք հավասարության սահմանափակումների: Ներկայացնենք երեք լրացուցիչ փոփոխականներ, որոնց արդյունքում սահմանափակումները կգրվեն հավասարումների համակարգի տեսքով.

Տնտեսական առումով այս լրացուցիչ փոփոխականները նշանակում են այս կամ այն ​​տեսակի հումքի քանակությունը, որը չի օգտագործվում տվյալ արտադրական պլանում: Օրինակ՝ – Սա I տիպի հումքի չօգտագործված քանակությունն է։

Փոխակերպված հավասարումների համակարգը գրում ենք վեկտորային ձևով.

Քանի որ վեկտորների շարքում Քանի որ կան երեք միավոր վեկտորներ, հղման պլանը կարող է ուղղակիորեն գրվել այս խնդրի համար: Դա է պլանը X=(0; 0; 0; 360; 192; 180), որը սահմանվում է եռաչափ միավոր վեկտորների համակարգով, որոնք կազմում են եռաչափ վեկտորային տարածության հիմքը:

Մենք կազմում ենք Simplex աղյուսակ I կրկնության համար (Աղյուսակ 6), հաշվարկում ենք արժեքները և ստուգում նախնական հղման պլանը օպտիմալության համար.

Հիմքի վեկտորների համար

Աղյուսակ 6

	r 5

Ինչպես երևում է Աղյուսակ 6-ից, բոլոր հիմնական փոփոխականների արժեքները հավասար են զրոյի, և լրացուցիչ փոփոխականներն իրենց արժեքները վերցնում են խնդրի սահմանափակումներին համապատասխան:

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

Դա երեւում է աղյուսակի 4-րդ տողից։ 6, քանի որ այն պարունակում է երեք բացասական թիվ. և բացասական թվերը ոչ միայն ցույց են տալիս արտադրության ընդհանուր արժեքի ավելացման հնարավորությունը, այլև ցույց են տալիս, թե որքան կավելանա այս գումարը, երբ այս կամ այն ​​տեսակի արտադրանքի միավորը մտցվի պլանում: ԱԱյսպիսով, թիվը՝ 9 նշանակում է, որ երբ մեկ ապրանք ներառված է արտադրության պլանում INապահովում է արտադրանքի ավելացում 9 ռուբլով: Եթե ​​դուք ներառում եք մեկ ապրանք արտադրության պլանում և C, ապա արտադրված արտադրանքի ընդհանուր արժեքը կավելանա համապատասխանաբար 10 և 16 ռուբլով:Հետևաբար, տնտեսական տեսանկյունից առավել նպատակահարմար է արտադրանքը ներառել արտադրության պլանում ՀԵՏ.Նույնը պետք է արվի սիմպլեքս մեթոդի պաշտոնական նշանի հիման վրա, քանի որ բացարձակ արժեքով առավելագույն բացասական թիվը գտնվում է վեկտորի սյունակի 4-րդ շարքում: ՀԵՏ.Ռ

3. Հետևաբար, մենք վեկտորը ներկայացնում ենք հիմքում և ապրանքներձեռնարկությունը կարող է արտադրել՝ հաշվի առնելով սպառման տեմպերը և յուրաքանչյուր տեսակի հումքի առկա ծավալները: Քանի որ այս տեսակի հումք կա համապատասխանաբար 360, 192 և 180 կգ, և մեկ ապրանքի համար. և ապրանքներՅուրաքանչյուր տեսակի հումք ծախսելու համար պահանջվում է համապատասխանաբար 12, 8 և 3 կգ, ապա արտադրանքի առավելագույն քանակը. և ապրանքներ, որը կարող է արտադրվել ձեռնարկության կողմից, հավասար է այսինքն՝ արտադրանքի արտադրության սահմանափակող գործոն և ապրանքներ II տիպի հումքի առկա ծավալն է։ Հաշվի առնելով դրա առկայությունը՝ ընկերությունը կարող է արտադրել 24 ապրանքատեսակ և C, ապա արտադրված արտադրանքի ընդհանուր արժեքը կավելանա համապատասխանաբար 10 և 16 ռուբլով:Այս դեպքում ամբողջությամբ կօգտագործվի II տիպի հումքը։

Հետեւաբար, վեկտորը ՀԵՏ. 5-ը ենթակա է բացառման հիմքից։ Վեկտորային սյունակ ՀԵՏ. 3-ից 2-րդ շարքերը ուղեցույցներ են:

Մենք կազմում ենք աղյուսակ II կրկնության համար (Աղյուսակ 7):

	Աղյուսակ 7 4 Պ 3

էջ Գ բՆախ, մենք լրացնում ենք հիմքում նոր ներմուծված վեկտորի գիծը, այսինքն՝ այն տողը, որի թիվը համընկնում է ուղեցույցի համարի հետ: Այստեղ ուղեցույցը 2-րդ տողն է։ Այս շարքի տարրերը ներկայացված են աղյուսակում: 7-ը ստացվում է 6-րդ աղյուսակի համապատասխան տարրերից՝ բաժանելով դրանք լուծող տարրի վրա (այսինքն՝ 8-ի): Ընդ որում, սյունակում

Հիմքում մուտքագրված վեկտորի սյունակում գրում ենք գործակիցը։ Այնուհետև լրացնում ենք սյունակների տարրերը նոր հիմքում ներառված վեկտորների համար։ Այս սյունակներում համանուն վեկտորների տողերի և սյունակների հատման կետում դնում ենք միավորներ, իսկ մնացած բոլոր տարրերը հավասարվում են զրոյի։

Աղյուսակի մնացած տարրերը որոշելու համար: ՀԵՏ. 7 մենք կիրառում ենք եռանկյունու կանոնը. Այս տարրերը կարող են նաև ուղղակիորեն հաշվարկվել՝ օգտագործելով կրկնվող բանաձևերը:

Եկեք հաշվարկենք աղյուսակի տարրերը. 7 կանգնած վեկտորային սյունակում ՀԵՏ. 0 . Առաջինն այս սյունակի 1-ին շարքում է։ Այն հաշվարկելու համար մենք գտնում ենք երեք թիվ.

1) աղյուսակի համարը. 6 վեկտորի սյունակի խաչմերուկում Աղյուսակ 7 0 և 1-ին տողեր (360);

2) աղյուսակի համարը. 6 վեկտորի սյունակի խաչմերուկում ՀԵՏ. 3-րդ և 1-ին տողեր (12);

3) աղյուսակի համարը. 7 վեկտորի սյունակի խաչմերուկում ՀԵՏ. 0 և 2-րդ տողերը (24):

Առաջին թվից հանելով մյուս երկուսի արտադրյալը՝ գտնում ենք անհրաժեշտ տարրը՝ 360 – 12 x 24 = 72; գրեք այն վեկտորի սյունակի 1-ին տողում ՀԵՏ. 0 ներդիր: 7. ՀԵՏ.Վեկտորի երկրորդ սյունակի տարրը ՀԵՏ. 0 ներդիր: 7-ն արդեն ավելի վաղ էր հաշվարկված։ Վեկտորի երրորդ սյունակի տարրը հաշվարկելու համար Աղյուսակ 7 0 մենք նաև երեք թիվ ենք գտնում. Դրանցից առաջինը (180) գտնվում է վեկտորի 3-րդ շարքի և սյունակի խաչմերուկում. ՀԵՏ. 0 ներդիր: 6, երկրորդ (3) - վեկտորի 3-րդ շարքի և սյունակի խաչմերուկում ՀԵՏ. 0 և 2-րդ տողերը (24):

3 սեղան 6, երրորդ (24) - վեկտորի 2-րդ շարքի և սյունակի խաչմերուկում ՖՆույն վեկտորի սյունակի 4-րդ շարքում 0-ը կարելի է գտնել երկու եղանակով.

1) ըստ բանաձևի, այսինքն.

2) եռանկյունի կանոնի համաձայն. այս դեպքում եռանկյունը ձևավորվում է 0, -16, 24 թվերով: Այս մեթոդը հանգեցնում է նույն արդյունքին` 0 - (-16) x 24 = 384:

Վեկտորային սյունակի տարրերը որոշելիս՝ օգտագործելով եռանկյունի կանոնը ՀԵՏ. 0 երրորդ թիվը, որը կանգնած է եռանկյան ստորին գագաթին, ամբողջ ժամանակ մնացել է անփոփոխ և փոխվել են միայն առաջին երկու թվերը: Սա հաշվի առնենք վեկտորի սյունակի տարրերը գտնելիս Աղյուսակ 7 1 սեղան 7. Նշված տարրերը հաշվարկելու համար վեկտորների սյունակներից վերցնում ենք առաջին երկու թվերը Աղյուսակ 7 1 և ՀԵՏ. 3 սեղան 6, իսկ երրորդ համարը աղյուսակից է: 7. Այս թիվը գտնվում է վեկտորի 2-րդ շարքի և սյունակի հատման կետում Աղյուսակ 7Վերջին աղյուսակի 1-ը. Արդյունքում մենք ստանում ենք անհրաժեշտ տարրերի արժեքները՝ 18 – 12 x (3/4) =9; 5 – 3 x (3/4) = 11/4:

Թիվը վեկտորի սյունակի 4-րդ շարքում Աղյուսակ 7 1 սեղան 7-ը կարելի է գտնել երկու եղանակով.

1) ըստ Z 1 -C 1 = (C,P 1) -C 1 բանաձևի ունենք.

2) եռանկյունի կանոնի համաձայն մենք ստանում ենք

Նմանապես, մենք գտնում ենք վեկտորի սյունակի տարրերը Աղյուսակ 7 2 .

Վեկտորի սյունակի տարրեր ՀԵՏ. 5-ը հաշվարկվում է օգտագործելով եռանկյունի կանոնը: Այնուամենայնիվ, այս տարրերը սահմանելու համար կառուցված եռանկյունները տարբեր տեսք ունեն:

Նշված սյունակի 1-ին շարքի տարրը հաշվարկելիս ստացվում է 0,12 և 1/8 թվերով կազմված եռանկյուն։ Հետևաբար, պահանջվող տարրը 0 – 12x (1/8) = -3/2 է: Այս սյունակի 3-րդ շարքի տարրը հավասար է 0 - 3 x (1/8) = -3/8:

Աղյուսակի բոլոր տարրերի հաշվարկի ավարտից հետո: . 7 դրանում նոր հղման պլան և վեկտորի ընդլայնման գործակիցներ են ստացվում բազային վեկտորների P 4, P 3, P 6 և արժեքների և Ինչպես երևում է այս աղյուսակից, առաջադրանքի նոր հղման պլանը պլանն է X և ապրանքներ=(0; 0; 24; 72; 0; 108): Այս արտադրական պլանով արտադրվում է 24 ապրանքատեսակ ՀԵՏ.իսկ չօգտագործված են մնում 1-ին տիպի 72 կգ և III տիպի 108 կգ հումք։ Այս պլանով արտադրված բոլոր ապրանքների արժեքը 384 ռուբլի է: Վեկտորային սյունակում գրված են նշված թվերը ՀԵՏ. 2 . 0 ներդիր: 7. Ինչպես տեսնում եք, այս սյունակի տվյալները դեռ ներկայացնում են դիտարկվող խնդրի պարամետրերը, թեև դրանք էական փոփոխություններ են կրել։ և ապրանքներՓոխվել են նաև այլ սյունակների տվյալները, և դրանց տնտեսական բովանդակությունը դարձել է ավելի բարդ։ Այսպիսով, օրինակ, վերցրեք վեկտորի սյունակի տվյալները Այս սյունակի 2-րդ տողի 1/2 թիվը ցույց է տալիս, թե որքանով պետք է կրճատվի արտադրանքի արտադրությունը, եթե նախատեսում եք թողարկել մեկ ապրանք Աղյուսակ 7 IN. IN, իսկ 4-րդ տողում՝ 2 թիվը ցույց է տալիս, որ եթե նախատեսվում է մեկ ապրանքի թողարկում IN, ապա դա կապահովի արտադրության արտադրանքի ավելացում արժեքային առումով 2 ռուբլով։ Այսինքն, եթե մեկ ապրանք ներառեք արտադրության պլանում IN, ապա դա կպահանջի արտադրանքի թողարկման կրճատում և ապրանքներ 1/2 միավորով և կպահանջի լրացուցիչ ծախսեր 9 կգ I տիպի հումք և 3/2 կգ հումք III տիպի, իսկ արտադրված արտադրանքի ընդհանուր արժեքը նոր օպտիմալ պլանի համաձայն կավելանա 2 ռուբլով: Այսպիսով, 9 և 3/2 համարները հանդես են գալիս որպես նոր «նորմեր» մեկ ապրանքի արտադրության համար I և III տիպերի հումքի արժեքի համար: IN(ինչպես երևում է աղյուսակ 6-ից, նախկինում դրանք հավասար էին 15-ի և 3-ի), ինչը բացատրվում է արտադրանքի թողարկման նվազմամբ. և C, ապա արտադրված արտադրանքի ընդհանուր արժեքը կավելանա համապատասխանաբար 10 և 16 ռուբլով:

Վեկտորային սյունակի տվյալները նույնպես ունեն նույն տնտեսական նշանակությունը ՀԵՏ. 1 սեղան ՀԵՏ. 5 . 7. Վեկտորային սյունակում գրված թվերն ունեն մի փոքր այլ տնտեսական բովանդակություն և ապրանքներԱյս սյունակի 2-րդ տողի 1/8 թիվը ցույց է տալիս, որ II տիպի հումքի ծավալի 1 կգ-ով ավելացումը թույլ կտա ավելացնել արտադրանքի թողարկումը. և ապրանքներ 1/8 միավորով Միաժամանակ կպահանջվեր հավելյալ 3/2 կգ I տիպի հումք և 3/8 կգ III տիպի հումք։ Արտադրանքի արտադրանքի ավելացում

1/8 միավորով կհանգեցնի արտադրանքի ավելացմանը 2 ռուբլով: Աղյուսակ 7Աղյուսակում ներկայացված տվյալների վերը նշված տնտեսական բովանդակությունից: 7 հետևում է, որ II կրկնության ժամանակ հայտնաբերված խնդրի պլանը օպտիմալ չէ: Դա երեւում է աղյուսակի 4-րդ տողից։ 7, քանի որ վեկտորի սյունակում Աղյուսակ 7Այս տողի 2-ը բացասական թիվ է՝ 2։ Սա նշանակում է, որ վեկտորը պետք է մուտքագրվի հիմքում Այս սյունակի 2-րդ տողի 1/2 թիվը ցույց է տալիս, թե որքանով պետք է կրճատվի արտադրանքի արտադրությունը 2, այսինքն՝ նոր պլանը պետք է նախատեսի արտադրանքի արտադրություն INԱրտադրվող ապրանքների հնարավոր քանակը որոշելիս INպետք է հաշվի առնել յուրաքանչյուր տեսակի հումքի առկա քանակությունը, այն է՝ արտադրանքի հնարավոր արտադրությունը

սահմանվում է , այսինքն՝ մենք գտնում ենք ՀԵՏ.Հետեւաբար, վեկտորը պետք է բացառվի հիմքից IN 4 այլ կերպ ասած՝ արտադրանքի թողարկում Այս սյունակի 2-րդ տողի 1/2 թիվը ցույց է տալիս, թե որքանով պետք է կրճատվի արտադրանքի արտադրությունըսահմանափակված է ձեռնարկությանը հասանելի I տիպի հումքով: Հաշվի առնելով այդ հումքի առկա ծավալները՝ ընկերությունը պետք է թողարկի 8 ապրանքատեսակ Աղյուսակ 7 9 թիվը լուծող տարրն է, իսկ վեկտորի սյունակը

Աղյուսակի 2-ին և 1-ին տողերը. 7-ը ուղեցույցներ են:

	Աղյուսակ 7 2 Աղյուսակ 7 3

Մենք կազմում ենք աղյուսակ III կրկնության համար (Աղյուսակ 8): ՀԵՏ. 2 . Աղյուսակ 8 Գ բԱղյուսակում 8, նախ լրացնում ենք 1-ին շարքի տարրերը, որը հիմքում նոր ներմուծված վեկտորի շարքն է. .

Այնուհետև լրացնում ենք հիմքի վեկտորների սյունակների տարրերը և, օգտագործելով եռանկյունի կանոնը, հաշվարկում մնացած սյունակների տարրերը։ Արդյունքում, աղյուսակում. 8 մենք ստանում ենք նոր հղման պլան Ինչպես երևում է այս աղյուսակից, առաջադրանքի նոր հղման պլանը պլանն է=(0; 8; 20; 0; 0; 96) և վեկտորի ընդլայնման գործակիցները բազային վեկտորների և համապատասխան արժեքների միջոցով և

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

Ուստի արտադրական պլան, որը ներառում է 8 ապրանքատեսակների արտադրություն INև 20 ապրանք և ապրանքներ, օպտիմալ է։ Արտադրանքի արտադրության այս պլանով I և II տիպի հումքը ամբողջությամբ օգտագործվում է և III տիպի 96 կգ հումք մնում է չօգտագործված, իսկ արտադրված արտադրանքի արժեքը 400 ռուբլի է։

Արտադրության օպտիմալ պլանը չի նախատեսում արտադրանքի արտադրություն Ա.Տիպի արտադրանքի արտադրության պլանի ներածություն Ակհանգեցնի նշված ընդհանուր ծախսերի կրճատմանը: Սա երևում է վեկտորի սյունակի 4-րդ շարքից Աղյուսակ 7 1, որտեղ 5 թիվը ցույց է տալիս, որ տվյալ պլանի համար, ներառյալ արտադրանքի միավորի թողարկումը Ահանգեցնում է միայն ընդհանուր արժեքի նվազմանը 5 ռուբլով:

Լուծում այս օրինակըՍիմպլեքս մեթոդը կարող է իրականացվել միայն մեկ աղյուսակի միջոցով (Աղյուսակ 9): Այս աղյուսակում հաշվողական գործընթացի բոլոր երեք կրկնությունները գրանցվում են հաջորդաբար՝ մեկը մյուսի հետևից:

Աղյուսակ 9

	r 5 Աղյուսակ 7 4 Պ 3 Աղյուսակ 7 2 Պ 3

Ինչպես երևում է աղյուսակից. 10, սկզբնական հղման պլանը օպտիմալ չէ: Հետևաբար, մենք անցնում ենք նոր հղման պլանի: Դա կարելի է անել, քանի որ վեկտորների սյունակներում Աղյուսակ 7 1 և Պ 5-ը, որի 4-րդ շարքը պարունակում է բացասական թվեր, ունի դրական տարրեր։ Նոր հղման պլանի անցնելու համար մենք հիմք ենք դնում վեկտորը Պ 5 և բացառել վեկտորը հիմքից Պ 4. Մենք կազմում ենք կրկնության II աղյուսակը:

Աղյուսակ 11

Ինչպես երևում է աղյուսակից. 11, խնդրի նոր հղման պլանը օպտիմալ չէ, քանի որ վեկտորի սյունակի 4-րդ շարքում. Աղյուսակ 7 1-ն արժե -11/3 բացասական թիվ: Քանի որ այս վեկտորի սյունակում դրական տարրեր չկան, այս խնդիրը չունի օպտիմալ պլան։