ingenieurkurse
online lernen

Besser lernen mit Online-Kursen

NEU! Jetzt online lernen:
Operations Research 1
Den Kurs kaufen für:
einmalig 39,00 €
Zur Kasse
Lineare Programmierung > Obere und untere Schranken bei Variablen > Obere Schranken:

Beispiel: Vielzahl an beschränkten Variablen

WebinarTerminankündigung aus unserem Online-Kurs Technische Mechanik 3: Dynamik:
 Am 06.12.2016 (ab 16:00 Uhr) findet unser nächstes Webinar statt.
Gratis-Webinar (Dynamik) Gradlinige Bewegung eines Massenpunktes
- Dieses 60-minütige Gratis-Webinar behandelt die geradlinige Bewegung eines Massenpunktes.
[weitere Informationen] [Terminübersicht]

In diesem Abschnitt soll jetzt ein lineares Optimierungsproblem gegeben sein, bei welchem eine Vielzahl an Variablen vorliegen, die obere Schranken aufweisen. Hier ist es ratsam nach dem Verfahren der oberen Schranken vorzugehen (siehe Abschnitt: Obere Schranken).

Gegeben sei das folgende Optimierungsproblem:

$f(x_1, x_2, x_3, x_4) = 4x_1 + 6x_2 + 3x_3 + x_4$   $\rightarrow$  max!

u.d.N.

$x_1 + 2x_2 + 4x_3 + x_4 \le 80$

$2x_1 + x_2 + x_3           \le 60$

$x_1 \le 20$

$x_2 \le 30$

$x_3 \le 10$

$x_4 \le 5$

$x_1, x_2, x_3, x_4 \ge 0$

Das obige lineare Optimierungsproblem ist in Standardform gegeben. Die Werte der rechten Seite sind alle positiv (kanonische Form). Es kann demnach das aus dem Abschnitt Obere Schranken gezeigte Verfahren angewandt werden, um die optimale Lösung zu bestimmen. Es ist auch möglich das primale Simplexverfahren durchzuführen. Die Anzahl der Nebenbedingungen beträgt dann aber 6 und die Bestimmung der optimalen Lösung ist sehr rechenaufwendig. Es wird im weiteren das Verfahren der oberen Schranken angewandt.

Zunächst muss das Optimierungsprroblem in Normalform überführt werden. Dazu werden die Schlupfvariablen eingefügt. Die oberen Schranken bleiben hierbei bestehen:

$f(x_1, x_2, x_3, x_4) = 4x_1 + 6x_2 + 3x_3 + x_4$   $\rightarrow$  max!

u.d.N.

$x_1 + 2x_2 + 4x_3 + x_4 + x_5           = 80$

$2x_1 + x_2 + x_3                    + x_6  = 60$

$x_1 \le 20$

$x_2 \le 30$

$x_3 \le 10$

$x_4 \le 5$

$x_1, x_2, x_3, x_4, x_5, x_6 \ge 0$

Eintragen in das Simplextableau ergibt:

Obere Schranken der Variablen im Simplex

Mittels der Iterationschritte für obere Schranken besitzt das Tableau nur 2 Nebenbedingungen. Die Berechnung wird wie folgt durchgeführt:

1. Schritt. Wahl der Pivotspalte. Kleinster negativer Wert in der Zielfunktionszeile. Hier $-6$. Setzen von $x_t = x_2$ mit der Beschränkung $\kappa_2 = 30$.

2. Schritt: Wahl der Pivotzeile. Es wird $q_1$ und $q_2$ bestimmt.

$q_1 = min \{\frac{80}{2}, \frac{60}{1} \} = 40$

$q_2 = \infty$ Kein negativer Koeffizient in der Pivotspalte vorhanden.

Bestimmung von $q = min \{q_1, q_2, \kappa_2 \} = 30$

Es gilt der Fall:

  • $q = \kappa_2$

