Πώς να χρησιμοποιήσετε Ακέραιος Γραμμικός Προγραμματισμός

Ακέραιος γραμμικός προγραμματισμός είναι η επιστήμη της μοντελοποίησης ενός προβλήματος που είτε ελαχιστοποιεί ή μεγιστοποιεί μια γραμμική αντικειμενική συνάρτηση , σύμφωνα με ένα σύνολο περιορισμών που εκφράζονται ως γραμμικές ανισότητες . Όταν λυθεί εντελώς , το διάλυμα στον ακέραιο γραμμικό πρόγραμμα εγγυάται τη βέλτιστη λύση στο πρόβλημα. Ωστόσο , η πολυπλοκότητα του προβλήματος κλιμακώνεται εκθετικά με το μέγεθος του προβλήματος . Ως εκ τούτου , μπορεί να πάρει πολύ χρόνο για να καταλήξουμε στην τελική λύση . Εναλλακτικά , το πρόβλημα μπορεί να επιλυθεί εν μέρει και μπορούν να εξερευνηθούν διαφορετικές heuristics για την επίτευξη μιας υπο - βέλτιστη λύση σε μικρότερο χρονικό διάστημα . Τα πράγματα που θα χρειαστείτε Γραμμική λύτης προγραμματισμού
υπολογιστών με επαρκή μνήμη και επεξεργαστική ισχύ

Παρουσίαση Περισσότερες οδηγίες
Διατύπωση και επίλυση γραμμικών προγραμμάτων
Η

1 Αποφασίστε αν το πρόβλημα είναι ένα " μεγιστοποίηση " πρόβλημα ή " ελαχιστοποίηση " πρόβλημα . Ένα πρόβλημα μεγιστοποίησης προσπαθεί να βρει μια λύση , όπως όταν η αντικειμενική συνάρτηση μεγιστοποιείται . Ένα πρόβλημα ελαχιστοποίησης προσπαθεί να βρει μια λύση όπου η αντικειμενική συνάρτηση ελαχιστοποιείται . Για παράδειγμα , το πρόβλημα της εύρεσης της συντομότερης διαδρομής μεταξύ δύο σημείων είναι ένα πρόβλημα ελαχιστοποίησης. Από την άλλη πλευρά , το πρόβλημα για τη συσκευασία των μέγιστο αριθμό διαφορετικού μεγέθους βότσαλα σε ένα μπουκάλι είναι ένα πρόβλημα μεγιστοποίησης . 2

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

μοντελοποιήσει την αντικειμενική συνάρτηση . Η αντικειμενική συνάρτηση διαμορφώνεται ως άθροισμα των γινομένων των μεταβλητών και των επιπτώσεών τους στην τελική λύση . Για παράδειγμα, εάν το πρόβλημα είναι να ελαχιστοποιηθεί η απόσταση μεταξύ δύο κόμβων σε μια γραφική παράσταση, κάθε σύνδεση μεταξύ δύο κόμβων θα είναι μια μεταβλητή που παίρνει την τιμή 0 ή 1 , και η συμβολή του στην αντικειμενική συνάρτηση θα είναι η απόσταση μεταξύ των κόμβων . Στην περίπτωση αυτή, η μεταβλητή μπορεί να ονομάζεται "X ( i, j) , " όπου το "i " και " j" είναι οποιαδήποτε δύο κόμβους στη γραφική παράσταση , και η απόσταση μεταξύ των δύο κόμβων μπορεί να είναι " V ( i, j) . " X ( i, j) θα είναι 1 , εάν η σύνδεση είναι μέρος της τελικής διαδρομής μεταξύ των δύο κόμβων . Ως εκ τούτου , η αντικειμενική συνάρτηση θα είναι να ελαχιστοποιηθεί το άθροισμα των V ( i, j ) * X ( i , j ) , όπου το άθροισμα είναι πάνω από όλες τις συνδέσεις .
Η

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

X ( i, j) μπορεί να είναι είτε 0 είτε 1 . Ως εκ τούτου , το Χ (ί , j) πρέπει να είναι μεγαλύτερη από ή ίση με 0 , και το Χ (ί , j) πρέπει να είναι μικρότερη από ή ίση με 1 .

Εάν επιλεγεί σύνδεσης Χ ( i, j) , ακριβώς μία σύνδεση από τον κόμβο " j" σε κάποιο άλλο κόμβο , εκτός από " Ι " πρέπει να επιλεγεί. Έτσι , το Χ (ί , j) θα πρέπει να είναι μεγαλύτερη ή ίση με το άθροισμα όλων των μεταβλητών του τύπου Χ ( j, k ), όπου "Κ " δεν είναι ίσο με το "i ".

Μία σύνδεση από θα πρέπει να επιλέγεται το αρχικό κόμβο. Ως εκ τούτου , άθροισμα των Χ ( n, k) θα πρέπει να είναι 1 , όπου " n" είναι το αρχικό κόμβο. Ομοίως , άθροισμα των X ( k , m) πρέπει να είναι 1 , όπου το " m" είναι το τελικό κόμβο .
5

μοντέλο το πρόβλημα είτε στην Μαθηματική Σύστημα Προγραμματισμού μορφή ( MPS ) , ή η Γραμμική Προγραμματισμός ( LP ) μορφή .
Η 6

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

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