रैखिक प्रोग्रामिंग: यह मॉडल, बाधाओं, अनुप्रयोगों के लिए क्या है - गणित - 2025

रैखिक प्रोग्रामिंग एक गणितीय पद्धति है कि है है अनुकूलन (अधिकतम या उचित रूप में कम से कम) एक समारोह जिसका चर प्रतिबंधित कर रहे हैं के लिए इस्तेमाल किया, के रूप में लंबे समय के रूप समारोह और बाधाओं रैखिक रूप से निर्भर चर हैं।

आमतौर पर, अनुकूलित किए जाने वाले फ़ंक्शन को एक व्यावहारिक स्थिति, जैसे निर्माता के इनपुट, श्रम या मशीनरी के लाभ सीमित होते हैं।

चित्रा 1. रैखिक प्रोग्रामिंग व्यापक रूप से लाभ का अनुकूलन करने के लिए उपयोग किया जाता है। स्रोत: पिक्सल्स

सबसे सरल मामलों में से एक अधिकतम होने के लिए एक रेखीय कार्य है, जो केवल दो चर पर निर्भर करता है, जिसे निर्णय चर कहा जाता है। यह फार्म का हो सकता है:

Z = k ₁ x + k ₂ y

K ₁ और k ₂ स्थिरांक के साथ। इस फ़ंक्शन को उद्देश्य फ़ंक्शन के रूप में जाना जाता है। बेशक, ऐसी स्थितियां हैं जो अध्ययन के लिए दो से अधिक चर का गुण रखती हैं, अधिक जटिल होना:

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +…।

और बाधाओं को गणितीय रूप से समीकरणों या असमानताओं की एक प्रणाली द्वारा मॉडल किया जाता है, एक्स और वाई में समान रूप से रैखिक।

इस प्रणाली में समाधान के सेट को व्यवहार्य समाधान या व्यवहार्य बिंदु कहा जाता है। और संभव बिंदुओं में से कम से कम एक है, जो उद्देश्य फ़ंक्शन का अनुकूलन करता है।

रैखिक प्रोग्रामिंग स्वतंत्र रूप से अमेरिकी भौतिक विज्ञानी और गणितज्ञ जॉर्ज डेंटजिग (1914-2005) और द्वितीय विश्व युद्ध के तुरंत बाद रूसी गणितज्ञ और अर्थशास्त्री लियोनिद कांटोरोविच (1912-1986) द्वारा विकसित की गई थी।

सिम्पलेक्स विधि के रूप में जानी जाने वाली समस्या-समाधान विधि, डेंटज़िग के दिमाग की उपज है, जिसने अमेरिकी वायु सेना, बर्कले विश्वविद्यालय और स्टैनफोर्ड विश्वविद्यालय के लिए काम किया था।

चित्रा 2. गणितज्ञ जॉर्ज डेंटजिग (बाएं) और लियोनिद कांतोरोविच (दाएं)। स्रोत: एफ। ज़पाटा

रैखिक प्रोग्रामिंग मॉडल

एक व्यावहारिक स्थिति के लिए उपयुक्त रैखिक प्रोग्रामिंग मॉडल स्थापित करने के लिए आवश्यक तत्व हैं:

-उद्देश्य समारोह

-Decision चर

-Restrictions

उद्देश्य फ़ंक्शन में आप परिभाषित करते हैं कि आप क्या हासिल करना चाहते हैं। उदाहरण के लिए, मान लें कि आप कुछ उत्पादों के निर्माण से किए गए मुनाफे को अधिकतम करना चाहते हैं। फिर "लाभ" फ़ंक्शन स्थापित किया जाता है, जिस कीमत पर उत्पादों को बेचा जाता है।

गणितीय शब्दों में, इस फ़ंक्शन को संक्षेप अंकन का उपयोग करके संक्षिप्त रूप में व्यक्त किया जा सकता है:

Z = ∑k _i x _i

इस समीकरण में, k _i गुणांक हैं और x _i निर्णय चर हैं।

निर्णय चर सिस्टम के तत्व हैं जिनका नियंत्रण था और उनके मूल्य सकारात्मक वास्तविक संख्याएं हैं। प्रस्तावित उदाहरण में, निर्णय चर अधिकतम लाभ प्राप्त करने के लिए निर्मित किए जाने वाले प्रत्येक उत्पाद की मात्रा हैं।

अंत में, हमारे पास बाधाएं हैं, जो निर्णय चर के संदर्भ में रैखिक समीकरण या असमानताएं हैं। वे समस्या की सीमाओं का वर्णन करते हैं, जो ज्ञात हैं और हो सकता है, उदाहरण के लिए, निर्माण में उपलब्ध कच्चे माल की मात्रा।

