विभाजन परिवहन कार्य ("ट्रेलरों के साथ")

आवश्यक ज्ञान: रैखिक प्रोग्रामिंग विधियों, परिवहन समस्या को हल करने के तरीके (विशेष रूप से संभावित विधि) के साथ परिचित।

एक साल पहले, तीसरे पर पाठ्यक्रम "ऑप्टिमाइज़ेशन मेथड्स" पर प्रयोगशाला के काम में से एक के रूप में मुझे परिवहन समस्या के समाधान को लागू करने के लिए कहा गया था, लेकिन एक छोटी सी स्थिति के साथ: परिवहन बैचों में होता है। इसका मतलब यह है कि अब, क्लासिक उत्पादन के विपरीत, माल की खेप का परिवहन (जैसे 10 टुकड़े) का भुगतान किया जाता है, और यहां तक ​​कि अगर आपको 11 टुकड़ों को परिवहन करने की आवश्यकता होती है, तो आप दो लॉट के लिए भुगतान करेंगे (11 टुकड़े एक ट्रेलर में फिट नहीं होंगे)। यह एक मामूली जोड़ प्रतीत होता है, लेकिन अब इस समस्या को कैसे हल किया जाए, और कम से कम इसे कैसे औपचारिक रूप दिया जाए? एप्लाइड गणित विभाग के एक छात्र के रूप में, मुझे इस तथ्य के लिए इस्तेमाल नहीं किया गया था कि महान google.ru को कुछ भी पता नहीं था, लेकिन जब मेरे बड़े भाई, अंग्रेजी बोलने वाले Google, और न ही अनुकूलन सिद्धांत पर पुस्तकों के अंधेरे का मुझे कोई जवाब नहीं मिला, तो मुझे क्या आश्चर्य हुआ? यह सवाल।

मैं तुरंत कहना चाहता हूं - मैं अपने एल्गोरिथ्म के साथ फील्ड्स पुरस्कार का उपयोग करने का नाटक नहीं करता हूं। मैं कुछ भी अलौकिक नहीं प्रस्तावित करता हूं, लेकिन जो लोग इस तरह की समस्या को हल करना शुरू कर रहे हैं, मैं उनकी थोड़ी मदद कर सकता हूं।
C , पेमेंट मैट्रिक्स हो, a , कार्गो स्टॉक का वेक्टर है, b कार्गो की मांग का वेक्टर है, k एक बैच में माल की संख्या है। हम निम्नलिखित औपचारिकता पर विचार करेंगे:

जहाँ X परिवहन मैट्रिक्स है, अर्थात अनुकूलित पैरामीटर, और छत - निकटतम पूर्णांक तक गोलाई।
इसके अलावा, हम विचार करते हैं:

सबसे पहले, हम F2-> मिनट के साथ शास्त्रीय परिवहन समस्या को हल करते हैं। F2 का प्राप्त मूल्य स्वीकार्य मानों के सेट पर F1 के लिए कम बाध्य है। F2_save का मूल्य याद रखें: = F2। हम परिणामी समाधान X के साथ F1 का मान पाते हैं और इसे F1_save = F1 को याद करते हैं। यदि F1_save == छत (F2_save) है, तो X वह समाधान है जिसे आप ढूंढ रहे हैं, अन्यथा आगे जाएं।
एफ को केवल एक्स के आधार घटकों को कम करके निकटतम कई k मानों तक कम किया जा सकता है ; इसलिए, हम अतिरिक्त प्रतिबंधों के साथ समस्याओं के समाधान के लिए एक शाखा (बाउंड विधि) का निर्माण करेंगे। पेड़ की चोटी पहले से प्राप्त समाधान है। पेड़ के प्रत्येक अगले स्तर का निर्माण इस प्रकार किया गया है: प्रत्येक आधार घटक (xij) के लिए कुछ गैर-एकाधिक k मान (z) के बराबर, हम शास्त्रीय परिवहन समस्या को हल करते हैं F2-> मिनट अतिरिक्त बाधा xij = [z / k] k ([x] के साथ X का पूर्णांक भाग है) (PS देखें)। यदि प्राप्त समाधान F1 <F1_save के लिए है, तो F1_save: = F1। यदि प्राप्त समाधान छत (F2)> = F1_save के लिए है, तो हम इस शाखा को जारी नहीं रखते हैं। यदि F1 == छत (F2_save) है, तो परिणामस्वरूप X वांछित समाधान है, अन्यथा आगे बढ़ें। इस प्रकार, हम एक निर्णय पेड़ प्राप्त करते हैं, जिसकी प्रत्येक शाखा समाप्त हो जाती है यदि इस शाखा की शीट पर छत (F2) = F1_save, या यदि आधार से सभी घटक कश्मीर के गुणक हैं, या यदि समस्या का समाधान बिल्कुल नहीं था। F1_save पेड़ के निर्माण के बाद प्राप्त की गई योजना इष्टतम है।

