lập trình tuyến tính

Question

Tôi muốn lập phương trình cho vấn đề này. Trước đây tôi đã xem xét nhiều ví dụ và tôi mới làm quen với điều này.

Giả sử tôi có n tổng số đồn điền trồng cây ăn quả và s số đồn điền trồng táo.

Tôi muốn đặt các đồn điền s và (ns) trên một lưới ruộng dài m x m.

Chức năng mục tiêu phải là tối thiểu hóa diện tích lưới ruộng nơi trồng n trái.

Ngoài ra, tôi cần kiểm soát (ns) đồn điền / điểm lưới. Điều đó có nghĩa là đối với tất cả các đồn điền ngoại trừ đồn điền táo, tôi có thể đặt nhiều đồn điền trên cùng một điểm lưới.

Xin vui lòng giúp đỡ.

Answer 1

Bạn cần ba bộ biến quyết định. Để biến nhị phân$a_{i,j}$ cho biết liệu một đồn điền táo có được đặt ở điểm lưới không $(i,j)$. Cho biến số nguyên không âm$b_{i,j}$ là số đồn điền không phải táo được đặt tại $(i,j)$. Để biến nhị phân$f_{i,j}$ cho biết liệu ít nhất một đồn điền ăn quả được đặt tại $(i,j)$. Vấn đề là giảm thiểu$\sum_{i,j} f_{i,j}$tuân theo các ràng buộc tuyến tính: \ 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 {cho tất cả$i,j$} \ tag3 \\ b_ {i, j} & \ le (ns) f_ {i, j} && \ text {cho tất cả $i,j$} \ tag4 \\ b_ {i, j} & \ le (ns) (1 - a_ {i, j}) && \ text {cho tất cả $i,j$Ràng buộc } \ tag5 \ end {align}$(1)$ đặt tất cả $s$đồn điền táo. Hạn chế$(2)$ đặt tất cả $n-s$đồn điền phi táo. Hạn chế$(3)$ thực thi $a_{i,j}=1 \implies f_{i,j}=1$. Hạn chế$(4)$ thực thi $b_{i,j}>0 \implies f_{i,j}=1$. Hạn chế$(5)$ thực thi $a_{i,j}=1 \implies b_{i,j}=0$.