Dualitet i lineære programmeringsproblemer
Dualitet i lineære programmeringsproblemer!
For hvert linjært programmeringsproblem er det et tilsvarende unikt problem som involverer de samme dataene, og det beskriver også det opprinnelige problemet. Det opprinnelige problemet kalles primalprogram og det tilsvarende unike problemet kalles Dual program. De to programmene er svært nært beslektede og optimal løsning av dual gir fullstendig informasjon om optimal løsning av primal og omvendt.
Ulike nyttige aspekter ved denne eiendommen er:
(a) Hvis primal har stort antall constaints og lite antall variabler, kan beregningen reduseres betydelig ved å konvertere problemet til Dual og deretter løse det.
(b) Dualitet i lineær programmering har viss vidtgående konsekvens av økonomisk natur. Dette kan hjelpe ledere til å svare på spørsmål om alternative handlingsmåter og deres relative verdier.
(c) Beregning av de to kontrollene er nøyaktigheten av den primale løsningen.
(d) Dualitet i lineær programmering viser at hvert lineært program er ekvivalent med et topersons null-sumspill. Dette indikerer at det eksisterer forholdsvis nært forhold mellom lineær programmering og teori om spill.
1. Forming Dual når Primal er i Canonical Form:
Fra de to ovennevnte programmene er følgende punkter klare:
(i) Maksimeringsproblemet i primalen blir minimeringsproblemet i dual og vice versa.
(ii) Maksimeringsproblemet har () begrensninger.
(iii) Hvis primalen inneholder n variabler og m begrensninger, vil den doble inneholde m variabler og n begrensninger.
(iv) Konstantene b 1 b 2, b 3 ......... b m i primalets begrensninger fremstår i den dobbelte objektivfunksjonen.
(v) Konstanterne c 1, c 2, c 3 c n i den primære funksjonens objektive funksjon vises i begrensningene til den dobbelte.
(vi) Variablene i begge problemene er ikke-negative.
Forholdsforholdene mellom primal og dual er representert nedenfor.
Eksempel 1:
Konstruer dual til det primale problemet
Løsning:
For det første omdannes ≥ begrensningen til ≤ begrensning ved å multiplisere begge sider med -1.
Eksempel 2:
Konstruer dual til det primale problemet
Løsning:
La Y 1, Y 2, V 3 og V 4 være de tilsvarende to variablene, så er det dobbelte problemet gitt av
Da det dobbelte problemet har mindre antall begrensninger enn primalen (2 i stedet for 4), krever det mindre arbeid og innsats for å løse det. Dette følger av det faktum at beregningsvanskeligheten i det lineære programmeringsproblemet hovedsakelig er forbundet med antall begrensninger i stedet for antall variabler.
Eksempel 3:
Konstruer dual av problemet
Løsning:
Som det oppgitte problemet er å minimere, bør alle begrensninger være av> type. Multiplikasjon av den tredje begrensningen med - 1 på begge sider får vi.
-8x 1 + 2x 2 + 2x 3 ≥ -10
Dobbel av det oppgitte problemet vil være
hvor y 1, y 2, y 3, y 4 og y 5 er de to variablene forbundet med henholdsvis den første, andre tredje, fjerde og femte begrensning.
