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

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

इतिहास

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

मानक स्वरूप

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

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

जैसे

f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}

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

जैसे

{\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)

जैसे.

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

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

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

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

उदाहरण

उदाहरण में दी गयी समस्या की व्याख्या

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

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

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

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

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

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

इन्हें भी देखें

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

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

अनुक्रम

इतिहास

मानक स्वरूप

उदाहरण

इन्हें भी देखें

बाहरी कड़ियाँ