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

1.

2. οδηγίες χρήσης χαλάκι. μοντέλα στην οικονομία.

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

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

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

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

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

Ο μαθηματικός προγραμματισμός περιλαμβάνει μια σειρά από ενότητες, οι κυριότερες από τις οποίες είναι οι ακόλουθες:

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

2. Μη γραμμικός προγραμματισμός.Αυτή η ενότητα περιλαμβάνει προβλήματα στα οποία η αντικειμενική συνάρτηση και (ή) περιορισμοί μπορεί να είναι μη γραμμικοί.

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

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

5. Στοχαστικός προγραμματισμός.Αυτή η ενότητα περιλαμβάνει εργασίες που περιέχουν τυχαίες μεταβλητέςστην αντικειμενική συνάρτηση ή περιορισμούς.

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

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

3. Η έννοια του μαθηματικού μοντέλου, είδη τάπητα. μοντέλα

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

Τα μοντέλα χωρίζονται σε:

1. γραμμικός, όπου όλες οι εξαρτήσεις περιγράφονται με γραμμικές σχέσεις,

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

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

4. ντετερμινιστική, τα οποία λαμβάνουν υπόψη τις μέσες τιμές όλων των παραμέτρων.

5. δυναμικόςμοντέλα στα οποία τα υπό μελέτη συστήματα εξετάζονται σε εξέλιξη για πολλές περιόδους,

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

7. βελτιστοποίησημοντέλα στα οποία η επιλογή γίνεται ανάλογα με εξτρεμισμόςκάποιο κριτήριο,

8. μη βελτιστοποίηση, στο οποίο δεν υπάρχει κριτήριο βελτιστοποίησης.

9. μακρομοντέλα(για όλο το νοικοκυριό)

10. μικρομοντέλα(επιμέρους δεσμοί ή διαδικασίες της οικονομίας).

Τύποι μαθηματικών μοντέλων: γραμμικό, μη γραμμικό, τετραγωνικό, ακέραιο, διακριτό, παραμετρικό, γραμμικό κλασματικό, δυναμικό, στοχαστικό

4. Γενική διατύπωση προβλημάτων μαθηματικού προγραμματισμού.

Εξετάστε τη γενική δήλωση του προβλήματος του μαθηματικού προγραμματισμού.

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

Z = f(x1, x2, …, xn)

στο δεδομένο εύρος μεταβολής αυτών των μεταβλητών

gi (x1, x2,…, xn)Ribi (i = 1, 2,…, m),

όπου Ri είναι ένα από τα σημάδια ≥, =, ≤.

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

Οικονομικό πλαίσιο:

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

Μαθηματική ρύθμιση:

Έστω j ο δείκτης του τύπου προϊόντος j = 1, n

i - δείκτης τύπου πόρου i = 1, m

και ij είναι το κόστος των πρώτων υλών Εγώ-ο τύπος για την παραγωγή μιας μονάδας παραγωγής ι-ο τύπος;

Αi είναι ένα δεδομένο όριο του διαθέσιμου όγκου πόρων του τύπου i-ου.

Pj - κέρδος από την πώληση μιας μονάδας παραγωγής του τύπου j.

xj είναι ο όγκος εξόδου του τύπου j.

z \u003d P1x 1 + P2x 2 + ... + Pnx n → Μέγιστη

a11x 1 + a12x 2 +…+ a1nx n ≤ A1

a21x 1 + a22x 2 +…+ a2nx n ≤ A2

…………………………….

a m1x1 + a m2x2 +…+ a m n x n ≤ Am

xj ≥ 0, j = 1, n

6. Το καθήκον της δίαιτας. Οικονομική διατύπωση και κατασκευή μαθηματικού μοντέλου του προβλήματος.

Οικονομικό σκηνικό

Ορισμένες φάρμες ταΐζουν ζώα. Χρησιμοποιείται για πάχυνση nείδη ζωοτροφών. Η περιεκτικότητα σε θρεπτικά συστατικά (ασβέστιο, φώσφορος κ.λπ.) είναι γνωστή ανά μονάδα τροφής κάθε είδους. Για τη σωστή διατροφή των ζώων, είναι απαραίτητο να καταναλώνονται θρεπτικά συστατικά όχι λιγότερα από τις καθορισμένες ποσότητες. Το μοναδιαίο κόστος κάθε τροφοδοσίας είναι γνωστό. Είναι απαραίτητο να καθοριστεί η διατροφή των ζώων, στην οποία το συνολικό κόστος πάχυνσης θα είναι ελάχιστο.

Μαθηματική ρύθμιση:

j είναι ο δείκτης του τύπου τροφοδοσίας, j = 1, n

i – δείκτης τύπου θρεπτικών συστατικών, i = 1, m

Αi είναι η απαιτούμενη ημερήσια πρόσληψη του i-ου τύπου θρεπτικών συστατικών.

Сj είναι το κόστος μιας μονάδας τροφοδοσίας του τύπου j.

Ας εισάγουμε άγνωστες μεταβλητές:

хj - ημερήσιος όγκος ζωοτροφής ι-η άποψηαυστηρός.

Ως προς την εισαγόμενη σημειογραφία δοθείσα εργασίαθα γραφτεί στη συνέχεια

a11x1 + a12x2 +…+ a1nxn ≥ A1

a21x1 + a22x2 +…+ a2nxn ≥ A2

…………………………….

am1x1 + am2x2 +…+ και mnxn ≥Am

xj ≥ 0, j = 1, n

7. Έργο μεταφοράς . Οικονομική διατύπωση και κατασκευή μαθηματικού μοντέλου του προβλήματος.

Οικονομικό σκηνικό :

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

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

Μαθηματική ρύθμιση :

Ας παρουσιάσουμε τους χαρακτηρισμούς των δεδομένων παραμέτρων:

j – δείκτης καταναλωτή, j = 1, n

i – δείκτης προμηθευτή, i = 1, m

Αi είναι ο όγκος των προϊόντων που διατίθενται από τον i-ο προμηθευτή.

Bj - ο όγκος της ζήτησης για τα προϊόντα του j-ου καταναλωτή.

Cij είναι το μοναδιαίο κόστος μεταφοράς μιας μονάδας προϊόντος από τον i-ο προμηθευτή στον j-ο καταναλωτή.

Ας εισάγουμε άγνωστες μεταβλητές:

хij είναι ο όγκος της μεταφοράς των προϊόντων από τον i-ο προμηθευτή στον j-ο καταναλωτή.

z = С11x11 + С12x12 +…+С1nx1n + С21x21 +…+ Сm(n -1)xm (n-1) + Сmnxmn → ελάχ

Περιορισμοί εργασιών.

I. Από κάθε προμηθευτή, μπορείτε να αποσύρετε προϊόντα όχι περισσότερο από τη διαθέσιμη ποσότητα:

x11 + x12 +…+ x1n ≤ A1

x21 + x22 +…+ x2n ≤ A2 (2)

…………………….

xm1 + xm2 +…+ xmn ≤ Am

II. Πρέπει να ικανοποιείται η ανάγκη κάθε καταναλωτή για προϊόντα

x11 + x21 +…+ xm1 ≥B1

x12 + x22 +…+ xm2 ≥B2

……………………. (3)

x1n + x2n +…+ xmn ≥Bn

III. Συνθήκη μη αρνητικότητας: xij ≥0, i = 1, m ; j = 1, n

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

, i = 1, m , j = 1, n

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

Οικονομικό σκηνικό :

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

Μαθηματική ρύθμιση .

Ας εισάγουμε τη σημείωση για τις δεδομένες παραμέτρους.

i – ευρετήριο έργων, i = 1, m

j είναι ο δείκτης των επιτελεστών, j = 1, n

Cij είναι το κόστος εκτέλεσης της i-ης εργασίας από τον j-ο εκτελεστή.

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

1 - εάν ο j-ος εκτελεστής έχει ανατεθεί στην i-η εργασία.

0 - διαφορετικά.

Όσον αφορά τον εισαγόμενο συμβολισμό, αυτό το πρόβλημα μπορεί να γραφτεί ως εξής:

z = С11x11 + С12x12 +…+С1nx1n + С21x21 …+ С(n-1)(n-1)x(n-1)(n-1) + Сnnxnn → ελάχ.

I ομάδα περιορισμών.

Μόνο ένας ερμηνευτής θα πρέπει να ανατεθεί σε κάθε έργο:

x11 + x12 +…+ x1n = 1

x21 + x22 +…+ x2n = 1

……………………..

xn1 + xn2 +…+ xnn = 1

II. ομάδα περιορισμού.

Κάθε εκτελεστής μπορεί να εκτελέσει μόνο μία εργασία:

x11 + x21 +…+ xn1 = 1

x12 + x22 +…+ xn2 = 1

……………………..

x1n + x2n +…+ xnn = 1

x ij = ( 0,1) i = 1, n ; j = 1, n

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

Οικονομικό σκηνικό .

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

Μαθηματική ρύθμιση .

Ας εισάγουμε τη σημειογραφία:

i είναι ο δείκτης των κενών,

Аi - ο απαιτούμενος αριθμός κενών του τύπου i-ου.

j - δείκτης επιλογών κοπής,

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

και ij είναι ο αριθμός των τεμαχίων του τύπου i-ου κατά την κοπή μιας μονάδας αρχικού υλικού σύμφωνα με την επιλογή j.

Ας εισαγάγουμε τον συμβολισμό άγνωστων μεταβλητών.

xj είναι η ποσότητα της πρώτης ύλης που κόβεται σύμφωνα με την επιλογή j.

Όσον αφορά τον εισαγόμενο συμβολισμό, αυτό το πρόβλημα μπορεί να γραφτεί ως εξής:

z \u003d С1x1 + С2x2 + ... + Сnxn → ελάχ

a11x1 + a12x2 +…+ a1nxn = A1

a21x1 + a22x2 +…+ a2nxn = A2

…………………………….

am1x1 + am2x2 +…+ amnxn =Am

xj ≥ 0, j = 1, n

Η χρήση μαθηματικών μοντέλων σάς επιτρέπει να εξοικονομήσετε έως και 20% των πρώτων υλών.

