Der optimale Wert der Zielfunktion wird aufgerufen. Lösung des Problems, das Minimum der Zielfunktion zu finden

27.09.2019 | Essen und Trinken

Lab Nr. 1 Probleme der linearen Programmierung lösen

Ziel der Arbeit Erwerb von Fähigkeiten zur Problemlösung Lineares Programmieren grafische, simplex-Methode und Mittel von Excel.

Die Aufgabe der linearen Programmierung besteht darin, zu lernen, wie man die maximalen oder minimalen Werte einer linearen Funktion bei Vorhandensein linearer Einschränkungen findet. Eine Zielfunktion ist eine Funktion, deren Maximal- oder Minimalwert gefunden wird. Der Satz von Variablenwerten, bei dem die maximalen oder minimalen Werte erreicht werden, wird als optimale Lösung (optimaler Plan) bezeichnet, jeder andere Satz von Werten, der die Einschränkungen erfüllt, wird als akzeptable Lösung (durchführbarer Plan) bezeichnet.

Geometrische Lösungsmethode ICH Betrachten Sie Probleme der linearen Programmierung anhand eines Beispiels.

Beispiel. Finden Sie den Maximalwert ZielfunktionL=2X 1 +2X 2 unter gegebenen Randbedingungen

Lösung. Konstruieren wir den Lösungsbereich des Constraint-Systems, indem wir die Vorzeichen von Ungleichungen in die Vorzeichen von exakten Gleichheiten ändern:

l 1: 3X 1 -2X 2 +6=0,

l 2: 3X 1 +X 2 -3=0,

l 3:X 1 -3=0.

DMIT

2 0 1 3 X 1

(l 1) (l 3)

Gerade l 1 teilt die Ebene X UM bei in zwei Halbebenen, von denen eine ausgewählt werden muss, die die erste Ungleichung in System (3) erfüllt. Dazu nehmen wir t. UM(0; 0) und in die Ungleichung einsetzen. Wenn dies zutrifft, müssen Sie die Halbebene von der geraden Linie abschattieren, in der die sogenannte. UM(0; 0). Machen Sie dasselbe mit geraden Linien. l 2 und l 3 . Der Lösungsbereich der Ungleichungen (3) ist ein Vieleck ABCD. Für jeden Punkt der Ebene die Funktion L nimmt einen festen Wert an L=L 1 . Die Menge aller Punktströme ist eine Gerade L=C 1 X 1 +C 2 X 2 (in unserem Fall L=2X 1 +2X 2) senkrecht zum Vektor MIT(Mit 1 ;Mit 2) (MIT(2; 2)), die aus dem Ursprung hervorgehen. Wenn diese Linie in die positive Richtung des Vektors verschoben wird Mit, dann die Zielfunktion L wird zunehmen, andernfalls wird es abnehmen. Also in unserem Fall die Gerade beim Verlassen des Polygons ABCD Entscheidungen werden durchgehen IN(3; 7.5), und daher inkl. IN die Zielfunktion nimmt den Maximalwert an, d.h. L max =2-3+2-7,5=21. In ähnlicher Weise wird bestimmt, dass die Funktion den Minimalwert annimmt, d. h. D(1; 0) und L min=2-1+2-0=2.

Der Algorithmus des Simplex-Verfahrens zum Lösen eines linearen Programmierproblems ist wie folgt.

1. Das allgemeine Problem der linearen Programmierung wird auf ein kanonisches Problem reduziert (es gibt Gleichheitszeichen in den Nebenbedingungen), indem so viele Hilfsvariablen eingeführt werden, wie es Ungleichungen im Nebenbedingungssystem gibt.

2. Die Zielfunktion wird durch Basis- und Hilfsvariablen ausgedrückt.

3. Die erste Simplex-Tabelle wird kompiliert. In die Basis werden Variablen geschrieben, bezüglich derer das Restriktionssystem erlaubt ist (am besten Hilfsvariablen als Basisvariablen nehmen). Die erste Zeile der Tabelle listet alle Variablen auf und bietet eine Spalte für freie Mitglieder. In der letzten Zeile der Tabelle sind die Koeffizienten der Zielfunktion mit entgegengesetzten Vorzeichen eingetragen

4. Jedes Simplextableau gibt eine Lösung für das Problem der linearen Programmierung: Die freien Variablen sind gleich Null, die Basisvariablen sind jeweils gleich den freien Mitgliedern.

5. Das Optimalitätskriterium ist das Fehlen negativer Elemente in der letzten Zeile der Tabelle zur Lösung des Problems für das Maximum und positiver Elemente für das Minimum.

6. Um die Lösung zu verbessern, ist es notwendig, von einem Simplex-Tableau zu einem anderen zu wechseln. Dazu wird in der vorherigen Tabelle eine Schlüsselspalte gefunden, die dem kleinsten negativen Element in der letzten Zeile der Tabelle im Maximumproblem und dem größten positiven Koeffizienten im Minimumproblem entspricht. Finden Sie dann die Schlüsselzeile, die dem Mindestverhältnis freier Terme zu den entsprechenden positiven Elementen der Schlüsselspalte entspricht. Am Schnittpunkt der Schlüsselspalte und der Schlüsselreihe befindet sich das Schlüsselelement.

7. Wir beginnen mit dem Ausfüllen der nächsten Simplex-Tabelle, indem wir die Basis ausfüllen: Die Variable, die der Schlüsselzeile entspricht, wird von der Basis abgeleitet, und die Variable, die der Schlüsselspalte entspricht, wird an ihrer Stelle eingeführt. Die Elemente der früheren Schlüsselzeichenfolge werden erhalten, indem das frühere Element durch die Schlüsselzeichenfolge dividiert wird. Die Elemente der früheren Schlüsselspalte werden zu Nullen, mit Ausnahme des Schlüsselelements, das Eins ist. Alle anderen Elemente werden nach der Rechteckregel berechnet:

8. Simplex-Tabellen werden transformiert, bis ein optimaler Plan erhalten wird.

Beispiel. Finden Sie den Maximalwert einer Funktion
wenn die Variablen
das Beschränkungssystem erfüllen:

Lösung. 1. Einführung neuer Variablen
, mit deren Hilfe wir die Ungleichungen des Systems in Gleichungen umwandeln:

Wir ändern das Vorzeichen der Koeffizienten der Zielfunktion oder schreiben es in die Form
. Wir füllen die erste Simplextabelle aus, in die Nulllinie schreiben wir X 1 ,X 2 und (freie Koeffizienten). In Spalte Null X 3 ,X 4 ,X 5 und F. Wir füllen diese Tabelle gemäß dem erhaltenen Gleichungssystem und der transformierten Zielfunktion aus.

Wir überprüfen das Optimalitätskriterium, um den Maximalwert zu finden: In der letzten Zeile müssen alle Koeffizienten positiv sein. Ist dieses Kriterium nicht erfüllt, fahren wir mit der Erstellung der zweiten Tabelle fort.

2. Wir finden das Auflösungselement der ersten Tabelle wie folgt. Unter den Elementen der letzten Zeile wählen wir den absolut größten negativen Koeffizienten (dies ist -3) und die zweite Spalte wird als Auflösung akzeptiert. Wenn alle Koeffizienten einer Spalte nicht positiv sind, dann
.

Um die Auflösungszeile zu bestimmen, dividieren wir die freien Koeffizienten durch die entsprechenden Elemente der Auflösungsspalte und wählen das minimale Verhältnis, während wir keine negativen Koeffizienten nehmen. Wir haben
, die zweite Zeile ist zulässig. Der Schnittpunkt der zulässigen Zeile und Spalte ergibt das zulässige Element - dies ist 3.

3. Füllen Sie die zweite Simplextabelle aus. Variablen, an deren Schnittpunkt wir ein Auflösungselement erhalten, Austausch, d.h. Und . Wir ersetzen das aktivierende Element durch sein Inverses, d.h. auf der. Die Elemente der zulässigen Zeile und Spalte (mit Ausnahme des zulässigen Elements) werden durch das zulässige Element geteilt. In diesem Fall ändern wir das Vorzeichen der Koeffizienten der Auflösungsspalte.

Die restlichen Elemente der zweiten Tabelle werden durch die Rechteckregel aus den Elementen der ersten Tabelle gewonnen. Für eine gefüllte Zelle und eine Zelle mit einem Auflösungselement erstellen wir ein Rechteck. Dann subtrahieren wir von dem Element für die zu füllende Zelle das Produkt der Elemente der anderen beiden Scheitelpunkte, dividiert durch das Auflösungselement. Lassen Sie uns die Berechnungen nach dieser Regel zum Füllen der ersten Zeile der zweiten Tabelle zeigen:

Wir füllen die Tabellen weiter nach diesen Regeln, bis das Kriterium erfüllt ist. Wir haben zwei weitere Tabellen für unsere Aufgabe.

	X 1	X 4		X 3	X 2
X 3			X 1
X 2			X 2
X 5			X 5

4. Das Ergebnis dieses Algorithmus wird wie folgt aufgezeichnet. In der letzten Tabelle das Element am Schnittpunkt der Zeile
und Spalte B, gibt den Maximalwert der Zielfunktion an. In unserem Fall
. Die Werte der Variablen in den Zeilen sind gleich den freien Koeffizienten. Für unsere Aufgabe haben wir
.

Es gibt andere Möglichkeiten, Simplex-Tabellen zu kompilieren und zu füllen. Beispielsweise werden für Stufe 1 alle Variablen und freien Koeffizienten in der Nullzeile der Tabelle eingetragen. Nachdem wir das Auflösungselement nach den gleichen Regeln in der folgenden Tabelle gefunden haben, ersetzen wir die Variable in der Nullspalte, aber nicht in der Zeile. Alle Elemente der zulässigen Zeile werden durch das zulässige Element dividiert und in einer neuen Tabelle aufgezeichnet. Für die restlichen Elemente der Freigabespalte schreiben wir Nullen. Als nächstes führen wir den angegebenen Algorithmus unter Berücksichtigung dieser Regeln aus.

Beim Lösen eines linearen Programmierproblems für ein Minimum wird der größte positive Koeffizient in der letzten Zeile ausgewählt und der angegebene Algorithmus wird ausgeführt, bis es keine positiven Koeffizienten in der letzten Zeile gibt.

Die Lösung linearer Programmierprobleme mit Excel wird wie folgt durchgeführt.

Um lineare Programmierprobleme zu lösen, wird das Add-On Search for Solution verwendet. Zuerst müssen Sie sicherstellen, dass dieses Add-In auf der Registerkarte Daten in der Gruppe Analyse vorhanden ist (für 2003 siehe Tools). Wenn der Befehl Solver oder die Gruppe Analysieren fehlt, müssen Sie dieses Add-In herunterladen.

Klicken Sie dazu auf Microsoft Office File (2010) und dann auf die Schaltfläche Excel-Optionen. Wählen Sie im angezeigten Fenster Excel-Optionen das Feld Add-Ins auf der linken Seite aus. Auf der rechten Seite des Fensters sollte der Wert des Felds Verwalten auf Excel-Add-Ins eingestellt sein, klicken Sie auf die Schaltfläche „Los“, die sich neben diesem Feld befindet. Aktivieren Sie im Fenster Add-Ins das Kontrollkästchen neben Lösung suchen und klicken Sie dann auf OK. Anschließend können Sie mit dem installierten Add-In Find Solutions arbeiten.

Vor dem Aufruf von Search Solutions müssen Daten zur Lösung eines linearen Programmierproblems (aus einem mathematischen Modell) auf einem Arbeitsblatt vorbereitet werden:

1) Bestimmen Sie die Zellen, in denen das Ergebnis der Lösung platziert werden soll, in der ersten Zeile tragen wir die Variablen und die Zielfunktion ein. Die zweite Zeile ist nicht ausgefüllt (änderbare Zellen), in diesen Zellen wird das optimale Ergebnis erzielt. Geben Sie in der nächsten Zeile die Daten für die Zielfunktion und in den nächsten Zeilen das Restriktionssystem (Koeffizienten für Unbekannte) ein. Rechte Seite Beschränkungen (freie Koeffizienten) eingeführt werden, wobei eine freie Zelle verbleibt, nachdem die Koeffizienten des Beschränkungssystems aufgezeichnet wurden.

2) Tragen Sie die Abhängigkeit von variablen Zellen für die Zielfunktion und die Abhängigkeit von variablen Zellen für die linken Teile des Constraint-Systems in die verbleibenden freien Zellen ein. Um Abhängigkeitsformeln einzuführen, ist es zweckmäßig, die mathematische Funktion SUMPRODUCT zu verwenden.

Als nächstes müssen Sie das Add-In Suchen nach einer Lösung verwenden. Wählen Sie auf der Registerkarte Daten in der Gruppe Analysieren die Option Solver aus. Das Dialogfeld Lösung suchen wird angezeigt, das wie folgt ausgefüllt werden muss:

1) Geben Sie im Feld „Zielfunktion optimieren“ die Zelle an, die die Zielfunktion enthält (diese Zelle muss die Formel für die Zielfunktion enthalten). Wählen Sie die Option, um den Wert der Zielzelle zu optimieren (maximieren, minimieren):

2) Geben Sie im Feld „Variablenzellen ändern“ die variablen Zellen ein. Tragen Sie im nächsten Feld „Nach Einschränkungen“ die vorgegebenen Einschränkungen über die Schaltfläche „Hinzufügen“ ein. Geben Sie im angezeigten Fenster die Zellen mit den Formeln für das Beschränkungssystem ein, wählen Sie das Vorzeichen der Beschränkung und den Wert der Beschränkung (freier Koeffizient):

3) Aktivieren Sie das Kontrollkästchen "Variablen ohne Einschränkungen nicht negativ machen". Wählen Sie die Lösungsmethode "Suche nach der Lösung linearer Probleme mit dem Simplex-Verfahren". Nachdem Sie auf die Schaltfläche "Lösung finden" geklickt haben, beginnt der Prozess der Problemlösung. Als Ergebnis erscheint das Dialogfeld "Ergebnisse der Suche nach einer Lösung" und die ursprüngliche Tabelle mit gefüllten Zellen für die Werte der Variablen und den optimalen Wert der Zielfunktion.

Beispiel. Lösen Sie ein lineares Programmierproblem mit dem Excel Solver-Add-In: Finden Sie den Maximalwert einer Funktion
unter Einschränkungen

;

,
.

Lösung. Um unser Problem auf einem Excel-Arbeitsblatt zu lösen, führen wir den angegebenen Algorithmus aus. Wir geben die Ausgangsdaten in Form einer Tabelle ein

Wir führen Abhängigkeiten für die Zielfunktion und das Nebenbedingungssystem ein. Geben Sie dazu in Zelle C2 die Formel =SUMMENPRODUKT(A2:B2;A3:B3) ein. In den Zellen C4 bzw. C5 lauten die Formeln: =SUMPRODUCT(A2:B2;A4:B4) und =SUMPRODUCT(A2:B2;A5:B5). Das Ergebnis ist eine Tabelle.

Wir starten den Befehl "Suche nach einer Lösung" und füllen das erscheinende Fenster Suche nach einer Lösung wie folgt aus. Geben Sie im Feld "Zielfunktion optimieren" die Zelle C2 ein. Wir entscheiden uns dafür, den Wert der Zielzelle "Maximum" zu optimieren.

Geben Sie im Feld "Variablenzellen ändern" die variablen Zellen A2:B2 ein. Tragen Sie im Feld „Nach Einschränkungen“ die vorgegebenen Einschränkungen über die Schaltfläche „Hinzufügen“ ein. Zellreferenzen $C$4:$C$5 Beschränkungsreferenzen =$D$4:$D$5 Zeichen dazwischen<= затем кнопку «ОК».

Aktivieren Sie das Kontrollkästchen "Unbeschränkte Variablen nicht negativ machen". Wählen Sie die Lösungsmethode "Suche nach der Lösung linearer Probleme mit dem Simplex-Verfahren".

Durch Drücken der Schaltfläche "Lösung finden" beginnt der Prozess der Problemlösung. Als Ergebnis erscheint das Dialogfeld "Ergebnisse der Suche nach einer Lösung" und die ursprüngliche Tabelle mit gefüllten Zellen für die Werte der Variablen und den optimalen Wert der Zielfunktion.

Im Dialog "Ergebnisse der Lösungssuche" speichern wir das Ergebnis x1=0.75, x2=0.75 , F=1.5 - gleich dem Maximalwert der Zielfunktion.

Aufgaben zum selbstständigen Arbeiten

Übung 1. Grafische, Simplex-Methoden und Excel-Tools, um den maximalen und minimalen Wert der Funktion zu finden F(X) für ein gegebenes System von Nebenbedingungen.

1. F(X)=10X 1 +5X 2 2. F(X)=3X 1 -2X 2

3. F(X)=3X 1 +5X 2 4. F(X)=3X 1 +3X 2

5. F(X)=4X 1 -3X 2 6. F(X)=2X 1 -X 2

7. F(X)=-2X 1 +4X 2 8. F(X)=4X 1 -3X 2

9. F(X)=5X 1 +10X 2 10. F(X)=2X 1 +X 2

11. F(X)=X 1 +X 2 12. F(X)=3X 1 +X 2

13. F(X)=4X 1 +5X 2 14. F(X)=3X 1 +2X 2

15. F(X)=-X 1 -X 2 16. F(X)=-3X 1 -5X 2

17. F(X)=2X 1 +3X 2 18. F(X)=4X 1 +3X 2

19. F(X)=-3X 1 -2X 2 20. F(X)=-3X 1 +4X 2

21. F(X)=5X 1 -2X 2 22. F(X)=-2X 1 +3X 3

23. F(X)=2X 1 +3X 2 24. F(X)=4X 1 +3X 2

25. F(X)=-3X 1 -2X 2 26. F(X)=-3X 1 +4X 2

27. F(X)=-2X 1 +4X 2 28. F(X)=4X 1 -3X 2

29. F(X)=-X 1 -X 2 30. F(X)=-3X 1 -5X 2

Kontrollfragen.

1. Welche Aufgaben werden als Probleme der linearen Programmierung bezeichnet?

2. Nennen Sie Beispiele für Probleme der linearen Programmierung.

3. Wie wird das Problem der linearen Programmierung durch eine grafische Methode gelöst?

4. Beschreiben Sie den Algorithmus des Simplex-Verfahrens zur Lösung linearer Programmierprobleme.

5. Beschreiben Sie den Algorithmus zur Lösung linearer Programmierprobleme mit Excel.

Gibt es nur einen limitierenden Faktor (z. B. eine knappe Maschine), lässt sich die Lösung mit einfachen Formeln finden (siehe Link am Anfang des Artikels). Bei mehreren limitierenden Faktoren wird die Methode der linearen Programmierung verwendet.

Lineares Programmieren ist die Bezeichnung für eine Kombination von Werkzeugen, die in der Managementwissenschaft verwendet werden. Diese Methode löst das Problem der Aufteilung knapper Ressourcen auf konkurrierende Aktivitäten, um einen bestimmten numerischen Wert, wie z. B. Grenzgewinne oder Kosten, zu maximieren oder zu minimieren. In der Wirtschaft kann es in Bereichen wie Produktionsplanung zur Gewinnmaximierung, Auswahl von Komponenten zur Kostenminimierung, Auswahl des Investitionsportfolios zur Maximierung der Rentabilität, Optimierung des Warentransports zur Reduzierung von Entfernungen, Personalzuweisung zur Maximierung der Arbeitseffizienz und Arbeitsplanung in in eingesetzt werden um Zeit zu sparen.

Notiz im , Zeichnungen im Format herunterladen

Die lineare Programmierung beinhaltet die Konstruktion eines mathematischen Modells des betrachteten Problems. Danach kann die Lösung grafisch (wird weiter unten besprochen) mithilfe von Excel (wird separat betrachtet) oder spezialisierten Computerprogrammen gefunden werden.

Der vielleicht schwierigste Teil der linearen Programmierung ist die Konstruktion eines mathematischen Modells, das die Übersetzung des betrachteten Problems in ein System von Variablen, Gleichungen und Ungleichungen erfordert – ein Prozess, der letztendlich von den Fähigkeiten, Erfahrungen, Fähigkeiten und der Intuition des Benutzers abhängt Compiler des Modells.

Betrachten Sie ein Beispiel für die Konstruktion eines mathematischen Modells der linearen Programmierung

Nikolai Kuznetsov betreibt eine kleine mechanische Fabrik. Im nächsten Monat plant er die Produktion von zwei Produkten (A und B), für die der spezifische Grenzgewinn auf 2.500 bzw. 3.500 Rubel geschätzt wird.

Die Herstellung beider Produkte erfordert Bearbeitungs-, Rohstoff- und Arbeitskosten (Abb. 1). Für die Herstellung jeder Einheit von Produkt A werden 3 Stunden maschinelle Bearbeitung, 16 Einheiten Rohstoffe und 6 Einheiten Arbeit zugeteilt. Die entsprechenden Anforderungen für Einheit B sind 10, 4 und 6. Nikolai prognostiziert, dass er im nächsten Monat 330 Bearbeitungsstunden, 400 Rohmaterialeinheiten und 240 Arbeitseinheiten bereitstellen kann. Die Technologie des Produktionsprozesses ist derart, dass in einem bestimmten Monat mindestens 12 Einheiten von Produkt B hergestellt werden müssen.

Reis. 1. Nutzung und Bereitstellung von Ressourcen

Nikolay möchte ein Modell bauen, um die Anzahl der Einheiten der Produkte A und B zu bestimmen, die er im nächsten Monat produzieren soll, um den Grenzgewinn zu maximieren.

Das lineare Modell kann in vier Schritten aufgebaut werden.

Stufe 1. Definition von Variablen

Es gibt eine Zielvariable (nennen wir sie Z), die optimiert, dh maximiert oder minimiert werden muss (z. B. Gewinn, Einnahmen oder Ausgaben). Nikolay versucht, den Grenzgewinn zu maximieren, daher ist die Zielvariable:

Z = Gesamtgrenzgewinn (in Rubel), der im nächsten Monat als Ergebnis der Produktion der Produkte A und B erzielt wird.

Es gibt eine Reihe unbekannter unbekannter Variablen (wir bezeichnen sie mit x 1, x 2, x 3 usw.), deren Werte bestimmt werden müssen, um den optimalen Wert der Zielfunktion zu erhalten, der in unserem Fall ist der gesamte Grenzgewinn. Dieser Deckungsbeitrag ist abhängig von der produzierten Menge der Produkte A und B. Diese Werte müssen berechnet werden und sind daher die interessierenden Variablen im Modell. Also bezeichnen wir:

x 1 = die Anzahl der im nächsten Monat produzierten Einheiten von Produkt A.

x 2 = Anzahl der im nächsten Monat produzierten Einheiten von Produkt B.

Es ist sehr wichtig, alle Variablen klar zu definieren; achten Sie besonders auf die Maßeinheiten und den Zeitraum, auf den sich die Variablen beziehen.

