Ein Beispiel für die Lösung eines Problems mit der Simplex-Methode in Excel. Jordan-Gauss-Transformation und Simplex-Methode in Excel

Eine Lösung zu finden ist ein Add-on Microsoft Excel, mit dem Sie unter Berücksichtigung der vom Anwender vorgegebenen Randbedingungen die optimale Lösung des Problems finden.

Wir werden die Suche nach einer Lösung in betrachten (dieses Add-In hat einige Änderungen im Vergleich zu . erfahren) vorherige Version v.
In diesem Artikel betrachten wir:

Erstellung eines Optimierungsmodells auf einem MS EXCEL Sheet
Anpassung Suche nach einer Lösung;
einfaches Beispiel (lineares Modell).

Solution Seeker installieren

Befehl Eine Lösung finden ist in der Gruppe Analyse in der Registerkarte Daten.

Wenn der Befehl Eine Lösung finden in einer Gruppe Analyse nicht verfügbar ist, müssen Sie das gleichnamige Add-on aktivieren.
Dafür:

Auf der Registerkarte Datei Team auswählen Optionen und dann die kategorie Add-ons;
Auf dem Feld Steuerung Wähle Wert Excel-Add-Ins und drücke den Knopf Gehen;
Auf dem Feld Verfügbare Add-ons Aktivieren Sie das Kontrollkästchen neben Eine Lösung finden und klicken Sie auf OK.

Notiz... Fenster Add-ons auch im Reiter verfügbar Der Entwickler... So aktivieren Sie diese Registerkarte.

Nach dem Drücken der Taste Eine Lösung finden in einer Gruppe Analyse, sein Dialogfeld wird geöffnet .

Bei häufigem Gebrauch Eine Lösung finden Es ist bequemer, es über die Symbolleiste für den Schnellzugriff zu starten als über die Registerkarte Daten. Um eine Schaltfläche im Panel zu platzieren, klicken Sie mit der rechten Maustaste darauf und wählen Sie Zur Symbolleiste für den Schnellzugriff hinzufügen.

Über Modelle

Dieser Abschnitt ist für diejenigen gedacht, die sich gerade mit dem Konzept des Optimierungsmodells vertraut machen.

Rat... Vor Gebrauch Eine Lösung finden Wir empfehlen dringend, die Literatur zur Lösung von Optimierungsproblemen und zum Erstellen von Modellen zu studieren.

Nachfolgend finden Sie ein kleines Bildungsprogramm zu diesem Thema.

Überbau Eine Lösung finden hilft bei der Bestimmung Die beste Weise tun etwas:

„Etwas“ kann die Zuweisung von Geld für Investitionen, das Laden eines Lagers, die Lieferung von Waren oder jede andere wesentliche Aktivität umfassen, bei der eine optimale Lösung erforderlich ist.
Der „beste Weg“ bzw. die optimale Lösung heißt in diesem Fall: Gewinn maximieren, Kosten minimieren, erreichen beste Qualität usw.

Hier sind einige typische Beispiele für Optimierungsprobleme:

Bestimmen Sie, bei welchem Einkommen aus dem Verkauf von hergestellten Produkten das Maximum ist;
Bestimmen Sie, zu welchem Zeitpunkt die Gesamtkosten des Transports minimal wären;
Stellen Sie fest, dass die Gesamtkosten für die Herstellung von Produkten minimal wären;
Bestimmen Sie den Mindesttermin für alle Projektarbeiten (kritischer Pfad).

Um die Aufgabe zu formalisieren, ist es erforderlich, ein Modell zu erstellen, das die wesentlichen Merkmale des Fachgebiets widerspiegelt (und keine kleinen Details enthält). Es ist zu beachten, dass das Modell optimiert wird Eine Lösung finden durch nur einen Indikator(diese optimierte Metrik heißt Zielfunktion).
In MS EXCEL-Modell ist eine Sammlung verwandter Formeln, die Variablen als Argumente verwenden. Normalerweise können diese Variablen nur zulässige Werte unterliegen benutzerdefinierten Einschränkungen.
Eine Lösung finden wählt solche Werte dieser Variablen (vorbehaltlich der angegebenen Einschränkungen) so aus, dass die Zielfunktion maximal (Minimum) oder gleich einem bestimmten numerischen Wert ist.

Notiz... Im einfachsten Fall lässt sich das Modell mit einer einzigen Formel beschreiben. Einige dieser Modelle können mit dem Tool optimiert werden. Vor der ersten Bekanntschaft mit Eine Lösung finden es ist sinnvoll, sich zunächst eingehend mit einem verwandten Instrument zu befassen.
Die wichtigsten Unterschiede Parameterauswahl von Eine Lösung finden:

Parameterauswahl funktioniert nur mit Modellen mit einer Variablen;
es ist unmöglich, Einschränkungen für Variablen darin festzulegen;
nicht das Maximum oder Minimum der Zielfunktion wird bestimmt, sondern ihre Gleichheit zu einem bestimmten Wert;
funktioniert nur bei linearen Modellen effektiv, im nichtlinearen Fall findet es das lokale Optimum (das dem Anfangswert der Variablen am nächsten kommt).

Erstellung eines Optimierungsmodells in MS EXCEL

