طالب علم کا ریاضیاتی تجربہ ختم نہیں ہوتا اگر وہ کبھی خود کے ذریعے ایک مسئلہ جوڑنے کا فرصت نہ حاصل کر لے۔ - جی۔ پولیا

12.1 تعارف

پچھلے فصلوں میں ہم نے لائنر مساواتوں کے سسٹمز اور ان کے روزمرہ کے مسائل میں استعمال کرنے کے بارے میں بات کی ہے۔ صفحہ 11 میں ہم نے دو متغیرات والی لائنر نامساوات اور لائنر نامساوات کے سسٹمز اور ان کے حلوں کو ترسیمی طریقے سے سیکھا ہے۔ ریاضی کے بہت سے استعمالات میں لائنر نامساوات/مساوات کے سسٹمز شامل ہوتے ہیں۔ اس فصل میں ہم لائنر نامساوات/مساوات کے سسٹمز کو ذیل میں دیے گئے چند روزمرہ کے مسائل میں استعمال کریں گے:

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

ایک خاص لیکن بہت مہمان ذات اوپٹیمائزیشن مسائل کا ایک زمرہ ہے جسے لائنر پروگرامنگ مسئلہ کہتے ہیں۔ زیر التوا فریم چیئر ڈیلر کا مذکورہ بالا اوپٹیمائزیشن مسئلہ لائنر پروگرامنگ مسئلے کا مثال ہے۔ لائنر پروگرامنگ مسائل بہت مہمان ذات ہیں کیونکہ ان کا واسع استعمال صنعت، تجارت، مینیجمنٹ سائنس جیسے بہت سی شعبوں میں ہے۔

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

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

ہم اوپٹیمائزیشن مسئلے کی بات کرتے ہوئے اوپٹیمائزیشن مسئلے کے مذکورہ بالا مثال کے ساتھ شروع کریں گے جو ہمیں دو متغیرات والی ریاضیاتی تشریح کے لیے راستہ دے گی۔ اس مثال میں ہم دیکھیں گے

(١) ڈیلر اپنی رقم کو صرف ٹیبلز یا چیئرز یا ان کا ترکیب خریدنے میں شروع کر سکتا ہے۔ اور وہ مختلف واپسی کی طریقوں کے ذریعے مختلف آمدنی حاصل کر سکتا ہے۔

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

اگر ڈیلر صرف ٹیبلز خریدنے کا فیصلہ کرے اور کوئی چیئر نہیں، تو اس کو 13، یعنی 20 ٹیبل خریدنے کا اسکیمہ ملے گا۔ اس صورت میں اس کی آمدنی 14، یعنی 15 روپے ہو گی۔

اگر اس کا فیصلہ چیئرز خریدنے کا ہو، اور کوئی ٹیبل نہیں، تو اس کے 50,000 روپے کے سرمایہ کے ساتھ اس کو 16، یعنی 100 چیئر خریدنے کا اسکیمہ ملے گا۔ لیکن اس کے پاس صرف 60 آئٹمز تک ذخیرہ کرنے کا جگہ ہے۔ لہٰذا، اس کو صرف 60 چیئر خریدنے کا اجبار ہو گا جو اس کو 17، یعنی 4500 روپے کی کل آمدنی دے گا۔

مختلف حالات موجود ہیں، مثلاً، اس کا فیصلہ 10 ٹیبلز اور 50 چیئرز خریدنے کا ہو سکتا ہے، کیونکہ اس کے پاس صرف 60 آئٹمز تک ذخیرہ کرنے کا جگہ ہے۔ اس صورت میں کل آمدنی 18، یعنی 19 روپے ہو گی اور اس طرح۔

ہم اس طرح دیکھتے ہیں کہ ڈیلر اپنی رقم کو مختلف طریقوں میں شروع کر سکتا ہے اور مختلف واپسی کی طریقوں کے ذریعے مختلف آمدنی حاصل کر سکتا ہے۔

اب مسئلہ یہ ہے: اس کو زیادہ سے زیادہ آمدنی حاصل کرنے کے لیے اس کی رقم کو کیسے واپسی کرنی چاہیے؟ اس سوال کا جواب دینے کے لیے، چلیں مسئلہ کو ریاضیاتی طور پر تشریح کرنے کی کوشش کریں۔