Το μαθηματικό μοντέλο κοπής χτίζεται σε δύο στάδια.

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

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

αριθμός επιλογής

Κενό i1

i2 κενό

κενό im

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

10. Γενική μορφή του μοντέλου προβλήματος LP και τα χαρακτηριστικά του

Η γενική μορφή του LLP είναι:

z \u003d С1x1 + ... + Сnxn μέγ. (ελάχ.)

a11 X1 + a12 X2 + … + a1n Xn R1 a1

a21 X1 + a22 X2 + … + a2n Xn R2 a2

………………………………………………….

am1 X1 + am2 X2 +…+ amnxn Rm am

xj ≥ 0, j = 1, k, k ≤ n

Σε γενική μορφή, κάθε σύμβολο R1 , R2 ,…, Rm σημαίνει ένα από τα πρόσημα: ≥, = ή ≤ .

Η γενική μορφή του μοντέλου προβλήματος LP έχει τα ακόλουθα χαρακτηριστικά.

1. Το σύστημα των περιορισμών παρουσιάζεται με τη μορφή εξισώσεων (άκαμπτες συνθήκες) και ανισώσεων (μη άκαμπτες συνθήκες).

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

3. Η αντικειμενική συνάρτηση τείνει είτε στο μέγιστο είτε στο ελάχιστο.

11. Τυπική μορφή του μοντέλου προβλήματος LP και τα χαρακτηριστικά του

Το τυπικό έντυπο έχει ως εξής.

Βρείτε το μέγιστο ή το ελάχιστο της αντικειμενικής συνάρτησης z:

z = С1x1 + … + Сnxn → max (min) (1)

Με την επιφύλαξη των ακόλουθων περιορισμών:

a11 X1 + a12 X2 + … + a1n Xn ≤ a1

a21 X1 + a22 X2 + ... + a2n Xn ≤ a2

…………………………………………..

am1 X1 + am2 X2 +… + amn Xn ≥ π.μ

xj ≥ 0, j = 1, k, k ≤ n

Τα χαρακτηριστικά της τυπικής μορφής του μοντέλου προβλημάτων LP είναι τα εξής:

1. το σύστημα των περιορισμών παρουσιάζεται με τη μορφή ανισοτήτων (μη άκαμπτες συνθήκες)

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

3. η αντικειμενική συνάρτηση τείνει είτε στο max είτε στο min

12. Κανονική μορφή του μοντέλου προβλήματος LP και τα χαρακτηριστικά του

Η κανονική μορφή είναι:

Βρείτε το ελάχιστο της αντικειμενικής συνάρτησης z:

z = С1x1 + … + Сnxn → ελάχ

Με την επιφύλαξη των ακόλουθων περιορισμών:

a11 X1 + a12 X2 + ... + a1n Xn = a1

a21 X1 + a22 X2 + ... + a2nxn = a2

…………………………

am1x1 + am2 X2 +… + amn Xn = π.μ

Xj ≥0, j = 1, n

Τα χαρακτηριστικά της κανονικής μορφής είναι τα εξής:

1. Το σύστημα περιορισμών παρουσιάζεται με τη μορφή εξισώσεων (αυστηροί όροι).

2. Οι συνθήκες μη αρνητικότητας ισχύουν για όλες τις μεταβλητές

3. Η αντικειμενική συνάρτηση τείνει να

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

13. Πιθανό, παραδεκτό, βέλτιστο βασικό σχέδιο εργασιών, ODZ της εργασίας LP

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

Ορισμός 2.Το σύνολο όλων των σχεδίων για ένα πρόβλημα γραμμικού προγραμματισμού ονομάζεται πεδίο των αποδεκτών τιμών μεταβλητών ( ODZ ).

Ορισμός 3.Το σχέδιο του προβλήματος γραμμικού προγραμματισμού, στο οποίο η αντικειμενική συνάρτηση παίρνει την ελάχιστη (ή μέγιστη) τιμή στο ODZ ονομάζεται άριστος .

14. Τύποι εγγραφών εργασιών LP: επέκταση, διπλωμένη, μήτρα, διάνυσμα.

Τα μοντέλα προβλημάτων LP μπορούν να γραφτούν με διάφορες μορφές.

1. Διευρυμένη προβολή της εγγραφής μοντέλου

Z = c1 X1 + c2 X2 + … + cn Xn → ελάχ

a11 X1 + a12 X2 + … + a1n Xn = a1,

a21 X1 + a22 X2 + … + a2n Xn = a2,

……………………………………………

a m1 X1 + am2 X2 + … + amn Xn = π.μ.

Xj ≥ 0, j = 1, n.

2. Συμπτυγμένη προβολή:

,

Xj ≥ 0, j = 1, n.

3. Μοντέλο του προβλήματος LP σε μορφή πίνακα:

X ≥ 0

Οπου

a11 a12 … a1n X1 a1

A= a21 a22 … a2n, X= X2, A0 = a2

… … … … … …

πμ1 πμ2 … πμ X3 π.μ

4. Μοντέλο του προβλήματος LP σε διανυσματική μορφή:

Οπου

X1 a11 a12 a1n a1

X2 , a21 , a22 , a2n , a2

… … … … …

Хn πμ1 πμ2 πμ2 π.μ

15. Μετάβαση από την τυπική και γενική μορφή των προβλημάτων LP στην κανονική.Θεώρημα σύνδεσης

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

1. Μεταβλητή μετατροπή. Εάν κάποια μεταβλητή Xk είναι μη θετική (Xk ≤ 0), τότε εισάγεται μια νέα μεταβλητή Xk ", έτσι ώστε Xk " = –Xk . Προφανώς, Xk " ≥ 0. Μετά από αυτό, σε κάθε περιορισμό και αντικειμενική συνάρτηση, η μεταβλητή Xk αντικαθίσταται από [ – Xk "].

Εάν κάποια μεταβλητή Xt μπορεί να πάρει οποιεσδήποτε τιμές, τότε αντικαθίσταται από τη διαφορά δύο μη αρνητικών μεταβλητών Xt' και Xt'', δηλ., υποτίθεται ότι xt = Xt' – Xt'', όπου Xt' 0 ≥ και Xt'' ≥ 0.

2. Μετασχηματισμός περιορισμών.Εάν κάποιος από τους περιορισμούς του μοντέλου έχει τη μορφή ανισότητας, τότε μετατρέπεται σε ισότητα προσθέτοντας (αν η ανισότητα είναι τύπου ≤) ή αφαιρώντας (αν η ανισότητα είναι τύπου ≥) από την αριστερή του πλευρά. Αυτές οι μεταβλητές ονομάζονται μεταβλητές ισορροπίας. Οι μεταβλητές του υπολοίπου περιλαμβάνονται στη συνάρτηση στόχου με μηδενικούς συντελεστές. Η μεταβλητή balance παίρνει την τιμή του δείκτη διαδοχικά μετά τις ήδη υπάρχουσες. Εάν, για παράδειγμα, το σύστημα περιορισμών έχει 5 μεταβλητές, τότε η πρώτη μεταβλητή ισορροπίας θα είναι X6 και η δεύτερη - X7, κ.λπ.

16. Μετάβαση από την κανονική μορφή του μοντέλου ZLP στο πρότυπο

Για να περάσει από την κανονική μορφή στην τυπική μορφή, καθένα από

εξισώσεις που πρέπει να αντικατασταθούν από ένα σύστημα ανισοτήτων:

Ένας άλλος τρόπος είναι να φέρετε το σύστημα των εξισώσεων σε μια ειδική μορφή και να εξαλείψετε περαιτέρω ορισμένες μεταβλητές.

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

α) πολλαπλασιασμός οποιασδήποτε εξίσωσης με σταθερά διαφορετική από το μηδέν.

β) προσθήκη σε οποιαδήποτε εξίσωση οποιασδήποτε άλλης εξίσωσης, πολλαπλασιαζόμενη με οποιαδήποτε σταθερά.

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

Γράφουμε το πρόβλημα σε τυπική μορφή.

17. Η έννοια ενός υπερεπίπεδου ενός ημιεπίπεδου, ενός υπερεπίπεδου υποστήριξης.

18. Γεωμετρική. ερμηνεία του συστήματος περιορισμών και της αντικειμενικής συνάρτησης στα προβλήματα LP

19. Κυρτό σύνολο: ακραία (γωνιακά) σημεία του συνόλου. Κυρτό πολύεδρο

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

κυρτό σύνολο

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

Θεώρημα 1. Οποιοδήποτε σημείο ενός τμήματος μπορεί να αναπαρασταθεί ως ένας κυρτός συνδυασμός των γωνιακών σημείων του.

x \u003d λ 1 A + λ 2 B

λ 1 , λ 2 ≥ 0 κυρτός συνδυασμός σημείων των γωνιακών σημείων Α και Β

λ1 + λ2 = 1

Θεώρημα 2. Οποιοδήποτε σημείο ενός κυρτού κλειστού συνόλου μπορεί να αναπαρασταθεί ως ένας κυρτός συνδυασμός των γωνιακών σημείων του.

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

1. Ελέγχεται εάν το αρχικό LPP είναι στην τυπική μορφή, εάν όχι, τότε η εργασία πρέπει να μετατραπεί στην τυπική φόρμα.

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

3. Η περιοχή των αποδεκτών τιμών των μεταβλητών για το ZLP είναι υπό κατασκευή.

4. Κατασκευάζεται ένας οδηγός διάνυσμα ντο .

5. Το αρχικό ισόπεδο σύρεται μέσω του ODZ (κάθετο στο διάνυσμα κατεύθυνσης).

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

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

8. Για να βρείτε τη βέλτιστη τιμή της αντικειμενικής συνάρτησης, είναι απαραίτητο να αντικαταστήσετε τις βέλτιστες τιμές των μεταβλητών στην αντικειμενική συνάρτηση και να υπολογίσετε την τιμή της.

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

Αλγόριθμος της γραφικής μεθόδου.

1. Με διαδοχική κατασκευή καθεμιάς από τις συνθήκες του συστήματος περιορισμών του προβλήματος πραγματοποιείται η κατασκευή του ΟΔΖ.

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

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

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

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

