Wenn Sie Ingenieur oder Student der Ingenieurwissenschaften sind, wissen Sie vielleicht, was es bedeutet, zu optimieren.
Um das bestmögliche Ergebnis zu erzielen, ist es wichtig, die beste Vorgehensweise zu finden.
Bei der linearen Programmierung können Sie eine Basislösung verwenden, um die beste Lösung zu finden.
Aber was ist eine Basislösung und warum ist es für Ingenieure so wichtig, sie zu kennen? In diesem Artikel werde ich darüber sprechen, was grundlegende Lösungen sind, warum sie in der Technik wichtig sind und wie sie verwendet werden können, um in verschiedenen Situationen die besten Ergebnisse zu erzielen.
Also schnallen Sie sich an und machen Sie sich bereit, in die Welt der grundlegenden Lösungen einzutauchen, wo ich die Geheimnisse lüften und Ihnen zeigen werde, wie leistungsfähig diese Technik sein kann.
Grundlegende Lösungen in der linearen Programmierung
Formale Definition:
Eine Lösung für ein lineares Programmmodell, das aus m Gleichungen in n Variablen besteht, wird erhalten, indem nach m Variablen in Bezug auf die verbleibenden (nm) Variablen aufgelöst wird und die (nm) Variablen gleich Null gesetzt werden.
Eine grundlegende Lösung in der linearen Programmierung ist eine Möglichkeit, ein Problem der linearen Programmierung zu lösen, das bestimmte technische Anforderungen erfüllt.
Insbesondere ist ein Vektor x eine Basislösung für ein Polyeder, wenn die Vektoren {ai : xi = 0} linear unabhängig sind.
Das bedeutet, dass die Spalten von A, die Variablen xi haben, die nicht Null sind, linear unabhängig sind.
Eine Basislösung mit nichtnegativen Komponenten wird als zulässige Basislösung (BFS) (BFS) bezeichnet.
Ein BFS erfüllt alle Regeln, die ein Polyeder definieren.
Aus geometrischer Sicht ist jede BFS eine Ecke des Polyeders zulässiger Lösungen.
Um eine einfache Lösung zu finden, müssen Sie nm Variablen, die nicht einfach sind, auf Null setzen und die m einfachen Variablen lösen.
Es ist möglich, dass verschiedene Basen zu derselben Grundlösung führen, was bedeutet, dass es möglicherweise mehr als einen Weg gibt, dasselbe Problem zu lösen.
Das Simplex-Verfahren ist ein iterativer Prozess, der sich von einem BFS zum nächsten BFS bewegt, bis es das beste BFS findet.
Nachdem wir die Simplex-Methode verwendet haben, um ein BFS zu finden, können wir feststellen, ob die Lösung die beste ist, indem wir sehen, ob andere BFSs in der Nähe einen besseren Wert für die Zielfunktion liefern.
Wenn es kein solches BFS gibt, ist das aktuelle BFS das beste.
Lineares Programmiermodell
Ein lineares Programmiermodell umfasst drei Hauptkomponenten: Entscheidungsvariablen, eine Zielfunktion und Einschränkungen.
Sowohl die Zielfunktion als auch die Beschränkungen müssen lineare Funktionen sein, und die Entscheidungsvariablen müssen kontinuierlich sein.
Die Zielfunktion wird verwendet, um eine Zahl zu erhöhen oder zu verringern, die Gewinn, Kosten, Anzahl der hergestellten Produkte usw. Darstellt.
Beschränkungen sind Grenzen oder Beschränkungen der Gesamtmenge einer bestimmten Ressource, die benötigt wird, um die Aufgaben zu erledigen, die den Grad des Erfolgs in den Entscheidungsvariablen bestimmen.
Außerdem erfordern einige lineare Programme, dass alle Entscheidungsvariablen nichtnegativ sind.
In linearen Programmiermodellen können Sie auch ganzzahlige und binäre Variablen verwenden.
Binäre Variablen können nur einen Wert von 0 oder 1 haben, also können sie nur einen Wert von 0 oder 1 haben.
Die Simplex-Methode
Eine der am häufigsten verwendeten Methoden zur Lösung linearer Programmierprobleme ist die Simplex-Methode.
Basislösungen sind bei der Simplex-Methode wichtig, da sie den Eckpunkten des zulässigen Bereichs entsprechen, und die Simplex-Methode bewegt sich von einer Ecke zur anderen, bis eine optimale Lösung gefunden ist.
Die Simplex-Methode ist ein schneller Weg, um die beste Antwort auf ein Problem der linearen Programmierung zu finden, indem die Eigenschaften einfacher Lösungen verwendet werden.
Um mit der Simplex-Methode die beste BFS zu finden, müssen wir eine Basis B für die Nebenbedingungsmatrix A finden und das System Ax = b lösen, wobei alle Variablen außer der Basis auf Null gesetzt werden.
Die resultierenden Werte für die Basisvariablen bilden ein BFS.
Wenn es eine optimale Lösung gibt, dann gibt es eine optimale BFS.
Das Simplex-Verfahren bewegt sich von einem BFS zu einem benachbarten BFS, bis es ein optimales BFS erreicht, indem Pivot-Prozeduren verwendet werden.
Vergleich zwischen Basislösungen und praktikablen Lösungen
Der Unterschied zwischen einer Basislösung und einer zulässigen Lösung besteht darin, dass eine Basislösung keine Bedingungen erfüllen muss.
Insbesondere muss es Vektoren haben, die linear unabhängig sind und Werte ungleich Null für xi haben, und x muss kleiner als 0 sein.
Andererseits ist eine zulässige Lösung jeder Punkt, der in die Grenzen des Problems passt.
Aber nicht alle zulässigen Lösungen sind grundlegende zulässige Lösungen.
Zulässige Basislösungen (BFSs) sind nur diejenigen, die zu den Ecken des Polyeders der zulässigen Lösungen passen.
Zurück zu den Grundlagen: Erschließung der Leistungsfähigkeit grundlegender Lösungen im Engineering
Immer noch schwer zu verstehen? Lassen Sie mich die Sichtweise etwas ändern:
Haben Sie es satt, komplizierte Methoden und Algorithmen zu verwenden, um schwierige Probleme zu lösen? Wünschen Sie sich eine einfachere und direktere Möglichkeit, mit Ihren Problemen mit linearen Programmmodellen umzugehen?
Machen Sie sich keine Sorgen, denn die Antwort ist hier: Lösen Sie nach m Variablen in Bezug auf die verbleibenden (nm) Variablen auf und setzen Sie die (nm) Variablen auf Null.
Wer braucht Algorithmen, die ausgefallen klingen, wenn man zu den Grundlagen zurückkehren kann? Legen Sie also Ihre Taschenrechner weg und lernen Sie einfache Lösungen kennen.
Okay, das war nur ein Witz, der wie eine Fernsehwerbung aussehen sollte.
Kommen wir nun zurück zur Erklärung.
Grundlegende Lösung Lineare Programmierung
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: | Die Basislösung kann bei Ressourcenzuweisungsproblemen verwendet werden, bei denen das Ziel darin besteht, begrenzte Ressourcen auf konkurrierende Bedürfnisse aufzuteilen. Beispielsweise muss ein Unternehmen sein Budget möglicherweise auf verschiedene Abteilungen oder Projekte aufteilen. Durch die Verwendung grundlegender Lösungen können sie herausfinden, wie sie ihre Ressourcen am besten einsetzen, um das meiste Geld zu verdienen oder so wenig wie möglich auszugeben. |
| Planung für die Produktion: | In der Produktionsplanung kann die Basislösung verwendet werden, um den besten Produktmix zu ermitteln, um das meiste Geld zu verdienen. Mit der Basislösung können Unternehmen den besten Produktionsmix finden, der am meisten Geld bringt und am wenigsten kostet. |
| Planung: | Die Basislösung kann verwendet werden, um herauszufinden, wie Aufgaben oder Jobs so geplant werden, dass sie auf die effizienteste Weise erledigt werden können. Beispielsweise muss ein Unternehmen möglicherweise die Arbeitszeiten seiner Mitarbeiter planen, um sicherzustellen, dass sie genügend Arbeitskräfte haben, wenn das Geschäft ausgelastet ist. Durch die Verwendung einer einfachen Lösung können sie herausfinden, wie sie die Dinge am besten so planen, dass es so wenig Ausfallzeiten wie möglich gibt und so viel Arbeit wie möglich erledigt wird. |
| Management der Lieferkette: | Ziel des Supply Chain Managements ist es, sicherzustellen, dass Waren und Dienstleistungen möglichst reibungslos vom Lieferanten zum Kunden gelangen. Beispielsweise muss ein Unternehmen möglicherweise die besten Routen für den Warentransport ermitteln, damit die Kosten auf ein Minimum reduziert und die Waren pünktlich geliefert werden. Durch die Verwendung von Basislösungen können sie den besten Plan für das Management der Lieferkette finden, der die Kosten niedrig hält und die Kunden zufrieden stellt. |
| Portfolio-Optimierung: | Bei der Portfoliooptimierung, bei der es darum geht, die beste Mischung von Anlagen zu finden, um mit dem geringsten Risiko das meiste Geld zu verdienen, können einfache Lösungen verwendet werden. Beispielsweise muss eine Wertpapierfirma möglicherweise die beste Mischung aus Aktien, Anleihen und anderen Wertpapieren finden, um ihren Kunden zu helfen, ihre Anlageziele zu erreichen. Durch die Verwendung einer einfachen Lösung können sie den besten Weg finden, ihre Portfolios so zu mischen, dass sie die besten Renditen erzielen und gleichzeitig das geringste Risiko eingehen. |
Abschluss
Zusammenfassend lässt sich sagen, dass die Idee einer Basislösung im Bereich des Ingenieurwesens sehr wichtig ist und auf vielfältige Weise verwendet werden kann.
Indem wir wissen, was eine Basislösung ist und was sie in der linearen Programmierung bewirkt, können wir Lösungen verbessern, Kosten senken und effizienter gestalten.
Aber es ist wichtig, sich daran zu erinnern, dass die Basislösung keine Einheitslösung ist, auch wenn es sich um ein leistungsstarkes Tool handelt.
Um die besten Ergebnisse zu erzielen, muss jedes Problem sorgfältig betrachtet und durchdacht werden.
Als Ingenieure müssen wir immer wieder prüfen, wie grundlegende Lösungen und andere Optimierungstechniken uns helfen können, Fortschritte zu erzielen und auf neue Ideen zu kommen.
Lassen Sie uns also die Kraft einfacher Lösungen erkennen und die Grenzen des Möglichen erweitern, indem wir neue Techniken und Strategien anwenden.
Links und Referenzen
Bücher:
- Lineare Programmierung von Vasek Chvatal
- Modellierung und Lösung linearer Programmierung mit R von Jose M. Sallan
Teilen auf…