Es wird nun die gesamte Spalte ersetzt durch $x_2 = \kappa_2 - \overline{x}_2 = 30 - \overline{x_2}$. Es wird das aktuelle lineare Optimierungsproblem (siehe Tableau) herangezogen. Die Spalte betrifft alle Nebenbedingungen und die Zielfunktion, weshalb das komplette Optimierungsmodell durch $x_2 = 30 - \overline{x_2}$ ersetzt werden muss. 

$f(x_1, x_2, x_3, x_4) = 4x_1 + 6(30 - \overline{x_2}) + 3x_3 + x_4$   $\rightarrow$  max!

u.d.N.

$x_1 + 2(30 - \overline{x_2}) + 4x_3 + x_4 + x_5           = 80$

$2x_1 + 30 - \overline{x_2} + x_3                    + x_6  = 60$

$x_1 \le 20$

$30 - \overline{x_2} \le 30$

$x_3 \le 10$

$x_4 \le 5$

$x_1, x_2, x_3, x_4, x_5, x_6 \ge 0$

Auflösen der Klammern und bei den Nebenbedingungen die Werte ohne Variablen auf die rechte Seite bringen:

$f(x_1, x_2, x_3, x_4) = 4x_1 - 6 \overline{x_2}) + 3x_3 + x_4 + 180$   $\rightarrow$  max!

u.d.N.

$x_1 - 2\overline{x_2}) + 4x_3 + x_4 + x_5           = 20$

$2x_1 - \overline{x_2} + x_3                     + x_6  = 30$

$x_1 \le 20$

$\overline{x_2} = 0$

$x_3 \le 10$

$x_4 \le 5$

$x_1, x_2, x_3, x_4, x_5, x_6 \ge 0$

Eintragen in das Tableau:

Obere Schranken der Variablen im Simplex

Der Zielfunktionswert von $180$ resultiert, weil $x_1 = \overline{x}_2 = x_3 = x_4 = 0$ (Nichtbasisvariablen) unter Berücksichtigung von $x_2 = 30 - \overline{x}_2 = 30 - 0 = 30$. Einsetzen in die Ausgangszielfunktion ergibt:

$f(x_1, x_2, x_3, x_4) = 4 \cdot 0 + 6 \cdot 30 + 3 \cdot 0 + 0 = 180$ 

Es wird nun wieder von vorne begonnen.

1. Schritt: Wahl der Pivotspalte. Der kleinste negative Wert ist $-4$. $x_t = x_1$ mit $\kappa_1 = 20$

2. Schritt: Wahl der Pivotzeile. Bestimmung von $q_1$ und $q_2$.

$q_1 = min \{\frac{20}{1}, \frac{30}{2} \} = 15$

$q_2 = \infty$  Kein negativer Koeffizient in der Pivotspalte.

Bestimmung von $q = min \{15, \infty, 20 \} = 15$

Es gilt der Fall:

  • $q = q_1$:

Es wird nun die Basisvariable betrachtet, für die $q_1 = 15$ gilt. Dies ist $x_6 = \frac{30}{2}$. Diese Basisvariable verlässt die Basis und wird zur Nichtbasisvariablen. Der Tausch erfolgt mit $x_t = x_1$. Es wird zudem ein Simplexschritt durchgeführt:

Obere Schranken der Variablen im Simplex

Der Zielfunktionswert ist berechnet worden durch: $x_1 = 15$, $\overline{x}_2 = 0$ mit $x_2 = 30 - \overline{x_2}$ also $x_2 = 30$ und $x_3 = x_4 = 0$:

$f(x_1, x_2, x_3, x_4) = 4 \cdot 15 + 6 \cdot 30 + 3 \cdot 0 + 0 = 240$ 

1. Schritt: Wahl der Pivotspalte. Es existieren zwei kleinste Werte. Es kann einer beliebig gewählt werden. Es wird der Wert $-1$ gewählt für welchen gilt $x_t = x_4$ mit $\kappa_4 = 5$.

2. Schritt: Wahl der Pivotzeile. Es werden $q_1$ und $q_2$ berechnet.

