Formulieren Sie ein Problem als Problem der gemischten linearen Programmierung

Sep 29 2020

Ich muss das folgende Problem als Mixed Integer Linear Programming-Problem formulieren

Ein Landwirt muss einen 17-Jahres-Geschäftsplan erstellen, in dem er entscheidet, wann er einen neuen LKW verkauft oder kauft. Der Landwirt kann den LKW nicht verkaufen, bevor er zwei Jahre alt ist, aber er muss ihn verkaufen, bis er fünf Jahre alt ist. Der Preis für einen neuen Lkw beträgt 43.000 USD, verliert jedoch beim Kauf 10% seines Wertes plus zusätzliche 7% pro Jahr. Außerdem wissen wir, dass die Lkw-Preise gegenüber dem Vorjahr jedes Jahr um 5% steigen.

Die jährlichen Betriebskosten des Lkw betragen 1300 USD und steigen jedes Jahr um 15%.

Bisher habe ich nur das Problem, dass ich die Kosten-Gewinn- Funktion minimieren muss, aber keine Ahnung habe, wie ich sie linear machen oder überhaupt anfangen soll, die Einschränkungen zu formulieren. Jedes ähnliche Problem, das ich gefunden habe, verwendet einen dynamischen Programmieransatz.

Antworten

1 GeoffreyBrent Sep 29 2020 at 08:51

Aus dem Zusammenhang gehe ich davon aus, dass der Landwirt immer einen LKW haben muss, und die Frage ist, wann er ihn ersetzen sollte.

Für die Einschränkungen können Sie 17 binäre Entscheidungsvariablen formulieren: $x_1$ = "in Jahr 1 ersetzen?", $x_2$ = "in Jahr 2 ersetzen?", ... etc.

"Kann nicht verkaufen, bevor es zwei Jahre alt ist": dh kann nicht in zwei aufeinander folgenden Jahren ersetzt werden, dh keine zwei aufeinander folgenden $x_i$ kann beides sein 1. Also $x_1+x_2 \le 1, x_2+x_3 \le 1, ...$

"Muss verkaufen, bis es fünf Jahre alt ist": dh wenn wir es im Jahr ersetzen $n$muss irgendwo zwischen Jahren wieder ersetzt werden $n+1$ zu $n+5$. Das heißt, wenn$x_n=1$, $x_{n+1}, x_{n+2},...,x_{n+5}$kann nicht alles Null sein. Da es sich bei allen um binäre Variablen handelt, kann dies wie folgt ausgedrückt werden:$x_n \le x_{n+1}+x_{n+2}+...+x_{n+5}$. (Ich überlasse es Ihnen, herauszufinden, wie Sie mit den Enden des Zeitraums umgehen sollen.)

Die Wiederbeschaffungskosten sind dann eine einfache lineare Funktion von Ihnen $x_i$Da sie nur davon abhängen, in welchem Jahr Sie neue LKWs kaufen - die Tatsache, dass es sich um eine Exponentialfunktion des Jahres handelt, spielt keine Rolle, sie ist in Ihren x-Variablen immer noch linear.

Der schwierige Teil des Problems besteht darin, wie mit den Kosten umzugehen ist, die davon abhängen, wie lange Sie den LKW hatten, dh Betriebskosten und -1 * Wiederverkaufswert.

Eine Möglichkeit, dies in einem linearen Rahmen zu handhaben, wäre die Einführung eines Satzes von binären Hilfsvariablen $y_{i,j}$ wo $y_{i,j}=1$ genau dann, wenn es einen LKW gibt, der im Jahr gekauft wird $i$ und im Jahr verkauft $j$.

