Τροποποιημένη μέθοδος Simplex online. Τροποποιημένη μέθοδος Simplex. Μορφή μήτρας για το τρέχον σύνολο εξισώσεων

x 1

+x 2

+x 3

x 1

+x 2

+x 3

x 1

+x 2

+x 3

≤ = ≥

≤ = ≥

≤ = ≥

×

Προειδοποίηση

Διαγραφή όλων των κελιών;

Κλείσιμο Clear

Οδηγίες εισαγωγής δεδομένων.Οι αριθμοί εισάγονται ως ακέραιοι (παραδείγματα: 487, 5, -7623, κ.λπ.), δεκαδικοί (π.χ. 67., 102,54, κ.λπ.) ή κλάσματα. Το κλάσμα πρέπει να εισαχθεί με τη μορφή a/b, όπου τα a και b (b>0) είναι ακέραιοι ή δεκαδικοί αριθμοί. Παραδείγματα 45/5, 6.6/76.4, -7/6.7, κ.λπ.

Μέθοδος Simplex

Παραδείγματα επίλυσης ZLP χρησιμοποιώντας τη μέθοδο simplex

Παράδειγμα 1: Λύστε το παρακάτω πρόβλημα γραμμικός προγραμματισμός:

Η δεξιά πλευρά των περιορισμών του συστήματος εξισώσεων έχει τη μορφή:

Ας γράψουμε το τρέχον σχέδιο αναφοράς:

Αυτό το σχέδιο αναφοράς δεν είναι βέλτιστο επειδή υπάρχουν αρνητικά στοιχεία στην τελευταία σειρά. Το μεγαλύτερο αρνητικό στοιχείο στο συντελεστή είναι (-3), επομένως το διάνυσμα περιλαμβάνεται στη βάση Χ στο . ελάχ(40:6, 28:2)=20/3 αντιστοιχεί στη γραμμή 1. Το διάνυσμα προκύπτει από τη βάση Χ 3. Ας κάνουμε Gaussian elimination για τη στήλη Χ 2, δεδομένου ότι το κύριο στοιχείο αντιστοιχεί στη γραμμή 1. Ας επαναφέρουμε όλα τα στοιχεία αυτής της στήλης εκτός από το κύριο στοιχείο. Για να το κάνετε αυτό, προσθέστε τις γραμμές της γραμμής 2, 3, 4 με τη γραμμή 1, πολλαπλασιασμένες με -1/3, 1/6, 1/2, αντίστοιχα. Στη συνέχεια, διαιρούμε τη γραμμή με το κύριο στοιχείο με το κύριο στοιχείο.

Αυτό το σχέδιο αναφοράς δεν είναι βέλτιστο, καθώς η τελευταία σειρά έχει αρνητικό στοιχείο (-3), επομένως η βάση περιλαμβάνει το διάνυσμα Χ 1 . Καθορίζουμε ποιο διάνυσμα βγαίνει από τη βάση. Για να γίνει αυτό, υπολογίζουμε στο . min(44/3:11/3, 62/3:5/3)=4 αντιστοιχεί στη γραμμή 2. Το διάνυσμα προκύπτει από τη βάση Χ 4 . Ας κάνουμε Gaussian elimination για τη στήλη Χ 1, δεδομένου ότι το κύριο στοιχείο αντιστοιχεί στη γραμμή 2. Ας επαναφέρουμε όλα τα στοιχεία αυτής της στήλης εκτός από το κύριο στοιχείο. Για να το κάνετε αυτό, προσθέστε τις γραμμές 1, 3, 4 με τη γραμμή 2 πολλαπλασιασμένη επί 1/11, -5/11, 9/11, αντίστοιχα. Στη συνέχεια, διαιρούμε τη γραμμή με το κύριο στοιχείο με το κύριο στοιχείο.

Ο πίνακας simplex θα έχει την ακόλουθη μορφή:

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

Η λύση μπορεί να γραφτεί ως εξής: .

Εννοια αντικειμενική λειτουργίασε αυτό το σημείο: φά(Χ)=.

Παράδειγμα 2. Βρείτε το μέγιστο μιας συνάρτησης

Λύση.

Διανύσματα βάσης Χ 4 , Χ 3 επομένως όλα τα στοιχεία σε στήλες Χ 4 , Χ 3, παρακάτω οριζόντια γραμμήπρέπει να είναι μηδέν.

