由于本人正在筹备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 |
假设生产甲机床台和乙机床
台时，利润最大。
那么设为总利润，我们的任务目标就是让
最大。(1)
而限制条件是：
上式（1）称为问题的目标函数，上式(2)称为该问题的限制条件。
上面这个问题就是一个完整的线性规划问题。
线性规划问题的标准形式
目标函数
限制条件
满足限制条件的解称为可行解，既满足限制条件又能使目标函数达到最值的解称为最优解。所有可行解构成的集合称为可行域
。
Matlab中解决线性规划问题的标准形式
目标函数
注意Matlab中的标准形式是让目标函数最小。
限制条件
第一行是不等式限制条件。
第二行是等式限制条件。
第三行是自变量范围。
其中,
是
维列向量，
,
是适当维数的矩阵，
,
是适当维数的列向量。
Matlab中的线性规划问题函数原型为：
[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS];
%x是最优自变量，fval是对应最优值，LB和UB是x的上下界，X0是X的初值，OPTIONS是控制参数。
我们高中时学过一种线性规划问题的求解算法———图解法，其思想是在直角坐标系中画出限可行域，之后用代表目标函数的直线族来扫过可行域来确定自变量的最优解。
图解法
不适用于此处，不再过多讨论。
利用Matlab解决线性规划问题
例1
仍然以上题为例，其目标函数和限制条件为：
本题中目标函数不符合Matlab标准型，只需将变为
（即代入时将
替换为
即可）就可将求取最大值变为求取最小值，即可用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
x =
2.0000
6.0000
问题求解完毕。
例2
本题中出现了不等号方向不符合标准型的情况，同理，需要先将不等号进行调整，再代入Matlab函数进行求解。
本题中，（*）标注的不等式是""号，若要将其变为“
”，需左右两边加一个“
”号。
代码求解：
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
求得：
x =
4.5000
2.5000
0
至此，线性规划问题的基本形式和基本解法就展示完了，下一部分，我们将会讨论一些利用线性规划思想解决的实际问题。
网友评论