لکیری الجبرا/باب 8

نفاذات

لکیری برمجہ

لکیری پروگرامنگ

سانچہ:اصطلاح برابر لکیری پروگرامنگ ریاضی کی ایک تکنیک ہے جس میں ایسے مسلئے حل کیے جاتے ہیں جن میں ایک اقتصادی منافع دالہ کو زیادہ سے زیادہ کرنا مقصود ہوتا ہے۔ مثلاً ایک کارخانہ میں مختلف اشیا کی تعداد $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{array}{c}{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\\ ⋮\\ a_{m,1}{x}_1+a_{m,2}{x}_2+\cdots +a_{m,n}{x}_n\le b_m\end{array}$

$x_1\ge 0,x_2\ge 0,\cdots ,x_n\ge 0$

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

مصفوفہ صورت

اس مسئلہ کو مصفوفہ صورت یوں لکھا جا سکتا ہے: سمتیہ (بصورت مصفوفہ)

$X=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right]$

کی ایسی قدر ڈھونڈو کہ دالہ

$f(X)=c^{t}X$

زیادہ سے زیادہ ہو، جبکہ دی گئی نامساوات مصفوفہ

$AX\le b$

$X\ge 0$

کی بھی تسکین ہو۔ یہاں A ایک $m\times n$ سائز کی مصفوفہ ہے، اور $b=\left[\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_m\end{array}\right]$ اور $c=\left[\begin{array}{c}{c}_1\\ c_2\\ ⋮\\ c_n\end{array}\right]$

مثال 1

ایک کاشتکار کے پاس 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)=4x+9y$

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

تصویر میں مساوات $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 ہزار کی آمدنی تصور کرتے ہوئے، اس مساوات کے لیے

$4x+9y=40$

سرخ لکیر لگائی ہے۔ اس لکیر پر کسی بھی نقطہ پر آمدنی 40 ہزار ہو گی۔ غور کرو کہ یہ لکیر کونہ $(x,y)=(10,0)$ سے گزرتی ہے۔ اس طرح دوسرے کونوں کو مد نظر رکھتے ہوئے ہم ان مساوات

$4x+9y=50$

$4x+9y=54$

کے مطابق متوازی سرخ لکیریں لگاتے ہیں۔ اب یہ واضح ہے کہ کونہ (نقطہ) $(x,y)=(0,6)$ پر سب سے زیادہ آمدنی (54 ہزار) ہے۔ اس لیے حل یہ ہے کہ 0 ایکڑ پر گاجر کاشت کی جائے اور 6 ایکڑ پر مٹر (یعنی صرف 6 ایکڑ رقبے پر مٹر کاشت کرو، اور باقی 4 ایکڑ فارغ چھوڑ دو)۔

غور کرو کہ نیلی اور کالی لکیریں نقطہ $(x,y)=(8,2)$ پر ملتی ہیں، جو ان متواقت لکیری مساوات کے نظام کا حل ہے۔ مگر یہ حل اس مسئلہ کا حل نہیں چونکہ اس میں آمدنی کا خیال نہیں رکھا گیا۔

حل نکالتے ہوئے ایک دلچسپ بات یہ دیکھنے میں آئی کہ کثیرالاضلاع کے صرف کونوں پر تلاش کرنے سے حل نکل آتا ہے، کثیرالضلاع کے اندر کےنقطوں کو پرکھنے کی ضرورت نہیں ہوتی۔

اگر ہم منڈی کی قیمت بدلیں تو حل بھی بدل سکتا ہے۔ مثلاً اگر مٹر کے9 ہزار ملتے ہوں اور گاجر کے 6 ہزار، یعنی

$f(x,y)=6x+9y$

تو حل نقطہ $(x=8,y=2)$ ہو گا، اور آمدنی 66 ہزار۔

مثال 2

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

ایک کاشتکار کے پاس 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)=4x_1+9x_2+7x_3$

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

$1x_1+2x_2+3x_3\le 12$

مٹر کی فصل کو 10 دن فی ایکڑ مزدوری چاہیے ہوتی ہے، گاجر کو 6 دن فی ایکڑ، اور ٹماٹر کو 11 دن فی ایکڑ۔ کل 100 دن کی مزدوری میسر ہے۔

$6x_1+10x_2+11x_3\le 100$

