一维背包问题的动态规划求解方法及Excel模型

某货运公司使用一辆最大承载能力为12 t的卡车来装载四种货物，每种货物的质量及价值如表5-1 所示。请问：（1）应当如何装载货物才能使总价值最大？（2）如果货物1 和货物2 至少要装1 件，又如何装载才能保证总价值最大？

表5-1　四种货物的质量及价值

1.问题分析

静态地来看，这是一个整数线性规划问题，但在此我们可以把该问题的解决动态地视为装载各物品（阶段）时先后做出决策（装载量）的过程，即多阶段决策过程。而在每个阶段做决策时，不能仅考虑本阶段的价值（阶段指标），因为本阶段的决策会对以后各阶段的决策产生影响，因此，应考虑从本阶段直到第四阶段末的总价值（总指标）。而每阶段的决策依赖于各阶段初背包的最大承载量（始端），而与以前各阶段如何造成这一最大承载量的情况无关（无后效性）。

因此，这是一个四阶段动态规划问题，根据逆序解法，第一阶段装载第一种物品，第二阶段装载第二种物品，以此类推。

2.建模

为建模需要，定义如下符号：

sk：第k 阶段开始背包的承载量（状态变量）；

uk：第k 阶段装载物品的数量（决策变量）；

ck：第k 阶段每件物品的质量；

qk：第k 阶段每件物品的价值。

根据题意，可得阶段指标函数、状态转移方程和基本方程，即

构建数学模型的具体过程如下：

（1）决策变量：

设卡车装载编号为i的货物数量为xi，i=1，2，3，4。

（2）约束条件：(www.xing528.com)

① 所装载货物总质量≤卡车的承载能力：3x1+4x2+2x3+5x4≤12；

② 非负且为整数：xi≥0且为整数。

对于问题2，还需要增加条件：x1，x2≥1。

（3）目标函数：

使卡车装载货物的总价值最大：maxz=4x1+5x2+3x3+6x4。

（4）数学模型：

根据上面的分析，即得到如下数学模型（整数线性规划）：

问题1：

问题2：

3.应用Excel 求解

对于问题1，利用Excel 求解的结果如图5-6 所示，其结果为当卡车装载3 号货物6 件时，卡车所装载的货物价值最大，为1800 元。

图5-6　一维背包问题1的Excel 电子模型

对于问题2，利用Excel 求解的结果如图5-7 所示，其结果为当卡车装载1 号货物2 件，2 号货物和3 号货物各1 件时，卡车所装载的货物价值最大，为1600 元。

图5-7　一维背包问题2的Excel 电子模型