Introduktion till linjärprogrammering

1 Ett produktionsproblem

En fabrik producerar två olika typer av möbler, bord och stolar. Produktionen av möbler erfordrar två olika typer av material; stora och små delar. Ett bord tillverkas genom att man sammanfogar två delar av vardera sorten, medan en stol består av en stor och två små delar. För att bestämma den optimala produktionsplanen, måste producenten beakta att det endast finns 6 stora och 8 små delar att tillgå. Ett bord kan säljas för 1600:- och en stol för 1000:-. Bestäm den produktionsplan som maximerar de totala intäkterna, under förutsättning att alla tillverkade möbler kan säljas och att de delar som används redan är betalda och inte kan säljas obearbetade.

[figure: Små bitar; Stora bitar; Stol, x_{2}; Bord, x_{1}]

Mål: maximera intäkterna

Variabeldefinition: x_{1} = antal bord som tillverkas och säljs
x_{2} = antal stolar som tillverkas och säljs
z = summan av intäkterna

Modell:  max z = 1600x_{1} + 1000x_{2}
då  2x_{1} +  x_{2} ≤ 6  (stora bitar)
2x_{1} +  2x_{2} ≤ 8  (små bitar)
x_{1}, x_{2} ≥ 0 (fysikaliska restriktioner)
x_{1}, x_{2} heltal  (bortses från här)

2 Lösning av modellen med hjälp av LEGO

Vi startar vid noll-produktion, d.v.s., x = (0, 0)^{T}, och studerar marginalförbättringar för att välja ut den möbeltyp som skall produceras. Eftersom x_{1} har den bästa marginalintäkten (1600:- per bord), väljer vi att producera så många bord som möjligt. Vid x = (3, 0)^{T} finns inga fler stora bitar kvar.

Marginalvärdet för x_{2} är nu 200, eftersom vi kan ta isär ett bord (−1600:-) och sedan bygga två stolar (+2000:-), vilket motsvarar intäkten +200:- per tillverkad stol. Öka värdet på x_{2} maximalt. Vid x = (2, 2)^{T} finns inga fler små bitar kvar.

Marginalvärdet för x_{1} är nu negativt (vi måste ta isär två stolar för att kunna bygga ett bord till, vilket ger en negativ intäkt, eller −400:- per tillverkat bord). Marginalvärdet för x_{2} är också negativt (vi måste ta isär ett bord för att kunna bygga en stol till, vilket ger en negativ intäkt, eller −600:- per tillverkad stol).

Alltså är x^{∗} = (2, 2)^{T} en optimallösning, d.v.s., tillverka två bord och två stolar för största möjliga intäkt, som är 5200:-.

3 Känslighetsanalys med hjälp av LEGO

Nedanstående förändringar antas göras oberoende av varandra; alla tre utgår från grundmodellen i avsnitt 1.

• Antag att producenten får möjlighet att köpa en stor bit till. Hur mycket är han/hon villig att betala för denna bit, och hur många bitar är värda detta pris?

Svar: Med en ytterligare stor bit kan vi göra ett bord av en stol. Förtjänsten från denna operation är 1600−1000:- = 600:-. Producenten betalar alltså maximalt 600:- för stora bitar, så länge det finns stolar kvar att omvandla till bord. Maximalt antal stora bitar som är värda detta pris är följdaktligen 2.

• Samma fråga för små bitar.

Svar: Med ytterligare två små bitar, kan vi göra två stolar av ett bord. Förtjänsten från denna operation är 2·1000−1600:- = 400:-. Producenten betalar alltså maximalt 200:- för små bitar, upp till maximalt antal bitar som är 4.

• Antag att försäljningspriset för bord sjunker till 750:-. Hur skall tillverkningsplanen förändras?

Svar: Marginalvärdet för att öka x_{2} ändras till 1000−750:- = 250:- per stol (ta isär ett bord och bygg en stol). Detta värde gäller så länge det finns bord kvar att montera ned, d.v.s., öka värdet på x_{2} med 2 till x_{2} = 4; då blir x_{1} = 0. Marginalvärdet för x_{1} är nu 750 − 1000 :- = −250:-, d.v.s., det lönar sig inte att bygga fler bord. Alltså är x^{∗} = (0, 4)^{T} optimalt, d.v.s, tillverka enbart fyra stolar. Förtjänsten blir 4000:-.

