@
前言
线性规划是数学规划中的一个重要分支，常用于解决如何利用现有资源来安排生产，以取得最大经济效益的问题。本文将粗略地介绍线性规划，matlab实现和常见变形。
一、基本概念
一般线性规划问题地（数学）标准型为
\[max\quad z=\sum\limits_{j=1}^nc_jx_j, \\s.t \quad
y=
\begin{cases}
\sum\limits_{j=1}^na_{ij}x_j=b_i,i=1,2,...,m\x_j\geq0,j=1,2,...,n
\end{cases}
\tag{1}
\]
可行解：满足约束条件的解\(x=[x_1,...,x_n]^T\)
最优解：使目标函数达到最大值的可行解
二、matlab实现
1.常用函数
matlab中规定线性规划的标准形式为：
\[\underset {x}{min}\ \pmb f^T\pmb x,\\s.t\quad
\begin{cases}
\pmb{A\cdot x}\leq \pmb b,\Aeq \cdot \pmb x=beq\lb\leq x\leq ub
\end{cases}
\]
其中\(\pmb{f,x,b},beq,lb,ub\)为列向量， \(\pmb f\)称为价值向量，\(\pmb b\)称为资源向量；\(\pmb A,Aeq\)为矩阵。
matlab求线性规划的函数为
[x,fval]=linprog(f,A,b);
[x,fval]=linprog(f,A,b,Aeq,beq);
[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub);//如果Aeq,beq不存在用[]代替
注意：
（1）如果是求\(\underset {x}{max}\ \pmb f^T\pmb x\)，则需转化为\(\underset {x}{min}\ \pmb {-f}^T\pmb x\)，答案为函数求出来的值的相反数。
（2）在得到矩阵\(\pmb {A,b}\)前，要将所有不等式转化为\(\pmb {Ax}\leq \pmb b\)的形式。
2.常见变形
\[min\quad |x_1|+|x_2|+...+|x_n|,\\ s.t\quad \pmb {Ax\leq b}.
\]
这看起来不是线性规划，但可以通过变换转化成线性规划问题。
注意到对任意\(x_i\)，存在\(u_i,v_i\geq 0\)满足
\[x_i=u_i-v_i,|x_i|=u_i+v_i\\u_i=\frac{x_i+|x_i|}{2},v_i=\frac{|x_i|-x_i}{2}
\]
记\(\pmb u=[u_1,...,u_n]^T,\pmb v=[v_1,...,v_n]^T\),于是上述问题转化为
\[min\quad \sum\limits_{i=1}^{n}(u_i+v_i),\\s.t\
\begin{cases}
\pmb{A\cdot (u-v)}\leq \pmb b,\\pmb {u,v}\geq 0.\\end{cases}
\]
改写成matlab形式
\[min\quad ,\left[ \begin{matrix} 1\\1\end{matrix}\right]^T\left[ \begin{matrix} \pmb u\\\pmb v\end{matrix}\right]\\s.t\
\begin{cases}
[A,-A]\cdot \left[ \begin{matrix} \pmb u\\\pmb v\end{matrix}\right],\\pmb {u,v}\geq 0.\\end{cases}
\]
code:
//z=|x1|+2|x2|+3|x3|+4|x4|
f=1:4;
f=[f,f]‘;
A=[1,-1,-1,1;1,-1,1,-3;1,-1,-2,3];
A=[A,-A];
b=[-2;-1;-0.5];
[y,z]=linprog(f,A,b,[],[],zeros(8,1));
x=y(1:4)-y(5:end)
z
参考书目
《数学建模算法与应用》