Γραφική μέθοδος γραμμικού προγραμματισμού online. Γραφικές μέθοδοι
φά= –Χ 1 + 5Χ 2 ¾> ελάχ;
4Χ 1+ 3Χ 2 24 £,
Χ 1– 10Χ 2 £ 0,
8Χ 1– 3Χ 2 ³ 0,
5Χ 1+ 3Χ 2³ 15,
Χ 1³0, Χ 2³ 0. (1)
Σύνολο μεταβλητών xj, που ικανοποιεί τη συνθήκη (1), ονομάζεται περιοχή των εφικτών λύσεων. Μια εφικτή λύση που μετατρέπει την αντικειμενική συνάρτηση σε ελάχή Μέγιστη, ονομάζεται βέλτιστη. Για τον προσδιορισμό του, είναι απαραίτητο να κατασκευαστεί ένας τομέας εφικτών λύσεων (τομέας ορισμού). Δεδομένου ότι δύο μεταβλητές καθορίζονται στη δήλωση προβλήματος, η περιοχή των εφικτών λύσεων βρίσκεται στο επίπεδο Χ 10Χ 2. Κάθε ανισότητα (1) ορίζει ένα ημιεπίπεδο και η ισότητα - μια ευθεία γραμμή. Για να κατασκευάσουμε ένα ημιεπίπεδο, είναι απαραίτητο να βρούμε τα όριά του και να προσδιορίσουμε σε ποια πλευρά του βρίσκεται το επιθυμητό ημιεπίπεδο. Ας ξαναγράψουμε τις συνθήκες (1) με τη μορφή ισοτήτων (2) και ας τις αριθμήσουμε.
| 4Χ 1+ 3Χ 2 | = | 24 (Εγώ), | |
| Χ 1– 10Χ 2 | = | 0 (II), | |
| 8Χ 1– 3Χ 2 | = | 0 (III), | |
| 5Χ 1+ 3Χ 2 | = | 15 (IV). | (2) |
Ας παρουσιάσουμε το σύστημα συντεταγμένων Χ 10Χ 2 και κατασκευάστε αυτές τις ευθείες γραμμές διαδοχικά - τα όρια των ημιεπίπεδων. Για να κατασκευάσετε μια γραμμή σε ένα επίπεδο, είναι απαραίτητο να προσδιορίσετε οποιαδήποτε δύο σημεία βρίσκονται σε αυτή τη γραμμή. Αν η ευθεία τέμνει τον άξονα 0 Χ 1 και 0 Χ 2, τότε μπορείτε να βρείτε τις συντεταγμένες των σημείων τομής του με τους άξονες συντεταγμένων. Ας προσδιορίσουμε τις συντεταγμένες της τομής της ευθείας ( Εγώ) με άξονα 0 Χ 1: Χ 1=0; Þ 3 Χ 2= 24; Þ Χ 2= 8, λοιπόν, προσδιορίζουμε τις συντεταγμένες του δεύτερου σημείου τομής της πρώτης γραμμής με τον άξονα 0 Χ 2: Χ 2=0; Þ 4 Χ 1= 24; Þ Χ 1= 6. Επομένως, τα σημεία τομής της ευθείας ( Εγώ) με άξονες συντεταγμένων ίσους με (0,8) και (6,0). Ας κατασκευάσουμε αυτή την ευθεία γραμμή (Εικ. 1).
Ας ορίσουμε ένα μισό επίπεδο. Για να γίνει αυτό, αντικαθιστούμε στην πρώτη ανισότητα (1) τις συντεταγμένες οποιουδήποτε σημείου που δεν βρίσκεται σε μια δεδομένη ευθεία, για παράδειγμα (0,0). Τότε από την πρώτη συνθήκη προκύπτει: 4×0+3×0 £24, που σημαίνει ότι η ανισότητα είναι αληθής, που σημαίνει ότι το ημιεπίπεδο βρίσκεται στην πλευρά της ευθείας όπου το σημείο με συντεταγμένες (0,0) είναι που βρίσκεται.
Άλλα ημιεπίπεδα κατασκευάζονται με παρόμοιο τρόπο. Είναι απαραίτητο να ληφθεί υπόψη ότι οι ευθείες γραμμές ( II)Και ( III)περάσουν από την αρχή, δηλ. σημείο (0,0). Συνιστάται να λαμβάνετε τις συντεταγμένες του δεύτερου σημείου σε αναλογία με τους συντελεστές στην εξίσωση της επιθυμητής γραμμής. Για παράδειγμα, για τη δεύτερη γραμμή – σημεία (0,0) και (10,1), και για την τρίτη – (0,0) και (3,8). Μετά την κατασκευή όλων των ημιεπίπεδων, η περιοχή των εφικτών λύσεων θα πάρει την ακόλουθη μορφή (Εικ. 3):
Αντικειμενική λειτουργία φάορίζει μια ευθεία στο επίπεδο που πρέπει να διέρχεται από ένα σημείο ή πλευρά ενός πολυγώνου και να έχει τη μικρότερη τιμή. Ας κατασκευάσουμε ένα διάνυσμα κατεύθυνσης για αυτή τη γραμμή. Αυτό το διάνυσμα είναι κάθετο στην επιθυμητή γραμμή και η κατεύθυνσή του καθορίζει πάντα το μέγιστο της αντικειμενικής συνάρτησης. Η αντίθετη φορά του διανύσματος καθορίζει το ελάχιστο. Ας συμβολίσουμε αυτό το διάνυσμα με . Διέρχεται από το σημείο (0,0) και (–1,5). Οι συντεταγμένες του δεύτερου σημείου λαμβάνονται από τους συντελεστές της αντικειμενικής συνάρτησης και με τη βοήθειά τους προσδιορίζεται η φορά του διανύσματος. Ας κατασκευάσουμε μια ευθεία γραμμή κάθετη σε αυτήν - Χ 1+ 5Χ 2=0. Όπως αναφέρθηκε παραπάνω, το διάνυσμα δείχνει πάντα την κατεύθυνση της αυξανόμενης τιμής της αντικειμενικής συνάρτησης ( Μέγιστη), το αντίθετο διάνυσμα είναι η κατεύθυνση της φθίνουσας τιμής της αντικειμενικής συνάρτησης ( ελάχ). Μετακίνηση της γραμμής - Χ 1+5Χ 2=0 στο πεδίο ορισμού παράλληλο με τον εαυτό του στην κατεύθυνση ελάχ. Αντικειμενική λειτουργία φάθα φτάσει την ελάχιστη τιμή του στο σημείο ΜΕ(Εικ. 4).
 |
Η βέλτιστη λύση στο πρόβλημα (1) αντιστοιχεί στο σημείο ΜΕ, που βρίσκεται στη διασταύρωση των γραμμών ( Εγώ) Και ( II):
4Χ 1+ 3Χ 2= 24;
Χ 1– 10Χ 2= 0.
Για να λύσετε αυτό το σύστημα εξισώσεων, πολλαπλασιάστε τη δεύτερη εξίσωση επί 4 και προσθέστε ανάλογα στοιχείο προς στοιχείο με την 1η εξίσωση:
4Χ 1+ 3Χ 2 = 24;
4Χ 1– 40Χ 2 = 0.
Αφαιρούμε το δεύτερο από την πρώτη εξίσωση, παίρνουμε: 43x2= 24 Þ Χ 2= 0,56.
Αντικατάσταση της τιμής που βρέθηκε Χ 2 στη δεύτερη εξίσωση, παίρνουμε:
Χ 1= 10Χ 2Þ Χ 1=5,6. Αντικατάσταση των συντεταγμένων του σημείου ΜΕστην αντικειμενική συνάρτηση, έχουμε το ακόλουθο αποτέλεσμα:
fmin= – 5,6 + 5×0,56 = – 2,8.
Γράφουμε το τελικό αποτέλεσμα του προβλήματος με την ακόλουθη μορφή:
Χ 1= 5,6, Χ 2= 0,56;fmin= – 2,8.
Η λύση αυτού του παραδείγματος σε υπολογιστή πραγματοποιείται από το πακέτο λογισμικού «Block-3». Χρησιμοποιείται για την εισαγωγή, την επίλυση και την έξοδο αποτελεσματικών πληροφοριών σε εξωτερικά μέσα. Η απλότητα και η προσβασιμότητα του συγκροτήματος θα σας επιτρέψει να το κατακτήσετε εύκολα και να το εφαρμόσετε στην πράξη.
Εργασία Νο. 1.1.2.
φά= 2Χ 1+ 3Χ 2 ¾> Μέγιστη;
2Χ 1+ 3Χ 2 £12,
2Χ 1– 5Χ 2 £ 0,
7Χ 1– 2x2³ 0,
Χ 1, Χ 2³ 0. (3)
Οι ορισμοί και η κατασκευή της περιοχής των εφικτών λύσεων είναι παρόμοιοι με την εργασία 1.1.1. Η τελική άποψη της περιοχής των εφικτών λύσεων φαίνεται στο Σχ. 5 πολύγωνο αλφάβητο(τελεία ΕΝΑσυμπίπτει με το σημείο 0).
Προφανώς, η ευθεία γραμμή που ορίζει την αντικειμενική συνάρτηση συμπίπτει με την ευθεία που σχηματίζει την πλευρά του πολυγώνου Ήλιος. Επομένως, η λύση σε αυτό το EMM είναι σημεία που βρίσκονται στο πλάι Ήλιοςπολλά απο-
τετράγωνο αλφάβητο. Για να σημειώσετε τη λύση EMM, πρέπει να βρείτε τη συντεταγμένη Χ 1σι– σημεία ΣΕΚαι Χ 1ντο– σημεία ΜΕ. Αφού τα ορίσουμε, μπορούμε να βρούμε το τμήμα που βρίσκεται στον άξονα 0 Χ 1 (Εικ. 6).
 |