12.2.1 مسئلہ کی ریاضیاتی تشریح

لیتے ہیں $x$ ڈیلر کے ٹیبلز کی تعداد اور $y$ ڈیلر کے چیئرز کی تعداد۔ ہوئے سر $x$ اور $y$ منفی نہیں ہونی چاہیں، یعنی،

$$ \begin{align*} & x \geq 0 \tag{1}\\ & y \geq 0 \tag{2} \end{align*} \text { (Non-negative constraints) } $$

ڈیلر کو اپنی واپسی کی حد (یہاں 50,000 روپے ہے) اور اس کے ذخیرہ کرنے کے جگہ کی حد (یہاں 60 آئٹمز ہے) کی ضرورت ہے۔

ریاضیاتی طور پر بیان کیا گیا،

یا $$ \begin{array}{rlrl} 2500 x+500 y & \leq 50,000 & \text { (investment constraint ) } \\ 5 x+y & \leq 100 & & \\ x+y & \leq 60 & & \text { (storage constraint) } \tag{4} \end{array} $$

ڈیلر ایسی واپسی کرنے کا فیصلہ کرنا چاہتا ہے تاکہ اس کی آمدنی زیادہ سے زیادہ ہو، جسے $Z$ کہا جاتا ہے، جو $x$ اور $y$ کے تعلق سے دیتا ہے، دیتا ہے

$Z=250 x+75 y$ (جسے مقصدی ترکیب کہا جاتا ہے)

ریاضیاتی طور پر، دیے گئے مسائل اب کم کرنے کے لیے کم کر دیا گیا ہے:

$Z=250 x+75 y$ کو زیادہ سے زیادہ کریں

اگر توقعات کے مطابق:

$$ \begin{aligned} 5 x+y & \leq 100 \\ x+y & \leq 60 \\ x \geq 0, y & \geq 0 \end{aligned} $$

تو ہم کسی لائنر ترکیب کو زیادہ سے زیادہ کرنے کے لیے ضروری ہے $Z$ جو کچھ کہیں $x$ اور $y$ کی حیثیت سے منفی نہیں ہونا چاہیے۔ مختلف مسائل میں ہم کسی لائنر ترکیب کو کم کرنے کے لیے کچھ کہیں $Z=a x+b y$ کی حیثیت سے منفی نہیں ہونا چاہیے۔ ایسے مسائل کو لائنر پروگرامنگ مسائل کہتے ہیں۔

اس طرح، ایک لائنر پروگرامنگ مسئلہ وہ ایک مسئلہ ہے جو کچھ کہیں $a, b$ اور $Z=250 x+75 y$) کی کچھ کہیں $x$ کی زیادہ سے زیادہ (یا کم سے کم) قیمت حاصل کرنے کے لیے متغیرات کے مطابق ہے۔ جو کچھ کہیں $y$ کی حیثیت سے منفی نہیں ہونا چاہیے اور کسی سیٹ کی لائنر نامساواتوں کو پورا کرنا چاہیے (جسے لائنر پابندیات کہا جاتا ہے)۔ لائن کہنے کا مطلب یہ ہے کہ مسئلے میں استعمال کی گئی تمام ریاضیاتی تعلقات لائنر تعلقات ہیں جبکہ پروگرامنگ کہنے کا مطلب یہ ہے کہ کسی خاص پروگرام یا کارروائی کا طریقہ جاننا۔

ابھی پیش کرنے سے پہلے، ابھی ہم کچھ اصطلاحات (جو اوپٹیمائزیشن مسئلے کے بارے میں اوپٹیمائزیشن مسئلے کے بارے میں بات کی گئی ہے) کو رسمی طور پر تعریف کریں گے جو ہم لائنر پروگرامنگ مسائل میں استعمال کریں گے:

مقصدی ترکیب لائنر ترکیب $x \geq 0, y \geq 0$، جہاں $x$ ثابت ہیں، جسے زیادہ سے زیادہ کرنے یا کم کرنے کے لیے ہے، کو لائنر مقصدی ترکیب کہا جاتا ہے۔ اس مثال میں، $y$ ایک لائنر مقصدی ترکیب ہے۔ متغیرات $x$ اور $y$ قرار دے دیتے ہیں۔

