规划论及MATLAB计算

1、线性规划

问题的提出

例1. 某工厂在计划期内要安排甲、乙两种产品的生产，已知生产单位产品所需的资源A、B、C的消耗以及资源的计划期供给量，如下表：

问题：工厂应分别生产多少单位甲、乙产品才能使工厂获利最多？

解：设 甲、乙产品的产量分别为x1、x2 ，
工厂获利为 z ， 则
目标函数：
Max z = 60x1 + 60x2
约束条件：s.t.
2 x1 + 3 x2 ≤ 180
3 x1 + 2 x2 ≤ 210
x1 + 5 x2 ≤ 250
x1 , x2 ≥ 0
从上述的例子看出，建立数学模型的基本过程是：
1）搞清要解决的问题：目标 和 条件;
2）设置决策变量–描述解决问题的方案;
3）描述约束条件和非负约束;
4）给出目标函数，确定目标函数的优化方向，即优化是对目标函数取最大还是最小。

（2）线性规划模型：一般形式

目标函数：
Max（Min）z = c1 x1 + c2 x2 + … + cn xn
约束条件：s.t.
a11 x1 + a12 x2 + … + a1n xn ≤（ =, ≥ ）b1
a21 x1 + a22 x2 + … + a2n xn ≤（ =, ≥ ）b2
…… ……
am1 x1 + am2 x2 + … + amnxn ≤（ =, ≥ ）bm

                         x1 ，x2 ，… ，xn  ≥ 0

线性规划一般数学模型的矩阵形式

目标函数 max(或min) z=c·x
约束条件 A·x≤ （ =, ≥ ） b
x≥0

式中 c=(c1,c2,…,cn), x=(x1,x2,…,xn)τ

    a11  a12  …  a1n
A=  a21  a22  …  a2n   , b=(b1,b2,…,bm)τ…  am1  am2  …  amn 

3）线性规划模型：标准形式

目标函数：
Max z = c1 x1 + c2 x2 + … + cn xn
约束条件：s.t.
a11 x1 + a12 x2 + … + a1n xn =b1
a21 x1 + a22 x2 + … + a2n xn =b2
…… ……
am1 x1 + am2 x2 + … + amnxn =bm

                         x1 ，x2 ，… ，xn  ≥ 0

线性规划标准型的矩阵形式

目标函数 max z=c·x
约束条件 A·x = b
x≥0

式中 c=(c1,c2,…,cn), x=(x1,x2,…,xn)τ

    a11  a12  …  a1n
A=  a21  a22  …  a2n   , b=(b1,b2,…,bm)τ…  am1  am2  …  amn 

（4）线性规划的图解法

目标函数：
max Z= X1 + X2
约束条件：


例1 的图解
目标函数：
Max z = 60 x1 + 60 x2
约束条件：
2 x1 + 3 x2 ≤ 180 (A)
3 x1 + 2 x2 ≤ 210 (B)
x1 + 5 x2 ≤ 250 ©
x1 ， x2 ≥ 0 (D)

得到最优解：
x1 = 54， x2 = 24
最优目标值 z = 4680

解的几种情况：
线性规划的最优解如果存在
则必定有一个顶点（极点）是最优解
① 唯一解
目标函数等值线与约束边界只有一个交点
② 无穷多最优解
目标函数等值线与约束边界平行
③ 无界解
可行域不封闭
④ 无可行解
可行域为空集

（5）线性规划解的概念

引入松驰变量____含义是资源的剩余量
例1 中引入 s1， s2， s3 模型化为 标准型

目标函数：Max z = 60 x1 + 60 x2 + 0 s1 + 0 s2 + 0 s3
约束条件：s.t. 2 x1 + 3 x2 + s1 = 180
3 x1 + 2 x2 + s2 = 210
x1 + 5 x2 + s3 = 250
x1 , x2 , s1 , s2 , s3 ≥ 0

对于标准型的最优解 x1 =54 x2 = 24 ， s1 = 0 s2 = 0 s3 = 76
说明：生产54单位甲产品和24单位乙产品将消耗完所有的A、B资源，但对资源C则还剩余76。
基最优解、最优解、基可行解、基解、可行解的关系如下所示：

（6）线性规划的基本定理

① 线性规划问题的所有可行解构成的集合(可行域)
R={x|A·x=b,x≥0}
R是一凸集(包括无界域)，它有有限个顶点；
② 线性规划问题的每个基可行解
对应可行域凸集R的一个顶点；
③ 若线性规划问题有最优解,
则必定在某顶点处得到

基本定理把可行域的有限个顶点与基可行解这一代数概念联系起来，可通过求基可行解的代数方法来得到可行域的一切极点，能在有限的计算中获得最优点。