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

Լուծում:

Ի կրկնություն:

x3, x4, x5, x6 x1,x2. Եկեք արտահայտենք հիմնական փոփոխականները ազատների տեսքով.

Եկեք նվազեցնենք օբյեկտիվ ֆունկցիան հետևյալ ձևով.

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

Աղյուսակ 5.3

Օրիգինալ սիմպլեքս սեղան

Հիմնական լուծման սահմանման համաձայն, ազատ փոփոխականները հավասար են զրոյի, իսկ հիմնական փոփոխականների արժեքները հավասար են ազատ թվերի համապատասխան արժեքներին, այսինքն.

Փուլ 3. ԲՀԿ սահմանափակումների համակարգի համատեղելիության ստուգում:

Այս կրկնության ժամանակ (Աղյուսակ 5.3-ում) սահմանափակման համակարգի անհամատեղելիության նշանը (նշան 1) նույնականացված չէ (այսինքն՝ չկա բացասական ազատ թվով տող (բացի տողից): օբյեկտիվ գործառույթ), որում չի լինի առնվազն մեկ բացասական տարր (այսինքն՝ բացասական գործակից ազատ փոփոխականի համար)):

Այս կրկնության ժամանակ (Աղյուսակ 5.3-ում) օբյեկտիվ ֆունկցիայի անսահմանափակության նշանը (նշան 2) չի հայտնաբերվել (այսինքն՝ օբյեկտիվ ֆունկցիայի տողում բացասական տարրով սյունակ չկա (բացառությամբ ազատ թվերի սյունակի): ) որի մեջ գոնե մեկ դրական տարր չի լինի):

Քանի որ հայտնաբերված հիմնական լուծումը չի պարունակում բացասական բաղադրիչներ, այն թույլատրելի է։

Փուլ 6. օպտիմալության ստուգում:

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

Քանի որ գտնված հիմնական լուծումը թույլատրելի է, մենք կփնտրենք լուծվող սյունակը հետևյալ սխեմայի համաձայն՝ օբյեկտիվ ֆունկցիայի տողում որոշում ենք բացասական տարրերով սյունակները (բացառությամբ ազատ թվերի սյունակի): Աղյուսակ 5.3-ի համաձայն, կան երկու այդպիսի սյունակներ. սյունակ « x1«և սյունակ» x2« Նման սյունակներից ընտրվում է այն, որը պարունակում է նպատակային ֆունկցիայի տողում ամենափոքր տարրը։ Նա կլինի ամենաթողությունը: Սյունակ" x2«պարունակում է ամենափոքր տարրը (–3) սյունակի համեմատ» x1

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

Աղյուսակ 5.4

Օրիգինալ սիմպլեքս սեղան

Աղյուսակ 5.4-ում ամենափոքր դրական գնահատողական հարաբերությունը համապատասխանում է «տողին. x5«Հետևաբար, դա ամենաթողություն կլինի։

Միավորող սյունակի և թույլատրող տողի խաչմերուկում գտնվող տարրն ընդունվում է որպես հնարավորություն: Մեր օրինակում սա այն տարրն է, որը գտնվում է գծի խաչմերուկում « x5«և սյունակներ» x2».

Լուծող տարրը ցույց է տալիս մեկ հիմք և մեկ ազատ փոփոխական, որոնք պետք է փոխարինվեն սիմպլեքս աղյուսակում՝ նոր «բարելավված» հիմնային լուծման անցնելու համար: IN այս դեպքումսրանք փոփոխականներ են x5Եվ x2, նոր սիմպլեքս աղյուսակում (Աղյուսակ 5.5) մենք դրանք փոխանակում ենք։

9.1. Լուծող տարրի փոխակերպում.

Աղյուսակ 5.4-ի լուծման տարրը փոխակերպվում է հետևյալ կերպ.

Ստացված արդյունքը մուտքագրում ենք աղյուսակ 5.5-ի նմանատիպ բջիջ:

9.2. Բանաձևի տողերի փոխարկում:

Մենք բաժանում ենք 5.4 աղյուսակի լուծվող տողի տարրերը այս սիմպլեքս աղյուսակի լուծվող տարրի վրա, արդյունքները տեղավորվում են նոր սիմպլեքս աղյուսակի նմանատիպ բջիջներում (աղյուսակ 5.5): Լուծման լարային տարրերի փոխակերպումները տրված են Աղյուսակ 5.5-ում:

9.3. Բանաձեւի սյունակի փոխակերպում.

