Gevoeligheidsanalyse op de RHZ

[Student@lessius]

Beste,
maandag de 16e heb ik mijn exaam en ik zit met een groot propleem. Hieronder vind u een examenvraag die er altijd bij is en ik heb geen idee hoe ik hem moet oplossen. Ik heb de opgave en de oplossingen maar ik weet niet hoe ik aan deze uitkomsten moet komen.
Ik vraag jullie allemaal om hulp.

OPGAVE:

Beschouw het volgende lineaire programma: maximaliseer 4x+2y als x≥0,y≥0
x+2y≤16
x+y≤9
3x+y≤21
x+y≥4
-->Voer een gevoeligheidsanalyse uit op de RHZ van de nevenvoorwaarden.
De antwoorden zijn

Hp z
X∩4 (4,0) 16
Y∩4 (0,4) 8
Y∩1 (0,8) 16
1∩2 (2,7) 22
3∩2 (6,3) 30
3∩X (7,0) 28

NVW RHZ Status Slack
1 12 NB 4
2 9 B 0
3 21 B 0
4 9 NB 5

Nevenvoorwaarde1

RHZ1 ↑ : onbeperkt
z=0
y1= z/RHZ1= 0/+ oneindig=0

RHZ1 ↓: tot (6,3) RHZ=-4
z=0
y1= z/rhz1=0/-4=0

Nevenvoorwaarde 2

RHZ2 ↑: tot 1∩3 : (26/5,27/5) RHZ2=1.6
z=1,6

y2=z/RHZ2=1,6/1,6=1

...er zijn 4 nevenvoorwaarden

NVW SCH pr RHZ nu RHZ dalen tot RHZ dalen met RHZ stijgen tot RHZ stijgen met
1 0 16 12 4 +oneindig +oneindig
2 1 9 7 2 10,6 1,6
3 1 21 13 8 27 6
4 0 4 -oneindig -oneindig 9 5



Hoe kom ik aan al deze getallen?
alvast heel erg bedankt voor jullie moeite

[arie]

Je wilt de maximale waarde weten van de functie f afhankelijk van x en y gegeven door:
f(x, y) = 4x + 2y
of kortweg de maximale waarde van z = f(x, y) in:
z = 4x + 2y
als de volgende nevenvoorwaarden NVW gegeven zijn:
NVW0: x≥0, y≥0
NVW1: x+2y≤16
NVW2: x+y≤9
NVW3: 3x+y≤21
NVW4: x+y≥4

Maak een grafiek in het xy vlak van alle met de nevenvoorwaarden corresponderende lijnen:
x-as en y-as
L1: x+2y=16, ofwel: y = 8 - 0.5x
L2: x+y=9, ofwel: y = 9 - x
L3: 3x+y=21, ofwel: y = 21 – 3x
L4: x+y=4, ofwel y = 4 - x

Arceer hierin het gebied van de feasible values = de (x,y)-waarden die voldoen aan de nevenvoorwaarden = het gebied omsloten door de lijnen van de nevenvoorwaarden (≥ correspondeert met het gebied boven/rechts van de lijn; ≤ met het gebied onder/links van de betreffende lijn).

Bepaal nu de hoekpunten Hp van dit gebied door de snijpunten te berekenen van de betreffende grenslijnen, je vindt dan de snijpunten:
x-as met L4: (4,0)
y-as met L4: (0,4)
y-as met L1: (0,8)
L1 met L2: (2,7)
L2 met L3: (6,3)
L3 met x-as: (7,0)

Bepaal nu de bij deze punten behorende z-waarden:
(4,0): x=4, y=0, dus z = 4x + 2y = 16
(0,4) : x=0, y=4, dus z = 4x + 2y = 8
(0,8) : x=0, y=8, dus z = 4x + 2y = 16
(2,7) : x=2, y=7, dus z = 4x + 2y = 22
(6,3) : x=6, y=3, dus z = 4x + 2y = 30
(7,0) : x=7, y=0, dus z = 4x + 2y = 28

Omdat bij Lineair Programmeren het maximum en minimum altijd op een hoekpunt liggen, kunnen we uit bovenstaande direct aflezen dat het maximum voor z gelijk is aan 30, voor het punt (6, 3), dus als x=6 en y=3, wat tevens het snijpunt is van L2 en L3, behorend bij NVW2 en NVW 3.
Hierdoor zijn NVW2 en NVW3 bindend (=B) (elke verandering in NVW2 of NVW3 zal direct effect hebben op de maximale waarde van z) en de overige NVW’s (NVW1 en NVW4) zijn niet bindend (=NB): kleine veranderingen van deze NVW’s hebben geen effect op z_max.

Kijken we nu naar de rechterhandzijden (RHZ’s) van de NVW’s indien hun lijnen door het punt (6, 3) zouden lopen (vul steeds x=6 en y=3 in):