Συντεταγμένες σημείων ΣΕ– x1 σικαθορίζονται ως αποτέλεσμα της τομής των γραμμών 2 Χ 1+ 3Χ 2 = 12 και 7 Χ 1– 2Χ 2 = 0. Για να γίνει αυτό, είναι απαραίτητο να λυθεί το σύστημα των εξισώσεων:
2Χ 1+ 3Χ 2= 12 ´ 2 Þ 4 Χ 1+ 6Χ 2= 24;
7Χ 1– 2Χ 2= 0 ´ 3 Þ 21 Χ 1– 6x2= 0.
Προσθέτοντας τις δύο τελευταίες εξισώσεις, παίρνουμε: 25 Χ 1=24, Χ 1=0,96. Από αυτό προκύπτει ότι Χ 1σι=0,96. Συντεταγμένη σημείου ΜΕ – Χ 1ντοπροσδιορίζεται ως αποτέλεσμα της τομής των γραμμών 2 Χ 1+ 3Χ 2=12 και 2 Χ 1–5Χ 2=0. Ας λύσουμε το σύστημα των εξισώσεων:
2Χ 1+ 3Χ 2= 12 ´ 5 Þ 10 Χ 1+ 15Χ 2= 60;
2Χ 1– 5Χ 2= 0 ´ 3 Þ 6 Χ 1 – 15Χ 2= 0.
Προσθέτοντας τις δύο τελευταίες εξισώσεις, παίρνουμε: 16 Χ 1= 60, Χ 1= 3,75, που σημαίνει ότι Χ 1ντο= 3,75.
Η τιμή της αντικειμενικής συνάρτησης για αυτό το EMM είναι 12 (καθώς η εξίσωση της ευθείας στην οποία ορίζεται το τμήμα είναι Ήλιος – 2Χ 1+3Χ 2= 12).
Έτσι, η απάντηση σε αυτό το πρόβλημα είναι:
Χ 1O[ Χ 1σι; Χ 1ντο] Þ Χ 1О;
2Χ 1+ 3Χ 2=12 Þ 3 Χ 2= 12 – 2Χ 1Þ Χ 2= (12 – 2Χ 1)/3.
Η πλήρης απάντηση για αυτό το παράδειγμα θα γραφεί ως εξής:
Χ 1О; Χ 2= (12 – 2Χ 1)/3; f max= 12.
Εργασία Νο. 1.1.3.
φά= 2Χ 1+ 3Χ 2 ¾> Μέγιστη;
2Χ 1+ 3Χ 2³ 12,
2Χ 1– 5Χ 2 £ 0,
7Χ 1– 2Χ 2³ 0,
Χ 1, Χ 2³0. (4)
Χρησιμοποιώντας το σχήμα για την κατασκευή της περιοχής των εφικτών λύσεων στα προβλήματα 1.1.1–1.1.2, λαμβάνουμε το ακόλουθο γράφημα (Εικ. 7):
φά= 2Χ 1+ 3Χ 2 ¾> Μέγιστη;
Χ 1+ x2 2 £,
2Χ 1+ 3Χ 2³ 12,
2Χ 1– 5Χ 2 £ 0,
7Χ 1– 2Χ 2³ 0,
Χ 1, Χ 2³ 0. (5)
Χρησιμοποιώντας τη γραφική παράσταση του προβλήματος 1.1.3 και συμπληρώνοντας το πρώτο ημιεπίπεδο Χ 1 + x2 £ 2, λαμβάνουμε το πεδίο ορισμού που φαίνεται στο Σχ. 8.
 |
Από το γράφημα (Εικ. 8) είναι σαφές ότι για ένα δεδομένο ΕΜΜ η περιοχή των εφικτών λύσεων Οχι. Απάντηση: δεν υπάρχει περιοχή εφικτών λύσεων.
Εργασία Νο. 1.1.5.
φά= – Χ 1+ 5Χ 2 ¾> min;
10Χ 1+ 3Χ 2 £ 30,
10Χ 1+ 5Χ 2³ 50,
2Χ 1– 6Χ 2 £ 0,
Χ 1, Χ 2³ 0. (6)
Η περιοχή ορισμού του EMM (6) φαίνεται στο Σχ. 9. Από την ανάλυση του γραφήματος προκύπτει ότι η περιοχή των εφικτών λύσεων θα είναι το σημείο ΕΝΑμε συντεταγμένες (0,10) (10 Χ 1+ 5Χ 2= 50, Χ 1= 0, 5Χ 2= 50, Χ 2=10). Στην περίπτωση που η λύση του EMM είναι ένα μόνο σημείο, η αντικειμενική συνάρτηση δεν χρειάζεται να κατασκευαστεί.
Απάντηση: Χ 1= 0; Χ 2=10; fmin= 0+5×10 = 50.
 |
