Dualizmi tesutyun ev velucutyunner / Դուալիզմի տեսություն և վերլուծություններ

Dualizmi tesutyun ev velucutyunner / Դուալիզմի տեսություն և վերլուծություններ :
Նյութը `

Դուալիզմի տեսությունը համարվում է ամենակարևոր հայտնագործություններից մեկը: Այս հայտնագործությունը վերաբերվում է ուղղագծային ծրագրավորման կապին այլ ուղղագծային ծրագրավորման հետ, որը կոչվում է դուալիզմ: Հիմնական խնդրի և դուալ խնդրի տարբերությունը ապացուցում է, նրանց չափազանց կարևորությունը այն մասին, որ սրանք օգնում են գտնել խնդրի օպտիմալ լուծումը, այն հնարավորություն է տալիս գտնել խնդրի միանգամից մի քանի ճանապարհով լուծումը:
Ստորև դուք ինքներդ կհամոզվեք դրա կարևորության մեջ : Դուալիզմի տեսությունը հիմնված է զգայուն (ճշգրիտ) վերլուծության կիրառման վրա: Զգայուն վերլուծությունը շատ կարևոր է գրեթե բոլոր ուղղագծային ծրագրավորումների համար համար: Որովհետև չափանիշների արժեքը, օգտագործված հիմնական մոդելում արտացոլում է լուծման եղանակները: Զգայուն վերլուծության միջոցով կարելի է ընտրել չափանիշների արժեքը, որոնք կօգնեն գտնել խնդրի օպտիմալ լուծումը:
Պարզեցման համար ստորև գրված երեք գլուխները քննարկում են դուալիզմի տեսությունը` ենթադրելով, որ հիմնական ուղղագծային ծրագրավորման խնդիրը մեր ստանդարտ ձևում է, այսինքն bi –ի արժեքները պետք է հավասար լինեն:
Առաջին գլուխը սկսում է ներկայացնել դուալիզմի էությունը
Այնուհետև նկարագրում ենք դուալ խնդրի տնտեսական ինտերպրիտացիան և խորապես ուսումնասիրում ենք դուալ և հիմնական խնդիրների միջև ընկած հարաբերությունները: Մեկ այլ գլխում կծանոթանաք դուալիզմի տեսության դերը զգայուն վերլուծություններում աղյուսակի հետ:

Փոփոխական վերլուծություն

Երբ ֆունդամենտալ հասկացությունը կիրառված է b2 վերջնական սիմպլեքսային աղյուսակում փոխված է, ապա դրա արդյունավետությունը կայանում է նրանում, որ աջ սյունակի ցուցանիշները փոխվում են հետևյալ արժեքների`
Z* =y*b=[0, 3/2,1] [█(4@24@18)]=54 x3x2x1

b* = S*b ̅= [■(1&1/3&-1/3@0&1/2&0@0&-□(1/3)&1/3)] [█(4@24@18)]= [█(6@12@-2)], այսպիսով [█(x3@x2@x1)]=[█(6@12@-2)]

Համապատասխանաբար քանի, որ հիմնական մոդելում միակ փոփոխությունը սա է`
∆b2 = 24 – 12 = 12,
Ինկրեմենտալ (մեծացման) վերլուծությունը կարող է օգտագործվել, որպեսզի այս արժեքներն ավելի արագ հաշվվեն: Ինկրեմենտալ վերլուծությունները ներգրավում են, այն ինկրեմենտալ հաշվարկները, որոնք բխում են հիմնական մոդելի փոփոխությունից կամ փոփոխություններից, որոնք առկա են հիմնական մոդելում և այնուհետև ավելացնում են այդ ինկրեմենտները հիմնական արժեքին:
Այս դեպքում ինկրեմենտները Z* և b*-ում հետևյլան են :

∆Z* = y*∆b =y* [█(∆b1@∆b2@∆b3)] =y*[█(0@12@0)]

∆b* =S*∆b =S* [█(∆b1@∆b2@∆b3)]=S*[█(0@12@0)]

Այդ պատճառով օգտագործելով y* -ի երկրորդ բաղադրիչը և S* երկրորդ սյունյակը տեսնում ենք, որ միակ հասանելի հաշվարկները սրանք են`

∆Z*=3/2 (12)=18, այսպիսով`Z* = 36 + 18 = 54,

∆b_1*=1/3 (12)=4, այսպիսով`〖 b〗_1* = 2 + 4 = 6

∆b_2*=1/2 (12)=6, 〖այսպիսով` b〗_2* = 6+6=12

