Die einfachste und intuitivste Methode der linearen Programmierung (LP) ist die grafische Methode. Es wird verwendet, um LP-Probleme mit zwei Variablen zu lösen. Betrachten Sie das LP-Problem in der Standardform:
max f (x 1 , x 2, ..., x n) = ,
, i = 1, 2, ..., m,
x j 0, j = 1, 2,…, n.
Wir stellen n = 2 und wir werden das Problem im Flugzeug betrachten. Das Ungleichungssystem sei konsistent (hat mindestens eine Lösung).
Jede Ungleichung dieses Systems definiert geometrisch eine Halbebene mit der Grenzlinie a i 1 x 1 + a i 2 x 2 = b i, i = 1, 2, …, m. Die Nichtnegativitätsbedingungen definieren Halbebenen mit Grenzlinien x 1 = 0 bzw. x 2 = 0. Das System ist daher kompatibel, Halbebenen als konvexe Mengen, die sich schneiden, bilden einen gemeinsamen Teil, der eine konvexe Menge ist und eine Ansammlung von Punkten ist, wobei die Koordinaten jedes Punktes die Lösung dieses Systems sind. Die Sammlung dieser Punkte wird als Entscheidungspolygon bezeichnet. Es kann ein Punkt, eine Linie, ein Strahl, ein begrenztes und ein unbegrenztes Polygon sein.
Somit ist der LPP geometrisch die Suche nach einem solchen Punkt des Lösungspolygons, dessen Koordinaten den maximalen (minimalen) Wert für die lineare Funktion des Ziels liefern, und alle Punkte des Lösungspolygons sind zulässige Lösungen.
Eine lineare Gleichung beschreibt eine Menge von Punkten, die auf einer Geraden liegen. Lineare Ungleichung beschreibt einen bestimmten Bereich in der Ebene. Bestimmen wir, welcher Teil der Ebene durch die Ungleichung 2x 1 + 3x 2 12 beschrieben wird.
Konstruiere zuerst eine Gerade 2x 1 + Zx 2= 12. Es geht durch die Punkte (6; 0) und (0; 4). Um zu bestimmen, welche Halbebene die Ungleichung erfüllt, ist es notwendig, einen beliebigen Punkt auf dem Graphen auszuwählen, der nicht zu einer Geraden gehört, und seine Koordinaten in die Ungleichung einzusetzen. Wenn die Ungleichung gilt, dann ist dieser Punkt eine zulässige Lösung, und die den Punkt enthaltende Halbebene erfüllt die Ungleichung. Für die Substitution in Ungleichungen ist es zweckmäßig, den Ursprungspunkt zu verwenden. Setze x 1 = x 2 = 0 in die Ungleichung 2x 1 + 3x 2 12 ein. Wir erhalten 2x0 + 3x0 12. Diese Aussage ist wahr, daher entspricht die Ungleichung 2x 1 + 3x 2 12 der unteren Halbebene mit dem Punkt (0; 0). Dies spiegelt sich in der Grafik in Abb. 1.1.
Ebenso können Sie alle Randbedingungen des LP-Problems grafisch darstellen.
Die Lösung jeder Ungleichung des LPP-Beschränkungssystems ist eine Halbebene, die die Grenzlinie enthält und auf einer Seite davon liegt. Der Schnittpunkt von Halbebenen, von denen jede durch die entsprechende Ungleichung des Systems bestimmt wird, wird als Bereich zulässiger Lösungen oder Definitionsbereich bezeichnet. Es sollte daran erinnert werden, dass der Bereich der zulässigen Lösungen die Nicht-Negativitäts-Bedingungen ( x j 0, j = 1, 2, ..., n). Die Koordinaten eines beliebigen Punktes, der zum Definitionsbereich gehört, sind eine zulässige Lösung des Problems.
Um den Extremwert der Zielfunktion bei der grafischen Lösung von LP-Problemen zu finden, wird ein Vektorgradient verwendet, dessen Koordinaten partielle Ableitungen der Zielfunktion sind, d.h.
Dieser Vektor zeigt die Richtung der schnellsten Änderung der Zielfunktion. Gerade mit 1 x 1 + mit 2 x 2 = f(x0), senkrecht zum Gradientenvektor, ist die Niveaulinie der Zielfunktion. An jedem Punkt der Niveaulinie nimmt die Zielfunktion denselben Wert an. Setzen wir die Zielfunktion mit einem konstanten Wert gleich "ein"... Wenn wir den Wert von "a" ändern, erhalten wir eine Familie paralleler gerader Linien, von denen jede eine Linie des Zielfunktionsniveaus ist.
Eine wichtige Eigenschaft der Pegellinie einer linearen Funktion besteht darin, dass bei einer Parallelverschiebung der Geraden in eine Richtung der Pegel nur ansteigt und bei einer Verschiebung in die andere Richtung nur abnimmt.
Aus geometrischer Sicht sucht man in einem linearen Programmierproblem nach einem solchen Eckpunkt oder einer Punktmenge aus der zulässigen Menge von Lösungen, bei der die höchste (niedrigste) Niveaulinie erreicht wird, die weiter (näher) liegt als die anderen in Richtung des schnellsten Wachstums.
Die grafische Methode zur Lösung des LPP besteht aus den folgenden Schritten.
1. Der polygonale Bereich zulässiger Lösungen (ODS) des LPP wird konstruiert.
2. Der Vektorgradient der Zielfunktion (CF) wird an einem Punkt x 0 der ODR konstruiert:
3. Die Niveaulinie mit 1 x 1 + c 2 x 2 = a (a ist ein konstanter Wert) - eine Gerade senkrecht zum Gradientenvektor - bewegt sich bei Maximierung von f (x 1, x 2) bis es die Grenzen der ODR verlässt. Der Begrenzungspunkt (oder Punkte) der Fläche während dieser Bewegung ist der maximale Punkt f (x 1, x 2).
4. Um die Koordinaten des maximalen Punktes zu finden, genügt es, zwei Gleichungen von Geraden zu lösen, die sich aus den entsprechenden Randbedingungen ergeben und den maximalen Punkt im Schnittpunkt angeben. Der am resultierenden Punkt gefundene f (x 1, x 2)-Wert ist das Maximum.
Beim Minimieren (Maximieren) der Funktion f (x 1, x 2) bewegt sich die Pegellinie in die dem Gradientenvektor entgegengesetzte Richtung. Wenn die der Niveaulinie entsprechende Gerade den ODR während ihrer Bewegung nicht verlässt, dann existiert das Minimum (Maximum) der Funktion f (x 1, x 2) nicht.
Wenn die Niveaulinie parallel zu einer funktionalen Einschränkung des Problems verläuft, wird der optimale Wert von CF an jedem Punkt dieser Einschränkung erreicht, der zwischen zwei optimalen Eckpunkten liegt, und dementsprechend ist jeder dieser Punkte die optimale Lösung von die LPP. Mögliche Situationen zur grafischen Lösung von LP-Problemen sind in der Tabelle dargestellt. 1.3.
Tabelle 1.3
| № | ODR-Typ | Optimaler Lösungstyp | Notizen (Bearbeiten) |
| Polygon geschlossen | Einzige Entscheidung | ||
| Einzige Entscheidung | |||
| Polygonal | ZF ist nicht von unten begrenzt | ||
| CF ist nicht von oben begrenzt | |||
| Polygonal offen | Einzige Entscheidung | ||
| Unendlich viele Lösungen | |||
| Abschnitt | Einzige Entscheidung |
Betrachten wir eine grafische Lösung von Problemen der linearen Programmierung anhand des folgenden Beispiels.
Beispiel 1.1. Produktionsplanung eines Nähbetriebes (das Problem der Anzüge).
Es ist geplant, zwei Arten von Anzügen herauszubringen - Männer und Frauen. Ein Damenanzug benötigt 1m Wolle, 2m Lavsan und 1 Person/Tag Arbeit. Für einen Herrenanzug - 3,5 m Wolle, 0,5 m Lavsan und 1 Person / Tag Arbeit. Es fallen insgesamt 350m Wolle, 240m Lavsan und 150 Mann/Tag Arbeitskosten an. Es muss festgelegt werden, wie viele Anzüge von jedem Typ genäht werden müssen, um den maximalen Gewinn zu erzielen, wenn der Gewinn aus dem Verkauf eines Damenanzugs 10 Währungseinheiten beträgt und bei einem Herrenanzug 20 Währungseinheiten. Zu beachten ist, dass mindestens 60 Herrenanzüge genäht werden müssen.
Lassen Sie uns die folgenden Bezeichnungen einführen: x 1 - die Anzahl der Damenanzüge; x 2 - die Anzahl der Herrenanzüge. Der Gewinn aus dem Verkauf von Damenanzügen beträgt 10x 1, und aus dem Verkauf von Herrenanzügen - 20x 2, d.h. Es ist notwendig, die Zielfunktion zu maximieren:
10x 1 + 20x 2
Die Aufgabenbeschränkungen sind wie folgt:
x 1 + x 2 150,
2 x 1 + 0,5 x 2 240,
x 1 + 3,5 x 2 350,
x 2 60,
x 1 0.
Die erste Arbeitsbeschränkung x 1 + x 2 150. Die Gerade x 1 + x 2 = 150 geht durch die Punkte (150; 0) und (0; 150) (Abb. 1.2).
Die zweite Einschränkung für Lavsan ist 2 x 1 + 0,5 x 2 240. Die Gerade 2 x 1 + 0,5 x 2 = 240 geht durch die Punkte (120; 0) und (0; 480). Die dritte Grenze für Wolle x 1 + 3,5 x 2 350. Fügen wir die vierte Grenze für die Anzahl der Herrenanzüge x 2 hinzu 60. Die Lösung dieser Ungleichung ist die über der Geraden liegende Halbebene x 2 = 60. 1.3 Der Bereich der zulässigen Lösungen ist schattiert. Um die Bewegungsrichtung optimal zu bestimmen, konstruieren wir einen Gradientenvektor, dessen Koordinaten partielle Ableitungen der Zielfunktion sind, d.h.
Um einen solchen Vektor zu erstellen, müssen Sie den Punkt (10; 20) mit dem Ursprung verbinden. Beim Maximieren der Zielfunktion muss man sich in Richtung des Gradientenvektors bewegen und beim Minimieren in die entgegengesetzte Richtung. Der Einfachheit halber können Sie einen Vektor proportional zum Vektor erstellen. Also, in Abb. 1.4 zeigt den Gradientenvektor (30; 60).
Um die Bewegungsrichtung optimal zu bestimmen, konstruieren wir einen Gradientenvektor, dessen Koordinaten partielle Ableitungen der Zielfunktion sind, d.h.
In unserem Fall bewegt sich die Niveaulinie, bis sie den Bereich der zulässigen Lösungen verlässt. Am extremen Winkelpunkt wird das Maximum der Zielfunktion erreicht. Um die Koordinaten dieses Punktes zu finden, reicht es aus, zwei Gleichungen von Geraden zu lösen, die sich aus den entsprechenden Randbedingungen ergeben und den maximalen Punkt am Schnittpunkt angeben:
x 1 + 3,5 x 2 = 350,
x1 + x2 = 150.
Von hier aus ist es einfach, die Lösung zum ursprünglichen LPP aufzuschreiben: max f (x)= 2300 und wird bei x 1 = 70 und x 2 = 80 erreicht (siehe Abb. 1.4).
1.3 TECHNOLOGIE ZUR LÖSUNG VON PROBLEMEN DER LINEAREN PROGRAMMIERUNG DURCH EINSTELLUNGEN SUCHE NACH EINER LÖSUNG IN DER EXCEL-UMGEBUNG
1.3.1. Allgemeine Informationüber die Arbeit mit einem Excel-Tabellenkalkulationsprozessor
Betrachten wir einige Aspekte der Arbeit mit einem Excel-Tabellenkalkulationsprozessor, der die Berechnungen vereinfacht, die zum Lösen von Optimierungsproblemen erforderlich sind. Tabellenprozessor ist ein Softwareprodukt zur Automatisierung der Verarbeitung von Tabellendaten.
Excel-Bildschirmelemente. Nach dem Start von Excel erscheint auf dem Bildschirm eine Tabelle, deren Ansicht in Abb. 1.5 dargestellt ist.
Dieses Bild wird als Arbeitsblatt bezeichnet. Es ist ein Raster aus Zeilen und Spalten, deren Schnittpunkte Rechtecke bilden, die Zellen genannt werden. Arbeitsblätter sind für die Dateneingabe, Berechnungen, Organisation der Informationsbasis usw. gedacht. Das Excel-Fenster zeigt die wichtigsten Programmelemente an: Titelleiste, Menüleiste, Statusleiste, Schaltflächen zur Fenstersteuerung.
Arbeiten mit Formeln. In Tabellenkalkulationsprogrammen werden Formeln verwendet, um eine Vielzahl von Berechnungen durchzuführen. MIT mit Excel Sie können schnell eine Formel erstellen. Die Formel besteht aus drei Hauptteilen:
1) ein Gleichheitszeichen;
2) eine Reihe von Werten oder Referenzen auf Zellen, mit denen Berechnungen durchgeführt werden;
3) Betreiber.
4) Wenn kein Gleichheitszeichen vorhanden ist, interpretiert Excel die Daten nicht als Formel, sondern als Dateneingabe in eine Zelle. Formeln können direkt in eine Zelle oder in die Bearbeitungsleiste eingegeben werden - entweder Text oder Zahlen. In diesem Fall müssen Sie Folgendes tun:
· Wählen Sie die Zelle aus, die die Formel enthalten soll, und geben Sie das Vorzeichen (=) ein;
· Geben Sie einen Operator oder ein Aktionszeichen ein;
· Wählen Sie eine andere Zelle aus, die in die Formel aufgenommen werden soll;
· Drücken Sie die Eingabetaste.
Die eingegebene Formel wird in der Bearbeitungsleiste angezeigt und das Berechnungsergebnis wird in der Zelle angezeigt.
Verwenden von Funktionen in Formeln. Sie können Excel-Funktionen verwenden, um die Eingabe von Formeln zu erleichtern. Funktionen sind in Excel integrierte Formeln. Excel enthält viele Formeln. Sie sind gruppiert nach verschiedene Typen: logisch, mathematisch, technisch, statistisch usw.
Um eine bestimmte Formel zu aktivieren, drücken Sie die Schaltflächen Einfügen, Funktionen. Das links angezeigte Fenster des Funktionsassistenten enthält eine Liste der Funktionstypen. Nach Auswahl des Typs wird rechts eine Liste der Funktionen selbst angezeigt. Die Funktion wird durch Anklicken des entsprechenden Namens ausgewählt.
Verschiedene Funktionen ausführen verschiedene Typen Berechnungen nach bestimmten Regeln. Wenn eine Funktion ein einzelnes Objekt in einer Zelle eines Arbeitsblatts ist, beginnt sie mit einem (=)-Zeichen, gefolgt vom Namen der Funktion und dann den in Klammern eingeschlossenen Funktionsargumenten.
Das Finden einer Lösung ist ein Excel-Add-In, mit dem Sie Optimierungsprobleme lösen können. Wenn der Befehl Lösung suchen im Menü Extras fehlt, müssen Sie dieses Add-In laden. Wählen Sie Tools => Add-Ins und aktivieren Sie das Add-In Find Solution. Wenn dieses Add-In nicht im Dialogfeld Add-Ins enthalten ist, müssen Sie auf das Panel verweisen Windows-Verwaltung, klicken Sie auf Programme hinzufügen oder entfernen, und verwenden Sie das Excel- (oder Office-) Setup, um das Add-In Find Solution zu installieren.
Nach Auswahl von Tools => Find Solution erscheint das Dialogfeld Find Solution.
Es gibt drei Hauptoptionen im Dialogfeld Lösung suchen;
Zielzelle festlegen.
Durch Zellenwechsel.
Einschränkungen.
Zuerst müssen Sie das Feld Zielzelle festlegen ausfüllen. Bei allen Aufgaben für das Solver-Tool wird das Ergebnis in einer der Zellen des Arbeitsblatts optimiert. Die Zielzelle wird über Formeln mit anderen Zellen in diesem Arbeitsblatt verknüpft. Solution Finder verwendet Formeln, die ein Ergebnis in der zu validierenden Zielzelle erzeugen mögliche Lösungen... Sie können nach dem kleinsten oder größten Wert für die Zielzelle suchen oder einen bestimmten Wert festlegen.
Der zweite wichtige Parameter des Solver-Tools ist der Parameter Zellen ändern. Hier legen Sie die Zellen fest, deren Werte sich ändern, um das Ergebnis in der Zielzelle zu optimieren. Sie können bis zu 200 veränderbare Zellen angeben, um nach einer Lösung zu suchen. Für diese Zellen gibt es zwei Hauptanforderungen: Sie sollten keine Formeln enthalten und Änderungen ihrer Werte sollten sich in der Änderung des Ergebnisses in der Zielzelle widerspiegeln. Mit anderen Worten, die Zielzelle hängt von den zu ändernden Zellen ab.
Der dritte Parameter, der auf der Registerkarte Lösen eingegeben werden muss, sind Abhängigkeiten.
Um das Problem zu lösen, müssen Sie:
1) geben Sie die Adressen der Zellen an, in die das Ergebnis der Lösung eingefügt wird (variable Zellen);
2) geben Sie die Anfangsdaten ein;
3) eine Abhängigkeit für die Zielfunktion einführen;
4) Abhängigkeiten einführen, um einzuschränken,
5) Führen Sie den Befehl Nach Lösungen suchen aus;
6) der Zielfunktion eine Zelle zuweisen (die Zielzelle festlegen);
7) Beschränkungen einführen;
8) Geben Sie die Parameter zum Lösen des LPP ein.
Betrachten Sie die Lösungstechnologie unter Verwendung der Bedingungen von Beispiel 1.1 (das Anzugsproblem).
Ökonomisches und mathematisches Modell des Problems
Sei x 1 die Anzahl der Damenanzüge; x 2 - die Anzahl der Herrenanzüge,
10 x x 1 + 20 x x 2 max
Die Aufgabenbeschränkungen sind wie folgt:
x 1 + x 2 150 - Arbeitsbeschränkungen;
2 x x 1 + 0,5 x NS 2 240 - Beschränkung auf Lavsan;
x 1 + 3,5 x x 2 350 - Beschränkung auf Wolle;
x 2 60 - Beschränkung auf Herrenanzüge;
x 1 0 - Beschränkung auf Damenanzüge.
1. Geben Sie die Adressen der Zellen an, in die das Lösungsergebnis eingefügt wird (modifizierte Zellen).
Beschriften Sie x 1, x 2 für die Anzahl der Farben jedes Typs. In unserem Problem werden die optimalen Werte des Vektors = (x 1, x 2) in Zellen A2 platziert: B2, der optimale Wert der Zielfunktion - in Zelle C3.
2. Geben Sie die Ausgangsdaten ein.
Geben Sie die Anfangsdaten der Aufgabe ein, wie in Abb. 1.6.
3. Führen Sie die Abhängigkeit für die Zielfunktion ein.
· Setzen Sie den Cursor in die Zelle "NW", die Zelle wird markiert.
· Platzieren Sie den Cursor auf der Funktionsassistenten-Schaltfläche in der Symbolleiste.
· Geben Sie Enter ein. Das Dialogfeld Funktionsassistent Schritt 1 von 2 wird auf dem Bildschirm angezeigt.
· Wählen Sie im Fenster Funktionen die Zeile SUMMENPRODUKT (Abb. 1.7). Auf dem Bildschirm
· Das Dialogfenster SUMMENPRODUKT erscheint (Abb. 1.8).
Geben Sie in der Zeile Array 1 ein A2: B2.
· Geben Sie in der Zeile Array 2 AZ: VZ ein.
Array 1 wird beim Einfügen von Constraint-Abhängigkeiten verwendet, daher müssen Sie einen absoluten Verweis auf dieses Array erstellen. In Abb. 1.9 zeigt, dass in Zelle СЗ eine Funktion eingeführt wurde.
5. Führen Sie Abhängigkeiten für Constraints ein (Abbildung 1.10).
· Platzieren Sie den Cursor in Zelle SZ.
· In der Symbolleiste die Schaltfläche In Zwischenablage kopieren.
· Platzieren Sie den Cursor in Zelle C4.
· Platzieren Sie den Cursor in Zelle C5.
· Auf der Symbolleiste die Schaltfläche Aus Zwischenablage einfügen.
· Platzieren Sie den Cursor in Zelle Sat.
· Auf der Symbolleiste die Schaltfläche Aus Zwischenablage einfügen.
· Platzieren Sie den Cursor in Zelle C7.
· Klicken Sie in der Symbolleiste auf die Schaltfläche Aus Zwischenablage einfügen. (Der Inhalt der Zellen C4-C7 muss überprüft werden. Sie müssen Informationen enthalten, wie für das Beispiel in Abbildung 1.11 gezeigt; der Inhalt der Zelle C5 wird als Beispiel gezeigt.)
· Platzieren Sie den Mauszeiger in der Menüleiste auf dem Dienst. Wählen Sie im erweiterten Menü den Befehl Lösung suchen. Das Dialogfenster Lösung suchen erscheint (Abb. 1.12).
5. Führen Sie den Befehl Lösung suchen aus.
6. Ordnen Sie eine Zelle für die Zielfunktion zu (setzen Sie die Zielzelle), geben Sie die Adressen der zu ändernden Zellen an.
· Setzen Sie den Cursor auf die Zeile Zielzelle setzen.
· Geben Sie die Adresse der Zelle $ C $ 3 ein.
· Geben Sie den Typ der Zielfunktion entsprechend den Bedingungen Ihres Problems ein. Markieren Sie dazu, ob die Zielfunktion gleich dem Maximalwert oder dem Minimalwert ist.
· Platzieren Sie den Cursor in einer Zeile Zellen ändern.
· Tragen Sie die Adressen der gewünschten Variablen A $ 2: B $ 2 ein (Abb. 1.13).
7. Führen Sie Einschränkungen ein.
· Bewegen Sie den Mauszeiger über die Schaltfläche Hinzufügen. Das Dialogfeld Einschränkung hinzufügen wird angezeigt.
· Führen Sie ein Beschränkungszeichen ein.
· Geben Sie in der Zeile Einschränkung die Adresse $ D $ 4 ein (Abb. 1.14).
· Bewegen Sie den Mauszeiger über die Schaltfläche Hinzufügen. Das Dialogfeld Einschränkung hinzufügen wird erneut auf dem Bildschirm angezeigt.
· Führen Sie den Rest der Problembedingungen gemäß dem obigen Algorithmus ein.
· Nachdem die letzte Einschränkung eingeführt wurde, klicken Sie auf die Schaltfläche OK. Auf dem Bildschirm erscheint das Dialogfenster Lösung suchen mit den eingegebenen Bedingungen (Abb. 1.15).
8. Geben Sie die Parameter zur Lösung des linearen Programmierproblems ein.
· Platzieren Sie im Dialogfenster den Mauszeiger auf die Schaltfläche Optionen. Das Dialogfenster Lösungssuchparameter erscheint auf dem Bildschirm (Abb. 1.16).
· Setzen Sie die Kontrollkästchen in den Feldern Lineares Modell (dadurch wird die Anwendung der Simplex-Methode sichergestellt) und Nicht-negative Werte.
· Bewegen Sie den Mauszeiger über die Schaltfläche OK. Das Dialogfeld Lösung suchen wird angezeigt.
· Platzieren Sie den Mauszeiger auf der Schaltfläche Ausführen.
Nach kurzer Zeit erscheint das Dialogfeld Lösungssuchergebnisse und die ursprüngliche Tabelle mit gefüllten AZ-Zellen: ВЗ für Werte x i und Zelle СЗ mit dem Maximalwert der Zielfunktion (Abb. 1.17).
Wenn Sie den Berichtstyp Stabilität angeben, erhalten Sie zusätzliche Informationen zur optimalen Lösung (Abb. 1.18).
Als Ergebnis der Lösung des Problems wurde die Antwort erhalten: 70 Stück müssen genäht werden. Damenanzüge und 80 Stück. Herrenanzüge, um den maximalen Gewinn von 2300 USD zu erzielen.
1.4. DUALITÄT BEI LINEAR PROGRAMMIERPROBLEMEN. ANALYSE ERREICHTER OPTIMALER LÖSUNGEN
1975 hat unser Landsmann L.V. Kantorowitsch erhielt den Wirtschaftsnobelpreis (zusammen mit dem amerikanischen Ökonomen T. Koopmans) für die Entwicklung der Theorie der optimalen Ressourcennutzung (siehe Anhang 1).
Eng verbunden mit jedem linearen Programmierproblem ist ein weiteres lineares Problem, das als duales Problem bezeichnet wird; die anfängliche Aufgabe wird als anfängliche oder direkte Aufgabe bezeichnet. Der Zusammenhang zwischen dem ursprünglichen und dem dualen Problem liegt insbesondere darin, dass die Lösung des einen direkt aus der Lösung des anderen gewonnen werden kann.
Die Variablen des dualen Problems y i werden objektiv bestimmte Schätzungen oder duale Schätzungen oder "Preise" von Ressourcen oder Schattenpreise genannt.
Jedes der Probleme des dualen Paares ist eigentlich ein unabhängiges lineares Programmierproblem und kann unabhängig vom anderen gelöst werden.
Das duale Problem in Bezug auf das Original wird nach folgenden Regeln zusammengestellt:
1) die Zielfunktion des ursprünglichen Problems wird für das Maximum und die Zielfunktion des dualen Problems - für das Minimum formuliert, während im Problem für das Maximum alle Ungleichungen in den funktionalen Nebenbedingungen die Form () haben, im Problem für das Minimum - das Formular ( );
2) die Matrix A, die sich aus den Koeffizienten bei unbekannten Randbedingungen im System des ursprünglichen Problems zusammensetzt, und eine ähnliche Matrix A T im dualen Problem werden durch Transposition voneinander erhalten;
3) die Anzahl der Variablen im dualen Problem ist gleich der Anzahl der funktionalen Beschränkungen des ursprünglichen Problems, und die Anzahl der Beschränkungen im System des dualen Problems ist gleich der Anzahl der Variablen im ursprünglichen;
4) die Koeffizienten für Unbekannte in der Zielfunktion des dualen Problems sind freie Terme im System der Randbedingungen des ursprünglichen Problems, und die rechten Seiten in den Randbedingungen des dualen Problems sind die Koeffizienten für Unbekannte in der Zielfunktion von das Original; j 0.
Diese beiden Probleme bilden ein Paar symmetrischer dualer Probleme. Die Hauptaussagen über wechselseitig duale Probleme sind in den nächsten beiden Sätzen enthalten.
Erster Dualitätssatz. Bei wechselseitig dualen Aufgaben tritt einer der sich gegenseitig ausschließenden Fälle ein.
1. Das direkte und das duale Problem haben optimale Lösungen,
in diesem Fall die Werte der Zielfunktionen auf den optimalen Lösungen
Spiel
2. Im direkten Problem ist die zulässige Menge nicht leer, und die Zielfunktion auf dieser Menge ist nicht nach oben beschränkt. Außerdem hat das duale Problem eine leere zulässige Menge.
3. Im dualen Problem ist die zulässige Menge nicht leer, und die Zielfunktion auf dieser Menge ist nicht nach unten beschränkt. In diesem Fall ist die zulässige Menge des direkten Problems leer.
4. Beide betrachteten Probleme haben leere zulässige Mengen.
Zweiter Dualitätssatz (komplementärer Nachlässigkeitssatz). Lass = ( x 1, x 2, ..., xn) ist eine zulässige Lösung des direkten Problems, a = (y 1, y 2,…, y m) ist eine zulässige Lösung des dualen Problems. Damit sie optimale Lösungen des direkten bzw. dualen Problems sind, ist es notwendig und ausreichend, dass die folgenden Beziehungen gelten:
Die Bedingungen (1.4) und (1.5) erlauben es, in Kenntnis der optimalen Lösung eines der wechselseitig dualen Probleme, die optimale Lösung eines anderen Problems zu finden.
Betrachten Sie einen weiteren Satz, dessen Schlussfolgerungen im Folgenden verwendet werden.
Schätztheorem. Die Werte der Variablen y i in der optimalen Lösung des dualen Problems sind Schätzungen des Einflusses freier Terme b i des Systems von Randbedingungen (Ungleichungen) des direkten Problems auf den Wert
Lösen wir das LPP mit der Simplex-Methode, lösen wir gleichzeitig das duale LPP. Die Variablen des dualen Problems y i werden objektiv bestimmte Schätzungen genannt.
Betrachten wir die ökonomische Interpretation des dualen Problems am Beispiel des Teppichproblems.
Beispiel 1 .2. Führen Sie die folgenden Aufgaben anhand der Beschreibung des Teppichproblems aus.
1. Formulieren Sie ein ökonomisches und mathematisches Modell des Teppichproblems für die maximalen Gesamtproduktionskosten unter Verwendung der Daten in der Tabelle. 1.1.
2. Suchen Sie mithilfe der Lösungssuche einen Produktionsplan, der die Gesamtproduktionskosten maximiert.
3. Formulieren Sie ein ökonomisches und mathematisches Modell des dualen Problems zum Teppichproblem.
4. Finden Sie den optimalen Plan des dualen Problems unter Verwendung des Dualitätssatzes, erklären Sie die Nullgleichheit von X 1 und X 4.
5. Analysieren Sie mithilfe der Protokolle der Lösungssuche die erhaltene optimale Lösung für das ursprüngliche Problem.
6. Bestimmen Sie, wie sich die Gesamtkosten und der Produktionsplan bei einer Erhöhung der Rohrressourcenreserve um 12 Einheiten ändern.
1. Lassen Sie uns ein ökonomisches und mathematisches Modell des Problems formulieren.
Lassen Sie uns durch X 1, X 2, X 3, X 4 die Anzahl der Teppiche jedes Typs bezeichnen. Die Zielfunktion hat die Form
F (X) = ZX 1 + 4X 2 + ZX 3 + X 4 max.
und Ressourcenbeschränkungen
7X 1 + 2X 2 + 2X 3 + 6X 4 80,
5X 1 + 8X 2 + 4 X 3 + ZX 4 480,
2X 1 + 4 X2 + X3 + 8X 4 130,
X1, X2, X3, X4 0.
2. Den optimalen Release-Plan finden.
Wir lösen das Problem mit dem Excel-Add-In Suche nach einer Lösung. Die Technologie zur Lösung des Problems wurde in der Anzügeproblematik ausführlich besprochen. In unserem Problem werden die optimalen Werte des Vektors X = (X 1, X 2, X 3, X 4) in die Zellen platziert: ЕЗ, der optimale Wert der Zielfunktion - in der Zelle F4.
Geben wir die Anfangsdaten ein. Zuerst beschreiben wir die Zielfunktion mit der Funktion - SUMPRODUCT (Abb. 1.19). Und dann geben wir Daten für die linke Seite der Einschränkungen ein. In Searching for a solution führen wir die Richtung der Zielfunktion, die Adressen der gesuchten Variablen ein und fügen Einschränkungen hinzu. Auf dem Bildschirm erscheint das Dialogfenster Lösung suchen mit den eingegebenen Bedingungen (Abb. 1.20).
Klicken Sie nach Eingabe der Parameter zum Lösen des LPP auf die Schaltfläche Ausführen. Auf dem Bildschirm erscheint eine Meldung, dass die Lösung gefunden wurde (Abb. 1.21).
Die resultierende Lösung bedeutet, dass das maximale Einkommen 150.000 Rubel beträgt. die Fabrik kann bei Freigabe 30 Teppiche des zweiten Typs und 10 Teppiche des dritten Typs erhalten. In diesem Fall werden die Ressourcen "Arbeit" und "Ausrüstung" voll ausgeschöpft und 280 kg 480 kg Garn (Ressource "Roh") verwendet.
Generierung eines Berichts basierend auf den Ergebnissen der Lösungssuche. Excel bietet Ihnen die Möglichkeit, die Ergebnisse der Lösungssuche in Form eines Berichts darzustellen (Tabelle 1.4). Es gibt drei Arten solcher Berichte:
· Ergebnisse (Antwort). Der Bericht enthält die Quell- und Zielwerte des Ziels und der geänderten Zellen sowie weitere Informationen zu den Einschränkungen.
· Stabilität (Empfindlichkeit). Ein Bericht, der Informationen zur Sensitivität einer Lösung gegenüber kleinen Änderungen in Zellen, die geändert werden, oder in Einschränkungsformeln bereitstellt.
· Grenzen. Neben den Quell- und Zielwerten der modifizierten und Zielzellen enthält der Bericht die Ober- und Untergrenze der Werte, die die beeinflussenden Zellen vorbehaltlich der Randbedingungen annehmen können.
Beispiel 6.1.
Lösung:
Das lineare Programmierproblem ist in einer Standardform gegeben und hat zwei Entwurfsparameter, daher
Es ist möglich, es mit einer geometrischen Methode zu lösen.
Stufe 1: ( SDT ).
Betrachten Sie die erste Einschränkung, ersetzen Sie das Ungleichungszeichen durch ein Gleichheitszeichen und drücken Sie die Variable aus x2über x1:
.
In ähnlicher Weise bestimmen wir die Punkte für die verbleibenden Randbedingungen des Systems und konstruieren Geraden, die jeder Ungleichung entsprechen (Abb. 1). Die Geraden sind nach dem zuvor angenommenen Schema nummeriert.
Stufe 2: .
Lassen Sie uns Halbebenen definieren - Lösungen für jede der Ungleichungen.
Betrachten Sie die erste Ungleichung des Beschränkungssystems des Problems. Nehmen Sie einen Punkt (Kontrollpunkt), der nicht zu der dieser Ungleichung entsprechenden Linie gehört, zum Beispiel der Punkt (0; 0). Wir setzen es in die betrachtete Ungleichung ein:
Beim Ersetzen von Koordinaten Kontrollpunkt Ungleichheit bleibt wahr. Folglich sind die zu dieser Geraden gehörenden Punkte (da die Ungleichung nicht streng ist) sowie die darunter liegenden Punkte Lösungen der betrachteten Ungleichung (wir markieren auf dem Graphen (Abb. 1) die gefundene Hälfte -Flugzeug mit zwei nach unten gerichteten Pfeilen neben der Geraden ich ) .
Ebenso definieren wir Lösungen für andere Ungleichungen und markieren sie entsprechend im Graphen. Als Ergebnis sieht die Grafik so aus:
Stufe 3: .
Die gefundenen Halbebenen (Lösungen jeder der Ungleichungen des Zwangsbedingungssystems) bilden an ihrem Schnittpunkt ein Polygon ABCDEO, die die ODR des betrachteten Problems ist.
Reis. 1. Bereich der machbaren Lösungen des Problems
Stufe 4:
Der Gradientenvektor zeigt die Richtung der Maximierung der Zielfunktion. Definieren wir seine Koordinaten: Koordinaten seines Anfangspunktes (Anwendungspunkt) - (0; 0), Koordinaten des zweiten Punktes:
Lassen Sie uns diesen Vektor auf dem Graphen aufbauen (Abb. 2).
Stufe 5: .
Betrachten Sie die Zielfunktion dieser Aufgabe:
.
Geben wir ihm zum Beispiel einen Wert. Drücken wir die Variable aus x2über x1:
.
Um eine Gerade nach dieser Gleichung zu konstruieren, setzen Sie zwei beliebige Punkte, zum Beispiel:
Konstruieren wir eine der Zielfunktion entsprechende Gerade (Abb. 2).
Reis. 2. Konstruktion der Zielfunktion F (X) und des Gradientenvektors С
Stufe 6: Bestimmung des Maximums der Zielfunktion.
Geradeaus bewegen F(x) parallel zu sich selbst in Richtung des Gradientenvektors definieren wir den Extrempunkt (die Punkte) des ODR. Gemäß der Grafik (Abb. 3) ist ein solcher Punkt der Punkt C - der Schnittpunkt der Geraden ich und II .
Reis. 3. Bestimmung des Maximalpunktes der Zielfunktion F (X)
Bestimmen Sie die Koordinaten des Punktes C, lösen Sie dazu folgendes lineares Gleichungssystem:
Setze die gefundenen Koordinaten in die Zielfunktion ein und finde ihren optimalen (maximalen) Wert:
Antworten: unter den gegebenen Randbedingungen der Maximalwert der Zielfunktion F(NS) = 24, die im Punkt C erreicht wird, dessen Koordinaten x1=6, x2=4.
Beispiel 6.2. Lösen Sie das lineare Programmierproblem mit der geometrischen Methode:
Lösung:
Die Schritte 1-3 ähneln den entsprechenden Schritten in der vorherigen Aufgabe.
Stufe 4: Konstruktion eines Vektorgradienten.
Die Konstruktion des Gradientenvektors erfolgt wie in der vorherigen Aufgabe. Lassen Sie uns diesen Vektor auf dem Graphen aufbauen (Abb. 4). Wir markieren auf diesem Graphen auch mit einem Pfeil die Richtung entgegengesetzt zum Gradientenvektor - die Richtung der Minimierung der Zielfunktion F (x).
Stufe 5: Aufbau einer direkten Zielfunktion.
Konstruktion einer direkten Zielfunktion F(x) wird auf die gleiche Weise wie bei der vorherigen Aufgabe durchgeführt (das Konstruktionsergebnis ist in Fig. 4 gezeigt).
Reis. 4. Konstruktion der Zielfunktion F (x) und des Gradientenvektors С
Stufe 6: Bestimmung des Optimums der Zielfunktion.
Geradeaus bewegen F(x) parallel zu sich selbst in der dem Gradientenvektor entgegengesetzten Richtung definieren wir den Extrempunkt (die Punkte) des ODR. Gemäß der Grafik (Abb. 5) ist ein solcher Punkt der Punkt O mit den Koordinaten (0; 0).
Reis. 5. Bestimmung des Minimalpunktes der Zielfunktion
Durch Einsetzen der Koordinaten des minimalen Punktes in die Zielfunktion bestimmen wir seinen optimalen (minimalen) Wert, der gleich 0 ist.
Antworten: unter den gegebenen Randbedingungen der Minimalwert der Zielfunktion F(NS) = 0, die im Punkt O (0; 0) erreicht wird.
Beispiel 6.3. Lösen Sie das folgende lineare Programmierproblem mit der geometrischen Methode:
Lösung:
Das betrachtete Problem der linearen Programmierung ist in der kanonischen Form gegeben; greifen wir die Basisvariablen heraus x 1 und x2 .
Lassen Sie uns eine erweiterte Matrix erstellen und die Basisvariablen mit der Jordan-Gauss-Methode auswählen x1 und x 2 .
Lassen Sie uns (Element für Element) die erste Zeile mit –3 multiplizieren und mit der zweiten hinzufügen: 
.
Wir multiplizieren die zweite Zeile mit:
.
Fügen Sie die zweite in die erste Zeile ein:
.
Infolgedessen wird das Beschränkungssystem die folgende Form annehmen:
Lassen Sie uns die grundlegenden Variablen in Form von freien Variablen ausdrücken:
Wir drücken die Zielfunktion auch in Form von freien Variablen aus, dafür setzen wir die erhaltenen Werte der Basisvariablen in die Zielfunktion ein:
Schreiben wir das resultierende lineare Programmierproblem:
Da die Variablen x1 und x2 nicht negativ sind, kann das resultierende System von Beschränkungen in der folgenden Form geschrieben werden:
Dann kann das ursprüngliche Problem als das folgende Äquivalent zu seinem Standardproblem der linearen Programmierung geschrieben werden:
Diese Aufgabe hat zwei Konstruktionsparameter und kann daher mit einem geometrischen Verfahren gelöst werden.
Stufe 1: Konstruktion von Linien, die den Bereich der zulässigen Lösungen begrenzen ( SDT ).
Betrachten Sie das System der Beschränkungen für das lineare Programmierproblem (der Einfachheit halber werden wir die Ungleichungen aufzählen):
Wir konstruieren gerade Linien, die jeder Ungleichung entsprechen (Abb. 6). Die Geraden sind nach dem zuvor angenommenen Schema nummeriert.
Stufe 2: Bestimmung der Lösung für jede der Ungleichungen des Restriktionssystems.
Mit den Kontrollpunkten definieren wir die Halbebenen - die Lösungen jeder der Ungleichungen und markieren sie mit den Pfeilen im Diagramm (Abb. 6).
Stufe 3: Definition des ODS eines linearen Programmierproblems.
Die gefundenen Halbebenen (dh Lösungen für jede der Ungleichungen des Zwangsbedingungssystems) haben keinen gemeinsamen Schnittpunkt (also widersprechen die Lösungen der Ungleichung I im Allgemeinen den anderen Ungleichungen des Zwangsbedingungssystems), daher ist das System von Beschränkungen ist nicht kompatibel und das Problem der linearen Programmierung hat daher keine Lösung.
Reis. 6. Fragment des MathCAD-Dokuments:
Konstruktion des Bereichs der zulässigen Lösungen des Problems
Antworten: das betrachtete Problem der linearen Programmierung hat aufgrund der Inkompatibilität des Systems der Beschränkungen keine Lösung.
Wenn nach Einsetzen der Koordinaten des Kontrollpunkts in die Ungleichung deren Bedeutung verletzt wird, dann ist die Lösung dieser Ungleichung eine Halbebene, die diesen Punkt nicht enthält (d. h. auf der anderen Seite der Geraden liegt).
Die dem Gradientenvektor entgegengesetzte Richtung entspricht der Minimierungsrichtung der Zielfunktion.
Es wird die Lösung von Problemen der linearen Programmierung durch eine grafische Methode betrachtet. Beschreibung der Methode. Beispiele für Problemlösungen.
InhaltSiehe auch: Probleme mit der Simplex-Methode lösen
Methodenbeschreibung
Wenn ein lineares Programmierproblem nur zwei Variablen enthält, kann es grafisch gelöst werden.
Betrachten Sie ein lineares Programmierproblem mit zwei Variablen und:
(1.1)
;
(1.2)
Hier gibt es beliebige Zahlen. Die Aufgabe kann sowohl darin bestehen, das Maximum (max) als auch das Minimum (min) zu finden. Im System der Beschränkungen können sowohl Zeichen als auch Zeichen vorhanden sein.
Aufbau der Region der machbaren Lösungen
Das graphische Verfahren zum Lösen von Problem (1) ist wie folgt.
Zuerst zeichnen wir die Koordinatenachsen und wählen den Maßstab. Jede der Ungleichungen des Zwangsbedingungssystems (1.2) definiert eine durch die entsprechende Gerade begrenzte Halbebene.
Also, die erste Ungleichung
(1.2.1)
definiert eine durch eine gerade Linie begrenzte Halbebene. Auf der einen Seite dieser Geraden und auf der anderen Seite. Auf der geradesten Linie. Um herauszufinden, ab welcher Seite die Ungleichung (1.2.1) gilt, wählen wir einen beliebigen Punkt, der nicht auf einer Geraden liegt. Als nächstes setzen wir die Koordinaten dieses Punktes in (1.2.1) ein. Wenn die Ungleichung gilt, enthält die Halbebene den ausgewählten Punkt. Ist die Ungleichung nicht erfüllt, liegt die Halbebene auf der anderen Seite (enthält nicht den ausgewählten Punkt). Schattierung der Halbebene, für die Ungleichung (1.2.1) gilt.
Dasselbe führen wir für die verbleibenden Ungleichungen des Systems (1.2) durch. Dadurch erhalten wir die schattierten Halbebenen. Die Punkte des Bereichs zulässiger Lösungen erfüllen alle Ungleichungen (1.2). Daher ist der Bereich zulässiger Lösungen (ADS) grafisch der Schnittpunkt aller konstruierten Halbebenen. Schattierung ODT. Es ist ein konvexes Polygon, dessen Flächen zu den konstruierten Geraden gehören. Außerdem kann ODR eine unbegrenzte konvexe Form, ein Liniensegment, ein Strahl oder eine gerade Linie sein.
Es kann der Fall eintreten, dass die Halbebenen keine gemeinsamen Punkte enthalten. Dann ist der Bereich der zulässigen Lösungen die leere Menge. Dieses Problem hat keine Lösungen.
Das Verfahren kann vereinfacht werden. Sie müssen nicht jede Halbebene schattieren, sondern bauen zuerst alle Geraden
(2)
Wählen Sie als Nächstes einen beliebigen Punkt aus, der zu keiner dieser Linien gehört. Setze die Koordinaten dieses Punktes in das Ungleichungssystem (1.2) ein. Wenn alle Ungleichungen erfüllt sind, wird der Bereich zulässiger Lösungen durch die konstruierten Geraden begrenzt und umfasst den ausgewählten Punkt. Wir schattieren den Bereich zulässiger Lösungen entlang der Grenzen der Geraden, sodass er den ausgewählten Punkt enthält.
Wenn mindestens eine Ungleichung nicht erfüllt ist, wählen wir einen anderen Punkt. Und so weiter, bis ein Punkt gefunden ist, dessen Koordinaten das System (1.2) erfüllen.
Ermitteln des Extremums der Zielfunktion
Wir haben also den schattierten Bereich der machbaren Lösungen (ODS). Es wird von einem Polygonzug begrenzt, der aus Segmenten und Strahlen besteht, die zu den konstruierten Geraden gehören (2). ODR ist immer eine konvexe Menge. Es kann entweder eine beschränkte Menge sein oder entlang einiger Richtungen nicht beschränkt sein.
Nun können wir nach dem Extremum der Zielfunktion suchen
(1.1)
.
Wähle dazu eine beliebige Zahl und bilde eine gerade Linie
(3)
.
Zur Vereinfachung der weiteren Darstellung nehmen wir an, dass diese Leitung durch das ODR verläuft. Auf dieser Linie ist die Zielfunktion konstant und gleich. eine solche gerade Linie wird als Funktionsebenenlinie bezeichnet. Diese Gerade teilt die Ebene in zwei Halbebenen. Auf einer halben Ebene
.
Auf der anderen Halbebene
.
Das heißt, auf einer Seite der geraden Linie (3) nimmt die Zielfunktion zu. Und je weiter wir den Punkt von der Geraden (3) entfernen, desto größer wird der Wert. Auf der anderen Seite der Geraden (3) nimmt die Zielfunktion ab. Und je weiter wir den Punkt von der Geraden (3) auf die andere Seite verschieben, desto niedriger wird der Wert. Ziehen wir eine Gerade parallel zur Geraden (3), dann ist die neue Gerade auch die Gerade des Zielfunktionsniveaus, jedoch mit einem anderen Wert.
Um den Maximalwert der Zielfunktion zu finden, ist es daher erforderlich, eine Gerade parallel zur Geraden (3) zu ziehen, die von ihr in Richtung steigender Werte am weitesten entfernt ist und durch mindestens einen Punkt verläuft des ODR. Um den Minimalwert der Zielfunktion zu finden, ist es notwendig, eine Gerade parallel zur Geraden (3) und am weitesten davon in Richtung abnehmender Werte zu ziehen, die durch mindestens einen Punkt des ODR verläuft.
Wenn die DDR unbegrenzt ist, kann der Fall eintreten, dass eine solche Gerade nicht gezogen werden kann. Das heißt, egal wie wir die Gerade von der Niveaulinie (3) in Richtung aufsteigend (abnehmend) entfernen, die Gerade wird immer durch den ODR gehen. In diesem Fall kann es beliebig groß (klein) sein. Daher gibt es keinen maximalen (minimalen) Wert. Das Problem hat keine Lösungen.
Betrachten Sie den Fall, dass eine extreme Gerade parallel zu einer beliebigen Geraden der Form (3) durch einen Scheitelpunkt des ODR-Polygons verläuft. Aus dem Graphen bestimmen wir die Koordinaten dieses Scheitelpunkts. Dann wird der maximale (minimale) Wert der Zielfunktion durch die Formel bestimmt:
.
Die Lösung des Problems ist
.
Es kann auch vorkommen, dass eine gerade Linie parallel zu einer der Flächen des ODR verläuft. Dann verläuft die Linie durch zwei Scheitelpunkte des ODR-Polygons. Bestimmen Sie die Koordinaten dieser Eckpunkte. Um den maximalen (minimalen) Wert der Zielfunktion zu bestimmen, können Sie die Koordinaten eines dieser Scheitelpunkte verwenden:
.
Das Problem hat unendlich viele Lösungen. Die Lösung ist jeder Punkt, der sich auf dem Segment zwischen den Punkten und befindet, einschließlich der Punkte und sich selbst.
Ein Beispiel für die Lösung eines linearen Programmierproblems mit einer grafischen Methode
Das Unternehmen produziert Kleider in zwei Modellen A und B. In diesem Fall werden drei Stoffarten verwendet. Für die Herstellung eines Kleides des Modells A werden 2 m der ersten Stoffart, 1 m der zweiten Stoffart und 2 m der dritten Stoffart benötigt. Für die Herstellung eines Kleides des Modells B werden 3 m der ersten Stoffart, 1 m der zweiten Stoffart, 2 m der dritten Stoffart benötigt. Die Reserven der ersten Stoffart betragen 21 m, die zweite Art - 10 m, die dritte Art - 16 m Die Veröffentlichung eines Produkts des Typs A bringt ein Einkommen von 400 den. Einheiten, ein Produkt vom Typ B - 300 den. Einheiten
Erstellen Sie einen Produktionsplan, der dem Unternehmen das höchste Einkommen beschert. Lösen Sie das Problem grafisch.
Lassen Sie die Variablen und die Anzahl der produzierten Kleider der Modelle A bzw. B bezeichnen. Dann beträgt die verbrauchte Stoffmenge des ersten Typs:
(m)
Die Menge des verbrauchten Stoffes des zweiten Typs beträgt:
(m)
Die Menge des verbrauchten Stoffes des dritten Typs beträgt:
(m)
Da die Anzahl der produzierten Kleider nicht negativ sein kann, dann
und .
Die Einnahmen aus den produzierten Kleidern betragen:
(Geldeinheiten)
Dann hat das ökonomische und mathematische Modell des Problems die Form:
Wir lösen es grafisch.
Wir zeichnen die Koordinatenachsen und.
Wir bauen eine gerade Linie.
Bei .
Bei .
Zeichnen Sie eine Gerade durch die Punkte (0; 7) und (10.5; 0).
Wir bauen eine gerade Linie.
Bei .
Bei .
Ziehen Sie eine Gerade durch die Punkte (0; 10) und (10; 0).
Wir bauen eine gerade Linie.
Bei .
Bei .
Zeichnen Sie eine Gerade durch die Punkte (0; 8) und (8; 0).
Schattieren des Bereichs, sodass Punkt (2; 2) in den schattierten Teil fällt. Wir erhalten ein vierseitiges OABC.
(A1.1) .
Bei .
Bei .
Ziehen Sie eine Gerade durch die Punkte (0; 4) und (3; 0).
Weiterhin stellen wir fest, dass, da die Koeffizienten bei und der Zielfunktion positiv sind (400 und 300), sie mit zunehmendem und zunimmt. Wir zeichnen eine Gerade parallel zur Geraden (A1.1), die in aufsteigender Richtung am weitesten davon entfernt ist und durch mindestens einen Punkt des Vierecks OABC verläuft. Eine solche Gerade geht durch den Punkt C. Aus der Konstruktion bestimmen wir ihre Koordinaten.
.
Die Lösung des Problems: ;
.
Das heißt, um das höchste Einkommen zu erzielen, müssen 8 Kleider des Modells A hergestellt werden. In diesem Fall beträgt das Einkommen 3200 den. Einheiten
Beispiel 2
Lösen Sie ein lineares Programmierproblem mit einer grafischen Methode.
Wir lösen es grafisch.
Wir zeichnen die Koordinatenachsen und.
Wir bauen eine gerade Linie.
Bei .
Bei .
Zeichnen Sie eine Gerade durch die Punkte (0; 6) und (6; 0).
Wir bauen eine gerade Linie.
Von hier.
Bei .
Bei .
Zeichnen Sie eine Gerade durch die Punkte (3; 0) und (7; 2).
Wir bauen eine gerade Linie.
Wir bauen eine Gerade (Abszissenachse).
Der Bereich zulässiger Lösungen (ODD) wird durch die konstruierten Geraden begrenzt. Um herauszufinden, von welcher Seite, stellen wir fest, dass der Punkt zur ODR gehört, da er das System der Ungleichungen erfüllt:
Wir schattieren den Bereich entlang der Grenzen der konstruierten Linien, so dass der Punkt (4; 1) in den schattierten Teil fällt. Wir erhalten ein Dreieck ABC.
Wir bauen eine beliebige Linie des Zielfunktionsniveaus, zum Beispiel
.
Bei .
Bei .
Wir ziehen eine Gerade des Niveaus durch die Punkte (0; 6) und (4; 0).
Da die Zielfunktion mit zunehmendem Wachstum zunimmt und wir dann eine Gerade ziehen, Parallele Ebene und die am weitesten davon in aufsteigender Richtung entfernte und durch mindestens einen Punkt des Dreiecks ABC verlaufend. Eine solche Gerade geht durch den Punkt C. Aus der Konstruktion bestimmen wir ihre Koordinaten.
.
Die Lösung des Problems: ;
Ein Beispiel für keine Lösung
Lösen Sie ein lineares Programmierproblem grafisch. Finden Sie den maximalen und minimalen Wert der Zielfunktion.
Wir lösen das Problem grafisch.
Wir zeichnen die Koordinatenachsen und.
Wir bauen eine gerade Linie.
Bei .
Bei .
Ziehen Sie eine Gerade durch die Punkte (0; 8) und (2.667; 0).
Wir bauen eine gerade Linie.
Bei .
Bei .
Ziehen Sie eine Gerade durch die Punkte (0; 3) und (6; 0).
Wir bauen eine gerade Linie.
Bei .
Bei .
Ziehen Sie eine Gerade durch die Punkte (3; 0) und (6; 3).
Geraden sind die Koordinatenachsen.
Der Bereich zulässiger Lösungen (ODS) wird durch die konstruierten Geraden und Koordinatenachsen begrenzt. Um herauszufinden, von welcher Seite, stellen wir fest, dass der Punkt zur ODR gehört, da er das System der Ungleichungen erfüllt:
Wir schattieren den Bereich so, dass der Punkt (3; 3) in den schattierten Teil fällt. Wir erhalten eine unbeschränkte Fläche, die von der Polylinie ABCDE begrenzt wird.
Wir bauen eine beliebige Linie des Zielfunktionsniveaus, zum Beispiel
(A3.1) .
Bei .
Bei .
Zeichnen Sie eine Gerade durch die Punkte (0; 7) und (7; 0).
Da die Koeffizienten bei und positiv sind, steigt er mit steigendem und.
Um das Maximum zu finden, müssen Sie eine parallele Gerade ziehen, die in aufsteigender Richtung maximal entfernt ist und durch mindestens einen Punkt der Fläche ABCDE verläuft. Da die Region jedoch von der Seite großer Werte von und unbegrenzt ist, kann eine solche gerade Linie nicht gezeichnet werden. Egal welche Gerade wir ziehen, es wird immer Punkte der Region geben, die in Richtung zunehmender und weiter entfernt liegen. Daher gibt es kein Maximum. beliebig groß gemacht werden kann.
Wir suchen ein Minimum. Wir zeichnen eine Gerade parallel zur Geraden (A3.1) und die am weitesten von ihr entfernte in abnehmender Richtung, die durch mindestens einen Punkt der Fläche ABCDE verläuft. Eine solche Gerade geht durch den Punkt C. Aus der Konstruktion bestimmen wir ihre Koordinaten.
.
Minimaler Zielfunktionswert:
Es gibt keinen Maximalwert.
Mindestwert
.
Die Werkstatt stellt die Produkte A und B her. Der Rohstoffverbrauch, der Lagerbestand und der Gewinn aus dem Verkauf jedes Produkts sind in der Tabelle aufgeführt.
| Art des Rohstoffs | Produktverbrauch | Aktie | EIN | B | 48 | 12 | 600 | 24 | 21 | 840 | 15 | 27 | 1350 | Profitieren | 12 | 18 |
Finden Sie einen Plan für die Herstellung von Produkten, der dem Unternehmen den maximalen Gewinn aus ihrem Verkauf bietet. Lösen Sie das Problem grafisch.
Die Lösung des Problems
Ökonomisches und mathematisches Modell des Problems
Mit und bezeichnen wir die Menge der hergestellten Produkte des Typs A bzw. B.
Dann sind die Ressourcengrenzen:
Außerdem im Sinne des Problems
Zielfunktion, die den Gewinn aus dem Verkauf von Produkten ausdrückt:
Wir erhalten das folgende ökonomische und mathematische Modell:
Erstellen einer Zeichnung
Um den Bereich zulässiger Lösungen zu konstruieren, konstruieren wir im Koordinatensystem die Grenzlinien, die diesen Ungleichungsbeschränkungen entsprechen:
Suchen wir die Punkte, durch die die Linien verlaufen:
Die Lösung jeder Ungleichung des LPP-Beschränkungssystems ist eine Halbebene, die die Grenzlinie enthält und auf einer Seite davon liegt.
Um eine Halbebene zu definieren, nehmen Sie einen beliebigen Punkt, z. B. einen Punkt, der nicht zur Geraden (1) gehört, und setzen Sie die Koordinaten (0; 0) in die entsprechende Ungleichung ein. Weil die Ungleichung ist wahr:
Das Lösungsgebiet der entsprechenden 1. Ungleichung entspricht der linken Halbebene
Nehmen Sie einen beliebigen Punkt, zB einen Punkt, der nicht zur Geraden (2) gehört, setzen Sie die Koordinaten (0; 0) in die entsprechende Ungleichung ein. Weil die Ungleichung ist wahr:
Das Lösungsgebiet der entsprechenden 2. Ungleichung entspricht der linken Halbebene
Um eine Halbebene zu definieren, nehmen Sie einen beliebigen Punkt, z. B. einen Punkt, der nicht zur Geraden (3) gehört, und setzen Sie die Koordinaten (0; 0) in die entsprechende Ungleichung ein. Weil die Ungleichung ist wahr:
Der Lösungsbereich der entsprechenden dritten Ungleichung entspricht der unteren Halbebene
Der Bereich der zulässigen Lösungen ist die Figur.
Wir bilden einen Vektor, dessen Koordinaten proportional zu den Koeffizienten der Zielfunktion sind.
Zeichnen Sie eine ebene Linie senkrecht zum konstruierten Vektor.
Den optimalen Plan finden
Verschieben Sie die Niveaulinie in Richtung des Vektors, so dass sie am äußersten Punkt den Bereich der möglichen Lösungen berührt. Die Lösung des Maximums ist der Punkt D, dessen Koordinaten als Schnittpunkt der Geraden (2) und der Achse gefunden werden.
Somit ist es notwendig, 40 Einheiten zu produzieren. Produkte B. Die Herstellung von Produkt a ist unrentabel. In diesem Fall ist der Gewinn maximal und beträgt WE 720.
In dieser Lektion lernen wir die grafische Lösungsmethode kennen Probleme der linearen Programmierung, also solche Probleme, bei denen es erforderlich ist, eine Lösung für ein System von linearen Gleichungen und (oder) Ungleichungen (ein System von Nebenbedingungen) zu finden, bei dem die Zielfunktion - eine lineare Funktion - den optimalen Wert annimmt.
Aufgrund der Tatsache, dass die Klarheit der grafischen Lösung nur in der Ebene erreicht wird, können wir uns mit der grafischen Darstellung des Problems nur im zweidimensionalen Raum vertraut machen. Diese Darstellung eignet sich für ein System von Ungleichungsbeschränkungen mit zwei Variablen oder für Gleichungssysteme, bei denen die Anzahl der Variablen um 2 größer ist als die Anzahl der Gleichungen, dh die Anzahl der freien Variablen beträgt zwei.
Daher hat die grafische Methode einen so engen Anwendungsbereich, dass man nicht von einer speziellen Methode zur Lösung von Problemen der linearen Programmierung sprechen kann.
Für die Entwicklung visueller Darstellungen von Lösungen für lineare Programmierprobleme ist die grafische Methode jedoch von besonderem Interesse. Darüber hinaus können Sie die Gültigkeit von . geometrisch bestätigen Theoreme der linearen Programmierung .
Theoretische Grundlagen der grafischen Methode
Also ein lineares Programmierproblem. Es ist erforderlich, nicht negative Werte der Variablen zu finden und das Ungleichungssystem zu erfüllen
bei der die lineare Form den optimalen Wert annimmt.
Beispiel 3.
Beispiel 4. Grafisches Lösen eines linearen Programmierproblems, bei dem es erforderlich ist, das Minimum einer Funktion unter Randbedingungen zu finden
Wir lösen weiterhin gemeinsam Probleme grafisch
Bisher basieren die Erkenntnisse auf der Tatsache, dass die Lösungsmenge eines linearen Programmierproblems so konfiguriert ist, dass die optimale Lösung endlich und eindeutig ist. Sehen wir uns nun Beispiele an, bei denen diese Bedingung verletzt wird. In diesen Beispielen wird das Entscheidungspolygon wie in den vorherigen Beispielen gezeigt konstruiert, aber lassen Sie uns auf die Merkmale eingehen, die diese außergewöhnlichen Beispiele auszeichnen.
Beispiel 5. Grafisches Lösen eines linearen Programmierproblems, bei dem es erforderlich ist, das Maximum einer Funktion unter Randbedingungen zu finden
Lösung. Die Abbildung zeigt: einen unbegrenzten vielfältigen Lösungsbereich dieses Beschränkungssystems, die Anfangsniveaulinie (schwarz), einen Vektor (burgunderrot), der die Bewegungsrichtung der Anfangsniveaulinie angibt, um das Maximum der Zielfunktion zu finden.
Es ist leicht zu erkennen, dass die Funktion F kann für ein gegebenes Restriktionssystem unbegrenzt zunehmen, also können wir das bedingt schreiben.
Beispiel 6. Grafisches Lösen eines linearen Programmierproblems, bei dem es erforderlich ist, das Maximum einer Funktion unter Randbedingungen zu finden
