Διάφορες μορφές σημειογραφίας του ZLP (γενική, κανονική, συμμετρική). Μέθοδος Simplex για την επίλυση ενός προβλήματος γραμμικού προγραμματισμού

Πρόβλημα γραμμικού προγραμματισμού της μορφής ax = b όπου a είναι ο πίνακας συντελεστών, b το διάνυσμα περιορισμού.
Παράδειγμα:

Σε κάθε πρόβλημα LP, οι τιμές των μεταβλητών αναζητούνται υπό την προϋπόθεση ότι:

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

Οδηγίες. Επιλέξτε τον αριθμό των μεταβλητών και τον αριθμό των σειρών (αριθμός περιορισμών). Η λύση που προκύπτει αποθηκεύεται σε ένα αρχείο Word.

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

Ορισμός. Το πρόβλημα LP έχει κανονική μορφή εάν όλοι οι περιορισμοί συστήματος αποτελούνται μόνο από εξισώσεις (εκτός από τις ανισότητες που εκφράζουν τη μη αρνητικότητα των μεταβλητών) και η αντικειμενική συνάρτηση πρέπει να ελαχιστοποιηθεί.
Ένα παράδειγμα τέτοιου προβλήματος LP σε κανονική μορφή είναι το Πρόβλημα 1 - ένα πρόβλημα ισορροπημένης μεταφοράς με ένα σύστημα περιορισμών (1) και μια αντικειμενική συνάρτηση (2).
Ωστόσο, στα περισσότερα οικονομικά προβλήματα, τις περισσότερες φορές το σύστημα περιορισμών περιλαμβάνει αρχικά όχι μόνο εξισώσεις, αλλά και ανισότητες.

Δήλωση.Οποιοδήποτε γενικό πρόβλημα LP μπορεί να μειωθεί σε κανονική μορφή.
Η μείωση του γενικού προβλήματος LP σε κανονική μορφή επιτυγχάνεται με την εισαγωγή νέων (ονομάζονται πρόσθετες) μεταβλητές.
Το σύστημα των περιορισμών (3) αυτού του προβλήματος αποτελείται από τέσσερις ανισότητες. Με την εισαγωγή πρόσθετων μεταβλητών y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0, y 4 ≥ 0, μπορούμε να πάμε στο σύστημα περιορισμών:

Αυτές οι πρόσθετες μεταβλητές yέχω ένα απολύτως σαφές οικονομικό νόημα, δηλαδή, σημαίνουν το ποσό του αχρησιμοποίητου χρόνου εργασίας (χρόνος διακοπής λειτουργίας του μηχανήματος Εγώ-ο τύπος).
Για παράδειγμα, εάν οι μηχανές του πρώτου τύπου δούλευαν και για τις 18 ώρες, τότε x + y = 18, επομένως, y 1 = 0. Επιτρέπουμε όμως την πιθανότητα ατελούς χρήσης του χρόνου λειτουργίας της πρώτης μηχανής Χ + y<18. В этом случае yΤο 1 παίρνει θετική τιμή και μπορεί να θεωρηθεί ως αχρησιμοποίητο χρονικό όριο. Για παράδειγμα, γνωρίζοντας τη λύση αυτού του προβλήματος από την παράγραφο 3.3.2, Χ = 12, y= 6, μπορούμε να συμπεράνουμε από το σύστημα περιορισμών (3.9) ότι y 1 = y 2 = y 3 = 0, και y 4 = 12 – 6 = 6. Δηλαδή μηχανές πρώτου, δεύτερου, τρίτου τύπου χρησιμοποιούν πλήρως τον χρόνο εργασίας τους. Αλλά το τέταρτο μηχάνημα είναι μόνο μισό φορτωμένο, 6 ώρες, και, δεδομένου του βέλτιστου σχεδίου, είναι σε αδράνεια. Ίσως, μετά από τέτοια συμπεράσματα, ο επικεφαλής της επιχείρησης να θέλει να το φορτώσει με άλλες εργασίες, να το νοικιάσει για αυτή τη φορά κ.λπ.
Έτσι, εισάγοντας πρόσθετες μεταβλητές, μπορούμε να μειώσουμε οποιονδήποτε περιορισμό τύπου ανισότητας σε μια εξίσωση.

