باب12

خطی پروگرامنگ

(LINEAR PROGRAMMING)

٭ ایک طالب علم کا ریاضیاتی تجربہ نامکمل ہے اگر اسے خودہی ایجاد کیے ہوئے مسئلہ کو حل کرنے کا موقع نہیں ملا ہو—جی۔پولیا ٭

12.1  تعارف(Introduction)

پچھلی جماعتوں میں ہم نے خطی مساواتوں کے نظام اور روزمرہ کے مسئلوں میں ان کے استعمال پر بحث کی ہے۔گیارھویں جماعت میں ہم نے خطی نامساواتوں اور دومتغیرمیں خطی نامساواتوں کے نظام اورگرافی طریقہ کے ذریعے حل کے بارے میں پڑھا ہے۔ریاضی کے بہت سے استعمال میں نامساوات/مساوات کا نظم شامل ہوتا ہے۔اس باب میں ہم ذیل میں دییے گئے کچھ حقیقی زندگی کے مسئلوں کا حل خطی نامساواتوں/مساواتوں کے نظام کو عمل میں لاکر کریں گے۔

ایک فرنیچر کا تاجر صرف دوطرح کی اشیا کا کاروبار کرتا ہے۔ میزیں اور کرسیاں۔ اس کے پاس صرف کرنے کے لیے50,000روپیے ہیں،اور زیادہ سے زیادہ60اشیا کو رکھنے کی جگہ ہے۔ ایک میز کی قیمت2500روپیے اور ایک کرسی کی 500روپیے ہے۔اس کا تخمینہ ہے کہ ایک میز کی فروخت سے اسے250روپیے کا منافع ہوگا اور ایک کرسی کی فروخت سے75روپیے کامنافع حاصل ہوگا۔ وہ یہ جانناچاہتا ہے کہ موجودہ رقم سے وہ کتنی میزیں اور کتنی کرسیاں خریدے تاکہ اس کا منافع زیادہ سے زیادہ ہو،یہ مانتے ہوئے کہ جتنی اشیاوہ خریدتا ہے وہ تمام اشیافروخت کرسکے گا۔

اس طرح کے مسئلے جو زیادہ سے زیادہ (یاکم سے کم)منافع چاہتے ہیں،مسئلہ کی عام جماعت بناتے ہیں،اوپٹیمائیزیشن مسئلہ(Optimisation problems) کہلاتے ہیں۔ اس لیے، استحسان مسئلہ میں زیادہ سے زیادہ منافع معلوم کرنا، کم سے کم قیمت یادستیاب ذرائع کا کم سے کم استعمال ہوسکتا ہے وغیرہ۔

ایک خاص لیکن ایک بہت اہم استحسان مسئلہ کی جماعت خطی پروگرامنگ مسئلہ ہے۔ اوپر بیان کیا گیا استحسان مسئلہ خطی پروگرامی مسئلے کی ایک مثال ہے۔خطی پروگرامی مسئلے بہت دلچسپ ہوتے ہیں کیونکہ صنعت،تجارت اور مینجمنٹ سائنس میں ان کا بہت زیادہ استعمال ہوتا ہے۔

اس باب میں ہم صرف گرافی حل کے ذریعہ کچھ خطی پروگرامی مسئلوں کا مطالعہ کریں گے، جب کہ اس طرح کے مسائل کو حل کرنے کے اوربھی بہت سے طریقے ہیں۔

12.2خطی پروگرامنگ مسئلہ اور ان کی ریاضیاتی تشکیل  

(Linear Programming Problem and its Mathematical Formulation)

ہم اپنی بحث فرنیچراورتاجر کی مندرجہ بالا مثال سے شروع کریں گے جو کہ ریاضیاتی مسئلہ کو دومتغیر کی تشکیل میں آگے لے جاتی ہے۔اس مثال میں ہم مشاہدہ کرتے ہیں:

(i) تاجر اپنی رقم میز میں خریدنے یا کرسیاں خریدنے اور دونوں کو اکٹھا کرنے میں صرف کرسکتا ہے۔ اس کے آگے وہ مختلف طریقے سے روپیے صرف کرکے مختلف منافع کما سکتا ہے۔

(ii) بہت سی مختلف چڑھتی ہوئی شرطیں یا پابندیاں ہیں، جس کی وجہ سے وہ زیادہ سے زیادہ50,000روپیے خرچ کرسکتا ہے اور اسی طرح اس کے پاس رکھنے کی جگہ جو کہ زیادہ سے زیادہ 60اشیا کے لیے ہے۔

مان لیجیے وہ صرف میزیں خریدنا چاہتا ہے اور کوئی کرسی نہیں،اس لیے وہ 2500÷50000، یعنی 20میزیں خرید سکتا ہے اس صورت میں اس کا منافع(250×20) ،یعنی 5000روپیے ہوگا۔

مان لیجیے وہ صرف کرسیاں ہی خریدنا چاہتا ہے اور کوئی میز نہیں۔وہ اپنی50,000روپیے کی رقم سے 500÷50,000 یعنی 100کرسیاں خریدسکتا ہے۔لیکن وہ صرف60اشیاہی رکھ سکتا ہے اس لیے اس پر صرف60کرسیاں ہی خریدنے کا دباو ہے۔ جو اسے کل منافع(60×75)یعنی 4500روپیے دے سکتا ہے۔

دیگرکئی ممکنات ہیں، مثال کے طورپر،وہ10میزیں اور50کرسیاں خریدتاہے،کیونکہ وہ صرف60اشیا ہی جمع کرسکتا ہے۔ اس صورت میں کل منافع(75×50+250×10)، یعنی 6250 روپیے ہوگااوراسی طرح آگے۔

اس طرح،ہم نے دیکھا کہ تاجر اپنی رقم کو مختلف طریقوں سے خرچ کرسکتا ہے اور اسے ان ہی طریقوں سے مختلف منافع ملے گا۔

اب مسئلہ یہ ہے کہ وہ اپنی رقم کس طرح خرچ کرے تاکہ منافع زیادہ سے زیادہ ہو؟ اس سوال کا جواب دینے کے لیے ہم مسئلہ کو ریاضیاتی طورپر قاعدہ کی شکل دیں۔

12.2.1مسئلہ کی ریاضیاتی تشکیل (Mathematical formulation of the problem) 

مان لیجیے میزوں کی تعدادx اورکرسیوں کی تعداد yہے جو کہ تاجر خریدتا ہے۔ صاف طورپر xاورyغیر منفی ہوں گے یعنی :

(1)........... x ≥ 0

(2)........... y ≥ 0 (غیرمنفی پابندی)

تاجر پر زیادہ سے زیادہ رقم خرچ کرنے کی پابندی ہے،(یہاں یہ50,000روپیے ہے) اوراشیاکی زیادہ سے زیادہ تعدادجمع کرنے کی(یہاں یہ60ہے)۔ریاضیاتی طورپر بیان کیا گیا ہے،

(سرمایہ کاری پر پابندی) 2500x + 500y ≤ 50000 

یا

(3)........... 5x + y ≤ 100

اور (ذخیرہ پر پابندی)      

(4)........... 5x + y ≤ 60

   تاجر اس طرح سے سرمایہ کاری کرنا چاہتا ہے تاکہ اسے زیادہ سے زیادہ منافع ہو،مان لیجیےZ جو کہ x اورyکے تفاعل کےطورپر بیان کیاگیا ہے اور اس طرح 

(جسے معروضی تفاعل کہتے ہیں)

(5)........... Z = 250x + 75y   

   ریاضیاتی طورپردیا ہوامسئلہ اب اس طرح چھوٹا ہوجاتا ہے

Z = 250x + 75y زیادہ سے زیادہ

پابندی پر منحصر:

5x + y ≤ 100

x + y ≤ 60

x ≥ 0,  y ≥ 0

اس لیے کچھ حالات کو مدد نظر رکھتے ہوئے ہمیں خطی تفاعل z کو بڑھانا ہوگا جوکہ خطی غیر مساوات کے سیٹ سے معلوم کیا گیا ہے اور جس کے متغیر غیر منفی ہیں۔ دوسرے اور کچھ مسئلہ بھی ہیں جہاں ہمیں کچھ حالات کے ساتھ تفاعل کو کم سے کم کرنا ہے جو کہ غیر منفی متغیر کے ساتھ ایک خطی غیر مساوات کے سیٹ سے معلوم کرنا ہے۔ اس طرح کے مسائل کو خطی پروگرامی مسئلے کہا جاتا ہے۔