Eine Lösung finden optimiert den Zielfunktionswert. Eine Zielfunktion ist eine Formel, die einen einzelnen Wert in einer Zelle zurückgibt. Das Ergebnis der Formel sollte von den Variablen des Modells abhängen (nicht unbedingt direkt, es ist möglich durch das Ergebnis der Berechnung anderer Formeln).
Einschränkungen des Modells können sowohl dem Variationsbereich der Variablen selbst als auch den Ergebnissen der Berechnung anderer Formeln des Modells auferlegt werden, die von diesen Variablen abhängen.
Alle Zellen, die Variablen und Modellbeschränkungen enthalten, sollten sich auf nur einem Blatt des Buchs befinden. Parameter in ein Dialogfeld eingeben Eine Lösung finden nur von diesem Blatt möglich.
Auf diesem Blatt muss sich auch die Zielfunktion (Zelle) befinden. Zwischenrechnungen (Formeln) können jedoch auf anderen Blättern platziert werden.

Rat... Organisieren Sie die Modelldaten so, dass sich auf einem MS EXCEL-Blatt nur ein Modell befindet. Andernfalls müssen Sie die Einstellungen ständig speichern und laden, um Berechnungen durchzuführen. Eine Lösung finden(siehe unten).

Geben wir einen Algorithmus für die Arbeit mit Eine Lösung finden, die die Entwickler selbst beraten (www.solver.com):

Zellen mit Entscheidungsvariablen definieren;
Erstellen Sie eine Formel in einer Zelle, die die Zielfunktion Ihres Modells berechnet.
Erstellen Sie Formeln in Zellen, die Werte berechnen, um sie mit Einschränkungen zu vergleichen ( links Ausdrücke);
Verwenden eines Dialogfelds Eine Lösung finden geben Sie Verweise auf Zellen mit Variablen, auf die Zielfunktion, auf Formeln für Einschränkungen und die Werte der Einschränkungen selbst ein;
Lauf Eine Lösung finden die optimale Lösung zu finden.

Lassen Sie uns all diese Schritte mit einem einfachen Beispiel durchführen.

Einfaches Anwendungsbeispiel Eine Lösung finden

Es ist notwendig, den Container mit Gütern zu beladen, um das Gewicht des Containers zu maximieren. Der Container hat ein Volumen von 32 Kubikmetern. Die Produkte sind in Kisten und Kisten enthalten. Jede Kiste mit Waren wiegt 20 kg, ihr Volumen beträgt 0,15 m3. Kiste - 80 kg bzw. 0,5 m3. Es ist erforderlich, dass die Gesamtzahl der Behälter mindestens 110 Stück beträgt.

Wir organisieren diese Modelle wie folgt (siehe Beispieldatei).

Modellvariablen (Menge jedes Behältertyps) sind grün hervorgehoben.
Zielfunktion (Gesamtgewicht aller Boxen und Boxen) ist rot.
Grenzen des Modells: durch die Mindestanzahl der Behälter (> = 110) und durch das Gesamtvolumen (<=32) – синим.
Die Zielfunktion berechnet sich nach der Formel = SUMMENPRODUKT (B8: C8, B6: C6) Ist das Gesamtgewicht aller in den Container geladenen Kisten und Kisten.
Ebenso berechnen wir das Gesamtvolumen - = SUMMENPRODUKT (B7: C7, B8: C8)... Diese Formel wird benötigt, um das Gesamtvolumen der Kisten und Kisten (<=32).
Um die Einschränkung des Modells festzulegen, berechnen wir außerdem die Gesamtzahl der Container = SUM (B8: C8).
Verwenden Sie jetzt den Dialog Eine Lösung finden Wir führen Verweise auf Zellen ein, die Variablen enthalten, eine Zielfunktion, Formeln für Einschränkungen und die Einschränkungswerte selbst (oder Verweise auf die entsprechenden Zellen).
Es ist klar, dass die Anzahl der Boxen und Boxen eine ganze Zahl sein muss - dies ist eine weitere Einschränkung des Modells.

Nach dem Drücken der Taste Finde eine Lösung die Anzahl der Kisten und Kisten wird so gefunden, dass ihr Gesamtgewicht (Zielfunktion) maximal ist und alle angegebenen Bedingungen erfüllt sind.

Zusammenfassung

Tatsächlich ist das Hauptproblem bei der Lösung von Optimierungsproblemen mit Eine Lösung finden ist keineswegs die Feinheiten der Einrichtung dieses Analysewerkzeugs, sondern die Korrektheit, ein der Aufgabenstellung angemessenes Modell zu bauen. Daher konzentrieren wir uns in anderen Artikeln genau auf den Bau von Modellen, denn ein "Kurven"-Modell ist oft der Grund für die Unmöglichkeit, eine Lösung mit Hilfe von . zu finden Eine Lösung finden.
Oft ist es einfacher, mehrere typische Aufgaben durchzusehen, eine ähnliche unter ihnen zu finden und dieses Modell dann für Ihre Aufgabe anzupassen.
Lösung klassischer Optimierungsprobleme mit Eine Lösung findenüberprüft.

Solver konnte keine praktikable Lösung finden

Diese Meldung erscheint, wenn Eine Lösung finden konnte keine Kombinationen von Variablenwerten finden, die gleichzeitig alle Einschränkungen erfüllen.
Wenn Sie verwenden Simplex-Methode zur Lösung linearer Probleme dann können Sie sicher sein, dass die Lösung nicht wirklich existiert.
Wenn Sie eine nichtlineare Problemlösungstechnik verwenden, die immer mit den Anfangswerten der Variablen beginnt, kann dies auch bedeuten, dass die zulässige Lösung weit von diesen Anfangswerten entfernt ist. Wenn du läufst Eine Lösung finden mit unterschiedlichen Anfangswerten der Variablen, dann wird vielleicht eine Lösung gefunden.
Stellen Sie sich vor, dass bei der Lösung des Problems durch eine nichtlineare Methode Zellen mit Variablen ungefüllt blieben (dh die Anfangswerte sind gleich 0), und Eine Lösung finden habe keine Lösung gefunden. Dies bedeutet nicht, dass es wirklich keine Lösung gibt (obwohl sie es sein kann). Basierend auf den Ergebnissen einiger Expertenbewertungen werden wir nun in die Zellen mit den Variablen einen weiteren Satz von Werten eingeben, der Ihrer Meinung nach dem optimalen (gewünschten) nahe kommt. In diesem Fall, Eine Lösung finden eine Lösung finden (wenn es sie wirklich gibt).