4 Geometrisk lösning av modellen

max z = 1600x_{1} + 1000x_{2}  (0)
då  2x_{1} +  x_{2} ≤ 6  (1)
2x_{1} +  2x_{2} ≤ 8  (2)
x_{1}, x_{2} ≥ 0

[figure: x_{2}; x_{1}; z = 0; (0); (1); (2); x^{∗} = (2, 2)]

4.1 Geometrisk känslighetsanalys

Modellen kan skrivas med generella beteckningar, enligt:

[ \begin{matrix}max & z & = & 1600x_{1} + 1000x_{2} \\ då & 2x_{1} & + & x_{2} & ≤ & 6 \\ 2x_{1} & + & 2x_{2} & ≤ & 8 \\ x_{1}, x_{2} & ≥ & 0 \end{matrix} ] ⟺ [ \begin{matrix}max & z & = c_{1}x_{1} + c_{2}x_{2} \\ då & a_{11}x_{1} & + & a_{12}x_{2} & ≤ & b_{1} \\ a_{21}x_{1} & + & a_{22}x_{2} & ≤ & b_{2} \\ & & x_{1}, x_{2} & ≥ & 0 \end{matrix} ]

Antag att följande ändringar görs (oberoende av varandra):

• b_{1} = 6 + Δb_{1}, Δb_{1} = 1 ⇒ x^{∗} = (3, 1)^{T} ⇒ z^{∗} = 5800:- Intäkt per ytterligare inköpt stor bit: 5800 − 5200:- = 600:- Δb_{1} > 2 ger ingen ytterligare intäkt, eftersom x_{2} ≥ 0 måste gälla.

• b_{2} = 8 + Δb_{2}, Δb_{2} = 2 ⇒ x^{∗} = (1, 4)^{T} ⇒ z^{∗} = 5600:- Intäkt per ytterligare inköpt liten bit: (5600 − 5200)/2:- = 200:- Δb_{2} > 4 ger ingen ytterligare intäkt, eftersom x_{1} ≥ 0 måste gälla.

• c_{1} = 1600 + Δc_{1}, Δc_{1} = −750 ⇒ x^{∗} = (0, 4)^{T} ⇒ z^{∗} = 4000 : −

[figure: x_{2}; x_{1}]

5 En icke-teknisk introduktion till simplexmetoden och känslighetsanalys i linjärprogrammering

5.1 Slack-, bas-, och icke-bas-variabler, samt extrempunkter

Ursprunglig problemformulering:

max z = 1600x_{1} + 1000x_{2}
då  2x_{1} +  x_{2} ≤ 6  (1)
2x_{1} +  2x_{2} ≤ 8  (2)
x_{1}, x_{2} ≥ 0

Olikheter kan inte manipuleras med hjälp av radoperationer. Därför gör vi om (1) och (2) till ekvationer med hjälp av slackvariabler:

max z = 1600x_{1} + 1000x_{2}
då  2x_{1} +  x_{2} + s_{1}  = 6  (1)
2x_{1} +  2x_{2}  + s_{2} = 8  (2)
x_{1}, x_{2}, s_{1}, s_{2} ≥ 0

Vi har nu 4 variabler och 2 ekvationer. Vi ska eliminera 2 av variablerna med hjälp av ekvationerna, och studera problemet i termer av de två återstående variablerna. Vi kallar de variabler som används för att lösa ekvationssystemet för basvariabler (eller beroende variabler), och de återstående för icke-basvariabler (eller oberoende variabler). Vi kommer att definiera målfunktionsvärdet z i termer av icke-basvariablerna.

När vi ska välja vilka variabler som är bas- respektive icke-basvariabler, måste vi tillse att

