Γραμμικός Προγραμματισμός — Μέθοδος Simplex & Γραφική Επίλυση

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

Χρησιμοποιήστε γραμμικό προγραμματισμό μόνο όταν η αντικειμενική συνάρτηση και οι περιορισμοί είναι γραμμικοί. Αν η σχέση λυγίζει, καμπυλώνεται ή εξαρτάται από γινόμενα όπως $xy$, τότε το μοντέλο δεν είναι πρόβλημα γραμμικού προγραμματισμού.

Ορισμός Γραμμικού Προγραμματισμού

$$\text{maximize or minimize } z = c_1x_1 + c_2x_2 + \cdots + c_nx_n$$

υπό περιορισμούς όπως

$$a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \le b_1$$

μαζί με παρόμοιες γραμμικές ανισότητες, καθώς και συνθήκες όπως $x_i \ge 0$ όταν οι αρνητικές τιμές δεν έχουν νόημα.

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

Πώς Λειτουργεί η Γραφική Μέθοδος

Αν υπάρχουν μόνο δύο μεταβλητές απόφασης, μπορείτε να σχεδιάσετε κάθε περιορισμό στο επίπεδο $xy$. Η τομή όλων των επιτρεπτών περιοχών είναι η εφικτή περιοχή.

Κάθε σημείο μέσα σε αυτή την περιοχή είναι μια έγκυρη λύση. Η αντικειμενική συνάρτηση αντιστοιχίζει μια τιμή σε καθεμία από αυτές.

Για τα προβλήματα γραμμικού προγραμματισμού, ένα βασικό γεγονός είναι το εξής: αν υπάρχει βέλτιστη λύση, τότε τουλάχιστον μία βέλτιστη λύση εμφανίζεται σε μια κορυφή της εφικτής περιοχής. Γι’ αυτό η γραφική μέθοδος εστιάζει στις κορυφές αντί να ελέγχει κάθε σημείο στη σκιασμένη περιοχή.

Λυμένο Παράδειγμα: Επίλυση Προβλήματος Γραμμικού Προγραμματισμού Γραφικά

Ας υποθέσουμε ότι ένα εργαστήριο κατασκευάζει δύο προϊόντα, $A$ και $B$.

• Κέρδος ανά μονάδα του $A$: $3$
• Κέρδος ανά μονάδα του $B$: $5$
• Όριο χρόνου μηχανής: κάθε μονάδα του $A$ χρησιμοποιεί $1$ ώρα, κάθε μονάδα του $B$ χρησιμοποιεί $2$ ώρες, και είναι διαθέσιμες το πολύ $8$ ώρες
• Όριο συναρμολόγησης: κάθε μονάδα του $A$ χρησιμοποιεί $1$ ώρα, κάθε μονάδα του $B$ χρησιμοποιεί $1$ ώρα, και είναι διαθέσιμες το πολύ $5$ ώρες

Έστω $x$ οι μονάδες του $A$ και $y$ οι μονάδες του $B$.

Μεγιστοποιήστε

$$P = 3x + 5y$$

υπό τους περιορισμούς

$$x + 2y \le 8$$ $$x + y \le 5$$ $$x \ge 0,\quad y \ge 0$$

Βρείτε τις κορυφές

Από τους άξονες και τις ευθείες των περιορισμών, οι εφικτές κορυφές είναι

• $(0,0)$
• $(5,0)$
• $(0,4)$
• $(2,3)$

Το σημείο $(2,3)$ προκύπτει από την επίλυση των εξισώσεων των ορίων

$$x + 2y = 8,\quad x + y = 5$$

Αφαιρώντας, παίρνουμε $y = 3$, και έπειτα $x = 2$.

Ελέγξτε την αντικειμενική συνάρτηση σε κάθε κορυφή

Υπολογίστε το κέρδος σε κάθε κορυφή:

• Στο $(0,0)$, $P = 0$
• Στο $(5,0)$, $P = 15$
• Στο $(0,4)$, $P = 20$
• Στο $(2,3)$, $P = 21$

Άρα το μέγιστο κέρδος είναι

$$P = 21$$

στο

$$(x,y) = (2,3)$$

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

Διαίσθηση για τη Μέθοδο Simplex

Η γραφική μέθοδος είναι πρακτική μόνο όταν υπάρχουν δύο μεταβλητές, και μερικές φορές τρεις αν μπορείτε να φανταστείτε μια τρισδιάστατη περιοχή. Τα πραγματικά προβλήματα βελτιστοποίησης συχνά έχουν πολλές μεταβλητές, οπότε η σχεδίαση της εφικτής περιοχής δεν είναι πλέον ρεαλιστική.

Η μέθοδος simplex διατηρεί την ίδια λογική των κορυφών, αλλά την εφαρμόζει αλγεβρικά. Σε γενικές γραμμές, μετακινείται από μια εφικτή κορυφή σε μια άλλη που βελτιώνει την αντικειμενική συνάρτηση και σταματά όταν καμία γειτονική μετακίνηση δεν δίνει καλύτερη τιμή.

Άρα ένα καλό νοητικό μοντέλο είναι:

• Γραφική μέθοδος: βλέπεις τις κορυφές
• Μέθοδος simplex: πλοηγείσαι στις κορυφές χωρίς να τις σχεδιάζεις

