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

मुक्त ज्ञानकोश विकिपीडिया से
(रैखिक प्रोग्रामन से अनुप्रेषित)
यहाँ जाएँ: भ्रमण, खोज
लिओनिद कान्तोरोविच

गणित में रैखिक प्रोग्रामन (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} \and \mathbf{x} \geq 0 \}

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

उदाहरण[संपादित करें]

इन्हें भी देखें[संपादित करें]

बाहरी कड़िया[संपादित करें]