شماره ركورد كنفرانس :
5432
عنوان مقاله :
يك الگوريتم نيوتن گسسته براي مسأله ممانعت از كمترين st-برش
پديدآورندگان :
طيبي جواد javadatyyebi@birjandut.ac.ir دانشيار گروه مهندسي صنايع، دانشكده، دانشگاه صنعتي بيرجند، بيرجند، ايران , حيدري هفتادر حسين hosein8212@gmail.com دانشجوي دكتري گروه رياضي، دانشكده علوم، دانشگاه بيرجند، بيرجند، ايران
كليدواژه :
مسأله ممانعت , برش كمينه , الگوريتم نيوتن , ريشه يابي , توابع قطعه قطعه خطي.
عنوان كنفرانس :
شانزدهمين كنفرانس بين المللي انجمن ايراني تحقيق در عمليات
چكيده فارسي :
مسأله كمترين st-برش يكي از مشهورترين مسايل بهينه‌سازي است كه فصل مشترك دسته مسايل برنامه‌ريزي خطي، بهينه‌سازي شبكه و بهينه‌سازي تركيبياتي است. جدا از اين كه اين مسأله، دوگان مسأله معروف بيشترين جريان بوده و از لحاظ نظري اهميت دارد، از منظر كاربرد نيز بسيار مورد توجه محققين قرار گرفته است. در اين مقاله يك توسيع از اين مسأله را در قالب نظريه بازيها بررسي مي‌كنيم. مسأله مورد نظر را ممانعت از كمترين st-برش مي‌ناميم. مسأله داراي دو بازيكن مهاجم و مدافع است. مهاجم سعي در انفصال خطوط مواصلاتي بين دو نقطه را با انتخاب كمترين برش داشته و مدافع با استحكام بخشي اين خطوط مي‌خواهد جلوي عملكرد مهاجم را تا حد ممكن بگيرد. در اين مقاله، يك الگوريتم زمان چندجمله‌اي براي حل مسأله پيشنهاد مي‌شود. اين الگوريتم از روش ريشه‌يابي نيوتن-كاتس استفاده كرده و در تعداد متناهي تكرار جواب دقيق مسأله را مي‌يابد.
