Konvexe Optimierung - Lineare Programmierung

Methodik

Die lineare Programmierung, auch lineare Optimierung genannt, ist eine Technik, mit der mathematische Probleme gelöst werden, bei denen die Beziehungen linearer Natur sind. Die grundlegende Natur der linearen Programmierung besteht darin, eine zu maximieren oder zu minimierenobjective function mit vorbehaltlich einiger constraints. Die Zielfunktion ist eine lineare Funktion, die aus dem mathematischen Modell des Problems erhalten wird. Die Einschränkungen sind die Bedingungen, die dem Modell auferlegt werden und auch linear sind.

Finden Sie aus der gegebenen Frage die Zielfunktion.
Finde die Einschränkungen.
Zeichnen Sie die Einschränkungen in ein Diagramm.
Finden Sie den realisierbaren Bereich, der durch den Schnittpunkt aller Einschränkungen gebildet wird.
Finden Sie die Eckpunkte der möglichen Region.
Finden Sie den Wert der Zielfunktion an diesen Eckpunkten.
Der Eckpunkt, der die Zielfunktion (entsprechend der Frage) entweder maximiert oder minimiert, ist die Antwort.

Beispiele

Step 1 - Maximieren Sie $ 5x + 3y $ vorbehaltlich

$ x + y \ leq 2 $,

$ 3x + y \ leq 3 $,

$ x \ geq 0 \: und \: y \ geq 0 $

Solution - -

Der erste Schritt besteht darin, den möglichen Bereich in einem Diagramm zu finden.

Aus dem Diagramm geht klar hervor, dass die Eckpunkte des realisierbaren Bereichs sind

$ \ left (0, 0 \ right) \ left (0, 2 \ right) \ left (1, 0 \ right) \ left (\ frac {1} {2}, \ frac {3} {2} \ right ) $

Sei $ f \ left (x, y \ right) = 5x + 3y $

Wenn wir diese Werte in die Zielfunktion einfügen, erhalten wir -

$ f \ left (0, 0 \ right) $ = 0

$ f \ left (0, 2 \ right) $ = 6

$ f \ left (1, 0 \ right) $ = 5

$ f \ left (\ frac {1} {2}, \ frac {3} {2} \ right) $ = 7

Daher maximiert die Funktion bei $ \ left (\ frac {1} {2}, \ frac {3} {2} \ right) $

Step 2- Eine Uhrenfirma stellt eine digitale und eine mechanische Uhr her. Langzeitprojektionen deuten auf einen erwarteten Bedarf von mindestens 100 digitalen und 80 mechanischen Uhren pro Tag hin. Aufgrund der begrenzten Produktionskapazität können täglich nicht mehr als 200 digitale und 170 mechanische Uhren hergestellt werden. Um einen Versandvertrag zu erfüllen, werden täglich mindestens 200 Uhren verschickt.

Wenn jede verkaufte Digitaluhr zu einem Verlust von 2 $ führt, aber jede mechanische Uhr einen Gewinn von 5 $ erzielt, wie viele von jedem Typ sollten täglich hergestellt werden, um den Nettogewinn zu maximieren?

Solution - -

$ X $ sei die Anzahl der produzierten Digitaluhren

$ y $ ist die Anzahl der produzierten mechanischen Uhren

Entsprechend der Frage sollen täglich mindestens 100 Digitaluhren hergestellt werden und es können maximal 200 Digitaluhren hergestellt werden.

$ \ Rightarrow 100 \ leq \: x \ leq 200 $

Ebenso sollen täglich mindestens 80 mechanische Uhren hergestellt werden und maximal 170 mechanische Uhren können hergestellt werden.

$ \ Rightarrow 80 \ leq \: y \ leq 170 $

Da sollen täglich mindestens 200 Uhren produziert werden.

$ \ Rightarrow x + y \ leq 200 $

Da jede verkaufte Digitaluhr zu einem Verlust von 2 $ führt, aber jede mechanische Uhr einen Gewinn von 5 $ erzielt,

Der Gesamtgewinn kann berechnet werden als

$ Profit = -2x + 5y $

Und wir müssen den Gewinn maximieren. Daher kann die Frage wie folgt formuliert werden:

Maximieren Sie $ -2x + 5y $ vorbehaltlich

$ 100 \: \ leq x \: \ leq 200 $

$ 80 \: \ leq y \: \ leq 170 $

$ x + y \: \ leq 200 $

Wenn wir die obigen Gleichungen in einem Diagramm darstellen, erhalten wir:

Die Eckpunkte der realisierbaren Region sind

$ \ left (100, 170 \ right) \ left (200, 170 \ right) \ left (200, 180 \ right) \ left (120, 80 \ right) und \ left (100, 100 \ right) $

Der Maximalwert der Zielfunktion wird bei $ \ left (100, 170 \ right) $ erhalten. Um den Nettogewinn zu maximieren, sollten 100 Einheiten Digitaluhren und 170 Einheiten mechanische Uhren hergestellt werden.