OR KURS 853 EA

denke ich habe das rucksackproblem gelöst .. nach kapitel 4, seite 71,
"rekursives verfahren zur Lösung des rucksackproblems"

lösung: x1=6; x2=0; x3=0; x4=1; x5=0; zielfunktionswert z = 25

hat jemand was anderes rausbekommen ?

mache mich morgen an beispiel 2 oder 3 ran .. 😱

lg
karin

habe bei der Aufgabe 3 (rundreiseproblem) folgendes ergebnis:
- schritt 1: nach anwenden der ungarischen methode ergibt sich eine
permutation phi = (1, 2, 3) (4, 5) mit dem zielfunktionswert z = 15;
- schritt 2: aufbrechen des zweiten teilzyklus (da kürzer)
problem P1: c45=unendlich; z1 = 2;
problem P2: c54=unendlich; z2=1;
- schritt 3: da z1 > z2 -> lösen von P2 mit c54 = unendlich:
nach anwenden der ungarischen methode ergibt sich eine
permutation phi = (1, 4, 5, 2, 3) mit dem zielfunktionswert z = 16;

.. ist optimallösung da z1 > z2;

hat das noch jemand rausbekommen ?

lg
karin

Kaktus,
habe die gleichen Ergebnisse bei Aufgabe 3 raus. Das beruhigt mich erst einmal. Allerdings macht mir die Aufgabe 2 arge Sorgen.
Immerhin habe ich schon:
max 20x1+38x2+9x3-250-110y
u.d.N.
2x1+1,5x2+0,5x3<=2600
3x1+3,5x2+0,2x3<=4100
???
y E (0,1) und x1,x2,x3 >=0 Denke, bis dahin ist es in Ordnung.
Und ab da fangen meine Probleme mit der Formulierung an.
x1+x2+x3>=1100 (Sobald x1+x2+x3>=1100; y=1) ?
x3>=250+150? ( mit x1+x2>=150).
Brauche dringend Hilfe.

mephista,

ich habe bei der kostenfunktion die du mit -250-110y in die zielfunktion
geschrieben hast - 2 binärvariablen da auch keine produktion vorkommen kann, oder? in der Aufgabe steht irgendwie so "bei produktionsaufnahme..."
habe daher hier -250y1 - 360 y2
mit
y1 … für Gesamtstückzahl x (=x1+x2+x3) < 1100
y2 … = für Gesamtstückzahl x >= 1100
beide 0 heisst bei mir keine produktion;
keine ahnung ob das zuviel des guten ist ..
was dann meiner meinung nach fehlt, ist die nebenbedingung für die funktion der fixkosten unter einbeziehung der binärvariable, da die nebenbedingung nur gelten soll wenn die binärvariable 1 ist.
für die Kostenfunktion muss ja in einem fall
x1+x2+x3 < 1100 sein und im anderen fall >= 1100
(da ich ja y1 und y2 habe, habe ich auch eine bedingung
eingebaut, damit nicht beides gleichzeitig 1 sein kann, y1 + y2 <= 1)

dann fehlt dir noch die nebenbedingung für die stückzahlen
da x3 >= 250 für (x1>=0 und x2=0) oder (x1=0 und x2>=0)
und x3>= 400 für x1 > 0 und x2 > 0

das was du bereits hattest ist sonst ok.

ich hoffe ich konnte dir weiter helfen obwohl ich nicht gleich
meine Lösung geschrieben habe .. sonst gib bescheid
der rest passt soweit 😉

schönen abend noch!

Stimmt, da steht: bei Produktionsaufnahme. Somit scheinst du mit 2 Binärvariablen recht zu haben bzw. benötige ich 3 Binärvariablen, da es ja heisst, P1 als auch P2 für die Bedingung x3>= 250+150? Ich breche gerade zusammen.

Yip - ich habe auch 3 binärvariablen in summe 🙂
am besten die bedingungen aufstellen und dann in ruhe durch setzen der verschiedenen möglichen(!) kombinationen für die binärvariablen prüfen ob
die entsprechenden bedingungen beschrieben werden.

Ich hab es jetzt auch geschafft. In Aufgabe 1 und 3 komme ich zu den gleichen Ergebnissen wie sie hier schon beschrieben sind.

Bei Aufgabe 2 bin ich auf folgendes Ergebnis gekommen:

max G= 20 x1+38 x2+ 9 x3
udN 2 x1+ 5 x2+ 0,5 x3 <= 2600
3 x1+3,5 x2+0,2 x3 <= 4100
x3>= 250

x1 >= delta x1<= M(my+delta)
x2 >= delta x2<= K(alpha+delta) M und K sind genügend grosse Zahlen
x3 >= 250+150delta
my+alpha<=1

Wenn delta=1 werden x1 und x2 produziert und x3 wird mit mind. 400 produziert. Wenn delta=0 werden x1 und x2 nicht produziert und x3 wird mit >= 250 produziert.

x1+x2+x3>= 1100 x eta
x1+x2+x3<= 1099 + L x eta
my,alpha,delta,eta aus (0,1)
x1,x2,x3>=0, ganzz.