6. Για να βρείτε τη βέλτιστη τιμή της αντικειμενικής συνάρτησης, είναι απαραίτητο να αντικαταστήσετε τις συντεταγμένες του βέλτιστου σημείου στην αντικειμενική συνάρτηση και να υπολογίσετε την τιμή της.

23. Θεωρήματα για το εύρος των αποδεκτών τιμών του προβλήματος LP και για την αντικειμενική συνάρτηση

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

Θεώρημα 2. Για την αντικειμενική συνάρτηση ενός προβλήματος γραμμικού προγραμματισμού.

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

24. Το θεώρημα για το γωνιακό σημείο. Επαρκές και απαραίτητη προϋπόθεση

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

Συνέπειες από θεωρήματα.

Ορισμός. Σχέδιο = (х1,х2,…,хn), του οποίου οι θετικές συντεταγμένες αντιστοιχούν σε γραμμικά ανεξάρτητα διανύσματα, ονομάζεται βασικό σχέδιο PLP .

Συνέπεια 1. Το σχέδιο αναφοράς δεν έχει περισσότερες από m θετικές συντεταγμένες.

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

Συνέπεια 2. Κάθε γωνιακό σημείο του ODZ είναι ένα σχέδιο αναφοράς.

27. Αλγόριθμος της μεθόδου simplex.

Κατά την επίλυση προβλημάτων LP με τη μέθοδο simplex, είναι απαραίτητο να εκτελέσετε την ακόλουθη σειρά ενεργειών.

1. Ελέγχεται αν το πρόβλημα LP είναι σε κανονική μορφή. Εάν όχι, τότε είναι απαραίτητο να μετατρέψετε το αρχικό μοντέλο σε κανονική μορφή.

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

3. Κατασκευάζεται ο αρχικός πίνακας simplex.

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

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

6. Από τη βάση προκύπτει ένα διάνυσμα, το οποίο αντιστοιχεί στην αναλογία simplex που υπολογίζεται με τον τύπο 0< Ө ≤ . Данная строка называется разрешающей строкой.

7. Κατασκευάζεται νέος πίνακας simplex. Οι στήλες B και C B αλλάζουν αναλόγως. Ο υπόλοιπος πίνακας συμπληρώνεται από τον προηγούμενο χρησιμοποιώντας μετασχηματισμούς Gauss, με τη γραμμή δείκτη να θεωρείται ως σειρές m+1 και επίσης να μετασχηματίζεται χρησιμοποιώντας μετασχηματισμούς Gauss. Προχωράμε στην υλοποίηση της παραγράφου 4 αυτού του αλγορίθμου.

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

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

29. Πίνακες απλοί, το γέμισμα τους. Τύποι για τον υπολογισμό των συντελεστών σειρών ευρετηρίου.

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

Θεώρημα 1: Αν για κάποιο διάνυσμα Ā j στο σύστημα

X 1 + a 1 m +1 X m +1 + a 1 m +2 X m +2 + ... + a 1 n X n \u003d a 1

X 2 + a 2 m +1 X m +1 + a 2 m +2 X m +2 + ... + a 2 n X n \u003d a 2

…………………………………………………..

X m + a mn +1 X m +1 + a mn +2 X m +2 + ... + a mn X n = a m

Η σχέση Z j – c j > 0 εκπληρώνεται, τότε το σχέδιο X B0 δεν είναι βέλτιστο και είναι δυνατό να περάσει στο σχέδιο X B1 έτσι ώστε Z (X B1) ≤ Z (X B0).

Εδώ το Z j = (С, Ā j) είναι το βαθμωτό γινόμενο των διανυσμάτων.

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

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

c j είναι ο συντελεστής της αντικειμενικής συνάρτησης Z με μεταβλητή X j

Συνέπεια από θεωρήματα: Αν για όλα τα διανύσματα Ā 1 , Ā 2 , …, Ā n κάποιου σχεδίου αναφοράς Χ η σχέση Z j – c j< 0, то опорный план Х является оптимальным. Величины (Z j – c j) – называются оценками оптимальности соответствующих векторов.

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

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

31. Επιλογή ενός διανύσματος που εισέρχεται στη βάση και προέρχεται από τη βάση. Σχέση Simplex.

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

αποσύνθεση -

Resp. διάνυσμα, γάτα. θα είναι σχέδιο αναφοράς εάν οι συντεταγμένες του είναι μη αρνητικές και ο αριθμός των θετικών συντεταγμένων θα είναι ίσος με m.

Οι συντεταγμένες του διανύσματος X1 πρέπει να είναι μη αρνητικές, δηλ. .

Αν , τότε αυτή η συντεταγμένη θα είναι μη αρνητική.

Έστω το ελάχιστο στη σχέση (5) στο i =1, τότε αν πάρουμε

τότε η πρώτη συντεταγμένη του διανύσματος 1 Χθα γίνει μηδέν.

Η σχέση (6) ονομάζεται σχέση απλού. Έτσι, μετακινηθήκαμε από την αρχική γραμμή βάσης 0 Χ(βασικά διανύσματα A1, A2, ... Am) στο σχέδιο αναφοράς 1 Χ(βασικά διανύσματα А2,А3,…,Аm, Am+1).

32. επιτρεπτικό στοιχείο του πίνακα, η επιλογή του. Πλήρης κανόνας εξάλειψης Jordan για επανυπολογισμό πίνακα απλών.

33. Τετραπλευρικός κανόνας για επανυπολογισμό πίνακα απλών

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

Κατά την επίλυση προβλημάτων με τη μέθοδο simplex, είναι δυνατοί οι ακόλουθοι τύποι βέλτιστων λύσεων:

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

2. Εναλλακτικό βέλτιστο (σύνολο βέλτιστων λύσεων).

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

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

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

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

35. Πότε χρησιμοποιείται η μέθοδος της τεχνητής βάσης;

τεχνητός.

36. Κατασκευή του προβλήματος Μ στη μέθοδο της τεχνητής βάσης

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

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

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

Κατασκευάζεται ο αρχικός πίνακας simplex.

37. δημιουργία μιας γραμμής δείκτη στη μέθοδο της τεχνητής βάσης

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

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

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

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

39. Αλγόριθμος της μεθόδου dual simplex

Αλγόριθμος της μεθόδου dual simplex:

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

2. Επιλέξτε την κατευθυντήρια γραμμή κατά το μεγαλύτερο απόλυτο αρνητικό στοιχείο της στήλης των ελεύθερων μελών A0

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

4. Υπολογίστε ξανά τον πίνακα simplex σύμφωνα με τον κανόνα των πλήρους αποκλεισμών Jordan

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

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

41. Ανοιχτά και κλειστά μοντέλα μεταφοράς. Μετάβαση από ένα ανοιχτό μοντέλο μεταφοράς σε ένα κλειστό.

Τύποι εργασιών μεταφοράς.

Διαθέσιμος Μπρομηθευτές ομοιογενών προϊόντων με γνωστά αποθέματα προϊόντων και nκαταναλωτές των προϊόντων αυτών με δεδομένους όγκους αναγκών. Το μοναδιαίο κόστος μεταφοράς είναι επίσης γνωστό.

Εάν το άθροισμα των όγκων των αποθεμάτων προϊόντων είναι ίσο με τον όγκο των αναγκών όλων των καταναλωτών, τότε ένα τέτοιο πρόβλημα ονομάζεται κλειστό έργο μεταφοράς

(δηλαδή, αν ∑ Ai = ∑ Bj), αλλιώς καλείται το πρόβλημα μεταφοράς Άνοιξε. Για να λυθεί το πρόβλημα μεταφοράς, είναι απαραίτητο να είναι κλειστό.

Μια εργασία ανοιχτής μεταφοράς μπορεί να μετατραπεί σε κλειστή με τον ακόλουθο τρόπο.

Έστω ∑Ai > ∑Bj. Σε αυτήν την περίπτωση, είναι απαραίτητο να εισαχθεί ένας πλασματικός n + 1 καταναλωτής με όγκο αναγκών ∑Ai – ∑Bj. Το μοναδιαίο κόστος μεταφοράς από τους προμηθευτές σε έναν πλασματικό καταναλωτή θεωρείται ότι είναι 0, αφού στην πραγματικότητα τέτοια μεταφορά δεν θα είναι και μέρος των προϊόντων θα παραμείνει στους προμηθευτές.

Αν ∑Bj > ∑Ai . Σε αυτή την περίπτωση, είναι απαραίτητο να εισαχθεί ένας πλασματικός προμηθευτής m + 1 με όγκο αποθέματος ∑Bj – ∑Ai . Το μοναδιαίο κόστος μεταφοράς από έναν εικονικό προμηθευτή στους καταναλωτές θεωρείται ότι είναι ίσο με 0, αφού στην πραγματικότητα τέτοια μεταφορά δεν θα πραγματοποιηθεί και οι καταναλωτές δεν θα λάβουν ορισμένα από τα προϊόντα.

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

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

Η μέθοδος του μικρότερου στοιχείου στη μήτρα.

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

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

Περαιτέρω κατανομή γίνεται πρώτα όσο το δυνατόν περισσότερο σε κελιά με δύο σημάδια, στη συνέχεια - με ένα, και στη συνέχεια το πρόβλημα εξισορροπείται εκ νέου σε (m + n - 1) γεμίσματα. Οργανώνουμε γεμίσματα όταν περνάμε το τραπέζι από αριστερά προς τα δεξιά και από πάνω προς τα κάτω.

43. Ιδιότητες μεταφορικών εργασιών

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

Θεώρημα 1. Ένα πρόβλημα κλειστών μεταφορών έχει πάντα λύση.

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

Θεώρημα 3. το σύστημα περιορισμών ενός προβλήματος κλειστής μεταφοράς εξαρτάται πάντα γραμμικά.

Από αυτό το θεώρημα προκύπτει ότι η κατανομή ενός προβλήματος κλειστής μεταφοράς έχει πάντα m + n – 1 βασικές μεταβλητές και (m – 1) (n – 1) μεταβλητές ελεύθερου χρόνου.

44. Εκφυλισμένη κατανομή στα προβλήματα μεταφοράς, απαλλαγή από τον εκφυλισμό. Διαγραμμένος συνδυασμός.

