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

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

Εξετάστε την τρίτη περίπτωση κατασκευής ενός αρχικού σχεδίου αναφοράς (το πρώτο και το δεύτερο περιγράφονται στην παράγραφο 2.1).

Αφήστε το σύστημα περιορισμών να έχει τη μορφή

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

.

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

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

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

;
;

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

;

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

.

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

Θεώρημα 5. Εάν στο βέλτιστο σχέδιο NS ΧΟΝΔΡΙΚΟ ΕΜΠΟΡΙΟ 

Μ-προβλήματα (10) - (12) όλες οι τεχνητές μεταβλητές
τότε σχεδιάστε
είναι το βέλτιστο σχέδιο για το αρχικό πρόβλημα (7) - (9).

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

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

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

Ο πρώτος περιορισμός έχει μια προτιμώμενη μεταβλητή NS 3, αλλά το δεύτερο δεν είναι. Επομένως, εισάγουμε μια τεχνητή μεταβλητή σε αυτήν w 1 Ερχόμαστε στο Μ-έργο

Ας προσθέσουμε τον όρο Μ-εργασίες σε έναν πίνακα simplex. 5. Το αρχικό σχέδιο αναφοράς είναι Χ 0 = (Χ 1 ;Χ 2 ;Χ 3 ;Χ 4 ;w 1) = (0; 0; 2; 0; 12),z(Χ 0) = 0 – 12Μ.

Πίνακας 5

	με σι
z ι – ντο ι

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

Είναι βολικό να χωρίσετε τη γραμμή ευρετηρίου στα δύο. Το πρώτο από αυτά περιέχει τους ελεύθερους όρους των εκφράσεων  0 = ντο σι ΕΝΑ 0 και  ι =ντο σι ΕΝΑ ι –ντο ι, και στο δεύτερο - συντελεστές που περιέχουν Μ... Για παράδειγμα, για πίνακα. 5:

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

Ας περάσουμε στο νέο τραπέζι. 6

Βρίσκουμε τη στήλη επίλυσης κατά μέγιστο (| –3 Μ|; |–4Μ|} = 4Μ, η συμβολοσειρά ανάλυσης καθορίζεται από
... Επομένως, το 1 είναι ένα στοιχείο που επιτρέπει.

Πίνακας 6

	με σι
z ι – ντο ι

Δεν υπάρχουν αρνητικές αξιολογήσεις στη σειρά ευρετηρίου. Επομένως, με βάση το κριτήριο βελτιστοποίησης, το βασικό σχέδιο (0; 2; 0; 0; 4) είναι το βέλτιστο. Αλλά αφού στο βέλτιστο σχέδιο η τεχνητή μεταβλητή w 1 δεν είναι ίσο με 0, τότε από το Θεώρημα 6 το σύστημα των περιορισμών του αρχικού προβλήματος είναι ασυμβίβαστο. Το πρόβλημα δεν έχει λύση.

Απάντηση: δεν υπάρχει απόφαση.

Παράδειγμα 5.Λύστε το πρόβλημα χρησιμοποιώντας τεχνητή βάση

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

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

Ο πρώτος και ο τέταρτος περιορισμός έχουν προτιμώμενες μεταβλητές, ενώ ο δεύτερος και ο τρίτος όχι. Επομένως, εισάγουμε τεχνητές μεταβλητές σε αυτές w 1 και w 2 Ερχόμαστε στο Μ-έργο

Ας προσθέσουμε τον όρο Μ-εργασίες σε έναν πίνακα simplex. 7. Το αρχικό σχέδιο αναφοράς είναι Χ 0 = (0; 0; 10; 0; 0; 4; 3; 9),z(Χ 0) = 0 + 12Μ.

Πίνακας 7

	με σι
z ι – ντο ι

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

Πίνακας 8

		με σι

Μέθοδος τεχνητής βάσης (μέθοδος Simplex) - Παράδειγμα 1

Αντικειμενική λειτουργία:

