Modellierung einer Restriktion eines Entscheidungsproblems

09.05.2008, 15:30

Barbicue

Modellierung einer Restriktion eines Entscheidungsproblems

Hallo!

Ich habe Schwierigkeiten, für folgendes Entscheidungsproblem eine Bedingung zu formulieren:

Von fünf Artikeln können pro Woche nur maximal drei produziert werden. Zudem kann (idR, dazu später mehr) in einer Folgewoche lediglich EIN "neuer" Artikel in Produktion genommen werden. Folgende Liste soll dies verdeutlichen:

W0 {1,2,3}
W1 {2,3,4}
W2 {2,3,5}
W3 {1,3,4}
W4 {2}
W5 {2,3,4}

was bedeutet, dass zB in W2 die Artikel 2, 3 und 5 in Prouktion sind etc.

Bis zur Woche W2 treten keine Problem auf, jeweils nur 3 Artikel in Produktion und nur ein Artikel, der "gewechselt" wird.
Das Setup in W3 wäre nun bei vorliegender W2 NICHT möglich, da mit Artikel 1 und 4 gleich ZWEI neue Artikel in Produktion genommen werden.
Der Übergang zu W4 sollte auch kein Problem darstellen, da zwar kein Artikel in Produktion bleibt, aber nur ein neuer hinzukommt.
W5 im Vergleich zu W4 bildet die Ausnahme, denn da die Restriktion von maximal 3 Artikeln nicht ausgereizt wird, sollen hier auch zwei neue Artikel gebaut werden können... (Ebenso sollte es möglich drei neue Artikel in Produktion zu nehmen, wenn in der Vorwoche gar kein Artikel gebaut wurde.)

Die Restriktion der verschieden Artikel, die maximal pro Woche in Produktion sein dürfen, lässt sich mit einer binären Variable leicht darstellen(bitte entschuldigt die dürftige Darstellungsweise, da ich total neu bin, habe ich mit Erschrecken durch die Vorschau feststellen müssen, dass sowohl Excel-Tabellen als auch Formeln aus Word07 hier nicht vernünftig wiedergegeben werden können unglücklich

...):

i ist Index für Artikel, t für die Wochen.

y_(i,t) ist Element {0,1}

Summe aller y_(i,t) von i=1 bis 5 <= 3

Probleme habe ich bei der Restiktion für die erlaubten Wechsel, meine ersten Versuche waren nicht brauchbar. Am vielversprechendsten war folgende Variante, die alle Szenarien, BIS AUF den Übergang von W3 zu W4, meistern konnte,

Summe über |y_(i,t)- y_(i,t-1) | von i=1 bis 5 <= 2 CH

wobei CH gleich die Anzahl der erlaubten Wechsel von Woche zu Woche ist, hier also 1.

Könnte mir bitte jmd. weiterhelfen oder verraten, wo ich vielleicht Informationen, über diverse Modellierungstricks bekomme. Ich habe bereits in zahlreichen Büchern und Internetdokumenten recherchiert, aber nichts Passendes entdecken können -.-

Bin ich mit der Art der Modellierung vielleicht komplett auf dem Holzweg oder sollte ich es durch mehrere Restriktionen versuchen?

Falls die Beschreibung unzureichend bzw unverständlich ist, lasst es mich wissen smile

Danke und schönes WE Big Laugh

09.05.2008, 23:42

Abakus

Auf diesen Beitrag antworten »

RE: Modellierung einer Restriktion eines Entscheidungsproblems
Mehrere Restriktionen bieten sich in jedem Fall an, ja.

Welche Restriktionen sind denn erlaubt bzw. vorzugsweise gewünscht ? (nur lineare oder dürfen auch Produkte von Variablen benutzt werden?)

Kannst du das Problem ggf. durch "und"- bzw. "oder"-Bedingungen weiter zerlegen und damit die einzelnen Fälle erledigen ? Vielleicht lässt sich sowas dann wieder allgemeiner zusammenfassen.

Grüße Abakus smile

10.05.2008, 11:17

Barbicue

Auf diesen Beitrag antworten »

RE: Modellierung einer Restriktion eines Entscheidungsproblems
Zunächst einmal Danke für die rasche Antwort!

Linear oder nichtlinear? Erlaubt ist, was Erfolg verspricht. Augenzwinkern

Oder sollte ich vor dem Hintergrund, dass ich das Modell später auch in eine mathematische Modellierungssprache verpacken will, von nichtlinearen Variablen absehen (soweit ich mich informiert habe, sind die Solver auch für nichtlineare Probleme gerüstet)? geschockt

Durch "und" und "oder" Beziehungen habe ich mir das Problem auch verdeutlicht, jedoch bin ich mir da letztlich nicht sicher, wie sich das mathematisch korrekt in "Gleichungsform" ausdrücken lässt.

Da der Übergang von Woche W4 zu W5 doch nicht meinen Anforderungen genügt Hammer

, möchte ich halt mathematisch sauber Folgendes abbbilden:

siehe (hoffentlich) Anhang...

Weiß nicht, ob ich durch Excel zu so einem "Wenn-Dann" Junkie geworden bin, aber nun frage ich mich, wie sich das in Gleichungen pressen lässt... Oo

Erneut Entschuldigung, aber auch der Formeleditor "will nicht so, wie ich das will". Augenzwinkern

10.05.2008, 18:28

