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) نیز کوتاهترین مسیر میان رأسهای متناظر است. این ویژگی که پایهٔ برنامهریزی پویا است، صحت الگوریتمهایی چون الگوریتم دایکسترا را توجیه میکند[8].
- ویژگیهای درخت پوشای کمینه (MST):
- ویژگی برش: برای هر برشی از گراف، یالی با کمترین وزن که از برش عبور میکند، به حداقل یک درخت پوشای کمینه تعلق دارد.
- ویژگی دور: در هر دوری از گراف، یالی با بیشترین وزن به هیچ درخت پوشای کمینهای تعلق ندارد.
صحت الگوریتمهای «حریصانهٔ» پریم و کروسکال بر این ویژگیها استوار است[9].
مسائل اصلی بهینهسازی شبکه
- مسئلهٔ کوتاهترین مسیر: یافتن مسیری با کمترین طول (وزن) کل میان دو گرهٔ مشخص. با الگوریتم دایکسترا (برای وزنهای غیرمنفی) یا الگوریتم بلمن-فورد (برای وزنهای دلخواه) حل میشود[8].
- مسئلهٔ جریان بیشینه: تعیین بیشترین جریان ممکن از منبع به مقصد با توجه به ظرفیتهای دادهشدهٔ کمانها. روش کلاسیک حل، الگوریتم فورد - فالکرسون است[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 "Метод критического пути". Википедия. [۹]