فرمول بندی برنامه ریزی صحیح برای مسیله طراحی شبکه K - یال - همبند 3- گام محدود

در این مقاله مسیله طراحی شبکه K- یال - همبند L - گام محدود را بررسی می کنیم. گراف وزن دار V,E و مجموعه D از جفت گره ها داده شده است. مسیله طراحی شبکه K - یال همبند L گام محدود شامل یافتن مینیم وزن زیر گراف G حاوی حداقل K مسیر یال مجزا از طول حداکثر L بین هر جفت s,tεD است. مسیله طراحی شبکه K یال همبند L گام محدود را در حالت های L=2.3 بررسی می کنیم. ابتدا فرمول بندی برنامه ریزی صحیح را مطرح می کنیم و سپس یک فرمول بندی برنامه ریزی جدید برای مسیله ای که براساس تغییر و تحول گراف، از یک گراف غیر جهت دار اولیه به یک گراف لایه بندی شده جهت دار تبدیل شده را معرفی می کنیم. در پایان این فرمول بندی ها را با استفاده از CPLEX آزمایش می کنیم.

کلیدواژه ها:

مسیرهای یال ، مجزا ، جریان ، فرمول بندی جداشده