मैंने विकिपीडिया article पर पढ़ा है, लेकिन ऐसा लगता है कि यह मेरी समझ से परे है। यह कहता है कि यह अनुकूलन के लिए है, लेकिन चीजों को अनुकूलित करने के लिए यह किसी अन्य विधि से अलग कैसे है?रैखिक प्रोग्रामिंग क्या है?
एक उत्तर जो मुझे रैखिक प्रोग्रामिंग के लिए प्रस्तुत करता है, इसलिए मैं कुछ कम शुरुआती-सुलभ सामग्री में डाइविंग शुरू कर सकता हूं। रैखिक प्रोग्रामिंग के
अब तक के जवाबों ने रैखिक प्रोग्रामिंग की एक बीजगणितीय परिभाषा और एक परिचालन परिभाषा दी है। लेकिन एक ज्यामितीय परिभाषा भी है। एक पॉलीटॉप बहुभुज (दो आयामों में) या पॉलीहेड्रोन (तीन आयामों में) का एक गैर-आयामी सामान्यीकरण है। एक उत्तल पॉलीटॉप एक पॉलीटॉप है जो एक उत्तल सेट भी है। परिभाषा के अनुसार, रैखिक प्रोग्रामिंग एक अनुकूलन समस्या है जिसमें आप उत्तल पॉलीटॉप पर रैखिक फ़ंक्शन को अधिकतम या कम करना चाहते हैं।
उदाहरण के लिए: मान लें कि आप लाल रेत और नीली रेत के कुछ संयोजन खरीदना चाहते हैं। मान लीजिए:
यदि आप विमान में एक तस्वीर खींचते हैं कि आप इन बाधाओं के साथ कितना खरीद सकते हैं, तो यह एक उत्तल पेंटागन है। फिर, जो कुछ भी आप अनुकूलित करना चाहते हैं (कहें, रेत में सोने की कुल मात्रा), आप जानते हैं कि एक इष्टतम (आवश्यक रूप से केवल इष्टतम नहीं) पॉलीटॉप के शीर्षकों में से एक पर है। वास्तव में, एक बहुत मजबूत परिणाम है: यहां तक कि उच्च आयामों में, ऐसी किसी भी रैखिक प्रोग्रामिंग समस्या को बहुपद समय में, बाधाओं की संख्या में, या पॉलीटॉप के रखरखाव पक्षों में हल किया जा सकता है। ध्यान दें कि हर बाधा एक तरफ से मेल नहीं खाती है। यदि बाधा एक समानता है, तो यह पॉलीटॉप के आयाम को कम कर सकती है। या यदि बाधा एक असमानता है, तो यह एक पक्ष नहीं बना सकता है अगर यह पहले से ही अन्य सभी बाधाओं से निहित है।
रैखिक प्रोग्रामिंग हैं जो बहुत व्यावहारिक अनुकूलन समस्याएं हैं। पहले उदाहरणों में से एक "आहार समस्या" था: भोजन के एक समूह के एक मेनू को देखते हुए, सबसे सस्ता संभव संतुलित भोजन क्या है? यह एक रैखिक प्रोग्रामिंग समस्या है क्योंकि लागत रैखिक है, और क्योंकि सभी बाधाओं (विटामिन, कैलोरी, धारणा है कि आप एक नकारात्मक मात्रा में भोजन नहीं खरीद सकते हैं, आदि) रैखिक हैं।
लेकिन, रैखिक प्रोग्रामिंग सैद्धांतिक कारण के लिए और भी महत्वपूर्ण है। यह अनुकूलन के लिए या किसी अन्य उद्देश्य के लिए सबसे शक्तिशाली बहुपद-समय एल्गोरिदम में से एक है। इस प्रकार, यह अन्य अनुकूलन समस्याओं को हल करने के लिए एक विकल्प के रूप में और वास्तव में उन्हें हल करने के लिए एक सबराउटिन के रूप में बहुत महत्वपूर्ण है।
हां, दो सामान्यीकरण उत्तल प्रोग्रामिंग और पूर्णांक प्रोग्रामिंग हैं। कुछ योग्यता के साथ, उत्तल प्रोग्रामिंग केवल साथ ही रैखिक प्रोग्रामिंग भी काम कर सकता है, बशर्ते कि उद्देश्य (अधिकतम करने की बात) रैखिक हो। यह पता चला है कि उत्परिवर्तन, फ्लैट पक्ष नहीं, मुख्य कारण यह है कि रैखिक प्रोग्रामिंग में एक अच्छा एल्गोरिदम है।
दूसरी तरफ इंटीजर प्रोग्रामिंग आमतौर पर कठिन होती है। उदाहरण के लिए, उदाहरण की समस्या में मान लीजिए कि आपको थोक के बजाय निश्चित आकार के बैग में रेत खरीदनी है; वह तब पूर्णांक प्रोग्रामिंग है। एक प्रमेय है कि यह एनपी-हार्ड हो सकता है। अभ्यास में यह कितना मुश्किल है इस पर निर्भर करता है कि यह रैखिक प्रोग्रामिंग के करीब कितना करीब है। पूर्णांक प्रोग्रामिंग समस्याओं के कुछ मनाए गए उदाहरण हैं जिनमें, चमत्कारी रूप से, रैखिक कार्यक्रम के सभी शीर्षांक पूर्णांक बिंदु हैं। फिर आप रैखिक कार्यक्रम को हल कर सकते हैं और समाधान अभिन्न अंग होगा। ऐसी समस्या का एक उदाहरण शादी की समस्या है, कुल खुशी को अधिकतम करने के लिए एन पुरुषों और एन महिलाओं से शादी कैसे करें। (या, एन शहरों में एन कारखानों, एन आवेदकों के लिए नौकरियां, एन कंप्यूटरों को एन प्रिंटर आदि।)
एक बड़ा अंतर (या कम से कम, ख़ास विशेषता) है कि बाधाओं, के रूप में रैखिक समीकरण मॉडलिंग कर रहे हैं यानी वे प्रपत्र c_1 x_1 + c_2 x_2... के सभी कर रहे हैं। विकिपीडिया लेख का मानक रूप खंड इस का एक अच्छा अच्छा अवलोकन देता है।
एक और अंतर/विशेषता यह है कि रैखिक प्रोग्रामिंग एक समारोह को अधिकतम (या कम करने) की मांग कर रही है - आप प्रभावी ढंग से बहु-उद्देश्य अनुकूलन नहीं कर सकते हैं।
एक समारोह के मानक को अधिकतम नहीं है? – Mathias
@ माथीस - शायद यह मानक है, लेकिन यह एकमात्र प्रकार का अनुकूलन नहीं है जो मौजूद है। – awshepard
असल में, मुझे आपके मन में क्या है इसके बारे में सुनने में दिलचस्पी होगी! एक अनुकूलन समस्या गणितीय रूप से कुछ फ़ंक्शन का न्यूनतमकरण है, और क्योंकि आप एक ही चर के एक साथ दो कार्यों को कम नहीं कर सकते हैं, आमतौर पर आप इन कार्यों के एक समारोह को कम करते हैं (जैसे उनमें से एक भारित संयोजन ...)। – Mathias
रैखिक प्रोग्रामिंग 'गणितीय प्रोग्रामिंग' का विषय है, जिसे 'गणितीय अनुकूलन' भी कहा जाता है। रैखिक कार्यक्रम सामान्य गणितीय कार्यक्रमों से भिन्न होते हैं जिसमें एक रैखिक कार्यक्रम (एलपी) के लिए सभी बाधाओं के कार्यों और उद्देश्य कार्य उनके चर के संबंध में रैखिक होते हैं।
शुरू करने के लिए एक अच्छी जगह here होगी यदि आप डांटज़ीग द्वारा मूल कार्य चाहते हैं, या यदि आप पाठ्यपुस्तक प्राप्त करना चाहते हैं, तो मैं this एक की अनुशंसा करता हूं। यदि आप अपने संसाधनों को देखना चाहते हैं, तो Simplex method को देखने के साथ शुरू करें - इन कार्यक्रमों को हल करने के लिए एक बहुत ही आम तकनीक है, या कम आम लेकिन निश्चित रूप से बहुपद समय Ellipsoid method। हालांकि मैंने इसे सब कुछ नहीं पढ़ा है, इसे तुरंत देखकर this पीडीएफ शुरू करने के लिए एक अच्छी जगह हो सकती है। सुनिश्चित करें कि जो कुछ भी आप पढ़ते हैं, वह द्वंद्व को कवर करता है (और शायद विशेष रूप से Farkas' lemma) क्योंकि यह अधिकांश एलपी हलकों में एक केंद्रीय विचार है।
सबसे प्राकृतिक एक्सटेंशन या तो इंटीजर प्रोग्राम (एलपी के समान हैं, लेकिन सभी चर पूर्णांक मानों पर लेना चाहिए - यानी, कोई अंश नहीं घटक) या उत्तल प्रोग्रामिंग (शायद एक और सामान्य एक्सटेंशन)। एक अच्छी उत्तल अनुकूलन पाठ्य पुस्तक पीडीएफ फॉर्म here में उपलब्ध है।
रैखिक प्रोग्रामिंग एक अनुकूलन तकनीक है जिसमें रैखिक बाधाएं और एक रैखिक उद्देश्य कार्य शामिल है। बाधाएं समस्या स्थान को बाध्य करने के लिए लिखी जाती हैं, जबकि उद्देश्य कार्य कुछ ऐसा होता है जिसे आप कम करने (या संभावित रूप से अधिकतम) को कम करने का प्रयास कर रहे हैं जो बाधाओं को पूरा करता है। simplex algorithm आमतौर पर बाधाओं को संतुष्ट करने वाले उद्देश्य कार्य के न्यूनतम (या अधिकतम) मान को खोजने के लिए बाधा चौराहे के किनारों के साथ चलने के लिए उपयोग किया जाता है।
एलपी समस्या स्थापित करते समय, यह सुनिश्चित करना महत्वपूर्ण है कि बाधाएं उचित कार्य को सही ढंग से बाध्य करती हैं। बाधाओं को परिभाषित करना संभव है जिसके परिणामस्वरूप कोई संभावित समाधान नहीं होता है (उदा। X> 1 और -x> 1)। यह बाधित है। किसी समस्या को कम करना भी संभव है (उदाहरण के लिए न्यूनतम x खोजें कि x < 1)।
मुझे यकीन है कि यह पूछने के लिए व्यर्थ है कि सवाल अब बंद हो गया है, लेकिन क्या वह व्यक्ति जिसने मुझे संशोधित किया है, वह समझाने के लिए पर्याप्त दयालु क्यों होगा? धन्यवाद। – andand
जैसा कि हर किसी ने कहा है, रैखिक प्रोग्रामिंग ऑप्टिमाइज़ेशन समस्याओं को हल करने का एक तरीका है, जिसमें शर्तें रैखिक हैं।
यह समझना महत्वपूर्ण है समस्याओं के प्रकार क्या एल.पी.
एक उदाहरण मैं कहाँ का उपयोग किया है रैखिक प्रोग्रामिंग एक रेस्तरां अनुसूची बनाने जा रहा है के समाधान में मदद कर सकते हैं।एक रेस्तरां में आप कौशल सेट है:
और तुम कर्मचारी हैं, जिनमें से प्रत्येक के साथ एक या अधिक कौशल सेट। प्रत्येक कर्मचारी की एक विशिष्ट उपलब्धता भी होती है। उदाहरण के लिए, बॉब रविवार सुबह काम नहीं कर सकता क्योंकि वह स्थानीय चर्च में पादरी है। कर्मचारियों के पास भी एक लागत है। बॉब $ 10.50/घंटा हो सकता है जबकि सूजी $ 5.15/घंटा है। अंत में कर्मचारियों के पास न्यूनतम गारंटीकृत घंटे हो सकते हैं। चूंकि बॉब 15 साल तक एक कर्मचारी रहा है, बॉस का कहना है कि उसे हमेशा कम से कम 35 घंटे मिलेंगे।
रेस्तरां की मांग है। उदाहरण के लिए इसमें 3 बदलाव हैं: सुबह, दोपहर और रात, और इनमें से प्रत्येक शिफ्ट में कर्मचारियों की आवश्यकताओं का एक सेट है: हमें 1 कुक, 1 सर्वर, 1 प्रबंधक सुबह, 3 कुक, 2 सर्वर, 2 होस्ट, 2 की आवश्यकता है शाम को दोपहर में प्रबंधकों, और 4 कुक, 4 सर्वर, 3 मेजबान, 2 प्रबंधक, 2 bussers। प्रत्येक शिफ्ट की अवधि होगी, और आप कर्मचारी की प्रति घंटा मजदूरी की अवधि को गुणा करके प्रत्येक शिफ्ट की लागत का आकलन कर सकते हैं।
अंततः हमारे पास राज्य और संघीय कानून हैं, और कुछ बुनियादी "व्यवसाय" नियम हैं: कोई भी कर्मचारी ओवरटाइम में बिना 8 घंटे से अधिक समय तक काम कर सकता है। कोई भी कर्मचारी कम से कम 2 घंटे के लिए निर्धारित किया जा सकता (क्योंकि यह एक 2 घंटे की पारी के लिए 30 मिनट की लघुकरण बनाने के लिए चूसना होगा), कर्मचारियों, दो ओवरलैप पाली, आदि
अब दिए गए सभी इन आवश्यकताओं को काम नहीं कर सकता देना मुझे एक कार्यक्रम है जो सभी आवश्यकताओं को पूरा करता है, और सबसे कम श्रम लागत पैदा करता है।
यह एक रैखिक प्रोग्रामिंग अनुकूलन समस्या का एक उदाहरण है।
एक उद्देश्य समारोह, चर, चर सीमा, और बाधाओं:
एक रेखीय कार्यक्रम आम तौर पर होते हैं।
चूंकि हम लागत को कम करना चाहते हैं, इसलिए हमारा उद्देश्य कार्य उन कर्मचारियों को शामिल करने जा रहा है जो कर्मचारी काम करते हैं, और संबंधित लागत (शिफ्ट अवधि * मजदूरी)।
इस मामले में चर, प्रत्येक कर्मचारी काम कर सकते हैं कि बदलाव हैं।
इन चरों पर सीमाएं 0 और 1 के बीच पूर्णांक हैं, क्योंकि कोई कर्मचारी शिफ्ट (1) काम कर रहा है, या कर्मचारी शिफ्ट (0) काम नहीं कर रहा है। यह, वैसे, एक विशेष कार्यक्रम है, जिसे बाइनरी इंटीजर प्रोग्राम या बीआईपी संक्षिप्त कहा जाता है, क्योंकि सभी चर पूर्णांक (कोई अंशकालिक मान नहीं होते हैं) और सभी मान या तो 0 या 1.
बाधाएं समानता/उपरोक्त आवश्यकताओं के आधार पर असमानता बाधाएं।
उदाहरण के लिए, यदि ऊपर वर्णित सीमाओं के कारण बॉब और सूजी सुबह में कुक के रूप में काम कर सकते हैं, तो Bob_Morning_Cook1_Shift + Suzy_Morning_Cook1_Shift = 1, Bob_Morning_Cook_Shift = {0,1} और Suzy_Morning_Cook_Shift = {0,1} के साथ। सूचना के ये तीन टुकड़े बताते हैं कि अधिकतर एक कर्मचारी को पहली सुबह पकाने के रूप में असाइन किया जा सकता है।
तो एक बार जब आप अपनी समस्या का समाधान करने वाली सभी बाधाओं को परिभाषित कर लेते हैं, तो आप समस्या को हल करना शुरू कर सकते हैं।यदि कोई समाधान पाया जा सकता है (और बाधाओं के आधार पर समस्या असुरक्षित हो सकती है), तो यह आपको कर्मचारी असाइनमेंट देगा जो सबसे कम साप्ताहिक श्रम लागत का उत्पादन करेगी।
बहुत सरलता से, यह आपकी समस्या को रैखिक समीकरणों के सेट के रूप में फिर से लिखने और फिर उन समीकरणों को हल करने के बारे में है। – FrustratedWithFormsDesigner
आप किस "अन्य विधि" के बारे में बात कर सकते हैं? –
अच्छा सवाल, मैं इसके बारे में भूल गया (जब से कैल्क हमने रैखिक प्रोग्रामिंग के बजाय इसे "अनुकूलन" कहा था) –