Ακέραια μοντέλα γραμμικού προγραμματισμού. N.Yu. Kolomarova Επίλυση προβλημάτων γραμμικού ακέραιου προγραμματισμού με τη μέθοδο Gomori

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

Πρόβλημα γραμμικού ακέραιου προγραμματισμούδιατυπώνεται ως εξής: βρείτε μια τέτοια λύση (σχέδιο)Εγώ, για την οποία η γραμμική συνάρτηση

λαμβάνει τη μέγιστη ή την ελάχιστη τιμή υπό περιορισμούς

(8.2)

(8.3)

- ολόκληροι αριθμοί. (8.4)

Πρέπει να σημειωθεί ότι το κλασικό πρόβλημα μεταφοράς και κάποια άλλα προβλήματα τύπου μεταφοράς δίνουν «αυτόματα» λύση στο πρόβλημα σε ακέραιους αριθμούς (αν, φυσικά, οι παράμετροι των συνθηκών είναι ακέραιοι). Ωστόσο, στη γενική περίπτωση, η ακέραια συνθήκη (8.4), που προστίθεται στα συνηθισμένα προβλήματα γραμμικού προγραμματισμού, περιπλέκει σημαντικά τη λύση της.

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

Οι μέθοδοι βελτιστοποίησης ακεραίων μπορούν να χωριστούν σε τρεις κύριες ομάδες: α) μεθόδους κλαδέματος. β) συνδυαστικές μέθοδοι. γ) κατά προσέγγιση μέθοδοι. Ας ρίξουμε μια πιο προσεκτική ματιά στις μεθόδους κοπής.

Μέθοδοι κοπής. Μέθοδος Gomori

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

• Πρέπει να είναι γραμμικό.
• θα πρέπει να κόψει το βέλτιστο μη ακέραιο σχέδιο που βρέθηκε.
• δεν πρέπει να κόβει κανένα ακέραιο σχέδιο.

Ένας πρόσθετος περιορισμός με αυτές τις ιδιότητες ονομάζεται σωστή κοπή.

Γεωμετρικά, η προσθήκη κάθε γραμμικού περιορισμού αντιστοιχεί στη χάραξη μιας ευθείας γραμμής (υπερεπίπεδο) που αποκόπτει μέρος της από το πολύγωνο της λύσης (πολύεδρο) μαζί με το βέλτιστο σημείο με μη ακέραιες συντεταγμένες, αλλά δεν επηρεάζει κανέναν από τους ακέραιους αριθμούς. σημεία αυτού του πολυέδρου. Ως αποτέλεσμα, το νέο πολύεδρο λύσης περιέχει όλα τα ακέραια σημεία που περιέχονται

στο αρχικό πολύεδρο των λύσεων, και κατά συνέπεια η βέλτιστη λύση που προκύπτει με αυτό το πολύεδρο θα είναι ακέραιος (Εικ. 8.1).

Ένας από τους αλγόριθμους για την επίλυση του προβλήματος γραμμικού ακέραιου προγραμματισμού (8.1)-(8.4), που προτείνεται από τον R. Gomori, βασίζεται στη μέθοδο simplex και χρησιμοποιεί μια αρκετά απλή μέθοδο για την κατασκευή μιας σωστής αποκοπής.

Έστω ότι το πρόβλημα γραμμικού προγραμματισμού (8.1)-(8.3) έχει ένα τελικό βέλτιστο και στο τελευταίο βήμα της επίλυσής του χρησιμοποιώντας τη μέθοδο simplex λαμβάνουμε τις ακόλουθες εξισώσεις που εκφράζουν τις κύριες μεταβλητές μέσω μη βασικών μεταβλητών της βέλτιστης λύσης:

(8.5)

Άρα η βέλτιστη λύση στο πρόβλημα (8.1)-(8.3) είναι το i, στο οποίο, για παράδειγμα, το β; – μη ακέραιο συστατικό. Σε αυτή την περίπτωση, μπορεί να αποδειχθεί ότι η ανισότητα που σχηματίζεται από Εγώ-στην εξίσωση του συστήματος (8.5), έχει όλες τις ιδιότητες μιας κανονικής αποκοπής.

Για την επίλυση του προβλήματος του ακέραιου γραμμικού προγραμματισμού (8.1)-(8.4) με τη μέθοδο Gomori, χρησιμοποιείται ο ακόλουθος αλγόριθμος.

• 1. Χρησιμοποιώντας τη μέθοδο simplex, λύστε το πρόβλημα (8.1)-(8.3) χωρίς να λάβετε υπόψη την ακέραια συνθήκη. Εάν όλα τα στοιχεία του βέλτιστου σχεδίου είναι ακέραιοι, τότε είναι βέλτιστο για το πρόβλημα προγραμματισμού ακέραιων αριθμών (8.1)-(8.4). Αν το πρώτο πρόβλημα (8.1)-(8.3) είναι άλυτο (δηλαδή δεν έχει τελικό βέλτιστο ή οι συνθήκες του είναι αντιφατικές), τότε το δεύτερο πρόβλημα (8.1)-(8.4) είναι επίσης άλυτο.
• 2. Εάν μεταξύ των συνιστωσών της βέλτιστης λύσης υπάρχουν και μη ακέραιοι, τότε επιλέξτε το στοιχείο με το μεγαλύτερο ακέραιο μέρος και, χρησιμοποιώντας την αντίστοιχη εξίσωση του συστήματος (8.5), σχηματίστε τη σωστή αποκοπή (8.6).
• 3. Με την εισαγωγή μιας πρόσθετης μη αρνητικής ακέραιας μεταβλητής, μετατρέψτε την ανισότητα (8.6) σε ισοδύναμη εξίσωση και συμπεριλάβετε την στο σύστημα περιορισμών (8.2).
• 4. Λύστε το εκτεταμένο πρόβλημα που προκύπτει χρησιμοποιώντας τη μέθοδο simplex. Εάν το βέλτιστο σχέδιο που βρέθηκε είναι ακέραιος, τότε λύνεται το πρόβλημα προγραμματισμού ακέραιου αριθμού (8.1)–(8.4). Διαφορετικά, επιστρέψτε στο βήμα 2 του αλγορίθμου.

Εάν το πρόβλημα είναι επιλύσιμο σε ακέραιους αριθμούς, τότε μετά από έναν πεπερασμένο αριθμό βημάτων (επαναλήψεις) θα βρεθεί το βέλτιστο ακέραιο σχέδιο.

1 Στην ανισότητα (8.6) υπάρχει ένα σύμβολο ( ), που σημαίνει το κλασματικό μέρος του αριθμού. Ακέραιο μέρος του αριθμού αείναι ο μεγαλύτερος ακέραιος αριθμός [σε] που δεν υπερβαίνει α, κλασματικό μέρος ενός αριθμού– αριθμός (α), ίσος με τη διαφορά μεταξύ αυτού του αριθμού και του ακέραιου μέρους του, δηλ. (α) = α-[β].

Για παράδειγμα, για (σημείωση, ακριβώς -3, όχι -2) και

Αν στη διαδικασία επίλυσης εμφανιστεί μια εξίσωση (εκφράζοντας την κύρια μεταβλητή ως προς τις μη βασικές) με μη ακέραιο ελεύθερο όρο και ακέραιους εναπομείναντες συντελεστές, τότε η αντίστοιχη εξίσωση δεν έχει λύση σε ακέραιους αριθμούς. Σε αυτήν την περίπτωση, αυτό το πρόβλημα δεν έχει βέλτιστη λύση ακέραιου αριθμού.

8.1. Για την αγορά εξοπλισμού διαλογής σιτηρών, ο αγρότης διαθέτει 34 den. μονάδες Ο εξοπλισμός πρέπει να τοποθετείται σε επιφάνεια που δεν υπερβαίνει τα 60 τετραγωνικά μέτρα. Ο αγρότης μπορεί να παραγγείλει δύο τύπους εξοπλισμού: λιγότερο ισχυρά μηχανήματα όπως ΕΝΑαξίας 3 ντεν. μονάδες που απαιτούν επιφάνεια παραγωγής 3 τ. m (συμπεριλαμβανομένων των πασών) και παραγωγικότητα ανά βάρδια 2 τόνων σιτηρών και πιο ισχυρά μηχανήματα όπως ΣΕκόστος 4 den. μονάδες που καταλαμβάνουν έκταση 5 τ. m, και παραγωγικότητα ανά βάρδια 3 τόνων σιτηρών υψηλής ποιότητας.

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

Λύση.Ας υποδηλώσουμε με τον αριθμό των μηχανών, αντίστοιχα, τον τύπο ΕΝΑΚαι ΣΕ,μέσω Z – συνολική παραγωγικότητα. Τότε θα πάρει τη μορφή το μαθηματικό μοντέλο του προβλήματος

(!!!8.8)

με περιορισμούς:

(8.2)

- ολόκληροι αριθμοί. (8.4)

Ας φέρουμε το πρόβλημα σε κανονική μορφή εισάγοντας επιπλέον μη αρνητικές μεταβλητές. Παίρνουμε ένα σύστημα περιορισμών:

(8.5)

Επιλύουμε το πρόβλημα χρησιμοποιώντας τη μέθοδο simplex. Για λόγους σαφήνειας, απεικονίζουμε τη λύση γραφικά (Εικ. 8.2).

Στο Σχ. 8.2 OKLM– περιοχή των εφικτών λύσεων στο πρόβλημα (8.D)–(8.3"), που περιορίζεται από ευθείες γραμμές (1), (2), (3) και άξονες συντεταγμένων. μεγάλο(2/3; 8) – σημείο βέλτιστης, αλλά μη ακέραιης λύσης του προβλήματος (8.1")–(8.3"); (4) – μια ευθεία γραμμή που αποκόπτει αυτή τη μη ακέραια λύση. ΟΚΝΜ– περιοχή των εφικτών λύσεων του εκτεταμένου προβλήματος (8.1")–(8.3"), (8.6"); N( 2; 7) – σημείο βέλτιστης ακέραιας λύσης.

Βήμα Ι. Βασικές μεταβλητές Μη βασικές μεταβλητές

Η πρώτη βασική λύση είναι να υποθέσουμε

μου. Αντίστοιχη γραμμική τιμή συνάρτησης

Μετατρέπουμε στις κύριες μεταβλητές τη μεταβλητή που περιλαμβάνεται στην έκφραση της γραμμικής συνάρτησης με τον μεγαλύτερο θετικό συντελεστή. Βρίσκουμε τη μέγιστη δυνατή τιμή της μεταβλητής που «επιτρέπει»

αποδεχτείτε ένα σύστημα περιορισμών που βασίζεται στην προϋπόθεση των ελάχιστων αντίστοιχων σχέσεων:

εκείνοι. Η επίλυση (επισημασμένη) εξίσωση είναι η τρίτη. Στο Χ. 2 = 8 σε αυτή την εξίσωση Χ- = 0, και η μεταβλητή πηγαίνει σε μη βασική Χ 5.

Βήμα II.Βασικές Μεταβλητές Χ 2, Χ 3, Χ 4.

Μικρές μεταβλητές.g, xy

Μετά από μεταμορφώσεις παίρνουμε

Μετατροπή σε κύρια μεταβλητή και σε μη κύριες x4.

III βήμα.Κύριες μεταβλητές x, Χ 2, Χ 3.

Μη κύριες μεταβλητές x4, x5.

Μετά από μεταμορφώσεις παίρνουμε

Βασική λύση Χ., βέλτιστη για το πρόβλημα (8.1")–(8.3") (), αφού στην έκφραση της γραμμικής συνάρτησης

δεν υπάρχουν μη βασικές μεταβλητές με θετικούς συντελεστές.

