sformułowanie programowania liniowego

Question

Chcę sformułować równania dla tego problemu. Wcześniej obejrzałem wiele przykładów i jestem w tym nowy.

Załóżmy, że mam łącznie n plantacji owoców i liczbę samych plantacji jabłek.

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

Funkcją celu powinno być zminimalizowanie obszaru pola siatki, na którym ma być sadzonych n owoców.

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

Proszę pomóż.

Answer 1

Potrzebujesz trzech zestawów zmiennych decyzyjnych. Niech zmienna binarna$a_{i,j}$ wskazać, czy plantacja jabłek jest umieszczona w punkcie siatki $(i,j)$. Niech nieujemna zmienna całkowita$b_{i,j}$ być liczbą plantacji owoców innych niż jabłka umieszczonych w $(i,j)$. Niech zmienna binarna$f_{i,j}$ wskazać, czy przynajmniej jedna plantacja owoców znajduje się na $(i,j)$. Problem polega na tym, aby zminimalizować$\sum_{i,j} f_{i,j}$podlega ograniczeniom liniowym: \ 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 {dla wszystkich$i,j$} \ tag3 \\ b_ {i, j} & \ le (ns) f_ {i, j} && \ text {dla wszystkich $i,j$} \ tag4 \\ b_ {i, j} & \ le (ns) (1 - a_ {i, j}) && \ text {dla wszystkich $i,j$} \ tag5 \ end {align} Ograniczenie$(1)$ umieszcza wszystko $s$plantacje jabłek. Przymus$(2)$ umieszcza wszystko $n-s$plantacje inne niż jabłka. Przymus$(3)$ wymusza $a_{i,j}=1 \implies f_{i,j}=1$. Przymus$(4)$ wymusza $b_{i,j}>0 \implies f_{i,j}=1$. Przymus$(5)$ wymusza $a_{i,j}=1 \implies b_{i,j}=0$.