Η κατανομή ονομάζεται εκφυλισμένη εάν ο αριθμός των κυττάρων είναι μικρότερος από m + n - 1.

45. Θεωρήματα βελτιστότητας για το πρόβλημα μεταφοράς.

Θεώρημα.Εάν για κάποια κατανομή του έργου μεταφοράς σας

πληρούνται οι προϋποθέσεις:

ΕΝΑ). ui+vj = cij για κατειλημμένα κελιά

σι) ui+vj ≤ сij, για ελεύθερα κελιά,

τότε αυτή η κατανομή είναι βέλτιστη.

Οι τιμές ui ονομάζονται δυναμικά γραμμής και οι τιμές vj ονομάζονται δυναμικά στήλης.

46. ​​Δυνατότητες και μέθοδοι υπολογισμού τους.

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

Ο αριθμός των εξισώσεων που βασίζονται σε αυτή τη συνθήκη είναι m + n – 1, και ο αριθμός των αγνώστων ui και vj είναι m + n. Οτι. ο αριθμός των μεταβλητών είναι μεγαλύτερος από τον αριθμό των εξισώσεων και όλες οι εξισώσεις είναι γραμμικά ανεξάρτητες. Η λύση ενός τέτοιου συστήματος γραμμικών εξισώσεων είναι απροσδιόριστη, επομένως σε ένα από τα δυναμικά πρέπει να αποδοθεί οποιαδήποτε τιμή. Στην πράξη προκύπτει ui = 0. σύστημα m + n – 1 εξισώσεων με m + n – 1 άγνωστες μεταβλητές. Αυτό το σύστημα μπορεί να λυθεί με οποιαδήποτε μέθοδο. Στην πράξη, για τον υπολογισμό των δυναμικών, λαμβάνονται υπόψη τα κατειλημμένα κελιά, για τα οποία είναι γνωστό ένα από τα δυναμικά τους και με βάση την προϋπόθεση α) του θεωρήματος υπολογίζονται οι τιμές των υπόλοιπων άγνωστων δυναμικών.

47. Υπολογισμός εκτιμήσεων της βέλτιστης κατανομής των εργασιών μεταφοράς και το κριτήριο της βέλτιστης.

Με βάση τη σχέση β) του θεωρήματος, μπορούμε να γράψουμε τον ακόλουθο τύπο για τον υπολογισμό των εκτιμήσεων: δ ij= ui + vj – сij. Για να μην συγχέονται οι εκτιμήσεις με τον όγκο κίνησης, αυτές (εκτιμήσεις) περικλείονται σε κύκλους.

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

48. ανακατανομή των προμηθειών στο μεταφορικό πρόβλημα

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

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

Για κάθε ελεύθερο κελί υπάρχει ένας κύκλος επανυπολογισμού και, επιπλέον, ο μοναδικός.

49. αλυσίδες αναδιανομής, οι τύποι τους.

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

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

Για να γίνει αυτό, το Q πρέπει να επιλεγεί ίσο με το μικρότερο αναγώγιμο από τα κελιά στα οποία αφαιρείται το Q. Στο παρακάτω σχ. Στα 7.1 και 7.2 θα δείξουμε παραδείγματα κύκλων και τον κανόνα υπολογισμού.

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

50. Η επιλογή του όγκου ανακατανομής.

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

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

β) ένα από τα κατειλημμένα κελιά πρέπει να γίνει ελεύθερο.

Για να πληρούνται αυτές οι προϋποθέσεις, είναι απαραίτητο να επιλέξετε τον όγκο των μεταφερόμενων προϊόντων ως εξής: θ=min (хij) -, όπου (хij) είναι ο όγκος μεταφοράς από τα κελιά του κύκλου επανυπολογισμού που σημειώνονται με το « -" σημάδι.

θ = min(20;30)=20

Το θ προστίθεται στις τιμές των κελιών που σημειώνονται με το σύμβολο «+». Το θ αφαιρείται από τις τιμές των κελιών που σημειώνονται με το σύμβολο "-". Η τιμή προσφοράς των υπόλοιπων κελιών αντικαθίσταται χωρίς αλλαγές. Ως αποτέλεσμα, παίρνουμε τον παρακάτω πίνακα.

53. Αλγόριθμος της μεθόδου των δυναμικών.

Αλγόριθμος:

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

2. Η συνθήκη εργασίας είναι γραμμένη με τη μορφή μεταφοράς.πίνακα

3. Κατασκευάζεται μια αρχική γραμμή βάσης

4. Προσδιορίζονται οι δυνατότητες προμηθειών και καταναλωτών

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

6. Φορτώστε ένα προοπτικό κελί. Ετοιμάστε ένα νέο σχέδιο βάσης με τη μορφή πίνακα μεταφοράς. Πηγαίνετε στο σημείο 4.

54. Λογιστική για το κόστος παραγωγής και μεταφοράς των προϊόντων. Έργο μεταφοράς με απαγορεύσεις εφοδιασμού.

Κατά την επίλυση ορισμένων προβλημάτων, είναι απαραίτητο να λαμβάνεται υπόψη το κόστος όχι μόνο για τη μεταφορά των εμπορευμάτων, αλλά και για την παραγωγή των μεταφερόμενων προϊόντων. Για να γίνει αυτό, στο matrix transp. καθήκοντα

Όπου Cij' είναι το μειωμένο κόστος παραγωγής μιας μονάδας παραγωγής.

Cij “- το κόστος μεταφοράς μιας μονάδας παραγωγής.

Καθήκοντα με απαγορεύσεις προμήθειας.

Σε ορισμένες περιπτώσεις, δεν είναι δυνατή η μεταφορά προϊόντων σε οποιαδήποτε διαδρομή.

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

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

λαμβάνοντας υπόψη τους περιορισμούς στη διεκπεραίωση των δρομολογίων.

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

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

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

56. Πιθανά συμπεράσματα με οικονομική. ερμηνεία της βέλτιστης κατανομής για προβλήματα ανοιχτής μεταφοράς.

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

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

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

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

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

Ας υπάρξει μια εργασία βελτιστοποίησης του σχεδίου παραγωγής. Μοιάζει με αυτό:

Αρχική εργασία:

a 11 x 1 + a 12 x 2 +…+ a 1p x p ≤v 1 | 1

a 21 x 1 + a 22 x 2 +…+ a 2p x p ≤v 2 | στις 2

……………….. |.. (1)

ΕΝΑ Τ 1 x 1 +a Τ 2 x 2 + ... + α Τ n x n ≤v 1 | στο Τ

x j ≥0, j = 1,n(2)

z = c 1 x 1 +c 2 x 2 +…+c n x n ->max(3)

X \u003d (x 1, x 2, ..., x n)

a ij - ο αριθμός των πρώτων υλών του τύπου i, που δαπανήθηκαν για την παραγωγή του j-ου τύπου προϊόντος

Διπλό πρόβλημα

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

i - η τιμή του i-ου τύπου πρώτης ύλης που διατίθεται στην επιχείρηση.

a 11 y 1 + a 21 y 2 + ... + a Τ 1 ε Τ≥s 1

a 12 x 1 + a 22 y 2 + ... + a Τ 2 x n ≥s 2

……………….. (1’)

ΕΝΑ 1π y 1 +a 2π y 2 +…+ α tpστο Τ≥s Π

i ≥0, j = 1,m(2')

F = b 1 y 1 +b 2 y 2 +…+b m y m ->min(3’)

58. Αντιστοιχία μεταξύ των δομικών στοιχείων των άμεσων και διπλών προβλημάτων

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

διπλή εργασία σύμφωνα με τους ακόλουθους κανόνες:

1. Σε όλους τους περιορισμούς του αρχικού προβλήματος, οι ελεύθεροι όροι πρέπει

να είναι στα δεξιά και οι όροι με άγνωστα στα αριστερά.

2. Οι περιορισμοί-ανισότητες του αρχικού προβλήματος πρέπει να έχουν πρόσημα,

κατευθύνεται προς μία κατεύθυνση.

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

4. Κάθε περιορισμός του αρχικού προβλήματος αντιστοιχεί σε μια μεταβλητή in

διπλή εργασία. Αν μια μεταβλητή αντιστοιχεί σε ανισότητα, είναι μη αρνητική, αν αντιστοιχεί σε ισότητα, τότε η μεταβλητή είναι χωρίς περιορισμούς στο πρόσημο («αυθαίρετο»).

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

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

6. Οι ελεύθεροι όροι του αρχικού προβλήματος είναι οι συντελεστές στο

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

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

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

59. Κατασκευή διπλών προβλημάτων στα αρχικά προβλήματα γραμμένα στην τυπική, κανονική και γενική μορφή του μοντέλου (κατασκευή συμμετρικών και ασύμμετρων διπλών προβλημάτων)

Τυπική φόρμα (πρωτότυπο)

Σ a ij x j ≤ b i , i=1,n(1)

x j ≥0, j=1,n(2)

z = Σ c j x j ->max(3)

Διπλό πρότυπο

Σ a ij y i ≤ c j , j=1,n(1)

yi ≥0, j=1,m(2)

F = Σ b i y i ->min(3)

Το αρχικό πρόβλημα σε κανονική μορφή:

Σ a ij x j = b i , i=1,m(1)

x j ≥0, j=1,n(2)

z = Σ c j x j -> min(3)

Διπλή κανονική

Σ a ij y i ≤ c j , j=1,n(1)

y i - οποιοδήποτε (2)

F = Σ b i y i -> max(3)

Ας δώσουμε μια οικονομική ερμηνεία ενός ζεύγους διπλών προβλημάτων. Εξετάστε το πρόβλημα της ορθολογικής χρήσης των πόρων. Αφήστε την επιχείρηση να έχει πόρους b1,b2,…bm που μπορούν να χρησιμοποιηθούν για την παραγωγή n-τύπων προϊόντων. Ας είναι επίσης γνωστό το κόστος μιας μονάδας του j-τύπου προϊόντος cj (j=1,n) και το ποσοστό κατανάλωσης του i-ου πόρου (i=1,m) για την παραγωγή μιας μονάδας ι-η παραγωγή– aij Απαιτείται ο προσδιορισμός του όγκου παραγωγής κάθε τύπου xj (j=1,n), μεγιστοποιώντας το συνολικό κόστος

f= c1x1+…+cnxn (1)

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

a11x1+…+a1nxn<=b1 }

