第四节 0-1规划.ppt

3.4 0-1规划,0-1规划的一般形式为,,或,有的线性规划问题要求决策变量仅取0或l两个值,称为0-1规划问题.,0-1规划的典型例子：背包问题,一个旅行者出门旅行之前，要往背包里装一些必备的出行物品．,他最多只能携带b公斤的物品，而每件物品都必须整件携带．,于是他给每件物品规定了一个价值，以表示其有用程度．,假设共有m件物品，第i 件物品重 公斤，其价值为,则问题为：在总重量不超过b公斤的条件下，怎样携带物品可使总价值最大？,引进变量 ,使得,当携带第i 件物品时,当不携带第i 件物品时,则线性规划模型为,或,,另例 某公司拟在市东、西、南三区建门市 部，拟议中有七个位置 Ai 可供选择，规定,1、在东区，A1 , A2 , A3 中至多选两个； 2、在西区，A4 , A5 中至少选一个； 3、在南区，A6 , A7 中至少选一个若选用Ai ，则设备投资估价 bi 元，每年可获利 ci 元．三个区投资总额为 B 元，则选择哪几个位置可使年利润最大？,解,，选择 Ai,，不选择 Ai,该问题的数学模型为如下的0-1规划问题：,求解0-1规划的方法,枚举(穷举)法,显枚举法：,隐枚举法：,将变量的可能取值的全部组合一一列举进行计算并比较找出最优值,将变量的可能取值的部分组合一一列举进行计算并比较找出最优值,例 求解0-1 规划问题,,解 的所有可能取值有8种：,,过滤性条件,,例 求解0-1 规划问题,√,√,√,√,×,×,×,√,√,√,√,√,√,√,√,×,×,显枚举法,,×,,例 求解0-1 规划问题,√,√,√,×,×,×,√,×,√,√,√,√,√,√,√,×,√,×,隐枚举法,,请练习： 100页 习题三 4.(1)(2),答案：,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变量 ，使,（2）若 x1≤5，则 x2≥0，否则 x2≤8;,引入0-1变量y，并设M是充分大的数，则,或,如果要求至少一个条件满足，第1个式子改为 ，第2个式子改为 。

3）x1+x2≤6 或 4x1+6x2≥10 或 2x1+4x2≤20.,引入0-1变量 并设M是充分大的数，则,一般地，若要从 p 个约束条件,中恰好选择 q 个，,可以引入p个0-1变量：,若选择第i 个约束条件,若不选第i 个约束条件,则可得符合要求的约束条件组：,保证有 p-q 个1 从而有q个0,,M是充分大的数,,2、某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、获利及受限情况如下表所示,问：甲，乙各托运多少箱可获利最大？,分析：若只考虑一种方式，则模型容易建立； 若二者同时考虑，因其是互相排斥的，为了统一在一个问题中，引入0-1变量y，令,y不必出现在目标函数中.,采取车运方式,采取船运方式,解 设甲乙分别托运 和 箱可获利最大，,引入0-1变量y，并设M是充分大的数，则线性规划模型为,3、企业计划生产4000件某产品，该产品可采取自己加工或外协加工两种方式已知数据如下表所示，怎样安排产品的加工可使总成本最小自己加工,外协加工Ⅰ,外协加工Ⅱ,固定成本(元),变动成本(元/件),最大加 工数(件),,,500,800,600,8,5,7,1500,2000,不限,解 设 为采用第 种方式生产的产品数量,,引入0-1变量,采用 第j 种加工方式,不采用j 第种加工方式,，即 时；,，即 时；,则线性规划模型为,为整数,或,表达 与 的关系,则线性规划模型为,为整数,或,,。