Übung 02: Primaler Simplex

Grundlagen Operations Research

Video zur Übung

Aufgabe 1

Lösen Sie folgendes Problem mit dem primalen Simplex-Algorithmus:

maximiere F=45X1+25X2+35X3+20X4u.d.N.2X1−X2+X3+2X4≤30X1+2X2+3X3−X4≤243X1+2X2−X3+2X4≤36X1,X2,X3,X4≥0 \begin{aligned} \text{maximiere } \; & F = 45 X_1 + 25 X_2 + 35 X_3 + 20 X_4 \\ \text{u.d.N.} \quad & 2 X_1 - X_2 + X_3 + 2 X_4 \le 30 \\ & X_1 + 2 X_2 + 3 X_3 - X_4 \le 24 \\ & 3 X_1 + 2 X_2 - X_3 + 2 X_4 \le 36 \\ & X_1, X_2, X_3, X_4 \ge 0 \end{aligned}

  1. Geben Sie die Simplex-Multiplikatoren πik\pi_i^k nach jeder Iteration an.
  2. Sei X2+X4=0X_2 + X_4 = 0. Lösen Sie das Restproblem grafisch. Ist der zugehörige Zielfunktionswert eine obere oder eine untere Schranke?
  3. Überprüfen Sie Ihre Lösungen mit Julia.

Ihre Lösung in Julia

Es bietet sich an, die Koeffizienten als Matrix/Vektoren zu erfassen und mit indizierten Variablen XjX_j zu modellieren. Nennen Sie Ihr Modell modell:

using JuMP, HiGHS

A = [2 -1  1  2;
     1  2  3 -1;
     3  2 -1  2]
b = [30, 24, 36]
c = [45, 25, 35, 20]

modell = Model(HiGHS.Optimizer)
set_silent(modell)

# IHR CODE HIER

optimize!(modell)
@assert isapprox(objective_value(modell), 2270 / 3; atol = 1e-3) "Noch nicht korrekt. Prüfen Sie Matrix A, b und c."
println("Vollständiges Problem korrekt: F* = ", objective_value(modell))

Restproblem X2=X4=0X_2 = X_4 = 0

Fixieren Sie X2X_2 und X4X_4 auf null (fix(modell[:X][2], 0; force = true)) und lösen Sie erneut. Vergleichen Sie den resultierenden Zielwert mit dem des vollständigen Problems (vgl. Aufgabenteil 2).

@assert isapprox(objective_value(modell), 720.0; atol = 1e-4) "Noch nicht korrekt. Sind X2 und X4 wirklich fixiert?"
println("Restproblem korrekt: F = ", objective_value(modell))