لکیری برمجہ

وکیپیڈیا سے

Linear programming

لکیری برمجہ ریاضی کی ایک تکنیک ہے جس میں ایسے مسلئے حل کیے جاتے ہیں جن میں ایک اقتصادی منافع فنکشن کو زیادہ سے زیادہ کرنا مقصود ہوتا ہے۔ مثلاً ایک کارخانہ میں مختلف اشیا کی تعداد $\ 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]$

[ترمیم کریں] مثال

ایک کاشتکار کے پاس 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$

جسے وہ زیادہ سے زیادہ کرنا چاہتا ہے۔

تصویر میں مساوات $\ 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 ہزار۔

[ترمیم کریں] مثال

اگر اوپر کی مثال میں ایک فصل زیادہ کر دیں:

ایک کاشتکار کے پاس 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)$ سے دوسر ے کونے، چھلانگیں اس طرح لگائی جا سکتی ہیں کہ ہر چھلانگ میں فنکشن کی قیمت میں اضافہ ہوتا جائے اور بالآخر سب سے بہتر حل نکل آئے۔

[ترمیم کریں] اور دیکھو

لکیری الجبرا
سائیلیب help linpro, help readmps

[ترمیم کریں] بیرونی روابط

سائیلیب سبق
بہت زیادہ متغیر میں لکیری برمجہ مسلئہ کے شمارندہ پر حل کے لیے lpsolve

              اردو ویکیپیڈیا پر مساوات کو بائیں سے دائیں (LTR) پڑھیۓ           ریاضی علامات

Retrieved from "http://ur.wikipedia.org../../../%D9%84/%DA%A9/%DB%8C/%D9%84%DA%A9%DB%8C%D8%B1%DB%8C_%D8%A8%D8%B1%D9%85%D8%AC%DB%81.html"

زمرہ: ریاضیات

We provide Linux to the World

لکیری برمجہ

وکیپیڈیا سے

فہرست

[ترمیم کریں] لکیری برمجہ مسلئہ

[ترمیم کریں] میٹرکس صورت

[ترمیم کریں] مثال

[ترمیم کریں] مثال

[ترمیم کریں] اور دیکھو

[ترمیم کریں] بیرونی روابط

Views

رہنمائی

ساتھی منصوبے

تلاش

دیگر زبانیں