线性规划概念与数学模型

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