(i) basvariablerna kan lösa det linjära ekvationssystemet; detta innebär att motsvarande kolumner i ekvationssystemet måste vara linjärt oberoende, samt att (ii) lösningen till ekvationssystemet också uppfyller icke-negativitetsvillkoren.

Notera att på randen till vart och ett av bivillkoren har en av variablerna värdet 0. Låt X = {x ∈ ℜ^{2} | 2x_{1} + x_{2} ≤ 6, 2x_{1} + 2x_{2} ≤ 8, x_{1} ≥ 0, x_{2} ≥ 0}

[figure: x_{2}; x_{1}; (1); (2); x_{1} = 0; x_{2} = 0; s_{1} = 0; s_{2} = 0; X; Extrempunkt till X; Ej tillåten skärningspunkt]

I figuren ser vi att en extrempunkt till X karaktäriseras av att två variabler samtidigt har värdet 0 (med andra ord, två linjer skär varann). Vi ser också att det finns andra punkter där två variabler har värdet 0, men dessa skärningspunkter är inte tillåtna, eftersom antingen en variabel x_{j} eller slackvariabel s_{i} där är negativ.

En fundamental egenskap hos optimallösningar till linjära optimeringsproblem är följande: Om det existerar en optimallösning så existerar en optimal extrempunkt.

Generellt, betrakta modellen:

max z = c^{T}x,
då  Ax = b,
x ≥ 0,

där x, c ∈ ℜ^{n}, b ∈ ℜ^{m} och A ∈ ℜ^{m×n}. Låt X = {x ∈ ℜ^{n} | Ax = b, x ≥ 0}.

I vårt exempel är då m = 2, n = 4, x = (x_{1}, x_{2}, s_{1}, s_{2})^{T}, c = (1600, 1000, 0, 0)^{T},

A = ( \begin{matrix}2 & 1 & 1 & 0 \\ 2 & 2 & 0 & 1 \end{matrix} ), samt b = ( \begin{matrix}6 \\ 8 \end{matrix} ).

En extrempunkt till X motsvaras av en lösning till systemet Ax = b, i vilken n − m variabler (icke-basvariablerna) har värdet 0, och de återstående variablerna (basvariablerna) är icke-negativa. (Detta är det fundamentala sambandet mellan, å ena sidan, geometrin och algebran hos linjärprogrammeringsproblem, och, å andra sidan, simplexmetoden.)

5.2 Simplexmetoden

Simplexmetoden söker bland extrempunkterna till X på ett smart sätt, längs kantlinjerna så att värdet på z ökar hela tiden tills en optimal extrempunkt är funnen. Vid förflyttningen från en extrempunkt till nästa, låter simplexmetoden en basvariabel byta plats med en icke-basvariabel. Den ser till att problemet hela tiden beskrivs i termer av de aktuella icke-basvariablerna. Vi börjar med att skriva systemet på formen

−z + c^{T}x = 0
Ax = b
x ≥ 0.

Simplexmetoden arbetar enligt följande: bland de n st variablerna väljs n − m st icke-basvariabler. Systemet Ax = b används för att beskriva de m basvariablerna i termer av de n − m st icke-basvariablerna. Problemet formuleras sedan i termer av dessa variabler, genom att övriga m st variabler elimineras från målfunktionen.

Om partitioneringen av de n st variablerna i bas- och icke-basvariabler är korrekt, och icke-basvariablernas värden sätts till noll, så kommer lösningen till systemet Ax = b att vara en extrempunkt till mängden X. Målfunktionen är nu beskriven i termer av icke-basvariablerna; vi avgör huruvida denna extrempunkt är optimal genom att studera tecknet hos koefficienterna (marginalvärdena) i denna beskrivning av målfunktionen.

Om alla koefficienter är ≤ 0, så kan värdet på z inte öka genom att man ökar värdet på en icke-basvariabel från noll. Om däremot någon koefficient är > 0, så innebär det en ökad vinst om man ökar värdet på motsvarande variabel. Vi väljer den variabel som har störst positiv koefficient.

