OpResearch Sept 24 Solutions

Άσκηση 1

Αρχικά, θα θεωρήσουμε τις 4 καταστάσεις, ανάλογα με το ιστορικό του πελάτη. Η κάθε κατάσταση S θα είναι ίση με x*y, όπου το x αναφέρεται στην υπάρξη ατυχήματος πριν 2 χρόνια, ενώ το y πριν 1 χρόνο.

π.χ. αν S=x*y=01, τότε υπήρχε ατύχημα πριν 1 χρόνο αλλά όχι πριν 2 χρόνια.

Έχουμε 4 διαφορετικές καταστάσεις, από (S_1) έως (S_4), και οι μεταβάσεις μεταξύ των καταστάσεων είναι οι εξής:

Σύμφωνα με τα παραπάνω, ο transition matrix P είναι ο εξής:

P=[[0.97,0,0.03,0],[0.97,0,0.03,0],[0,0.9,0,0.1],[0,0.9,0,0.1]]

Θεωρούμε ότι οι πιθανότητες να βρεθούμε στην κάθε κατάσταση μετά απο μεγάλο χρονικό διάστημα είναι (π_1)-(π_4), δηλαδή το διάνυσμα με τις πιθανότητες είναι ο π=[[(π_1),(π_2),(π_3),(π_4)]] (steady state probability vector)

Τώρα πρέπει να λύσουμε το σύστημα εξισώσεων {[(π_1)+(π_2)+(π_3)+(π_4)=1],[π*P=π]}, δηλαδή:

{[(π_1)+(π_2)+(π_3)+(π_4)=1],[0.97*(π_1)+0.97*(π_2)=(π_1)],[0.9*(π_3)+0.9*(π_4)=(π_2)],[0.03*(π_1)+0.03*(π_2)=(π_3)],[0.1*(π_3)+0.1*(π_4)=(π_4)]} ={[(π_1)+(π_2)+(π_3)+(π_4)=1],[0.97*(π_2)=0.03*(π_1)],[0.9*(π_3)+0.9*(π_4)=(π_2)],[0.03*(π_1)+0.03*(π_2)=(π_3)],[0.1*(π_3)=0.9*(π_4)]}

{[(π_1)+(π_2)+(π_3)+(π_4)=1],[97/3*(π_2)=(π_1)],[0.9*(π_3)+0.9*(π_4)=(π_2)],[0.03*(π_1)+0.03*(π_2)=(π_3)],[(π_3)=9*(π_4)]}={[(π_1)+(π_2)+(π_3)+(π_4)=1],[97/3*(π_2)=(π_1)],[0.9⋅9*(π_4)+0.9*(π_4)=(π_2)],[0.03⋅97/3*(π_2)+0.03*(π_2)=9*(π_4)],[(π_3)=9*(π_4)]}

{[(π_1)+(π_2)+(π_3)+(π_4)=1],[97/3*(π_2)=(π_1)],[9*(π_4)=(π_2)],[(π_2)=9*(π_4)],[(π_3)=9*(π_4)]}={[(π_1)+(π_2)+(π_3)+(π_4)=1],[97/3*(π_2)=(π_1)],[(π_2)=(π_3)=9*(π_4)]}

{[(π_1)+(π_2)+(π_3)+(π_4)=1],[291*(π_4)=(π_1)],[(π_2)=(π_3)=9*(π_4)]} ={[291*(π_4)+9*(π_4)+9*(π_4)+(π_4)=1],[291*(π_4)=(π_1)],[(π_2)=(π_3)=9*(π_4)]}

{[310*(π_4)=1],[291*(π_4)=(π_1)],[(π_2)=(π_3)=9*(π_4)]}={[(π_4)=1/310],[(π_1)=291/310],[(π_2)=(π_3)=9/310]}

α) το μέσο κόστος ασφάλισης ανά έτος για μεγάλο χρονικό διάστημα υπολογίζεται ως:

400*(π_1)+450*(π_2)+450*(π_3)+550*(π_4)=403.38*€

β) Έστω ψ(i)=E ( χρόνια για να φτάσεις στην κατάσταση (S_1) | (X_0)=i)

