学习笔记：Matlab算法篇之规划算法（线性规划、整数规划等）

01线性规划

Matlab求解线性规划命令：[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)这里 fval 返回目标函数的值，LB 和 UB 分别是变量 x 的下界和上界，x0是x的初始值，OPTIONS 是控制参数。

例题（e01）求解以下线性规划问题

matlab求解线性规划问题，要统一将大于等于化为小于等于

c=[2;3;-5];a=[-2 5 -1;1 3 1];b=[-10;12];aeq=[1 1 1];beq=7;x=linprog(-c,a,b,aeq,beq,zeros(3,1));value=c'*x;fprintf('x1=%.4f,x2=%.4f,x3=%.4f\nz:%.4f\n',x,value);

结果：

x1=6.4286,x2=0.5714,x3=0.0000z:14.5714

02 整数规划

求解方法

1.分支定界法—可求解纯整数或混合整数线性规划

2.割平面法—可求解纯整数或者混合整数线性规划

3.隐枚举法—求解“0-1”整数规划

4.蒙特卡洛法—可求解各种类型规划问题

02.1分支定界法

      对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。

例子（e02）求解以下整数规划问题

1. 先不考虑整数限制，即解相应的线性规划，得最优解为：

x1=4.8092,x2=1.8168,z=355.8779

上述解不符合整数条件。这时z是问题的最优目标函数值的上界。而x1=0,x2=0取到下界，因而实际解的
免责声明：本文系网络转载或改编，未找到原创作者，版权归原作者所有。如涉及版权，请联系删