Network model (operations research) — نیٹ ورک ماڈلز
Jump to navigation
Jump to search
نیٹ ورک ماڈلز (آپریشنز ریسرچ میں؛ انگریزی: Network models) — یہ ریاضیاتی ماڈلوں کا ایک طبقہ ہے جو کسی مسئلے کو گراف (نیٹ ورک) کی شکل میں پیش کرتا ہے، جہاں رأس (نوڈز) اشیاء یا حالتوں کو ظاہر کرتے ہیں، اور کنارے (قوسیں) ان کے درمیان روابط یا عمل کو ظاہر کرتے ہیں[1]۔ اصلاح (optimization) کے تناظر میں نیٹ ورک سے اکثر ایک ہدایت یافتہ گراف مراد لیا جاتا ہے، جسے آپریشنل تجزیے میں براہ راست «نیٹ ورک» کہا جاتا ہے؛ ایسے نیٹ ورک کے رأس کو نوڈز اور کناروں کو قوسیں کہتے ہیں[2]۔
نیٹ ورک ماڈلز لاجسٹکس، ٹیلی کمیونیکیشن، پروجیکٹ مینجمنٹ اور مالیات جیسے شعبوں میں پیچیدہ نظاموں کے تجزیے اور اصلاح کے لیے ایک طاقتور ذریعہ ہیں۔ ان کی قوت تجرید کی بلند سطح میں مضمر ہے: ایک نوڈ کسی شہر، کمپیوٹر روٹر یا پروجیکٹ کے مرحلے کو ظاہر کر سکتا ہے، اور ایک قوس کسی سڑک، مواصلاتی چینل یا تکنیکی آپریشن کو۔
تعریف اور اصطلاحات
نیٹ ورک ماڈلز کی بنیاد گراف تھیوری پر ہے۔ اہم تصورات درج ذیل ہیں:
- فلو نیٹ ورک (انگریزی: flow network): ایک ہدایت یافتہ گراف جس میں ہر کنارے کی گنجائش (capacity) اور بہاؤ (flow) ہوتا ہے۔ گراف میں دو خاص رأس ہوتے ہیں: ماخذ (source)، جہاں سے بہاؤ نکلتا ہے، اور منتہا (sink)، جہاں وہ داخل ہوتا ہے[1]۔
- بہاؤ کے تحفظ کا قانون: کسی بھی ایسے رأس کے لیے جو ماخذ یا منتہا نہ ہو، کل آنے والا بہاؤ کل جانے والے بہاؤ کے برابر ہونا چاہیے۔ یہ شرط تحفظ کے طبیعی قوانین کا ایک منفصل مماثل ہے[3]۔
- نیٹ ورک پلاننگ: ایک ماڈل جو کسی پروجیکٹ کو باہم مربوط آپریشنز (قوسوں) اور واقعات (نوڈز) کے مجموعے کے طور پر پیش کرتا ہے۔ ایسے نیٹ ورک ہدایت یافتہ چکر سے پاک گراف ہوتے ہیں، جو کاموں کی ترتیب کی عکاسی کرتے ہیں[4]۔
اہم خصوصیات اور نظریات
نیٹ ورک ماڈلز میں کچھ خاص خصوصیات ہوتی ہیں جو انہیں حل کرنے کے لیے انتہائی مؤثر الگورتھم کے استعمال کی اجازت دیتی ہیں۔
- حلوں کی عددی صحت: نیٹ ورک اصلاح کے بہت سے مسائل (مثلاً زیادہ سے زیادہ بہاؤ یا مختصر ترین راستے کا مسئلہ) پابندیوں کی میٹرکس کی مکمل یونی ماڈیولیریٹی کی خاصیت رکھتے ہیں۔ اس کی بدولت، اگر مسئلے کے پیرامیٹر (گنجائش، لمبائی) صحیح اعداد ہوں، تو لکیری پروگرامنگ کے طریقوں سے حاصل کردہ بہترین حل بھی اضافی پابندیاں لگائے بغیر صحیح عدد ہو گا[5][6]۔
- زیادہ سے زیادہ بہاؤ اور کم سے کم کٹ کا نظریہ: بہاؤ تھیوری کا مرکزی نتیجہ۔ یہ بیان کرتا ہے کہ ماخذ سے منتہا تک زیادہ سے زیادہ بہاؤ کی مقدار ان تمام کٹوں میں سے کم سے کم گنجائش کے برابر ہے جو ماخذ اور منتہا کو الگ کرتے ہیں۔ یہ نظریہ بہاؤ کے لیے بہترینیت کا معیار قائم کرتا ہے اور بہت سے الگورتھم کی بنیاد ہے[6][7]۔
- مختصر ترین راستوں کے لیے بہترینیت کا اصول: اگر نقطہ الف سے نقطہ ج تک کا راستہ مختصر ترین ہے، تو اس کا کوئی بھی حصہ (مثلاً درمیانی نقطہ ب سے ج تک) بھی متعلقہ رأس کے درمیان مختصر ترین راستہ ہوگا۔ یہ خاصیت، جو dynamic programming کی بنیاد ہے، Dijkstra جیسے الگورتھم کی درستگی کو ممکن بناتی ہے[8]۔
- کم سے کم پھیلاؤ والے درخت (Minimum Spanning Tree) کی خصوصیات:
- کٹ کی خاصیت: گراف کے کسی بھی کٹ کے لیے، وہ کنارہ جس کا وزن سب سے کم ہو اور جو کٹ کو عبور کرے، کم از کم ایک MST میں موجود ہوتا ہے۔
- چکر کی خاصیت: گراف کے کسی بھی چکر میں، سب سے زیادہ وزن والا کنارہ کسی بھی MST میں موجود نہیں ہوتا۔
انہی خصوصیات پر Prim اور Kruskal کے «لالچی» الگورتھم کی درستگی مبنی ہے[9]۔
نیٹ ورک اصلاح کے بنیادی مسائل
- مختصر ترین راستے کا مسئلہ: دو مقررہ نوڈز کے درمیان کم سے کم مجموعی لمبائی (وزن) کا راستہ تلاش کرنا۔ یہ Dijkstra کے الگورتھم (غیر منفی اوزان کے لیے) یا Bellman-Ford کے الگورتھم (من مانے اوزان کے لیے) سے حل کیا جاتا ہے[8]۔
- زیادہ سے زیادہ بہاؤ کا مسئلہ: قوسوں کی مقررہ گنجائش کے ساتھ ماخذ سے منتہا تک زیادہ سے زیادہ ممکنہ بہاؤ معلوم کرنا۔ حل کا کلاسک طریقہ Ford–Fulkerson الگورتھم ہے[6]۔
- کم سے کم پھیلاؤ والے درخت کا مسئلہ: ایسا ذیلی گراف تلاش کرنا جو نیٹ ورک کے تمام رأس کو جوڑے اور کناروں کی کم سے کم مجموعی لاگت رکھتا ہو۔
- Critical Path Method (CPM): نیٹ ورک پلاننگ ماڈلز میں کاموں کی سب سے طویل ترتیب معلوم کرنا، جو پورے پروجیکٹ کی کم سے کم ممکنہ مدت متعین کرتی ہے۔ اس راستے پر موجود کاموں کا وقت کا ذخیرہ صفر ہوتا ہے[10]۔
مثالیں
- مختصر ترین راستہ: شہر کے نقشے پر دو نقاط کے درمیان نیویگیشن سسٹم کے ذریعے بہترین راستے کی تلاش، جہاں شہر نوڈز ہیں اور سڑکیں قوسیں جن کے اوزان لمبائی یا سفر کے وقت کے برابر ہیں۔
- زیادہ سے زیادہ بہاؤ: پائپ لائن نیٹ ورک کی زیادہ سے زیادہ گنجائش معلوم کرنا، جہاں پمپنگ اسٹیشن نوڈز ہیں اور پائپ محدود گنجائش والی قوسیں ہیں۔
- کم سے کم پھیلاؤ والا درخت: کئی شہروں کو کم سے کم کل کیبل لمبائی کے ساتھ جوڑنے کے لیے مواصلاتی نیٹ ورک کی ڈیزائننگ (مثلاً آپٹک فائبر کیبل بچھانا)۔
- کریٹیکل پاتھ: گھر کی تعمیر کے پروجیکٹ میں، جہاں کاموں (بنیاد رکھنا، دیواریں اٹھانا، چھت نصب کرنا) کی مقررہ مدت اور تکنیکی انحصار ہوتے ہیں، کریٹیکل پاتھ تعمیر کی کم سے کم مدت متعین کرتا ہے۔ اس راستے پر کسی بھی کام میں تاخیر پورے پروجیکٹ میں تاخیر کا باعث بنے گی[10]۔
مزید دیکھیے
- آپریشنز ریسرچ
- گراف تھیوری
- ٹرانسپورٹیشن مسئلہ
- Critical Path Method
- PERT
حواشی
- ↑ 1.0 1.1 "Flow network". Wikipedia. [1]
- ↑ "Тема 10: Сетевые модели". Учебное пособие. Гомель: БелГУТ. [2]
- ↑ "Транспортная сеть". Википедия. [3]
- ↑ "Сетевое планирование". Википедия. [4]
- ↑ Bradley S. P., Hax A. C., Magnanti T. L. (1977). Applied Mathematical Programming. Addison-Wesley. Ch.8: Network Models. [5]
- ↑ 6.0 6.1 6.2 "Задача о максимальном потоке". Википедия. [6]
- ↑ Goldberg A. V., Tardos É., Tarjan R. E. (1990). "Network Flow Algorithms". In: Paths, Flows, and VLSI-Layout. Springer. [7]
- ↑ 8.0 8.1 "Задача о кратчайшем пути". Википедия. [8]
- ↑ "Минимальное остовное дерево". Википедия.
- ↑ 10.0 10.1 "Метод критического пути". Википедия. [9]