ہمیں یہ ڈھونڈنا ہے کہ کتنے ایکڑ پر مٹر اُگائے جائیں، کتنے پر گاجر، اور کتنے پر ٹماٹر، تاکہ کاشتکار کو زیادہ سے زیادہ آمدنی ہو۔

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

ثنویت

ثنویت

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

تکبیر $f(X)=c^{t}X$

جبکہ یہ لوازمات پورے ہوں

$AX\le b$

$X\ge 0$

مقدم مسئلہ کہلاتا ہے۔

اس مسئلہ کے ساتھ انتہای قریبی تعلق رکھنے والا مسئلہ:

تصغیر $g(Y)=b^{t}Y$

جبکہ یہ لوازمات پورے ہوں

$A^{t}Y\ge c$

$Y\ge 0$

ثنوی مسئلہ کہلاتا ہے۔ (یہاں الفاظ "تکبیر" اور "تصغیر" صرف و نحو کے حوالے سے فعل ہیں۔)

ان دونوں مسلئوں کا گہرا تعلق نیچے دیہ ہے:

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

1. $f(X)\le g(Y)$
2. اگر ان X اور Y کے لیے، مساوات $f(X)=g(Y)$ ہو، تو یہ X اور Y ان مسائل کے کامل حل ہیں (یعنی X مقدم مسئلہ کی دالہ ‪f()‬ کی تکبیر کرتا ہے، اور Y ثنوی مسلئی کی دالہ g‪()‬ کی تصغیر کرتا ہے)۔ کامل حل کو عموماً $X^{*}$ اور $Y^{*}$ لکھا جاتا ہے (تصویر)۔

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

مثال 3

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

تکبیر

$f(x_1,x_2)=\left[\begin{array}{cc}4& 9\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]$

جبکہ

$\left[\begin{array}{cc}1& 1\\ 1& 2\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]\le \left[\begin{array}{c}10\\ 12\end{array}\right]$

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

$g(y_1,y_2)=10y_1+12y_2$

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

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

$1y_1+1y_2\ge 4$

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

$1y_1+2y_2\ge 9$

تو ثنوی لکیری پروگرامنگ مسئلہ یہ بنا

تصغیر

$g(y_1,y_2)=\left[\begin{array}{cc}10& 12\end{array}\right]\left[\begin{array}{c}{y}_1\\ y_2\end{array}\right]$

جبکہ

$\left[\begin{array}{cc}1& 1\\ 1& 2\end{array}\right]\left[\begin{array}{c}{y}_1\\ y_2\end{array}\right]\ge \left[\begin{array}{c}4\\ 9\end{array}\right]$

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

اس مثال میں ہم نے یہ عجیب بات دیکھی کہ زمین کی قیمت صفر لگی۔ ثنوی لکیری پروگرامنگ مسائل میں ان قیمتوں کو پرچھائیں قیمتیں (shadow prices) کہا جاتا ہے۔ اس کا یہ مطلب نہیں کہ زمین کی کوئی وقعت نہیں۔ صرف یہ کہ منڈی (مارکیٹ) کے حوالے سے اس ایک مسئلہ کے تناظر میں ان اشیاء کا بھاؤ یہ (پرچھائیں قیمت) لگا۔

بیرونی روابط

• سائیلیب سبق
• بہت زیادہ متغیر میں لکیری پروگرامنگ مسئلہ کے کمپیوٹر پر حل کے لیے lpsolve

اقل مربعات تقرب

اقل مربعات تقرب

سانچہ:اصطلاح برابر تجربات سے اکثر ایسا ڈیٹا اکٹھا ہوتا ہے جسے کسی کثیر رقمی سے تقرب کرنا مفید رہتا ہے۔ فرض کرو کہ کسی تجربے کے نتیجے میں ہمیں n پیمائش جوڑے ملتی ہیں:

$(x_1,y_1),(x_2,y_2),\cdots ,(x_n,y_n)$

ان کے گراف کو دیکھتے ہوئے ہم یہ فیصلہ کرتے ہیں کہ یہ دالہ $y=f(x)$، ذیل میں سے کسی کثیر رقمی