1Χ 1 + 5Χ 2 + 4Χ 3 -3Χ 4 → μέγ

2Χ 1 + 7Χ 2 + 1Χ 3 + 0Χ 4 ≤5
1Χ 1 + 4Χ 2 + 2Χ 3 + 8Χ 4 = 6
-1Χ 1 + 0Χ 2 + 2Χ 3 + 5Χ 4 = 9

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

2Χ 1 + 7Χ 2 + 1Χ 3 + 0Χ 4 + Χ5 = 5
1X 1 + 4X 2 + 2X 3 + 8X 4 + R1 = 6
-1X 1 + 0X 2 + 2X 3 + 5X 4 + R2 = 9
Περνάμε στο σχηματισμό του αρχικού πίνακα απλού τύπου. Οι συντελεστές της συνάρτησης αντικειμένου καταχωρούνται στη σειρά F του πίνακα. Δεδομένου ότι πρέπει να βρούμε το μέγιστο της αντικειμενικής συνάρτησης, οι συντελεστές με το αντίθετο πρόσημο εισάγονται στον πίνακα

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

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

	Χ1	Χ2	X3	X4	Δωρεάν μέλος
φά	-1	-5	-4	3	0
Χ5	2	7	1	0	5
R1	1	4	2	8	6
R2	-1	0	2	5	9
Μ	0	-4	-4	-13	-15

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

	Χ1	Χ2	X3	Δωρεάν μέλος
φά	-1.375	-6.5	-4.75	-2.25
Χ5	2	7	1	5
X4	0.125	0.5	0.25	0.75
R2	-1.625	-2.5	0.75	5.25
Μ	1.625	2.5	-0.75	-5.25

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

	Χ1	Χ2	X4	Δωρεάν μέλος
φά	1	3	19	12
Χ5	1.5	5	-4	2
X3	0.5	2	4	3
R2	-2	-4	-3	3
Μ	2	4	3	-3

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

Μέθοδος τεχνητής βάσης (πρόβλημα Μ).

Για πολλά προβλήματα γραμμικού προγραμματισμού γραμμένα με τη μορφή του κύριου προβλήματος και με σχέδια αναφοράς, δεν υπάρχουν πάντα m διανύσματα μονάδας μεταξύ των διανυσμάτων P j.

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

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

φά = ντο 1 Χ 1 + ντο 2 Χ 2 + ……+ ντο ν Χ ν (1)

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

……………………………………… (2)

όπου σι Εγώ  0 ( Εγώ= l, m), Μ<.>νκαι μεταξύ των διανυσμάτων P 1, P 2, ..., P n δεν υπάρχουν διανύσματα m μονάδας.

Ορισμός... Το έργο του καθορισμού της μέγιστης τιμής μιας συνάρτησης

φά= γ 1 Χ 1 + ντο 2 Χ 2 + ……+ ντο ν Χ ν -ΜΧ ν +1 - ... - ΜΧ ν + Μ (3)

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

……………………………………… (4)

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

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

Χ = (0; 0; ...; 0; β 1; σι 2 ; ...; β μ).

καθορίζεται από το σύστημα των διανυσμάτων μονάδων P n +1. R n + 2 , … R n + t , σχηματίζοντας μια βάση διανυσματικού χώρου m-ro, που ονομάζεται τεχνητός.Τα ίδια τα διανύσματα, καθώς και οι μεταβλητές Χ n + i ( Εγώ= l, Μ), λέγονται τεχνητός.Δεδομένου ότι το εκτεταμένο πρόβλημα έχει ένα βασικό σχέδιο, η λύση του μπορεί να βρεθεί χρησιμοποιώντας μια μέθοδο simplex.

Θεώρημα Εάν στο βέλτιστο σχέδιο X * = ( Χ * 1 , Χ* 2 , ...; Χ* n , Χ* n +1 ; ...; Χ* n + m) εκτεταμένο έργο (3) - (4) τεχνητές μεταβλητές τιμές Χ* n + i = 0 ( Εγώ=1, Μ), τότε X * = ( Χ * 1 , Χ* 2 , ...; Χ* ν) είναι το βέλτιστο σχέδιο εργασίας (1) - (2).

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

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