Աղյուսակ 5.4-ի լուծման սյունակի տարրերը բաժանում ենք այս սիմպլեքս աղյուսակի լուծման տարրի վրա, և արդյունքը վերցվում է հակառակ նշանով։ Ստացված արդյունքները տեղավորվում են նոր սիմպլեքս աղյուսակի նմանատիպ բջիջներում (Աղյուսակ 5.5): Որոշման սյունակի տարրերի փոխակերպումները բերված են Աղյուսակ 5.5-ում:

9.4. Սիմպլեքս աղյուսակի մնացած տարրերի փոխակերպումը:

Սիմպլեքս աղյուսակի մնացած տարրերի (այսինքն՝ լուծվող տողում և լուծվող սյունակում չգտնվող տարրերի) փոխակերպումն իրականացվում է «ուղղանկյունի» կանոնի համաձայն։

Օրինակ, հաշվի առեք գծի խաչմերուկում գտնվող տարրը փոխակերպելը: x3« և «» սյունակները, պայմանականորեն նշենք այն» x3« Աղյուսակ 5.4-ում մենք մտովի գծում ենք ուղղանկյուն, որի մեկ գագաթը գտնվում է այն բջիջում, որի արժեքը մենք փոխակերպում ենք (այսինքն՝ բջիջում « x3«), իսկ մյուսը (անկյունագծային գագաթը) գտնվում է լուծող տարր ունեցող բջիջում։ Մյուս երկու գագաթները (երկրորդ անկյունագծի) եզակիորեն որոշված ​​են։ Այնուհետև բջիջի փոխակերպված արժեքը » x3«հավասար կլինի այս բջիջի նախորդ արժեքին` հանած այն կոտորակը, որի հայտարարում լուծվող տարրն է (աղյուսակ 5.4-ից), իսկ համարիչում` երկու այլ չօգտագործված գագաթների արտադրյալը, այսինքն.

« x3»: .

Այլ բջիջների արժեքները փոխակերպվում են նույն կերպ.

« x3 x1»: ;

« x4»: ;

« x4 x1»: ;

« x6»: ;

« x6 x1»: ;

«»: ;

« x1»: .

Այս փոխակերպումների արդյունքում ստացվել է նոր սիմպլեքս աղյուսակ (Աղյուսակ 5.5):

II կրկնություն:

Փուլ 1. սիմպլեքս աղյուսակի կազմում:

Աղյուսակ 5.5

Սիմպլեքս սեղանII կրկնություններ

Փուլ 2. հիմնական լուծման որոշում:

Սիմպլեքս փոխակերպումների արդյունքում ստացվել է նոր հիմնական լուծում (Աղյուսակ 5.5).

Ինչպես տեսնում եք, այս հիմնական լուծման դեպքում օբյեկտիվ ֆունկցիայի արժեքը = 15, որն ավելի մեծ է, քան նախորդ հիմնական լուծումը:

Աղյուսակ 5.5-ի 1-ին հատկանիշի համաձայն սահմանափակումների համակարգի անհամապատասխանությունը չի հայտնաբերվել:

Փուլ 4. օբյեկտիվ ֆունկցիայի սահմանների ստուգում:

Աղյուսակ 5.5-ի 2-րդ չափանիշի համաձայն օբյեկտիվ ֆունկցիայի անսահմանափակ լինելը բացահայտված չէ:

Փուլ 5. հայտնաբերված հիմնական լուծման թույլատրելիության ստուգում:

Չափանիշ 4-ի համաձայն գտնված հիմնական լուծումը օպտիմալ չէ, քանի որ սիմպլեքս աղյուսակի օբյեկտիվ ֆունկցիայի գիծը (Աղյուսակ 5.5) պարունակում է բացասական տարր՝ –2 (այս տողի ազատ թիվը հաշվի չի առնվում դա դիտարկելիս բնորոշ): Այսպիսով, մենք անցնում ենք 8-րդ փուլին:

Փուլ 8. լուծող տարրի որոշում:

8.1. Բանաձեւի սյունակի սահմանում.

Գտնված հիմնական լուծումը ընդունելի է օբյեկտիվ ֆունկցիայի շարքում բացասական տարրերով սյունակները (բացառությամբ ազատ թվերի սյունակի). Աղյուսակ 5.5-ի համաձայն, կա միայն մեկ այդպիսի սյունակ. x1« Հետեւաբար, մենք ընդունում ենք այն, ինչպես թույլատրված է:

8.2. Միացման տողի սահմանում:

Աղյուսակ 5.6-ում դրական գնահատողական հարաբերությունների ստացված արժեքների համաձայն նվազագույնը «տողին համապատասխանող հարաբերությունն է. x3« Հետեւաբար, մենք ընդունում ենք այն, ինչպես թույլատրված է:

Աղյուսակ 5.6

Սիմպլեքս սեղանII կրկնություններ

Փուլ 9. սիմպլեքս աղյուսակի վերափոխում:

Սիմպլեքս աղյուսակի փոխակերպումները (Աղյուսակ 5.6) կատարվում են նույն կերպ, ինչ նախորդ կրկնության մեջ: Սիմպլեքս աղյուսակի տարրերի փոխակերպումների արդյունքները բերված են Աղյուսակ 5.7-ում:

III կրկնություն

Նախորդ կրկնության սիմպլեքս փոխակերպումների արդյունքների հիման վրա մենք կազմում ենք նոր սիմպլեքս աղյուսակ.

Աղյուսակ 5.7

Սիմպլեքս սեղանIII կրկնություններ

Փուլ 2. հիմնական լուծման որոշում:

Սիմպլեքս փոխակերպումների արդյունքում ստացվել է նոր հիմնական լուծում (Աղյուսակ 5.7).

Փուլ 3. սահմանափակումների համակարգի համատեղելիության ստուգում:

Աղյուսակ 5.7-ի 1-ին հատկանիշի համաձայն սահմանափակումների համակարգի անհամապատասխանությունը չի հայտնաբերվել:

Փուլ 4. օբյեկտիվ ֆունկցիայի սահմանների ստուգում:

Աղյուսակ 5.7-ի 2-րդ չափանիշի համաձայն օբյեկտիվ ֆունկցիայի անսահմանափակ լինելը չի ​​բացահայտվում:

Փուլ 5. հայտնաբերված հիմնական լուծման թույլատրելիության ստուգում:

Գտնված հիմնական լուծումը 3-րդ չափանիշին համապատասխան թույլատրելի է, քանի որ այն չի պարունակում բացասական բաղադրիչներ:

Փուլ 6. հայտնաբերված հիմնական լուծման օպտիմալության ստուգում:

Գտնված հիմնական լուծումը 4-րդ չափանիշին համապատասխան օպտիմալ չէ, քանի որ սիմպլեքս աղյուսակի օբյեկտիվ ֆունկցիայի գիծը (Աղյուսակ 5.7) պարունակում է բացասական տարր՝ –3 (այս տողի ազատ թիվը հաշվի չի առնվում դա դիտարկելիս։ բնորոշ): Այսպիսով, մենք անցնում ենք 8-րդ փուլին:

Փուլ 8. լուծող տարրի որոշում:

8.1. Բանաձեւի սյունակի սահմանում.

Գտնված հիմնական լուծումը ընդունելի է օբյեկտիվ ֆունկցիայի շարքում բացասական տարրերով սյունակները (բացառությամբ ազատ թվերի սյունակի). Աղյուսակ 5.7-ի համաձայն, կա միայն մեկ այդպիսի սյունակ. x5« Հետեւաբար, մենք ընդունում ենք այն, ինչպես թույլատրված է:

8.2. Միացման տողի սահմանում:

Աղյուսակ 5.8-ում դրական գնահատողական հարաբերությունների ստացված արժեքների համաձայն նվազագույնը «տողին համապատասխանող հարաբերությունն է. x4« Հետեւաբար, մենք ընդունում ենք այն, ինչպես թույլատրված է:

Աղյուսակ 5.8

Սիմպլեքս սեղանIII կրկնություններ

Փուլ 9. սիմպլեքս աղյուսակի վերափոխում:

Սիմպլեքս աղյուսակի փոխակերպումները (Աղյուսակ 5.8) կատարվում են նույն կերպ, ինչպես նախորդ կրկնության մեջ: Սիմպլեքս աղյուսակի տարրերի փոխակերպումների արդյունքները բերված են Աղյուսակ 5.9-ում:

IV կրկնություն

Փուլ 1. նոր սիմպլեքս աղյուսակի կառուցում:

Նախորդ կրկնության սիմպլեքս փոխակերպումների արդյունքների հիման վրա մենք կազմում ենք նոր սիմպլեքս աղյուսակ.

Աղյուսակ 5.9

Սիմպլեքս սեղանIV կրկնություններ

Փուլ 2. հիմնական լուծման որոշում:

Սիմպլեքս փոխակերպումների արդյունքում ստացվել է նոր հիմնական լուծում՝ համաձայն աղյուսակ 5.9-ի, լուծումը հետևյալն է.

Փուլ 3. սահմանափակումների համակարգի համատեղելիության ստուգում:

Աղյուսակ 5.9-ի 1-ին հատկանիշի համաձայն սահմանափակումների համակարգի անհամապատասխանությունը չի հայտնաբերվել:

Փուլ 4. օբյեկտիվ ֆունկցիայի սահմանների ստուգում:

Աղյուսակ 5.9-ի 2-րդ չափանիշի համաձայն օբյեկտիվ ֆունկցիայի անսահմանափակ լինելը բացահայտված չէ:

Փուլ 5. հայտնաբերված հիմնական լուծման թույլատրելիության ստուգում:

Գտնված հիմնական լուծումը 3-րդ չափանիշին համապատասխան թույլատրելի է, քանի որ այն չի պարունակում բացասական բաղադրիչներ:

Փուլ 6. հայտնաբերված հիմնական լուծման օպտիմալության ստուգում:

Գտնված հիմնական լուծումը ըստ հատկանիշի 4-ի օպտիմալ է, քանի որ սիմպլեքս աղյուսակի օբյեկտիվ ֆունկցիայի գծում բացասական տարրեր չկան (Աղյուսակ 5.9) (այս հատկանիշը դիտարկելիս այս տողի ազատ թիվը հաշվի չի առնվում) .

Փուլ 7. լուծման այլընտրանքայինության ստուգում:

Գտնված լուծումը եզակի է, քանի որ օբյեկտիվ ֆունկցիայի գծում զրո տարրեր չկան (Աղյուսակ 5.9) (այս տողի ազատ թիվը հաշվի չի առնվում այս բնութագիրը դիտարկելիս):

Պատասխան. օպտիմալ արժեքԴիտարկվող խնդրի օբյեկտիվ ֆունկցիան =24, որը ձեռք է բերվում ժամը.

Օրինակ 5.2.Լուծեք վերը նշված գծային ծրագրավորման խնդիրը, պայմանով, որ նպատակային ֆունկցիան նվազագույնի հասցվի.

Լուծում:

Ի կրկնություն:

Փուլ 1. նախնական սիմպլեքս աղյուսակի ձևավորում:

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

Ստացված հավասարումների համակարգում մենք ընդունում ենք որպես թույլատրելի (հիմնական) փոփոխականներ x3, x4, x5, x6, ապա ազատ փոփոխականները կլինեն x1,x2. Եկեք արտահայտենք հիմնական փոփոխականները ազատների տեսքով:

Համառոտ տեսություն

Գծային ծրագրավորման խնդիրները լուծելու համար առաջարկվել են բազմաթիվ տարբեր մեթոդներ: Այնուամենայնիվ, պարզվեց, որ սիմպլեքս մեթոդը ամենաարդյունավետն ու ունիվերսալն է դրանցից։ Պետք է նշել, որ որոշ խնդիրներ լուծելիս ավելի արդյունավետ կարող են լինել այլ մեթոդներ։ Օրինակ, երկու փոփոխական ունեցող ZLP-ի համար օպտիմալ մեթոդ է համարվում, իսկ լուծման համար օգտագործվում է պոտենցիալ մեթոդը: Սիմպլեքս մեթոդը հիմնական է և կիրառելի ցանկացած PPL-ի համար՝ կանոնական ձևով:

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

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

1. նախնական հղման պլան գտնելու ունակություն.
2. հղման պլանի օպտիմալության նշանի առկայությունը.
3. ոչ վատագույն հղման պլանի անցնելու ունակությունը:

Խնդրի լուծման օրինակ

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

