مسائل جريان در شبكه با توابع هزينه مقعر (MCNEP)

اصفهان : دانشگاه صنعتي اصفهان . دانشكده صنايع

كارشناسي ارشد

يكي از مسائل مهم در شبكه ، مسئله جريان در شبكه به منظور كمينه كردن هزينه كل جريان است . در حالتي كه توابع هزينه تعريف شده روي كمانها، توابعي مقعر از حجم جريان باشند، مسئله متعلق به خانواده مسائل سخت غيرقابل حل در زمان چندجمله اي است و كاربردهاي وسيعي در زمينه هاي مختلف از قبيل برنامه ريزي توليد، حمل و نقل ، شبكه هاي مخابراتي و طراحي شبكه و ... دارد. به دليل تقعر تابع هدف ، جواب بهينه اين گونه مسائل در حالت تك كالايي يا چند كالايي ، يك جريان حدي است و جريان حدي، جرياني است كه براي هر كالا يك درخت جريان ايجاد مي كند يا به عبارتي كمانهاي غيراشباع در جريان حدي، مجموعه اي از درختها به وجود مي آورند. براين اساس راه حلهاي زيادي با استفاده از آلگوريتم هاي شاخه و كران ، برنامه ريزي پويا، ايجاد همسايگي ها و روشهاي ابداعي ارائه شده است . در اين پايان نامه يك آلگوريتم ژنتيك روي مسئله جريان چند كالايي بدون محدوديت ظرفيتي پياده سازي شده و نتايج آن با يك آلگوريتم ابداعي كاراي ديگر مقايسه شده است . همچنين يك روش لاگرانژي نيز با تركيب روشهاي ابداعي مناسب براي مسئله جريان چند كالايي با محدوديت ظرفيتي كمانها مورد بررسي قرار گرفته است .

7101

([مهندسي صنايع])

مهندسي صنايع و سيستم ها

دانشگاه صنعتي اصفهان

محمدرضا زماني

سعيده كتابي