Η επαναληπτική διαδικασία κατά μήκος της γραμμής (m + 2) -και συνεχίζεται μέχρι:

είτε όλα τα τεχνητά διανύσματα δεν θα εξαιρεθούν από τη βάση.

ή δεν εξαιρούνται όλα τα τεχνητά διανύσματα, αλλά η (m + 2) ου σειρά δεν περιέχει πλέον αρνητικά στοιχεία στους δείκτες ∆ 1,…, ∆ n.

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

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

Στάδια εύρεσης λύσης στο πρόβλημα (1) - (2)

μέθοδος τεχνητής βάσης:

Το εκτεταμένο πρόβλημα (3) - (4) αποτελείται.

Βρείτε το βασικό σχέδιο της εκτεταμένης εργασίας.

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

Χρησιμοποιώντας το σχέδιο υποστήριξης του προβλήματος (1) - (2), είτε το βέλτιστο σχέδιο του αρχικού προβλήματος βρίσκεται με τη μέθοδο simplex, είτε καθορίζεται η αναποφασιστικότητά του.

Παράδειγμα.

Βρείτε το ελάχιστο μιας συνάρτησης φά= - 2Χ 1 + 3Χ 2 - 6Χ 3 - Χ 4

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

2x 1 + x 2 -2x 3 + x 4 = 24

x 1 + 2x 2 + 4x 3 ≤22

x 1 -x 2 + 2x 3 ≥10

Χ Εγώ ≥0, Εγώ=1,4

Λύση.

Ας γράψουμε αυτήν την εργασία με τη μορφή της κύριας εργασίας: βρείτε τη μέγιστη συνάρτηση φά= 2Χ 1 - 3Χ 2 + 6Χ 3 + Χ 4

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

2x 1 + x 2 -2x 3 + x 4 = 24

x 1 + 2x 2 + 4x 3 + x 5 = 22

x 1 -x 2 + 2x 3 - x 6 = 10

Χ Εγώ ≥0, Εγώ=1, 6

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

Μεταξύ των διανυσμάτων P 1, R 2 , … P 6 μόνο δύο μονά (P 4 και P 5). Επομένως, στην αριστερή πλευρά της τρίτης εξίσωσης του συστήματος περιορισμών του προβλήματος, προσθέτουμε μια επιπλέον μη αρνητική μεταβλητή x 7 και εξετάστε το εκτεταμένο πρόβλημα μεγιστοποίησης της συνάρτησης

φά= 2Χ 1 - 3Χ 2 + 6Χ 3 + Χ 4 - Мх7

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

2x 1 + x 2 -2x 3 + x 4 = 24

x 1 + 2x 2 + 4x 3 + x 5 = 22

x 1 -x 2 + 2x 3 - x 6 + x 7 = 10

Το διευρυμένο πρόβλημα έχει μια βασική γραμμή Χ = (0; 0; 0; 24; 22; 0; 10), που καθορίζεται από ένα σύστημα τριών μονάδων διανυσμάτων: Ρ 4, Ρ 5, Ρ 7.

Η έννοια ενός διπλού (συζευγμένου) προβλήματος γραμμικού προγραμματισμού.

Κανόνες κατασκευής διπλή εργασία.

Με κάθε πρόβλημα γραμμικού προγραμματισμού (LPP), το οποίο ονομάζεται διπλό πρόβλημα (ή παρακείμενο) σε σχέση με το αρχικό πρόβλημα, το οποίο ονομάζεται άμεσο.

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

F = c 1 x 1 + c 2 x 2 +… + c n x n  max (3,6)

a 11 x 1 + a 12 x 2 +… + a 1n x n ≤ b 1,

α 21 x 1 + a 22 x 2 +… + a 2n x n ≤ b 2,

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

a k1 x 1 + a k2 x 2 +… + a kn x n ≤ = b k, (3,7)