…………………….. } (2)

am1x1+…+amnxn<=bm }

Όλα τα γνωστά με την οικονομική τους έννοια είναι μη αρνητικά:

Xj>=0 (j=1,n). (3)

Σημειώστε ότι αυτό το πρόβλημα δημιουργεί ένα συμμετρικό διπλό πρόβλημα.

Ασύμμετρα διπλά προβλήματα.

Ας πάρουμε το ZLP στο μέγιστο στην κανονική μορφή:

Μέγιστο Z=(n;j=1)Σcj*xj

(n;j=1)Σaij*xj=bi (i=1,m)

Xj>=0 (j=1,n).

60. Κύριο και δεύτερο θεώρημα δυαδικότητας (διατυπώστε τα θεωρήματα και εξηγήστε)

Το πρώτο θεώρημα δυαδικότητας.

Θεώρημα: αν ένα από τα διπλά προβλήματα έχει βέλτιστο σχέδιο, τότε το άλλο είναι επιλύσιμο, δηλ. έχει σχέδιο επιλογής. Σε αυτήν την περίπτωση, οι ακραίες τιμές των αντικειμενικών συναρτήσεων συμπίπτουν (j=από 1 έως n) Σcjxj*= (i=από 1 έως m)Σbiyi* εάν είναι στο πρωτότυπο. πρόβλημα η αντικειμενική συνάρτηση είναι απεριόριστη στο σύνολο των σχεδίων, τότε στο διπλό πρόβλημα το σύστημα των περιορισμών είναι ασυνεπές.

Δεύτερο θεώρημα δυαδικότητας και η οικονομική του ερμηνεία.

Ωστε να έγκυρες λύσειςζεύγη διπλών προβλημάτων ήταν βέλτιστα, είναι απαραίτητο και επαρκές για την εκπλήρωση της συνθήκης: xj*(∑aij yi*-cj)=0, j από 1 έως n, yi*(∑aij xj*-bi)=0, I από 1 έως m. Αυτές είναι συνθήκες συμπληρωματικής χαλαρότητας. Από αυτά προκύπτει: εάν οποιοσδήποτε περιορισμός του διπλού προβλήματος μετατραπεί από το βέλτιστο σχέδιο σε αυστηρή ισότητα, τότε η αντίστοιχη συνιστώσα του οφ. Το σχέδιο του διπλού προβλήματος θα πρέπει να είναι ίσο με μηδέν. σχέδιο είναι ίσο με μηδέν, τότε ο αντίστοιχος περιορισμός του διπλού προβλήματος μετατρέπεται από το opt.plan σε αυστηρή ισότητα xj*>0, επομένως (i= από 1 έως m)Σaij yi*=cj opt.plan, τότε αν κόστος>τιμές, όγκος παραγωγής=0 Σaij yi* >cj άρα xj*=0

yi*>0 επομένως (j=από 1 έως n) Σaij xj*=bi (κούρσες πόρων = απόθεμα πόρων).

(j=1 έως n) Σaij xj*

Το νόημα του θεωρήματος έχει ως εξής:

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

Εάν το κόστος υπερβαίνει την τιμή, τότε το prod-yu δεν πρέπει να παράγεται.

Εάν η κατανάλωση πόρων = απόθεμα, τότε η εκτίμηση κόστους αυτού του πόρου είναι θετική. Ένας τέτοιος πόρος ονομάζεται σπάνιος. Το πιο deficient.res-s έχει την υψηλότερη βαθμολογία.

Εάν ο πόρος δεν δαπανηθεί πλήρως, τότε η εκτίμηση του κόστους του = 0.

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

Πληροφορίες από τις στήλες του αντίστροφου πίνακα γραμμικών μετασχηματισμών που οδήγησαν στο βέλτιστο αποτέλεσμα. Οι στήλες του πίνακα D-1 παρέχουν πολύ χρήσιμες πληροφορίες.

Στήλη A3: η "σκιώδης" τιμή του πόρου S2 είναι y01=0, η στήλη παραμένει

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

