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

剩余变量X3=0,X4=125，松弛变X5=0最优解在C点。C点是第1、第3个约束条件对应的直线的交点，所以第1、第3个约束条件加入的剩余变量和松弛变量都为0，而第2个约束条件加入的剩余变量不为0（与C点还有一点距离）。第31页,共32页，星期六，2024年，5月感谢大家观看第32页,共32页，星期六，2024年，5月关于运筹学线性规划的标准形式数学模型如下第2页,共32页，星期六，2024年，5月改造方法（1）１、若目标函数求最小值，则在函数式前加上“－”号，转化为求最大值。转化后目标函数的最优解不变，最优值差一个符号。例：第3页,共32页，星期六，2024年，5月改造方法（2）2、若约束条件中，某些常数项bi为负数，则可先在约束条件等式或不等式两边乘上“-1”，使得bi≥0。例：第4页,共32页，星期六，2024年，5月改造方法（3）3、若约束条件不等式符号为“≤”，则在不等式左边加上一个非负变量（称为松弛变量），把不等式改为等式。例：新设一个非负变量第5页,共32页，星期六，2024年，5月改造方法（4）4、若约束条件不等式符号为“≥”，则在不等式左边减去一个非负变量（称为剩余变量），不等式改为等式。例：新设一个非负变量第6页,共32页，星期六，2024年，5月改造方法（5）5、若约束条件中，某些决策变量没有非负要求：①xj≤0，则令新变量xj’=-xj；②xj无符号限制，则可增设两个非负变量Vk≥0,Uk≥0，令原变量Xk=Vk-Uk，代入原线性规划问题的目标函数及约束条件。第7页,共32页，星期六，2024年，5月例1第8页,共32页，星期六，2024年，5月步骤1：minmax第9页,共32页，星期六，2024年，5月步骤2：bi0bi0第10页,共32页，星期六，2024年，5月步骤3：“≤”“=“引入新变量(松弛变量）x5≥0，将约束条件不等式变为等式。+松弛变量第11页,共32页，星期六，2024年，5月步骤4：“≥”“=”引入新变量（剩余变量）x6≥0，将约束条件不等式变为等式。—剩余变量第12页,共32页，星期六，2024年，5月步骤5：满足变量非负条件设新变量x7≥0，令x7=-x2，带入目标函数和约束条件中。设两个新变量x8≥0，x9≥0，令x4=x8-x9，带入目标函数和约束条件中。整理得：第13页,共32页，星期六，2024年，5月整理后数学模型为：第14页,共32页，星期六，2024年，5月松弛变量与剩余变量概念：松弛变量：在线性规划模型中，如果约束条件为“≤”，则在不等式左边加入一个非负变量，这个非负变量成为松弛变量。剩余变量：在线性规划模型中，如果约束条件为“≥”，则在不等式左边减去一个非负变量，这个非负变量成为剩余变量。第15页,共32页，星期六，2024年，5月理解松弛变量的实际含义例：某工厂在计划期内要安排甲、乙两种产品的生产。生产单位产品所需的设备台时及A、B两种原材料的消耗以及资源的限制如下表：工厂每生产一单位甲产品可获利50元，每生产一单位乙产品可获利100元，问工厂应分别生产多少单位产品甲和产品乙才能使得获利最多？甲产品乙产品资源限制设备11300台时原料A21400kg原料B01250kg第16页,共32页，星期六，2024年，5月建立数学模型：设甲、乙两种产品的产量分别为x1、x2：第17页,共32页，星期六，2024年，5月DBC图解法100200300400100200300400OA可行解域为OABCD最优解为B点（50，250）第18页,共32页，星期六，2024年，5月最优解的解释最优解x1=50，x2=250表示甲产品生产50个单位，乙产品生产250个单位时，获利最大。此时，资源利用情况为（代入约束条件）：设备台时利用量=1*50+1*250=300=资源限制量原料A使用量=2*50+1*250=350资源限制量400原料B使用量=1*250=250=资源限制量第19页,共32页，星期六，2024年，5月引入松弛变量x3,x4,x5，将数学模型标准化：∵最优解为x1=50,x2=250,∴代入标准化的数学模型，得松弛变量x3=0,x4=50,x5=0。第20页,共32页，星期六，2024年，5月松弛变量的含义松弛变量x3=0，表示按最优生产方案生产时，设备已充分利用，无多余的设备台时。松弛变量x4=50，表示按最优生产方案生产时，原料A未用完，还有50个单位。松弛变