线性规划与整数规划

Author：怪使
发布时间：August 14, 2019
1598views
No comments
4208 words
Categories：数学建模

线性规划与整数规划

1. 线性规划

适用于：约束条件和决策变量比较多，且为线性关系时的规划问题。

线性规划问题是在一组线性约束条件的限制下，求一线性目标函数的最大或者最小值问题。

1.1 matlab实例

在matlab中，规定其目标函数为求最小值，标准求线性规划的形式模型为：

$$ min{c^Tx}\\ s.t\begin{cases} Ax \le b \\ Aeq.x=beq\\ lb \le x \le ub \end{cases} $$

其中有三种约束条件，一个是不等号约束，一个是等式约束，一个则是自变量范围约束。

并且其中$c$与$x$为$n$维列向量，$A$、$Aeq$为适当维数的矩阵，$b$、$beq$为适当维数的列向量。

所以要将实际上的模型转换为标准形式模型再进入matlab计算。

切记：要求维数保证没有问题，而且不等号方向确定为$\le$

线性规划的相关知识有可行域与最优解。

对于高维度来说，要求其可行域必须为一个凸集，不然就没有解。

1.2 这里利用matlab举例来计算一个线性规划问题：

首先用到matlab函数是：

[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)

fval表示返回目标函数的值，也就是最优解。

LB和UB分别是变量x的下界和上界，也就是决策变量不等式约束条件第三条，X0是X的初始值，而OPTIONS是控制参数

举个例子：求解下列线性规划问题

$$ max z=2x_1+3x_2-5x_3\\ s.t\begin{cases} x_1+x_2+x_3=7\\ 2x_1-5x_2+x_3 \ge 10\\ x_1+3x_2+x_3 \le 12\\ x_1,x_2,x_3 \ge 0\\ \end{cases} $$

代码如下：首先编写m文件，保存运行即可

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

首先可以看到这里用了$-c$，而且只限定了上界。这是题目要求的。

2 整数规划

适用于：题目要求规划中的变量限制为整数，目前仅仅针对整数线性规划有通用的解法，而对非线性的整数规划则是各有各的解法。

分成两类：

变量全部限制为整数，称为纯（完全）整数规划
变量部分限制为整数，称为混合整数规划

特点：

原线性规划最优解就是纯整数，所以就相同一致
整数规划没有可行解

所以求解方式一般分为下列几种：

分支限界法——可以求纯或者混合整数线性规划
割平面发——可以求纯或者混合整数线性规划
隐枚举法——求解“0-1”整数规划问题
1. 过滤隐枚举法
2. 分支隐枚举法
匈牙利法——解决指派问题（特殊的“0-1”规划）
蒙特卡洛法——概率算法，可以求解各种类型的规划

2.1 分支限界法

内容：对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索。

分支：将全部可行解空间反复分割为越来越小的子集

限界：对每个子集内的解集计算一个目标下界（对于最小值问题）

然后每次分支之后，凡是界限超出已知可行域目标值的那些子集不再进行分支，这样可以避免考虑许多的子集。

应用：生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等等。

对于线性整数规划问题，套用分支限界法就是，对于整数线性规划问题，先去计算它的线性规划问题，这个时候我们得到对于整数线性规划问题的上界。接下来我们只需要把对应的线性规划问题的可行域进行分割为子区域，然后通过分支限界法，就可以不断接近我们要取的整数线性规划问题的解。

举个例子：求解下例的整数规划

$$ Max z=40x_1+90x_2\\ \begin{cases} 9x_1+7x_2 \le 56\\ 7x_1+20x_2 \le 70\\ x_1,x_2 \ge 0&且为整数\\ \end{cases} $$

先不考虑整数限制，直接解相应的线性规划$B$，得到最优解为：
```
c=[40;90];
a=[9,7;7,20];
b=[56,70];
[x,y]=linprog(-c,a,b,[],[],zeros(2,1))
```

容易计算出来：

$$ x_1=4.8092,x_2=1.8168,z=355.8779(这里是转化为求最小值，所以记得加上负号) $$

可以知道显然不符合整数条件，所以这个时候$z$是问题$A$的最优目标函数$z^*$的上界，记为$\overline{z}$。而$x_1=0,x_2=0$显然是问题$A$的一个整数可行解，这时可以取$z=0$,是$z^*$的一个下界，记作$\dot{z}$,也就是有$0 \le z^* \le 356$