Att öka värdet på en icke-basvariabel från sitt värde noll, som den har i den aktuella extrempunkten, innebär att vi lämnar randen till ett bivillkor och rör oss längs en kantlinje till mängden X. Vi rör oss längs denna kantlinje tills vi når ett nytt bivillkor, vilket bestämmer den största ökningen hos värdet på denna icke-basvariabel som kan göras. Det uppnådda bivillkoret svarar mot en basvariabel, som får värdet noll. I den nya punkten har således (n − m) − 1 + 1 = n − m st variabler värdet noll; alltså är den en extrempunkt.

Nästa steg i simplexmetoden är att ersätta den icke-basvarabel som har fått ett högre värde än noll med den basvariabel som fått värdet noll, d.v.s., de två variablerna byter roller så att den tidigare basvariabeln blir icke-basvariabel och vice versa. Detta görs med hjälp av enkla radoperationer, och vi upprepar ovanstående steg från denna nya beskrivning av problemet.

5.3 Lösning av exemplet med hjälp av simplexmetoden

Vi skriver systemet på formen

z − c^{T}x = 0
Ax = b
x ≥ 0

vilket ger följande linjära ekvationssystem (då vi utesluter icke-negativitetsvillkoren, som underförstås):

\begin{aligned}−z & + & 1600x_{1} & + & 1000x_{2} & & & & & = & 0 \\ & & 2x_{1} & + & x_{2} & + & s_{1} & & & = & 6 \\ & & 2x_{1} & + & 2x_{2} & & & + & s_{2} & = & 8 \end{aligned}

Vi låter s_{1} och s_{2} vara basvariabler, och x_{1} och x_{2} vara icke-basvariabler, eftersom (i) s_{1} och s_{2} är givna som funktioner av x_{1} och x_{2}, och (ii) s_{1} och s_{2} finns inte med i målfunktionen.

Vi låter icke-basvariablerna få värdet noll, d.v.s., x_{1} = x_{2} = 0, vilket motsvarar extrempunkten origo. Koefficienterna för x_{1} och x_{2} i målfunktionen är 1600 respektive 1000; alltså är det mest lönsamt att öka värdet på x_{1}. (Origo är inte en optimal punkt, eftersom marginalvärdet för att öka värdet på variabeln är positivt för minst en variabel.)

Öka nu värdet på x_{1} från 0; detta innebär att vi rör oss längs x_{1}-axeln (en kantlinje till mängden X). Hur långt kan vi gå? Från ovanstående ekvationssystem följer (notera att x_{2} förblir lika med 0 medan värdet på x_{1} ökar):

\begin{aligned}s_{1} & = & 6 & − & 2x_{1} & − & x_{2} & = & 6 & − & 2x_{1} \\ s_{2} & = & 8 & − & 2x_{1} & − & 2x_{2} & = & 8 & − & 2x_{1} \end{aligned}

Värdet på x_{1} kan öka så länge som s_{1} och s_{2} förblir ≥ 0. Den variabel som först når värdet 0 är s_{1} (då x_{1} = 6/2 = 3), och det maximala värdet på x_{1} är 3. (s_{1} = 0 innebär att vi har använt alla stora bitar.) Vi har nu funnit den icke-basvariabel (x_{1}) och den basvariabel (s_{1}) som ska byta roller med varann.

För att uttrycka systemet med hjälp av de nya icke-basvariablerna (s_{1}, x_{2}), utför vi följande radoperationer:

\begin{aligned}−z & + & 1600 x_{1} & + & 1000 x_{2} & & & & & = & 0 & (0) \\ & & 2 x_{1} & + & x_{2} & + & s_{1} & & & = & 6 & (1) \\ & & 2 x_{1} & + & 2 x_{2} & & & + & s_{2} & = & 8 & (2) \\ −z & & & + & 200 x_{2} & − & 800 s_{1} & & & = & − 4800 & (0)−800·(1) \\ & & x_{1} & + & \frac{1}{2}x_{2} & + & \frac{1}{2}s_{1} & & & = & 3 & \frac{1}{2}·(1) \\ & & & & x_{2} & − & s_{1} & + & s_{2} & = & 2 & (2)−(1) \end{aligned}

