@

前言

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

一、基本概念

一般线性规划问题地（数学）标准型为

可行解：满足约束条件的解\(x=[x_1,...,x_n]^T\)
最优解：使目标函数达到最大值的可行解

二、matlab实现

1.常用函数

matlab中规定线性规划的标准形式为：

其中\(\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.常见变形

这看起来不是线性规划，但可以通过变换转化成线性规划问题。
注意到对任意\(x_i\)，存在\(u_i,v_i\geq 0\)满足

记\(\pmb u=[u_1,...,u_n]^T,\pmb v=[v_1,...,v_n]^T\),于是上述问题转化为

改写成matlab形式

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

参考书目

《数学建模算法与应用》

matlab——线性规划

原文：https://www.cnblogs.com/Tarjan-Zeng/p/15028388.html