数学建模 - 线性和整数编程 - Matlab 解决优化问题

matlab内置有优化工具箱，可以解决绝大多数优化问题

Optimization Toolbox™ 提供了寻找最小化或最大化目标并同时满足约束条件的函数。工具箱中包括了线性规划 (LP)、混合整数线性规划 (MILP)、二次规划 (QP)、非线性规划 (NLP)、约束线性最小二乘法、非线性最小二乘和非线性方程的求解器。
详见Optimization Toolbox官方网站
或https://blog.****.net/cclethe/article/details/77200997

matlab常用解决优化问题的函数有：

转自头条号/算法集市

对于整数规划问题，matlab内置了intlinprog函数

函数命令为：
[x, fval]=intlinprog(f, intcon, A, b, Aeq, beq, lb, ub)
其中变量intcon是有整数要求的决策变量的下标组成的列向量，其余变量与线性规划相同。

数学模型为：
$$\begin{gathered} \underset{x}{\min }{\text{f}}^T\text{x}, \\ s.t.\{\begin{array}{l}\text{x}(intcon)为整数\\ \text{A}\cdot \text{x}⩽\text{b}\\ Aeq\cdot \text{x}=beq\\ lb⩽\text{x}⩽ub\end{array} \end{gathered}$$
intlinprog函数中的决策变量只能是一维，因此只有将二维决策变量转化为一维才能继续使用该函数
例：
以下指派问题中指派矩阵为：
$$\left[\begin{array}{ccccc}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{array}\right]$$
将二维决策变量x_ij（i，j=1，2，3，4，5）变为一维决策变量y_k（k=1，2，3，…，25）

matlab代码：

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];
c=c(:); a=zeros(10,25); intcon =1:25;
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);
lb = zeros(25,1);
ub = ones(25,1);
x = intlinprog(c,intcon,[],[],a,b,lb,ub);
x = reshape(x,[5,5])

输出：

>> 
LP:                Optimal objective value is 21.000000.                                            


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     0     0     0     1
     0     0     1     0     0
     0     1     0     0     0
     0     0     0     1     0
     1     0     0     0     0

>> 

若问题中决策变量为一维，则与线性规划无太大差别。

参考文献：
[1]司守奎，孙兆亮．数学建模算法与应用[M]．第二版．北京：国防工业出版社，2018.
[2]部分资料来源于互联网