运筹学模型.doc

运筹学模型源于第二次世界大战期间的运筹学研究，有效地解决了如何将有限的资源分配于各项军事活动，以取得最优的战争效果等重大军事决策问题，为盟军取得二战的胜利作出了不可磨灭的贡献。战后，该项技术不但在军事科学上不断发展，在工农业生产、科学实验、工程技术、经济管理和社会科学中都有着广泛的应用和发展。特别是计算机技术的引入，更使得运筹学的研究和应用如虎添翼，一些大规模或超大规模的决策变量和约束条件问题的求解也变成了现实。运筹学的分支较多，这里我们只介绍线性规划、整数规划、动态规划等方面的运筹学应用和模型，读者通过学习解决这些运筹学问题的思想和方法，而对运筹学模型的建立、应用和求解有更深的认识。一、 线性规划模型1线性规划数学模型的一般形式 例1农作物的生产安排问题1）问题的提出以色列的某社区联盟，其农业生产受农田面积和灌溉配水量的限制，其资料如表4.1所示表4.1社区可耕地（英亩）配水量140060026008003300375适合该地区种植的农作物有甜菜、棉花和栗子，其每英亩的期望净收益、用水量及可种植的最大面积如表4.2所示表4.2农作物最大面积（英亩）每英亩用水量净收益（元/英亩）甜菜6003400棉花5002300栗子3251100试问，该社区联盟应如何安排这三种农作物的生产，方使总的收益最大？2）假设与分析决策变量分别表示这三个社区三种农作物的种植面积（见表4.3所示）。 表4.3农作物社区123甜菜棉花栗子则该问题的线性规划模型为：目标函数 约束条件为：非负性： 土地约束： 水资源约束： 最大面积约束：3）模型的建立与求解用单纯形法或用数学软件包求得其最优解如下表所示：农作物社区123甜菜10025棉花100250150栗子000一般地，线性规划问题的求解过程具有如下的一些共同特征：（1）每一问题都可用一组称之为决策变量的未知数来表示相应的活动方案，由于实际问题的要求，这些决策变量通常是非负的。（2）对决策变量，大都存在一定的限制条件（称为约束条件），且这些限制条件一般可用关于决策变量的一组线性不等式或等式来表示。（3）有一个追求的目标函数，且目标函数一般可表示为决策变量的线性函数，并由实际问题来决定目标函数应追求最大还是最小。用数学语言描述，线性规划问题的的数学模型为：目标函数： 约束条件为：简单线性规划问题大都用图解法或单纯形法求解，而复杂线性规划问题可用相应的数学软件包求解，这里，不再详述。2.应用实例例2空气污染管理问题1) 问题的提出 位于钢城的诺利公司为当地的主要钢铁厂家之一，公司为钢城的繁荣与发展作出了一定的贡献。但现在情况有所改变，由于钢厂对熔炉的排放物未进行管理，致使空气污染破坏了钢城的环境，并危害了当地居民的健康。公司董事会就此作出了明智的决定，指定专门人员与市政官员和人民团体商讨解决空气污染问题，以保证工厂的排放物能达到环保部门的要求。研究发现，造成空气污染的物质主要有三种：微粒、氧化硫及碳化氢，钢厂每年须减少的污染物排放量达到表4.4的要求时，方满足环保的要求。表4.4 （环保部门的空气清洁标准）污染物每年须减少的污染物排放量（百万磅）微粒60氧化硫150碳化氢125污染物的主要来源为：（1）制造生铁之鼓风炉；（2）炼钢之敞炉。减少污染物排放的有效方法为：（1）增加烟囱高度；（2）在烟囱内安装过滤器；（3）使用优质燃料。这些方法对减少污染虽有帮助（其效果见表4.5），但任一方法的单独使用，均不能达到环保部门的要求，若三种方法同时以最高的标准实施，则工厂的产品成本将陡增，从而使产品失去市场竞争力甚至因此而破产，管理部门因此而忧心忡忡。表4.5（各减污法每年最高可能减少的污染排放量（单位：百万磅）污染物增高烟囱安装过滤器使用优质燃料鼓风炉敞炉鼓风炉敞炉鼓风炉敞炉微 粒12925201713氧化硫354218315649碳化氢375328242920专题组人员经分析知各减污方法中最高减污量之总成本的近似值如表4.6所示。而公司每年可拨出的治污专款也有一底限，试确定该公司是否能实施“空气污染管理”工程。表4.6（最高减污法之总成本：以百万元为单位）减 污 法鼓风炉敞 炉增高烟囱810过 滤 器76优质燃料1192）假设与模型的建立工程实施的关键在于既要确保排污效果能达到环保部门的要求，又要最大限度地降低成本（不超过其所能承受的底限）。由于问题的解决具有组合性，故可考虑用线性规划模型求解，假设决策变量分别表示各减污法中最高成本的比例值（见下表）减污方法鼓风炉敞炉增高烟囱过滤器优质燃料则其目标函数为：约束条件为：求解得：工程造价为：。若问题的最优解3215.9万元未超过公司所能承受的底限，则该治污工程可上马，否则得另谋它法。例3饲料配比问题1) 问题的提出某公司长期饲养实验用的动物以供出售，已知这些动物的生长对饲料中的蛋白质、矿物质、维生素这三种营养成分特别敏感，每个动物每天至少需要蛋白质70g、矿物质3g、维生素10mg，该公司能买到五种不同的饲料，每种饲料1 kg所含的营养成分如表4.7所示，每种饲料1kg的成本如表4.8所示，试为公司制定相应的饲料配方，以满足动物生长的营养需要，并使投入的总成本最低。表4.7饲料蛋白质（g）矿物质（g）维生素（mg）10.30.10.05220.050.1310.020.0240.60.20.251.80.050.08表4.8饲 料12345成本（元）0.20.70.40.30.52）假设与分析设表示混合饲料中所含的第种饲料的数量（即决策变量），因每个动物每天至少需要蛋白质70g、矿物质3g、维生素10mg，所以应满足如下的约束条件因要求配制出来的饲料其总成本最低，故其目标函数为：由于约束条件及目标函数均为线性函数，故原问题是一线性规划模型。3）模型的建立与求解由上述讨论知，饲料配比问题的线性规划模型为：，使如下约束条件成立：例4 连续投资问题1) 问题的提出 某部门在今后五年内考虑给下列项目投资，已知如下条件：项目A，从第一年到第四年每年年初均需投资，并于次年末回收本利115%；项目B，第三年初需要投资，到第五年末回收本利125%，但规定最大投资额不超过4万元；项目C，第二年初需要投资，到第五年末回收本利140%，但规定最大投资额不超过3万元；项目D，五年内每年初可购买公债，于当年末归还，可获利息6%。该部门现有资金10万元，问它应如何确定给给这些项目每年的投资额，使到第五年末部门所拥有的资金的本利总额最大。2）假设与分析这是一个连续投资问题，能否定义好决策变量，并使之满足线性关系，是能否用线性规划方法求最优解的关键。我们用表示第年初分别用于项目A，B，C，D的投资额（即决策变量），根据题设条件，可列出表4.9（表中空格部分表示该项目当年的投资为0）：表4.9年份项目12345ABCD下面讨论这些决策变量应满足的线性约束条件。从表4.9知：第一年年初仅对项目A、D进行投资，因年初拥有资金10万元，设项目A、D的投资额分别为、，则有：。同理，第二年对项目A、C、D的投资额应满足方程：而第三年、第四年、第五年对项目A、B、D；项目A、D；项目D的投资额应分别满足如下的方程：另外，项目B、C的投资额度应受如下条件的约束：由于“连续投资问题”要求第五年末部门所拥有的资金的本利总额最大，故其目标函树为：3）模型的建立与求解有了如上的分析，我们可给出该“连续投资问题”的线性规划模型为：求解得：第一年：第二年：第三年：第四年：第五年：由此求出第五年末该部门所拥有的资金的本利总额为：143750元，即部门赢利43.75% 。二、 运输问题模型1.运输问题模型概述运输问题是一类特殊的线性规划模型，该模型的建立最初用于解决一个部门的运输网络所要求的最经济的运输路线和产品的调配问题，并取得了成功。然而，在实际问题的应用中，除运输问题外，许多非运输问题的实际问题一样可以建立其相应的运输问题模型，并由此而求出其最优解。下面以“产销平衡模型”对运输问题进行一下简单的概括和描述： 某产品的生产有个产地，其生产量分别为，而该产品的销售有个销地，其需要量分别为，已知该产品从产地到销地的单位运价为，试建立该运输问题的线性规划模型。解：假设从产地到销地的运输量为，因从产地到销地的单位运价为，我们可把运输量（）汇总于产销平衡表中，而把单位运价汇总于单位运价表中（见下表）。产销平衡表 产地销地12n产量12 销 量 则在该产销平衡表表中，第列的物理含义为：从各产地发往销地的部分运输量的和应等于销量，第行的物理含义类同。 单位运价表销地产地1212 由以上的讨论，对产销平衡的情形，我们可给出其运输问题的数学模型如下： 当然，在实际问题的应用中，常出现产销不平衡的情形，此时，需要把产销不平衡问题转化为产销平衡问题来进行讨论。例当产量大于销量时，只需增加一个虚拟的销地，而该销地的需要量为即可。销量大于产量的情形类同。2. 应用实例 运输问题模型的应用比较广泛，并不完全局限于运输问题，下面我们举例说明之。例1.生产时序的安排1) 问题的提出北方飞机公司为全球各航空公司制造商用飞机。其生产过程之最后阶段为生产喷射引擎，然后装置于（一极速工作）制妥的机体，该公司有若干近期必须交付使用的飞机的合同，现须安排今后四个月飞机喷射引擎的生产计划，并须于每月末分别提供10、15、25、20台引擎。已知该公司各月的生产能力和生产每台引擎的成本如下表所示（单位：百万元），又如果生产出来的引擎当月不能交货的，每台引擎每积压一个月需存储和维护费用0.015百万元，试在完成合约的情况下，制定一引擎数量的生产安排方案，以使该公司今后四个月的生产费用最小。生产成本表月 份合约数生产能力单位成本存储和维护费110251080015215351110015325301100015420101132）模型分析与变量的假设初看之下，这是一个与运输问题模型毫无关系的问题，如何用运输问题模型求出其最优解，这种素质和能力是因人而异的。用运输问题模型求该问题最优解的关键在于怎样建立该问题的产销平衡表及元素和单位运价表及元素。为此，我们假设表示第月生产并用于第月交货的引擎数，因公司必须完成合同，则应满足：又每月生产的用于当月和以后各月交货的引擎数不可能超过该公司的实际生产能力，故还应满足：下面再构造“单位运价表”，它应等价于这里的“成本费用表”。因第月生产并用于第月交货的引擎数的实际成本应该是其生产单位成本再加上存储、维护费用，从而我们可得其“成本费用表”如下：成本费用表123411.081.0951.1101.12521.1101.1251.14031.1001.11541.130由于这是产销不平衡问题，故增加一虚拟的销地D，使之能构造为产销平衡模型，并把“产销平衡表和单位运价表”合二为一（见下表）：1234D产量（）11.081.0951.1101.1250252M1.1101.1251.1400353MM1.1001.1150304MMM1.130010销量（）1015252030在该表中，表示公司第月的生产能力，表示第月的合同供应量，表示相应的成本费用，因在实际问题中，当时，故令相应的。3）模型的建立与求解有了如上的讨论，我们可给出“生产时序的安排”所对应的“运输问题模型”为：且据此，我们可求出其最优解为：。相应的最小生产费用为：故今后四个月引擎数量的生产安排为：月 份1234引擎生产数量2553010例2航运公司的船只配备问题1）问题的提出某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务，已知各条航线的起点、终点城市及每天的航班数如下表所示：航线起点城市终点城市每天航班数1ED32BC23AF14DB1假定各条航线使用相同型号的船只，又各城市间的航程天数如下表所示： ABCDEFA0121477B1031388C23015557851703F7852030若每条船只每次装卸货的时间各需一天，则该航运公司至少应配备多少条船只，才能满足所有航线的运营要求？2）模型分析与变量的假设公司所需配备的船只数分为“在航所需船只数及调度所需船只数”这两部分，计算出在航所需船只及调度所需船只这两种情况所必需的最少数量，便可确定该航运公司至少应配备的船只数。在航所需船只数情形可直接进行计算，例如航线1，在起点E装货需1天，从ED航程需17天，在终点D卸货需1天，共计19天，该航线每天发3班，故该航线在航船只至少需57只船，同理，可求出其它各航线所需的最少在航船只数如下表所示：航线装货天数航程天数卸货天数小 计航班数周转数11171193572131521031719194113115115合计91但调度所需船只数情形就不便直接求出了，因为有的港口，它每天到达船只数大于所需船只数，例如港口D，每天到达3条船只，需求1条船只；而有的港口，它每天到达船只数小于所需船只数，例如港口B，每天到达1条船只，需求2条船只。故如何确定公司调度所需船只数是解决问题的关键。对此，我们建立运输问题模型求其最优解。这样一来，怎样给出调度所需船只数情形所对应的产销平衡表和单位运价表，以据此求出其最优解，是迫在眉睫的事情了。为建立调度所需船只数情形所对应的产销平衡表和单位运价表，我们以每个港口城市作为考虑对象，凡到达船只数大于需求船只数的港口城市，我们将其视为产销平衡表中产地，而到达船只数小于需求船只数的港口城市，我们将其视为产销平衡表中销地，对管理部门而言，每个港口城市的到达船只和需求船只是不难获知的（见下表）：港口城市每天到达每天需求余缺数A01-1B12-1C202D312E03-3F101用表示从港调拨到港的船只数，则我们给出该问题的产销平衡表如下： 销 地产 地ABE“产量”C2D2F1“销量”113而该问题的单位运价表的元素视为各港口之间的船只航行天数，于是可给出该问题的单位运价表如下：ABEC235D141317F7833）模型的建立与求解有了以上的分析，我们可给出该问题对应的运输问题模型为：且由表上作业法，我们可求出其最优解为：，其余为0。相应的船只调度最小数为：所以，在不考虑维修、储备等情况下，该航运公司至少应配备138条船只。三、 目标规划模型1. 目标规划模型概述1) 引例 目标规划模型是有别于线性规划模型的一类多目标决策问题模型，通过下面的例子，我们可看出这两者的区别。例1 某工厂的日生产能力为每天500小时，该厂生产A、B两种产品，每生产一件A产品或B产品均需一小时，由于市场需求有限，每天只有300件A产品或400件B产品可卖出去，每出售一件A产品可获利10元，每出售一件B产品可获利5元，厂长按重要性大小的顺序列出了下列目标，并要求按这样的目标进行相应的生产。（1）尽量避免生产能力闲置；（2）尽可能多地卖出产品，但对于能否多卖出A产品更感兴趣；（3）尽量减少加班时间。显然，这样的多目标决策问题，是单目标决策的线性规划模型所难胜任的，对这类问题，须采用新的方法和手段来建立对应的模型。2）相关的几个概念（1）正、负偏差变量、正偏差变量表示决策值超过目标值的部分；负偏差变量表示决策值未达到目标值的部分；一般而言，正负偏差变量、的相互关系如下：当决策值超过规定的目标值时，；当决策值未超过规定的目标值时，；当决策值正好等于规定的目标值时，。（2）绝对约束和目标约束绝对约束是必须严格满足的等式约束或不等式约束，前述线性规划中的约束条件一般都是绝对约束；而目标约束是目标规划所特有的，在约束条件中允许目标值发生一定的正偏差或负偏差的一类约束，它通过在约束条件中引入正、负偏差变量、来实现。（3）优先因子（优先级）与权系数目标规划问题常要求许多目标，在这些诸多目标中，凡决策者要求第一位达到的目标赋予优先因子，要求第二位达到的目标赋予优先因子，并规定，即级目标的讨论是在级目标得以实现后才进行的（这里）。若要考虑两个优先因子相同的目标的区别，则可通过赋予它们不同的权系数来完成。3）目标规划模型的目标函数 目标规划的目标函数是根据各目标约束的正、负偏差变量、和其优先因子来构造的，一般而言，当每一目标值确定后，我们总要求尽可能地缩小与目标值的偏差，故目标规划的目标函数只能是 的形式。我们可将其分为以下三种情形：（1）当决策值要求恰好等于规定的目标值时，这时正、负偏差变量、都要尽可能小，即对应的目标函数为： ；（2）当决策值要求不超过规定的目标值时，这时正偏差变量要尽可能小，即对应的目标函数为： ；（3）当决策值要求超过规定的目标值时，这时负偏差变量要尽可能小，即对应的目标函数为： 。目标规划数学模型的一般形式为：且满足： 有了以上的讨论，在例1中，设分别表示产品A、B的生产数量，表示生产能力闲置的时间，表示加班时间，表示产品A没能达到销售目标的数目，表示产品B没能达到销售目标的数目。因要求尽量避免生产能力闲置及尽量减少加班时间，故有目标约束条件为：（、要尽可能小），又要求尽可能多地卖出产品，故有目标约束条件为：（、要尽可能小），多卖出A产品的要求可体现在目标函数的权系数中，于是可得到例1的目标规划模型为：且满足目标约束：2应用实例例1. 职工的调资方案问题1）问题的提出某单位领导在考虑本单位职工的升级调资方案时，要求相关部门遵守以下的规定：（1） 年工资总额不超过60000元；（2） 每级的人数不超过定编规定的人数；（3） 、级的升级面尽可能达到现有人数的20%；（4） 级不足编制的人数可录用新职工，又I级的职工中有10%的人要退休。相关资料汇总于下表中，试为单位领导拟定一个满足要求的调资方案。等 级工资额（元/年）现有人数编制人数I20001012150012151000155合 计37422）模型分析与变量假设 显然这是一个多目标规划的决策问题，适于用目标规划模型求解，故需要确定该问题与之对应的决策变量、目标值、优先等级及权系数等。设、分别表示提升到I、级和录用到级的新职工人数，由题设要求可确定各目标的优先因子为：年工资总额不超过60000元；每级的人数不超过定编规定的人数；、级的升级面尽可能达到现有人数的20%；下面再确定目标约束，因要求年工资总额不超过60000元，所以有：20000（10-1010%+）+1500（12-+）+1000（15-+）+且正偏差变量要尽可能小，又第二目标要求每级的人数不超过定编规定的人数，所以，对I级有：，且正偏差变量要尽可能小；对级有：，且正偏差变量要尽可能小；对级有：，且正偏差变量要尽可能小；对第三目标、级的升级面尽可能达到现有人数的20%，我们有：且负偏差变量要尽可能小；且负偏差变量要尽可能小；3）模型的建立 由此，我们可得到该问题的目标规划模型为：且满足：求解后可得到该问题的一个多重解，并将这些解汇总于下表中，以供领导根据具体情况进行决策：变量含 义解1解2解3解4晋升到I级的人数242433晋升到级的人数3335晋升到级的人数0335工资总额的节余数6300330030000I级缺编人数060600级缺编人数242431级缺编人数30060级超编人数00006级超编人数0002例2.物资的调运安排问题1）问题的提出有一供需不平衡（供应量需求量）的物资调运问题如下表所示：请为其制订物资调运方案，使之满足以下的目标要求：尽量保证满足重点客户的需求指标；要求总运费不超过预算指标元；至少满足客户需求指标的80%；由至的运输量按合同规定不少于1万吨；至的道路危险，运量要减少到最低点。 客户运价仓库B1B2B3供应量（万吨）A1C11C12C135A2C21C22C238A3C31C32C337需求量（万吨）86102）模型分析与变量假设 这仍然是一个多目标决策规划问题，虽然未给出给出仓库到客户之间的单位运价，但这并不影响我们的分析与建模。设从仓库调拨到客户的货运量为，因该问题的供应量小于需求量，故从仓库调拨到客户的货运量不可能超过所要求的需求量，因此，于是有：又目标为：尽量保证满足重点客户的需求指标，故有：，且都要尽可能小；对目标：因要求总运费不超过预算指标元，故有：，且应尽可能小；对目标：因要求至少满足客户需求指标的80%，故有：，且应尽可能小；对目标因要求由至的运输量按合同规定不少于1万吨，故有：，且应尽可能小；对目标因至的道路危险，而要求运量要减少到最低点，故有：，且应尽可能小；另外，从仓库调拨到客户的货运量不可能超过该仓库的供应量，所以有：3）模型的建立与求解至此，我们得到该“物资调运安排问题”的目标规划模型为：且满足： 这里四、 01型整数规划模型1. 01型整数规划模型概述整数规划指的是决策变量为非负整数值的一类线性规划，在实际问题的应用中，整数规划模型对应着大量的生产计划或活动安排等决策问题，整数规划的解法主要有分枝定界解法及割平面解法（这里不作介绍，感兴趣的读者可参考相关书籍）。在整数规划问题中，01型整数规划则是其中较为特殊的一类情况，它要求决策变量的取值仅为0或1，在实际问题的讨论中，01型整数规划模型也对应着大量的最优决策的活动与安排讨论，我们将列举一些模型范例，以说明这个事实。01型整数规划的的数学模型为：目标函数 约束条件为：这里，0 | 1表示0或1。2. 01型整数规划模型的解法 01型整数规划模型的解法一般为穷举法或隐枚举法，穷举法指的是对决策变量的每一个0或1值，均比较其目标函数值的大小，以从中求出最优解。这种方法一般适用于决策变量个数较小的情况，当较大时，由于个0、1的可能组合数为，故此时即便用计算机进行穷举来求最优解，也几乎是不可能的。隐枚举法是增加了过滤条件的一类穷举法，该法虽能减少运算次数，但有的问题并不使用。此时，就只能用穷举法了。3. 应用实例例1 工程上马的决策问题1）问题的提出 某部门三年内有四项工程可以考虑上马，每项工程的期望收益和年度费用（千元）如下表所示：假定每一项已选定的工程要在三年内完成，是确定应该上马哪些工程，方能使该部门可能的期望收益最大。工 程费 用期望收益第1年第2年第3年15 1 84 7 103 9 28 6 1020402030234可用资金1822242）模型分析与变量的假设 这是工程上马的决策问题，对任一给定的工程而言，它只有两种可能，要么上马，要么不上马，这两种情况分别对应二进制数中的1、0，大凡这样的实际背景所对应的工程问题，大都可考虑用01型整数规划模型建立其相应的模型。设因每一年的投资不超过所能提供的可用资金数25千元，故该01型整数规划问题的约束条件为：由于期望收益尽可能大，故目标函数为：3）模型的建立与求解至此，我们得到该问题的01型整数规划模型为：约束条件为：下面用隐枚举法求其最优解。易知，该01型整数规划模型有一可行解（0，0，0，1），它对应的目标函数值为：。自然，该模型的最优解所对应的目标函数值应不小于30，于是，我们增加一过滤条件为： （4）在此过滤条件（过滤条件可不唯一）下，用隐枚举法求01型整数规划模型的最优解的步骤为：（1）先判断第一枚举点所对应的目标函数值是否满足过滤条件，若不满足，则转下一步；若满足，再判断该枚举点是否满足各约束条件，若有一个约束条件不满足，则转下一步，若均满足，则将该枚举点所对应的目标函数值z1（本例中，z1）作为新的目标值，并修改过滤条件为： ，再转下一步；(2) 再判断第二枚举点所对应的目标函数值是否满足新的过滤条件，若不满足，则转下一步；若满足，接着判断该枚举点是否满足各约束条件，若有一个约束条件不满足，则转下一步，若均满足，则将该枚举点所对应的目标函数值z2（z2 z1）作为新的目标值，并修改过滤条件为： ，再转下一步；(3) 重复步骤（2），直至所有的枚举点均比较结束为止。由隐枚举法的求解步骤，我们可给出该问题的求解过程如下表所示，并得到最优解为：，相应的目标值为90（千元）。故应上马的工程为2号、3号、4号工程。枚举点当前目标值满足约束条件（含过滤条件）？新目标值（4）（1）（2）（3）（0，0，0，0）（0，0，0，1）（0，0，1，0）（0，0，1，1）（0，1，0，0）（0，1，0，1）（0，1，1，0）（0，1，1，1）（1，0，0，0）（1，0，0，1）（1，0，1，0）（1，0，1，1）（1，1，0，0）（1，1，0，1）（1，1，1，0）（1，1，1，1）3030303050507070909090909090909030303050507070909090909090909090注：在该表中，表示满足相应条件，表示不满足相应条件。例2 工序的流程安排问题1）问题的提出 一条装配线由一系列工作站组成，被装配或制造的产品在装配线上流动的过程中，每站都要完成一道或几道工序，假定一共有六道工序，这些工序按先后次序在各工作站上完成，关于这些工序有如下的数据：工序所需时间（分）前驱工序13无25无322461，3582634另外工艺流程特别要求，在任一给定的工作站上，不管完成哪些工序，可用的总时间不能超过10分钟，如何将这些工序分配给各工作站，以使所需的工作站数为最少？2）模型分析与变量的假设下面，我们先讨论工序与工作站的关系，并试图建立起该问题的01型整数规划模型。 对任一工序而言，它要么属于工作站，要么不属于工作站，故决策变量可定义为： 这种定义，使我们能根据最优解中的值来很快确定工序与工作站之间的隶属关系。 又因工序1，2，3所需的工作时间不超过10分钟，故工序1，2，3的工作可以在一个工作站上完成，此时，工序4，5，6只能分别在各自的工作站上工作，该可行解对应的工作站数为4个。也就是说，对最优解而言，该装配线上所需的工作站个数不会多于4个。因此，我们再定义变量如下：至此，我们得到所需的目标函数为：再考虑该模型的约束条件：（1） 每道工序均隶属于一个工作站，且每一工序都必须完成，故有以下六个约束：（2） 在任一工作站上完成隶属工序所用的时间不能超过10分钟，故有以下四个约束：（3）最后，我们再考虑各道工序所受的先后次序约束的条件，各工序间的优先关系见右图：先考察工序2与工序3的关系，因工序2在工序3之前 1 2 运行，故若工序3隶属于工作站4，则工序2无论属于那个工作站均可；若工序3隶属于工作站3，则工序2可属于工作站 3 1或2或3；此时，变量应满足的约束条件为：； 4 同理，若工序3隶属于工作站2或1，则变量应 6 5 满足的约束条件为：同理，根据其它工序的优先关系，可仿此法给出其相应的约束条件，由上图知，六个工序之间有五个优先关系，故这类约束条件共有15个。另外，在最优解中，若有一个工作站不用（即=0），则隶属于该工作站的全部必须为0，于是，有以下四个约束条件：3）模型的建立与求解 至此，我们得到了该问题的01型整数规划模型，它共包含28个变量，29个约束条件，这样的模型用枚举法求解，人工计算是很难胜任的，这时，只能求助于计算机求解了。我们给出该问题的模型如下，求解的过程望感兴趣的读者自己完成之。该问题的目标函数为：约束条件为：； ； ； ； ； ； ； ； ； ； ；五、离散模型在现实世界中涉及到的许多变量都是离散的，例如从实验或观察得到的数据，或者统计数据；还有一些原本是连续的变量，比如时间，但是从建模的目的考虑，将变量离散化以后加以考虑则更加合适。一般来说，离散模型包括的范围非常广。本章只介绍了两个有趣的案例。更多的模型请看习题和参考书。1 网络通讯问题本问题取材于1994年美国大学生数学建模竞赛B题，介绍的方法主要来自于多伦多大学工业工程系一个参赛队的获特等奖的优秀论文。1） 问题的提出 在公司里，各部门每天都要分享信息。这些信息包括前一天的销售统计和当前的生产指南。尽快公布这些信息是非常重要的。假设一个通讯网络被用来从一台计算机向另一台计算机传输数据组（文件）。作为例子，考虑图5-1。图5-1 文件传输网络的例子顶点V1，V2，Vm表示计算机，边e1，e2，en表示要传输的文件，T(ex)表示传输文件ex所需的时间，C(Vy)表示计算机Vy同时能传输多少个文件的容量。文件的传输必须占用两个有关计算机为传输该文件所需的全部时间，C(Vy)=1表示计算机Vy一次只能传输一个文件。 我们有兴趣的是以最优的方式来安排传输，使得传输完所有的文件所用的总时间最少。这个总时间被称为“完工时间”（makespan）。请为你们的公司考虑以下三种情况：情形A: 你们公司有28个部门。每个部门有一台计算机，每台计算机被表示为图2中的一个顶点。每天必须传输27个文件，在图5-2中用边来表示文件传输。对于这个网络，对所有的。试找出该网络的一个最优时间表（schedule）和相应的完工时间。你们能向你们的主管人员证明你们对该网络求出的完工时间是最优的吗？叙述你们求解该问题的方法。你们的方法适用于一般情形吗，即是否适用于以及图的结构都是任意的情形？情形B： 假设你们的公司改变了传输要求。现在你必须在相同的基本网络结构（见图5-2）上考虑不同类型和数量的文件。传输这些文件所需的时间由表5-1中每条边的项表示。对全部仍有。试对新网络找出一个最优时间表和其完工时间。你们能对新网络而言所求得的完工时间是最小可能的吗？叙述你们求解该问题的方法。你们的方法适用于一般情形吗，试对任何特异的或出乎意料的结果发表评论。图5-2：情形A和B的网络情况C： 你们公司正在考虑扩展业务。如果公司这样做的话，每天有一些新文件（边）要传输。这种业务扩展还包括计算机系统的升级换代。28个部门中的某些部门将配备新的计算机使之每次能传输不止一个文件。所有这些变化都在图5-3和表5-2、表5-3中说明。你们能找到的最优时间表和完工时间是什么？你们能证明对该网络而言你们的完工时间是最小可能的吗？叙述你们求解该问题的方法。你们的方法适用于一般情形吗，试对任何特异的或出乎意料的结果发表评论。表5-1 情形B的文件传输时间数据图5-3 情形C的网络表5-2 情况C的文件传输时间数据表3 情况C的计算机容量数据问题的背景 该通讯网络问题是离散最优化学科中“时间表问题”（Scheduling problems）的一类，即在受传输时间和计算机容量等因素的限制下，使得完成全部文件传输的时间最短。该时间称为“完工时间”（makespan）。 时间表问题可按其结构不同分为许多类型。就复杂度而言，其中大多数问题属于NP困难问题，这种问题的规模一般较大，所以其最优解的寻求是很困难的。目前解决NP困难问题最常用的方法是使用一些多项式时间的近似法。为了合理地衡量这种接近程度，常用的衡量指标是“最坏情况下的性能比”。本次竞赛的问题属于规模较小的时间表问题，规模较小的离散最优化问题可以使用“穷举方法”来求出其最优解，但是NP困难问题的任何穷举方法都是指数级的。优秀论文摘要该论文利用图论的一些结果和最大匹配设计了一类方法，并证明对于情况A、B和C，所计算的结果都是最优的，对于任意图的结构和容量，所给出的方法其结果也是最优的。2) 基本概念和定理1. 图可以表示为G=(V,E)，其中V是“顶点”集，E是“边”集。无向图是指图的任何一条边(x,y)都没有方向，。图G被称为简单图，如果E的任何一条边(x,y)，都有。2. 顶点x的“次”或“度”（degree）是指与x关联的边的个数。3. 图G称为连通的，如果对每一对顶点，都存在一列边，使得，且。4.图称为图的一个“子图”，如果。5. 图G的一条“路”是指G的一个连通子图，而且子图中的两个顶点的次为1，其它顶点的次为2。6. 图G的一个连通子图被称为“圈”，如果子图中顶点的次都是2。7. 图被称为一个“二分图”，如果，X与Y是不相交的顶点集，且E中任何一边的两个端点都分别属于X和Y。二分图也表示为。8. 图G被称为“树”（tree），如果它是连通的没有圈的简单图。注意树一定是二分图。9. E的子集M被称为G的一个“匹配”，如果M中边的顶点全都互不相同。显然G中任一顶点最多与匹配M中一条边关联。10.如果G中顶点x与匹配M中一条边关联，则称x为“M饱和顶点”；反之，x被称为M不饱和顶点。11. 匹配M被称为“最大基数匹配”，如果G中没有另一匹配，使得。12. M被称为“完美匹配”，如果G中任一顶点都是M饱和顶点。显然完美匹配必是一最大基数匹配。13. 路P是匹配M的一条“交错路”，如果路P中的边交错地一条属于M，下一条不属于M。14. 匹配M的交错路P被称为M的“增广路”，如果交错路P的首尾两个端点都是M的非饱和顶点。显然增广路P的边的个数是奇数，其中不属于M的边数比属于M的边数多一个。15. 图G的边着色是指对每一条边指定一种颜色，使得没有两个相邻的边有同一种颜色。那么对图进行边着色时，所需要的最少颜色数叫做G的边色数。下面是图论中的一些重要定理。定理1：匹配M是图G的最大基数匹配，当且仅当G中没有M的增广路。定理2：二分图的边色数等于顶点的最大次。3）模型假设1、 通讯网络问题的图是无向的简单图，且任意两个顶点间没有重边这意味着任意两台计算机之间传输的全部信息可以包括在一个文件中。2、 所有的文件都为传输做好准备，也即文件的“准备时间”为零，所以通讯网络的文件传输过程可以连续地进行。3、 每一文件的传输时间都已确定，是固定的数。4、 所有的文件都是相互独立的，它们之间没有先后顺序的规定，不存在优先传输的文件。5、 任一文件在其传输时间内不能中断。一个文件一经传输，就要连续地被传输完。6、 通讯网络中的计算机在文件传输过程中都不会出现故障。4) 模型分析与建模对于情况A，由于假设了每一文件的传输时间和每一台计算机的容量，所以问题比较简单。要将所有的文件在最短的时间内传输完毕，只需将文件分批处理，批数的最小值即为完工时间。通过观察情况A的任意一种传输方案就可以发现在传输过程中每一分钟内都有一些不同的文件在传输，它们对应的是情况A的图中没有相同端点的边集，即 图5-2的一个匹配。且不同的匹配含有不同的边，它们的并即构成图5-2。这样情况A的最优传输时间表就是将图5-2分解为最少个不相重的匹配，这些匹配的个数即是最优完工时间。对于情况B来说，计算机容量仍为1，但传输时间不全为1。但是情况A和情况B的图都是树，也是二分图。只是情况B的图是加权的二分图。而情况C的图已不是二分图。解决情况B和情况C的时间表问题，本文利用了LPT算法（即加工时间最长的工作首先被处理）的基本思想，使得传输时间比较长的文件尽早被传输出去。最优传输方案必然是在文件传输的每一时刻被传输的文件个数尽量多。所以我们采取一种“动态的最大基数匹配算法”来求解通讯网络问题，并称这种方法为“局部调整方法”，它不断地对尚未传输的文件构成的子网络使用最大基数算法，且尽可能先挑选传输时间长的文件。情况A的方法基于二分图的最大基数匹配算法（参考1），设计以下方法。第一步 令E(u)是G的所有边的集合。置STAGE=1。第二步 求E(u)中的一个最大基数匹配。匹配中的边被称为已标号的。第三步 从E(u)中删除已被标号的边。第四步 如E(u)不为空集，到第五步；否则，计算中止，STAGE即为完工时间。第五步 令STAGE=STAGE+1。返回第二步。 将情况A的图表示为二分图的形式，得到图5-4。找出图5-4的最大基数匹配（见图5-5中黑色的边），该匹配中的边所对应的文件第一批传输。删除这些边，得到图5-