多約束二次0-1背包問題的一個有效算法.pdf

1、當前我國正處在經濟快速發(fā)展時期，與此同時，資源消耗也呈高速增長的趨勢.如何最合理地利用有限的資源，使生產的消耗最小，利潤最大是經營管理者所關心的主要問題.而現(xiàn)實中的有些資源是只能取整數(shù)的，特別是很多決策變量只能取0或1.所以對0-1整數(shù)規(guī)劃的研究在理論上和實踐上都有著重大意義.本文主要討論多約束二次0-1背包問題.其數(shù)學模型可描述如下： (MQKP)maxf(x)=n∑i=1qiixi+∑1≤i＜j≤nqijxixjs.t.Ax

2、≤b,x∈{0,1}n,其中qij≥0,1≤i≤j≤n,A=(aij)m×n,aij≥0,i=1,...,m,j=1,...,n,b=(b1,...,bm)T,0＜bi＜∑j=1naij,i=1,...,m.我們根據(jù)這類問題的特殊性質，提出一個新的分枝定界算法，該算法使用分枝定界策略和拉格朗日對偶來尋找問題的最優(yōu)解.在算法中，我們把拉格朗日松弛問題轉化為最大流網絡最優(yōu)化問題，并使用外逼近方法求解子問題的對偶界.我們還使用替代約束技術搜索