Linear optimization - Exam

Aufgabe 2)

Ein Unternehmen produziert zwei Produkte, Produkt A und Produkt B. Jede Einheit von Produkt A bringt einen Gewinn von 5€ und jede Einheit von Produkt B bringt einen Gewinn von 8€. Die Herstellung einer Einheit von Produkt A erfordert 2 Stunden Arbeitszeit und 1 Stunde Maschinennutzung, während die Herstellung einer Einheit von Produkt B 1 Stunde Arbeitszeit und 3 Stunden Maschinennutzung erfordert. Das Unternehmen hat insgesamt 100 Arbeitsstunden und 120 Maschinennutzungsstunden zur Verfügung. Entwickle ein lineares Optimierungsmodell, um den Gewinn zu maximieren.

b)

Berechne mit Hilfe der graphischen Methode die optimalen Produktionsmengen für Produkt A und Produkt B, die den Gesamtgewinn maximieren. Zeichne dabei alle relevanten Restriktionen einschließlich der Zielfunktion in ein Koordinatensystem und bestimme den Schnittpunkt der Zielfunktion mit den Restriktionen, der den optimalen Gewinn liefert.

Lösung:

Um die optimalen Produktionsmengen für Produkt A und Produkt B mit Hilfe der graphischen Methode zu berechnen, brauchen wir die linearen Ungleichungen und die Zielfunktion in ein Koordinatensystem einzuzeichnen. Es werden die Schnittpunkte der Restriktionen berechnet und die optimale Lösung wird bestimmt.

1. Einschränkungen und Zielfunktion:

• Einschränkung 1 (Arbeitszeit): 2x + y ≤ 100
• Einschränkung 2 (Maschinennutzung): x + 3y ≤ 120
• Nicht-Negativitätsbedingungen: x ≥ 0 und y ≥ 0

2. Einzeichnen der Restriktionen in das Koordinatensystem:

• Um 2x + y ≤ 100 zu zeichnen, berechnen wir die Schnittpunkte mit den Achsen:
• Für x = 0: y = 100
• Für y = 0: x = 50
• Um x + 3y ≤ 120 zu zeichnen, berechnen wir ebenfalls die Schnittpunkte mit den Achsen:
• Für x = 0: y = 40
• Für y = 0: x = 120
• Der Bereich unter diesen Geraden sowie im Bereich der positiven Achsen (x ≥ 0 und y ≥ 0) repräsentiert den zulässigen Bereich.

3. Finden der Eckpunkte des zulässigen Bereichs:

• Der zulässige Bereich wird durch die Schnittpunkte dieser Linien definiert. Wir identifizieren die relevanten Eckpunkte:
• Schnittpunkt von 2x + y = 100 und x + 3y = 120:

 Solve by substitution or linear equation methods: 2x + y = 100 (1) x + 3y = 120 (2) Multiply (1) by 3: 6x + 3y = 300 (3) Subtract (2) from (3): 5x = 180 x = 36 Substituting x = 36 into (1): 2(36) + y = 100 y = 28 

Der Schnittpunkt ist (36, 28).

• Weitere Schnittpunkte sind die Achsenabschnitte (50, 0), (0, 40) und (0, 0).

4. Berechnung des Gewinns an den Eckpunkten:

• Zielfunktion ist Z = 5x + 8y.
• Eckpunkt (0, 0): Z = 5(0) + 8(0) = 0
• Eckpunkt (50, 0): Z = 5(50) + 8(0) = 250
• Eckpunkt (0, 40): Z = 5(0) + 8(40) = 320
• Eckpunkt (36, 28): Z = 5(36) + 8(28) = 180 + 224 = 404

Fazit:

Der optimale Produktionsplan für das Unternehmen lautet, 36 Einheiten von Produkt A und 28 Einheiten von Produkt B herzustellen. Dies maximiert den Gewinn auf 404€.

