لکیری برمجہ

لکیری پروگرامنگ ریاضی کی ایک تکنیک ہے جس میں ایسے مسلئے حل کیے جاتے ہیں جن میں ایک اقتصادی منافع فنکشن کو زیادہ سے زیادہ کرنا مقصود ہوتا ہے۔ مثلاً ایک کارخانہ میں مختلف اشیا کی تعداد \ x_1, x_2, \cdots, x_n تیار کی جاتی ہیں جن کی مارکیٹ میں قیمت باترتیب \ c_1, c_2, \cdots, c_n ہے۔ اب منافع فنکشن ہو گی
:\ f(x_1, x_2,\cdots, x_n) = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n
اب ان اشیا کی تیاری کے لیے ایک خام مال باترتیب \ a_1, a_2, \cdots, a_n درکار ہوتا ہے، جس کی محدود مقدار \ b مہیا ہوتی ہے۔ اس پابندی کو نامساوات کی صورت میں یوں لکھا جا سکتا ہے
:\ a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \le b
دوسرے خام مال کے لیے اسی صورت علاحدہ نامساوات لکھی جا سکتی ہے۔ اس کے علاوہ مزدوری وغیرہ کی نامساوات بھی لکھی جا سکتی ہیں۔
لکیری پروگرامنگ مسلئہ

تو لکیری پروگرامنگ مسلئہ یہ بنا کہ متغیر \ x_1, x_2, \cdots, x_n کی ایس قیمتیں ڈھونڈو کہ منافع فنکشن
:\ f(x_1, x_2, \cdots, x_n) = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n
زیادہ سے زیادہ ہو، جبکہ دی گئی نامساوات
:\begin{matrix}
a_{1,1} x_1 + a_{1,2} x_2 + \cdots + a_{1,n} x_n \le b_1 \\
a_{2,1} x_1 + a_{2,2} x_2 + \cdots + a_{2,n} x_n \le b_2 \\
\vdots \\
a_{m,1} x_1 + a_{m,2} x_2 + \cdots + a_{m,n} x_n \le b_m
\end{matrix}

:x_1 \ge 0, \, x_2 \ge 0, \, \cdots,\, x_n \ge 0
کی بھی تسکین ہو۔
میٹرکس صورت

اس مسلئہ کو میٹرکس صورت یوں لکھا جا سکتا ہے:
سمتیہ (بصورت میٹرکس)
:X=\left[\begin{matrix}
x_1 \\
x_2 \\
\vdots\\
x_n
\end{matrix}
\right]
کی ایسی قیمت ڈھونڈو کہ فنکشن
:\ f(X) = c^t X
زیادہ سے زیادہ ہو، جبکہ دی گئی نامساوات میٹرکس
:\ AX \le b
:\ X \ge 0
کی بھی تسکین ہو۔ یہاں A ایک \ m \times n سائز کی میٹرکس ہے اور
b=\left[\begin{matrix}
b_1 \\
b_2 \\
\vdots\\
b_m
\end{matrix}
\right]
اور
c=\left[\begin{matrix}
c_1 \\
c_2 \\
\vdots\\
c_n
\end{matrix}
\right]
مثال 1

ایک کاشتکار کے پاس 10 ایکڑ زمین ہے جس پر وہ مٹر اور گاجر کی فصل کاشت کرنا چاہتا ہے۔ مٹر کی فصل میں ہر ایکڑ کے لیے 2 میٹرک ٹن کھاد درکار ہوتی ہے جبکہ گاجر کی فصل کے لیے 1 میٹرک ٹن فی ایکڑ۔ فرض کرو کہ کاشتکار کو صرف 12 میٹرک ٹن کھاد دستیاب ہے۔ اب منڈی میں مٹر کی فی ایکڑ پیداوار کے 9 ہزار روپے ملتے ہیں جبکہ گاجر کی ایک ایکڑ پیداوار کے 4 ہزار روپے۔ ہمیں یہ ڈھونڈنا ہے کہ کتنے ایکڑ پر مٹر اُگائے جائیں اور کتنے پر گاجر تاکہ کاشتکار کو زیادہ سے زیادہ آمدنی ہو۔