Vi har nu eliminerat basvariablerna (x_{1} och s_{2}) ur målfunktionen, och de två basvariablerna är tecknade som funktioner av icke-basvariablerna (s_{1} och x_{2}). Observera följande:

(i) Vi låter s_{1} = x_{2} = 0 och erhåller x = (3, 0)^{T}, d.v.s, en extrempunkt till X. (ii) Målfunktionsvärdet är 4800. (iii) Marginalvärdet för att öka värdet på x_{2} är i denna punkt 200, vilket står i målfunktionsraden. (iv) s_{2} = 2 > 0, vilket innebär att det finns små bitar kvar.

Eftersom en målfunktionskoefficient är positiv (ett marginalvärde är positivt), är lösningen x = (3, 0)^{T} inte optimal.

Vi väljer härnäst att öka värdet på x_{2} från 0. Eftersom vi låter värdet på s_{1} förbli = 0, rör vi oss längs bivillkoret (1). Ur systemet ovan erhålls följande:

\begin{aligned}x_{1} & = & 3 & − & \frac{1}{2}x_{2} \\ s_{2} & = & 2 & − & x_{2} \end{aligned}

Först att nå värdet 0 är variabeln s_{2} (vid x_{2} = 2). Vi låter x_{2} = 2 och har identifierat nästa variabelpar att byta roller. Den nya extrempunkten är uppenbarligen x = (2, 2)^{T}, eftersom det nya värdet på x_{1} är x_{1} = 3 − \frac{1}{2} · 2 = 2, och vi skriver om systemet enligt följande:

\begin{aligned}−z & & + & 200 x_{2} & − & 800 s_{1} & & & = & −4800 & (0) \\ & x_{1} & + & \frac{1}{2}x_{2} & + & \frac{1}{2}s_{1} & & & = & 3 & (1) \\ & & & x_{2} & − & s_{1} & + & s_{2} & = & 2 & (2) \\ −z & & & & − & 600 s_{1} & − & 200 s_{2} & = & −5200 & (0)−200·(2) \\ & x_{1} & & & + & s_{1} & − & \frac{1}{2}s_{2} & = & 2 & (1)−\frac{1}{2}·(2) \\ & & & x_{2} & − & s_{1} & + & s_{2} & = & 2 & (2) \end{aligned}

Ur detta system kan vi utläsa att x = (2, 2)^{T}, z = 5200, och att denna extrempunkt är optimal, eftersom ingen koefficient i målfunktionsraden är positiv. Vi har härmed löst exemplet med hjälp av simplexmetoden.

5.4 Känslighetsanalys

Vi är intresserade av värdet av ytterligare resurser, i form av fler stora respektive små bitar, för den ovanstående modellen. Vi är också intresserade av hur många bitar av respektive sort som har detta värde.

Antag att vi låter b_{1} := b_{1} + Δb_{1}, där Δb_{1} > 0. Om vi bibehåller representationen av systemet ovan, och utnyttjar den nya kapaciteten fullt ut genom att ändra optimallösningen x^{∗} = (2, 2)^{T} så att den följer bivillkoret (2), så kommer slackvariabeln s_{1} (som är proportionell mot avståndet från aktuell punkt till randen av det ursprungliga bivillkoret (1)) att få ett negativt värde.

Notera att det är tillåtet att resonera på det sättet eftersom

2x_{1} + x_{2} + s_{1} = b_{1} + Δb_{1}, s_{1} ≥ 0  ⟺  2x_{1} + x_{2} + s_{1} = b_{1}, s_{1} ≥ −Δb_{1}.

Om Δb_{1} = 1 så blir s_{1} = −1, och vinsten kommer att öka med (−600) · (−1) = 600:-. För att finna den nya optimallösningen utnyttjar vi systemet, vilket ger:

x_{1} = 2 − s_{1}
x_{2} = 2 + s_{1}

