Πίνακας περιεχομένων:
Ορισμός - Τι σημαίνει η μέθοδος Simplex;
Η μέθοδος simplex, στη μαθηματική βελτιστοποίηση, είναι ένας πολύ γνωστός αλγόριθμος που χρησιμοποιείται για τον γραμμικό προγραμματισμό. Σύμφωνα με το περιοδικό Computing in Science & Engineering, αυτή η μέθοδος θεωρείται ένας από τους 10 κορυφαίους αλγόριθμους που δημιουργήθηκαν κατά τον εικοστό αιώνα.
Η μέθοδος simplex παρουσιάζει μια οργανωμένη στρατηγική για την αξιολόγηση των κορυφών της εφικτής περιοχής. Αυτό βοηθά να καταλάβουμε τη βέλτιστη τιμή της αντικειμενικής λειτουργίας.
Ο Γιώργος Dantzig ανέπτυξε τη μέθοδο simplex το 1946.
Η μέθοδος είναι επίσης γνωστή ως ο αλγόριθμος simplex.
Η Techopedia εξηγεί τη μέθοδο Simplex
Η μέθοδος simplex χρησιμοποιείται για την εξάλειψη των ζητημάτων στον γραμμικό προγραμματισμό. Εξετάζει τις παρακείμενες κορυφές των εφικτών συνόλων διαδοχικά για να διασφαλίσει ότι σε κάθε νέα κορυφή η αντικειμενική συνάρτηση αυξάνεται ή δεν επηρεάζεται. Σε γενικές γραμμές, η μέθοδος simplex είναι εξαιρετικά ισχυρή, η οποία συνήθως απαιτεί επαναλήψεις 2m έως 3m (εδώ το m υποδηλώνει το εύρος των περιορισμών ισότητας) και συγκλίνει στον αναμενόμενο πολυωνυμικό χρόνο για συγκεκριμένες κατανομές τυχαίων εισροών.
Η μέθοδος simplex χρησιμοποιεί μια συστηματική στρατηγική για τη δημιουργία και δοκιμή λύσεων υποψήφιων κορυφών σε ένα γραμμικό πρόγραμμα. Σε κάθε επανάληψη, επιλέγει τη μεταβλητή που μπορεί να κάνει τη μεγαλύτερη τροποποίηση προς την ελάχιστη λύση. Αυτή η μεταβλητή έπειτα αντικαθιστά μία από τις μεταβλητές της, η οποία την περιορίζει δραστικά, αλλάζοντας έτσι τη μέθοδο simplex σε ένα άλλο μέρος της λύσης και προς την τελική λύση.
Επιπλέον, η μέθοδος simplex είναι σε θέση να αξιολογήσει εάν υπάρχει πραγματικά λύση. Μπορεί να παρατηρηθεί ότι ο αλγόριθμος είναι άπληστος καθώς επιλέγει την καλύτερη επιλογή σε κάθε επανάληψη, χωρίς ζήτηση πληροφοριών από προηγούμενες ή μελλοντικές επαναλήψεις.
Μερικές φορές, η κύρια δομή δεδομένων που εφαρμόζεται με τη μέθοδο simplex αναφέρεται ως λεξικό. Τα λεξικά περιλαμβάνουν μια απεικόνιση των συνόλων εξισώσεων που έχουν ρυθμιστεί σωστά στην υπάρχουσα βάση. Τα λεξικά μπορούν να χρησιμοποιηθούν για να δώσουν μια διαισθητική κατανόηση του γιατί όλες οι μεταβλητές εισέρχονται και αφήνουν τη βάση.
