Summary
Operationeel Onderzoek Samenvatting (HIR) (D0H28A) (16/20)
- Course
- Institution
Samenvatting van alle 6 hoofdstukken van het vak Operationeel Onderzoek gegeven door Roel Leus in Bachelor 3 Handelsingenieur.
[Show more]
Seller
Follow
jan-willemdenys
Content preview
📕Notes
Deel 1: Geheeltallige programmering (IP)
Preemptive Programming: Er bestaat een Hierarchie tijdens de objectieven.
Cutting-plane Algoritme:
Tailing off: Optiamle doelfunctie waarde zal afvlakken naarmate aantal toegevoegde sneden ∞ nadert; laatste x
iteraties geen significante verbetering in de LP-bound.
Branch-and-cut: combinatie branch and bound met cuts.
Snedes zijn sterker als ze meer van de LP-oplossingsruimte wegsnijden.
Gomory Snedes: bewaart alle geheeltallige oplossing.
Maak gomory-snede-equatie enkel van de equatie(s) met fractionele oplossing(en).
Voorbeeld: x1 − 14 s1 + 64 s3 = 3
4 ⇒ ⌊x1 ⌋ + ⌊− 14 s1 ⌋ + ⌊ 64 s3 ⌋ = ⌊ 34 ⌋ ⇒ x1 − s1 + s3 ≤ 0
Niet-nul snedes:
∑ xi ≥ 1 voor alle nonbasic variabelen.
DFJ-Formulering (Subtour Eliminatie): 2 formuleringen zijn even sterk (LP-relaxaties hebben zelfde
oplossingsruimte)
Sterker dan MTZ formulering:
Wordt sneller groter in rekentijd dan MTZ: 2n
∑ x{i,j} ≥ 2 met S ∈ N, 2 ≤ ∣S∣ < ∣N∣
De 2 subtours moeten verbonden zijn met elkaar met minstens 2 ‘links’.
∑ x{i,j} ≤ ∣S∣ − 1 met S ∈ N, 2 ≤ ∣S∣ < ∣N∣
Het aantal links/paden in een cluster moet kleiner zijn ∣S∣ − 1 met S het aantal knooppunten, om zo subtours
te vermijden.
Comb Inequality: Subgraaf met x{1,2} + x{1,3} + x{1,4} + x{2,3} + x{2,5} + x{3,6} ≤ 4
Met 4 het aantal bogen dat ge maximaal kunt gebruiken om een loop/lus te doorlopen.
Subgraaf lijkt op een kam, comb.
MTZ-Formulering: Voor asymmetrische TSP.
Zwakker dan DF J .
u3 ≥ u2 + 1 − M(1 − x23 )
u4 ≥ u3 + 1 − M(1 − x34 )
u2 ≥ u4 + 1 − M(1 − x42 )
Notes 1
, Als er een pijl is tussen 4 en 2 ⇒ x42 ; dan moet u2 groter zijn dan u4 +1
Als er geen pijl is tussen 4 en 2 ⇒ x42 ; dan is u2 vrij, (moet groter zijn dan −M ) met M groot.
Deel 2: Combinatorische Optimalisatie (Dynamische
Programmering)
Kortste pad vanuit één knooppunt naar alle andere:
Langste pad doorheen G(N, A) = Kritiekste pad:
Earliest Start (ES): Voorwaarste DP
Latest Start (LS): Achterwaartse DP
( )
ES
LS
DP-recursie: Als G acyclisch
Achterwaarts (DP recursie):
T ijdscomplexiteit : O(m)
f(i) = waardefunctie (afstand van node(i) tot node(9))
Initialisatie : f(9) = 0; f(8) = 7; f(7) = 4; f(6) = 5
f(5) = min(2 + f(8); 6 + f(7)) = min(9; 10) = 9
f(4) = min(4 + f(7); 1 + f(6)) = min(8; 6) = 6
f(2) = min(2 + f(5); 4 + f(4)) = min(11; 10) = 10
f(3) = 3 + f(5) = 12
f(1) = min(3 + f(3); 5 + f(2)) = min(15; 15) = 15
Voorwaarts (DP):
Notes 2
, f(i) = waardefunctie (afstand van node(i) tot node(1))
Initialisatie : f(1) = 0
f(2) = 5; f(3) = 3
f(5) = min{f(3) + 3; f(2) + 2}
...
Gevraagd : f(9) = min{f(8) + 7; f(7) + 4; f(6) + 5}
Dijkstra: wel cycli
Rekentijd/Tijdscomplexiteit: O(n²) :
O(n x n) : checken in elke iteratie of de getallen kleiner zijn.
+O(m) : Elk van de pijlen gaat maar 1x gebruikt worden
Iteratie 1 2 3 4 5 6
0 0* Infinity Infinity Infinity Infinity Infinity
1 0* 5 3* Infinity Infinity Infinity
2 0* 5* 3* Infinity 6 Infinity
3 0* 5* 3* 9 6* Infinity
4 0* 5* 3* 9 6* Infinity
5 0* 5* 3* 9* 6* Infinity
6 0* 5* 3* 9* 6* 10*
7 0* 5* 3* 9* 6* 10*
8 0* 5* 3* 9* 6* 10*
Met i∗ = permanent gemaakt.
Ge gaat altijd verder van de node die net permanent gemaakt is.
Als ge een waarde vind voor node(i) bij iteratie j die groter is dan bij iteratie j − 1, dan laat ge de kleinste
waarde staan.
Bellman-Ford: Opsporen negatieve Lus
Notes 3
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller jan-willemdenys. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $10.81. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
64438 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now