حالت کلی تساوی جریان کمان‌ها در شبکه‌های جریان چند‌کالایی

نویسندگان

چکیده

در این مقاله مسئله شبکه جریان چند کالایی با جریان‌های مساوی روی کمان‌های معین مطرح می‌شود. قیود تساوی ایجاب می‌کند که جریان کمان‌های عضو زیر مجموعه‌های معین، برای کالاهای مجزا و مشخص مساوی باشند. به‌منظور حل این مسئله ابتدا با استفاده از الگوریتم تخصیص ظرفیت یک جواب شروع، برای مسئله به وجود می‌آوریم. سپس با استفاده از تکنیک تخفیف لاگرانژین روی قیود کلی یک کران پایین، و بعد با استفاده از الگوریتم سیمپلکس شبکه محاط‌شده، یک کران بالا را برای مقدار تابع هدف محاسبه می‌کنیم آنگاه کران‌های بالا و پایین را تعدیل کرده تا به جواب بهینه یا جواب بسیار نزدیک به بهینه برسیم.

کلیدواژه‌ها