Alltså, om b_{1} := b_{1} + 1 så erhålls s_{1} = −1, vilket ger x^{∗} = (3, 1)^{T}. Det är också klart att den maximala ökningen Δb_{1} som är intressant är den då antingen x_{1}^{∗} eller x_{2}^{∗} blir lika med noll. Detta inträffar då s_{1} = −2, d.v.s., då Δb_{1} = 2; då blir x^{∗} = (4, 0)^{T} (enbart bord produceras). Alltså är vi intresserade av att köpa maximalt två extra stora bitar till ett högsta pris av 600:- per styck.

För köp av ytterligare små bitar använder vi samma argument. Låt b_{2} := b_{2} + Δb_{2}. Effekten av att öka värdet på b_{2} är att s_{2} blir negativ, och vi kan utläsa intäkterna för en extra liten bit som (−200) · (−1) = 200:-. Vi betalar alltså maximalt 200:- för en extra liten bit. Den nya lösningen, för vilket värde som helst på Δb_{2}, och det maximala värdet på Δb_{2} kan utläsas ur systemet:

x_{1} = 2 + \frac{1}{2}s_{2} = 2 − \frac{1}{2}Δb_{2}
x_{2} = 2 − s_{2} = 2 + Δb_{2}.

Om vi låter Δb_{2} = 2 erhålls x^{∗} = (1, 4)^{T}. Det maximala värdet på Δb_{2} är 4, vilket motsvarar x^{∗} = (0, 6)^{T}. Vi är alltså intresserade av att köpa maximalt 4 små bitar till en högsta kostnad av 250:- vardera.

6 En icke-teknisk introduktion till dualitet i linjärprogrammering

6.1 En konkurrent

Antag att en annan fabrik (låt oss kalla den Billy) tillverkar bokhyllor vars råmaterial är detsamma som för borden och stolarna, alltså stora och små bitar. Billy vill expandera sin verksamhet och är intresserad av att köpa den resurs som “vår” fabrik har. Vi kan ställa oss två frågor, som (skall det visa sig) har samma svar: (1) vilket är det lägsta bud (pris) som vi kan acceptera för den totala kapaciteteten?;

(2) vilket är det högsta bud (pris) som Billy är beredd att erbjuda för råvarorna?

6.2 Ett dualt problem

För att studera problemet närmare införs:

Variabeldefinition: y_{1} = priset (i kronor) som Billy erbjuder för varje stor bit
y_{2} = priset (i kronor) som Billy erbjuder för varje liten bit
w = det totala budet som Billy erbjuder

För att vi ska acceptera att sälja vår resurs måste rimligen det pris som erbjuds för den vara minst lika stort som det värde resursen representerar i vår optimala produktionsplan, annars tjänar vi mer på att använda resursen själva. Betrakta till exempel nettointäkten för ett såld bord. Nettointäkten är 1600:- per bord, och för den åtgår två stora och två små bitar. För att inte budet omedelbart skall förkastas måste alltså Billy erbjuda ett pris som uppfyller 2y_{1} + 2y_{2} ≥ 1600. Motsvarande för värdet av en tillverkad stol är kravet att y_{1} + 2y_{2} ≥ 1000.

Billy är naturligtvis intresserad av att minimera det totala budet under förutsättning att budet accepteras. Med observationen att y_{1} och y_{2} är priser och därför ickenegativa har vi följande matematiska modell för Billys problem:

Modell:  min w = 6y_{1} + 8y_{2}
då 2y_{1} + 2y_{2} ≥ 1600 (bord)
y_{1} + 2y_{2} ≥ 1000  (stolar)
y_{1}, y_{2} ≥ 0  (priser)

Detta problem brukar kallas det duala problemet till vårt produktionsplaneringsproblem (som i stället benämnes det primala problemet).

Den optimala lösningen till detta problem är y^{∗} = (600, 200)^{T}. Det totala budet är w^{∗} = 5200:-.

6.3 Tolkningar av den duala optimala lösningen

Som synes är den optimala duala lösningen identisk med skuggpriserna för resursbivillkoren. (Detta är en generell slutsats i linjärprogrammering.)