Ας εξετάσουμε το πρόβλημα του μείγματος. Το σύστημα περιορισμών έχει τη μορφή:
Οι ανισότητες στράφηκαν προς το "περισσότερο", επομένως, εισάγοντας πρόσθετες μεταβλητές y 1, y 2, y 3 ≥ 0, πρέπει να αφαιρεθούν από την αριστερή πλευρά για να εξισωθούν με τη δεξιά. Λαμβάνουμε ένα σύστημα περιορισμών σε κανονική μορφή:
Οι μεταβλητές y i θα έχουν επίσης οικονομική λογική. Εάν θυμάστε το πρακτικό περιεχόμενο του προβλήματος, τότε η μεταβλητή y 1 θα σημαίνει την ποσότητα της περίσσειας ουσίας Α στο μείγμα, y 2 θα σημαίνει την ποσότητα της περίσσειας ουσίας ΣΕστο μείγμα y 3 – πλεόνασμα ΜΕστο μείγμα.
Η εργασία εύρεσης της μέγιστης τιμής της αντικειμενικής συνάρτησης μπορεί να μειωθεί στην εύρεση της ελάχιστης για τη συνάρτηση - φάλόγω της προφανείας της πρότασης max F = –min (– F). Κοιτάξτε την εικόνα: αν κάποια στιγμή Χ= Χ 0 λειτουργία y= φά(Χ) φτάνει στο μέγιστο και μετά η συνάρτηση y= –φά(Χ), συμμετρικό προς αυτό σε σχέση με τον άξονα ΒΟΔΙ, στο ίδιο σημείο ΧΤο 0 θα φτάσει στο ελάχιστο και φάμέγιστο = – (– φά min) σε Χ = Χ 0 .

Συμπέρασμα.Για να αναπαραστήσουμε το πρόβλημα LP σε κανονική μορφή είναι απαραίτητο:

• να μετατρέψει τις ανισότητες που περιλαμβάνονται στο σύστημα περιορισμών του προβλήματος σε εξισώσεις εισάγοντας πρόσθετες μεταβλητές.
• αν η αντικειμενική συνάρτηση φά→max (μεγιστοποιεί), αντικαθίσταται από τη συνάρτηση – φά→ min (το οποίο ελαχιστοποιείται).

Μια αναλυτική μέθοδος για την επίλυση ενός προβλήματος γραμμικού προγραμματισμού είναι μέθοδο simplex.Για να εφαρμοστεί, τα προβλήματα LP που παρουσιάζονται με διαφορετικούς τρόπους πρέπει να μειωθούν σε κανονική μορφή. Το πρόβλημα γραμμικού προγραμματισμού, γραμμένο με τη μορφή (2.1.1)-(2.1.3), είναι μια διευρυμένη μορφή γραφής του γενικού προβλήματος γραμμικού προγραμματισμού (GLP).

Θα ονομάσουμε το ακόλουθο πρόβλημα πρόβλημα κανονικού γραμμικού προγραμματισμού (CLPT):

υπό περιορισμούς που έχουν τη μορφή ισότητας,

Εάν για ένα πρόβλημα στη μορφή (2.3.1)-(2.3.4) η προϋπόθεση ικανοποιείται t = n,τότε η λύση του ανάγεται στην επίλυση του συστήματος των εξισώσεων

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

κατάσταση Τ

• 1. Να πάω από το πρόβλημα μεγιστοποίησηςαντικειμενική συνάρτηση (2.3.1) έως πρόβλημα ελαχιστοποίησηςαρκετά πάρτε όλους τους συντελεστές Cjαντικειμενική λειτουργία με αντίστροφα σημάδιακαι λύστε το πρόβλημα που προκύπτει στο μέγιστο. Μετά την εύρεση του μέγιστου, η τιμή της αντικειμενικής συνάρτησης πρέπει να ληφθεί με το αντίθετο πρόσημο. Η βέλτιστη λύση θα παραμείνει η ίδια.
• 2. Να πάω από μικρότερο ή ίσο με περιορισμό ισότηταςείναι απαραίτητο με το σύμβολο συν:

3. Να πάω από έναν περιορισμό «μεγαλύτερο ή ίσο με» στην ισότηταείναι απαραίτητο εισάγετε μια πρόσθετη μη αρνητική μεταβλητήμε πρόσημο μείον:

Σε αυτή την περίπτωση, κάθε ανισότητα εισάγει τη δική της (n +/)-η πρόσθετη μεταβλητή.

• 4. Τα πάντα ισότητες που έχουν αρνητικούς ελεύθερους όρους χωρίζονται σε-1, για να πληρούται η προϋπόθεση (2.3.4).
• 5. Εάν σε κάποια μεταβλητή Xj η συνθήκη μη αρνητικότητας δεν επιβάλλεται, Οτι κάντε μια αλλαγή των μεταβλητών Xj=x".- Χ" x"j > 0, x"> 0. Στο μετασχηματισμένο πρόβλημα όλες οι μεταβλητές είναι μη αρνητικές.

Υπάρχει μια δήλωση ότι οποιοδήποτε ZLP μπορεί να αναχθεί σε κανονική μορφή.

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

Ας εισάγουμε μια πρόσθετη μεταβλητή jc 3 > 0 με σύμβολο συν στην πρώτη ανισότητα και στη δεύτερη x 4> 0 με αρνητικό πρόσημο και στο τρίτο x 5> 0 επίσης με πρόσημο συν. Ως αποτέλεσμα, λαμβάνουμε ένα σύστημα περιορισμών προβλημάτων σε κανονική μορφή:

Δεδομένων αυτών των περιορισμών, πρέπει να βρείτε τη μέγιστη τιμή της συνάρτησης:

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

