فاطمه مولایی نژاد - بخش ریاضی کاربردی، دانشکده ریاضی و رایانه، دانشگاه شهید باهنر کرمان، کرمان؛
محمدحسین دریایی - بخش ریاضی کاربردی، دانشکده ریاضی و رایانه، دانشگاه شهید باهنر کرمان، کرمان؛

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

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