第三章 线性规划及图解法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 线性规划及图解法,第三章 线性规划及图解法,确定型决策,线性规划方法,线性规划,所有资源限制条件式和目标式都是自变量的一次方关系。,描述的是在一定资源限制下,(,自然状态,),，给出了很多个可以选择的不方案,(,运行方案,),，从这些方案中找到一个最好的方案来执行。,第一节 问题的提出,一、 线性规划数学模型,二、 线性规划模型的三个基本要素,三、 线性规划数学模型的一般形式,一、线性规划数学模型,例,1,某工厂在计划期内要安排,I,，,两种产品的生产。生产单位产品所需的设备台时及,A,，,B,两种原材料的消耗以及资源的限制如下表所示。工厂每生产一个单位产品,I,可获利,50,元，每生产一个单位产品,可获利,100,元，问工厂应分别生产多少单位产品,I,和产品,才能使获利最多？,产品资源,I,II,资源限制,设备,1,1,300,台时,原料,A,2,1,400kg,原料,B,0,1,250kg,建立问题的数学关系,2,、用,x,l,和,x,2,以线性函数形式表达工厂所要求的最大利润的目标,:,单位产品,I,和,的利润,3,、以,x,l,和,x,2,的线性不等式来表示问题中相应资源的约束条件：,台时数的限制：,x,l,+,x,2,300,max z= 50,x,l,100,x,2,，,原材料的限量 ：,2,x,l,+,x,2,400,，,x,2, 250,解,:,1,、设,:,x,l,，,x,2,分别表示产品,I,和产品,的产量。,例,1,的线性规划数学模型,max,z,50,x,l,+100,x,2,满足条件：,x,l,x,2,300,2,x,l,+,x,2,400,x,2,250,x,l,0,，,x,2,0,即：这一类问题都可以用这种语言、这种方式来表达。,二、线性规划模型的三个基本要素,（,1,）决策变量（约束变量）：用符号来表示可控制的因素，如,x,i,。,（,2,）目标函数：,Max z,或,Min f,，用来计算和实现问题目标。,（,3,）约束条件：,s.t,. (subject to),满足于（一个等式或不等式组），一般是问题的资源限制 条件。,例,2,： 营养配餐问题,假定一个成年人每天需要从食物中获得,3000,千卡的热量、,55,克蛋白质和,800,毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分及市场价格见下表。问如何选购才能在满足营养的前提下使购买食品的费用最小？,序号,食品名称,热量,(,kcal/kg,),蛋白质,(,g/kg,),钙,(,mg/kg,),价格,(,元,/kg,),1,鸡肉,1000,50,400,14,2,鸡蛋,800,60,200,6,3,大米,900,20,300,3,4,白菜,200,10,500,2,解：,（,1,）确定决策变量,设,x,i,为第,i,种食品每天的购入量；,（,3,）确定约束条件,食品的热量、,蛋白质和钙的单位含量构成和总含量应满足最低要求。,（,2,）确定目标函数,购买食品的费用为最小，总费用为：,14,x,1,+ 6,x,2,+ 3,x,3,+ 2,x,4,配餐问题的线性规划模型,min Z = 14,x,1,+ 6,x,2,+ 3,x,3,+ 2,x,4,s.t. 1000,x,1,+800,x,2,+900,x,3,+200,x,4,3000,50,x,1,+ 60,x,2,+ 20,x,3,+ 10,x,4,55,400,x,1,+200,x,2,+300,x,3,+500,x,4,800,x,1,，,x,2,，,x,3,，,x,4,0,总热量,蛋白质,钙,食用量不能为负,一般线性规划问题的建模过程,（,1,）理解要解决的问题。明确在什么条件下，要追求什么目标。,（,2,）定义决策变量。每个问题都用一组决策变量,(,x,1,x,2, ,x,n,),表示，当这组决策变量取具体值时就代表一个具体方案，一般这些变量取值是非负的。,（,3,）用决策变量的线性函数形式写出所要追求的目标，即目标函数，按问题的不同，要求目标函数实现最大化或最小化。,（,4,）用一组决策变量的等式或不等式来表示在解决问题过程中所必须遵循的约束条件（决策分析中的自然状态）。,三、线性规划数学模型的一般形式,max(min,),z,=,c,l,x,l,+,c,2,x,2,+,+,c,n,x,n,；,满足约束条件：,a,l1,x,l,+,a,12,x,2,+,a,1,n,x,n,（,=,，）,b,1,a,21,x,l,+,a,22,x,2,+,a,2,n,x,n,（,=,，）,b,2,a,m,1,x,l,+,a,m,2,x,2,+,a,mn,x,n,（,=,，）,b,m,x,l,，,x,2,，,，,x,n,0,c,i,是目标函数的变量系数，也称做价值系数；,a,ij,是约束条件的变量系数，也称做资源配制系数；,b,j,是常数项，也称做资源限制量。,其中：,线性规划问题的求解方法,1,、二维线性规划问题的图解法；,2,、高维线性规划问题的单纯形方法手工求解；,3,、计算机软件求解。,第二节 图解法,特征：,只包含两个决策变量的线性规划问题，才可用图解法来求解。,优点：,简单直观，有助于了解线性规划问题求解的基本原理。,方法：,在以,x,1,，,x,2,为坐标轴的直角坐标系里，图上任意一点的坐标代表了决策变量,x,1,，,x,2,的一组值，也就代表了一个具体的决策方案。,一、最大化问题的图解法,仍用例,1,来介绍线性规划问题的图解法！,图,3-1(,满足约束条件的公共部分,),0 100 200 300 400,x,1,400,300,200,100,x,2,x,2,=250,2,x,l,+,x,2,=400,x,l,+,x,2,=300,同时满足：,2,x,1,+,x,2,400,x,1,+,x,2,300,x,2,250,x,1,0,x,2,0,的区域可行域,可行域,图,3-2,线性规划问题的可行域,0 100 200 300 400,x,1,400,300,200,100,x,2,可行域,A(0,250),B(50,250),C(100,200),D(200,0),O(0,0),线性规划模型的可行域,可行域的几何形状可千变万化，但几何结构都是凸集。,图,3-3,最优目标函数值,0 100 200 300 400,x,1,400,300,200,100,x,2,可行域,A(0,250),B(50,250),C(100,200),D(200,0),z=0=50,x,1,+100,x,2,图,3-3,最优目标函数值,0 100 200 300 400,x,1,400,300,200,100,x,2,可行域,A(0,250),B(50,250),C(100,200),D(200,0),z=10000=50,x,1,+100,x,2,图,3-3,最优目标函数值,0 100 200 300 400,x,1,400,300,200,100,x,2,可行域,A(0,250),B(50,250),C(100,200),D(200,0),z=20000=50,x,1,+100,x,2,图,3-3,最优目标函数值,0 100 200 300 400,x,1,400,300,200,100,x,2,可行域,A(0,250),B(50,250),C(100,200),D(200,0),z=30000=50,x,1,+100,x,2,图,3-3,最优目标函数值,0 100 200 300 400,x,1,400,300,200,100,x,2,可行域,A(0,250),B(50,250),C(100,200),D(200,0),z=27500=50,x,1,+100,x,2,最优目标函数值,B,点的坐标为,(50,，,250),，因此最佳决策为,x,1,=50,，,x,2,=250,，此时,z,=27500,。,最优生产计划方案是生产产品,I 50,单位，生产产品,250,单位，可得最大利润,27500,元。,二、线性规划问题的解,1,、在线性规划问题的解集合中，若约束条件能构成一个封闭的可行域，则可行域的任意点都是问题的一个可行解，这些可行解中必有最优解。,若最优解是可行域中一个点，则这个解是线性规划的唯一最优解。唯一最优解都必落在可行域的顶点上，可行域的所有顶点称为基本可行解；,对于求最大目标的线性规划问题，取,Z,值最小的基本可行解为初始基本可行解，再依次迭代至最优解。,求最小目标的情况，可选可行域中任意目标初函数值较大的点为初始基本可行解，再依次迭代至最优解。,线性规划问题的解（,2,）,2,、若可行域的某一个边与目标函数平行，则最优解是这条边上的所有点，所以是无穷多点，此时线性规划问题就有无穷多解（或最优解不唯一）。,3,、对于目标为求最大的线性规划问题，若约束条件不能构成封闭（或有限）区域的可行域，如沿目标函数值增大的方向无限扩散而没有边界。这时的可行域是无界的，线性规划问题就有无界解。,4,、若约束条件虽构成封闭区域，但是两个及两个以上的互不相连的区域，那么这些区域中的点都不能同时满足约束要求，因此都不是可行域，则线性规划问题没有可行域，即无可行解（或无解）。,三、剩余资源的松弛量,在线性规划的解中，约束条件的实际值与常数项（资源限制量）不一定相等。,设备台时：,150+1250=300,(kg,),等于限制量,原料,A,：,250+1250=350(kg),小于限制量,原料,B 050+1250,250(kg),等于限制量,在线性规划中，一个“”约束条件中没使用的资源或能力被称之为松弛量。,松弛变量,松弛变量,:,代表没使用的资源或能力的变量 。,约束条件实际值,+,松弛变量,=,资源限制量,在例,1,中引入三个松弛变量,s,l,、,s,2,、,s,3,后，线性规划数学模型描述为：,约束条件：,x,1,+,x,2,+,s,l,300,，,2,x,1,+,x,2,+,s,2,400,，,x,2,+,s,3,250,，,x,1,，,x,2,，,s,l,，,s,2,，,s,3,0,例,1,中,s,l,0,s,2,50,s,3,0,max,z,50,x,1,+100,x,2,+0,s,l,+0,s,2,+0,s,3,；,四、最小化问题的图解法,例,2,：下面给出一个求目标函数最小化的线性规划问题。,min,f,= 11,x,1,+8,x,2,约束条件,10,x,1,+2,x,2,20,3,x,1,+3,x,2,18,4,x,1,+9,x,2,36,x,1,，,x,2,0,图,3-4,例,2,的可行域及基本可行解,可行域 ：,以,x,1,=0,、,AB,、,BC,、,CD,和,x,2,=0,形成的半发散区域,基本可行解：,A,、,B,、,C,、,D,点为基本可行解。,离原较远的基本可行解为初始基本可行解。,B(1, 5),x,2,8,6,4,2,x,1,2 4 6 8,A(0, 10),C(3.6, 2.4),D(9, 0),图,3-5,例,2,目标函数的最优解,B(1, 5),x,2,8,6,4,2,x,1,2 4 6 8,f,= 11,x,1,+8,x,2,目标函数,f,11,x,1,+8,x,2,减小时，其代表的直线向左下方平移 ，当移动到,B,点 ，目标函数在可行域内取最小值。,图,3-5,例,2,目标函数的最优解,B(1, 5),x,2,8,6,4,2,x,1,2 4 6 8,f,= 11,x,1,+8,x,2,即获得问题的最优解：,x,1,=1,x,2,=5,。,最优值：,min,f,= 11,x,1+8,x,2,=51,五、多于资源低限的剩余量,把例,2,中,x,1,=1,，,x,2,5,代入约束条件：,10,x,1,+2,x,2,20,3,x,1,+3,x,2,18,4,x,1,+9,x,2,36,资源,限制量,资源利用,实际值,10,1+25=20,31+35=18,41+95=49,“”约束条件中超过资源或能力最低限量被称之为剩余量。,剩余变量,剩余变量,:,代表没超过资源或能力最低限的变量 。,约束条件实际值,剩余,变量,=,资源限制量,约束条件：,10,x,1,+,2,x,2,-,s,l,20,，,3,x,1,+3,x,2,-,s,2,18,，,4,x,1,+9,x,2,-,s,3,36,，,x,1,，,x,2,，,s,l,，,s,2,，,s,3,0,例,2,中,s,l,0,s,2,0,s,3,13,例,2,引入三个剩余变量,s,l,、,s,2,、,s,3,后，线性规划数学模型描述为：,max,z,11,x,1,+8,x,2,+0,s,l,+0,s,2,+0,s,3,；,六、线性规划数学模型的标准形式,引入了松驰变量和剩余变量后，就可以将线性规划数学模型用“”，“”和“,=”,建立的一般形式化为统一用“,=”,的标准形式：,max(min,),z,=,c,l,x,l,+,c,2,x,2,+,+,c,n,x,n,；,约束条件：,a,l1,x,l,+,a,12,x,2,+,a,1,n,x,n,=,b,1,a,21,x,l,+,a,22,x,2,+,a,2,n,x,n,=,b,2,a,m,1,x,l,+,a,m,2,x,2,+,a,mn,x,n,=,b,m,x,l,，,x,2,，,，,x,n,0,线性规划标准形式的特征：,所有约束条件都是“,=”,关系,若不是“,=”,关系，可以添加松弛变量或剩余变量，将不等号化为等号。,决策变量的取值区间,0,x,i,+,若变量不在此区间，需要进行数学代换，将其调整到这个区间；,常数项,b,j,都为大于或等于,0,的数；,若是小于,0,的数时，可将等号两端同乘一个,-1,。,目标函数即可求最大，也可求最小，最大和最小可以转换，转换的规则是：,max,z=,min (,-z,),第三节 线性规划问题的灵敏度分析,灵敏度分析,研究线性规划的一些系数,c,i,a,ij,b,j,的微小变化对最优解所产生的影响。,灵敏度分析的意义：,用确定的（一组理想的）环境数据建立模型，研究环境变化情况下不确定的（一系列现实的）问题。,一、目标函数中变量系数,c,i,的取值范围分析,c,i,代表广义的产品价值 ，称之为价值系统，价值或价格是经营的环境。,c,i,的灵敏度分析是研究经营环境的变化对最优解的影响。,c,i,的改变只是改变目标函数直线的斜率，不改变可行域的形状。,例,1,中,c,i,的变化如何影响最优解？,目前的生产条件下：,生产,50,单位产品,I,、,250,单位产品,可以获得最大利润。,当产品,I,，,中的某一产品的单位利润增加或减少时，为了获取最大利润就应该增加或减少这一产品的产量，即改变最优解。如何精确地确定这一产品利润变化的上限与下限，使得利润在这个范围内变化时其最优解不变，即仍然生产,50,单位的产品,I,和,250,单位的产品,而使获利最大？,图,3-6,目标函数直线斜率变化分析,x,1,0 100 200 300,x,2,300,200,100,直线,S,3,(,原料,A,约束,),直线,z,(,目标函数,),直线,S,1,(,原料,B,约束,),直线,S,2,(,设备约束,),A,B,D,C,目标函数,系数的,取值范围,当 时，,B,仍然是其最优解 。,1 0,假设单位产品,的利润为,100,元不变，即,c,2,100,，则有,即只要当产品,的利润为,100,元，产品,I,的利润在,0-100,元之间时，坐标,x,l,=50,，,x,2,=250,的顶点,B,仍是最优解。,1 0,0,c,l,100,目标函数,系数的,取值范围,假设单位产品,I,的利润为,50,元不变，即,c,l,=50,，得：,1 0,50,c,2,即当产品,I,的利润为,50,元，而产品,的利润只要大于等于,50,元时，顶点,B,仍为其最优解。,最低限,当前值,最高限,C,1,0,50,100,C,2,50,100,不限,同样在本问题中使得最优解放不变的目标函数两个系数的取值范围如下表：,二、约束条件中常数项,b,j,的取值范围分析,1,、对偶价格,常数项,b,j,代表的是厂房面积、生产总时间、设备数量等所提供给企业经营的资源限制量。,b,j,的灵敏度分析是研究资源的变化对最优解的影响。,b,j,的改变是可行域某一边的平行移动，这种改变必将导致最优解和最优值的改变。,图,3-7,常数项的变化改变可行域,B,C,直线,Z(,目标函数,),100,200,300,x,2,200,100,300,x,1,0,O,D,A,例,1,中的可行域是,OABCD,，最优解,是,B,（,20,，,250,），最优值是,27500,。,图,3-7,常数项的变化改变后的解,假设例,1,中的设备台时数增加到,310,个台时，则例,1,中的设备台时数的约束条件变为：,x,l,+,x,2,310,B,B,C,直线,Z(,目标函数,),C,100,200,300,x,2,200,100,300,x,1,0,O,D,A,新的可行域变为,OABCD,，最优解由,B,点变为,B,。,B,点的坐标为,x,l,= 60,x,2,=250,，获得的最大利润为,28000,（元）。,对偶价格,在约束条件常数中增加一个单位而使最优目标函数值得到改进的数量称之为这个约束条件的对偶价格。,图,3-8,100,200,300,x,2,B,C,直线,Z(,目标函数,),C,D,200,100,300,x,1,0,O,D,A,原料,A,增加,10 kg,，对最优解产生的影响,约束条件：,2,x,l,+,x,2,410,线性规划的可行域变为,OABCD,，但它的最优解仍是,B,点，它的最优值仍然是,27500,。因此原料,A,的对偶价格为零。,对偶价格的进一步解释,（,1,）如果对偶价格大于零，则其最优目标函数值得到改进，即求最大值时，常数项的增（减）使最优目标函数值变得更大（更小）；求最小值时，常数项的增（减）使最优目标函数值变得更小（更大）。,（,2,）如果对偶价格小于零，则其最优目标函数值变坏，即求最大值时，常数项的增（减）使最优目标函数值变得更小（更大）；求最小值时，常数项的增（减）使最优目标函数值变得更大（更小）。,（,3,）如果对偶价格等于零，则常数项的增（减）不会使其最优目标函数值改变。,（,4,）若约束条件的松驰量或剩余量不为,0,，则对偶价格必等于零。,2,、常数项的上限与下限,常数项的改变，将使可行域的边界发生平移，因此，最优解和最优值都必将发生改变。,常数项的改变也会影响对偶价格的值。,但,在现有最优解的前提下，并不是常数项的所有改变都会导致对偶价格的改变。,确切地说，常数项的改变肯定会改变可行域的形状，也可能会改变可行域的结构。只有可行域的结构发生改变时才会使对偶价格改变。,我们关心的常数项的上限和下限是在现有最优解的前提下，使对偶价格不变的常数项的取值范围。,图,3-9,0 100 200 300 400,x,1,400,300,200,100,x,2,可行域,A,C,x,2,x,l,+,x,2,=300=b,1,x,2,=250=b,3,2x,l,+,x,2,=400=b,2,最优解,目标函数,O,B,常数项没变化的最优解,D,最优解,图,3-10,0 100 200 300 400,x,1,400,300,200,100,x,2,x,2,=250=b,3,2x,l,+,x,2,=400=b,2,D,B,O,C,A,目标函数,x,l,+,x,2,=260=b,1,可行域,常数项,b,1,在改变（由,300,减小到,260,），使可行域形状改变，而结构不变，对偶价格就不变。,400,300,200,100,x,2,图,3-11,最优解,0 100 200 300 400,x,1,x,2,=250=b,3,2x,l,+,x,2,=400=b,2,D,O,C,A,目标函数,x,l,+,x,2,=250=b,1,B,可行域,常数项继续减小，到可行域结构开始改变时的常数项值，就是这个约束条件常数项的下限值。即本例常数项,b,1,的下限为,250,。,图,3-12,0 100 200 300 400,x,1,400,300,200,100,x,2,可行域,A,x,2,x,l,+,x,2,=325=b,1,x,2,=250=b,3,2x,l,+,x,2,=400=b,2,最优解,目标函数,O,B,C,同样，常数项增大，到可行域结构开始改变时的常数项值，就是这个约束条件常数项的上限值。即本例常数项,b,1,的上限为,325,。,表,3-6,约束条件中常数项的取值范围,最下限,当前值,最高限,b,1,250,300,325,b,2,350,400,不限,b,3,200,250,300,用同样的方法可以求得,b,2,、,b,3,的上下限。如下表：,三、约束条件中常数项,a,mn,的灵敏度分析,a,mn,根据,m,n,的不同构成决策变量的系数矩阵，它代表着企业资源的分配。,资源分配系数矩阵的变化改变了可行域各边界线段的斜率，即完全且不规则地改变了可行域的形状。,资源分配系数矩阵的变化对最优解的影响太繁杂，也不具有共性，可视为完全改变了原有的数学模型，另外求解。,四、 百分之一百法则,当两个或更多的系数同时发生变化时的灵敏度分析,最低限,当前值,最高限,目标函数,系数,c,1,0,50,100,c,2,50,100,不限,常数项,b,1,250,300,325,b,2,350,400,不限,b,3,200,250,300,对于例,1,单个系数变化时目标函数系数和约束条件中常数项的可变化范围如下表 ，在此基础上进行多个系数同时变化的灵敏度分析。,1,、多个目标函数系数的百分之一百法则,允许增加量,目标函数的决策变量系数在上限范围内的最大增加量（最高限,-,当前值）。,引入两个述语：,允许减少量,目标函数的决策变量系数在下限范围内的最大减少量（当前值,-,最低限）。,目标函数决策变量系数的百分之一百法则：对于所有变化的目标函数决策变量系数，当其所有实际增加量与允许增加量的百分比和所有实际减少量与允许减少量的百分比之和不超过百分之一百时，最优解不变。即：,1,、多个目标函数系数的百分之一百法则,例,1,中，原来每件产品,I,和产品,的利润分别为,50,和,100,元，现在每件产品,I,和产品,的利润分别变为,70,和,80,元 ，对其进行灵敏度分析。,x,1,的系数,c,l,的允许增加量为：,100,50,50,x,2,的系数,c,2,的允许减少量也为：,100,50,50,百分一百法则：,（,70-50,）,/50+,（,100-80,）,/50=80 %,最优解不变，最优值为,23500,1,、多个目标函数系数的百分之一百法则,再如例,1,中，原来每件产品,I,和产品,的利润分别为,50,和,100,元，现在每件产品,I,和产品,的利润分别变为,70,和,70,元 ，对其进行灵敏度分析。,x,1,的系数,c,l,的允许增加量为：,100,50,50,x,2,的系数,c,2,的允许减少量也为：,100,50,50,百分一百法则：,（,70-50,）,/50+,（,100-70,）,/50=100 %,最优解不变，最优值为,21000,1,、多个目标函数系数的百分之一百法则,又如例,1,中，原来每件产品,I,和产品,的利润分别为,50,和,100,元，现在每件产品,I,和产品,的利润分别变为,70,和,69,元 ，对其进行灵敏度分析。,x,1,的系数,c,l,的允许增加量为：,100,50,50,x,2,的系数,c,2,的允许减少量也为：,100,50,50,百分一百法则：,（,70-50,）,/50+,（,100-69,）,/50=102 %,此时最解由,B,点变为,C,点，即,x,1,100,，,x,2,200,最优值为,20800,2,、多个约束条件中常数项同时变化,约束条件中常数项的百分之一百法则：对于所有变化的约束条件中的常数项，当其所有实际增加量与允许增加量的百分比和所有实际减少量与允许减少量的百分比之和不超过百分之一百时，则这些约束条件的对偶价格不变。即：,2,、多个约束条件中常数项同时变化,在例,1,中，设备台时数从,300,台时增加为,315,台时（上限,325,），而原料,A,从,400kg,减少到,390 kg,（下限,350,），原料,B,从,250 kg,减少到,240kg,（下限,200,）可得：,15/25+10/50+10/50=100%,没有超过,100%,，所以三个约束条件的对偶价格：,50,，,0,，,50,，都不变。但最优值变为：,27750,2,、多个约束条件中常数项同时变化,而若再增加一个台时，从,300,台时增加为,316,台时（上限,325,），而原料,A,从,400kg,减少到,390 kg,（下限,350,），原料,B,从,250 kg,减少到,240kg,（下限,200,），这样我们可以得到：,16/25+10/50+10/50=104%,对偶价格由原来的,50,，,0,，,50,改变为,0,，,25,，,75,百分之一百使用说明：,（,1,）当允许增,(,减,),量为无穷大时，则对于任一个增,(,减,),量，其允许增,(,减,),的百分比都看成零。这时灵敏度的分析结果就只取决于减,(,增,),量的百分比,(,即另一方向的变化,),。,（,2,）百分之一百法则是判断最优解或对偶价格是否发生变化的充分条件，但不是必要条件。也就是说，当其允许增,(,减,),的百分比之和不超过,(,小于,)100%,时，其最优解或对偶价格不变；但是当其允许增,(,减,),的百分比之和超过,(,大于,)100%,时，我们并不知道其最优解或对偶价格是否发生变化。,（,3,）百分之一百法则不能应用于目标函数决策变量系数和约束条件中常数项同时变化的情况，在这种情况下，只有重新求解。,（,4,）百分之一百法则不包括同步增加或同步减小的情况。,百分之一百使用说明：,五 目标函数中变量系数,c,i,的相差值分析,相差值,-,递减成本的绝对值,产品 资源,I,II,资源限制,设备,1,1,300,台时,原料,A,2,1,400kg,原料,B,0,1,300kg,例,3,将本章例,1,中,原料,B,的限制量改变为,300kg,，其它条件都不变,重新建立模型,重新求解。,五 目标函数中变量系数,c,i,的相差值分析,根据例,1,建模过程可得本问题的线性规划模型为：,max,z,50,x,l,+100,x,2,；,满足条件：,x,l,x,2,300,2,x,l,+,x,2,400,x,2,300,x,l,0,，,x,2,0,0 100 200 300 400,x,1,400,300,200,100,x,2,可行域,A,C,x,2,x,l,+,x,2,=300=b,1,x,2,=300,2x,l,+,x,2,=400=b,2,最优解,目标函数,O,B,五 目标函数中变量系数,c,i,的相差值分析,五 目标函数中变量系数,c,i,的相差值分析,所谓目标函数变量系数的相差值，是指最优解中为,0,的变量，在其它变量系数保持不变的情况下，使最优解中该变量的值不为,0,时，相应目标函数变量系数由现有值再改变的量。,五 目标函数中变量系数,c,i,的相差值分析,注：,1,、最优解不为,0,的变量，相差值必为,0,，反之不然，因为也有可能是外在约束所致；,2,、对于相差值不为,0,的变量系数：,当目标为求最大值时，当前值加上这个相差值，必等于该变量系数的上限值，且该变量系数无下限；此时其相应的变量值就会由原来为,0,变为非,0,。,当目标为求最小值时，当前值减去这个相差值，必等于该变量系数的下限值，且该变量系数无上限；此时其相应的变量值就会由原来为,0,变为非,0,。,3,、对于目标求最大值时，递减成本为负；对于目标求最小值时，递减成本为正。,用线性规划解决实际问题的概念总结,一、线性规划数学模型三要素：,决策变量、约束条件、目标函数,二、线性规划问题隐含的假定 ：,1,、比例性假定,-,决策变量变化引起的目标函数的改变量和决策变量的改变量成比例，同样，每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例。,2,、可加性假定,-,每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数贡献的总和。,3,、连续性假定,-,线性规划问题中的决策变量应取连续值。,4,、确定性假定,-,线性规划问题中的所有参数都是确定的参数。线性规划问题不包含随机因素。,用线性规划解决实际问题的概念总结,三、本节引入的基本概念,1,、线性规划问题,所谓线性规划，是指求线性函数在线性,(,不等式或等式,),约束下达最,(,小或大,),值的决策问题；,（,1,）线性规划的一般形式,-,只有绝对变量，没有松驰变量和剩余变量，约束条件为不等式；,（,2,）线性规划的标准形式,-,除了绝对变量，还有松驰变量和剩余变量，约束条件为等式。,用线性规划解决实际问题的概念总结,三、本节引入的基本概念,2,、基本术语,（,1,）决策变量,-,决策变量是指,决策问题,需要控制的因素一般称为决策变量（包括绝对变量、松驰变量和剩余变量）；,（,2,）目标函数（最大目标或最小目标）,-,用数学形式表示出来的,实际系统,的期望目标称为目标函数（价值体现）；,（,3,）约束条件,-,约束条件是指对决策变量限定一变化空间，是决策决策问题中关键因素受到的资源环境限制。,（,4,）可行域,-,由约束条件所围成的，符合所有约束条件要求的区域；,用线性规划解决实际问题的概念总结,三、本节引入的基本概念,2,、基本术语,（,5,）凸集合,-,凸多边形,-,凸多面体,凸多边形,-,区域内任意两点间的连线，都在区域内。或所多边形的内角都小于,。,（,6,）可行解,-,可行域中的任一点；,（,7,）基本可行解,-,或行域的凸多面体的顶点；,（,8,）初始基本可行解,-,初次迭代的基本可行解；,（,9,）线性规划的灵敏度分析,-,线性规划取得最优解后，再分析相关资源限制或所处条件发生变化时对最优解或对最优值的影响,。,用线性规划解决实际问题的概念总结,三、本节引入的基本概念,2,、基本术语,（,10,）相差值,-,所谓目标函数变量系数的相差值，是指最优解中为,0,的变量，在其它变量系数保持不变的情况下，使最优解中该变量的值不为,0,时，相应目标函数变量系数由现有值再改变的量。,（,11,）目标函数系数的取值范围,-,线性规划取得最优解后，目标函数系数中，在其它系数都不变前提下，某一系数的变化不会改变最优解的取值范围。,（,12,）常数项的取值范围,-,线性规划取得最优解后，在其它约束条件常数项都不变前提下，某一约束条件常数项的变化不会改变对偶价格的取值范围。,用线性规划解决实际问题的概念总结,三、本节引入的基本概念,2,、基本术语,（,13,）对偶价格,-,在约束条件中，增加一个单位的资源量而使最优目标函数值得到改进的数量，称为这个给条件的对偶价格；,（,14,）影子价格,-,约束条件中资源对目标极值的贡献，是资源的单位价格，反映资源在企业内部运用的贡献情况。或指资源改变时对最优收益产生的影响，所以又有人把它称为资源的,边际产出,或者资源的,机会成本,，它表示资源在最优,产品组合,时所具有的“潜在价值”或“贡献”。,一个讲贡献，一个讲大小。即：对于目标函数为最大时，对偶价格,=,影子价格。目标函数为最小时，对偶价格,=-,影子价格,用线性规划解决实际问题的概念总结,三、本节引入的基本概念,2,、基本术语,(15),百分一百法则,-,目标函数系数同时改变时使最优解不变的条件是各系数的增加量（减少量）与允许增加量（减少量）的比之和小于,100%,则最优解不变，否则是否改变无法肯定；约束条件常数项同时改变时使对偶价格不变的条件是各常数项的增加量（减少量）与允许增加量（减少量）的比之和不大于,100%,则对偶价格不变，否则是否改变无法肯定。,用线性规划解决实际问题的概念总结,三、本节引入的基本概念,3,、求解方法,（,1,）图解法,-,只能求解二个变量（二维）的线性规划问题。但概念可以扩展到多个变量（多维）的线性规划问题；,（,2,）单纯形法,-,利用线性代数逆矩阵多次迭代的方法对任何维线性规划问题求解；,（,3,）计算机软件求解,-,利用计算机软件多次迭代的方法对任何维线性规划问题求解；,用线性规划解决实际问题的概念总结,三、本节引入的基本概念,4,、线性规划问题解的特征,（,1,）唯一最优解,-,必在凸多面体的顶点上的一个点；,（,2,）无界解,-,没有有限范围的可行域；,（,3,）无穷多解,-,必在凸多面体的一个面或一个线上的点的集合；,（,4,）无可行解,-,没有可行域。,用线性规划解决实际问题的概念总结,三、本节引入的基本概念,5,、灵敏度分析,-,强调是微分效果的特征,c,i,-,价值系统的变化对最优解的影响。得到最优解不变情况下的各系数的取值范围、百分一百法则；,b,i,-,资源限制量（常数项）对最优解的影响。得到三个重要分析结果：,一个是对偶价格，就是单位资源的增加，对最优值的改进；,一个是对于各种资源，在对偶价格不变的前提下，可以确定资源量的可变化范围；,另一个是百分一百法则。,a,ij,-,资源分配矩阵（分配矩阵或条件系数矩阵），包括增加变量、增加约束条件、包括在现有变量个数的约束条件个数的前提下,a,ij,的变化，都使可行域发生较为复杂的变化，都需要做为新的线性规划问题重新求解。,