a k + 1,1 x 1 + a k + 1,2 x 2 +… + a k + 1, n x n = b k + 1,

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

a m1 x 1 + a m2 x 2 +… + a mn x n = b m,

x j ≥ 0 ,, μεγάλο≤ n (3.8)

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

L = b 1 y 1 + b 2 y 2 +… + b m y m (3,9)

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

a 11 y 1 + a 12 y 2 +… + a m1 y m ≥ c 1

α 21 y 1 + a 22 y 2 +… + a m2 y m ≥ c 2

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

Α'1 μεγάλο y 1 + a 2 μεγάλο y 2 +… + a m μεγάλο y m ≥ c μεγάλο (3.10)

ένα μεγάλο+1,1 y 1 + α μεγάλο+1,2 y 2 + ... + a μεγάλο+ 1, m y m = c l + 1

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

a m1 y 1 + a m2 y 2 +… + a mn y m = c m

y i ≥ 0 ,, k ≤ m (3.11)

ονομάζεται διπλό σε σχέση με το πρόβλημα (3.6) - (3.8).

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

Δομικά χαρακτηριστικά του ZLP	Πρόβλημα γραμμικού προγραμματισμού
		Διπλός
1. Αντικειμενική συνάρτηση	Μεγιστοποίηση (μέγ.)	Ελαχιστοποίηση (λεπτό)
2. Αριθμός μεταβλητών	n μεταβλητές	Alδιο με τον αριθμό των περιορισμών του άμεσου προβλήματος (3.7), y i, δηλ. Μ
3. Αριθμός περιορισμών	m περιορισμούς	Alδιο με τον αριθμό των μεταβλητών του άμεσου προβλήματος x j, δηλ. N
4. Πίνακας συντελεστών στο σύστημα περιορισμών
5. Συντελεστές μεταβλητών στην αντικειμενική συνάρτηση	c 1, c 2, ..., c n	β 1, β 2, ..., β μ
6. Δεξί μέροςσυστήματα περιορισμών	β 1, β 2, ..., β μ	c 1, c 2, ..., c n
7. Σημάδια στο σύστημα περιορισμών	α) x j ≥ 0- συνθήκη μη αρνητικότητας	Ο περιορισμός j-th έχει ένα σύμβολο ""
	β) η μεταβλητή x j δεν υπόκειται στη συνθήκη μη αρνητικότητας	Ο περιορισμός j-th έχει ένα σύμβολο "="
	v) i-th περιορισμόςέχει το σύμβολο ""	μεταβλητή y i ≥0
	δ) ο i-ο περιορισμός έχει το σύμβολο "="	η μεταβλητή y i δεν υπόκειται στη συνθήκη μη αρνητικότητας

Σημείωση

Το άμεσο πρόβλημα στο μέγιστο και το διπλό στο ελάχιστο είναι αμοιβαία διπλά προβλήματα. Επομένως, μπορούμε να θεωρήσουμε το πρόβλημα (3.9) - (3.11) ως άμεσο LPP και το πρόβλημα (3.6) - (3.8) ως το διπλό του πρόβλημα. Σε αυτήν την περίπτωση, οι κανόνες για την κατασκευή ενός διπλού LPP διατηρούνται, μόνο με την αλλαγή ότι το ελάχιστο πρόβλημα θεωρείται το αρχικό.

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

α) είτε πολλαπλασιάστε και τα δύο μέρη Εγώου ( ι-θ) ανισότητα κατά (-1) και αλλάξτε το πρόσημο σε "" ("≥")

β) είτε φέρτε Εγώ-ε ( ι-στ) περιορισμός στην ισότητα εισάγοντας μια πρόσθετη μεταβλητή x n + Εγώ ≥0

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

