1.Lineaire programmering (H3-4-5)
Inleiding op een LP-probleem
Bepalen van de optimale oplossing grafisch (H3)
Maximaliseringsprobleem met 2 variabelen
Minimaliseringsprobleem met 2 variabelen
Speciale gevallen
Alternatieve optimale oplossingen (oneindig)
Onmogelijk LP-probleem
Onbegrensd LP-probleem
Voorbeelden met meerdere beslissingsvariabelen
Dieetprobleem
Mengprobleem
Productieproces modelleren
Voorraadmodel
Bepalen van de optimale oplossing procedureel (H4)
Standaardformatie
Simplex algoritme inleiding
Matrixnotatie
Basis en niet-basisvariabelen (BV & NBV)
Haalbare / toelaatbare basisoplossingen (BFS)
Simplex algoritme
Voor maximaliseringsprobleem
standaardformatie
Rij 0 versie
Canonieke vorm 0,1,2,…
1
, Simplex tableau
Ratio test (ingaande en uitgaande NBV/BV)
Pivot rij
Voor minimaliseringsproblemen -> min. omzetten in max.
M-techniek (penaliseringsmethode) (-> voor >/=)
Goal programming (afweging maken bij ledige verzameling)
Pre-emptive goal programming
Bepalen van de optimale oplossing software (Lindo, Excel Solvare) (H5)
Gevoeligheidsanalyse
Grafisch
Doelfunctiecoëffiënt wijzigen
RHS beperking wijzigen
Schaduwprijs inleiding
Computer
Interpretatie computer-output
Schaduwprijzen (shadowprices/dualprices)
Dualiteit
Van primaal normaal max. probleem naar duaal normaal min. probleem
Van primaal normaal min. Probleem naar duaal normaal max. probleem
Geheeltallige programmering (GP) (H9)
LP relaxatie
Enumeratie
GP problemen van 0-1 variabelen
Knapzakproblemen
Vaste kosten
Magazijnvestigingsproblemen
Partitieproblemen
Overdekkingsproblemen
Branch & bound methode
Puur GP
Gemengd GP
0-1 GP
4
,1. Lineaire Programmering
Inleiding op een LP-probleem
Beslissingsvariabelen: de onbekende beslissingen die moeten gemaakt worden (bvb. Aantal van x1?)
Doelfunctie: deze willen we zo groot (maximaliseringsprobleem) of zo klein
(minimaliseringsprobleem) mogelijk krijgen
Lineair: moet een som of aftrekking zijn (-> geen vermenigvuldiging van de variabelen) EN moet </=
of = of >/= zijn -> niet < of > lineaire functie
LP-probleem: optimeren onder voorwaarden, gebonden optimeringsprobleem waarbij alle functies
lineair zijn en waarbij elke beslissingsveranderlijke al dan niet met een tekenbeperking geassocieerd
is (-> niet negatief of onbeperkt in teken). ; doelfunctie met beperkingen
Oplossen LP-probleem:
1) bepaal de beslissingsveranderlijken
2) formuleer de doelstelling (winst = opbrengst – kost) en beperkingen
S.t. : onder voorwaarde dat
Tekenbeperking: wijst op geen negatieve output mogelijk
Basisveronderstellingen betreffende beslissingsvariabelen: deze voorwaarden moeten voldaan zijn
opdat LP een realistische voorstelling biedt van het beslissingsprobleem.
Proportionaliteit: bijdrage doelfunctie is proportioneel aan de waarde van de
beslissingsvariabele; als de productie met x stijgt, zal de output met x stijgen -> elk product
vraagt 4 min tijd onafhankelijk van het aantal producten elk product levert dus constante
winst op
Additiviteit: onafhankelijkheid van beslissingsvariabele x1 en x2, je kunt optellen
Divisibiliteit: deelbaarheid; x1 en x2 kunnen eender welke fractionele waarde aannemen
(halve kan) maar vaak niet realistisch (0=NEE en 1=JA -> wat indien 0,5??)
dus geheeltalligheid vereisen -> voorwaarde van Giopetto
Zekerheid: alle coëfficiënten zijn gekend met zekerheid; doel is zeker, verkoop is zeker (->
wel moeilijk)
Geheeltallig = integer programmeringsprobleem
Haalbaarheidsverzameling: verzameling van alle punten die voldoen aan de LP- en tekenbeperkingen
Optimale oplossing: beste haalbare punt (max -> hoogste doelfunctiewaarde, min -> laagste
doelfunctiewaarde)
NU: bepalen van de optimale oplossing grafisch, procedureel en software
5
,Bepalen van de optimale oplossing grafisch
Maximaliseringsprobleem met 2 variabelen
-> Haalbaar: onder de rechte (of op)
Lijnen die alle punten omvatten met een zelfde doelfunctiewaarde; bij max-probleem = isowinstlijn :
bij min-probleem = isokostenlijn -> zoek dus punt in haalbaarheidsverzameling met hoogste/laagste
isowinstlijn/isokostenlijn.
Bindende beperking: LHS en RHS van de beperking zijn gelijk bij de optimale oplossing -> geen
overschot/tekort -> alles produceren
Niet-bindende beperking: LHS en RHS van de beperking zijn niet gelijk bij de optimale oplossing
Convexe verzameling: verzameling is convex als een lijnsegment dat éénder welk puntenpaar in de
verzameling verbindt (= convexe combinatie) ook volledig in deze verzameling ligt de
haalbaarheidsverzameling van een LP probleem is steeds een convexe verzameling (met eindig aantal
extreme punten)
Extreem punt of hoekpunt: kan niet tussen een convexe combinatie liggen -> steeds een hoekpunt
optimale oplossing is steeds een extreem punt
-> Optimale oplossing op snijpunt van rechten van 2 bindende beperkingen
Minimaliseringsprobleem met 2 variabelen
-> haalbaar: boven de rechte (of op) -> haalbaarheidsverzameling onbegrensd ( niet gelijk aan een
onbegrensd LP probleem)
Doelfunctiewaarde: kost x1 . aantal x1 + kost x2 . aantal x2
Afvragen of de impliciete basisveronderstellingen realistisch zijn? -> telkens probleem
Indien de isolijn verschoven wordt zal deze terecht komen op een lijnstuk van de
haalbaarheidsverzameling -> oneindig veel optimale punten met meerdere extreme punten (2) die
optimaal zijn (-> alle convexe combinaties van deze extreme punten zijn dus ook optimaal) -> al deze
combo’s zijn in principe even goed -> verdere discriminatie (omwille van bvb. Eenvoud)
Onmogelijk LP-probleem
Indien de haalbaarheidsverzameling leeg is (= onmogelijk om te voldoen aan alle beperkingen) -> valt niet op te
lossen, geen optimum
6
,Onbegrensd LP-probleem
Haalbare punten die corresponderen met een oneindig hoge/lage waarde voor de doelfunctie ->
doelfunctie onbegrensd -> optimum onbepaald -> de isolijnen kunnen oneindig verschoven worden
en nog steeds binnen de haalbaarheidsverzameling blijven oplossingswaarde = oneindig
Dus 4 mogelijkheden van optimale oplossing UNIEK (max. en min.), ONEINDIG, ONBEGRENSD,
ONMOGELIJK
Voorbeelden met meerdere beslissingsvariabelen
Dieetprobleem
Dagelijkse behoefte tegen minimale kost
-> meerdere beslissingsvariabelen dus oplossen via simplex methode
Mengprobleem
Optimale winst bepalen in termen van de geproduceerde producten die omgezet worden in een
nieuw product. Input -> output
Maximaliseren -> opbrengst – kost
Productieproces modelleren
Output als finaal goed: kan rechtstreeks verkocht worden -> het eindproduct
Output als intermediair goed: wordt gebruikt als input voor een ander product
Maximaliseren: opbrengst – kost (intermediaire kost en materiele kost)
Voorraadmodel
Dynamisch beslissingsprobleem -> t heeft invloed op t+1
-> veel variabelen -> per tijd en per product -> ook de voorraden per tijd en product
Eindvoorraad periode = Beginvoorraad (= eindvoorraad van vorige periode) + geproduceerd –
gebruikt (= de vraag)
7
,Bepalen van de optimale oplossing procedureel (H4)
Standaardformatie
Standaardformatie = Ongelijkheidsbeperkingen worden omgezet in gelijkheidsbeperkingen dmv:
- slackvariabelen (tekort) -> bij “<” -> + S -> “S” capteert het verschil tussen links en rechts
- excess variabelen (overschot) -> bij “>” -> - e
-> S1 -> 1 stemt overeen met de eerste beperking van een LP-probleem
Simplex algoritme inleiding
Matrixnotatie
Meer onbekenden/variabelen (=n) dan vergelijkingen/beperkingen (=m) -> matrixnotatie: Ax = b
Voorwaarde: n >/= m
- M = n -> exact 1 oplossing
- M < n -> minstens ‘n-m’ NBV
- M > n -> strijdige beperkingen
Wij gaan er in onze context dus altijd van uit dat 𝑚 ≤ 𝑛. Vermits we in standaardvorm al m
beperkingen hebben, hebben we er nog maar (𝑛 − 𝑚) bijkomende nodig om tot een uniek punt te
komen.
Basis en niet-basisvariabelen (BV & NBV)
Basisoplossing: oplossing van dit stelsel wanneer juist ‘n-m’ variabelen op nul gesteld worden
Basisvariabelen (BV): de ‘n-m’ variabelen die niet nul zijn
Niet-basisvariabelenv (NBV): de ‘n-m’ variabelen die nul zijn
-> niet elk systeem van n variabelen en m vergelijkingen heeft een basisoplossing
Een basisoplossing voor 𝑨𝒙 = 𝒃 kunnen we vinden door (𝒏 − 𝒎) variabelen (nietbasisvariabelen of
NBV) te kiezen en deze gelijk te stellen aan 0. Daarna zoeken we de waarde van de resterende 𝒏 − (𝒏
− 𝒎) = 𝒎 variabelen (basisvariabelen of BV) die voldoen aan 𝑨𝒙 = 𝒃. Elke basisoplossing voor 𝑨𝒙 = 𝒃
die we zo vinden is een toelaatbare basisoplossing (TBO) als alle variabelen groter dan of gelijk aan 0
zijn.
Haalbare / toelaatbare basisoplossingen (BFS)
Haalbare / toelaatbare basisoplossingen = ‘basic feasible solution’ = BFS: is een basisoplossing
waarbij alle variabelen niet-negatief zijn -> wanneer 1 variabele negatief is in de basisoplossing dan is
deze oplossing niet haalbaar
8
, -> een extreem punt van de haalbaarheidsverzameling van een LP, is steeds een haalbare
basisoplossing (BFS) -> dus alle variabelen in een extreem punt zijn positief
Elk LP met een optimale oplossing heeft een optimale BFS -> het volstaat om te kijken naar de
eindige verzameling van BFS (=> of extreme punten) voor het stelsel Ax=b om het optimum van het
LP probleem op te lossen
Aanliggende BFS: 2 BFS zijn aanliggend als ze een zelfde factor hebben die verschillend is van nul
(NBV) en een BV en NBV omgewisseld zijn -> ze hebben grafisch éénzelfde lijnsegment
In principe, kunnen we alle toelaatbare basisoplossingen van een LP opstellen en dan de toelaatbare
basisoplossing kiezen met de grootste z-waarde om de optimale toelaatbare basisoplossing te
vinden. Probleem: Zelfs kleine LP’s hebben een groot aantal toelaatbare basisoplossingen!
Oplossing: In plaats van alles te enumereren (‘brute-forcen’) gaan we verstandig te werk met het
simplex-algoritme.
Simplex algoritme
Simplex algoritme = een eindige en efficiënte procedure om snel tot optimale oplossing te komen
(bij meerdere beslissingsvariabelen) -> begint met een toelaatbare basisoplossing en probeert dan
aan de hand van aanliggende BFS betere oplossingen te vinden
-> indien de beperkingen </= zijn dan gebruiken we het simplex algoritme, indien er minstens 1
keer ‘>/=’ of ‘=’ staat dan gebruiken we de Big M methode of de Two-Phase Simplex methode
Voor maximaliseringsprobleem
1. Zet doelfunctie om in Rij 0 versie en LP om in standaardformaat (-> naar gelijkheid met +S en -e)
2. Vind een BFS voor het LP -> converteer LP naar canonieke vorm en simplextableau + Als de
rechterkant van het LP in canonieke vorm overal niet negatief is, dan kunnen we een toelaatbare
basisoplossing zo aflezen
3. Bepaal of deze optimaal is Toelaatbare basisoplossing is optimaal als er in rij 0 geen niet-
basisvariabelen zijn met negatieve coëfficiënten. In zo’n geval kunnen we ‘z’ niet meer verhogen
door één van die NBV-variabelen in de basis te brengen
4. Zoniet, vind dan een aanliggende BFS met hogere doelfunctiewaarde (-> BV en NBV omwisselen
om beter te vinden) Pivoteren totdat we een optimale toelaatbare basisoplossing hebben
gevonden -> welke wisselen bepalen we adhv de ratio test
5. Een nieuw simplex tableau door elementaire rijoperaties (ERO’s):
-> ingaande BV krijgt waarde 1 in de pivot rij en waarde 0 in de andere rijen
-> de pivot rij delen door de coëfficiënt van de ingaande BV in de pivotrij
-> de ingaande BV vervangen door de nieuwe pivot rij in ELKE rij
Rij 0 versie
Oorspronkelijke versie: z = c1x1 + c2x2 +….
Rij 0 versie: 0 = z – c1x1 – c2x2 - ….
9
Les avantages d'acheter des résumés chez Stuvia:
Qualité garantie par les avis des clients
Les clients de Stuvia ont évalués plus de 700 000 résumés. C'est comme ça que vous savez que vous achetez les meilleurs documents.
L’achat facile et rapide
Vous pouvez payer rapidement avec iDeal, carte de crédit ou Stuvia-crédit pour les résumés. Il n'y a pas d'adhésion nécessaire.
Focus sur l’essentiel
Vos camarades écrivent eux-mêmes les notes d’étude, c’est pourquoi les documents sont toujours fiables et à jour. Cela garantit que vous arrivez rapidement au coeur du matériel.
Foire aux questions
Qu'est-ce que j'obtiens en achetant ce document ?
Vous obtenez un PDF, disponible immédiatement après votre achat. Le document acheté est accessible à tout moment, n'importe où et indéfiniment via votre profil.
Garantie de remboursement : comment ça marche ?
Notre garantie de satisfaction garantit que vous trouverez toujours un document d'étude qui vous convient. Vous remplissez un formulaire et notre équipe du service client s'occupe du reste.
Auprès de qui est-ce que j'achète ce résumé ?
Stuvia est une place de marché. Alors, vous n'achetez donc pas ce document chez nous, mais auprès du vendeur mariedebode. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour €15,49. Vous n'êtes lié à rien après votre achat.
