--第三章整数规划及其应用_1020.pptVIP

物品的容量及价格对照表 问题分析 变量—对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中 约束 包裹容量限制 必带物品限制 选带物品限制 目标函数—未带物品购买费用最小 模 型 S.t. 例-5： 假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02M3。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品价值最大： （1）所装物品不变； （2）如果选择旅行箱，则只能装载丙和丁两种物品。如下表所示。则载重量和体积的约束为： 物品 重量 （公斤/件） 体积 （m3/件） 价值 （元/件） 丙 丁 1.8 0.6 0.0015 0.002 4 3 S.t. 1.8X1+0.6 X2 ≤12 1.5X1+2X2 ≤20 X1≥0，X2≥0 且均取整数 解：此问题可以建立两个整数规划模型。 引入0—1变量（或称逻辑变量）yi,令 yi= 1，0采用第i种方式装载时，i=1,2 0, 不采用第i种方式装载时 i=1, 2 分别是采用背包及旅行箱装载。 （1）由于所装物品不变， 式 Max Z ＝4X1＋3X2 S.t. 1.2X1+0.8 X2 ≤10 2 X1+2.5X2 ≤25 X1≥0，X2≥0 且均取整数 上式 约束左边不变，整数规划数学模型为： S.t. 1.2X1+0.8 X2 ≤10 y1+12y2 （1） 2 X1+2.5X2 ≤25 y1 + 20y2 （2） y1+y2=1 （3） Xi≥0且均取整数; yi=0或1; i=1,2 Max Z ＝4X1＋3X2 （2）由于不同载体所装物品不一样，但物品价值相同，目标函数不变，数学模型为： S.t. 1.2X1+0.8 X2 ≤10 + My2 （1） 1.8X1+0.6X2 ≤12 + My1 （2） 2X1+2.5X2 ≤25 + My2 （3） 1.5X1+2X2 ≤20 + My1 （4） y1+y2=1 （5） X1， X2 ≥0且均取整数; y1 ，y2 =0或1 Max Z ＝4X1＋3X2 式中，M 为充分大的正数。 从上式可知： 当使用背包时（ y1=1，y2 =0 ），（2）式（4）式是多余的，即约束条件不起作用； 当使用旅行箱时（ y1=0，y2 =1 ），（1）式（3）式是多余的，即约束条件不起作用； 二、模型描述 整数规划问题就是要求决策变量取整数值的线性或非线性规划问题。 因此，整数规划分为： ⑴ 整数线性规划 (I LP) ⑵ 整数非线性规划 (IN LP) 两类。 按对变量的不同要求，还可将整数规划分为下述几种类型： ⑴ 纯整数规划 (Pure IP)或全整数规划( All IP)：要求全部变量都取整数值。 ⑵ 混合整数规划( Mixed IP)：只要求一部分变量取整数值 ⑶ 0-1整数规划（binary programming, 简记为 BIP）。要求全部或部分变量只取0或1值。 在管理与规划的大量问题中，常要求变量 满足取整条件,如： 生产计划中， 生产机器多少台（整数）； 人力资源管理中，招聘员工多少人（整数）； 运输问题中，从一个港口到另一个港口的集装箱调运数量（整数）。 另外，运作管理中的决策问题，如： 物流中心选址、 人员的工作指派、 设备购置和配置、 系统可靠性设计、 机床加工任务的均衡分派等等。 从技术角度看，这些问题的规划模型不同于前述的线性规划范畴，而属于一种新的类型——整数规划。 例如-6 挑选球队队员问题 2. 某篮球教练要从8名业余队员中挑选3名队员参加专业球队，使平均身高达到最高。队员的号码、身高及所擅长的位置如下表 所示。要求：中锋1人；后卫1人；前锋1人，但1号、3号与6号队员中必须保留1人给业余球队。 表2-27 队员身高 号码 身高（米） 位置 出