Μηδενίστε όλα τα στοιχεία στήλης Χ 4, εκτός από το ηγετικό στοιχείο. Για να το κάνετε αυτό, προσθέστε τη σειρά 3 με τη σειρά 1 πολλαπλασιασμένη επί 4. Μηδενίστε όλα τα στοιχεία της στήλης στο μηδέν Χ 3, εκτός από το ηγετικό στοιχείο. Για να το κάνετε αυτό, προσθέστε τη γραμμή 3 με τη γραμμή 2 πολλαπλασιασμένη επί 1.

Ο πίνακας simplex θα έχει τη μορφή:

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

Παραδείγματα επίλυσης ZLP με τη μέθοδο της τεχνητής βάσης

Παράδειγμα 1. Βρείτε το μέγιστο μιας συνάρτησης

Λύση Δεδομένου ότι ο αριθμός των διανυσμάτων βάσης πρέπει να είναι 3, προσθέτουμε μια τεχνητή μεταβλητή και προσθέτουμε αυτή τη μεταβλητή πολλαπλασιαζόμενη επί −M στην αντικειμενική συνάρτηση, όπου το M είναι πολύ. μεγάλος αριθμός:

Ο πίνακας συντελεστών του συστήματος εξισώσεων έχει τη μορφή:

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

Ας επαναφέρουμε όλα τα στοιχεία της στήλης εκτός από το κύριο στοιχείο. Για να το κάνετε αυτό, προσθέστε τη γραμμή 5 με τη γραμμή 3 πολλαπλασιασμένη με -1.

Ο πίνακας simplex θα έχει τη μορφή:

Αυτό το σχέδιο αναφοράς δεν είναι βέλτιστο επειδή υπάρχουν αρνητικά στοιχεία στην τελευταία σειρά. Το μεγαλύτερο απόλυτο αρνητικό στοιχείο είναι το (-5), επομένως το διάνυσμα περιλαμβάνεται στη βάση. Για να γίνει αυτό, υπολογίζουμε στο αντιστοιχεί στη γραμμή 3. Ένα διάνυσμα προκύπτει από τη βάση Ας κάνουμε μια εξαίρεση Gauss για τη στήλη, δεδομένου ότι το κύριο στοιχείο αντιστοιχεί στη γραμμή 3. Ας επαναφέρουμε όλα τα στοιχεία αυτής της στήλης, εκτός από το κύριο στοιχείο. Για να το κάνετε αυτό, προσθέστε τις γραμμές γραμμής 5 με τη γραμμή 3 πολλαπλασιαζόμενη επί 1. Στη συνέχεια, διαιρέστε τη γραμμή με το κύριο στοιχείο με το κύριο στοιχείο.

Ο πίνακας simplex θα έχει την ακόλουθη μορφή:

Αυτό το σχέδιο αναφοράς δεν είναι βέλτιστο επειδή υπάρχουν αρνητικά στοιχεία στην τελευταία σειρά. Το μεγαλύτερο απόλυτο αρνητικό στοιχείο είναι το (-3), επομένως το διάνυσμα περιλαμβάνεται στη βάση. Για να γίνει αυτό, υπολογίζουμε στο αντιστοιχεί στη σειρά 1. Το διάνυσμα προκύπτει από τη βάση Χ 2. Ας κάνουμε Gaussian elimination για τη στήλη Χ 1 , δεδομένου ότι το κύριο στοιχείο αντιστοιχεί στη γραμμή 1. Ας επαναφέρουμε όλα τα στοιχεία αυτής της στήλης εκτός από το κύριο στοιχείο. Για να το κάνετε αυτό, προσθέστε τις γραμμές 2, 3, 4 με τη γραμμή 1, πολλαπλασιαζόμενες επί 3/2, -1/10, 3/2, αντίστοιχα. Στη συνέχεια, διαιρούμε τη γραμμή με το κύριο στοιχείο με το κύριο στοιχείο.

Ο πίνακας simplex θα έχει την ακόλουθη μορφή:

Αυτό το σχέδιο αναφοράς δεν είναι βέλτιστο επειδή υπάρχουν αρνητικά στοιχεία στην τελευταία σειρά. Το μεγαλύτερο αρνητικό στοιχείο στο συντελεστή (-13/2), επομένως η βάση περιλαμβάνει το διάνυσμα Χ 3. Καθορίζουμε ποιο διάνυσμα βγαίνει από τη βάση. Για να γίνει αυτό, υπολογίζουμε στο αντιστοιχεί στη γραμμή 3. Το διάνυσμα προκύπτει από τη βάση Χ 5 . Ας κάνουμε Gaussian elimination για τη στήλη Χ 3, δεδομένου ότι το κύριο στοιχείο αντιστοιχεί στη γραμμή 3. Ας επαναφέρουμε όλα τα στοιχεία αυτής της στήλης εκτός από το κύριο στοιχείο. Για να το κάνετε αυτό, προσθέστε τις γραμμές της γραμμής 1, 2, 4 με τη γραμμή 3, πολλαπλασιαζόμενες επί 5/3, 25/9, 65/9, αντίστοιχα. Στη συνέχεια, διαιρούμε τη γραμμή με το κύριο στοιχείο με το κύριο στοιχείο.

Ο πίνακας simplex θα έχει την ακόλουθη μορφή:

Το τρέχον σχέδιο αναφοράς είναι βέλτιστο, καθώς δεν υπάρχουν αρνητικά στοιχεία κάτω από τις μεταβλητές στις γραμμές 4−5.

Η λύση στο αρχικό πρόβλημα μπορεί να γραφτεί ως εξής:

Παράδειγμα 2. Βρείτε βέλτιστο σχέδιοΠροβλήματα γραμμικού προγραμματισμού:

Ο πίνακας συντελεστών του συστήματος εξισώσεων έχει τη μορφή:

Διανύσματα βάσης Χ 4 , Χ 5 , Χ 6 επομένως όλα τα στοιχεία σε στήλες Χ 4 , Χ 5 , Χ 6, κάτω από την οριζόντια γραμμή πρέπει να είναι μηδέν.

Μηδενίστε όλα τα στοιχεία στήλης Χ 4, εκτός από το ηγετικό στοιχείο. Για να το κάνετε αυτό, προσθέστε τη γραμμή 4 με τη γραμμή 1 πολλαπλασιασμένη με -1. Μηδενίστε όλα τα στοιχεία στήλης Χ 5, εκτός από το κύριο στοιχείο. Για να το κάνετε αυτό, προσθέστε τη γραμμή 5 με τη γραμμή 2 πολλαπλασιασμένη με -1. Μηδενίστε όλα τα στοιχεία στήλης Χ 6, εκτός από το ηγετικό στοιχείο. Για να το κάνετε αυτό, προσθέστε τη γραμμή 5 με τη γραμμή 3 πολλαπλασιασμένη με -1.

Ο πίνακας simplex θα έχει τη μορφή:

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

Λαμβάνοντας υπόψη τις δυνατότητες των σύγχρονων PPP που χρησιμοποιούν μια τροποποιημένη μέθοδο simplex με πολλαπλασιαστική αναπαράσταση του πίνακα, η αντιστοίχιση του επόμενου διανύσματος στην κατηγορία των διανυσμάτων που εξασφαλίζουν συμβατότητα ή ασυμβατότητα απαιτεί μόνο μερικές επαναλήψεις μετά την τροποποίηση του γενικευμένου πίνακα  

ΤΡΟΠΟΠΟΙΗΜΕΝΗ ΜΕΘΟΔΟΣ SIMPLEX  

Ένα υπολογιστικό σχήμα που βασίζεται στον μετασχηματισμό των αντίστροφων πινάκων. Αναλύοντας την υπολογιστική διαδικασία της μεθόδου simplex από την άποψη της εκτίμησης της έντασης εργασίας, είναι εύκολο να παρατηρήσουμε ότι η πιο κρίσιμη από αυτή την άποψη είναι η διαδικασία επανυπολογισμού των τιμών των A και b κατά τη μετάβαση από το ένα βασικό σχέδιο στο άλλο ( ρήτρα 3 του αλγορίθμου). Ωστόσο, στην περίπτωση που ο αριθμός των περιορισμών του προβλήματος m είναι σαφώς μικρότερος από τον αριθμό των μεταβλητών i, είναι δυνατό να επιτευχθεί σημαντική εξοικονόμηση πόρων εκτελώντας στην επόμενη επανάληψη q τον μετασχηματισμό Jordan-Gauss όχι στον πίνακα A(p () από τον D Chr(αρχική στήλη aChr O. Αυτές οι σκέψεις βασίζονται στη βάση του υπολογιστικού σχήματος της μεθόδου simplex, που βασίζεται στον μετασχηματισμό των αντίστροφων πινάκων, που ονομάζεται επίσης τροποποιημένη μέθοδος simplex για πρώτη φορά. αυτόν τον αλγόριθμοπροτάθηκε το 1951 στα έργα του L. V. Kantorovich.  

Το υπολογιστικό σχήμα της τροποποιημένης μεθόδου simplex αντιστοιχεί στο σύστημα των πινάκων 7] και T q). Ο Πίνακας 7J (Εικ. 1.7) είναι κοινός σε όλες τις επαναλήψεις και χρησιμεύει για την απόκτηση  

