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

第三节线性规划的标准形式 为什么要转化为标准形式 标准形式的特点 1 目标函数求最大值 max 不一定 2 所有的约束条件均由等式表示 3 所有的决策变量限于非负值 xj 0 4 每一个约束条件等式的右端常数均为非负值 bi 0 不一定 1 数学模型如下 2 改造方法 1 若目标函数求最小值 则在函数式前加上 号 转化为求最大值 转化后目标函数的最优解不变 最优值差一个符号 例 3 改造方法 2 2 若约束条件中 某些常数项bi为负数 则可先在约束条件等式或不等式两边乘上 1 使得bi 0 例 4 改造方法 3 3 若约束条件不等式符号为 则在不等式左边加上一个非负变量 称为松弛变量 把不等式改为等式 例 新设一个非负变量 5 改造方法 4 4 若约束条件不等式符号为 则在不等式左边减去一个非负变量 称为剩余变量 不等式改为等式 例 新设一个非负变量 6 改造方法 5 5 若约束条件中 某些决策变量没有非负要求 xj 0 则令新变量xj xj xj无符号限制 则可增设两个非负变量Vk 0 Uk 0 令原变量Xk Vk Uk 代入原线性规划问题的目标函数及约束条件 7 例1 8 步骤1 minmax 9 步骤2 bi0 10 步骤3 引入新变量 松弛变量 x5 0 将约束条件不等式变为等式 松弛变量 11 步骤4 引入新变量 剩余变量 x6 0 将约束条件不等式变为等式 剩余变量 12 步骤5 满足变量非负条件 设新变量x7 0 令x7 x2 带入目标函数和约束条件中 设两个新变量x8 0 x9 0 令x4 x8 x9 带入目标函数和约束条件中 整理得 13 整理后数学模型为 14 松弛变量与剩余变量 概念 松弛变量 在线性规划模型中 如果约束条件为 则在不等式左边加入一个非负变量 这个非负变量成为松弛变量 剩余变量 在线性规划模型中 如果约束条件为 则在不等式左边减去一个非负变量 这个非负变量成为剩余变量 15 理解松弛变量的实际含义 例 某工厂在计划期内要安排甲 乙两种产品的生产 生产单位产品所需的设备台时及A B两种原材料的消耗以及资源的限制如下表 工厂每生产一单位甲产品可获利50元 每生产一单位乙产品可获利100元 问工厂应分别生产多少单位产品甲和产品乙才能使得获利最多 16 建立数学模型 设甲 乙两种产品的产量分别为x1 x2 17 D B C 图解法 100 200 300 400 100 200 300 400 O A 可行解域为OABCD最优解为B点 50 250 18 最优解的解释 最优解x1 50 x2 250表示甲产品生产50个单位 乙产品生产250个单位时 获利最大 此时 资源利用情况为 代入约束条件 设备台时利用量 1 50 1 250 300 资源限制量原料A使用量 2 50 1 250 350 资源限制量400原料B使用量 1 250 250 资源限制量 19 引入松弛变量x3 x4 x5 将数学模型标准化 最优解为x1 50 x2 250 代入标准化的数学模型 得松弛变量x3 0 x4 50 x5 0 20 松弛变量的含义 松弛变量x3 0 表示按最优生产方案生产时 设备已充分利用 无多余的设备台时 松弛变量x4 50 表示按最优生产方案生产时 原料A未用完 还有50个单位 松弛变量x5 0 表示按最优生产方案生产时 原料B已用完 所以 松弛变量不等于零 表示某种资源较充裕 21 理解剩余变量的含义 例 某公司由于生产的需要 共需要A B两种原料至少350吨 A B两种原料有一定的替代性 其中原料A至少购进125吨 但由于A B两种原料的规格不同 各自所需的加工时间也是不同的 加工每吨原料A需要2小时 加工每吨原料B需要1小时 而公司总共有600个加工时数 又知道每吨原料A的价格为2万元 每吨原料B的价格为3万元 试问在满足生产需要的前提下 在公司加工能力的范围内 如何购买A B两种原料 使得购进成本最低 22 建立数学模型 设x1 x2分别为原料A B的购进量 23 将数学模型标准化 引入剩余变量x3 x4 及松弛变量x5 24 图解法 100 200 300 400 500 600 100 200 300 400 500 B A C 可行解域为ABC最优解为C点 250 100 25 最优解的解释 最优解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 表示工时数被全部利用 26 关于松弛变量和剩余变量的信息也可以从图解法中获得 另外 27 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 28 松弛变量x3 0 x4 50 x5 0 最优解在B点 B点是第1 第3个约束条件对应的直线的交点 所以第1 第3个约束条件加入的松弛变量为0 而第2个约束条件加入的松弛变量不为0 与B点还有一点距离 29 剩余变量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 30 剩