《第四节 0-1规划PPT幻灯片课件》由会员分享，可在线阅读，更多相关《第四节 0-1规划PPT幻灯片课件（22页珍藏版）》请在金锄头文库上搜索。
1、3 40 1规划 0 1规划的一般形式为 或 有的线性规划问题要求决策变量仅取0或l两个值 称为0 1规划问题 1 0 1规划的典型例子 背包问题 一个旅行者出门旅行之前 要往背包里装一些必备的出行物品 他最多只能携带b公斤的物品 而每件物品都必须整件携带 于是他给每件物品规定了一个价值 以表示其有用程度 假设共有m件物品 第i件物品重公斤 其价值为 则问题为 在总重量不超过b公斤的条件下 怎样携带物品可使总价值最大 2 引进变量 使得 当携带第i件物品时 当不携带第i件物品时 则线性规划模型为 或 3 另例某公司拟在市东 西 南三区建门市部 拟议中有七个位置Ai可供选择 规定 1 在东区 A
2、1 A2 A3中至多选两个 2 在西区 A4 A5中至少选一个 3 在南区 A6 A7中至少选一个 若选用Ai 则设备投资估价bi元 每年可获利ci元 三个区投资总额为B元 则选择哪几个位置可使年利润最大 解 选择Ai 不选择Ai 4 该问题的数学模型为如下的0 1规划问题 5 求解0 1规划的方法 枚举 穷举 法 显枚举法 隐枚举法 将变量的可能取值的全部组合一一列举进行计算并比较找出最优值 将变量的可能取值的部分组合一一列举进行计算并比较找出最优值 6 例求解0 1规划问题 解的所有可能取值有8种 过滤性条件 7 例求解0 1规划问题 显枚举法 8 例求解0 1规划问题 隐枚举法 9 请练
3、习 100页习题三4 1 2 答案 10 1 引入0 1变量将下列条件用一个式子表达 1 x取值0 1 3 5 7 2 若x1 5 则x2 0 否则x2 8 3 x1 x2 6或4x1 6x2 10或2x1 4x2 20 另例 解 1 引入0 1变量 使 11 2 若x1 5 则x2 0 否则x2 8 引入0 1变量y 并设M是充分大的数 则 12 或 如果要求至少一个条件满足 第1个式子改为 第2个式子改为 3 x1 x2 6或4x1 6x2 10或2x1 4x2 20 引入0 1变量并设M是充分大的数 则 13 一般地 若要从p个约束条件 中恰好选择q个 可以引入p个0 1变量 若选择第i
4、个约束条件 若不选第i个约束条件 14 则可得符合要求的约束条件组 保证有p q个1从而有q个0 M是充分大的数 15 2 某厂拟用集装箱托运甲乙两种货物 每箱的体积 重量 获利及受限情况如下表所示 问 甲 乙各托运多少箱可获利最大 16 分析 若只考虑一种方式 则模型容易建立 若二者同时考虑 因其是互相排斥的 为了统一在一个问题中 引入0 1变量y 令 y不必出现在目标函数中 采取车运方式 采取船运方式 17 解设甲乙分别托运和箱可获利最大 引入0 1变量y 并设M是充分大的数 则线性规划模型为 18 3 企业计划生产4000件某产品 该产品可采取自己加工或外协加工两种方式 已知数据如下表所示 怎样安排产品的加工可使总成本最小 自己加工 外协加工 外协加工 固定成本 元 变动成本 元 件 最大加工数 件 500 800 600 8 5 7 1500 2000 不限 19 解设为采用第种方式生产的产品数量 引入0 1变量 采用第j种加工方式 不采用j第种加工方式 即时 即时 20 则线性规划模型为 为整数 或 表达与的关系 21 则线性规划模型为 为整数 或 22
