Εάν είστε μηχανικός ή φοιτητής μηχανικής, ίσως γνωρίζετε τι σημαίνει βελτιστοποίηση.
Για να έχετε το καλύτερο δυνατό αποτέλεσμα, είναι σημαντικό να βρείτε τον καλύτερο τρόπο για να κάνετε πράγματα.
Στον γραμμικό προγραμματισμό, μπορείτε να χρησιμοποιήσετε μια βασική λύση για να βρείτε την καλύτερη λύση.
Ποια είναι όμως μια βασική λύση και γιατί είναι τόσο σημαντικό για τους μηχανικούς να γνωρίζουν γι' αυτήν; Σε αυτό το άρθρο, θα μιλήσω για το ποιες είναι οι βασικές λύσεις, γιατί είναι σημαντικές στη μηχανική και πώς μπορούν να χρησιμοποιηθούν για να έχετε τα καλύτερα αποτελέσματα σε διαφορετικές καταστάσεις.
Λύστε λοιπόν και ετοιμαστείτε να βουτήξετε στον κόσμο των βασικών λύσεων, όπου θα αναλύσω τα μυστήρια και θα σας δείξω πόσο ισχυρή μπορεί να είναι αυτή η τεχνική.
Βασικές Λύσεις στον Γραμμικό Προγραμματισμό
Επίσημος ορισμός:
Μια λύση σε ένα μοντέλο γραμμικού προγράμματος που αποτελείται από m εξισώσεις σε n μεταβλητές λαμβάνεται λύνοντας m μεταβλητές ως προς τις υπόλοιπες (nm) μεταβλητές και ορίζοντας τις μεταβλητές (nm) ίσες με μηδέν.
Μια βασική λύση στον γραμμικό προγραμματισμό είναι ένας τρόπος επίλυσης ενός προβλήματος γραμμικού προγραμματισμού που πληροί ορισμένες τεχνικές απαιτήσεις.
Συγκεκριμένα, ένα διάνυσμα x είναι μια βασική λύση για ένα πολύεδρο εάν τα διανύσματα {ai : xi = 0} είναι γραμμικά ανεξάρτητα.
Αυτό σημαίνει ότι οι στήλες του Α που έχουν μεταβλητές xi που δεν είναι μηδενικές είναι γραμμικά ανεξάρτητες.
Μια βασική λύση με μη αρνητικά συστατικά ονομάζεται βασική εφικτή λύση (BFS) (BFS).
Ένα BFS πληροί όλους τους κανόνες που ορίζουν ένα πολύεδρο.
Κάθε BFS είναι μια γωνία του πολυέδρου των εφικτών λύσεων από γεωμετρική άποψη.
Για να βρείτε μια βασική λύση, πρέπει να ορίσετε τις nm μεταβλητές που δεν είναι βασικές στο μηδέν και να λύσετε τις m μεταβλητές που είναι βασικές.
Είναι δυνατόν διαφορετικές βάσεις να οδηγήσουν στην ίδια βασική λύση, πράγμα που σημαίνει ότι μπορεί να υπάρχουν περισσότεροι από ένας τρόποι επίλυσης του ίδιου προβλήματος.
Η μέθοδος Simplex είναι μια επαναληπτική διαδικασία που μετακινείται από το ένα BFS στο επόμενο BFS μέχρι να βρει το καλύτερο BFS.
Αφού χρησιμοποιήσουμε τη μέθοδο simplex για να βρούμε ένα BFS, μπορούμε να πούμε αν η λύση είναι η καλύτερη βλέποντας εάν κάποιο άλλο BFS κοντά δίνει καλύτερη τιμή για τη συνάρτηση αντικειμένου.
Εάν δεν υπάρχει τέτοιο BFS, τότε το τρέχον BFS είναι το καλύτερο.
Μοντέλο Γραμμικού Προγραμματισμού
Ένα μοντέλο γραμμικού προγραμματισμού περιλαμβάνει τρία κύρια στοιχεία: μεταβλητές απόφασης, μια αντικειμενική συνάρτηση και περιορισμούς.
Τόσο η αντικειμενική συνάρτηση όσο και οι περιορισμοί πρέπει να είναι γραμμικές συναρτήσεις και οι μεταβλητές απόφασης πρέπει να είναι συνεχείς.
Η αντικειμενική συνάρτηση χρησιμοποιείται είτε για να αυξήσει είτε να μειώσει έναν αριθμό που αντιπροσωπεύει το κέρδος, το κόστος, τον αριθμό των προϊόντων που παράγονται κ.λπ.
Οι περιορισμοί είναι όρια ή περιορισμοί στο συνολικό ποσό ενός συγκεκριμένου πόρου που απαιτείται για την εκτέλεση των εργασιών που θα καθορίσουν το επίπεδο επιτυχίας στις μεταβλητές απόφασης.
Επιπλέον, ορισμένα γραμμικά προγράμματα απαιτούν όλες οι μεταβλητές απόφασης να είναι μη αρνητικές.
Στα μοντέλα γραμμικού προγραμματισμού, μπορείτε επίσης να χρησιμοποιήσετε ακέραιες και δυαδικές μεταβλητές.
Οι δυαδικές μεταβλητές μπορούν να έχουν μόνο τιμή 0 ή 1, επομένως μπορούν να έχουν μόνο τιμή 0 ή 1.
Η μέθοδος Simplex
Ένας από τους πιο χρησιμοποιούμενους τρόπους επίλυσης προβλημάτων γραμμικού προγραμματισμού είναι η μέθοδος Simplex.
Οι βασικές λύσεις είναι σημαντικές στη μέθοδο simplex επειδή αντιστοιχούν στα γωνιακά σημεία της εφικτής περιοχής και η μέθοδος simplex μετακινείται από τη μια γωνία στην άλλη μέχρι να βρεθεί μια βέλτιστη λύση.
Η μέθοδος simplex είναι ένας γρήγορος τρόπος για να βρείτε την καλύτερη απάντηση σε ένα πρόβλημα γραμμικού προγραμματισμού χρησιμοποιώντας τις ιδιότητες των βασικών λύσεων.
Για να χρησιμοποιήσουμε τη μέθοδο simplex για να βρούμε το καλύτερο BFS, πρέπει να βρούμε μια βάση B για τον πίνακα περιορισμών A και να λύσουμε το σύστημα Ax = b με όλες τις μεταβλητές εκτός από τη βάση που ορίζονται στο μηδέν.
Οι τιμές που προκύπτουν για τις βασικές μεταβλητές σχηματίζουν ένα BFS.
Εάν υπάρχει μια βέλτιστη λύση, τότε υπάρχει μια βέλτιστη BFS.
Η μέθοδος Simplex μετακινείται από ένα BFS σε ένα γειτονικό BFS μέχρι να φτάσει σε ένα βέλτιστο BFS χρησιμοποιώντας διαδικασίες περιστροφής.
Σύγκριση Βασικών Λύσεων και Εφικτών Λύσεων
Η διαφορά μεταξύ μιας βασικής λύσης και μιας εφικτής λύσης είναι ότι μια βασική λύση δεν χρειάζεται να πληροί καμία προϋπόθεση.
Συγκεκριμένα, πρέπει να έχει διανύσματα που είναι γραμμικά ανεξάρτητα και έχουν μη μηδενικές τιμές για το xi και το x πρέπει να είναι μικρότερο από 0.
Από την άλλη πλευρά, εφικτή λύση είναι κάθε σημείο που εντάσσεται στα όρια του προβλήματος.
Αλλά δεν είναι όλες οι εφικτές λύσεις βασικές εφικτές λύσεις.
Οι βασικές εφικτές λύσεις (BFS) είναι μόνο εκείνες που ταιριάζουν με τις γωνίες του πολυέδρου των εφικτών λύσεων.
Επιστροφή στα βασικά: Ξεκλείδωμα της δύναμης των βασικών λύσεων στη μηχανική
Ακόμα είναι δύσκολο να το καταλάβεις; Να αλλάξω λίγο την άποψη:
Έχετε βαρεθεί να χρησιμοποιείτε περίπλοκες μεθόδους και αλγόριθμους για την επίλυση δύσκολων προβλημάτων; Θα θέλατε να υπήρχε ένας απλούστερος, πιο άμεσος τρόπος για να αντιμετωπίσετε τα προβλήματα του γραμμικού μοντέλου προγράμματος;
Λοιπόν, μην ανησυχείτε, γιατί η απάντηση είναι εδώ: λύστε για m μεταβλητές ως προς τις υπόλοιπες μεταβλητές (nm) και ορίστε τις μεταβλητές (nm) στο μηδέν.
Ποιος χρειάζεται αλγόριθμους που ακούγονται φανταχτεροί όταν μπορείτε να επιστρέψετε στα βασικά; Αφήστε λοιπόν μακριά τις αριθμομηχανές σας και ας αρχίσουμε να μαθαίνουμε για απλές λύσεις.
Εντάξει, αυτό ήταν απλώς ένα αστείο για να μοιάζει με τηλεοπτική διαφήμιση.
Τώρα ας επιστρέψουμε στην εξήγηση.
Βασική λύση Γραμμικός Προγραμματισμός
Συμβουλή: Ενεργοποιήστε το κουμπί υπότιτλων εάν το χρειάζεστε. Επιλέξτε «αυτόματη μετάφραση» στο κουμπί ρυθμίσεων, εάν δεν είστε εξοικειωμένοι με την ομιλούμενη γλώσσα. Ίσως χρειαστεί να κάνετε πρώτα κλικ στη γλώσσα του βίντεο προτού η αγαπημένη σας γλώσσα γίνει διαθέσιμη για μετάφραση.
Θήκες χρήσης
| Χρησιμοποιείται σε: | Περιγραφή: |
|---|---|
| Κατανομή των πόρων: | Η βασική λύση μπορεί να χρησιμοποιηθεί σε προβλήματα κατανομής πόρων, όπου ο στόχος είναι να διαιρεθούν περιορισμένοι πόροι μεταξύ των ανταγωνιστικών αναγκών. Για παράδειγμα, μια εταιρεία μπορεί να χρειαστεί να μοιράσει τον προϋπολογισμό της μεταξύ διαφορετικών τμημάτων ή έργων. Χρησιμοποιώντας βασικές λύσεις, μπορούν να βρουν τον καλύτερο τρόπο να χρησιμοποιήσουν τους πόρους τους για να βγάλουν τα περισσότερα χρήματα ή να ξοδέψουν όσο το δυνατόν λιγότερα. |
| Προγραμματισμός Παραγωγής: | Στον προγραμματισμό παραγωγής, η βασική λύση μπορεί να χρησιμοποιηθεί για να βρει τον καλύτερο συνδυασμό προϊόντων για να βγάλετε τα περισσότερα χρήματα. Οι εταιρείες μπορούν να βρουν το καλύτερο μείγμα παραγωγής που αποφέρει τα περισσότερα χρήματα και κοστίζει λιγότερο χρησιμοποιώντας τη βασική λύση. |
| Χρονοδρομολόγηση: | Η βασική λύση μπορεί να χρησιμοποιηθεί για να καταλάβετε πώς να προγραμματίσετε εργασίες ή εργασίες έτσι ώστε να μπορούν να εκτελεστούν με τον πιο αποτελεσματικό τρόπο. Για παράδειγμα, μια εταιρεία μπορεί να χρειαστεί να προγραμματίσει τις ώρες εργασίας των υπαλλήλων της για να βεβαιωθεί ότι έχουν αρκετούς εργαζομένους όταν η επιχείρηση είναι απασχολημένη. Χρησιμοποιώντας μια βασική λύση, μπορούν να βρουν τον καλύτερο τρόπο να προγραμματίσουν τα πράγματα, ώστε να υπάρχει όσο το δυνατόν λιγότερος χρόνος διακοπής λειτουργίας και να γίνεται όσο το δυνατόν περισσότερη δουλειά. |
| Διαχείριση της Εφοδιαστικής Αλυσίδας: | Στη διαχείριση της εφοδιαστικής αλυσίδας, ο στόχος είναι να διασφαλιστεί ότι τα αγαθά και οι υπηρεσίες κινούνται όσο το δυνατόν πιο ομαλά από τον προμηθευτή στον πελάτη. Για παράδειγμα, μια επιχείρηση μπορεί να χρειαστεί να βρει τις καλύτερες διαδρομές για τη μεταφορά αγαθών, έτσι ώστε το κόστος να περιορίζεται στο ελάχιστο και τα αγαθά να παραδίδονται στην ώρα τους. Χρησιμοποιώντας βασικές λύσεις, μπορούν να βρουν το καλύτερο σχέδιο για τη διαχείριση της εφοδιαστικής αλυσίδας που διατηρεί το κόστος χαμηλό και κρατά τους πελάτες ευχαριστημένους. |
| Βελτιστοποίηση χαρτοφυλακίου: | Στη βελτιστοποίηση χαρτοφυλακίου, όπου ο στόχος είναι να βρεθεί ο καλύτερος συνδυασμός επενδύσεων για να βγάλετε τα περισσότερα χρήματα με το λιγότερο ρίσκο, μπορούν να χρησιμοποιηθούν βασικές λύσεις. Για παράδειγμα, μια επιχείρηση επενδύσεων μπορεί να χρειαστεί να βρει τον καλύτερο συνδυασμό μετοχών, ομολόγων και άλλων τίτλων για να βοηθήσει τους πελάτες της να επιτύχουν τους επενδυτικούς τους στόχους. Χρησιμοποιώντας μια απλή λύση, μπορούν να βρουν τον καλύτερο τρόπο να αναμειγνύουν τα χαρτοφυλάκιά τους, έτσι ώστε να έχουν τις καλύτερες αποδόσεις, παίρνοντας παράλληλα το λιγότερο ρίσκο. |
συμπέρασμα
Συμπερασματικά, η ιδέα μιας βασικής λύσης είναι πολύ σημαντική στον τομέα της μηχανικής και μπορεί να χρησιμοποιηθεί με πολλούς διαφορετικούς τρόπους.
Γνωρίζοντας τι είναι μια βασική λύση και τι κάνει στον γραμμικό προγραμματισμό, μπορούμε να βελτιώσουμε τις λύσεις, να μειώσουμε το κόστος και να τις κάνουμε πιο αποτελεσματικές.
Αλλά είναι σημαντικό να θυμάστε ότι η βασική λύση δεν είναι μια λύση που ταιριάζει σε όλους, παρόλο που είναι ένα ισχυρό εργαλείο.
Για να έχετε τα καλύτερα αποτελέσματα, κάθε πρόβλημα πρέπει να εξετάζεται και να εξετάζεται προσεκτικά.
Ως μηχανικοί, πρέπει να συνεχίσουμε να εξετάζουμε πώς οι βασικές λύσεις και άλλες τεχνικές βελτιστοποίησης μπορούν να μας βοηθήσουν να σημειώσουμε πρόοδο και να βρούμε νέες ιδέες.
Ας αναγνωρίσουμε λοιπόν τη δύναμη των απλών λύσεων και ας συνεχίσουμε να πιέζουμε τα όρια του δυνατού χρησιμοποιώντας νέες τεχνικές και στρατηγικές.
Σύνδεσμοι και παραπομπές
Βιβλία:
- Γραμμικός Προγραμματισμός από τον Vasek Chvatal
- Μοντελοποίηση και επίλυση Γραμμικού Προγραμματισμού με το R από τον Jose M. Sallan
Κοινοποίηση στο…