Ωστόσο, η λύση ΧΤο 3 δεν ικανοποιεί την ακέραια συνθήκη (8.4") Χρησιμοποιώντας την πρώτη εξίσωση με τη μεταβλητή x να λαμβάνει μια μη ακέραια τιμή στη βέλτιστη λύση (2/3), δημιουργούμε έναν πρόσθετο περιορισμό (8.6):

Σημειώστε ότι, σύμφωνα με τις (8.5) και (8.6), παίρνουμε το κλασματικό μέρος ελεύθερο μέλος με το ίδιο πρόσημο,που έχει στην εξίσωση, και τα κλασματικά μέρη συντελεστές για δευτερεύουσες μεταβλητές x 4 και x- – με αντίθετα πρόσημα.

Από κλασματικά μέρη ,

, γράφουμε την τελευταία ανισότητα

(8.6")

Εισάγοντας μια πρόσθετη ακέραια μεταβλητή x6 ≥ 0, λαμβάνουμε την εξίσωση που ισοδυναμεί με την ανισότητα (8,6")

(8.7")

Η εξίσωση (8.7") πρέπει να συμπεριληφθεί στο σύστημα περιορισμών (8.5") του αρχικού κανονικού προβλήματος και στη συνέχεια να επαναλάβετε τη διαδικασία επίλυσης του προβλήματος χρησιμοποιώντας τη μέθοδο simplex σε σχέση με το εκτεταμένο πρόβλημα. Σε αυτήν την περίπτωση, για να μειωθεί ο αριθμός των βημάτων (επαναλήψεις), συνιστάται η εισαγωγή μιας πρόσθετης εξίσωσης (8,7") στο σύστημα που ελήφθη στο τελευταίο βήμα επίλυσης του προβλήματος (χωρίς την ακέραια συνθήκη).

IV βήμα.Βασικές Μεταβλητές Χ v Χ 2, x3, χβ.

Μη κύριες μεταβλητές x4, x5.

Η βασική λύση δεν επιτρέπεται

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

Για να ληφθεί μια αποδεκτή βασική λύση, είναι απαραίτητο να μετατραπεί στην κύρια μεταβλητή, η οποία περιλαμβάνεται με θετικό συντελεστή στην εξίσωση στην οποία ο ελεύθερος όρος είναι αρνητικός, δηλ. x, ή x. (σε αυτό το στάδιο δεν θεωρούμε γραμμική συνάρτηση). Μεταφράζουμε σε βασικές, για παράδειγμα, τη μεταβλητή x5.

Βήμα V.Οι κύριες μεταβλητές είναι x, x2, x3, x5.

Μη κύριες μεταβλητές x4, x6.

Παίρνουμε μετά από μεταμορφώσεις

Εφόσον δεν υπάρχουν κύριες μεταβλητές με θετικούς συντελεστές στην έκφραση μιας γραμμικής συνάρτησης, τότε ΧΤο 5 είναι η βέλτιστη λύση.

Άρα, Zmax = 25 για τη βέλτιστη ακέραια λύση Χ* = Χ 5 = (2; 7; 19; 0; 1; 0), δηλ. μέγιστη παραγωγικότητα 25 τόνων σιτηρών υψηλής ποιότητας ανά βάρδια μπορεί να επιτευχθεί με την αγορά 2 μηχανών τύπου L και 7 μηχανών τύπου ΣΕΤαυτόχρονα, η ακατοίκητη επιφάνεια των χώρων θα είναι 19 τετραγωνικά μέτρα. m, το υπόλοιπο των κεφαλαίων που διατέθηκαν είναι μηδέν, το αποθεματικό για αγορά είναι 1 μηχανή του τύπου ΣΕ(το έκτο συστατικό δεν έχει νόημα).

Σχόλιο. Για τη γεωμετρική ερμηνεία στο επίπεδο Ox, x2 (βλ. Εικ. 8.2) της αποκοπής (8.6"), οι μεταβλητές που περιλαμβάνονται σε αυτό είναι απαραίτητες Χ 4 και Χ-εκφραστεί μέσω των μεταβλητών x και x2. Λαμβάνουμε (δείτε 2η και 3η εξίσωση του συστήματος περιορισμών (8,5"))

• (βλ. γραμμή αποκοπής (4) στην Εικ. 8.2).
• 8.2. Υπάρχει ένας αρκετά μεγάλος αριθμός κορμών μήκους 3 μέτρων. αντίστοιχα. Κάθε κορμός μπορεί να κοπεί στα καθορισμένα κομμάτια με διάφορους τρόπους: 1) σε 2 κομμάτια αλλά 1,2 m. 2) για 1 τεμάχιο 1,2 m και 2 τεμάχια 0,9 m το καθένα. 3) για 3 τεμάχια των 0,9 m το καθένα Βρείτε τον αριθμό των κορμών που κόβονται με κάθε μέθοδο, έτσι ώστε να λαμβάνονται τεμάχια οποιουδήποτε τύπου από τον μικρότερο αριθμό κορμών.

Λύση.Ας υποδηλώσουμε με Χ() x2, x3 ο αριθμός των κορμών που πριονίστηκαν χρησιμοποιώντας 1, 2 και 3 μεθόδους, αντίστοιχα. Από αυτά μπορείτε να πάρετε 2xj +x2 κενά 1,2 m το καθένα και 2x x +3x2 κενά των 0,9 m το καθένα Ας υποδηλώσουμε τον συνολικό αριθμό των κορμών Ζ.Τότε θα πάρει τη μορφή το μαθηματικό μοντέλο του προβλήματος

με περιορισμούς:

Με την εισαγωγή πρόσθετων μεταβλητών

ανάγουμε το σύστημα των ανισοτήτων σε ένα ισοδύναμο σύστημα εξισώσεων:

(8.5")

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

III βήμα.Βασικές Μεταβλητές Χ v Χ 2.

Μη βασικές μεταβλητές Χστο ΧΕΝΑ , Χ 5.

δηλαδή με μια βέλτιστη λύση

Αποδείχθηκε ότι δύο συστατικά της βέλτιστης λύσης δεν ικανοποιούν την ακέραια συνθήκη (8,4") και το στοιχείο έχει το μεγαλύτερο ακέραιο μέρος Χ 2. Σύμφωνα με το ∏. 2 αλγόριθμοι για την επίλυση ενός προβλήματος ακέραιου προγραμματισμού (βλ. σελ. 166) χρησιμοποιώντας τη δεύτερη εξίσωση που περιέχει αυτή τη μεταβλητή Χ 2, δημιουργούμε έναν επιπλέον περιορισμό (8.6):

Ας βρούμε τα κλασματικά μέρη

και γράψτε την τελευταία ανισότητα στη φόρμα

(8.6")

Με την εισαγωγή μιας πρόσθετης μεταβλητής παίρνουμε

εξίσωση ισοδύναμη με ανισότητα (8,6"):

(8.7")

Ας εκφράσουμε από (8,7") την πρόσθετη μεταβλητή x6 και ας εισαγάγουμε την εξίσωση που προκύπτει στο σύστημα περιορισμών που είχαμε στο τελευταίο, III, βήμα επίλυσης του προβλήματος (8,1") - (8,3") (χωρίς την ακέραια συνθήκη ).

IV βήμα. Βασικές Μεταβλητές Χ{, Χστο Χ 6.

Μη βασικές μεταβλητές Χ 3, x4, Χ 5.

Επιλύοντας αυτό το εκτεταμένο πρόβλημα χρησιμοποιώντας τη μέθοδο simplex (καλούμε τους μαθητές να το κάνουν μόνοι τους), έχουμε τα εξής.

βήμα V. Κύριες μεταβλητές x); Χ 2, x3.

Μη κύριες μεταβλητές x4, x5, xb.

δηλαδή με μια βέλτιστη λύση

Η προκύπτουσα βέλτιστη λύση στο εκτεταμένο πρόβλημα (8,1")–(8,3"), (8,6") και πάλι δεν ικανοποιεί την ακέραια συνθήκη (8,4"). Σύμφωνα με την πρώτη εξίσωση με τη μεταβλητή Xj να λαμβάνει μια μη ακέραια τιμή στη βέλτιστη

λύση (), αφήνουμε το δεύτερο πρόσθετο όριο

ανάγνωση (8.6):

που φέρνουμε στο μυαλό μας

Χρησιμοποιώντας μια πρόσθετη μεταβλητή

Μειώνουμε αυτήν την ανισότητα σε μια ισοδύναμη εξίσωση, την οποία συμπεριλαμβάνουμε στο σύστημα περιορισμών που λήφθηκε στο τελευταίο, V, βήμα επίλυσης του εκτεταμένου προβλήματος (8.G")–(8.3"), (8.6") ​​χρησιμοποιώντας το μέθοδο simplex.

VI βήμα. Βασικές Μεταβλητές Χ v Χ 2, Χστο ΧΤ

Μη βασικές μεταβλητές Χ 4, Χ-, χ 6.

Παραλείποντας περαιτέρω λύση του προβλήματος χρησιμοποιώντας τη μέθοδο simplex (προτείνουμε στους μαθητές να το κάνουν μόνοι τους), στο τελικό, VII, βήμα παίρνουμε.

VII βήμα. Βασικές Μεταβλητές Χ v Χ t x3, Χσολ

Μη βασικές μεταβλητές Χ v Χ 6, ΧΤ

Εφόσον δεν υπάρχουν μη βασικές μεταβλητές με αρνητικούς συντελεστές στην έκφραση μιας γραμμικής συνάρτησης, τότε Χ 7 – βέλτιστη ακέραια λύση στο αρχικό πρόβλημα.

Πρέπει να σημειωθεί ότι στην προκύπτουσα έκφραση της γραμμικής συνάρτησης Z δεν υπάρχουν δευτερεύουσες μεταβλητές ΧΔ) και Χ 6. Αυτό σημαίνει ότι, μιλώντας γενικά, υπάρχει ένα άπειρο σύνολο βέλτιστων λύσεων (οποιεσδήποτε, όχι απαραίτητα ακέραιος), για τις οποίες Z" = Zmjn = 46. Αυτές οι λύσεις λαμβάνονται για την τιμή της μη κύριας μεταβλητής Χ 7 (περιλαμβάνεται στην έκφραση για το Z), ίσο με μηδέν (δηλ. όταν Χ 7 = 0), και στο όποιοςτιμές μη βασικών μεταβλητών x5 και Χ 6 (δεν περιλαμβάνεται στην έκφραση για το Z), το οποίο το σύστημα περιορισμών «επιτρέπει» να γίνει αποδεκτό: 0<лг5 Χ 5 ≤ 1 και 0< Χ(i ≤ 1. Αλλά λόγω της ακέραιας συνθήκης, οι μεταβλητές Χ-Και Χ(> μπορεί να πάρει μόνο τις τιμές 0 ή 1. Επομένως, το πρόβλημα θα έχει τέσσερις βέλτιστες ακέραιες λύσεις όταν Χ.και *6 σε οποιονδήποτε συνδυασμό πάρτε τις τιμές 0 ή 1 και Χ 7 = 0. Αντικαθιστώντας αυτές τις τιμές στο σύστημα περιορισμών στο βήμα VII, βρίσκουμε αυτές τις βέλτιστες λύσεις:

Η παρουσία εναλλακτικών βέλτιστων ακεραίων λύσεων καθιστά δυνατή την επιλογή μιας από αυτές, καθοδηγούμενη από πρόσθετα κριτήρια που δεν λαμβάνονται υπόψη στο μαθηματικό μοντέλο του προβλήματος. Για παράδειγμα, από τις συνθήκες αυτού του προβλήματος προκύπτει ότι το πριόνισμα των κορμών δεν παράγει απόβλητα μόνο χρησιμοποιώντας την 3η μέθοδο, επομένως, όταν επιλέγετε μία από τις τέσσερις βέλτιστες λύσεις, είναι φυσικό να προτιμάτε τη λύση Χ^ 3 στον οποίο ο μέγιστος αριθμός αρχείων καταγραφής ( Χ 2 = 41) πριονίζεται χωρίς απορρίμματα.

Άρα, Zmin=46 για βέλτιστες ακέραιες λύσεις (5; 41; 0), (6; 39; 1), (7; 36; 3), (6; 38; 2). Κατά την καταγραφή των βέλτιστων λύσεων, αφήσαμε μόνο τα τρία πρώτα στοιχεία, εκφράζοντας τον αριθμό των ημερολογίων που κόπηκαν σύμφωνα με την 1η, 2η και 3η μέθοδο, αντίστοιχα, και αποκλείσαμε τα τέσσερα τελευταία στοιχεία, τα οποία δεν έχουν σημασιολογική σημασία.

Το μειονέκτημα της μεθόδου Gomori είναι η απαίτηση για ακέραιες τιμές για όλες τις μεταβλητές - τόσο βασικές (που εκφράζουν, για παράδειγμα, στο πρόβλημα χρήσης πόρων μιας μονάδας παραγωγής) όσο και πρόσθετες (εκφράζοντας την ποσότητα των αχρησιμοποίητων πόρων, που μπορεί να να είναι κλασματική).

• Μπορείτε να δείτε ότι η λύση στο πρόβλημα είναι πιο σύντομη.

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

Αλγόριθμος Gomori

GP Χρησιμοποιώντας τη μέθοδο simplex βρίσκουμε το βέλτιστο πρόγραμμα. Εάν λάβετε ακέραιες τιμές για όλους Xj, τότε το πρόβλημα λύνεται. Διαφορετικά μεταξύ Xjυπάρχουν μη αριθμητικές τιμές.

|~2~1 Μεταξύ μη ακεραίων Xjεπιλέξτε ένα αυθαίρετο στοιχείο x gκαι προσθέστε έναν άλλο περιορισμό στο πρόβλημα

που ισοδυναμεί με την προσθήκη μιας ακόμη σειράς στον πίνακα simplex, μετά την οποία δεν αντιστοιχεί πλέον σε μια αποδεκτή βασική λύση στο νέο πρόβλημα γραμμικού προγραμματισμού που περιγράφει. Ο περιορισμός χρησιμοποιεί κλασματικά μέρη των στοιχείων της γραμμής στην οποία βρίσκεται. x g.Ο συμβολισμός που χρησιμοποιείται για το κλασματικό μέρος βασίζεται στο γεγονός ότι κάθε πραγματικός αριθμός στομπορεί να αναπαρασταθεί ως άθροισμα στο = [y]+ (?у), πού [y] -ολόκληρο μέρος και (y) = U ~ [y] ~κλάσμα.

[η] Βρίσκουμε μια παραδεκτή βασική λύση, θεωρώντας ότι η νέα γραμμή είναι επίλυση, δηλ. Εγώ = Π + 1.

• α) Αν όλοι οι συντελεστές uc> 0, τότε το πρόβλημα δεν έχει λύση (δηλαδή λύνεται το ακέραιο πρόβλημα).
• β) Διαφορετικά, βρείτε το ευρετήριο Προς τηντέτοια που

(κριτήριο εισαγωγής νέας βάσης). Σημειώστε ότι η επιλογή του στοιχείου επίλυσης στοΚαι*δεν αλλάζει το πρόσημο των κριτηρίων Aj.

[4] Εάν ο νέος πίνακας έχει τουλάχιστον ένα x 3και επαναλάβετε αυτές τις διαδικασίες όσες φορές χρειάζεται.

[~5~| Εάν η βέλτιστη λύση που προκύπτει είναι ακέραιος, τότε το πρόβλημα λύνεται. Διαφορετικά, πρέπει να επιστρέψετε στο σημείο.

Παράδειγμα 4.6.1. Λύστε ένα ακέραιο πρόβλημα χρησιμοποιώντας τη μέθοδο Gomori

Λύση. Αφού προσθέσουμε τις βοηθητικές μεταβλητές, έχουμε το ακόλουθο πρόβλημα γραμμικού προγραμματισμού σε τυπική μορφή:

με πίνακες

Τραπέζι 1
	Χ4

Προς την= 1 Τ

Χρησιμοποιώντας τη μέθοδο περιστροφής, συμπληρώστε τους παρακάτω πίνακες. Στοιχείο ανάλυσης - 6*.

πίνακας 2				Χ 2
		„ _ 1 ΚΑΙΖ ~_3_

κ" = 2 Τ

Στοιχείο ανάλυσης - 1/2*.

Χ σε^0). Επομένως, το πρόγραμμα (xi = 11/3, Χ 2 = 5) θα δώσει το μέγιστο της οικονομικής συνάρτησης z,ίσο με 1370/3 = 45b|, τ.σ. z= z max = 456§. "

Εφόσον αυτό το βέλτιστο πρόγραμμα δεν είναι ακέραιο, εφαρμόζουμε τον αλγόριθμο του Gomori για να βρούμε ένα ακέραιο βέλτιστο πρόγραμμα. Ως γραμμή με βάση την οποία σχηματίζουμε μια πρόσθετη γραμμή από τα κλασματικά μέρη όλων των στοιχείων, επιλέγουμε τη δεύτερη γραμμή (δείκτης 7’ = 1). Ας συμπληρώσουμε τον πίνακα 3", προσθέτοντας στον πίνακα 3 μια επιπλέον σειρά (4.14) με κλασματικά μέρη για την πρόσθετη μεταβλητή Ж5 και μια επιπλέον στήλη. Παίρνουμε

κ" = 4 Τ

Μετά την προσθήκη μιας νέας γραμμής, ο πίνακας simplex 3" δεν αντιστοιχεί πλέον σε μια αποδεκτή βασική λύση στο πρόβλημα που περιγράφει. Βρίσκουμε μια αποδεκτή βασική λύση, θεωρώντας ότι η νέα γραμμή επιλύεται, π.χ. /" = 5.

Βρίσκουμε τη στήλη ανάλυσης, δηλ. δείκτης Προς την"τέτοια που

(κριτήριο εισαγωγής νέας βάσης). Στοιχείο ανάλυσης - (-2/3*). Σημειώστε ότι μια τέτοια επιλογή ενός στοιχείου επίλυσης δεν αλλάζει το πρόσημο των κριτηρίων Aj.

Ας συμπληρώσουμε τον πίνακα Simplex 4.

Πίνακας 4				Χ2
	Χ2

Τιμές όλων των κριτηρίων ^ 0, ( Χ σε^0). Επομένως, το πρόγραμμα (xi = 3, x 2 = 6, x±= 1) δίνει το μέγιστο της οικονομικής συνάρτησης r ίσο με 450, t.s. z = ζμα^= 450. Αυτό το βέλτιστο πρόγραμμα είναι ένας ακέραιος αριθμός. ?

Παράδειγμα 4.6.2. Λύστε ένα ακέραιο πρόβλημα χρησιμοποιώντας τη μέθοδο του Gomori

Λύση. Υπάρχει ένα πρόβλημα γραμμικού προγραμματισμού με πίνακες

Ας συμπληρώσουμε τον πίνακα simplex με το αρχικό πρόγραμμα.

Τραπέζι 1

Προς την= 1 Τ

Χρησιμοποιώντας τη μέθοδο περιστροφής, συμπληρώστε τους παρακάτω πίνακες. Στοιχείο ανάλυσης - 1*.

πίνακας 2				Χ2

Επιτρεπτικό στοιχείο - 5*.

Πίνακας 3

Τιμές όλων των κριτηρίων ^ 0, ( Χ σε^0). Κατά συνέπεια, το πρόγραμμα (xi = 12/5, 24 = 1/5, 25 = 28/5) δίνει το ελάχιστο της οικονομικής συνάρτησης r ίσο με -11/5 = -2,2, δηλ. z =

~min = -2.2.

Εφόσον αυτό το βέλτιστο πρόγραμμα δεν είναι ακέραιο, εφαρμόζουμε τον αλγόριθμο του Gomori για να βρούμε ένα ακέραιο βέλτιστο πρόγραμμα. Ως συμβολοσειρά με βάση την οποία σχηματίζουμε μια πρόσθετη συμβολοσειρά από τα κλασματικά μέρη των στοιχείων ss, επιλέγουμε, για παράδειγμα, την τρίτη σειρά (δείκτης r = 5) με το μέγιστο κλασματικό μέρος. Ας συμπληρώσουμε τον πίνακα 3" προσθέτοντας μια πρόσθετη γραμμή (4.14) στον πίνακα 3 με κλασματικά μέρη της τρίτης γραμμής για την πρόσθετη μεταβλητή xq (αυτή η γραμμή σάς επιτρέπει να αποκόψετε από την περιοχή προγράμματος τμήματα που περιέχουν σημεία με μη αριθμητικές συντεταγμένες) και μια πρόσθετη στήλη. Παίρνουμε

Πίνακας 3"
		G - -ΚΑΙ

κ" = 3 Τ

Μετά την προσθήκη μιας νέας γραμμής, ο πίνακας simplex 3" δεν αντιστοιχεί πλέον σε μια αποδεκτή βασική λύση στο πρόβλημα που περιγράφει. Βρίσκουμε μια αποδεκτή βασική λύση, θεωρώντας ότι η νέα γραμμή επιλύεται, π.χ. εγώ" = 6.

Βρίσκουμε τη στήλη επίλυσης, δηλ. δείκτης Προς την"τέτοια που

(κριτήριο εισαγωγής νέας βάσης). Στοιχείο ανάλυσης - (-3/5*). Σημειώστε ότι μια τέτοια επιλογή ενός στοιχείου επίλυσης δεν αλλάζει το πρόσημο των κριτηρίων Aj.

Ας συμπληρώσουμε τον πίνακα Simplex 4.

Πίνακας 4

Τιμές όλων των κριτηρίων ^ 0, ( Χ σε^0). Επομένως το πρόγραμμα (x = 2, Χ2 = 0, xs = 1, Χ 4 = 0, f 5 = 5) θα δώσει το ελάχιστο της οικονομικής συνάρτησης z 9 ίσο με (-2), τ.σ. z =-min = - 2. Αυτό το βέλτιστο πρόγραμμα είναι ένας ακέραιος αριθμός. ?

Πρόβλημα 4.6.1. Λύστε ένα ακέραιο πρόβλημα χρησιμοποιώντας τη μέθοδο Gomori

Απάντηση. Πρόγραμμα

δίνει ένα ελάχιστο της οικονομικής συνάρτησης z ίσο με (-31), δηλ. z= 2 m i n = -31. Αυτό το βέλτιστο πρόγραμμα είναι ακέραιος.

Εισαγωγή

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

Η πρώτη μέθοδος για την επίλυση ενός ακέραιου προβλήματος γραμμικού προγραμματισμού με κλάδεμα προτάθηκε από τον Gomori και ονομάστηκε αλγόριθμος Gomori.

1. Δήλωση του προβλήματος

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

1.1 Κανονική μορφή

Θα εξετάσουμε το πρόβλημα προγραμματισμού κανονικού ακέραιου αριθμού με nμεταβλητές και Μσυνθήκες, συμπληρωμένες από την ακέραια συνθήκη:

Οπου c = (c 1 , c 2 , … , c n), x = (x 1 , x 2 , … , x n)- διάνυσμα διάστασης n, - το βαθμωτό γινόμενο τους (), που ονομάζεται επίσης αντικειμενική συνάρτηση, ΕΝΑ- πίνακας διαστάσεων n´ Μ, σι- διάνυσμα στήλης διάστασης Μ.

Η ακέραια συνθήκη περιπλέκει σημαντικά το πρόβλημα γραμμικού προγραμματισμού (1.1), (1.2). Μπορεί το πρόβλημα (1.1)-(1.3) να έχει αποδεκτά (ακέραια) σχέδια, η αντικειμενική συνάρτηση να περιορίζεται στο αποδεκτό σύνολο, αλλά να μην επιτυγχάνεται το μέγιστο. Για παράδειγμα στην εργασία:

Δεν υπάρχουν ακέραιες λύσεις, ενώ χωρίς αυτή τη συνθήκη, οποιοδήποτε διάνυσμα της μορφής μπορεί να χρησιμεύσει ως λύση

.

Σε σχέση με τα παραπάνω, κατά την αιτιολόγηση αριθμητικών αλγορίθμων για την επίλυση προβλημάτων τύπου (1.1)-(1.3), είναι απαραίτητο να επιβληθούν διάφορες πρόσθετες προϋποθέσεις Χσχέδια του προβλήματος (1.1), (1.2) (χωρίς την ακέραια συνθήκη) είναι οριοθετημένη, δηλαδή είναι πολύεδρο.

Από αυτή τη συνθήκη προκύπτει ότι το σύνολο Χ*όλα τα ακέραια σχέδια του προβλήματος (1.1)-(1.3) είναι πεπερασμένα. Θα υποθέσουμε ότι όλοι οι συντελεστές γ ι, j=1, 2 , …, n, οι συναρτήσεις στόχου είναι ακέραιοι.

Από την συνθήκη II προκύπτει ότι για οποιοδήποτε ακέραιο σχέδιο ΧÎ Χ* νόημα<ντο, Χ> γραμμική μορφή που πρέπει να μεγιστοποιηθεί - ένας ακέραιος αριθμός. Σε αυτή την περίπτωση, λέμε ότι είναι εγγυημένη η ακεραιότητα της αντικειμενικής συνάρτησης.

Αν και οι συνθήκες I και II για το πρόβλημα (1.1) - (1.3) είναι αρκετά αυστηρές, είναι δυνατό να εξασθενήσουν μόνο ελαφρά για να ληφθούν τα απαραίτητα αποτελέσματα.

1.2 Αναγωγή σε κανονική μορφή

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

Μπορούμε να μεταβούμε από μια τέτοια σημείωση στην (1.2) προσθέτοντας μια νέα μεταβλητή σε κάθε εξίσωση, τότε οι περιορισμοί θα πάρουν τη μορφή

Οι προστιθέμενες μεταβλητές θα έχουν μηδενικό βάρος στην αντικειμενική συνάρτηση.

Σημειώστε ότι για να προκύψει, ανάλογα με το είδος της ανισότητας, θα πρέπει όχι μόνο να προσθέσετε, αλλά και να αφαιρέσετε μια μεταβλητή ανάλογα με το πρόσημο της ανισότητας, λαμβάνοντας υπόψη την συνθήκη (1.3).

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

2. Γενικές ιδέες μεθόδων κοπής

Υπάρχει μια θεμελιώδης δυνατότητα μείωσης της λύσης του προβλήματος (1.1) - (1.3) στην εύρεση του βέλτιστου σχεδίου για κάποιο πρόβλημα γραμμικού προγραμματισμού (χωρίς την προϋπόθεση ότι οι μεταβλητές είναι ακέραιοι). Αφήνω Χ- ένα πολυεδρικό σύνολο που ορίζεται από τις συνθήκες (1.1), (1.2). Διά μέσου Χ*συμβολίζει το σύνολο όλων των ακέραιων διανυσμάτων Χ*, ξαπλωμένος μέσα Χ. Με άλλα λόγια Χ*δίνεται από τις προϋποθέσεις (1.1)-(1.3), δηλ.

Α-πριό Χ*Í Χ. Θα υποδηλώσουμε με X zκυρτή γάστρα του σετ Χ*. Επειτα X zÍ Χ.

Έτσι, έχουμε συνδέσει με το πολυεδρικό σύνολο X κάποιο κυρτό σύνολο X zÍ Χσύμφωνα με τον ακόλουθο κανόνα: X zείναι το ελάχιστο κυρτό σύνολο που περιέχει όλα τα ακέραια διανύσματα από Χ.

Σύμφωνα με την υπόθεση Ι, Χείναι ένα πολύεδρο, εξ ου και το σύνολο Χ*Σίγουρα. Στη συνέχεια το κυρτό σύνολο X zείναι επίσης ένα πολύεδρο, και επομένως έχουμε αυτό X zμπορεί να προσδιοριστεί από έναν πεπερασμένο αριθμό γραμμικών ανισώσεων.

Για να επισημάνετε τη βασική διαφορά μεταξύ του σετ X zαπό πολλούς Χ, ας δώσουμε τον ακόλουθο ορισμό.

Ορισμός 1. Ένα πολύεδρο του οποίου όλα τα ακραία σημεία είναι ακέραιοι (δηλαδή όλες οι συντεταγμένες τους είναι ακέραιοι) ονομάζεται ακέραιο πολύεδρο.

Προφανώς, το πολύεδρο X z- ακέραιος, αφού τα ακραία σημεία του είναι μόνο σημεία του συνόλου Χ*ακέραια σχέδια.

Αιτιολόγηση για τη μελέτη συμμόρφωσης Χ® X zείναι το εξής απλό γεγονός.

Θεώρημα 1. Οποιοδήποτε βέλτιστο σχέδιο αναφοράς για ένα πρόβλημα γραμμικού προγραμματισμού είναι μια λύση στο πρόβλημα (1.1)-(1.3).

Απόδειξη.Ας` Χ*- βέλτιστο σχέδιο αναφοράς του προβλήματος (2.1), Χ*- κάποιου είδους λύση στο αρχικό πρόβλημα (1.1)-(1.3). ` Χ*Î X zÍ Χ, Οτι

<ντο,`Χ*> £ <ντο, Χ*>.

Από την άλλη, αφού Χ*είναι λοιπόν ένα ακέραιο σχέδιο Χ*Î Χ*Í X z, και ως εκ τούτου

<ντο,`Χ*> ³ <ντο, Χ*>,

που

<ντο,`Χ*> = <ντο, Χ*>.

Η απόδειξη του θεωρήματος είναι πλήρης.

Τονίζουμε ότι το Θεώρημα 1 δηλώνει μόνο τη θεμελιώδη δυνατότητα αναγωγής της λύσης ενός ακέραιου προβλήματος γραμμικού προγραμματισμού στην αναζήτηση σχεδίων αναφοράς ενός προβλήματος γραμμικού προγραμματισμού της μορφής (2.1). Η κύρια δυσκολία στη χρήση αυτού του χαρακτηριστικού είναι ο σαφής ορισμός του πολυέδρου X zένα σύστημα γραμμικών ανισώσεων προκειμένου να εφαρμοστούν στη συνέχεια αριθμητικές μέθοδοι γραμμικού προγραμματισμού για την επίλυση του προβλήματος (2.1). Είναι πιθανό ότι αυτό το πρόβλημα είναι υπολογιστικά τόσο δύσκολο όσο το αρχικό πρόβλημα της εύρεσης του βέλτιστου σχεδίου ακέραιου αριθμού.

Παρόλα αυτά, η ιδέα του «στενεύματος» του συνόλου Χαποδείχθηκε χρήσιμο και οδήγησε στη δημιουργία αρκετών αλγορίθμων για την επίλυση προβλημάτων γραμμικού προγραμματισμού ακεραίων, που ονομάζονται «μέθοδοι κοπής».

Ας παρουσιάσουμε την ιδέα των μεθόδων κλαδέματος. Ας υποθέσουμε ότι καταφέραμε να κατασκευάσουμε την ακολουθία ( L r}, r = 0, 1 , 2 , ..., προβλήματα γραμμικού προγραμματισμού, καθένα από τα οποία καθορίζεται από το δικό του πολύεδρο Xrκαι μια αντικειμενική λειτουργία για όλους<ντο, Χ>:

Επιπλέον, αυτή η ακολουθία εργασιών έχει τις ακόλουθες ιδιότητες:

) Χ 0 =Χ, δηλ. όπως και Χ 0Πάρτε το σύνολο των σχεδίων για το πρόβλημα (1.1), (1.2).

) X r z = X z, r=1,2, …;

) εάν κατά την επίλυση ενός προβλήματος L rτο βέλτιστο διάνυσμα που προκύπτει x r *δεν ικανοποιεί την ακέραια συνθήκη, τότε δεν είναι σχέδιο εργασιών L r+1, δηλ. x r *Ï X r+1.

Σημειώστε ότι αν σε κάποιο βήμα rδιάνυσμα x r *- τη λύση του προβλήματος L r- αποδείχθηκε ότι είναι ακέραιος, τότε είναι μια λύση στο αρχικό πρόβλημα (1.1)-(1.3) λόγω της ιδιότητας 2) της ακολουθίας L r.

Είναι διαισθητικά σαφές ότι η διαδοχική κατασκευή των εργασιών L r, r=1,2,..., δίνει κατά μία έννοια μια προσέγγιση του συνόλου X zμε τη βοήθεια πολλών Xr.

Μέθοδοι για την κατασκευή μιας ακολουθίας ( L r), εξασφαλίζουν το πεπερασμένο της διαδικασίας επίλυσης του προβλήματος (1.1)-(1.3), προτάθηκαν για πρώτη φορά από τον Gomori.

3. Περιγραφή της μεθόδου Gomori

Ας εξετάσουμε τώρα τον αλγόριθμο Gomori για την επίλυση προβλημάτων γραμμικού προγραμματισμού ακέραιων αριθμών. Αυτή η μέθοδος ανήκει στις μεθόδους κοπής και υλοποιεί τις ιδέες που περιγράφονται στην προηγούμενη παράγραφο.

3.1 Η έννοια της σωστής κοπής και ο απλούστερος τρόπος κατασκευής της

Γραμμικός προγραμματισμός αλγόριθμος Ομήρου

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

Ορισμός 2. Έστω x* το βέλτιστο σχέδιο για το πρόβλημα (1.1), (1.2), το οποίο δεν είναι ακέραιος. Ανισότητα

όπου g = (ζ 1 , ζ 2 , …, ζ n), ονομάζεται σωστή περικοπή εάν ικανοποιεί τις απαιτήσεις:

α) για ένα διάνυσμα Χ*η ανισότητα δεν ισχύει, δηλ. Χ*> > ζ 0 (συνθήκη αποκοπής).

β) εάν Χείναι το ακέραιο σχέδιο του προβλήματος (1.1), (1.2) (δηλαδή το σχέδιο του προβλήματος (1.1)-(1.3)), τότε Χ- ικανοποιεί (3.1) (συνθήκη ορθότητας).

Είναι σαφές ότι η προσθήκη της ανισότητας (3.1) στις συνθήκες (1.1), (1.2) περιορίζει το αποδεκτό σύνολο Χ, διατηρώντας παράλληλα όλα τα ακέραια σημεία του. Έτσι, η συνεπής εφαρμογή αυτής της τεχνικής δίνει μια προσέγγιση πολλαπλών σταδίων του πολυέδρου X zχρησιμοποιώντας γραμμικούς περιορισμούς.

Υπάρχουν δύο προβλήματα με την έννοια της σωστής κοπής. Το πρώτο από αυτά είναι η διαμόρφωση ενός γενικού αλγόριθμου κλαδέματος για ένα πρόβλημα γραμμικού προγραμματισμού αυθαίρετου ακέραιου αριθμού. Το δεύτερο πρόβλημα είναι η κατασκευή μιας σωστής αποκοπής με τέτοιο τρόπο ώστε να διασφαλίζεται η λύση του προβλήματος (1.1)-(1.3) σε έναν πεπερασμένο αριθμό βημάτων, π.χ. ώστε από το πλήθος Χκάθε φορά αποκόπτονταν αρκετά μεγάλες περιοχές.

Σημειώστε ότι η δεύτερη απαίτηση είναι αρκετά λεπτή. Ως επιβεβαίωση, εξετάστε τη μέθοδο κατασκευής μιας σωστής αποκοπής που προτείνει ο Danzig.

Αφήνω Χ*- υποστήριξη βέλτιστου σχεδίου προβλήματος (1.1), (1.2), s και w - λίστες αριθμών βασικών και μη βασικών μεταβλητών, αντίστοιχα, που αντιστοιχούν σε κάποια βάση του σχεδίου Χ*. Επειτα x j *= 0 σε ιÎw. Λαμβάνοντας υπόψη αυτήν την ιδιότητα, δεν είναι δύσκολο να κατασκευαστεί μια σωστή αποκοπή για το σχέδιο x* εάν δεν είναι ακέραιος: η ανισότητα

Πράγματι, η συνθήκη αποκοπής ικανοποιείται επιπόλαια, αφού . Ικανοποιείται και η προϋπόθεση της ορθότητας, αφού αν x = (x 1,x 2 , …,x n) είναι το ακέραιο σχέδιο του προβλήματος (1.1), (1.2), στη συνέχεια η τιμή λαμβάνοντας υπόψη τις συνθήκες x j ³ 0, ιÎ w, μπορεί να είναι μικρότερη από την ενότητα μόνο στην περίπτωση που x j= 0 για όλους ιÎ w. Αλλά σε αυτή την περίπτωση το σχέδιο Χ- αναφορά και ως βάση μπορεί να ληφθεί η βάση του σχεδίου Χ*. Το σχέδιο αναφοράς καθορίζεται μοναδικά από τη βάση του, από την οποία προκύπτει ότι η ανισότητα συνεπάγεται x=x *. Το τελευταίο όμως είναι αδύνατο, αφού Χείναι ένα ακέραιο διάνυσμα και Χ*δεν είναι.

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

Ας περιγράψουμε τη μέθοδο για την κατασκευή μιας σωστής αποκοπής που προτείνεται από τον Gomori. Για αυθαίρετο αριθμό ένα, μέσω [ ένα] θα συμβολίσουμε ολόκληρο το τμήμα του, δηλ. [ ένα] είναι ο μεγαλύτερος ακέραιος αριθμός κμη υπερβαίνοντα αριθμό ένα.

κλασματικό μέρος ( ένα) αριθμοί ένακάλεσε τον αριθμό ( ένα} = ένα - [ένα]. Ας σημειώσουμε την προφανή ιδιότητα του κλασματικού μέρους ενός αυθαίρετου αριθμού: 0 £ ( ένα}<1, причем {ένα) = 0 αν και μόνο αν ένα - ένας ακέραιος αριθμός.

Αφήνω Χ*- λύση αναφοράς του προβλήματος (1.1), (1.2), που δεν είναι ακέραιος, - τη βάση του και σι- τον αντίστοιχο πίνακα simplex σε μορφή συντεταγμένων.

Ας εξετάσουμε το μειωμένο σύστημα εξισώσεων που αντιστοιχεί σε αυτή τη βάση (και τον πίνακα σι) σχέδιο

Χ*:

Επειδή η x j *= 0 σε ιΕ, τότε μόνο οι ποσότητες μπορούν να είναι μη ακέραιες x 0 * = <ντο, Χ*>, x i *, ΕγώΕίναι.

Αφήνω μικρό- ένας τέτοιος δείκτης (0 £ μικρό £ n) ότι ο αριθμός xs*- όχι ολόκληρο. Ας σκεφτούμε μικρόη σειρά σε έναν πίνακα simplex σι (μικρόη εξίσωση στο σύστημα (3.2), (3.3)) και συνθέστε την παράσταση

Θεώρημα 2. Αν ΧÎ Χ*είναι το ακέραιο σχέδιο του προβλήματος (1.1), (1.2), τότε

Απόδειξη.Χρησιμοποιώντας τη σχέση

έναsj = [έναsj] + {έναsj }, ι = 0, 1, 2, … , n, από (3.3) με Εγώ= μικρόπαίρνουμε

που

Η αριστερή πλευρά αυτής της ανισότητας περιέχει έναν ακέραιο, επομένως τον αριθμό

επίσης ολόκληρο. Από τι x j ³ 0, ιÎw, χρησιμοποιώντας την ιδιότητα του κλασματικού μέρους, λαμβάνουμε

εκείνοι. - z s(Χ) < 1, или z s(Χ) > -1. Λαμβάνοντας υπ 'όψιν ότι z s(Χ) - ακέραιος, τελικά θα δεχθούμε z s(Χ) ³ 0.

Συνέπεια.Αν xs*(= έναs0) - μη ακέραιος αριθμός και Σετ Χ*Τα σχέδια του ακέραιου προβλήματος (1.1)-(1.3) δεν είναι κενά, τότε μεταξύ των αριθμών ( έναsj}, ι=1, 2, …, n, υπάρχουν θετικά.

Στην πραγματικότητα, όλοι οι αριθμοί ( έναsj), είναι προφανώς μη αρνητικές. Ας υποθέσουμε ότι ( έναsj} = 0, ι = 1, 2, …, n.

Αν Χ*μη άδειο και Χ* Î Χ*, Οτι z s(Χ*)= - {έναs0), ότι z s(Χ*) είναι ακέραιος, αφού το 0< {έναs0} < 1.

Σχόλιο. Στην απόδειξη του Θεωρήματος 2, χρησιμοποιήσαμε την υπόθεση II ότι η αντικειμενική συνάρτηση είναι εγγυημένη ότι είναι ακέραιος. Ισχύει σε περίπτωση μικρό= 0 τιμή

είναι ακέραιος (με την προϋπόθεση ότι ΧÎ Χ*) μόνο όταν ο αριθμός x 0 = < ντο, Χ> - ολόκληρο.

Από αυτό προκύπτει

Θεώρημα 3.Αν ο αριθμός xs*- δεν είναι ακέραιος, τότε ανισότητα

είναι η σωστή αποκοπή.

Απόδειξη.Ας ελέγξουμε τη συνθήκη αποκοπής στον Ορισμό 2. Αφού xs* = έναs0, τότε από το γεγονός ότι xs*- δεν είναι ακέραιος, παίρνουμε την ανισότητα ( έναs0) > 0. Αφού x j *= 0 σε ιО w, λοιπόν

και επομένως το διάνυσμα Χ*δεν ικανοποιεί την ανισότητα (3.5). Η συνθήκη ορθότητας προκύπτει από τη δήλωση z s(Χ) ³ 0 στο Θεώρημα 2.

3.3 Ο πρώτος αλγόριθμος του Gomory

Ας περάσουμε στην παρουσίαση του πρώτου αλγορίθμου Gomori.

Ας υποδηλώσουμε το πρόβλημα (1.1), (1.2) με μεγάλο 0 . Ο Γκόμορι πρότεινε να βρει το λεξικογραφικό μέγιστο του προβλήματος στο πρώτο στάδιο του αλγορίθμου του μεγάλο 0 . Θα υποδηλώσουμε με

Χ(0) = (Χ 0 (0), Χ 1 (0), …, Χ n(0))

(n+1) διάνυσμα διαστάσεων τέτοιο ώστε ( Χ 1 (0), Χ 2 (0), …, Χ n (0)) - λύση στο λεξικογραφικό πρόβλημα μεγάλο 0 , α Χ 0 (0) = - τιμή γραμμικής μορφής. Σε περιπτώσεις που αυτό δεν προκαλεί παρεξήγηση, θα καλέσουμε Χ(0) - βέλτιστο σχέδιο για το λεξικογραφικό πρόβλημα μεγάλο 0 (αν και σύμφωνα με την γενικά αποδεκτή ορολογία, ένα σχέδιο είναι ένα διάνυσμα που αποτελείται από το τελευταίο nδιανυσματικές συντεταγμένες Χ(0)).

Σημειώστε επίσης ότι ΧΤο (0) θα είναι ένα σχέδιο αναφοράς, καθώς και ένα αυστηρά παραδεκτό ψευδο-σχέδιο του προβλήματος μεγάλο 0 .

Αν το x(0) είναι ακέραιο διάνυσμα, τότε είναι προφανώς λύση στο πρόβλημα (1.1) - (1.3).

Διαφορετικά, βρίσκουμε τον ελάχιστο δείκτη s, 0 £ s £ n, για τον οποίο η τιμή xsΤο (0) δεν είναι ακέραιος αριθμός. Αφήνω σι(0) - πίνακας simplex σε μορφή συντεταγμένων που αντιστοιχεί στο διάνυσμα Χ(0). Χρησιμοποιώντας συντελεστές μικρόΣτη σειρά αυτού του πίνακα (δηλαδή οι συντελεστές του μειωμένου συστήματος (3.2), (3.3)), χρησιμοποιώντας την τεχνική που περιγράφεται παραπάνω, κατασκευάζεται η σωστή αποκοπή.

Εισάγεται μια βοηθητική μεταβλητή x n+1 και η εργασία εξετάζεται μεγάλο 1:

Το επόμενο στάδιο είναι να βρεθεί το λεξικογραφικό μέγιστο του προβλήματος μεγάλο 1 . Ένα σημαντικό πλεονέκτημα του αλγορίθμου Gomori είναι το γεγονός ότι το αρχικό παραδεκτό αυστηρό ψευδο-πλάνο για την εφαρμογή της μεθόδου dual simplex στο πρόβλημα μεγάλοΤο 1 βρίσκεται χωρίς δυσκολία. Πράγματι, είναι εύκολο να δούμε ότι ως τέτοιο ψευδοπλάνο μπορούμε να πάρουμε το διάνυσμα

Στην πραγματικότητα, είναι προφανές ότι y(1) ικανοποιεί (μαζί με τη διανυσματική μορφή Χ(0)) περιορισμοί (3.6), (3.7) προβλήματα μεγάλο 1, και μόνο ένας από τους περιορισμούς (3.8) παραβιάζεται: x n+1 (0)= - (α μικρό 0 } < 0. Кроме того, yΗ (1) είναι η αναφορά για το σύστημα των εξισώσεων (3.6), (3.7), γιατί αν - βάση σχεδίου Χ(0) μετά το σύστημα

είναι γραμμικά ανεξάρτητη και χρησιμεύει ως βάση για y(1). Ας το δείξουμε yΤο (1) είναι αυστηρά αποδεκτό ψευδοπλάνο. Για το σκοπό αυτό, θα κατασκευάσουμε έναν πίνακα simplex που αντιστοιχεί στην καθορισμένη διανυσματική βάση y(1). Για να το κάνετε αυτό, πρέπει απλώς να προσθέσετε παρακάτω στον πίνακα σι(0) γραμμή

Όπου w = ( ι 1 , ι 2 , …, jn -Μ) - λίστα αριθμών μη βασικών μεταβλητών που αντιστοιχούν στον πίνακα σι(0) σχέδιο αναφοράς Χ(0). Επειδή η ΧΤο (0) είναι ένα αυστηρά αποδεκτό ψευδοπλάνο, τότε κάθε στήλη β ι, ιΕ, τραπέζια σι(0) λεξικογραφικά θετικό: β ι > 0, ιÎw. Από αυτό προκύπτει ότι στον πίνακα simplex σε μορφή συντεταγμένων που αντιστοιχεί στο διάνυσμα υποστήριξης y(1), κάθε στήλη (εκτός από την πρώτη, που συμπίπτει με yΤο (1)) είναι λεξικογραφικά θετικό:

Έτσι, έχοντας στη διάθεσή μας μια λύση Χ(0) λεξικογραφική εργασία μεγάλο 0 και τον αντίστοιχο πίνακα simplex σε μορφή συντεταγμένων σι(0), χωρίς πρόσθετους υπολογισμούς βρίσκουμε το αρχικό αυστηρά αποδεκτό ψευδοπλάνο y(1) για την εργασία μεγάλο 1 και να κατασκευάσετε τον αντίστοιχο πίνακα simplex σε μορφή συντεταγμένων.

Μπορεί να συμβεί ότι η λεξικογραφική εργασία μεγάλο 1 δεν εχει λυση. Σε αυτήν την περίπτωση, η λύση του ακέραιου προβλήματος (1.1) - (1.3) θα πρέπει να σταματήσει από τότε

Θεώρημα 4.Αν στο πρόβλημα μεγάλο 1 δεν υπάρχει λεξικογραφικό μέγιστο, τότε το σύνολο Χ* ακέραια σημεία του προβλήματος (1.1) - (1.3) είναι κενά.

Απόδειξη.Αφού πολλοί Χδιανύσματα που ικανοποιούν τις συνθήκες Τσεκούρι = σι, Χ³ 0, σύμφωνα με την υπόθεση I οριοθετείται, τότε το σύνολο των σχεδίων για το πρόβλημα είναι επίσης οριοθετημένο μεγάλο 1 . Επομένως, ο μόνος λόγος για τον οποίο αυτό το πρόβλημα μπορεί να μην έχει λεξικογραφικό ελάχιστο είναι ότι το σύνολο των σχεδίων του είναι κενό. Ας δείξουμε ότι σε αυτή την περίπτωση το σύνολο Χ* επίσης άδειο.

Ας υποθέσουμε το αντίθετο, δηλ. Τι Χ* ¹ Æ, και ας Χ* = (Χ 1 * , Χ 2 * , …, x n*) О X*. Με το Θεώρημα 2 βρίσκουμε ότι η ποσότητα

μη αρνητικό. Αλλά αυτό σημαίνει ότι διάνυσμα = ( Χ 1 * , Χ 2 * , …, x n * , x n+1 *) είναι το σχέδιο εργασιών μεγάλο 1, σε αντίθεση με τα παραπάνω. Το θεώρημα έχει αποδειχθεί.

Αφήνω Χ(1) = (Χ 0 (1), Χ 1 (1), …, x n(1), x n+1 (1)) - λύση στο λεξικογραφικό πρόβλημα μεγάλο 1 . Αναχώρηση από την εργασία μεγάλο 1 και διάνυσμα Χ(1), τα προβλήματα κατασκευάζονται με παρόμοιο τρόπο L r, r= 2, 3, … και λύσεις Χ(r) Î Â n +1+rαντίστοιχες λεξικογραφικές εργασίες.

Σημειώστε ότι ο αλγόριθμος του Gomori καθορίζει μοναδικά την ακολουθία Χ(r), r= 0, 1, 2, …, που προκύπτει από τη μοναδικότητα της επιλογής μικρό. Ας δώσουμε επίσης προσοχή στο γεγονός ότι ο δείκτης μικρόπάντα δεν υπερβαίνει το n: 0 s n. Αν μάλιστα τα πάντα x j(r) στο ι= 0, 1, 2, …, n είναι ακέραιοι, τότε από το Θεώρημα 2 προκύπτει ότι x n +1 (r), x n +2 (r), … - επίσης ακέραιοι αριθμοί.

Αν σε κάποιο βήμα rδιάνυσμα

Χ(r) = (Χ 0 (r), Χ 1 (r), …, x n(r), …, x n +r (r))

αποδεικνύεται ότι είναι ακέραιος αριθμός, τότε το διάνυσμα ( Χ 0 (r), Χ 1 (r), …, x n(r)) είναι μια λύση στο πρόβλημα (1.1) - (1.3). Η απόδειξη αυτής της δήλωσης είναι προφανής.

Μετάβαση από διάνυσμα Χ(r) στο διάνυσμα Χ(r+1) χρησιμοποιώντας τον περιγραφόμενο αλγόριθμο Gomori ονομάζεται μεγάλη επανάληψη, σε αντίθεση με τις ενδιάμεσες επαναλήψεις της μεθόδου dual simplex, που ονομάζονται μικρές.

Το κύριο ερώτημα που σχετίζεται με τον πρώτο αλγόριθμο του Gomori είναι: είναι πάντα δυνατό να ληφθεί ένα ακέραιο διάνυσμα σε έναν πεπερασμένο αριθμό μεγάλων επαναλήψεων; Χ(r).

Ας αποδείξουμε το πεπερασμένο του πρώτου αλγορίθμου Gomory. Θα χρησιμοποιήσουμε τον ακόλουθο συμβολισμό:

Χ(0) = (Χ 0 (0), Χ 1 (0), …, x n(0));

Οπου ( Χ 1 (0), …, x n(0)) είναι η λύση στο λεξικογραφικό πρόβλημα L0, και Χ(0) = - η αντίστοιχη τιμή της γραμμικής μορφής (αντικειμενική συνάρτηση).

y(1) = (Χ 0 (0), Χ 1 (0), …, x n(0), x n +1),

το διάνυσμα y(1) χρησιμεύει ως το αρχικό αυστηρά αποδεκτό ψευδοπλάνο κατά την επίλυση του προβλήματος L1 χρησιμοποιώντας τη μέθοδο dual simplex σε μορφή συντεταγμένων: ` y(1) = (`y 0 (1), `y 1 (1), …, `y n(1), `y nΤο +1 (1)) είναι το διάνυσμα που προκύπτει από y(1) ως αποτέλεσμα της πρώτης (μικρής) επανάληψης της μεθόδου dual simplex σε μορφή συντεταγμένων.

Ο συμβολισμός εισάγεται με παρόμοιο τρόπο

Χ(r), y(r + 1), `y(r + 1), r = 1, 2, …

Από τις ιδιότητες της μεθόδου dual simplex σε μορφή συντεταγμένων προκύπτει

y(r) >`y(r) ³ Χ(r).

Λήμμα 1.Αφήνω μικρό- ο ελάχιστος δείκτης για τον οποίο ο αριθμός xs(0) δεν είναι ακέραιος. Επειτα

Απόδειξη.Αφού από το (3.9) ακολουθεί y(1) >`y(1), τότε είναι δυνατές δύο περιπτώσεις:

Στην περίπτωση 1, η δήλωση του λήμματος ικανοποιείται επιπόλαια από τον ορισμό της λεξικογραφικής σειράς.

Εξετάστε την περίπτωση 2. Σύμφωνα με τους κανόνες της μεθόδου dual simplex, στην πρώτη (μικρή) επανάληψη επίλυσης του προβλήματος μεγάλο 1 μεταβλητή υπόκειται σε εξαγωγή μεταξύ των βασικών x n+1 γιατί στο διάνυσμα y(1) x j(0) ³ 0, ιО w, x n +1 < 0. Пусть κО w είναι ένας δείκτης τέτοιος ώστε

Για οποιονδηποτε ιО w, αν -(α sj} < 0. По правилам симплексного метода в число базисных вводится переменная x k.

Η περίπτωση 2 είναι δυνατή μόνο υπό την προϋπόθεση β ik = 0, Εγώ = 0, 1, 2, …, μικρό- 1. Επειδή Χ(0) - αυστηρά αποδεκτό ψευδο-πλάνο της εργασίας μεγάλο 0 , τότε όλες οι στήλες του β ι, ιО w, πίνακας simplex σι(0) λεξικογραφικά θετικό. ειδικότερα β κ> 0 . Επομένως, η συντεταγμένη β σκαυτής της στήλης πρέπει να είναι μη αρνητικό. Σημειώστε ότι β σκ= α σκ(δηλαδή 0 £ μικρό £ nΚαι μικρόО w), υπό την προϋπόθεση (3.10) ο αριθμός α σκ- όχι μηδέν. Να γιατί

ένα σκ> 0 και α σκ³ (α σκ}

Σύμφωνα με τον τύπο μετασχηματισμού του πίνακα simplex, έχουμε

Υπενθυμίζοντας ότι xs(0) = as0, παίρνουμε:

.

Λαμβάνοντας υπόψη το (3.11), λαμβάνουμε την ακόλουθη εκτίμηση:

Το λήμμα είναι αποδεδειγμένο.

Σχόλιο.Εάν το αρχικό πρόβλημα (1.1) - (1.3) είναι παραδεκτό, τότε, σύμφωνα με το συμπέρασμα του Θεωρήματος 2, υπάρχει η συνθήκη που ικανοποιεί τον δείκτη k (3.10).

Συνέπεια.Δίκαιη αναλογία

Ισχύει στις r= 1, αυτή η ανισότητα προκύπτει από το λήμμα και τη δεύτερη ανισότητα (3.9). Για να αποκτήσετε αυτή τη δήλωση για αυθαίρετο r, πρέπει να εκμεταλλευτείτε το γεγονός ότι y j(r) = x j(r) στα 0 £ ι £ nκαι την ανισότητα y(r) ³ Χ(r) στο (3.9).

Θεώρημα 5. Εάν ικανοποιηθούν οι παραδοχές I και II, τότε ο πρώτος αλγόριθμος του Gomori απαιτεί μόνο έναν πεπερασμένο αριθμό μεγάλων επαναλήψεων.

Για να επαληθεύσουμε την αλήθεια του θεωρήματος, είναι απαραίτητο να δείξουμε ότι για κάποιους rδιάνυσμα Χ(r) = (Χ 0 (r), Χ 1 (r), …, x n +r (r)) - ακέραιος αριθμός. Για να γίνει αυτό, με τη σειρά του, αρκεί να αποδείξουμε την ακέραια φύση του διανύσματος ( Χ 0 (r), Χ 1 (r), …, x n(r)), αφού από το Θεώρημα 2 προκύπτει ότι όλοι οι αριθμοί x n +1 (r), x n +2 (r), …, x n +r (r) είναι επίσης ολόκληρες. Θυμηθείτε επίσης ότι ο ελάχιστος δείκτης s για τον οποίο ο αριθμός xs(r) είναι μη ακέραιος δεν υπερβαίνει πάντα το n: 0 £ s £ n. Πριν προχωρήσουμε στην κύρια απόδειξη, αποδεικνύουμε το ακόλουθο λήμμα:

Λήμμα 2.Για οποιονδηποτε ι, 0 £ ι £ n, υπάρχει τέτοιος αριθμός R j, ότι στο r ³ R jόλους τους αριθμούς x j(r) - ακέραιοι και ίσοι με τον ίδιο ακέραιο x j(R j).

Απόδειξη.Αφήνω μικρό, 0 £ μικρό £ n, - ο ελάχιστος δείκτης για τον οποίο δεν ισχύει η δήλωση του Λήμματος. Ας υποδηλώσουμε

Στην περίπτωση που μικρό= 0, ας βάλουμε R = 0.

Αφήνω r, μεγάλο- τέτοιοι δείκτες που R £ r£ l και αριθμοί xs(r), xs(μεγάλο) - όχι ολόκληρο. Ας δείξουμε ότι τότε [ xs(r)] > [xs(μεγάλο)]. Ισχύει εξ ορισμού μικρόέχουμε

Σε αυτήν την περίπτωση μικρό- ο ελάχιστος δείκτης για τον οποίο ο αριθμός xs(r) - ακέραιος αριθμός. Κατά συνέπεια στο Λήμμα 1 έχουμε [ xs(r)] ³ xs(μεγάλο).

Λαμβάνοντας υπ 'όψιν ότι xs(μεγάλο) δεν είναι ακέραιος, έχουμε xs(μεγάλο) > [xs(μεγάλο)], από το οποίο λαμβάνουμε την επιθυμητή δήλωση. Αφού πολλοί ΧΤα σχέδια του προβλήματος (1.1) - (1.3) είναι περιορισμένα, τότε οποιαδήποτε τιμή είναι περιορισμένη xs(r), 0 £ μικρό £ n, r= 1, 2, …. Επομένως, μια άπειρη αλυσίδα ανισοτήτων της μορφής [ xs(r)] > [xs(μεγάλο)] > ... δεν μπορεί να υπάρχει, και, επομένως, στην ακολουθία xs(r), r= 0, 1, …, δεν μπορεί να υπάρχει άπειρος αριθμός μη ακέραιων αριθμών. Ομοίως αποδεικνύεται ότι αυτή η ακολουθία δεν μπορεί να περιέχει άπειρους διαφορετικούς ακέραιους αριθμούς.

Το λήμμα είναι αποδεδειγμένο.

Ας επιστρέψουμε στην απόδειξη του θεωρήματος. Αφήνω

που είναι οι αριθμοί R jεμφανίζονται στη διατύπωση του Λήμματος 2. Στη συνέχεια, σύμφωνα με αυτό το λήμμα, όλοι οι αριθμοί x j(R), 0 £ ι £ n, - ολόκληρος. Από το Θεώρημα 2 προκύπτει ότι το διάνυσμα Χ(R) - ακέραιος αριθμός. Επομένως, ο αλγόριθμος του Gomory δεν απαιτεί περισσότερα από Rεπαναλήψεις.

Το θεώρημα έχει αποδειχθεί.

3.5 Σημειώσεις για την πρακτική εφαρμογή του πρώτου αλγορίθμου Gomori

Στην πρακτική εφαρμογή του πρώτου αλγορίθμου Gomori, σημαντικό πρόβλημα είναι η αύξηση του αριθμού των περιορισμών, που οδηγεί σε αύξηση του μεγέθους των πινάκων simplex. Ο Gomori πρότεινε έναν τρόπο για να εξαλειφθεί αυτό το μειονέκτημα του αλγορίθμου, ο οποίος είναι ο εξής.

) Κατά την επίλυση του προβλήματος L rχρησιμοποιώντας τη μέθοδο dual simplex, σε κάθε μικρή επανάληψη, θα πρέπει να χρησιμοποιείτε έναν εκλεπτυσμένο κανόνα συμπερασμάτων από τον αριθμό των διανυσμάτων βάσης για την επίλυση προβλημάτων γραμμικού προγραμματισμού χρησιμοποιώντας τη μέθοδο simplex: εάν η πρώτη στήλη του πίνακα simplex έχει πολλά αρνητικά στοιχεία β Εγώ 0 (= x i), Εγώ =1, 2, …, n, …, n + r, τότε η μεταβλητή με τον ελάχιστο αριθμό πρέπει να αφαιρεθεί από τις βασικές.

) Εάν κατά την επόμενη μικρή επανάληψη κατά την υλοποίηση της εργασίας L rόλες οι κύριες μεταβλητές Χ 1 , Χ 2 , …, x nαποδείχθηκε ότι δεν ήταν αρνητικό, στη συνέχεια, περαιτέρω εφαρμογή της μεθόδου dual simplex στο πρόβλημα L rθα πρέπει να σταματήσει, παρά το γεγονός ότι μπορεί να μην έχει επιτευχθεί ακόμη το λεξικογραφικό μέγιστο. Αν όλες οι μεταβλητές x j, ι = 1, 2, …, n, αποδείχθηκε ότι ήταν ακέραιος, στη συνέχεια από το Θεώρημα 2 όλες οι βοηθητικές μεταβλητές x n +κ , κ = 1, 2, …, r, είναι ακέραιοι και μη αρνητικοί. Αυτό σημαίνει, όπως είναι ήδη γνωστό, ότι το διάνυσμα ( Χ 0 , Χ 1 , Χ 2 , … , x n) είναι μια λύση στο αρχικό ακέραιο πρόβλημα. Διαφορετικά, προχωράμε σε μια νέα μεγάλη επανάληψη.

) Απλή γραμμή πίνακα που αντιστοιχεί στη βοηθητική μεταβλητή x n +r, αφαιρείται μόλις η μεταβλητή x n +rδηλώνεται ως μη βασικό. Ας θυμηθούμε ότι αυτό συμβαίνει με την πρώτη μικρή επανάληψη επίλυσης του προβλήματος L r.

) Εάν στην πορεία επίλυσης του προβλήματος L rμεταβλητός x n +rκαι πάλι εμπίπτει στον αριθμό των βασικών, τότε η αντίστοιχη σειρά δεν αποκαθίσταται.

Είναι σαφές ότι όταν ακολουθούνται οι κανόνες 3), 4), οι διαστάσεις του πίνακα simplex στον πρώτο αλγόριθμο Gomori δεν αυξάνονται - κάθε πίνακας περιέχει n+ 2 γραμμές που αντιστοιχούν στις κύριες μεταβλητές Χ 0 , Χ 1 , … , x nκαι η τρέχουσα βοηθητική μεταβλητή x n +rκατά την εισαγωγή του) και n - Μ+1 στήλες (από τον αριθμό n - Μοι μη βασικές μεταβλητές δεν αλλάζουν).

) Στην πρώτη μικρή επανάληψη επίλυσης του προβλήματος L rΗ +1 επιλέγεται ως η μεταβλητή που προκύπτει από τη βάση x n +r+1, παρά το γεγονός ότι οι τιμές άλλων βοηθητικών μεταβλητών αυτή τη στιγμή μπορεί επίσης να είναι αρνητικές.

Σημειώστε ότι ο κανόνας 5) είναι στην πραγματικότητα περιττός, καθώς όταν εκπληρώνονται οι κανόνες 3) και 4), δεν γνωρίζουμε τίποτα για την τιμή των υπόλοιπων μεταβλητών x n +1 , …, x n +rτη στιγμή της μετάβασης στην εργασία L r+1. Αυτός ο κανόνας επισημαίνεται μόνο για να επισημανθεί η διαφορά μεταξύ των υπό εξέταση αλγορίθμων.

Σημειώστε ότι όταν χρησιμοποιείτε τον κανόνα 2) την προκύπτουσα ακολουθία Χ ’ (r) μπορεί να μην είναι το λεξικογραφικό μέγιστο του προβλήματος L r, καθώς οι τιμές ορισμένων από τις βοηθητικές μεταβλητές μπορεί να είναι αρνητικές.

Ωστόσο, για συνέπεια Χ ’ (r), r= 0, 1, 2, …, που λαμβάνεται με χρήση των κανόνων 1) και 2), διατηρείται μια σημαντική ιδιότητα: αυτή η ακολουθία είναι μοναδική.

Μένει μόνο να αποδείξουμε ότι κατά τη χρήση των κανόνων 1) - 4) ο αλγόριθμος Gomori παραμένει πεπερασμένος, αφού το πεπερασμένο του θα σημαίνει ότι οδηγεί στον στόχο - την εύρεση μιας ακέραιας λύσης στο πρόβλημα (1.1) - (1.3). Πράγματι, το πεπερασμένο του αριθμού Rμεγάλες επαναλήψεις σημαίνει ότι το διάνυσμα Χ ’ (R) ακέραιος αριθμός.

Ας σημειώσουμε, πρώτον, ότι όταν χρησιμοποιείται ο κανόνας 2) ο αριθμός των μικρών επαναλήψεων επίλυσης του προβλήματος L rφυσικά - όχι περισσότερο από αυτό που απαιτείται για να βρεθεί το λεξικογραφικό μέγιστο.

Θεώρημα 6. Η ακολουθία x’(r) που προκύπτει κατά τη διαδικασία εφαρμογής του αλγορίθμου Gomori, του εξευγενισμένου κανόνα 1) - 4), είναι πεπερασμένη.

Απόδειξη. Σημειώστε ότι στην απόδειξη του Θεωρήματος 5 σχετικά με το πεπερασμένο της ακολουθίας x(r), χρησιμοποιήθηκαν μόνο δύο περιστάσεις που ρυθμίζουν την εμφάνιση αυτής της ακολουθίας: η μέθοδος κατασκευής της σωστής περικοπής και το γεγονός ότι σε οποιονδήποτε τρέχοντα πίνακα απλού όλες οι στήλες σι ι, ιΕ, είναι λεξικογραφικά θετικά. Έτσι, η διαγραφή της γραμμής που αντιστοιχεί στη βοηθητική μεταβλητή μπορεί να επηρεάσει μόνο την τελευταία περίσταση. Αυτό, ωστόσο, δεν μπορεί να ισχύει, όπως φαίνεται στο ακόλουθο λήμμα.

Λήμμα 3.Σε οποιονδήποτε πίνακα simplex που προκύπτει κατά τη διάρκεια του αλγόριθμου Gomori, που έχει βελτιωθεί από τους κανόνες 1) - 4), για οποιαδήποτε στήλη

υπάρχει ανισότητα

Απόδειξη.Ας υποθέσουμε ότι η δήλωση του λήμματος δεν ισχύει για κάποιους κО w. Αφού β κ, τότε αυτή η υπόθεση σημαίνει ότι

Με τον ορισμό ενός πίνακα simplex σε μορφή συντεταγμένων, έχουμε

Για οποιονδηποτε Χ Î Rn +1+r, εάν η δήλωση του λήμματος παραβιαστεί κατά την επίλυση του προβλήματος L r. Ο τύπος (3.13) λαμβάνοντας υπόψη το (3.12) σημαίνει ότι μια αλλαγή στην τιμή της μεταβλητής x kδεν επηρεάζει την τιμή x i, Εγώ = 0, 1, 2, …, n. Με άλλα λόγια, για το ίδιο σύνολο τιμών x i, 0£ Εγώ£ n, μεταβλητή x kμπορεί να πάρει μια αυθαίρετη τιμή. Συνάγεται, πρώτον, ότι κ ³ n+ 1, και δεύτερον, ότι η αποδεκτή υπόθεση (3.13) είναι εσφαλμένη, αφού η τιμή οποιασδήποτε βοηθητικής μεταβλητής x k, κ ³ nΤο + 1, όπως προκύπτει από το (3.7), καθορίζεται μοναδικά από τις τιμές των κύριων μεταβλητών.

Επειδή η διαγραφή γραμμών που αντιστοιχούν σε βοηθητικές μεταβλητές δεν επηρεάζει την ιδιότητα των στηλών b ι, ιÎ w, να είστε λεξικογραφικά θετικοί, τότε αυτές οι γραμμές δεν χρειάζονται καθόλου. Πράγματι, λαμβάνοντας υπόψη τους κανόνες 1) - 2) μεταβλητή x n +r, έχοντας γίνει ένα από τα βασικά, παραμένει βασικό μέχρι το τέλος των υπολογισμών και η γραμμή του δεν απαιτείται για τον προσδιορισμό της μεταβλητής που εισάγεται στη βάση σύμφωνα με τους κανόνες της μεθόδου simplex.

Έτσι, τα στοιχεία σειράς που αντιστοιχούν στη μεταβλητή x n +r, μην συμμετέχετε στους τύπους της μεθόδου dual simplex για τον υπολογισμό των τιμών όλων των άλλων μεταβλητών.

Δεδομένου ότι, όπως σημειώνεται, ο δείκτης μικρόρύθμιση του σχηματισμού της σωστής αποκοπής δεν υπερβαίνει n, 0 £ μικρό £ n, τότε δεν απαιτούνται βοηθητικές μεταβλητές για αυτούς τους σκοπούς.

4. Υλοποίηση υπολογιστή

Σε αυτό το μάθημα, το πρόγραμμα έχει σχεδιαστεί για να βρει μια λύση σε ένα ακέραιο πρόβλημα γραμμικού προγραμματισμού χρησιμοποιώντας τη μέθοδο Gomori.

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

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

…

…

…

…

Οπου n- αριθμός μεταβλητών, Μ- αριθμός περιορισμών, ντο 1 , ντο 2 , … , c n- συντελεστές της μεγιστοποιημένης γραμμικής μορφής, ένα ij- στοιχεία μήτρας Α, β ι- διανυσματικά στοιχεία σι. A, b - χαρακτηρίζουν περιορισμούς [βλ. (1.2)].

Παράδειγμα αρχείου εισαγωγής:

2 5 0 0 0 0 0 0 0

3 1 0 0 0 0 0 0 12

2 5 0 1 0 0 0 0 0 30

3 2 0 0 1 0 0 0 0 22

2 -1 0 0 0 1 0 0 0 12

1 -3 0 0 0 0 1 0 0 0

2 5 0 0 0 0 0 -1 0 10

5 1 0 0 0 0 0 0 -1 5

Βιβλιογραφία:

1. Abramov L.A., Kapustin V.F. Μαθηματικός προγραμματισμός. - L.: Leningrad State University Publishing House, 1981. -328 p.

Μπελούσοβα Γ.Σ. Γραμμικός προγραμματισμός. Φροντιστήριο. -Krasnoyarsk: Science, 1975. -107 p.

Kuznetsov Yu.N. και άλλα Μαθηματικός προγραμματισμός: Σχολικό βιβλίο. - 2η έκδ., αναθεωρημένη. και επιπλέον -Μ.: Ανώτατο Σχολείο, 1980. -300 σελ.

Ashmanov S.A., Γραμμικός προγραμματισμός. Μ.: Επιστήμη. 1969. -240 s

Gabasov R.I. Kirillova F.M., Μέθοδοι γραμμικού προγραμματισμού. Μινσκ: Επιστήμη. 1977. -174 s

Στα προβλήματα προγραμματισμού ακεραίων, σε αντίθεση με τα προβλήματα γραμμικού προγραμματισμού, εισάγεται ένας πρόσθετος περιορισμός στις μεταβλητές: μπορούν να λάβουν μόνο ακέραιες τιμές.

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

Στη μαθηματική σημειογραφία, ένα γενικό πρόβλημα προγραμματισμού ακεραίων μοιάζει με αυτό:

αυξάνω στον ανώτατο βαθμό

υπο προυποθεσεις

x j≥ 0, x j - ολόκληρος.

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

Σε μια άλλη ομάδα προβλημάτων γραμμικού προγραμματισμού, οι ποσότητες που πρέπει να προσδιοριστούν είναι οι παραγωγικές δυνατότητες που ικανοποιούν αποτελεσματικότερα μια δεδομένη ανάγκη. Δεδομένου ότι οι «φορείς» της παραγωγικής ικανότητας είναι μεμονωμένες επιχειρήσεις, αδιαίρετα κομμάτια εξοπλισμού κ.λπ., αυτά τα προβλήματα περιορίζονται επίσης σε προβλήματα γραμμικού προγραμματισμού ακέραιου αριθμού.

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

Σε όλα τα προβλήματα που αναφέρθηκαν, η λύση μπορεί να βρεθεί χρησιμοποιώντας συμβατικές μεθόδους γραμμικού προγραμματισμού, ακολουθούμενες από προσαρμογές και απόκτηση ενός ακέραιου σχεδίου που είναι λίγο πολύ κοντά στο βέλτιστο. Αλλά υπάρχουν προβλήματα για τα οποία μια μη ακέραια λύση δεν έχει νόημα. Αυτά περιλαμβάνουν προβλήματα επιλογής στα οποία οι αριθμητικές τιμές των μεταβλητών χρησιμεύουν μόνο για τον προσδιορισμό μιας εναλλακτικής ("ή-ή", "ναι-όχι").

Τα μοντέλα επιλογής ακέραιων αριθμών περιλαμβάνουν ορισμένα λειτουργικά προβλήματα προγραμματισμού, για παράδειγμα, προβλήματα σχετικά με τη βέλτιστη σειρά εισαγωγής διαφόρων προϊόντων (εξαρτημάτων) στην παραγωγή. Ας υποθέσουμε ότι πρέπει να καθορίσετε τη σειρά εκκίνησης n εξαρτήματα, καθένα από τα οποία επεξεργάζεται διαδοχικά σε πολλά μηχανήματα. Μεταβλητές x ij ίσο με ένα αν το μέρος ι πρέπει να τρέξει μετά το εξάρτημα Εγώ , και μηδέν - σε όλες τις άλλες περιπτώσεις. Για κάθε διορθωμένο ι , όπως για όλους Εγώ , μόνο ένα από n Οι μεταβλητές μπορεί να είναι ίσες με μία, επομένως οι περιορισμοί του προβλήματος περιλαμβάνουν τα ακόλουθα:

Ο συνολικός χρόνος επεξεργασίας όλων των εξαρτημάτων σε μηχανήματα αυτής της ομάδας ελαχιστοποιείται. Μια μη ακέραια λύση σε ένα τέτοιο πρόβλημα δεν έχει νόημα.

Υπάρχουν διάφορες μέθοδοι για την επίλυση προβλημάτων προγραμματισμού ακεραίων. Γνωστότεροι Μέθοδος Gomori, με βάση τη χρήση της μεθόδου simplex.

Ας δούμε τις μαθηματικές έννοιες: μαθηματική αναλογίααριθμούς, ολόκληροςΚαι κλασματικό μέρος ενός αριθμού. Αριθμός ΕΝΑ σύμφωνο με τον αριθμό σι αν και μόνο αν η διαφορά α – β είναι ακέραιος αριθμός. Η ευθυγράμμιση υποδεικνύεται με τρεις οριζόντιες γραμμές ( ≡ ) Ετσι, ΕΝΑ ≡ σι , Αν α – β είναι ακέραιος αριθμός.

Για παράδειγμα: 5 / 3 ≡ 2 / 3 , επειδή 5 / 3 - 2 / 3 = 1;

- 1 / 3 ≡ 2 / 3 , επειδή - 1 / 3 - 2 / 3 = 1.

Όλοι οι ακέραιοι είναι ίσοι μεταξύ τους και ίσοι με το μηδέν. Τα μη ακέραια στοιχεία μπορούν να αναπαρασταθούν ως το άθροισμα των ακέραιων και των κλασματικών μερών του αριθμού ΕΝΑ = [ένα ] + {ένα ). Οι αγκύλες σημαίνουν τη λήψη του ακέραιου μέρους του αριθμού που περικλείεται σε αυτές, οι αγκύλες σημαίνουν τη λήψη του κλασματικού μέρους του αριθμού.

Ακέραιο μέρος ενός αριθμού ΕΝΑ ονομάζεται ο μεγαλύτερος ακέραιος [ ένα ], που να μην υπερβαίνει ΕΝΑ .

Κλασματικό μέρος ενός αριθμού ΕΝΑ ορίζεται ως ο μικρότερος μη αρνητικός αριθμός ( ένα ), σύμφωνο με τον αριθμό ΕΝΑ . Κλασματικό μέρος ενός αριθμού ΕΝΑ ίση με τη διαφορά μεταξύ του αριθμού ΕΝΑ και ολόκληρο το μέρος του: ( ένα }=ΕΝΑ - [ένα ]

Για παράδειγμα, για ΕΝΑ = 2 1 / 3 [ένα ]= 2 (α) = 1 / 3

για ένα = - 2 1 / 3 [ένα ]= -3 (α) = 2 / 3

Ιδιότητες αρίθμησης αριθμών:

1. Αν ΕΝΑ ≡ σι , Οτι ( ΕΝΑ } = {σι }.

2. {ΕΝΑ +σι } = {ΕΝΑ } + {σι }.

3. Αν n είναι ακέραιος, τότε για οποιοδήποτε ΕΝΑ

na ≡ {na } ≡ n {ΕΝΑ }.

Κατά την επίλυση προβλημάτων προγραμματισμού ακέραιων αριθμών χρησιμοποιώντας τη μέθοδο Gomori, το πρώτο στάδιο συμπίπτει με τον συνηθισμένο υπολογισμό χρησιμοποιώντας τον αλγόριθμο simplex. Η προκύπτουσα λύση σε γενική μορφή θα ικανοποιήσει όλες τις προϋποθέσεις του προβλήματος, εκτός από την απαίτηση της ακεραιότητας (είναι δυνατόν, φυσικά, να ληφθεί μια ακέραια λύση ήδη στο πρώτο στάδιο). Εάν μεταξύ των τιμών των μεταβλητών στο βέλτιστο σχέδιο (σημείο Α στο Σχ. 13) υπάρχουν κλασματικές, τότε συντάσσεται ένας πρόσθετος περιορισμός, σαν να "κόβει" το κλασματικό μέρος της λύσης (γραμμή 1 σε Εικ. 13), αφήνοντας όμως σε ισχύ όλους τους περιορισμούς του προβλήματος που θα πρέπει να ικανοποιούν το βέλτιστο σχέδιο. Ένας επιπλέον περιορισμός προστίθεται στους αρχικούς περιορισμούς του προβλήματος και η διαδικασία simplex εφαρμόζεται ξανά στο εκτεταμένο σύστημα. Εάν πάλι η βέλτιστη λύση αποδειχθεί μη ακέραιος (σημείο Β στο Σχ. 13), τότε προστίθεται ένας άλλος επιπλέον περιορισμός (γραμμή 2 στο Σχ. 13) και η διαδικασία υπολογισμού επαναλαμβάνεται. Ο αλγόριθμος μας επιτρέπει να φτάσουμε σε μια βέλτιστη ακέραια λύση (εάν υπάρχει) σε έναν πεπερασμένο αριθμό βημάτων (σημείο C στο Σχ. 13).

Ρύζι. 13. Μέθοδος αποκοπής Gomori

Παράδειγμαεπίλυση ενός προβλήματος ακέραιου προγραμματισμού. Διατέθηκαν 20 χρηματικές μονάδες για την αγορά εξοπλισμού νέας μονάδας παραγωγής. Ο εξοπλισμός πρέπει να τοποθετείται σε επιφάνεια που δεν υπερβαίνει τα 38 m2. Μια επιχείρηση μπορεί να παραγγείλει δύο τύπους εξοπλισμού: πιο ισχυρά μηχανήματα τύπου Α που κοστίζουν 5 χρηματικές μονάδες, που απαιτούν επιφάνεια παραγωγής 8 m 2 (συμπεριλαμβανομένων των διόδων) και παρέχουν παραγωγικότητα 7 χιλιάδων μονάδων παραγωγής ανά βάρδια. λιγότερο ισχυρά μηχανήματα τύπου Β κοστίζουν 2 χρηματικές μονάδες, καταλαμβάνουν έκταση 4 m 2 και παράγουν 3 χιλιάδες μονάδες παραγωγής ανά βάρδια.

Ας υποδηλώσουμε με Χ 1 αριθμός αγορασμένων αυτοκινήτων Α και μετά Χ 2 - ο αριθμός των αγορασμένων αυτοκινήτων Β, λαμβάνουμε τις μαθηματικές συνθήκες του προβλήματος:

μεγιστοποίηση 7x 1 + 3x 2 → μέγ

υπό συνθήκες: 5x 1 + 2x 2 ≤ 20

8x 1 + 4x 2 ≤ 38

x 1, x 2 ≥ 0 (ακέραιοι).

Με τη βοήθεια πρόσθετων μεταβλητών x 3 και x 4, οι αρχικές ανισότητες μετατρέπονται σε εξισώσεις (ανάγεται σε κανονική μορφή):

5x 1 + 2x 2 + x 3 = 20

8x 1 + 4x 2 + x 4 = 38

Εάν οι κύριες μεταβλητές x 1 και x 2 είναι ακέραιοι, τότε αμέσως από τις εξισώσεις προκύπτει ότι οι μεταβλητές x 3 και x 4 μπορούν να λάβουν μόνο ακέραιες τιμές.

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

Ο πίνακας simplex μοιάζει με αυτό:

Βάση	ΜΕ	Σχέδιο					θ
Χ 1	Χ 2	Χ 3	Χ 4
X 1 → X 3							20/5=4 λεπτά
Χ 4							38/8=4,75
f(x) = 0	-7	-3
Χ 1				2/5	1/5		4:2/5=10
X 2 → X 4				4/5	-8/5		6:4/5=7,5 λεπτά
f(x) =28		-1/5	7/5
Χ 1						-1/2
Χ 2		7,5			-2	5/4
f(x) =29,5				1/4

Στο βέλτιστο σχέδιο, X 1 = 1, X 2 = 7,5; το μέγιστο της αντικειμενικής συνάρτησης είναι 29,5. Έτσι, είναι απαραίτητο να αγοράσετε ένα μηχάνημα τύπου Α και 7 μηχανές τύπου Β (δεν υπάρχουν αρκετά χρήματα ή χώρος για 8 μηχανές), τότε ο όγκος παραγωγής θα είναι f(x) = 7 × 1 + 3 × 7 = 28 χιλιάδες μονάδες παραγωγής .

Ας βρούμε μια ακέραια λύση χρησιμοποιώντας τη μέθοδο του Gomori. Για τη μεταβλητή X2, η οποία έχει λάβει μια μη ακέραια τιμή στο σχέδιο, συνθέτουμε την ακόλουθη εξίσωση, η οποία προκύπτει άμεσα από τον δεδομένο πίνακα simplex:

7,5 = Χ 2 – 2Χ 3 + 1,25Χ 4.

X 2 = 7,5 + 2X 3 – 1,25X 4.

Αυτή η εξίσωση, προφανώς, πρέπει να ισχύει και για μια αποδεκτή ακέραια λύση του προβλήματος.

Εφόσον το X 2 είναι ακέραιος, η έκφραση στη δεξιά πλευρά της εξίσωσης είναι επίσης ακέραιος. Επομένως, η τιμή της δεξιάς πλευράς αυτής της εξίσωσης είναι σύμφωνη με το μηδέν:

7,5 + 2Χ 3 – 1,25Χ 4 ≡ 0,

–2Χ 3 + 1,25Χ 4 ≡ 7,5.

Δεδομένων των παραπάνω ιδιοτήτων της συνάφειας, καθώς και του γεγονότος ότι τα X 3 και X 4 είναι ακέραιοι αριθμοί, αυτή η έκφραση μπορεί να μετατραπεί στα εξής:

(-2)X 3 + (1,25)X 4 ≡ {7,5} ;

από εδώ παίρνουμε:

0,25Χ 4 ≡ 0,5.

Δεδομένου ότι το X 4 είναι ένας μη αρνητικός ακέραιος, έχουμε:

0,25X 4 = 0,5, ή 1,5, ή 2,5, ...;

ως εκ τούτου,

0,25Χ 4 ≥ 0,5.

Η προκύπτουσα ανισότητα μετατρέπεται σε εξίσωση και προστίθεται στο αρχικό σύστημα περιορισμών, το οποίο τώρα περιέχει τις ακόλουθες τρεις εξισώσεις:

5x 1 + 2x 2 + x 3 = 20

8x 1 + 4x 2 + x 4 = 38

0,25x 4 – x 5 = 0,5.

Επαναλαμβάνοντας τη διαδικασία λύσης χρησιμοποιώντας τη μέθοδο simplex σε σχέση με το εκτεταμένο σύστημα περιορισμών, λαμβάνουμε ένα νέο βέλτιστο σχέδιο στο οποίο οι τιμές των μεταβλητών που περιλαμβάνονται στη βάση είναι ίσες με: X 1 = 2. X 2 = 5; X 4 = 2 (απομένουσα ελεύθερη περιοχή).

Έτσι, επιτεύχθηκε μια βέλτιστη ακέραια λύση στο πρόβλημα: κάτω από αυτούς τους περιορισμούς, η μέγιστη παραγωγικότητα (29 χιλιάδες μονάδες παραγωγής) εξασφαλίζεται με την αγορά 2 μηχανών τύπου Α και 5 μηχανών τύπου Β.

ΠΡΑΚΤΙΚΟ ΜΑΘΗΜΑ

ΚΛΑΔΟΣ ΚΑΙ ΔΕΜΕΝΗ ΜΕΘΟΔΟΣ

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

Σκεφτείτε το μοντέλο

υπό περιορισμούς

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

H j ≤ X j ≤ V j ; j=1,2,…,k,…,n.

Συνήθως Hj = 0, αλλά αυτή η συνθήκη δεν είναι απαραίτητη. Το πρόβλημα επιλύεται με τη μέθοδο simplex. Αν Xk παίρνει κλασματικές τιμές, πιστεύουμε ότι η βέλτιστη λύση στο πρόβλημα θα ικανοποιήσει τον γραμμικό περιορισμό X k ≤ D k , ή γραμμικό περιορισμό X k ≤ D k + 1 , Οπου Dk =[Xk ] – ο πλησιέστερος ακέραιος προς τα κάτω από την τιμή Xk ; D k + 1 – τον ​​πλησιέστερο ακέραιο προς τα πάνω από Xk . Εν H j ≤ D k ≤ V j – 1 . Στη συνέχεια, είναι απαραίτητο να λυθούν μερικά προβλήματα γραμμικού προγραμματισμού χρησιμοποιώντας τη μέθοδο simplex:

ΕΝΑ.

ΣΕ.

Λαμβάνουμε μια επαναληπτική διαδικασία που αναπαρίσταται ως δέντρο, η κορυφή του οποίου αντιστοιχεί στη λύση του αρχικού προβλήματος και οι δύο κλάδοι που συνδέονται με αυτό είναι λύσεις σε ένα ζεύγος προβλημάτων γραμμικού προγραμματισμού Α και Β. Οι προκύπτουσες τιμές του Οι αντικειμενικές συναρτήσεις μπορεί να είναι μικρότερες ή ίσες με την τιμή της αντικειμενικής συνάρτησης του αρχικού προβλήματος f(X) A ≤ f(X)­ 0 ; f(X) B ≤ f(X)­ 0 . Κάθε μία από τις δύο νέες κορυφές διακλάδωσης που λαμβάνονται μπορεί να έχει τους δικούς της περαιτέρω κλάδους.

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

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

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

4) Εάν στο επόμενο βήμα επανάληψης ένα από τα προβλήματα δεν έχει λύση και το δεύτερο πρόβλημα μεταξύ των τιμών των μεταβλητών στη λύση που προκύπτει έχει κλασματικές τιμές. Στη συνέχεια, για το πρώτο πρόβλημα, η διαδικασία διακλάδωσης σταματά και για περαιτέρω μετασχηματισμό του δεύτερου προβλήματος, επιλέγεται μία από τις μη ακέραιες μεταβλητές, για την οποία συντάσσονται πρόσθετοι περιορισμοί για ένα νέο ζεύγος προβλημάτων γραμμικού προγραμματισμού.

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

Εάν η επιλεγμένη εργασία οδηγεί σε διακοπή (αδιέξοδο) ή η τιμή της συνάρτησης είναι μικρότερη από την εργασία Β.1 στ(Χ) Α.4< f(X)­ В,1 ., τότε εμφανίζεται μια επιστροφή στην εργασία B.1 και εμφανίζεται ένας νέος κλάδος.

Εικ. 14. Διάγραμμα ροής αλγόριθμου διακλάδωσης και δεσμεύσεως

Ρύζι. 15. Μέθοδος διακλάδωσης και δεσίματος