Formulierung eines linearen Programmierproblems (erweitert)

Question

Diese Frage ist eine modifizierte Version von https://math.stackexchange.com/questions/3803341/linear-programming-formulation. Ich möchte die Entscheidungsvariablen, die Zielfunktion, die Einschränkungen und die Nicht-Negativitätsbeschränkungen für das folgende Problem kennen.

Wieder habe ich insgesamt n Obstplantagen und s Anzahl von nur Apfelplantagen.

Ich möchte s- und (ns-) Plantagen auf einem Feldraster von m mal m platzieren.

Die Zielfunktion sollte darin bestehen, den Bereich des Gitterfeldes zu minimieren, in dem n Früchte gepflanzt werden sollen.

Außerdem muss ich die (ns) Plantagen / Gitterpunkte steuern. Das bedeutet, dass ich für alle Plantagen außer den Apfelplantagen mehrere Plantagen auf demselben Gitterpunkt platzieren kann.

Neue zusätzliche Einschränkungen:

• Jede Pflanze darf nur einmal gepflanzt werden. Beispielsweise kann sich dieselbe Anlage nicht auf zwei verschiedenen Gitterpunkten befinden.
• Diesmal ist die Fläche die tatsächliche Fläche des erstellten Gitters, nicht die Anzahl der Gitterpunkte wie zuvor.
• Zuletzt muss ich feststellen, dass die Plantagen einen gewissen Abstand voneinander haben.

Bitte helfen Sie.

Answer 1

Ich denke, die erste Kugel wird bereits durch die Tatsache erfasst, dass die Variablen binär oder ganzzahlig sind.

Für das zweite Aufzählungszeichen möchten Sie das Produkt aus Länge und Breite minimieren und die Summe der Protokolle entsprechend minimieren, die Sie wie folgt linearisieren können. Zum$k\in\{1,\dots,m\}$Lassen Sie binäre Entscheidungsvariablen $\ell_k$ und $w_k$ Geben Sie an, ob die Länge oder Breite des Gitters gleich ist $k$. Die Einschränkungen sind: \ begin {align} \ sum_k \ ell_k & = 1 \ tag1 \\ \ sum_k w_k & = 1 \ tag2 \\ f_ {i_1, j_1} + f_ {i_2, j_2} - 1 & \ le \ sum_ {k \ ge i_2-i_1} \ ell_k && \ text {for$i_1<i_2$ und $(j_1,j_2)\in \{1,\dots,m\}^2$} \ tag3 \\ f_ {i_1, j_1} + f_ {i_2, j_2} - 1 & \ le \ sum_ {k \ ge j_2-j_1} w_k && \ text {for $j_1<j_2$ und $(i_1,i_2)\in \{1,\dots,m\}^2$} \ tag4 \ end {align} Constraints$(1)$ und $(2)$Erzwingen Sie eine Länge bzw. eine Breite. Zwang$(3)$ erzwingt $$(f_{i_1,j_1} \land f_{i_2,j_2}) \implies \bigvee_{k \ge i_2-i_1} \ell_k.$$ Hier, $\land$ ist der logische UND-Operator (wahr, wenn und nur wenn alle Argumente wahr sind) und $\bigvee$ist der logische ODER-Operator (genau dann wahr, wenn mindestens ein Argument wahr ist). Mit Worten, wenn Plantagen angelegt werden$(i_1,j_1)$ und $(i_2,j_2)$dann ist die Länge mindestens $i_2-i_1$. Zwang$(4)$ ist ähnlich für die Breite.

Das nichtlineare Ziel besteht darin, die Fläche zu minimieren $$\left(\sum_{k=1}^m k\ \ell_k\right)\left(\sum_{k=1}^m k\ w_k\right).$$ weil $\log$ ist eine zunehmende Funktion, die Sie äquivalent minimieren können $$\log\left[\left(\sum_{k=1}^m k\ \ell_k\right)\left(\sum_{k=1}^m k\ w_k\right)\right]=\log\left(\sum_{k=1}^m k\ \ell_k\right)+\log\left(\sum_{k=1}^m k\ w_k\right).$$ Wegen Einschränkungen $(1)$ und $(2)$ist diese nichtlineare Funktion gleich der linearen Funktion $$\sum_{k=1}^m \log(k)\ell_k+\sum_{k=1}^m \log(k)w_k=\sum_{k=1}^m \log(k) \left(\ell_k + w_k\right).$$

Für das dritte Aufzählungszeichen können Sie Konfliktbeschränkungen einführen $a_{i_1,j_1} + a_{i_2,j_2} \le 1$ wenn der Abstand zwischen $(i_1,j_1)$ und $(i_2,j_2)$ ist weniger als $d$.