NVW1: x+2y ≤ 6+2*3 = 12
NVW2: x+y≤ 6+3 = 9
NVW3: 3x+y≤ 3*6+3 = 21
NVW4: x+y≥ 6+3 = 9

De Slack is het verschil tussen de oorspronkelijke waarden en de waarden die we zojuist hebben gevonden:

NVW1: 16-12=4
NVW2: 9-9=0
NVW3: 21-21=0
NVW4: 9-4=5

NB:
[1] voor bindende NVW’s is deze waarde altijd nul.
[2] kijk even na of bij jullie de Slack ook altijd positief gedefinieerd is, zo niet dan krijgt NVW1 of NVW4 een min-teken.

Nu de gevoeligheid:

Nevenvoorwaarde1
Indien je de RHZ (= het getal rechts van het ongelijkheidsteken) van NVW1 groter maakt, dus L1 naar boven verschuift, voor alle waarden van RHZ tot in het oneindige, heeft dit geen effect op de maximale waarde van z, we stellen dan z=0, of meer formeel: de verandering van z_max = delta(z_max) = 0.
De schaduwprijs SCH, gedefinieerd als y(i) = delta(z_max)/delta(RHZ(i)), of minder formeel , Y(i) = z/RHZ(i), is in dit geval
Y1 = z/RHZ1 = 0/(+oneindig) = 0.

Ofwel:
RHZ1 ↑ : onbeperkt (= +oneindig)
z=0
y1= z/RHZ1= 0/+ oneindig=0
zoals je zelf al aangaf.

Indien je RHZ1 kleiner maakt, kan dit zonder effect op z_max tot delta(RHZ1) = -4.
Merk op dat je dit hierboven ook al uitgerekend had: RHZ1 is 16 en deze mag dalen tot 12 voordat z_max gaat veranderen en RVW1 bindend zou gaan worden.

Dus:
RHZ1 ↓: tot (6,3) RHZ=-4
z=0
y1= z/rhz1=0/-4=0


Nevenvoorwaarde 2

Deze is bindend.
Als we RHZ2 gaan verhogen (= L2 omhoog schuiven), kunnen we dit doen totdat L2 door het snijpunt van L1 en L3 loopt, gaan we nog hoger, dan is NVW2 niet meer bindend en is NVW 1 bindend (ga dit na in je grafiek).
Omdat
L1: y = 8 - 0.5x
L3: y = 21 – 3x
geldt voor het snijpunt:
8 - 0.5x = 21 – 3x
ofwel
x = 26/5 = 5.2
en
y = 21 - 3x = 27/5 = 5.4
Kijk nu naar NVW2: x + y ≤ 9
Indien x=5.2 en y=5.4 zou RHZ2 worden:
x + y ≤ 5.2 + 5.4 = 10.6
waardoor delta(RHZ2) = 10.6 – 9 = 1.6

Vervolgens delta(z_max):
z_max was 30,
de niewe z_max in (5.2, 5.4) = 4*5.2 + 2*5.4 = 31.6
(hier gebruiken we weer: z = 4x + 2y zoals in de opgave gegeven)
Dus:
delta(z_max) = 31.6 – 30 = 1.6
en
y2 = delta(z_max)/delta(RHZ2) = 1.6 / 1.6 = 1.

Samengevat in jouw notatie:
RHZ2 ↑: tot 1∩3 : (26/5,27/5) RHZ2=1.6
z=1,6
y2=z/RHZ2=1,6/1,6=1

Evenzo voor alle andere NVW’s.

[arie]

Bij gevoeligheidsanalyse begrijp ik niet hoe je aan
x = 26/5 = 5.2 en y = 21 - 3x = 27/5 = 5.4 komt
met rekenmachine los ik dit op om gewoon de intersection te zoeken tussen de twee,
maar wat nu als er geen intersection is, daarom wil ik die berekening zeker
begrijpen de rest is heel duidelijk.

In de grafiek kijk je bij de berekening altijd naar de dichtstbijzijnde snijpunten, omdat alleen tot daar onze berekening lineair is (voor delta(z_max) en delta(RHZ(i))).
Omdat NVW2 bindend is, bekijken we wat er met delta(z_max) en delta(RHZ2) gebeurt in het snijpunt van L2 en L3, waar het maximum bereikt wordt.
Als we de gevoeligheid van NVW2 bepalen, dus L2 verschuiven, verschuift dit snijpunt ook over L3.
Schuiven we L2 omhoog, dan is het dichtstbijzijnde andere snijpunt op L3 het snijpunt van L3 met L1, vandaar dat we dit moeten nemen bij verhoging van RHZ2.
Schuiven we L2 omlaag, dan is het dichtstbijzijnde andere snijpunt op L3 het snijpunt van L3 met de x-as, vandaar dat we dit moeten nemen bij verlaging van RHZ2.