Bühne. 2. Konstruktion der Zielfunktion

Eine Zielfunktion ist eine lineare Gleichung, die entweder maximiert oder minimiert werden muss. Es enthält die Zielvariable, ausgedrückt in Bezug auf die gewünschten Variablen, dh Z, ausgedrückt in Bezug auf x 1 , x 2 ... als lineare Gleichung.

In unserem Beispiel bringt jedes hergestellte Produkt A 2500 Rubel. Grenzgewinn, und bei der Herstellung von x 1 Einheiten von Produkt A beträgt der Grenzgewinn 2500 * x 1. In ähnlicher Weise beträgt der Grenzgewinn aus der Herstellung von x 2 Einheiten von Produkt B 3500 * x 2. Somit ist der gesamte Grenzgewinn, der im nächsten Monat aufgrund der Produktion von x 1 Einheiten von Produkt A und x 2 Einheiten von Produkt B erzielt wird, d.h. die Zielvariable Z, wie folgt:

Z = 2500 * x 1 + 3500 * x 2

Nikolay versucht, diesen Indikator zu maximieren. Somit lautet die Zielfunktion in unserem Modell:

Maximiere Z = 2500 * x 1 + 3500 * x 2

Bühne. 3. Definition von Beschränkungen

Constraints sind ein System von linearen Gleichungen und/oder Ungleichungen, die die Werte der erforderlichen Variablen begrenzen. Sie spiegeln mathematisch die Verfügbarkeit von Ressourcen, technologische Faktoren, Vermarktungsbedingungen und andere Anforderungen wider. Es gibt drei Arten von Beschränkungen: „kleiner als oder gleich“, „größer als oder gleich“, „strikt gleich“.

In unserem Beispiel erfordern die Produkte A und B Verarbeitungszeit, Rohstoffe und Arbeitskräfte zur Herstellung, und die Verfügbarkeit dieser Ressourcen ist begrenzt. Die Produktionsmengen dieser beiden Produkte (d. h. x 1 von 2 Werten) werden daher durch die Tatsache begrenzt, dass die Menge an Ressourcen, die im Produktionsprozess benötigt werden, nicht die verfügbaren Ressourcen übersteigen kann. Betrachten Sie die Situation mit der Bearbeitungszeit der Maschine. Die Produktion jeder Einheit von Produkt A erfordert drei Stunden maschinelle Verarbeitung, und wenn x 1 Einheiten produziert werden, werden 3 * x 1 Stunden dieser Ressource verbraucht. Die Produktion jeder Einheit von Produkt B erfordert 10 Stunden und daher werden, wenn x 2 Produkte hergestellt werden, 10 * x 2 Stunden benötigt. Somit ist die Gesamtmenge an Maschinenzeit, die erforderlich ist, um x 1 Einheiten von Produkt A und x 2 Einheiten von Produkt B herzustellen, 3 * x 1 + 10 * x 2 . Diese Gesamtmaschinenlaufzeit darf 330 Stunden nicht überschreiten. Mathematisch wird dies wie folgt geschrieben:

3 * x 1 + 10 * x 2 ≤ 330

Ähnliche Überlegungen gelten für Rohstoffe und Arbeitskräfte, sodass zwei weitere Einschränkungen niedergeschrieben werden können:

16 * x 1 + 4 * x 2 ≤ 400

6 * x 1 + 6 * x 2 ≤ 240

Abschließend sei noch angemerkt, dass es eine Bedingung gibt, nach der mindestens 12 Stück von Produkt B hergestellt werden müssen:

Stufe 4. Schreiben der Bedingungen der Nicht-Negativität

Die gewünschten Variablen können keine negativen Zahlen sein, die als Ungleichungen x 1 ≥ 0 und x 2 ≥ 0 geschrieben werden müssen. In unserem Beispiel ist die zweite Bedingung redundant, da oben festgelegt wurde, dass x 2 nicht kleiner als 12 sein kann.

Das vollständige lineare Programmiermodell für das Produktionsproblem von Nikolai kann wie folgt geschrieben werden:

Maximieren: Z = 2500 * x 1 + 3500 * x 2

Vorausgesetzt: 3 * x 1 + 10 * x 2 ≤ 330

16 * x 1 + 4 * x 2 ≤ 400

6 * x 1 + 6 * x 2 ≤ 240

Betrachten Sie eine grafische Methode zur Lösung eines Problems der linearen Programmierung.

Diese Methode ist nur für Probleme mit zwei erforderlichen Variablen geeignet. Das oben erstellte Modell wird verwendet, um das Verfahren zu demonstrieren.

Die Achsen in der Grafik stellen die zwei unbekannten Variablen dar (Abb. 2). Es spielt keine Rolle, welche Variable entlang welcher Achse gezeichnet werden soll. Es ist wichtig, einen Maßstab zu wählen, der es Ihnen letztendlich ermöglicht, ein visuelles Diagramm zu erstellen. Da beide Variablen nicht negativ sein müssen, wird nur der 1. Quadrant gezeichnet.

Reis. 2. Graphachsen der linearen Programmierung

Betrachten Sie zum Beispiel die erste Einschränkung: 3 * x 1 + 10 * x 2 ≤ 330. Diese Ungleichung beschreibt die Fläche unter der Linie: 3 * x 1 + 10 * x 2 = 330. Diese Linie schneidet die x-Achse 1 bei x 2 \u003d 0, das heißt, die Gleichung sieht so aus: 3 * x 1 + 10 * 0 \u003d 330 und ihre Lösung: x 1 \u003d 330 / 3 \u003d 110

In ähnlicher Weise berechnen wir die Schnittpunkte mit den Achsen x 1 und x 2 für alle Randbedingungen:

Akzeptable Reichweite	Grenze der zulässigen Werte	Schnittpunkt mit x-Achse 1	Schnittpunkt mit x-Achse 2
3 * x 1 + 10 * x 2 ≤ 330	3 * x 1 + 10 * x 2 = 330	x 1 = 110; x2 = 0	x1 = 0; x 2 = 33
16 * x 1 + 4 * x 2 ≤ 400	16 * x 1 + 4 * x 2 = 400	x 1 = 25; x2 = 0	x1 = 0; x 2 = 100
6 * x 1 + 6 * x 2 ≤ 240	6 * x 1 + 6 * x 2 = 240	x 1 = 40; x2 = 0	x1 = 0; x 2 = 40
x2 ≥ 12	x 2 = 12	kreuzt nicht; verläuft parallel zur x-Achse 1	x1 = 0; x 2 = 12

Grafisch ist die erste Einschränkung in Abb. 3.

Reis. 3. Konstruktion des Bereichs zulässiger Lösungen für die erste Nebenbedingung

Jeder Punkt innerhalb des ausgewählten Dreiecks oder an seinen Rändern entspricht dieser Einschränkung. Solche Punkte heißen gültig, Punkte außerhalb des Dreiecks heißen ungültig.

In ähnlicher Weise spiegeln wir die restlichen Einschränkungen im Diagramm wider (Abb. 4). Die Werte x 1 und x 2 auf oder innerhalb des schattierten Bereichs ABCDE erfüllen alle Modellbeschränkungen. Ein solcher Bereich wird als Bereich zulässiger Lösungen bezeichnet.

Reis. 4. Der Bereich der machbaren Lösungen für das Gesamtmodell

Nun gilt es im Bereich der machbaren Lösungen die Werte x 1 und x 2 zu bestimmen, die Z maximieren. Dazu in der Zielfunktionsgleichung:

Z = 2500 * x 1 + 3500 * x 2

wir dividieren (oder multiplizieren) die Koeffizienten vor x 1 und x 2 durch dieselbe Zahl, so dass die resultierenden Werte in den in der Grafik gezeigten Bereich fallen; in unserem Fall reicht ein solcher Bereich von 0 bis 120; also können die Koeffizienten durch 100 (oder 50) geteilt werden:

Z = 25 x 1 + 35 x 2

weisen Sie dann Z einen Wert zu, der gleich dem Produkt der Koeffizienten vor x 1 und x 2 ist (25 * 35 = 875):

875 = 25 x 1 + 35 x 2

und finden Sie schließlich die Schnittpunkte der Linie mit den Achsen x 1 und x 2:

Lassen Sie uns diese Zielgleichung auf die gleiche Weise wie die Einschränkungen in den Graphen eintragen (Abb. 5):

Reis. 5. Anwendung der Zielfunktion (schwarz gepunktete Linie) auf den Bereich der machbaren Lösungen

Der Z-Wert ist über die Zielfunktionslinie hinweg konstant. Um die Werte x 1 und x 2 zu finden, die Z maximieren, müssen Sie die Linie der Zielfunktion parallel zu einem solchen Punkt innerhalb der Grenzen des Bereichs zulässiger Lösungen übertragen, der sich am Maximum befindet Abstand von der ursprünglichen Linie der Zielfunktion nach oben und rechts, dh zum Punkt C (Abb. 6).

Reis. 6. Die Gerade der Zielfunktion hat ihr Maximum im Bereich zulässiger Lösungen erreicht (bei Punkt C)

Daraus kann geschlossen werden, dass die optimale Lösung an einem der Extrempunkte des Entscheidungsbereichs liegen wird. In welcher davon hängt es von der Steigung der Zielfunktion ab und davon, welches Problem wir lösen: Maximieren oder Minimieren. Daher ist es nicht erforderlich, eine objektive Funktion zu zeichnen - es müssen lediglich die Werte von x 1 und x 2 an jedem der Extrempunkte durch Ablesen aus dem Diagramm oder durch Lösen des entsprechenden Gleichungspaares bestimmt werden. Die gefundenen Werte von x 1 und x 2 werden dann in die Zielfunktion eingesetzt, um den entsprechenden Wert von Z zu berechnen. Die optimale Lösung ist diejenige, bei der der Maximalwert von Z beim Lösen des Maximierungsproblems erhalten wird, und das Minimum bei der Lösung des Minimierungsproblems.

Lassen Sie uns zum Beispiel die Werte von x 1 und x 2 am Punkt C bestimmen. Beachten Sie, dass Punkt C am Schnittpunkt der Linien liegt: 3x 1 + 10x 2 = 330 und 6x 1 + 6x 2 = 240. Die Die Lösung dieses Gleichungssystems ergibt: x 1 = 10, x 2 = 30. Die Berechnungsergebnisse für alle Eckpunkte des Bereichs der zulässigen Lösungen sind in der Tabelle angegeben:

Punkt	Wert x 1	Wert x 2	Z \u003d 2500x 1 + 3500x 2
A	22	12	97 000
IN	20	20	120 000
MIT	10	30	130 000
D	0	33	115 500
E	0	12	42 000

Daher muss Nikolai Kuznetsom die Produktion von 10 Artikeln A und 30 Artikeln B für den nächsten Monat planen, wodurch er einen Grenzgewinn von 130.000 Rubel erzielen kann.

Kurz gesagt, die Essenz der grafischen Methode zur Lösung von Problemen der linearen Programmierung kann wie folgt zusammengefasst werden:

Zeichnen Sie zwei Achsen in das Diagramm, die zwei Entscheidungsparameter darstellen; Zeichnen Sie nur den 1. Quadranten.
Bestimmen Sie die Koordinaten der Schnittpunkte aller Randbedingungen mit den Achsen, indem Sie der Reihe nach die Werte x 1 = 0 und x 2 = 0 in die Gleichungen der Randbedingungen einsetzen.
Zeichnen Sie Modellbeschränkungslinien in das Diagramm.
Bestimmen Sie den Bereich auf dem Graphen (als zulässiger Entscheidungsbereich bezeichnet), der alle Einschränkungen erfüllt. Wenn es keinen solchen Bereich gibt, hat das Modell keine Lösung.
Ermitteln Sie die Werte der gewünschten Größen an den Extrempunkten des Entscheidungsbereichs und berechnen Sie jeweils den entsprechenden Wert der Zielgröße Z.
Bei Maximierungsproblemen ist die Lösung der Punkt, an dem Z maximal ist, bei Minimierungsproblemen ist die Lösung der Punkt, an dem Z minimal ist.

THEMA: LINEARE PROGRAMMIERUNG

AUFGABE 2.A. Lösen eines linearen Programmierproblems mit einer grafischen Methode

Aufmerksamkeit!

Dies ist eine EINFÜHRUNGSVERSION des Werkes Nr. 2073, der Preis des Originals beträgt 200 Rubel. Entworfen in Microsoft Word.

Zahlung. Kontakte.

Option 7. Finden Sie die maximalen und minimalen Wertelineare Funktion Ф \u003d 2x 1 - 2 x 2mit Einschränkungen: x 1 + x 2 ≥ 4;

- x 1 + 2 x 2 ≤ 2;

x 1 + 2 x 2 ≤ 10;

x ich ≥ 0, ich = 1,2.

Lösung:

Wenn wir bedingt Ungleichheitszeichen durch Gleichheitszeichen ersetzen, erhalten wir ein Gleichungssystem x1 + x2 = 4;

- x1 + 2 x2 = 2;

x1 + 2 x2 = 10.

Wir konstruieren gerade Linien gemäß diesen Gleichungen, dann wählen wir gemäß den Vorzeichen der Ungleichungen die Halbebenen aus und erhalten ihren gemeinsamen Teil - den Bereich zulässiger Lösungen der ODE - das Viereck MNPQ.

Der Mindestwert der Funktion

tsii - am Punkt M (2; 2)

Ф min = 2 2 - 2 2 = 0.

Der Maximalwert ist am Punkt N (10; 0) erreicht,

Ф max \u003d 2 10 - 2 0 \u003d 20.

Option 8. Finden Sie die maximalen und minimalen Werte

lineare Funktion Ф \u003d x 1 + x 2

mit Einschränkungen: x 1 - 4 x 2 - 4 ≤ 0;

3 x 1 - x 2 ≥ 0;

x1 + x2 – 4 ≥ 0;

x ich ≥ 0, ich = 1,2.

Lösung:

Wenn wir bedingt Ungleichheitszeichen durch Gleichheitszeichen ersetzen, erhalten wir ein Gleichungssystem x1 - 4 x2 = 4;

3 x1 - x2 = 0;

Wir konstruieren gerade Linien gemäß diesen Gleichungen, dann wählen wir gemäß den Vorzeichen der Ungleichungen Halbebenen aus und erhalten ihren gemeinsamen Teil - den Bereich zulässiger Lösungen der ODE - ein unbeschränktes Polygon MNPQ.

Der Mindestwert der Funktion

z. B. auf einer Geraden NP

am Punkt Р(4; 0)

Ф min = 4 + 0 = 4.

ODE ist von oben nicht begrenzt, daher gilt Ф max = + ∞.

Option 10. Finden Sie die maximalen und minimalen Werte

lineare Funktion Ф \u003d 2 x 1 - 3 x 2

mit Einschränkungen: x 1 + 3 x 2 ≤ 18;

2 x 1 + x 2 ≤ 16;

x 2 ≤ 5;

x ich ≥ 0, ich = 1,2.

Wenn wir die Ungleichheitszeichen bedingt durch Gleichheitszeichen ersetzen, erhalten wir ein Gleichungssystem

x 1 + 3 x 2 = 18 (1);

2 x 1 + x 2 = 16 (2);

3 x 1 = 21 (4).

Wir konstruieren den Vektor Г(2; -3) und ziehen durch den Ursprung Ebene Linie- gerade.

Wir verschieben die Pegellinie in die Richtung, während der Wert von F zunimmt. Am Punkt S(7; 0) erreicht die Zielfunktion ihr Maximum Ä max =2·7–3·0= = 14. Wir verschieben die Niveaulinie in Richtung, während der Wert von Ä abnimmt. Der Minimalwert der Funktion liegt am Punkt N(0; 5)

Ф min = 2 0 – 3 5 = –15.

AUFGABE 2.B. Lösung eines linearen Programmierproblems

Analytisches Simplex-Verfahren

Option 7. Minimieren Sie die Zielfunktion Ф \u003d x 1 - x 2 + x 3 + x 4 + x 5 - x 6

unter Einschränkungen: x 1 + x 4 +6 x 6 = 9,

3 x 1 + x 2 - 4 x 3 + 2 x 6 \u003d 2,

x 1 + 2 x 3 + x 5 + 2 x 6 = 6.

Lösung:

Die Anzahl der Unbekannten ist n=6, die Anzahl der Gleichungen m=3. Daher können r = n-m = 3 Unbekannte als frei angenommen werden. Wählen wir x 1 , x 3 und x 6 .

Wir drücken die Grundvariablen x 2 , x 4 und x 5 durch freie aus und bringen das System auf die Einheitsbasis

x 2 \u003d 2 - 3 x 1 + 4 x 3 - 2 x 6

x 4 \u003d 9 - x 1 - 6 x 6 (*)

x 5 \u003d 6 - x 1 - 2 x 3 - 2 x 6

Die Zielfunktion sieht folgendermaßen aus:

Ф \u003d x 1 - 2 + 3 x 1 - 4 x 3 + 2 x 6 + x 3 + 9 - x 1 - 6 x 6 +6 - x 1 - 2 x 3 - 2 x 6 - x 6 =

13 + 2 x 1 - 5 x 3 - 7 x 6

Nehmen wir x 1 \u003d x 3 \u003d x 6 \u003d 0, während die Basisvariablen die Werte x 2 \u003d 2 annehmen; x 4 \u003d 9; x 5 \u003d 6, dh die erste zulässige Lösung (0; 2; 0; 9; 6; 0), Zielfunktion Ф 1 \u003d 13.

Die Variablen x 3 und x 6 sind in der Zielfunktion mit negativen Koeffizienten enthalten, daher nimmt der Wert von Ф mit zunehmendem Wert ab. Nehmen wir zum Beispiel x 6 . Aus der 1. Gleichung des Systems (*) ist ersichtlich, dass eine Erhöhung des Wertes von x 6 bis zu x 6 \u003d 1 möglich ist (solange x 2 ³ 0). In diesem Fall behalten x 1 und x 3 Werte gleich Null. Als grundlegende Variablen nehmen wir nun x 4, x 5, x 6 als frei - x 1, x 2, x 3. Lassen Sie uns die neuen Basisvariablen durch die neuen freien Variablen ausdrücken. Erhalten

x 6 \u003d 1 - 3/2 x 1 - 1/2 x 2 + 2 x 3

x 4 \u003d 3 + 8 x 1 + 3 x 2 - 12 x 3

x 5 \u003d 4 + 2 x 1 + x 2 - 6 x 3

Ф \u003d 6 + 25/2 x 1 + 7/2 x 2 - 19 x 3

Weisen Sie freien Variablen Nullwerte zu, dh x 1 \u003d x 2 \u003d x 3 \u003d 0, während x 6 \u003d 1, x 4 \u003d 3, x 5 \u003d 4, dh der dritte gültige Lösung (0; 0; 0; 3; 4; 1). In diesem Fall Ф 3 \u003d 6.

Die Variable x 3 ist in der Zielfunktion mit einem negativen Koeffizienten enthalten, daher führt eine Erhöhung von x 3 relativ zu Null zu einer Verringerung von F. Aus der 2. Gleichung ist ersichtlich, dass x 3 bis zu 1/ 4, von der 3. Gleichung - bis zu 2/3 . Die zweite Gleichung ist kritischer. Wir übersetzen die Variable x 3 in die Anzahl der Basiswerte, x 4 in die Anzahl der freien.

Nun nehmen wir x 1 , x 2 und x 4 als neue freie Variablen. Lassen Sie uns die neuen Grundvariablen x 3 , x 5 , x 6 durch sie ausdrücken. Holen wir uns das System

x 3 \u003d 1/4 + 2/3 x 1 + 1/4 x 2 - 1/12 x 4

x 5 \u003d 5/2 - 2 x 1 - 1/2 x 2 + 1/2 x 4

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

Die Zielfunktion nimmt die Form an

Ф \u003d 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4

Die Variablen x 1 und x 2 sind in der Zielfunktion mit negativen Koeffizienten enthalten, daher nimmt der Wert von Ф mit zunehmendem Wert ab. Nehmen wir zum Beispiel x 2 . Aus der 2. Gleichung des Systems ist ersichtlich, dass eine Erhöhung des Wertes von x 2 bis zu x 2 \u003d 5 möglich ist (solange x 5 ³ 0). In diesem Fall behalten x 1 und x 4 Nullwerte bei, die Werte anderer Variablen sind gleich x 3 = 3/2; x 5 \u003d 0, x 6 \u003d 3/2, also die vierte gültige Lösung (0; 5; 3/2; 0; 0; 3/2). In diesem Fall Ф 4 \u003d 5/4.

Nun nehmen wir x 1 , x 4 und x 5 als neue freie Variablen. Lassen Sie uns die neuen Grundvariablen x 2 , x 3 , x 6 durch sie ausdrücken. Holen wir uns das System

x 2 \u003d 5 - 4 x 1 + x 4 - 2 x 5

x 3 \u003d 3/2 - 1/3 x 1 + 1/6 x 4 - 1/2 x 5

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

Die Zielfunktion nimmt die Form an

F \u003d - 5 + 29/6 x 1 + 1/3 x 4 + 5/2 x 5

Die Koeffizienten für beide Variablen im Ausdruck für Ф sind positiv, daher ist eine weitere Verringerung des Werts von Ф unmöglich.

Das heißt, der Mindestwert von Ф min = - 5, die letzte zulässige Lösung (0; 5; 3/2; 0; 0; 3/2) ist optimal.

Option 8. Maximiere die Zielfunktion Ф = 4 x 5 + 2 x 6

mit Einschränkungen: x 1 + x 5 + x 6 = 12;

x 2 + 5 x 5 - x 6 \u003d 30;

x 3 + x 5 - 2 x 6 \u003d 6;

2 x 4 + 3 x 5 - 2 x 6 \u003d 18;

Lösung:

Die Anzahl der Gleichungen ist 4, die Anzahl der Unbekannten ist 6. Daher können r = n - m = 6 - 4 = 2 Variablen als freie, 4 Variablen als Basis gewählt werden. Wir wählen x 5 und x 6 als freie, x 1, x 2, x 3, x 4 als grundlegende. Wir drücken die Grundvariablen durch die freien aus und reduzieren das Gleichungssystem auf die Einheitsbasis

x 1 \u003d 12 - x 5 - x 6;

x 2 \u003d 30 - 5 x 5 + x 6;

x 3 \u003d 6 - x 5 + 2 x 6;

x 4 \u003d 9 - 3/2 x 5 + x 6;

Wir schreiben die Zielfunktion in der Form Ä = 4 x 5 + 2 x 6 . Wir weisen freien Variablen x 5 = x 6 = 0 Nullwerte zu. In diesem Fall nehmen die Basisvariablen die Werte x 1 = 12, x 2 = 30, x 3 = 6, x 4 = 9 an , das heißt, wir erhalten die erste zulässige Lösung (12, 30 , 6, 9, 0,) und Ä 1 = 0.