Notiz... Den Einfluss der Modellnichtlinearität auf die Berechnungsergebnisse können Sie im letzten Abschnitt des Artikels nachlesen.

In jedem Fall (linear oder nichtlinear) müssen Sie das Modell zunächst auf Konsistenz von Randbedingungen, dh Bedingungen, die nicht gleichzeitig erfüllt werden können, analysieren. Dies liegt meistens an der falschen Wahl des Verhältnisses (z.<= вместо >=) oder Grenzwert.
Wird beispielsweise im oben betrachteten Beispiel der Wert des maximalen Volumens auf 16 m3 statt 32 m3 gesetzt, dann widerspricht diese Beschränkung der Beschränkung der Mindestsitzzahl (110), da die Mindestanzahl der Plätze entspricht einem Volumen von 16,5 m3 (110 * 0,15, wobei 0,15 das Volumen der Kiste, d. h. des kleinsten Behälters) ist. Durch Einstellen eines maximalen Volumens von 16 m3 als Grenze, Eine Lösung finden wird keine Lösung finden.

Mit einer Begrenzung von 17 m3 Eine Lösung finden wird eine Lösung finden.

Einige Einstellungen Eine Lösung finden

Lösungsmethode
Das oben betrachtete Modell ist linear, d.h. die Zielfunktion (M ist das maximierbare Gesamtgewicht) wird durch die folgende Gleichung ausgedrückt M = a1 * x1 + a2 * x2, wobei x1 und x2 Modellvariablen (die Anzahl der Kästen und Kästen) sind und a1 und a2 sind ihre Gewichte. In einem linearen Modell müssen Nebenbedingungen auch lineare Funktionen von Variablen sein. In unserem Fall wird die Volumenbegrenzung V = b1 * x1 + b2 * x2 auch als linearer Zusammenhang ausgedrückt. Offensichtlich ist eine weitere Einschränkung - Maximale Tara (n) - ebenfalls linear x1 + x2 Lineare Probleme werden normalerweise mit der Simplex-Methode gelöst. Durch Auswahl dieser Lösungsmethode im Fenster Eine Lösung finden Sie können auch das Modell selbst auf Linearität überprüfen. Bei einem nichtlinearen Modell erhalten Sie folgende Meldung:

In diesem Fall ist es notwendig, eine Methode zur Lösung des nichtlinearen Problems zu wählen. Beispiele für nichtlineare Abhängigkeiten: V = b1 * x1 * x1; V = b1 * x1 ^ 0,9; V = b1 * x1 * x2, wobei x eine Variable und V eine Zielfunktion ist.

Schaltflächen Hinzufügen, Bearbeiten, Löschen
Mit diesen Schaltflächen können Sie Modellbeschränkungen hinzufügen, ändern und entfernen.

Reset-Knopf
Um alle Einstellungen zu entfernen Eine Lösung finden Drücken Sie den Knopf Zurücksetzen- Das Dialogfeld wird gelöscht.

Diese Option ist nützlich, wenn Sie verschiedene Beschränkungsoptionen verwenden. Beim Speichern von Modellparametern (Schaltfläche Laden speichern, dann drücke den Knopf Speichern). Optionen). Stellen Sie vor dem Speichern sicher, dass dieser Bereich keine Modelldaten enthält.
Um die gespeicherten Parameter zu laden, drücken Sie zuerst die Taste. Laden speichern, dann im angezeigten Dialogfeld die Schaltfläche Herunterladen, und legen Sie dann den Zellenbereich fest, der die zuvor gespeicherten Einstellungen enthält (Sie können nicht nur eine oberste Zelle angeben). OK klicken. Bestätigen Sie das Zurücksetzen der aktuellen Werte der Aufgabenparameter und das Ersetzen durch neue.

Genauigkeit
Beim Erstellen eines Modells hat der Forscher zunächst eine gewisse Schätzung der Variationsbreite der Zielfunktion und der Variablen. Unter Berücksichtigung der Berechnungen in MS EXCEL wird empfohlen, dass diese Schwankungsbreiten deutlich über der Berechnungsgenauigkeit liegen (diese wird normalerweise von 0,001 bis 0,000001 eingestellt). In der Regel werden die Daten im Modell so normalisiert, dass die Variationsbereiche der Zielfunktion und Variablen im Bereich von 0,1 - 100.000 liegen. Natürlich hängt alles vom spezifischen Modell ab, aber wenn sich Ihre Variablen um mehr ändern als 5-6 Größenordnungen, dann sollten Sie das Modell vielleicht "grob" z. B. mit der Logarithmus-Operation.

Die Entscheidung der LPP Simplex-Methode mit EXCEL-Tabellen

Das ursprüngliche LPP sei auf die kanonische Form reduziert, und sein Beschränkungssystem hat eine bevorzugte Form. Für das "Problem der Rohstoffnutzung" wird beispielsweise das mathematische Modell des entsprechenden Typs wie folgt aussehen:

Die erste Simplex-Tabelle auf dem EXCEL-Arbeitsblatt sieht so aus (Abbildung 10):

Unter der Annahme, dass der Student mit dem Algorithmus des tabellarischen Simplex-Verfahrens vertraut ist, beschreiben wir die Hauptschritte seiner Implementierung mit Hilfe von EXCEL-Tabellen.