Երեք խումբ ապրանքներ վաճառելու համար առևտրային ձեռնարկությունն ունի երեք տեսակի սահմանափակ նյութական և դրամական ռեսուրսներ , , , միավորների չափով։ Միաժամանակ 1 հազար ռուբլով ապրանքների 1 խմբի վաճառքի համար։ ապրանքաշրջանառությունը սպառում է առաջին տեսակի ռեսուրսը` միավորների քանակով, երկրորդ տեսակի ռեսուրսը` միավորների քանակով, երրորդ տեսակի ռեսուրսը` միավորների քանակով: 2 և 3 խմբերի ապրանքների վաճառք 1 հազար ռուբլով: ապրանքաշրջանառությունը ծախսվում է ըստ առաջին տեսակի ռեսուրսի՝ , միավորների, երկրորդ տեսակի ռեսուրսների՝ , միավորների, երրորդ տեսակի ռեսուրսների՝ , միավորների չափով: Երեք խմբի ապրանքների վաճառքից շահույթ 1 հազար ռուբլով: շրջանառությունը, համապատասխանաբար, հազար ռուբլի է:

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

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

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

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

Նշանակենք համապատասխանաբար 1-ին, 2-րդ և երրորդ տեսակի ապրանքների շրջանառությունը։

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

Նյութական և դրամական ռեսուրսների սահմանափակումները.

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

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

Կրճատում ZLP-ի կանոնական ձևին

Եկեք խնդիրը հասցնենք կանոնական ձևի։ Անհավասարությունները հավասարության վերածելու համար մենք ներկայացնում ենք լրացուցիչ փոփոխականներ: Փոփոխականները սահմանափակումների մեջ ընդգրկված են 1 գործակցով: Բոլոր լրացուցիչ փոփոխականները ներմուծում ենք օբյեկտիվ ֆունկցիա՝ զրոյի հավասար գործակցով:

Սահմանափակումն ունի նախընտրելի ձև, եթե աջ կողմը ոչ բացասական է ձախ կողմըունի փոփոխական, որը ներառված է մեկին հավասար գործակցով, իսկ մնացած հավասարության սահմանափակումները՝ զրոյի հավասար գործակցով: Մեր դեպքում 1-ին, 2-րդ, 3-րդ սահմանափակումներն ունեն նախընտրելի ձև՝ համապատասխան հիմնական փոփոխականներով։

Լուծում սիմպլեքս մեթոդով

Լրացնում ենք 0-րդ կրկնության սիմպլեքս աղյուսակը։

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

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

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

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

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

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

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

Մենք ստանում ենք 1-ին կրկնության աղյուսակը.

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

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

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

Վեկտորը բխում է հիմքից և ներմուծվում է վեկտորը:

Ստանում ենք 2-րդ կրկնության աղյուսակը.

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

Այսպիսով, անհրաժեշտ է վաճառել 7,1 հազար ռուբլի։ 1-ին տեսակի ապրանքներ և 45,2 հազար ռուբլի: 3-րդ տեսակի ապրանքներ. 2-րդ տեսակի ապրանք վաճառելը ձեռնտու չէ. Այս դեպքում շահույթը կլինի առավելագույնը և կկազմի 237,4 հազար ռուբլի: Օպտիմալ պլանի իրականացման դեպքում 3-րդ տիպի մնացած ռեսուրսը կկազմի 701 միավոր։

Կրկնակի LP խնդիր

Եկեք գրենք երկակի խնդրի մոդելը:

Երկակի խնդիր կառուցելու համար դուք պետք է օգտագործեք հետևյալ կանոնները.

1) եթե ուղղակի խնդիրը լուծվում է առավելագույնը, ապա երկակի խնդիրը լուծվում է նվազագույնի, և հակառակը.

2) առավելագույն խնդրի դեպքում անհավասարության սահմանափակումներն ունեն ≤ նշանակությունը, իսկ նվազագույնի հասցնելու հարցում՝ ≥;

3) ուղղակի խնդրի յուրաքանչյուր սահմանափակում համապատասխանում է երկակի խնդրի փոփոխականին, և հակառակը, երկակի խնդրի յուրաքանչյուր սահմանափակում համապատասխանում է ուղղակի խնդրի փոփոխականին.

4) երկակի խնդրի սահմանափակումների համակարգի մատրիցը ստացվում է սկզբնական խնդրի սահմանափակումների համակարգի մատրիցից՝ տրանսպոզիցիայով.

5) ուղղակի խնդրի սահմանափակումների համակարգի ազատ անդամները երկակի խնդրի օբյեկտիվ ֆունկցիայի համապատասխան փոփոխականների գործակիցներն են և հակառակը.

6) եթե ուղղակի խնդրի փոփոխականի վրա դրված է ոչ բացասական պայման, ապա երկակի խնդրի համապատասխան սահմանափակումը գրվում է որպես անհավասարության սահմանափակում, եթե ոչ, ապա որպես հավասարության սահմանափակում.

7) եթե ուղղակի խնդրի որևէ սահմանափակում գրված է որպես հավասարություն, ապա երկակի խնդրի համապատասխան փոփոխականի վրա չի դրվում ոչ բացասական պայման։

Մենք փոխադրում ենք սկզբնական խնդրի մատրիցը.

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

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

Բնօրինակի և երկակի խնդրի փոփոխականների համապատասխանությունը.

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

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

Տրանսպորտային խնդրի լուծում
Տրանսպորտի խնդիրը, դրա մաթեմատիկական մոդելը և լուծման մեթոդները մանրամասն դիտարկվում են՝ նվազագույն տարրի մեթոդով հղման պլանի հայտնաբերում և պոտենցիալ մեթոդով օպտիմալ լուծման որոնում:

Որոշումների կայացում անորոշության պայմաններում
Վիճակագրական մատրիցային խաղի լուծումը անորոշության պայմաններում դիտարկվում է օգտագործելով Wald, Savage, Hurwitz, Laplace և Bayes չափանիշները: Օգտագործելով խնդրի օրինակ, մանրամասն ցուցադրվում է վճարային մատրիցայի և ռիսկի մատրիցայի կառուցումը:

Անհրաժեշտ է լուծել գծային ծրագրավորման խնդիր։

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

2x 1 +5x 2 +3x 3 +8x 4 →ր

Սահմանափակման պայմանները.

3x 1 +6x 2 -4x 3 +x 4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x 1 +7x 2 +x 3 ≥1

Սահմանափակումների համակարգը բերենք կանոնական ձևի, դրա համար անհրաժեշտ է անհավասարություններից անցում կատարել դեպի հավասարումներ՝ հավելյալ փոփոխականների ավելացմամբ։

Քանի որ մեր խնդիրը նվազագույնի հասցնելու խնդիր է, մենք պետք է այն վերածենք առավելագույն որոնման խնդրի: Դրա համար մենք փոխում ենք օբյեկտիվ ֆունկցիայի գործակիցների նշանները հակառակի: Առաջին անհավասարության տարրերը գրում ենք անփոփոխ՝ ավելացնելով հավելյալ x 5 փոփոխական և «≤» նշանը փոխելով «=»-ի։ Քանի որ երկրորդ և երրորդ անհավասարություններն ունեն «≥» նշաններ, անհրաժեշտ է հակադարձել դրանց գործակիցների նշանները և դրանց մեջ ներմուծել համապատասխանաբար x 6 և x 7 լրացուցիչ փոփոխականներ: Արդյունքում մենք ստանում ենք համարժեք խնդիր.

3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1

Մենք անցնում ենք նախնական սիմպլեքս աղյուսակի ձևավորմանը: Աղյուսակի F տողը պարունակում է օբյեկտիվ ֆունկցիայի գործակիցները հակառակ նշան.

Քանի որ ազատ տերմինների սյունակում բացասական տարրեր չկան, թույլատրելի լուծում է գտնվել F տողը պարունակում է բացասական տարրեր, ինչը նշանակում է, որ ստացված լուծումը օպտիմալ չէ: Եկեք սահմանենք առաջատար սյունակը: Դա անելու համար մենք F տողում կգտնենք առավելագույն մոդուլով բացասական տարրը - սա -1.988 Առաջատար շարքը կլինի այն, որի համար ազատ անդամի և առաջատար սյունակի համապատասխան տարրի հարաբերակցությունը նվազագույն է: Առաջատար շարքը X2 է, իսկ առաջատար տարրը` 0,313:

Քանի որ F տողում բացասական տարրեր չկան, մենք գտանք օպտիմալ լուծում. Քանի որ սկզբնական խնդիրը նվազագույնը գտնելն էր, օպտիմալ լուծումը կլինի F տողի ազատ տերմինը՝ վերցված հակառակ նշանով։ F=1.924
փոփոխական արժեքներով հավասար՝ x 3 = 0,539, x 1 = 0,153: x 2 և x 4 փոփոխականները ներառված չեն հիմքում, ուստի x 2 =0 x 4 =0:

Ահա երկու խնդիրների մեխանիկական (ոչ ապլետի) լուծում՝ օգտագործելով սիմպլեքս մեթոդը (նման է ապլետի լուծմանը) մանրամասն բացատրություններով, որպեսզի հասկանանք սիմպլեքս մեթոդով խնդիրների լուծման ալգորիթմը: Առաջին խնդիրը պարունակում է անհավասարության նշաններ միայն «≤» (խնդիր սկզբնական հիմքով), երկրորդը կարող է պարունակել «≥», «≤» կամ «=» (արհեստական ​​հիմքով խնդիր), դրանք լուծվում են այլ կերպ։

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

1)Սիմպլեքս մեթոդսկզբնական հիմքով խնդրի համար (անհավասարության սահմանափակումների բոլոր նշանները «≤»):

Եկեք գրենք խնդիրը կանոնականձևը, այսինքն. անհավասարության սահմանափակումները վերաշարադրում ենք հավասարումների տեսքով՝ ավելացնելով հաշվեկշիռըփոփոխականներ:

Այս համակարգը հիմք ունեցող համակարգ է (հիմք՝ s 1, s 2, s 3, դրանցից յուրաքանչյուրը ներառված է համակարգի միայն մեկ հավասարման մեջ՝ 1 գործակցով), x 1 և x 2 ազատ փոփոխականներ են։ Սիմպլեքս մեթոդով լուծվող խնդիրները պետք է ունենան հետևյալ երկու հատկությունները. - սահմանափակումների համակարգը պետք է լինի հիմք ունեցող հավասարումների համակարգ. - Համակարգի բոլոր հավասարումների ազատ անդամները պետք է լինեն ոչ բացասական:

Ստացված համակարգը հիմքով համակարգ է և դրա անվճար պայմանները ոչ բացասական են, ուստի կարող ենք դիմել սիմպլեքս մեթոդ. Եկեք ստեղծենք առաջին սիմպլեքս աղյուսակը (Iteration 0) խնդիրը լուծելու համար սիմպլեքս մեթոդ, այսինքն. նպատակային ֆունկցիայի գործակիցների աղյուսակ և համապատասխան փոփոխականների հավասարումների համակարգ։ Այստեղ «BP» նշանակում է հիմնական փոփոխականների սյունակ, «Լուծում» նշանակում է համակարգի հավասարումների աջ կողմի սյունակ: Լուծումը օպտիմալ չէ, քանի որ z տողում կան բացասական գործակիցներ:

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

Լուծումը բարելավելու համար եկեք անցնենք հաջորդ կրկնությանը սիմպլեքս մեթոդ, ստանում ենք հետևյալ սիմպլեքս աղյուսակը. Դա անելու համար անհրաժեշտ է ընտրել միացնել սյունակը, այսինքն. փոփոխական, որը կներառվի հիմքում սիմպլեքս մեթոդի հաջորդ կրկնության ժամանակ: Այն ընտրվում է z-շարքում ամենամեծ բացարձակ բացասական գործակցով (առավելագույն խնդրի դեպքում) - simplex մեթոդի սկզբնական կրկնության մեջ սա սյունակ է x 2 (գործակից -6):

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

Թույլատրելի տարրգտնվում է լուծվող սյունակի և լուծվող տողի հատման կետում, նրա բջիջը ընդգծված է գույնով, այն հավասար է 1-ի: Հետևաբար, սիմպլեքս մեթոդի հաջորդ կրկնության ժամանակ x 2 փոփոխականը կփոխարինի s 1-ին հիմքում: Նկատի ունեցեք, որ կապը չի որոնվում z տողում, այնտեղ դրված է «-» գծիկ: Եթե ​​կան միանման նվազագույն հարաբերություններ, ապա ընտրվում է դրանցից որևէ մեկը։ Եթե ​​լուծման սյունակում բոլոր գործակիցները փոքր են կամ հավասար են 0-ին, ապա խնդրի լուծումն անսահման է:

Լրացնենք հետևյալ աղյուսակը «Իտերացիա 1». Մենք այն կստանանք «Iteration 0» աղյուսակից: Հետագա փոխակերպումների նպատակն է x2 լուծման սյունակը վերածել միավորի սյունակի (լուծման տարրի փոխարեն մեկ և մնացած տարրերի փոխարեն զրոներ):

1) Հաշվեք «Iteration 1» աղյուսակի x 2 տողը: Նախ, «Iteration 0» աղյուսակի լուծվող s 3 տողի բոլոր անդամներին բաժանում ենք այս աղյուսակի լուծվող տարրի վրա (այս դեպքում այն ​​հավասար է 1-ի), «Iteration 1» աղյուսակում ստանում ենք x 2 տող։ . Որովհետև լուծող տարրը այս դեպքում հավասար է 1-ի, ապա «Iteration 0» աղյուսակի s 3 տողը կհամընկնի «Iteration 1» աղյուսակի x 2 տողի հետ: «Iteration 1» աղյուսակի x 2 տողը ստացանք 0 1 0 0 1 20, «Iteration 1» աղյուսակի մնացած տողերը կստացվեն այս տողից, իսկ «Iteration 0» աղյուսակի տողերը՝ հետևյալ կերպ.

2) «Iteration 1» աղյուսակի z տողի հաշվարկը. Iteration 0 աղյուսակի x2 սյունակի առաջին շարքում (z-տող) -6-ի փոխարեն, Iteration 1 աղյուսակի առաջին տողում պետք է լինի 0: Դա անելու համար «Iteration 1» աղյուսակի x 2 տողի բոլոր տարրերը բազմապատկեք 0 1 0 0 1 20 6-ով, ստացեք 0 6 0 0 6 120 և ավելացրեք այս տողը առաջին տողով (z - տող): աղյուսակ «Iteration 0» -4 -6 0 0 0 0, ստանում ենք -4 0 0 0 6 120. x 2 սյունակում հայտնվում է զրո 0, նպատակը ձեռք է բերվում: Որոշման x 2 սյունակի տարրերը ընդգծված են կարմիրով:

3) «Iteration 1» աղյուսակի s 1 տողի հաշվարկը. «Iteration 0» աղյուսակի 1-ի s 1 տողի փոխարեն «Iteration 1» աղյուսակում պետք է լինի 0: Դա անելու համար «Iteration 1» աղյուսակի x 2 տողի բոլոր տարրերը 0 1 0 0 1 20 բազմապատկեք -1-ով, ստացեք 0 -1 0 0 -1 -20 և ավելացրեք այս տողը s 1 - տողի հետ: Աղյուսակ «Iteration 0» 2 1 1 0 0 64, մենք ստանում ենք տողը 2 0 1 0 -1 44. x 2 սյունակում մենք ստանում ենք պահանջվող 0:

