Παραδείγματα Επίλυσης ΠΓΠ με τη Μέθοδο Simplex
ΠΑΡΑΔΕΙΓΜΑ 1
Να λυθεί το παρακάτω ΠΓΠ με τη μέθοδο Simplex:
ΥΤΠ:
4·Χ1 + Χ2 ≤ 28
2·Χ1 + 3·Χ2 ≤ 24
Χ1, Χ2 ≥ 0
ΑΣ:
Να μεγιστοποιηθεί το: P = 10·Χ1 + 5·Χ2
ΛΥΣΗ:
Α) Διαπιστώνουμε ότι το μοντέλο είναι πρόβλημα μεγιστοποίησης σε τυποποιημένη μορφή (όλοι οι περιορισμοί είναι ≤ θετικών αριθμών και τα Χi θετικά), οπότε μπορούμε να ακολουθήσουμε τη διαδικασία που περιγράψαμε νωρίτερα:
Β) Δημιουργούμε το Αρχικό Σύστημα Simplex (οι περιορισμοί συμπληρώνονται με μεταβλητές περιθωρίου Si, και η ΑΣ γράφεται = 0):
4·Χ1 + Χ2 + S1 = 28
2·Χ1 + 3·Χ2 + S2 = 24
-10·Χ1 - 5·Χ2 + P = 0
Γ) Από το Αρχικό Σύστημα δημιουργούμε τον Αρχικό Πίνακα Simplex (που περιέχει την αρχική βασική εφικτή λύση, για Χi =0 & με βασικές μεταβλητές τις Si, P):
| β.μ. | Χ1 | Χ2 | S1 | S2 | P | |
| S1 | 4 | 1 | 1 | 0 | 0 | 28 |
| S2 | 2 | 3 | 0 | 1 | 0 | 24 |
| P | -10 | -5 | 0 | 0 | 1 | 0 |
Δ) Εκτελούμε τη 1η επανάληψη της Simplex:
1. Επιλέγουμε την εισερχόμενη μεταβλητή (οδηγό στήλη) & την εξερχόμενη από τις β.μ. (οδηγό γραμμή).
| β.μ. | Χ1 | Χ2 | S1 | S2 | P | ||
| S1 | 4 | 1 | 1 | 0 | 0 | 28 | 28/4 = 7 |
| S2 | 2 | 3 | 0 | 1 | 0 | 24 | 24/2 = 12 |
| P | -10 | -5 | 0 | 0 | 1 | 0 |
2. Διαιρούμε την οδηγό γραμμή με το οδηγό στοιχείο (για να το κάνουμε 1).
| β.μ. | Χ1 | Χ2 | S1 | S2 | P | |
| S1 | 1 | ¼ | ¼ | 0 | 0 | 7 |
| S2 | 2 | 3 | 0 | 1 | 0 | 24 |
| P | -10 | -5 | 0 | 0 | 1 | 0 |
3. Αφαιρούμε την οδηγό γραμμή από τις άλλες γραμμές (για να γίνουν 0 τα υπόλοιπα στοιχεία της οδηγού στήλης).
| β.μ. | Χ1 | Χ2 | S1 | S2 | P | |
| S1 | 1 | ¼ | ¼ | 0 | 0 | 7 |
| S2 | 0 | 5/2 | - ½ | 1 | 0 | 10 |
| P | 0 | - 5/2 | 5/2 | 0 | 1 | 70 |
4. Τοποθετούμε την εισερχόμενη μεταβλητή στη θέση της εξερχόμενης και διαβάζουμε τη λύση στη τελευταία στήλη.
| β.μ. | Χ1 | Χ2 | S1 | S2 | P | |
| Χ1 | 1 | ¼ | ¼ | 0 | 0 | 7 |
| S2 | 0 | 5/2 | - ½ | 1 | 0 | 10 |
| P | 0 | - 5/2 | 5/2 | 0 | 1 | 70 |
5. Ελέγχουμε αν η λύση, Χ1 = 7, Χ2 = 0, και P = 70, είναι η βέλτιστη (δηλ., αν στη γραμμή του Ρ υπάρχουν αρνητικές ποσότητες). Εφόσον υπάρχουν (-5/2) προχωρούμε στην επόμενη επανάληψη.
Ε) Εκτελούμε τη 2η επανάληψη της Simplex:
1. Επιλέγουμε την εισερχόμενη μεταβλητή (οδηγό στήλη) & την εξερχόμενη από τις β.μ. (οδηγό γραμμή).
| β.μ. | Χ1 | Χ2 | S1 | S2 | P | ||
| Χ1 | 1 | ¼ | ¼ | 0 | 0 | 7 | 7/¼ = 28 |
| S2 | 0 | 5/2 | - ½ | 1 | 0 | 10 | 10/(5/2) = 4 |
| P | 0 | - 5/2 | 5/2 | 0 | 1 | 70 |
2. Διαιρούμε την οδηγό γραμμή με το οδηγό στοιχείο (για να το κάνουμε 1).
3. Αφαιρούμε την οδηγό γραμμή από τις άλλες γραμμές (για να γίνουν 0 τα υπόλοιπα στοιχεία της οδηγού στήλης).
4. Τοποθετούμε την εισερχόμενη μεταβλητή στη θέση της εξερχόμενης και διαβάζουμε τη λύση στη τελευταία στήλη.
| β.μ. | Χ1 | Χ2 | S1 | S2 | P | |
| Χ1 | 1 | 0 | 6/20 | -2/20 | 0 | 6 |
| Χ2 | 0 | 1 | -1/5 | 2/5 | 0 | 4 |
| P | 0 | 0 | 2 | 1 | 1 | 80 |
5. Ελέγχουμε αν η λύση, Χ1 = 6, Χ2 = 4, και P = 80, είναι η βέλτιστη (δηλ., αν στη γραμμή του Ρ υπάρχουν αρνητικές ποσότητες). Εφόσον δεν υπάρχουν αρνητικοί αριθμοί στο Ρ, η διαδικασία της Simplex έχει τελειώσει και η λύση είναι η βέλτιστη.
ΠΑΡΑΔΕΙΓΜΑ 2
Να λυθεί το παρακάτω ΠΓΠ με τη μέθοδο Simplex:
ΥΤΠ:
3·Χ1 + 4·Χ2 + Χ3 ≤ 2
Χ1 + 3·Χ2 + 2·Χ3 ≤ 1
Χ1, Χ2, Χ3 ≥ 0
ΑΣ:
Να μεγιστοποιηθεί το: P = 3·Χ1 + 6·Χ2 + 2·Χ3
ΛΥΣΗ:
Α) Διαπιστώνουμε ότι το μοντέλο είναι πρόβλημα μεγιστοποίησης σε τυποποιημένη μορφή (όλοι οι περιορισμοί είναι ≤ θετικών αριθμών και τα Χi θετικά), οπότε μπορούμε να ακολουθήσουμε τη διαδικασία που περιγράψαμε νωρίτερα:
Β) Δημιουργούμε το Αρχικό Σύστημα Simplex (οι περιορισμοί συμπληρώνονται με μεταβλητές περιθωρίου Si, και η ΑΣ γράφεται = 0):
3·Χ1 + 4·Χ2 + Χ3 + S1 = 2
Χ1 + 3·Χ2 + 2·Χ3 + S2 = 1
-3·Χ1 - 6·Χ2 - 2·Χ3 + P = 0
Γ) Από το Αρχικό Σύστημα δημιουργούμε τον Αρχικό Πίνακα Simplex (που περιέχει την αρχική βασική εφικτή λύση, για Χi =0 & με βασικές μεταβλητές τις Si, P):
| β.μ. | Χ1 | Χ2 | Χ3 | S1 | S2 | P | |
| S1 | 3 | 4 | 1 | 1 | 0 | 0 | 2 |
| S2 | 1 | 3 | 2 | 0 | 1 | 0 | 1 |
| P | -3 | -6 | -2 | 0 | 0 | 1 | 0 |
Δ) Εκτελούμε τη 1η επανάληψη της Simplex:
1. Επιλέγουμε την εισερχόμενη μεταβλητή (οδηγό στήλη) & την εξερχόμενη από τις β.μ. (οδηγό γραμμή).
| β.μ. | Χ1 | Χ2 | Χ3 | S1 | S2 | P | ||
| S1 | 3 | 4 | 1 | 1 | 0 | 0 | 2 | 2/4= ½ |
| S2 | 1 | 3 | 2 | 0 | 1 | 0 | 1 | 1/3 |
| P | -3 | -6 | -2 | 0 | 0 | 1 | 0 |
2. Διαιρούμε την οδηγό γραμμή με το οδηγό στοιχείο (για να το κάνουμε 1).
3-4. Αφαιρούμε την οδηγό γραμμή από τις άλλες γραμμές (για να γίνουν 0 τα υπόλοιπα στοιχεία της οδηγού στήλης), και, τοποθετούμε την εισερχόμενη μεταβλητή στη θέση της εξερχόμενης και διαβάζουμε τη λύση στη τελευταία στήλη.
| β.μ. | Χ1 | Χ2 | Χ3 | S1 | S2 | P | |
| S1 | 5/3 | 0 | -5/3 | 1 | -4/3 | 0 | 2/3 |
| Χ2 | 1/3 | 1 | 2/3 | 0 | 1/3 | 0 | 1/3 |
| P | -1 | 0 | 2 | 0 | 2 | 1 | 2 |
5. Ελέγχουμε αν η λύση, Χ1 = Χ3 = 0, Χ2 = 2/3, και P = 2, είναι η βέλτιστη (δηλ., αν στη γραμμή του Ρ υπάρχουν αρνητικές ποσότητες). Εφόσον υπάρχουν (-1) προχωρούμε στην επόμενη επανάληψη.
Ε) Εκτελούμε τη 2η επανάληψη της Simplex:
1. Επιλέγουμε την εισερχόμενη μεταβλητή (οδηγό στήλη) & την εξερχόμενη από τις β.μ. (οδηγό γραμμή).
| β.μ. | Χ1 | Χ2 | Χ3 | S1 | S2 | P | ||
| S1 | 5/3 | 0 | -5/3 | 1 | -4/3 | 0 | 2/3 | 2/5 |
| Χ2 | 1/3 | 1 | 2/3 | 0 | 1/3 | 0 | 1/3 | 1 |
| P | -1 | 0 | 2 | 0 | 2 | 1 | 2 |
2. Διαιρούμε την οδηγό γραμμή με το οδηγό στοιχείο (για να το κάνουμε 1)
3-4. Αφαιρούμε την οδηγό γραμμή από τις άλλες γραμμές (για να γίνουν 0 τα υπόλοιπα στοιχεία της οδηγού στήλης), και, τοποθετούμε την εισερχόμενη μεταβλητή στη θέση της εξερχόμενης και διαβάζουμε τη λύση στη τελευταία στήλη.
| β.μ. | Χ1 | Χ2 | Χ3 | S1 | S2 | P | |
| Χ1 | 1 | 0 | -1 | 3/5 | -4/5 | 0 | 2/5 |
| Χ2 | 0 | 1 | 1 | -1/5 | 3/5 | 0 | 1/5 |
| P | 0 | 0 | 1 | 3/5 | 6/5 | 1 | 12/5 |
5. Ελέγχουμε αν η λύση, Χ1 = 2/5, Χ3 = 1/5, Χ3 = 0, και P = 12/5, είναι η βέλτιστη (δηλ., αν στη γραμμή του Ρ υπάρχουν αρνητικές ποσότητες). Εφόσον δεν υπάρχουν αρνητικοί αριθμοί στο Ρ, η διαδικασία της Simplex έχει τελειώσει και η λύση είναι η βέλτιστη.
ΠΑΡΑΔΕΙΓΜΑ 3
Ένας αγρότης έχει στη διάθεσή του 3200 € και 160 μέρες για να σπείρει τα 100 στρέμματα του χωραφιού του. Στην αγορά υπάρχουν τρία είδη σπόρων Α, Β, και Γ με τιμές 40, 20 και 30 €/στρέμμα αντίστοιχα, και τα οποία απαιτούν 1, 2, και 1, αντίστοιχα, μέρες σποράς ανά στρέμμα. Αν από το κάθε είδος κερδίζει 100, 300, και 200 €/στρέμμα αντίστοιχα, πόσα στρέμματα πρέπει να σπείρει για κάθε είδος σπόρου, ώστε να μεγιστοποιήσει το κέρδος του;
ΛΥΣΗ:
Α) Γράφουμε το παραπάνω πρόβλημα μεγιστοποίησης σε τυποποιημένη μορφή:
ΥΤΠ:
Χ1 + Χ2 + Χ3 ≤ 100
40·Χ1 + 20·Χ2 + 30·Χ3 ≤ 3200
Χ1 + 2·Χ2 + Χ3 ≤ 160
Χ1, Χ2, Χ3 ≥ 0
Α.Σ.:
Να μεγιστοποιηθεί το: P = 100·Χ1 + 300·Χ2 + 200·Χ3
Β) Δημιουργούμε το Αρχικό Σύστημα Simplex (οι περιορισμοί συμπληρώνονται με μεταβλητές περιθωρίου Si, και η ΑΣ γράφεται = 0):
Χ1 + Χ2 + Χ3 + S1 = 100
40·Χ1 + 20·Χ2 + 30·Χ3 + S2 = 3200
Χ1 + 2Χ2 + Χ3 + S3 = 160
-100·Χ1 - 300·Χ2 - 200·Χ3 + P = 0
Γ) Από το Αρχικό Σύστημα δημιουργούμε τον Αρχικό Πίνακα Simplex (που περιέχει την αρχική βασική εφικτή λύση, για Χi = 0 & με βασικές μεταβλητές τις Si, P):
| β.μ. | Χ1 | Χ2 | Χ3 | S1 | S2 | S3 | P | |
| S1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 100 |
| S2 | 40 | 20 | 30 | 0 | 1 | 0 | 0 | 3200 |
| S3 | 1 | 2 | 1 | 0 | 0 | 1 | 0 | 160 |
| P | -100 | -300 | -200 | 0 | 0 | 0 | 1 | 0 |
Δ) 1η επανάληψη της Simplex:
| β.μ. | Χ1 | Χ2 | Χ3 | S1 | S2 | S3 | P | ||
| S1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 100 | 100/1 = 100 |
| S2 | 40 | 20 | 30 | 0 | 1 | 0 | 0 | 3200 | 3200/ 20=160 |
| S3 | 1 | 2 | 1 | 0 | 0 | 1 | 0 | 160 | 160/2 = 80 |
| P | -100 | -300 | -200 | 0 | 0 | 0 | 1 | 0 |
Με αποτέλεσμα:
| β.μ. | Χ1 | Χ2 | Χ3 | S1 | S2 | S3 | P | ||
| S1 | ½ | 0 | ½ | 1 | 0 | -½ | 0 | 20 | 20/ ½ =40 |
| S2 | 30 | 0 | 20 | 0 | 1 | -10 | 0 | 1600 | 1600/ 20=80 |
| Χ2 | ½ | 1 | ½ | 0 | 0 | ½ | 0 | 80 | 80/ ½ =160 |
| P | 50 | 0 | -50 | 0 | 0 | 150 | 1 | 24000 |
Ε) 2η επανάληψη της Simplex:
| β.μ. | Χ1 | Χ2 | Χ3 | S1 | S2 | S3 | P | |
| Χ3 | 1 | 0 | 1 | 2 | 0 | -1 | 0 | 40 |
| S2 | 10 | 0 | 0 | -40 | 1 | 10 | 0 | 800 |
| Χ2 | 0 | 1 | 0 | -1 | 0 | 1 | 0 | 60 |
| P | 100 | 0 | 0 | 100 | 0 | 100 | 1 | 26000 |
Εφόσον δεν υπάρχουν αρνητικοί αριθμοί στο Ρ, η διαδικασία της Simplex έχει τελειώσει και η λύση είναι η βέλτιστη. Ο αγρότης, επομένως, θα πρέπει να σπείρει 60 στρέμματα με σπόρο τύπου Β και 40 στρέμματα με σπόρο τύπου Γ για να έχει το μέγιστο κέρδος που είναι 26000 €.
ΠΑΡΑΔΕΙΓΜΑ 4
Να λυθεί το παρακάτω ΠΓΠ με τη μέθοδο Simplex:
ΥΤΠ:
2·Χ1 + Χ2 + 3·Χ3 ≤ 450
3·Χ2 + Χ3 + Χ4 ≤ 180
4·Χ1 + 2·Χ3 ≤ 400
Χ1 + Χ2 + 2·Χ4 ≤ 110
Χ1, Χ2, Χ3, Χ4 ≥ 0
ΑΣ:
Να μεγιστοποιηθεί το: P = 50·Χ1 + 120·Χ2 + 40·Χ3 + 80·Χ4
ΛΥΣΗ:
Α) Διαπιστώνουμε ότι το μοντέλο είναι πρόβλημα μεγιστοποίησης σε τυποποιημένη μορφή (όλοι οι περιορισμοί είναι ≤ θετικών αριθμών και τα Χi θετικά), οπότε μπορούμε να ακολουθήσουμε τη διαδικασία που περιγράψαμε νωρίτερα:
Β) Δημιουργούμε το Αρχικό Σύστημα Simplex (οι περιορισμοί συμπληρώνονται με μεταβλητές περιθωρίου Si, και η ΑΣ γράφεται = 0):
2·Χ1 + Χ2 + 3·Χ3 + S1 = 450
3·Χ2 + Χ3 + Χ4 + S2 = 180
4·Χ1 + 2·Χ3 + S3 = 400
Χ1 + Χ2 + 2·Χ4 + S4 = 110
-50·Χ1 -120·Χ2 -40·Χ3 -80·Χ4 + P = 0
Γ) Από το Αρχικό Σύστημα δημιουργούμε τον Αρχικό Πίνακα Simplex (που περιέχει την αρχική βασική εφικτή λύση, για Χi =0 & με βασικές μεταβλητές τις Si, P):
| β.μ. | Χ1 | Χ2 | Χ3 | Χ4 | S1 | S2 | S3 | S4 | P | |
| S1 | 2 | 1 | 3 | 0 | 1 | 0 | 0 | 0 | 0 | 450 |
| S2 | 0 | 3 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 180 |
| S3 | 4 | 0 | 2 | 0 | 0 | 0 | 1 | 0 | 0 | 400 |
| S4 | 1 | 1 | 0 | 2 | 0 | 0 | 0 | 1 | 0 | 110 |
| P | -50 | -120 | -40 | -80 | 0 | 0 | 0 | 0 | 1 | 0 |
Δ) 1η επανάληψη της Simplex:
| β.μ. | Χ1 | Χ2 | Χ3 | Χ4 | S1 | S2 | S3 | S4 | P | ||
| S1 | 2 | 1 | 3 | 0 | 1 | 0 | 0 | 0 | 0 | 450 | 450 |
| S2 | 0 | 3 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 180 | 180/3=60 |
| S3 | 4 | 0 | 2 | 0 | 0 | 0 | 1 | 0 | 0 | 400 | 400/2=200 |
| S4 | 1 | 1 | 0 | 2 | 0 | 0 | 0 | 1 | 0 | 110 | 110 |
| P | -50 | -120 | -40 | -80 | 0 | 0 | 0 | 0 | 1 | 0 |
Ε) 2η επανάληψη της Simplex:
| β.μ. | Χ1 | Χ2 | Χ3 | Χ4 | S1 | S2 | S3 | S4 | P | ||
| S1 | 2 | 0 | 8/3 | -1/3 | 1 | -1/3 | 0 | 0 | 0 | 390 | 390/2 =195 |
| Χ2 | 0 | 1 | 1/3 | 1/3 | 0 | 1/3 | 0 | 0 | 0 | 60 | |
| S3 | 4 | 0 | 2 | 0 | 0 | 0 | 1 | 0 | 0 | 400 | 400/4 =100 |
| S4 | 1 | 0 | -1/3 | 5/3 | 0 | -1/3 | 0 | 1 | 0 | 50 | 50 |
| P | -50 | 0 | 0 | -40 | 0 | 40 | 0 | 0 | 1 | 7200 |
Ζ) 3η επανάληψη της Simplex:
| β.μ. | Χ1 | Χ2 | Χ3 | Χ4 | S1 | S2 | S3 | S4 | P | ||
| S1 | 0 | 0 | 10/3 | -11/3 | 1 | 1/3 | 0 | 0 | 0 | 290 | 290*3/10 =87 |
| Χ2 | 0 | 1 | 1/3 | 1/3 | 0 | 1/3 | 0 | 0 | 0 | 60 | 60*3 =180 |
| S3 | 0 | 0 | 10/3 | -20/3 | 0 | 4/3 | 1 | -4 | 0 | 200 | 200*3/10=60 |
| Χ1 | 1 | 0 | -1/3 | 5/3 | 0 | -1/3 | 0 | 1 | 0 | 50 | 50*3=150 |
| P | 0 | 0 | -50/3 | 130/3 | 0 | 70/3 | 0 | 50 | 1 | 9700 |
Με τελικό αποτέλεσμα:
| β.μ. | Χ1 | Χ2 | Χ3 | Χ4 | S1 | S2 | S3 | S4 | P | |
| S1 | 0 | 0 | 0 | 3 | 1 | -1 | -1 | 4 | 0 | 90 |
| Χ2 | 0 | 1 | 0 | 1 | 0 | 1/5 | -1/10 | 2/5 | 0 | 40 |
| Χ3 | 0 | 0 | 1 | -2 | 0 | 2/5 | 3/10 | -6/5 | 0 | 60 |
| Χ1 | 1 | 0 | 0 | 1 | 0 | -1/5 | 1/10 | 3/5 | 0 | 70 |
| P | 0 | 0 | 0 | 10 | 0 | 30 | 5 | 30 | 1 | 10700 |
Εφόσον δεν υπάρχουν αρνητικοί αριθμοί στο Ρ, η διαδικασία της Simplex έχει τελειώσει και η λύση είναι η βέλτιστη.
