Network model (operations research) — সেতু মডেল
সেতু মডেল (অপারেশন রিসার্চে; ইং. Network models) — এটি গাণিতিক মডেলের একটি শ্রেণি যা কোনো সমস্যাকে গ্রাফ (নেটওয়ার্ক) আকারে উপস্থাপন করে, যেখানে শীর্ষবিন্দু (নোড) বস্তু বা অবস্থা নির্দেশ করে এবং ধার (চাপ) — তাদের মধ্যে সংযোগ বা প্রক্রিয়া নির্দেশ করে[1]। অপ্টিমাইজেশনের প্রসঙ্গে নেটওয়ার্ক বলতে প্রায়ই একটি অভিমুখী গ্রাফ বোঝানো হয়, যাকে অপারেশন বিশ্লেষণে সরাসরি «নেটওয়ার্ক» বলা হয়; এই নেটওয়ার্কের শীর্ষবিন্দুগুলিকে নোড এবং ধারগুলিকে চাপ বলা হয়[2]।
সেতু মডেল লজিস্টিক্স, টেলিযোগাযোগ, প্রকল্প ব্যবস্থাপনা এবং অর্থায়নের মতো ক্ষেত্রে জটিল সিস্টেম বিশ্লেষণ ও অপ্টিমাইজেশনের একটি শক্তিশালী হাতিয়ার। এদের শক্তি নিহিত উচ্চ স্তরের বিমূর্ততায়: একটি নোড একটি শহর, একটি কম্পিউটার রাউটার বা একটি প্রকল্পের পর্যায় উপস্থাপন করতে পারে, আর একটি চাপ — একটি সড়ক, একটি যোগাযোগ চ্যানেল বা একটি প্রযুক্তিগত অপারেশন।
সংজ্ঞা ও পরিভাষা
সেতু মডেলের ভিত্তি হলো গ্রাফ তত্ত্ব। মূল ধারণাগুলি হলো:
- প্রবাহ নেটওয়ার্ক (ইং. flow network): একটি অভিমুখী গ্রাফ যেখানে প্রতিটি ধারের ধারণক্ষমতা (capacity) এবং প্রবাহ (flow) রয়েছে। গ্রাফে দুটি বিশেষ শীর্ষবিন্দু চিহ্নিত থাকে: উৎস (source), যেখান থেকে প্রবাহ নির্গত হয়, এবং গন্তব্য (sink), যেখানে প্রবাহ প্রবেশ করে[1]।
- প্রবাহ সংরক্ষণ সূত্র: যেকোনো শীর্ষবিন্দুর জন্য যা উৎস বা গন্তব্য নয়, মোট প্রবেশকারী প্রবাহ মোট নির্গামী প্রবাহের সমান হতে হবে। এই শর্তটি ভৌত সংরক্ষণ সূত্রের বিচ্ছিন্ন সমতুল্য[3]।
- নেটওয়ার্ক পরিকল্পনা: একটি মডেল যা একটি প্রকল্পকে পরস্পর সংযুক্ত অপারেশন (চাপ) এবং ঘটনার (নোড) সমন্বয় হিসেবে উপস্থাপন করে। এই ধরনের নেটওয়ার্কগুলি অভিমুখী অচক্রীয় গ্রাফ, যা কাজের সম্পাদন ক্রম প্রতিফলিত করে[4]।
মূল বৈশিষ্ট্য ও উপপাদ্য
সেতু মডেলগুলি কিছু বিশেষ বৈশিষ্ট্যের অধিকারী, যা তাদের সমাধানে অত্যন্ত কার্যকর অ্যালগরিদম প্রয়োগের সুযোগ দেয়।
- সমাধানের পূর্ণসংখ্যা বৈশিষ্ট্য: নেটওয়ার্ক অপ্টিমাইজেশনের অনেক সমস্যা (যেমন সর্বোচ্চ প্রবাহ বা সংক্ষিপ্ততম পথের সমস্যা) সীমাবদ্ধতা ম্যাট্রিক্সের সম্পূর্ণ ইউনিমডুলারিটির বৈশিষ্ট্য ধারণ করে। এর ফলে, যদি সমস্যার প্যারামিটারগুলি (ধারণক্ষমতা, দৈর্ঘ্য) পূর্ণসংখ্যা হয়, তাহলে রৈখিক প্রোগ্রামিং পদ্ধতিতে পাওয়া সর্বোত্তম সমাধানটিও পূর্ণসংখ্যা হবে, অতিরিক্ত সীমাবদ্ধতা আরোপ ছাড়াই[5][6]।
- সর্বোচ্চ প্রবাহ ও সর্বনিম্ন কাটা উপপাদ্য: প্রবাহ তত্ত্বের কেন্দ্রীয় ফলাফল। এটি বলে যে উৎস থেকে গন্তব্যে সর্বোচ্চ প্রবাহের মান উৎস ও গন্তব্যকে বিভক্তকারী সকল কাটার মধ্যে সর্বনিম্ন ধারণক্ষমতার সমান। এই উপপাদ্য প্রবাহের সর্বোত্তমতার মানদণ্ড স্থাপন করে এবং অনেক অ্যালগরিদমের ভিত্তি[6][7]।
- সংক্ষিপ্ততম পথের অপ্টিমালিটি নীতি: যদি বিন্দু A থেকে বিন্দু C পর্যন্ত পথটি সংক্ষিপ্ততম হয়, তাহলে এর যেকোনো অংশ (যেমন মধ্যবর্তী বিন্দু B থেকে C পর্যন্ত) সংশ্লিষ্ট শীর্ষবিন্দুগুলির মধ্যে সংক্ষিপ্ততম পথ। গতিশীল প্রোগ্রামিংয়ের ভিত্তিতে থাকা এই বৈশিষ্ট্য Dijkstra-র অ্যালগরিদমের মতো পদ্ধতির সঠিকতা নিশ্চিত করে[8]।
- সর্বনিম্ন বিস্তৃত গাছের (MST) বৈশিষ্ট্য:
- কাটার বৈশিষ্ট্য: গ্রাফের যেকোনো কাটার জন্য, কাটাটি অতিক্রমকারী সর্বনিম্ন ওজনের ধারটি অন্তত একটি MST-তে অন্তর্গত।
- চক্রের বৈশিষ্ট্য: গ্রাফের যেকোনো চক্রে সর্বোচ্চ ওজনের ধারটি কোনো MST-তে অন্তর্গত নয়।
Prim ও Kruskal-এর «লোভী» অ্যালগরিদমের সঠিকতা এই বৈশিষ্ট্যগুলির উপর ভিত্তি করে[9]।
নেটওয়ার্ক অপ্টিমাইজেশনের মূল সমস্যাসমূহ
- সংক্ষিপ্ততম পথের সমস্যা: দুটি নির্দিষ্ট নোডের মধ্যে সর্বনিম্ন মোট দৈর্ঘ্য (ওজন) সম্পন্ন পথ খোঁজা। Dijkstra-র অ্যালগরিদম (অঋণাত্মক ওজনের জন্য) বা Bellman-Ford অ্যালগরিদম (যেকোনো ওজনের জন্য) দিয়ে সমাধান করা হয়[8]।
- সর্বোচ্চ প্রবাহের সমস্যা: চাপের নির্দিষ্ট ধারণক্ষমতায় উৎস থেকে গন্তব্যে সর্বোচ্চ সম্ভব প্রবাহ নির্ধারণ করা। সমাধানের ক্লাসিক পদ্ধতি হলো Ford–Fulkerson অ্যালগরিদম[6]।
- সর্বনিম্ন বিস্তৃত গাছের সমস্যা: এমন একটি উপগ্রাফ খোঁজা যা নেটওয়ার্কের সকল শীর্ষবিন্দু সংযুক্ত করে এবং ধারগুলির মোট ব্যয় সর্বনিম্ন।
- ক্রিটিক্যাল পাথ মেথড (CPM): নেটওয়ার্ক পরিকল্পনা মডেলে কাজের দীর্ঘতম ক্রম নির্ধারণ করা, যা পুরো প্রকল্পের সম্ভাব্য সর্বনিম্ন সমাপ্তি সময় নির্ধারণ করে। এই পথের কাজগুলির সময়ের রিজার্ভ শূন্য[10]।
উদাহরণ
- সংক্ষিপ্ততম পথ: শহরের মানচিত্রে দুটি বিন্দুর মধ্যে নেভিগেশন সিস্টেম দ্বারা সর্বোত্তম রুট অনুসন্ধান, যেখানে শহরগুলি নোড এবং সড়কগুলি চাপ যার ওজন দৈর্ঘ্য বা ভ্রমণ সময়ের সমান।
- সর্বোচ্চ প্রবাহ: পাইপলাইন নেটওয়ার্কের সর্বোচ্চ ধারণক্ষমতা নির্ধারণ, যেখানে পাম্পিং স্টেশনগুলি নোড এবং পাইপগুলি সীমিত ধারণক্ষমতাসহ চাপ।
- সর্বনিম্ন বিস্তৃত গাছ: ন্যূনতম মোট কেবল দৈর্ঘ্যে একাধিক শহর সংযুক্ত করার জন্য যোগাযোগ নেটওয়ার্ক ডিজাইন (যেমন অপটিক ফাইবার কেবল বিছানো)।
- ক্রিটিক্যাল পাথ: বাড়ি নির্মাণ প্রকল্পে, যেখানে কাজগুলির (ভিত্তি স্থাপন, দেয়াল নির্মাণ, ছাদ স্থাপন) নির্দিষ্ট সময়কাল ও প্রযুক্তিগত নির্ভরতা রয়েছে, ক্রিটিক্যাল পাথ নির্মাণ সমাপ্তির সর্বনিম্ন সময় নির্ধারণ করে। এই পথের যেকোনো কাজে বিলম্ব পুরো প্রকল্পে বিলম্ব ঘটাবে[10]।
আরও দেখুন
- অপারেশন রিসার্চ
- গ্রাফ তত্ত্ব
- পরিবহন সমস্যা
- ক্রিটিক্যাল পাথ মেথড
- PERT
টীকা
- ↑ 1.0 1.1 "Flow network". Wikipedia. [১]
- ↑ "Тема 10: Сетевые модели". Учебное пособие. Гомель: БелГУТ. [২]
- ↑ "Транспортная сеть". Википедия. [৩]
- ↑ "Сетевое планирование". Википедия. [৪]
- ↑ Bradley S. P., Hax A. C., Magnanti T. L. (1977). Applied Mathematical Programming. Addison-Wesley. Ch.8: Network Models. [৫]
- ↑ 6.0 6.1 6.2 "Задача о максимальном потоке". Википедия. [৬]
- ↑ Goldberg A. V., Tardos É., Tarjan R. E. (1990). "Network Flow Algorithms". In: Paths, Flows, and VLSI-Layout. Springer. [৭]
- ↑ 8.0 8.1 "Задача о кратчайшем пути". Википедия. [৮]
- ↑ "Минимальное остовное дерево". Википедия.
- ↑ 10.0 10.1 "Метод критического пути". Википедия. [৯]