Lineares Optimierungsproblem

Question

Aufgabe:

Für eine Geburtstagsparty sollen 10 Liter Bowle bestehend aus Fruchtmix, hochprozentigen Alkohol und Sekt hergestellt werden.

• Die Bowle soll mindestens 4Liter Fruchtmix und mindestens 1,5Liter hochprozentigen Alkohol beinhalten.

• Sie soll höchstens 3 mal soviel Fruchtmix wie Sekt enthalten.

• Und mindestens \( \frac{2}{3} \) soviel Sekt wie Fruchtmix und hochprozentigen Alkohol zusammen enthalten.

Formulieren sie ein lineares Optimierungsproblem für die kostengünstigste Mischung, wenn die Kosten für den Fruchtmix 3€ pro Liter, für den hochprozentigen Alkohol 8€ pro Liter und für den Sekt 4€ pro Liter betragen.

Problem/Ansatz:

Ich kenne mich mit Optimierungsproblemen noch nicht so gut aus, habe aber schonmal ein paar Bedingungen versucht aufzustellen, aber wie man nun weiter vorgeht ist mir nicht klar.

F-Fruchtmix,  A-hochprozentiger Alkohol,  S-Sekt

F + A + S = 10

F ≥ 4

A ≥ 1,5

3*F ≤ S

\( \frac{2}{3} \)*S ≥ F+A

Answer 1

Es muss

        f(F,A,S) = 3F + 8A + 4S

minimiert werden. Zunächst wird das Problem in die Normalform überführt. Das heißt

1. Das Problem wird in eine Maximierungsproblem umgewandelt.
2. Nebenbedingungen werden in ≤-NB umgewandelt, wobei auf der rechten Seite der Ungleichung keine Variablen stehen.
3. Variablen werden auf nicht-negative Zahlen beschränkt.
4. Die Nebenbedingungen werden in Gleichungen umgewandelt indem sogenannte Schlupfvariablen eingeführt werden.
   

Zu 1. Die Zielfunktion wird mit -1 multipliziert. Die Funktion

        - f(F,A,S) = -3F - 8A - 4S

muss also maximiert werden.

Zu 2. Die Nebendedingung F + A + S = 10 ist genau dann erfüllt, wenn sowohl

(1)        F + A + S ≤ 10

als auch

        F + A + S ≥ 10

erfüllt sind. Letzteres wird in eine ≤-NB umgewandelt indem mit -1 multipliziert wird:

(2)        -F - A - S ≤ 10

ebenso lauten die weiteren Nebenbedingungen

(3)        F ≤ -4

(4)        -A ≤ -1,5

(5)        3F - S ≤ 0

(6)        F + A - 2/3·S ≤ 0

Es gibt also sechs Nebenbedingungen.

Zu 3. Das trifft auf dein Problem nicht zu, weil negative Flüssigkeitmengen nicht gültig sind. Der Vollständigkeit halber nehme ich aber mal an, das F auch negativ sein darf. Dann teilt man F in zwei Variablen

        F = F₊ - F_-

auf, wobei F₊ ≥ 0 und F_- ≥ 0 sind. Anschließend ersetzt man in der Zielfunktion und in den Nebenbedingungen jedes F durch F₊ - F_-.

Zu 4. Die Nebenbedingungen lauten

(1)        F + A + S + s₁ = 10

(2)        -F - A - S + s₂ = 10

(3)        F + s₃ =  -4

(4)        -A + s₄ = -1,5

(5)        3F - S + s₅ = 0

(6)        F + A - 2/3·S + s₆ = 0

Jetzt kann das Problem mit dem dualen Simplexalgorithmus gelöst werden.

Answer 2

Meine Empfehlung wäre einmal die zum LP min gehörigen NB A x >= b aufzustellen

höchstens  3 mal soviel Fruchtmix wie Sekt enthalten:

z.B. 1 L skt + 3 L fmx  ===> fmx/skt <= 3 ===>  0 <=3 skt - fmx

alk analog  ===>

Da LP min, darf man die Mengenbetrachtung  sicher auf fmx+alk+skt>=10 setzen - um das Tableau nicht unnötig zu komplexen

minimize_lp(

3*fmx+8*alk+4*skt,[
    fmx+alk+skt>=10,
    fmx >= 4,
    alk >=1.5,
    3*skt-fmx >=0,
    skt-2/3*(fmx+alk)>=0]
), nonegative_lp=true;

[41.5,[skt=4.0,fmx=4.5,alk=1.5]]

===> Starttableau des dualen LPmin

\(\small \left(\begin{array}{rrrrrrrrr}1&0&-1&-\frac{2}{3}&1&1&0&0&3\\0&1&0&-\frac{2}{3}&1&0&1&0&8\\0&0&3&1&1&0&0&1&4\\-4&-\frac{3}{2}&0&0&-10&0&0&0&0\\\end{array}\right)\)