运筹学线性规划的标准形式.pptx

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,第三节 线性规划的标准形式,为什么要转化为标准形式？,标准形式的特点：,1,、目标函数求最大值（,max,）；,（不一定）,2,、所有的约束条件均由等式表示（,=,）；,3,、所有的决策变量限于非负值（,x,j,0,）；,4,、每一个约束条件等式的右端常数均为非负值（,b,i,0),。,（不一定）,数学模型如下,改造方法（,1,）,、若目标函数求最小值，则在函数式前加上,“,”,号，转化为求最大值。转化后目标函数的,最优解不变，最优值差一个符号,。,例：,改造方法（,2,）,2,、若约束条件中，某些常数项,bi,为负数，则可先在约束条件等式或不等式两边乘上,“,-1,”,，使得,bi,0,。,例：,改造方法（,3,）,3,、若约束条件不等式符号为,“,”,，则在不等式左边加上一个非负变量（称为,松弛变量,），把不等式改为等式。,例：,新设一个非负变量,改造方法（,4,）,4,、若约束条件不等式符号为,“,”,，则在不等式左边减去一个非负变量（称为,剩余变量,），不等式改为等式。,例：,新设一个非负变量,改造方法（,5,）,5,、若约束条件中，某些决策变量没有非负要求：,x,j,0,，则令新变量,x,j,=-x,j,；,x,j,无符号限制，,则可增设两个非负变量,V,k,0,U,k,0,，令原变量,X,k,=V,k,-U,k,，代入原线性规划问题的目标函数及约束条件。,例,1,步骤,1,：,min max,步骤,2,：,b,i,0,步骤,3,：,“,”,“,=,“,引入新变量,(,松弛变量）,x,5,0,，将约束条件不等式变为等式。,+,松弛变量,步骤,4,：,“,”,“,=,”,引入新变量（剩余变量）,x,6,0,，将约束条件不等式变为等式。,剩余变量,步骤,5,：满足变量非负条件,设新变量,x,7,0,，令,x,7,=-x,2,，带入目标函数和约束条件中。,设两个新变量,x,8,0,，,x,9,0,，,令,x,4,=x,8,-x,9,，带入目标函数和约束条件中。,整理得,：,整理后数学模型为：,松弛变量与剩余变量,概念：,松弛变量：在线性规划模型中，如果约束条件为,“,”，则在不等式左边加入一个非负变量，这个非负变量成为松弛变量。,剩余变量：在线性规划模型中，如果约束条件为,“,”，则在不等式左边减去一个非负变量，这个非负变量成为剩余变量。,理解松弛变量的实际含义,例：某工厂在计划期内要安排甲、乙两种产品的生产。生产单位产品所需的设备台时及,A,、,B,两种原材料的消耗以及资源的限制如下表：,工厂每生产一单位甲产品可获利,50,元，每生产一单位乙产品可获利,100,元，问工厂应分别生产多少单位产品甲和产品乙才能使得获利最多？,甲产品,乙产品,资源限制,设备,1,1,300,台时,原料,A,2,1,400kg,原料,B,0,1,250kg,建立数学模型：,设甲、乙两种产品的产量分别为,x,1,、,x,2,：,D,B,C,图解法,100,200,300,400,100,200,300,400,O,A,可行解域为,OABCD,最优解为,B,点（,50,，,250,）,最优解的解释,最优解,x,1,=50,，,x,2,=250,表示甲产品生产,50,个单位，乙产品生产,250,个单位时，获利最大。,此时，,资源利用情况,为（代入约束条件）：,设备台时利用量,=1*50+1*250=300,=,资源限制量,原料,A,使用量,=2*50+1*250=350,最低要求,125,原料加工时数,=2*250+100=600,=,最高限制,进一步计算剩余变量和松弛变量,:,X,3,=0,，表示正好达到最低要求；,X,4,=125,，表示超出最低要求，多购进,125,吨；,X,5,=0,，表示工时数被全部利用。,关于松弛变量和剩余变量的信息也可以从图解法中获得。,另外，,D,B,C,松弛变量,x,3,=0,x,4,=50,x,5,=0,100,200,300,400,100,200,300,400,O,A,可行解域为,OABCD,最优解为,B,点（,50,，,250,）,1,3,2,松弛变量,x,3,=0,x,4,=50,x,5,=0,最优解在,B,点。,B,点是第,1,、第,3,个约束条件对应的直线的交点，所以第,1,、第,3,个约束条件加入的松弛变量为,0,，而第,2,个约束条件加入的松弛变量不为,0,（与,B,点还有一点距离）。,剩余变量,X,3,=0,X,4,=125,，松弛变,X,5,=0,100,200,300,400,500,600,100,200,300,400,500,B,A,C,可行解域为,ABC,最优解为,C,点（,250,，,100,）,1,2,3,剩余变量,X,3,=0,X,4,=125,，松弛变,X,5,=0,最优解在,C,点。,C,点是第,1,、第,3,个约束条件对应的直线的交点，所以第,1,、第,3,个约束条件加入的剩余变量和松弛变量都为,0,，而第,2,个约束条件加入的剩余变量不为,0,（与,C,点还有一点距离）。,思考题与练习题,