∆b_3*=-1/3 (12)=-4, այսպիսով` b_3* = 2-4 = -2

Վերջնական աղյուսակի արդյունքը համապատասխանում է սկզբանական հիմնական աղյուսյակի թվերին, բացի աջ կողմիս սյունյակից: Այդ պատճառով հիմնական լուծումը դառնում է ` (x1, x2, x3, x4, x5) = (-2, 12, 6, 0, 0), որը խնդիրը լուծելի է դարձնում ի հաշիվ իր բացսական արժեքի:
Հիմա կարող է կիրառվել դուալ սիմպլեքսային մեթոդը, որպեսզի գտնվի նոր օպտիմալ լուծում: Այս մեթոդը տանում է դեպի նոր վերջնական սիմպլեքսային աղյուսյակի: Այս աղյուսյակը նշում է , որ նոր օպտիմալ լուծումն է` (x1, x2, x3, x4, x5) = (0, 9, 4, 6, 0), Z = 45-ով:
b2 =12 + բանաձևը չափազանց մեծ է, որպեսզի հիմնական խնդիրը լուծելի մնա, որտեղ հիմնական փոփոխականներն են` x1, x2 և x3 վերը նշված մեծացված վերլուծությունները ցույց են տալիս որքանով է խնդիրը լուծելի, հիշեք որ

b1* =2 + 1/3 ∆ b2
b2* = 6 + 1/2 ∆ b2
b3* = 2- 1/3 ∆ b2

այս երեք քանակականները x1, x2 և x3 -ի արժեքներն են, որոնք համարվում են հիմնական խնդրի լուծման եղանակներ: Խնդիրը լուծելի և օպտիմալ է այնքան ժամանակ, որքան այս երեք քանակականները բացսական են:

2+ 1/3 ∆ b2 ≥ 0□( ⇒┬ ) 1/(3 ) ∆ b2 ≥ -2 □( ⇒┬ ) ∆ b2 ≥ 6
6+ 1/2 ∆ b2 ≥ 0□( ⇒┬ ) 1/(2 ) ∆ b2 ≥ -6 □( ⇒┬ ) ∆ b2 ≥ -12
2 – 1/3 ∆ b2 ≥ 0□( ⇒┬ 2≥) 1/(3 ) ∆ b2 ≥ ∆ b2 ≤ 6

Այդ պատճառով մինչ b2 =12 +∆ b2 խնդիրը լուծելի է, եթե միայն
-6 ≤ ∆ b2 ≤ 6 դա է 6 ≤ b2 ≤18

Յուրաքանչյուր bi –ի համր լուծելի հորիզոն է հանդիսանում օպտիմալ BF լուծումը (հիմանական փոփոխականների համար ուղղված արժեքներով), հիմնական փոփոխականների ուղղված արժեքները ստանում ենք b*=S*b բանաձևով: Թույլատրելի հորիզոնականի հաշվարկը լուծելի է, եթե bi -ի արժեքը, որն է b* ≥ 0, երբ bi –ի արժեքը կամ արժեքները փոխված են, ապա b*=S*b բանաձևը կրկին կօգտագործվի տեսնելու աջ սյունյակի ցուցանիշների փոփոխությունը աղյուսակում, եթե դրանք դրական են, ապա խնդիրը դեռ լուծելի է: Մինչ 0 շարքն անփոփոխ է խնդրի լուծումը օպտիմալ է:
Չնայած այս մոտեցումը օպտիմալ է bi փոփոխման արդյունքները ստուգելու համար, սակայն այն հնրարավորություն չի տալիս ստուգել թե, որքան կարող ենք bi –ի արժեքը փոխել իր հիմնական արժեքից:

Windor մոդելի փոփոխություն
Որպեսզի նկարագրենք այս կանոնը եկեք տեսնենք օրինակ, որտեղ ցուցադրվում է աջ կողմի վեկտորի փոփոխությունը

b = [█(4@12@18)]→ b ̅ = [█(4@15@15)]

Հետևելով այս կանոնին հաշվարկներն են
b2 :12 → 15 հնարավորությունը մեծանում է մինչև 100% 100 ( (5-12)/6)=50%
b2 :18 → 15 հնարավորությունը մեծանում է մինչև 100% 100 ( (18-15))/6)=50%

