【数学建模算法】（1）线性规划的基本形式

由于本人正在筹备9月的研究生数学建模比赛，所以需要学习数学建模的相关知识，想把一些学习的心得和成果分享给大家，第一部分就是数学建模中涉及的基本算法，从今天开始我将不定期更新关于数学建模中的基本算法知识以及Matlab实现过程，希望大家捧场。

线性规划的定义及举例

线性规划这个词相信大家并不陌生，但可能由于年代久远大家忘记了它是什么，那我们就看一道例题：

例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000与3000元。生产甲机床需用A,B两种机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用A，B，C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A机器10小时、B机器8小时和C机器 7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？

怎么做这道题呢，让我们把已知条件列出来：

消耗工时如下表：

	甲	乙
A	2	1
B	1	1
C	0	1

问题中给出了每台机器每天的最大工作时间

	A	B	C
最大工作时间	10	8	7

也给出了甲乙两种机床的利润

	甲	乙
利润	4000	3000

假设生产甲机床 $x_{1}$ 台和乙机床 $x_{2}$ 台时，利润最大。
那么设 $z$ 为总利润，我们的任务目标就是让 $z=4000 x_{1}+3000 x_{2}$ 最大。(1)
而限制条件是：
$\left\{\begin{array}{l}{2 x_{1}+x_{2} \leq 10} \\ {x_{1}+x_{2} \leq 8} \\ {x_{2} \leq 7} \\ {x_{1}, x_{2} \geq 0}\end{array}\right.$

上式（1）称为问题的目标函数，上式(2)称为该问题的限制条件。
上面这个问题就是一个完整的线性规划问题。

线性规划问题的标准形式

目标函数
$\max \quad z=\sum_{j=1}^{n} c_{j} x_{j}$
限制条件
$\left\{\begin{array}{l}{\sum_{j=1}^{n} a_{i j} x_{j}=b_{i} \quad i=1,2, \cdots, m} \\ {x_{j} \geq 0 \quad j=1,2, \cdots, n}\end{array}\right.$

满足限制条件的解称为可行解，既满足限制条件又能使目标函数达到最值的解称为最优解。所有可行解构成的集合称为可行域 $R$ 。

Matlab中解决线性规划问题的标准形式

目标函数
$\min _{x} c^{T} x$

注意Matlab中的标准形式是让目标函数最小。

限制条件
$\left\{\begin{array}{l}{A x \leq b} \\ {A e q \cdot x=b e q} \\ {l b \leq x \leq u b}\end{array}\right.$

第一行是不等式限制条件。
第二行是等式限制条件。
第三行是自变量范围。

其中 $c$ , $x$ 是 $n$ 维列向量， $A$ , $Aeq$ 是适当维数的矩阵， $b$ , $beq$ 是适当维数的列向量。

Matlab中的线性规划问题函数原型为：

[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS];
%x是最优自变量，fval是对应最优值，LB和UB是x的上下界，X0是X的初值，OPTIONS是控制参数。

我们高中时学过一种线性规划问题的求解算法———图解法，其思想是在直角坐标系中画出限可行域，之后用代表目标函数的直线族来扫过可行域来确定自变量的最优解。

图解法

不适用于此处，不再过多讨论。

利用Matlab解决线性规划问题

例1
仍然以上题为例，其目标函数和限制条件为：

$\max \quad z=4000 x_{1}+3000 x_{2}$
$\left\{\begin{array}{l}{2 x_{1}+x_{2} \leq 10} \\ {x_{1}+x_{2} \leq 8} \\ {x_{2} \leq 7} \\ {x_{1}, x_{2} \geq 0}\end{array}\right.$

本题中目标函数不符合Matlab标准型，只需将 $c^{T} x$ 变为 $-c^{T} x$ （即代入时将 $c$ 替换为 $-c$ 即可）就可将求取最大值变为求取最小值，即可用matlab求解。

求解代码：

c=[4000 3000];
A=[2 1;
    1 1;
    0 1];
b=[10 8 7]';
Aeq=[];
beq=[];
LB=zeros(2,1);

x=linprog(-c,A,b,Aeq,beq,LB);
%将-c替换成了c，此时函数输出的最优值是-c*x，不是我们想要的最优值，若需要最优值，需要自行计算c*x

输出x

问题求解完毕。

例2
$\max z=2 x_{1}+3 x_{2}-5 x_{3}$
$x_{1}+x_{2}+x_{3}=7$
$2 x_{1}-5 x_{2}+x_{3} \geq 10（*）$
$x_{1}+3 x_{2}+x_{3} \leq 12$
$x_{1}, x_{2}, x_{3} \geq 0$

本题中出现了不等号方向不符合标准型的情况，同理，需要先将不等号进行调整，再代入Matlab函数进行求解。
本题中，（*）标注的不等式是" $\geq$ "号，若要将其变为“ $\leq$ ”，需左右两边加一个“ $-$ ”号。

代码求解：

c=[2 3 -5];
A=[-2 -5 -1;%这一行不等式经过调整，左右取负号
    1 3 1];
b=[-10 12]';
Aeq=[1 1 1];
beq=[7];
LB=zeros(3,1);

x=linprog(-c,A,b,Aeq,beq,LB);%由于目标函数要求取最大值，所以此处代-c

求得：

至此，线性规划问题的基本形式和基本解法就展示完了，下一部分，我们将会讨论一些利用线性规划思想解决的实际问题。