Sie können dann die Gesamtbetriebskosten und den Wiederverkauf abzüglich der Kosten als lineare Funktion davon ausdrücken $y_{i,j}$(Berücksichtigen Sie auch hier unbedingt die Endfälle!). Jetzt müssen Sie nur noch einige Einschränkungen festlegen, die sich auf das beziehen$x_i$ zum $y_{i,j}$ auf eine Weise, die die Definition von erzwingt $y_{i,j}$. Das ist:$y_{i,j} = 1$ dann und nur dann, wenn $x_i=x_j=1$ und keiner der Werte zwischen ihnen ist 1. Dies kann durch zwei lineare Ungleichungsbeschränkungen erreicht werden, die nicht zu schwer herauszufinden sein sollten - wenn Sie hier Schwierigkeiten haben, kommentieren Sie dies bitte und ich werde es erweitern.

Dies erweitert die Problemgröße ein wenig, da Sie 17 ^ 2 = 289 zusätzliche Hilfsvariablen erstellen. Wenn jedoch die Effizienz eine Rolle spielt, können Sie dies erheblich reduzieren, indem Sie dies bemerken $y_{i,j}$ kann nur 1 sein, wenn $2 \le j-i \le 5$.

Bearbeiten: Wie Rob Pratt in den Kommentaren vorgeschlagen hat, können Sie das beseitigen $x_i$ aus dem Problem insgesamt durch Anwenden von Flussbilanzbeschränkungen: wenn $y_{i,j}=1$ es muss genau einen geben $k$ so dass $y_{j,k}=1$und so weiter. (Wieder beschönigen Sie die Endbedingungen.)

Das behalten $x_i$s in dem Problem kann es einfacher machen zu verstehen, was vor sich geht, aber in der Lage zu sein, das Problem zu transformieren, ist eine sehr nützliche Fähigkeit und es lohnt sich, sie weiterzuentwickeln.

2 marcotognoli Sep 30 2020 at 02:57

Das folgende Modell gibt die zeitliche Abfolge des Einkaufs für LKW an, sodass der Cashflow innerhalb des Planungshorizonts von 17 Jahren optimal ist. Das Modell erfordert$68$ Boolesche Variablen ($68=17 \cdot 4$) und $17$Ganzzahlvariablen (1 Ganzzahlvariable für jedes Jahr). Jedes Jahr wird mittels eines Pedices bezeichnet$k=1, 2, \cdots, m=17$.

Für jedes Jahr gibt es grundsätzlich zwei Möglichkeiten:

Den LKW im k-ten Jahr „verkaufen“ oder „kaufen“

Für den Wettbewerb stehen vier Arten von Plänen zur Verfügung:

1. Plan : Halten Sie den LKW$2$ Jahre, $t_1=2$;;

2. Plan : Halten Sie den LKW$3$ Jahre, $t_2=3$;;

3. Plan : Halten Sie den LKW$4$ Jahre, $t_3=4$;;

4. Plan : Halten Sie den LKW$5$ Jahre, $t_4=5$.

Wir bezeichnen mittels eines Pedices $j=1, 2, \cdots , 4$die Art des angenommenen Plans für jedes Jahr. Als Konsequenz brauchen wir$17 \cdot 4 = 68 $Variablen, um alle möglichen Entscheidungen zu definieren. Lassen Sie uns die Boolesche Variable einführen$x_{k,j}$::

$x_{k,j}=1$ Wenn ich mich im k-ten Jahr entscheide, den LKW so viele Jahre zu halten, wie im j-ten Plan angegeben
$x_{k,j}=0$ Wenn ich mich im k-ten Jahr entscheide, den LKW nicht so viele Jahre zu halten, wie im j-ten Plan angegeben.

Zum Beispiel die Reihenfolge $ x_{1,3}= x_{2,3}= \cdots = x_{k-1,3}= x_{k+1,3}= \cdots = 0 $ und $ x_{k,3}=1$ ist geeignet, um die Wahl des Kaufs des Lastwagens im Jahr k und seiner Aufbewahrung für 3 Jahre zu beschreiben.

Einheitlicher Zeitraum