प्रतिबंधों के प्रकार

आपके पास j = 1 से j = M से शुरू होने वाली सीमाओं की संख्या M हो सकती है। गणितीय रूप से प्रतिबंध तीन प्रकार के होते हैं:

1. ए _जे = ∑ एक _आईजे । x _i
2. ब _ज ∑ _j ब _इज । x _i
3. सी _जे ≤ _j सी _आईजे । x _i

पहला प्रतिबंध रैखिक समीकरण प्रकार का है और इसका मतलब है कि मूल्य ए _जे, जिसे ज्ञात है, का सम्मान करना होगा।

शेष दो प्रतिबंध रैखिक असमानताएं हैं और इसका मतलब है कि ज्ञात मूल्य B _j और C _j का सम्मान या उससे अधिक हो सकता है, जब दिखाई देने वाला प्रतीक ≥ (अधिक से अधिक या बराबर) या सम्मान या उससे अधिक हो, यदि प्रतीक ≤ है (से कम या बराबर)।

मॉडल उदाहरण

व्यवसाय प्रशासन से लेकर पोषण तक आवेदन के क्षेत्र बहुत विविध हैं, लेकिन विधि को समझने के लिए, दो चर के साथ एक व्यावहारिक स्थिति का एक सरल मॉडल नीचे प्रस्तावित है।

एक स्थानीय पेटिसरी को दो विशिष्टताओं के लिए जाना जाता है: काला वन केक और सैप्रिपेंटाइन केक।

इसकी तैयारी में उन्हें अंडे और चीनी की आवश्यकता होती है। काले जंगल के लिए आपको 9 अंडे और 500 ग्राम चीनी की जरूरत होती है, जबकि सैप्रिपेंटाइन के लिए आपको 8 अंडे और 800 ग्राम चीनी की जरूरत होती है। संबंधित बिक्री मूल्य $ 8 और $ 10 हैं।

समस्या यह है: बेकरी को अपने लाभ को अधिकतम करने के लिए प्रत्येक प्रकार के कितने केक बनाने चाहिए, यह जानते हुए कि इसमें 10 किलो चीनी और 144 अंडे हैं?

निर्णय चर

निर्णय चर "x" और "y" हैं, जो वास्तविक मान लेते हैं:

-x: काले वन केक की संख्या

-y: sacripantine प्रकार के केक।

प्रतिबंध

प्रतिबंध इस तथ्य से दिए गए हैं कि केक की संख्या एक सकारात्मक मात्रा है और उन्हें तैयार करने के लिए सीमित मात्रा में कच्चे माल हैं।

इसलिए, गणितीय रूप में, ये प्रतिबंध रूप लेते हैं:

1. x ≥ 0
2. और ≥0
3. 9x + 8y ≤ 144
4. 0.5 x + 0.8y ≤ 10

बाधाएं 1 और 2 पहले उजागर होने वाली गैर-नकारात्मकता की स्थिति का गठन करती हैं, और उठाए गए सभी असमानताएं रैखिक हैं। प्रतिबंध 3 और 4 में वे मूल्य हैं जो अधिक नहीं होने चाहिए: 144 अंडे और 10 किलो चीनी।

उद्देश्य समारोह

अंत में, उद्देश्य समारोह काला वन केक की "x" मात्रा और "y" मात्रा में sacripantines का निर्माण करते समय प्राप्त लाभ है। यह प्रत्येक प्रकार के लिए बनाए गए केक की मात्रा से मूल्य को गुणा करके और बनाया गया है। यह एक रैखिक कार्य है जिसे हम G (x, y) कहेंगे:

जी = 8x + 10y

समाधान के तरीके

विभिन्न समाधान विधियों में ग्राफिकल तरीके, सिंपलेक्स एल्गोरिथ्म और आंतरिक बिंदु विधि शामिल हैं, कुछ को नाम देने के लिए।

- ग्राफिक या ज्यामितीय विधि

जब आपके पास पिछले अनुभाग में एक की तरह दो-चर समस्या होती है, तो बाधाएं xy विमान में एक बहुभुज क्षेत्र का निर्धारण करती है, जिसे व्यवहार्य क्षेत्र या व्यवहार्यता क्षेत्र कहा जाता है।

चित्रा 3. संभव क्षेत्र, जहां अनुकूलन समस्या का समाधान पाया जाता है। स्रोत: विकिमीडिया कॉमन्स

