formulation de programmation linéaire

Question

Je veux formuler des équations pour ce problème. J'ai déjà regardé de nombreux exemples et je suis nouveau dans ce domaine.

Supposons que 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.

Veuillez aider.

Answer 1

Vous avez besoin de trois ensembles de variables de décision. Soit une variable binaire$a_{i,j}$ indiquer si une plantation de pommiers est placée au point de grille $(i,j)$. Soit une variable entière non négative$b_{i,j}$ être le nombre de plantations de fruits autres que de pommes $(i,j)$. Soit une variable binaire$f_{i,j}$ indiquer si au moins une plantation fruitière est située $(i,j)$. Le problème est de minimiser$\sum_{i,j} f_{i,j}$soumis à des contraintes linéaires: \ begin {align} \ sum_ {i, j} a_ {i, j} & = s \ tag1 \\ \ sum_ {i, j} b_ {i, j} & = ns \ tag2 \\ a_ {i, j} & \ le f_ {i, j} && \ text {pour tous$i,j$} \ tag3 \\ b_ {i, j} & \ le (ns) f_ {i, j} && \ text {pour tous $i,j$} \ tag4 \\ b_ {i, j} & \ le (ns) (1 - a_ {i, j}) && \ text {pour tous $i,j$} \ tag5 \ end {align} Contrainte$(1)$ place tout $s$plantations de pommes. Contrainte$(2)$ place tout $n-s$plantations autres que de pommiers. Contrainte$(3)$ applique $a_{i,j}=1 \implies f_{i,j}=1$. Contrainte$(4)$ applique $b_{i,j}>0 \implies f_{i,j}=1$. Contrainte$(5)$ applique $a_{i,j}=1 \implies b_{i,j}=0$.