Αφήστε το πρόβλημα να μειωθεί στην κανονική μορφή (1.6), στην οποία σε ορισμένες εξισώσεις, πείτε στο Εγώ 1 μ., Εγώ 2ο, ..., είναι -μ, οι βασικές μεταβλητές δεν κατανέμονται ρητά. Προσθέστε σε αυτές τις εξισώσεις τεχνητές μεταβλητές x m +1 , x m +2 , …, x m + μικρό , και η συνάρτηση αντικειμένου περιέχει τους όρους Μχ μ +1, ± Μχ μ +2,…, Μχ μ + μικρό , όπου Μ >>1 (Μ είναι ένας αρκετά μεγάλος θετικός αριθμός) και "±" είναι "+" εάν το πρόβλημα επιλυθεί για ελάχιστο και "±" είναι "-" εάν το πρόβλημα επιλυθεί για μέγιστο. Αποδεικνύεται μια νέα εργασία που ονομάζεται πρόσθετος ή θυγατρική .

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

ντο 1 Χ 1 +ντο 2 Χ 2 +…+c n x n +Mx n + Μ +1 +Mx n + Μ +2 +…+Mx n +2 Μ ®λεπ

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

ντο 1 Χ 1 +ντο 2 Χ 2 +…+c n x n -Mx n +1 -Mx n +2 -…-Mx n + Μ ® max

(5.1)

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

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

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

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

3. Λύστε το βοηθητικό πρόβλημα και εάν (,,… ,,, ...,) είναι η βέλτιστη λύση στο βοηθητικό πρόβλημα, όπου Χ 1 , Χ 2 , …, x m - βασικές και πρόσθετες μεταβλητές (από το πρόβλημα στην κανονική μορφή), x m +1 , x m +2 , …, x m + μικρό - τεχνητές μεταβλητές τότε (,,…,) - η λύση του προβλήματος σε κανονική μορφή. Η βέλτιστη τιμή της αντικειμενικής συνάρτησης του βοηθητικού προβλήματος είναι ίση με τη βέλτιστη τιμή του αρχικού προβλήματος.

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

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

2. Οι τεχνητές μεταβλητές, όπως προέρχονται από τη βάση, αποκλείονται από περαιτέρω εξέταση.

3. Αφού προκύψουν όλες οι τεχνητές μεταβλητές από τη βάση, οι συντελεστές Δ κ στο Μ θα είναι ίση με μηδέν, μόνο η γραμμή = D παραμένει στον πίνακα κ .

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

Λύση. Υπενθυμίζουμε την εργασία:

3Χ 1 +Χ 2 +2Χ 3 ® max (min)

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

3Χ 1 +Χ 2 +2Χ 3 ® max (min)

2. Η βάση με τη μορφή μονάδας διανύσματος περιλαμβάνει μόνο το διάνυσμα στο Χ 4, δηλαδή, η μεταβλητή στη δεύτερη εξίσωση. Στην πρώτη και τρίτη εξίσωση του συστήματος των περιορισμών, εισάγουμε τεχνητές μεταβλητές Χ 6 και Χ 7:

Θα εισέλθουν στην αντικειμενική συνάρτηση με τους συντελεστές Μ ή - Μ ανάλογα με το αν το πρόβλημα λύθηκε στο min ή στο max.

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

3Χ 1 +Χ 2 +2Χ 3 -Mx 6 -Mx 7 ® μέγ

3. Λύνουμε το προκύπτον βοηθητικό πρόβλημα χρησιμοποιώντας πίνακες simplex:

Βάση

ΜΕ σι

Ελεύθερος μέλος

-3

-Μ

-Μ

q 2

q 3

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 6

-Μ

-1

λ

x 4

-

x 7

-Μ

-1

-1

-2

-8

-2

-3