Also, wirklich erklären kann ich das ganze System nicht so gut (WE-Seminar) aber ich gehe schwer davon aus dass es richtig ist.

Hat jemand mal ein bisschen bessere Literatur gefunden als das Skript. Da gibt es wirklich ziemlich viele Sachen die ich einfach gar nicht verstehe....

Martha,
was ist mit den Fixkosten in Höhe von 250 bzw. 360?
Liebe Grüsse
Mephista

reicht nicht eine Binärvariable in der Zielfunktion? Hier steht zwar, dass "bei Produktionsaufnahme..." die Stückkosten entstehen, aber eine andere Bedingung besagt "Für Produktart P3 ist eine Mindestherstellungsmenge von 250 Stück einzuhalten". Das heißt doch, eine Produktion wird in jedem Fall stattfinden, oder?@kaktusIch glaub in der Nebenbedingung x3 >= 250 kann man das "für ..." weglassen, weil die Produktion in jedem Fall >=250 ist, auch wenn sie >=400 ist.Ansonsten bin ich bei den Nebenbedingungen mit den Binärvariablen inzwischen total verunsichert! Und so wahnsinnig viel Zeit ist ja auch nicht mehr.Wäre für schnelle Hilfe super dankbar!-Niko-

sunik,

ich fürchte so wirklich kann ich dir da auch nicht weiterhelfen;
ich habe die angabe für die mindestmenge von x3 so verstanden, dass
diese gilt wenn (x1>=0 und x2=0) oder (x1=0 und x2>=0)
--> eine von beiden ist > 0;
und zusammen mit dem "bei produktionsaufnahme" komme ich auf 3 binärvariablen;
für x1, x2 und x3 gilt ja auch >=0 ..
aber vielleicht ist es ja auch redundant, da sowieso immer produziert wird ..
ich lasse es mal so.

lg
karin

eine vielleicht sehr dumme Frage:

Wie errechnet sich denn die z bei Aufgabe Nummer 3? Ich komme noch bis zur Matrix nach der Ungarischen Methode, aber danach ist es aus.

Vielen Dank!

Matthias

MHaselbauer schrieb:

Hallo Leute,

eine vielleicht sehr dumme Frage:

Wie errechnet sich denn die z bei Aufgabe Nummer 3? Ich komme noch bis zur Matrix nach der Ungarischen Methode, aber danach ist es aus.

Vielen Dank!

Matthias

Zum Vergrößern anklicken....

gibt keine dummen fragen sondern
- nur dumme antworten oder
- leute die gar nicht fragen
😀

hier meine Lösung und auch der link auf das dokument mit dem ich die ungarische methode kapiert habe https://www.pim.uni-essen.de/vorlesungen/EOR/Sommer2004/Folien_OR-Teil_5.pdf

ad Aufgabe 3)
geg: Entfernungsmatrix:

cij j=1 j=2 j=3 j=4 j=5
i=1 4 2 4 4
i=2 3 1 5 5
i=3 2 8 6 7
i=4 6 7 2 2
i=5 5 7 5 6

Anwenden der ungarischen Methode:

- modifizierte Matrix nach zeilenweiser Reduktion:

cij j=1 j=2 j=3 j=4 j=5
i=1 2 0 2 2
i=2 2 0 4 4
i=3 0 6 4 5
i=4 4 5 0 0
i=5 0 2 0 1

- modifizierte Matrix nach spaltenweiser Reduktion und Zuordnung der Nullelemente:

cij j=1 j=2 j=3 j=4 j=5
i=1 0* 0 1 2
i=2 2 0* 3 4
i=3 0* 4 3 5
i=4 4 3 0 0*
i=5 0 0 0 0*

Zielfunktionswert:
z = c12 + c23 + c31 + c45 + c54 = 4 + 1 + 2 +2 + 6 = 15

i: 1 2 3 4 5
phi(i): 2 3 1 5 4 => phi = (1, 2, 3) (4, 5)

- Aufbrechen des zweiten, kürzeren Teilzyklus:
Definition der 2 neuen Probleme:

P(1) : c45 = unendl. ; z(1) = c43 + c15 = 0 + 2 = 2
P(2) : c54 = unendl. ; z(2) = c51 + c14 = 0 + 1 = 1

->P(2) zuerst lösen, da z(1) > z(2)

Ausgangsmatrix für P(2) :

cij j=1 j=2 j=3 j=4 j=5
i=1 0 0 1 2
i=2 2 0 3 4
i=3 0 4 3 5
i=4 4 3 0 0
i=5 0 0 0


- reduzierte Matrix nach zeilenweiser (entspricht auch spaltenweiser) Reduktion und Zuordnung der Nullelemente:

cij j=1 j=2 j=3 j=4 j=5
i=1 0 0 0* 2
i=2 2 0* 2 4
i=3 0* 4 2 5
i=4 4 3 0 0*
i=5 0 0* 0

Zielfunktionswert:
z = c14 + c23 + c31 + c45 + c52 = 4 + 1 + 2 + 2 + 7 = 16

i: 1 2 3 4 5 --> 1 4 5 2 3
phi(i): 4 3 1 5 2 --> 4 5 2 3 1 --> phi = (1, 4, 5, 2, 3)

viel spass 🙂