पुनश्च समस्या को हल करने के लिए एक बाधा जोड़ना आवश्यक नहीं है। उदाहरण के लिए, आप सभी संभव F1-घटते चक्रों के माध्यम से जा सकते हैं और उनमें से एक को चुन सकते हैं। या दोहरी सिंप्लेक्स विधि के तरीकों का उपयोग करें।

उदाहरण
एल्गोरिथ्म पर एक बहुत ही सरल उदाहरण में विचार करें। Let k = 3, C = {{2,2}, {4,5}}, a = {2,3}, b = {2,3}। तो पेड़ के शीर्ष उद्देश्य समारोह F2 के साथ इस तरह के एक परिवहन समस्या का समाधान है:

0) X = {{0,2}, {2,1}}, F2 (X) ~ = 5.67, F1 (X) = 2 + 4 + 5 = 11।
F2_save: = 5.67, F1_save: = 11
क्योंकि छत (5.67) <11 हम आगे बढ़ते हैं - हम पेड़ के निम्नलिखित स्तर का निर्माण करते हैं:
१.१) नोड १ में हल होने वाली समस्या में x12 == ० को जोड़ें और इसे फिर से हल करें।
X = {{2.0}, {0.3}}, F2 (X) ~ = 6.35, F1 (X) = 2 + 5 = 7।
क्योंकि F1 <F1_save (7 <11), फिर F1_save: = 7
क्योंकि Ceil (F2)> = F1_save (7> = 7), फिर इस शाखा को जारी न रखें
क्योंकि एफ 1> छत (F2_save) हम आगे बढ़ते हैं (शायद एक बेहतर समाधान है), शाखा जारी नहीं है, लेकिन टियर अभी तक समाप्त नहीं हुआ है।
1.2) नोड 0 में हल की जा रही समस्या में x21 == 0 की स्थिति जोड़ें और इसे फिर से हल करें।
X = {{2.0}, {0.3}}, F2 (X) ~ = 6.35, F1 (X) = 2 + 5 = 7।
क्योंकि F1 == F1_save (7 == 7), फिर F1_save नहीं बदलता है
क्योंकि Ceil (F2)> = F1_save (7> = 7), फिर इस शाखा को जारी न रखें
क्योंकि एफ 1> छत (F2_save) हम आगे बढ़ते हैं (शायद एक बेहतर समाधान है), शाखा जारी नहीं है, लेकिन टियर अभी तक समाप्त नहीं हुआ है।
1.3) नोड 0 में हल की जा रही समस्या में x22 == 0 की स्थिति जोड़ें और इसे फिर से हल करें। ऐसी समस्या का कोई समाधान नहीं है => और हम इस शाखा को जारी नहीं रखते हैं।

अधिक बुनियादी घटक नहीं बचे हैं (टियर समाप्त हो गया है) और शाखाओं को जारी रखने की कोई आवश्यकता नहीं है (व्यर्थ, हमें एक बेहतर समाधान नहीं मिलेगा), फिर पेड़ बनाया गया है। F1_save == 7 हमारी न्यूनतम लागत है। उनके अनुरूप एक योजना (वह उत्तर है) X = {{2,0}, {0,3}}