چکیده :

در اين مقاله، مساله‌ی کوتاهترين مسير در شبکه‌های پويا بررسی می‌شود که در آن بردار هزينه يک متغير تصادفی است. تصادفی بودن با يک رويکرد چند سناريويي توصيف می‌شود که هر سناريو يک حالت ممکن از بردار هزينه را نشان می‌دهد. مدل‌بندی تجميع سناريو برای مساله کوتاهترين مسير تصادفی در شبکه جريان پويا بيان می‌گردد که تصادفی بودن را با به‌کارگيری نمونه به‌جای توزيع، مدل‌بندی می‌کند. در اين مدل، هر سناريو يک زيرمساله کوتاهترين مسير توليد می‌کند و مساله اصلی چندين قيود ديگر به‌نام قيود غير قابل پش‌بينی دارد که وابستگی بين سناريوها را نشان می‌دهد. سرانجام برای حل اين مساله، الگوريتمی با مرتبه‌ي زمانی چندجمله‌ای ارايه ‌می‌گردد.

کلید واژگان :

مساله‌ کوتاهترين مسير، شبکه جريان پويا، برنامه‌ريزی تصادفی.



ارزش ریالی : 200000 ریال
دریافت مقاله
با پرداخت الکترونیک