"لکیری برمجہ" کے نسخوں کے درمیان فرق

دوسرے خام مال کے لیے اسی صورت علاحدہ نامساوات لکھی جا سکتی ہے۔ اس کے علاوہ مزدوری وغیرہ کی نامساوات بھی لکھی جا سکتی ہیں۔

 

تو لکیری پروگرامنگ مسلئہ یہ بنا کہ متغیر <math>\ x_1, x_2, \cdots, x_n</math> کی ایس قیمتیں ڈھونڈو کہ منافع فنکشن

:<math>\ f(x_1, x_2, \cdots, x_n) = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n</math>

کی بھی تسکین ہو۔

 

اس مسلئہ کو [[میٹرکس]] صورت یوں لکھا جا سکتا ہے:

[[سمتیہ]] (بصورت میٹرکس)

\right]</math>

 

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

 

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

 

 

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

تو حل نکتہ <math>(x=8,y=2)</math> ہو گا اور آمدنی 66 ہزار۔

 

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

:ایک کاشتکار کے پاس 10 ایکڑ زمین ہے جس پر وہ مٹر، گاجر اور ٹماٹر کی فصل کاشت کرنا چاہتا ہے۔ گاجر، مٹر اور ٹماٹر کے ایکڑوں کو <math>\ x_1, x_2, x_3</math> کہتے ہوئے

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

 

{{اصطلاح برابر|ثنویت<br> تکبیر <br> تصغیر <br> مقدم <br> ثنوی <br> کامل <br> بسیط <br>ممکن؟|

Duality <br> Maximize <br> Minimize <br> Primal <br> Dual <br> Optimal <br> Simplex

<br> feasible}}

اوپر دیا لکیری پروگرامنگ کا مسلئہ، یعنی:

: تکبیر <math>\ f(X) = c^t X</math>

اگر ''X'' اور ''Y'' ایسے سمتیہ ہیں جو بالترتیب مقدم اور ثنوی مسائل کے لوازمات پورے کرتے ہیں، تو

# <math>\ f(X) \le g(Y)</math>

 

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

 

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

 

اوپر مثال 1 میں مقدم مسلئہ کو یوں لکھا جا سکتا ہے

:تکبیر

* [[سائیلیب]] help linpro, help readmps

 

* [http://sourceforge.net/projects/lipside/ LiPS]

* بہت زیادہ متغیر میں لکیری پروگرامنگ مسلئہ کے کمپیوٹر پر حل کے لیے [http://sourceforge.net/projects/lpsolve lpsolve]