第四节-0-1规划.ppt

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