فرض کرو کہ گاجر x ایکڑ پر کاشت کی جاتی ہے اور مٹر y ایکڑ پر۔ اب چونکہ کل رقبہ 10 ایکڑ ہے، اس لیے
:\ x + y \le 10
کھاد مٹرکو 2 میٹرک ٹن فی ایکڑ اور گاجر کو 1 میٹرک ٹن فی ایکڑ۔ جبکہ کاشتکار کے پاس کھاد کی ساری مقدار 12 میٹرک ٹن ہے، اس لیے
:\ x + 2y \le 12
اس کے علاوہ چونکہ زیر کاشت رقبہ منفی نہیں ہو سکتا، اس لیے
:\ x \ge 0
:\ y \ge 0
مٹر کی قیمت 9 ہزار فی ایکڑ اور گاجر کی قیمت 4 ہزار فی ایکڑ کے حساب سے کاشتکار کی آمدنی ہو گی
:\ f(x,y) = 4 x + 9 y
جسے وہ زیادہ سے زیادہ کرنا چاہتا ہے۔

تصویر:Linear_programming_2_constraint_example.png

تصویر میں مساوات \ x + y = 10 کالے رنگی لکیر سے دکھائ گئی ہے۔ اس کالی لکیر سے نیچے کا سارا علاقہ پہلی نامساوات کی رُو سے جائز ہے۔ مساوات\ x + 2y = 12 نیلے رنگی لکیر سے دکھائ گئی ہے۔ دوسری نامساوات کی رو سے اس نیلی لکیر سے نیچے کا سارا علاقہ جائز ہے۔ اب نامساوات \ x \ge 0 \,,\, y \ge 0 کو ملا کر رنگدار (shaded) علاقہ جائز ہے، یعنی اس رنگدار علاقے کا کوئی بھی نکتہ تمام نامساوات کی تسکین کرتا ہے۔ غور کرو کہ یہ علاقہ ایک کثیرالاضلاع (polygon) ہے، جسے کے کونے یہ ہیں:


x
y

0
0


0
6


8
2


10
0


ہمیں اس رنگدار علاقے میں سے وہ نکتہ چننا ہے جس پر سب سے زیادہ آمدنی\ f(x,y) ہو۔ یہ پتہ کرنے کے لیے ہم نے تصویر میں 40 ہزار کی آمدنی تصور کرتے ہوئے، اس مساوات کے لیے
:\ 4 x + 9 y = 40
سرخ لکیر لگائی ہے۔ اس لکیر پر کسی بھی نکتہ پر آمدنی 40 ہزار ہو گی۔ غور کرو کہ یہ لکیر کونہ (x,y)=(10,0) سے گزرتی ہے۔ اس طرح دوسرے کونوں کو مد نظر رکھتے ہوئے ہم ان مساوات
:\ 4 x + 9 y = 50
:\ 4 x + 9 y = 54
کے مطابق متوازی سرخ لکیریں لگاتے ہیں۔ اب یہ واضح ہے کہ کونہ (نکتہ) (x,y)=(0,6) پر سب سے زیادہ آمدنی (54 ہزار) ہے۔ اس لیے حل یہ ہے کہ 0 ایکڑ پر گاجر کاشت کی جائے اور 6 ایکڑ پر مٹر (یعنی صرف 6 ایکڑ رقبے پر مٹر کاشت کرو اور باقی 4 ایکڑ فارغ چھوڑ دو)۔

غور کرو کہ نیلی اور کالی لکیریں نکتہ (x,y)=(8,2) پر ملتی ہیں، جو ان یکلخت لکیری مساوات کا حل ہے۔ مگر یہ حل اس مسلئہ کا حل نہیں چونکہ اس میں آمدنی کا خیال نہیں رکھا گیا۔

حل نکالتے ہوئے ایک دلچسپ بات یہ دیکھنے میں آئی کہ کثیرالاضلاع کے صرف کونوں پر تلاش کرنے سے حل نکل آتا ہے، کثیرالضلاع کے اندر کے نکتوں کو پرکھنے کی ضرورت نہیں ہوتی۔

اگر ہم منڈی کی قیمت بدلیں تو حل بھی بدل سکتا ہے۔ مثلاً اگر مٹر کے 9 ہزار ملتے ہوں اور گاجر کے 6 ہزار، یعنی
:\ f(x,y) = 6 x + 9 y
تو حل نکتہ (x=8,y=2) ہو گا اور آمدنی 66 ہزار۔
مثال 2