Εδώ D 2 = -2 Μ -1, D3 = -3 Μ -2. Συντελεστές στο Μ γραμμένο στη σειρά. Έχουμε αυτό το D 2<0 и D 3 <0, то есть для переменных Χ 2 και Χ 3 το κριτήριο βελτιστοποίησης παραβιάζεται. Ως εκ τούτου, θα εισαγάγουμε στη βάση Χ 2 ή Χ 3 Ποιες από αυτές τις μεταβλητές και αντί ποιες από τις τεχνητές (αντί για Χ 6 ή αντί Χ 7), ορίζεται με τη χρήση στηλών q 2 και q 3 Στη διασταύρωση μιας στήλης q 2 και οι σειρές και οι αριθμοί 2 και 4, αντίστοιχα, σημαίνουν ότι αν συμπεριληφθούν στη βάση Χ 2, η τιμή της συνάρτησης θα αυξηθεί κατά - q 2 Δ 2 = 4 Μ +2, και αν περιλαμβάνεται στη βάση Χ 3 η τιμή της συνάρτησης θα αυξηθεί κατά - q 3 Δ 3 = 3 Μ +2<-q 2 Δ 2. Ως εκ τούτου, συμπεριλαμβάνουμε στη βάση Χ 2 (που παρέχει μεγαλύτερη αύξηση της λειτουργίας και επιταχύνει τελικά τη διαδικασία επίλυσης του προβλήματος). Δεδομένου ότι το ελάχιστο = 2 επιτυγχάνεται στη γραμμή Χ 6, τότε εξαιρούμε από τη βάση Χ 6 Δημιουργούμε έναν νέο πίνακα simplex, στον οποίο υπάρχει ήδη μια στήλη με τεχνητή μεταβλητή Χ 6 λείπει (διαγράφεται) επειδή το ομοίωμα Χ 6 αποκλείεται από την περαιτέρω διαδικασία. Στο νέο πίνακα, ο συντελεστής στο Χ 2 στην πρώτη γραμμή (η οποία αντιστοιχεί τώρα στη νέα μεταβλητή βάσης Χ 2) είναι ίσο με 1, και στο δεύτερο είναι μηδέν. Επομένως, ξαναγράφουμε τις δύο πρώτες γραμμές στον νέο πίνακα από τον παλιό. Για να ευθυγραμμιστούν Χ 7 στις Χ 2 πάρτε 0, από συμβολοσειρά Χ 7 στον παλιό πίνακα, αφαιρέστε πρώτα το νέο. Παίρνουμε τον επόμενο, επόμενο πίνακα:

Βάση

ΜΕ σι

Ελεύθερος μέλος

-3

-Μ

-Μ

q 1

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 2

-1

-

x 4

x 7

-Μ

-1

-1

λ

-4

-2

Αφού ο Δ κ <0 только для одного значения κ = 1, δηλαδή, D 1 = -2 Μ +2<0 (напоминаем, что Μ είναι αρκετά μεγάλος αριθμός έτσι ώστε -2 Μ <2 и D 1 <0), то ищем только отношения q 1 Το ελάχιστο αυτών των σχέσεων συμπληρώνεται στη γραμμή Χ 7: λεπτά = 2. Επομένως, η τεχνητή μεταβλητή εξαιρείται από τη βάση και αντί αυτής, περιλαμβάνεται η βάση Χ 1 .

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

Βάση	ΜΕ σι	Ελεύθερος μέλος	-3
x 1	x 2	x 3	x 4	x 5
x 2					3/2		-1/2
x 4					3/2		1/2
x 7	-3				-1/2		-1/2
ρε κ	-2

Στον πίνακα που προκύπτει Δ κ ³0 για όλους κ Χ 0 = (2; 4; 0) είναι η βέλτιστη λύση για την οποία η τιμή της συνάρτησης στόχου είναι -2 ( Χ 4 δεν λαμβάνεται υπόψη στην τελική απάντηση, καθώς είναι μια πρόσθετη μεταβλητή και δεν περιλαμβάνεται στην αρχική εργασία).

Ας λύσουμε το ελάχιστο πρόβλημα (min). Τότε το βοηθητικό πρόβλημα έχει ως εξής:

3Χ 1 +Χ 2 +2Χ 3 -Mx 6 -Mx 7 ® μέγ

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

Βάση

ΜΕ σι

Ελεύθερος μέλος

-3

Μ

Μ

q 2

q 3

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 6

Μ

-1

