第四节 0-1规划

3.40-1规划0-1规划的一般形式为1maxnjjjScx1(1,,)nijjijaxbimL01(1,,)jxjnL或有的线性规划问题要求决策变量仅取0或l两个值,称为0-1规划问题.0-1规划的典型例子：背包问题一个旅行者出门旅行之前，要往背包里装一些必备的出行物品．他最多只能携带b公斤的物品，而每件物品都必须整件携带．于是他给每件物品规定了一个价值，以表示其有用程度．假设共有m件物品，第i件物品重公斤，其价值为则问题为：在总重量不超过b公斤的条件下，怎样携带物品可使总价值最大？ia.ic引进变量,使得1,0,ix当携带第i件物品时ix当不携带第i件物品时则线性规划模型为1maxniiiScx1niiiaxb01ix或另例某公司拟在市东、西、南三区建门市部，拟议中有七个位置Ai可供选择，规定1、在东区，A1,A2,A3中至多选两个；2、在西区，A4,A5中至少选一个；3、在南区，A6,A7中至少选一个。若选用Ai，则设备投资估价bi元，每年可获利ci元．三个区投资总额为B元，则选择哪几个位置可使年利润最大？解令10ix，选择Ai，不选择Ai或71711234567max2.1101iiiiiiiZcxbxBxxxstxxxxx该问题的数学模型为如下的0-1规划问题：求解0-1规划的方法枚举(穷举)法显枚举法：隐枚举法：将变量的可能取值的全部组合一一列举进行计算并比较找出最优值将变量的可能取值的部分组合一一列举进行计算并比较找出最优值例求解0-1规划问题123max42+3Sxxx123232xxx1234+4xxx121xx123,,01xxx或解的所有可能取值有8种：123(,,)xxx(0,0,0),(0,0,1),(0,1,0),(0,1,1)(1,0,0),(1,0,1),(1,1,0),(1,1,1)3SSxxx12342+33过滤性条件例求解0-1规划问题123xxx000001010011100101110111目标函数值S是否≥下界是否满足约束最优值下界(1)(2)(3)03214725√√√√×××√√√√√√√√××34显枚举法123max42+3Sxxx123232xxx1234+4xxx121xx123,,01xxx或×例求解0-1规划问题231xxx000001010011100101110111目标函数值S是否≥下界是否满足约束最优值下界(1)(2)(3)03214725√√√×××√×√√√√√√√×√×04隐枚举法123max42+3Sxxx123232xxx1234+4xxx121xx123,,01xxx或请练习：100页习题三4.(1)(2)答案：(1)(1,0,1),8XS(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变量，使1234357xyyyy1234,,,01yyyy或12341yyyy1234,,,yyyy10)1(8)1(552211或yMyxyMxMyxyMx（2）若x1≤5，则x2≥0，否则x2≤8;引入0-1变量y，并设M是充分大的数，则3,2,1102204210646321321221121jyyyyMyxxMyxxMyxxj，或3,2,1101)1(2042)1(1064)1(6321321221121jyyyyMyxxMyxxMyxxj，或或如果要求至少一个条件满足，第1个式子改为，第2个式子改为。2321yyy1321yyy（3）x1+x2≤6或4x1+6x2≥10或2x1+4x2≤20.引入0-1变量并设M是充分大的数，则123,,,yyy一般地，若要从p个约束条件1(1,2,,)nijjijaxbip中恰好选择q个，可以引入p个0-1变量：0,1,iy若选择第i个约束条件若不选第i个约束条件11nijjiijpiiaxbMyypq则可得符合要求的约束条件组：保证有p-q个1从而有q个0M是充分大的数2、某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、获利及受限情况如下表所示货物船运体积（米3/箱）车运体积（米3/箱）重量（百斤/箱）利润甲乙7354252010限制452413问：甲，乙各托运多少箱可获利最大？分析：若只考虑一种方式，则模型容易建立；若二者同时考虑，因其是互相排斥的，为了统一在一个问题中，引入0-1变量y，令y不必出现在目标函数中.0,1,y采取车运方式采取船运方式1212121212max201054247345(1).2513,,01ZxxxxyMxxyMstxxxxZy或解设甲乙分别托运和箱可获利最大，12xx引入0-1变量y，并设M是充分大的数，则线性规划模型为3、企业计划生产4000件某产品，该产品可采取自己加工或外协加工两种方式。已知数据如下表所示，怎样安排产品的加工可使总成本最小。自己加工外协加工Ⅰ外协加工Ⅱ固定成本(元)变动成本(元/件)最大加工数(件)50080060085715002000不限解设为采用第种方式生产的产品数量,引入0-1变量(1,2,3):jyj0,1,jy采用第j种加工方式不采用j第种加工方式，即时；0jx，即时；0jx(1,2,3)jxjj则线性规划模型为112233min(5008)(8005)(6007)Zyxyxyx1234000xxx1101500xy2202000xy123,,xxx123,,01yyy为整数或330xMy表达与的关系iixy则线性规划模型为112233min(5008)(8005)(6007)Zyxyxyx1234000xxx11500x22000x123,,0xxx123,,01yyy为整数或0jjxMy0jx0jjMyx1jy0jx0jMyminZ0jy