रैखिक प्रोग्रामिंग, गणितीय मॉडलिंग तकनीक जिसमें विभिन्न बाधाओं के अधीन होने पर एक रेखीय कार्य को अधिकतम या न्यूनतम किया जाता है। यह तकनीक व्यावसायिक योजना में, औद्योगिक इंजीनियरिंग में, और कुछ हद तक सामाजिक और भौतिक विज्ञानों में मात्रात्मक निर्णय लेने के लिए उपयोगी है।
अनुकूलन: रैखिक प्रोग्रामिंग
यद्यपि व्यापक रूप से हर रोज निर्णय की समस्याओं को हल करने के लिए अब उपयोग किया जाता है, 1947 से पहले रैखिक प्रोग्रामिंग तुलनात्मक रूप से अज्ञात थी। कोई महत्व का काम नहीं
।
लीनियर प्रोग्रामिंग समस्या का समाधान, लीनियर एक्सप्रेशन (उद्देश्य फ़ंक्शन कहा जाता है) के इष्टतम मान (समस्या के आधार पर सबसे बड़ा या सबसे छोटा) को कम करता है।
असमानताओं के रूप में व्यक्त बाधाओं के एक सेट के अधीन:
ए, बी, और सी की क्षमता, आवश्यकताओं, लागतों, मुनाफे, और समस्या की अन्य आवश्यकताओं और प्रतिबंधों द्वारा निर्धारित किया जाता है। इस पद्धति के आवेदन में मूल धारणा यह है कि मांग और उपलब्धता के बीच विभिन्न संबंध रैखिक हैं; अर्थात्, x i में से कोई भी एक शक्ति के अलावा अन्य 1 में नहीं उठाया गया है। इस समस्या का समाधान प्राप्त करने के लिए, रैखिक असमानताओं की प्रणाली का समाधान खोजना आवश्यक है (अर्थात, n मानों का समुच्चय) चर x मैं कि एक साथ सभी असमानताओं को संतुष्ट करता है)। ऑब्जेक्टिव फंक्शन का मूल्यांकन x i के मानों को समीकरण में परिभाषित करके किया जाता है जो f को परिभाषित करता है।
रैखिक प्रोग्रामिंग की पद्धति के अनुप्रयोगों को पहली बार 1930 के दशक के उत्तरार्ध में सोवियत गणितज्ञ लियोनिद कांटोरोविच द्वारा और अमेरिकी अर्थशास्त्री वासली लेओंटिफ़ द्वारा क्रमशः निर्माण कार्यक्रम और अर्थशास्त्र के क्षेत्रों में गंभीरता से लेने का प्रयास किया गया था, लेकिन दशकों तक उनके काम को अनदेखा कर दिया गया था। द्वितीय विश्व युद्ध के दौरान, लागत और उपलब्धता जैसे कुछ प्रतिबंधों के अधीन संसाधनों के परिवहन, शेड्यूलिंग और संसाधनों के आवंटन से निपटने के लिए रैखिक प्रोग्रामिंग का बड़े पैमाने पर उपयोग किया गया था। इन अनुप्रयोगों ने इस पद्धति की स्वीकार्यता को स्थापित करने के लिए बहुत कुछ किया, जिसने अमेरिकी गणितज्ञ जॉर्ज डेंटज़िग की सरल विधि की शुरुआत के साथ 1947 में और अधिक प्रोत्साहन प्राप्त किया, जिसने रैखिक प्रोग्रामिंग समस्याओं के समाधान को बहुत सरल किया।
हालाँकि, अधिक चरों को शामिल करते हुए अधिक जटिल समस्याओं का प्रयास किया गया था, आवश्यक संचालन की संख्या में तेजी से विस्तार हुआ और यहां तक कि सबसे शक्तिशाली कंप्यूटरों की कम्प्यूटेशनल क्षमता से अधिक हो गई। फिर, 1979 में, रूसी गणितज्ञ लियोनिद खाचियान ने एक बहुपद-समय एल्गोरिथ्म की खोज की - जिसमें कम्प्यूटेशनल चरणों की संख्या तेजी से बढ़ने के बजाय चर की संख्या की शक्ति के रूप में बढ़ती है - जिससे उच्चतर दुर्गम समस्याओं के समाधान की अनुमति मिलती है। हालांकि, व्यावहारिक रूप से लागू होने पर, खाकियान का एल्गोरिथ्म (दीर्घवृत्त विधि कहा जाता है) सरल विधि से धीमा था। 1984 में भारतीय गणितज्ञ नरेंद्र कर्मकार ने एक और बहुपद-समय एल्गोरिथ्म की खोज की, जो कि आंतरिक बिंदु विधि है, जो कि सरल पद्धति से प्रतिस्पर्धी साबित हुई।