Beide freien Variablen gehen mit positiven Koeffizienten in die Zielfunktion ein, dh eine weitere Erhöhung von F ist möglich.Übersetzen wir beispielsweise x 6 in die Anzahl der Basiswerte. Gleichung (1) zeigt, dass x 1 = 0 bei x 5 = 12, in (2) ÷ (4) x 6 mit positiven Koeffizienten eingeht. Gehen wir zu einer neuen Basis über: Grundvariablen - x 6, x 2, x 3, x 4, frei - x 1, x 5. Lassen Sie uns die neuen Grundvariablen durch neu frei ausdrücken

x 6 \u003d 12 - x 1 - x 5;

x 2 \u003d 42 - x 1 - 6 x 5;

x 3 \u003d 30 - 2 x 1 - 3 x 5;

x 4 \u003d 21 - x 1 - 5/2 x 5;

Die Zielfunktion hat die Form Ф = 24 - 2 x 1 + 2 x 5 ;

Wir weisen freien Variablen x 1 = x 5 = 0 Nullwerte zu. In diesem Fall nehmen die Basisvariablen die Werte x 6 = 12, x 2 = 42, x 3 = 30, x 4 = 21 an , d. h. wir erhalten die zweite zulässige Lösung (0, 42 , 30, 21, 0, 12) und Ä 2 = 24.

Die Zielfunktion x 5 tritt mit einem positiven Koeffizienten ein, dh eine weitere Erhöhung von F ist möglich. Gehen wir zu einer neuen Basis über: Grundvariablen - x 6, x 5, x 3, x 4, freie - x 1 , x 2. Lassen Sie uns neue grundlegende Variablen durch new free ausdrücken

x 6 \u003d 5 - 5/6 x 1 + 1/6 x 2;

x 5 \u003d 7 - 1/6 x 1 - 1/6 x 2;

x 3 \u003d 9 - 3/2 x 1 + 1/2 x 2;

x 4 \u003d 7/2 - 7/12 x 1 + 5/12 x 5;

Die Zielfunktion hat die Form Ф = 38 - 7/2 x 1 - 1/3 x 2;

Weisen Sie freien Variablen Nullwerte x 1 = x 2 = 0. In diesem Fall nehmen die Basisvariablen die Werte x 6 = 5, x 5 = 7, x 3 = 9, x 4 = 7/ 2, d. h. wir erhalten die dritte zulässige Lösung X 3 = (0, 0, 9, 7/2, 7, 5) und Ä 3 = 38.

Beide Variablen gehen mit negativen Koeffizienten in die Zielfunktion ein, d. h. eine weitere Erhöhung von Ф ist nicht möglich.

Daher ist die letzte zulässige Lösung optimal, d. h. Х opt = (0, 0, 9, 7/2, 7, 5) und Ф max = 38.

Option 10. Maximieren Sie die Zielfunktion Ф \u003d x 2 + x 3

unter Einschränkungen: x 1 - x 2 + x 3 \u003d 1,

x 2 - 2 x 3 + x 4 \u003d 2.

Lösung:

Das Gleichungssystem - Einschränkungen ist konsistent, da die Ränge der Matrix des Gleichungssystems und der erweiterten Matrix gleich und gleich 2 sind. Daher können zwei Variablen als frei angenommen werden, zwei andere Variablen - grundlegend - können sein linear ausgedrückt durch zwei freie Einsen.

Nehmen wir x 2 und x 3 als freie Variablen, dann sind die Variablen x 1 und x 2 die Basisvariablen, die wir durch frei ausdrücken

x 1 \u003d 1 + x 2 - x 3; (*)

x 4 \u003d 2 - x 2 + 2 x 3;

Die Zielfunktion wurde bereits durch x 2 und x 3 ausgedrückt, d. h. Ф = x 2 + x 3 .

Bei x 2 \u003d 0 und x 3 \u003d 0 sind die Basisvariablen gleich x 1 \u003d 1, x 4 \u003d 2.

Wir haben die erste zulässige Lösung X 1 = (1, 0, 0, 2), während Ä 1 = 0.

Eine Erhöhung von Ф ist beispielsweise mit einer Erhöhung des Wertes von x 3 möglich, der mit einem positiven Koeffizienten in den Ausdruck für Ф eingeht (x 2 bleibt gleich Null). In der ersten Gleichung des Systems (*) ist ersichtlich, dass x 3 auf 1 erhöht werden kann (aus der Bedingung x 1 ³0), d. h. diese Gleichung erlegt der Erhöhung des Werts von x 3 eine Beschränkung auf. Die erste Gleichung des Systems (*) löst sich auf. Auf der Grundlage dieser Gleichung gehen wir zu einer neuen Basis über und ändern x 1 und x 3 Stellen. Jetzt sind die Basisvariablen x 3 und x 4, frei - x 1 und x 2. Wir drücken jetzt x 3 und x 4 durch x 1 und x 2 aus.

Wir erhalten: x 3 \u003d 1 - x 1 + x 2; (**)

x 4 \u003d 4 - 2 x 1 + x 2;

Ф \u003d x 2 + 1 - x 1 + x 2 \u003d 1 - x 1 + 2 x 2

Setzt man die freien Variablen gleich Null, erhält man die zweite zulässige Basislösung X 2 = (0; 0; 1; 4), in der Ä 2 =1.

Eine Erhöhung von F ist mit einer Erhöhung von x 2 möglich. Die Erhöhung von x 2 ist nach dem letzten Gleichungssystem (**) nicht begrenzt. Daher nimmt Ä alle großen positiven Werte an, d. h. Ä max = + ¥.

Die Zielfunktion Ф ist also nicht nach oben beschränkt, also gibt es keine optimale Lösung.

AUFGABE 2.D. Schreiben Sie ein Problem dual zu dem gegebenen.

ursprüngliche Aufgabe.

Option 7. Maximiere die Zielfunktion Ф = 2× x 1 - x 4

mit Einschränkungen: x 1 + x 2 \u003d 20,

x 2 + 2× x 4 ≥ 5,

x 1 + x 2 + x 3 ≤ 8,

x ich ≥ 0 (i = 1, 2, 3, 4)

Lösung:

Wir bringen das Nebenbedingungssystem auf eine einzige, beispielsweise kanonische Form, indem wir zusätzliche Variablen in die 2. und 3. Gleichung einführen

x 1 + x 2 = 20,

x 2 + 2 × x 4 - x 5 \u003d 5,

- x 1 + x 2 + x 3 + x 6 \u003d 8.

Wir haben ein asymmetrisches Problem des 2. Typs. Das duale Problem wird wie folgt aussehen:

Zielfunktion F = 20 minimieren × y 1 + 5 × j 2 + 8 × ja 3

für y 1 — y 3 ≥ 2,

y1 + y2 + y3 ≥ 0,

ja 3 ≥ 0,

2× y2 ≥ 1,

Y2 ≥ 0,

ja 3 ≥ 0.

Option 8. Maximieren Sie die Zielfunktion Ф \u003d x 2 - x 4 - 3× x 5

mit Einschränkungen: x 1 + 2× x 2 - x 4 + x 5 \u003d 1,

— 4 × x 2 + x 3 + 2× x 4 - x 5 = 2,

3 × x 2 + x 5 + x 6 = 5,

x ich ≥ 0, (ich = 1, 6)

Lösung:

Wir haben das ursprüngliche Maximierungsproblem mit einem System von Zwangsbedingungen in Form von Gleichungen, d. h. ein Paar dualer Probleme hat eine asymmetrische Form des 2. Typs, dessen mathematisches Modell in Matrixform die Form hat:

Anfangsproblem: Doppeltes Problem:

F = S × X max F = B T × Ymin

an einer × X \u003d B bei A T × Y ≥ CT

Im ursprünglichen Problem hat die Matrixreihe der Koeffizienten für Variablen in der Zielfunktion die Form С = (0; 1; 0; -1; -3; 0),

die Spaltenmatrix der freien Terme und die Matrix der Koeffizienten für Variablen im Constraint-System haben die Form

B \u003d 2, A \u003d 0 - 4 1 2 -1 0

Suchen Sie die transponierte Koeffizientenmatrix, die Matrixzeile der Koeffizienten für Variablen in der Zielfunktion und die Matrixspalte der freien Elemente

0 1 0 0 VT \u003d (1; 2; 5)

EIN T = -1 2 0 C T = -1

Das duale Problem kann in folgender Form geschrieben werden:

Finden Sie den Minimalwert der Zielfunktion F = y 1 + 2 × j 2 + 5 × ja 3

unter Einschränkungen y 1 ≥ 0,

2× und 1-4 × y 2 + 3 × y3 ≥ 1,

- und 1 + 2 × y2 ≥ -1,

y 1 - y 2 + y 3 ≥ -3,

Option 10. Minimiere die Funktion Ф = x 1 + x 2 + x 3

eingeschränkt: 3× x 1 + 9× x 2 + 7× x 3 ≥ 2,

6 × x 1 + 4 x 2 + 5× x 3 ≥ 3,

8 × x 1 + 2 x 2 + 4× x 3 ≥ 4,

Lösung:

Wir haben das ursprüngliche Minimierungsproblem mit einem System von Zwangsbedingungen in Form von Ungleichungen, d. h. ein Paar dualer Probleme hat eine symmetrische Form des 3. Typs, dessen mathematisches Modell in Matrixform die Form hat:

Ursprüngliches Problem Doppeltes Problem

F = S × Xmin F \u003d B T × Ymax

an einer × X ≥ B bei AT × Y ≤ C T

X ≥ 0 Y ≥ 0

Im ursprünglichen Problem haben die Matrix-Reihe von Koeffizienten für Variablen in der Zielfunktion, die Matrix-Spalte von freien Termen und die Matrix von Koeffizienten für Variablen im Beschränkungssystem die Form

C \u003d (1; 1; 1), B \u003d 3, A \u003d 6 4 5

Lassen Sie uns die Matrizen des dualen Problems finden

B T = (2; 3; 4) C T = 3 EIN T = 9 4 2

Das duale Problem wird wie folgt formuliert:

Zielfunktion maximieren F = 2y 1 + 3y 2 + 4y 3

unter Einschränkungen 3 × y 1 + 6 × j 2 + 8 × y 3 ≤ 1,

9× y 1 + 4 × j 2 + 2 × y 3 ≤ 1,

7× y 1 + 5 × y 2 + 4 × y 3 ≤ 1,

y ich ≥ 0 (i = 1, 2, 3)

AUFGABE 2.C. Lösung eines linearen Programmierproblems mit Simplextabellen.

Option 7. Maximiere die Zielfunktion Ф = 2 x 1 - x 2 + 3 x 3 + 2 x 4

unter Einschränkungen: 2 x 1 + 3 x 2 - x 3 + 2 x 4 ≤ 4,

x 1 - 2 x 2 + 5 x 3 - 3 x 4 ≥ 1,

4 x 1 + 10 x 2 + 3 x 3 + x 4 ≤ 8.

Lösung:

Wir führen das System der Beschränkungen auf die kanonische Form zurück

2 x 1 + 3 x 2 - x 3 + 2 x 4 + z 1 = 4, (1)

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1, (2)

4 x 1 + 10 x 2 + 3 x 3 + x 4 + z 3 = 8. (3)

Wir haben ein System von 3 Gleichungen mit 7 Unbekannten. Wir wählen x 1 , z 1 , z 3 als 3 Basisvariablen, x 2 , x 3 , x 4 , z 2 als freie, wir drücken die Basisvariablen durch sie aus.