För att motivera att detta är rimligt kan vi tänka oss att Billy endast är en fiktiv konkurrent, som vi använder tillsammans med det duala problemet för att mäta värdet av vår resurs. Detta (fiktiva) mått kan användas till exempel för att skapa en intern prissättning av sådana begränsade resurser som flera underavdelningar inom ett produktionsföretag utnyttjar. Det pris som den duala optimallösningen (skuggpriset) utgör är då ett prisstyrningsinstrument som får underavdelningarna att utnyttja de begränsade resurserna på ett optimalt sätt avseende det övergripande målet.

Vi noterar också att det totala värdet av produktionen (5200:-) överensstämmer med det totala värdet w^{∗} av resurserna i vårt företag. (Detta är också en generell slutsats i linjärprogrammering; se Stark dualitet nedan.) Billy är naturligtvis inte villig att bjuda mer än vad resursen är värd, men kan samtidigt inte ge ett lägre bud än den vinst som vi själva kan åstadkomma, eftersom vi då inte är beredda att sälja.

Vi kan notera att det för varje tillåten produktionsplan x och pris y gäller att z ≤ w, eftersom

z = 1600x_{1} + 1000x_{2} ≤ (2y_{1} + 2y_{2})x_{1} + (y_{1} + 2y_{2})x_{2} = y_{1}(2x_{1} + x_{2}) + y_{2}(2x_{1} + 2x_{2})

≤ 6y_{1} + 8y_{2} = w,

där vi i olikheterna utnyttjar alla bivillkoren i det primala och det duala problemet. (Även detta är en generell slutsats; se Svag dualitet nedan.) Alltså är varje acceptabelt bud (från vår sida sett) en överskattning av vår möjliga vinst, och det är denna överskattning som Billy minimerar i det duala problemet.

6.4 Duala problem

Samma data förekommer i båda problemen. I själva verket kan man till varje linjärt problem formulera ett motsvarande dualt dito:

Primalt problem:  max z = c^{T}x
då  Ax ≤ b
x ≥ 0

Dualt problem:  min w = b^{T}y
då  A^{T}y ≥ c
y ≥ 0

I vårt fall är c = (\begin{matrix}1600 \\ 1000 \end{matrix}) , A = (\begin{matrix}2 & 1 \\ 2 & 2 \end{matrix}) , och b = (\begin{matrix}6 \\ 8 \end{matrix}) .

Mellan dessa finns många relationer, som bildar en teori om linjära optimeringsproblems dualitet och optimalitet. Vi tar här upp ett par exempel på sådana.

6.5 Dualitetsteori

Låt det primala problemet ovan förkortas (P) och det duala (D). Vi noterar att det duala problemet till (D) är (P).

Svag dualitet: Om x är tillåten i (P) och y är tillåten i (D) gäller att z ≤ w.

Bevis: z = c^{T}x ≤ (A^{T}y)^{T}x = y^{T}Ax ≤ y^{T}b = w. □

Stark dualitet: Om (P) och (D) båda har tillåtna lösningar så har båda också optimala lösningar, och z^{∗} = w^{∗}.

Bevis: Se Appendix. □

Komplementaritet: Låt x^{∗} och y^{∗} vara optimala lösningar till problemen (P) respektive (D). Då gäller att

y_{i}^{∗}[a_{i}x^{∗} − b_{i}] = 0,  i = 1, …, m,
x_{j}^{∗}[(a^{j})^{T}y^{∗} − c_{j}] = 0,  j = 1, …, n,

där a_{i} är rad i i matrisen A och a^{j} är kolumn j i matrisen A.

Bevis: Eftersom stark dualitet gäller så råder likhet i de två olikheterna i beviset för svag dualitet. Dessa två bildar just komplementvillkoren ovan. □

Med andra ord, om ett bivillkor i (P) inte är uppfyllt med likhet (dvs. det finns ett slack i det bivillkoret) så är dess pris 0. I vårt exempel är båda resursbivillkoren uppfyllda med likhet (all resurs utnyttjas); om så ej vore fallet skulle det alltså betyda att värdet av ytterligare resurs (dvs. skuggpriset) vore 0, vilket är naturligt eftersom vi då inte kan (eller vill) utnyttja den i vår optimala produktionsplan.

