运筹学第五章 整数规划

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

1、第五章第五章 整数规划整数规划5.1 整数规划实例及一般模型5.2 分支定界法5.3 0-1整数规划5.4 指派问题5.1.1 5.1.1 整数规划实例整数规划实例例5.1某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如下表所示。 货物每件体积/立方英尺每件重量/百千克每件利润/百元 甲19542乙273403托运限制1365140甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大？解 设x1、x2分别为甲、乙两种货物托运的件数，建立模型3整数规划问题的松弛问题xj部分或全部取整数5.1.2 整数规划的一般模型整数规划的类型纯整数规划：xj

2、全部是整数混合整数规划： xj部分是整数0-1型整数规划：xj = 0或1xj部分或全部取整数 整数规划问题的可行解集合是它的松弛问题可行 解集合的一个子集; 整数规划问题的最优解的目标函数值不会优于松 弛问题的最优解的目标函数值.松弛问题 最优解整数规划 最优解例例不能通过舍入取整地方 法，由松弛问题的解得 到整数规划的最优解5.3 0-15.3 0-1整数规划的建模方法整数规划的建模方法0-1变量（逻辑变量 Logical variable） ：只能取 值0或1的变量。0-1变量也称为逻辑变量。它常用来表示决策时是否取某个特定方案，或者表示系 统是否处于某个特定状态，或者表示两个选项中 非

3、此即彼的选择。xj = 1 当决策取方案 P j 时 0 当决策不取方案 Pj 时例5.5 广州某食品公司计划在市区的东、西、南、北四区 建立销售门市部，目前有10个位置可供选择，考虑到 各地区居民的消费水平及居民居住密集程度，规定：在东区由三个点中最多选择两个；在西区由两个点中至少选择一个；在南区由两个点中至少选择一个；在北区由三个点中至少选择两个。投资总额不能超过720万元，问应该选择哪几个销售点 ，可使年利润为最大？ 1 1、0-10-1型变量表示决策时是否取某个特定方案型变量表示决策时是否取某个特定方案s.t.在东区由三个点中最多 选择两个在西区由两个点中至少 选择一个在南区由两个点中

4、至少 选择一个在北区由三个点中至少 选择两个解:设 xj = 1 当A i点被选用; 0 当Ai点不被选用2、0-1型变量常用来表示是否处于某个特定状态l例5.6 有三种资源被用于生产三种产品，资源量、 产品单件可变费用及售价、资源单耗量及组织三种产 品生产的固定费用见下表。要求制定一个生产计划， 使总收益最大。产品1产品2产品3a11 机床1a13 机床3a14 机床4a21 机床1a22 机床2a24 机床4 a32 机床2a33 机床31 同一 件产品 在不同 机床上 的加工 顺序同一件产品在下一台机床上加工的开始时间不得早 于在上一台机床上加工的结束时间xij表示第i种产品在第j台机床

5、上加工的开始时间。产品1：x11+a11x13 及 x13+a13x14产品2：x21+a21x22 及 x22+a22x24产品3：x32+a32x33l例5.7 用4台机床加工3件产品。各产品的机床加工顺序，以及产品在机 床上的加工工时见下表，且要求工件二的总工时不超过d。现要求确定 各件产品在机床上的加工方案,使在最短的时间内加工完全部产品.0-10-1型变量常用来表示型变量常用来表示两个选项中非此即彼的选择2 每台机 床对不同 产品的加 工顺序约 束一台机床在工作中，若已开始的加工还未结束，则 不能开始加工另一产品。注意到每台机床可以加工两种产品。因此可以用0- 1变量yi表示第i台机