Eine graphische Darstellung in einem Koordinatensystem hilft dabei, diese Punkte visuell zu verifizieren.

Aufgabe 3)

Angenommen, ein Unternehmen produziert zwei Produkte, Produkt A und Produkt B. Produkt A erfordert 3 Einheiten einer Ressource pro Einheit Produktion, Produkt B erfordert 4 Einheiten derselben Ressource pro Einheit Produktion. Die verfügbare Menge dieser Ressource beträgt 240 Einheiten. Darüber hinaus benötigt das Unternehmen mindestens eine Produktion von 30 Einheiten von Produkt A und 20 Einheiten von Produkt B, um die Nachfrage zu decken. Das Unternehmen möchte den Gewinn maximieren, wobei der Gewinn für Produkt A 5 Euro pro Einheit beträgt und für Produkt B 7 Euro pro Einheit.

a)

Formuliere das oben beschriebene Problem als lineares Programm. Bestimme die Zielfunktion und die Restriktionen, die die Produktion der Produkte A und B beschreiben.

Lösung:

Lineares Programmierungsproblem:Um das Problem als lineares Programm zu formulieren, müssen wir die Zielfunktion und die Restriktionen bestimmen.

• Zielfunktion (Gewinnmaximierung):Das Unternehmen möchte den Gewinn maximieren. Der Gewinn pro Einheit von Produkt A beträgt 5 Euro und der Gewinn pro Einheit von Produkt B beträgt 7 Euro. Daher lautet die Zielfunktion:\(\text{Maximiere} \; Z = 5A + 7B\)
• Restriktionen:
  1. Verfügbare Ressource:Produkt A benötigt 3 Einheiten der Ressource pro Einheit Produktion und Produkt B benötigt 4 Einheiten derselben Ressource pro Einheit Produktion. Insgesamt sind 240 Einheiten der Ressource verfügbar.\(3A + 4B \leq 240\)
  2. Mindestproduktion:Das Unternehmen muss mindestens 30 Einheiten von Produkt A und 20 Einheiten von Produkt B produzieren, um die Nachfrage zu decken.\(A \geq 30\)\(B \geq 20\)
  3. Nicht-Negativitätsbedingungen:Die Anzahl der produzierten Einheiten kann nicht negativ sein.\(A \geq 0\)\(B \geq 0\)

• \(\text{Maximiere} \; Z = 5A + 7B\)
• \(\text{unter den folgenden Bedingungen:}\)
  • \(3A + 4B \leq 240\)
  • \(A \geq 30\)
  • \(B \geq 20\)
  • \(A \geq 0\)
  • \(B \geq 0\)

b)

Stelle das lineare Programm in Matrix-Notation dar. Fasse die Ungleichungen sowie die Zielfunktion in Matrix-Form zusammen.

Lösung:

Lineares Programm in Matrix-Notation:Um das lineare Programm in Matrix-Notation darzustellen, definieren wir die notwendigen Matrizen und Vektoren.

• Zielfunktion:Die Zielfunktion soll den Gewinn maximieren und lautet:\(\text{Maximiere} \, Z = 5A + 7B\)In Matrix-Form schreiben wir dies als:\[ \text{Maximiere} \, Z = \mathbf{c}^T \mathbf{x} = \begin{bmatrix} 5 & 7 \end{bmatrix} \begin{bmatrix} A \ B \end{bmatrix} \]
• Restriktionen:Die Restriktionen können ebenfalls in Matrix-Form dargestellt werden. Dazu zählen:\[ 3A + 4B \leq 240 \]\[ A \geq 30 \]\[ B \geq 20 \]Um dies zu vereinfachen, können wir die Ungleichungen umformen, um sie in einer einzigen Matrix darzustellen:\[ \begin{bmatrix} 3 & 4 \ -1 & 0 \ 0 & -1 \end{bmatrix} \begin{bmatrix} A \ B \end{bmatrix} \leq \begin{bmatrix} 240 \ -30 \ -20 \end{bmatrix} \]
• Nicht-Negativitätsbedingungen:Um sicherzustellen, dass die Produktionsmengen nicht negativ sind, fügen wir die Nicht-Negativitätsbedingungen hinzu:\[ A \geq 0 \]\[ B \geq 0 \]In Matrix-Form wird dies dargestellt als:\[ \begin{bmatrix} 1 & 0 \ 0 & 1 \end{bmatrix} \begin{bmatrix} A \ B \end{bmatrix} \geq \begin{bmatrix} 0 \ 0 \end{bmatrix} \]