Stufe 1. Wählen Sie die zulässige Spalte und Zeile aus und wählen Sie das zulässige Element aus (siehe Abb. 11).

Stufe 2. Ersetzen Sie die Spalten "Basis" und "С b" in der neuen Tabelle gemäß den Ausfüllregeln.

Die Elemente der auflösenden Zeile werden durch das auflösende Element geteilt und in die entsprechende Zeile der neuen Tabelle geschrieben:

, bei ich = r. (*)

Alle anderen Elemente der neuen Tabelle werden nach den Formeln berechnet:

, bei ich r (**)

wo ist ein Element der neuen Simplex-Tabelle, ein ij , - ein Element der vorherigen Simplex-Tabelle, ein rk- zulassendes Element, ein ich k- Element der Auflösungssäule, ein rj- ein Element der Berechtigungszeile.

Notiz ... Um die EXCEL-Funktion zum Kopieren von Formeln mit Änderung der Adressen der darin enthaltenen Zellen zu verwenden, ist es ratsam, die Formeln (*) und (**) nur für die Zellen der Spalte "B" zu programmieren und den unveränderlichen Zellen absolute Adressen zuzuweisen . Die Formeldaten werden dann in alle verbleibenden Zellen jeder Zeile in der neuen Tabelle kopiert.

Stufe 4. Die Elemente der letzten Zeile der neuen Tabelle werden entweder nach den Formeln (**) oder nach der Regel zum Füllen dieser Zeile gefüllt.

Die Berechnungsergebnisse in den EXCEL-Tabellen für unser Beispiel sind in Abb. 11 dargestellt und die in diesen Berechnungen verwendeten Formeln sind in Abb. 12.

Akulich I.L. Mathematische Programmierung in Beispielen und Problemen: Lehrbuch. Handbuch für Studierende der Wirtschaftswissenschaften. Spezialist. Universitäten. - M.: Höher. shk., 1986.-319s., mit Abb.

Sakovich V. A. Operations Research (Deterministische Methoden und Modelle): Ein Referenzhandbuch. - Mn.: Vysh. shk., 1984.-256s.

Taha H. Einführung in Operations Research: in 2 Büchern. Buch 1. Pro. aus dem Englischen - M.: Mir, 1985.-479s., Ill.

Methodische Anleitung zur praktischen Ausbildung im Fach "Mathematische Programmierung" (lineare Programmierung) für Studierende der wirtschaftswissenschaftlichen Fachrichtungen / Komp. Turovtsev G.V., Nudny I.P. - Saporoschje, ZGIA, 1984.-31s.

Mathematische Programmierung. Skript für Vollzeit- und Teilzeitstudierende der Wirtschaftswissenschaften / Glushchevsky V.V., Isaenko A.N. - Saporoschje: ZGIA, 2003 .-- 150p.

Senden Sie Ihre gute Arbeit in die Wissensdatenbank ist einfach. Verwenden Sie das untenstehende Formular

Studierende, Doktoranden, Nachwuchswissenschaftler, die die Wissensbasis in Studium und Beruf nutzen, werden Ihnen sehr dankbar sein.

Veröffentlicht am http://www.allbest.ru/

Lösen eines Problems mit Excel und der Simplex-Methode

Aufgabe (Verteilung)

Simplex-Methode

Lösen eines Problems mit Excel

Aufgabe (Verteilung)

Aufgabe 1 (Verteilung)

Im Unternehmen können 4 Produkttypen auf 3 separaten Wechselmaschinen hergestellt werden.

Bekannt:

Produktionsauftrag zur Freigabe von Produkten unterschiedlicher Art im Planungszeitraum

· Fonds der effektiven Arbeitszeit der Ausrüstung im geplanten Zeitraum -;

· Aufwandsquoten der Maschinenzeit für die Herstellung einer Produktionseinheit -;

· Gewinn in Rubel. aus dem Verkauf einer Produktionseinheit, die auf einer bestimmten Anlage hergestellt wurde -.

Die Ausgangsinformationen werden in der Tabelle im folgenden Formular angezeigt.

Tabelle 1. Ausgangsdaten

Fonds ef. Sklave. Zeit. -	Kostensätze der Zeit. pro Einheit Produkte - Gewinn pro Einheit. Produkte -

In der Aufgabe müssen Sie einen Plan für die Verteilung einer Produktionsaufgabe für die Freigabe von Produkten zwischen Ausführenden finden

an dem die Aufgabe mit dem maximalen Gesamtgewinn aus dem Verkauf von Produkten abgeschlossen werden würde.

LÖSUNG

Entwicklung eines ökonomischen und mathematischen Modells.

Die gesuchten Variablen - charakterisieren das Volumen der Produktion von m durch den Darsteller.

Dann ist die Matrix der benötigten Variablen

charakterisiert den Plan zur Verteilung der Produktionsaufgabe zur Herstellung von Produkten unter den Ausführenden.

Zielfunktion

charakterisierenden Gesamtgewinn aus dem Verkauf aller Produkte muss maximiert werden.

Beschränkungen der Verfügbarkeit und Nutzung der effektiven Arbeitszeit der ausübenden Künstler werden in Form eines Systems linearer Ungleichheiten (2) erfolgen:

Dieses Restriktionssystem kennzeichnet die Bedingung, dass die Gesamtkosten der effektiven Arbeitszeit jedes ausübenden Künstlers im Planungszeitraum für die Freigabe aller Arten von Produkten den Zeitrahmen nicht überschreiten dürfen. Somit erhält jeder Ausführende als Ergebnis der Lösung des Problems seine Aufgabe, basierend auf seinen Fähigkeiten. Wenn bei der Lösung des Problems eine Ausgleichsvariable einen Wert annimmt, charakterisiert sie die nicht ausgelastete effektive Arbeitszeit des einen oder anderen Ausführenden, die unter Produktionsbedingungen verwendet werden kann, um über die Aufgabe hinausgehende Produkte freizugeben.