Aus (2) haben wir x 1 = 1 + 2 x 2 - 5 x 3 + 3 x 4 + x 6

Setzen Sie in (1) und (3) ein, erhalten wir

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 \u003d 1,

z 1 + 7 x 2 - 11 x 3 + 8 x 4 + 2 z 2 = 2,

z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,

Ф - 3 x 2 + 7 x 3 - 8 x 4 - 2 z 2 \u003d 2.

Erstellen Sie eine Simplex-Tabelle

I Iteration Tabelle 1

Basic AC	Freiheit. AC
x 1	1	1	— 2	5	— 3	0	— 1	0		3/8
z1	2	0	7	-11		1	2	0	1/ 4	1/8
z3	4	0	18	-17	13	0	4	1	4/13	13/8
F	2	0	— 3	7	— 8	0	— 2	0		1

X 1 \u003d (1; 0; 0; 0; 2; 0; 4) F 1 \u003d 2.

II Iteration Tabelle 2

x 1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
F	4	0	4	— 4	0	1	0	0		32/7

X 2 \u003d (14/8; 0; 0; 1/4; 0; 0; 4) Ф 2 \u003d 4.

III Iteration Tabelle 3

x 1	1	1	— 6	0	0		-1	— 1	1/2
x4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7	11/7
x 3	6/7	0	53/7	1	0	-13/7	6/7	8/7	13/14
F	52/7	0	240/7	0	0	-45/7	24/7	32/7	45/14

X 3 \u003d (1; 0; 6/7; 10/7; 0; 0; 0) Ф 3 \u003d 52/7.

IV Iteration Tabelle 4

z1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
x 3	25/14	13/14	28/14	1	0	0	-1/14	3/14
F	149/14	45/14	15	0	0	0	3/14	19/14

X 4 \u003d (0; 0; 25/14; 37/14; 1/2; 0; 0) F 4 \u003d 149/14.

Es gibt keine negativen Zahlen in der Indexzeile der letzten Tabelle, also im Ausdruck für die Zielfunktion, alle Ã i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

Antwort: Ф max = 149/14,

optimale Lösung (0; 0; 25/14; 37/14; 1/2; 0; 0)

Option 8. Minimiere die Zielfunktion Ф = 5 x 1 - x 3

unter Einschränkungen: x 1 + x 2 + 2 x 3 - x 4 \u003d 3,

x 2 + 2 x 4 \u003d 1,

Lösung:

Die Anzahl der Variablen ist 4, der Rang der Matrix ist 2, daher ist die Anzahl der freien Variablen r \u003d 4 - 2 \u003d 2, die Anzahl der Basisvariablen ist ebenfalls 2. Wir nehmen x 3, x 4 als freie Variablen, wir werden die Basisvariablen x 1, x 2 in freien Variablen ausdrücken und das System auf die Einheitsbasis bringen:

x 2 \u003d 1 - 2 x 4,

x 1 \u003d 3 - x 2 - 2 x 3 + x 4 \u003d 3 - 1 + 2 x 4 - 2 x 3 + x 4 \u003d 2 - 2 x 3 + 3 x 4

Ф \u003d 5 x 1 - x 3 \u003d 5 (2 - 2 x 3 + 3 x 4) - x 3 \u003d 10 - 10 x 3 + 15 x 4 - x 3 \u003d 10 - 11 x 3 + 15 x 4

Wir schreiben das Gleichungssystem und die Zielfunktion in einer für die Simplextabelle geeigneten Form, d. h. x 2 + 2 x 4 = 1,

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

Ф + 11 x 3 - 15 x 4 \u003d 10

Lass uns einen Tisch machen

I Iteration Tabelle 1

Basic AC	Freiheit. AC
x1	2	1	0		— 3	1/2
x2	1	0	1	0	2
F	10	0	0	11	— 15	— 11/2

X 1 \u003d (2; 1; 0; 0) F 1 \u003d 10.

II Iteration Tabelle 2

x3	1	1/2	0	1	-3/2	3/4
x2	1	0	1	0		1/2
F	— 1	— 11/2	0	0	3/2	— 3/4

X 2 \u003d (0; 1; 1; 0) F 2 \u003d -1.

III Iteration Tabelle 3

x3	7/4	1/2	3/4	1	0
x4	1/2	0	1/2	0	1
F	— 7/4	— 11/2	— 3/4	0	0

X 3 \u003d (0; 0; 7/4; 1/2) F 3 \u003d -7/4.

In der Indexzeile der letzten Tabelle, also im Ausdruck für die Zielfunktion, gibt es keine positiven Zahlen, alle Ã i > 0. Wir haben Fall I, also ist die letzte Basislösung optimal.

Antwort: Ф min = -7/4, optimale Lösung (0; 0; 7/4; 1/2)

********************

Option 10. Minimieren Sie die Zielfunktion Ф \u003d x 1 + x 2,

mit Einschränkungen: x 1 -2 x 3 + x 4 \u003d 2,

x 2 - x 3 + 2 x 4 \u003d 1,

Lösung:

Die Anzahl der Variablen ist 5, der Rang der Matrix ist 3, daher ist die Anzahl der freien Variablen r \u003d 6-3 \u003d 2. Wir nehmen x 3 und x 4 als freie Variablen, x 1, x 2, x 5 als grundlegende. Alle Gleichungen des Systems wurden bereits auf eine einzige Basis reduziert (grundlegende Variablen werden in Form von freien ausgedrückt), aber sie sind in einer Form geschrieben, die für die Verwendung von Simplex-Tabellen nicht geeignet ist. Wir schreiben das Gleichungssystem in der Form

x 1 - 2 x 3 + x 4 \u003d 2

x 2 - x 3 +2 x 4 \u003d 1

x 5 + x 3 - x 4 . = 5

Wir drücken die Zielfunktion durch freie Variablen aus und schreiben sie in der Form Ф - 3 x 3 +3 x 4 = 3

Lass uns einen Tisch machen

I Iteration Tabelle 1

Basic AC	Freiheit. AC
x 1	2	1	0	-2	1	0	2	-1/2
x 2	1	0	1	-1		0	1/2	1/2
x 5	5	0	0	1	-1	1		1/2
F	3	0	0	-3	3	0		-3/2

X 1 \u003d (2; 3; 0; 0; 5) F 1 \u003d 3.

Tabelle 2

x 1	3/2	1	-1/2	-3/2	0	0
x 4	1/2	0	1/2	-1/2	1	0
x 5	11/2	0	1/2	1/2	0	1
F	3/2	0	-3/2	-3/2	0	0

X 2 \u003d (3/2; 0; 0; 1/2; 11/2) F 2 \u003d 3/2.

In der Indexzeile der letzten Tabelle, also im Ausdruck für die Zielfunktion, sind keine positiven Zahlen, alle Гi > 0. Wir haben Fall 1, also ist die letzte Basislösung optimal.

Antwort: Ф min = 3/2, die optimale Lösung ist (3/2; 0; 0; 1/2; 11/2).

Finden Sie mit einer grafischen Methode das Maximum der Zielfunktion

F= 2X 1 + 3X 2 ® max

Mit Einschränkungen

Lösung mithilfe von Excel-Tabellen

Lassen Sie uns zuerst auf einem Blatt bauen Excel-Lösung Systeme der Ungleichheit.

Betrachten Sie die erste Ungleichung.

Konstruieren wir eine Grenzlinie aus zwei Punkten. Bezeichnen Sie die Zeile mit (L1) (oder Row1). Koordinaten X 2 rechnen wir nach den Formeln:

Wählen Sie zum Erstellen ein Streudiagramm aus

Auswahl von Daten für eine gerade Linie

Ändern Sie den Namen der Zeile:

Wählen Sie ein Diagrammlayout. Namen der Koordinatenachsen ändern:

Gerade (L1) auf dem Diagramm:

Die Lösung der strikten Ungleichung kann mit einem einzigen Testpunkt gefunden werden, der nicht zur Linie (L1) gehört. Verwenden Sie zum Beispiel den Punkt (0; 0)W(L1).

0+3×0< 18 или 0 < 18 .

Die Ungleichung ist wahr, daher ist die Lösung der Ungleichung (1) die Halbebene, in der sich der Testpunkt befindet (in der Abbildung unter der Linie L1).

Dann lösen wir die Ungleichung (2) .

Konstruieren wir die Grenzlinie 2 aus zwei Punkten. Bezeichne die Linie mit (L2).

Gerade Linie (L2) auf dem Diagramm:

Die Lösung der strengen Ungleichung 2 kann unter Verwendung des einzigen Testpunkts gefunden werden, der nicht zur Linie (L2) gehört. Verwenden Sie zum Beispiel den Punkt (0; 0)W(L2).

Durch Ersetzen der Koordinaten des Punktes (0; 0) erhalten wir die Ungleichung

2×0 + 0< 16 или 0 < 16 .

Die Ungleichung ist wahr, daher ist die Lösung der Ungleichung (2) die Halbebene, in der sich der Testpunkt befindet (in der Abbildung unten die Linie L2).

Dann lösen wir die Ungleichung (3) .

Konstruieren wir eine Grenzlinie aus zwei Punkten. Bezeichne die Linie mit (L3).

Gerade (L3) auf dem Diagramm:

Die Lösung der strengen Ungleichung 2 kann unter Verwendung des einzigen Testpunkts gefunden werden, der nicht zur Linie (L3) gehört. Verwenden Sie zum Beispiel den Punkt (0; 0)W(L3).

Durch Ersetzen der Koordinaten des Punktes (0; 0) erhalten wir die Ungleichung

Die Ungleichung ist wahr, daher ist die Lösung der Ungleichung (3) die Halbebene, in der sich der Testpunkt befindet (in der Abbildung unten, Linie L3).

Dann lösen wir die Ungleichung (4) .

Konstruieren wir eine Grenzlinie aus zwei Punkten. Bezeichne die Linie mit (L4).

Daten zu Excel-Tabelle hinzufügen

Gerade (L4) auf dem Diagramm:

Lösung der strengen Ungleichung 3 X 1 < 21 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L4). Например, с помощью точки (0; 0)Ï(L4).

Durch Ersetzen der Koordinaten des Punktes (0; 0) erhalten wir die Ungleichung

Die Ungleichung ist wahr, daher ist die Lösung der Ungleichung (4) die Halbebene, in der sich der Testpunkt befindet (links von der Linie L4 in der Figur).

Durch Lösen zweier Ungleichungen (5) und (6)

ist das 1. Viertel, das durch die Koordinatenlinien und begrenzt wird.

Das Ungleichungssystem ist gelöst. Die Lösung für das Ungleichungssystem (1) - (6) in diesem Beispiel ist ein konvexes Polygon in der unteren linken Ecke der Figur, begrenzt durch die Linien L1, L2, L3, L4 und die Koordinatenlinien und . Sie können sicherstellen, dass das Polygon richtig gewählt wird, indem Sie einen Testpunkt, zum Beispiel (1; 1), in jede Ungleichung des ursprünglichen Systems einsetzen. Durch Ersetzen des Punktes (1; 1) erhalten wir, dass alle Ungleichungen, einschließlich der natürlichen Beschränkungen, wahr sind.

Betrachten Sie nun die Zielfunktion

F= 2X 1 + 3X 2 .

Lassen Sie uns Ebenenlinien für Funktionswerte erstellen F=0 Und F=12(Zahlenwerte sind willkürlich gewählt). Daten zu Excel-Tabelle hinzufügen

Niveaulinien auf dem Chart:

Konstruieren wir einen Richtungsvektor (oder einen Gradienten) (2; 3). Die Vektorkoordinaten stimmen mit den Koeffizienten der Zielfunktion überein F.

Einführung

Die moderne Stufe der menschlichen Entwicklung unterscheidet sich darin, dass das Jahrhundert der Energie durch das Zeitalter der Informatik ersetzt wird. Es gibt eine intensive Einführung neuer Technologien in allen Bereichen der menschlichen Tätigkeit. Erhebt sich echtes ProblemÜbergang zu Informationsgesellschaft für die die Entwicklung der Bildung eine Priorität werden sollte. Auch die Wissensstruktur in der Gesellschaft verändert sich. Grundlegendes Wissen, das zur kreativen Entfaltung des Einzelnen beiträgt, wird für das praktische Leben immer wichtiger. Wichtig ist auch die Konstruktivität des erworbenen Wissens, die Fähigkeit, es zielgerichtet zu strukturieren. Auf der Grundlage von Wissen werden neue Informationsressourcen der Gesellschaft gebildet. Die Bildung und der Erwerb von neuem Wissen sollten auf einer strengen Methodik eines systematischen Ansatzes basieren, innerhalb dessen ein modellhafter Ansatz einen gesonderten Platz einnimmt. Die Möglichkeiten des Modellierungsansatzes sind sowohl hinsichtlich der verwendeten formalen Modelle als auch hinsichtlich der Implementierung von Modellierungsmethoden äußerst vielfältig. Die physikalische Modellierung ermöglicht es, zuverlässige Ergebnisse für relativ einfache Systeme zu erhalten.

Derzeit ist es unmöglich, einen Bereich menschlicher Aktivität zu nennen, in dem Modellierungsmethoden nicht bis zu einem gewissen Grad verwendet würden. Dies gilt insbesondere für die Verwaltung verschiedener Systeme, bei denen die wichtigsten Entscheidungsprozesse auf der Grundlage der erhaltenen Informationen sind.

1. Problemstellung

minimale Zielfunktion

Lösen Sie das Problem, das Minimum der Zielfunktion für das durch das Entscheidungspolygon spezifizierte Zwangssystem gemäß Option Nr. 16 der Aufgabe zu finden. Das Entscheidungspolygon ist in Abbildung 1 dargestellt:

Abbildung 1 – Polygon von Problemlösungen

Das System der Beschränkungen und die objektive Funktion des Problems werden im Folgenden dargestellt:

Es ist notwendig, das Problem mit den folgenden Methoden zu lösen:

Grafische Methode zur Lösung von LP-Problemen;

Algebraische Methode zur Lösung von LP-Problemen;

Simplex-Verfahren zur Lösung von LP-Problemen;

Methode zum Finden einer praktikablen Lösung für LP-Probleme;

Lösung des Dual-LP-Problems;

Die Methode der "Zweige und Grenzen" zur Lösung ganzzahliger LP-Probleme;

Gomorys Methode zum Lösen ganzzahliger LP-Probleme;

Balash-Methode zum Lösen von Booleschen LP-Problemen.

Vergleichen Sie die Ergebnisse der Lösung mit verschiedenen Methoden, um die entsprechenden Rückschlüsse auf die Arbeit zu ziehen.

2. Graphische Lösung des Problems der linearen Programmierung

Die grafische Methode zur Lösung von Problemen der linearen Programmierung wird in Fällen verwendet, in denen die Anzahl der Unbekannten drei nicht überschreitet. Bequem für qualitative Forschung Eigenschaften von Lösungen und wird in Verbindung mit anderen Methoden (algebraisch, Branch and Bound usw.) verwendet. Die Idee des Verfahrens basiert auf der grafischen Lösung eines Systems linearer Ungleichungen.

Reis. 2 Graphische Lösung des LP-Problems

Tiefpunkt

Gleichung einer Geraden, die durch zwei Punkte A1 und A2 verläuft:

AB: (0;1); (3;3)

Sonne: (3;3); (4;1)

CD: (4;1); (3;0)

EA: (1;0); (0;1)

CF: (0;1); (5;2)

mit Einschränkungen:

Lösung eines linearen Programmierproblems mit der algebraischen Simplex-Methode

Die Anwendung der algebraischen Methode zur Lösung des Problems erfordert eine Verallgemeinerung der Darstellung des LP-Problems. Das ursprüngliche System von Beschränkungen, die in Form von Ungleichungen gegeben sind, wird in die Standardnotation umgewandelt, wenn die Beschränkungen in Form von Gleichheiten gegeben sind. Das Konvertieren eines Beschränkungssystems in eine Standardform umfasst die folgenden Schritte:

Transformiere Ungleichungen so, dass links Variablen und freie Glieder stehen und rechts 0, d.h. dass die linke Seite größer oder gleich Null ist;

Führen Sie zusätzliche Variablen ein, deren Anzahl gleich der Anzahl der Ungleichheiten im Beschränkungssystem ist;

Führen Sie zusätzliche Einschränkungen für die Nicht-Negativität der hinzugefügten Variablen ein und ersetzen Sie die Ungleichheitszeichen durch strikte Gleichheitszeichen.

Bei der Lösung des LP-Problems algebraische Methode eine Bedingung kommt hinzu: Die Zielfunktion muss gegen ein Minimum streben. Wenn dieser Zustand nicht erfüllt ist, ist es notwendig, die Zielfunktion geeignet zu transformieren (mit -1 zu multiplizieren) und das Minimierungsproblem zu lösen. Nachdem die Lösung gefunden wurde, ersetzen Sie die Werte der Variablen in der ursprünglichen Funktion und berechnen Sie deren Wert.

Die Lösung des Problems mit der algebraischen Methode wird als optimal angesehen, wenn die Werte aller Basisvariablen nicht negativ sind und die Koeffizienten freier Variablen in der Zielfunktionsgleichung ebenfalls nicht negativ sind. Wenn diese Bedingungen nicht erfüllt sind, ist es notwendig, das Ungleichungssystem umzuwandeln, indem einige Variablen durch andere ausgedrückt werden (Änderung freier und grundlegender Variablen), um die obigen Einschränkungen zu erreichen. Der Wert aller freien Variablen wird mit Null angenommen.

Die algebraische Methode zur Lösung linearer Programmierprobleme ist eine der bekanntesten wirksame Methoden bei der manuellen Lösung kleiner Probleme. erfordert keine große Anzahl von arithmetischen Berechnungen. Die maschinelle Durchführung dieses Verfahrens ist aufwendiger als beispielsweise beim Simplex-Verfahren, weil Der Algorithmus zur Lösung der algebraischen Methode ist in gewissem Maße heuristisch und die Effektivität der Lösung hängt weitgehend von der persönlichen Erfahrung ab.

freie Variablen

St. Gasse - hinzufügen. Bausatz

Die Nicht-Negativitätsbedingungen sind erfüllt, daher wird die optimale Lösung gefunden.

3. Lösen eines linearen Programmierproblems mit einer Simplextabelle

Lösung: Bringen wir das Problem in eine Standardform zum Lösen mit Hilfe einer Simplex-Tabelle.

Wir reduzieren alle Gleichungen des Systems auf die Form:

Wir bauen eine Simplex-Tabelle:

In der oberen Ecke jeder Zelle der Tabelle tragen wir die Koeffizienten aus dem Gleichungssystem ein;

Wir wählen das maximale positive Element in Zeile F aus, außer dass dies die allgemeine Spalte sein wird;

Um das allgemeine Element zu finden, bauen wir eine Beziehung für alle positiven auf. 3/3; 9/1;- Mindestverhältnis in Zeile x3. Daher - allgemeine Zeichenfolge und =3 - allgemeines Element.

Wir finden =1/=1/3. Wir bringen die untere Ecke der Zelle ein, wo sich das allgemeine Element befindet;

In alle ungefüllten unteren Ecken der allgemeinen Zeile geben wir das Produkt des Werts in der oberen Ecke der Zelle ein;

Wählen Sie die oberen Ecken der allgemeinen Linie aus;

In allen unteren Ecken der allgemeinen Spalte geben wir das Produkt des Werts in der oberen Ecke mit - ein und wählen die resultierenden Werte aus;

Die restlichen Zellen der Tabelle werden als Produkte der entsprechenden ausgewählten Elemente ausgefüllt;

Dann bauen wir eine neue Tabelle, in der die Bezeichnungen der Zellen der Elemente der allgemeinen Spalte und Zeile umgekehrt sind (x2 und x3);

In der oberen Ecke der ehemaligen allgemeinen Zeile und Spalte werden die Werte geschrieben, die zuvor in der unteren Ecke standen;

Die Summe der Werte der oberen und unteren Ecken dieser Zellen in der vorherigen Tabelle wird in die obere Ecke der verbleibenden Zellen geschrieben

4. Lösen des Problems der linearen Programmierung durch Finden einer zulässigen Lösung

Gegeben sei ein System linearer algebraischer Gleichungen:

Das können wir alles annehmen, ansonsten multiplizieren wir die entsprechende Gleichung mit -1.

Wir führen Hilfsvariablen ein:

Wir führen auch eine Hilfsfunktion ein

Wir werden das System unter Nebenbedingungen (2) und Bedingungen minimieren.

REGEL ZUM FINDEN EINER MÖGLICHEN LÖSUNG: Um eine zulässige Lösung für System (1) zu finden, minimieren wir Form (3) unter Nebenbedingungen (2), als freie Unbekannte nehmen wir xj als grundlegende.

Bei der Lösung eines Problems mit der Simplex-Methode können zwei Fälle auftreten:

min f=0, dann müssen alle i gleich Null sein. Und die resultierenden Werte xj werden eine zulässige Lösung für System (1) sein.

min f>0, d.h. das ursprüngliche System hat keine zulässige Lösung.

Quellsystem:

Die Bedingung des Problems des vorherigen Themas wird verwendet.

Lassen Sie uns zusätzliche Variablen hinzufügen:

Eine zulässige Lösung des ursprünglichen Problems wird gefunden: x1 = 3, x2 = 3, F = -12. Basierend auf der erhaltenen zulässigen Lösung finden wir die optimale Lösung des ursprünglichen Problems unter Verwendung der Simplex-Methode. Dazu bauen wir aus der oben erhaltenen Tabelle eine neue Simplextabelle auf, indem wir die Zeile und die Zeile mit der Zielfunktion der Hilfsaufgabe löschen:

Wenn wir die konstruierte Simplextabelle analysieren, sehen wir, dass die optimale Lösung für das ursprüngliche Problem bereits gefunden wurde (die Elemente in der Zeile, die der Zielfunktion entspricht, sind negativ). Somit stimmt die beim Lösen des Hilfsproblems gefundene zulässige Lösung mit der optimalen Lösung des ursprünglichen Problems überein:

6. Das duale Problem der linearen Programmierung

Das anfängliche Beschränkungssystem und die Zielfunktion des Problems sind in der folgenden Abbildung dargestellt.

mit Einschränkungen:

Lösung: Wir bringen das Restriktionssystem auf die Standardform:

Die Aufgabe, die zu dieser dual ist, sieht folgendermaßen aus:

Das duale Problem wird mit dem Simplex-Verfahren gelöst.

Transformieren wir die Zielfunktion so, dass das Minimierungsproblem gelöst ist, und schreiben wir das System der Zwangsbedingungen in der Standardform für die Lösung nach dem Simplex-Verfahren auf.

y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)

y7 = 5 - (-3y1 - y2 + y3 + y4)

Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ??min

Lassen Sie uns das anfängliche Simplex-Tableau zur Lösung des dualen LP-Problems konstruieren.

