@

目录

• 前言
• 一、基本概念
• 二、matlab实现
  • 1.常用函数
  • 2.常见变形
• 参考书目

---

前言

线性规划是数学规划中的一个重要分支，常用于解决如何利用现有资源来安排生产，以取得最大经济效益的问题。本文将粗略地介绍线性规划，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实现

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\)的形式。

\[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

---

参考书目

《数学建模算法与应用》