formulation de problème de programmation linéaire (étendue)

Question

Cette question est une version modifiée de https://math.stackexchange.com/questions/3803341/linear-programming-formulation. Je veux connaître les variables de décision, la fonction objective, les contraintes et les contraintes de non-négativité pour le problème suivant.

Encore une fois, j'ai n plantations de fruits au total et le nombre de plantations de pommes uniquement.

Je veux placer les plantations s et (ns) sur une grille m par m de champ.

La fonction objective doit être de minimiser la zone du champ quadrillé où n fruits doivent être plantés.

En outre, je dois contrôler les plantations / points de grille (ns). Cela signifie que pour toutes les plantations à l'exception des plantations de pommiers, je pourrais placer plusieurs plantations sur le même point de grille.

Nouvelles contraintes supplémentaires:

• Chaque plante ne doit être plantée qu'une seule fois. Par exemple, la même plante ne peut pas être sur deux points de grille différents.
• Cette fois, la zone est la zone réelle de la grille créée, et non le nombre de points de grille comme auparavant.
• Enfin, je dois vérifier que les plantations sont à une certaine distance les unes des autres.

Veuillez aider.

Answer 1

Je pense que la première puce est déjà capturée par le fait que les variables sont binaires ou entières.

Pour la deuxième puce, vous voulez minimiser le produit de la longueur et de la largeur, minimiser de manière équivalente la somme des journaux, que vous pouvez linéariser comme suit. Pour$k\in\{1,\dots,m\}$, laissez les variables de décision binaires $\ell_k$ et $w_k$ indiquer si la longueur ou la largeur, respectivement, de la grille est $k$. Les contraintes sont: \ 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 {pour$i_1<i_2$ et $(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 {pour $j_1<j_2$ et $(i_1,i_2)\in \{1,\dots,m\}^2$} \ tag4 \ end {align} Contraintes$(1)$ et $(2)$appliquer respectivement une longueur et une largeur. Contrainte$(3)$ applique $$(f_{i_1,j_1} \land f_{i_2,j_2}) \implies \bigvee_{k \ge i_2-i_1} \ell_k.$$ Ici, $\land$ est l'opérateur logique AND (vrai si et seulement si tous les arguments sont vrais), et $\bigvee$est l'opérateur logique OR (vrai si et seulement si au moins un argument est vrai). En mots, si les plantations sont placées à$(i_1,j_1)$ et $(i_2,j_2)$, alors la longueur est au moins $i_2-i_1$. Contrainte$(4)$ est similaire pour la largeur.

L'objectif non linéaire est de minimiser la zone $$\left(\sum_{k=1}^m k\ \ell_k\right)\left(\sum_{k=1}^m k\ w_k\right).$$ Car $\log$ est une fonction croissante, vous pouvez minimiser de manière équivalente $$\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).$$ En raison de contraintes $(1)$ et $(2)$, cette fonction non linéaire est égale à la fonction linéaire $$\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).$$

Pour la troisième puce, vous pouvez introduire des contraintes de conflit $a_{i_1,j_1} + a_{i_2,j_2} \le 1$ si la distance entre $(i_1,j_1)$ et $(i_2,j_2)$ est inférieur à $d$.