Der Planungshorizont $T$ ist in eine endliche Menge von unterteilt $m$ Augenblicke: $t_{k+1}= t_k + \Delta h_k$ wo $ K=0,1, \cdots, m-1$. Der Diskretisierungsschritt wird konstant und mit einer Dauer von 1 Jahr gewählt:$ \Delta h_k = \Delta h = 1$Jahr. Auf diese Weise,$T= \Delta t_1 + \cdots + \Delta t_m = m \cdot \Delta h $ und in unserer Fallstudie haben wir $m=17$ mit $t_0=0$.

Zeitliche Einschränkungen

Wir stellen vor $m=17$ Gleichungen und Variablen $A_k$ diese Spur in jedem Jahr, wie lange der LKW für die kommenden Jahre gehalten wird.

$ A_1 = \sum_{j=1}^{4} x_{1,j} \cdot t_j $

$ A_2 = A_1 - 1 + \sum_{j=1}^{4} x_{2,j} \cdot t_j $

$ \vdots $

$ A_m = A_{m-1} - 1 + \sum_{j=1}^{4} x_{m,j} \cdot t_j $

Wenn wir uns beispielsweise im ersten Jahr entscheiden, den LKW zu kaufen und drei Jahre lang zu behalten (2. Plan), ergibt sich Folgendes: $ A_1 = \sum_{j=1}^{4} x_{1,j} \cdot t_j = t_2 = 3$ weil $ x_{1,2}=1$ und $ x_{1,1}=x_{1,3}= x_{1,4}= 0 $. Um zu behaupten, dass jedes Jahr ein LKW in Betrieb ist, fügen wir weitere hinzu$m$ Einschränkungen: $ A_k \geq 1 \quad \forall k=1,\ldots,m $.

Schließlich die Einschränkung $ \sum_{k=1}^{17} \sum_{j=1}^{4} x_{k,j} \cdot t_j \leq 17 $ stellt sicher, dass alle Investitionsentscheidungen innerhalb des festgelegten Planungshorizonts getroffen werden $T$ und Cashflows mit einer Laufzeit spätestens bis zur Horizontplanung generieren $T=17$.

Um die inakzeptable Situation des Kaufs eines Lastwagens zu vermeiden, wenn der Plan des vorherigen Lastwagens noch nicht abgeschlossen ist, führen wir ein $m-1$ zusätzliche Einschränkungen wie folgt:

$\left\{ \begin{array}{l} \sum_{j=1}^{4} x_{1,j} \cdot t_j \leq (1 - \sum_{j=1}^{4} x_{2,j} ) \cdot M +1 \\ A_{1} -1 + \sum_{j=1}^{4} x_{2,j} \cdot t_j \leq (1 - \sum_{j=1}^{4} x_{3,j} ) \cdot M +1 \\ \vdots \\ A_{m-2} -1 + \sum_{j=1}^{4} x_{m-1,j} \cdot t_j \leq (1 - \sum_{j=1}^{4} x_{m,j} ) \cdot M +1 \\ \end{array} \right. $

wo $M > \max_j t_j $

Wann immer $ A_{k-1} = A_{k-2} -1 + \sum_{j=1}^{4} x_{k-1,j} \cdot t_j \geq 2 $ wir haben $(1 - \sum_{j=1}^{4} x_{k,j} ) \cdot M +1 = M+1 $, so erfordert es implizit, dass in der folgenden Zeit $ \sum_{j=1}^{4} x_{k,j} = 0 $ für jeden $j$. Nehmen wir andererseits zur Zeit an$k$ Wir kaufen einen LKW in Bezug auf $\tilde j$ Planen Sie früher als erwartet, das ist, wenn Sie sind $ A_{k-2} \geq 2$ dann $ A_{k-2} -1 + t_{\tilde j} \leq 1 $hält. Diese letzte Ungleichung ist nicht möglich, wenn$ A_{k-2} \geq 2$. Infolgedessen ist es nicht möglich, einen LKW vor dem Verkauf des vorherigen zu kaufen. Natürlich ist es möglich, einen LKW zu kaufen$k-1$ Zeitraum wenn $ A_{k-2} =1 $.