《1-1线性规划概念与数学模型-wxp.ppt》由会员分享，可在线阅读，更多相关《1-1线性规划概念与数学模型-wxp.ppt（43页珍藏版）》请在三一文库上搜索。
1、第一章、 线性规划,1、线性规划问题及其数学模型 2、线性规划的几何意义 3、线性规划的求解单纯形法,一、线性规划问题：生产计划问题（例1）,甲、乙产品每件获利分别为2、3元，如何安排获利最多？,第一节、 线性规划问题及其数学模型,如何制定生产计划，使两种产品总利润最大？,何为生产计划？ 总利润如何描述？ 还要考虑什么因素？ 有什么需要注意的地方（技巧）？ 最终得到的数学模型是什么？,二、线性规划的定义和数学描述（模型） 1定义：对于求取一组变量xj (j =1,2,n)，使之既满足线性约束条件，又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划。,2
2、. 线性规划模型的特点：,用一组未知变量表示要求的方案，这组未知变量称为决策变量； 存在一定的限制条件，且为线性表达式； 有一个目标要求（最大化，当然也可以是最小化），目标表示为未知变量的线性表达式，称之为目标函数； 对决策变量有非负要求。,三LP的数学描述(数学模型)：,一般形式,二、 线性规划的图解法,解的几何表示,1什么是图解法？ 线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。 求解的思路是：先将约束条件加以图解，求得满足所有约束条件的解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。,可行解：满足所有约束条件的解,图解法举例,实施图解法，以求出最优生产计
3、划（最优解）,例1 maxZ=2x1+3x2,s.t.,工时 原材料,由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可进行图解.,第一步：建立平面直角坐标系，标出坐标原 点, 坐标轴的指向和单位长度。 用x1轴表示产品甲的产量，用x2轴表示产品乙的产量。 第二步：对约束条件加以图解。 第三步：画出目标函数等值线，结合目标函数的要求求出最优解最优生产方案。,约束条件的图解: 每一个约束不等式在平面直角坐标系中都代表一个半平面，只要先画出该半平面的边界，然后确定是哪个半平面。,以第一个约束条件（工时） x1+2 x2 8 为例 说明约束条件的图解过程。,如果全部的劳动工时都用来生
4、产甲 产品而不生产乙产品，那么甲产品的最大可能产量为8吨，计算过程为： x1+208 x18 这个结果对应着下图中的点B(8,0),同样我们可以找到B产品最大可能生产量对应的点A(0,4)。连接A、B两点得到约束 x1+2 x2 8 所代表的半平面 的边界: x1+2x2 8， 即直线AB。,1,2,3,4,5,6,7,8,9,1,2,3,4,5,x1+2x2 = 8,A,B,A,B,三个约束条件及非负条件x1,x2 0所代表的公共部分 图中阴影区，就是满足所有约束条件和非负条件的点的集合，即可行域。在这个区域中的每一个点都对应着一个可行的生产方案。,第二、三个约束条件的边界 直线CD，EF:
5、 4x1 =16,4x2 =12,1,2,3,4,5,6,7,8,9,1,2,3,4,5,E,F,4x2 = 12,4x1=16,A,B,C,D,x1+4x2 = 8,令 Z=2x1+3x2=c,其中c为任选的一个常数，在图中画出直线 2x1+3x2=c,这条直线上的点即对应着一个可行的生产方案，即使两种产品的总利润达到c。 这样的直线有无数条，而且相互平行，称这样的直线为目标函数等值线。只要画出两条目标函数等值线，比如令c0和c=6，就能看出 目标函数值递增的方向， 用箭头标出这个方向。 图中两条虚线 l1和l2就 分别代表 目标函数等值线 2x1+3x2=0 和 2x1+3x2=6, 箭头
6、表示使两种产品的总 利润递增的方向。,1,2,3,4,5,6,7,8,9,1,2,3,4,5,x1+2x2 = 8,A,B,D,C,4x1=16,l1,l2,l3,F,E,B,A,4x1=12,沿着箭头的方向平移目标函数等值线，使其达到可行域中的最远点Q2, Q2点就是要求的最优点，它对应的相应坐标 x1=4,x2=2 就是最有利的产品组合，即生产甲产品4件，乙产品2件能使两种产品的总利润达到最大值 Zmax=24+32=14(元)，x1=4,x2=2就是线性规划模型的最优解，Zmax=14就是相应的目标函数最优值,尽管最优点的对应坐标可以直接从图中给出，但是在大多数情况下，对实际问题精确地看
7、出一个解答是比较困难的。所以，通常总是用解联立方程的方法求出最优解的精确值。 比如Q2点对应的坐标值我们可以通过求解下面的联立方程，即求直线AB和CD的交点来求得。 直线AB: x1+2x2=8 直线CD: 4x1=16,（8，0）,C=6,（0，4）,C=0,s.t.,Q2（4，2）,一般线性规划解的几种不同情形：,无穷多最优解（多重最优解）,无界解,无可行解,0 1 2 3 4 5 6 7 8 9 x1,5 4 3 2 1,x2,-2 -1,4x1=12,4x1=16,x1+2x2 = 8,-2x1+x2 = 4,二、 线性规划的标准型,1、LP标准型的概念 （1）什么是LP的标准型？标准
8、格式！ （2）LP标准型的特点 目标函数约定是极大化Max(或极小化Min); 约束条件均用等式表示; 决策变量限于取非负值; 右端常数均为非负值 ;,2LP的数学描述(数学模型)：,（1）标准形式,（2）紧缩形式,（3）向量矩阵形式：,其中：,（4）矩阵形式,其中 :,3、LP问题的标准化 （为了问题的求解）,（2） 约束条件的标准化 & 约束条件是 类型，左边加非负松弛变量, 变为等式； & 约束条件是类型，左边减非负剩余变量, 变为等式； & 变量符号不限，引入新变量,（1）目标函数的标准化,将下面的线性规划问题化为标准型：,讨论： 如何下手？标准化过程排序 -,课堂练习1, x3； 约
9、束1引松弛变量；约束2引剩余变量；约束3变号； 目标函数标准化，引入变换Z=-Z； 整理；,令,四、 线性规划的各种解,可行解：满足LP约束条件的解 称为LP的可行解,其中使目标函数达到最大（或最小）值的可行解为最优解。 可行域：所有可行解的集合。 最优值：与LP问题最优解x*对应的目标函数的取值Zmax叫最优值。,注意：LP问题求解结果包括两部分： 最优解x*（列向量） 最优值Zmax（数值）,基,设LP标准型中约束方程组系数矩阵A是mn阶矩阵，秩为m，B是A中mm阶非奇异子矩阵（|B|0），则称B是LP问题的一个基。,x1， x2， x3 （P1，P2，P3）,基向量：设B为LP问题的一个
10、基，即 B=(Pr1, Pr2, Prm)。则称线性独立列向量Prj = (a1,rj, a2,rj, an,rj)T, j=1,2,m 为基向量。因此，一个基对应m个基向量。 基变量,非基变量：与基向量Prj对应的决策变量 xrj (j=1,2, m)称基变量；其他n-m个决策变量xrj (j=m+1,m+2, n)称为非基变量。,基本解 :设B是LP问题的一个基，令与B的列不相对应的n-m个决策变量(即非基变量)等于 0，对应方程组的解称为方程组AX=b关于基B的解，也叫LP问题的一个基本解.,注意：可以看出,有一个基就有一个基本解，基本解的个数等于基的个数，总是小于等于 。当一个基解中的
11、非零分量小于m时，该基解是一个退化解。,基可行解：满足非负条件的基本解叫基可行解，其对应的基称为可行基。基本可行解的非零分量均为正分量，分量的个数m。,解的关系,可行解,基本解,基本 可行解,基本解与基本可行解的几何意义,求解线性规划问题：,讨论求取基本解的步骤： 将线性规划标准化； s.t. AX=b,1)寻找基(不超过 个); 2)确定基变量与非基变量； 例如，基变量( x3, x4, x5 ) 3)令非基变量取值为0； 令x1=x2=0 4)(基变量, 非基变量)构成基本解。 (0,0,4,2,2),然后按照基本解的定义：,H(6,4,-6,0,0)T, C(3,1,0,3,0)T, B
12、(2,2,0,0,2)T, D(2,0,2,4,0)T, F(-2,0,6,0,4)T, I(4,0,0,6,-2)T, E(0,-2,6,6,0)T, A(0,1,3,0,3)T, G(0,4,0,-8,6)T, O(0,0,4,2,2)T.,对于上例,共有10个基本解,求得的基本解和图解法对照，找出相应的点。 为何红点和绿点是基本解却不是基本可行解?,1,2,3,4,3,2,1,0,X2,X1,x1-x2=2,-x1+2x2=2,x1+x2=4,Z=0,Z=14,I,D,B,A,C,H,F,E,G,结论： (1) 基本解对应所有可行域边界及其延 长线、坐标轴之间的交点； (2) 基本可行解对应可行域的顶点。,第一节 总 结,LP定义，模型特点， 图解法,标准型概念及其作用 标准型特点及四种形式 标准化步骤,LP的提出与定义,LP数学描述,可行解 基解（基） 基可行解（可行基）,LP问题的解,课后作业:,P44页1.1题的4个小题，1.3题的（1）题,