մեկ այլ օրինակ, որտեղ կտեսնենք Z* մեծացումը
Z=1.5 (3)+1(-3)=1.5 այսպիսով Z* կմեծանա 36-ից մինչև 37.5 այս դեպքում օպտիմալ լուծումը SPF լուծումն է, որը տալիս է` Z=3×1+5×2=0+5(7.5)=37.5
Նշեք թե ինչ կլիներ, եթե b2 –ը 15-ից մեծացված լիներ, իսկ b3-ը 15-ից փոքր, այսպիսով այս դեպքում մենք կհամոզվեյինք, որ խնդիրն անլուծելի է:
Համապատասխանաբար հին արժեքը Z* համար իրական չէր լինի:

Ոչ հիմնական փոփոխականների ցուցանիշների փոփոխում (դեպք 2ա)

Xj փոփոխականը, սիմպլեքսային աղյուսակով ոչ հիմնականփոփոխական է: 2ա դեպքում միակ փոփոխությունը այս մոդելում այն է, որ փոխվել են ցուցանիշներից մեկը կամ ավելին (ցուցանիշներն են cj a1j a2j…., amj) : Այսպիսով թույլ տանք cj aij –ին ցուցադրել նոր արժեքները Aj հետ որպես վեկտոր, որը պարունակում է aij կունենանք այս մոդելը cj cj , Aj Aj
Ինչպես արդեն նշել ենք դուալիզմի տեսությունը չափազանց հարմար ճանապարհ է ստուգելու այս փոփոխությունները:
Եթե դուալ խնդրում լրացուցիչ լուծում y*-ը դեռ բավարարում է մեկ դուալ սահմանափակմանը, որը փոխվել է, ապա լուծումը հիմանական խնդրում մնում է օպտիմալ: Մյուս դեպքում, եթե y* -ը խախտում է դուալ սահմանափակումն, ապա լուծումն այլևս օպտիմալ չէ:
Եթե օպտիմալ լուծումը փոխվել է և ցանկանում եք մեկ այլ նորը գտնել, կարող եք հեշտությամբ դա անել, միայն կիրառեք ֆունդամենտալ հասկացությունը և xj սյունյակը (միակ սյունյակը, որը կարելի է փոփոխել), վերջնական սիմպլեքսային աղյուսակում:
օր.` xj ցուցանիշը վերջին 0 շարքում xj*-cj=y* Aj-cj1
xj ցուցանիշը վերջին 1 շարքում Aj*=S* Aj

Ընթացիկ հիմանկան լուծումով, որն արդեն օպտիմալ չէ, նոր xj-cj արժեքը 0 շարքում կլինի մեկ բացսական ցուցանիշ, այսպիսով վերսկսեք սիմպլեքսային մեթոդը xj –ով որպես հիմնական փոփոխական:
ԴՈՒԱԼԻԶՄԻ ՏԵՍՈՒԹՅՈՒՆ ԵՎ ՎԵՐԼՈՒԾՈՒԹՅՈՒՆՆԵՐ

Դուալիզմի տեսությունը համարվում է ամենակարևոր հայտնագործություններից մեկը: Այս հայտնագործությունը վերաբերվում է ուղղագծային ծրագրավորման կապին այլ ուղղագծային ծրագրավորման հետ, որը կոչվում է դուալիզմ: Հիմնական խնդրի և դուալ խնդրի տարբերությունը ապացուցում է, նրանց չափազանց կարևորությունը այն մասին, որ սրանք օգնում են գտնել խնդրի օպտիմալ լուծումը, այն հնարավորություն է տալիս գտնել խնդրի միանգամից մի քանի ճանապարհով լուծումը:
Ստորև դուք ինքներդ կհամոզվեք դրա կարևորության մեջ : Դուալիզմի տեսությունը հիմնված է զգայուն (ճշգրիտ) վերլուծության կիրառման վրա: Զգայուն վերլուծությունը շատ կարևոր է գրեթե բոլոր ուղղագծային ծրագրավորումների համար համար: Որովհետև չափանիշների արժեքը, օգտագործված հիմնական մոդելում արտացոլում է լուծման եղանակները: Զգայուն վերլուծության միջոցով կարելի է ընտրել չափանիշների արժեքը, որոնք կօգնեն գտնել խնդրի օպտիմալ լուծումը:
Պարզեցման համար ստորև գրված երեք գլուխները քննարկում են դուալիզմի տեսությունը` ենթադրելով, որ հիմնական ուղղագծային ծրագրավորման խնդիրը մեր ստանդարտ ձևում է, այսինքն bi –ի արժեքները պետք է հավասար լինեն:
Առաջին գլուխը սկսում է ներկայացնել դուալիզմի էությունը
Այնուհետև նկարագրում ենք դուալ խնդրի տնտեսական ինտերպրիտացիան և խորապես ուսումնասիրում ենք դուալ և հիմնական խնդիրների միջև ընկած հարաբերությունները: Մեկ այլ գլխում կծանոթանաք դուալիզմի տեսության դերը զգայուն վերլուծություններում աղյուսակի հետ:

Փոփոխական վերլուծություն

Երբ ֆունդամենտալ հասկացությունը կիրառված է b2 վերջնական սիմպլեքսային աղյուսակում փոխված է, ապա դրա արդյունավետությունը կայանում է նրանում, որ աջ սյունակի ցուցանիշները փոխվում են հետևյալ արժեքների`
Z* =y*b=[0, 3/2,1] [█(4@24@18)]=54 x3x2x1