Αυτή η περιγραφή δίνει τη διαίσθηση, όχι τον πλήρη αλγόριθμο. Η πραγματική διαδικασία της simplex χρησιμοποιεί έναν πίνακα tableau ή μια ισοδύναμη αλγεβρική μορφή για να αποφασίσει ποια μεταβλητή εισέρχεται και ποια εξέρχεται σε κάθε βήμα.

Γιατί οι Κορυφές Έχουν Σημασία

Οι γραμμικές αντικειμενικές συναρτήσεις δημιουργούν ισοσταθμικές ευθείες όπως

$$3x + 5y = k$$

για διαφορετικές τιμές του $k$. Καθώς μετακινείτε αυτή την ευθεία προς την κατεύθυνση μεγαλύτερου κέρδους, το τελευταίο σημείο όπου εξακολουθεί να αγγίζει την εφικτή περιοχή είναι εκεί όπου εμφανίζεται το μέγιστο.

Σε πολλά σχήματα, αυτή η τελευταία επαφή συμβαίνει σε μία μόνο κορυφή. Αν η ευθεία της αντικειμενικής συνάρτησης είναι παράλληλη με μια πλευρά του ορίου, πολλά σημεία πάνω σε εκείνη την πλευρά μπορεί να είναι όλα βέλτιστα. Σε αυτή την περίπτωση, εξακολουθεί να υπάρχει τουλάχιστον μία βέλτιστη κορυφή.

Συχνά Λάθη

Σύγχυση του εφικτού με το βέλτιστο

Ένα σημείο μπορεί να ικανοποιεί κάθε περιορισμό και παρ’ όλα αυτά να μην μεγιστοποιεί ή να μην ελαχιστοποιεί την αντικειμενική συνάρτηση. Εφικτό σημαίνει μόνο επιτρεπτό.

Παράλειψη των συνθηκών μη αρνητικότητας

Αν τα $x$ και $y$ παριστάνουν ποσότητες που παράγετε ή μεταφέρετε, οι αρνητικές τιμές συνήθως δεν έχουν νόημα. Η παράλειψη των $x \ge 0$ ή $y \ge 0$ μπορεί να αλλάξει το πρόβλημα.

Υπόθεση ότι κάθε απάντηση πρέπει να είναι ακέραιος αριθμός

Ο απλός γραμμικός προγραμματισμός επιτρέπει κλασματικές τιμές. Αν οι μεταβλητές πρέπει να είναι ακέραιοι αριθμοί, όπως ο αριθμός φορτηγών ή ο αριθμός εργαζομένων, χρειάζεστε μοντέλο ακέραιου προγραμματισμού ή μια επιπλέον συνθήκη ακεραιότητας.

Υπόθεση ότι κάθε πρόβλημα έχει βέλτιστη απάντηση

Μερικά προβλήματα γραμμικού προγραμματισμού είναι μη εφικτά, πράγμα που σημαίνει ότι κανένα σημείο δεν ικανοποιεί όλους τους περιορισμούς. Άλλα είναι μη φραγμένα, πράγμα που σημαίνει ότι η αντικειμενική συνάρτηση μπορεί να βελτιώνεται χωρίς όριο. Παίρνετε πεπερασμένο βέλτιστο μόνο όταν οι περιορισμοί περιορίζουν πραγματικά αρκετά το πρόβλημα.

Χρήση της γραφικής μεθόδου όταν υπάρχουν πάρα πολλές μεταβλητές

Μόλις οι μεταβλητές γίνουν πολλές, η γραφική παράσταση δεν είναι πλέον το σωστό εργαλείο. Εκεί είναι που η simplex ή άλλες μέθοδοι βελτιστοποίησης γίνονται απαραίτητες.

Πού Χρησιμοποιείται ο Γραμμικός Προγραμματισμός

Ο γραμμικός προγραμματισμός χρησιμοποιείται όταν οι αποφάσεις ανταγωνίζονται για περιορισμένους πόρους και τόσο ο στόχος όσο και οι περιορισμοί μπορούν να μοντελοποιηθούν γραμμικά. Τυπικά παραδείγματα περιλαμβάνουν τον προγραμματισμό παραγωγής, τις μεταφορές, τη στελέχωση, την ανάμειξη, τον χρονοπρογραμματισμό και την κατανομή προϋπολογισμού.

Το μοντέλο είναι τόσο καλό όσο και οι υποθέσεις του. Αν η πραγματική σχέση δεν είναι αρκετά κοντά στη γραμμική, ή αν οι μεταβλητές πρέπει να είναι ακέραιες, ένα απλό μοντέλο γραμμικού προγραμματισμού μπορεί να είναι μόνο η αφετηρία.

Δοκιμάστε ένα Παρόμοιο Πρόβλημα

Πάρτε ένα μικρό λεκτικό πρόβλημα με δύο προϊόντα, δύο περιορισμούς πόρων και μια συνάρτηση κέρδους. Ορίστε τις μεταβλητές, σχεδιάστε τους περιορισμούς και ελέγξτε μόνοι σας τις κορυφές. Μόλις κατανοήσετε αυτή την ιδέα, η μέθοδος simplex γίνεται πολύ πιο εύκολη στην κατανόηση, επειδή επεκτείνει την ίδια λογική σε περισσότερες διαστάσεις.