λ

x 4

-

x 7

Μ

-1

-1

-2

-1

Το κριτήριο βελτιστοποίησης παραβιάζεται για τις μεταβλητές Χ 2 και Χ 3: D 2 = 2 Μ -1> 0, D 3 = 3 Μ -2> 0. Επειδή - q 2 Δ 2 = -4 Μ Το +2 σε απόλυτη τιμή υπερβαίνει - q 3 Δ 3 = -3 Μ +2, τότε συμπεριλαμβάνουμε στη βάση Χ 2 Σε αυτήν την περίπτωση, min = 2 επιτυγχάνεται στη γραμμή Χ 6, και εξαιρούμε από τη βάση Χ 6 Η μετάβαση στον νέο πίνακα είναι παρόμοια με τη μετάβαση κατά την επίλυση του προβλήματος για max:

Βάση

ΜΕ σι

Ελεύθερος μέλος

-3

-Μ

-Μ

q 1

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 2

-1

-

x 4

x 7

-Μ

-1

-1

λ

-1

-1

Τώρα D 1> 0. Επομένως, η μετάβαση στον νέο πίνακα είναι παρόμοια με την αντίστοιχη μετάβαση κατά την επίλυση του προβλήματος για max: Χ 1 αντί για Χ 7:

Βάση	ΜΕ σι	Ελεύθερος μέλος	-3					q 3	q 5
x 1	x 2	x 3	x 4	x 5
x 2					3/2		-1/2	8/3	-
x 4					3/2		1/2	4/3
x 7	-3				-1/2		-1/2	-	-
ρε κ	-2						-4/3	-4

Έχουμε D 3 = 1> 0 και D 5 = 1> 0. Από | - q 5 Δ 5 | = | - q 3 D 3 |, τότε εισάγουμε στη βάση Χ 5 (αντί για Χ 4): πρώτα πολλαπλασιάζουμε τη 2η σειρά με 2 και στη συνέχεια η νέα δεύτερη σειρά, πολλαπλασιασμένη με ½, προστίθεται στην πρώτη και την τρίτη (στην πραγματικότητα, η δεύτερη παλιά προστίθεται στην πρώτη και την τρίτη):

Στον πίνακα που προκύπτει Δ κ 0 λίρες για όλους κ = 1, 2,…, 5, δηλαδή πληρούται το κριτήριο βελτιστοποίησης. Να γιατί Χ 0 = (4; 6; 0) είναι η βέλτιστη λύση για την οποία η τιμή της συνάρτησης αντικειμένου είναι -6.

Απάντηση: φά min = -6, το ελάχιστο επιτυγχάνεται στο σημείο Χ 2 =(4; 6; 0);

φά max = -2, το μέγιστο επιτυγχάνεται στο σημείο Χ 1 =(2; 4; 0).

5.2. Η άσκηση.Λύστε τα αντίστοιχα προβλήματα γραμμικού προγραμματισμού από Ασκήσεις 1.3με τη μέθοδο της τεχνητής βάσης.

Θεωρία διττότητας

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

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

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

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

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

Αφήστε όλα /; > 0, αλλά μερικές ή όλες οι βασικές μεταβλητές είναι αρνητικές, Χ; 0. Επομένως, δεν υπάρχει σχέδιο αναφοράς.

Συμπληρώνουμε τις εξισώσεις περιορισμού με τεχνητές μεταβλητές (υποθέτουμε ότι όλα x j j - 1, NS).

Παρουσιάζω Τμεταβλητές (από τον αριθμό των εξισώσεων): x lM m, το οποίο στο νέο σύστημα θα είναι βασικό και αρνητικό NS-

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

Εδώ οι μεταβλητές x n + iδεν έχουν καμία σχέση με το αρχικό πρόβλημα γραμμικού προγραμματισμού. Χρησιμεύουν μόνο για την απόκτηση ενός σχεδίου αναφοράς και ονομάζονται εικονικές μεταβλητές. Και το νέο

