线性规划问题的基本内容
线性规划解决的是自变量在一定的线性约束条件下，使得线性目标函数求得最大值或者最小值的问题。
\[ \min z=\sum_{j=1}^{n} f_{j} x_{j} \]
\[ \text { s.t. }\left\{\begin{array}{ll}{\sum_{j=1}^{n} a_{i j} x_{j} \leqslant b_{i}} & {(i=1,2, \cdots, m)} \\ {\sum_{j=1}^{n} a_{k j}^{\mathrm{eq}} x_{j} \leqslant b_{k}^{\mathrm{eq}}} & {(k=1,2, \cdots, h)} \\ {\mathrm{lb}_{j} \leqslant x_{j} \leqslant \mathrm{ub}_{j}} & {(j=1,2, \cdots, n)}\end{array}\right. \]
其中
价值系数向量为
\[ \mathbf{F}=\left(f_{1}, f_{2}, \cdots, f_{n}\right)^{\mathrm{T}} \]
决策变量向量为
\[\mathbf{X}=\left(x_{1}, x_{2}, \cdots, x_{n}\right)^{\mathrm{T}}\]
不等式约束系数矩阵为
\[\mathbf{A}=\left(\begin{array}{ccc}{a_{11}} & {\cdots} & {a_{1 n}} \\ {\vdots} & {\ddots} & {\vdots} \\ {a_{m 1}} & {\cdots} & {a_{m n}}\end{array}\right)\]
不等式右端常数向量为
\[\mathbf{B}=\left(b_{1}, b_{2}, \cdots, b_{n}\right)^{\mathrm{T}}\]
等式约束系数矩阵为
\[\mathbf{A}_{eq} = \left(\begin{array}{ccc}{a_{11}^{\mathrm{cq}}} & {\cdots} & {a_{1 n}^{\mathrm{cq}}} \\ {\vdots} & {\ddots} & {\vdots} \\ {a_{\mathrm{h1}}^{\mathrm{eq}}} & {\cdots} & {a_{\mathrm{hn}}^{\mathrm{eq}}}\end{array}\right)\]
等式右端常数向量为
\[\mathbf{B}_{\mathrm{eq}}=\left(b_{1}^{\mathrm{eq}}, b_{2}^{\mathrm{eq}}, \cdots, b_{\mathrm{h}}^{\mathrm{eq}}\right)^{\mathrm{T}}\]
决策变量下界向量为
\[\mathbf{L B}=\left(\mathrm{lb}_{1}, \mathrm{lb}_{2}, \cdots, \mathrm{lb}_{n}\right)^{\mathrm{T}}\]
决策变量上界变量为
\[\mathbf{UB}=\left(\mathrm{ub}_{1}, \mathrm{ub}_{2}, \cdots, \mathrm{ub}_{n}\right)^{\mathrm{T}}\]
当目标函数为最小值时，上述问题可以写成如下形式：
\[ \min z=\boldsymbol{F}^{\mathrm{T}} \boldsymbol{X} \]
\[ \text { s.t. }\left\{\begin{array}{l}{\mathbf{A}\mathbf{X} \leqslant \mathbf{B}} \\ {\mathbf{A}_{\mathrm{eq}} \mathbf{X}=\mathbf{B}_{\mathrm{eq}}} \\ {\mathbf{LB} \leqslant \mathbf{X} \leqslant \mathbf{UB}}\end{array}\right. \]
当目标函数为最大值时，上述问题可以写成如下形式：
\[ \max z=\boldsymbol{-F}^{\mathrm{T}} \boldsymbol{X} \]
\[ \text { s.t. }\left\{\begin{array}{l}{\mathbf{A}\mathbf{X} \leqslant \mathbf{B}} \\ {\mathbf{A}_{\mathrm{eq}} \mathbf{X}=\mathbf{B}_{\mathrm{eq}}} \\ {\mathbf{LB} \leqslant \mathbf{X} \leqslant \mathbf{UB}}\end{array}\right. \]
Matlab模型代码
调用形式
[X,FVAL,EXITFLAG,OUTPUT,LAMBDA] = linprog(F,A,B,Aeq,Beq,LB,UB) % 目标函数为最小值
[X,FVAL,EXITFLAG,OUTPUT,LAMBDA] = linprog(-F,A,B,Aeq,Beq,LB,UB) % 目标函数为最大值输入变量
F 为目标函数中的价值系数向量
A 为不等式约束系数矩阵(注意默认不等式方向为小于等于，若为大于等于，需要将其取相反数)
B 为不等式右端常数向量(注意默认不等式方向为小于等于，若为大于等于，需要将其取相反数)
Aeq 为等式约束系数矩阵
Beq 为等式右端常数向量
LB 为决策变量下界向量
UB为决策变量上界向量
在调用时，输入参数不存在时，可以将其输入用 [] 空矩阵表示。
输出变量
- X 为最优解
- FVAL 为最优目标值
- EXITFLAG 为运行结束标志，当等于1时，表示程序收敛于解 X；当等于0时，表示程序运行次数到达最大；当小于0时，说明情况较多
- OUTPUT 为程序迭代次数
- LAMBDA 为解X相关的Largrange乘子和影子价格
案例演示
目标函数与约束条件
\[ \min z=2 x_{1}+3 x_{2}+x_{3} \]
\[ \left\{\begin{array}{l}{x_{1}+4 x_{2}+2 x_{3} \geq 8} \\ {3 x_{1}+2 x_{2} \geq 6} \\ {x_{1}, x_{2}, x_{3} \geq 0}\end{array}\right. \]
Matlab程序
F= [2;3;1];
A = [1,4,2;3,2,0];
B = [8;6];
LB = zeros(3,1);
[X,FVAL] = linprog(F,-A,-B,[],[],LB,[])运行结果
Optimization terminated.
X =
0.8066
1.7900
0.0166
FVAL =
7.0000
