Linear programming — لکیری پروگرامنگ
لکیری پروگرامنگ — یہ ریاضیاتی پروگرامنگ کی ایک شاخ اور آپریشنز ریسرچ کا ایک وسیع پیمانے پر استعمال ہونے والا طریقہ ہے، جو لکیری فنکشن کے انتہائی قدر (زیادہ سے زیادہ یا کم سے کم) کی تلاش کے مسائل کو حل کرنے کی نظریہ اور طریقوں کی ترقی کے لیے وقف ہے، جب کہ لکیری پابندیاں موجود ہوں۔
لکیری پروگرامنگ معیشت، انتظام، منصوبہ بندی، لاجسٹکس اور دیگر شعبوں میں اصلاح کے مسائل حل کرنے کے لیے سب سے طاقتور اور کثرت سے استعمال ہونے والے اوزاروں میں سے ایک ہے۔
موضوع اور مقصد
لکیری پروگرامنگ کا بنیادی مسئلہ — محدود وسائل کو کسی ہدف کے حصول کے لیے بہترین (زیادہ سے زیادہ موزوں) طریقے سے تقسیم کرنا ہے، جب کہ ہدف اور وسائل کے استعمال پر پابندیاں دونوں لکیری تعلقات کے ذریعے ظاہر کی جا سکیں۔
- لکیری پروگرامنگ ایسے عملی مسائل حل کرنے کی اجازت دیتی ہے جیسے:
- پیداوار کی بہترین منصوبہ بندی۔
- نقل و حمل کے بہاؤ کی اصلاح (ٹرانسپورٹ مسئلہ)۔
- سرمایہ کاری کی بہترین تقسیم۔
- مواد کی بہترین کٹائی۔ تفویض کا مسئلہ۔
لکیری پروگرامنگ کے مسئلے کی ریاضیاتی تشکیل
لکیری پروگرامنگ کا معیاری مسئلہ درج ذیل طور پر بیان کیا جاتا ہے:
فیصلہ سازی کے متغیرات کی ایسی قدریں تلاش کرنا ضروری ہے جو لکیری ہدفی فنکشن کو زیادہ سے زیادہ یا کم سے کم کریں۔ اس کے ساتھ فیصلہ سازی کے متغیرات پر لکیری مساوات اور/یا لکیری ناہمواریوں کے نظام کی صورت میں پابندیاں عائد ہوتی ہیں۔ عام طور پر فیصلہ سازی کے متغیرات کی عدم منفیت کی شرط بھی شامل کی جاتی ہے (ان کی قدریں صفر سے زیادہ یا اس کے برابر ہونی چاہئیں)، جو اکثر مسئلے کے طبیعی یا معاشی معنی سے لازمی ہوتی ہے۔
ریاضیاتی طور پر اس کا مطلب لکیری فنکشنز اور لکیری مساوات/ناہمواریوں کے نظاموں کے ساتھ کام کرنا ہے۔
لکیری پروگرامنگ کے بنیادی تصورات
- فیصلہ سازی کے متغیرات (قابلِ کنٹرول متغیرات): وہ مقداریں جن کی قدریں مسئلے کو حل کرنے کے عمل میں متعین کرنی ہوتی ہیں (مثلاً مختلف مصنوعات کی پیداوار کے حجم، مختلف اہداف کے لیے مختص وسائل کی مقدار)۔
- ہدفی فنکشن: فیصلہ سازی کے متغیرات کا لکیری فنکشن، جس کی قدر کو زیادہ سے زیادہ یا کم سے کم کرنا ہوتا ہے۔ یہ مسئلے کے ہدف کو مقداری طور پر ظاہر کرتا ہے (مثلاً کل منافع، مجموعی اخراجات)۔
- پابندیاں: لکیری مساوات اور/یا ناہمواریوں کا نظام جن کو فیصلہ سازی کے متغیرات کو پورا کرنا ہوتا ہے۔ پابندیاں وسائل کی حدود، تکنیکی ضروریات، منصوبہ بندی کے اہداف اور مسئلے کی دیگر شرائط کو ظاہر کرتی ہیں۔
- قابلِ قبول حل کا علاقہ: فیصلہ سازی کے متغیرات کی تمام قدروں کے مجموعوں کا سیٹ جو مسئلے کی تمام پابندیوں کو پورا کرتے ہیں۔ ہندسی طور پر کثیر الجہتی فضا میں قابلِ قبول حل کا علاقہ ایک محدب کثیر الاضلاع (پولی ہیڈرون) کی شکل اختیار کرتا ہے، جو ممکنہ طور پر غیر محدود یا خالی ہو سکتا ہے۔
- قابلِ قبول حل: متغیرات کی قدروں کا کوئی بھی مجموعہ جو قابلِ قبول حل کے علاقے سے تعلق رکھتا ہو۔
- زیادہ سے زیادہ موزوں حل: وہ قابلِ قبول حل جس میں ہدفی فنکشن اپنی انتہائی (زیادہ سے زیادہ یا کم سے کم) قدر تک پہنچتا ہے۔ اگر زیادہ سے زیادہ موزوں حل موجود ہو تو یہ ہمیشہ قابلِ قبول حل کے علاقے کی سرحد پر، کم از کم محدب کثیر الاضلاع کے ایک کونے پر موجود ہوتا ہے (لکیری پروگرامنگ کا بنیادی نظریہ)۔
لکیری پروگرامنگ کے مسائل حل کرنے کے طریقے
لکیری پروگرامنگ کے مسائل حل کرنے کے لیے کئی بنیادی طریقے موجود ہیں:
- گرافیکل طریقہ: دو فیصلہ سازی متغیرات والے مسائل کے لیے استعمال ہوتا ہے۔ یہ قابلِ قبول حل کے علاقے اور ہدفی فنکشن کو ہموار سطح پر واضح طور پر دکھانے اور قابلِ قبول حل کے علاقے کے کونوں کے تجزیہ یا ہدفی فنکشن کی سطح کی لکیر کو منتقل کرنے کے ذریعے زیادہ سے زیادہ موزوں حل تلاش کرنے کی اجازت دیتا ہے۔
- سمپلیکس طریقہ: جارج ڈینٹزگ کا تیار کردہ ایک عالمگیر تکراری الگورتھم۔ یہ طریقہ قابلِ قبول حل کے علاقے کے ایک کونے سے پڑوسی کونے کی طرف یکے بعد دیگرے منتقل ہوتا ہے، ہر مرحلے میں ہدفی فنکشن کی قدر کو بہتر بناتا ہے، یہاں تک کہ زیادہ سے زیادہ موزوں حل مل جائے۔ یہ لکیری پروگرامنگ کے مسائل حل کرنے کا کلاسک اور سب سے مشہور طریقہ ہے۔
- داخلی نقطہ کے طریقے: الگورتھموں کا ایک متبادل درجہ جو سمپلیکس طریقہ کے بعد ظہور میں آیا۔ یہ قابلِ قبول حل کے علاقے کے اندر سے زیادہ سے زیادہ موزوں حل کی طرف بڑھتے ہیں، نہ کہ اس کی سرحدوں کے ساتھ۔ یہ طریقے بہت بڑی جہت والے لکیری پروگرامنگ کے مسائل حل کرنے کے لیے خاص طور پر کارآمد ہیں۔
لکیری پروگرامنگ میں دوہریت
ہر لکیری پروگرامنگ کے مسئلے (جسے اصل مسئلہ کہا جاتا ہے) سے ایک اور لکیری پروگرامنگ مسئلہ منسلک کیا جا سکتا ہے، جسے دوہرا مسئلہ کہتے ہیں۔ اصل اور دوہرا مسئلہ ایک دوسرے سے گہرا تعلق رکھتے ہیں:
ایک مسئلے کا حل دوسرے کے حل کے بارے میں معلومات فراہم کرتا ہے۔ دونوں مسائل میں ہدفی فنکشنز کی زیادہ سے زیادہ موزوں قدریں ایک جیسی ہوتی ہیں (اگر وہ موجود ہوں)۔ دوہرے مسئلے کے متغیرات کی ایک اہم معاشی تشریح ہوتی ہے — یہ وسائل کی سایہ قیمتوں (یا دوہری قدروں) کے مطابق ہوتے ہیں، یہ ظاہر کرتے ہوئے کہ متعلقہ وسائل کی پابندی میں معمولی تبدیلی سے اصل مسئلے کی ہدفی فنکشن کی زیادہ سے زیادہ موزوں قدر کتنی بدل جائے گی۔
لکیری پروگرامنگ کا اطلاق
لکیری پروگرامنگ درج ذیل شعبوں میں وسیع پیمانے پر استعمال ہوتی ہے:
- معیشت اور کاروبار میں (پیداوار کی منصوبہ بندی، لاجسٹکس، مالیات، مارکیٹنگ)۔
- صنعت میں (تکنیکی عمل کی اصلاح، ذخیرہ کا انتظام، مواد کی کٹائی)۔
- نقل و حمل میں (راستوں اور شیڈولز کی اصلاح)۔ زراعت میں (کاشت کاری کے رقبے اور خوراک کے راشن کی اصلاح)۔
- توانائی میں (بجلی پیدا کرنے والی صلاحیتوں کی بوجھ کی اصلاح)۔
کتابیات
- ڈینٹزگ جے. لکیری پروگرامنگ، اس کے استعمالات اور تعمیمات۔ — ماسکو: پروگریس، 1966۔
- یودن ڈی. بی.، گولڈشٹین ای. جی. لکیری پروگرامنگ (نظریہ، طریقے اور اطلاقات)۔ — ماسکو: ناوکا، 1969۔
- Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
- Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)
مزید دیکھیے
- آپریشنز ریسرچ
- اصلاح
- ہدفی فنکشن
- پابندیاں
- قابلِ قبول حل کا علاقہ
- زیادہ سے زیادہ موزوں حل