η αντικειμενική συνάρτηση /(.t) διαμορφώνεται για την πληρότητα του προβλήματος.

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

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

Ας ξαναγράψουμε το PLP σε τυπική μορφή. Για να γίνει αυτό, εισάγουμε πρόσθετες μεταβλητές x), x A, x 5, x 6 και γράψτε το πρόβλημα σε κανονική μορφή.

Δωρεάν μεταβλητές x, NS 2 = 0, ενώ οι βασικές μεταβλητές θα λάβουν τις τιμές x 3 = -5, x 4 = -5, x 5 = 7, x 6 = 9. Δεδομένου ότι ορισμένες από τις βασικές μεταβλητές είναι αρνητικές, δεν υπάρχει σχέδιο βάσης. Για να αποκτήσουμε το αρχικό σχέδιο βάσης, εισάγουμε τις μεταβλητές x 7, x 8 στις δύο πρώτες εξισώσεις περιορισμών και διατυπώνουμε ένα βοηθητικό πρόβλημα:

Έτσι, η αρχική βάση είναι

Απλός πίνακας με τεχνητή βάση

	NS4

Ας γράψουμε τις ακολουθίες των σχεδίων αναφοράς.

Για τα τρία πρώτα βήματα της προσαύξησης Και στουπολογίζεται μόνο από τεχνητές μεταβλητές που περιλαμβάνονται στην τεχνητή αντικειμενική συνάρτηση f (x) = x 7 + x 8 με συντελεστή c, = 1.

Στο τρίτο βήμα, εξαιρούνται οι τεχνητές μεταβλητές, αφού όλα Και στοθετικός.

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

Σχηματισμός και επίλυση του βοηθητικού προβλήματος LP με την εισαγωγή τεχνητών μεταβλητών. Τα ανδρείκελα στο αρχικό σχέδιο αναφοράς είναι βασικά. Η εικονική συνάρτηση αντικειμένου περιλαμβάνει μόνο εικονικές μεταβλητές. Όταν λαμβάνουμε παρακείμενα σχέδια αναφοράς, μεταφέρουμε τεχνητές μεταβλητές από βασικές σε δωρεάν. Ως αποτέλεσμα, επιτεύχθηκε ένα βέλτιστο αρχικό σχέδιο για το βοηθητικό πρόβλημα f (x) = 0.

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

Παρατηρήσεις

• 1. Η εισαγωγή τεχνητών μεταβλητών απαιτείται σε δύο περιπτώσεις:
  • μια σειρά βασικών μεταβλητών x είναι αρνητικές σε κανονική μορφή.
  • εάν είναι δύσκολο να μειωθεί στην κανονική μορφή, τότε απλά προσθέστε μια τεχνητή μεταβλητή σε οποιαδήποτε εξίσωση-περιορισμό.
• 2. Τα προβλήματα γραμμικού προγραμματισμού που συναντώνται στην πρακτική του αυτόματου ελέγχου περιέχουν από 500 έως 1500 περιορισμούς και περισσότερες από 1000 μεταβλητές. Είναι σαφές ότι τα προβλήματα αυτής της διάστασης μπορούν να επιλυθούν μόνο με τη βοήθεια υπολογιστών και ειδικού λογισμικού. Η πολυπλοκότητα του αλγορίθμου είναι ότι:
  • Το RFP απαιτεί μια κανονική μορφή.
  • Το PPP για προβλήματα αυτής της διάστασης απαιτεί τη χρήση μεγάλων υπολογιστών (και παράλληλων υπολογισμών), αφού η μέθοδος simplex αποθηκεύει ολόκληρο τον πίνακα.
• 3. Η υπολογιστική αποτελεσματικότητα της μεθόδου simplex μπορεί να εκτιμηθεί με τους ακόλουθους δείκτες:
  • αριθμός βημάτων (παρακείμενες γραμμές βάσης).
  • κόστος του χρόνου χρήσης υπολογιστή.

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

• Μέσα βήματα * 2 Τκαι βρίσκεται στην περιοχή)