Optimaliteten hos en vektor x kan sammanfattas med att tre krav måste vara uppfyllda: x måste (1) vara tillåten i (P), och x skall motsvaras av en (2) komplementär dual vektor y som (3) är tillåten i (D):

Optimalitet: Om x är tillåten i (P) och y är tillåten i (D) gäller att de är optimala i respektive problem om och endast om de har samma målfunktionsvärde, vilket är ekvivalent med att de tillsammans uppfyller komplementaritet. □

Om vi har löst det ena problemet kan vi alltså lösa ut det andra problemets lösning via komplementvillkoren. I simplexmetoden är dessa uppfyllda hela tiden, medan den komplementära lösningen blir tillåten precis då den primala är optimal. Då ger också, som vi har sett, simplextablån automatiskt den duala optimallösningen.

Appendix Farkas Lemma och starka dualsatsen

Följande resultat är centralt för teorin om polyedriska mängder:

Farkas Lemma (1901): Precis ett av följande linjära system har en lösning:

Ax ≥ 0,  (1a)
c^{T}x < 0  (1b)

A^{T}y = c,  (2a)
y ≥ 0  (2b)

Vi applicerar detta resultat på primal–dual paret

(P) min z = c^{T}x
då  Ax ≥ b
x ≥ 0

(D) max w = b^{T}y
då  A^{T}y ≤ c
y ≥ 0

Notera att svag dualitet implicerar att varje par av tillåtna lösningar till (P) och (D) uppfyller c^{T}x ≥ b^{T}y.

Bevis av stark dualitet: Betrakta systemet

Ax  ≥ b,
− A^{T}y ≥ −c,
−c^{T}x + b^{T}y ≥ 0,
x ≥ 0,  y ≥ 0

Om detta system har en lösning, (x, y), så följer resultatet av svag dualitet, eftersom z = w. Antag därför att det saknar lösning. En lämplig omskrivning av systemet och en tillämpning av Farkas Lemma ger då att följande system har en lösning:

A^{T}u  − λc ≤ 0,
− Av + λb ≤ 0,
b^{T}u − c^{T}v  > 0,
u ≥ 0,  v ≥ 0  λ ≥ 0

Antag först att λ > 0. Vi kan anta utan inskränkning att λ = 1, eftersom högerleden är noll. Då ser vi omedelbart att u respektive v är tillåtna lösningar i (P) respektive (D) med målfunktionsvärden som motsäger svag dualitet. Alltså måste λ = 0 gälla. Antag nu att c^{T}v ≥ 0. Då följer att b^{T}u > 0 och via Farkas Lemma kan vi dra slutsatsen att (P) saknar lösning, vilket är en motsägelse. Om vi i stället antar att c^{T}v < 0 kan vi från en tillåten lösning x i (P) konstruera en primalt tillåten lösning x(θ) := x + θv för vilket gäller att c^{T}x(θ) → −∞ när θ → +∞. Från svag dualitet följer då att (D) saknar lösning, vilket är en motsägelse. □

Vi kan också motivera Farkas Lemma med hjälp av starka dualsatsen (trots att stark dualitet bevisas med hjälp av den …):

Bevis av Farkas Lemma:

[(1) ⟹ ¬(2)]: Antag att (1) har en lösning, x. Om (2) också har en lösning, y, implicerar det att

c^{T}x = y^{T}Ax ≥ 0,

vilket leder till en motsägelse.

[¬(1) ⟹ (2)]: Antag att (1) saknar lösning. Vi konstruerar en lösning till (2) enligt följande. Konstruera det linjära primal–duala problemparet

min z = c^{T}x
då  Ax ≥ 0

max w = 0^{T}y
då  A^{T}y = c
y ≥ 0

Minimeringsproblemet har optimallösning x^{∗} = 0. Enligt starka dualsatsen har dess dual en optimallösning. Den är därför speciellt tillåten. □