اگر اوپر کی مثال میں ایک فصل زیادہ کر دیں:
:ایک کاشتکار کے پاس 10 ایکڑ زمین ہے جس پر وہ مٹر، گاجر اور ٹماٹر کی فصل کاشت کرنا چاہتا ہے۔ گاجر، مٹر اور ٹماٹر کے ایکڑوں کو \ x_1, x_2, x_3 کہتے ہوئے
:\ x_1 + x_2 + x_3 \le 10
:\ x_1 \ge 0, x_2 \ge 0, x_3 \ge 0
اب منڈی میں مٹر کی فی ایکڑ پیداوار کے 9 ہزار روپے ملتے ہیں جبکہ گاجر کی ایک ایکڑ پیداوار کے 4 ہزار روپے اور ٹماٹر کے 7 ہزار روپے فی ایکڑ۔
:\ f(x_1, x_2, x_3) = 4 x_1 + 9 x_2 + 7 x_3
مٹر کی فصل میں ہر ایکڑ کے لیے 2 میٹرک ٹن کھاد درکار ہوتی ہے جبکہ گاجر کی فصل کے لیے 1 میٹرک ٹن فی ایکڑ اور ٹماٹر کی فصل کے لیے 3 میٹرک ٹن فی ایکڑ۔ فرض کرو کہ کاشتکار کو صرف 12 میٹرک ٹن کھاد دستیاب ہے۔
:\ 1 x_1 + 2 x_2 + 3 x_3 \le 12
مٹر کی فصل کو 10 دن فی ایکڑ مزدوری چاہیے ہوتی ہے، گاجر کو 6 دن فی ایکڑ اور ٹماٹر کو 11 دن فی ایکڑ۔ کل 100 دن کی مزدوری میسر ہے۔
:\ 6 x_1 + 10 x_2 + 11 x_3 \le 100
ہمیں یہ ڈھونڈنا ہے کہ کتنے ایکڑ پر مٹر اُگائے جائیں، کتنے پر گاجر اور کتنے پر ٹماٹر، تاکہ کاشتکار کو زیادہ سے زیادہ آمدنی ہو۔

اب دیکھو کہ یہ مسلئہ تین متغیر میں ہے۔ اس کا کثیرالاضلاع سہ العبادی ہو گا۔ اس سے واضح ہوا کہ جب متغیر کی تعداد زیادہ ہو تو ہندسیہ کی مدد سے کثیرالاضلاع کا تصور کر کے اس کے کونے ڈھونڈنا ممکن نہیں رہتا۔ خوش قسمتی سے بسیط (simplex) کا ایسا طریقہ موجود ہے جس کے استعمال سے تصور کرنے کی ضرورت نہیں رہتی اور ایک میکانکی طریقہ استعمال کرتے ہوئے ایک کونے \ (x_1, x_2, \cdots, x_n) سے دوسر ے کونے، چھلانگیں اس طرح لگائی جا سکتی ہیں کہ ہر چھلانگ میں فنکشن کی قیمت میں اضافہ ہوتا جائے اور بالآخر سب سے بہتر حل نکل آئے۔
ثنویت

بائیں|تصغیر|ثنویت
اوپر دیا لکیری پروگرامنگ کا مسلئہ، یعنی:
: تکبیر \ f(X) = c^t X
:جبکہ یہ لوازمات پورے ہوں
:\ AX \le b
:\ X \ge 0
مقدم مسلئہ کہلاتا ہے۔

اس مسلئہ کے ساتھ انتہای قریبی تعلق رکھنے والا مسلئہ:
: تصغیر \ g(Y) = b^t Y
:جبکہ یہ لوازمات پورے ہوں
:\ A^tY \ge c
:\ Y \ge 0
ثنوی مسلئہ کہلاتا ہے۔
(یہاں الفاظ "تکبیر" اور "تصغیر" صرف و نحو کے حوالے سے فعل ہیں۔)

ان دونوں مسلئوں کا گہرا تعلق نیچے دیہ ہے:

اگر X اور Y ایسے سمتیہ ہیں جو بالترتیب مقدم اور ثنوی مسائل کے لوازمات پورے کرتے ہیں، تو
# \ f(X) \le g(Y)
# اگر ان X اور Y کے لیے، مساوات \ f(X)=g(Y) ہو، تو یہ X اور Y ان مسائل کے کامل حل ہیں (یعنی X مقدم مسلئہ کی فنکشن f() کی تکبیر کرتا ہے اور Y ثنوی مسلئی کی فنکشن g() کی تصغیر کرتا ہے)۔ کامل حل کو عموماً X^* اور Y^* لکھا جاتا ہے (تصویر)۔

جب بسیط کے طریقہ سے لکیری پروگرامنگ مقدم مسلئہ کا حل X نکالا جاتا ہے، تو اس دوران ثنوی مسلئہ کا حل Y بھی ساتھ ہی نکل آتا ہے۔
ثنوی مسلئہ اثباتی

