Η απλή μέθοδος γραμμικής βελτιστοποίησης εξηγείται απλά

Μοντελοποίηση γραμμικών προγραμμάτων

Κατά τη μοντελοποίηση γραμμικών προγραμμάτων, διάφορες παράμετροι όπως π.χ. ΣΙ. Μπορούν να καθοριστούν οι χρόνοι επεξεργασίας των τεμαχίων εργασίας ή της χωρητικότητας της μηχανής. Στη συνέχεια, ορίζεται μια αντικειμενική συνάρτηση, η οποία πρέπει να μεγιστοποιηθεί υπό ορισμένους περιορισμούς. Η αντικειμενική συνάρτηση είναι συχνά η συνάρτηση κέρδους, καθώς η μεγιστοποίηση του καθαρού κέρδους αποτελεί βασικό στόχο για τις εταιρείες. Οι περιορισμοί περιγράφονται από την έλλειψη πόρων (π. ΣΙ. Χωρητικότητα, χρόνος, χώρος). Στη συνέχεια, μπορείτε να λύσετε το πρόβλημα χρησιμοποιώντας τη μέθοδο simplex.

• Μπορείτε να μάθετε τη διαδικασία δημιουργίας γραμμικών μοντέλων ιδιαίτερα εύκολα εάν κάνετε μόνοι σας ένα απλό παράδειγμα: Ας υποθέσουμε ότι έχετε τρία μηχανήματα Μ
  instagram viewer
  ₁, Μ₂ και Μ₃ επί των οποίων τα δύο προϊόντα Ρ₁ και π₂ πρέπει να παράγονται. Οι μηχανές έχουν διαφορετική χωρητικότητα και χρειάζεται χρόνος για την επεξεργασία ενός συγκεκριμένου προϊόντος στις μηχανές για διαφορετικά χρονικά διαστήματα και τα τελικά προϊόντα έχουν διαφορετικά κέρδη Μακριά.
• Weάχνουμε τώρα για το πρόγραμμα παραγωγής με το μέγιστο κέρδος, δηλαδή το πρόγραμμα παραγωγής στο οποίο επιτυγχάνεται το μεγαλύτερο κέρδος.

Παράδειγμα με αριθμητικές τιμές και εισαγωγή στη μέθοδο simplex

Στο επόμενο βήμα χρειάζεστε συγκεκριμένες αριθμητικές τιμές για να μοντελοποιήσετε το πρόβλημά σας. Ας υποθέσουμε ότι για την επεξεργασία του P₁ στο Μ₁ Συγκεντρώνονται 2 ώρες στο Μ₂ 3 ώρες και στις Μ₃ 4 ώρες. Για τον Π₂ πέσει στο Μ₁ 4 ώρες μετά, στις Μ₂ 5 ώρες και στις Μ₃ 3 ώρες. Οι χωρητικότητες της μηχανής για Μ₁ 500 ώρες, για Μ₂ 300 ώρες και για Μ3 600 ώρες. Τα κέρδη για τα τελικά προϊόντα P₁ είναι 3 ευρώ / τεμάχιο, για τα τελικά προϊόντα P₂ 4 ευρώ / τεμάχιο.

1. Είναι καλύτερο να δημιουργήσετε έναν πίνακα με τρεις σειρές και τρεις στήλες, με επιπλέον χώρο για τις επικεφαλίδες των γραμμών και των στηλών. Πρέπει να αφήσει στήλες. Για παράδειγμα, ο χρόνος επεξεργασίας του Ρ είναι στο πεδίο "Στήλη 1 και Σειρά 1"₁ στο Μ₁, στο πεδίο "Στήλη 2 και Γραμμή 3" ο χρόνος επεξεργασίας του Ρ₂ στο Μ₃. Η στήλη 3 δείχνει τις χωρητικότητες των τριών μηχανών.


Ο αλγόριθμος Gauss των γραμμικών συστημάτων εξισώσεων εξηγείται με λίγα λόγια

Θα συναντήσετε γραμμικά συστήματα εξισώσεων για πρώτη φορά στο γυμνάσιο στο ...

2. Τώρα χρειάζεστε δύο μεταβλητές x₁, Χ₂ καθορίζουν τις ποσότητες παραγωγής του Ρ₁ και π₂ ανταποκρίνομαι.
3. Έτσι παίρνετε τους περιορισμούς 2x₁+ 4x₂ ≤ 500 (μηχανή 1), 3x₁+ 5x₂ ≤ 300 (μηχανή 2) και 4x₁+ 3x₂ ≤ 600 (μηχανή 3). Σε κάθε περίπτωση, υπάρχουν ανισότητες, καθώς οι ικανότητες δεν χρειάζεται να εξαντληθούν πλήρως.
4. Η αντικειμενική συνάρτηση (κέρδος) που πρέπει να μεγιστοποιηθεί είναι G (x₁, Χ₂) = 3x₁+ 4x₂ -> μέγ.
5. Επιπλέον, οι συνθήκες μη αρνητικότητας του x ισχύουν για την ποσότητα παραγωγής₁, Χ₂ ≥ 0. Βλέπετε, όλες οι εξισώσεις είναι γραμμικές εξισώσεις. Αν τα κοιτάξετε μαζί, αντιμετωπίζετε ένα πρόβλημα γραμμικής βελτιστοποίησης.

Γραμμική βελτιστοποίηση και εφαρμογή της μεθόδου simplex

Η ιδέα για την επίλυση ενός γραμμικού προγράμματος είναι ότι οι ανισότητες εξαλείφονται με την εισαγωγή "χαλαρών μεταβλητών" στο Εξισώσεις και το πρόβλημα τροποποιημένης βελτιστοποίησης λύνεται ως LGS. Η μέθοδος simplex είναι επομένως πολύ παρόμοια με τον αλγόριθμο Gauss για την επίλυση του LGS.