इस क्षेत्र का निर्माण प्रतिबंध रेखाओं का उपयोग करके किया गया है, जो प्रतिबंधों की असमानताओं से प्राप्त रेखाएं हैं, जो केवल समान चिह्न के साथ काम कर रही हैं।

बेकरी जो लाभ का अनुकूलन करना चाहता है, के मामले में, बाधा रेखाएँ निम्न हैं:

1. x = 0
2. य = ०
3. 9x + 8y = 144
4. 0.5 x + 0.8y = 10

इन रेखाओं से घिरे क्षेत्र के सभी बिंदु संभव समाधान हैं, इसलिए उनमें से कई अनंत हैं। उस मामले को छोड़कर जहां व्यवहार्य क्षेत्र खाली हो जाता है, जिस स्थिति में समस्या का कोई समाधान नहीं है।

सौभाग्य से, पेस्ट्री समस्या के लिए संभव क्षेत्र खाली नहीं है, हमारे पास यह नीचे है।

चित्रा 4. पेस्ट्री समस्या का संभव क्षेत्र। लाभ 0 वाली रेखा मूल को पार करती है। स्रोत: जोगेब्रा के साथ एफ।

इष्टतम समाधान, यदि यह मौजूद है, तो उद्देश्य फ़ंक्शन की सहायता से पाया जाता है। उदाहरण के लिए, अधिकतम लाभ G को खोजने की कोशिश करते समय, हमारे पास निम्न रेखा होती है, जिसे आईएसओ-लाभ रेखा कहा जाता है:

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

इस पंक्ति के साथ हम सभी जोड़े (x, y) प्राप्त करते हैं जो एक दिया गया G प्रदान करते हैं, इसलिए G के मान के अनुसार लाइनों का एक परिवार है, लेकिन सभी एक ही ढलान -k ₁ / k _{2 के साथ हैं}, इसलिए वे हैं समानांतर रेखाएं।

इष्टतम समाधान

अब, यह दिखाया जा सकता है कि एक रेखीय समस्या का इष्टतम समाधान हमेशा एक चरम बिंदु या संभव क्षेत्र का शीर्ष होता है। इसलिए:

यदि मूल के निकटतम रेखा के पास एक संपूर्ण खंड है जो संभव क्षेत्र के साथ आम है, तो यह कहा जाता है कि अनंत समाधान हैं। यह मामला तब होता है यदि आइसो-प्रॉफिट लाइन का ढलान क्षेत्र को सीमित करने वाली किसी भी अन्य लाइन के बराबर है।

हमारी पेस्ट्री के लिए, उम्मीदवार लंबवत ए, बी और सी हैं।

- डेंटजिग की सरल विधि

ग्राफिकल या ज्यामितीय विधि दो चर के लिए लागू होती है। हालाँकि, यह अधिक जटिल है जब तीन चर होते हैं, और बड़ी संख्या में चर के लिए उपयोग करना असंभव होता है।

दो से अधिक चरों के साथ समस्याओं का सामना करते समय, सरल विधि का उपयोग किया जाता है, जिसमें उद्देश्य कार्यों का अनुकूलन करने के लिए एल्गोरिदम की एक श्रृंखला होती है। गणनाओं को अंजाम देने के लिए अक्सर गणित और सरल अंकगणित का उपयोग किया जाता है।

सिंपलेक्स विधि एक व्यवहार्य समाधान चुनकर शुरू होती है और जांचती है कि क्या यह इष्टतम है। यदि यह है, तो हम पहले ही समस्या का समाधान कर चुके हैं, लेकिन यदि ऐसा नहीं है, तो हम अनुकूलन के करीब एक समाधान की ओर बढ़ते हैं। यदि समाधान मौजूद है, तो एल्गोरिथ्म इसे कुछ प्रयासों में पाता है।

अनुप्रयोग

लागत को कम करने और मुनाफे में वृद्धि के संदर्भ में सर्वोत्तम निर्णय लेने के लिए रैखिक और गैर-रैखिक प्रोग्रामिंग कई क्षेत्रों में लागू की जाती हैं, जो हमेशा मौद्रिक नहीं होती हैं, क्योंकि उन्हें समय में मापा जा सकता है, उदाहरण के लिए, यदि आप आवश्यक समय को कम करना चाहते हैं संचालन की एक श्रृंखला को पूरा करने के लिए।

यहाँ कुछ क्षेत्र हैं:

-एक विशिष्ट उत्पाद का विज्ञापन करने के लिए मीडिया (सोशल नेटवर्क, टेलीविजन, प्रेस और अन्य) का सबसे अच्छा संयोजन खोजने के लिए इसका उपयोग किया जाता है।

