formulação de programação linear

Question

Quero formular equações para este problema. Já observei muitos exemplos e sou novo nisso.

Suponha que eu tenha um total de n plantações de frutas e um número s de 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 os (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.

Por favor ajude.

Answer 1

Você precisa de três conjuntos de variáveis ​​de decisão. Deixe a variável binária$a_{i,j}$ indicar se uma plantação de maçã é colocada no ponto da grade $(i,j)$. Deixe uma variável inteira não negativa$b_{i,j}$ ser o número de plantações de frutas que não sejam de maçã colocadas em $(i,j)$. Deixe a variável binária$f_{i,j}$ indicar se pelo menos uma plantação de frutas é colocada em $(i,j)$. O problema é minimizar$\sum_{i,j} f_{i,j}$sujeito a restrições lineares: \ 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 {para todos$i,j$} \ tag3 \\ b_ {i, j} & \ le (ns) f_ {i, j} && \ text {para todos $i,j$} \ tag4 \\ b_ {i, j} & \ le (ns) (1 - a_ {i, j}) && \ text {para todos $i,j$} \ Tag5 \ final {align} restrição$(1)$ coloca tudo $s$plantações de maçã. Limitação$(2)$ coloca tudo $n-s$plantações sem maçã. Limitação$(3)$ força $a_{i,j}=1 \implies f_{i,j}=1$. Limitação$(4)$ força $b_{i,j}>0 \implies f_{i,j}=1$. Limitação$(5)$ força $a_{i,j}=1 \implies b_{i,j}=0$.