Dualitet i linjära programmeringsproblem
Dualitet i linjära programmeringsproblem!
För varje linjärt programmeringsproblem finns ett motsvarande unikt problem som innefattar samma data och beskriver också det ursprungliga problemet. Det ursprungliga problemet heter primalprogram och motsvarande unika problem heter Dual program. De två programmen är mycket nära besläktade och optimal lösning av dual ger fullständig information om optimal lösning av primal och vice versa.
Olika användbara aspekter av den här egenskapen är:
(a) Om primal har ett stort antal konstanter och ett litet antal variabler kan beräkningen minskas avsevärt genom att konvertera problem till Dual och sedan lösa det.
b) Dualitet i linjär programmering har viss långtgående konsekvens av ekonomisk karaktär. Detta kan hjälpa chefer att svara på frågor om alternativa handlingsplaner och deras relativa värden.
(c) Beräkning av dubbelkontrollen är noggrannheten hos den primala lösningen.
(d) Dualitet i linjär programmering visar att varje linjärt program motsvarar ett nollspel med två personer. Detta indikerar att det finns ganska nära relationer mellan linjär programmering och spelteorin.
1. Forming Dual när Primal är i canonisk form:
Från ovanstående två program är följande punkter tydliga:
(i) Maximeringsproblemet i primalen blir minimeringsproblemet i dubbla och vice versa.
(ii) Maximeringsproblemet har () begränsningar.
iii) Om primalen innehåller n-variabler och m-begränsningar, innehåller den dubbla viljan m variabler och n-begränsningar.
(iv) Konstanterna b 1 b 2, b 3 ......... b m i primärns begränsningar förekommer i den dubbla funktionens objektiva funktion.
(v) Konstanterna c 1, c 2, c 3 c n i den primära funktionens objektiva funktion förekommer i de dubbla gränserna.
(vi) Variablerna i båda problemen är icke-negativa.
Förhållandeförhållandena mellan den primala och den dubbla är representerade nedan.
Exempel 1:
Konstruera dual till primalproblemet
Lösning:
För det första omvandlas ≥ begränsningen till ≤ begränsning genom att multiplicera båda sidorna med -1.
Exempel 2:
Konstruera dual till primalproblemet
Lösning:
Låt Y 1, Y 2, V 3 och V 4 vara motsvarande dubbla variabler, då är det dubbla problemet givet av
Eftersom det dubbla problemet har mindre antal begränsningar än primalen (2 istället för 4), kräver det mindre arbete och ansträngning för att lösa det. Detta härrör från det faktum att beräkningsproblemet i det linjära programmeringsproblemet huvudsakligen är förknippat med antalet begränsningar snarare än antalet variabler.
Exempel 3:
Konstruera dual av problemet
Lösning:
Eftersom det givna problemet är att minimera, bör alla begränsningar vara av> typ. Multiplicera den tredje begränsningen med - 1 på båda sidor får vi.
-8x 1 + 2x 2 + 2x 3 ≥ -10
Den dubbla av det givna problemet kommer att vara
där y 1, y 2, y 3, y 4 och y 5 är de dubbla variablerna associerade med den första, andra tredje, fjärde och femte begränsningen.
