توسیع مسئله کوتاهترین مسیر به کمک کارایی متقاطع

Authorsمصطفی داوطلب علیائی، فاطمه قندی
Conference Titleچهل و هشتمین کنفرانس ریاضی ایران
Holding Date of Conferenceشهریور ۹۶
Event Placeهمدان
PresentationSPEECH
Conference LevelNational Conferences

Abstract

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