रैखिक क्रमादेशन

गणित में रैखिक प्रोग्रामन (linear programming) इष्टतमीकरण (ऑप्टिमाइजेशन) की एक तकनीक है जिसमें लक्ष्य-फलन भी रैखीय होता है तथा शर्तें (समिकाएं/असमिकाएँ) भी रैखिक होतीं हैं। किन्तु इसका कम्प्यूटर प्रोग्रामन से कोई सम्बन्ध नहीं है।

सन १९३९ में लिओनिद कान्तोरोविच (Leonid Kantorovich) ने प्रथम रैखिक प्रोग्रामन समस्या निर्मित की थी। उन्होने इस समस्या के हल की विधि भी प्रस्तुत की थी। उन्होने इसे द्वितीय विश्वयुद्ध के समय विकसित किया था जिसका उद्देश्य युद्ध में सेना के खर्चे को कम करना था।

मानक रूप (Standard form), रैखिक क्रमादेशन समस्या के वर्णन का सबसे अच्छा तरीका है। रैखिक प्रोग्रामिंग की समस्या के तीन भाग होते हैं।

• एक रैखिक फलन का अधिकतमीकरण (linear function to be maximized)

जैसे ${\displaystyle f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}}$

• समस्या की शर्तें (Problem constraints), जो कुछ इस प्रकार के होते हैं-

जैसे

${\displaystyle {\begin{matrix}a_{11}x_{1}+a_{12}x_{2}&\leq b_{1}\\a_{21}x_{1}+a_{22}x_{2}&\leq b_{2}\\a_{31}x_{1}+a_{32}x_{2}&\leq b_{3}\\\end{matrix}}}$

• वे चर जिनका मान केवल धनात्मक हो सकता है (Non-negative variables)

जैसे.

${\displaystyle {\begin{matrix}x_{1}\geq 0\\x_{2}\geq 0\end{matrix}}}$

रैखिक क्रमादेशन की समस्या को प्रायः मैट्रिक्स के रूप में अभिव्यक्त किया जाता है, तब समस्या का रूप यह हो जाता है-

${\displaystyle \max\{\mathbf {c} ^{\mathrm {T} }\mathbf {x} \;|\;A\mathbf {x} \leq \mathbf {b} \land \mathbf {x} \geq 0\}}$

अन्य प्रकार की रैखिक क्रमानुदेशन समस्याएं (जैसे न्यूनीकरण समस्या, दूसरे प्रकार की शर्तें, ऋणात्मक चर मानों वाली समस्याएँ आदि) हमेशा उपरोक्त मानक रूप में बदलकर लिखी सकतीं हैं।

मना दो चरों ${\displaystyle x_{1}}$ तथा ${\displaystyle x_{2}}$ के रैखिक फलन G का अधिकतम मान निकालना है-

${\displaystyle G(x_{1},x_{2})=300x_{1}+500x_{2}.}$

किन्तु, उपरोक्त फलन का अधिकतम मान निकालते समय निम्नलिखित शर्तों का पालन भी होना चाहिये-

${\displaystyle {\begin{alignedat}{3}x_{1}&+&2x_{2}&\leq 170\\x_{1}&+&x_{2}&\leq 150\\&&3x_{2}&\leq 180\end{alignedat}}}$

इन शर्तों के साथ यह भी ध्यान रखना है कि दोनों चर ऋणात्मक मान नहीं ले सकते, अर्थात् ${\displaystyle x_{1},x_{2}\geq 0}$

इस समस्या का हल सामने के ग्राफ से हो जाता है। ग्राफ में नीली रेखा में बने बहुभुज के किसी शीर्ष पर ही उपरोक्त फलन G का मान अधिकतम होगा। एक-एक करके जाँचने पर पता चलता है कि x1=130 तथा x2=20 रखने पर G का मान अधिकतम (49000) प्राप्त होता है।

• गतिक क्रमादेशन (डायनेमिक प्रोग्रामिंग)
• एकधा विधि (सिम्प्लेक्स मेथड)
• इष्टतमकरण

• Guidance on Formulating LP problems
• 0-1 Integer Programming Benchmarks with Hidden Optimum Solutions
• Mathematical Programming Glossary
• A Tutorial on Integer Programming
• The linear programming FAQ
• Linear Programming Survey OR/MS Today
• Linear Programming: Guide to Formulation, Simplex Algorithm, Goal Programming and Excel Solver examples
• George Dantzig