因为$x_1,x_2$均为非整数，不满足整数要求，任选一个进行分支，设选$x_1$进行分支，可以将可行集分为2个子集：

$$ x_1 \le [4.8092]=4, x_1 \ge [4.8092]+1=5 $$

因为4与5之间没整数，所以这两个子集的整数解必与原可行集合整数解一致，这一步称为分支。这两个子集的规划及其求解如下：

问题$B_1$:

$$ Max z=40x_1+90x_2\\ \begin{cases} 9x_1+7x_2 \le 56\\ 7x_1+20x_2 \le 70\\ 0 \le x_1 \le 4,x_2 \ge 0\ \end{cases} $$

c=[40;90];
a=[9,7;7,20];
b=[56,70];
[x,y]=linprog(-c,a,b,[],[],zeros(2,1),[4,[]])

最优解为：$x_1=4.0,x_2=2.1,z_1=349$

问题$B_2$:

$$ Max z=40x_1+90x_2\\ \begin{cases} 9x_1+7x_2 \le 56\\ 7x_1+20x_2 \le 70\\ x_1 \ge 5,x_2 \ge 0\ \end{cases} $$

c=[40;90];
a=[9,7;7,20];
b=[56,70];
[x,y]=linprog(-c,a,b,[],[],[5,0])

最优解为：$x_1=5.0,x_2=1.5714,z=341.4286$

再定界：$341.4 \le z^* \le 349$

对问题$B_1$再继续分支可以得到问题$B_{11}$和$B_{12}$，它们的最优解为：

$$ B_{11}:x_1=4,x_2=2,z_{11}=340\\ B_{12}:x_1=1.43,x_2=3.00,z_{12}=327.14 $$

再次定界：$340 \le z^* \le 341$，并将$B_{12}$剪枝

对问题$B_2$再进行分支可以得到问题$B_{21}$和$B_{22}$，它们的最优解为：

$$ B_{21}:x_1=5.44,x_2=1.00,z_{21}=308\\ B_{22}无可行解 $$

将$B_{21},B_{22}$剪枝

于是可以断定原问题的最优解为：

$$ x_1=4,x_2=2,z^*=340 $$

这里就不讲具体的思路了，对分支提一下：在最优解中任选一个不符合整数条件的变量$x_j$，其值为$b_j$，以$[b_j]$表示小于$b_j$的最大整数。构造两个约束条件：

$$ x_j \le [b_j] 和 x_j \ge [b_j]+1 $$

将这两个约束条件，分别加入问题再求出后继的规划问题，不考虑整数条件求解这两个后继规划问题。

2.2 0-1整数规划

显然指的是变量仅能取值为0或者1，这个时候变量被称为二进制变量。

2.2.1 过滤隐枚举法解0-1整数规划问题

穷举法，检查变量取值为0或1的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的$2^n$个组合，对于变量个数较大的问题基本上做不到，所以设计了这种方法，仅检查变量取值的组合的一部分，求得问题的最优解。常见的分支定界法也是一种隐枚举法。

举个例子

$$ Max z=3x_1-2x_2+5x_3\\ \begin{cases} x_1+2x_2-x_3 \le 2\\ x_1+4x_2+x_3 \le 4\\ x_1+x_2 \le 3\\ 4x_2+x_4 \le 6\\ x_1,x_2,x_3=0或1\\ \end{cases} $$

求解思路：

先试探求一个可行解，容易看出$(x_1,x_2,x_3)=(1,0,0)$满足约束条件，故为一个可行解，且$z=3$
因为是求极大值问题，所以求最优解的时候，其目标值$z<3$的解不必检验是否满足约束条件即可删除，因为必定不是最优解，于是应该增加一个约束条件（目标值下界）
改近过滤条件
由于对每个组合首先计算目标值以验证过滤条件，故应该优先计算目标值$z$大的组合，从而提高过滤门槛，以减少计算量。

2.3 蒙特卡洛法（随机取样方法）

前面介绍的整数规划求解方法，主要是针对线性整数规划。而对于非线性整数规划本身没有什么好的做法，但是由于整数解是有限的，所以穷举法其实是可以完成的，但是在自变量维数很大和取值很广的情况下，穷举法计算比较浪费时间。但是概率理论可以证明，在一定的计算量下，完全可以得到一个满意解。