Στήλη Α4: η «σκιώδης» τιμή του πόρου S2 είναι ίση με y02=1, ο πόρος θα χρησιμοποιηθεί πλήρως και η πιθανή αύξησή του θα οδηγήσει σε αύξηση της αντικειμενικής συνάρτησης (δηλ. εισοδήματος). Και επειδή y02=1, τότε η αύξηση του πόρου S2 κατά 1 c.u. θα δώσει μια πρόσθεση ως προς το εισόδημα κατά.Z = y02· .w2 = = 1,1 = 1 (χιλιάδες UAH) (εδώ.w2 είναι η αύξηση του πόρου S2 και .Z είναι η αντίστοιχη αύξηση του εισοδήματος). Με μια τέτοια αύξηση του πόρου S2, το μέγιστο εισόδημα θα είναι ήδη Zmax=58 χιλιάδες UAH. + 1 χιλιάδες UAH = 59 χιλιάδες UAH. Στο σχ. Το 6.2 απεικονίζει αυτήν την κατάσταση, σχολιασμός της οποίας θα δοθεί παρακάτω. Από τη στήλη Α4 προκύπτει επίσης ότι με αύξηση του πόρου S2 κατά 1 c.u. για το νέο βέλτιστο σημείο, η παραγωγή των αγαθών T1 θα μειωθεί κατά ½ τόνο (στη τομή της σειράς της βασικής μεταβλητής x1 και της στήλης A4 είναι "-1/2") και η παραγωγή των αγαθών T2 θα αυξηθεί κατά 3 /2 τόνους (γιατί στη σειρά με τη βασική μεταβλητή x2 στη στήλη Α4 έχουμε "3/2". Ό,τι έχει ειπωθεί για τη στήλη Α4 θα σχολιαστεί παρακάτω χρησιμοποιώντας γραφικές κατασκευές (Εικ. 6.2). Στήλη Α5: η "σκιά Η τιμή του πόρου S3 είναι ίση με y03=2. Αυτό σημαίνει ότι μια αύξηση του πόρου S3 κατά 1 c.u. θα φέρει μια προσθήκη στο Z σε.Z = y03 · .v3 = 2,1 =2(χιλιάδες hryvnia) και θα είναι Zmax=58 χιλιάδες hryvnia. + 2 χιλιάδες UAH = 60 χιλιάδες UAH. Παράλληλα, όπως προκύπτει από τη στήλη Α5 του Πίνακα. 3, η παραγωγή Τ1 θα αυξηθεί κατά ½ τόνο και η Τ2 θα μειωθεί κατά ½ τόνο. Το απόθεμα πρώτων υλών S1 (βλ. γραμμή 1) θα αυξηθεί κατά 3/2 c.u.

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

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

Για να το ορίσετε, χρειάζεστε:

1. γράψτε τη συναρτησιακή εξίσωση για την τελευταία κατάσταση της διαδικασίας (αντιστοιχεί σε l \u003d n-1)

fn-1(Sl-1)=βέλτιστη(Rn(Sn-1,Un)+f0(Sn))

2. βρείτε το Rn(Sn-1,Un) από ένα διακριτό σύνολο τιμών του για ορισμένα σταθερά Sn-1 και Un από τις αντίστοιχες αποδεκτές περιοχές (αφού f0(Sn)=0, μετά f1(Sn-1)= βέλτιστη(Rn(Sn-1,Un)

Ως αποτέλεσμα, μετά το πρώτο βήμα, η λύση Un και η αντίστοιχη τιμή της συνάρτησης f1(Sn-1) είναι γνωστές

3. Μειώστε την τιμή του l κατά ένα και σημειώστε την αντίστοιχη συναρτησιακή εξίσωση. Για l=n-k (k= 2,n) μοιάζει

fk(Sn-k)=βέλτιστη(Rn-k+1(Sn-k,Un-k+1)+fk-1(Sn-k+1)) (2)

4. Βρείτε μια υπό όρους βέλτιστη λύση με βάση την έκφραση (2)

5. ελέγξτε με ποια τιμή ισούται η τιμή του l. Αν l=0, ολοκληρώνεται ο υπολογισμός των βέλτιστων υπό συνθήκη λύσεων και βρίσκεται η βέλτιστη λύση του προβλήματος για την πρώτη κατάσταση της διαδικασίας. Εάν το l δεν ισούται με 0, μεταβείτε στο βήμα 3.

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

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

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

Μαθηματικά, γράφεται ως έκφραση της μορφής:

fn-1(Sl)=βέλτιστη(Rl+1(Sl,Ul+1)+fn-(l+1)(Sl+1)) (1)

(l=0,n-1) Βέλτιστο στην έκφραση σημαίνει το μέγιστο ή το ελάχιστο ανάλογα με την κατάσταση του προβλήματος.

63. Απαιτήσεις για προβλήματα που επιλύονται με τη μέθοδο DP

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

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

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

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

64.Οικονομική διατύπωση και κατασκευή μαθηματικού μοντέλου του προβλήματος που λύθηκε με τη μέθοδο DP (στο παράδειγμα του προβλήματος της κατανομής των επενδύσεων κεφαλαίου). Σχέση υποτροπής Bellman.

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

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

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

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

Όλοι οι υπολογισμοί που καθιστούν δυνατή την εύρεση της βέλτιστης τιμής του αποτελέσματος που επιτυγχάνεται σε n βήματα, fn(S0), πραγματοποιούνται σύμφωνα με τον τύπο (1), ο οποίος ονομάζεται βασική συναρτησιακή εξίσωση Bellman ή σχέση επανάληψης. Κατά τον υπολογισμό της επόμενης τιμής της συνάρτησης fn-1, χρησιμοποιείται η τιμή της συνάρτησης fn-(l+1) που λήφθηκε στο προηγούμενο βήμα και η άμεση τιμή της επίδρασης Rl+1(Sl,Ul+1), επιτυγχάνεται ως αποτέλεσμα της επιλογής της λύσης Ul+1 για συστήματα Sl δεδομένης κατάστασης. Η διαδικασία υπολογισμού της τιμής της συνάρτησης fn-1(l=0,n-1)

Εκτελείται υπό τη φυσική αρχική συνθήκη f0(Sn)=0, που σημαίνει ότι εκτός της τελικής κατάστασης του συστήματος, το αποτέλεσμα είναι μηδέν.

65. Το πρόβλημα της κατανομής των επενδύσεων κεφαλαίου (παράδειγμα).

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

Ας ξεκινήσουμε με τη βέλτιστη κατανομή των κατανεμημένων επενδύσεων κεφαλαίου στο ποσό του Κ μεταξύ δύο επιχειρήσεων. Τα τμήματα προγραμματισμού των επιχειρήσεων, με βάση τους υπολογισμούς τους, σχημάτισαν τις συναρτήσεις εισοδήματος q(x) για την επιχείρηση P1 και h(x) για την επιχείρηση P2. Αυτές οι συναρτήσεις σημαίνουν ότι εάν η πρώτη ή η δεύτερη επιχείρηση λάβει μια επένδυση ύψους x, τότε η πρώτη επιχείρηση

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

Έτσι, έστω ότι η εταιρεία P1 διέθεσε επενδύσεις κεφαλαίου στο ποσό x, τότε στην εταιρεία P2 κατανέμεται το ποσό K - x. Σε αυτή την περίπτωση, το εισόδημα q(x) θα ληφθεί από την πρώτη επιχείρηση και το h(K - x) από τη δεύτερη. Εάν οι επενδύσεις Κ κατανεμήθηκαν για μία περίοδο προγραμματισμού, τότε τα συνολικά έσοδα από τις δύο επιχειρήσεις θα είναι R(K, x) = q(x) + h(K - x). Προφανώς, το x και, κατά συνέπεια, το K - x πρέπει να επιλεγούν έτσι ώστε το R(K, x) να λάβει τη μέγιστη τιμή του, την οποία συμβολίζουμε με F(K):

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

συναρτησιακή εξίσωση Bellman. ΠΕΡΙΠΛΟΚΟΥΜΕ το έργο μας κατανέμοντας τις επενδύσεις κεφαλαίου σε δύο περιόδους προγραμματισμού (δύο στάδια) . Ας αποφασιστεί αρχικά να κατανεμηθεί το ποσό x στην πρώτη επιχείρηση P1 και x στη δεύτερη επιχείρηση P1. Γενικά, το εισόδημα θα ήταν ίσο με R(K, x) = q(x) +

h(K - x). Αν λάβουμε υπόψη ότι οι επενδύσεις κατανέμονται σε 2 περιόδους (2 στάδια), τότε στην πρώτη επιχείρηση το υπόλοιπο των επενδύσεων θα είναι x, όπου , και στη δεύτερη - .(K - x), όπου αντίστοιχα, το εισόδημα για την η δεύτερη περίοδος θα είναι q( .x) - σύμφωνα με την πρώτη διευκόλυνση και h[.(K - x)] - σύμφωνα με τη δεύτερη. Η βελτιστοποίηση δυναμικού προγραμματισμού, κατά κανόνα, ξεκινά από το τελικό στάδιο. Επομένως, ξεκινάμε από το δεύτερο στάδιο, δηλώνοντας F1 το μέγιστο δυνατό εισόδημα από δύο επιχειρήσεις στο δεύτερο

στάδιο. Παίρνω

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

Ομοίως, για n στάδια, λαμβάνουμε

όπου Fn-1 είναι η αντικειμενική συνάρτηση που δίνει το καλύτερο αποτέλεσμα για τα τελευταία (n - 1) στάδια. Η προκύπτουσα συναρτησιακή εξίσωση Bellman είναι επαναλαμβανόμενη, δηλ. συσχετίζει την τιμή Fn με την τιμή Fn-1.

Γενικότερα, η εξίσωση Bellman έχει τη μορφή

όπου , Fn-1 - μέγιστο εισόδημα για (n - 1) τελευταία στάδια, Fn -

μέγιστο εισόδημα για όλα τα n στάδια.

66. Η έννοια της επίλυσης προβλημάτων μη γραμμικού προγραμματισμού

Αφήστε το πρόβλημα του μη γραμμικού προγραμματισμού να τεθεί στην ακόλουθη γενική μορφή: βρείτε τέτοιες τιμές των μεταβλητών x1, x2, ..., xn που πληρούν τις προϋποθέσεις:

και να φέρει το απαιτούμενο άκρο (μέγιστο ή ελάχιστο) της αντικειμενικής συνάρτησης

f = f(x1, x2,…, xn), (13.2)

όπου f(х1, …, хn) και qi(х1, …, хn) (m , 1 i =) είναι πραγματικές μη γραμμικές,

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

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

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

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

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

θεωρείται πρόβλημα και η επαναληπτική διαδικασία των υπολογισμών ξεκινά από το σημείο

Περαιτέρω, πρώτα γίνεται μια μετάβαση κατά μήκος της κλίσης της αντικειμενικής συνάρτησης και μετά μια επιστροφή στην περιοχή. κατά μήκος της κλίσης μέχρι το διαταραγμένο όριο της περιοχής O2 O3. Το 13.3 φαίνεται έτσι ώστε το Ai με περιττούς δείκτες να ανήκουν στην περιοχή., και τα σημεία Ai με ζυγούς δείκτες όχι. Καθώς πλησιάζουμε στο βέλτιστο σημείο Q, οι κατευθύνσεις των κλίσεων εργασίας συγκλίνουν. Επομένως, το ιδανικό κριτήριο για τη διακοπή της διαδικασίας θα είναι η συγγραμμικότητα της κλίσης στόχου και της διακεκομμένης κλίσης ορίου.

67. Η έννοια του παραμετρικού και ακέραιου προγραμματισμού .

Δήλωση και μαθηματικό μοντέλο ZCLP.

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

f=(n,j=1)∑CjXi μέγ

(n,j=1)∑AijXj=bi, i=1,m

xi-ακέραιος,j=1,n

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

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

2.Συνδυαστική

3. Κατά προσέγγιση μέθοδοι..

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

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

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

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

Γενικά, το μαθηματικό μοντέλο ενός προβλήματος γραμμικού προγραμματισμού (LP) γράφεται ως

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

Οπου x j- άγνωστο aij, β i, cjδίνονται σταθερές.

Όλες ή μερικές εξισώσεις του συστήματος περιορισμών μπορούν να γραφτούν ως ανισότητες.

Το μαθηματικό μοντέλο σε συντομότερη σημειογραφία έχει τη μορφή

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

Ορισμός.Μια εφικτή λύση (σχέδιο) ενός προβλήματος γραμμικού προγραμματισμού είναι ένα διάνυσμα = ( Χ 1 , Χ 2 ,..., x p),ικανοποιώντας το σύστημα των περιορισμών.

Το σύνολο των αποδεκτών διαλυμάτων σχηματίζει την περιοχή των αποδεκτών διαλυμάτων (ODD).

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

Βασική αποδεκτή λύση (Χ 1 , Χ 2 ,...,Χ r , 0, …, 0) είναι μια λύση αναφοράς, όπου r-η κατάταξη του συστήματος περιορισμών.

Το μαθηματικό μοντέλο του προβλήματος LP μπορεί να είναι κανονικό και μη κανονικό.

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

Γραφική Μέθοδος Επίλυσης Προβλημάτων Γραμμικού Προγραμματισμού

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

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

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

Οπου μι 1 και μι 2 - μοναδιαία διανύσματα κατά μήκος των αξόνων ΒΟΔΙ 1 και ΒΟΔΙ 2 αντίστοιχα? έτσι = (∂L/∂x 1 , ∂L/∂х 2 ). Οι διανυσματικές συντεταγμένες είναι οι αντικειμενικοί συντελεστές συνάρτησης ΜΕΓΑΛΟ().Η κατασκευή της γραμμής στάθμης θα εξεταστεί λεπτομερώς κατά την επίλυση πρακτικών προβλημάτων.

Αλγόριθμος επίλυσης προβλημάτων

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

2. Χτίζοντας ένα διάνυσμα .

3. Σχεδιάστε μια γραμμή επιπέδου μεγάλο 0 , η οποία είναι κάθετη .

4. Μετακινούμε τη γραμμή επιπέδου προς την κατεύθυνση του διανύσματος για εργασίες στο μέγιστο και στην αντίθετη κατεύθυνση , για ελάχιστες εργασίες.

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

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

Όπου 0 ≤ t≤ 1, 1 και 2 - βέλτιστες λύσεις στα γωνιακά σημεία του ODS.

Ένα πρόβλημα LP μπορεί να είναι άλυτο όταν οι περιορισμοί που το καθορίζουν αποδειχθούν αντιφατικοί.

5. Βρίσκουμε τις συντεταγμένες του ακραίου σημείου και την τιμή της αντικειμενικής συνάρτησης σε αυτό.

Παράδειγμα 3Επιλέγοντας την καλύτερη επιλογή έκδοσης προϊόντος

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

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

Επιπλέον, διαπιστώθηκε ότι η ζήτηση για παγωτό σοκολάτα δεν ξεπερνά τα 350 κιλά την ημέρα. Λιανική τιμή 1 κιλού κρεμώδους παγωτού είναι 16 ρούβλια, σοκολάτα - 14 ρούβλια.

Πόσο από κάθε είδος παγωτού πρέπει να παράγει η επιχείρηση για να μεγιστοποιήσει τα έσοδα από τις πωλήσεις της;

Λύση.Δείχνω: Χ 1 - ημερήσιος όγκος παραγωγής κρεμώδους παγωτού, kg. Χ 2 - ημερήσια παραγωγή παγωτού σοκολάτας, kg.

Ας φτιάξουμε ένα μαθηματικό μοντέλο του προβλήματος.

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

Θέστε όρια στο γάλα για παγωτό. Η κατανάλωσή του για κρεμώδες παγωτό είναι 0,8 κιλά, για παγωτό σοκολάτα - 0,5 κιλά. Απόθεμα γάλακτος 400 κιλά. Επομένως, η πρώτη ανισότητα θα μοιάζει με:

0,8x 1 + 0,5x 2 ≤400 - η πρώτη ανισότητα είναι περιορισμός. Οι υπόλοιπες ανισότητες κατασκευάζονται με παρόμοιο τρόπο.

Το αποτέλεσμα είναι ένα σύστημα ανισοτήτων. ποια είναι η περιοχή λύσης κάθε ανισότητας. Αυτό μπορεί να γίνει αντικαθιστώντας τις συντεταγμένες του σημείου Ο(0:0) σε καθεμία από τις ανισότητες. Ως αποτέλεσμα, παίρνουμε:

Εικόνα ΟΑΒΔΕΦ-τομέα των αποδεκτών λύσεων. Κατασκευάζουμε το διάνυσμα (16; 14). γραμμή επιπέδου μεγάλοΤο 0 δίνεται από την εξίσωση 16x 1 +14x 2 =Const. Επιλέγουμε οποιονδήποτε αριθμό, για παράδειγμα τον αριθμό 0, μετά 16x 1 +14x 2 =0. Στο σχήμα, για τη γραμμή L 0 επιλέγεται κάποιος θετικός αριθμός, όχι ίσος με μηδέν. Όλες οι γραμμές επιπέδου είναι παράλληλες μεταξύ τους. Το κανονικό διάνυσμα της γραμμής επιπέδου.

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

Λύνοντας το σύστημα, παίρνουμε τις συντεταγμένες του σημείου ρε(312.5; 300), στην οποία θα υπάρχει μια βέλτιστη λύση, δηλ.

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

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

9.Απλή μέθοδος. Χαρακτηριστικά και αλγόριθμος της μεθόδου, η δυνατότητα εφαρμογής της.

Για να λυθεί το πρόβλημα με τη μέθοδο simplex, είναι απαραίτητο:

1. Υποδείξτε μια μέθοδο για την εύρεση της βέλτιστης λύσης αναφοράς

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

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

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

1. Φέρτε το πρόβλημα στην κανονική μορφή

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

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

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

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

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

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

1. Εύρεση της αρχικής λύσης αναφοράς.

2. Έλεγχος αυτής της λύσης για βελτιστοποίηση.

3. Μετάβαση από τη μια βασική λύση στην άλλη.

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

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

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

1. Επιλέξτε μεταβλητές εργασίας.

2. Να καταρτίσει ένα σύστημα περιορισμών.

3. ορίστε την αντικειμενική συνάρτηση.

Μεταβλητές εργασιώνλέγονται οι ποσότητες x 1 , x 2 ,…, x n, που χαρακτηρίζουν πλήρως την οικονομική διαδικασία. Συνήθως γράφονται ως διάνυσμα X \u003d (x 1, x 2, ..., x n).

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

Η αντικειμενική συνάρτηση καλείταισυνάρτηση F(X) = f(x 1 , x 2 ,…, x n) των μεταβλητών εργασίας, η οποία χαρακτηρίζει την ποιότητα της εργασίας και το άκρο της οποίας απαιτείται να βρεθεί.

Γενικό Πρόβλημα Μαθηματικού Προγραμματισμούδιατυπώνεται ως εξής: βρείτε τις μεταβλητές εργασίας x 1 , x 2 ,…, x n που παρέχουν το άκρο της αντικειμενικής συνάρτησης

F (X) \u003d f (x 1, x 2, ..., x n) ® max (min) (2)

και ικανοποιούν το σύστημα των περιορισμών (1).

Εάν η αντικειμενική συνάρτηση (2) και το σύστημα περιορισμών (1) είναι γραμμικά, τότε το πρόβλημα του μαθηματικού προγραμματισμού ονομάζεται Πρόβλημα γραμμικού προγραμματισμού (LPP).

Καλείται το διάνυσμα X (ένα σύνολο μεταβλητών εργασιών). αποδεκτή λύση, ή το σχέδιο PLP, εάν πληροί το σύστημα περιορισμών (1). Ένα εφικτό σχέδιο Χ που παρέχει ένα άκρο της αντικειμενικής συνάρτησης ονομάζεται βέλτιστη λύση ZLP.

2. Παραδείγματα σύνταξης μαθηματικών μοντέλων οικονομικών προβλημάτων

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

1.Το πρόβλημα του βέλτιστου σχεδίου παραγωγής

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

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

Λύση.

Ας υποδηλώσουμε x 1, x 2 - τον αριθμό των μονάδων παραγωγής, αντίστοιχα, T 1 και T 2, που έχουν προγραμματιστεί για παραγωγή. Για την κατασκευή τους, θα απαιτηθούν (x 1 + x 2) μονάδες του πόρου S 1, (x 1 + 4x 2) μονάδες του πόρου S 2, (x 1) μονάδες του πόρου S 3. Η κατανάλωση των πόρων S 1 , S 2 , S 3 δεν πρέπει να υπερβαίνει τα αποθέματά τους, αντίστοιχα 8, 20 και 5 μονάδες.

Στη συνέχεια, το οικονομικό-μαθηματικό μοντέλο του προβλήματος μπορεί να διατυπωθεί ως εξής:

Βρείτε ένα σχέδιο παραγωγής X \u003d (x 1, x 2) που να ικανοποιεί το σύστημα περιορισμών:

και η συνθήκη

κάτω από την οποία η συνάρτηση παίρνει τη μέγιστη τιμή.

Το πρόβλημα μπορεί εύκολα να γενικευτεί στην περίπτωση παραγωγής n τύπων προϊόντων χρησιμοποιώντας m τύπους πόρων.

2.Το βέλτιστο πρόβλημα διατροφής

Υπάρχουν δύο είδη τροφίμων K 1 και K 2 που περιέχουν θρεπτικά συστατικά S 1 , S 2 και S 3 . Η περιεκτικότητα του αριθμού των θρεπτικών μονάδων σε 1 κιλό κάθε τύπου ζωοτροφής, το απαιτούμενο ελάχιστο θρεπτικών συστατικών, καθώς και το κόστος 1 κιλού ζωοτροφής φαίνονται στον πίνακα:

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

Λύση.

Ας υποδηλώσουμε x 1, x 2 - την ποσότητα τροφής K 1 και K 2 που περιλαμβάνονται στην καθημερινή διατροφή. Στη συνέχεια, αυτή η δίαιτα θα περιλαμβάνει (3x 1 + x 2) μονάδες θρεπτικού συστατικού S 1, (x 1 + 2 x 2) μονάδες ουσίας S 2, (x 1 + 6 x 2) μονάδες θρεπτικών συστατικών S 3. Δεδομένου ότι η περιεκτικότητα σε θρεπτικά συστατικά S 1 , S 2 και S 3 στη δίαιτα πρέπει να είναι 9, 8 και 12 μονάδες, αντίστοιχα, το οικονομικό-μαθηματικό μοντέλο του προβλήματος μπορεί να διατυπωθεί ως εξής:

Συνθέστε μια καθημερινή δίαιτα X \u003d (x 1, x 2), ικανοποιώντας το σύστημα περιορισμών:

και η συνθήκη

κάτω από την οποία η συνάρτηση παίρνει την ελάχιστη τιμή.

Φόρμες εγγραφής PLP

Στο LLP, απαιτείται να βρεθεί το άκρο της συνάρτησης γραμμικού στόχου:

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

και η συνθήκη μη αρνητικότητας

όπου a ij , b i , c j ( , ) δίνονται σταθερές.

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

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

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

Ένας περιορισμός ανισότητας (£) μπορεί να μετατραπεί σε περιορισμό ισότητας προσθέτοντας μια επιπλέον μη αρνητική μεταβλητή στην αριστερή του πλευρά και ένας περιορισμός ανισότητας (³) μπορεί να μετατραπεί σε περιορισμό ισότητας αφαιρώντας μια επιπλέον μη αρνητική μεταβλητή από τον αριστερή πλευρά. Ο αριθμός των εισαγόμενων πρόσθετων μη αρνητικών μεταβλητών είναι ίσος με τον αριθμό των μετασχηματισμένων περιορισμών ανισότητας.

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

Παράδειγμα 1. Γράψτε στην κανονική μορφή ZLP:

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

Λύση.

Η αντικειμενική συνάρτηση παραμένει αμετάβλητη:

Το σύστημα των ανισοτήτων μετατρέπεται σε σύστημα ισοτήτων:

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

Για να φέρετε το LLP σε μια τυπική φόρμα, χρησιμοποιήστε Μέθοδος Jordan-GaussΛύσεις SLAU. Σε αντίθεση με τη μέθοδο Gauss, στην οποία ο εκτεταμένος πίνακας του συστήματος μειώνεται σε μια βαθμιδωτή μορφή, στη μέθοδο Jordan-Gauss, σχηματίζεται ένας πίνακας ταυτότητας ως μέρος του εκτεταμένου πίνακα. Επομένως, δεν απαιτείται αντίστροφη κίνηση εδώ.

Για να μετατρέψετε το αρχικό κανονικό LLP στο ισοδύναμο πρότυπο LLP:

α) ένα μη μηδενικό στοιχείο a qp επιλέγεται στον εκτεταμένο πίνακα του συστήματος περιορισμών. Αυτό το στοιχείο ονομάζεται επιτρεπτικός, και q - i γραμμή και p-η στήλη ονομάζεται γραμμή ενεργοποίησης και στήλη ενεργοποίησης.

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

Θεωρήστε τέσσερα στοιχεία του διευρυμένου πίνακα: το στοιχείο a ij προς μετατροπή, το στοιχείο επίλυσης a qp και τα στοιχεία a i p και a qj . Για να βρεθεί το στοιχείο a ij, ακολουθεί το στοιχείο a ij να αφαιρεθεί το γινόμενο των στοιχείων a i p και ενός qj που βρίσκονται στις απέναντι κορυφές του ορθογωνίου, διαιρούμενο με το στοιχείο ανάλυσης a qp:

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

Παράδειγμα 2. Αλλαγή σε τυπική φόρμα:

Λύση.

Χρησιμοποιώντας τη μέθοδο Jordan-Gauss, φέρνουμε το σύστημα των εξισώσεων περιορισμού LLP σε ένα ισοδύναμο σύστημα ανισοτήτων. Ας επιλέξουμε το τρίτο στοιχείο της πρώτης σειράς ως στοιχείο επίλυσης:

Ο αριθμός -9 που προκύπτει στην τελευταία στήλη της τελευταίας σειράς πρέπει να γραφτεί στην αντικειμενική συνάρτηση με το αντίθετο πρόσημο. Ως αποτέλεσμα των μετασχηματισμών, το LLP παίρνει τη μορφή:

Επειδή Οι μεταβλητές x 2 και x 3 είναι μη αρνητικές, τότε απορρίπτοντας τις, μπορούμε να γράψουμε το ZLP σε συμμετρική μορφή:

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

Ιδιότητες ZLP

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

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

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

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

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

Το σημείο Χ ονομάζεται κυρτός γραμμικός συνδυασμόςσημεία X 1 , X 2 ,…, X n εάν πληρούνται οι ακόλουθες προϋποθέσεις:

X \u003d α 1 X 1 + α 2 X 2 + ... + α n X n,

αj ≥ 0, Σαj = 1.

Είναι προφανές ότι στην ειδική περίπτωση για n = 2 ένας κυρτός γραμμικός συνδυασμός δύο σημείων είναι ένα τμήμα που τα συνδέει.

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

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

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

Διάλεξη 2

ΣΕ κανονική μορφή

αποδεκτή λύση του PLP(αποδεκτό σχέδιο).

βέλτιστη λύση του LLP.

Ανάγκη

Παράδειγμα.

Ας γράψουμε το πρόβλημα κανονική μορφή

Ειδικές καταστάσεις της γραφικής λύσης του ZLP

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

1. καθήκον έχει ένας άπειρος αριθμός βέλτιστων λύσεων – το άκρο της συνάρτησης επιτυγχάνεται στο τμήμα ( εναλλακτικό βέλτιστο)- Σχήμα 2;

2. καθήκον μη επιλύσιμο λόγω του απεριόριστου του ODR, ή - Εικόνα 3.

3. ODR - ΜΟΝΑΔΙΚΟ σημείο Α, τότε;

4. καθήκον μη επιλύσιμο εάν το ODR έχει κενή περιοχή.

ΕΝΑ

Εικόνα 2 Εικόνα 3

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

που είναι η παράμετρος. Για οποιαδήποτε τιμή από το 0 έως το 1, μπορείτε να λάβετε όλα τα σημεία του τμήματος, για καθένα από τα οποία η συνάρτηση παίρνει την ίδια τιμή. Εξ ου και το όνομα - εναλλακτικό βέλτιστο.

Παράδειγμα. Λύστε γραφικά το πρόβλημα γραμμικού προγραμματισμού ( εναλλακτικό βέλτιστο):

Ερωτήσεις για αυτοέλεγχο

1. Καταγράψτε το πρόβλημα γραμμικού προγραμματισμού σε γενική μορφή.

2. Καταγράψτε το πρόβλημα γραμμικού προγραμματισμού σε κανονικές και τυπικές μορφές.

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

4. Δώστε έναν ορισμό των εφικτών και βέλτιστων λύσεων στο πρόβλημα του γραμμικού προγραμματισμού.

5. Ποια από τις λύσεις είναι η «καλύτερη» για το πρόβλημα της ελαχιστοποίησης της συνάρτησης αν ?

6. Ποια από τις λύσεις είναι η «καλύτερη» για το πρόβλημα της μεγιστοποίησης της συνάρτησης αν ?

7. Να γράψετε την τυπική μορφή του μαθηματικού μοντέλου ενός προβλήματος γραμμικού προγραμματισμού με δύο μεταβλητές.

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

9. Τι λέγεται η λύση ενός συστήματος γραμμικών ανισώσεων με δύο μεταβλητές; Κατασκευάστε στο επίπεδο το πεδίο των εφικτών λύσεων ενός τέτοιου συστήματος γραμμικών ανισοτήτων, το οποίο:

1) έχει μια μοναδική λύση.

2) έχει ένα άπειρο σύνολο λύσεων.

