HS2: Optimalisatieproblemen Flashcards
Wat is het verschil tussen discrete en continue variabelen?
Discrete variabelen kunnen enkel bepaalde waarde in een interval aannemen, dus niet elke waarde in het interval kan worden gebruikt bv. gehele getallen
Continue variabelen kunnen alle waarden in een gegeven interval aannemen bv. Reële getallen
=> In een optimalisatieprobleem kunnen beide tegelijk voorkomen.
Wat is het verschil tussen een lineair en niet-lineair optimalisatieprobleem.
Een lineair optimalisatieprobleem zal een lineaire doelfunctie en lineaire beperkingen hebben. Een niet-lineair optimalisatie probleem zal een macht of wortel hebben in de doelfunctie of beperkingen.
Welke soorten lineaire optimalisatieproblemen zijn er?
Er kan een onderscheidt worden gemaakt tussen lineair probleem met Reële getallen die zal worden opgelost adhv de simplex methode. Daarnaast zijn er de lineaire problemen waarbij alle beslissingvariabelen gehele getallen moeten zijn. Deze worden opgelost adhv de branch and bound methode.
Welke soorten niet-lineaire optimalisatieproblemen zijn er? De speciale gevallen…
Speciale gevallen:
- Mixed Integer Programming (MIP): bevatten zowel gehele als reële variabelen
- Quadratic programming (QP) : doelfunctie of beperkingen bevatten kwadraten, deze problemen kunnen niet met de simplex of branch and bound methode worden opgelost.
Welke is het moeilijkst om op te lossen, LP of ILP? en waarom?
ILP is moeilijker dan LP, dit is contra-intuïtief omdat je minder mogelijke oplossingen hebt. Het is moeilijk omdat tenzij de punten van de simplex methode samenvallen met gehele getallen, er nog verder moet worden gezocht naar de optimale waarde. Afronden zal niet de optimale oplossing garanderen.
Wat is de rekentijd?
De rekentijd is de tijd nodig om tot een oplossing te komen voor het optimalisatieprobleem. Men kan een limiet zetten op de rekentijd of deze kan ongelimiteerd zijn.
Hoe groter een probleem (n = aantal elementen die de het aantal mogelijke oplossingen beinvloedt), hoe langer het neemt om een probleem op te lossen.
Hoe wordt complexiteit onderverdeeld bij optimalisatieproblemen? (3)
Klasse P: verzameling van optimalisatieproblemen waarvoor een polynomiaal exact algoritme bestaat. De rekentijd van dit algoritme stijgt met een polynomiale functie naarmate de grootte van het probleem. (bv. Dijkstra stijgt met n^3).
Klasse NP: Dit zijn optimalisatieproblemen waarvoor geen exact algoritme bestaat met een rekentijd die met minder dan exponentieel stijgt. Er kan wel een algoritme bestaan met een polynomiale rekentijd maar deze is nog niet gevonden. Deze problemen kunnen verhuizen naar klasse P als iemand er een algoritme voor vindt. (exponentiele stijging: 2^n of n!)
Klasse NP compleet: Deze maken deel uit van de klasse NP maar zijn de moeilijkste problemen in NP. Als je een polynomiaal algoritme vindt voor een NP compleet, dan vind je een algoritme voor alle problemen in NP!
1 miljoen euro voor persoon die bewijst dat P = NP of niet gelijk!
Hoe kunnen we deze NP problemen dan toch oplossen?
- Voor de lange rekentijd te reduceren kunnen we gebruik maken van heuristieken.
- Het probleem berust niet op éénduidig te omschrijven voorwaarden.
- Met deze methode kunnen we op een snelle manier tot een goede oplossing komen (niet perse de exacte oplossing). Localsolver is een heuristiek!
Wat zijn de 6 voorbeelden van optimalisatieproblemen gezien in de les?
- Kortste pad probleem [shortest path problem (SPP)]
=> Algoritme van Dijkstra - Minimale overspannende boom [Minimum spanning tree (MST)] =>Algoritme van Prim of Kruskal
- Knapzakprobleem [Knapsack problem]
- Faciliteitslocatieprobleem [facility location problem]
- Handelsreizigersprobleem [traveling salesperson problem]
- Rittenplanningsprobleem [Vehicle routing problem]
Leg het shortest path problem uit.
We hebben een netwerk van punten waar wegen tussen kunnen worden gekozen. Ook is er een beginpunt A en een eindpunt B.
Beslissing: Welke weg moeten we nemen?
Doelfunctie: minimaliseer de afstand/ tijd/kost tussen punt A en B.
Beperkingen:
- De punten in het netwerk,
- In het punt dat je toekomt moet je ook terug vertrekken
- In punt A vertrekken
- In punt B eindigen
=> Algoritme van Dijkstra
Leg het Algoritme van Dijkstra uit.
Exact algoritme om het kortste pad probleem op te lossen.
1. Je vertrekt vanuit het beginpunt A en zet de afstand gelijk aan nul. De naastliggende punten krijgen een waarde oneindig.
- Nu maak je een lijst van alle punten die je bezocht hebt, je voegt steeds 1 punt toe. Nu voor elk omliggend punt de kortste weg zoeken
- We gaan zo alle mogelijke punten af tot we via de kortste weg tot in punt B zijn gekomen.
Toepassing: het internet , maar in elk punt wordt terug het kortste pad berekent door de verandering in het netwerk.
Leg het Minimal spanning tree uit.
We hebben een netwerk van punten waar wegen tussen kunnen worden gekozen. Deze wegen hebben een kost.
Beslissingen: Welke leiding aanleggen en welke niet (binair)?
Doelfunctie: Minimaliseren van de kost
Beperkingen: Er moet minstens 1 leiding in elk punt toekomen.
=> Algoritme van Prim of Kruskal
Algoritme van Prim of Kruskal
Voer de volgende stap zo vaak uit als mogelijk: Kies uit de bogen van graaf G die nog niet werden gekozen, de kortste boog die geen kring vormt met de bogen die reeds werden gekozen.
Met “kortste boog” bedoelt men de boog met het kleinste gewicht. Als er geen kandidaten meer overblijven vormen de geselecteerde bogen de minimaal opspannende boom
Leg het Knapzakprobleem uit.
We hebben een zak met een capaciteit C en een aantal items met een gewicht en een winst.
Beslissing: Welke items nemen we mee en welke niet (binair)
Doelfunctie: Maximaliseer de winst van de items die in de knapzak zitten
Beperkingen: Het gewicht van de meegenomen items mag niet groter zijn dan de capaciteit van de knapzak .
Leg het Faciliteitslocatieprobleem uit.
We hebben een aantal fabrieken/ warehouses en een aantal klanten die beleverd moeten worden door de fabrieken.
Beslissing: Welke fabrieken gaan welke klanten beleveren?
Doelfunctie: Minimaliseren van de transportkosten
Beperkingen: Elke klant moet worden beleverd. Klanten kunnen niet door meerdere fabrieken worden beleverd.