Der nächste Restriktionsblock soll die Bedingung für die zwingende Erfüllung der allgemeinen Produktionsaufgabe für die Produktion von Produkten nach Typen widerspiegeln und wird durch ein lineares Gleichungssystem (3) dargestellt:

Die Bedingung für die Nicht-Negativität von Variablen:

Lassen Sie uns das Problem auf die kanonische Form reduzieren, dazu fügen wir Variablen zur Ungleichung hinzu (2) und fügen 4 künstliche Basen zu den Gleichungen hinzu (3). Als Ergebnis schreiben wir das mathematische Modell des Problems in der kanonischen Form auf:

Simplex-Methode

Lassen Sie uns dieses Problem mit der Simplex-Methode lösen, indem wir die Tabelle ausfüllen. Die Lösung erfordert mehrere Iterationen. Zeigen wir es.

Tabelle 1

In der obersten Zeile der Tabelle werden die Koeffizienten der Zielfunktion eingetragen, in der zweiten Zeile sind die Namen aller Unbekannten, die in den Simplex-Gleichungen enthalten sind. In die erste Spalte links werden die Koeffizienten der Zielfunktion geschrieben, die den grundlegenden Unbekannten entsprechen, die im Originalprogramm enthalten sind (in der Spalte aufgezeichnet). Die nächste, dritte in Folge, Spalte in der ersten Simplex-Tabelle wird mit den Werten der grundlegenden Unbekannten gefüllt. Als nächstes sind die Spalten, die Bedingungsvektoren darstellen. Ihre Zahl ist 19. In der nächsten Spalte, der ersten nach der Bedingungsmatrix, werden die Summen aller Elemente in Zeilen geschrieben. Die Spalte enthält Quotienten aus der Aufteilung der Elemente der letzten Spalte B in die Elemente einer bestimmten Spalte, der Bedingungsmatrix. Da wir eine künstliche Basis haben, gibt es in der Indexlinie zwei Berechnungen, in der ersten unter Berücksichtigung der Variablen und in der zweiten nur eine künstliche Basis. Da wir ein Maximierungsproblem haben, ist es notwendig, aus der Basis künstliche Basen abzuleiten. Wählen Sie in der zweiten Indexzeile die höchste positive Markierung aus. Wir haben - dies ist die erste Spalte. Wertverhältnis finden

und. Aus diesen Relationen wählen wir die kleinste, wir haben die vierte Zeile, dafür ist das geschätzte Verhältnis 1300. Wählen Sie die Zeile aus. Die letzte Spalte ist der Koeffizient, mit dem jedes Element der Zeile bei der Neuberechnung multipliziert wird. Es wird erhalten, indem die Elemente der ausgewählten Spalte durch das Schlüsselelement geteilt werden, das sich am Schnittpunkt der ausgewählten Spalte und der Zeile befindet. Für uns ist es 1. Wir führen die Neuberechnung für alle nicht ausgewählten Elemente durch, die wie folgt ausgeführt wird folgt: Subtrahiere das Element der Schlüsselzeile vom neu zu berechnenden Element, multipliziert mit dem neu berechneten Zeilenfaktor: und so sind alle Elemente. Aus der Basis leiten wir eine künstliche Basis ab, während wir eine Variable in die Basis einführen.

Die letzten beiden Zeilen sind Indexzeilen, bei denen die Werte der Zielfunktion neu berechnet werden, sowie die gesamte Indexzeile, wenn alle Elemente positiv oder null sind, wird das Problem gelöst.

Zeigen wir es.

Tabelle 2

Wählen wir die Spalte mit der Variablen aus. Wir finden die geschätzten Beziehungen, von denen wir die kleinste wählen - das sind 550. Aus der Basis leiten wir eine künstliche Variable ab, während wir die Variable in die Basis einführen. Wenn aus der Basis eine künstliche Basis abgeleitet wird, entfernen wir die entsprechende Spalte.

Tisch 3

Wählen Sie die Spalte aus. Das kleinste geschätzte Verhältnis, 600, befindet sich in der sechsten Reihe. Aus der Basis leiten wir eine künstliche Basis ab, während wir eine Variable in die Basis einführen.

Tabelle 4

Wählen wir die Spalte mit der Variablen aus. Das kleinste geschätzte Verhältnis, 28,57, steht in der ersten Reihe. Wir leiten eine Variable von der Basis ab, während wir eine Variable in die Basis einführen.

Tabelle 5

Wählen wir die Spalte mit der Variablen aus. Das kleinste geschätzte Verhältnis, 407,7, befindet sich in der dritten Reihe. Wir leiten eine Variable von der Basis ab, während wir eine Variable in die Basis einführen.

Tabelle 6

Wählen wir die Spalte mit der Variablen aus. Das kleinste geschätzte Verhältnis, 344,3, befindet sich in der siebten Reihe. Aus der Basis leiten wir eine künstliche Basis ab, während wir eine Variable in die Basis einführen.

Tabelle 7

Wählen wir die Spalte mit der Variablen aus. Das kleinste geschätzte Verhältnis, 3.273, befindet sich in der zweiten Reihe. Wir leiten eine Variable von der Basis ab, während wir eine Variable in die Basis einführen.

Tabelle 8

Wählen wir die Spalte mit der Variablen aus. Das kleinste geschätzte Verhältnis, 465, befindet sich in der siebten Reihe. Wir leiten eine Variable aus der Basis ab, während wir eine Variable in die Basis einführen.

