Ακέραιος προγραμματισμός

Ένα πρόβλημα γραμμικού προγραμματισμού χρησιμοποιείται για να βρεθεί είτε το μέγιστο είτε το ελάχιστο μιας αντικειμενικής συνάρτησης που υπόκειται σε ορισμένους περιορισμούς. Αυτοί οι περιορισμοί είναι συνήθως ανισότητες. Όταν πληρούνται αυτοί οι περιορισμοί, κάποιος λαμβάνει μια εφικτή λύση. Όταν μία από αυτές τις λύσεις είναι είτε η μέγιστη είτε η ελάχιστη σύμφωνα με την αντικειμενική συνάρτηση, λαμβάνεται μια βέλτιστη λύση/

Σε πολλές πραγματικές καταστάσεις μπορεί κανείς να απαιτήσει οι μεταβλητές απόφασης να είναι ακέραιες καθώς πρέπει να βρεις τον αριθμό των λεωφορείων που απαιτούνται ή τον αριθμό του προσωπικού που απαιτείται να αναπτυχθεί κ.λπ.. Τέτοιες κατηγορίες προβλημάτων ονομάζονται προβλήματα προγραμματισμού ακέραιων αριθμών.

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

Υπάρχουν διάφοροι τύποι μεθόδων που χρησιμοποιούνται για την επίλυση προβλημάτων Γραμμικού Προγραμματισμού Ακέραιων Αριθμών. Η πιο συχνά χρησιμοποιούμενη μέθοδος είναι η μέθοδος διακλάδωσης και δέσμευσης.

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

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

Μια επέκταση του προβλήματος προγραμματισμού ακέραιων αριθμών είναι το πρόβλημα προγραμματισμού ακέραιου αριθμού 0-1 όπου οι μεταβλητές απόφασης μπορούν να λάβουν μόνο 0 ή 1. Αυτού του είδους τα προβλήματα είναι ιδιαίτερα χρήσιμα για την επίλυση προβλημάτων παρόμοια με το πρόβλημα του σάκου knap.



Source by Srinivasa Gopal

Σχολιάστε