پابندیات لائنر نامساوات یا مساوات یا لائنر پروگرامنگ مسئلے کے متغیرات پر پابندیات یا محدودیتوں کو پابندیات کہتے ہیں۔ شرائط $x, y \geq 0$ کو منفی نہیں رکھنے کی پابندیات کہتے ہیں۔ اس مثال میں، نامساوات کے سیٹ (١) سے (٤) کو پابندیات کہا جاتا ہے۔

اوپٹیمائزیشن مسئلہ ایک مسئلہ جو کچھ کہیں $OABC$ اور $(10,50)$) کی کسی لائنر ترکیب کو زیادہ سے زیادہ یا کم کرنے کی تلاش کرتا ہے، جو کچھ کہیں $(0,60),(20,0)$ کی حیثیت سے منفی نہیں ہونا چاہیے، کسی سیٹ کی لائنر نامساواتوں کے تحت ہے، کو اوپٹیمائزیشن مسئلہ کہا جاتا ہے۔ لائنر پروگرامنگ مسائل اوپٹیمائزیشن مسائل کا ایک خاص قسم ہے۔ ڈیلر کے پاس دیے گئے مجموعے کو خریداری کرتے ہوئے چیئرز اور ٹیبلز کے لیے ایک مسئلہ ایک اوپٹیمائزیشن مسئلے کا مثال ہے اور لائنر پروگرامنگ مسئلے کا بھی۔

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

12.2.2 لائنر پروگرامنگ مسائل کے حل کے ترسیمی طریقے

صفحہ 11 میں ہم نے دو متغیرات والی لائنر نامساواتوں کے سسٹم کی ترسیم کرنے اور ان کے حلوں کو ترسیمی طریقے سے حاصل کرنے کا سبق سیکھا ہے۔ چلیں 12.2 میں مشاورہ کرنے والے ٹیبلز اور چیئرز کے لیے واپسی کے مسئلے کو ترسیمی طریقے سے حل کریں۔ چلیں پابندیات کو لائنر نامساوات کے طور پر ترسیم کریں:

$$ \begin{align*} 5 x+y & \leq 100 \tag{1} \\ x+y & \leq 60 \tag{2} \\ x & \geq 0 \tag{3} \\ y & \geq 0 \tag{4} \end{align*} $$

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

شکل 12.1

دستیاب ریجن مسئلے کے لیے تمام پابندیات کے ذریعے حدودی ریجن (یا حل ریجن) کہلاتا ہے۔ شکل 12.1 میں، ریجن OABC (سیڈڈ) مسئلے کے لیے دستیاب ریجن ہے۔ دستیاب ریجن کے باہر کو دستیاب نہیں ریجن کہلاتا۔

دستیاب حلوں کے نقاط دستیاب ریجن کے اندر اور اس کی ماحولیات کے نقاط شرائط کے دستیاب حل کی حیثیت سے ذکر کرتے ہیں۔ شکل 12.1 میں، دستیاب ریجن $(25,40)$ کے اندر اور اس کی ماحولیات کے ہر نقطہ مسئلے کے لیے دستیاب حل کی حیثیت سے ذکر کرتا ہے۔ مثال کے طور پر، نقطہ $OABC$ مسئلے کا ایک دستیاب حل ہے اور اس طرح ہی نقاط $Z=250 x+75 y$ جیسے نقاط بھی۔

دستیاب ریجن کے باہر کو کسی نقطہ کو دستیاب نہیں حل کہلاتا۔ مثال کے طور پر، نقطہ $R$ مسئلے کا ایک دستیاب نہیں حل ہے۔

اوپٹیمل (دستیاب) حل: مقصدی ترکیب کی زیادہ سے زیادہ (یا کم سے کم) قیمت دینے والا ہر نقطہ دستیاب ریجن میں ایک اوپٹیمل حل کہلاتا ہے۔

اب، ہم دیکھیں گے کہ دستیاب ریجن $Z=a x+b y$ میں ہر نقطہ (١) سے (٤) میں دیے گئے تمام شرائط کو پورا کرتا ہے، اور کیونکہ دستیاب نقاط بہت سے ہیں، اس لیے اس کے حل کے لیے ہم کیسے چلیں گے کا استنباط نہیں ہے۔ اس صورت کو ہینڈل کرنے کے لیے، ہم استعمال کریں گے جو منصوبہ بندی مسائل کے حل کرنے میں بنیادی طور پر مفید ہونے والے منصوبے۔ ان منصوبوں کی ثباتات کی وجہ سے اس کتاب کے حدود سے باہر ہیں۔