b* = S*b ̅= [■(1&1/3&-1/3@0&1/2&0@0&-□(1/3)&1/3)] [█(4@24@18)]= [█(6@12@-2)], այսպիսով [█(x3@x2@x1)]=[█(6@12@-2)]

Համապատասխանաբար քանի, որ հիմնական մոդելում միակ փոփոխությունը սա է`
∆b2 = 24 – 12 = 12,
Ինկրեմենտալ (մեծացման) վերլուծությունը կարող է օգտագործվել, որպեսզի այս արժեքներն ավելի արագ հաշվվեն: Ինկրեմենտալ վերլուծությունները ներգրավում են, այն ինկրեմենտալ հաշվարկները, որոնք բխում են հիմնական մոդելի փոփոխությունից կամ փոփոխություններից, որոնք առկա են հիմնական մոդելում և այնուհետև ավելացնում են այդ ինկրեմենտները հիմնական արժեքին:
Այս դեպքում ինկրեմենտները Z* և b*-ում հետևյլան են :

∆Z* = y*∆b =y* [█(∆b1@∆b2@∆b3)] =y*[█(0@12@0)]

∆b* =S*∆b =S* [█(∆b1@∆b2@∆b3)]=S*[█(0@12@0)]

Այդ պատճառով օգտագործելով y* -ի երկրորդ բաղադրիչը և S* երկրորդ սյունյակը տեսնում ենք, որ միակ հասանելի հաշվարկները սրանք են`

∆Z*=3/2 (12)=18, այսպիսով`Z* = 36 + 18 = 54,

∆b_1*=1/3 (12)=4, այսպիսով`〖 b〗_1* = 2 + 4 = 6

∆b_2*=1/2 (12)=6, 〖այսպիսով` b〗_2* = 6+6=12

∆b_3*=-1/3 (12)=-4, այսպիսով` b_3* = 2-4 = -2

