بخشی از مقاله
تجزیه بندر یک روشی سیستماتیک برای حل مسائل بزرگ برنامه ریزی خطی یا مسائل برنامه ریزی خطی با ساختار ویژه قید ها میباشد. استراتژی این روشی به این نحو است که روی دو مساله برنامه ریزی خطی مجزا عمل می کند، که یکی از این مسائلی روی قیدهای عمومی مساله کار میکند که مساله اصلی نامیده می شود و دیگری روی قیدهای با ساختار ویژه اعمال می شود که به عنوان مساله فرعی از آن نام برده می شود. اطلاعات آنقدر بین این دو مساله رد و بدل می شود تا به نقطه ای برسیم که جواب بهینه مساله اولیه است.
این روشی روشی برای اولین بار به وسیله بندر پیشنهاد شد. روشی تجزیه بندر در ابتدا برای حل مسائل عدد صحیح مختلط بکار برده میشد اما چندی بعد »جفریون« و »گراوز« ثابت کردند که این روش برای حل سیستمهای چند کالایی با مقیاسهای بزرگ نیز بسیار مناسب است. پس از آن کاربردهای فراوان دیگری از تجزیه بندر مانند » استفاده از تجزیه بندر برای حل مسائل تخصیصی « و یا »استغاده از تجزیه بندر برای حل مسائلی مسیریابی « توسط دانشمندان زیادی همچون »مگنتی« و »ؤنگ« پیشنهاد شد. روش تجزیه بندر بهبود یافته به وسیله دانشمندان متعددی انجام گشت. »کوولیس« و »یو« روش جدیدی برای حل نوعی از مسائل طراحی شبکه قوی به وسیله تجزیه بندر پیشنهاد دادند. » منتمنی« و »گامبادرلا« برای حل کوتاهترین مسیر قوی با مقادیر بازه ای ، از تجزیه بندر استفاده کردند.
-1مقدمه
چکیده
برقراری ارتباط از راه دور، انسان را به بررسی درخت فراگیر کمینه، با مقادیر بازهای سوق داد و از آنجا که حل مساله درخت فراگیر کمینه به درک قیمت واقعی یالهای گراف وابسته است، مساله درخت فراگیر قوی تعریف شده است. مساله درخت فراگیر قوی، به عنوان ردهای از مساله درخت فراگیر کمینه به حساب میآید که در آن یالها به جای داشتن مقادیر ثابت، مقادیر بازه ای به خود می گیرند.
در این مقاله برای یافتن درخت فراگیر قوی روشی »تجزیه بندر« استفاده میکنیم ، در مسائل عملی، بسیاری از مسائل برنامه ریزی خطی از لحاظ ابعادی آنقدر بزرگ میباشند که حتی در رایانه های پیشرفته امروزی آنها را نمی توان حل نمود. در حل این چنین مسائلی، باید از روشهایی استفاده کرد که مسائل بزرگ را به تعدادی مسائلی کوچک قابل حل تبدیل تبدیل کند و سپس از طریق حل این مسائل کوچک به حل مساله بزرگ اولیه رسید.
-2 توصیف مساله
مساله درخت فراگیر قوی با مقادیر بازهای بر روی گراف G = {V, E{ تعریف می شود، که V مجموعه رئوس و E مجموعه یالهای گراف است.