Der zweite Schritt der Simplex-Methode

So wurde im dritten Schritt des Simplex-Verfahrens die optimale Lösung des Minimierungsproblems mit den folgenden Ergebnissen gefunden: y2 = -7 /8, y1 = -11/8, Ф = 12. Um den Wert von zu finden der Zielfunktion des dualen Problems ersetzen wir die gefundenen Werte der Basis- und freien Variablen in die Maximierungsfunktion:

Ämax = - Ämin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12

Da der Wert der Zielfunktion des direkten und des dualen Problems gleich ist, wird die Lösung des direkten Problems gefunden und ist gleich 12.

Fmin \u003d Fmax \u003d -12

7. Lösung des Problems der ganzzahligen linearen Programmierung mit der „Branches and Bounds“-Methode

Transformieren wir das ursprüngliche Problem so, dass die ganzzahlige Bedingung beim Lösen mit konventionellen Methoden nicht erfüllt ist.

Das anfängliche Polygon von Lösungen für ein ganzzahliges Programmierproblem.

Für das transformierte Lösungspolygon konstruieren wir neues System Einschränkungen.

Wir schreiben das System der Beschränkungen in Form von Gleichungen auf, um es mit der algebraischen Methode zu lösen.

Als Ergebnis der Lösung wurde der optimale Aufgabenplan gefunden: x1 = 9/4, x2 = 5/2, F = -41/4. Diese Lösung erfüllt nicht die im Problem gesetzte Integritätsbedingung. Wir teilen das ursprüngliche Lösungspolygon in zwei Regionen auf, wobei Region 3 davon ausgeschlossen wird

Geändertes Polygon der Problemlösungen

Lassen Sie uns neue Restriktionssysteme für die gebildeten Bereiche des Lösungspolygons zusammenstellen. Der linke Bereich ist ein Viereck (Trapez). Das Beschränkungssystem für den linken Bereich des Lösungspolygons ist unten dargestellt.

Beschränkungssystem für den linken Bereich

Der rechte Bereich repräsentiert Punkt C.

Das System der Beschränkungen für den rechten Entscheidungsbereich ist unten dargestellt.

Die neuen Constraint-Systeme sind zwei untergeordnete Probleme, die unabhängig voneinander gelöst werden müssen. Lösen wir das Problem der ganzzahligen Programmierung für den linken Bereich des Lösungspolygons.

Als Ergebnis der Lösung wurde der optimale Aufgabenplan gefunden: x1 = 3, x2 = 3, F = -12. Dieser Plan erfüllt die Bedingung ganzzahliger Variablen in dem Problem und kann als optimaler Referenzplan für das ursprüngliche Problem der ganzzahligen linearen Programmierung angesehen werden. Es macht keinen Sinn, die Lösung für den richtigen Lösungsbereich durchzuführen. Die folgende Abbildung zeigt den Lösungsfortschritt eines ganzzahligen linearen Programmierproblems in Form eines Baums.

Der Ablauf der Lösung eines ganzzahligen linearen Programmierproblems nach der Gomory-Methode.

In vielen praktischen Anwendungen ist das Problem der ganzzahligen Programmierung von großem Interesse, bei dem ein System linearer Ungleichungen und eine lineare Form gegeben sind

Es ist erforderlich, eine ganzzahlige Lösung des Systems (1) zu finden, die die Zielfunktion F minimiert, und alle Koeffizienten sind ganze Zahlen.

Eine der Methoden zur Lösung des ganzzahligen Programmierproblems wurde von Gomori vorgeschlagen. Die Idee des Verfahrens besteht darin, Methoden der kontinuierlichen linearen Programmierung zu verwenden, insbesondere das Simplex-Verfahren.

1) Unter Verwendung des Simplex-Verfahrens wird die Lösung des Problems (1), (2) bestimmt, für die die Anforderung, dass die Lösung ganzzahlig ist, entfernt wird; wenn sich herausstellt, dass die Lösung ganzzahlig ist, dann wird auch die gewünschte Lösung des ganzzahligen Problems gefunden;

2) Andernfalls, wenn eine Koordinate keine ganze Zahl ist, wird die erhaltene Lösung des Problems auf die Möglichkeit der Existenz einer ganzzahligen Lösung überprüft (das Vorhandensein ganzzahliger Punkte in einem zulässigen Polyeder):

Wenn sich in einer Zeile mit einem gebrochenen freien Element alle anderen Koeffizienten als ganze Zahlen herausstellen, gibt es keine ganzen Zahlen, Punkte in einem zulässigen Polyeder, und das Problem der ganzzahligen Programmierung hat keine Lösung.

Andernfalls wird eine zusätzliche lineare Nebenbedingung eingeführt, die von dem zulässigen Polyeder einen Teil abschneidet, der für das Finden einer Lösung eines ganzzahligen Programmierproblems nicht vielversprechend ist;

3) Um eine zusätzliche lineare Beschränkung zu konstruieren, wählen Sie die l-te Zeile mit einem gebrochenen freien Element aus und schreiben Sie die zusätzliche Beschränkung auf

wobei und jeweils die Bruchteile der Koeffizienten und frei sind

Mitglied. Führen wir eine Hilfsvariable in die Nebenbedingung (3) ein:

Lassen Sie uns die Koeffizienten bestimmen und in die Nebenbedingung einbeziehen (4):

wobei und die nächsten niedrigeren ganzen Zahlen für bzw. sind.

Gomory bewies, dass eine endliche Anzahl solcher Schritte zu einem linearen Programmierproblem führt, dessen Lösung ganzzahlig und daher die gewünschte ist.

Lösung: Wir reduzieren das System der linearen Zwangsbedingungen und der Zielfunktion auf die kanonische Form:

Lassen Sie uns die optimale Lösung des Systems linearer Nebenbedingungen bestimmen, indem wir die ganzzahlige Bedingung vorübergehend verwerfen. Wir verwenden dafür die Simplex-Methode. Die folgenden Tabellen stellen nacheinander die anfängliche Lösung des Problems dar, und die Transformationen der ursprünglichen Tabelle werden angegeben, um die optimale Lösung des Problems zu erhalten:

Lösen von Booleschen LP-Problemen mit der Balash-Methode.

Verfassen Sie Ihre eigene Variante für das Problem der ganzzahligen linearen Programmierung mit booleschen Variablen unter Berücksichtigung der folgenden Regeln: Das Problem verwendet mindestens 5 Variablen, mindestens 4 Nebenbedingungen, die Nebenbedingungskoeffizienten und die Zielfunktion werden willkürlich gewählt, aber in einer solchen Weise, dass das Constraint-System kompatibel ist. Die Aufgabe besteht darin, das ZCLP mit booleschen Variablen unter Verwendung des Balash-Algorithmus zu lösen und die Verringerung des Rechenaufwands in Bezug auf die Lösung des Problems durch vollständige Suche zu bestimmen.

Ausführung von Beschränkungen

F-Wert

Filterbeschränkung:

Berechnung Reduktionsermittlung

Die Lösung des Problems durch das erschöpfende Suchverfahren sind 6*25=192 berechnete Ausdrücke. Die Lösung des Problems nach der Balash-Methode ist 3*6+(25-3)=47 berechnete Ausdrücke. Die vollständige Reduzierung der Komplexität von Berechnungen in Bezug auf die Lösung des Problems durch das erschöpfende Suchverfahren ist.

Abschluss

Der Prozess des Entwerfens von Informationssystemen, die neue Informationstechnologien implementieren, wird ständig verbessert. Immer komplexere Systeme rücken in den Fokus der Systemingenieure, was die Verwendung physikalischer Modelle erschwert und die Bedeutung von mathematischen Modellen und Computersimulationen von Systemen erhöht. Maschinenmodellierung ist zu einem effektiven Werkzeug für die Erforschung und Gestaltung komplexer Systeme geworden. Die Relevanz mathematischer Modelle nimmt aufgrund ihrer Flexibilität, Angemessenheit an realen Prozessen, geringen Implementierungskosten auf Basis moderner PCs ständig zu. Dem Benutzer, d. h. einem Spezialisten für die Modellierung von Systemen mittels Computertechnologie, werden immer mehr Möglichkeiten geboten. Der Einsatz von Modellen ist besonders effektiv in den frühen Phasen des Entwurfs automatisierter Systeme, wenn die Kosten fehlerhafter Entscheidungen am größten sind.

Moderne Rechenwerkzeuge haben es ermöglicht, die Komplexität der bei der Untersuchung von Systemen verwendeten Modelle erheblich zu erhöhen, es ist möglich geworden, kombinierte Analyse- und Simulationsmodelle zu erstellen, die die ganze Vielfalt von Faktoren berücksichtigen, die in realen Systemen auftreten, dh die Verwendung von Modellen, die den untersuchten Phänomenen angemessener sind.

Literatur:

1. Ljaschtschenko I. N. Lineare und nichtlineare Programmierung / I. N. Lyashchenko, E. A. Karagodova, N. V. Chernikova, N. Z. Shor. - K.: "Höhere Schule", 1975, 372 S.

2. Richtlinien zur Durchführung des Studiengangsprojekts im Fach „Angewandte Mathematik“ für Studierende der Fachrichtung „Computersysteme und Netze“ Vollzeit- und Teilzeitausbildungsformen / Zusammengestellt von: I.A. Balakireva, A.V. Skatkov – Sewastopol: SevNTU Verlag, 2003. - 15 p.

3. Richtlinien für das Studium der Disziplin "Angewandte Mathematik", Abschnitt "Methoden der globalen Suche und eindimensionale Minimierung" / Vgl. A. V. Skatkov, I. A. Balakireva, L. A. Litvinova - Sewastopol: SevGTU Publishing House, 2000. - 31s.

4. Richtlinien für das Studium der Disziplin "Angewandte Mathematik" für Studierende der Fachrichtung "Computersysteme und Netzwerke" Abschnitt "Lösen ganzzahliger linearer Programmierprobleme" der Vollzeit- und Fernausbildungsformen / Zusammengestellt von: I. A. Balakireva, A. V. Skatkov - Sewastopol : SevNTU-Verlag, 2000. - 13 p.

5. Akulich I.L. Mathematisches Programmieren in Beispielen und Aufgaben:

6. Verarbeitung Zuschuss für Studentenwirtschaft. Spezialist. Universitäten.-M.: Höher. Schule, 1986.- 319f., mit Abb.

7. Andronov S.A. Optimale Entwurfsmethoden: Vorlesungstext / SPbGUAP. SPb., 2001. 169 S.: Abb.

Der optimale Wert der Zielfunktion wird aufgerufen. Lösung des Problems, das Minimum der Zielfunktion zu finden

Aufmerksamkeit!

Dies ist eine EINFÜHRUNGSVERSION des Werkes Nr. 2073, der Preis des Originals beträgt 200 Rubel. Entworfen in Microsoft Word.

Zahlung. Kontakte.

Ähnliche Dokumente

Kategorien

Der optimale Wert der Zielfunktion wird aufgerufen. Lösung des Problems, das Minimum der Zielfunktion zu finden

Aufmerksamkeit!

Dies ist eine EINFÜHRUNGSVERSION des Werkes Nr. 2073, der Preis des Originals beträgt 200 Rubel. Entworfen in Microsoft Word.

Zahlung. Kontakte.

Ähnliche Dokumente

Leukozyten im Blut, ihre Norm

Welcher Wert von Leukozyten wird als Norm angesehen?

Milch mit Honig und Butter - das beste Volksheilmittel gegen Husten

Ernährung bei Verstopfung bei Erwachsenen

Kategorien