اس طرح خطی پروگرامی مسئلہ وہ ہے جو احسن قدر (زیادہ سے زیادہ یا کم سے کم قدر) دریافت کرنے سے تعلق رکھتا ہے ایک خطیتفاعل (جسے معروضی فنکشن کہتے ہیں) بہت سے متغیروں کی (مان لیجیے xاور y) ، جس کے ساتھ یہ شرط ہے کہ متغیر غیر منفی ہیں اور خطی نامساواتوں کا سیٹ اسے مطمئن کرتا ہے (جسے خطی پابندیاں کہتے ہیں) خطی رکن کا مطلب ہے کہ مسئلہ میں استعمال کیے گئے تمام ریاضیاتی رشتے خطی رشتے ہیں جب کہ پروگرامی رکن ایک خاص پروگرام یا کام کے منصوبہ کو معلوم کرنے کے طریقے کی سفارش کرتا ہے۔

اس سے پہلے کے ہم آگے بڑھیں، اب ہم کچھ ارکان کو باضابطہ بیان کرتے ہیں (جوکہ اوپر استعمال کیے گئے ہیں) جو کہ ہم خطی پروگرامی مسئلوں میں استعمال کریں گے۔

معروضی تفاعل(Objective function)خطی تفاعل Z = ax + by، جہاں b،a مستقلہ ہیں، جنھیں زیادہ سے زیادہ یا کم سے کم تر کرنا ہے ایک خطی معروضی تفاعل کہلاتا ہے ۔

اوپر کی مثال میں Z=250x+75y ایک خطی معروضی تفاعل ہے۔متغیر x اور y فیصلہ کن متغیر(decision Veriables) کہلاتے ہیں۔

پابندیاں(Constraints) ایک خطی پروگرامی مسئلہ کے متغیر پر خطی نامساواتیں یا مساواتیں یا بندشیں، پابندیاں کہلاتی ہیں۔ شرطیںx≥ 0, y ≥ 0 غیر منفی پابندیاں کہلاتی ہیں۔ مندرجہ بالا مثال میں،(1)سے (4) نامساواتوں کا سیٹ پابندیاں ہیں۔

استحسان مسئلہ(Optimisation problem) ایک مسئلہ جو ایک خطی تفاعل (مان لیجیے دو متغیرx اورy کا) کم سے کم یا زیادہ سے زیادہ نکالنا چاہتے ہے جو کہ کچھ پابندیوں پر مبنی ہے اور خطی نا مساواتوں کے سیٹ کے ذریعہ معلوم کیا جاتا ہے ایک استحسان مسئلہ کہلاتا ہے۔ خطی پروگرامی مسئلہ خاص قسم کے استحسان مسئلے ہیں۔ مندرجہ بالا مسئلہ جو کہ ایک تاجر کے ذریعہ دی ہوئی رقم کو کرسیاں اور میزیں خرید کر خرچ کرنا ہے ایک استحسان مسئلہ کی مثال ہے اور ساتھ ہی یہ ایک خطی پروگرامی مسئلہ ہے۔

اب ہم اس پر بحث کریں گے کہ کس طرح ایک خطی پروگرامی مسئلہ کا حل معلوم کیاجاتا ہے۔ اس باب میں ہم صرف گرافی طریقوں کاہی استعمال کریں گے۔

12.2.2 خطی پروگرامی مسئلوں کو گرافی طریقہ سے حل کرنا

(Graphical method of solving linear programming problems)

گیارھویں جماعت میں ہم نے دو متغیروں xاورyمیں ملوث ایک خطی نامساوات کے نظام کو بنانے اور اس کا حل گراف کے ذریعے معلوم کرنے کے بارے میں پڑھا تھا۔ ہم سیکشن12.2میں بحث کیے گئے میز اور کرسیوں میں سرمایہ کاری کیے گئے مسئلہ کا حوالہ دیتے ہیں۔ہم اب اس مسئلہ کو گراف کے ذریعہ حل کریں گے۔ ہم بندشوں کا گراف بنانا چاہتے ہیں جس طرح خطی نامساواتیں بیان کی گئی ہیں۔

(1)……… 5x + y ≤ 100

(2)………    x + y ≤ 60

(3)……… x ≥ 0

(4)……… y ≥ 0

اس نظام کا گراف(شیڈ کیا ہوا حصہ ) دونقاط پر مبنی ہے جو آدھی مستوی پر مشترک ہیں اور جو کہ (1)سے(4)نامساواتوں کے ذریعے معلوم کی گئی ہیں(شکل12.1)۔اس علاقہ میں ہر ایک نقطہ ایک ممکن پسند کو ظاہر کرتاہے جو کہ تاجر کے لیے میزوں اورکرسیوں میں سرمایہ کاری کے لیے کھلاہے۔ اس لیے علاقہ مسئلہ کے لیے ممکن علاقہ کہلاتا ہے۔اس علاقہ کا ہر ایک نقطہ مسئلہ کا ممکن حل کہلاتا ہے۔اس طرح ہمارے پاس ہے،

معقول خطہ(feasible region) ایک خطی پروگرامی مسئلہ کا مشترکہ علاقہ جو کہ تمام پابندیوں سے معلوم کیاگیاہے اور جس میں غیرمنفی پابندیاںx, y≥ 0 بھی شامل ہیں مسئلہ کے لیے معقول حل کہلاتاہے۔ شکل12.1 میں، علاقہ OABC (شیڈڈ) مسئلہ کا معقول حل کہلاتا ہے۔ ممکن علاقہ کے علاوہ علاقہ ایک غیرممکن علاقہ(infeasible region) کہلاتاہے۔

معقول حل(Feasible solution)معقول  خطہ کی حد پر اور حد کے اندر نقاط پابندیوں کا معقول حل کہلاتا ہے۔شکل12.1میں ممکن علاقہOABCکی حدپر اور حد کے اندر ایک نقطہ مسئلہ کا ممکن حل ہے۔مثال کے طورپر(50, 10) مسئلہ کا معقول حل ہے اور اسی طرح نقاط(0,60)،(20,0)وغیرہ ہیں۔

معقول خطّہ کے باہر کوئی بھی نقطہ ایک غیر ممکن حل کہلاتا ہے۔ مثال کے طورپر،نقطہ(25,40) مسئلہ کا ایک غیر ممکن حل ہے۔

احسن( معقول)حل:(Optimal (feasible) Solution) کوئی بھی نقطہ معقول خطّہ میں جو کہ معروضی تفاعل کی احسن قدر (عظیم یا قلیل)دیتا ہے،احسن حل کہلاتا ہے۔

اب ہم دیکھتے ہیں کہ ممکن علاقہOABCمیں ہر ایک نقطہ تمام پابندیوں کو مطمئن کرتا ہے جیسا کہ(1) تا (4)میں دیاگیا ہے اور کیونکہ بہت سے لاتعدادنقاط ہیں،ظاہر نہیں ہے کہ ہم کس طرح نقطہ کو معلوم کریں جو کہ معروضی تفاعل Z = 250x + 75yکی عظیم قدر دے۔ اِن حالات سے نمٹنے کے لیے ہم ذیل مسئلہ کا استعمال کرتے ہیں جو کہ خطی پروگرامی مسئلہ کو حل کرنے کے لیے بنیادی ہے۔ان مسئلوں کا ثبوت اس کتاب کی حدود سے باہر ہے۔

مسئلہ1:مان لیجیے ایک خطی پروگرامی مسئلہ کے لیےR ایک معقول خطّہ(محدب کثیر ضلعی) ہے اور معروضی تفاعل سےZ = ax + by ہے۔ جبZ ایک احسن قدر(عظیم یا قلیل) رکھتا ہے جہاں متغیر x اورyخطی نامساواتوں کی پابندی پر ظاہر کرنے پر مبنی ہیں، یہ احسن قدر ممکن علاقہ میں ایک کونے کے نقطہ پر ملنی چاہیے*

مسئلہ2:مان لیجیےRایک خطی پروگرامی مسئلہ کے لیے ممکن علاقہ ہے،اور مان لیجیے Z = ax + byایک معروضی تفاعل ہے۔ اگر Rکی حدود** (bounded)ہیں، تب معروضی تفاعلZ،Rپر دونوں عظیم اورقلیل قدریں رکھتا ہے،اوراس میں سے ہر ایکRکے کونے کے نقطہ پر ملتی ہے

ریمارک:اگر Rلامحدود ہے، تب ہوسکتا ہے معروضی تفاعل کی عظیم یا قلیل قدر وجود میں نہ ہو۔ حالانکہ،اگر یہ وجود میں ہے ، تویہRکے ایک کونے کے نقطہ پرہوسکتی ہے(مسئلہ 1سے)

اوپرکی مثال میں محدود(ممکن )علاقہ کے کونے کے نقاطO,A,Bاور Cہیں اور ان کے مختصات بالترتیب جیسے(0, 0)، (20, 0)،  (50, 10)اور(60, 0) معلوم کرنا آسان ہے۔اب ہم Z  کی ان قدروں کا ان نقاط پر حساب لگاتے ہیں، 

ہمارے پاس ہے۔

عظیم

