《物流运筹方法与工具 教学课件 ppt 作者 彭秀兰 毛磊第四章整数规划 第二节0-1规则问题》由会员分享，可在线阅读，更多相关《物流运筹方法与工具 教学课件 ppt 作者 彭秀兰 毛磊第四章整数规划 第二节0-1规则问题（18页珍藏版）》请在金锄头文库上搜索。
1、0-1规划是变量只取0或1的一种特殊形式的整数 规划。在实际问题中，诸如开与关、取与舍、有与 无等逻辑现象都可用0-1变量来描述。由于0-1整数 规划在实践中有着广泛的应用和独特的建摸技巧 ，我们单独作为一节来讲。,一、 选址问题 例4-3 某物流公司打算在昆明或贵阳设立销售分公司 （也许在两个城市都设立销售分公司），以增加市场份额，决 策层同时也计划在新设分公司的城市最多建一个配送中心（当 然也可以不建）。每种选择公司收益的净现值、所需费用均列 在表4-3中，总的预算费用不得超过20万元。如何决策既满足 约束条件又使总的净现值最大？ 表4-3 决策资料,一、 选址问题,例4-3 解：引入0-
2、1变量,总的净现值用Z表示，目标函数为,因总的预算费用不得超过20万元，得约束条件,因公司在新设分公司的城市最多只建一个新配送中心，表达为,一、 选址问题,于是，得到一个约束,同理，决策变量4受决策变量2的约束为,即,即,例4-3 又因决策变量3和4的值分别受到决策变量1和2的约束，这两个变量的值是否取1分别决定于决策变量1和2（公司只在建有分公司的城市才决定是否建配送中心）。所以对于决策变量3，只有决策变量1取值为1时，它才可能取值为1，当然也可能取值为0；而决策变量1取值为0时，决策变量3就只能取值为0。,一、 选址问题,例4-3,将上述约束条件综述之，得该问题的数学模型,s.t.,max
3、Z =,一、 选址问题,例4-4 设有n个需求点，有m个可供选择的厂址，每 个厂址只能建一个工厂，在i处建厂，生产能力为Di， 单位时间的固定成本为ai，需求点j的需求量为bj，从 厂址i到需求点j的单位运费为cij,问应如何选择厂址才 能获得经济上总花费最小的方案。 解：设在单位时间内，从厂址i运往需求点j的产品 数量为xij，引入0-1变量,设在单位时间内的总花费为Z， 则该问题的数学模型为,一、 选址问题,例4-4,s.t.,其中第一个约束表示从i处所建工厂运出的产品数量不超过该处的生产能力；第二个约束表示从各个新建工厂运到需求点j的产品数量必须满足该点的需求量。 这是一个含有0-1变量
4、的混合整数规划问题。,二、 0-1规划的解法,（一） 枚举法 检查变量取值为0或1的每一个组合，比较目标函数值的大小以求得最优解。 例4-5 求解 maxZ=2x1+x2-x3,s.t.,解：（x1, x2, x3）共有 =8种不同的组合，各种组合下目标函数及各约束条件左端的值列于下表4-4中。,二、 0-1规划的解法,例4-5 表4-4 枚举过程,上表中用标“*”表示相应的组合不满足该约束条件，知可行解为（0，0，0），（0，0，1），（1，0，0），（1，0，1），相应的目标函数值分别为0，-1，2，1，而max(0，-1，2，1) = 2, 即 maxZ = 2, 最优解为（1，0，0）
5、T 。 当变量数n较大时，n个变量取值的组合数为2n， 2n相当大，枚举法已不是一种可行的办法。,二、 0-1规划的解法,(二) 隐枚举法 检查变量取值组合的一部分（而不是全部），就能求得问 题最优解的方法。 其基本思路是：先找到一组可行解，然后改进目标值，直 到不能改进为止。具体步骤：求解时，先找到一个可行解， 算出其目标函数值，并令该值为初始过滤值。根据目标函数 中各变量系数的递增顺序，对目标函数和约束不等式中的变量 重新排列。考察各变量的可能组合，若产生的目标函数值劣 于此时的过滤值，则不予考虑；若优于此时的过滤值，则以它 为更好的可行解，并以它的目标函数值为新的过滤值。重复 步骤，一直
6、到不能再改进目标函数值为止。最后的过滤值， 就是最优目标函数值，对应的可行解，就是最优解。,二、 0-1规划的解法,例4-6 求解0-1规划问题 maxZ=3x1-2x2+5x3,s.t.,解：根据目标函数中xi系数的递增顺序，重新排列变量的次序，得 maxZ= -2x2+3x1+5x3,s.t.,二、 0-1规划的解法,例4-6 因-2，3，5是递增的，变量的组合也以（x2, x1, x3）的顺序排列。按上述各变量的递增顺序列出的解有：（0，0，0），（0，0，1），（0，1，0），（0，1，1），（1，0，0），（1，0 ，1），（1，1， 0），（1，1，1），按这样的顺序寻优，最优解常
7、易较早发现。显然（0，0，0）是一个可行解，相应的目标函数值Z=0可作为初始过滤值。 目标函数在（x2, x1, x3）=（0，0，1）处的值Z=5，且它是一个可行解，因50，故用5取代0为新的过滤值。 继续查目标函数在（x2, x1, x3）=（0，1，0）处的值，得Z=3，因35,需查（0，1，1）是否为可行解，易知它是可行解，故用8取代5为新的过滤值。,二、 0-1规划的解法,例4-6 由目标函数 maxZ= -2x2+3x1+5x3 3x1+5x3 31+51=8 可知，目标函数值不会超过8，即过滤值8不能再改进。8就是最 后的过滤值。所以目标函数的最优值Z=8，最优解X=（x2, x
8、1, x3）=（0，1，1）。 上述解题过程示于表4-5中。表中“”表示满足该约束条 件，“”表示不必检查是否满足约束条件。 表4-5 隐枚举过程,三、混合整数线性规划模型,在物流系统的管理问题中，大量的问题是线性的， 加之整个系统网络对决策变量的要求不会仅仅是0或 1；或仅是整数。常有一部分决策变量因其实际意义 需取整数，而另一部分决策变量需是连续的非负数。 这样，针对物流系统的网络化结构，许多问题的数学 模型就是一个大型的混合-整数线性规划模型。现举 一例加以说明。,三、混合整数线性规划模型,例-7 已知某企业有40个需求城市，准备在广州和深圳两 地设立物流中心，配送中心候选地有8个，包括
9、广州、深圳、厦 门、武汉、长沙、郑州、汕头、福州。从每一个物流中心，经过 若干个配送中心，向若干个客户配送货物，同一需求城市需要的 产品由同一配送中心供给，各配送中心不存在维持运营的最低数 量限制。物流中心已定，企业物流网络结构如图4-6所示。为完 善其物流网络，研究建立其网络优化模型，要求从中选择若干个 配送中心，使总的物流成本最低,图4-6 物流网络结构模型,三、混合整数线性规划模型,例-7 解：设变量Xijk表示由物流中心i经配送中心j到达需 求城市k的物流通过量，Cijk表示从物流中心i经配送中 心j到达需求城市k的单位平均生产、搬运、运输成 本，Si表示物流中心i的生产能力，fj表示配送中心j运 营的固定成本， vj表示配送中心j货流量的单位变动成 本， 表示配送中心j最大库容量，Dk表示需求城市 k对商品的需求量，再引入两个0-1变量：,Zj=,Yjk=,三、混合整数线性规划模型,例-7 由题意得数学模型（结合题意考虑到该网络物流通过量不能超过物流中心各自的供货能力；所有城市的需求必须得到满足；各配送中心的吞吐量不能超过其吞吐能力。）：,s.t.,min Z =,本节作业题,教材P89： 3题， 教材P90 5题， 6题， 7题。,
