HOOFDSTUK 1 LP-problemen
1.1 Wat is een LP-probleem?
Basisveronderstellingen
• Proportionaliteit: de bijdrage tot de doelfunctie is proportioneel aan de waarde van de
beslissingsvariabele
• Additiviteit: de bijdrage tot de doelfunctie van elke beslissingsvariabele is onafhankelijk van
de waarden van de andere beslissingsvariabelen
• Deelbaarheid: we werken met continue beslissingsveranderlijken
• Zekerheid: alle coëfficiënten zijn gekend met zekerheid
Haalbaarheidsverzameling = alle punten die voldoen aan de LP-beperkingen en de tekenbeperkingen
Max-probleem: isowinstlijn
Min-probleem: isokostenlijn
Isowinstlijnen (en isokostenlijnen) zijn evenwijdig
Bindende beperking: linkerhandzijde en rechterhandzijde zijn gelijk bij de optimale oplossing
Niet-bindende beperking: linkerhandzijde en rechterhandzijde zijn niet gelijk bij optimale oplossing
Bindende beperkingen karakteriseren de optimale oplossing
Convexe verzameling: elke convexe combinatie (gewogen gemiddelde) van een puntenpaar van S
behoort tot S
De haalbaarheidsverzameling van een LP-probleem is steeds een convexe verzameling
Een extreem punt is een punt in S dat niet kan gereconstrueerd worden als een convexe combinatie
van 2 andere punten in S
Een LP-probleem dat een optimale oplossing heeft, heeft een extreem punt dat optimaal is, en het
aantal extreme punten van de haalbaarheidsverzameling van een LP-probleem is eindig
1.2 Speciale gevallen
Oneindig aantal optimale oplossingen (alternatieve of multipele optimale oplossingen)
Meerdere extreme punten zijn optimaal en ook alle convexe combinaties ervan
1
,Verdere discriminatie tussen deze punten via bijkomende, secundaire data (kies hier (40,0) eenvoud)
Geen haalbare oplossingen (een onmogelijk LP-probleem)
• Haalbaarheidsverzameling is ledig
Het LP-probleem is onbegrensd (er zijn haalbare oplossingen met een oneindig hoge of lage waarde)
1.3 Enkele voorbeelden
MENGPROBLEEM
Sunco Oil mengt 3 types van ruwe olie (O1, O2 en O3) tot 3 types van benzine (B1, B2 en B3):
Andere productievoorwaarden:
– Aanbod past zich aan de vraag aan (productie = vraag)
2
, – Reclame: 1$ reclame voor een type benzine impliceert een extra vraag van 10 vaten
voor dat type
Bijkomende vraag- en technologische beperkingen:
• Technologische beperkingen:
– Een vat olie omzetten in een vat benzine kost $4
– Max 5000 vaten ruwe olie (per type) per dag (inputcapaciteit)
– Max 14000 vaten benzine (in totaal) per dag (outputcapaciteit)
• Vraag:
– Zonder reclame 3000 vaten per dag van B1 (Vraag B1)
– Zonder reclame 2000 vaten per dag van B2 (Vraag B2)
– Zonder reclame 1000 vaten per dag van B3 (Vraag B3)
PRODUCTIEPROCES MODDELEREN
De onderneming Rylon Corporation gebruikt 1 ruwe input voor de productie van 4 parfums/outputs,
waarvan 2 outputs kunnen dienen als (intermediaire) inputs voor 2 andere outputs.
Beslissingsveranderlijken:
• Outputs:
– Regular brute (x1): $7
– Luxury brute (x2): $18
3
, – Regular Chanelle (x3): $6
– Luxury Chanelle (x4): $14
• Input:
– Ruwe materialen (x5): $3 (max. hoeveelheid = 4000)
– (Bewerken van 1 eenheid ruw materiaal kost 1 eenheid laboratoriumkosten, met
maximale hoeveelheid = 6000)
Productievoorwaarden:
• 1 eenheid x5 brengt 3 eenheden x1 en 4 eenheden x3 op
• 1 eenheid x2 vereist 1 eenheid x1, 3 eenheden laboratoriumkosten en $4 bewerkingskosten
• 1 eenheid x4 vereist 1 eenheid x3, 2 eenheden laboratoriumkosten en $4 bewerkingskosten
VOORRAADMODEL
Dynamisch beslissingsprobleem, simultaan beslissen voor verschillende perioden
De zeilboot producerende onderneming Sailco moet zijn optimale productie- en voorraadplanning
(voor 1 jaar; meerdere perioden: per trimester) bepalen onder de volgende voorwaarden:
• Vraag (die steeds is voldaan): trim1: 40; trim2: 60; trim3: 75; trim4: 25
• Initiële voorraad (in trim1): 10
• Productiekost (per eenheid):
– $400 tijdens reguliere arbeidsuren (met max. aantal = 40, per trimester)
– $450 tijdens overuren (onbeperkt)
• Extra voorraadkost (per eenheid):
Bewaarkosten per zeilboot bij overdracht naar volgende trimester: $20
4
1.1 Wat is een LP-probleem?
Basisveronderstellingen
• Proportionaliteit: de bijdrage tot de doelfunctie is proportioneel aan de waarde van de
beslissingsvariabele
• Additiviteit: de bijdrage tot de doelfunctie van elke beslissingsvariabele is onafhankelijk van
de waarden van de andere beslissingsvariabelen
• Deelbaarheid: we werken met continue beslissingsveranderlijken
• Zekerheid: alle coëfficiënten zijn gekend met zekerheid
Haalbaarheidsverzameling = alle punten die voldoen aan de LP-beperkingen en de tekenbeperkingen
Max-probleem: isowinstlijn
Min-probleem: isokostenlijn
Isowinstlijnen (en isokostenlijnen) zijn evenwijdig
Bindende beperking: linkerhandzijde en rechterhandzijde zijn gelijk bij de optimale oplossing
Niet-bindende beperking: linkerhandzijde en rechterhandzijde zijn niet gelijk bij optimale oplossing
Bindende beperkingen karakteriseren de optimale oplossing
Convexe verzameling: elke convexe combinatie (gewogen gemiddelde) van een puntenpaar van S
behoort tot S
De haalbaarheidsverzameling van een LP-probleem is steeds een convexe verzameling
Een extreem punt is een punt in S dat niet kan gereconstrueerd worden als een convexe combinatie
van 2 andere punten in S
Een LP-probleem dat een optimale oplossing heeft, heeft een extreem punt dat optimaal is, en het
aantal extreme punten van de haalbaarheidsverzameling van een LP-probleem is eindig
1.2 Speciale gevallen
Oneindig aantal optimale oplossingen (alternatieve of multipele optimale oplossingen)
Meerdere extreme punten zijn optimaal en ook alle convexe combinaties ervan
1
,Verdere discriminatie tussen deze punten via bijkomende, secundaire data (kies hier (40,0) eenvoud)
Geen haalbare oplossingen (een onmogelijk LP-probleem)
• Haalbaarheidsverzameling is ledig
Het LP-probleem is onbegrensd (er zijn haalbare oplossingen met een oneindig hoge of lage waarde)
1.3 Enkele voorbeelden
MENGPROBLEEM
Sunco Oil mengt 3 types van ruwe olie (O1, O2 en O3) tot 3 types van benzine (B1, B2 en B3):
Andere productievoorwaarden:
– Aanbod past zich aan de vraag aan (productie = vraag)
2
, – Reclame: 1$ reclame voor een type benzine impliceert een extra vraag van 10 vaten
voor dat type
Bijkomende vraag- en technologische beperkingen:
• Technologische beperkingen:
– Een vat olie omzetten in een vat benzine kost $4
– Max 5000 vaten ruwe olie (per type) per dag (inputcapaciteit)
– Max 14000 vaten benzine (in totaal) per dag (outputcapaciteit)
• Vraag:
– Zonder reclame 3000 vaten per dag van B1 (Vraag B1)
– Zonder reclame 2000 vaten per dag van B2 (Vraag B2)
– Zonder reclame 1000 vaten per dag van B3 (Vraag B3)
PRODUCTIEPROCES MODDELEREN
De onderneming Rylon Corporation gebruikt 1 ruwe input voor de productie van 4 parfums/outputs,
waarvan 2 outputs kunnen dienen als (intermediaire) inputs voor 2 andere outputs.
Beslissingsveranderlijken:
• Outputs:
– Regular brute (x1): $7
– Luxury brute (x2): $18
3
, – Regular Chanelle (x3): $6
– Luxury Chanelle (x4): $14
• Input:
– Ruwe materialen (x5): $3 (max. hoeveelheid = 4000)
– (Bewerken van 1 eenheid ruw materiaal kost 1 eenheid laboratoriumkosten, met
maximale hoeveelheid = 6000)
Productievoorwaarden:
• 1 eenheid x5 brengt 3 eenheden x1 en 4 eenheden x3 op
• 1 eenheid x2 vereist 1 eenheid x1, 3 eenheden laboratoriumkosten en $4 bewerkingskosten
• 1 eenheid x4 vereist 1 eenheid x3, 2 eenheden laboratoriumkosten en $4 bewerkingskosten
VOORRAADMODEL
Dynamisch beslissingsprobleem, simultaan beslissen voor verschillende perioden
De zeilboot producerende onderneming Sailco moet zijn optimale productie- en voorraadplanning
(voor 1 jaar; meerdere perioden: per trimester) bepalen onder de volgende voorwaarden:
• Vraag (die steeds is voldaan): trim1: 40; trim2: 60; trim3: 75; trim4: 25
• Initiële voorraad (in trim1): 10
• Productiekost (per eenheid):
– $400 tijdens reguliere arbeidsuren (met max. aantal = 40, per trimester)
– $450 tijdens overuren (onbeperkt)
• Extra voorraadkost (per eenheid):
Bewaarkosten per zeilboot bij overdracht naar volgende trimester: $20
4