$q_1 = min \{\frac{5}{1} \} = 5$

$q_2 = \infty$  Es existieren keine negative Koeffizienten in der Pivotspalte.

Es wird $q$ bestimmt:

$q = min \{5, \infty, 5 \}$. 

Es gelten nun zwei Fälle. Gewählt wird der Fall 2.

  • $q = \kappa_4$

Es wird nun für die Basisvariable $x_t = x_4$ die gesamte Spalte ausgetauscht durch $x_4 = 5 - \overline{x}_4$. Dabei muss das aktuelle Optimierungsmodell herangezogen werden (siehe Tableau):

ZF: $-2x_6 - 4 \overline{x}_2 + x_3 + x_4$     (mit umkehrten Vorzeichen berücksichtigen)

NB: $-\frac{1}{2} x_6 - \frac{3}{2} \overline{x}_2 + \frac{7}{2} x_3 +  x_4   = 5$

     $  \frac{1}{2} x_6 - \frac{1}{2} \overline{x}_2 + \frac{1}{2} x_3             = 15$

$x_1 \le 20$

$\overline{x_2} = 0$

$x_3 \le 10$

$x_4 \le 5$

$x_1, x_2, x_3, x_4, x_5, x_6 \ge 0$

Einsetzen von $x_4 = 5 - \overline{x}_2$:

ZF: $-2x_6 - 4 \overline{x}_2 + x_3 + 5 + \overline{x}_4$   

NB: $-\frac{1}{2} x_6 - \frac{3}{2} \overline{x}_2 + \frac{7}{2} x_3 +  5 - \overline{x}_4   = 5$

     $  \frac{1}{2} x_6 - \frac{1}{2} \overline{x}_2 + \frac{1}{2} x_3             = 15$

$x_1 \le 20$

$\overline{x_2} = 0$

$x_3 \le 10$

$5 - \overline{x}_4 \le 5$

$x_1, x_2, x_3, x_4, x_5, x_6 \ge 0$

Zusammenfassen:

ZF: $-2x_6 - 4 \overline{x}_2 + x_3 - \overline{x}_4 + 5$   

NB: $-\frac{1}{2} x_6 - \frac{3}{2} \overline{x}_2 + \frac{7}{2} x_3 - \overline{x}_4   = 0$

     $  \frac{1}{2} x_6 - \frac{1}{2} \overline{x}_2 + \frac{1}{2} x_3             = 15$

$x_1 \le 20$

$\overline{x_2} = 0$

$x_3 \le 10$

$\overline{x}_4 \le 0$

$x_1, x_2, x_3, x_4, x_5, x_6 \ge 0$

Einfügen in das Tableau:

Obere Schranken der Variablen im Simplex

Es ist deutlich zu erkennen, dass sich nur die Spalte verändert hat, in der sich vorher $x_4$ und jetzt $\overline{x}_4$ befindet. Der neue Zielfunktionswert ergibt sich durch: $x_1 = 15$, $x_6 = x_3 = 0$ und $\overline{x}_2 = \overline{x}_4 = 0$ wobei $x_2 = 30 - \overline{x}_2 = 30 - 0 = 30$ und $x_4 = 5 - \overline{x}_4 = 5 - 0 = 5$. Einsetzen in die Ausgangszielfunktion ergibt:

$f(x_1, x_2, x_3, x_4) = 4 \cdot 15 + 6 \cdot 30 + 3 \cdot 0 + 5 = 245$ 

1. Schritt: Wahl der Pivotspalte. Es existiert noch ein negativer Wert in der Zielfunktionszeile: $-1$ mit $x_t = x_3$ und $\kappa_3 = 10$.

2. Schritt: Wahl der Pivotspalte. Bestimmung von $q_1$ und $q_2$.

$q_1 = min \{\frac{0}{\frac{7}{2}}; \frac{15}{\frac{1}{2}} \} = 0$

$q_2 = \infty$

Bestimmung von $q$:

$q = min \{0, \infty, 10 \} = 0$

