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

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

Keywords:

مسیرهای یال- مجزا , جریان , فرمول بندی جدا شده , تغییر و تحول گراف , مسیر غیر-جهت دار