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

《《运筹学教程》胡云权 第五版 第三章 整数规划》由会员分享，可在线阅读，更多相关《《运筹学教程》胡云权 第五版 第三章 整数规划（65页珍藏版）》请在金锄头文库上搜索。

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

2、作。逻辑变量也是只允许取整数值的一类变量。整数规划数学模型【例1】企业计划生产2000件某种产品，该种产品可利用、 设备中的任意一种加工。已知每种设备的生产准备结束费用、生 产该产品时的单件成本以及每种设备限定的最大加工数量（件）如 下表所示，试建立总成本最小的数学模型。1、生产安排问题整数规划数学模型设备生产准备结束费（元 ）生产成本（元/件 ）限定最大加工数（件）n 变量 设xj表示在第 j（j=1,2,3）种设备上加工的产品数量， 其生产费用为：式中Kj是同产量无关的生产准备费用（即固定费用），cj是单位产 品成本。设01变量yj，令1、生产安排问题整数规划数学模型当在第 j 种设备上加

3、工，即 xj0 时当不在第 j 种设备上加工，即 xj=0 时n目标函数n 约束条件1、生产安排问题整数规划数学模型式中 是一个特殊的约束条件，显然当 xj0 时，yj=1, 当 xj0时，为使Z极小化，只有 yj=0 才有意义。整数规划数学模型2、投资组合问题 证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润。 项目投资：财团或银行把资金投入到若干项目中以获得中长期的收益最大。【例2】选择投资场所,使收益最大？Ai投资Bi元，收益Ci元，总投资B. 【解】设xix1 + x2 + x3 2x4 + x5 1x6 + x7 1B1x1 + B2x2 + + B7x7 BA

4、6A7A4A5A3A2A1最多选2个最少选1个最少选1个南区西区东区求解0-1规划的隐枚举法max z = C1x1 + C2x2 + + C7x71 Ai选中 0 Ai落 选=2、投资组合问题【例3】某财团 有 万元的资金，经出其考察选中 个投资项 目，每个项目只能投资一次。其中第 个项目需投资金额为 万元，预计5年后获利 （ ）万元，问应如何选 择项目使得5年后总收益最大？整数规划数学模型2、投资组合问题n变量每个项目是否投资n约束总金额不超过限制n目标总收益最大整数规划数学模型3、背包问题 邮递包裹：把形状可变的包裹用尽量少的车辆运走 旅行背包：容量一定的背包里装尽可能的多的物品【例4】

5、某人出国留学打点行李，现有三个旅行包，容积大小分别 为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单 ，其中一些物品是必带物品共有7件，其体积大小分别为400、300 、150、250、450、760、190、（单位毫升）。尚有10件可带可不 带物品，如果不带将在目的地购买，通过网络查询可以得知其在目 的地的价格（单位美元）。这些物品的容量及价格分别见下表，试 给出一个合理的安排方案把物品放在三个旅行包里。 整数规划数学模型物品12345678910体积200350500430320120700420250100价格15451007050752009020303、背包问题n

6、变量：对每个物品要确定是否带同时要确定放在哪个包裹里， 如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化 为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放 在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的 函数。为此我们设变量为第i个物品是否放在第j个包裹中。整数规划数学模型3、背包问题整数规划数学模型3、背包问题n 约 束 包裹容量限制必带物品限制选带物品限制n目标函数未带物品购买费用最小整数规划数学模型2、背包问题【例5】某人有一背包可以装10公斤重、0.025m3的物品。他准备用 来装甲、乙两种物品，每件物品的重量、体积和价值如下表所示。 问两种物品各装多少件，所

7、装物品的总价值最大？整数规划数学模型解的特点物品重量（公斤/件）体积（立方米/件）价值（元/件） 甲1.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=35 。整数规划数学模型解的特点整数规划松

8、弛问题n 可行域是离散集合，任意两个可行解的凸组合不一定为可行解n 最优解不一定在顶点上达到n 最优解不一定是放松问题最优解的邻近整数解n 一般，整数规划的最优解不会优于松弛问题的最优解n 整数可行解远多余于顶点，枚举法不可取整数规划数学模型解的特点割平面法纯整数线性规划 松弛问题设aij(i=1,2,m; j=1,2,，n)和bi (i=1,2,m)皆为整数，若不为整数，可以乘上一个倍数化的整数。（3.1a ）（3.1b ） （3.1c ）（3.1d ）（3.1a ）（3.1b ） （3.1c ）在松弛问题的最优单纯形表中，记Q为m个基变量的下标集 合，K为n-m个非基变量的下标集合。割平面

