آشنایی با برنامه ریزی هندسی

معرفی و شمای کلی

نظریه برنامه‌ریزی هندسی (Geometric Programming) یا به اختصار GP در سال‌های ۱۹۶۱ الی ۱۹۶۷ توسط فیزیکدان نظری آقای زنر (Clarence Zener) مطرح گردید. هدف از این کار ارائه راهکار مطمئن برای حل مسایل غیرخطی با ساختارهای مشخص بود. متعاقبا در سال‌های بعدی آقای دافین (Richard Duffin) نظریه دوگان را برای حل مسایل غیرخطی در قالب برنامه‌ریزی هندسی ارائه کرد. از طرفی مشخصه‌های ساختاری مسایل برنامه‌ریزی هندسی، محققان و متخصصین حوزه بهینه‌سازی را به سمت طراحی الگوریتم‌های کارا مانند روش نقطه داخلی برای حل این دسته مسایل سوق داده است. به طور کلی مسایل GP دسته‌ی متمایزی از مسایل بهینه‌سازی در مجموعه‌ی برنامه‌ریزی محدب (Convex Programming) هستند.

بیشتر بخوانید

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

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

بیشتر بخوانید