Dualiteit bij problemen met lineaire programmering

Dualiteit bij problemen met lineaire programmering!

Voor elk Lineair programmeerprobleem is er een overeenkomstig uniek probleem met dezelfde gegevens en wordt ook het oorspronkelijke probleem beschreven. Het oorspronkelijke probleem wordt oerprogramma genoemd en het bijbehorende unieke probleem wordt Dual-programma genoemd. De twee programma's zijn nauw met elkaar verbonden en optimale oplossing van dual geeft volledige informatie over optimale oplossing van oer en vice versa.

Verschillende nuttige aspecten van deze eigenschap zijn:

(a) Als oer een groot aantal composities en een klein aantal variabelen heeft, kan de berekening aanzienlijk worden verminderd door het probleem in Dual om te zetten en het vervolgens op te lossen.

(b) Dualiteit in lineaire programmering heeft bepaalde verstrekkende gevolgen van economische aard. Dit kan managers helpen vragen over alternatieve handelwijzen en hun relatieve waarden te beantwoorden.

(c) Berekening van de dubbele controles van de nauwkeurigheid van de oeroplossing.

(d) Dualiteit bij lineaire programmering toont aan dat elk lineair programma equivalent is aan een zero-sumspel voor twee personen. Dit geeft aan dat er vrij nauwe relaties bestaan ​​tussen lineaire programmering en de theorie van games.

1. Forming Dual wanneer Primal in canonieke vorm is:

Uit de bovenstaande twee programma's zijn de volgende punten duidelijk:

(i) Het maximalisatieprobleem in het oerbeeld wordt het minimalisatieprobleem in de dual en vice versa.

(ii) Het maximalisatieprobleem heeft () beperkingen.

(iii) Als de oer n-variabelen en m-beperkingen bevat, bevat de dual m-variabelen en n beperkingen.

(iv) De constanten b 1 b 2, b 3 ......... b m in de beperkingen van de oer verschijnen in de doelfunctie van de duaal.

(v) De constanten c 1, c 2, c 3 c n in de doelfunctie van de oer verschijnen in de beperkingen van de duale.

(vi) De variabelen in beide problemen zijn niet-negatief.

De beperkingsrelaties van het oorspronkelijke en het dubbele worden hieronder weergegeven.

Voorbeeld 1:

Construeer het duaal voor het oerprobleem

Oplossing:

Eerst wordt de ≥ beperking omgezet in ≤ beperking door beide zijden met -1 te vermenigvuldigen.

Voorbeeld 2:

Construeer het duaal voor het oerprobleem

Oplossing:

Laat Y 1, Y 2, V 3 en V 4 de overeenkomstige duale variabelen zijn, dan wordt het dubbele probleem gegeven door

Omdat het dubbele probleem een ​​kleiner aantal beperkingen heeft dan het primaire (2 in plaats van 4), heeft het minder inspanning en moeite nodig om het op te lossen. Dit volgt uit het feit dat de rekenkundige moeilijkheid in het probleem met lineaire programmering voornamelijk wordt geassocieerd met het aantal beperkingen in plaats van het aantal variabelen.

Voorbeeld 3:

Construeer de dubbel van het probleem

Oplossing:

Aangezien het opgegeven probleem van minimalisatie is, moeten alle beperkingen van> type zijn. De derde beperking vermenigvuldigen met - 1 aan beide kanten krijgen we.

-8x 1 + 2x 2 + 2x 3 ≥ -10

De duaal van het gegeven probleem zal zijn

waarbij y 1, y 2, y 3, y 4 en y 5 de duale variabelen zijn die respectievelijk geassocieerd zijn met de eerste, tweede derde, vierde en vijfde beperking.