الگوریتم شاخه و کران برای حل مساله برنامه ریزی خطی کسری تعمیم یافته

در این مقاله، الگوریتم شاخه و کران را برای حل مسائل برنامه ریزی خطی کسری تعمیم یافته ارائه می کنیم. در واقع با استفاده از یک روش انتقال، ابتدا مساله برنامه ریزی خطی کسری تعمیم یافته را به یک مسالهبرنامه ریزی نامحدب معادل تبدیل کرده و سپس الگوریتم شاخه و کران را برای حل این مساله معادل استفاده می کنیم. الگوریتم شاخه و کران دارای دو مرحله شاخه سازی و پیداکردن کران بالا و پایین برای مقدار بهین مساله معادل است. در مرحله شاخه سازی معمولا از قاعده دو بخشی استفاده می کنیم و در مرحله پیداکردن کران، بایستی یک مساله برنامه ریزی خطی را حل کنیم. همگرایی این الگوریتم هم در این مقاله مورد بررسی قرار گرفته است.

کلیدواژه ها:

برنامه ریزی کسری ، آزادسازی خطی ، مجموع نسبت ، شاخه و کران ، تکنیک کاهش