Η απλή περίπτωση
Η συνάρτηση
simplex_reduce κάνει την αναγωγή
με τον αλγόριθμο simplex για την εύρεση :
max(c.x), A.x ≤ b, x ≥ 0, b≥ 0 |
όπου c,x είναι διανύσματα του ℝn, b≥ 0 είναι ένα διάνυσμα του
ℝp και A είναι ένας πίνακας με p γραμμές και n στήλες.
simplex_reduce παίρνει ως όρισμα
A,b,c και
επιστρέφει το
max(c.x), την επαυξημένη λύση του
x
(επαυξημένη επειδή ο αλγόριθμος δουλεύει προσθέτοντας
nrows(A) βοηθητικές
μεταβλητές) και τον ανηγμένο πίνακα.
Παράδειγμα
Βρείτε το
max(X+2Y) όπου | ⎧ ⎪ ⎨ ⎪ ⎩ |
|
Είσοδος :
Έξοδος :
Το οποίο σημαίνει ότι το μέγιστο του
X+2Y κάτω από αυτές τις συνθήκες είναι
7, που προκύπτει θέτοντας
X=1,Y=3
επειδή το
[1,3,0,0] είναι η επαυξημένη λύση και ο ανηγμένος πίνακας είναι ο :
[[0,1,1/5,3/5,3],[1,0,(-1)/5,2/5,1], [0,0,1/5,8/5,7]].
Μια πιο περίπλοκη περίπτωση που ανάγεται στην απλή περίπτωση
Για να καλέσουμε την
simplex_reduce, πρέπει το πρόβλημα να έχει μετασχηματισθεί στην κανονική του μορφή (για περισσότερες λεπτομέρειες δείτε και
http://en.wikipedia.org/wiki/Simplex_algorithm). Δηλαδή πρέπει να έχουν γίνουν τα ακόλουθα :
Για παράδειγμα, βρείτε :
min(2x+y−z+4) όπου | ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ |
|
Αν θέσουμε x=1−X, y=Y+2, z=5−X+3Y τότε το παραπάνω πρόβλημα είναι ισοδύναμο με την εύρεση του ελαχίστου της παράστασης (−2X+Y−(5−X+3Y)+8) όπου :
⎧ ⎪ ⎨ ⎪ ⎩ |
|
το οποίο είναι ισοδύναμο με την εύρεση του ελαχίστου της παράστασης :
(−X−2Y+3) όπου | ⎧ ⎪ ⎨ ⎪ ⎩ |
|
Δηλαδή το πιο σύνθετο πρόβλημα ανάγεται στο να βρούμε το μέγιστο της παράστασης −(−X−2Y+3)=X+2Y−3 κάτω από συνθήκες, που είναι ίδιες με εκείνες της εύρεσης του μεγίστου της παράστασης X+2Y (απλή περίπτωση). Στην απλή περίπτωση η απάντηση ήταν 7, συνεπώς, το αποτέλεσμα εδώ είναι το 7-3=4.
Η γενική περίπτωση
Ένα πρόβλημα γραμμικού προγραμματισμού μπορεί, γενικά, να μην ανάγεται άμεσα στην
απλή περίπτωση όπως παραπάνω. Ο λόγος είναι ότι, πριν την εφαρμογή του αλγορίθμου
simplex,
πρέπει να βρεθεί μια αρχική κορυφή (αρχικό σημείο). Επομένως,
simplex_reduce μπορεί να κληθεί συγκεκριμενοποιώντας αυτήν την αρχική
κορυφή. Στην περίπτωση αυτή, όλα τα ορίσματα, συμπεριλαμβανομένης και της αρχικής
κορυφής, ομαδοποιούνται σε ένα μόνο πίνακα.
Επεξηγούμε αρχικά αυτό το είδος της κλήσης στην απλή περίπτωση όπου για το αρχικό σημείο δεν απαιτείται η επίλυση βοηθητικού προβλήματος. Εάν ο A έχει p γραμμές και n στήλες και αν ορίσουμε :
τότε η εντολή
simplex_reduce μπορεί να κληθεί με το
D σαν το μόνο όρισμα.
Για το προηγούμενο παράδειγμα, εισάγετε :
Εδώ το
C=[[-3,2,1,0,3],[1,1,0,1,4]]
και το
D=[[-3,2,1,0,3],[1,1,0,1,4],[-1,-2,0,0,0]]
Είσοδος :
Έξοδος είναι το ίδιο αποτέλεσμα όπως πριν.
Επανερχόμαστε στην γενική περίπτωση.
Η κανονική μορφή ενός προβλήματος γραμμικού προγραμματισμού είναι ίδια με
την απλή περίπτωση παραπάνω, αλλά με ισότητα Ax=b (αντί Ax≤ b)
και x≥ 0. Μπορούμε επιπλέον να υποθέσουμε ότι b≥ 0
(εάν όχι, μπορούμε να αλλάξουμε το πρόσημο της αντίστοιχης γραμμής).
simplex_reduce
με
μονaδικό όρισμα τον πίνακα που προκύπτει επαυξάνοντας τον A με τον
ταυτοτικό πίνακα, την στήλη b αμετάβλητη και μία επαυξημένη γραμμή
c με 0 κάτω από τον A και 1 κάτω από τον ταυτοτικό).
Εάν το μέγιστο υπάρχει και είναι 0, μας δίνεται και μια λύση x , όπου όλες οι χαλαρές
μεταβλητές είναι 0.
simplex_reduce
με το αρχικό c και τον ανηγμένο πίνακα που βρίσκουμε λύνοντας το πρώτο πρόβλημα παραπάνω.
⎧ ⎨ ⎩ |
|
simplex_reduce([[-1,-1,0,1,1,0,1], [ 0,1,-1,1,0,1,3], [ 0,0, 0,0,1,1,0]])Έξοδος: βέλτιστο=0, λύση x=(0,1,0,2,0,0) όπου οι χαλαρές μεταβλητές=0 (τα δύο μηδενικά στο τέλος του διανύσματος x), και ο ανηγμένος πίνακας
⎛ ⎜ ⎜ ⎝ |
| ⎞ ⎟ ⎟ ⎠ |
simplex_reduce([[-1/2,0,-1/2,1,2], [ 1/2,1,-1/2,0,1], [ 2, 3, -1, 1,0]])Έξοδος: maximum=-5, γι’ αυτό το ελάχιστο του αντίθετου είναι 5, και προκύπτει από την λύση x=(0,1,0,2), μετά την αντικατάσταση x=0, y=1, z=0 και t=2.
Για περισσότερες λεπτομέρειες, ψάξτε στο
google τον
simplex algorithm
.