Ψάχνουμε στην ουσία το ψ(4)

Οπότε έχουμε:

{[ψ(1)=0],[ψ(2)=1+0.97*ψ(1)+0.03*ψ(3)],[ψ(3)=1+0.9*ψ(2)+0.1*ψ(4)],[ψ(4)=1+0.9*ψ(2)+0.1*ψ(4)]}

με ένα κουμπιουτεράκι βγάζουμε απευθείας

{[ψ(1)=0],[ψ(2)=1.065],[ψ(3)=2.176],[ψ(4)=2.176]}

Άρα ο αναμενόμενος χρόνος είναι ψ(4)=2.176

Άσκηση 2

α) Έχουμε τον ακόλουθο γράφο στον οποίο θα εκτελέσουμε τον αλγόριθμο Dijkstra:

Ο κόμβος s έχει ανατεθεί ως ο current node και είναι permanent (p), ενώ οι υπόλοιποι είναι temporary (t) με απόσταση ∞ από τον s.

Ο τύπος για την χαλάρωση των ακμών είναι (d_j)=min((d_j),(d_i)+(c_i*j)) , όπου (c_i*j) είναι το βάρος της ακμής από τον κόμβο iπρος τον κόμβο j. Άρα έχουμε:

Ο κόμβος a ανατίθεται ως ο current node (και γίνεται permanent) καθώς έχει τη χαμηλότερη απόσταση απ'όλους τους κόμβους. Συνεχίζουμε την ίδια διαδικασία:

Επιλέγουμε ή τον κόμβο h ή τον κόμβο g ως current node. Δεν έχει διαφορά στο τελικό αποτέλεσμα.

Έχουμε ολοκληρώσει τον αλγόρθμο, συμπεριληπτικά έχουμε:

β) Έχουμε τον ίδιο γράφο χωρίς βάρη στις ακμές:

Ο αλγόριθμος του Kruskal είναι πολύ απλός, απλά επιλέγουμε την μικρότερη ακμή κάθε φορά που να μην δημιουργεί κύκλους. Οπότε έχουμε:

Τώρα εδώ προσέχουμε να μην δημιουργήσουμε κανέναν κύκλο. Προσπερνάμε την ακμή 9 και πάμε κατευθείαν στην 10

Τελικά έχουμε:

Άσκηση 3

α) Έχουμε: (λ_1)=6, (μ_1)=12,(λ_2)=12 και (μ_2)=24(θέματα/ώρα)

Τα μοντέλα είναι Μ/Μ/1 (δύο ανεξάρτητα), οπότε από το τυπολόγιο έχουμε:

(L_q1)=((λ_1)2)/((μ_1)*((μ_1)-(λ_1)))=(62)/(12*(12-6))=0.5 άτομα ο μέσος αριθμός ατόμων στην ουρά ιδιωτών

(L_q2)=((λ_2)2)/((μ_2)*((μ_2)-(λ_2)))=(122)/(24*(24-12))=0.5 άτομα ο μέσος αριθμός ατόμων στην ουρά εταιριών

(W_q1)=(λ_1)/((μ_1)*((μ_1)-(λ_1)))=6/(12*(12-6))=0.0833 ώρες = 0.0833⋅60 λεπτά =5 λεπτά ο μέσος χρόνος αναμονής στην ουρά ιδιωτών

(W_q2)=(λ_2)/((μ_2)*((μ_2)-(λ_2)))=12/(24*(24-12))=0.0416 ώρες = 0.0416⋅60 λεπτά =2.5 λεπτά ο μέσος χρόνος αναμονής στην ουρά εταιριών

β) Τώρα έχουμε ένα μοντέλο M/M/2 με (λ_3)=18 και (μ_3)=18 (θέματα/ώρα)

Έχουμε:

(P_0)=[(∑_n=0^1)((((λ_3)/(μ_3))n)/n!)+(((λ_3)/(μ_3))2)/2!⋅1/(1-((λ_3)/(2*(μ_3))))](-1)=[1/1+(λ_3)/(μ_3)+(((λ_3)/(μ_3))2)/2!⋅1/(1-((λ_3)/(2*(μ_3))))](-1)=1/3