Tabelle 9

Wählen wir die Spalte mit der Variablen aus. Das kleinste geschätzte Verhältnis, 109, steht in der dritten Reihe. Wir leiten eine Variable von der Basis ab, während wir eine Variable in die Basis einführen.

Tabelle 10

Wählen wir die Spalte mit der Variablen aus. Das kleinste geschätzte Verhältnis, 10, steht in der ersten Reihe. Wir leiten eine Variable von der Basis ab, während wir eine Variable in die Basis einführen.

Tabelle 11

Wählen wir die Spalte mit der Variablen aus. Das kleinste geschätzte Verhältnis, 147, steht in der zweiten Reihe. Wir leiten eine Variable von der Basis ab, während wir eine Variable in die Basis einführen.

Tabelle 12

Wählen wir die Spalte mit der Variablen aus. Das kleinste geschätzte Verhältnis, 367, befindet sich in der fünften Reihe. Wir leiten eine Variable von der Basis ab, während wir eine Variable in die Basis einführen.

Tabelle 13

Wählen wir die Spalte mit der Variablen aus. Das kleinste geschätzte Verhältnis, 128, steht in der vierten Zeile. Wir leiten eine Variable aus der Basis ab, während wir eine Variable in die Basis einführen.

Tabelle 14

Da es keine negativen Schätzungen in der Indexlinie gibt, wird ein optimaler Plan erhalten, für den das Produktionsvolumen durch die Matrix dargestellt wird

der Gewinn ist maximal und beträgt 17.275,31 Rubel.

Lösung des Problems mit Excel

Das mathematische Modell des Problems muss auf ET EXCEL übertragen werden. Dafür:

· Überdenken Sie die Organisation der Ausgangsdaten des Modells (objektive Funktionskoeffizienten und Beschränkungen) und geben Sie klare Namen.

· Reservieren Sie unabhängige Variablen des mathematischen Modells in separaten Zellen.

· Erstellen Sie in einer der Zellen eine Formel, die die Zielfunktion definiert.

· Wählen Sie Zellen aus und platzieren Sie Formeln darin, die den linken Seiten der Beschränkungen entsprechen.

· Geben Sie den Menüpunkt "Lösung suchen" ein, geben Sie die erforderlichen Daten ein und erhalten Sie die optimale Lösung für das Problem.

· Analysieren Sie die erhaltene Lösung und Berichte.

Betrachten wir die Abfolge von Aktionen für die Implementierung dieser Phasen der Problemlösung mit EXCEL.

Erstellen wir eine Tabelle für die Eingabe von Anfangsdaten.

Geben wir die Anfangsdaten in das erstellte Formular ein.

Die Zielfunktionskoeffizienten, die den Gewinn aus der Produktion einer Produktionseinheit jedes Typs (Einheitsgewinn) ausdrücken, werden in die Zellen B6 geschrieben: M6.

Die Ressourcenbeschränkungskoeffizienten, die den Bedarf für jede der Ressourcenarten für die Produktion einer Produktionseinheit bestimmen, befinden sich in den Zellen B9: M15. Die Zellen P9: P15 enthalten die rechte Seite der Ressourcengrenzen. Die Zellen B3: M3 sind für die unabhängigen Variablen des Problems reserviert - das gewünschte Produktionsvolumen.

Geben Sie in Zelle N7 die Formel für die Zielfunktion ein, indem Sie den Befehl zum Einfügen der SUMMENPRODUKT-Funktion anwenden:

Und füllen Sie auch die Einschränkungen auf der rechten Seite aus.

Danach können Sie mit der Suche nach einer Lösung beginnen. Um Optimierungsprobleme in EXCEL zu lösen, wird der Befehl NACH LÖSUNG SUCHEN des Menüs SERVICE verwendet.

Dieses Team arbeitet mit drei Hauptkomponenten eines optimierten Modells, das in ET gebaut wurde:

· Die Zelle, die die Zielfunktion der Aufgabe enthält.

· Modifizierbare Zellen mit unabhängigen Variablen.

· Die Zellen, die die linken Seiten der Beschränkungen der verfügbaren Ressourcen sowie einfache Beschränkungen der unabhängigen Variablen enthalten.

Betrachten wir die Reihenfolge der Eingabe dieser Komponenten.

Der Cursor befindet sich in Zelle N7 und der Befehl SERVICE - Nach einer Lösung suchen. Auf dem Bildschirm wird ein Dialogfeld angezeigt.

Füllen Sie im Fenster das Feld Zielzelle festlegen aus, das die Adresse $ N $ 7 enthalten sollte. Stellen Sie als Nächstes die Schaltfläche ein, um nach dem maximalen Wert zu suchen. Geben Sie im Feld Zellen ändern die Adressen der gesuchten Variablen $ B3: $ M3 ein. Dann sollten Sie die Einschränkungen über die Schaltfläche Hinzufügen eingeben.

Nachdem nun alle Randbedingungen für das Finden der optimalen Lösung festgelegt sind, können wir die Schaltfläche drücken:

Danach bekommen wir die Lösung des Problems.

Wenn die Berechnungen erfolgreich waren, werden nach Abschluss der Lösungssuche die Werte in die Tabelle eingefügt, und Sie können auch den Berichtstyp - Ergebnisse angeben, wodurch wir den nächsten Bericht erhalten können. Arbeitszeit Ausrüstung Gewinn

Folglich ist die Lösung in EXCEL die gleiche wie in der SIMPLEX-Methode, was bedeutet, dass das betrachtete Problem korrekt gelöst wird.

Gepostet auf Allbest.ru

...

Lösung des Problems mit der Simplex-Methode