-किसी कंपनी या फैक्ट्री के कर्मियों को पर्याप्त कार्य सौंपना या उन्हें शेड्यूल करना।

-सबसे अधिक पौष्टिक भोजन का चयन और पशुधन और कुक्कुट उद्योगों में सबसे कम लागत पर।

हल किया अभ्यास

- अभ्यास 1

रेखांकन पूर्ववर्ती वर्गों में उठाए गए रैखिक प्रोग्रामिंग मॉडल को हल करें।

उपाय

समस्या में निर्दिष्ट प्रतिबंधों की प्रणाली द्वारा निर्धारित मूल्यों के सेट को रेखांकन करना आवश्यक है:

1. x ≥ 0
2. और ≥0
3. 9x + 8y ≤ 144
4. 0.5 x + 0.8y ≤ 10

असमानता 1 और 2 द्वारा दिया गया क्षेत्र कार्टेशियन विमान के पहले चतुर्थांश से मेल खाता है। 3 और 4 की असमानताओं के बारे में, हम प्रतिबंध लाइनों को खोजने से शुरू करते हैं:

9x + 8y = 144

0.5 x + 0.8y = 10 → 5x + 8y = 100

संभाव्य क्षेत्र एक चतुर्भुज है, जिसके कोने बिंदु A, B, C और D हैं।

न्यूनतम लाभ 0 है, इसलिए लाइन 8x + 10y = 0 निचली सीमा है और आईएसओ-लाभ लाइनों में ढलान -8/10 = - 0.8 है।

यह मूल्य अन्य प्रतिबंध लाइनों के ढलानों से अलग है और चूंकि संभव क्षेत्र बाध्य है, अद्वितीय समाधान मौजूद है।

चित्रा 5. व्यायाम 1 का ग्राफिकल समाधान, संभव क्षेत्र और समाधान बिंदु सी को उक्त क्षेत्र के कोने में से एक पर दिखाता है। स्रोत: एफ। ज़पाटा

यह समाधान ढलान -0.8 की एक रेखा से मेल खाता है, जो कि किसी भी बिंदु A, B या C से होकर गुजरता है, जिसके निर्देशांक निम्न हैं:

ए (11; 5.625)

बी (0; 12.5)

सी (16, 0)

सर्वोतम उपाय

हम इनमें से प्रत्येक बिंदु के लिए G के मान की गणना करते हैं:

- (11; 5.625): जी _ए = 8 x 11 + 10 x 5.625 = 144.25

- (0; 12.5): जी _बी = 8 x 0 + 10 x 12.5 = 125

- (16, 0): जी _सी = 8 x 16 + 10 x 0 = 128

सबसे अधिक लाभ 11 काले वन केक और 5,625 सैक्रिपेंटाइन केक के निर्माण में पाया जाता है। यह समाधान सॉफ्टवेयर के माध्यम से पाए जाने वाले से सहमत है।

- व्यायाम २

एक्सेल या लिब्रे ऑफिस कैलक जैसे अधिकांश स्प्रेडशीट में उपलब्ध सॉल्वर फ़ंक्शन का उपयोग करके पिछले अभ्यास के परिणाम को सत्यापित करें, जो रैखिक प्रोग्रामिंग में अनुकूलन के लिए सिम्पलेक्स एल्गोरिथ्म को शामिल करता है।

उपाय

चित्रा 6. लिबर ऑफिस Calc स्प्रेडशीट के माध्यम से व्यायाम 1 से समाधान का विस्तार। स्रोत: एफ। ज़पाटा

चित्रा 7. लिबर ऑफिस Calc स्प्रेडशीट के माध्यम से व्यायाम 1 से समाधान का विस्तार। स्रोत: एफ। ज़पाटा

संदर्भ

1. प्रतिभाशाली। रैखिक प्रोग्रामिंग। से पुनर्प्राप्त: शानदार ।.org।
2. इप्पेन, जी। 2000. प्रशासनिक विज्ञान में संचालन अनुसंधान। 5 वीं। संस्करण। शागिर्द कक्ष।
3. Haeussler, ई। 1992. प्रबंधन और अर्थशास्त्र के लिए गणित। 2। संस्करण। ग्रुपो संपादकीय Iberoamericana।
4. Hiru.eus। रैखिक प्रोग्रामिंग। से पुनर्प्राप्त: hiru.eus।
5. विकिपीडिया। रैखिक प्रोग्रामिंग। से बरामद: तों। wikipedia.org।