формулировка линейного программирования

Question

Я хочу сформулировать уравнения для этой проблемы. Я ранее просмотрел множество примеров, и я новичок в этом.

Предположим, у меня есть n фруктовых плантаций и количество только яблоневых плантаций.

Я хочу разместить s и (ns) насаждения на м х м сетке поля.

Целевая функция должна сводить к минимуму площадь поля сетки, на которой должны быть посажены n фруктов.

Кроме того, мне нужно контролировать (нс) плантации / точки сетки. Это означает, что для всех плантаций, кроме яблоневых, я могу разместить несколько плантаций в одной точке сетки.

Пожалуйста помоги.

Answer 1

Вам понадобится три набора переменных решения. Пусть двоичная переменная$a_{i,j}$ указать, размещена ли яблоня в точке сетки $(i,j)$. Пусть целочисленная неотрицательная переменная$b_{i,j}$ быть количеством плантаций, не выращивающих яблоки, $(i,j)$. Пусть двоичная переменная$f_{i,j}$ указать, размещена ли хотя бы одна фруктовая плантация $(i,j)$. Проблема в том, чтобы минимизировать$\sum_{i,j} f_{i,j}$с учетом линейных ограничений: \ 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 {для всех$i,j$} \ tag3 \\ b_ {i, j} & \ le (ns) f_ {i, j} && \ text {для всех $i,j$} \ tag4 \\ b_ {i, j} & \ le (ns) (1 - a_ {i, j}) && \ text {для всех $i,j$} \ tag5 \ end {align} Ограничение$(1)$ размещает все $s$яблоневые плантации. Ограничение$(2)$ размещает все $n-s$неяблочные плантации. Ограничение$(3)$ заставляет $a_{i,j}=1 \implies f_{i,j}=1$. Ограничение$(4)$ заставляет $b_{i,j}>0 \implies f_{i,j}=1$. Ограничение$(5)$ заставляет $a_{i,j}=1 \implies b_{i,j}=0$.