3) δεν έχει λύση.

10. Γράψτε για μια γραμμική συνάρτηση διανυσματική κλίση, ονομάστε τον τύπο των γραμμών επιπέδου. Πώς βρίσκονται οι γραμμές κλίσης και επιπέδου μεταξύ τους;

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

12. Πώς να βρείτε τις συντεταγμένες και τις τιμές λύσης, ;

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

1) επιτυγχάνεται σε ένα μόνο σημείο και - στο τμήμα ODR.

2) επιτυγχάνεται σε ένα μόνο σημείο του ODS και .

14. Δώστε μια γεωμετρική απεικόνιση του LLP εάν:

1) έχει μοναδικές βέλτιστες λύσεις για και ;

2) έχει ένα σύνολο βέλτιστων λύσεων για .

Διάλεξη 2

γραφική μέθοδος για την εύρεση της βέλτιστης λύσης

1. Μορφές γραμμικών μαθηματικών μοντέλων και μετασχηματισμός τους

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

3. ΕΙΔΙΚΕΣ ΚΑΤΑΣΤΑΣΕΙΣ ΤΗΣ ΓΡΑΦΙΚΗΣ ΛΥΣΗΣ ΤΟΥ LLP

4. Γραφική επίλυση οικονομικών προβλημάτων γραμμικού προγραμματισμού

