Γνωρίζετε τι σημαίνει να βελτιστοποιείτε ένα σύστημα για να έχετε το καλύτερο δυνατό αποτέλεσμα, εάν είστε φοιτητής μηχανικός ή μηχανικός.
Η βελτιστοποίηση μιας λύσης είναι το κλειδί της επιτυχίας σε οτιδήποτε, από την κατασκευή γεφυρών έως την κατασκευή λογισμικού.
Η ιδέα μιας βασικής εφικτής λύσης μπαίνει σε αυτό το σημείο.
Είναι μια βασική ιδέα στον γραμμικό προγραμματισμό που σας επιτρέπει να καταλάβετε ποια από ένα σύνολο πιθανών λύσεων είναι η καλύτερη.
Γιατί όμως έχει τόση σημασία; Σε αυτό το άρθρο, θα μιλήσω για βασικές εφικτές λύσεις και πώς μπορούν να χρησιμοποιηθούν για την επίλυση προβλημάτων μηχανικής στον πραγματικό κόσμο.
Θα μιλήσω για το πώς να τα βρείτε, από τι αποτελούνται και γιατί είναι σημαντικά.
Έτσι, είτε είστε έμπειρος μηχανικός είτε φοιτητής που μόλις ξεκινάτε, ελάτε μαζί μας καθώς βουτάω στον κόσμο των βασικών εφικτών λύσεων και σας δείχνω πώς να χρησιμοποιείτε τη δύναμη του γραμμικού προγραμματισμού.
Κατανόηση της Βασικής Εφικτής Λύσης
Επίσημος ορισμός:
Μια βασική λύση σε ένα γραμμικό μοντέλο προγράμματος στο οποίο όλες οι μεταβλητές είναι μη αρνητικές.
Μια βασική εφικτή λύση (BFS) είναι μια βασική ιδέα στον γραμμικό προγραμματισμό που βοηθά στην εύρεση των καλύτερων λύσεων.
Ένα BFS είναι μια λύση με τον μικρότερο δυνατό αριθμό μη μηδενικών μεταβλητών.
Είναι μια γωνία του πολυέδρου των εφικτών λύσεων.
Με άλλα λόγια, ένα BFS είναι μια βασική λύση που πληροί τους μη αρνητικούς περιορισμούς και βρίσκεται στην εφικτή περιοχή ή περιοχή προβλημάτων.
Εύρεση Βέλτιστης Βασικής Εφικτής Λύσης
Για να βρούμε το καλύτερο BFS, πρέπει να κάνουμε τα εξής:
- Γράψτε το πρόγραμμα σε τυπική μορφή για γραμμική ακολουθία.
- Μετατρέψτε το σύστημα των ανισοτήτων σε επαυξημένο πίνακα.
- Υπολογίστε ποιες μεταβλητές είναι βασικές και ποιες όχι.
- Υπολογίστε ποιες είναι οι βασικές μεταβλητές σε σχέση με τις άλλες μεταβλητές.
- Βάλτε αυτές τις εκφράσεις στη συνάρτηση αντικειμενικού για να λάβετε μια συνάρτηση μόνο των μεταβλητών που δεν είναι βασικές.
- Βρείτε μια μη βασική μεταβλητή που μπορεί να αυξηθεί χωρίς να σπάσει κανένας περιορισμός και που θα κάνει τη λειτουργία του στόχου καλύτερη.
Αυτή η μεταβλητή είναι πλέον βασική μεταβλητή και μία από τις άλλες βασικές μεταβλητές δεν είναι πλέον βασική μεταβλητή.
Εάν υπάρχει μια βέλτιστη λύση, αυτή πρέπει να βρίσκεται σε ένα από τα άκρα ή τις κορυφές της περιοχής όπου είναι δυνατές οι λύσεις.
Έτσι, εάν ένα LP έχει μια βέλτιστη λύση, έχει μια βέλτιστη λύση σε ένα ακραίο σημείο του εφικτού συνόλου.
Επίσης, υπάρχει πάντα ένα βέλτιστο BFS εάν υπάρχει μια βέλτιστη λύση.
Χρησιμοποιώντας τη μέθοδο Simplex για να βρείτε ένα βέλτιστο BFS
Η μέθοδος Simplex είναι ένας αλγόριθμος για την επίλυση προβλημάτων στο γραμμικό προγραμματισμό.
Μετακινείται από ένα BFS σε ένα "γειτονικό" BFS χρησιμοποιώντας τη διαδικασία περιστροφής.
Στη διαδικασία περιστροφής, μια μη βασική μεταβλητή επιλέγεται για να γίνει βασική μεταβλητή και, στη συνέχεια, χρησιμοποιείται το τρέχον BFS για την επίλυση των νέων βασικών μεταβλητών.
Όταν καμία μη βασική μεταβλητή δεν μπορεί να αλλάξει για να βελτιωθεί η αντικειμενική συνάρτηση, ο αλγόριθμος ολοκληρώνεται.
Γιατί οι βασικές εφικτές λύσεις είναι κρίσιμες για την επίλυση σύνθετων τεχνικών προβλημάτων
Ακόμα είναι δύσκολο να το καταλάβεις; Να αλλάξω λίγο την άποψη:
Ποιος χρειάζεται ούτως ή άλλως απλές, εφαρμόσιμες απαντήσεις; Απλώς συγκεντρώστε τα πάντα και ελπίζετε για το καλύτερο.
Τελικά, ποιος χρειάζεται βελτιστοποίηση όταν το χάος είναι πολύ πιο διασκεδαστικό; Καλώς ήρθατε στον κόσμο των μη αρνητικών μεταβλητών, όπου όλα είναι απλώς μια πρόταση και η αποτυχία είναι σχεδόν βέβαιη.
Ή μήπως είναι?
Ας διερευνήσουμε γιατί η φαινομενικά βασική ιδέα των βασικών εφικτών λύσεων κάθε άλλο παρά βασική είναι και γιατί μπορεί απλώς να είναι το κλειδί για την επίλυση ακόμη και των πιο περίπλοκων μηχανικών προβλημάτων.
Εντάξει, αυτό ήταν απλώς ένα αστείο για να μοιάζει με τηλεοπτική διαφήμιση.
Τώρα ας επιστρέψουμε στην εξήγηση.
Εύρεση Βασικής Εφικτής Λύσης
Μια βασική εφικτή λύση (BFS) είναι μια λύση σε ένα πρόβλημα γραμμικής βελτιστοποίησης που πληροί όλους τους περιορισμούς και έχει τον μικρότερο αριθμό μη μηδενικών μεταβλητών.
Κάθε BFS είναι μια γωνία του πολυέδρου των εφικτών λύσεων από γεωμετρική άποψη.
Εάν υπάρχει η καλύτερη λύση, πρέπει να υπάρχει και το καλύτερο πρώτο βήμα.
Σε αυτό το άρθρο, θα μιλήσουμε για το πώς να βρείτε μια αρχική βασική εφικτή λύση, πώς να βρείτε όλες τις βασικές εφικτές λύσεις και πώς να βρείτε μια βασική εφικτή λύση χωρίς χαλαρές μεταβλητές.
Εύρεση μιας αρχικής βασικής εφικτής λύσης
Μπορούμε να χρησιμοποιήσουμε διαφορετικές μεθόδους, ανάλογα με το πώς έχει ρυθμιστεί το πρόβλημα, για να βρούμε μια αρχική βασική λύση που λειτουργεί για ένα πρόβλημα γραμμικής βελτιστοποίησης.
Ένας τρόπος είναι να προσθέσετε μεταβλητές slack στους περιορισμούς των ανισοτήτων και να μηδενίσετε όλες τις άλλες μεταβλητές.
Οι μεταβλητές slack γίνονται οι βασικές μεταβλητές και οι υπόλοιπες είναι μη βασικές μεταβλητές.
Η μέθοδος Simplex δύο φάσεων είναι ένας άλλος τρόπος επίλυσης του προβλήματος.
Αυτή η μέθοδος περιλαμβάνει την επίλυση ενός επιπλέον γραμμικού προβλήματος προγραμματισμού για την εύρεση μιας αρχικής βασικής λύσης που είναι εφικτή.
Μόλις βρεθεί μια αρχική βασική εφικτή λύση, η μέθοδος Simplex μπορεί να χρησιμοποιηθεί για τη μετάβαση από τη μία βασική εφικτή λύση στην επόμενη και στη συνέχεια στην καλύτερη λύση.
Εύρεση όλων των βασικών εφικτών λύσεων
Μπορεί να υπάρχουν περισσότερες από μία βασικές λύσεις που να λειτουργούν για ένα γραμμικό πρόγραμμα.
Μπορούμε να αλλάξουμε το σύστημα προσθέτοντας μεταβλητές slack και στη συνέχεια να χρησιμοποιήσουμε το νέο σύστημα για να βρούμε όλες τις βασικές εφικτές λύσεις για ένα γραμμικό πρόγραμμα.
Στη συνέχεια, αυτές οι βασικές εφικτές λύσεις χρησιμοποιούνται για την εύρεση των βασικών εφικτών λύσεων για το αρχικό πρόβλημα.
Εύρεση βασικής εφικτής λύσης χωρίς μεταβλητές χαλαρότητας
Πρέπει να χρησιμοποιήσουμε μεταβλητές slack για να απαλλαγούμε από τους λιγότερους περιορισμούς, ώστε να μπορούμε να βρούμε μια βασική λύση που να λειτουργεί χωρίς μεταβλητές slack.
Μια μεταβλητή slack είναι απλώς η διαφορά μεταξύ της δεξιάς πλευράς ενός περιορισμού και της αριστερής πλευράς.
Για παράδειγμα, για τον πρώτο περιορισμό, ορίζουμε μια χαλαρή μεταβλητή x4 = 14 - 2x1 - x2 - x3. Όσον αφορά αυτή τη νέα μεταβλητή, ο πρώτος περιορισμός είναι απλώς ισοδύναμος με x4 ≥ 0, που είναι περιορισμός θετικότητας για το x4.
Όταν προσθέτουμε αυτές τις χαλαρές μεταβλητές, παίρνουμε ένα γραμμικό πρόγραμμα που είναι ίδιο με το αρχικό, με τη διαφορά ότι όλοι οι περιορισμοί είναι είτε εξισώσεις είτε περιορισμοί που λένε ότι κάτι είναι θετικό.
Το σύνολο των βασικών μεταβλητών, που έχουν τιμές διαφορετικές από το μηδέν στη βασική λύση, ονομάζεται βάση.
Οι μεταβλητές που έχουν τιμή μηδέν στη βασική λύση δεν είναι βασικές μεταβλητές.
Για να βρούμε την καλύτερη λύση, πρέπει να βρούμε ένα διάνυσμα x που να πληροί όλους τους κανόνες και να έχει τη μεγαλύτερη ή τη μικρότερη τιμή για τον στόχο.
Αλλά η εύρεση της καλύτερης λύσης απαιτεί περισσότερα βήματα από την εύρεση μιας λύσης που να λειτουργεί και να μην έχει χαλαρές μεταβλητές.
Δεν είναι πάντα δυνατό να βρεθεί μια βασική λύση χωρίς χαλαρές μεταβλητές, ειδικά για προβλήματα με λιγότερους από περιορισμούς.
Για να βρείτε μια βασική εφικτή λύση, πρέπει να χρησιμοποιήσετε τη μέθοδο simplex ή άλλον αλγόριθμο γραμμικού προγραμματισμού για να αναζητήσετε μια λύση που να πληροί όλους τους περιορισμούς και να έχει τις λιγότερες μη μηδενικές μεταβλητές.
Ιδιότητες και Σημασία Βασικής Εφικτής Λύσης
Ιδιότητες Βασικής Εφικτής Λύσης
Μια βασική εφικτή λύση έχει το πολύ m μεταβλητές που δεν είναι μηδέν και τουλάχιστον nm μεταβλητές που είναι μηδέν, όπου n είναι ο αριθμός των μεταβλητών απόφασης και m είναι ο αριθμός των περιορισμών.
Ένα BFS είναι μια γωνία του πολυέδρου των πιθανών λύσεων και κάθε BFS έχει n ενεργούς περιορισμούς που είναι γραμμικά ανεξάρτητοι.
Εάν υπάρχει η καλύτερη λύση, πρέπει να υπάρχει και το καλύτερο πρώτο βήμα.
Το πιο σημαντικό πράγμα για τις βασικές εφικτές λύσεις είναι ότι αποτελούν τα άκρα του συνόλου των κυρτών λύσεων για ένα πρόβλημα γραμμικού προγραμματισμού.
Για να βρείτε την καλύτερη απάντηση, ο αλγόριθμος simplex περνάει από μια σειρά BFS.
Ο αλγόριθμος Simplex αναζητά όλες τις βασικές πιθανές λύσεις με οργανωμένο τρόπο για να βρει την καλύτερη.
Σημασία Βασικής Εφικτής Λύσης
Η εύρεση μιας βασικής λύσης που είναι δυνατή είναι σημαντική γιατί βοηθά στην εύρεση της καλύτερης απάντησης σε προβλήματα γραμμικού προγραμματισμού.
Δίνει επίσης στους σύνθετους αλγόριθμους μια θέση για να ξεκινήσουν και μπορεί να χρησιμοποιηθεί για να καταλάβουμε εάν ένα γραμμικό πρόγραμμα είναι δυνατό ή όχι.
Για να βρείτε όλες τις βασικές εφικτές λύσεις για ένα γραμμικό πρόγραμμα, μπορείτε να αλλάξετε το σύστημα προσθέτοντας μεταβλητές slack και στη συνέχεια να χρησιμοποιήσετε το αλλαγμένο σύστημα για να βρείτε όλες τις βασικές εφικτές λύσεις.
Στη συνέχεια, αυτές οι βασικές εφικτές λύσεις χρησιμοποιούνται για την εύρεση των βασικών εφικτών λύσεων για το αρχικό πρόβλημα.
Βίντεο: Βασικές εφικτές λύσεις
Συμβουλή: Ενεργοποιήστε το κουμπί υπότιτλων εάν το χρειάζεστε. Επιλέξτε «αυτόματη μετάφραση» στο κουμπί ρυθμίσεων, εάν δεν είστε εξοικειωμένοι με την ομιλούμενη γλώσσα. Ίσως χρειαστεί να κάνετε πρώτα κλικ στη γλώσσα του βίντεο προτού η αγαπημένη σας γλώσσα γίνει διαθέσιμη για μετάφραση.
Θήκες χρήσης
| Χρησιμοποιείται σε: | Περιγραφή: |
|---|---|
| Κατανομή των πόρων: | Το BFS μπορεί να χρησιμοποιηθεί για την κατανομή περιορισμένων πόρων μεταξύ πολλών έργων, έτσι ώστε τα περισσότερα να μπορούν να γίνουν με τα λιγότερα. Αυτή η μέθοδος μπορεί να χρησιμοποιηθεί σε πολλούς διαφορετικούς τομείς, όπως οι μεταφορές, η γεωργία και τα οικονομικά. |
| Βελτιστοποίηση του Δικτύου: | Το BFS μπορεί να χρησιμοποιηθεί για την καλύτερη λειτουργία των δικτύων επικοινωνίας, μεταφορών και logistics. Το BFS μπορεί να βοηθήσει στην εύρεση των καλύτερων διαδρομών για αγαθά και υπηρεσίες, να μειώσει το χρόνο και τα χρήματα που δαπανώνται για τη μεταφορά και να επιταχύνει και να κάνει πιο ακριβείς παραδόσεις. |
| Προγραμματισμός Παραγωγής: | Το BFS μπορεί να χρησιμοποιηθεί για τον προγραμματισμό της παραγωγής έτσι ώστε οι πόροι όπως η εργασία, οι πρώτες ύλες και ο εξοπλισμός να χρησιμοποιούνται με τον καλύτερο δυνατό τρόπο για να αξιοποιηθούν στο έπακρο. Το BFS μπορεί να βοηθήσει στη μείωση του κόστους παραγωγής, στη μείωση των απορριμμάτων και στη βελτίωση της αποδοτικότητας. |
| Οικονομικός σχεδιασμός: | Στον χρηματοοικονομικό σχεδιασμό, το BFS μπορεί να χρησιμοποιηθεί για τη βελτιστοποίηση των επενδυτικών χαρτοφυλακίων, τη μείωση του κινδύνου και την επιστροφή των περισσότερων χρημάτων. Το BFS μπορεί να σας βοηθήσει να βρείτε τον καλύτερο τρόπο για να μοιράσετε περιουσιακά στοιχεία, να μειώσετε το κόστος συναλλαγής και να κερδίσετε περισσότερα χρήματα. |
| Διαχείριση της Εφοδιαστικής Αλυσίδας: | Το BFS μπορεί να χρησιμοποιηθεί για τη βελτίωση της ροής αγαθών και υπηρεσιών από τους προμηθευτές στους πελάτες ως μέρος της διαχείρισης της εφοδιαστικής αλυσίδας. Το BFS μπορεί να σας βοηθήσει να βρείτε την καλύτερη ποσότητα αποθεμάτων που μπορείτε να διατηρήσετε, να συντομεύσει τους χρόνους παράδοσης και να βελτιώσει την εξυπηρέτηση πελατών. |
συμπέρασμα
Καθώς αυτή η ματιά σε βασικές εφικτές λύσεις πλησιάζει στο τέλος της, είναι σαφές ότι αποτελούν σημαντικό εργαλείο για κάθε μηχανικό ή φοιτητή μηχανικού.
Από την εξεύρεση του καλύτερου τρόπου δημιουργίας ενός περίπλοκου συστήματος έως την αξιοποίηση των διαθέσιμων πόρων, οι βασικές εφικτές λύσεις παρέχουν ένα πλαίσιο για να έχετε το καλύτερο δυνατό αποτέλεσμα.
Αλλά περισσότερο από το να είναι απλά χρήσιμα, δείχνουν πόσο κομψά και όμορφα μπορεί να είναι τα μαθηματικά.
Είναι εκπληκτικό ότι μπορείτε να συνοψίσετε πολύπλοκα προβλήματα σε ένα απλό σύνολο εξισώσεων και στη συνέχεια να χρησιμοποιήσετε αυτές τις εξισώσεις για να λύσετε προβλήματα στον πραγματικό κόσμο.
Είναι μια καλή υπενθύμιση ότι η μηχανική έχει να κάνει με την επίλυση προβλημάτων και ότι χρησιμοποιώντας τη δύναμη των μαθηματικών, μπορούμε να βρούμε απαντήσεις που κάποτε θεωρούνταν αδύνατες.
Έτσι, καθώς μαθαίνετε περισσότερα για τη μηχανική, έχετε κατά νου όσα έχετε μάθει για απλές λύσεις που λειτουργούν και χρησιμοποιήστε τις για να κάνετε τον κόσμο ένα καλύτερο, πιο αποτελεσματικό μέρος.
Σύνδεσμοι και παραπομπές
Βιβλία:
- Γραμμικός Προγραμματισμός: Θεμέλια και Επεκτάσεις
- Γραμμικός Προγραμματισμός: Θεωρία και Εφαρμογές
Κοινοποίηση στο…
