文章目录
一、谈谈我的理解
前两次打卡，我们学会了线性规划，这里为什么又引入一个整数规划呢？其实两个规划很类似，唯一的区别就是整数规划限制了我们的变量x必须为整数，而线性规划没有限制变量类型。
为什么我们要引入整数规划呢？在实际生活中，我们就算付钱，可能也很少遇到让你付小数的钱，都是让你给一个整数，因此这就是整数规划的由来。
二、题目
1）题目与简析
假设我们有如下的整数规划：
假设我们先把最后一个条件限制为整数暂时忽略？你是不是能用前面的知识求解出max,x1,x2呢？请把你的matlab求解过程写到博客，提交到任务中。(晚上我提交答案）
我在这里先直接给出答案：
x1 = 4.8092, x2 = 1.8168,z = 355.8779
根据我计算出的结果可以看到x1和x2都不满足整数情况，因此这就不再是最优解了。
2）分枝定界法步骤
方法用处：分枝定界法可用于解纯整数或混合的整数规划问题
2.1）第一步
根据我们出的结果，我们可以暂定z的上限（最大值）可以是356；我们也可以一样看出x1,x2分别为0时，z最小值为0；因此最大值z的范围可以暂定为：0=<z=<356
2.2）第二步
因为 x1, x2 当前均为非整数，故不满足整数要求，任选一个进行分枝。设选 x1进行分枝，把可行集分成 2 个子集：
x1 =<[4.8092] = 4 ， x1 >= [4.8092] +1 = 5
4与5之间没有整数，因此这种方法就是叫做分枝。
这两个子集的规划及求解如下：
问题 B1 ：
目标函数：
Max z = 40x1 + 90x2
约束条件：
9*x1+7*x2<=56 7*x1+20*x2<=70 0<x1<4 x2>0
因为我们只对x1做了分枝，因此x2的约束不变。
这里计算方法跟线性规划不一样，但是有一点我没有讲到的是前面我们没有遇到x在两者之间的问题，因此我对此B1做matlab计算最优解如下：
clc clear all c=[40 90];%用目标函数系数来确定 a=[9 7 ;7 20];%约束条件左边约束 b=[56 70];%约束条件右边系数 aeq=[];%没有等式约束，因此aeq,beq都为空 beq=[]; lb=[0;0];%下限依然都为0 ub=[4;inf];%x1上限为4，x2没有上限 [x,y]=linprog(-c,a,b,aeq,beq,lb,ub); %这里没有等式约束，对应的矩阵为空矩阵 x %获取对应x1,x2 best=c*x%计算最优值
运行结果：
因此我们得出：x1 = 4.0, x2 = 2.1,z1 = 349。
我们对下x1做了分支，因此我们还要计算x1的另一半（我们就是相当于把x1范围划分两半，分别计算，后面我们再求其和）。因此对于x1有问题 B2 ：
目标函数：
Max z = 40x1 + 90x2
条件约束：
9*x1+7*x2<=56 7*x1+20*x2<=70 x1>=5 x2>0
上面我已经写过解法了，请对照上面的解法写出你的matlab求解，并写在博客里（本篇文章所有留下的问题写在一篇博客提交任务）
我直接给出答案：
可以看到x1=5 x2=1.5714 z=341.4286
现在我们把最优值再定界确定范围为：0 ≤ z ≤ 349。
2.3）第三步
对第二步的问题B1继续分支，我们可以看到问题B1只有x2有小数，因此我们是对B1问题里的x2进行分枝（按照第一步的方法）:
0=<x2<[2.1]=2,x2>[2.1]+1=3
从而得到问题如下：
B11问题目标函数：
Max z = 40x1 + 90x2
约束条件：
9*x1+7*x2<=56 7*x1+20*x2<=70 0<=x1<=4 2>x2>0
matlab计算代码如下：
clc clear all c=[40 90];%用目标函数系数来确定 a=[9 7 ;7 20];%约束条件左边约束 b=[56 70];%约束条件右边系数 aeq=[];%没有等式约束，因此aeq,beq都为空 beq=[]; lb=[0;0];%下限依然都为0 ub=[4;2];%x1上限为4，x2没有上限 [x,y]=linprog(-c,a,b,aeq,beq,lb,ub); %这里没有等式约束，对应的矩阵为空矩阵 x %获取对应x1,x2 best=c*x%计算最优值
运行：
然后我们再计算x2另一个分枝，唯一变化的还是x范围.
问题B12:
目标函数：
Max z = 40x1 + 90x2
条件约束:
9*x1+7*x2<=56 7*x1+20*x2<=70 0<=x1<=4 x2>3
matlab计算结果为：（请你在博客写上此题的matlab计算过程）
因此我们可以再次确定z范围为：340 ≤ z ≤ 341
到这里我们已经对问题B1做出完美分枝，因此我们再对问题B2进行分枝，请看第四步。
2.4）第四步
为了便于观看，我把问题B2拖下来：
根据上面的结果，x2=1.5714为小数，因此我们对B2中的x2进行分枝。
0=<x2<[1.5714]=1,x2>[1.5714]+1=2
得到问题B21如下：
目标函数：
Max z = 40x1 + 90x2
条件约束：
9*x1+7*x2<=56 7*x1+20*x2<=70 x1>=5 1>x2>0
用matlab计算结果如下：（请你在博客写出你的matlab代码）
B22问题如下：
目标函数：
Max z = 40x1 + 90x2
条件约束：
9*x1+7*x2<=56 7*x1+20*x2<=70 x1>=5 x2>2
matlab如下：
clc clear all c=[40 90];%用目标函数系数来确定 a=[9 7 ;7 20];%约束条件左边约束 b=[56 70];%约束条件右边系数 aeq=[];%没有等式约束，因此aeq,beq都为空 beq=[]; lb=[5;2];%下限 ub=[inf;inf];%上限 [x,y]=linprog(-c,a,b,aeq,beq,lb,ub) %这里没有等式约束，对应的矩阵为空矩阵
运行如下：
根据结果我指出的地方可以看到，没有解。
综合B2的两个分枝，B21分枝后依然有小数，不可取；B22不可行解，因此也不可取。这样的操作呢，叫做剪枝。
2.5）结论
由于B2的两个分枝都不可取，B1只有一个枝可取，即最优解为：
x1 = 4, x2 = 2,z = 340
三、总结
开始，将要求解的整数规划问题称为问题 A ，将与它相应的线性规划问题称为问题 B。求解情况如下：
- B 没有可行解，这时 A 也没有可行解，则停止
- ） B 有最优解，并符合问题 A 的整数条件， B 的最优解即为 A 的最优解，则停止。
- B 有最优解，但不符合问题 A 的整数条件，记它的目标函数值为 z，通过我上述所说的四个步骤使用花枝定界法进行分枝，剪枝，最后得出结果。
再次提醒： 请务必完成我在本篇文章中留下的问题，写一篇博客提交任务，学习是靠你自己，你不努力，总有人比你更努力。