6、床加工产品的顺序。具体表示y1y2y3y40先加工 产品11先加工 产品20先加工 产品21先加工 产品30先加工 产品11先加工 产品30先加工 产品11先加工 产品2机床1 x11+a11x21+My1 及 x21+a21 x11+M(1-y1) 机床2 x22+a22x32+My2 及 x32+a32 x22+M(1-y2) 机床3 x13+a13x33+My3 及 x33+a33 x13+M(1-y3) 机床4 x14+a14x24+My4 及 x24+a24 x14+M(1-y4)互斥的 约束条件3 产品2 的加工总 时间约束产品2加工开始的时间是x21，结束加工的时间是 x24+a

7、24，于是x24+a24 x21d4 目标函 数的建立设全部产品加工结束时间为W。 由于三件产品的加工结束时间分别为x14+a14, x24+a24, x33+a33 故 W=max(x14+a14, x24+a24, x33+a33 )根据问题的要求，目标函数为 min z=W满足W x14+a14 W x24+a24 W x33+a33从而最后得到p140的混合整数线性规划模型l例5.3 某企业在A1地已有一个工厂，其产品的生产能力为30千箱，为了扩大生产，打算在A2，A3，A4，A5地中再选择几个地方建厂，已知在A2地建厂的固定成本为175千元，在A3地建厂的固定成本为300千元，在A4

8、地建厂的固定成本为375千元，在A5地建厂的固定成本为500千元，另外，在A1的产量，A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地到销地的单位运价（每千箱运费）如下表5-3所示。问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小？如果A2和A3两地必 须有且只有一个建 厂，怎么办？0-10-1型整数规划问题的解法型整数规划问题的解法 枚举法：列出变量取值为0或1的可能的组合（若有n个 变量则有2n个组合），再逐一验证它们是否满足约束条件，然后对满足约束条件的可行解计算目标函数值，其 中目标函数值最优的就是最优解 方法的改进：若已发现一个可行解，则

9、根据它的目标 函数值可以产生一个过滤条件（filtering constraint），对于目标函数值比它差的变量组合就不必再去检验它的 可行性。只要发现某个变量组合不满足其中一个约束条 件，就不必再去检验其他约束条件是否可行。隐枚举法解 为提高搜索效率，减少运算量，先按照目标函数中 各变量系数的大小顺序重新排列各变量。 排为x3,x2,x1 。(x3,x2,x1)z值值约约束条件过滤过滤 条件 abcd 0，0，00，0，1 0，1，0 0，1，1 1，0，0 1，0，1 1，1，0 1，1，1021不检验3不检验-1不检验1不检验0不检验2不检验max z = -x3+x2+2x1所以最优解

10、是（x1,x2,x3）T = (1,0,0)T, max z =2n项不同的任务，需要n个人分别完成其中的一项，但由于 任务的性质和每个人的专长不同，因此，每个人去完成不 同的任务的效率（或花费的时间、费用）也就不同，于是 产生了一个问题，应指派哪个人去完成哪项任务，使完成 n项任务的总效率最高（或所需时间最短、费用最少）。 这类问题称为指派问题。5.4 5.4 指派问题指派问题应该指派哪个人 完成哪个任务？如何将n个零件分配 到n台设备进行加工 ？指派问题的标准形式为：今分配n个人去完成n项任务，每个人只能完成一项任务，每项 任务只能由一个人来完成，第i个人来完成第j 项任务的费用或时间为

11、，问如何安排才能使 总费用或总时间最小？5.4 5.4 指派问题指派问题标准形式标准形式l例5.9 有四个工人，要分别指派他们完成四项不同的工作 ，每人做各项工作所消耗的时间(我们称之为消耗系数矩 阵、效率矩阵或系数矩阵)如表5-6所示，问应如何分配任 务，才能使总的消耗时间最少？ABCD甲15172124 乙19232218 丙26171619 丁192123171 若指派第i 人做第j 事 0 若不指派第i 人做第j 事 解：令 xij=（i, j=1, , n）满足约束条件的可行解 也可写成矩阵形式，称 为解矩阵。如例5.9的一 个可行解矩阵是:每个人只能完 成一项任务每项任务只能由 一