• Zielfunktion:\[ \text{Maximiere} \, Z = \mathbf{c}^T \mathbf{x} = \begin{bmatrix} 5 & 7 \end{bmatrix} \begin{bmatrix} A \ B \end{bmatrix} \]
• unter den Bedingungen:\[ \mathbf{A} \mathbf{x} \leq \mathbf{b} \]\[ \begin{bmatrix} 3 & 4 \ -1 & 0 \ 0 & -1 \end{bmatrix} \begin{bmatrix} A \ B \end{bmatrix} \leq \begin{bmatrix} 240 \ -30 \ -20 \end{bmatrix} \]
• und\[ \mathbf{I} \mathbf{x} \geq \mathbf{0} \]\[ \begin{bmatrix} 1 & 0 \ 0 & 1 \end{bmatrix} \begin{bmatrix} A \ B \end{bmatrix} \geq \begin{bmatrix} 0 \ 0 \end{bmatrix} \]

c)

Bestimme die Eckpunkte der zulässigen Menge des linearen Programms. Berechne den maximalen Gewinn und gebe die Werte von Produkt A und Produkt B an, die den maximalen Gewinn erzielen.

Lösung:

Berechnung der Eckpunkte der zulässigen Menge:Um die Eckpunkte der zulässigen Menge zu bestimmen, lösen wir das System der Ungleichungen:

• \(3A + 4B \leq 240\)
• \(A \geq 30\)
• \(B \geq 20\)

• \(A \geq 0\)
• \(B \geq 0\)

1. Schnittpunkt von \(3A + 4B = 240\) und \(A = 30\):Setze \(A = 30\) in die Gleichung \(3A + 4B = 240\) ein:\[3(30) + 4B = 240\]\[90 + 4B = 240\]\[4B = 150\]\[B = 37.5\]Punkt 1: (30, 37.5)
2. Schnittpunkt von \(3A + 4B = 240\) und \(B = 20\):Setze \(B = 20\) in die Gleichung \(3A + 4B = 240\) ein:\[3A + 4(20) = 240\]\[3A + 80 = 240\]\[3A = 160\]\[A = 53.33\]Punkt 2: (53.33, 20)
3. Andere Punkte durch Schnitte von Restriktionen mit Achsen:
   • Punkt 3: (30, 20) (Minimum Anforderungen an Produktion)
   • Punkt 4: (0, 60) (Schnittpunkt von \(3A + 4B = 240\) mit der B-Achse)
   • Punkt 5: (80, 0) (Schnittpunkt von \(3A + 4B = 240\) mit der A-Achse)

• Punkt 1 (30, 37.5):\(Z = 5A + 7B = 5(30) + 7(37.5) = 150 + 262.5 = 412.5\) Euro
• Punkt 2 (53.33, 20):\(Z = 5A + 7B = 5(53.33) + 7(20) = 266.65 + 140 = 406.65\) Euro
• Punkt 3 (30, 20):\(Z = 5A + 7B = 5(30) + 7(20) = 150 + 140 = 290\) Euro
• Punkt 4 (0, 60):\(Z = 5A + 7B = 5(0) + 7(60) = 0 + 420 = 420\) EuroAber nicht zulässig, da \(A < 30\).
• Punkt 5 (80, 0):\(Z = 5A + 7B = 5(80) + 7(0) = 400 + 0 = 400\) EuroAber nicht zulässig, da \(B < 20\).

