doğrusal programlama problem formülasyonu (genişletilmiş)
Bu soru, şunun değiştirilmiş bir sürümüdür https://math.stackexchange.com/questions/3803341/linear-programming-formulation. Aşağıdaki problem için karar değişkenlerini, amaç fonksiyonunu, kısıtlamaları ve olumsuz olmayan kısıtlamaları bilmek istiyorum.
Yine, toplam n tane meyve plantasyonum ve birkaç tane sadece elma plantasyonum var.
S ve (ns) plantasyonlarını m x m alan ızgarasına yerleştirmek istiyorum.
Amaç, n adet meyvenin ekileceği ızgara alanı alanını en aza indirmek olmalıdır.
Ayrıca, (ns) plantasyonları / ızgara noktalarını kontrol etmem gerekiyor. Bu, elma tarlaları dışındaki tüm tarlalar için, aynı ızgara noktasına birden fazla ekim yerleştirebileceğim anlamına gelir.
Yeni ek kısıtlamalar:
- Her bitki yalnızca bir kez dikilecektir. örneğin, aynı tesis iki farklı ızgara noktasında olamaz.
- Bu kez alan, daha önce olduğu gibi ızgara noktalarının sayısı değil, oluşturulan ızgaranın gerçek alanıdır.
- Son olarak, tarlaların birbirinden belirli bir mesafede, d uzakta olduğunu doğrulamalıyım.
Lütfen yardım et.
Yanıtlar
İlk madde işaretinin, değişkenlerin ikili veya tamsayı olması gerçeğiyle zaten yakalandığını düşünüyorum.
İkinci madde işareti için, uzunluk ve genişlik çarpımını en aza indirmek, aynı şekilde aşağıdaki gibi doğrusallaştırabileceğiniz günlüklerin toplamını en aza indirmek istiyorsunuz. İçin$k\in\{1,\dots,m\}$ikili karar değişkenlerine izin ver $\ell_k$ ve $w_k$ ızgaranın sırasıyla uzunluğunun veya genişliğinin olup olmadığını belirtin $k$. Kısıtlamalar şunlardır: \ begin {align} \ sum_k \ ell_k & = 1 \ tag1 \\ \ sum_k w_k & = 1 \ tag2 \\ f_ {i_1, j_1} + f_ {i_2, j_2} - 1 & \ le \ sum_ {k \ ge i_2-i_1} \ ell_k && \ text {için$i_1<i_2$ ve $(j_1,j_2)\in \{1,\dots,m\}^2$} \ tag3 \\ f_ {i_1, j_1} + f_ {i_2, j_2} - 1 & \ le \ sum_ {k \ ge j_2-j_1} w_k && \ text {için $j_1<j_2$ ve $(i_1,i_2)\in \{1,\dots,m\}^2$} \ tag4 \ end {hizala} Kısıtlamalar$(1)$ ve $(2)$sırasıyla bir uzunluk ve bir genişlik uygulayın. Kısıtlama$(3)$ zorlar $$(f_{i_1,j_1} \land f_{i_2,j_2}) \implies \bigvee_{k \ge i_2-i_1} \ell_k.$$ Buraya, $\land$ mantıksal AND operatörüdür (ancak ve ancak tüm bağımsız değişkenler doğruysa doğrudur) ve $\bigvee$mantıksal OR operatörüdür (ancak ve ancak en az bir bağımsız değişken doğruysa doğrudur). Yani, tarlalar yerleştirilirse$(i_1,j_1)$ ve $(i_2,j_2)$en azından uzunluk $i_2-i_1$. Kısıtlama$(4)$ genişlik için benzerdir.
Doğrusal olmayan amaç, alanı en aza indirmektir. $$\left(\sum_{k=1}^m k\ \ell_k\right)\left(\sum_{k=1}^m k\ w_k\right).$$ Çünkü $\log$ artan bir işlevdir, aynı şekilde küçültebilirsiniz $$\log\left[\left(\sum_{k=1}^m k\ \ell_k\right)\left(\sum_{k=1}^m k\ w_k\right)\right]=\log\left(\sum_{k=1}^m k\ \ell_k\right)+\log\left(\sum_{k=1}^m k\ w_k\right).$$ Kısıtlamalar nedeniyle $(1)$ ve $(2)$, bu doğrusal olmayan fonksiyon doğrusal fonksiyona eşittir $$\sum_{k=1}^m \log(k)\ell_k+\sum_{k=1}^m \log(k)w_k=\sum_{k=1}^m \log(k) \left(\ell_k + w_k\right).$$
Üçüncü madde için, çatışma kısıtlamaları getirebilirsiniz $a_{i_1,j_1} + a_{i_2,j_2} \le 1$ eğer arasındaki mesafe $(i_1,j_1)$ ve $(i_2,j_2)$ daha az $d$.