منصوبہ ١ $Z$ لائنر پروگرامنگ مسئلے کے لیے دستیاب ریجن (محدود ضلعی شکل) اور $x$ مقصدی ترکیب۔ جب $y$ کی کوئی زیادہ سے زیادہ قیمت (زیادہ سے زیادہ یا کم سے کم) ہو، جہاں متغیرات $R$ اور $Z=a x+b y$ کی شرائط کے تحت ہیں، تو اس زیادہ سے زیادہ قیمت کو دستیاب ریجن کے ایک کونے (ورٹیکس) میں ہونا چاہیے۔

منصوبہ ٢ $R$ لائنر پروگرامنگ مسئلے کے لیے دستیاب ریجن، اور $Z$ مقصدی ترکیب۔ $R$ محدود ہونے کی صورت میں، مقصدی ترکیب $R$ پر $O, A, B$ اور کم سے کم قیمتیں ہوں گی اور ان کا ہر ایک کونے (ورٹیکس) میں ہونا چاہیے۔

تبصرہ $C$ غیر محدود ہونے کی صورت میں، مقصدی ترکیب کی زیادہ سے زیادہ یا کم سے کم قیمت موجود نہیں ہو سکتی۔ لیکن اگر موجود ہو، تو اس کو دستیاب ریجن کے ایک کونے میں ہونا چاہیے۔ (منصوبہ ١ کے ذریعے)۔

اوپٹیمائزیشن مسئلے کے مذکورہ بالا مثال میں، محدود (دستیاب) ریجن کے کونے (ورٹیکس) ہیں: $(0,0),(20,0),(10,50)$ اور $(0,60)$ اور ان کے خطابات کو $Z$ اور $ \mathbf{6 2 5 0} $ کے طور پر چھوڑ سکتے ہیں۔ اب ہم ان پر $(10,50)$ کی قیمت حاصل کریں۔

ہمیں ملتا ہے

• دستیاب ریجن کا ایک کونہ ایک نقطہ ہے جو ریجن میں ہے جو دوسری ماحولیات کی لائنز کے تعامل کے نتیجے میں ہوتا ہے۔

• ایک لائنر نامساوات کے سسٹم کا دستیاب ریجن ایسے محدود ریجن کہلاتا ہے جسے ایک دائرہ کے اندر شامل کیا جا سکتا ہے۔ دوسری طرف، اسے غیر محدود ریجن کہلاتا ہے۔ غیر محدود کہنے کا مطلب یہ ہے کہ دستیاب ریجن کسی بھی سمت میں غیر محدودیت کے ساتھ پہنچنا جارہا ہے۔

ہم دیکھتے ہیں کہ ڈیلر کی زیادہ سے زیادہ آمدنی $\mathbf{M}$، یعنی 10 ٹیبلز اور 50 چیئرز خریدنے کے واپسی کی طریقے کے ذریعے ہوتی ہے۔

ایسے لائنر پروگرامنگ مسئلے کو حل کرنے کا اس طریقہ کونر پوائنٹ طریقہ کہلاتا ہے۔ اس طریقے میں درج ذیل مراحل شامل ہیں:

١۔ لائنر پروگرامنگ مسئلے کا دستیاب ریجن حاصل کریں اور اس کے کونے (ورٹیکس) کو دیکھ کر یا اس کے کونے پر ملنے والی دو لائنز کے دو ایکس کو حاصل کر کے حاصل کریں۔

٢۔ ہر کونے پر مقصدی ترکیب $m$ کو ارزاش کریں۔ $M$ اور $m$، ان نقاط کی زیادہ سے زیادہ اور کم سے کم قیمتیں کے طور پر ذکر کر دیں۔

٣۔ (١) جب دستیاب ریجن محدود ہو، تو $Z$ کی زیادہ سے زیادہ اور کم سے کم قیمتیں $M$ اور $Z$ ہوں گی۔

(٢) صورت میں، دستیاب ریجن غیر محدود ہو، ہمیں ملتا ہے:

٤۔ (١) $a x+b y>M$ مقصدی ترکیب کی زیادہ سے زیادہ قیمت ہو گی، اگر $Z$ کے ذریعے حدودی ہال پلان کے کوئی نقطہ دستیاب ریجن کے ساتھ مشترکہ نہ ہو۔ دوسری صورت میں، $m$ کی کوئی زیادہ سے زیادہ قیمت موجود نہیں ہو گی۔

(٢) اس طرح، $Z$ مقصدی ترکیب کی کم سے کم قیمت ہو گی، اگر $a x+b y<m$ کے ذریعے حدودی ہال پلان کے کوئی نقطہ دستیاب ریجن کے ساتھ مشترکہ نہ ہو۔ دوسری صورت میں، $Z$ کی کوئی کم سے کم قیمت موجود نہیں ہو گی۔

ابھی ہم ایسی مراحل کو کونر پوائنٹ طریقے کے ذریعے شرح دے دیں:

مثال ١ درج ذیل لائنر پروگرامنگ مسئلہ کو ترسیمی طریقے سے حل کریں:

$Z=4 x+y$ کو زیادہ سے زیادہ کریں

اگر توقعات کے مطابق:

$$ \begin{aligned} x+y & \leq 50 \\ 3 x+y & \leq 90 \\ x \geq 0, y & \geq 0 \end{aligned} $$

حل شکل 12.2 میں سیڈڈ ریجن مسئلے کے لیے دستیاب ریجن کی حیثیت سے ذکر کرتا ہے۔ ہم دیکھتے ہیں کہ دستیاب ریجن OABC محدود ہے۔ اس لیے ہم اب کونر پوائنٹ طریقے کے ذریعے $Z$ کی زیادہ سے زیادہ قیمت حاصل کرنے کے لیے استعمال کریں گے۔

دستیاب ریجن کے کونے $O, A, B$ اور $C$ کے خطابات $(0,0),(30,0),(20,30)$ اور $(0,50)$ کے طور پر چھوڑ سکتے ہیں۔ اب ہم $Z$ کو ہر کونے پر ارزاش کریں۔

شکل 12.2

اس لیے، $Z$ کی زیادہ سے زیادہ قیمت 120 ہے جو نقطہ $(30,0)$ پر ہے۔

مثال ٢ درج ذیل لائنر پروگرامنگ مسئلہ کو ترسیمی طریقے سے حل کریں:

$Z=200 x+500 y$ کو کم کریں

اگر توقعات کے مطابق:

$$ \begin{align*} x+2 y & \geq 10 \tag{1}\\ 3 x+4 y & \leq 24 \tag{2}\\ x \geq 0, y & \geq 0 \tag{3} \end{align*} $$

حل شکل 12.3 میں سیڈڈ ریجن مسئلے کے لیے دستیاب ریجن کی حیثیت سے ذکر کرتا ہے۔ جو کچھ کہیں $C$، جو کچھ کہیں $(0,5),(4,3)$ کے طور پر چھوڑ سکتے ہیں۔ اب ہم $(0,6)$ کو ان پر ارزاش کریں۔

شکل 12.3

اس لیے، $ \mathbf 2300 $ کی کم سے کم قیمت 2300 ہے جو نقطہ $Z$ پر حاصل ہوتی ہے۔

مثال ٣ درج ذیل مسئلہ کو ترسیمی طریقے سے حل کریں:

$(4,3)$ کو کم کریں اور زیادہ سے زیادہ کریں

اگر توقعات کے مطابق: $Z=3 x+9 y$

$$ \begin{align*} x+3 y & \leq 60 \tag{1}\\ x+y & \geq 10 \tag{2}\\ x & \leq y \tag{3}\\ x \geq 0, y & \geq 0 \tag{4} \end{align*} $$

حل پہلے ہیں، چلیں سسٹم لائنر نامساوات (٢) سے (٥) کا دستیاب ریجن ترسیم کریں۔ دستیاب ریجن $\quad x+3 y \leq 60$ شکل 12.4 میں دکھایا گیا ہے۔ نوٹ کریں کہ ریجن محدود ہے۔ دستیاب ریجن کے کونے A، B، C اور D کے خطابات $ABCD$ اور $(0,10),(5,5),(15,15)$ کے طور پر چھوڑ سکتے ہیں۔

شکل 12.4

