实例讲解Excel求解简单的线性整数规划和0-1规划

上一节解释了 Excel 如何解决一些简单的线性规划问题。 操作比较简单，适合电脑中未安装的Lingo等编程规划软件。 今天的实际例子讲解了Excel的简单线性整数规划和0-1规划，并使用编程求解器功能来验证结果。

1. 整数线性规划示例

Step1：新建一个excel文件，在任意空白处输入模型的目标函数和约束条件。

Step2：根据文字描述将模型转化为excel规划模型，缺失项系数为0。

Step3：将目标函数值处单元格H25的计算公式输入到目标函数计算公式中。

=H16*H23+I16*H24+J16

第四步：将约束左半部分的计算公式输入到相应的单元格中。

K18单元格输入的公式
=H23*H18+H24*I18
K19单元格输入的公式
=H19*H23+I19*H24
K20单元格输入的公式
=H20*H23+I20*H24
K21单元格输入的公式
=H21*H23+I21*H24

Step5：使用Excel 工具求解，点击右上角的Data -> ，弹出如下对话框。

我们首先选择目标函数计算值所在的单元格为“设定目标”，同时选择x1、x2的变量值为“通过改变变量单元格”的单元格。

其次，我们需要添加我们的约束，点击添加，会弹出如下对话框。

例如，我们将第一个约束条件添加到 中，操作如下：

选择不等式约束左边的计算公式和右边的常数部分，根据约束条件选择关系符号，点击添加，约束条件添加成功。 其余约束条件可依此类推。

设置整型变量的约束，选择变量x1的值的H23单元格，将选择设置为int，然后单击添加将x1设置为整型变量。

选择变量x2 的值的H24 单元格，将选择设置为int，然后单击“添加”将x1 设置为整型变量。

选择相应的计算方法非线性GRE或简单线性规划方法进行求解，选择方法后点击求解按钮。

Step6：获取规划求解结果

Step7：编程求解线性规划，并检查Excel求解结果与求解结果是否一致。

程序

clc;
clear all;
f=[-5 -8];
A=[1 1;5 9];
b=[6 45];
lb=zeros(2,1);
intcon=[1 2];
[x,fval]=intlinprog(f,intcon,A,b,[],[],lb,[]);
x,fval=-fval

运算结果

LP:                Optimal objective value is -41.250000.                                           
Heuristics:        Found 1 solution using ZI round.                                                 
                   Upper bound is -39.000000.                                                       
                   Relative gap is 2.50%.                                                          
Cut Generation:    Applied 1 Gomory cut.                                                            
                   Lower bound is -40.000000.                                                       
                   Relative gap is 0.00%.                                                          
Optimal solution found.
Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value,
options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).
x =
     0
     5
fval =
    40
>>

2.0-1 线性规划示例

在Excel中求解0-1线性规划的步骤与求解整数规划的步骤类似。 唯一的区别是对变量值的约束选择为bin约束。

程序验证结果

程序

clc;
clear all;
f=[-6 -2 -3 -5];
A=[-3 5 -1 -6;2 1 1 -1;1 2 4 5];
b=[-4 3 10]';
intcon=[1 2 3 4];
lb=zeros(4,1);
ub=ones(4,1);
[x,fval]=intlinprog(f,intcon,A,b,[],[],lb,ub);
x,fval=-fval

运算结果

LP:                Optimal objective value is -14.500000.                                           
Heuristics:        Found 1 solution using ZI round.                                                 
                   Upper bound is -13.000000.                                                       
                   Relative gap is 0.00%.                                                          
Optimal solution found.
Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value,
options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).
x =
     1
     0
     1
     1
fval =
    14
>>