Seien x 1, x 2, x 3 - die Anzahl der verkauften Waren in Tausend Rubel, 1, 2, 3 - ihre Gruppen. Dann hat das mathematische Modell des Problems die Form:

F = 4 x 1 + 5 x 2 + 4 x 3 -> max

0))) (~) "title =" (! LANG: delim (lbrace) (matrix (4) (1) ((2x_1 + 3x_2 + 6x_3 = 0))) (~)">!}

Wir lösen die Simplex-Methode.

Führe zusätzliche Variablen x 4 0, x 5 ≥ 0, x 6 ≥ 0 ein, um Ungleichungen in Gleichheiten umzuwandeln.

Nehmen Sie x 4 = 240 als Basis; x5 = 200; x6 = 160.

Wir geben die Daten ein in Simplex-Tabelle

Simplex-Tischnummer 1

Zielfunktion:

0 240 + 0 200 + 0 160 = 0

Wir berechnen die Scores mit der Formel:

Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0

Da es negative Bewertungen gibt, ist der Plan nicht optimal. Niedrigste Note:

Wir führen die Variable x 2 in die Basis ein.

Wir definieren eine Variable, die die Basis verlässt. Dazu finden wir das kleinste nicht-negative Verhältnis für die Spalte x 2.

= 26.667

Kleinstes nicht-negativ: Q 3 = 26,667. Wir leiten die Variable x 6 aus der Basis

Teilen Sie die dritte Reihe durch 6.
Von der 1. Zeile subtrahieren Sie die 3. Zeile, multipliziert mit 3
Von der 2. Zeile subtrahieren Sie die 3. Zeile, multipliziert mit 2

Wir berechnen:

Wir bekommen eine neue Tabelle:

Simplex-Tischnummer 2

Zielfunktion:

0 160 + 0 440/3 + 5 80/3 = 400/3

Wir berechnen die Scores mit der Formel:

Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1) / 2 + 0 (-1) / 3 + 5 1/6 - 0 = 5/6

Da es eine negative Schätzung Δ 1 = - 2/3 gibt, ist der Plan nicht optimal.

Wir führen die Variable x 1 in die Basis ein.

Wir definieren eine Variable, die die Basis verlässt. Dazu finden wir das kleinste nicht-negative Verhältnis für die Spalte x 1.

Das kleinste nicht-negativ: Q 3 = 40. Wir leiten die Variable x 2 aus der Basis

Teilen Sie die 3. Reihe durch 2/3.
Von der 2. Reihe subtrahieren Sie die 3. Reihe, multipliziert mit 8/3

Wir berechnen:

Wir bekommen eine neue Tabelle:

Simplex-Tischnummer 3

Zielfunktion:

0 160 + 0 40 + 4 40 = 160

Wir berechnen die Scores mit der Formel:

Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1) / 2 + 0 (-1) + 4 1/4 - 0 = 1

Da es keine negativen Bewertungen gibt, ist der Plan optimal.

Die Lösung des Problems:

Antworten

x 1 = 40; x2 = 0; x3 = 0; x4 = 160; x5 = 40; x6 = 0; Fmax = 160

Das heißt, es ist notwendig, die Waren des ersten Typs in Höhe von 40 Tausend Rubel zu verkaufen. Es ist nicht erforderlich, Waren der 2. und 3. Art zu verkaufen. In diesem Fall beträgt der maximale Gewinn F max = 160 Tausend Rubel.

Lösung des dualen Problems

Das Doppelproblem ist:

Z = 240 Jahre 1 + 200 Jahre 2 + 160 Jahre 3 -> min

Titel = "(! LANG: delim (lbrace) (matrix (4) (1) ((2y_1 + 4y_2 + 4y_3> = 4) (3y_1 + 2y_2 + 6y_3> = 5) (6y_1 + 4y_2 + 8y_3> = 4) (y_1, y_2, y_3> = 0))) (~)">!}

Führe zusätzliche Variablen y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 ein, um Ungleichungen in Gleichheiten umzuwandeln.

Konjugierte Variablenpaare des direkten und dualen Problems haben die Form:

Aus dem letzten Simplex der Tabelle Nr. 3 des direkten Problems finden wir die Lösung des dualen Problems:

Zmin = Fmax = 160;
y 1 = 4 = 0; y 2 = 5 = 0; y 3 = 6 = 1; y 4 = Δ 1 = 0; y 5 = 2 = 1; y 6 = 3 = 4;

Lektion 1. Lösen eines linearen Programmierproblems in Excel mit dem Add-In "Find Solution"

Ökonomische und mathematische Methoden und Modelle. Problem bei der Ressourcenzuordnung. Ein klassisches Beispiel und Lösungen für ein lineares Programmierproblem. Beschreibung der Verwendung des Add-Ins Find Solution in Excel. Die Bedingung des Problems ist hier -, weitere Beispiele für die Lösung von Problemen durch EMMM -

# ЭМММ #Excel # Matprogramming # SearchSolutions #Easyhelp

Lösen eines linearen Programmierproblems mit dem Add-In Nach einer Lösung suchen

Verwenden des Add-Ins Suchen Sie nach einer Lösung zum Lösen von Problemen der linearen Programmierung. Geben Sie eine Klasse, wenn das Video für Sie nützlich war.

Einfaches lineares Programmierproblem Nr. 2. Simplex-Methode zum Finden des Maximums.

Lösen eines einfachen linearen Programmierproblems mit der Simplex-Methode zum Ermitteln des Maximums. Für eine genauere Erklärung stehen Untertitel zur Verfügung.

Einfaches lineares Programmierproblem Nr. 1. Simplex-Methode zum Finden des Minimums.

