Resume
Samenvatting basismodellen uit operationeel onderzoek 14/20
- Cours
- B-KUL-D0W22A
- Établissement
- Katholieke Universiteit Leuven (KU Leuven)
Samenvatting basismodellen uit operationeel onderzoek
[Montrer plus]
1 vérifier
Par: louiselegrand123 • 10 mois de cela
Aperçu du contenu
Basismodellen uit operationeel onderzoekOpbouw van de cursus
- Doelstelling van de cursus: wiskundige optimaliseringsproblemen oplossen en analyseren
o Lineaire programmering en de simplexmethode
▪ Hoofdstuk 3, 4 en 5/ deel 1, 2 en 3
o Niet-lineaire programmering
▪ Hoofdstuk 11/ deel 4
o Veel voorkomende typeproblemen
▪ Hoofdstuk 7,8 en 9 / deel 5,6 en 7
Inleiding tot het operationeel onderzoek
1. Inleiding
A. Wat is OR?
- Operationeel onderzoek / operationele research (OR)
o = Een wiskundige ondersteuning voor beslisssingen bij praktijkproblemen
o Onderzoek kan gedaan worden via gebonden of ongebonden
optimalisering
o Voorbeelden:
▪ Productieplanning
▪ Dieet
▪ Samenstelling portfolio
2. Een inleiding op LP
A. Wat is een LP problem?
- Een probleem waarbij
o Een lineaire doesltelling geoptimaliseerd (maximum of minimum) wordt
o Onder lineaire beperkingen (technoligische beperkingen,
vraagbeperkingen)
o En waarbij met elke beslissingvariable een tekenbeperking geassocieerd is
(bv. mag niet negatief zijn)
- Beslssingsvariabelen (⇒ moeten voldaan zijn opdat een LP een realsitisch
voorstelling biedt van het beslissingsprobleem)
1) Proportionaliteit
• De bijdrage tot de doelfunctie (=functie die de optimalisatie
voorsteld) van elke beslissingvariabele is proportyioneel aan de
waarde van de beslissingsvariabele
o bv. De bijdrage van 4 geproduceerde eenheden is 4 keer de
bijdrage van 1 geproduceerd eenheid
, Analoog: de bijdrage van elk beslissingsvariabele van een beperking
•
(technologiscg, vraag,…) is proportioneel tot de waarde van de
beslissingswaarde
2) Additiviteit
• De bijdrage tot de doelfunctie van elke beslissingsvariabele is
onafhankelijk van de andere beslissingsvariabelen
o M.a.w. je kan de beslissingsvariabelen optellen
• Analoog: de bijdrage van elke beslissingsvariabele van een
beperking is onafhankelijk van de waarden van de andere
beslissingsvariabelen
3) Deelbaarheid
• We werken met continue beslissingsveranderlijken
• Probleem: vaak niet realistisch om enkel gehele getallen uit te
komen, daarom ronden we niet-gehele uitkomsten af.
4) Zekerheid
• Alle coëfficiënten zijn gekend met zekerheid
o Soorten coëfficiënten
▪ Doelfunctiecoëfficiënten: bijdragen tot de doelfunctie
▪ Technologische coëfficiënten: bijdragen tot linkerzijde
van de vergelijking
- Haalbaarheidsverzameling
o De verzameling van alle punten die voldoen aan de LP-verzameling en de
tekenbeperking
- Optimale oplossing
o Voor een maximaliseringsprobleem/minimaliseringsprobleem, is de optimale
oplossing het punt in de haalbaarheidsverzameling met de hoogste/laagste
doelfunctiewaarde
o Manieren de optimale oplossing te berekenen:
▪ Grafisch
▪ Procedureel
▪ Software
B. Grafische oplossing van een maximaliseringsprobleem met 2 variabelen
- Haalbaarheidsverzameling
o Door een vergelijking van de rechte van de beperking op te stellen
bekomen we een gedeelte op de grafiek die:
▪ Haalbaar is (gebied onder de rechte)
, ▪ Niet-haalbaar is (gebied boven de rechte)
- Optimum
o We kunnen het optimum berekenen aan de hand van isowinstlijnen of
isokostlijnen
▪ Isowinstlijn: Maximaliseringsprobleem (= opbrengsten optimaliseren)
▪ Isokostenlijn: Minimaliseringsprobleem (= kosten optimaliseren)
o Deze isowinstlijnen en isokostenlijn zijn evenwijdig
▪ De vergelijking van deze lijn wordt afgeleidt uit de doelfunctie z
▪ De zien in die vergelijking dat enkel de interecept afhankelijk is van z en
de hellingsgraad dus niet verandert bij een aanpassing
⇒ M.a.w. de isowinstlijnen en isokostlijnen zijn altijd evenwijdig
o Het optimum is de dat punt in de haalbaarheidsverzameling dat
geassocieerd is met de hoogste isowinstlijn of de laagste isokostlijn
Voorbeeld van een LP-probleem
, Onthoud:
Iso-winstcurve = niveaucurve
Alle iso-winstcurves (‘niveaucurves’) lopen evenwijdig
Hoe tekenen we een iso-winstcurve?
Neem een willekeurig punt (𝑥1, 𝑥2) in de oplossingsruimte en bereken de bijhorende z-waarde (‘winst’)!
bv. Als we het punt (4 , 0) nemen, dan is de bijhorende z-waarde (‘winst’) gelijk aan 12. Het punt (4 , 0)
ligt dus op de iso-winstcurve 𝑧 = 3x1 + 2x2 = 12
We kunnen dit herschrijven naar 𝑥2 = z/2 – 3/2 x1 .
De richtingscoëfficiënt is dus 3/2. We kunnen deze iso-winstcurve bijgevolg tekenen.
Omdat alle iso-winstcurves van de vorm 3x1 + 2x2 = 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡𝑒 zijn, hebben alle iso-winstcurves dezelfde
richtingscoëfficiënt. Dit betekent dat we alle iso- winstcurves kunnen vinden door eenvoudigweg de
reeds getekende iso-winstcurve evenwijdig te verschuiven.
Elementaire begrippen
- Bindende beperkingen
o De linkerzijde en rechterzijde van de bperkingen zijn gelijk bij de optimale oplossing
- Niet-bindende beperkingen
o De linkerzijde en rechterzijde van de bperkingen zijn ongelijk bij de optimale oplossing
Bij ons voorbeeld: (1) en (2) zijn bindend, (3) niet-bindend
- Convexe verzameling
o Een verzameling S is covex als het lijnsegment dat éénder welk puntenpaar AB in S
verbindt ook volledig tot de verzameling S behoort
▪ We zien dus ook dat de haalbaarheidsverzameling van een LP probleem steeds
een convexe verzameling is
o Een extreempunt of hoekpunt
▪ Voor een convexe verzameling S is een punt P een extreem punt als elk
lijnsegment dat volledig in S ligt en het punt P omvat, P als eindpunt heeft
▪ M.a.w. een extreem punt P is een punt in S dat niet kan gereconstueerd worden
als een convexe combinatie van 2 andere punten in S
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 juliettevandeghinste. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour €4,49. Vous n'êtes lié à rien après votre achat.
Peut-on faire confiance à Stuvia ?
4.6 étoiles sur Google & Trustpilot (+1000 avis)
72042 résumés ont été vendus ces 30 derniers jours
Fondée en 2010, la référence pour acheter des résumés depuis déjà 14 ans