Omdat we het maximum op een hoekpunt hebben liggen, zijn er altijd 2 snijdende lijnen, anders was er geen hoekpunt (in dit geval het snijpunt van L2 en L3).

Was er nog een NVW5 met L5 parallel aan L2, dan zijn er 3 situaties:
- L2 = L5, dan is bij verhoging van L2 delta(z_max)=0 omdat NVW5 dan bindend blijft
- L5 ligt boven L2: dan snijden L5 en L3 ook, en kunnen we dat snijpunt berekenen, en dit nemen als dit het eerstvolgende hogere snijpunt met L2 zou zijn
- L5 ligt onder L2: dan was NVW5 en niet NVW2 bindend

Was er nog een NVW5 met L5 parallel aan L3, dan zijn er eveneens 3 situaties:
- L3 = L5, dan zijn zowel NVW3 als NVW5 naar benenden bindend, en kunnen we L2 verhogen tot aan het snijpunt van L1 met L3 = het snijpunt van L1 met L5
- L5 ligt boven L3: dan is NVW5 niet bindend en kan die buiten beschouwing blijven
- L5 ligt onder L3: dan was NVW5 en niet NVW3 bindend

Nu het snijpunt van L1 en L3:
Gegeven:
L1: y = 8 - 0.5x
L3: y = 21 – 3x
Voor het snijpunt geldt dat x_L1 = x_L3 en y_L1 = y_L3, in feite stel je beide vergelijkingen aan elkaar gelijk:
y_L1 = y_L3
dus
y_L1 = 8 - 0.5x = y_L3 = 21 – 3x
8 - 0.5x = 21 – 3x
tel nu 3x bij zowel linker als rechter lid op:
8 + 2.5x = 21
trek 8 van linker en rechter lid af:
2.5x = 13
deel linker en rechter lid door 2.5:
x = 13/2.5 = 26/5 = 5.2
Vul deze waarde van x in 1 van de 2 oorspronkelijke vergelijkingen in en je hebt y:
L1: y = 8 - 0.5 * 5.2 = 5.4
L3: y = 21 - 3 * 5.2 = 5.4
Dit is wat de intersection-functie van je rekenmachine ook doet.

Verder heb ik nog een opmerking.
Hoe kom ik aan deze uitkomsten?

* Bij nevenvoorwaarde 2 staat er bij mij ook:
RHZ2 ↓:tot X∩3: (7,0) RHZ2=-2 (hier is er geen intersection tussen
de twee alleen tussen de x-as en de functie)
z=-2
y2= z/RHZ2=1 (begrijp ik)
Hoe moet ik deze dan oplossen?

De x-as heeft vergelijking:
x-as: y = 0
We hebben dan dus de volgende 2 lijnen:
x-as: y = 0
L3: y = 21 – 3x
met snijpunt:
0 = 21 - 3x
x = 7
en uiteraard y = 0.


Kijk nu naar NVW2: x + y ≤ 9
Indien x=7 en y=0 zou RHZ2 worden:
x + y ≤ 7 + 0 = 7
waardoor delta(RHZ2) = 7 - 9 = -2

Vervolgens delta(z_max):
z_max was 30,
de niewe z_max in (7, 0) = 4*7 + 2*0 = 28
(hier gebruiken we weer: z = 4x + 2y zoals in de opgave gegeven)
Dus:
delta(z_max) = 28 – 30 = -2
en
y2 = delta(z_max)/delta(RHZ2) = (-2)/(-2) = 1.

* Nevenvoorwaarde 3
RHZ3↑: tot X∩2: (9,0) RHZ3=6 (als het gelijkaardig de vorige is,
hoeft u daar geen antwoord op geven)
Z=6
y3=1 (begrijp ik)
RHZ3↓:tot 1∩2:(2,7) RHZ3=-8
z=-8
y3=1
Moet ik bij deze naar NVW 3 kijken?

Voor NVW3 zie je dat het snijpunt van L3 met L2 een hoekpunt vormt van
de feasible region (dit snijpunt levert overigens ook z_max)
RHZ3↑:
We schuiven L3 omhoog, en kijken wat dan het eerstvolgende andere
snijpunt is op L2, dit is inderdaad L2 met de x-as.
RHZ3↓:
We schuiven L3 omlaag, en kijken weer wat dan het eerstvolgende andere
snijpunt is op L2, dit is L2 met L1.



PS: mocht je ooit het snijpunt nodig hebben van de y-as met de lijn
y = a*x + b,
dan geldt voor de y-as: x = 0,
dus voor het snijpunt: y = a*0 + b = b.
Dit snijpunt is dan (0, b).