Dualiteit (lineair programmeren)
Dualiteit is een begrip dat voortvloeit uit het lineair programmeren.
Dualiteit is de mogelijkheid om een ander optimaliseringsprobleem af te leiden van een lineair-programmerenprobleem door in een van de beperkingen de capaciteit toe- of af te laten nemen. Het eerste probleem heet het primale probleem. Door het toe- of afnemen van de capaciteit zal het lineair programma en dus het optimale resultaat veranderen. Deze verandering is fictief en noemen we daarom schaduwkosten.
Het belang hiervan wordt duidelijk in een klein voorbeeld:
Een boer die over grond en werkkracht beschikt, wil tarwe, rogge en suikerbieten telen en wil onderzoeken hoe hij zijn grond het beste over die drie gewassen moet verdelen. Hij heeft twee capaciteitsbeperkingen:
- De totale hoeveelheid grond is beperkt.
- De beschikbare werkkracht is beperkt.
Voor elk gewas gelden andere richtwaarden voor:
- het benodigde aantal uren werk per vierkante meter en
- de opbrengst per vierkante meter.
Dit is een typisch lineair-programmerenprobleem. Dit probleem is het primaal probleem.
Het afgeleide probleem is het volgende: Iemand wil de boerderij en de grond of een deel ervan overnemen. Hij moet beslissen hoeveel vierkante meter hij koopt. Voor elke oppervlakte grond verandert een van de capaciteitsbeperkingen van het oorspronkelijke probleem (hoeveelheid grond), maar de beschikbare werkkracht (aantal uren) verandert niet. Dus de totaal haalbare opbrengst van het land hangt af van de grootte van de aangekochte grond. Bij welke landoppervlakte is de opbrengst maximaal? Dat is het duale probleem.