سائلیب/باب 20

لکیری پروگرامنگ کی ایک مثال سائلیب کی مدد سے حل کرتے ہیں۔ وکیپیڈیا پر یہ مثال ہم نے گراف کی مدد سے حل کی تھی۔

مثال 1

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

فرض کرو کہ گاجر x ایکڑ پر کاشت کی جاتی ہے اور مٹر y ایکڑ پر۔ اب چونکہ کل رقبہ 10 ایکڑ ہے، اس لیے

$\ x+y\leq 10$

کھاد مٹرکو 2 میٹرک ٹن فی ایکڑ، اور گاجر کو 1 میٹرک ٹن فی ایکڑ۔ جبکہ کاشتکار کے پاس کھاد کی ساری مقدار 12 میٹرک ٹن ہے، اس لیے

$\ x+2y\leq 12$

اس کے علاوہ چونکہ زیر کاشت رقبہ منفی نہیں ہو سکتا، اس لیے

$\ x\geq 0$

$\ y\geq 0$

مٹر کی قیمت 9 ہزار فی ایکڑ اور گاجر کی قیمت 4 ہزار فی ایکڑ کے حساب سے کاشتکار کی آمدنی ہو گی

$\ f(x,y)=4x+9y$

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

سائلیب میں یہ مسئلہ linpro کی مدد سے حل کیا جاتا ہے۔ منافع فنکشن کے لیے ہم لکھتے ہیں:

--> p = [ 4 ; 9]
p =
    4
    9

تو منافع فنکشن یہ ہوئی (میٹرکس صورت میں)

$f(x,y)=p^{t}{\begin{bmatrix}x\\y\end{bmatrix}}$

اب نامساوات کو میٹرکس صورت یوں لکھ کر

${\begin{bmatrix}1&1\\1&2\end{bmatrix}}{\begin{bmatrix}x\\y\end{bmatrix}}\leq {\begin{bmatrix}10\\12\end{bmatrix}}$

یا

$C{\begin{bmatrix}x\\y\end{bmatrix}}\leq b$

جو سائلیب کی زبان میں یوں کہہ سکتے ہیں

--> C = [ 1  1; 1 2];
--> b = [ 10 ; 12];

اب سائلیب کو بتاتے ہیں کہ x اور y کی کم سے کم (min) اور زیادہ سے زیادہ (max) قیمت کیا ہو سکتی ہے:

--> cmin = [ 0 ; 0];
--> cmax = [ 10 ; 10];

چونکہ سائلیب linpro منافع فنکشن کی بجائے نقصان فنکشن استعمال کرتی ہے اس لیے ہم اسے منفی p بتاتے ہیں۔ آخری صفر کا مطلب ہے کہ C, b میں سب نامساوات ہیں (مساوات کوئی نہیں)

--> [X, lag, f] = linpro(-p, C, b, cmin, cmax, 0)
--> f =
    -54
    X =
       0
       6

تو جواب یہ آیا

${\begin{bmatrix}x\\y\end{bmatrix}}={\begin{bmatrix}0\\6\end{bmatrix}}$

یعنی گاجر کاشت نہ کی جائے، اور مٹر چھ ایکڑ پر کاشت کیا جائے۔ اور منافع ہو گا 54 ہزار۔

---

مثال 3 کے لیے لکیری پروگرامنگ میں ثنویت کی تعریف ملاحظہ کریں۔

مثال 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}}\leq {\begin{bmatrix}10\\12\end{bmatrix}}$

اب ثنوی مسئلہ کو یوں سمجھا جا سکتا ہے۔ فرض کرو کہ کوئی شخص کاشتکار سے ساری کھاد (بارہ میٹرک ٹن) خریدنا چاہتا ہے اور زمیں (دس ایکڑ) فصل کے دورانیہ کے لیے کرائے پر لینا چاہتا ہے۔ اب اس شخص کا مسئلہ یہ ہو گا کہ کاشتکار کو کیا قیمت کی پیشکش کرے۔ یہ شخص ایک ایکڑ کے کرائے کی قیمت $y_{1}$ روپے لگاتا ہے، اور کھاد کی فی میٹرک ٹن قیمت $y_{2}$ روپے لگاتا ہے، تو پوری قیمت یہ بنی

$g(y_{1},y_{2})=10y_{1}+12y_{2}$

ظاہر ہے کہ یہ شخص کم سے کم قیمت لگانا پسند کرے گا۔

چونکہ ایک ایکڑ زمین اور ایک میٹرک ٹن کھاد کے استعمال سے چار ہزار روپے مالیت کی گاجر پیدا ہوتی ہے، اس لیے کاشتکار یہ سودا اسی وقت قبول کرے گا جبکہ

$1y_{1}+1y_{2}\geq 4$

اور چونکہ ایک ایکڑ زمین اور دو میٹرک ٹن کھاد کے استعمال سے نو ہزار روپے مالیت کا مٹر پیدا ہوتا ہے، اس لیے کاشتکار یہ سودا اسی وقت قبول کرے گا جبکہ

$1y_{1}+2y_{2}\geq 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}}\geq {\begin{bmatrix}4\\9\end{bmatrix}}$

سائلیب میں اس کا حل یوں نکلے گا۔

--> p = [ 4 ; 9]
p =
    4
    9

--> C = [ 1  1; 1 2];
--> b = [ 10 ; 12];

--> cmin = [ 0 ; 0];
--> cmax = [ 10 ; 10];

اب چونکہ linpro کو نامساوات کی "کم" صورت چاہیے، اس لیے ہم C اور b کو منفی لکھیں گے۔ یعنی

$-{\begin{bmatrix}1&1\\1&2\end{bmatrix}}{\begin{bmatrix}y_{1}\\y_{2}\end{bmatrix}}\leq -{\begin{bmatrix}4\\9\end{bmatrix}}$

چونکہ g نقصان فنکشن ہی ہے، اس لیے p کو مثبت ہی رہنے دیں گے

--> [Y, lag, g] = linpro(p, -C, -b, cmin, cmax, 0)
--> g =
    54
    Y =
       0
       4.5

اس مسئلہ کا حل یہ نکالا کہ کل قیمت 54 ہزار ہی نکلے گی، اور $y_{1}=0$، $y_{2}=4.5$۔ یعنی اپنی دانست میں یہ شخص کھاد کی قیمت ساڑھے چار پزار روپے فی میٹرک ٹن لگائے، اور زمین کا کرایہ صفر۔