Es gilt der Fall:

  • $q = q_1$:

Es wird nun die Basisvariable für die $q_1 = \frac{0}{\frac{7}{2}}$ zur Basisvariablen. Hierbei handelt es sich um $x_5$. Der Tausch findet mit der Nichtbasisvariablen der Pivotspalte statt, also mit $x_3$. Es wird zudem ein Simplexschritt durchgeführt:

Obere Schranken der Variablen im Simplex

Es liegt die Optimallösung vor, da keine negative Werte mehr in der Zielfunktionszeile gegeben sind. Die Optimallösung beträgt:

$x_1 = 15$, $\overline{x}_2 = 0$, $x_3 = 0$ und $\overline{x}_4 = 0$. Dabei gilt $x_2 = 30 - \overline{x}_2 = 30 - 0 = 30$ und $x_4 = 5 - \overline{x}_4 = 5 - 0 = 5$. Einsetzen in die Ausgangszielfunktion ergibt:

Methode

$f(x_1, x_2, x_3, x_4) = 4 \cdot 15 + 6 \cdot 30 + 3 \cdot 0 + 5 = 245$ 


Das Problem kann auch mittels primalen Simplex gelöst werden. Dann aber werden die oberen Schranken mit als Nebenbedingungen berücksichtigt. Es ergeben sich dann statt 2 ingesamt 6 Schlupfvariablen:

Obere Schranken der Variablen im Simplex

Es kann hier der primale Simplexalgorithmus angewandt werden. Am Ende resultiert das selbe Ergebnis. Es ist aber auch deutlich zu erkennen, dass durch die Anzahl der Nebenbedingungen ein hoher Rechenaufwand gegeben ist. Nach 4 Iterationen ist die optimale Lösung gegeben.

Vorstellung des Online-Kurses Operations ResearchOperations Research
Dieser Inhalt ist Bestandteil des Online-Kurses

Operations Research 1

Ingenieurkurse (ingenieurkurse.de)
Diese Themen werden im Kurs behandelt:

[Bitte auf Kapitelüberschriften klicken, um Unterthemen anzuzeigen]

  • Kurs: Operations Research 1 - Lineare Optimierung, Graphentheorie und Netzplantechnik
    • Einleitung zu Kurs: Operations Research 1 - Lineare Optimierung, Graphentheorie und Netzplantechnik
  • Lineare Programmierung
    • Einleitung zu Lineare Programmierung
    • Definition: Lineares Programm
    • Standardform: Maximierungsproblem
      • Einleitung zu Standardform: Maximierungsproblem
      • Grafische Lösung eines Maximierungsproblems
        • Einleitung zu Grafische Lösung eines Maximierungsproblems
        • Beispiel: Grafische Lösung eines Maximierungsproblems
      • Umformung in die Standardform (Maximierungsproblem)
      • Umformung in die Normalform (Maximierungsproblem)
      • Simlpex-Algorithmus: Einführung
        • Einleitung zu Simlpex-Algorithmus: Einführung
        • Primales Simlpexverfahren
          • Einleitung zu Primales Simlpexverfahren
          • Primales Simplexverfahren: Anfangstableau aufstellen
          • Primales Simplexverfahren: Pivotspalte/-zeile/-element
          • Primales Simplexverfahren: 1. Simplexschritt
          • Primales Simplexverfahren: Weitere Simplexschritte (optimale Lösung)
          • Beispiel: Maximierungsproblem / grafische Lösung
          • Beispiel: Maximierungsproblem / Primales Simplexverfahren
        • Duales Simplexverfahren
          • Einleitung zu Duales Simplexverfahren
          • Duales Simplexverfahren: Pivotzeile/-spalte/-element
          • Duales Simplexverfahren: Simplexschritte
        • Die Big-M-Methode des primalen Simplexverfahrens
          • Einleitung zu Die Big-M-Methode des primalen Simplexverfahrens
          • Die Big-M-Methode: Einfügen von künstlichen Variablen
          • Die Big-M-Methode: Künstliche Variablen als Basisvariablen
          • Big-M-Methode: Simplexschritt durchführen
          • Big-M-Methode: Weiterer Simplexschritt (zulässige Lösung)
          • Big-M-Methode: Weitere Simplexschritte (optimale Lösung)
      • Kanonische Form, Standardform, Normalform
      • Zusammenfassung: Maximierungsproblem
    • Minimierungsproblem
      • Einleitung zu Minimierungsproblem
      • Dualität - Primalproblem als Maximierungsproblem
      • Dualität - Primalproblem als Minimierungsproblem
      • Dualität - Dualproblem in Primalproblem
      • Beispiel: Primalproblem als Minimierungsproblem
      • Minimierungsproblem- Big-M/dualer Simplex
      • Zusammenfassung: Minimierungsproblem
    • Sonderfälle bei Optimierungsmodellen
      • Einleitung zu Sonderfälle bei Optimierungsmodellen
      • Beispiel: Minimierungsproblem ohne optimal Lösung
    • Sensitivitätsanalyse
      • Einleitung zu Sensitivitätsanalyse
      • Änderung der Zielfunktionskoeffizienten
        • Einleitung zu Änderung der Zielfunktionskoeffizienten
        • Beispiel: Sensitivitätsanalyse Zielfunktionskoeffizienten
      • Änderung der Restriktionen
    • Obere und untere Schranken bei Variablen
      • Untere Schranken
      • Obere Schranken
        • Einleitung zu Obere Schranken
        • Beispiel: Primaler Simplexalgorithmus
        • Beispiel: Vielzahl an beschränkten Variablen
    • Revidierter Simplex-Algorithmus
      • Einleitung zu Revidierter Simplex-Algorithmus
      • Beispiel: Revidierter Simplex-Algorithmus
  • Transport- und Zuordnungsprobleme
    • Das klassische Transportproblem
      • Einleitung zu Das klassische Transportproblem
      • Ausgleichsprüfung
      • Reduktion der Kostenmatrix
      • Eröffnungsverfahren
        • Einleitung zu Eröffnungsverfahren
        • Nord-Westecken-Verfahren
        • Rangfolgeverfahren
          • Einleitung zu Rangfolgeverfahren
          • Spaltenfolgeverfahren
          • Zeilenfolgeverfahren
          • Matrixminimumverfahren
        • Vogelsches-Approximations-Verfahren
      • Optimierungsverfahren
        • Einleitung zu Optimierungsverfahren
        • Stepping-Stone-Methode
        • MODI-Methode
    • Lineare Zuordnungsprobleme
      • Definition: Zuordnungsprobleme
      • Ungarische Methode
  • Netzplantechnik
    • Einführung Netzplantechnik
    • Ablaufplanung
      • Einleitung zu Ablaufplanung
      • Strukturplanung
      • Netzplanerstellung
    • Zeitplanung
      • Einleitung zu Zeitplanung
      • Beispiel 1: Vorgangsknotennetzplan
      • Beispiel 2: Vorgangsknotennetzplan
    • Kostenplanung
    • Kapazitätsplanung
  • Graphentheorie
    • Einführung: Graphentheorie
    • Kürzeste Wege
      • Einleitung zu Kürzeste Wege
      • Dijkstra-Algorithmus
      • Fifo-Algorithmus
  • 74
  • 11
  • 42
  • 144
einmalig 39,00
umsatzsteuerbefreit gem. § 4 Nr. 21 a bb) UStG
Online-Kurs Top AngebotTrusted Shop

Unsere Nutzer sagen:

  • Gute Bewertung für Operations Research 1

    Ein Kursnutzer am 22.06.2016:
    "top!! ;)"

  • Gute Bewertung für Operations Research 1

    Ein Kursnutzer am 05.12.2015:
    "Super erklärt !! "

NEU! Sichere dir jetzt die perfekte Prüfungsvorbereitung und spare 10% bei deiner Kursbuchung!

10% Coupon: lernen10

Zu den Online-Kursen