sformułowanie problemu programowania liniowego (rozszerzone)

Question

To pytanie jest zmodyfikowaną wersją https://math.stackexchange.com/questions/3803341/linear-programming-formulation. Chcę poznać zmienne decyzyjne, funkcję celu, ograniczenia i ograniczenia nieujemności dla następującego problemu.

Znów mam n ogółem plantacji owoców i liczbę tylko jabłek.

Chcę umieścić plantacje s i (ns) na siatce pola m na m.

Funkcja celu powinna polegać na zminimalizowaniu obszaru pola siatki, na którym ma być sadzonych n owoców.

Muszę również kontrolować (ns) plantacje / punkty siatki. Oznacza to, że dla wszystkich plantacji oprócz plantacji jabłek mógłbym umieścić wiele plantacji w tym samym punkcie siatki.

Nowe dodatkowe ograniczenia:

• Każdą roślinę należy sadzić tylko raz. np. ta sama roślina nie może znajdować się w dwóch różnych punktach siatki.
• Tym razem obszar jest faktycznym obszarem utworzonej siatki, a nie liczbą punktów siatki, jak poprzednio.
• Na koniec muszę się upewnić, że te plantacje znajdują się w pewnej odległości od siebie.

Proszę pomóż.

Answer 1

Myślę, że pierwszy punktor jest już uchwycony przez fakt, że zmienne są binarne lub całkowite.

W przypadku drugiego punktu należy zminimalizować iloczyn długości i szerokości, równoważnie zminimalizować sumę dzienników, które można zlinearyzować w następujący sposób. Dla$k\in\{1,\dots,m\}$niech binarne zmienne decyzyjne $\ell_k$ i $w_k$ wskazują, czy odpowiednio długość lub szerokość siatki to $k$. Ograniczenia to: \ 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 {dla$i_1<i_2$ i $(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$ i $(i_1,i_2)\in \{1,\dots,m\}^2$} \ tag4 \ end {align} Ograniczenia$(1)$ i $(2)$wymuszaj odpowiednio jedną długość i jedną szerokość. Przymus$(3)$ wymusza $$(f_{i_1,j_1} \land f_{i_2,j_2}) \implies \bigvee_{k \ge i_2-i_1} \ell_k.$$ Tutaj, $\land$ jest operatorem logicznym AND (prawda wtedy i tylko wtedy, gdy wszystkie argumenty są prawdziwe) i $\bigvee$jest operatorem logicznym OR (prawda wtedy i tylko wtedy, gdy przynajmniej jeden argument jest prawdziwy). Słowem, jeśli plantacje znajdują się na$(i_1,j_1)$ i $(i_2,j_2)$, to co najmniej długość $i_2-i_1$. Przymus$(4)$ jest podobna do szerokości.

Nieliniowym celem jest zminimalizowanie obszaru $$\left(\sum_{k=1}^m k\ \ell_k\right)\left(\sum_{k=1}^m k\ w_k\right).$$ Dlatego $\log$ jest funkcją rosnącą, którą można odpowiednio zminimalizować $$\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).$$ Z powodu ograniczeń $(1)$ i $(2)$, ta nieliniowa funkcja jest równa funkcji liniowej $$\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).$$

W przypadku trzeciego punktu można wprowadzić ograniczenia konfliktu $a_{i_1,j_1} + a_{i_2,j_2} \le 1$ jeśli odległość między $(i_1,j_1)$ i $(i_2,j_2)$ jest mniej niż $d$.