12、个人来完成数学模型：1 若指派第i 人做第j 事 0 若不指派第i 人做第j 事 令 xij=（i, j=1, , n）st.标准形式指派问题的数学模型指派问题是一类特殊的整数规划问题。指派问题是运 输问题的特例，也是线性规划（0 1规划）的特例， 当然可用求运输问题、整数规划或0-1规划的解法去求解。这就如同用单纯形法求运输问题一样是不合算的 。利用指派问题的特点可有更简便的解法。1955年，库恩（W. W. Kuhn）提出了求解指派问题的一种算法，习惯上称之为匈牙利算法。5.4.2 5.4.2 指派问题的匈牙利算法指派问题的匈牙利算法定理5.1:如果对系数矩阵C =(cij)nn的任一行（

13、 列）各元素减去该行（列）的最小元素，得到 新矩阵B = (bij)nn ，则以B为系数矩阵的指派问 题的最优解也是原问题的最优解。匈牙利算法的步骤l步骤1：变换指派问题的系数矩阵l步骤2：试指派l步骤3：判断最优性l步骤4：调整后返回步骤2每行减该行最小数每列减该列最小数步骤1：变换指派问题的系数矩阵（cij）为(bij)，使在 (bij)的各行各列中都出现0元素，即(1) 从（cij）的每行元素都减去该行的最小元素；(2) 再从所得新系数矩阵的每列元素中减去该列的最 小元素此时独立零元素有3个，第四行没有，故转入步骤4。步骤2：试指派将只有一个0元素的行（列）的0最先画圈，称其为独立零 元

14、素。然后将其所在列（行）其它的0划掉。然后继续寻找， 直到尽可能多的0元素都被圈出和划掉为止。若仍有没有划圈的0元素，且同行同列的0元素至少有两个 ，则从剩有0元素最少的行(列)开始，比较这行各0元素所在列 中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选 择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元 素。可反复进行，直到所有0元素都已圈出和划掉为止。步骤3：判断最优性 如果独立零元素的个数等于n计算停止，按 照独立零元素对应的位置进行指派即可。 否则进入下一步进行调整。步骤4：调整任意选择一个没有独立零元素的行，将该行所有元素减去该行除0外的最小数(m)；然后该行的0

15、将会变为负数，为了将负数删除，我们将该行0所对应的列的所有元素都加上m；则原来的所在的列中的0会被变为正数。为了使0所在行能够找到新的0，须让该行所有元素再减去除0外的最小数。如果此时没有出现负数，调整结束；否则继续使负数所在列加上一个常数，继续循环。 直到系数矩阵中 没有负数，此时调整结束，重新回到step2。步骤步骤4 4：调整调整l第四行没有独立零元素，所 以让该行减2l第四行第四列的0变为-2，所以让第四列再加2l第四列的独立零元素被破坏 ，所以让第二行再减1 -2 -1 +2步骤步骤5 5 再次试指派再次试指派此时独立零元素还是只有3个，第二行没有，故转 入步骤5。步骤步骤6 6：调

16、整：调整l第二行没有独立零元素， 所以让该行减1l第二行第一列的0变为-1， 所以让第一列再加1l第一列的独立零元素被破 坏，所以让第一行再减1 -1 -1 +1步骤步骤7 7 再次试指派再次试指派此时找到了4个独立零元素，所以最优方案为：练习题：5.6(1)-1 +1-1-3-3-2+3+3Z=48非标准形式指派问题的处理非标准形式指派问题的处理1、最大化指派问题：目标函数求max最大元素：m 将原系数矩阵 C转换为B最大化指派问题例题最大化指派问题例题有5个工人，要指派去做5项工作，每人做各项工作的 能力见下表。应如何指派，才能使总的得分最大？J1J2J3J4J5S1 S2 S3 S4 S515 5 1 7 125 11 0 12 93 13 13 0 80 8 5 3 912 10 6 8 12工人工作m-cij-