Κατ' αναλογία με την παράγραφο 1.4.1, θα περιγράψουμε το επίσημο σχήμα του αλγορίθμου της τροποποιημένης μεθόδου simplex.  

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

Παράδειγμα αποφάσεις ΣΔΙΤτροποποιημένη μέθοδος Simplex. Ας παρουσιάσουμε μια λύση στο πρόβλημα που εξετάστηκε προηγουμένως (1.34)-(1.35), με βάση τη χρήση της διαδικασίας της τροποποιημένης μεθόδου simplex. Κατ' αναλογία με την ρήτρα 1.4.3  

Ας επιστρέψουμε για άλλη μια φορά στον πίνακα T (Εικ. 1.8), που προέκυψε στην τελική επανάληψη της διαδικασίας της τροποποιημένης μεθόδου simplex. Ας εξετάσουμε λεπτομερέστερα τη μηδενική σειρά του πίνακα A 4p(

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

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

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

Διατυπώστε τις κύριες διαφορές μεταξύ της τροποποιημένης μεθόδου simplex και της τυπικής μεθόδου.  

Να αναφέρετε τα πλεονεκτήματα της τροποποιημένης μεθόδου simplex.  

Θα διαφέρει ο αριθμός των επαναλήψεων κατά την επίλυση του ίδιου προβλήματος κατά την επίλυσή του χρησιμοποιώντας την τυπική και τροποποιημένη μέθοδο simplex;  

Η μέθοδος αποσύνθεσης αναπτύχθηκε για την επίλυση προβλημάτων γραμμικού προγραμματισμού υψηλών διαστάσεων με δομή μπλοκ. Η υπολογιστική του διαδικασία βασίζεται κυρίως στις ιδέες της τροποποιημένης μεθόδου simplex. Ωστόσο, η σημασία της μεθόδου Dantzig-Wolfe δεν έγκειται μόνο και (όχι τόσο) στα υπολογιστικά της πλεονεκτήματα, αλλά στην ικανότητα να δίνει μια ουσιαστική οικονομική ερμηνεία. Η μέθοδος περιλαμβάνει την αποσύνθεση του αρχικού προβλήματος (5.6)-(5.9) σε τοπικά προβλήματα που αντιστοιχούν σε μεμονωμένα μέρη της ένωσης (σε σε αυτήν την περίπτωσηεπιχειρήσεις), και κύρια δραστηριότητα(αντιστοιχεί στο σύνολο της ένωσης και συνδέει αυτές τις τοπικές εργασίες).  

R. B. Dubina, K. E. Chernin. Πρόγραμμα εκπαίδευσης και καταγραφής σε πίνακες M.B για την τροποποιημένη μέθοδο Simplex - Συλλογή προγραμμάτων υπολογιστή Ural. L., Arkt. και την Ανταρκτική. Ινστιτούτο, 1966.  

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

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

Καλή δουλειάστον ιστότοπο">

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

Παρόμοια έγγραφα

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

περίληψη, προστέθηκε 15/06/2010


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

εργασία μαθήματος, προστέθηκε 17/02/2010


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

δοκιμή, προστέθηκε 15/08/2012


Χρησιμοποιώντας τη μέθοδο simplex για την επίλυση προβλημάτων γραμμικού προγραμματισμού για τον υπολογισμό του ημερήσιου όγκου παραγωγής. Έλεγχος του σχεδίου για βελτιστοποίηση. Επανυπολογισμός πίνακας simplexΜέθοδος Jordan-Gauss. Κατάρτιση μοντέλου μεταφορικού προβλήματος.

δοκιμή, προστέθηκε 18/02/2014


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

δοκιμή, προστέθηκε 05/11/2014


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

εργασία μαθήματος, προστέθηκε 11/12/2010


Συλλογή μαθηματικό μοντέλοκαθήκοντα. Υπολογισμός του βέλτιστου σχεδίου μεταφοράς με το ελάχιστο κόστος με τη μέθοδο του δυναμικού. Η καλύτερη επιλογήειδικό κινητό εξοπλισμό για τεχνική υποστήριξηΔΙΟΙΚΗΣΗ ΠΑΡΑΓΩΓΗΣ.

δοκιμή, προστέθηκε 06/01/2014

3. Τροποποιημένη μέθοδος simplex

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

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

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

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

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

1. Το αρχικό πρόβλημα ανάγεται σε πρόβλημα γραμμικού προγραμματισμού.

2. Βρείτε μια λύση γραμμικό πρόβλημα

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

Πρώτο στάδιο: Λήψη εργασιών για μαθήματα

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

Κάτω από κάθε αριθμό αναγράφονται τα γράμματα a, b, c, d, e, f την παρακάτω φόρμα:

από την τελευταία σειρά του πίνακα ατομικές εργασίεςΒρίσκουμε τις στήλες που αντιστοιχούν στα γράμματα a, b, c, d, e, f. Στη συνέχεια, τα αριθμητικά δεδομένα που απαιτούνται για να γίνει αυτό εργασία μαθημάτων, θα υπάρχουν δεδομένα που βρίσκονται σε α - αυτή η στήλη στη γραμμή 9, β - αυτή η στήλη στη γραμμή 5, γ - αυτή η στήλη στη γραμμή 5, δ - αυτή η στήλη στη γραμμή 8, e - αυτή η στήλη στη γραμμή 7 και f - αυτή η στήλη στη γραμμή 2.

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

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

όπου C i και είναι σταθερές τιμές, i = 1, 2, 3;

X 1 – εργατικοί πόροι σε ανθρωποημέρες.

X 2 – νομισματικοί και υλικοί πόροι, σε tenge.

Το Y i είναι το προϊόν που προκύπτει

X 1 = a 1 x 1 + b 1 x 2 + c 1 x 3

X 2 = a 2 x 1 + b 2 x 2 + c 2 x 3

Βρείτε όλες τις μη αρνητικές βασικές λύσεις και προσδιορίστε το βέλτιστο σχέδιο F = y 1 + y 2 + y 3.

Είναι γνωστό ότι για την παραγωγή του j – αυτού του τύπου προϊόντος, ij μονάδες του i – δαπανώνται αυτός ο πόρος. Οι δαπάνες αυτές δίνονται στους πίνακες 3.9.1. – 3.9.10

Τα επόμενα αριθμητικά δεδομένα λαμβάνονται μόνο από τον πίνακα δεδομένων πηγής της επιλεγμένης επιλογής εργασίας, π.χ. από τον πίνακα Νο 3.9.11.

2. Σύμφωνα με τη στήλη του πίνακα Νο. 3.9.11 για τη γραμμή 8, ο αρχικός πίνακας κόστους των μονάδων πόρων θα είναι ο πίνακας Νο. 3.9.4 δηλ. παρακάτω πίνακας:

Πόροι προϊόντων
Εγώ	8	4	6
II	160	240	200

3. Χρησιμοποιώντας τη στήλη c – στη γραμμή 3 βρίσκουμε με 1 =6, α 1 =0,6

4. Χρησιμοποιώντας τη στήλη d – στη γραμμή 5 προσδιορίζουμε με 2 =5, α 2 =0,5

5. Χρησιμοποιώντας τη στήλη e – γραμμή 4, διαπιστώνουμε ότι c 3 =8, α 3 =0,4.

6. Και τέλος, χρησιμοποιώντας τη στήλη f - στη γραμμή 1 βρίσκουμε Τ άτομα ημέρες = 1000, P tenge = 280000

Για την παραγωγή υπάρχουν εργατικοί πόροι T man ημέρες και νομισματικοί πόροι P tenge.

Απαιτείται να βρεθεί το βέλτιστο σχέδιο παραγωγής στο οποίο το προϊόν παραγωγής θα είναι το μεγαλύτερο.

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

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

Πόροι προϊόντων
Εγώ	8	4	6	1000
II	160	240	200	280000

Έστω X 1 που υποδηλώνει πόρους του πρώτου τύπου.

Έστω X 2 που υποδηλώνει πόρους τύπου II.

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

8Χ 1 + 4Χ 2 + 6Χ 3 ≤ 1000

240Χ 1 + 200Χ 2 + 160Χ 3 ≤ 280000

Έτσι, έχουμε ένα πρόβλημα μη γραμμικού προγραμματισμού. Τέτοια προβλήματα ονομάζονται προβλήματα μη γραμμικού προγραμματισμού.

Τα προβλήματα μη γραμμικού προγραμματισμού λύνονται με την αναγωγή τους σε προβλήματα γραμμικού προγραμματισμού.

Για την επίλυση του προβλήματος του γραμμικού προγραμματισμού χρησιμοποιείται η μέθοδος simplex.

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

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

8Χ 1 + 4Χ 2 + 6Χ 3 + Χ 4 = 1000

240Χ 1 + 200Χ 2 + 160Χ 3 + Χ 5 = 280000

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

Η εύρεση του σημείου Kuhn-Tucker παρέχει μια βέλτιστη λύση στο πρόβλημα του μη γραμμικού προγραμματισμού. Το θεώρημα 2 μπορεί επίσης να χρησιμοποιηθεί για να αποδειχθεί η βέλτιστη αυτή την απόφασηπροβλήματα μη γραμμικού προγραμματισμού. Για να το καταλάβετε, εξετάστε ξανά το παράδειγμα: Ελαχιστοποίηση υπό περιορισμούς Χρησιμοποιώντας το Θεώρημα 2, αποδεικνύουμε ότι η λύση είναι βέλτιστη. Έχουμε λοιπόν...

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

Αν βάλουμε τις τρέχουσες βασικές μεταβλητές σε έναν τόσο απλό πίνακα ίσο με Ai,0 και τις ελεύθερες ίσες με μηδέν, θα πάρουμε βέλτιστη λύση. Η πρακτική της χρήσης της μεθόδου simplex έχει δείξει ότι ο αριθμός των επαναλήψεων που απαιτούνται για την επίλυση ενός προβλήματος γραμμικού προγραμματισμού κυμαίνεται συνήθως από 2m έως 3m, αν και για ορισμένα ειδικά κατασκευασμένα προβλήματα, οι υπολογισμοί σύμφωνα με τους κανόνες της μεθόδου simplex μετατρέπονται σε άμεσο...

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

3.1. Περιγραφή

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

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

Η εξίσωση W(x) = c, όπου W(x) είναι η γραμμική συνάρτηση που πρέπει να μεγιστοποιηθεί (ή να ελαχιστοποιηθεί), δημιουργεί το υπερεπίπεδο L(c). Η εξάρτηση από το c δημιουργεί μια οικογένεια παράλληλων υπερεπίπεδων. Στην περίπτωση αυτή, το ακραίο πρόβλημα παίρνει την ακόλουθη διατύπωση: απαιτείται να βρεθεί το μεγαλύτερο c έτσι ώστε το υπερεπίπεδο L(c) να τέμνει το πολύεδρο τουλάχιστον σε ένα σημείο. Σημειώστε ότι η τομή ενός βέλτιστου υπερεπίπεδου και ενός πολυέδρου θα περιέχει τουλάχιστον μία κορυφή και θα είναι περισσότερες από μία εάν η τομή περιέχει μια ακμή ή μια όψη διαστάσεων k. Επομένως, το μέγιστο της συνάρτησης μπορεί να αναζητηθεί στις κορυφές του πολυέδρου. Η αρχή της μεθόδου simplex είναι ότι επιλέγεται μία από τις κορυφές του πολυέδρου, μετά την οποία αρχίζει η κίνηση κατά μήκος των άκρων του από κορυφή σε κορυφή προς την κατεύθυνση της αύξησης της τιμής της συνάρτησης. Όταν η μετάβαση κατά μήκος μιας ακμής από την τρέχουσα κορυφή σε μια άλλη κορυφή με υψηλότερη λειτουργική τιμή είναι αδύνατη, θεωρείται ότι έχει βρεθεί η βέλτιστη τιμή του c.

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

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

Η ακολουθία των υπολογισμών που χρησιμοποιούν τη μέθοδο simplex μπορεί να χωριστεί σε δύο κύριες φάσεις:

1. εύρεση της αρχικής κορυφής του συνόλου των εφικτών λύσεων.

2. διαδοχική μετάβαση από κορυφή σε κορυφή, που οδηγεί στη βελτιστοποίηση της τιμής της αντικειμενικής συνάρτησης.

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

διφασικό.

3.2. Αλγόριθμος μεθόδου Simplex

Ενισχυμένη δήλωση προβλήματος

Εξετάστε το ακόλουθο πρόβλημα γραμμικού προγραμματισμού:

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

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

Στη συνέχεια, μπορούμε να εκχωρήσουμε την τιμή 0 σε αυτόν τον αριθμό μεταβλητών και να καλέσουμε