Abakus

Auf diesen Beitrag antworten »

RE: Modellierung einer Restriktion eines Entscheidungsproblems
OK soweit. Nun brauchst du zunächst eine (sehr) ausführliche Fallunterscheidung aller vorkommenden Möglichkeiten. Die einzelnen Möglichkeiten kannst du dann in Gleichungen übersetzen.

ZB:

Es bezeichne $\begin{eqnarray*} x_{i,t} \end{eqnarray*}$ die i-te Produktion zum Zeitpunkt t, ist diese Variable 1 wird diese durchgeführt, ist sie 0, wird sie nicht durchgeführt. Nun gibt es folgende Fälle:

[1] es werden 3 Produkte fabriziert und nichts wird geändert:

$\begin{eqnarray*} \sum_{i=1}^5 x_{i,t} = 3 \end{eqnarray*}$ und $\begin{eqnarray*} \sum_{i=1}^5 x_{i,t+1} = 3 \end{eqnarray*}$ und $\begin{eqnarray*} \sum_{i=1}^5 x_{i,t} \cdot x_{i,t+1} = 3 \end{eqnarray*}$

[2] es werden 3 Produkte fabriziert, aber genau 1 Produkt wird ausgetauscht:

$\begin{eqnarray*} \sum_{i=1}^5 x_{i,t} = 3 \end{eqnarray*}$ und $\begin{eqnarray*} \sum_{i=1}^5 x_{i,t+1} = 3 \end{eqnarray*}$ und $\begin{eqnarray*} \sum_{i=1}^5 x_{i,t} \cdot x_{i,t+1} = 2 \end{eqnarray*}$

[3] genau eines der 3 fabrizierten Produkte wird eingestellt:

$\begin{eqnarray*} \sum_{i=1}^5 x_{i,t} = 3 \end{eqnarray*}$ und $\begin{eqnarray*} \sum_{i=1}^5 x_{i,t+1} = 2 \end{eqnarray*}$ und $\begin{eqnarray*} \sum_{i=1}^5 x_{i,t} \cdot x_{i,t+1} = 2 \end{eqnarray*}$

[4] usw.

Es ergeben sich etliche Fälle (erstmal 17 ?). Ich würde die zunächst ausformulieren, und dann sehen, ob sich was zusammenfassen lässt.

Die logischen Formeln kannst du auch noch in Gleichungen umformen.

Grüße Abakus smile

PS: durch den Zitat-Button kannst du sehen, wie die Formeln in Latex aussehen

11.05.2008, 00:29

Barbicue

Auf diesen Beitrag antworten »

RE: Modellierung einer Restriktion eines Entscheidungsproblems
Ei, vielen Dank für die sehr hilfreiche Anregung!

Habe die Übung mal durchgemacht und meine, und das finde ich äußerst überraschend und bitte im Überprüfung, schließlich ist es doch recht spät, die Anforderungen mit einer allgemein gültigen Restriktionen festmachen zu können:

$\begin{eqnarray*} \sum_{i=1}^5 y_{i,t} * y_{i,t+1} \geq (\sum_{i=1}^5 y_{i,t+1}) -1 \end{eqnarray*}$ für $\begin{eqnarray*} \sum_{i=1}^5 y_{i,t+1} > 0 \end{eqnarray*}$
für $\begin{eqnarray*} \sum_{i=1}^5 y_{i,t+1} = 0 \end{eqnarray*}$ ist natürlich auch
$\begin{eqnarray*} \sum_{i=1}^5 y_{i,t} * y_{i,t+1} = 0 \end{eqnarray*}$

Liege ich da richtig...? Oo

Danke und frohe Pfingsten Prost

11.05.2008, 16:48

Abakus

Auf diesen Beitrag antworten »

RE: Modellierung einer Restriktion eines Entscheidungsproblems
Das sieht schon gut aus, ich übersehe aber nicht, ob das nun wirklich alle Fälle abdeckt. Wie ist es zB mit dem Wechsel (im folgenden sind die Variablenwerte angegeben):

0 0 0 0 0 -> 1 1 0 0 0

Grüße Abakus smile

12.05.2008, 10:25

Barbicue

Auf diesen Beitrag antworten »

RE: Modellierung einer Restriktion eines Entscheidungsproblems
Ein Wechsel, der zwei "neue" Produkte mit sich bringt, genügt wie in meinem zweiten Beitrag geschrieben, DOCH NICHT MEHR meinen "realen" Anforderungen. Big Laugh

Derartige Wechsel werden von der kreierten Restriktion auch untersagt. Im Übrigen lässt sich diese auch auf "größere" Fälle beziehen; subtrahiert werden müssen halt immer die Anzahl der erlaubten Wechsel, also wie hier -1.

Danke nochmals! Wink

14.05.2008, 01:16

Abakus

Auf diesen Beitrag antworten »

RE: Modellierung einer Restriktion eines Entscheidungsproblems

Zitat:

Original von Barbicue
Ein Wechsel, der zwei "neue" Produkte mit sich bringt, genügt wie in meinem zweiten Beitrag geschrieben, DOCH NICHT MEHR meinen "realen" Anforderungen. Big Laugh

Ahh, ok. Dann sieht es gut aus.

Grüße Abakus smile

Neue Frage »

Antworten »

Modellierung einer Restriktion eines Entscheidungsproblems

Verwandte Themen