(L_q3)=((P_0)((λ_3)/(μ_3))2*(ρ_3))/(2!*(1-(ρ_3))2)

όπου (ρ_3)=(λ_3)/(2*(μ_3))=0.5

άρα (L_q3)=0.5/(3⋅2*(1-0.5)2)=1/3 άτομα ο μέσος αριθμός ατόμων στην ουρά

και (W_q3)=(L_q3)/(λ_3) (από τον νόμο του Little (L_q3)=(λ_3)*(W_q3) ), οπότε

(W_q3)=1/(3⋅18) =1/54 ώρες =1/54⋅60 λεπτά = 1.111 λεπτά ο μέσος χρόνος αναμονής στην ουρά

Αφού μειώσαμε και το (L_q) και το (W_q) , τότε θα προτείναμε στην διεύθυνση το σύστημα (β)

Άσκηση 4

Έχουμε να μεγιστοποιήσουμε (όχι ελαχιστοποιήσουμε, λάθος της εκφώνησης) την z=2*(x_1)+(x_2) υπό τους περιορισμούς

2*(x_1)+(x_2)≤18
-(x_1)+(x_2)≤4
(x_1)-(x_2)≤4
(x_1),(x_2)≥0

Προσθέτουμε τα slack variables για να την φέρουμε σε κανονική μορφή:

z-2*(x_1)-(x_2)=0
2*(x_1)+(x_2)+(s_1)=18
-(x_1)+(x_2)+(s_2)=4
(x_1)-(x_2)+(s_3)=4
(x_1),(x_2),(s_1),(s_2),(s_3)≥0

Τώρα μπορούμε να κατασκευάσουμε το tableau:

Επιλέγουμε την τελευταία γραμμή (R_4) για απαλοιφή Gauss αφού έχει το μικρότερο ratio, οπότε μηδενίζουμε τα πράσινα:

(R_1)←(R_1)+2*(R_4)
(R_2)←(R_2)-2*(R_4)
(R_3)←(R_3)+(R_4)

Επιλέγουμε την (R_2) για απαλοιφή Gauss, οπότε μηδενίζουμε τα παρακάτω:

(R_1)←(R_1)+(R_2)
(R_4)←(R_4)+1/3*(R_2)

Βρήκαμε την βέλτιστη λύση (x_1)=22/3 και (x_2)=10/3

Όμως αν παρατηρήσουμε λίγο τις μη βασικές μεταβλητές (s_1) και (s_3) , θα δούμε ότι η (s_3) έχει συντελεστή 0 στην αντικειμενική συνάρτηση ((R_1)). Αυτό σημαίνει ότι αν την εισάγουμε στην βάση (την κάνουμε βασική μεταβλητή), δεν θα αλλάξει η τιμή της αντικειμενικής συνάρτησης, δηλαδή θα παραμείνει ίση με 18.

Ας την εισάγουμε στην βάση:

Επιλέγουμε την (R_3) για απαλοιφή Gauss, οπότε μηδενίζουμε τα παρακάτω:

(R_2)←(R_2)+2*(R_3)
(R_4)←(R_4)-1/3*(R_3)

Βρήκαμε διαφορετική βέλτιστη λύση, την (x_1)=14/3 και (x_2)=26/3

Όλες οι βέλτιστες λύσεις βρίσκονται επάνω στο ευθύγραμμο τμήμα αυτών των 2 σημείων (δηλαδή έχουμε άπειρες λύσεις). Άρα το σύνολο των λύσεων είναι:

([(x_1)],[(x_2)])=([22/3-1/3*λ],[10/3+2/3*λ]) για 0≤λ≤8

Για να βγει το παραπάνω στην ουσία κάνεις:

{[(x_1)(λ)=(1-λ)⋅22/3+14/3*λ=22/3-(8*λ)/3],[(x_2)(λ)=(1-λ)⋅10/3+26/3*λ=10/3+(16*λ)/3]} για λ∈[0,1]