Μορφές γραμμικών μαθηματικών μοντέλων και μετασχηματισμός τους

Ένα μαθηματικό μοντέλο ενός προβλήματος γραμμικού προγραμματισμού (LPP) μπορεί να γραφτεί σε μία από τις τρεις μορφές.

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

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

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

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

Το σύνολο των εφικτών λύσεων ονομάζεται την περιοχή των εφικτών λύσεων του LLP.

Μια εφικτή λύση, στην οποία η αντικειμενική συνάρτηση φτάνει μια ακραία τιμή, ονομάζεται βέλτιστη λύση του LLP.

Οι τρεις μορφές του LLP είναι ισοδύναμες με την έννοια ότι καθεμία από αυτές μπορεί να αναχθεί σε διαφορετική μορφή με τη βοήθεια μαθηματικών μετασχηματισμών.

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

Μετάβαση στον κανονικό συμβολισμό ZLP.

Παράδειγμα.

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

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

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

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

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

Η κατάρτιση ενός μαθηματικού μοντέλου περιλαμβάνει:

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

Μεταβλητές εργασιώνονομάζονται ποσότητες X1, X2, Xn, που χαρακτηρίζουν πλήρως την οικονομική διαδικασία. Συνήθως γράφονται ως διάνυσμα: X=(X 1 , X 2 ,...,X n).

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

λειτουργία στόχουΗ εργασία ονομάζεται συνάρτηση μεταβλητών εργασιών που χαρακτηρίζει την ποιότητα της εργασίας και της οποίας το άκρο απαιτείται να βρεθεί.

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

Αυτή η καταχώρηση σημαίνει τα εξής: βρείτε το άκρο της αντικειμενικής συνάρτησης (1) και τις αντίστοιχες μεταβλητές X=(X 1 , X 2 ,...,X n) με την προϋπόθεση ότι αυτές οι μεταβλητές ικανοποιούν το σύστημα περιορισμών (2) και μη -συνθήκες αρνητικότητας (3) .

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

Το σύνολο των εφικτών λύσεων (σχεδίων) του προβλήματος διαμορφώνεται γκάμα εφικτών λύσεων(ODR).

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

Ένα παράδειγμα σύνταξης μαθηματικού μοντέλου

Το έργο της χρήσης πόρων (πρώτων υλών)

Κατάσταση:Για την κατασκευή n τύπων προϊόντων, χρησιμοποιούνται m τύποι πόρων. Φτιάξτε ένα μαθηματικό μοντέλο.

Γνωστός:

• b i (i = 1,2,3,...,m) είναι τα αποθέματα κάθε i-ου τύπου πόρου.
• a ij (i = 1,2,3,...,m; j=1,2,3,...,n) είναι το κόστος κάθε i-ου τύπου πόρου για την παραγωγή μοναδιαίου όγκου τον j-ο τύπο προϊόντος.
• c j (j = 1,2,3,...,n) είναι το κέρδος από την πώληση μιας μονάδας όγκου του j-ου τύπου προϊόντος.

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

Λύση:

Εισάγουμε ένα διάνυσμα μεταβλητών X=(X 1 , X 2 ,...,X n), όπου x j (j = 1,2,...,n) είναι ο όγκος παραγωγής του j-ου τύπου προϊόν.

Το κόστος του i-ου τύπου πόρου για την παραγωγή ενός δεδομένου όγκου x j προϊόντων είναι ίσο με ij x j , επομένως, ο περιορισμός στη χρήση πόρων για την παραγωγή όλων των τύπων προϊόντων έχει τη μορφή:
Το κέρδος από την πώληση του j-ου τύπου προϊόντος είναι ίσο με c j x j , άρα η αντικειμενική συνάρτηση ισούται με:

Απάντηση- Το μαθηματικό μοντέλο μοιάζει με:

Κανονική μορφή προβλήματος γραμμικού προγραμματισμού

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

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

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

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

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

• Το Α είναι ο πίνακας των συντελεστών του συστήματος των εξισώσεων
• Το X είναι ένας πίνακας στήλης μεταβλητών εργασιών
• Το Ao είναι η μήτρα-στήλη των δεξιών τμημάτων του συστήματος περιορισμών

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

Αναγωγή ενός γενικού προβλήματος γραμμικού προγραμματισμού σε κανονική μορφή

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

Αυτό μπορεί να γίνει ως εξής:

Πάρτε μια γραμμική ανισότητα a 1 x 1 +a 2 x 2 +...+a n x n ≤b και προσθέστε στην αριστερή της πλευρά κάποια τιμή x n+1 έτσι ώστε η ανίσωση να γίνει η ισότητα a 1 x 1 +a 2 x 2 + ...+a n x n +x n+1 =b. Επιπλέον, αυτή η τιμή x n+1 είναι μη αρνητική.

Ας εξετάσουμε τα πάντα με ένα παράδειγμα.

Παράδειγμα 26.1

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

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