数学建模--线性规划

今天结束了为时两周的数学建模暑假培训，打算重新整理一下课堂上的知识，并通过博客做笔记，这是第一节课讲的内容–线性规划。

线性规划（Linear programming,简称LP）属于运筹学的重要分支，其目的在于合理利用有限资源进行最优决策。

建立线性规划数学模型的基本步骤是

1.确定目标变量和决策变量，一般决策变量要求是非负的；

2.根据决策变量与变量的函数关系确定目标函数；

3.根据限制条件确定约束条件。

线性规划的标准型

min f(x) = c’x

st.

Ax<=b

Aeq.x=beq

lb<=x<=ub

c为行向量。

一般来说，一个问题是否能化成线性规划问题来求解，需符合如下4个假定：

1.比例性假定：决策变量的变化所引起的目标函数的改变量和决策变量的改变量成比例，同样，每个决策变量的变化所引起的约束方程左端值的改变量和该变量的改变量成比例 ；

2.可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数是每个决策变量对目标函数贡献的总和；

3.连续性假定：线性规划问题中的决策变量应取连续值；

4.确定性假定:线性规划问题中的所有参数都是确定的参数，线性规划问题不包含随机因素。

线性规划问题的解有可能出现如下几种情况：

1.有可行解

1)有唯一最优解 ；

2)有无穷多最优解；

3)无最优解。

2.无最优解。

线性规划问的求解算法都是基于单纯形法，单纯形法的基本思路是：先找出可行域的一个极点，根据一定规则判断是否最优，否则转到与之相邻的另一个极点，并使目标函数值最优；如此下去，直到找到某一最优解。

MATLAB中解决线性规划的基本函数是linprog，基本调用格式如下：

x=linprog(c,A,b)

[x,y,exitflag]=linprog(c,A,b,Aeq,beq,lb,ub,x0,opt)

x为最优解列向量

y为目标函数最小值

exitflag为描述调用寻优函数时退出的状态

（

1 表示函数收敛到解x

0 表示达到了函数最大评价次数或迭代次数

-2 表示没有找到可行解

-3 表示所求解的线性规划问题是无界的

-4 表示在执行算法的时候遇到了NaN

-5 表示原问题和对偶问题都是不可行的

-6 表示搜索方向使得目标函数值下降得很少

）

例子

min z=2x1+3x2+x3

st.

x1+4x2+2x3>=8

3x1+2x2>=6

x1,x2,x3>=0

c=[2 3 1]'
A=[1 4 2;3 2 0]
b=[8;6]
[x y]=linprog(c,-a,-b,[],[],zeros(3,1))

x=
    0.8066
    1.7900
    0.0166
y=
    7.000