اگر مقدم اور اس کے ثنوی لکیری پروگرامنگ مسلئہ دونوں ممکن ہوں، تو دونوں کا کامل حل موجود ہو گا اور مقدم مسلئہ کا کبیر برابر ہو گا ثنوی مسلئہ کے صغیر کے۔ اگر ان میں سے ایک مسلہ ناممکن ہو، تو دوسرے مسلہ کا کامل حل موجود نہیں ہوتا۔
مثال 3

اوپر مثال 1 میں مقدم مسلئہ کو یوں لکھا جا سکتا ہے
:تکبیر
:f(x_1, x_2) = \begin{bmatrix} 4 & 9 \end{bmatrix}
\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}

:جبکہ
:\begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}
\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}
\le \begin{bmatrix} 10 \\ 12 \end{bmatrix}


اب ثنوی مسلئہ کو یوں سمجھا جا سکتا ہے۔ فرض کرو کہ کوئی شخص کاشتکار سے ساری کھاد (بارہ میٹرک ٹن) خریدنا چاہتا ہے اور زمیں (دس ایکڑ) فصل کے دورانیہ کے لیے کرائے پر لینا چاہتا ہے۔ اب اس شخص کا مسلئہ یہ ہو گا کہ کاشتکار کو کیا قیمت کی پیشکش کرے۔ یہ شخص ایک ایکڑ کے کرائے کی قیمت y_1 روپے لگاتا ہے اور کھاد کی فی میٹرک ٹن قیمت y_2 روپے لگاتا ہے، تو پوری قیمت یہ بنی
:g(y_1,y_2) = 10 y_1 + 12 y_2
ظاہر ہے کہ یہ شخص کم سے کم قیمت لگانا پسند کرے گا۔

چونکہ ایک ایکڑ زمین اور ایک میٹرک ٹن کھاد کے استعمال سے چار ہزار روپے مالیت کی گاجر پیدا ہوتی ہے، اس لیے کاشتکار یہ سودا اسی وقت قبول کرے گا جبکہ
: 1 y_1 + 1 y_2 \ge 4
اور چونکہ ایک ایکڑ زمین اور دو میٹرک ٹن کھاد کے استعمال سے نو ہزار روپے مالیت کا مٹر پیدا ہوتا ہے، اس لیے کاشتکار یہ سودا اسی وقت قبول کرے گا جبکہ
: 1 y_1 + 2 y_2 \ge 9

تو ثنوی لکیری پروگرامنگ مسلئہ یہ بنا
:تصغیر
:g(y_1, y_2) = \begin{bmatrix} 10 & 12 \end{bmatrix}
\begin{bmatrix} y_1 \\ y_2 \end{bmatrix}

:جبکہ
:\begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}
\begin{bmatrix} y_1 \\ y_2 \end{bmatrix}
\ge \begin{bmatrix} 4 \\ 9 \end{bmatrix}


اس مسلئہ کا حل نکالا جائے تو کل قیمت 54 ہزار ہی نکلے گی اور y_1=0،
y_2=4.5۔ یعنی اپنی دانست میں یہ شخص کھاد کی قیمت ساڑھے چار پزار روپے فی میٹرک ٹن لگائے اور زمین کا کرایہ صفر۔

اس مثال میں ہم نے یہ عجیب بات دیکھی کہ زمین کی قیمت صفر لگی۔ ثنوی لکیری پروگرامنگ مسائل میں ان قیمتوں کو پرچھائیں قیمتیں (shadow prices) کہا جاتا ہے۔ اس کا یہ مطلب نہیں کہ زمین کی کوئی وقعت نہیں۔ صرف یہ کہ منڈی (مارکیٹ) کے حوالے سے اس ایک مسلئہ کے تناظر میں ان اشیاء کا بھاؤ یہ (پرچھائیں قیمت) لگا۔
مزید دیکھیے

* خطی الجبرا
* سائیلیب help linpro, help readmps
بیرونی روابط

* سائیلیب سبق
* LiPS
* بہت زیادہ متغیر میں لکیری پروگرامنگ مسلئہ کے کمپیوٹر پر حل کے لیے lpsolve


زمرہ:تحقیق عملیات
زمرہ:ریاضیاتی کاملیت
زمرہ:ویکی ڈیٹا سے مختلف مختصر وضاحت
زمرہ:Harv اور Sfn کے بدون ہدف نقائص