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

第三节 线性规划的标准形式,为什么要转化为标准形式？标准形式的特点：1、目标函数求最大值（max）；（不一定）2、所有的约束条件均由等式表示（=）；3、所有的决策变量限于非负值（xj0）；4、每一个约束条件等式的右端常数均为非负值（bi0)。（不一定）,数学模型如下,改造方法（1）,、若目标函数求最小值，则在函数式前加上“”号，转化为求最大值。转化后目标函数的最优解不变，最优值差一个符号。例：,改造方法（2）,2、若约束条件中，某些常数项bi为负数，则可先在约束条件等式或不等式两边乘上“-1”，使得bi0。例：,改造方法（3）,3、若约束条件不等式符号为“”，则在不等式左边加上一个非负变量（称为松弛变量），把不等式改为等式。例：,新设一个非负变量,改造方法（4）,4、若约束条件不等式符号为“”，则在不等式左边减去一个非负变量（称为剩余变量），不等式改为等式。例：,新设一个非负变量,改造方法（5）,5、若约束条件中，某些决策变量没有非负要求：xj0，则令新变量xj=-xj；xj无符号限制，则可增设两个非负变量Vk0,Uk0，令原变量Xk=Vk-Uk，代入原线性规划问题的目标函数及约束条件。,例1,步骤1：min max,步骤2：bi0,步骤3：“”“=“,引入新变量(松弛变量）x50，将约束条件不等式变为等式。,+松弛变量,步骤4：“”“=”,引入新变量（剩余变量）x60，将约束条件不等式变为等式。,剩余变量,步骤5：满足变量非负条件,设新变量x70，令x7=-x2，带入目标函数和约束条件中。设两个新变量x80，x90，令x4=x8-x9，带入目标函数和约束条件中。整理得：,整理后数学模型为：,松弛变量与剩余变量,概念：松弛变量：在线性规划模型中，如果约束条件为“”，则在不等式左边加入一个非负变量，这个非负变量成为松弛变量。剩余变量：在线性规划模型中，如果约束条件为“”，则在不等式左边减去一个非负变量，这个非负变量成为剩余变量。,理解松弛变量的实际含义,例：某工厂在计划期内要安排甲、乙两种产品的生产。生产单位产品所需的设备台时及A、B两种原材料的消耗以及资源的限制如下表：工厂每生产一单位甲产品可获利50元，每生产一单位乙产品可获利100元，问工厂应分别生产多少单位产品甲和产品乙才能使得获利最多？,建立数学模型：,设甲、乙两种产品的产量分别为x1、x2：,D,B,C,图解法,100,200,300,400,100,200,300,400,O,A,可行解域为OABCD最优解为B点（50，250）,最优解的解释,最优解x1=50，x2=250表示甲产品生产50个单位，乙产品生产250个单位时，获利最大。此时，资源利用情况为（代入约束条件）：设备台时利用量=1*50+1*250=300=资源限制量原料A使用量=2*50+1*250=350资源限制量400原料B使用量=1*250=250=资源限制量,引入松弛变量x3,x4,x5，将数学模型标准化：,最优解为x1=50,x2=250,代入标准化的数学模型，得松弛变量x3=0,x4=50,x5=0。,松弛变量的含义,松弛变量x3=0，表示按最优生产方案生产时，设备已充分利用，无多余的设备台时。松弛变量x4=50，表示按最优生产方案生产时，原料A未用完，还有50个单位。松弛变量x5=0，表示按最优生产方案生产时，原料B已用完。所以，松弛变量不等于零，表示某种资源较充裕。,理解剩余变量的含义,例：某公司由于生产的需要，共需要A、B两种原料至少350吨（A、B两种原料有一定的替代性），其中原料A至少购进125吨。但由于A、B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨原料A需要2小时，加工每吨原料B需要1小时，而公司总共有600个加工时数，又知道每吨原料A的价格为2万元，每吨原料B的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A、B两种原料，使得购进成本最低？,建立数学模型：,设x1，x2分别为原料A、B的购进量：,将数学模型标准化,引入剩余变量x3，x4，及松弛变量x5：,图解法,100,200,300,400,500,600,100,200,300,400,500,B,A,C,可行解域为ABC最优解为C点（250，100）,最优解的解释,最优解x1=250，x2=100表示最佳购买方案是原料A购进250吨，原料B购进100吨。代入约束条件分析：总购进量=250+100=350吨=最低要求原料A购进量=250最低要求125原料加工时数=2*250+100=600=最高限制进一步计算剩余变量和松弛变量:X3=0，表示正好达到最低要求；X4=125，表示超出最低要求，多购进125吨；X5=0，表示工时数被全部利用。,关于松弛变量和剩余变量的信息也可以从图解法中获得。,另外，,D,B,C,松弛变量x3=0,x4=50,x5=0,100,200,300,400,100,200,300,400,O,A,可行解域为OABCD最优解为B点（50，250）,1,3,2,松弛变量x3=0,x4=50,x5=0,最优解在B点。B点是第1、第3个约束条件对应的直线的交点，所以第1、第3个约束条件加入的松弛变量为0，而第2个约束条件加入的松弛变量不为0（与B点还有一点距离）。,剩余变量X3=0,X4=125，松弛变X5=0,100,200,300,400,500,600,100,200,300,400,500,B,A,C,可行解域为ABC最优解为C点（250，100）,1,2,3,剩余变量X3=0,X4=125，松弛变X5=0,最优解在C点。C 点是第1、第3个约束条件对应的直线的交点，所以第1、第3个约束条件加入的剩余变量和松弛变量都为0，而第2个约束条件加入的剩余变量不为0（与C点还有一点距离）。,思考题与练习题,