Linjär optimering

Bivillkor

Bivillkor beskriver begränsningarna i problemet.

Exempel:

x ≥ 0

y ≥ 0

2x + y ≤ 10

Tillåtet område

När alla bivillkor ritas i samma koordinatsystem bildas ett område där samtliga villkor är uppfyllda.

Det kallas det tillåtna området.

Målfunktion

Målfunktionen är den storhet som ska maximeras eller minimeras.

Exempel:

P = 40x + 30y

För ett begränsat tillåtet område och en linjär målfunktion finns ett maximum eller minimum i någon av områdets hörnpunkter, om ett ändligt optimum finns.

Därför räcker det ofta att bestämma hörnpunkterna och jämföra målfunktionens värde där.

Anta bivillkoren:

x ≥ 0

y ≥ 0

x + y ≤ 6

2x + y ≤ 8

Målfunktion:

P = 30x + 20y

Hörnpunkterna är:

(0,0), (0,6), (2,4), (4,0)

Beräkna P:

0, 120, 140, 120

Maximum är alltså:

P = 140 vid (2,4)

1. Definiera variablerna.
2. Översätt begränsningarna till linjära olikheter.
3. Rita gränslinjerna och markera det tillåtna området.
4. Bestäm områdets hörnpunkter.
5. Beräkna målfunktionen i hörnpunkterna och jämför värdena.
6. Tolka svaret i den ursprungliga situationen.

Fel:

Testa slumpmässiga punkter i området.

Rätt:

För ett vanligt begränsat linjärt optimeringsproblem räcker det att jämföra hörnpunkterna.

Fel:

Rita bara gränslinjerna men glömma vilken sida av varje linje som uppfyller olikheten.

Rätt:

Markera det gemensamma tillåtna området.

Fel:

Ge bara koordinaterna som svar.

Rätt:

Tolka också vad x, y och målfunktionens värde betyder i problemet.

Målfunktion:

P = 5x + 3y

Hörnpunkter:

(0,0), (0,4), (2,3), (5,0)

Värden:

0, 12, 19, 25

Svar:

Maximum är 25 vid (5,0).

• Bivillkor beskriver problemets begränsningar.
• Det tillåtna området uppfyller alla bivillkor samtidigt.
• Målfunktionen beskriver vad som ska maximeras eller minimeras.
• För ett begränsat linjärt optimeringsproblem kontrolleras hörnpunkterna.
• Svaret ska alltid tolkas i den ursprungliga situationen.