Παράδειγμα 2.3.2. Πρόβλημα βέλτιστης χρήσης πόρων (πρόβλημα χαλιού)[17 J.

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

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

Οικονομικό και μαθηματικό μοντέλο του προβλήματος Μεταβλητές: x x, x 2, x 3, x 4 -αριθμός χαλιών κάθε τύπου. Αντικειμενική λειτουργία -είναι το συνολικό κόστος παραγωγής που πρέπει να μεγιστοποιηθεί:

Όρια πόρων:

Ας φέρουμε το πρόβλημα σε κανονική μορφή εισάγοντας πρόσθετες μεταβλητές x 5, x 6Και x 7:

Θα φανεί παρακάτω ότι το βέλτιστο σχέδιο παραγωγής είναι το διάνυσμα Χ* =(0; 30; 10; 0), η τιμή της αντικειμενικής συνάρτησης είναι 150, δηλ. Για τη μεγιστοποίηση του συνολικού κόστους παραγωγής, απαιτείται η παραγωγή 30 χαλιών δεύτερου τύπου και 10 χαλιών τρίτου τύπου. Ας αντικαταστήσουμε τις βέλτιστες διανυσματικές τιμές Χστους περιορισμούς KZLP:

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

Σε αυτήν την περίπτωση x σεδείχνει ότι έχουν απομείνει 200 ​​κιλά πρώτων υλών.

Οι κύριες μεταβλητές λοιπόν x v x 2, x 3, x lσημαίνει τον αριθμό των χαλιών κάθε τύπου και πρόσθετες μεταβλητές x 5, x 6 το 7 τους -όγκος υποχρησιμοποιημένων πόρων.

Απάντηση. Βέλτιστο σχέδιο παραγωγής Χ* = (0; 30;

10; 0).

Σχέδιο, ή αποδεκτή λύση, το KZLP ονομάζεται διάνυσμα X =(jc σελ Χ 2 ,..., x n), ικανοποιώντας τις προϋποθέσεις (2.3.2)-(2.3.4).

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

Το σχέδιο αναφοράς ονομάζεται μη εκφυλισμένος,εάν περιέχει Τθετικά συστατικά, αλλιώς λέγεται εκφυλισμένος.

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

Το σύνολο όλων των σχεδίων της ΣΔΙΤ (αν υπάρχουν) είναι κυρτό πολύεδρο.Κάθε γωνία (ακραίο) σημείο του πολυεδρικού διαλύματος αντιστοιχεί σε σχέδιο αναφοράς(μη αρνητικές βασικές λύσεις του συστήματος εξισώσεων KZLP). Κάθε σχέδιο αναφοράς καθορίζεται από το σύστημα Τ γραμμικά ανεξάρτητα διανύσματα που περιέχονται σε ένα δεδομένο σύστημα των Π διανύσματα D, D,..., Μια σελ. Εάν υπάρχει ένα βέλτιστο σχέδιο, τότε υπάρχει ένα γωνιακό σημείο του πολυέδρου απόφασης στο οποίο η γραμμική συνάρτηση φτάνει τη μεγαλύτερη (μικρότερη) τιμή της.

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

Παράδειγμα 2.3.3.Λάβετε μια λύση στο πρόβλημα της βέλτιστης χρήσης περιορισμένων πόρων (λύστε το ZL P):

Λύση. Ας φέρουμε το πρόβλημα σε κανονική μορφή εισάγοντας πρόσθετες μεταβλητές x 3, x 4 και x 5:

Ας βρούμε όλα τα υποστηρικτικά σχέδια του συστήματος περιορισμών αυτού του KZLP (l? - 5; /77 - 3). ο αριθμός τους δεν υπερβαίνει τα 10:

Χρησιμοποιώντας τη μέθοδο Jordan-Gauss (βλ. παράγραφο 1.4), γράφουμε όλες τις βασικές λύσεις του συστήματος εξισώσεων (Πίνακας 2.3.2).

Αριθμός βάση nogo λύσεις	Βάση						Σχέδιο

Μεταξύ των δέκα βασικών λύσεων υπάρχουν πέντε βασικές:

Τα υποδεικνυόμενα σχέδια αναφοράς στο Σχ. 2.3.1 αντιστοιχούν αντίστοιχα στα ακόλουθα γωνιακά σημεία και τις τιμές του CF σε αυτά:

Ρύζι. 2.3.1.

Σύμφωνα με τη θεωρία Η βέλτιστη λύση LP περιλαμβάνεται μεταξύ των σχεδίων αναφοράς.

Έτσι, η μέγιστη τιμή ίση με 2300 επιτυγχάνεται από την αντικειμενική συνάρτηση στο σημείο ΣΕ στο σχέδιο αναφοράς Χ 5 = (70; 80; 0; 60; 0).

Απάντηση.Βέλτιστο σχέδιο εργασιών: x (= 70, x 2 = 80, αντικειμενική τιμή συνάρτησης f(x v x 2) = 2300.

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

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

• εάν στο αρχικό πρόβλημα είναι απαραίτητο να προσδιοριστεί το μέγιστο μιας γραμμικής συνάρτησης, τότε θα πρέπει να αλλάξετε το πρόσημο και να αναζητήσετε το ελάχιστο αυτής της συνάρτησης.
• Εάν η δεξιά πλευρά των περιορισμών είναι αρνητική, τότε αυτός ο περιορισμός πρέπει να πολλαπλασιαστεί με -1.
• εάν υπάρχουν ανισότητες μεταξύ των περιορισμών, τότε με την εισαγωγή πρόσθετων μη αρνητικών μεταβλητών μετατρέπονται σε ισότητες.
• αν κάποια μεταβλητή x jδεν έχει περιορισμούς πρόσημου, τότε αντικαθίσταται (στην αντικειμενική συνάρτηση και σε όλους τους περιορισμούς) από τη διαφορά μεταξύ δύο νέων μη αρνητικών μεταβλητών:
  x 3 = x 3 + - x 3 - , Οπου x 3 + , x 3 - ≥ 0 .

Παράδειγμα 1. Αναγωγή του προβλήματος γραμμικού προγραμματισμού σε κανονική μορφή:

min L = 2x 1 + x 2 - x 3 ;
2x 2 - x 3 ≤ 5;
x 1 + x 2 - x 3 ≥ -1;
2x 1 - x 2 ≤ -3;
x 1 ≤ 0; x 2 ≥ 0; x 3 ≥ 0.

Ας εισάγουμε μεταβλητές ισοπέδωσης σε κάθε εξίσωση του συστήματος περιορισμών x 4, x 5, x 6. Το σύστημα θα γραφτεί με τη μορφή ισοτήτων και στην πρώτη και τρίτη εξίσωση του συστήματος των περιορισμών οι μεταβλητές x 4, x 6εισάγονται στην αριστερή πλευρά με το σύμβολο «+» και στη δεύτερη εξίσωση η μεταβλητή x 5εισάγεται με το σύμβολο "-".

2x 2 - x 3 + x 4 = 5;
x 1 + x 2 - x 3 - x 5 = -1;
2x 1 - x 2 + x 6 = -3;
x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.

Οι ελεύθεροι όροι στην κανονική μορφή πρέπει να είναι θετικοί για να γίνει αυτό, πολλαπλασιάστε τις δύο τελευταίες εξισώσεις με -1:

2x 2 - x 3 + x 4 = 5;
-x 1 - x 2 + x 3 + x 5 = 1;
-2x 1 + x 2 - x 6 = 3.

Στην κανονική μορφή γραφής προβλημάτων γραμμικού προγραμματισμού, όλες οι μεταβλητές που περιλαμβάνονται στο σύστημα περιορισμών πρέπει να είναι αρνητικές. Ας υποθέσουμε ότι x 1 = x 1 " - x 7 , Οπου x 1 "≥ 0, x 7 ≥ 0 .

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

L min = 2x 1 " + x 2 - x 3 - 2x 7 ;
2x 2 - x 3 + x 4 = 5;
-x 1 " - x 2 + x 3 + x 5 + x 7 = 1;
-2x 1 " + x 2 - x 6 + 2x 7 = 3;
x 1 "≥ 0; x i ≥ 0, i=2, 3, 4, 5, 6, 7.

Συνθήκη βελτιστοποίησης για το βασικό σχέδιο του κανονικού προβλήματος LP. Μέθοδος Simplex και η σύγκλισή της.

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

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

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

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

Μια λύση αναφοράς είναι μια βασική μη αρνητική λύση.

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

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

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

Οι ακόλουθες περιπτώσεις είναι δυνατές κατά την επίλυση προβλημάτων στο ανώτατο όριο:

1. Αν όλοι οι συντελεστές της τελευταίας σειράς του πίνακα simplex DJ³ 0, στη συνέχεια βρέθηκε

λύση άριστος.

2 Εάν τουλάχιστον ένας συντελεστής Dj £ 0, αλλά για την αντίστοιχη μεταβλητή δεν υπάρχει ούτε μία θετική σχέση αξιολόγησης, τότε η λύση σταματάμε εργασίες, αφού F(X) ® ¥ ,δηλαδή η αντικειμενική συνάρτηση δεν περιορίζεται στην περιοχή των εφικτών λύσεων.

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

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

5. Εάν ένας τουλάχιστον συντελεστής Dk< 0 ,Οτι κ - ουστήλη αποδοχή για την παρουσιάστρια.

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

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

Συμπλήρωση του πίνακα Simplex 2 :

· γεμίστε τη βασική στήλη με μηδενικά και μονάδες

· ξαναγράψτε την κύρια γραμμή διαιρώντας την με το κύριο στοιχείο

· εάν η πρώτη γραμμή έχει μηδενικά, τότε οι αντίστοιχες στήλες μπορούν να μετακινηθούν στον επόμενο πίνακα simplex

· βρίσκουμε τους υπόλοιπους συντελεστές χρησιμοποιώντας τον κανόνα «ορθογώνιο».

Λαμβάνουμε μια νέα λύση αναφοράς, την οποία ελέγχουμε για βελτιστοποίηση:

Αν όλοι οι συντελεστές της τελευταίας σειράς DJ³ 0 και στη συνέχεια βρέθηκε η λύση ανώτατο όριο.

Αν όχι, τότε συμπληρώστε τον πίνακα simplex του 8ου βήματος και ούτω καθεξής.

Αν η αντικειμενική συνάρτηση F(X)απαιτεί εύρεση ελάχιστη τιμή, τότε το κριτήριο βελτιστοποίηση του προβλήματοςείναι μη θετικούς συντελεστέςρε j για όλα τα j = 1,2,...n.

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

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

θα επιτευχθεί για πολλές σειρές του πίνακα T (q) ταυτόχρονα. Στη συνέχεια, στην επόμενη επανάληψη, η στήλη b(β(q+1)) θα περιέχει μηδενικά στοιχεία.

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

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

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

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

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

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

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

Ο περιορισμός ανισότητας του αρχικού προβλήματος, που έχει τη μορφή « ", μπορεί να μετατραπεί σε περιορισμό εξίσωσης προσθέτοντας μια επιπλέον μη αρνητική μεταβλητή στην αριστερή της πλευρά και έναν περιορισμό ανισότητας της μορφής " ” – αφαιρώντας μια επιπλέον μη αρνητική μεταβλητή από την αριστερή της πλευρά.

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

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

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

Παράδειγμα. Γράψτε το ακόλουθο πρόβλημα γραμμικής βελτιστοποίησης σε κανονική μορφή: βρείτε το ελάχιστο της συνάρτησης
υπό περιορισμούς

Λύση

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

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

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

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

βρείτε το μέγιστο μιας συνάρτησης

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

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

1. Το πρόβλημα κανονικού γραμμικού προγραμματισμού σε συμβολισμό συντεταγμένων έχει τη μορφή

.

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

(1.7)

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

(1.8)

Οπου ,

.

3. Το πρόβλημα κανονικού γραμμικού προγραμματισμού στη σημειογραφία πίνακα έχει τη μορφή

(1.9)

, .

Εδώ ΕΝΑ– πίνακας συντελεστών του συστήματος εξισώσεων, Χ– μήτρα-στήλη μεταβλητών εργασιών, – μήτρα-στήλη των δεξιών πλευρών του συστήματος περιορισμών.

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

(1.10)

(1.11)

1.4. Μείωση ενός γενικού προβλήματος γραμμικού προγραμματισμού
σε κανονική μορφή

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

Θεώρημα 1.1.Σχετικά με την αντικατάσταση μιας ανισότητας με μια εξίσωση. Κάθε απόφαση ανισότητες

αντιστοιχεί σε μια μοναδική λύση της εξίσωσης

και ανισότητες

, (1.14)

και, αντιστρόφως, κάθε λύση της εξίσωσης (1.13) και της ανισότητας (1.14) αντιστοιχεί σε μια μοναδική λύση της ανίσωσης (1.12).

Απόδειξη.Αφήνω είναι η λύση της ανισότητας (1.12), τότε . Ας υποδηλώσουμε τη διαφορά μεταξύ της δεξιάς και της αριστερής πλευράς αυτής της ανισότητας με , δηλ.

Προφανώς . Ας αντικαταστήσουμε στην εξίσωση (1.13) αντί για τις μεταβλητές τις τιμές , παίρνουμε

Έτσι, ικανοποιεί την εξίσωση (1.13) και την ανισότητα (1.14). Αυτό σημαίνει ότι το πρώτο μέρος του θεωρήματος έχει αποδειχθεί.

Ας ικανοποιήσουμε τώρα την εξίσωση (1.13) και την ανισότητα (1.14), δηλαδή έχουμε

ΚΑΙ

Απορρίπτοντας τη μη αρνητική τιμή στην αριστερή πλευρά της τελευταίας ισότητας, λαμβάνουμε

δηλ. ικανοποιεί την ανισότητα (1.12). Το θεώρημα είναι αποδεδειγμένο.

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

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

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

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

Παράδειγμα 1.1.Φέρτε το πρόβλημα γραμμικού προγραμματισμού σε κανονική μορφή.

ρε

Λύση. Ας προχωρήσουμε στο πρόβλημα της εύρεσης του μέγιστου της αντικειμενικής συνάρτησης. Για να γίνει αυτό, αλλάζουμε τα πρόσημα των συντελεστών της αντικειμενικής συνάρτησης. Για να μετατρέψουμε τη δεύτερη και την τρίτη ανισότητα του συστήματος των περιορισμών σε εξισώσεις, εισάγουμε μη αρνητικές πρόσθετες μεταβλητές (στο μαθηματικό μοντέλο αυτή η πράξη σημειώνεται με το γράμμα D). Η μεταβλητή εισάγεται στην αριστερή πλευρά της δεύτερης ανισότητας με πρόσημο «+», αφού η ανισότητα έχει τη μορφή . Η μεταβλητή εισάγεται στην αριστερή πλευρά της τρίτης ανισότητας με πρόσημο «-», αφού η ανισότητα έχει τη μορφή . Οι μεταβλητές εισάγονται στην αντικειμενική συνάρτηση με συντελεστή ίσο με μηδέν. Η μεταβλητή στην οποία δεν επιβάλλεται η συνθήκη μη αρνητικότητας αντικαθίσταται από τη διαφορά , . Γράφουμε το πρόβλημα σε κανονική μορφή

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

Παράδειγμα 1.2.Φέρτε ένα πρόβλημα γραμμικού προγραμματισμού σε συμμετρική μορφή