Πολλά καθήκοντα οικονομικής φύσης, προβλήματαΟ προγραμματισμός και ακόμη και η επίλυση θεμάτων από άλλους τομείς της ανθρώπινης ζωής σχετίζεται με μεταβλητές που σχετίζονται με ακέραιους αριθμούς. Ως αποτέλεσμα της ανάλυσής τους και της αναζήτησης βέλτιστων λύσεων, εμφανίστηκε η έννοια ενός ακραίου προβλήματος. Τα χαρακτηριστικά του είναι το παραπάνω χαρακτηριστικό για να πάρει μια ακέραια τιμή και η ίδια η εργασία θεωρείται στα μαθηματικά ως ακέραιος προγραμματισμός.
Ως κύρια κατεύθυνση χρήσηςεργασίες με μεταβλητές που λαμβάνουν ακέραιες τιμές είναι η βελτιστοποίηση. Μια μέθοδος που χρησιμοποιεί ακέραιο γραμμικό προγραμματισμό ονομάζεται επίσης μέθοδος αποκοπής.
Η μέθοδος Gomori πήρε το όνομά της με το όνομαμαθηματικά, ο πρώτος που ανέπτυξε έναν αλγόριθμο το 1957-1958, ο οποίος εξακολουθεί να χρησιμοποιείται ευρέως για την επίλυση ακέραιων προβλημάτων γραμμικού προγραμματισμού. Η κανονική μορφή του ακέραιου προβλήματος προγραμματισμού μας επιτρέπει να αποκαλύψουμε πλήρως και πλήρως τα πλεονεκτήματα αυτής της μεθόδου.
Η μέθοδος Gomori όπως εφαρμόζεται στη γραμμικήΟ προγραμματισμός περιπλέκει σημαντικά το έργο της εύρεσης βέλτιστων τιμών. Σε τελική ανάλυση, η ακεραιότητα είναι η κύρια συνθήκη, εκτός από όλες τις παραμέτρους του προβλήματος. Υπάρχουν συχνές περιπτώσεις όταν ένα πρόβλημα, με αποδεκτά (ακέραια) σχέδια, εάν οι αντικειμενικές συναρτήσεις έχουν περιορισμούς σε ένα αποδεκτό σύνολο, δεν φτάνει στο μέγιστο της λύσης. Αυτό οφείλεται στην απουσία ακέραιων λύσεων. Χωρίς αυτήν την κατάσταση, κατά κανόνα, ένας κατάλληλος φορέας βρίσκεται με τη μορφή μιας λύσης.
Για να τεκμηριωθούν οι αριθμητικοί αλγόριθμοι στην επίλυση προβλημάτων, καθίσταται απαραίτητο να επιβληθούν διάφοροι πρόσθετοι όροι.
Χρησιμοποιώντας τη μέθοδο Gomori, πολλοίσχέδια προβλημάτων που περιορίζονται από το λεγόμενο πολυέδρον λύσεων. Με βάση αυτό προκύπτει ότι το σύνολο όλων των ακέραιων σχεδίων για την εργασία έχει μια πεπερασμένη τιμή.
Επίσης, για να διασφαλιστεί η ακεραιότητα της συνάρτησης, θεωρείται ότι οι συντελεστές των τιμών είναι επίσης ακέραιοι. Παρά τη σοβαρότητα τέτοιων καταστάσεων, είναι δυνατόν να χαλαρώσετε λίγο.
Η μέθοδος Gomori, στην ουσία, περιλαμβάνει την κατασκευή περιορισμών που διακόπτουν λύσεις που δεν είναι ακέραιες. Ταυτόχρονα, καμία λύση του ακέραιου σχεδίου δεν διακόπτεται.
Ο αλγόριθμος για την επίλυση του προβλήματος περιλαμβάνειεύρεση κατάλληλων παραλλαγών με τη μέθοδο simplex, χωρίς να λαμβάνονται υπόψη οι ακέραιες συνθήκες. Εάν σε όλα τα στοιχεία του βέλτιστου σχεδίου υπάρχουν λύσεις που σχετίζονται με ακέραιους αριθμούς, τότε μπορούμε να υποθέσουμε ότι επιτυγχάνεται ο στόχος του ακέραιου προγραμματισμού. Είναι πιθανό να ανακαλυφθεί μια αδιαλυτότητα του προβλήματος, οπότε έχουμε απόδειξη ότι το πρόβλημα του ακέραιου προγραμματισμού δεν έχει λύση.
Η επιλογή είναι δυνατή όταν στα εξαρτήματαΗ βέλτιστη λύση περιέχει μη ακέραιους αριθμούς. Σε αυτήν την περίπτωση, ένας νέος περιορισμός προστίθεται σε όλους τους περιορισμούς της εργασίας. Ένας νέος περιορισμός χαρακτηρίζεται από την παρουσία ορισμένων ιδιοτήτων. Πρώτα απ 'όλα, πρέπει να είναι γραμμικό, πρέπει να κόβει ένα σχέδιο χωρίς ακέραιο από το βέλτιστο σύνολο. Δεν πρέπει να χαθεί ακέραιος, περικομμένος.
Κατά την κατασκευή περιορισμών, πρέπει κανείς να επιλέξει το στοιχείο του βέλτιστου σχεδίου με το μεγαλύτερο κλασματικό μέρος. Αυτός ο περιορισμός θα προστεθεί στον υπάρχοντα απλό πίνακα.
Βρίσκουμε μια λύση στο πρόβλημα χρησιμοποιώνταςσυνηθισμένοι απλοί μετασχηματισμοί. Ελέγχουμε τη λύση του προβλήματος για την ύπαρξη ενός ακέραιου βέλτιστου σχεδίου, εάν ικανοποιείται η προϋπόθεση, τότε το πρόβλημα επιλύεται. Εάν, και πάλι, επιτευχθεί ένα αποτέλεσμα με την παρουσία μη ακέραιων λύσεων, τότε εισάγουμε έναν πρόσθετο περιορισμό και επαναλαμβάνουμε τη διαδικασία υπολογισμού.
Έχοντας ολοκληρώσει έναν πεπερασμένο αριθμό επαναλήψεων, λαμβάνουμε το βέλτιστο σχέδιο για το πρόβλημα που τίθεται στον ακέραιο προγραμματισμό ή αποδεικνύουμε τη μη επίλυση του προβλήματος.