4) Հաշվե՛ք «Iteration 1» աղյուսակի s 2 տողը: «Iteration 0» աղյուսակի s 2 տողի 3-րդ տեղում «Iteration 1» աղյուսակում պետք է լինի 0: Դա անելու համար «Iteration 1» աղյուսակի x 2 տողի բոլոր տարրերը 0 1 0 0 1 20 բազմապատկեք -3-ով, ստացեք 0 -3 0 0 -3 -60 և ավելացրեք այս տողը աղյուսակի s 1 - տողով: «Iteration 0» 1 3 0 1 0 72, ստանում ենք 1 0 0 1 -3 12 տողը: x 2 սյունակում ստացվում է «Iteration 1» աղյուսակի x 2 սյունակը միավոր , այն պարունակում է մեկ 1, իսկ մնացածը՝ 0։

«Iteration 1» աղյուսակի տողերը ստացվում են հետևյալ կանոնի համաձայն.

Նոր տող = Հին տող – (Հին տողի լուծման սյունակի գործակից)*(Նոր լուծման տող):

Օրինակ, z-string-ի համար մենք ունենք.

Հին z-string (-4 -6 0 0 0 0) -(-6)*Նոր լուծվող տող -(0 -6 0 0 -6 -120) =Նոր z-string (-4 0 0 0 6 120):

Հետևյալ աղյուսակների համար աղյուսակի տարրերի վերահաշվարկը կատարվում է նույն կերպ, ուստի մենք այն բաց ենք թողնում:

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

x 1 սյունակը լուծելը, s 2, s 2 տողերը լուծելը թողնում է հիմքը, x 1-ը մտնում է հիմք: Ճիշտ նույն կերպ մենք ստանում ենք մնացած սիմպլեքս աղյուսակները, մինչև ստանանք աղյուսակ՝ z տողում գտնվող բոլոր դրական գործակիցներով: Սա օպտիմալ սեղանի նշան է:

սիմպլեքս մեթոդի կրկնություն 2

Ս 3 սյունակը լուծելը, s 1, s 1 տողերը լուծելը թողնում է հիմքը, s 3-ը մտնում է հիմք:

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

Z տողում բոլոր գործակիցները ոչ բացասական են, հետևաբար, ստացվում է x 1 = 24, x 2 = 16, z max = 192 օպտիմալ լուծում:

11.4. DUAL SIMPLEX ՄԵԹՈԴ

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

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

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

Դիտարկելով այս պայմանը՝ հաշվի առնելով երկակիությունը, կարող ենք գրել

.

Այսպիսով, եթե, Դա . Սա նշանակում է, որ երբ ուղղակի խնդրի լուծումը ոչ օպտիմալ է, ապա երկակի խնդրի լուծումն իրագործելի չէ։ Մյուս կողմից ժամը . Դրանից բխում է, որ ուղղակի խնդրի օպտիմալ լուծումը համապատասխանում է երկակի խնդրի թույլատրելի լուծմանը։

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

Dual simplex մեթոդը հնարավորություն է տալիս լուծել գծային ծրագրավորման խնդիրներ, որոնց սահմանափակման համակարգերը դրական հիմքով պարունակում են ցանկացած նշանի ազատ պայմաններ։ Այս մեթոդը թույլ է տալիս նվազեցնել սահմանափակումների համակարգի փոխակերպումների քանակը, ինչպես նաև սիմպլեքս աղյուսակի չափը: Դիտարկենք կրկնակի սիմպլեքս մեթոդի կիրառումը օրինակով։

Օրինակ. Գտեք ֆունկցիայի նվազագույնը

սահմանափակումների տակ

.

Անցնենք կանոնական ձևին.

սահմանափակումների տակ

Սկզբնական սիմպլեքս աղյուսակն ունի ձև

Սկզբնական հիմքի լուծումօպտիմալ, բայց ոչ ընդունելի:

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

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

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

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

Այս օրինակում բացառված փոփոխականն է. Նոր բազային փոփոխականը որոշելու համար հաշվարկված գործակիցները տրված են հետևյալ աղյուսակում.

Ներառված փոփոխականն ընտրված է x 2. Տողերի հետագա փոխարկումը հանգեցնում է նոր սիմպլեքս աղյուսակի.

Նոր լուծում նույնպես օպտիմալ, բայց դեռ անընդունելի։ Որպես նոր բացառված փոփոխական մենք ընտրում ենք (կամայականորեն) x 3. Եկեք սահմանենք ներառվող փոփոխականը։