背包问题的解法与优化

【例8-5】是典型的背包问题,建模和求解过程如下:

解:

根据题意,设三种物品各携带x1,x2,x3件,则该背包问题的数学模型为:

(1)动态规划问题模型。

①阶段变量:按物品种类进行划分,n种物品,n个阶段。由于已知初始状态,所以k＝n,n－1,…,2,1。

②状态变量:y/Sk表示背包人在选择第k种物品之前所能承担的最大负荷。

③决策变量:xk表示携带第k种物品数量,一般具有整数限制。由于ak表示第k种物品的重量,所以有0≤ak xk≤Sk。

④状态转移方程:Sk－1＝Sk－ak xk。

⑤阶段指标:由于ck表示携带单位第k种物品的使用价值,因此背包人携带xk个第k种物品的使用价值为ckxk。

⑥最优函数:fk(Sk)表示携带第k种到第1种物品的使用价值最大。

⑦动态规划基本方程为:

其中,[S1/a1]表示不超过S1/a1的最大整数。

(2)求解。(www.xing528.com)

当k＝3时,由于a3＝5,5/a3＝5/5＝1,因此x3的取值为0和1(决策允许集),最优函数为:

当k＝2时,由于a2＝2,5/a2＝5/2＝2．5,因此x2的取值可以是0,1和2(决策允许集),最优函数为:

当k＝1时,由于a1＝3,5/a1＝5/3≈1．67,因此x1的取值可以是0和1(决策允许集),最优函数为:

则:

因此,

由f3(5)＝0＋f2(5)＝0＋5＋f1(3)＝0＋5＋8×1＝13,可知x1＝1,x2＝1,x3＝0。因此该问题的最优解为X∗＝(1,1,0)T,Z∗＝13。

【例8-6】装载问题的建模和求解过程如下:

解:

由题意可得各种货物利润函数为:

设S2＝x2,S2＋x1＝S1＝10,0≤x2≤S2,0≤x1≤S1＝10,用逆序解法求解:

当k＝2时,

最优解为X∗＝(6,4)T,Z∗＝48。