例子：已经知道非线性整数规划为：

$$ Max z=x_1^2+x_2^2+3x_3^2+4x_4^2+2x_5^2-8x_1-2x_2-3x_3-x_4-2x_5\\ \begin{cases} 0 \le x_i \le 99&{(i=1,...,5)}\\ x_1+x_2+x_3+x_4+x_5 \le 400 \\ 2x_1+x_2+6x_3 \le 200\\ x_3+x_4+5x_5 \le 200\\ \end{cases} $$

如果用穷举法，则需要计算$(100)^5=10^10$个点，显然计算量极大；而用蒙特卡洛法随机计算$10^6$个点，即可找到满意解。

可信度估计：

不失一般性，假定一个整数规划的最优点不是孤立的奇点、

假设目标函数落在高值区的概率分别为0.01,0.00001,则当计算$10^6$个点后，有任一个点能落在高值区的概率分别为：

$$ 1-0.99^{1000000}\approx0.99...99(100多位)\\ 1-0.99999^{1000000}\approx0.999954602 $$

也就是满足了我们能找到满意解的可能性。

程序编码：

function [f,g]=mengte(x);
f=x(1)^2+x(2)^2+3*x(3)^2+4*x(4)^2+2*x(5)-8*x(1)-2*x(2)-3*x(3)-...
x(4)-2*x(5);   %整个最大值函数
g=[sum(x)-400     
x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800
2*x(1)+x(2)+6*x(3)-200
x(3)+x(4)+5*x(5)-200];  %限制条件

rand('state',sum(clock));  %随机时钟
p0=0;   %初始赋值
tic        %计时开始
for i=1:10^6     %遍历贼多次
 x=99*rand(5,1);   %随机数
x1=floor(x);x2=ceil(x);   %向负数取整，向正数取整
[f,g]=mengte(x1);   %调用前面的函数，计算值
if sum(g<=0)==4     %满足4个约束条件
 if p0<=f           %分支限界法
 x0=x1;p0=f;
 end
end
[f,g]=mengte(x2);   %同理
if sum(g<=0)==4
 if p0<=f
 x0=x2;p0=f;
 end
end
end
x0,p0   %返回整数规划的值与最大值
toc     %计时结束

最后得到的解为：

$$ x_0=(44,92,1,99,3),p_0=48969 $$

2.4 指派问题的计算机求解

对于一般的整数规划问题，matlab并没有写好的内置函数可以运用，必须自己编程实现分支限界法和割平面解法，但是对于指派问题等0-1整数规划问题，可以直接使用Matlab的内置函数bintprog进行求解。

指派问题的系数矩阵指的是：分配该人去做第几项工作，花费的时间，一般就是稳怎么指派，能够完成工作并且花费时间最少。

标准模型为：

$$ min \sum^n_{i=1}\sum^n_{j=1}c_{ij}x_{ij}\\ s.t.\sum^n_{j=1}x_{ij}=1 $$

例子：求解下列指派问题，已经知道指派矩阵为：

$$ \begin{bmatrix} {3}&{8}&{2}&{10}&{3}\\ {8}&{7}&{2}&{9}&{7}\\ {6}&{4}&{2}&{7}&{5}\\ {8}&{4}&{2}&{3}&{5}\\ {9}&{10}&{6}&{9}&{10}\\ \end{bmatrix} $$

c=[3 8 2 10 3;8 7 2 9 7;6 4 2 7 5;8 4 2 3 5;9 10 6 9 10];  %指派系数矩阵,这里是25行1列的向量形式
c=c(:);
a=zeros(10,25);   %生成10行25列的0矩阵
for i=1:5
    a(i,(i-1)*5+1:5*i)=1;   %做到所有的等式约束条件
    a(5+i,i:5:25)=1;
end
b=ones(10,1);    %生成10行1列的全为1的矩阵
[x,y]=bintprog(c,[],[],a,b);  %黑箱操作指派运行
x=reshape(x,[5,5]),y   %转换为矩阵形式

最优的指派方案为：

$$ x_{15}=x_{23}=x_{32}=x_{44}=x_{51}=1,最优值为21 $$

Last modification：August 15th, 2019 at 12:33 am

如果觉得我的文章对你有用，请随意赞赏

线性规划与整数规划

怪使 • 2019 年 08 月 14 日