• Produkt A: 30 Einheiten
• Produkt B: 37.5 Einheiten

Aufgabe 4)

Ein kleines Unternehmen produziert zwei Produkte, A und B. Die Produktion der beiden Produkte unterliegt den folgenden Einschränkungen hinsichtlich der verfügbaren Ressourcen: Arbeitsstunden, Materialien und Maschinenzeit. Produkt A benötigt 2 Stunden Arbeit, 3 Einheiten Material und 1 Stunde Maschinenzeit pro Einheit. Produkt B benötigt 4 Stunden Arbeit, 1 Einheit Material und 2 Stunden Maschinenzeit pro Einheit. Das Unternehmen hat insgesamt 100 Arbeitsstunden, 90 Einheiten Material und 80 Stunden Maschinenzeit zur Verfügung. Zudem liegt der Gewinn pro Einheit für Produkt A bei 40€ und für Produkt B bei 50€. Formuliere ein lineares Optimierungsproblem, um den Gewinn zu maximieren und löse das Problem mit einem Softwaretool Deiner Wahl (MATLAB, LINDO oder Excel Solver).

b)

Nutze ein Softwaretool Deiner Wahl, um das lineare Optimierungsproblem zu lösen. Dokumentiere den Synthax oder die Schritte zur Lösung für das gewählte Tool (MATLAB, LINDO oder Excel Solver). Beschreibe detailliert, wie Du die Lösung implementiert hast und präsentiere das optimale Ergebnis (Anzahlen von Produkt A und B sowie den maximalen Gewinn).

Lösung:

Hier beschreiben wir die Schritte zur Lösung des linearen Optimierungsproblems, indem wir Excel Solver verwenden:

• Excel Solver Einrichten:

1. Öffne eine neue Excel-Tabelle.
2. Gib die Entscheidungsvariablen, Zielfunktion und Randbedingungen in die Tabelle ein.

• In Zelle A1 schreibe 'Produkt A'
• In Zelle B1 schreibe 'Produkt B'
• In Zelle A2 schreibe 'x'
• In Zelle B2 schreibe 'y'
• In Zelle A3 setze den Wert '0' (Initiale Anzahl Produkt A)
• In Zelle B3 setze den Wert '0' (Initiale Anzahl Produkt B)

• In Zelle C1 schreibe 'Gewinn'
• In Zelle C2 schreibe diese Formel:

  =40*A3+50*B3

• Arbeitsstunden: In Zelle D1 schreibe 'Arbeitsstunden', und in Zelle D2 schreibe diese Formel:

  =2*A3 + 4*B3

• In Zelle E1 setze '100' (Gesamte verfügbare Arbeitsstunden)
• Materialien: In Zelle F1 schreibe 'Materialien', und in Zelle F2 schreibe diese Formel:

  =3*A3 + B3

• In Zelle G1 setze '90' (Gesamte verfügbare Materialien)
• Maschinenzeit: In Zelle H1 schreibe 'Maschinenzeit', und in Zelle H2 schreibe diese Formel:

  =A3 + 2*B3

• In Zelle I1 setze '80' (Gesamte verfügbare Maschinenzeit)

• Gehe zu Daten > Solver.

• Setze das Ziel: Wähle Set Objective als Zelle C2.
• Set Mine dann auf Max (um den Gewinn zu maximieren).
• Wähle By Changing Variable Cells und setze sie auf A3:B3.
• Füge unter 'Subject to the Constraints' die Randbedingungen hinzu:
• D2 ≤ E1
• F2 ≤ G1
• H2 ≤ I1
• A3, B3 ≥ 0

Optimales Ergebnis:

• Die optimale Anzahl von Produkt A (x) und Produkt B (y) wird in den Zellen A3 und B3 angezeigt.
• Der maximale Gewinn wird in der Zelle C2 angezeigt.