多背包問題的精確算法

多背包問題的精確算法

一、混合遺傳算法包絡問題（kp）是一個經典的組合優(yōu)化問題，它具有廣泛的實際應用背景，如預算控制、項目選擇、材料切割、貨物裝載等。多背包問題是背包問題的一種變化形式,主要應用在分布式計算機系統(tǒng)中的處理和數據庫的分配、項目選擇和貨物裝配以及庫存壓縮等問題中。本文主要研究多背包問題的一種求解方法。宋海生,傅仁毅等針對多背包問題最優(yōu)解的求解,提出了一種求解多背包問題的混合遺傳算法。該算法對背包資源利用不足的可行解進行修正處理,對不可行解進行修復處理。馬炫,劉慶提出一種基于人工魚覓食,追尾、聚群等行為的求解多背包問題的優(yōu)化算法。針對多約束導致大量非可行解的產生而使算法性能劣化的問題,采用基于啟發(fā)式規(guī)則的調整算子,使人工魚群始終在可行解域中尋優(yōu)。董朝陽,蔡安江,阮曉光將網絡化制造中的最優(yōu)制造伙伴選擇問題歸結為一種復雜的多目標、多選擇、多約束背包問題,并提出了一種并行多目標妥協(xié)遺傳算法進行求解。TakeoYamada,TakahiroTakeoka采用貪婪啟發(fā)式算法得到一組上界和下界以縮小問題空間,據此提出了一種解決復雜背包問題的確定性算法。DavidPisinger提出了一種求解復雜多背包問題精確解的方法,通過將多背包問題分解成多個子背包問題來求解,并計算上下限來縮小問題求解空間,結果表明,它有非常迅速的求解速度。二、模型改進(一)高至低至總重量背包量的確定文中提出啟發(fā)式規(guī)則,將相對優(yōu)的物品提前接受,將相對劣的物品直接排除,改進了多背包問題的求解速度。啟發(fā)式規(guī)則部分根據所確定的相對優(yōu)和相對劣的比例,對物品的信息進行統(tǒng)計得出高分數線和低分數線,高分數線和低分數線確定之后,開始對物品進行篩選,高于高分數線的物品確定接收,由模型確定放入哪個背包中,那些分數低于低分數線的物品會被拒絕。位于中間分數的物品由模型確定是否裝入,以及裝入哪個背包中。這個高分數線和低分數線的確定過程如下:首先,確定相對優(yōu)和相對劣的比例;其次,根據物品本來的分數排序,利用回歸分析,求出各個訂單的名次分,分數范圍為0到100。如果所有的物品總重量小于總背包容量,高分數線就為100,低分數線為0,意味著都接收。否則,按分數從高往低取,取到總背包量乘以相對優(yōu)的比例的量,將該訂單的分數作為高分數線;最后,按分數從低往高取,取到總背包量乘以相對優(yōu)的比例的數量,將該訂單的分數作為低分數線。通過確定高分數線和低分數線,可以縮小背包問題求解空間,提高背包問題求解速度?？梢园l(fā)現這個規(guī)則可以根據提前接收比例和多余物品量比例這兩個指標可以確定分數線,并對物品進行篩選,提高背包模型計算的效率。(二)多背書問題的求解多背包問題是指在一個物品集合N={1,2,…,n}中選出一個子集分別裝入m個背包中,在不超出每個包的限制容量bj的條件下,使選出的全部物品的總價值最大,其中j∈M,M={1,2,...,m}其模型描述為:ci表示物品i的價值,aij表示物品i放入背包j所占的容量。式(2)表示背包約束,bj為第j個背包的容量。早期求解多背包問題的方法主要集中于精確求解算法,如分支定價、動態(tài)規(guī)劃,由于精確求解算法計算量大,難以求解大規(guī)模多背包問題,近年出現了遺傳算法、分散搜索算法等,提高了算法的性能和求解速度。物品經過篩選后,將相對優(yōu)的物品和一般物品的信息,代入背包問題的模型,進行運算,以確定相對優(yōu)的物品裝入哪個背包、一般物品是否接收及放入哪個背包中。下面是經過改進的背包問題模型:輸入變量:ai:第i個背包的重量bj:第j個背包的容量H:背包個數N:物品個數s:開始裝入的背包編號e:最后裝入的背包編號決策變量:vgi:是否裝入第i個物品sgi:裝入第i個物品的背包編號x_i_j:第i個物品是否裝入第j個背包目標函數:該線性模型與前面所講的多背包問題基本類似,但是在約束(2)中,i∈N要改成i∈{s,e},即物品i只能放在從s到e之間的背包中,并增加約束(4)提前指定一些必須放入背包中的物品,由模型確定放入哪個背包。三、模型求解結果該啟發(fā)式規(guī)則和背包問題模型的解法可以應用于企業(yè)的訂單接收策略中,某一生產企業(yè)A,生產周期為h天,每天產能為c,現在有一批訂單到達,其相關的信息為:到達時間、交貨期、訂單分數,訂貨量、訂單處理時間。根據這些信息,企業(yè)A要確定接收哪些訂單,拒絕哪些訂單,以及確定接收的訂單的開始生產時間。其中有一些訂單由于評分較高,已經確定提前接收,這個模型只確定它們的開始生產時間。假設這個企業(yè)每天的產能是400單位,生產周期為10天,表1為這個企業(yè)收到的訂單信息,如表1所示。首先,根據這些訂單信息,采用回歸分析方法,計算得出標準分數,即名次分數,通過計算以確定高分數線和低分數線。由于每個訂單的情況不一樣,模型無法直接出來進行求解,這里面我們利用C++根據訂單的信息,將其它數據生成Lingo程序,并調用lingo運算,求解。最后,通過模型求解到的利潤為93093,訂單接收情況見表2。從以上實例可以看出,使用相對優(yōu)和相對劣的標準可以預先縮小解的求解范圍,提高計算的效率。四、算法的基本思想通過上面的實例及其分析,可以得出以下結論:第一,本文提出的一種多背包問題的求解方法,使用線性規(guī)劃建立確定性算法模型,并通過c++和lingo編程技術,根據數據生成模型,以縮小求解空間提高算