K. Eshghi and H. Djavanshir. An Efficient Algorithm for Reducing the Duality Gap in a Special Class of the Knapsack Problem. Journal of Advanced Materials in Engineering (Esteghlal) 2005; 24 (1) :47-57
URL:
http://jame.iut.ac.ir/article-1-332-fa.html
چکیده: (4921 مشاهده)
یکی از انواع مسئله
کوله پشتی مسئله کوله پشتی جدایی پذیر غیر خطی نام دارد. این مسئله به دلیل کاربردهای فراوان مورد توجه محققان قرار گرفته است. یکی از روشهای اصلی حل این مسئله برنامه ریزی پویا است اما به دلیل آنکه فضای متغیر حالت به سرعت رشد میکند مشکل ابعادی را بوجود میآورد. در این مقاله روشی کارا ارائه میشود تا ضرایب جانشین را در هر مرحله از برنامهریزی پویا بیابد و با این کار مسئله اصلی را به مسئلهایی با یک محدودیت موسوم به مسئله جانشین تبدیل کند. بر طبق نتایج محاسباتی حاصله حدود بالایی و پایینی ناشی از حل مسئله جانشین میتواند متغیرهای حالت بسیاری را در برنامه ریزی پویا حذف کرده و فاصله ثانویه را به نحو چشمگیری کاهش دهد.
نوع مطالعه:
پژوهشي |
موضوع مقاله:
عمومى دریافت: 1393/8/3 | انتشار: 1384/4/24