Lösen eines einfachen linearen Programmierproblems mit der Simplex-Methode, um das Minimum zu finden. Zur weiteren Erläuterung stehen Untertitel zur Verfügung.

- Einfaches lineares Programmierproblem Nr. 3. Simplex-Methode zum Finden des Minimums.
- Lösung eines linearen Programmierproblems mit dem Dual-Simplex-Methoden-Algorithmus
- Lösungen des direkten dualen LP-Problems, Konstruktion des dualen LP-Problems.
- Lösung eines linearen Programmierproblems mit heterogenen Ungleichungen nach der Simplex-Methode
- Lineares Programmierproblem mit einem Gleichungssystem

Vorlesung 2: Das Problem der linearen Programmierung. Ressourcenproblem

Die Lösung des linearen Programmierproblems durch das Simplex-Verfahren wird betrachtet.
Vorlesung und Tests bei NOU INTUIT

Lineares Programmieren

Lösen eines linearen Programmierproblems mit der MS Excel-Lösungssuche
Das Textmaterial auf der Website befindet sich unter:

Lektion 2. Ein duales lineares Programmierproblem in Excel lösen

Stabilitätsanalyse für direkte und duale lineare Programmierprobleme in Excel. Sehen Sie hier den Zustand des Problems - weitere Beispiele zur Problemlösung hier -

#Excel #mathematikprogrammierung #easyhelp

Simplex-Methode Excel VBA (Lösen eines linearen Programmierproblems mit Makros)

Demonstration der Arbeit eines Makros in Excel. Lösung eines linearen Programmierproblems nach der Simplex-Methode.
Makro bestellen - [E-Mail geschützt]

Lösung Labor arbeit in Excel zur Bestellung

Simplex-Methode zur Lösung linearer Programmierprobleme

Lineares Programmieren. Simplex-Tabelle. Zulässiges Element. Zulässige Zeichenfolge. Zulässige Spalte. Simplex-Beziehung
Eine grafische Methode zur Lösung von Optimierungsproblemen.

Ein Programm, das die Simplex-Methode implementiert

Das Programm ist unter folgendem Link verfügbar:

Lösen eines Transportproblems in Excel mit dem Add-In "Find a solution"

Lineares Programmierproblem. Transportproblem. Excel-Lösung, Nachhaltigkeitsanalyse. Die Bedingung des Problems ist hier -, weitere Beispiele zum Lösen von Problemen in der mathematischen Programmierung sind hier -

#excel #mathprogramming #transportationProblem #linearProgramming #SearchSolutions #easyhelp #Stabilitätsanalyse

Duale Methode

Optimierungsmethoden 12. Lineare Programmierung, Simplex-Methode

Virishuєmo Simplex-Methode werde ich übergeben

Einfaches lineares Programmierproblem Nr. 3. Simplex-Methode zum Finden des Minimums.

Höchst Detaillösung einfaches lineares Programmierproblem mit der Simplex-Methode, um das Minimum zu finden.

Einfaches lineares Programmierproblem Nr. 1. Simplex-Methode zum Finden des Minimums.
- Einfaches lineares Programmierproblem # 2. Simplex-Methode zum Finden des Maximums.
- Lösung eines linearen Programmierproblems mit dem Dual-Simplex-Methoden-Algorithmus
- Lösungen des direkten dualen LP-Problems, Konstruktion des dualen LP-Problems.
- Lösung eines linearen Programmierproblems mit heterogenen Ungleichungen nach der Simplex-Methode
- Lineares Programmierproblem mit einem Gleichungssystem

Grafische Lösung des linearen Programmierproblems

Nachdem Sie in der vorherigen Videolektion ein Modell eines linearen Programmierproblems erstellt haben, müssen Sie dessen Lösung finden. Eine der gebräuchlichsten Optimierungsmethoden ist die grafische Methode. Es kann verwendet werden, wenn die Anzahl der unbekannten Variablen X zwei nicht überschreitet. Zu den Vorteilen der Methode gehören ihre Einfachheit, die Nachteile - die Genauigkeit der erhaltenen Lösung hängt davon ab, wie genau wir die Skala beim Konstruieren beobachtet haben. Das zeigt Ihnen unser Video-Tutorial.

Wenn Ihnen dieses Video einen echten Nutzen gebracht hat und Sie dem Autor danken möchten:
WMR: R370550256930
WMZ: Z939960413056

In unserer Auswahl finden Sie weitere Video-Tutorials zum Arbeiten mit Microsoft Excel-Tabellen:

Auf unserer Website finden Sie noch mehr weitere Lernvideo-Tutorials:

Lösen von Problemen der linearen Programmierung mit Excel

Optimierungsprobleme, lineare Programmierprobleme, dynamische Programmierung- Lösung mit Tabellenkalkulationen

Siegel

Auch interessant:

So erstellen Sie einen transparenten Hintergrund für ein Bild

Vorlagen für Photoshop CS6 herunterladen

So fixieren Sie Ebenen in Photoshop

Wir empfehlen zu lesen:

2021-09-21 05:14:28

Inhaltsorientiertes Entfernen und Verschieben von Objekten

2021-09-21 05:14:28

Installieren und verwenden Sie Aktionen in der Photoshop atn-Datei, wie zu installieren

2021-09-21 05:14:28

Verwenden von Aktionen in Photoshop So laden Sie eine Aktion

Fortsetzung des Themas:

Geräte

So aktivieren und deaktivieren Sie das Raster in Photoshop So aktivieren Sie Hilfslinien in Photoshop

Photoshop (FS) löst viele Probleme, vom Pickel bis zum Bigboard auf dem Boden des Hauses. Dazu hat er für jeden Geschmack ein Set an Werkzeugen parat. Symmetrie ist wichtig...