Վերջնական աղյուսակի արդյունքը համապատասխանում է սկզբանական հիմնական աղյուսյակի թվերին, բացի աջ կողմիս սյունյակից: Այդ պատճառով հիմնական լուծումը դառնում է ` (x1, x2, x3, x4, x5) = (-2, 12, 6, 0, 0), որը խնդիրը լուծելի է դարձնում ի հաշիվ իր բացսական արժեքի:
Հիմա կարող է կիրառվել դուալ սիմպլեքսային մեթոդը, որպեսզի գտնվի նոր օպտիմալ լուծում: Այս մեթոդը տանում է դեպի նոր վերջնական սիմպլեքսային աղյուսյակի: Այս աղյուսյակը նշում է , որ նոր օպտիմալ լուծումն է` (x1, x2, x3, x4, x5) = (0, 9, 4, 6, 0), Z = 45-ով:
b2 =12 + բանաձևը չափազանց մեծ է, որպեսզի հիմնական խնդիրը լուծելի մնա, որտեղ հիմնական փոփոխականներն են` x1, x2 և x3 վերը նշված մեծացված վերլուծությունները ցույց են տալիս որքանով է խնդիրը լուծելի, հիշեք որ

b1* =2 + 1/3 ∆ b2
b2* = 6 + 1/2 ∆ b2
b3* = 2- 1/3 ∆ b2

այս երեք քանակականները x1, x2 և x3 -ի արժեքներն են, որոնք համարվում են հիմնական խնդրի լուծման եղանակներ: Խնդիրը լուծելի և օպտիմալ է այնքան ժամանակ, որքան այս երեք քանակականները բացսական են:

2+ 1/3 ∆ b2 ≥ 0□( ⇒┬ ) 1/(3 ) ∆ b2 ≥ -2 □( ⇒┬ ) ∆ b2 ≥ 6
6+ 1/2 ∆ b2 ≥ 0□( ⇒┬ ) 1/(2 ) ∆ b2 ≥ -6 □( ⇒┬ ) ∆ b2 ≥ -12
2 – 1/3 ∆ b2 ≥ 0□( ⇒┬ 2≥) 1/(3 ) ∆ b2 ≥ ∆ b2 ≤ 6

Այդ պատճառով մինչ b2 =12 +∆ b2 խնդիրը լուծելի է, եթե միայն
-6 ≤ ∆ b2 ≤ 6 դա է 6 ≤ b2 ≤18

Յուրաքանչյուր bi –ի համր լուծելի հորիզոն է հանդիսանում օպտիմալ BF լուծումը (հիմանական փոփոխականների համար ուղղված արժեքներով), հիմնական փոփոխականների ուղղված արժեքները ստանում ենք b*=S*b բանաձևով: Թույլատրելի հորիզոնականի հաշվարկը լուծելի է, եթե bi -ի արժեքը, որն է b* ≥ 0, երբ bi –ի արժեքը կամ արժեքները փոխված են, ապա b*=S*b բանաձևը կրկին կօգտագործվի տեսնելու աջ սյունյակի ցուցանիշների փոփոխությունը աղյուսակում, եթե դրանք դրական են, ապա խնդիրը դեռ լուծելի է: Մինչ 0 շարքն անփոփոխ է խնդրի լուծումը օպտիմալ է:
Չնայած այս մոտեցումը օպտիմալ է bi փոփոխման արդյունքները ստուգելու համար, սակայն այն հնրարավորություն չի տալիս ստուգել թե, որքան կարող ենք bi –ի արժեքը փոխել իր հիմնական արժեքից:

Windor մոդելի փոփոխություն
Որպեսզի նկարագրենք այս կանոնը եկեք տեսնենք օրինակ, որտեղ ցուցադրվում է աջ կողմի վեկտորի փոփոխությունը

b = [█(4@12@18)]→ b ̅ = [█(4@15@15)]

Հետևելով այս կանոնին հաշվարկներն են
b2 :12 → 15 հնարավորությունը մեծանում է մինչև 100% 100 ( (5-12)/6)=50%
b2 :18 → 15 հնարավորությունը մեծանում է մինչև 100% 100 ( (18-15))/6)=50%

մեկ այլ օրինակ, որտեղ կտեսնենք Z* մեծացումը
Z=1.5 (3)+1(-3)=1.5 այսպիսով Z* կմեծանա 36-ից մինչև 37.5 այս դեպքում օպտիմալ լուծումը SPF լուծումն է, որը տալիս է` Z=3×1+5×2=0+5(7.5)=37.5
Նշեք թե ինչ կլիներ, եթե b2 –ը 15-ից մեծացված լիներ, իսկ b3-ը 15-ից փոքր, այսպիսով այս դեպքում մենք կհամոզվեյինք, որ խնդիրն անլուծելի է:
Համապատասխանաբար հին արժեքը Z* համար իրական չէր լինի:

Ոչ հիմնական փոփոխականների ցուցանիշների փոփոխում (դեպք 2ա)

Xj փոփոխականը, սիմպլեքսային աղյուսակով ոչ հիմնականփոփոխական է: 2ա դեպքում միակ փոփոխությունը այս մոդելում այն է, որ փոխվել են ցուցանիշներից մեկը կամ ավելին (ցուցանիշներն են cj a1j a2j…., amj) : Այսպիսով թույլ տանք cj aij –ին ցուցադրել նոր արժեքները Aj հետ որպես վեկտոր, որը պարունակում է aij կունենանք այս մոդելը cj cj , Aj Aj
Ինչպես արդեն նշել ենք դուալիզմի տեսությունը չափազանց հարմար ճանապարհ է ստուգելու այս փոփոխությունները:
Եթե դուալ խնդրում լրացուցիչ լուծում y*-ը դեռ բավարարում է մեկ դուալ սահմանափակմանը, որը փոխվել է, ապա լուծումը հիմանական խնդրում մնում է օպտիմալ: Մյուս դեպքում, եթե y* -ը խախտում է դուալ սահմանափակումն, ապա լուծումն այլևս օպտիմալ չէ:
Եթե օպտիմալ լուծումը փոխվել է և ցանկանում եք մեկ այլ նորը գտնել, կարող եք հեշտությամբ դա անել, միայն կիրառեք ֆունդամենտալ հասկացությունը և xj սյունյակը (միակ սյունյակը, որը կարելի է փոփոխել), վերջնական սիմպլեքսային աղյուսակում:
օր.` xj ցուցանիշը վերջին 0 շարքում xj*-cj=y* Aj-cj1
xj ցուցանիշը վերջին 1 շարքում Aj*=S* Aj

Ընթացիկ հիմանկան լուծումով, որն արդեն օպտիմալ չէ, նոր xj-cj արժեքը 0 շարքում կլինի մեկ բացսական ցուցանիշ, այսպիսով վերսկսեք սիմպլեքսային մեթոդը xj –ով որպես հիմնական փոփոխական:

Leave a Reply