اب ہم $(0,20)$ کی کم سے کم اور زیادہ سے زیادہ قیمت حاصل کریں۔ از جدول سے ہمیں ملتا ہے کہ $Z$ کی کم سے کم قیمت 60 ہے جو دستیاب ریجن کے نقطہ $Z$ پر ہے۔

دستیاب ریجن پر $B(5,5)$ کی زیادہ سے زیادہ قیمت دو کونے $Z$ اور $C(15,15)$ پر حاصل ہوتی ہے اور اس کی قیمت ہر دو صورت میں 180 ہے۔

تبصرہ دیکھیں کہ مذکورہ بالا مثال میں، مسئلے کے کونے $D(0,20)$ اور $C$ میں متعدد اوپٹیمل حلوں کے ہونے کی وجہ سے ہے، یعنی ان دو نقاط کی زیادہ سے زیادہ قیمت 180 کو حاصل کرتی ہیں۔ اس صورتوں میں، آپ دیکھ سکتے ہیں کہ دو کونے $D$ اور $C$ کو جوڑنے والی لائن سیگمنٹ CD کے ہر نقطہ بھی ایسی زیادہ سے زیادہ قیمت کو حاصل کرتا ہے۔ ایسی صورت میں بھی ہے کہ دو نقاط کی زیادہ سے زیادہ قیمت ہی حاصل کرتی ہیں۔

مثال ٤ درج ذیل مسئلہ کو ترسیمی طریقے سے حل کریں:

$$ Z=-50 x+20 y $$ کی کم سے کم قیمت حاصل کریں

اگر توقعات کے مطابق:

$$ \begin{aligned} & 2 x-y \geq-5 \\ & 3 x+y \geq 3 \\ & 2 x-3 y \leq 12 \\ & x \geq 0, y \geq 0 \end{aligned} $$

حل پہلے ہیں، چلیں سسٹم نامساوات (٢) سے (٥) کا دستیاب ریجن ترسیم کریں۔ دستیاب ریجن (سیڈڈ) شکل 12.5 میں دکھایا گیا ہے۔ دیکھیں کہ دستیاب ریجن غیر محدود ہے۔

اب ہم $D$ کو کونے پر ارزاش کریں۔

شکل 12.5

از اس جدول سے ہمیں ملتا ہے کہ -300 $Z$ کی کم سے کم قیمت ہے جو دستیاب ریجن کے کونہ $Z$ پر ہے۔ ہم کہ سکتے ہیں کہ $(6,0)$ کی کم سے کم قیمت -300 ہے؟ نوٹ کریں کہ اگر ریجن محدود ہوتا، تو ایسی کم سے کم قیمت $Z$ کی کم سے کم قیمت ہوتی (منصوبہ ٢)۔ لیکن یہاں ہم دیکھتے ہیں کہ دستیاب ریجن غیر محدود ہے۔ اس لیے -300 $Z$ کی کم سے کم قیمت ہو سکتی ہے یا نہیں۔ اس خیال کو قرار دینے کے لیے، ہم نامساوات کو ترسیم کریں

$$ -50 x+20 y<-300 \text{ (see Step 3(ii) of corner Point Method.) } $$

یعنی، $$ -5 x+2 y<-30 $$

اور چیک کریں کہ نتیجہ والی غیر محدود ہال پلان دستیاب ریجن کے ساتھ مشترکہ نقاط کی حیثیت سے ذکر کرتی ہے یا نہیں۔ اگر اس کے پاس مشترکہ نقاط ہوں، تو -300 $Z$ کی کم سے کم قیمت نہیں ہو گی۔ دوسری صورت میں، -300 $Z$ کی کم سے کم قیمت ہو گی۔

شکل 12.5 میں دکھایا گیا ہے کہ اس کے پاس مشترکہ نقاط ہیں۔ اس لیے، $Z$ کی کوئی کم سے کم قیمت دیے گئے پابندیات کے تحت موجود نہیں ہے۔

مذکورہ بالا مثال میں، ہم کہ سکتے ہیں کہ $Z$ نقطہ $Z=-50 x+20 y$ پر 100 کی زیادہ سے زیادہ قیمت ہے؟ اس کے لیے، چیک کریں کہ $z=-50 x+20 y$ کی ترسیم دستیاب ریجن کے ساتھ مشترکہ نقاط کی حیثیت سے ذکر کرتی ہے۔ (کیونکہ؟)

