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

《运筹学线性规划的标准形式课件.ppt》由会员分享，可在线阅读，更多相关《运筹学线性规划的标准形式课件.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于运筹学线性规划的标准形式现在学习的是第1页，共32页数学模型如下 现在学习的是第2页，共32页改造方法（改造方法（1）n、若目标函数求最小值，则在函数式前加上“”号，转化为求最大值。转化后目标函数的最优解不变，最优值最优解不变，最优值差一个符号差一个符号。n例：现在学习的是第3页，共32页改造方法（改造方法（2）n2、若约束条件中，某些常数项bi为负数，则可先在约束条件等式或不等式两边乘上“-1”，使得bi0。n例：现在学习的是第4页，共32页改造方法（改造方法（3）n3、若约束条件不等式符号为“”，则在不等式左边加上一个非负变量（称为松弛变量松弛变量），把不等式改为等式。n例：新设一个非

2、负变量现在学习的是第5页，共32页改造方法（改造方法（4）n4、若约束条件不等式符号为“”，则在不等式左边减去一个非负变量（称为剩余变量剩余变量），不等式改为等式。n例：新设一个非负变量现在学习的是第6页，共32页改造方法（改造方法（5）n5、若约束条件中，某些决策变量没有非负要求：nxj0，则令新变量xj=-xj；nxj无符号限制，则可增设两个非负变量Vk0,Uk0，令原变量Xk=Vk-Uk，代入原线性规划问题的目标函数及约束条件。现在学习的是第7页，共32页例1现在学习的是第8页，共32页步骤1：min max现在学习的是第9页，共32页步骤2：bi0现在学习的是第10页，共32页步骤3：

3、“”“=“n引入新变量(松弛变量）x50，将约束条件不等式变为等式。+松弛变量松弛变量现在学习的是第11页，共32页步骤4：“”“=”n引入新变量（剩余变量）x60，将约束条件不等式变为等式。剩余变量剩余变量现在学习的是第12页，共32页步骤5：满足变量非负条件n设新变量x70，令x7=-x2，带入目标函数和约束条件中。n设两个新变量x80，x90，令x4=x8-x9，带入目标函数和约束条件中。整理得整理得：现在学习的是第13页，共32页整理后数学模型为：现在学习的是第14页，共32页松弛变量与剩余变量松弛变量与剩余变量n概念：n松弛变量：在线性规划模型中，如果约束条件为“”，则在不等式左边加

4、入一个非负变量，这个非负变量成为松弛变量。n剩余变量：在线性规划模型中，如果约束条件为“”，则在不等式左边减去一个非负变量，这个非负变量成为剩余变量。现在学习的是第15页，共32页理解松弛变量的实际含义n例：某工厂在计划期内要安排甲、乙两种产品的生产。生产单位产品所需的设备台时及A、B两种原材料的消耗以及资源的限制如下表：n工厂每生产一单位甲产品可获利50元，每生产一单位乙产品可获利100元，问工厂应分别生产多少单位产品甲和产品乙才能使得获利最多？甲产品乙产品资源限制设备11300台时原料A21400kg原料B01250kg现在学习的是第16页，共32页建立数学模型：n设甲、乙两种产品的产量分

5、别为x1、x2：现在学习的是第17页，共32页DBC图解法100200300400100200300400OA可行解域为OABCD最优解为B点（50，250）现在学习的是第18页，共32页最优解的解释n最优解x1=50，x2=250表示甲产品生产50个单位，乙产品生产250个单位时，获利最大。n此时，资源利用情况资源利用情况为（代入约束条件）：n设备台时利用量=1*50+1*250=300=资源限制量n原料A使用量=2*50+1*250=350最低要求125n原料加工时数=2*250+100=600=最高限制n进一步计算剩余变量和松弛变量:nX3=0，表示正好达到最低要求；nX4=125，表示

6、超出最低要求，多购进125吨；nX5=0，表示工时数被全部利用。现在学习的是第26页，共32页n关于松弛变量和剩余变量的信息也可以从图解法中获得。另外，现在学习的是第27页，共32页DBC松弛变量x3=0,x4=50,x5=0100200300400100200300400OA可行解域为OABCD最优解为B点（50，250）132现在学习的是第28页，共32页松弛变量x3=0,x4=50,x5=0n最优解在B点。B点是第1、第3个约束条件对应的直线的交点，所以第1、第3个约束条件加入的松弛变量为0，而第2个约束条件加入的松弛变量不为0（与B点还有一点距离）。现在学习的是第29页，共32页剩余变量X3=0,X4=125，松弛变X5=0100200300400500600100200300400500BAC可行解域为ABC最优解为C点（250，100）123现在学习的是第30页，共32页剩余变量X3=0,X4=125，松弛变X5=0n最优解在C点。C 点是第1、第3个约束条件对应的直线的交点，所以第1、第3个约束条件加入的剩余变量和松弛变量都为0，而第2个约束条件加入的剩余变量不为0（与C点还有一点距离）。现在学习的是第31页，共32页感感谢谢大大家家观观看看现在学习的是第32页，共32页