Mit welchem Verfahren kann ich dieses Lineare Program lösen?

Question

Aufgabe:

In einem Fuhrbetrieb stehen zum Befahren von 3 Routen R1, R2, R3 drei Wagen W1, W2, W3 mit den Nutzlasten 1,5 t, 3,5 t und 5 t zur Verfügung. Auf der Route R1 sind 780 t, auf R2 425 t und R3 1000 t zu transportieren. Der Wagen W1 darf höchstens 250, W2 höchstens 250 und W3 höchstens 200 Routen insgesamt befahren. Jeder Wagen wird auf jeder Route voll ausgelastet. Die Kosten für eine Fahrt sind in der folgenden Tabelle angegeben

Erstellen Sie ein lineares Programm (Entscheidungsvariablen, Nebenbedingungen, NNB und Zielfunktion) zur Lösung dieser Aufgabe

Problem/Ansatz:

Entscheidungsvariablen:

\( x_{i j} \) : Anzahl der Fahrten von Wagen \( i \) (mit \( i=1,2,3 \) ) auf Route \( j \) (mit \( j= \) \( 1,2,3) \)

Nebenbedingungen:

\( \begin{array}{c}1.5 x_{11}+3.5 x_{21}+5 x_{31} \geq 780 \\ 1.5 x_{12}+3.5 x_{22}+5 x_{32} \geq 425 \\ 1.5 x_{13}+3.5 x_{23}+5 x_{33} \geq 1000 \\ x_{11}+x_{12}+x_{13} \leq 250 \\ x_{21}+x_{22}+x_{23} \leq 250 \\ x_{31}+x_{32}+x_{33} \leq 200 \\ x_{i j} \geq 0 \end{array} \)

Zielfunktion → Mini :

\( \begin{array}{l}Z=35 x_{11}+65 x_{12}+85 x_{13} \\ +60 x_{21}+90 x_{22}+110 x_{23} \\ +25 x_{31}+33 x_{32}+40 x_{33}\end{array} \)

Wäre das soweit richtig und wie würde ich das jetzt lösen(ohne Solver)?

Answer 1

Wäre das soweit richtig

Die ersten drei Nebenbedingungen sollen Gleichungen sein, nicht Ungleichungen.

und wie würde ich das jetzt lösen(ohne Solver)?

Gestern, bei Deiner letzten Frage, kanntest Du den Simplex-Algorithmus.

Comments

Gestern, bei Deiner letzten Frage, kanntest Du den Simplex-Algorithmus.

Das stimmt, aber ich dachte, es könnte möglicherweise eine bessere oder einfachere Methode geben.

Answer 2

Da es sich hier um ein ganzzahliges Problem handelt (ILP), kann es sein, dass der Simplex-Algorithmus gar keine ganzzahlige Lösung liefert.

Weitere Ansätze können daher folgende sein:

Branch-and-Bound-Algorithmen,

das Schnittebenenverfahren,

Lagrange-Relaxation

Was die "Einfachheit" angeht: ganzzahlige Probleme sind meist gar nicht so einfach zu lösen, da sie NP-schwer sind und damit nicht in polynomieller Zeit lösbar.

Answer 3

Hm,

wenn man Simplexen will ist das fürchterlich aufwendig und über die Rechnung mit Tableaus nicht sinnvoll handlebar. Bei automatisiertem Simplex, z.B. mit wxMaxima kann man eine Entwicklung zur Ganzzahl selber einbringen.

Da sind Zahlendreher in deinen Angaben - kann das sein? Anpassung eingefügt!

http://www.dma.ufv.br/maxima/index.php

load("simplex");

minimize_lp(
35*x11+60*x12+25*x13+65*x21+90*x22+33*x23+85*x31+110*x32+40*x33,[
1.5*x11+3.5*x21+5*x31=780,
1.5*x12+3.5*x22+5*x32=425,
1.5*x13+3.5*x23+5*x33=1000,
x11+x12+x13<=250,
x21+x22+x23<=250,
x31+x32+x33<=200,
x11=220,
x21=0,
x22=0
]),
nonegative_lp=true;