مثال ٥ $(0,5)$ کو کم کریں

اگر توقعات کے مطابق:

$$ \begin{align*} x+y & \geq 8 \tag{1}\\ 3 x+5 y & \leq 15 \tag{2}\\ x \geq 0, y & \geq 0 \tag{3} \end{align*} $$

حل چلیں (١) سے (٣) کے نامساوات کو ترسیم کریں (شکل 12.6)۔ دستیاب ریجن کو کوئی حیثیت سے ذکر کرتا ہے؟ اس کی وجہ کی ہے؟

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

تبصرے مذکورہ بالا میں ہم نے بات کی ہے۔

(١) دستیاب ریجن ہمیشہ ایک محدود ریجن ہوتا ہے۔

(٢) مقصدی ترکیب کا زیادہ سے زیادہ (یا کم سے کم)

شکل 12.6 حل مقصدی ترکیب کی زیادہ سے زیادہ (یا کم سے کم) قیمت دستیاب ریجن کے کونے (کونر) پر حاصل ہوتی ہے۔ اگر دو کونے مقصدی ترکیب کی زیادہ سے زیادہ (یا کم سے کم) قیمت کو حاصل کرتے ہوں، تو ان دو نقاط کو جوڑنے والی لائن سیگمنٹ کے ہر نقطہ بھی ایسی زیادہ سے زیادہ (یا کم سے کم) قیمت کو حاصل کرے گا۔

خلاصہ

ایک لائنر پروگرامنگ مسئلہ وہ ایک مسئلہ ہے جو کچھ کہیں $-50 x+20 y>100$ کی کچھ کہیں $Z=3 x+2 y$) کی زیادہ سے زیادہ (یا کم سے کم) قیمت حاصل کرنے کے لیے متغیرات کے مطابق ہے۔ جو کچھ کہیں �127⟧ کی حیثیت سے منفی نہیں ہونا چاہیے اور کسی سیٹ کی لائنر نامساواتوں کو پورا کرنا چاہیے۔ متغیرات کو کچھ ہیں https://temp-public-img-folder.s3.ap-south-1.amazonaws.com/sathee.prutor.images/images/ncertbook/math/m12/linear_programming/ncert_m12_ch12_figure_12_1.png" کہا جاتا ہے۔

تاریخی نوٹ

دنیا دوسری جنگ کے دوران، جب جنگ کی عملیات کو خرچ کم کرنے کے لیے منصوبہ بندی کیا جاتا تھا، تو لائنر پروگرامنگ مسائل کو آگے بڑھایا جاتا تھا۔

لائنر پروگرامنگ میں پہلا مسئلہ 1941 میں روسی ریاضیدان، L. Kantorovich اور ایمریکی معاشرتی اقتصادی، F. L. Hitchcock کے ذریعے جو ان کے دونوں اپنے انفرادی طور پر کام کرتے تھے، شکل دیا گیا تھا۔ اس کو بہت مہمان ذات طریقہ کار کہلایا گیا تھا۔ 1945 میں، ایک انگلش معاشرتی اقتصادی، G.Stigler نے ایک دوسرا لائنر پروگرامنگ مسئلہ بیان کیا تھا - جو کہ ایک اوپٹیمل ڈیٹ کا تعین کرنا تھا۔

1947 میں، ایک ایمریکی معاشرتی اقتصادی، G. B. Dantzig نے ایک مؤثر طریقہ کہلایا تھا جسے سیمپلیکس طریقہ کہلایا جاتا ہے جو لائنر پروگرامنگ مسائل کو منتقل کرنے کے لیے ایک ایٹریشن طریقہ ہے۔

L. Katorovich اور ایمریکی ریاضیاتی معاشرتی اقتصادی، T. C. Koopmans نے 1975 میں اقتصاد کے لیے نوبل گرنٹ کے ساتھ لائنر پروگرامنگ میں اپنے پہلے سے کام کے لیے گرنٹ حاصل کیے۔ کمپیوٹرز اور ضروری سافٹ ویئر کے آنے کے ساتھ، لائنر پروگرامنگ ماڈل کو بہترین طریقے سے چند مسائل کو چند شعبوں میں استعمال کرنے کا فرصت مل گئی۔