Linijinio programavimo problemų dvilypumas
Linijinio programavimo problemų dvilypumas!
Kiekvienai linijinei programavimo problemai yra atitinkama unikali problema, susijusi su tais pačiais duomenimis, taip pat aprašoma pradinė problema. Pradinė problema vadinama pirminė programa ir atitinkama unikali problema vadinama Dual programa. Abi programos yra labai glaudžiai susijusios ir optimalus dvigubo sprendimo būdas pateikia išsamią informaciją apie optimalų pirminį ir atvirkščią sprendimą.
Įvairūs naudingi šio turto aspektai:
(a) Jei pirminis turi daug konstantų ir nedidelio kintamųjų skaičiaus, skaičiavimas gali būti žymiai sumažintas konvertuojant problemą į „Dual“ ir išsprendžiant jį.
b) Linijinio programavimo dvilypumas turi tam tikrą didelę ekonominio pobūdžio pasekmę. Tai gali padėti vadovams atsakyti į klausimus apie alternatyvius veiksmus ir jų santykines vertes.
(c) Dvigubo skaičiavimas tikrina pirminio tirpalo tikslumą.
(d) Linijinio programavimo dvilypumas rodo, kad kiekviena linijinė programa yra lygi dviejų asmenų nulinės sumos žaidimui. Tai rodo, kad tarp linijinio programavimo ir žaidimų teorijos yra gana glaudūs ryšiai.
1. Dual formavimas, kai pirminis yra kanoninėje formoje:
Iš pirmiau minėtų dviejų programų aišku, kad:
(i) Maksimalizavimo problema pirminėje padėtyje tampa minimalizavimo problema dviguboje ir atvirkščiai.
(ii) Maksimalizavimo problema turi () apribojimus.
(iii) Jei pirminis yra n kintamieji ir m suvaržymai, dvigubai bus m kintamieji ir n apribojimai.
(iv) konstantos b 1 b 2, b 3 ……… b m primityviuose suvaržymuose yra objektyvios dvigubos funkcijos funkcijos.
(v) Konstantos c 1, c 2, c 3 c n objektyvinėje funkcijoje rodomos dvigubo ribose.
vi) Abiejų problemų kintamieji yra neigiami.
Žemiau pateikiami pirminiai ir dvigubi apribojimai.
1 pavyzdys:
Sukurkite dvigubą prie pirminės problemos
Sprendimas:
Pirma, ≥ suvaržymas paverčiamas ≤ suvaržymu, abiejų pusių padauginus iš -1.
2 pavyzdys:
Sukurkite dvigubą prie pirminės problemos
Sprendimas:
Tegul Y1, Y2, V3 ir V4 yra atitinkami dvigubi kintamieji, tada dvigubą problemą nurodo
Kadangi dviguba problema turi mažiau suvaržymų nei pirminis (2 vietoj 4), reikia mažiau darbo ir pastangų ją išspręsti. Tai išplaukia iš to, kad linijinio programavimo problemos skaičiavimo sunkumai daugiausia susiję su apribojimų skaičiumi, o ne kintamųjų skaičiumi.
3 pavyzdys:
Sukurkite dvigubą problemą
Sprendimas:
Kadangi minėta problema yra minimalizuojama, visi apribojimai turėtų būti> tipo. Trečiąją ribą padauginus iš - 1 abiejose pusėse.
-8x 1 + 2x 2 + 2x 3 ≥ -10
Šios problemos dvejopa bus
kur y1, y2, y3, y4 ir y5 yra du kintamieji, susiję su pirmuoju, antruoju trečiuoju, ketvirtuoju ir penktuoju apribojimu.
