Sie wissen, was es bedeutet, ein System zu optimieren, um das bestmögliche Ergebnis zu erzielen, wenn Sie Ingenieurstudent oder Ingenieur sind.
Die Optimierung einer Lösung ist der Schlüssel zum Erfolg – vom Brückenbau bis zur Softwareentwicklung.
An dieser Stelle kommt die Idee einer grundsätzlich zulässigen Lösung ins Spiel.
Es ist eine Grundidee der linearen Programmierung, mit der Sie herausfinden können, welche Lösung aus einer Menge möglicher Lösungen die beste ist.
Aber warum ist es so wichtig? In diesem Artikel werde ich über grundlegende praktikable Lösungen sprechen und wie sie verwendet werden können, um technische Probleme in der realen Welt zu lösen.
Ich werde darüber sprechen, wie man sie findet, woraus sie bestehen und warum sie wichtig sind.
Egal, ob Sie ein erfahrener Ingenieur oder ein Student sind, der gerade erst anfängt, kommen Sie mit uns, wenn ich in die Welt der grundlegenden machbaren Lösungen eintauche und Ihnen zeige, wie Sie die Leistungsfähigkeit der linearen Programmierung nutzen können.
Grundlegende durchführbare Lösung verstehen
Formale Definition:
Eine grundlegende Lösung für ein lineares Programmmodell, in dem alle Variablen nichtnegativ sind.
Eine grundlegende zulässige Lösung (BFS) ist eine Schlüsselidee in der linearen Programmierung, die hilft, die besten Lösungen zu finden.
Ein BFS ist eine Lösung mit der kleinstmöglichen Anzahl von Nicht-Null-Variablen.
Es ist eine Ecke des Polyeders der zulässigen Lösungen.
Mit anderen Worten, ein BFS ist eine Basislösung, die die nicht negativen Nebenbedingungen erfüllt und in der zulässigen Region oder Problemzone liegt.
Finden einer optimalen grundlegenden machbaren Lösung
Um das beste BFS zu finden, müssen wir Folgendes tun:
- Schreiben Sie das Programm in Standardform für eine lineare Folge.
- Verwandle das Ungleichungssystem in eine erweiterte Matrix.
- Finden Sie heraus, welche Variablen grundlegend sind und welche nicht.
- Finden Sie heraus, was die grundlegenden Variablen in Bezug auf die anderen Variablen sind.
- Fügen Sie diese Ausdrücke in die Zielfunktion ein, um eine Funktion nur der Variablen zu erhalten, die nicht grundlegend sind.
- Finden Sie eine nicht grundlegende Variable, die erhöht werden kann, ohne irgendwelche Einschränkungen zu brechen, und die die Zielfunktion verbessert.
Diese Variable ist jetzt eine Basisvariable, und eine der anderen Basisvariablen ist keine Basisvariable mehr.
Wenn es eine optimale Lösung gibt, muss sie an einem der Enden oder Scheitelpunkte des Bereichs liegen, wo Lösungen möglich sind.
Wenn also ein LP eine optimale Lösung hat, hat es eine optimale Lösung an einem Extrempunkt der zulässigen Menge.
Außerdem gibt es immer ein optimales BFS, wenn es eine optimale Lösung gibt.
Verwenden der Simplex-Methode zum Finden eines optimalen BFS
Die Simplex-Methode ist ein Algorithmus zur Lösung von Problemen in der linearen Programmierung.
Es bewegt sich von einem BFS zu einem "benachbarten" BFS unter Verwendung des Pivot-Verfahrens.
Bei der Pivot-Prozedur wird eine Nicht-Basisvariable ausgewählt, um eine Basisvariable zu werden, und dann wird die aktuelle BFS verwendet, um nach den neuen Basisvariablen aufzulösen.
Wenn keine nicht grundlegende Variable geändert werden kann, um die Zielfunktion zu verbessern, ist der Algorithmus fertig.
Warum grundlegende machbare Lösungen entscheidend für die Lösung komplexer technischer Probleme sind
Immer noch schwer zu verstehen? Lassen Sie mich die Sichtweise etwas ändern:
Wer braucht schon einfache, praktikable Antworten? Wirf einfach alles zusammen und hoffe das Beste.
Denn wer braucht Optimierung, wenn Chaos so viel mehr Spaß macht? Willkommen in der Welt der nichtnegativen Variablen, wo alles nur ein Vorschlag ist und ein Scheitern fast sicher ist.
Oder ist es?
Lassen Sie uns untersuchen, warum das scheinbar grundlegende Konzept grundlegender machbarer Lösungen alles andere als einfach ist und warum sie möglicherweise nur der Schlüssel zur Lösung selbst der komplexesten technischen Probleme sind.
Okay, das war nur ein Witz, der wie eine Fernsehwerbung aussehen sollte.
Kommen wir nun zurück zur Erklärung.
Grundlegende machbare Lösung finden
Eine grundlegende zulässige Lösung (BFS) ist eine Lösung für ein lineares Optimierungsproblem, das alle Einschränkungen erfüllt und die geringste Anzahl von Variablen ungleich Null aufweist.
Aus geometrischer Sicht ist jede BFS eine Ecke des Polyeders zulässiger Lösungen.
Wenn es eine beste Lösung gibt, muss es auch einen besten ersten Schritt geben.
In diesem Artikel sprechen wir darüber, wie man eine anfängliche zulässige Basislösung findet, wie man alle grundlegenden zulässigen Lösungen findet und wie man eine grundlegende zulässige Lösung ohne Schlupfvariablen findet.
Finden einer ersten grundlegenden machbaren Lösung
Je nach Problemstellung können wir verschiedene Methoden anwenden, um eine erste Basislösung zu finden, die für ein lineares Optimierungsproblem funktioniert.
Eine Möglichkeit besteht darin, Schlupfvariablen zu den Einschränkungen für Ungleichungen hinzuzufügen und alle anderen Variablen auf Null zu setzen.
Die Slack-Variablen werden zu Basisvariablen, und der Rest sind Nicht-Basisvariablen.
Das zweiphasige Simplex-Verfahren ist eine weitere Möglichkeit, das Problem zu lösen.
Dieses Verfahren beinhaltet das Lösen eines extralinearen Programmierproblems, um eine anfängliche grundlegende Lösung zu finden, die machbar ist.
Sobald eine erste zulässige Basislösung gefunden wurde, kann die Simplex-Methode verwendet werden, um von einer zulässigen Basislösung zur nächsten und dann zur besten Lösung zu gelangen.
Alle grundlegenden machbaren Lösungen finden
Es kann mehr als eine grundlegende Lösung geben, die für ein lineares Programm funktioniert.
Wir können das System ändern, indem wir Schlupfvariablen hinzufügen und dann das neue System verwenden, um alle grundlegenden zulässigen Lösungen für ein lineares Programm zu finden.
Dann werden diese grundlegenden zulässigen Lösungen verwendet, um die grundlegenden zulässigen Lösungen für das ursprüngliche Problem zu finden.
Finden einer grundlegenden machbaren Lösung ohne Slack-Variablen
Wir müssen Schlupfvariablen verwenden, um die Kleiner-als-Einschränkungen loszuwerden, damit wir eine grundlegende Lösung finden können, die ohne Schlupfvariablen funktioniert.
Eine Slack-Variable ist nur die Differenz zwischen der rechten Seite einer Einschränkung und der linken Seite.
Beispielsweise definieren wir für die erste Einschränkung eine Schlupfvariable x4 = 14 - 2x1 - x2 - x3. In Bezug auf diese neue Variable ist die erste Einschränkung einfach äquivalent zu x4 ≥ 0, was eine positive Einschränkung für x4 ist.
Wenn wir diese Schlupfvariablen hinzufügen, erhalten wir ein lineares Programm, das mit dem ursprünglichen identisch ist, außer dass alle Einschränkungen entweder Gleichungen oder Einschränkungen sind, die sagen, dass etwas positiv ist.
Die Menge der Basisvariablen, die in der Basislösung andere Werte als Null haben, wird als Basis bezeichnet.
Variablen, die in der Basislösung den Wert Null haben, sind keine Basisvariablen.
Um die beste Lösung zu finden, müssen wir einen Vektor x finden, der alle Regeln erfüllt und den größten oder kleinsten Wert für das Ziel erhält.
Aber um die beste Lösung zu finden, sind mehr Schritte erforderlich, als nur eine Lösung zu finden, die funktioniert und keine Schlupfvariablen hat.
Es ist nicht immer möglich, eine grundlegende Lösung ohne Schlupfvariablen zu finden, insbesondere für Probleme mit weniger als Einschränkungen.
Um eine grundlegende zulässige Lösung zu finden, müssen Sie die Simplex-Methode oder einen anderen linearen Programmieralgorithmus verwenden, um nach einer Lösung zu suchen, die alle Einschränkungen erfüllt und die wenigsten Nicht-Null-Variablen hat.
Eigenschaften und Bedeutung der grundlegenden machbaren Lösung
Eigenschaften der grundlegenden durchführbaren Lösung
Eine zulässige Basislösung hat höchstens m Variablen, die nicht null sind, und mindestens n Variablen, die null sind, wobei n die Anzahl der Entscheidungsvariablen und m die Anzahl der Nebenbedingungen ist.
Ein BFS ist eine Ecke des Polyeders möglicher Lösungen, und jedes BFS hat n aktive Einschränkungen, die linear unabhängig sind.
Wenn es eine beste Lösung gibt, muss es auch einen besten ersten Schritt geben.
Das Wichtigste an zulässigen Basislösungen ist, dass sie die Enden der Menge konvexer Lösungen für ein lineares Programmierproblem sind.
Um die beste Antwort zu finden, durchläuft der Simplex-Algorithmus eine Reihe von BFSs.
Der Simplex-Algorithmus durchsucht alle grundlegenden möglichen Lösungen auf organisierte Weise, um die beste zu finden.
Bedeutung der grundlegenden durchführbaren Lösung
Es ist wichtig, eine mögliche grundlegende Lösung zu finden, da dies hilft, die beste Antwort auf Probleme der linearen Programmierung zu finden.
Es gibt auch komplexen Algorithmen einen Ausgangspunkt und kann verwendet werden, um herauszufinden, ob ein lineares Programm möglich ist oder nicht.
Um alle grundlegenden zulässigen Lösungen für ein lineares Programm zu finden, können Sie das System ändern, indem Sie Schlupfvariablen hinzufügen und dann das geänderte System verwenden, um alle grundlegenden zulässigen Lösungen zu finden.
Dann werden diese grundlegenden zulässigen Lösungen verwendet, um die grundlegenden zulässigen Lösungen für das ursprüngliche Problem zu finden.
Video: Grundlegende praktikable Lösungen
Tipp: Aktivieren Sie die Untertitel-Schaltfläche, wenn Sie sie benötigen. Wählen Sie „automatische Übersetzung“ im Einstellungs-Button, wenn Sie mit der gesprochenen Sprache nicht vertraut sind. Möglicherweise müssen Sie zuerst auf die Sprache des Videos klicken, bevor Ihre bevorzugte Sprache für die Übersetzung verfügbar ist.
Anwendungsfälle
| Benutzt in: | Beschreibung: |
|---|---|
| Zuweisung von Ressourcen: | BFS kann verwendet werden, um begrenzte Ressourcen auf mehrere Projekte aufzuteilen, sodass mit dem wenigsten das meiste erreicht werden kann. Diese Methode kann in vielen verschiedenen Bereichen wie Transport, Landwirtschaft und Finanzen eingesetzt werden. |
| Optimierung des Netzwerks: | BFS kann verwendet werden, um Kommunikations-, Transport- und Logistiknetzwerke besser funktionieren zu lassen. BFS kann helfen, die besten Routen für Waren und Dienstleistungen zu finden, den Zeit- und Geldaufwand für den Transport zu reduzieren und die Lieferungen zu beschleunigen und genauer durchzuführen. |
| Produktionsplanung: | BFS kann verwendet werden, um die Produktion so zu planen, dass Ressourcen wie Arbeitskräfte, Rohstoffe und Ausrüstung bestmöglich genutzt werden, um das Beste aus ihnen herauszuholen. BFS kann dazu beitragen, die Produktionskosten zu senken, Abfall zu reduzieren und die Effizienz zu verbessern. |
| Finanzielle Planung: | In der Finanzplanung kann BFS verwendet werden, um Anlageportfolios zu optimieren, Risiken zu senken und das meiste Geld zurückzubekommen. BFS kann helfen, den besten Weg zu finden, um Vermögenswerte aufzuteilen, Transaktionskosten zu senken und mehr Geld zu verdienen. |
| Management der Lieferkette: | BFS kann zur Verbesserung des Waren- und Dienstleistungsflusses von Lieferanten zu Kunden im Rahmen des Supply Chain Managements eingesetzt werden. BFS kann helfen, die beste Menge an Lagerbeständen zu ermitteln, die Vorlaufzeiten zu verkürzen und den Kundenservice zu verbessern. |
Abschluss
Wenn dieser Blick auf grundlegende machbare Lösungen zu Ende geht, wird klar, dass sie ein wichtiges Werkzeug für jeden Ingenieur oder Ingenieurstudenten sind.
Von der Suche nach dem besten Weg zum Aufbau eines komplizierten Systems bis hin zur optimalen Nutzung der verfügbaren Ressourcen bieten grundlegende praktikable Lösungen einen Rahmen, um das bestmögliche Ergebnis zu erzielen.
Aber sie sind nicht nur nützlich, sondern zeigen auch, wie elegant und schön Mathematik sein kann.
Es ist erstaunlich, dass Sie komplizierte Probleme auf einen einfachen Satz von Gleichungen herunterbrechen und diese Gleichungen dann verwenden können, um Probleme in der realen Welt zu lösen.
Es ist eine gute Erinnerung daran, dass es beim Ingenieurwesen darum geht, Probleme zu lösen, und dass wir durch die Nutzung der Kraft der Mathematik Antworten finden können, die einst für unmöglich gehalten wurden.
Wenn Sie also mehr über Engineering lernen, denken Sie daran, was Sie über einfache Lösungen gelernt haben, die funktionieren, und nutzen Sie sie, um die Welt zu einem besseren und effizienteren Ort zu machen.
Links und Referenzen
Bücher:
- Lineare Programmierung: Grundlagen und Erweiterungen
- Lineare Programmierung: Theorie und Anwendungen
Teilen auf…
