OpResearch June 23 Solutions

Θέμα 4

α) Έχουμε τον παρακάτω γράφο:

Σε κάθε ακμή σημειώνουμε στην αρχή την "απομένουσα χωρητικότητα", ενώ στο τέλος της ακμής σημειώνουμε το ίδιο αλλά προς την αντίθετη κατεύθυνση (χρησιμοποιείται για να ακυρώσουμε ροές σε περίπτωση που κάνουμε κάποιο λάθος).

Κάθε φορά ψάχνουμε ένα "επαυξάνον μονοπάτι", δηλαδή ένα μονοπάτι με αυστηρά θετική απομένουσα χωρητικότητα σε κάθε ακμή. Ας επιλέξουμε το παρακάτω:

Τώρα βρίσκουμε την μικρότερη απομένουσα χωρητικότητα ροής, δηλαδή min(2,1,1,3)=1, την αφαιρούμε από την κάθε αρχή της ακμής και την προσθέτουμε σε κάθε τέλος της ακμής.

Ο αλγόριθμος σταματάει όταν δεν βρίσκουμε άλλο επαυξάνον μονοπάτι. Συνεχίζουμε με την ίδια λογική:

Εδώ θα αναιρέσουμε την ροή από το 4 προς το 3:

Δεν υπάρχει άλλο επαυξάνον μονοπάτι, άρα τελειώσαμε. Η μέγιστη ροή μπορεί να υπολογιστεί προσθέτοντας όλα τα min που βρήκαμε σε κάθε στάδιο (1+1+2+1+1=6) , ή εναλλακτικά βλέπουμε πχ στον κόμβο s ότι αρχικά είχαμε συνολικά 4+2=6 διαθέσιμη χωρητικότητα, ενώ τώρα έχουμε 0+0=0, άρα η μέγιστη ροή είναι 6-0=6

β) Θεωρούμε ότι η κάθε ακμή έχει τιμή (x_ij), που συμβολίζει την ροή (flow) που έχει εκχωρηθεί από τον κόμβο i στον κόμβο j .

Αρχικά, όλες οι ροές πρέπει να είναι μη-αρνητικές:

(x_ij)≥0

Capacity constraints:

(x_ij)≤d ,∀i,j όπου d είναι το capacity της ροής
π.χ. έχουμε (x_s1)≤4
πάντα κοιτάμε και την φορά των ακμών, π.χ. έχουμε (x_31)≤0

Flow conservation:

Συνολική ροή που μπαίνει σε ένα κόμβο = Συνολική ροή που εξέρχεται από τον ίδιο κόμβο
π.χ. για τον κόμβο 1: (x_s1)=(x_13)+(x_12)
Εξαιρούνται οι κόμβοι s και t !!

Αντικειμενική συνάρτηση:

z=(x_s1)+(x_s4)
ή z=(x_2*t)+(x_3*t)+(x_4*t)