* ایک معقول خطّہ کا ایک کونے کا نقطہ علاقہ میں وہ نقطہ ہے جو کہ حدود خطوط کا تقاطع ہے۔

** ایک خطی نامساواتوں کے نظام کا معقول خطّہ میں اس وقت محدود کیاجاتا ہے جب کہ یہ ایک دائرہ میں بندکیاجاسکے۔ ورنہ یہ لامحدود ہے۔ غیرمحدود کا مطلب ہے کہ اس کا معقول خطّہ کسی بھی سمت میں لامحدود پھیل سکے۔

 خطی پروگرامی مسئلہ کے حل کرنے کے اس طریقے کو کارنر نقطہ طریقہ کہتے ہیں۔

 یہ طریقہ ذیل مراحل پر مبنی ہے۔

1۔ خطی پروگرامی مسئلہ کا معقول خطّہ معلوم کیجیے اور اس کے کارنر کے نقاط (راس) معلوم کیجیے یاتوجانچ (inspection) کے طریقے سے یا ایک نقطہ پر دونقاط خطوط کی دومساوات کو حل کرنے کے طریقے سے۔

2۔ ہرکونے پر معروضی تفاعلZ = ax + byکی قیمت کااندازہ لگائیے۔ مان لیجیےMاورmبالترتیب ان نقاط کی زیادہ سے زیادہ اور کم سے کم قدروں کو ظاہر کرتے ہیں۔

3۔ (i) جب ممکن علاقہ محدود ہے،MاورZ،mکی عظیم اورقلیل قدریں ہیں۔

     (ii) اگر کسی کیس میں،ممکن علاقہ غیر محدود ہے،ہمارے پاس ہے:

4۔ (Z  (a کی عظیم قدرMہے،اگر ممکن علاقہ کے ساتھ کھلی ہوئی آدھی مستوی جو کہax + by>M   سے معلوم کی گئی ہے، کے ساتھ کوئی مشترک نقطہ نہیںرکھتی۔ورنہzکی کوئی عظیم قدرنہیں ہے۔

(b) اسی طرح،Z، mکی قلیل قدر ہے،اگر کھلی ہوئی آدھی مستوی جو کہax + by < mسے معلوم کی گئی ہے،معقول خطّہ کے ساتھ کوئی مشترک نقطہ نہیں رکھتی۔ورنہ Zکی کوئی قلیل قدر نہیں ہے۔

اب ہم کچھ مثالوں کومد نظررکھتے ہوئے ان اقدامات کو کارنر نقطہ طریقے سے سمجھائیں گے۔

مثال1:   ذیل خطی پروگرامی مسئلہ کو گراف کے ذریعہ حل کیجیے:

(1) ... زیادہ سے زیادہZ = 4x + y

معروضی پابندی کے ساتھ

(2)...... x + y ≤ 50

(3)....... 3x + y ≤ 90

(4).......    x ≥ 0, y ≥ 0

حل: شکل12.2میں شیڈڈ علاقہ،ممکن علاقہ ہے جو کہ(2) تا (4)پابندیوں کے نظام سے معلوم کیاگیا ہے۔ہم مشاہدہ کرتے ہیں کہ معقول خطّہ OABCمحدود ہے۔اس لیے، اب ہم Zکی عظیم قدر معلوم کرنے کے لیے کارنر نقطہ طریقہ کا استعمال کرتے ہیں۔

کارنرنقاطB،A،O اور Cکے مختص بالترتیب(0, 0), (0, 30),(30, 20) اور(50, 0)ہیں۔ اب ہم Z کا حساب ہر کارنر نقطہ پر لگاتے ہیں۔

عظیم 

شکل 12.2

اس لیے، نقطہ(0, 30)پر Z کی عظیم قدر120ہے۔

مثال2:   ذیل خطی پروگرامی مسئلہ کو گراف کے ذریعے حل کیجیے

(1) ... Z = 200 x + 500 yکم سے کم

پابندی پر منحصر

(x + 2y ≥ 10 .... ...(2

(3x + 4y ≤ 24  ........(3

(x ≥ 0, y≤ 0     .........(4

حل: شکل12.3میں شیڈڈعلاقہ ABCمعقول خطّہ ہے جو کہ(2) تا (4)پابندیوں کے نظام سے معلوم کیے گئے ہیں اورحدود میں ہیں۔ کارنرنقاطA،BاورCکے مختصات بالترتیب (0,5)،(4,3)اور(0,6)ہیں۔ اب ہم ان نقاط پرZ  = 200x + 500yکی قدر کااندازہ لگائیں گے۔

 اس لیے،Zکی کم ازکم قدر2300ہے جو کہ نقطہ(4,3)پر ہے۔

عظیم 

مثال3: ذیل مسئلہ کو گراف کے ذریعے حل کیجیے۔

(Z = 3x + 9y ...(1 کم سے کم اورزیادہ سے زیادہ

پابندی پر منحصر:

(x + 3y ≤ 60 ...(2 

(x + y ≥ 10 ...(3 

(x ≤ y ...(4

x ≥ 0, y ≥ 0 ...(5 

حل:سب سے پہلے ہم(2) تا (5)خطی نامساواتوں کے نظام کے معقول خطّہ کاگراف کھینچتے ہیں۔معقول خطّہABCDشکل 12.4 میں دکھایاگیا ہے۔نوٹ کیجیے کہ خطّہ حدود میں ہے ۔کارنرنقاط C،B،AاورDکے مختص بالترتیب (0,10), (5, 5),(15, 15) اور(20, 0) ہیں۔

قلیل 

عظیم 

(آپٹیکل حل کے ضعف)

اب ہمZکی قلیل اورعظیم قدریں معلوم کرتےہیں۔جدول سے، ہم معلوم کرتے ہیں کہ نقطہ(5,5) Bپرمعقول خطّہ میں Zکی قدر60ہے۔

ہر ایک معاملے میںZکی معقول خطّہ پر عظیم قدر دوکارنر نقاط (15,15) C اور(0,20) D پر 180ہے۔

ریمارک(Remark): مشاہدہ کیجیے کہ،اوپر کی مثال میں،مسئلہ کے کارنر نقاط C اورDپرکثیر احسن حل ہیں، یعنی،دونوں نقاط یکساں عظیم قدر180دیتے ہیں۔ اس طرح کے معاملوں میں،آپ دیکھ سکتے ہیں کہ قطع خطCDکے ہر ایک نقطہ پر جو کہ دوکارنر نقاطCاورDکو ملانے سے بنتا ہے،بھی یکسان عظیم قدر دیتا ہے۔ یہی اس کیس میں بھی صحیح ہے اگر دونقاط یکساں قلیل قدریں دیتے ہیں۔

مثال4:  معروضی تفاعل کی قلیل قدر گراف کے ذریعے معلوم کیجیے

(Z = – 50x + 20y ...(1

پابندیوں پرمبنی

(2x –y ≥ – 5 ...(2 

(3x +y ≥ 3   ...(3

(2x –3y ≤ 12 ...(4 

(x ≥ 0, y ≥ 0 ...(5

حل: سب سے پہلے ،ہمیں(2) یا (5)نامساواتوں کے نظام کے محدود علاقہ کا گراف بنانا چاہیے۔ ممکن علاقہ(شیڈڈ) شکل12.5 میں دکھایاگیا ہے۔مشاہدہ کیجیے کہ معقول خطّہ کھلاہوائے میں ہے۔

 اب ہمZکی قدر کااندازہ کارنر نقاط پر لگاتے ہیں۔

 سب سے  چھوٹا

شکل 12.5

اس جدول سے ہمیں کارنر نقطے(6,0) پر Z کی کم سے کم قدر300– حاصل ہوئی ہے۔کیا ہم کہہ سکتے ہیں کہ Zکی قلیل قدر 300–ہے؟ یہ نوٹ کرلیجیے کہ اگر خطّہ کی حدود ہوتیں،یہZکی کم سے کم قدرZکی قلیل قدر ہے(مسئلہ2)۔لیکن یہاں ہم دیکھتے ہیں کہ معقول خطّہ کھلا ہواہے۔اس لیے،Zکی قلیل قدر 300– بھی ہو سکتی ہے اور نہیں بھی۔اس کا فیصلہ کرنے کے لیےہم نامساوات کا گراف کھینچتے ہیں۔

50x + 20y < – 300–  (کارنر نقطہ طریقہ کا قدم 3 (ii)دیکھیے)

یعنی،  30 –> 5x + 2y –

جانچ کیجیے کہ کیا نتیجتاً کھلی ہوئی آدھی مستوی میں معقول خطّہ کے ساتھ نقاط مشترک ہیں یانہیں۔اگر اس میں نقاط مشترک ہیں، تب Zکی قلیل قدر300–نہیں ہوگی۔ ورنہ، 300–،Z کی قلیل قدر ہوگی۔

جیساکہ شکل12.5میں دکھایا گیا ہے، اس میں مشترک نقاط موجود ہیں۔اس لیےZ = –50 x + 20 yکی دی ہوئی پابندیوں کے ساتھ کوئی قلیل قدر نہیں ہے۔

اوپر کی مثال میں نقطہ(0,5)پر کیا آپ کہہ سکتے ہیں کہ z = – 50 x + 20 yکی عظیم قدر100ہے؟ اس کے لیے، جانچ کیجیے کہ کیا  کے گراف کے معقول خطّہ کے ساتھ مشترک نقاط ہیں(کیوں؟)

مثال 5 :   Z = 3x + 2y کوکم سے کم کیجیے

پابندیوں پر منحصر

(1) ... x + y≥8  

(2) ... 3x + 5y ≤15  

(3) ... x ≥ 0, y≥0  

حل:  ہم (1) تا (3)نامساواتوں کے گراف کھینچتے ہیں(شکل12.6)۔کیا کوئی معقول خطّہ ہے؟ ایسا کیوں ہے؟

شکل12.6سے،آپ دیکھ سکتے ہیں کہ کوئی ایسا نقطہ نہیں ہے جو ایک کے بعد ایک پابندیوں کو مطمئن کررہا ہو۔ اس لیے، مسئلہ کا کوئی معقول خطّہ نہیں ہے اور اس لیے کوئی معقول حل نہیں ہے۔

ریمارک(Remark): ان مثالوں سے جن پر ابھی تک ہم نے بحث کی ہے، ہم یہ غور کرتے ہیں کہ خطی پروگرامی مسئلہ کی کچھ عام خصوصیت ہیں:

(i) معقول خطّہ ہمیشہ محدب علاقہ ہے۔

(ii) معروضی تفاعل کا حل عظیم(یا قلیل)، ممکن علاقہ کے راس(کارنر) پر وجود میں آتا ہے۔اگر کارنر دونقاط معروضی تفاعل کی یکساں عظیم (یا قلیل) قدر دیتے ہیں، تب ان دونقاط سے ملنے والے قطعہ خط کا ہر ایک نقطہ یکساں عظیم(یاقلیل) قدر دے گا۔

مشق 12.1

ذیل خطی پروگرامی مسئلہ کو گراف کے ذریعے حل کیجیے:

1۔ Z =  3x + 4yکو زیادہ سے زیادہ کیجیے

پابندیوں پرمنحصر : x + y ≤ 4, x  ≥  0, y ≥ 0

2۔ Z = – 3x + 4 y کوکم سے کم کیجیے

ان پرمنحصر .x + 2y ≤ 8, 3x + 2y ≤ 12,  x  ≥  0, y ≥ 0

3۔ Z = 5x + 3y کوزیادہ سے زیادہ کیجیے

ان پر منحصر3x + 5y  ≤ 15, 5x + 2y ≤ 10, x  ≥ 0, y ≥ 0

4۔ Z = 3x + 5y کوکم سے کم کیجیے

تاکہx + 3y ≥ 3, x + y ≥ 2, x, y ≥ 0

5۔ Z = 3x + 2y کو زیادہ سے زیادہ کیجیے

ان پر منحصرx + 2y ≤ 10, 3x + y ≤ 15, x, y ≥ 0

6۔ Z = x + 2y کو کم سے کم کیجیے

اس پر منحصر2x + y ≥ 3, x + 2y ≥ 6, x, y ≥ 0

دکھائیے کہZ کا قلیل ترین دو سے زیادہ نقطوں پر واقع ہے ۔

7۔ Z = 5x + 10 yکوکم سے کم اورزیادہ سے زیادہ کیجیے

اس پر منحصر x + 2y  ≤ 120, x + y ≥ 60, x – 2y ≥ 0, x, y ≥ 0

8۔ Z = x + 2y کو کم سے کم اورزیادہ سے زیادہ کیجیے

اس پر منحصر ہے x + 2y ≥ 100, 2x – y ≤ 0, 2x + y ≤ 200; x, y ≥ 0

9۔ Z = – x + 2y کو زیادہ سے زیادہ کیجیے

ان پابندیوں پر منحصر ہےx ≥ 3, x + y ≥ 5, x + 2y ≥ 6, y ≥ 0

10۔ Z = x + yکو زیادہ سے زیادہ کیجیے

ان پابندیوں پر منحصر ہےx – y ≤ –1, –x + y ≤  0,  x, y ≥ 0

12.3مختلف قسم کے خطی پروگرامنگ مسائل

(Different Types of Linear Programming Problems)

کچھ اہم خطی پروگرامنگ مسئلوں کی ذیل میں فہرست بنائی گئی ہے۔

1۔ صنعت کاری مسئلے(Manufacturing problems):ان مسئلوں میں ہم مختلف اشیا کی اکائیوں کی تعداد معلوم کرتے ہیں جو کہ ایک فرم کے ذریعے تیار کی گئی ہوں اور بیچی گئی ہوں،جب کہ ہر اشیا کو ایک مخصوص انسانی طاقت، مشین پر لگاہوا وقت،اشیا کی ایک اکائی کو تیار کرنے یں مزدوری فی گھنٹہ، بنی ہوئی اشیا کی ایک اکائی کو رکھنے کی جگہ کا کرایہ وغیرہ وغیرہ درکار ہوں،تاکہ منافع زیادہ سے زیادہ ہوسکے۔

2۔ خوراک کے مسئلے(Diet problems):ان مسئلوں میں ہم،مختلف قسم کے ترکیبی/غذائیت والی اشیا کی قیمت کو معلوم کرتے ہیں جو کہ خوراک میں شامل کی گئی ہیں تاکہ مطلوبہ خوراک کی قیمت کم سے کم ہو،اور ساتھ ہی اس میں ہر ایک جزو ترکیبی/غذائیت والی اشیا کی تعداد کم سے کم ہو۔

3۔ نقل وحمل مسئلے(Transportation problems):ان مسئلوں میں ہم نقل وحمل شیڈیول معلوم کرتے ہیں تاکہ ایک اشیا کو ایک پلانٹ فیکٹری سے مختلف بازاروں میں لانے لے جانے میں جو کہ مختلف مقامات پر واقع ہیں کم سے کم رقم خرچ ہو۔

آئیے اب کچھ اس طرح کے خطی پروگرامنگ مسئلوں کو حل کریں:

مثال6: (خوراک کے مسئلہ):ایک ماہر خوراک دوطرح کے کھانوں کو اس طرح ملانے کی خواہش ظاہر کرتا ہے تاکہ مرکب میں وٹامن کی موجودگی اس طرح ہو کہ وٹامنAکی کم سے کم 8اکائیاں اوروٹامنCکی10اکائیاں۔ کھانہ’I‘ میں وٹامنAکی مقدار2 اکائی/فی کلوگرام اور وہ وٹامن Cکی مقدار’I‘ اکائی/فی کلوگرام ہو۔کھانہ IIمیں وٹامن Aکی مقدار’I‘ اکائی /فی کلوگرام اور وٹامن Cکی مقدار’2‘ اکائی/فی کلوگرام ہو۔ اس کھانہIکی قیمت خرید /لاگت50روپیے فی کلوگرام پڑتی ہے اور کھانہIIکی قیمت خرید(لاگت)70روپیے فی کلوگرام پڑتی ہے۔اس مسئلہ کو ایک خطی پروگرامی مسئلہ کے طورپر فارمولے کی شکل دیجیے تاکہ اس طرح کے مرکب کی لاگت کم سے کم ہو۔

حل:مان لیجیے کہ مرکب میں غذا ’I‘کی مقدارxکلوگرام اورکھانہ’II‘کی مقدارyکلوگرام ہے۔صاف طورپرx≥ 0, y≥ 0 ہے۔ ہم دیے ہوئے اعداد وشمار سے ذیل جدول بناتے ہیں:

کیوں کہ مرکب میں ہرحال میں وٹامنAکی8 اکائیاں اوروٹامنCکی10اکائیاں ہونی چاہیے ہیں،ہمارے پاس پابندیاں ہیں:

2x + y ≥ 8

x + 2y ≥10

Zکی،xکلوگرام کھاتہ’I‘اورyکلوگرام کھاتہ’II‘خریدنے کی کل قیمت ہے

Z = 50x +70y

اس لیے مسئلہ کی ریاضیاتی تشکیل یہ ہے:

(1) ... Z = 50x +70yکم سے کم کیجیے

پابندیوں پر منحصر:

 (2)..... 2x + y ≥ 8

(3)...... x + 2y ≥10

(4)....... x, y ≥ 0

نامساواتوں (2) تا (4) کا ہم گراف کھینچتے ہیں۔اس نظام کے ذریعہ معلوم کیا گیامعقول خطّہ شکل12.7میں دیاگیا ہے۔ یہاں دوبارہ،مشاہدہ کیجیے کہ معقول خطّہ کھلا ہوا  ہے۔

ہمZکی قیمت کا اندازہ کارنر نقاطپر کرتے ہیں۔

قلیل 

شکل 12.7

جدول میں ہم نے نقطہ(2,4) پرZکی کم ازکم قدر380معلوم کی ہے۔ کیا ہم کہہ سکتے ہیں کہZکی قلیل قدر380ہے؟ یادرکھیے کہ معقول خطّہ کھلا ہواہے۔ اس لیے، ہمیں نامساواتوں کا گراف کھینچنا ہوگا

50x + 70y <380   یعنی   5x + 7y < 38

یہ جانچ کرنے کے لیے کہ کیا کھلی ہوئی آدھی مستوی میں معقول خطّہ کے ساتھ کوئی نقطہ مشترک ہے۔شکل12.7سے ہم دیکھتے ہیں کہ اس میں کوئی نقطہ مشترک نہیں ہے۔ 

اس طرح،Zکی قلیل قدر380ہے جو کہ نقطہ(2,4)پر موجودہے۔اس لیے،ماہر خوراک کی مرکب کو ملانے کی احسن صلاحیت یہ ہوگی کہ وہ کھانہ’I‘ کا 2کلوگرام اورکھانہ’II‘کا 4کلوگرام ملائیے،اور اس خصوصیت کے ساتھ، مرکب کی کم سے کم قیمت 380روپیے ہوگی۔

مثال7: مقرر کرنے کا مسئلہ(Allocation problem):کسانوں کی ایک کوآپرٹیو سوسائٹی کے پاس دو طرح کی فصلیں XاورY اُگانے کے لیے 50 ہیکٹر زمین دستیاب ہے۔فصلXاورYسے منافع فی ہیکٹربالترتیب10,500روپیے اور 9000روپیے تخمینہ لگایا گیا ہے۔ کیڑے وغیرہ کومارنے کے لیےXاورYفصلوں کے لیے 20لیٹر اور10لیٹر فی ہیکٹر کی شرح سے جڑی بوٹی سے بنے ایک رقیق کا استعمال کرنا ہے اس کے آگے، 800لیٹر سے زیادہ ہر رقیق کو استعمال نہیں کرنا ہے تاکہ مچھلیاں اور جنگلی جانور جو اس تالاب کو استعمال کریں گے تو نقصان نہ ہو جہاں اس زمین سے کوڑاکرکٹ جمع ہوگا۔ہر ایک فصل کے لیے کتنی زمین مقرر کی جائے تاکہ سوسائٹی کا کل منافع زیادہ سے زیادہ ہو؟

حل: مان لیجیے فصلXکے لیےxہیکٹیراورفصلYکے لیےyہیکٹر زمین مقرر کی گئی ہے۔صاف طورپرx ≥ 0, y ≥ 0

فصلX  پر فی ہیکٹر منافع=10500روپیے

فصلYپر فی ہیکٹر منافع=9000روپیے

اس لیے،کل منافع=(10500x + 9000y)روپیے

مسئلہ کی ریاضیاتی تشکیل ذیل  طرح ہے:

Z =10500 x + 9000 y ،زیادہ سے زیادہ کیجیے

پابندیوں پر منحصر ہے:

(زمین پر مبنی پابندیاں) (x + y ≤50  ..........(1

(جڑی بوٹیوں سے بنے رقیق ہربیسائیڈ کے استعمال پر مبنی پابندی) 20x + 10y ≤800

  (2).......... 2x + y ≤ 80 یعنی

(3).......... x ≥ 0, y ≥0     (غیر منفی پابندیاں)

 ہم(1) تا (3)نامساواتوں کے نظام کا گراف کھینچتے ہیں۔ ممکن علاقہOABCشکل12.8میں(شیڈڈ) دکھایاگیا ہے۔ مشاہدہ کیجیے کہ معقول خطہ بندہو ا ہے۔

کارنرنقاطB،A،O اورCکے مختصات بالترتیب (0,0)،(40,0)،(30,20)اور(0,50) ہیں۔ہم ان راسوں پر معروضی تفاعل Z= 10500 x + 9000yکی قیمت کا اندازہ یہ معلوم کرنے کے لیے لگاتے ہیں کہ کون زیادہ سے زیاہ منافع دیتا ہے۔

عظیم 

اس لیے، سوسائٹی کو 4,95,000روپیے زیادہ سے زیادہ منافع فصلX کو30ہیکٹر اورفصلYکو20ہیکٹر زمین مقرر کرنے پر ملے گا۔

مثال8: صنعت کاری مسئلہ(Manufacturing problem) ایک صنعت کارکمپنی ایک اشیا کے دو ماڈلAاورBتیارکرتی ہے۔ ماڈل Aکے ہر ٹکڑے کو تیار کرنے میں 9گھنٹے کی محنت لگتی ہے اور مکمل کرنے میں کا ایک گھنٹہ کی محنت لگتی ہے۔ ماڈلBکے ہر ٹکڑے کو تیار کرنے میں12گھنٹے کی محنت لگتی ہے اور مکمل کرنے میں3گھنٹے کی محنت لگتی ہے۔تشکیل کرنے اورمکمل کرنے میں بالترتیب مزدوری کے 180اور30گھنٹے کی محنت دسیتاب ہے۔کمپنی ماڈلAکے ہرٹکڑے پر8000روپیے منافع اورماڈلBکے ہر ٹکڑے پر12000روپیے منافع کماتی ہے۔زیادہ سے زیادہ منافع حاصل کرنے کے لیے ماڈل AاورماڈلBکے کتنے ٹکڑے ایک ہفتہ میں تیار کیے جائیں؟ ایک ہفتہ میں زیادہ سے زیادہ منافع کیا ہے؟

حل: مان لیجیے ماڈلAکے ٹکڑوں کی تعدادxہے اور ماڈلBکے ٹکڑوں کی تعداد yہے۔تب

کل منافع (روپیہ میں) = 8000x +12000 y  

مان لیجیے Z = 8000 x + 12000 y

اب ہمارے پاس دئیے ہوئے مسئلہ کے لیے ریاضیاتی ماڈل ہے

(1)  ... Z = 8000 x + 12000 y (زیادہ سے زیادہ کیجیے)

پابندیوں پر منحصر:

(پابندیاں کی تشکیل کرنے پر)  9x + 12y ≤180 

(3x + 4y ≤60 ...(2 

(3) ... (پابندی مکمل کرنے پر) x + 3y ≤30

(4) ... (غیر–منفی پابندی) x ≥ 0, y ≥ 0

OABC(شیڈڈ)معقول خطّہ، جو کہ(2)تا(4)نامساواتوں کے ذریعہ حاصل کیاگیا شکل12.9میں دکھایاگیا ہے۔یہ نوٹ کیجیے کہ معقول خطّہ حدود میں ہے۔

ہمیں معروضی تفاعل Zکے ہر ایک کارنر نقطہ پر قیمت کا اندازہ لگاناچاہیے جیساکہ نیچے دکھایاگیا ہے:

عظیم 

ہمیں نقطہ(B (12, 6 پر Zکی عظیم قدر1,68,000حاصل ہوتی ہے۔ اس لیے، کمپنی ماڈل Aکے 12ٹکڑے اور ماڈل Bکے 6ٹکڑے تیار کرے تاکہ زیادہ سے زیادہ منافع کماسکے اور تب زیادہ سے زیادہ منافع1,68,000روپیے ہوگا۔

مشق12.2

1۔ ریشما کی خواہش ہے کہ وہ دوقسم کے کھانےPاورQ اس طرح ملائے تاکہ مرکب میں کم سے کم وٹامن Aکی مقدار 8 اکائیاں اوروٹامنBکی مقدار11اکائیاں ہوں۔کھانہ Pکی قیمت60روپیے فی کلوگرام اورکھانہQکی قیمت80 روپیے فی کلوگرام ہے۔کھانہPمیں وٹامن Aکی مقدار3اکائیاں فی کلوگرام ہے اوروٹامنBکی مقدار5اکائیاں فی کلوگرام ہے جب کہ کھانہQمیں وٹامن Aکی مقدار4اکائیاں فی کلوگرام ا وروٹامن Bکی مقدار2اکائیاں فی کلوگرام ہے۔ مرکب کی کم سے کم قیمت معلوم کیجیے۔

2۔ ایک قسم کے کیک میں200گرام آٹے کی ضرورت ہوتی ہے اور25گرام چربی کی(Fat)، اوردوسرے قسم کے کیک میں 100 گرام آٹے اور 50گرام چربی کی ضرورت ہے۔ تو یہ مانتے ہوئے کہ کیک بنانے میں استعمال ہونے والے دوسرے جزوترکیبی کی کوئی کمی نہیں ہے۔بتائیے کہ 5کلو گرام آٹے اور 1 کلو گرام چربی میں کیک کی زیادہ سے زیادہ کتنی تعداد تیار کی جا سکتی ہے۔ 

3۔ ایک فیکٹری ٹینس کے ریکٹ اورکرکٹ کے بلے بناتی ہے۔ ٹینس کا ایک ریکٹ کو تیارکرنے میں مشین1.5گھنٹے لیتی ہے اور دستکار اسے مکمل کرنے میں3گھنٹے لیتاہے جب کہ ایک کرکٹ کابلابنانے میں مشین3گھنٹے لیتی ہے اور دستکار1 گھنٹہ کاوقت لیتا ہے۔ایک دن میں، فیکٹری کے پاس مشین کے 42 گھنٹوں سے زیادہ نہیں ہیں اوردستکار کے پاس 24گھنٹے ہیں۔

(i) اگر فیکٹری اپنی پوری صلاحیت کے ساتھ کام کرے تو ریکٹ اوربلوں کی تیار ہونے والی تعداد کیا ہے؟

(ii) اگر ایک ریکٹ اورایک بلے پر منافع بالترتیب20روپیے اور10روپیے ہے،تو فیکٹری کا زیادہ سے زیادہ منافع معلوم کیجیے جب کہ یہ اپنی مکمل صلاحیت کے ساتھ کام کرتی ہے۔

4۔ ایک صنعت کارنٹ اوربولٹ تیار کرتا ہے۔یہ نٹ کاایک پیکٹ تیارکرنے کے لیے مشینAپر’1‘گھنٹہ اور مشین B پر ’1‘ گھنٹہ کام کرتا ہے ۔یہ بولٹ کے ایک پیکٹ کو تیار کرنے کے لیے مشین A پر ’3‘ گھنٹہ اور مشین B پر ’1‘گھنٹہ کام کرتا ہے۔ وہ نٹ کے ایک پیکٹ پر17.50روپیہ منافع اوربولٹ کے ایک پیکٹ پر7روپیہ منافع کماتا ہے۔ ہر ایک دن میں وہ زیادہ سے زیادہ منافع کمانے کے لیے ہر ایک کے کتنے پیکٹ تیار کرے اگر وہ روزانہ اپنی مشینوں کو زیادہ سے زیادہ12گھنٹے چلاتا ہے۔

5۔ ایک فیکٹر ی AاورBدوطرح کے پیچ (Screws)تیار کرتی ہے۔ ہر ایک پیچ کو دوطرح کی مشینوں کی ضرورت ہے،ایک خود کار اور ایک ہاتھ سے کام کرنے والی کی۔پیچAکے ایک پیکٹ کو تیار کرنے کے لیے خود کار مشین 4منٹ اورہاتھ سے کام کرنے والی مشین 6منٹ لیتی ہے،جب کہ پیچ Bکے ایک پیکٹ کو تیار کرنے کے لیے خود کارمشین6منٹ اور ہاتھ سے کام کرنے والی مشین 3منٹ لیتی ہے۔ہر ایک مشین کسی بھی دن زیادہ سے زیادہ کام کرنے کے لیے4گھنٹے موجود ہے۔ صنعت کار پیچAکے پیکٹ کو7روپیے منافع سے بیچ سکتا ہے اور پیچBکے پیکٹ کو10روپیے پر، یہ مانتے ہوئے کہ ہر ایک قسم کے وہ جتنے بیج تیار کرتا ہے، فیکٹری مالک ایک دن میں کتنے پیکٹ تیار کرے تاکہ اسکا منافع زیادہ سے زیادہ ہو؟ اس کا زیادہ سے زیادہ منافع معلوم کیجیے۔

6۔ ایک کاٹیج صنعت پیڈسٹل لیمپ اور لکڑی کے شیڈتیارکرتی ہے،ہر ایک میں گھسنے  /کاٹنے کی مشین کے استعمال کی ضرورت ہوتی ہے اور رنگ ڈالنے کی مشین کی ایک پیڈسٹل لیمپ تیار کرنے کے لیے گھسنے /کاٹنے کی مشین2گھنٹے اور رنگ چھڑکنے کی مشین3گھنٹے لیتی ہے۔ ایک شیڈتیارکرنے کرنے کے لیے گھسنے /کاٹنے کی مشین ’1‘گھنٹہ اوررنگ چھڑکنے کی مشین2گھنٹے لیتی ہے۔ کسی بھی دن، رنگ چھڑکنے کی مشین(Sprayer) زیادہ سے زیادہ20گھنٹہ کے لیے مل سکتی ہے اور گھسنے/کاٹنے کی مشین12گھنٹے کے لیے مل سکتی ہے۔ یہ مانتے ہوئے کہ صنعت کار جتنے لیمپ اورشیڈتیارکرتا ہے، وہ انھیں بیچ سکتا ہے، وہ اپنا روزانہ کے کام کرنے کا جدول کس طرح تیارکرے تاکہ اس کا منافع زیادہ سے زیادہ ہوجائے؟

7۔ ایک کمپنی دو طرح کی انوکھی نشانیاں تیارکرتی ہے جو کہ پلائی وڈسے بنی ہیں۔ نشانیAکوکاٹنے کے لیے5منٹ اورجوڑنے کے لیے10منٹ کی ضرورت ہوتی ہے۔ نشانیBکو کاٹنے کے لیے8منٹ اور جوڑنے کے لیے8منٹ کی ضرورت ہوتی ہے۔ کاٹنے کے لیے3گھنٹہ ،20منٹ موجود ہیں اور جوڑنے کے لیے4گھنٹے۔Aقسم کی نشانی پر5روپیے منافع ہے اورBقسم کی نشانی پر6روپیے منافع ہے۔کمپنی ہر ایک قسم کی کتنی نشانیاں تیارکرے تاکہ اس کا منافع زیادہ سے زیادہ ہوسکے؟

8۔ ایک کاروباری دوطرح کے ذاتی کمپیوٹر بیچنے کا پلان بناناہے۔ ایک ڈیسک ٹاپ(Desktop) ماڈل اور ایک پورٹیبل(Portable) ماڈل جن کی قیمت بالترتیب25000روپیے اور40000روپیے ہوگی۔ اس کاتخمینہ ہے کہ ایک مہینہ میں کمپیوٹرس کی مانگ250اکائیوں سے زیادہ نہیں بڑھے گی ہر قسم کمپیوٹرس کی وہ تعداد معلوم کیجیے جو کہ کاروباری ذخیرہ کرے تاکہ اس کامنافع عظیم ہوجب کہ وہ70لاکھ روپیے سے رقم سے زیادہ خرچ نہیں کرنا چاہتا اوراگر اس کا ڈیسک ٹاپ ماڈل پر منافع4500روپیے اورپورٹیبل ماڈل پر منافع5000روپیے ہے۔

9۔ ایک خوراک میں وٹامنAکی کم سے کم80اکائیاں اورمعدنیات کی100اکائیاں ہونی چاہئیں۔دوغذاوںF1اورF2دستیاب ہیں۔غذاF1 کی قیمت4روپیے فی اکائی غذاہے اورF2 کی قیمت6روپیہ فی اکائی کھانہ ہے۔ غذاF1کی ایک اکائی میں وٹامنAکی 3اکائیاں اورمعدنیات کی4اکائیاں ہیں۔ غذاF2کی ایک اکائی میں وٹامنA کی6اکائی اورمعدنیات کی3اکائیاں ہیں۔اسے ایک خطی پروگرامنگ مسئلہ کے طورپر قانونی شکل دیجیے۔ خوراک کی قلیل قدر معلوم کیجیے جس میں دوغذاؤں کے مرکب ہوں اور معدنیاتی غذائیت کی ضروریات مکمل ہوں۔

10۔F1اورF2دوقسم کی مصنوعی کھادہیں۔F1میں10فی صدنائیٹروجن اور6فی صدفاسفورک ایسڈہے اورF2میں5فی صد نائیٹروجن اور10فی صدفاسفورک ایسڈہے۔ مٹی کے حالات کو ٹیسٹ کرنے کے بعد ایک کسان کو پتہ چلتا ہے کہ اسے فصل کے لیے کم سے کم 14کلو نائیٹروجن اور14کلوفاسفورس کی ضرورت ہے۔ اگرF1کی قیمت6روپیے فی کلوگرام اورF2کی قیمت 5روپیے فی کلوگرام ہے،تو معلوم کیجیے کہ ہر طرح کی مصنوعی کھاد کی کتنی تعداد استعمال کی جائے تاکہ کم سے کم روپیے صرف ہو۔ کم سے کم قیمت کیا ہے؟

11۔ ذیل خطی نامساواتوں کے x, y ≥ 0, x +3y ≥15, 2x +y +y ≥10

کے نظام سے معقول خطّہ کے کارنر نقاط  [0,0], [5,0], [3,4] اور  (0,5)

ہیں۔مان لیجیے کہZ = px+ qyہے۔جہاںp, q >0ہے۔pاورqپر یہ شرط ہے کہZکا عظیم(3,4)اور(0,5) دونوں پر ملتا ہے یہ ہے:

q = 3p   (D)       p = 3q  (C)         p =2q   (B)          p=q   (A) 

متفرق مشقیں

مثال9: (کھانے کا مسئلہ) ایک ماہرِخوراک کو دوکھانوں PاورQکا استعمال کرکے ایک خاص قسم کی خوراک بناتا ہے۔ Pکھانے کے ہر ایک پیکٹ میں(جس میں30گرام ہے)12اکائی کیلشیم کی،4اکائی آئرن کی،6اکائی کولیسٹرول اور6اکائی وٹامنAکی ہیں۔Qکھانے کے ہر ایک پیکٹ میں جس میں برابر مقدار ہے،3اکائی کیلشیم،20اکائی آئرن،4اکائی کولیسٹرول اور3اکائی وٹامنAکی ہیں۔ خوراک میں کم سے کم240اکائی کیلشیم،کم سے کم460اکائی آئرن اور زیادہ سے زیادہ300اکائی کولیسٹرول کی ضرورت ہے۔ہر کھانے کے کتنے پیکٹ استعمال کیے جائیں کہ خوراک میں وٹامنAکی کم سے کم مقدار ہوسکے؟ وٹامنAکی قلیل مقدار کیا ہے؟

حل: مان لیجیے غذاPاورQکے پیکٹوں کی تعداد بالترتیبxاورyہے۔صاف طورپرہے۔ دییے ہوئے مسئلے کی ریاضیاتی تشکیل ذیل کی طرح ہے:

(وٹامن کم سے کم کیجیے

پابندیاں 

(کیلشیم پرپابندی)

(1)........        4x y ≥80 ,  یعنیx           12x + 3y ≥240 

(آئرن پر پابندی)

(2)..........            x + 5y  ≥ 115,  یعنیx 4x` + 20y  ≥ 460 

(کولیسٹرول پر پابندی)

(3)........ 3x+2y ≤150,   

یعنی 

6x +4y ≤300

(4)........    x ≥ 0, y ≥0 

ہمیں(1)تا(4)نامساواتوں کا گراف کھینچنا چاہیے۔

(1)تا(4)پابندیوں کے ذریعہ معلوم کیاگیا معقول علاقہ(شیڈڈ) شکل12.10میں دیاگیا ہے اوریہ نوٹ کیجیے کہ یہ بند ہے۔

کارنرنقاط M،LاورNکے مختصات بالترتیب(72, 2)،(20, 15)اور(15, 40)ہیں۔ ہمیں ان نقاط پرZکی قیمت کا اندازہ لگانا چاہیے:

قلیل 

جدول سے،ہمیں نقطہ(20, 15) پرZقلیل معلوم ہوا ہے۔ اس لیے مسئلے کی دی ہوئی پابندیوں کے تحت وٹامنAکی مقدار قلیل ہوگی،اگرغذاPکے15پیکٹ اورغذاQکے18پیکٹ خاص خوراک بنانے میں استعمال ہوئے ہیں۔ وٹامنAکی قلیل مقدار150اکائی ہوگی۔

مثال10:(صنعت کاری مسئلہ)ایک صنعت کارنے تین مشینیںII،IاورIIIاپنی فیکٹری میں لگائیں۔ مشین IاورIIایک دن میں زیادہ سے زیادہ12گھنٹے کام کرنے کی صلاحیت رکھتی ہیں جب کہ مشینIII کو روزانہ کم سے کم 5 گھنٹے کام کرناہی ہے۔وہMاورNدوقسم کی اشیا بناتی ہے جس میں تینوںمشینوں کا استعمال ہوتاہے۔

تینوں مشینوں پرMاورNقسم کی اشیا ء کی’I‘اکائی بنانے کے لیے ذیل جدول میں ان کے گھنٹے دئیے گئے ہیں:

وہ اشیا MاورNپر بالترتیب600روپیے اور400روپیے منافع کماتی ہے۔وہ ہر قسم کی کتنی اشیا تیار کرے تاکہ اس کا منافع زیادہ سے زیادہ ہوسکے، یہ مانتے ہوئے کہ اس نے جتنی اشیا تیارکی ہیں وہ سب بیچ سکتی ہے؟زیادہ سے زیادہ منافع کیا ہوگا؟

حل:  مان لیجیے اشیا MاورNکی تعداد بالترتیبxاورyہے ۔

پیداوار پر کل منافع=(600x+400y)روپیے

دئیے ہوئے مسئلہ کی ریاضیاتی تشکیل ذیل کی طرح ہے:

Z=600x+400yزیادہ سے زیادہ کیجیے

پابندیوں پر منحصر:

(مشین Iپرپابندی)     

(1)...........  x +2y ≤ 12

(مشین IIپرپابندی)  

(2) ....... 2x +y ≤ 12

(مشینIIIپرپابندی)

(4) ....... x ≤0, y ≤0

آئیے(1)تا(4)پابندیوں کا گراف کھینچیں۔ پابندیوں(1)تا(4)کے ذریعے معلوم کیاگیا معقول خطّہABCDE (شیڈڈ)12.11میں دکھایاگیا ہے۔ مشاہدہ کیجیے کہ ممکن علاقہ بندہے، کارنر نقاطD،C،B،A اور Eکے بالترتیب مختصات (5,0)،(6,0)،(4,4)،(0,6)اور(0,4)ہیں۔

ہمیں ان کارنر نقاط پرZ=600x+400yکی قیمت کااندازہ لگانا چاہیے۔

عظیم

ہم نے دیکھاکہ نقطہ(4,4)، Z کی عظیم قدر دے رہا ہے۔ اس لیے  صنعت کار کو ہر قسم کی اشیا کی4اکائیاں تیار کرنی چاہئیں تاکہ زیادہ سے زیادہ منافع4000روپیے حاصل ہو۔

مثال11:(نقل وحمل مسئلہ)(Transportation problem):دو فیکٹریاں ہیں۔ ایکPپر واقع ہے اور دوسریQپر واقع ہے۔ ان جگہوں سے،کچھ سامان تین ڈپوA،BاورCپر جانا ہے۔ ڈپوں کی ہفتہ وار ضرورت بالترتیب اشیا کی 5,5اور4 اکائیاں ہیں جب کہ PاورQجگہ پر واقع فیکٹریوں کی اشیا بنانے کی صلاحیت بالترتیب8اور6اکائیاں ہیں۔آمدورفت پر فی اکائی خرچ نیچے دیاگیا ہے:

ہر ایک فیکٹری سے ہر ایک ڈپو پر کتنی اشیا لے جائی جائیں تاکہ آمدورفت پر خرچ کم سے کم  ہو۔ آمدورفت کی قلیل قیمت کیاہوگی؟

حل:  مسئلہ کو شکل(ڈائیگرام) کے ذریعہ ذیل کی طرح سمجھاجاسکتا ہے(شکل12.12):

مان لیجیے فیکٹریPسے اشیا کیxاکائی اورyاکائی بالترتیب ڈپوAاورBکو لے جائی گئیں ہیں۔تب(8–x–y)اکائی ڈپوCتک لے جائی جائیں گی(کیوں؟)

اس لیے، ہمارے پاس ہے

8 - x - y ≥ 0 اور  x ≥ 0, y ≥0 

  یعنی،x ≥ 0, y≥0اور ،x + y ≤ 8

اب، ڈپوAپر اشیا کی ہفتہ وار ضرورت5اکائیوںکی ہے۔کیونکہ فیکٹری سےPپرxاکائی لے جائی گئی ہیں،باقی(x– 5) اکائی فیکٹری سےQپر لے جانے کی ضرورت ہے۔صاف طور پر، 

اسی طرح،

6- (5 - x + - y ) = x +y - 4 اور  (5 - y )

 اکائیاںQپر فیکٹری سے بالترتیب ڈپوBاورCپر لے جائی جائیں گی۔

اس لیے،

x + y - 4 ≥ 0, 5 - y ≥0 

یعنی

x + y ≥ 4, y ≥ 5

کی کل آمدورفت کی قیمت اس طرح دی گئی ہےZ

Z = 160 x + 100 y + 100 (5 - x) + 120 (5-y ) + 100 (x + y - 4) + 150 (8 - x - y) = 10 (x - 7 y +190)

اس لیے، مسئلہ اس طرح چھوٹا ہوجاتا ہے

Z = 10 (x – 7y + 190)کم سے کم کیجیے

پابندیوں پر منحصر

x ≥ 0, 0≥0   ........(1)

x + y ≥8    ........(2)

x ≥5  .......(3)

y ≥5   .......(4)

x + y ≥4    .....(5)

شیڈڈ علاقہABCDEFپابندیوں (1) تا (5)سے ظاہر کیاگیا معقول خطّہ ہے(شکل12.13)

مشاہدہ کیجیے کہ معقول خطّہ بند ہے۔ معقول خطّہ کے کارنر نقاط کے مختصات (0,4)،(0,5)،(3,5)،(5,3) ،(5,0) اور (4,0) ہیں۔

ہمیں ان نقاط پرZکی قیمت کا اندازہ لگانا چاہیے۔

قلیل

ہم جدول سے دیکھتے ہیں کہ نقطہ(0,5)پرZکی قلیل قدر1550ہے۔

اس لیے، نقل وحمل کی احسن کارکردگی فیکٹری سے Pپر5،0 اور3اکائی پہنچانے کی ہوگی، اور فیکٹری سےQپر ڈپوB، A اورCپربالترتیب 0،5اور’I‘اکائی لے جانے کی ہوگی۔اس کارکردگی کے مطابق نقل وحمل کی کم سے کم قیمت ہوگی، یعنی 1550روپیے۔

 باب12پر مبنی متفرق مشقیں

1۔ مثال9کے حوالے سے،ہر ایک کھانے کے کتنے پیکٹ استعمال کیے جائیں تاکہ خوراک میں وٹامنAکی مقدار عظیم ہو؟ خوراک میں وٹامن Aکی زیادہ سے زیادہ مقدار کیا ہے؟

2۔ مویشیوں کے کھانے میں ایک کسان دوقسم(برانڈ) PاورQملاتا ہے۔ قسمPکی قیمت250روپیے فی بیگ ہے جس میں غذائی عنصرAکی 3اکائیاں،عنصرBکی2.5اکائیاں اورعنصرCکی2اکائیاں موجود ہیں۔قسمQکی قیمت200روپیے فی بیگ ہے جس میں غذائی عنصرAکی1.5اکائیاں غذائی عنصر B کی 11.25اکائیاں، اور وٹامنC کی 3اکائیاں موجود ہیں وٹامن A، Bاور C کی کم سے کم ضرورت بالترتیب18اکائیاں،45اکائیاں اور24اکائیاں ہے۔ہرقسم کے بیگوں کی تعداد معلوم کیجیے جو کہ اس ترتیب میں ملائے جائیں کہ حاصل ہونے والے مرکب کی فی بیگ کم سے کم کی قیمت ہو؟ ہر مرکب کے فی بیگ کی کم سے کم قیمت کیا ہے؟

3۔ ایک ماہر خوراکxاورyدو قسم کے کھانے اس طرح آپس میں ملاناچاہتا ہے تاکہ مرکب میں وٹامنAکی کم سے کم10اکائیاں ہوں،وٹامنBکی’ 12‘اکائیاں اوروٹامن Cکی ’8‘اکائیاں ہوں۔ ایک کلوگرام کھانے میںوٹامن کی مقدار ذیل میں دی گئی ہے:

Xکھانے کی ایک کلوگرام کی قیمت16روپیے ہے اورYکھانہ کی ایک کلوگرام کی قیمت20روپیے ہے۔مرکب کی کم سے کم قیمت معلوم کیجیے جو کہ مطلوبہ خوراک بنائے گا؟

4۔ ایک صنعت کارAاورBدوقسم کے کھلونے بناتا ہے۔اس کام کے لیے تین مشینیں درکار ہیں اور ہر کھلونے کے لیے مشین پردرکار وقت(منٹ میں)ذیل میں دیاگیا ہے:

ہر مشین روزانہ زیادہ سے زیادہ 6گھنٹہ دستیاب ہے۔اگرAقسم کے ہر کھلونے پر 7.50روپیے منافع ہے اورBقسم کے ہر کھلونے پر منافع5روپیے ہے،تب دکھائیے کہ ایک دن میںزیادہ سے زیادہ منافع کمانے کے لیے صنعت کارAقسم کے 15 کھلونے اورBقسم کے30کھولنے تیار کرے۔

5۔ ایک ہوائی جہاز زیادہ سے زیادہ200مسافر لے جاسکتا ہے۔ہراعلا درجے کے ٹکٹ پر 1000روپیے منافع ہوتا ہے اورہر عام درجہ کے ٹکٹ پر600روپیے منافع ہوتا ہے۔ہوائی کمپنی کم سے کم20سیٹیں اعلا درجے کے لیے معین کرتی ہے۔ حالانکہ، چارگنا مسافر عام درجہ سے سفر کرنے کو ترجیح دیتے ہیں بہ نسبت اعلا درجہ کے۔ معلوم کیجیے کہ ہر ایک قسم کے کتنے ٹکٹ بیچے جائیں تاکہ ہوائی کمپنی کوزیادہ سے زیادہ منافع ہو۔زیادہ سے زیادہ کتنا منافع حاصل ہوسکتا ہے؟

6۔ دوگوداموںAاورBکی گیہوں رکھنے کی گنجائش بالترتیب100کوئنٹل اور50کوئنٹل ہے۔ وہ راشن کی تین دکانوں E،D اورF کو بالترتیب 50،60اور40کیونٹل گیہوؤں کی سپلائی کرتی ہیں۔ گوداموں سے دکانوں تک گیہوں پہنچانے کی فی کیونٹل رقم ذیل جدول میں دی گئی ہے:

سپلائی کو کس طرح انجام دیاجائے کہ لانے لے جانے کی رقم کم سے کم ہو؟ کم سے کم قیمت کیا ہے؟

7۔ ایک تیل کی کمپنی کے پاس دوڈپوAاورBہیں جن کی تیل رکھنے کی صلاحیت بالترتیب7000لیٹر اور4000لیٹر ہے۔کمپنی کو  تین پیٹرول پمپوںE،DاورFکو تیل سپلائی کرنا ہے جن کی ضرورت بالترتیب4500لیٹر،3000لیٹر اور 3500 لیٹر ہے۔ ڈپوں اور پٹرول پمپوں کے درمیان فاصلہ(کلومیٹر میں)ذیل میں دیاگیا ہے:

یہ مانتے ہوئے کہ10لیٹر تیل لانے لے جانے کی رقم ایک روپیہ فی کلومیٹر ہے،تیل کو کس طرح پہنچایا جائے کہ آمدورفت کی رقم کم سے کم ہو؟ کم سے کم قیمت کیا ہے؟

8۔ ایک پھل اُگانے والا اپنے باغ میں دو قسم کی مصنوعی کھاد Pاور Qاستعمال کرسکتا ہے۔نائیٹروجن،فاسفورک ایسڈ،پوٹاش اور کلورین کی ایک بیگ میں ہر قسم کی مقدار (کلوگرام میں)جدول میں دی گئی ہیں۔ ٹیسٹ بتاتے ہیں کہ باغ کو کم سے کم240کلوگرام فاسفورک ایسڈ، کم سے کم270کلوگرام پوٹاش اور زیادہ سے زیادہ310کلوگرام کلورین کی ضرورت ہے۔

اگر پھل اگانے والا باغ میں ڈالنے والی نائیٹروجن کی مقدار کم سے کم کرناچاہتا ہے،تو ہر قسم کے بیگوں کے استعمال کی تعداد کتنی ہوگی؟ باغ میں کم سے کم نائیٹروجن کی کتنی مقدار ڈالی گئی ہے؟

9۔ سوال نمبر8کے حوالے سے،اگر پھل اُگانے والا چاہتا ہے کہ باغ میں ڈالی گئی نائیٹروجن کی مقدار زیادہ سے زیادہ ہو، توہر قسم کے کتنے بیگ ڈالے جائیں؟زیادہ سے زیادہ ڈالی گئی نائیٹروجن کی مقدار کیا ہوگی؟

10۔ ایک کھلونے بنانے والی کمپنی AاورBدوطرح کی گڑیاں تیارکرتی ہے۔بازار میں کی گئی جانچ اور دستیاب ذرائع یہ اشارہ کرتے ہیں کہ دونوں قسم کی گڑیاں بنانے کی مقدار ایک ہفتہ میں 1200 سے زیادہ نہیں ہونی چاہیے، اورBقسم کی گڑیاکی مانگAقسم کی گڑیا کی مانگ کی زیادہ سے زیادہ آدھی ہے۔مزید یہ کہ Aقسم کی گڑیا کے بننے کا لیول دوسری گڑیا کے بننے کے لیول سے تین گنا بڑھ سکتا ہے جو کہ زیادہ سے زیادہ 600اکائیاں ہے ۔اگر کمپنی کو AاورBگڑیوں پر منافع بالترتیب 12روپیے اور16روپیے ہے، تو ایک ہفتہ میں ہر ایک قسم کی کتنی گڑیاں بنائی جائیں تاکہ منافع زیادہ سے زیادہ ہوسکے؟

٭٭٭