[33950.0,[x33=25.0,x23=250.0,x13=0,x32=85.0,x22=0,x12=0,x31=90.0,x21=0,x11=220.0]]

schrittweise Entwicklung zur Ganzzahl mit:

x11=220, x21=0, x22=0

sind nach je einem Durchlauf als kleinster Bruchkoeffizent ganzzahlig gesetzt worden.

[[1.5*x11+3.5*x21+5*x31,1.5*x12+3.5*x22+5*x32 ,1.5*x13+3.5*x23+5*x33],
[x11+x12+x13,x21+x22+x23,x31+x32+x33]],
[x33=25.0,x23=250.0,x13=0,x32=85.0,x22=0,x12=0,x31=90.0,x21=0,x11=220.0];

[[780.0,425.0,1000.0],[220.0,250.0,200.0]]

würde also die exakten Mengen transportieren und die Wagen voll auslasten...

Comments

Stimmen Deine Nebenbedingungen?

---

Jetzt schon, hab die Daten per copy&paste übernommen und erst später gemerkt, dass da Zahlendreher drin sind - Zielfunktion stimmte nicht mit NB über ein - Korrektur erfolgt...

Interessanter weise ist

minimize_lp(
35*x11+60*x12+25*x13+65*x21+90*x22+33*x23+85*x31+110*x32+40*x33,[
x11+x12+x13<=250,
x21+x22+x23<=250,
x31+x32+x33<=200,
1.5*x11+3.5*x21+5*x31>=780,
1.5*x12+3.5*x22+5*x32>=425,
1.5*x13+3.5*x23+5*x33>=1000,
x33=25
]),
nonegative_lp=true;

die kürzeste Version...

---

die kürzeste Version...

Gesucht wird die billigste.

Die gute Nachricht ist, bei diesem LP gibt es nur eine Lösung mit dem Optimum.

---

\( \begin{array}{c}1.5 x_{11}+3.5 x_{21}+5 x_{31} \ =780 \\ 1.5 x_{12}+3.5 x_{22}+5 x_{32} \ = 425 \\ 1.5 x_{13}+3.5 x_{23}+5 x_{33} \ = 1000 \\ x_{11}+x_{12}+x_{13} \leq 250 \\ x_{21}+x_{22}+x_{23} \leq 250 \\ x_{31}+x_{32}+x_{33} \leq 200 \\ x_{i j} \geq 0 \end{array} \)

Das sind doch die richtigen Nebenbedingungen oder?

Ich habe ein paar Videos angeschaut, und anscheinend kann man ein Transportproblem auch mit der Stepping-Stone-Methode lösen. Allerdings müsste ich noch herausfinden, wie ich diese Methode auf die gegebene Aufgabe anwenden kann.

---

Das sind doch die richtigen Nebenbedingungen oder?

Wie der Wächter geschrieben hat, der Fehler (bei Deiner Lösung) lag in der Zielfunktion. Bei ihm ist auch noch etwas bei den Nebenbedingungen falsch.

Ich habe ein paar Videos angeschaut ... Allerdings müsste ich noch herausfinden, wie ich diese Methode auf die gegebene Aufgabe anwenden kann.

Damit sieht man, dass die "paar Videos" untauglich waren, es zu lernen. Energiesparende, vegane Bücher bringen typischerweise mehr.

Ich finde den Originalartikel gut verständlich, dort hat es sogar ein Beispiel (Charnes/Cooper: The stepping stone method of explaining linear programming calculations in transportation problems, 1954).

---

\( \begin{array}{l}Z=35 x_{11}+60 x_{12}+25 x_{13} \\ +65x_{21}+90 x_{22}+33 x_{23} \\ +85 x_{31}+110 x_{32}+40 x_{33}\end{array} \)

Mein Fehler war, dass ich die Nummerierung von links nach rechts durchgeführt habe, anstatt von oben nach unten.