Dualitet i lineære programmeringsproblemer

Dualitet i lineære programmeringsproblemer!

For hvert lineært programmeringsproblem er der et tilsvarende unikt problem, der involverer de samme data, og det beskriver også det oprindelige problem. Det oprindelige problem kaldes primal program og det tilsvarende unikke problem kaldes Dual program. De to programmer er meget nært beslægtede og den optimale løsning af dual giver fuldstændig information om optimal opløsning af primal og omvendt.

Forskellige nyttige aspekter af denne ejendom er:

(a) Hvis primal har stort antal constaints og et lille antal variabler, kan beregningen reduceres betydeligt ved at konvertere problemet til Dual og derefter løse det.

b) Dualitet i lineær programmering har en vis vidtrækkende konsekvens af økonomisk karakter. Dette kan hjælpe ledere med at besvare spørgsmål om alternative handlingskurser og deres relative værdier.

(d) Dualitet i lineær programmering viser, at hvert lineært program svarer til et topersons nul-sum-spil. Dette indikerer, at der eksisterer ret tætte relationer mellem lineær programmering og teori om spil.

1. Formering Dual, når Primal er i canonisk form:

Fra ovenstående to programmer er følgende punkter tydelige:

(i) Maksimeringsproblemet i primalen bliver minimeringsproblemet i det dobbelte og omvendt.

(ii) Maksimeringsproblemet har () begrænsninger.

(iii) Hvis primalen indeholder n-variabler og m-begrænsninger, vil den dobbelte indeholde m-variabler og n-begrænsninger.

(iv) Konstanterne b ₁ b ₂, b ₃ ......... b _m i primalets begrænsninger fremgår af den dobbelts objektive funktion.

(v) Konstanterne c ₁, c ₂, c ₃ c _n i primals objektive funktion fremgår af de dobbelts begrænsninger.

(vi) Variablerne i begge problemer er ikke-negative.

Forholdet mellem primal og dobbelt er repræsenteret nedenfor.

Eksempel 1:

Konstruer dual til det primale problem

Opløsning:

For det første omdannes ≥ begrænsningen til ≤ begrænsning ved at gange begge sider med -1.

Eksempel 2:

Konstruer dual til det primale problem

Opløsning:

Lad Y ₁, Y ₂, V ₃ og V ₄ være de tilsvarende to variable, så er det dobbelte problem givet af

Da det dobbelte problem har mindre antal begrænsninger end primalen (2 i stedet for 4), kræver det mindre arbejde og indsats for at løse det. Dette skyldes det faktum, at beregningsvanskeligheden i det lineære programmeringsproblem hovedsageligt er forbundet med antallet af begrænsninger snarere end antallet af variabler.

Eksempel 3:

Konstruer dual af problemet