《运筹学教程》胡云权 第五版 第三章 整数规划

《《运筹学教程》胡云权 第五版 第三章 整数规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章整数规划学习目标整数规划数学模型分枝定界法割平面法0－1规划指派问题整数规划数学模型部分或全部决策变量是整数的规划，称为整数规划。若模型是线性的，称为整数线性规划。本章只讨论整数线性规划。纯整数规划：全部决策变量取整数值，又称全整数规划；混合整数规划：部分决策变量取整数值；0-1规划：决策变量只能取0或1。例如1.变量是人数、机器设备台数或产品件数等都要求是整数；2.对某一个项目要不要投资的决策问题，可选用一个逻辑变量x，当x=1表示投资，x=0表示不投资；3.人员的合理安排问题，当变量xij=1表

2、示安排第i人去做j工作，xij=0表示不安排第i人去做j工作。逻辑变量也是只允许取整数值的一类变量。整数规划数学模型【例1】企业计划生产2000件某种产品，该种产品可利用Ａ、Ｂ、Ｃ设备中的任意一种加工。已知每种设备的生产准备结束费用、生产该产品时的单件成本以及每种设备限定的最大加工数量（件）如下表所示，试建立总成本最小的数学模型。1、生产安排问题整数规划数学模型设备生产准备结束费（元）生产成本（元/件）限定最大加工数（件）Ａ１００１０６００Ｂ３００２８００Ｃ２００５１２００变量设xj表示在第j（j=1,2

3、,3）种设备上加工的产品数量，其生产费用为：式中Kj是同产量无关的生产准备费用（即固定费用），cj是单位产品成本。设0－1变量yj，令1、生产安排问题整数规划数学模型当在第j种设备上加工，即xj>0时当不在第j种设备上加工，即xj=0时目标函数约束条件1、生产安排问题整数规划数学模型式中是一个特殊的约束条件，显然当xj>0时，yj=1,当xj＝0时，为使Z极小化，只有yj=0才有意义。整数规划数学模型2、投资组合问题证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润。项目投资：财团或银

4、行把资金投入到若干项目中以获得中长期的收益最大。【例2】选择投资场所,使收益最大？Ai投资Bi元，收益Ci元，总投资≤B.【解】设xix1+x2+x3≤2x4+x5≥1x6+x7≥1B1x1+B2x2+…+B7x7≤BA6A7A4A5A3A2A1最多选2个最少选1个最少选1个南区西区东区求解0-1规划的隐枚举法maxz=C1x1+C2x2+…+C7x71Ai选中0Ai落选=2、投资组合问题【例3】某财团有万元的资金，经出其考察选中个投资项目，每个项目只能投资一次。其中第个项目需投资金额为万元，预计5年后获

5、利（）万元，问应如何选择项目使得5年后总收益最大？整数规划数学模型2、投资组合问题变量—每个项目是否投资约束—总金额不超过限制目标—总收益最大整数规划数学模型3、背包问题邮递包裹：把形状可变的包裹用尽量少的车辆运走旅行背包：容量一定的背包里装尽可能的多的物品【例4】某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有1

6、0件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。整数规划数学模型物品12345678910体积200350500430320120700420250100价格15451007050752009020303、背包问题变量：对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包

7、裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中。整数规划数学模型3、背包问题整数规划数学模型3、背包问题约束包裹容量限制必带物品限制选带物品限制目标函数—未带物品购买费用最小整数规划数学模型2、背包问题【例5】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如下表所示。问两种物品各装多少件，所装物品的总价值最大？整数规划数学模型解的特点物品重量（公斤/件）体积（立方米/件）价值（元/件）甲1

8、.20.0024乙0.80.00253【解】设甲、乙两种物品各装x1、x2件，则数学模型为：不考虑x1、x2取整数的约束，称为上述规划的松弛问题，可行域如图；B为最优解：X＝(3.57，7.14)，Z＝35.7。由于x1、x2必须取整数值，可行解集只是图中可行域内的那些整数点；凑整法：比较四种组合，但（4，7）、（4，8）（3，8）都不是可行解，（3，7）虽属可行解，但代入目标函数得Z=33；实际问题的最优解是（5，5），Z=