1. $y=ax+b$     (گراف راست خط)
2. $y=a{x}^2+bx+c$     (درجہ دوم کثیر رقمی)
3. $y=a{x}^3+b{x}^2+cx+d$     (سہ کثیر رقمی)
4. $\cdots \cdots \cdots \cdots \cdots$
5. $y=c_m{x}^m+c_{m-1}{x}^{m-1}+c_{1}x+c_0$     (m کثیر رقمی)

سے تقرب کی جا سکتی ہے۔

تصویر میں گیارہ نقطوں (x,y) کا درجہ دوم کثیر رقمی سے تقرب کیا گیا ہے۔

تجربہ سے حاصل ہونے والے n جوڑے اگر درجہ m کے کثیر رقمی میں ایک ایک کر کے ڈالے جائیں تو ہمارے پاس n مساوات حاصل ہونگی، جنہیں درج ذیل مصفوفہ مساوات کی صورت لکھا جا سکتا ہے (عام طور پر $n>m$ ):

$Y=MC$

$Y=\left[\begin{array}{c}{y}_1\\ y2\\ ⋮\\ y_n\end{array}\right],M=\left[\begin{array}{ccccc}1& x_1& x_1^2& \cdots & x_1^m\\ 1& x_2& x_2^2& \cdots & x_2^m\\ ⋮& ⋮& & ⋮\\ 1& x_n& x_n^2& \cdots & x_n^m\end{array}\right],C=\left[\begin{array}{c}{c}_0\\ c_1\\ ⋮\\ c_m\end{array}\right]$

عام طور پر یہ متواقت لکیری مساوات کا نظام ناموافق ہو گا، اس لیے اس کا کوئی حل نہیں ہو گا، یعنی ایسا کوئی C نہیں جو ان مساوات کی تسکین کرے۔ اس لیے کوشش یہ ہو گی کہ ایسا $C^{*}$ نکلا جائے جس کا غلطی سمتیہ $e=Y-M{C}^{*}$ کم سے کم ہو۔ یعنی غلطی سمتیہ کا امثولہ $\Vert e\Vert$ کم سے کم ہو۔

چونکہ سمتیہ Y فضا ${ℝ}^n$ میں ہے، اس لیے ہمیں اقلیدسی فضا میں امثولہ کی عام تعریف استعمال کرتے ہوئے

$\Vert e{\Vert }^2=e_1^2+e_2^2+\cdots +e_n^2$

کی تصغیر کرنا ہے۔

اب لکیری فضا ${ℝ}^{m+1}$ کے کسی سمتیہ C کے لیے، سمتیہ $MC$ ، مصفوفہ M کی ستون فضا میں ہے، جو ${ℝ}^n$ کی لکیری ذیلی فضا ہے۔ اب مسقط کی تعریف سے ہم جانتے ہیں، کہ سمتیہ Y کا مصفوفہ M کی ستون فضا میں مسقط، غلطی امثولہ $\Vert e\Vert$ کی تصغیر کرتا ہے۔ ذیلی فضا $MC$ میں سمتیہ Y کے مسقط کو ہم $M{C}^{*}$ لکھتے ہیں۔ بہترین تقرب مسئلہ اثباتی کی رو سے غلطی سمتیہ قائم الزاویہ ہو گا ذیلی فضا کے۔ دوسرے الفاظ میں غلطی سمتیہ اور مصفوفہ M کی ستون فضا کے کسی بھی سمتیہ MC کا "اندرونی حاصل ضرب" صفر ہو گا:

$(MC{)}^t(Y-M{C}^{*})=0$

(اقلیدسی فضا میں اندرونی حاصل ضرب کی عام تعریف استعمال کرتے ہوئے)،
یا

$C^t{M}^t(Y-M{C}^{*})=0$

$C^t(M^{t}Y-M^{t}M{C}^{*})=0$

$⟨M^{t}Y-M^{t}M{C}^{*},C⟩=0$

جس سے یہ نتیجہ اخذ کیا جا سکتا ہے کہ

$M^{t}Y-M^{t}M{C}^{*}=0$

یا

$M^{t}M{C}^{*}=M^{t}Y$

اگر مصفوفہ $M^{t}M$ مقلوب ہو تو حل یہ ہو گا

$C^{*}=(M^{t}M{)}^{-1}{M}^{t}Y$

$E=m{c}^2$     یہاں ریاضی مساوات کو بائیں سے دائیں (LTR) پڑھو     ریاضی علامات