نحوه شناسایی تک کالبدی بودن ضرایب فنی

به ماتریس مربعی که دارای عناصر عدد صحیح ۰ یا ۱- یا ۱+ و دترمینان ۱- یا ۱ باشه، ماتریس تک کالبدی (unimodular matrix) گفته می‌شود. از طرفی، ماتریس کاملا تک کالبدی (totally unimodular) ماتریسی است که تمامی زیرماتریس‌های مربعی آن معکوس‌پذیر و تک کالبدی باشند. به عبارتی در صورتی که یک ماتریس ۸×۸ داشته باشیم، بایستی ۲۰۴ زیرماتریس آن را به لحاظ تک کالبدی بودن بررسی نماییم.
مزیت عمده این خاصیت این است که در برنامه ریزی تمام عدد صحیح، در صورتی که ماتریس ضرایب فنی دارای خاصیت کاملا تک‌کالبدی باشند، در اینصورت جواب‌های رهاشده خطی مساله عدد صحیح، همان جواب‌های مساله اصلی خواهند بود (تمامی متغیرها مقادیر صحیح می گیرند). به بیان دگر، پوسته محدب تمامی نقاط گوشه‌ای آن صحیح خواهند بود. برای بررسی کاملا تک‌کالبدی بودن یک برنامه‌ریزی عدد صحیح کافی است ماتریس ضرایب فنی آن را استخراج و تحلیل کرد.

جهت استخراج ماتریس ضvایب فنی کافی است تمامی محدودیت‌های به فرم مساوی را به نامساوی و متغیرهای صفر و یک را به حالت پیوسته تبدیل کرده و بلوک کد زیر را در انتهای کد فایل mod درج نمایید:

 main {
 thisOplModel.generate();
 cplex.exportModel("problem.mps");
 }

پس از اجرای مدل، بدین ترتیب اطلاعات کل مساله در فایل problem.mps جاسازی می‌شود. توجه شود که مدل در این حالت حل نمی‌شود بلکه صرفا یک فایل خروجی mps در کنار سایر فایل های مدل ایجاد می شود. سپس به کمک نرم افزار MATLAB و دستور mpsread فایل mps را فراخوانی می‌کند. حال ماتریس A خروجی همان ماتریس ضرایب فنی می‌باشد. در نهایت، به کمک کد m-file(کلیک کنید) تماما تک کالبدی بودن ماتریس A بررسی می‌شود.

بنابراین به راحتی می توان متغیرهای صفر و یک را به متغیرهای پیوسته تغییر داده و شاهد افزایش شتاب محاسباتی و بالتبع کاهش زمان حل باشیم.

0 Comments
Inline Feedbacks
View all comments