Έτσι, κατά την επίλυση προβλημάτων EMM LP, είναι δυνατές οι ακόλουθες καταστάσεις:
– το πρόβλημα έχει μια βέλτιστη λύση.
– το πρόβλημα έχει άπειρο αριθμό βέλτιστων λύσεων.
– το πρόβλημα δεν έχει βέλτιστη λύση·
– το πρόβλημα δεν έχει περιοχή εφικτών λύσεων.
Στην πράξη, το LP EMM δεν έχει λύσεις μόνο εάν η δήλωση προβλήματος είναι λανθασμένη.
Όπως δείχνει η εμπειρία από την ανάπτυξη του EMM, η κύρια δυσκολία έγκειται στην περιγραφή των οικονομικών και τεχνολογικών διαδικασιών στο μοντέλο και στην επιλογή ενός κριτηρίου βελτιστοποίησης. Από αυτό προκύπτει ότι είναι απαραίτητο να προσδιοριστούν με ακρίβεια οι ρυθμιστικές παράμετροι. Αυτό, με τη σειρά του, απαιτεί σωστή λογιστική και ανάλυση στο υπό μελέτη αντικείμενο. Ταυτόχρονα, το επίπεδο της εξειδικευμένης εκπαίδευσης έχει ιδιαίτερη σημασία για την κατάρτιση του μοντέλου. Η ποιότητα της λύσης σε αυτό το πρόβλημα θα εξαρτηθεί από την ικανότητά του να προσδιορίζει τους κύριους κρίκους της τεχνολογικής διαδικασίας, να προσδιορίζει τα στάδια επίλυσης του προβλήματος και να διατυπώνει τους στόχους της έρευνας.
Εργασία Νο. 1.1.6.
Μια επιχείρηση μπορεί να οργανώσει την παραγωγή των προϊόντων της με δύο τρόπους. Με την πρώτη μέθοδο, η επιχείρηση παράγει σε ένα μήνα ντο 1 χίλια προϊόντα, με το δεύτερο – ντο 2 χιλιάδες προϊόντα. Η κατανάλωση παραγωγής και ανθρώπινου δυναμικού, η απόσβεση του εξοπλισμού και οι περιορισμοί πόρων φαίνονται στον παρακάτω πίνακα.
Πόσους μήνες πρέπει να λειτουργήσει η επιχείρηση, πώς να οργανώσει την παραγωγή για να εξασφαλίσει τη μέγιστη απόδοση.
1) Λύστε γραφικά.
2) Λύστε με βάση το σύμπλεγμα "Block-3".
3) Μέθοδος Simplex.
Σύντομη θεωρία
Ο γραμμικός προγραμματισμός είναι ένας κλάδος του μαθηματικού προγραμματισμού που χρησιμοποιείται στην ανάπτυξη μεθόδων εύρεσης του άκρου γραμμικών συναρτήσεων πολλών μεταβλητών κάτω από γραμμικούς πρόσθετους περιορισμούς που επιβάλλονται στις μεταβλητές. Ανάλογα με το είδος των προβλημάτων που επιλύονται, οι μέθοδοί του χωρίζονται σε καθολικές και ειδικές. Χρησιμοποιώντας καθολικές μεθόδους, μπορούν να λυθούν τυχόν προβλήματα γραμμικού προγραμματισμού (LPP). Οι ειδικές μέθοδοι λαμβάνουν υπόψη τα χαρακτηριστικά του μοντέλου προβλήματος, την αντικειμενική του λειτουργία και το σύστημα περιορισμών. Ένα χαρακτηριστικό των προβλημάτων γραμμικού προγραμματισμού είναι ότι η αντικειμενική συνάρτηση φτάνει σε ένα άκρο στο όριο της περιοχής των εφικτών λύσεων.
Η γραφική μέθοδος για την επίλυση προβλημάτων γραμμικού προγραμματισμού καθιστά δυνατή την οπτικοποίηση της δομής τους, τον εντοπισμό χαρακτηριστικών και ανοίγει τρόπους μελέτης πιο σύνθετων ιδιοτήτων. Ένα πρόβλημα γραμμικού προγραμματισμού με δύο μεταβλητές μπορεί πάντα να λυθεί γραφικά. Ωστόσο, ήδη στον τρισδιάστατο χώρο μια τέτοια λύση γίνεται πιο περίπλοκη και σε χώρους με διαστάσεις μεγαλύτερες από τρεις, μια γραφική λύση είναι, γενικά, αδύνατη. Η περίπτωση δύο μεταβλητών δεν έχει ιδιαίτερη πρακτική σημασία, αλλά η εξέτασή της διευκρινίζει τις ιδιότητες των περιορισμών του LLP, οδηγεί στην ιδέα επίλυσής του και καθιστά τις μεθόδους λύσης και τους τρόπους πρακτικής εφαρμογής τους γεωμετρικά σαφείς.
Εάν οι περιορισμοί και η αντικειμενική συνάρτηση περιέχουν περισσότερες από δύο μεταβλητές, τότε είναι απαραίτητο (ή με τη μέθοδο της διαδοχικής βελτίωσης της λύσης) - είναι καθολική και μπορεί να χρησιμοποιηθεί για την επίλυση οποιουδήποτε προβλήματος. Για ορισμένα εφαρμοσμένα προβλήματα γραμμικού προγραμματισμού, όπως το , έχουν αναπτυχθεί ειδικές μέθοδοι επίλυσης.
Παράδειγμα λύσης προβλήματος
Το έργο
Η επιχείρηση παράγει δύο τύπους προϊόντων: Προϊόν 1 και Προϊόν 2. Για την παραγωγή μιας μονάδας προϊόντος 1, είναι απαραίτητο να δαπανηθούν kg πρώτων υλών του πρώτου τύπου, kg πρώτων υλών του δεύτερου τύπου, kg πρώτων υλών ο τρίτος τύπος. Για την κατασκευή μιας μονάδας του Προϊόντος 2, είναι απαραίτητο να ξοδέψετε κιλά πρώτου τύπου, πρώτες ύλες δεύτερου τύπου και πρώτες ύλες του τρίτου τύπου. Η παραγωγή παρέχεται με πρώτες ύλες κάθε είδους σε ποσότητες kg, kg, kg, αντίστοιχα. Η τιμή αγοράς μιας μονάδας προϊόντος 1 είναι χιλιάδες ρούβλια και μια μονάδα προϊόντος 2 είναι χιλιάδες ρούβλια.
Απαιτείται:
- Κατασκευάστε ένα μαθηματικό μοντέλο του προβλήματος.
- Να συντάξετε ένα σχέδιο παραγωγής προϊόντων που να εξασφαλίζει τα μέγιστα έσοδα από την πώλησή τους χρησιμοποιώντας μια γραφική μέθοδο για την επίλυση ενός προβλήματος γραμμικού προγραμματισμού.
Για να διασφαλιστεί ότι η λύση σε ένα πρόβλημα γραμμικού προγραμματισμού είναι όσο το δυνατόν ακριβέστερη και σωστή, πολλοί παραγγέλνουν ανέξοδα δοκιμαστικές εργασίες σε αυτόν τον ιστότοπο. Μπορείτε να διαβάσετε περισσότερες λεπτομέρειες (τρόπος υποβολής αιτήματος, τιμές, προθεσμίες, τρόποι πληρωμής) στη σελίδα Αγορά δοκιμαστικής εργασίας για γραμμικό προγραμματισμό...
Η λύση του προβλήματος
Πρότυπο κτίριο
Έστω και συμβολίζουμε τον αριθμό των κατασκευασμένων προϊόντων του 1ου και του 2ου τύπου.
Στη συνέχεια, περιορισμοί πόρων:
Επιπλέον, σύμφωνα με το νόημα της εργασίας
Η συνάρτηση στόχος του οικονομομαθηματικού μοντέλου, που εκφράζει τα έσοδα από τις πωλήσεις:
Παίρνουμε το ακόλουθο οικονομικό και μαθηματικό μοντέλο:
Κατασκευή του τομέα των εφικτών λύσεων
Ας λύσουμε το πρόβλημα γραμμικού προγραμματισμού που προκύπτει γραφικά:
Για να κατασκευάσουμε μια περιοχή με εφικτές λύσεις, κατασκευάζουμε οριακές γραμμές που αντιστοιχούν σε αυτές τις ανισότητες στο σύστημα συντεταγμένων:
Ας βρούμε τα σημεία από τα οποία περνούν οι ευθείες:
Η λύση σε κάθε ανισότητα του συστήματος περιορισμού ZLP είναι ένα μισό επίπεδο που περιέχει την οριακή γραμμή και βρίσκεται στη μία πλευρά της.
Για να ορίσετε ένα ημιεπίπεδο, πάρτε οποιοδήποτε σημείο, για παράδειγμα, που δεν ανήκει στην ευθεία (1) και αντικαταστήστε τις συντεταγμένες (0;0) στην αντίστοιχη ανισότητα. Επειδή η ανισότητα είναι αληθής:
Η περιοχή λύσης της αντίστοιχης 1ης ανισότητας αντιστοιχεί στο αριστερό μισό επίπεδο
Ας πάρουμε οποιοδήποτε σημείο, για παράδειγμα, που δεν ανήκει στην ευθεία (2), και ας αντικαταστήσουμε τις συντεταγμένες (0;0) στην αντίστοιχη ανισότητα. Επειδή η ανισότητα είναι αληθής:
Ας πάρουμε οποιοδήποτε σημείο, για παράδειγμα, που δεν ανήκει στη γραμμή (3) και ας αντικαταστήσουμε τις συντεταγμένες (0;0) στην αντίστοιχη ανισότητα. Επειδή η ανισότητα είναι αληθής:
Η περιοχή λύσης της αντίστοιχης 2ης ανισότητας αντιστοιχεί στο αριστερό ημιεπίπεδο
Η περιοχή των εφικτών λύσεων είναι το σχήμα.
Εύρεση λύσης στο πρόβλημα LP
Κατασκευάζουμε ένα διάνυσμα του οποίου οι συντεταγμένες είναι ανάλογες με τους συντελεστές της αντικειμενικής συνάρτησης. Εδώ είναι ο συντελεστής αναλογικότητας.
Σχεδιάστε μια γραμμή στάθμης κάθετη στο κατασκευασμένο διάνυσμα.
Μετακινούμε τη γραμμή επιπέδου προς την κατεύθυνση του διανύσματος έτσι ώστε να αγγίζει την περιοχή των εφικτών λύσεων στο ακραίο σημείο. Η λύση στο μέγιστο είναι το σημείο , οι συντεταγμένες του οποίου βρίσκονται ως σημείο τομής των ευθειών (2) και (1).
Απάντηση
Έτσι, είναι απαραίτητο να παραχθούν 56 προϊόντα 1ου τύπου και 64 προϊόντα 2ου τύπου. Στην περίπτωση αυτή, τα έσοδα από την πώληση προϊόντων θα είναι μέγιστα και θα ανέρχονται σε 5104 χρηματικές μονάδες.
Η μέθοδος γραφικής λύσης, εάν ένα πρόβλημα με δύο μεταβλητές έχει γραμμικούς περιορισμούς και η αντικειμενική συνάρτηση είναι τετραγωνική, συζητείται αναλυτικά εδώ
Η σελίδα περιγράφει λεπτομερώς τη λύση ενός προβλήματος γραμμικού προγραμματισμού χρησιμοποιώντας τη μέθοδο simplex, επιπλέον, δείχνει την κατασκευή ενός προβλήματος διπλού γραμμικού προγραμματισμού και την εύρεση της λύσης του λύνοντας το άμεσο πρόβλημα.
Πρόβλημα μεταφοράς και πιθανή μέθοδος
Το πρόβλημα μεταφοράς, το μαθηματικό του μοντέλο και οι μέθοδοι επίλυσης εξετάζονται λεπτομερώς - εύρεση του σχεδίου αναφοράς με τη μέθοδο ελάχιστων στοιχείων και αναζήτηση της βέλτιστης λύσης με τη μέθοδο δυνητικού.
Κυρτός προγραμματισμός - γραφική μέθοδος
Δίνεται ένα παράδειγμα επίλυσης προβλήματος τετραγωνικού κυρτού προγραμματισμού με χρήση γραφικής μεθόδου.
Παράδειγμα 6.1.
Λύση:
Το πρόβλημα γραμμικού προγραμματισμού δίνεται σε τυπική μορφή και έχει λοιπόν δύο παραμέτρους σχεδιασμού
Είναι δυνατή η επίλυσή του με τη γεωμετρική μέθοδο.
Στάδιο 1: ( ODR ).
Θεωρήστε τον πρώτο περιορισμό, αντικαταστήστε το πρόσημο της ανισότητας με πρόσημο ίσου και εκφράστε τη μεταβλητή x2διά μέσου x1:
.
Ομοίως, προσδιορίζουμε τα σημεία για τους υπόλοιπους περιορισμούς του συστήματος και κατασκευάζουμε ευθείες από αυτές που αντιστοιχούν σε κάθε ανισότητα (Εικ. 1). Αριθμούμε τις γραμμές σύμφωνα με το προηγούμενο σχήμα.
Στάδιο 2: .
Ας ορίσουμε ημιεπίπεδα - λύσεις σε καθεμία από τις ανισώσεις.
Ας εξετάσουμε την πρώτη ανισότητα του συστήματος περιορισμών προβλήματος. Ας πάρουμε κάποιο σημείο (σημείο ελέγχου) που δεν ανήκει στην ευθεία που αντιστοιχεί σε αυτήν την ανισότητα, για παράδειγμα, το σημείο (0; 0). Ας το αντικαταστήσουμε με την υπό εξέταση ανισότητα:
Κατά την αντικατάσταση των συντεταγμένων του σημείου ελέγχου, η ανισότητα παραμένει έγκυρη. Κατά συνέπεια, το σύνολο των σημείων που ανήκουν σε αυτή τη γραμμή (καθώς η ανισότητα δεν είναι αυστηρή), καθώς και αυτά που βρίσκονται κάτω από αυτήν, θα είναι λύσεις στην υπό εξέταση ανισότητα (ας σημειώσουμε στο γράφημα (Εικ. 1) το μισό που βρέθηκε -επίπεδο με δύο βέλη που δείχνουν προς τα κάτω δίπλα στη γραμμή Εγώ ) .
Ομοίως προσδιορίζουμε τις λύσεις άλλων ανισώσεων και τις σημειώνουμε ανάλογα στο γράφημα. Ως αποτέλεσμα, το γράφημα θα μοιάζει με αυτό:
Στάδιο 3: .
Τα ευρεθέντα ημιεπίπεδα (λύσεις σε καθεμία από τις ανισότητες του συστήματος των περιορισμών) σχηματίζουν ένα πολύγωνο όταν τέμνονται ABCDEO, που είναι το ODD του υπό εξέταση προβλήματος.
Ρύζι. 1. Περιοχή εφικτών λύσεων στο πρόβλημα
Στάδιο 4:
Το διάνυσμα κλίσης δείχνει την κατεύθυνση μεγιστοποίησης της αντικειμενικής συνάρτησης. Ας προσδιορίσουμε τις συντεταγμένες του: τις συντεταγμένες του αρχικού του σημείου (σημείο εφαρμογής) – (0; 0), τις συντεταγμένες του δεύτερου σημείου:
Ας σχεδιάσουμε αυτό το διάνυσμα στο γράφημα (Εικ. 2).
Στάδιο 5: .
Ας εξετάσουμε την αντικειμενική συνάρτηση αυτού του προβλήματος:
.
Ας του δώσουμε κάποια αξία, για παράδειγμα, . Ας εκφράσουμε τη μεταβλητή x2διά μέσου x1:
.
Για να κατασκευάσουμε μια ευθεία γραμμή χρησιμοποιώντας αυτήν την εξίσωση, θα καθορίσουμε δύο αυθαίρετα σημεία, για παράδειγμα:
Ας κατασκευάσουμε μια ευθεία γραμμή που αντιστοιχεί στην αντικειμενική συνάρτηση (Εικ. 2).
Ρύζι. 2. Κατασκευή της συνάρτησης στόχου F(X) και του διανύσματος κλίσης C
Στάδιο 6: προσδιορίζοντας το μέγιστο της συνάρτησης στόχου.
Κίνηση ευθείας γραμμής φά(Χ) παράλληλα με τον εαυτό του προς την κατεύθυνση του διανύσματος κλίσης, προσδιορίζουμε το ακραίο σημείο (σημεία) του ODR. Σύμφωνα με το γράφημα (Εικ. 3), ένα τέτοιο σημείο είναι το σημείο C - το σημείο τομής των γραμμών Εγώ Και II .
Ρύζι. 3. Προσδιορισμός του μέγιστου σημείου της αντικειμενικής συνάρτησης F(X)
Ας προσδιορίσουμε τις συντεταγμένες του σημείου Γ, για το σκοπό αυτό, λύνουμε το ακόλουθο σύστημα γραμμικών εξισώσεων:
Ας αντικαταστήσουμε τις συντεταγμένες που βρέθηκαν στην αντικειμενική συνάρτηση και ας βρούμε τη βέλτιστη (μέγιστη) τιμή της:
Απάντηση:υπό δεδομένους περιορισμούς, τη μέγιστη τιμή της αντικειμενικής συνάρτησης φά(Χ)=24, που επιτυγχάνεται στο σημείο Γ, οι συντεταγμένες του οποίου x1=6, x2=4.
Παράδειγμα 6.2.Λύστε το πρόβλημα του γραμμικού προγραμματισμού χρησιμοποιώντας τη γεωμετρική μέθοδο:
Λύση:
Τα στάδια 1-3 είναι παρόμοια με τα αντίστοιχα στάδια της προηγούμενης εργασίας.
Στάδιο 4: κατασκευή ενός διανύσματος κλίσης.
Η κατασκευή του διανύσματος κλίσης πραγματοποιείται με τον ίδιο τρόπο όπως στο προηγούμενο πρόβλημα. Ας σχεδιάσουμε αυτό το διάνυσμα στο γράφημα (Εικ. 4). Ας σημειώσουμε επίσης σε αυτό το γράφημα με ένα βέλος την αντίθετη κατεύθυνση από το διάνυσμα της κλίσης - την κατεύθυνση ελαχιστοποίησης της αντικειμενικής συνάρτησης φά (Χ).
Στάδιο 5: κατασκευή μιας συνάρτησης άμεσου στόχου.
Κατασκευή άμεσης αντικειμενικής συνάρτησης φά(Χ) εκτελείται με τον ίδιο τρόπο όπως στο προηγούμενο πρόβλημα (το αποτέλεσμα κατασκευής φαίνεται στο Σχ. 4).
Ρύζι. 4. Κατασκευή της αντικειμενικής συνάρτησης F(x) και διανύσματος κλίσης C
Στάδιο 6: τον καθορισμό του βέλτιστου της συνάρτησης στόχου.
Κίνηση ευθείας γραμμής φά(Χ) παράλληλα με τον εαυτό του στην αντίθετη κατεύθυνση από το διάνυσμα κλίσης, προσδιορίζουμε το ακραίο σημείο (σημεία) του ODR. Σύμφωνα με το γράφημα (Εικ. 5), ένα τέτοιο σημείο είναι το σημείο Ο με συντεταγμένες (0; 0).
Ρύζι. 5. Προσδιορισμός του ελάχιστου σημείου της αντικειμενικής συνάρτησης
Αντικαθιστώντας τις συντεταγμένες του ελάχιστου σημείου στη συνάρτηση στόχο, προσδιορίζουμε τη βέλτιστη (ελάχιστη) τιμή της, η οποία είναι ίση με 0.
Απάντηση:κάτω από δεδομένους περιορισμούς, την ελάχιστη τιμή της αντικειμενικής συνάρτησης φά(Χ)=0, το οποίο επιτυγχάνεται στο σημείο O (0; 0).
Παράδειγμα 6.3.Λύστε το παρακάτω πρόβλημα γραμμικού προγραμματισμού χρησιμοποιώντας τη γεωμετρική μέθοδο:
Λύση:
Το υπό εξέταση πρόβλημα γραμμικού προγραμματισμού δίνεται σε κανονική μορφή, επιλέγουμε τις βασικές μεταβλητές Χ 1 Και Χ2 .
Ας συνθέσουμε έναν εκτεταμένο πίνακα και ας επιλέξουμε τις βασικές μεταβλητές χρησιμοποιώντας τη μέθοδο Jordan-Gauss Χ1 Και Χ 2 .
Πολλαπλασιάστε (στοιχείο προς στοιχείο) την πρώτη γραμμή με –3 και προσθέστε τη στη δεύτερη: 
.
Πολλαπλασιάστε τη δεύτερη γραμμή με:
.
Ας προσθέσουμε τη δεύτερη γραμμή στην πρώτη γραμμή:
.
Ως αποτέλεσμα, το σύστημα περιορισμών θα λάβει την ακόλουθη μορφή:
Ας εκφράσουμε τις βασικές μεταβλητές ως ελεύθερες:
Ας εκφράσουμε επίσης τη συνάρτηση στόχου με όρους ελεύθερων μεταβλητών, για να γίνει αυτό, αντικαθιστούμε τις λαμβανόμενες τιμές των βασικών μεταβλητών στη συνάρτηση προορισμού.
Ας γράψουμε το πρόβλημα γραμμικού προγραμματισμού που προκύπτει:
Δεδομένου ότι οι μεταβλητές Χ1 Και Χ2 μη αρνητικό, τότε το προκύπτον σύστημα περιορισμών μπορεί να γραφτεί με την ακόλουθη μορφή:
Τότε το αρχικό πρόβλημα μπορεί να γραφτεί ως εξής, ισοδύναμο με ένα τυπικό πρόβλημα γραμμικού προγραμματισμού:
Αυτό το πρόβλημα έχει δύο παραμέτρους σχεδιασμού, επομένως, μπορεί να λυθεί χρησιμοποιώντας τη γεωμετρική μέθοδο.
Στάδιο 1: κατασκευή ευθειών γραμμών που περιορίζουν την περιοχή των εφικτών λύσεων ( ODR ).
Ας εξετάσουμε το σύστημα περιορισμών του προβλήματος γραμμικού προγραμματισμού (για λόγους ευκολίας, αριθμούμε τις ανισότητες):
Ας κατασκευάσουμε ευθείες γραμμές που αντιστοιχούν σε κάθε ανισότητα (Εικ. 6). Αριθμούμε τις ευθείες γραμμές σύμφωνα με το προηγουμένως υιοθετημένο σχήμα.
Στάδιο 2: προσδιορισμός της λύσης σε καθεμία από τις ανισότητες του συστήματος των περιορισμών.
Χρησιμοποιώντας σημεία ελέγχου, προσδιορίζουμε ημιεπίπεδα - λύσεις σε καθεμία από τις ανισώσεις και τις σημειώνουμε στο γράφημα (Εικ. 6) χρησιμοποιώντας βέλη.
Στάδιο 3: προσδιορισμός του ODD ενός προβλήματος γραμμικού προγραμματισμού.
Τα ευρεθέντα ημιεπίπεδα (δηλαδή, λύσεις σε καθεμία από τις ανισότητες του συστήματος περιορισμών) δεν έχουν κοινή τομή (άρα οι λύσεις στην ανισότητα I γενικά έρχονται σε αντίθεση με τις υπόλοιπες ανισώσεις του συστήματος περιορισμών), επομένως, το σύστημα περιορισμών δεν είναι συνεπής και επομένως το πρόβλημα του γραμμικού προγραμματισμού δεν έχει λύση.
Ρύζι. 6. Τμήμα ενός εγγράφου MathCAD:
την κατασκευή μιας περιοχής με εφικτές λύσεις σε ένα πρόβλημα
Απάντηση:Το υπό εξέταση πρόβλημα γραμμικού προγραμματισμού δεν έχει λύση λόγω της ασυνέπειας του συστήματος των περιορισμών.
Εάν, μετά την αντικατάσταση των συντεταγμένων του σημείου ελέγχου στην ανισότητα, η σημασία του παραβιάζεται, τότε η λύση αυτής της ανισότητας είναι ένα μισό επίπεδο που δεν περιέχει αυτό το σημείο (δηλαδή, βρίσκεται στην άλλη πλευρά της γραμμής).
Η κατεύθυνση αντίθετη από το διάνυσμα κλίσης αντιστοιχεί στην κατεύθυνση ελαχιστοποίησης της αντικειμενικής συνάρτησης.
Οι γραφικές μέθοδοι συνδέονται κυρίως με τη γεωμετρική αναπαράσταση της συναρτησιακής εξάρτησης χρησιμοποιώντας γραμμές σε ένα επίπεδο. Τα γραφήματα χρησιμοποιούνται για τη γρήγορη εύρεση της τιμής των συναρτήσεων με βάση την αντίστοιχη τιμή ορίσματος, για την οπτική εμφάνιση λειτουργικών εξαρτήσεων.
Στην οικονομική ανάλυση χρησιμοποιούνται σχεδόν όλοι οι τύποι γραφημάτων: γραφήματα σύγκρισης, διαγράμματα χρονοσειρών, καμπύλες κατανομής, γραφήματα πεδίων συσχέτισης, στατιστικά χαρτογράμματα. Τα διαγράμματα σύγκρισης είναι ιδιαίτερα διαδεδομένα στην ανάλυση - για τη σύγκριση δεικτών αναφοράς με προγραμματισμένους, προηγούμενες περιόδους και κορυφαίες επιχειρήσεις εγχώριων ή ξένων επιχειρήσεων. Για την οπτική απεικόνιση της δυναμικής των οικονομικών φαινομένων (και στην ανάλυση πρέπει να ασχολείται κανείς πολύ συχνά με χρονοσειρές), χρησιμοποιούνται διαγράμματα χρονοσειρών.
Χρησιμοποιώντας ένα πλέγμα συντεταγμένων, κατασκευάζονται επίσης γραφήματα της εξάρτησης, για παράδειγμα, του επιπέδου του κόστους από τον όγκο των παραγόμενων και πωλούμενων προϊόντων. γραφήματα στα οποία μπορείτε να απεικονίσετε συσχετίσεις μεταξύ δεικτών. Σε ένα σύστημα αξόνων συντεταγμένων, η εικόνα δείχνει την επίδραση διαφόρων παραγόντων σε έναν συγκεκριμένο δείκτη.
Η γραφική μέθοδος χρησιμοποιείται ευρέως για τη μελέτη διαδικασιών παραγωγής, οργανωτικών δομών, διαδικασιών προγραμματισμού κ.λπ. Για παράδειγμα, για την ανάλυση της αποτελεσματικότητας της χρήσης εξοπλισμού παραγωγής, κατασκευάζονται γραφήματα υπολογισμού, συμπεριλαμβανομένων γραφημάτων πολλαπλών παραγόντων.
Σημείωση: κάθε κύκλος θεωρείται μία από τις κορυφές του γραφήματος. ο αριθμός στον άνω τομέα κάθε κορυφής σημαίνει τον αύξοντα αριθμό της· Με βάση τους αριθμούς δύο γειτονικών κορυφών, σχηματίζεται ο κώδικας εργασίας. Ο αριθμός στον κάτω τομέα κάθε κορυφής είναι ο σειριακός αριθμός της προηγούμενης κορυφής και η γραμμή που συνδέει αυτές τις δύο κορυφές σημαίνει μια συγκεκριμένη εργασία. Κάτω από τη γραμμή είναι η προγραμματισμένη διάρκεια αυτής της εργασίας. ο αριθμός στον αριστερό τομέα κάθε κορυφής σημαίνει τη συνολική διάρκεια όλων των προηγούμενων εργασιών, ο αριθμός στον δεξιό τομέα διαφέρει από τον αριθμό στον αριστερό κατά το ποσό του αποθεματικού (χρονοαπόθεμα). Έτσι, για κορυφές που βρίσκονται στην κρίσιμη διαδρομή, οι αριθμοί στον αριστερό και τον δεξιό τομέα της κορυφής συμπίπτουν, καθώς το χρονικό περιθώριο είναι 0.
Σε ένα μαθηματικά επισημοποιημένο σύστημα ανάλυσης, σχεδιασμού και διαχείρισης, τα δικτυακά διαγράμματα καταλαμβάνουν ιδιαίτερη θέση. Παρέχουν μεγάλη οικονομική επίδραση στην κατασκευή και εγκατάσταση βιομηχανικών και άλλων επιχειρήσεων.
Το διάγραμμα δικτύου (Εικ. 6.1) σας επιτρέπει να εντοπίσετε τα πιο σημαντικά από ολόκληρο το συγκρότημα έργων, αυτά που βρίσκονται στην κρίσιμη διαδρομή, και να συγκεντρώσετε τους κύριους πόρους των κατασκευαστικών οργανισμών σε αυτά, να δημιουργήσετε σχέσεις μεταξύ διαφόρων εξειδικευμένων οργανισμών και να συντονίσετε τους δουλειά. Οι δραστηριότητες στο κρίσιμο μονοπάτι απαιτούν τη μεγαλύτερη αναμονή για την άφιξη του επόμενου συμβάντος. Στο στάδιο της επιχειρησιακής ανάλυσης και διαχείρισης, το χρονοδιάγραμμα του δικτύου καθιστά δυνατή την αποτελεσματική παρακολούθηση της προόδου της κατασκευής και τη λήψη έγκαιρων μέτρων για την εξάλειψη πιθανών καθυστερήσεων στις εργασίες.
Η χρήση διαγραμμάτων δικτύου για ανάλυση, σχεδιασμό και διαχείριση παρέχει, όπως δείχνουν πολλά παραδείγματα, μείωση του χρόνου κατασκευής κατά 20-30% και αύξηση της παραγωγικότητας της εργασίας κατά 15-20%.
Κατά την απευθείας ανάλυση σε εργοτάξια, η χρήση υλικών σχεδιασμού και διαχείρισης δικτύου συμβάλλει στον σωστό εντοπισμό των λόγων που επηρεάζουν την πρόοδο της κατασκευής και στον προσδιορισμό των επιχειρήσεων που δεν διασφαλίζουν την ολοκλήρωση των εργασιών που τους έχουν ανατεθεί ή την παράδοση του εξοπλισμού εντός των προθεσμιών που ορίζει το χρονοδιάγραμμα.
Η ανάπτυξη ενός χρονοδιαγράμματος δικτύου στην κατασκευή πραγματοποιείται παρουσία: προτύπων για τη διάρκεια της κατασκευής και την περίοδο έναρξης λειτουργίας ενός αντικειμένου ή συγκροτήματος αντικειμένων, εκτιμήσεις σχεδιασμού, ένα έργο οργάνωσης κατασκευής και παραγωγής εργασίας, τυπικών τεχνολογικών χαρτών , τρέχοντα πρότυπα για το κόστος εργασίας, τα υλικά και τη λειτουργία μηχανών. Επιπλέον, κατά την κατάρτιση ενός χρονοδιαγράμματος, χρησιμοποιείται η εμπειρία εκτέλεσης μεμονωμένων εργασιών, καθώς και δεδομένα σχετικά με την παραγωγική βάση των οργανισμών κατασκευής και εγκατάστασης.
Με βάση όλα αυτά τα δεδομένα, καταρτίζεται ένας πίνακας εργασιών και πόρων, όπου στην τεχνολογική ακολουθία παραγωγής εργασίας τα χαρακτηριστικά τους, όγκος, ένταση εργασίας σε ανθρωποημέρες, εκτελεστής (οργάνωση και ομάδα), αριθμός εργαζομένων, βάρδιες, ανάγκη Αναφέρονται οι μηχανισμοί και τα υλικά, οι πηγές προμήθειας τους, η συνολική διάρκεια των εργασιών σε ημέρες, καθώς και η προηγούμενη εργασία, μετά την ολοκλήρωση της οποίας μπορεί να ξεκινήσει η εργασία. Με βάση τους δείκτες ενός τέτοιου πίνακα, προετοιμάζεται ένα διάγραμμα δικτύου, το οποίο μπορεί να έχει διαφορετικούς βαθμούς λεπτομέρειας ανάλογα με το υιοθετημένο σχήμα παραγωγής.
διαχείριση εργασίας και επίπεδο διαχείρισης· Εκτός από το γενικό πρόγραμμα, οι ερμηνευτές αναπτύσσουν ένα πρόγραμμα για την εργασία που εκτελούν.
Τα κύρια στοιχεία ενός διαγράμματος δικτύου: συμβάν, εργασία, αναμονή, εξάρτηση.
Κατά την ανάλυση της προόδου κατασκευής ενός αντικειμένου, θα πρέπει να διαπιστωθεί εάν το χρονοδιάγραμμα του δικτύου έχει σχεδιαστεί σωστά, εάν η κρίσιμη διαδρομή δεν έχει υπερεκτιμηθεί, εάν έχουν ληφθεί υπόψη όλες οι δυνατότητες μείωσής του κατά τη βελτιστοποίηση του χρονοδιαγράμματος, εάν οποιαδήποτε εργασία μπορεί να εκτελεστεί παράλληλα ή ο χρόνος που αφιερώνεται σε αυτές μπορεί να μειωθεί αυξάνοντας τα μέσα μηχανοποίησης κ.λπ. Αυτό είναι ιδιαίτερα σημαντικό σε περιπτώσεις όπου η διάρκεια της εργασίας σύμφωνα με το χρονοδιάγραμμα δεν εξασφαλίζει την έγκαιρη ολοκλήρωση της κατασκευής.
Το κύριο υλικό για τον προγραμματισμό δικτύου που χρησιμοποιείται στην ανάλυση είναι οι πληροφορίες σχετικά με την πρόοδο των εργασιών σύμφωνα με το χρονοδιάγραμμα, το οποίο συνήθως καταρτίζεται τουλάχιστον μία φορά τη δεκαετία. Ως παράδειγμα, δίνεται ένας χάρτης της εργασίας και πληροφορίες σχετικά με την πρόοδο των εργασιών σε ένα κατασκευαστικό έργο που εκτελείται σύμφωνα με το χρονοδιάγραμμα του δικτύου (Πίνακας 6.1). Σύμφωνα με τον χάρτη, κρίσιμες εργασίες πραγματοποιήθηκαν στις αρχές του μήνα πριν από το χρονοδιάγραμμα, αλλά στη συνέχεια η εγκατάσταση δοκών γερανού κατά μήκος της σειράς Β αφέθηκε να καθυστερήσει και οι επόμενες εργασίες - εγκατάσταση δοκών γερανού κατά μήκος της σειράς Α - ολοκληρώθηκαν μια μέρα πίσω από το πρόγραμμα.
Η βελτιστοποίηση των χρονοδιαγραμμάτων του δικτύου πραγματοποιείται στο στάδιο του σχεδιασμού με μείωση της κρίσιμης διαδρομής, δηλαδή ελαχιστοποίηση του χρόνου κατασκευής σε δεδομένα επίπεδα πόρων, ελαχιστοποίηση του επιπέδου κατανάλωσης υλικών, εργατικών και οικονομικών πόρων σε καθορισμένες προθεσμίες για την ολοκλήρωση των κατασκευαστικών εργασιών. Είναι επίσης δυνατή μια μικτή προσέγγιση: για ένα μέρος της εργασίας (πιο ακριβό) - ελαχιστοποίηση του επιπέδου κατανάλωσης πόρων με καθορισμένη προθεσμία για την ολοκλήρωση της εργασίας, για το άλλο - ελαχιστοποίηση της προθεσμίας για ένα σταθερό επίπεδο πόρων.
Η επίλυση προβλημάτων βελτιστοποίησης διευκολύνεται σε μεγάλο βαθμό από την παρουσία πακέτων προγραμμάτων εφαρμογών (APP) προσαρμοσμένων για την προετοιμασία βέλτιστων διαγραμμάτων δικτύου σε έναν υπολογιστή.
Στην ξένη πρακτική της ανάλυσης συστημάτων, είναι ευρέως διαδεδομένη μια γραφο-μαθηματική μέθοδος που ονομάζεται «δέντρο αποφάσεων». Η ουσία αυτής της μεθόδου είναι η εξής.
Μέσα από μια προκαταρκτική εκτίμηση των αναγκών, μια προκαταρκτική ανάλυση των πιθανών οργανωτικών, τεχνικών ή τεχνολογικών συνθηκών, σκιαγραφούνται όλες οι πιθανές επιλογές για την επίλυση ενός δεδομένου προβλήματος. Αναπτύχθηκε για πρώτη φορά
| | Ασκηση | | Πληροφορίες | Απόθεμα χρόνου για εργασία | Αριθμός ty |
|||||||
| Ονομα έργα | κρυπτογράφημα | ημερομηνία ξεκίνησε | ημερομηνία αφού τελειώσει | σχεδιασμένος συνεχίζεται | Σχετικά με Αποθεματικό χρόνος | % εκείνοι- | απαιτούμενος χρόνος για | στο τάξη | πραγματική ημερομηνία | εύρεση ρεύμα | δεν βρίσκεται | κρατήστε χρόνο με |
| | έργα | έργα (σχέδιο) | νια έργα (σχέδιο) | κάτοικος ας, ημέρες | μου | ουα έτοιμος ness | αφού τελειώσει νια έργα, ημέρες | zader γυναίκες | αφού τελειώσει νια έργα | στην κρίσιμη διαδρομή | αα κρίσιμη διαδρομή | αρχή μήνα, ημέρες |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| Ανάπτυξη του εδάφους | 1-2 | 1/IV | 6/IV | 5 | 0 | 100 | - | - | 6/IV | ¦- | - | - |
| Σκυροδέτηση θεμελίων λεβήτων | 2-3 | 7/IV | 17/1V | 9 | 0 | 100 | 14/IV | 2 | 2 |
|||
| Σκυροδέτηση θεμελίων σύμφωνα με τη σειρά Α | 2-4 | 7/IV | 14/1V | 7 | 2 | 100 | 14/IV | | | |
||
| Το ίδιο και για τη σειρά Β | 2-5 | 7/IV | 14/IV | 7 | 2 | 100 | - | - | 14/IV | | | |
| Συσκευή διανομής σωλήνων | 6-18 | 18/IV | 21/IV | 4 | 19 | 100 | - | - | 29/IV | -7 |
||
| Συσκευή επίχωσης | 6-7 | 18/IV | 19/IV | 2 | 0 | 100 | 17/IV | 2 | 2 |
|||
| Εγκατάσταση προκατασκευασμένων κατασκευών από σκυρόδεμα | | | | | | | | | | | | |
| lonn: κατά μήκος της σειράς Β | 7-8 | 20/IV | 22/IV | 3 | 1 | 100 | - | - | 22/IV | _ | - | - |
| κατά μήκος της σειράς Α | 7-9 | 20/IV | 22/IV | 3 | 1 | 100 | - | - | 22/IV | - | - | - |
Κατασκευή σιδηροτροχιών γερανού και εγκατάσταση πύργου γερανού 7-10
Τοποθέτηση πλαισίων στήριξης στη βάση για εξοπλισμό 7-16 Εγκατάσταση δοκών γερανού:
κατά μήκος της σειράς Β 8-11
20/IV 24/IV 4
20/IV 24/IV 4
24/IV 25/IV 2
κατά μήκος της σειράς Α 10-12 25/IV 26/IV
Τοποθέτηση πρώτου μέρους δοκών και πλακών κάλυψης 12-13 27/IV 4/V
Εγκατάσταση τροχιών γερανού για γέφυρα lt;3 γερανοί 12-14 27/IV 3/V
| 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 0 | 100 | - | - | 22/IV | 1 | - | 1 |
| 14 | 100. | - | - | 29/IV | - | -5 | - |
| 1 | 100 | πίσω- | 27/IV | -2 |
27/IV -1
υποστήριξη με προμήθεια κατασκευών από οπλισμένο σκυρόδεμα
- 100 -
διευρυμένες επιλογές. Στη συνέχεια, καθώς εισάγονται πρόσθετες προϋποθέσεις, καθεμία από αυτές χωρίζεται σε έναν αριθμό επιλογών. Μια γραφική αναπαράσταση αυτών των επιλογών σας επιτρέπει να εξαιρέσετε τις λιγότερο κερδοφόρες και να επιλέξετε την πιο αποδεκτή.
Αυτή η μέθοδος μπορεί να χρησιμοποιηθεί για τον καθορισμό της σειράς επεξεργασίας ορισμένων εξαρτημάτων σε πολλά μηχανήματα, προκειμένου να ελαχιστοποιηθεί ο συνολικός χρόνος επεξεργασίας. κατά τον καθορισμό του μεγέθους των πόρων για την ελαχιστοποίηση του συνολικού κόστους παραγωγής· κατά την κατανομή των επενδύσεων κεφαλαίου και άλλων πόρων μεταξύ βιομηχανικών εγκαταστάσεων· κατά την επίλυση προβλημάτων μεταφοράς και άλλων προβλημάτων.
Η γραφική μέθοδος για την επίλυση του ZLP βασίζεται στις δηλώσεις που δίνονται στην παράγραφο 2.1. Σύμφωνα με το Θεώρημα 2, η βέλτιστη λύση βρίσκεται στην κορυφή του πεδίου των εφικτών λύσεων και επομένως για να λυθεί το ZLP είναι να βρεθεί η κορυφή του πεδίου των εφικτών λύσεων, οι συντεταγμένες του οποίου δίνουν τη βέλτιστη τιμή της αντικειμενικής συνάρτησης.
Η γραφική μέθοδος χρησιμοποιείται για την επίλυση μιας περιορισμένης κατηγορίας προβλημάτων με δύο μεταβλητές, μερικές φορές με τρεις μεταβλητές. Πρέπει να σημειωθεί ότι για τρεις μεταβλητές αυτή η περιοχή δεν είναι αρκετά σαφής.
Αλγόριθμος για τη γραφική μέθοδο επίλυσης προβλημάτων
Θα εξετάσουμε την υλοποίηση της γραφικής μεθόδου για την επίλυση του ZLP χρησιμοποιώντας παραδείγματα.
Παράδειγμα 2.2.1. Λύστε το ZLP γραφικά:
(2.2.1)
Μέγιστη z=Χ 1 + 4Χ 2 (2.2.2)
Λύση.Για να κατασκευάσουμε μια περιοχή εφικτών λύσεων, η οποία αποτελείται από την τομή ημιεπίπεδων που αντιστοιχούν σε κάθε ανισότητα του συστήματος περιορισμών (2.2.1), γράφουμε τις εξισώσεις των οριακών ευθειών:
μεγάλο 1: Χ 1 + 5Χ 2 = 5; μεγάλο 2: Χ 1 + Χ 2 = 6; μεγάλο 3: 7Χ 1 + Χ 2 = 7.
μεγάλο 1 στη φόρμα (2.2.3.) διαιρούμε και τα δύο μέρη του με 5: 
. Έτσι, ευθεία μεγάλο 1 τομές στον άξονα Ω 1 5 μονάδες, στον άξονα Ω 2 1 μονάδα. Ομοίως έχουμε για μεγάλο 2:
Και μεγάλο 3:
.
Για να προσδιορίσετε ημιεπίπεδα που πληρούν τους περιορισμούς του συστήματος (2.2.1), πρέπει να αντικαταστήσετε τις συντεταγμένες οποιουδήποτε σημείου που δεν βρίσκεται στην οριακή γραμμή με τους περιορισμούς. Εάν λάβουμε μια αληθινή ανισότητα, τότε όλα τα σημεία από αυτό το ημιεπίπεδο είναι λύσεις σε αυτήν την ανισότητα. Διαφορετικά, επιλέξτε ένα άλλο μισό επίπεδο.
Έτσι, το πρώτο και το δεύτερο επιθυμητό ημιεπίπεδο βρίσκονται στην αντίθετη κατεύθυνση από την αρχή των συντεταγμένων (0 – 5 0 
- 5; 7 0 + 0 
7), και το δεύτερο - προς την αρχή των συντεταγμένων (0 + 0 
6). Η περιοχή των εφικτών λύσεων στο Σχήμα 2.2.1 είναι σκιασμένη.
Εικόνα 2.2.1 – Περιοχή εφικτών λύσεων
Για να βρείτε το βέλτιστο σχέδιο, το οποίο θα βρίσκεται στην κορυφή του πολυγώνου λύσης, πρέπει να κατασκευάσετε ένα διάνυσμα κατευθύνσεων 
=(Με 1 ,Με 2), το οποίο υποδεικνύει την κατεύθυνση της μεγαλύτερης αύξησης στην αντικειμενική συνάρτηση z=Με 1 Χ 1 +Με 2 Χ 2 .
Σε αυτό το πρόβλημα, το διάνυσμα κατεύθυνσης 
= (1, 4): ξεκινά από το σημείο ΣΧΕΤΙΚΑ ΜΕ(0,0) και τελειώνει στο σημείο Ν(1, 4).
Στη συνέχεια, κατασκευάζουμε μια ευθεία γραμμή που διέρχεται από την περιοχή των εφικτών λύσεων, κάθετη στο διάνυσμα, και ονομάζεται γραμμή επιπέδου στόχου λειτουργίες. Μετακινούμε τη γραμμή επιπέδου προς την κατεύθυνση του διανύσματος σε περίπτωση μεγιστοποίησης της αντικειμενικής συνάρτησης zκαι προς την αντίθετη κατεύθυνση, σε περίπτωση ελαχιστοποίησης z, μέχρι την τελευταία διασταύρωση με την περιοχή των εφικτών λύσεων. Ως αποτέλεσμα, το σημείο ή τα σημεία προσδιορίζονται όπου η αντικειμενική συνάρτηση φτάνει σε μια ακραία τιμή ή διαπιστώνεται το απεριόριστο της αντικειμενικής συνάρτησης zστο σύνολο των λύσεων του προβλήματος.
Έτσι, το μέγιστο σημείο της αντικειμενικής συνάρτησης zείναι το σημείο ΕΝΑδιασταυρώσεις γραμμών μεγάλο 2 και μεγάλο 3 .
Να υπολογιστεί η βέλτιστη τιμή της αντικειμενικής συνάρτησης z βρείτε τις συντεταγμένες του σημείουΕΝΑ . Από το σημείοΕΝΑ είναι το σημείο τομής των ευθειώνμεγάλο 2 καιμεγάλο 3, τότε οι συντεταγμένες του ικανοποιούν ένα σύστημα εξισώσεων που αποτελείται από τις εξισώσεις των αντίστοιχων οριακών γραμμών:
Το θέμα λοιπόνΕΝΑ έχει συντεταγμένεςΧ 1 =1/6, Χ 2 = 35/6.
Για να υπολογίσετε τη βέλτιστη τιμή της αντικειμενικής συνάρτησης, πρέπει να αντικαταστήσετε τις συντεταγμένες του σημείου σε αυτήνΕΝΑ .
Αντικατάσταση των συντεταγμένων του σημείουΕΝΑ στην αντικειμενική συνάρτηση (2.4), λαμβάνουμε
Μέγιστη z = 1/6 + 4·(35/6) = 47/2.
Παράδειγμα 2.2.2. Κατασκευάστε στο επίπεδο την περιοχή των εφικτών λύσεων του συστήματος γραμμικών ανισώσεων (2.2.4) και βρείτε τις μεγαλύτερες και μικρότερες τιμές της αντικειμενικής συνάρτησης (2.2.5):
(2.2.4)
z= –2Χ 1 –Χ 2 (2.2.5)
Λύση.Για να κατασκευάσουμε μια περιοχή εφικτών λύσεων, η οποία αποτελείται από τη τομή ημιεπίπεδων που αντιστοιχεί σε κάθε ανισότητα του συστήματος περιορισμών (2.2.4), γράφουμε τις εξισώσεις των οριακών γραμμών:
μεγάλο 1: 4Χ 1 – Χ 2 = 0; μεγάλο 2: Χ 1 + 3Χ 2 = 6; μεγάλο 3: Χ 1 – 3Χ 2 = 6; μεγάλο 4: Χ 2 = 1.
Ευθεία μεγάλοΤο 1 διέρχεται από το σημείο με συντεταγμένες (0;0). Για να το κατασκευάσουμε, εκφράζουμε Χ 2 έως Χ 1: Χ 2 = 4Χ 1 . Ας βρούμε ένα άλλο σημείο από το οποίο διέρχεται η γραμμή μεγάλο 1, για παράδειγμα (1;4). Μέσα από το σημείο με συντεταγμένες (0;0) και το σημείο με συντεταγμένες (1;4) σχεδιάζουμε μια ευθεία γραμμή μεγάλο 1 .
Να μειωθεί η εξίσωση μιας ευθείας γραμμής μεγάλο 2 στη μορφή σε τμήματα στους άξονες (2.2.3), διαιρούμε και τα δύο μέρη του με το 6: 
. Έτσι, ευθεία μεγάλο 2 τομές στον άξονα Ω 1 6 μονάδες, στον άξονα Ω 2 - 2 μονάδες. Ομοίως έχουμε για μεγάλο 3:
και Άμεση μεγάλο 4 παράλληλα με τον άξονα Ω 1 και διέρχεται από το σημείο με συντεταγμένες (0;1) .
Για τον προσδιορισμό ημιεπίπεδων που πληρούν τους περιορισμούς του συστήματος (2.2.4), είναι απαραίτητο να αντικατασταθούν οι συντεταγμένες οποιουδήποτε σημείου που δεν βρίσκεται στην οριακή γραμμή με τους περιορισμούς. Λόγω περιορισμώνΧ 1 
0,
Χ 2 
0, η περιοχή των αποδεκτών λύσεων του ZLP βρίσκεται στο πρώτο τέταρτο του επιπέδου συντεταγμένων.
ΣΧΕΤΙΚΑ ΜΕ 
η περιοχή των εφικτών λύσεων στο σχήμα 2.2.2 είναι σκιασμένη.
Εικόνα 2.2.2 – Περιοχή εφικτών λύσεων
Ας κατασκευάσουμε ένα διάνυσμα κατευθύνσεων 
= (–2,–1). Στη συνέχεια, χτίζουμε μια γραμμή επιπέδου κάθετη στο διάνυσμα .
Για να βρούμε τη μεγαλύτερη τιμή της αντικειμενικής συνάρτησης, μετακινούμε τη γραμμή επιπέδου προς την κατεύθυνση του διανύσματος μέχρι την τελευταία τομή με την περιοχή των εφικτών λύσεων. Έτσι, το μέγιστο σημείο της αντικειμενικής συνάρτησης zείναι το σημείο ΕΝΑ(διασταύρωση γραμμών μεγάλο 1 και μεγάλο 2).
Να υπολογιστεί η βέλτιστη τιμή της αντικειμενικής συνάρτησης zβρείτε τις συντεταγμένες του σημείου ΕΝΑ. Από το σημείο ΕΝΑείναι το σημείο τομής των ευθειών μεγάλο 1 και μεγάλο 2, τότε οι συντεταγμένες του ικανοποιούν ένα σύστημα εξισώσεων που αποτελείται από τις εξισώσεις των αντίστοιχων οριακών γραμμών:
Το θέμα λοιπόνΕΝΑ έχει συντεταγμένεςΧ 1 =6/13, Χ 2 = 24/13.
Αντικατάσταση των συντεταγμένων του σημείουΕΝΑ στην αντικειμενική συνάρτηση (2.2.5), λαμβάνουμε τη βέλτιστη τιμή της αντικειμενικής συνάρτησης
Μέγιστη z= – 2·(6/13) – (24/13) = – 36/13.
Για να βρούμε τη μικρότερη τιμή της αντικειμενικής συνάρτησης, μετακινούμε τη γραμμή επιπέδου στην αντίθετη κατεύθυνση από το διάνυσμα μέχρι την τελευταία τομή με την περιοχή των εφικτών λύσεων. Στην περίπτωση αυτή, η αντικειμενική συνάρτηση είναι απεριόριστη στην περιοχή των εφικτών λύσεων, δηλ. Το ZLP δεν έχει ελάχιστο.
Ως αποτέλεσμα της απόφασης της ΣΔΙΤ, είναι δυνατές οι ακόλουθες περιπτώσεις:
Η αντικειμενική συνάρτηση φτάνει τη βέλτιστη τιμή της σε μία μόνο κορυφή του πολυγώνου λύσης.
Η αντικειμενική συνάρτηση φτάνει τη βέλτιστη τιμή της σε οποιοδήποτε σημείο στην άκρη του πολυγώνου λύσης (το ZLP έχει εναλλακτικά σχέδια αναφοράς με τις ίδιες τιμές z );
Το PLP δεν έχει βέλτιστα σχέδια.
Η ZLP έχει ένα βέλτιστο σχέδιο στην περίπτωση απεριόριστης γκάμα εφικτών λύσεων.