1. Παράδειγμα: Ένα αεροπλάνο διαιρείται με τρία αγαθά G₁, G₂, G₃ να φορτωθεί με την υψηλότερη δυνατή συνολική αξία φορτίου. Αυτά έχουν απαίτηση χώρου 1, 0,2 ή 6 dm³, έχουν βάρος 1, 0, 4 και 8 κιλά και τιμή 10, 3 ή 50 ευρώ. Πώς φορτίζεται ιδανικά το αεροσκάφος όταν ο χώρος φόρτωσης είναι 2000dm³ και μπορεί να μεταφέρει το πολύ 3000 κιλά φορτίου;
2. Ορίζεις το x₁, Χ₂, Χ₃ ως ποσότητες αγαθών G₁, G₂, G₃.
3. Μπορείτε τώρα να ορίσετε τους περιορισμούς με μεταβλητές χαλαρών ως εξής: x₁+ 0,4x₂+ 8x₃+ x₄ = 3000 και x₁+ 0,2x₂+ 6x₃+ x₅ = 2000. Η αντικειμενική συνάρτηση (συνολική αξία μεταφοράς) είναι G (x₁, Χ₂, Χ₃) = 10x₁+ 3x₂+ 50x₃ -> μέγ. Μπορείτε να το αλλάξετε φέρνοντας όλες τις μεταβλητές σε μία σελίδα (G-10x₁-3x₂-50x₃ = 0).
4. Στη συνέχεια, ρυθμίστε τον πίνακα Simplex. Έχει 3 σειρές και 7 στήλες. Στην αριστερή πλευρά εισάγετε το x στις στήλες₁, Χ₂, Χ₃, Χ₄, Χ₅ και G ως επικεφαλίδες. Στα δεξιά, το b είναι η μόνη στήλη. Εκεί αναγράφονται οι βέλτιστες ποσότητες αγαθών και η υψηλότερη δυνατή συνολική αξία φορτίου. Η τρίτη γραμμή είναι η γραμμή στόχος. (Έλεγχος: στις τρεις γραμμές με τις παραπάνω επικεφαλίδες υπάρχουν οι αριθμοί: Γραμμή 1: 1, 0.4, 8, 1, 0, 0, 3000, Γραμμή 2: 1, 0.2 6, 0, 1, 0, 2000 και Γραμμή 3: -10, -3, -50, 0, 0, 1, 0).
5. Τώρα προχωρήστε όπως όταν χρησιμοποιείτε τη μέθοδο Gaussian για να λύσετε ένα LGS. Στο πρώτο βήμα αλλάζετε τη γραμμή 1 αντίστοιχη. Η γραμμή 2 αποστέλλεται και προστίθεται στην άλλη γραμμή έτσι ώστε να εμφανίζεται μόνο ένα 1 στη "Γραμμή 1 + Στήλη 1" και ένα 0 στη "Γραμμή 2 + Στήλη 1". Αυτό αλλάζει επίσης τις τιμές στη γραμμή προορισμού αυτόματα.
6. Σε αυτήν την περίπτωση, για παράδειγμα, μπορείτε να πολλαπλασιάσετε τη σειρά 2 επί -1 και να την προσθέσετε στη σειρά 1 και να πολλαπλασιάσετε τη σειρά 2 επί 10 και προσθέστε στη γραμμή 3 (έλεγχος: γραμμή 1: 0, 0.2, 2, 1, -1, 0, 1000, γραμμή 2: παραμένει η ίδια, γραμμή 3: 0, -1, 10, 0, 10, 1, 20.000).
7. Στο δεύτερο βήμα, πάρτε τη στήλη 2 και δημιουργήστε ένα 0 μετασχηματίζοντας "Σειρά 2 + Στήλη 2" και στη συνέχεια ένα 1 στη "Σειρά 1 και Στήλη 2". Και πάλι, πρέπει να σημειωθεί πώς αλλάζει η γραμμή -στόχος.
8. Τα βήματα μετασχηματισμού θα ήταν, για παράδειγμα, να πολλαπλασιάσετε τη γραμμή 1 επί -1 και να προσθέσετε στη σειρά 2 και τη σειρά 1 έως 5 και να προσθέσετε στη σειρά 3 (Έλεγχος: αφού εκτελέσετε και τα δύο βήματα, το αποτέλεσμα είναι: γραμμή 1: 0, 1, 10, 5, -5, 0, 5000, γραμμή 2: 1, 0, 4, -1, 2, 0, 1000 και γραμμή 3: 0, 0, 20, 5, 5, 1, 25.000).
9. Τώρα μπορείτε να διαβάσετε τις λύσεις στη δεξιά πλευρά του πίνακα. Αυτό έχει ως αποτέλεσμα συνολική αξία φορτίου 25.000 ευρώ, 5000 μονάδες αγαθού 1, 1000 μονάδες αγαθού 2 και καμία μονάδα αγαθού 3 δεν μεταφέρονται.

Λάβετε υπόψη ότι η λύση του πίνακα simplex οδηγεί σε μια βέλτιστη λύση μόνο εάν εμφανίζονται μόνο θετικά αποτελέσματα στη γραμμή στόχου στα αριστερά μετά το τελευταίο βήμα αναδιαμόρφωσης Αρίθμηση στάση. Έχετε εσωτερικεύσει το σύστημα μετά από 2-3 άλλα παραδείγματα και θα μπορείτε να λύσετε τέτοιες εργασίες στο μέλλον με παιχνιδιάρικο τρόπο.