|
|
|
|
یک الگوریتم نیوتن گسسته برای مساله ممانعت از کمترین st-برش
|
|
|
|
|
|
|
|
نویسنده
|
طیبی جواد ,حیدری هفتادر حسین
|
|
منبع
|
شانزدهمين كنفرانس بين المللي انجمن ايراني تحقيق در عمليات - 1402 - دوره : 16 - شانزدهمین کنفرانس بین المللی انجمن ایرانی تحقیق در عملیات - کد همایش: 02230-33623 - صفحه:0 -0
|
|
چکیده
|
مساله کمترین st-برش یکی از مشهورترین مسایل بهینه‌سازی است که فصل مشترک دسته مسایل برنامه‌ریزی خطی، بهینه‌سازی شبکه و بهینه‌سازی ترکیبیاتی است. جدا از این که این مساله، دوگان مساله معروف بیشترین جریان بوده و از لحاظ نظری اهمیت دارد، از منظر کاربرد نیز بسیار مورد توجه محققین قرار گرفته است. در این مقاله یک توسیع از این مساله را در قالب نظریه بازیها بررسی می‌کنیم. مساله مورد نظر را ممانعت از کمترین st-برش می‌نامیم. مساله دارای دو بازیکن مهاجم و مدافع است. مهاجم سعی در انفصال خطوط مواصلاتی بین دو نقطه را با انتخاب کمترین برش داشته و مدافع با استحکام بخشی این خطوط می‌خواهد جلوی عملکرد مهاجم را تا حد ممکن بگیرد. در این مقاله، یک الگوریتم زمان چندجمله‌ای برای حل مساله پیشنهاد می‌شود. این الگوریتم از روش ریشه‌یابی نیوتن-کاتس استفاده کرده و در تعداد متناهی تکرار جواب دقیق مساله را می‌یابد.
|
|
کلیدواژه
|
مساله ممانعت؛ برش کمینه؛ الگوریتم نیوتن؛ ریشه یابی؛ توابع قطعه قطعه خطی.
|
|
آدرس
|
, iran, , iran
|
|
پست الکترونیکی
|
hosein8212@gmail.com
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|