रैखिक प्रोग्रामिंग समस्या निर्माण (विस्तारित)
यह प्रश्न संशोधित संस्करण है https://math.stackexchange.com/questions/3803341/linear-programming-formulation। मैं निम्नलिखित समस्या के लिए निर्णय चर, उद्देश्य समारोह, बाधाओं और गैर-नकारात्मकता बाधाओं को जानना चाहता हूं।
फिर, मेरे पास कुल फलों के बागान हैं और सिर्फ सेब के बागानों की संख्या है।
मैं एक मीटर पर मी (s) और (ns) के पौधे लगाना चाहता हूं।
उद्देश्य फ़ंक्शन को ग्रिड फ़ील्ड के क्षेत्र को कम करना चाहिए जहां एन फलों को लगाया जाना है।
इसके अलावा, मुझे (ns) वृक्षारोपण / ग्रिड बिंदुओं को नियंत्रित करने की आवश्यकता है। सेब के बागानों को छोड़कर सभी वृक्षारोपण के लिए इसका मतलब है, मैं एक ही ग्रिड बिंदु पर कई वृक्षारोपण लगा सकता हूं।
नई अतिरिक्त बाधाएं:
- प्रत्येक पौधा केवल एक बार लगाया जाना है। उदाहरण के लिए एक ही पौधा दो अलग-अलग ग्रिड बिंदुओं पर नहीं हो सकता है।
- इस बार क्षेत्र निर्मित ग्रिड का वास्तविक क्षेत्र है, पहले की तरह ग्रिड बिंदुओं की संख्या नहीं।
- अंत में, मुझे यह पता लगाना होगा कि रोपण एक निश्चित दूरी पर हैं, एक दूसरे से दूर हैं।
कृपया मदद करे।
जवाब
मुझे लगता है कि पहली गोली इस तथ्य से पहले ही पकड़ ली गई है कि चर द्विआधारी या पूर्णांक हैं।
दूसरी गोली के लिए, आप लंबाई और चौड़ाई के उत्पाद को कम से कम करना चाहते हैं, समान रूप से लॉग के योग को कम कर सकते हैं, जिसे आप निम्नानुसार रैखिक कर सकते हैं। के लिये$k\in\{1,\dots,m\}$, बाइनरी निर्णय चर दें $\ell_k$ तथा $w_k$ इंगित करें कि ग्रिड की लंबाई या चौड़ाई क्रमशः है या नहीं $k$। बाधाएँ हैं: \ start {align} \ sum_k \ ell_k & = 1 \ tag1 \\ \ sum_k w_k & = 1 \ tag2 \\ f_ {i_1, j_1} + f_ {{_2, j_2} - 1 & \ _ \ _ \ _ {k \ ge i_2-i_1} \ ell_k && \ text {के लिए$i_1<i_2$ तथा $(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 {के लिए $j_1<j_2$ तथा $(i_1,i_2)\in \{1,\dots,m\}^2$} \ tag4 \ end {संरेखित करें} बाधाएं$(1)$ तथा $(2)$क्रमशः एक लंबाई और एक चौड़ाई लागू करें। बाधा$(3)$ लागू करता है $$(f_{i_1,j_1} \land f_{i_2,j_2}) \implies \bigvee_{k \ge i_2-i_1} \ell_k.$$ यहाँ, $\land$ तार्किक और ऑपरेटर है (यदि सभी तर्क सत्य हैं, तो केवल सच है), और $\bigvee$तार्किक या ऑपरेटर (सही है और केवल अगर कम से कम एक तर्क सत्य है)। शब्दों में, यदि वृक्षारोपण लगाए जाते हैं$(i_1,j_1)$ तथा $(i_2,j_2)$, तो लंबाई कम से कम है $i_2-i_1$। बाधा$(4)$ चौड़ाई के लिए समान है।
क्षेत्र को कम करने के लिए nonlinear उद्देश्य है $$\left(\sum_{k=1}^m k\ \ell_k\right)\left(\sum_{k=1}^m k\ w_k\right).$$ चूंकि $\log$ एक बढ़ता हुआ कार्य है, आप इसे न्यूनतम कर सकते हैं $$\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).$$ अड़चन के कारण $(1)$ तथा $(2)$, यह nonlinear फ़ंक्शन रैखिक फ़ंक्शन के बराबर है $$\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).$$
तीसरी गोली के लिए, आप संघर्ष बाधाओं का परिचय दे सकते हैं $a_{i_1,j_1} + a_{i_2,j_2} \le 1$ अगर बीच की दूरी $(i_1,j_1)$ तथा $(i_2,j_2)$ से कम है $d$।