Formulação do problema de programação linear (estendido)
Esta pergunta é uma versão modificada de https://math.stackexchange.com/questions/3803341/linear-programming-formulation. Eu quero saber as variáveis de decisão, função objetivo, restrições e restrições de não negatividade para o seguinte problema.
Novamente, eu tenho um total de n plantações de frutas e um número de apenas plantações de maçãs.
Quero colocar plantações s e (ns) em uma grade de campo m por m.
A função objetivo deve ser minimizar a área do campo de grade onde n frutos serão plantados.
Além disso, preciso controlar as (ns) plantações / pontos de grade. Isso significa que, para todas as plantações, exceto as de maçã, posso colocar várias plantações no mesmo ponto de grade.
Novas restrições adicionais:
- Cada planta deve ser plantada apenas uma vez. por exemplo, a mesma planta não pode estar em dois pontos de grade diferentes.
- Desta vez, a área é a área real da grade criada, não o número de pontos da grade como antes.
- Por último, tenho que verificar se as plantações estão a uma certa distância, d de distância umas das outras.
Por favor ajude.
Respostas
Acho que o primeiro marcador já foi capturado pelo fato de as variáveis serem binárias ou inteiras.
Para o segundo marcador, você deseja minimizar o produto de comprimento e largura, de forma equivalente, minimizar a soma de toras, que você pode linearizar da seguinte maneira. Para$k\in\{1,\dots,m\}$, deixe as variáveis de decisão binárias $\ell_k$ e $w_k$ indicam se o comprimento ou largura, respectivamente, da grade é $k$. As restrições são: \ 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 {para$i_1<i_2$ e $(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 {para $j_1<j_2$ e $(i_1,i_2)\in \{1,\dots,m\}^2$} \ tag4 \ end {align} Restrições$(1)$ e $(2)$impõem um comprimento e uma largura, respectivamente. Restrição$(3)$ força $$(f_{i_1,j_1} \land f_{i_2,j_2}) \implies \bigvee_{k \ge i_2-i_1} \ell_k.$$ Aqui, $\land$ é o operador lógico AND (verdadeiro se e somente se todos os argumentos forem verdadeiros), e $\bigvee$é o operador lógico OR (verdadeiro se e somente se pelo menos um argumento for verdadeiro). Em palavras, se as plantações são colocadas em$(i_1,j_1)$ e $(i_2,j_2)$, então o comprimento é de pelo menos $i_2-i_1$. Restrição$(4)$ é semelhante para a largura.
O objetivo não linear é minimizar a área $$\left(\sum_{k=1}^m k\ \ell_k\right)\left(\sum_{k=1}^m k\ w_k\right).$$ Porque $\log$ é uma função crescente, você pode minimizar de forma equivalente $$\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).$$ Por causa de restrições $(1)$ e $(2)$, esta função não linear é igual à função linear $$\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).$$
Para o terceiro item, você pode introduzir restrições de conflito $a_{i_1,j_1} + a_{i_2,j_2} \le 1$ se a distância entre $(i_1,j_1)$ e $(i_2,j_2)$ é menos do que $d$.