9、法CBCNXBXNCBXBB-1bIB-1Ncj-zj00松弛问题的最优解其中 若各 皆为整数， 则X*为纯整数规划的最 优解。 若各 不全为整数 ，则X*不是纯整数规划 的可行解，非最优解。割平面法 从X*的非整数分量中选取一个，用以构造一个线性约束条件，将 其加入原松弛问题，形成一个新的线性规划，再求解。 若新的线性规划最优解满足整数要求，即为纯整数规划的最优解 ，否则，重复上述步骤，直到获得整数最优解为止。 新加约束条件基本性质 已获得的不符合整数要求的线性规划最优解不满足该线性约束条 件，以使原来的非整数最优解不再出现。 凡整数可行解均满足该线性约束条件，以使整数最优解始终被保 留在每

10、次形成的线性规划可行域中。割平面法割平面法在松弛问题的最优单纯形表中，记Q为m个基变量的下标集 合，K为n-m个非基变量的下标集合。CBCNXBXNCBXBB-1bIB-1Ncj-zj00m个约束方程可表示为若其中的 不是整数，则式（3.2）中相应的约 束方程为（3.2）（3.3）原松弛问题的最优解不可行整数规划的整数可行解可行最大整数与非负真分数之和割平面法得到新的整数规划经验表明，若从最有单纯性表中选择具有最大分数部分的非整数分量所在行构造割平面约束，往往可提高“切割”效果，减少“切割”次数。割平面法【例】求下列整数规划的最优解【解】（1）松弛问题的最优表如下（单纯形法）割平面法cj320

11、0CBXBbx1x2x3x42x25/2011/2-1/2 3x113/410-1/43/4j00-1/4-5/4最优解X=(5/2，13/4，0，0)T， x1 、x2不满足整数要求，选择x2行进行分割：割平面法（2）建立新约束条件割平面法（2）将新约束加入松弛问题最优单纯形表cj32000CBXBbx1x2x3x4x52x25/2011/21/20 3x113/4101/43/402010-11割平面法（2）将新约束加入松弛问题最优单纯形表cj32000CBXBbx1x2x3x4x52x25/2011/2-1/20 3x113/410-1/43/400x5-1/200-1/2-1/21j0

12、0-1/4-5/40运用对偶单纯形法，继续计算，得到最优单纯形表割平面法cj32000CBXBbx1x2x3x4x52x25/2011/2-1/20 3x113/410-1/43/400x5-1/200-1/2-1/21j00-1/4-5/402x22010-11 3x17/21001-1/20x310011-2j000-1-1/2aijZ因此LP5的最优解就是原整数规划的最优解。上述分枝过程可用下图表示： LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x13x14LP3:X=(4.33,6)Z3=35.33x

13、26LP4:X=(4,6)Z4=34LP5:X=(5,5)Z5=35x14x15无可行解x27分支定界法 混合整数规划只对整数变量分支，对非整数变量不分支 0-1整数规划作业P1465.15.25.35.4求解0-1规划的隐枚举法求解0-1规划的隐枚举法1. 找出任意一可行解，目标函数值为Z0； 2. 原问题求最大值时，则增加一个约束当原问题求最小值时，上式改为小于等于约束； 3. 列出所有可能解，对每个可能解先检验式（*），若满足再检验 其它约束，若不满足式（*），则认为不可行，若所有约束都满 足，则认为此解是可行解，求出目标值； 4. 目标函数值最大（最小）的解就是最优解。 (*)【解】（

14、1）观察一个可行解x1 = 1 x2 = x3 = 0此时，z = 3（2）增加一个过滤条件3x1-2x2+5x33 *【例】用隐枚举法求解下列规划求解0-1规划的隐枚举法max z = 3x1 - 2x2 + 5x3 x1 + 2x2 - x3 2 x1 + 4x2 + x3 4 x1 + x2 3 4x2 + x3 6 x1,x2,x3 = 0或146（3）列表计算x1x2x3*可行 ？zx1x2x3*可行 ？z000 001 010 011 100101 110 111x1x2x3*可行 ？z0000 001 010 011 100101 110 111x1x2x3*可行 ？z0000

15、0015-11015 010 011 100101 110 111x1x2x3*可行 ？z0000 0015-11015 010-2 011 100101 110 111x1x2x3*可行 ？z0000 0015-11015 010-2 011315 100101 110 111x1x2x3*可行 ？z0000 0015-11015 010-2 011315 100311103101 110 111x1x2x3*可行 ？z0000 0015-11015 010-2 011315 100311103101802118 110 111x1x2x3*可行 ？z0000 0015-11015 010-2 011315 100311103101802118 1101 111x1x2x3*可行 ？z0000 0015-11015 010-2 011315 100311103101802118 1101 111626最优解：x1* = 1 x2* = 0 x3*