运筹学(简化).doc

第一部分 运筹学一、什么是运筹学？实例：一公司有：三个工厂：A、B、C。 各工厂分别有140吨、120吨、50吨产品待运；三个仓库：甲、乙、丙。甲库可存货60吨，乙库可存货100吨，丙库可存货150吨；任一工厂到仓库的路程如表： 工厂仓库ABC甲9126乙613.54.5丙1.539问：如何调运货物才能使总的吨公里最小？直观思路：1、距离最短A丙。（140吨）； 2、B丙。（10吨）；依此类推。可得调运方案： 工厂仓库ABC存货量甲6060乙5050100丙14010150供应量14012050总和310总吨公里数1401.560125013.5103504.51860。最佳方案： 工厂仓库ABC存货量甲105060乙100100丙30120150供应量14012050总和310总吨公里数1395。对该问题如果利用数学符号（即建立数学模型）来表示,可如下讨论：设工厂A向仓库甲、乙、丙的调运吨数分别为、，工厂B向仓库甲、乙、丙的调运吨数分别为、，工厂C向仓库甲、乙、丙的调运吨数分别为、，则调运货物的总吨公里数（相当于运输费用）为 现在需要求该函数的最小值，而限制条件为： 运筹学：以系统为研究对象，把系统的功能和特点用模型表示，通过对模型的定量分析，从总体上寻求最优策略，为决策和揭露新问题提供数量根据，并以研究结果的应用为目的，保证系统高效运行。运筹学建立模型的最终目的是实现系统的最优化，帮助管理者作出正确的决策，使系统正常有效地运行。这里的最优化是指在一定条件下求最优解（可以是求最大值，也可以是求最小值）。运筹学研究系统的基本方法由以下5个阶段构成：第一阶段：观察所要研究的系统，确定存在的问题、影响问题的因素、约束、假设以及准备优化的目标。第二阶段：对系统进行描述建立模型。模型的复杂程度视具体问题而定，过份简单则不能准确反映系统的实质，过份复杂则造成求解的困难。模型是所研究系统的一个理想（简化的）表达形式。一个现实系统的性质可能受到许多因素的影响，但是一般只有一小部分因素真正支配着系统的特性。建模时应该抓住这些支配系统的因素，从现实系统中抽象出一个“假想的现实系统”，然后把这些因素之间的关系确定下来，并简化成一个适合于分析的形式，这种形式就是模型。第三阶段：根据实际条件对模型进行检验。模型一旦确定，就应该根据实际条件对模型的正确性、可靠性进行分析检验。一般可按照下述三种情况之一处理：（1）给出有关方程的统一的精确解法；（2）如果没有统一解法，则可以代入具体数据进行测算，分析测算结果是否和实际情况相符；（3）如果该模型不能用任何正规的数学方法处理，则可以用类比方法进行模拟处理。第四阶段：分析模型。按优化目标的要求选取最优解，即在模型规定的约束条件下求出符合目标函数要求的最优条件组合。这一阶段还需要检验在这些约束条件下最优解的敏感程度，即弄清楚当约束条件之一稍有变化时最优解会不会改变。经过检验，就可以知道最优解对各个约束条件的依赖程度。第五阶段：贯彻执行。二、规划问题的几个基本概念：决策变量：规划问题需要求解的一组变量，这组变量的每一组定值就对应规划问题的一个具体实施方案。如上例中的；目标函数：规划问题一定有一个要求目标，并且这个要求目标可以表示为决策变量的函数，问题的解决归结为寻求一组决策变量的值，使目标函数实现最大或最小；如上例中的函数z；约束条件：每一个规划问题中，决策变量都要满足一定的约束条件，这些条件可用包含决策变量的等式或不等式表示；可行域：由约束条件所确定的决策变量的集合，可行域中的每一组决策变量的取值称为可行解，如上例中的第一个调运方案；最优解：使目标函数达到最值的可行解，如上例中的最佳方案。分 类：线性规划和非线性规划 单目标规划和多目标规划注意：1、规划问题类似于高等数学中的多元函数的最值问题，如： 例：求函数的最值，其中 决策变量：x, y 目标函数： 约束条件： 可行域：由不等式所确定的平面区域 可行域显然，可行域中的任何一个点，都满足约束条件，都是可行解，而要求的最值点应该是可行域中的最优解。2、优化问题中目标函数和决策变量必不可少，约束条件对于实际问题一般情况下也一定存在，但是在利用软件求解时，没有目标函数也可以给出结果，但是这时的结果一般只是一个可行解，并不是最优解。三、线性规划：1、线性规划的特征：目标函数和约束条件都是决策变量的线性函数。2、一般形式： 注意：1规划问题的理论求解方法很多，但是这里我们将不考虑具体理论方法，只需要掌握软件求解即可。2实际解决问题时，对于规划问题一定要对目标函数，以及每一个约束条件给于详细的解释，不要不加解释只是纯粹的罗列公式。例1 资源最优利用问题某厂生产甲、乙两种产品，需要煤、电力、水泥三种资源。生产每种产品1kt需要各种资源的数量、各种资源的限量以及生产每种产品（kt）的利润（千元）如表所示。问在这种条件下，应该安排生产甲、乙产品各多少，才能使该厂获得最大利润？ 产品单位消耗资源 甲 乙资源限量煤电力水泥2 11 20 3879产品利润4 5解：（1）问题中待确定的变量决策变量：甲、乙两种产品的生产量，（2）决策变量所受的约束。问题中受到限制的是煤、电力、水泥的数量。于是有： 煤的总需求量不能超过供应量： 电力的总需求量不能超过供应量： 水泥的总需求量不能超过供应量： 此外，甲、乙两种产品的生产量应该取非负值：，（3）建立目标函数。在三种资源供应量的限制下，合理安排两种产品的产量，使得总利润 达到最大。（4）资源最优利用问题的数学模型：求，的值，使 达到最大，并满足： 例2 物资调运问题设有两个仓库，分别储存水泥23t和27t。有三个工地各需水泥17t，18t和15t (总存货量等于总需求量)。已知各仓库到各工地的单位运费如表所示，问应如何调运，使运费最省？ 工地运费仓库 3 11 31 9 2 数学模型：求变量（从仓库运往工地的水泥数量）的值，使目标函数： 达到最小，并满足： 例3 生产安排问题某车间的车工分、两级，各级车工每人每天的加工能力、成品合格率及日工资数如表所示级别加工能力（个人天）成品合格率（）工资（元天）2401609795.55.63.6工厂要求每天至少加工配件2400个，车工每出一个废品，工厂要损失2元，现有级车工8人，级车工12人，且工厂要求至少安排6个级车工。试安排车工工作，使工厂每天支出费用最小。解：（1）决策变量：安排、两级车工的人数为，（2）分析约束条件： 车工人数限制：， 每天加工的配件总数限制： 即 特殊约束：，且为整数（3）目标函数：这个问题的目标是使工厂每天的总费用最小。包括车工的工资和因为出废品而造成的损失。每个级车工每天的费用： 工资：5.6 废品损失： 共计：20同理每个级车工每天的总费用为：18工厂每天的总费用为： 。（4）数学模型：求求，的值，使 达到最大，并满足： 四、整数规划：1、整数规划：决策变量只能取整数值。整数规划对应的线性规划：去掉整数规划中的整数限制，得到的一般线性规划。2、常见基本模型：（1）最优生产计划问题一家玩具公司制造三种玩具，每一种要求不同的制造技术，高级的一种每台需要17小时加工装配劳动力，8小时检验，利润30元。中级的每台需要2小时加工装配劳动力，半小时检验，利润5元。低级的每台需要半小时加工装配劳动力，10分钟检验，利润0.6元。可供利用的加工劳动力为500小时，检验100小时，同时，据市场预测，对高级玩具需求量不超过10台，中级不超过30台，低级不超过100台。该公司应如何安排生产计划才能使利润最大？（2）工厂选址问题有个城市，每日需要某种物资的数量分别是，先在计划要在其中选取个城市，建造座生产这种物资的工厂。假设已知若在城市建厂，日产量最多为，而建设费用为。设城市到城市的单位运价为，问这个工厂应该设在何处，才能使得既满足需要又能使总费用最省？解：设变量 ，从城市到城市运送的物资数量为，则可以建立如下数学模型： Min 使得： （3）背包问题一个背包的容积为。现有中物品可装，而每种物品都只能整件装入；物品的重量为，体积为。问如何配装，使得既不超过背包的容积，又使装的总重量最大？解：设 ，则可以建立如下数学模型： Max 使得： （4）指派问题设有项任务，恰好有个人可以分别完成其中一项，但由于各人能力不同，由不同的人去完成不同的工作所耗用的时间不同，具体所耗用的时间可用如下效率矩阵表示，问指派那个人完成那项任务，总耗时最少？ 效率矩阵：第个人完成第项任务所耗时 解：设 ，则可以建立如下数学模型： Min 满足： 3、整数规划的求解：几个结论：1整数规划无法直接求解，往往先转化为对应的线性规划求解，但是对应的线性规划的解一般不是整数规划的最优解；2对求最大的整数规划，整数规划的最优目标函数值不大于其对应的线性规划的最优目标函数值；3对求最小的整数规划，整数规划的最优目标函数值不小于其对应的线性规划的最优目标函数值；4如果将线性规划的可行域分为若干子域，则在每个子域上求得的最优值不优于整个可行域上的最优值。求解方法：分枝定界解法步骤Step1: 设原整数规划为A，对应的线性规划为A；Step2: 如果A没有可行解，则A也无可行解；Step3: 如果A有最优解，则进一步检查是否符合整数条件： 符合： 则该解就是A的最优解，程序停止； 不符合：任选一个不符合整数条件的变量，将A分解为两个问题： Step4: 分别求的最优解； Step5: 比较尚未分解的两个问题的最优解，注意其中最大的一个，若该最优值对应的解以符合整数条件，则该解就是A的最优解，停止；若该最优值对应的解不符合整数条件，则重复3继续分解。 例：问题A： 解：（1）求解A对应的线性规划A的最优解 （2）因为不满足整数条件，故可以按照变量将问题分解为 (3) 不考虑整数条件,求解以上两个问题的对应线性规划, 得最优解: : : 其中已经是整数解,故不必继续分解. 但是所对应的目标函数值不一定是原问题A的最优解, 这是因为还没有得到整数解,由所确定的原整数规划A的最优值的上界是14.33, 而由所确定的最优值为14.00, 故原问题A的最优解的目标函数值可能在14.00和14.33之间, 故仍需对进行分解. (4)考虑中非整数解将问题分解为: (5) 不考虑整数条件,求解以上两个问题的对应线性规划, 得最优解: : : 其中已是整数解,所以不必继续分解. 仍未得到整数解,故仍可对继续分解.比较已经得到的整数解对应的目标函数值以及尚未分解的目标函数值13.50, 由于所对应的目标函数值最大,故对继续分解已无意义(因为的后继问题所对应的最优目标函数值的上界是13.50, 小于14.00). 所以原问题的最优解为.五、01规划01规划是一种特殊的整数规划问题，它的全部决策变量只取0或1两个值，对它的求解可以利用整数规划的方法，也可以利用完全枚举法（n个变量的可能情况为种）。注意：1、在实际问题中，决策变量往往只有两种可能或两种状态，如，对某个建设项目投资或不投资，对某种货物购进或不购进，在某地建厂或不建厂。此时可以引入01变量，建立数学模型。2、在实际的数学建模竞赛题目中，往往决策变量中的几个属于01变量，而其余仍是普通变量，这是就不能用以上方法解决。而需要具体问题具体对待。六、非线性规划：目标函数和约束条件中至少有一个是非线性的。例1某城市要选定一个运输服务中心的位置，为该城市有固定位置的m个用户提供服务，其中k (km) 个用户要求其距离不超过d.。如何确定服务中心的位置，才能使其服务时总的费用最小？解设服务中心的坐标是，第个用户的坐标已知为，表示服务中心到第个用户的单位运价，进一步假设运输路线不受道路的影响，则可以得到以下非线性规划模型：例在传送网络上，从个电站向负载输送能量。设为第个电站产生的能量，为第个电站产生能量所需成本，为传递过程中所造成的能量损耗，为总的需求量。试确定一个最经济的产生能量方案，使需求得到满足。解最经济的产生能量方案需使总的成本最低，于是该问题中的决策变量为，则可得以下非线性规划模型：例设国民经济由个部门组成，分别编号为。已知各部门间的直接消耗系数矩阵为其中表示第部门生产价值为一单位的产品直接消耗第部门的产品的价值，。第个部门的生产函数为其中：为第个部门的总产品价值；为投入到第个部门的资金总额；为投入到第个部门的劳力数。问题是如何在给定总资金与总劳力的前提下，对每个部门进行最佳的资金及劳力投入分配，以使国民收入最大。解国民经济的各部门的总产品应该由两部分构成，一部分产品用来供给其它部门供其它部门消耗，另一部分作为该部门的最终产品。因而该部门的总产品价值也对应的应该由两部分构成。国民收入应该指国民经济的各个组成部门生产的最终产品的总价值之和。对每个部门而言，最终产品总价值可以通过总产品价值减去其它部门消耗该部门的产品价值求得。于是可设第个部门的最终产品价值为，则有以矩阵形式表示为，即其中为阶单位矩阵，。于是可得如下的非线性规划模型：第二部分 赛题选讲钢管订购和运输要铺设一条的输送天然气的主管道, 如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表：1234567800800100020002000200030001601551551601551501601单位钢管的铁路运价如下表：里程(km)300301350351400401450451500运价(万元)2023262932里程(km)5016006017007018008019009011000运价(万元)37445055601000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A19130190260100A2A3A4A5A6A7A8A11A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16A17A18A20(A21)图二A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A11A711A11A8A11A911A11A10A11A12A13A14A15S1S2S3S4S5S6S7图一钢管购运和管道铺设方案一摘要：本文解决的是一个钢管购运和管道铺设方案设计问题，目的是使总费用最小。首先利用动态规划方法求解所有钢厂到各管道节点的最小运费表，并通过分析得出从管道两边节点向中间铺路的方法可以减少铺设费用，以所有钢厂到各管道节点并向不同方向铺设的钢管数量为变量，导出总费用的表达式，把问题化为以总费用为目标函数的非线形规划，用Matlab对此进行求解。然后通过钢厂钢管销价和产量上限的微小变化及在新的条件下的求解，分析对总费用和购运计划的影响。最后把模型推广到树形管道，通过变换把它化为多条线形管道，用同样方法求解。由于计算中变量个数的增加使计算复杂度提高，我们提供了一些优化策略。在本文的末尾，我们讨论了模型的优缺点和实际应用中的改进方向。本文利用以上算法较好的解决了问题，得到了问题的最优解。对于问题一，解得最小总费用为127.86亿元，购运和铺设方案见表二。对于问题二，分析得出S6厂的钢管价格变化对总费用影响最大，S1厂的产量上限变化对总费用影响最大。对于问题三，解得最小总费用为140.66亿元，购运和铺设方案见表六。一 问题重述要铺设一条线形的天然气的运输管道，钢管由7个钢厂提供，可以由公路、铁路运往铺设地点。钢厂提供的钢管量不能超过它的产量上限，且或者大于500或者为0。公路、铁路运输费用的计算公式已经给定。在此条件下求出定购运输计划，使总费用最小。并分析钢厂钢管销价和产量上限变化对购运计划和总费用的影响。以及推广模型以解决铺设树形管道这种更一般的情形。二 模型的假设1公路运输费用为1单位钢管每公里0.1万元，不足整公里按整公里计算。2购买和运输钢管都是整单位（即为整公里）。3沿管道或者原来有公路或者建有施工公路。4一个钢厂如果承担制造钢管，至少要生产500个单位。5钢管可由铁路、公路运往铺设地点。6把“钢厂钢管的销价和产量上限变化对总费用和运购计划的影响”理解为在最优解附近的微小变化对总费用和运购计划的影响。销价最小变化是1万元，产量上限的最小变化是1个单位。三 问题分析铺设一个天然气运输管道（线形或树形），总费用包括购买钢管的费用，运费和铺设时的运费。购买钢管的费用由钢厂的钢管销价和向这个厂订购的钢管数量决定。运费由钢厂向铺设起始点运输的钢管数量和它到此起始点的运输道路决定（由于通过铁路和公路运输，所以并不仅仅由路程决定）。一般情况下铁路运输比公路运输要节省费用（只有在200公里以内，公路运输比铁路运输要节省）。对于铺设费用，在假设一的前提下，由一头出发，铺设x公里的费用的计算是：0.1*x+(x-1)+(x-2)+2+1=0.05*x*(x+1)，通过比较可以发现：铺设一段管道，从两头往中间铺比从一端向另一端铺要节省费用。再由假设三，铺设时沿管道走的是公路，所以当管道段较长时，两头铺所节省的费用是比较可观的。比如问题一中，所有管道段都从一头铺的铺设总费用为：=12.29亿元。而在最优的铺设方法下（即两头向中间铺的路程相同），铺设总费用为：=6.16亿元，最优解中的铺设费用应在这两者之间。因为铺设费用的表达式是二次式，所以求解总费用是一个非线性规划问题。四 符号说明pi：钢厂Si的钢管销售价格si：指定期限内钢厂Si能生产钢管的最大数量Li,j：从Si运到Aj，且向左边铺路的钢管数量Ri,j：从Si运到Aj，且向右边铺路的钢管数量Ti：从Si运出的钢管总量，要求Ti =500Fi, j：一单位钢管从Si运到Aj的最少费用Dx,y：相邻两点Ax,Ay之间的路程C1：购买钢管的费用C2：把钢管运送到所有Aj的总运费C3：从Aj开始铺设钢管过程中的公路运费C：总费用，C= C1+ C2+ C3ki：Si厂钢管价格对总费用的边际影响mi：Si厂钢管产量上限对总费用的边际影响五 模型的建立与求解(一) 问题一的订购和运输计划求解：1模型一的建立：由定义得：从Si运出的钢管总量：购买钢管的费用：C1=把钢管运送到所有Aj的总运费：C2=从Aj向左铺设的钢管量Lj=；向右铺设的钢管量Rj=铺设钢管过程中的公路运费：C3=0.1*目标函数(总费用)为：min(C1+ C2+ C3) s.t. Ti si，且Ti =0或Ti 500 (i=1,2,7)对相邻两点Ax,Ay有Rx+ Ly=Dx,y (x,y=1,2,15)问题即转化为对以Li,j，Ri,j为变量的非线形规划的求解。2先求出从Si运送单位钢管到Aj的最少费用Fi, j，这是一个类似求最短轨道的动态规划问题，可以仿照Dijkstra算法，特殊的是边的权以路程表示，而阶段指标是运费。求解结果列表如下： 表一：最小运费表（问题一） 单位（万元）S1S2S3S4S5S6S7A1170.7215.7230.7260.7255.7265.7275.7A2160.3205.3220.3250.3245.3255.3265.3A3140.2190.2200.2235.2225.2235.2245.2A498.6171.6181.6216.6206.6216.6226.6A538111121156146156166A620.595.5105.5140.5130.5140.5150.5A73.18696131121131141A821.271.286.2116.2111.2121.2131.2A964.2114.248.284.279.284.299.2A10921428262576277A11961468651335166A121061569661514556A13121.2171.2111.276.271.226.238.2A1412817811883731126A1514219213297872823用Matlab编程序求解目标函数，得到最优解为127.54亿元，此时从S1,S2S7运出的钢管数量为：T1=800, T2=800, T3=1000, T4=0, T5=1336, T6=990, T7=245但是由于T7=245=500的情况下分别计算。对于第一种情况，在实际计算中我们发现，只要把S7销售钢管的价格p7变的很高（比如1000万元），那么在最后的结果中肯定不会出现有S7提供钢管的情况，这样求得的结果与增加约束T7=0相同。由Matlab解得总费用为127.86亿元。对于第二种情况，求得的结果是127.97亿元。并且在两种情况下所有的Ti都满足条件，故不需要再继续求解。最优解是第一种情况，即当T7=0时。补充：如果在计算中，第二步求解得到的解仍然有Ti不满足条件，再对此Ti分几部分进行下一步求解，依次类推。最优解对应的钢管购运计划如下表：表二：钢管购运和铺设计划（问题一）S1S2S3S4S5S6S7左右左右左右左右左右左右左右A100000000000000A200104750000000000A3002260000002820000A4370950336000000000A52980000000308100000A618415000000000000A719076000000000000A8001251750000000000A9000050515900000000A1000000000321300000A11000000002701450000A120000000000751100A13000000000019913400A14000000000028633500A150000000000165000Ti80080010000136612050说明：1)表中表示从Si订购并运输到Aj的钢管数量，以及这些钢管向左和向右铺设的数量。2)虽然表中有从Si运到Aj的钢管向左和向右的分配量，实际上只要所有的钢管运到Aj后，向左和向右的铺设量与钢管的来源无关。在上表的方案下，第一问的总费用最小为127.86亿元。钢管购运和管道铺设方案二1、符号说明：钢厂在指定期限内钢管的最大产量；：到之间铺设管道的里程数；：单位钢管从钢厂运到所需最小订购和运输费用；：钢厂是否承担制造这种钢管；：钢厂运到点的钢管数量，不含路过的部分；：运到的所有钢管沿铺设的数量；：运到的所有钢管沿铺设的数量；：树中的度数；：树中的入度数；：树中的出度数；：单位钢管1公里的公路运输费用。2、基本假设：（1）假设运到的钢管，只能在和之间包含的某个区段内铺设。并且到达的钢管在和之间包含的铺设区段和到达的钢管在到之间包含的铺设区段不相交。（2）在具体铺设每一公里时，我们只把钢管运输到每一公里开始的地方，沿运送方向向前铺，然后往前铺设的运送费用不予考虑。3、模型建立：（1）决策变量：我们首先引入一组01变量，其中表示钢厂是否承担制造这种钢管，若制造，则，否则。所由钢管都是先运到后，或者转运到其他地方，或者在包含的一个区段内铺设，我们设从钢厂运抵且在包含的一个区段内铺设的钢管数量为。我们用变量表示从所有钢厂运到的钢管总量中沿铺设的部分。（2）目标函数：该问题的目的是寻求好的订购和运输方案，使得总费用最小，事实上，总费用可以分成两部分。第一部分包括钢管的订购费用和钢管从钢厂运抵所需的费用；我们用表示单位钢管从钢厂运抵所需的最小订购和运输费用，则第一部分费用为： 第二部分费用是钢管运抵后，在运到具体铺设地点的费用，由假设2，从到区段所需费用为 其中表示从到之间铺设管道的里程数，这样，第二部分费用为： （3）约束条件：首先，由于一个钢厂如果承担制造这种钢管，则至少需要生产500个单位，而钢厂在指定期限内能生产钢管的最大数量为，所以 由于订购的所有钢管总量等于的里程数，则 很显然，我们可以设 运抵的钢管总量，等于向包含的区段铺设的里程数，则 并且还有和于是可以建立非线性规划模型： Min S.t , 关于“钢管订购和运输”问题的进一步讨论：“钢管订购和运输”是一道离散优化问题，它的目标是针对天然气输送管道的铺设要求，制定使总给用最小的攻关订购运输计划。1、关于订购和运输单价的计算：要制定出使总费用最小的订购和运输计划，首先需要计算出单位长度的钢管从个钢厂到需铺设的主管道上个枢纽点的最小费用。由于钢管可以通过铁路和公路运往铺设地点，其中公路段的运费是运输里程的线性函数，而铁路段的运费则是分段阶跃函数，因此在计算时，不管对运输总里程还是对费用而言，都不具有可加性。图论中用以计算最短路的算法均失效。因此在计算时，如果要利用计算最短路的算法，必须要经过一定的调整和修改例如：(1)将图中39个点构成一个39阶方阵，表示从点到的最短路程，若, 不能直接相连，用表示，铁路自身构成另一方阵，公路自身构成方阵，分别对和运用弗洛伊德算法，得出局部最短路程矩阵和最短路径矩阵path1,path2;（2）对公路，将记为公路局部最短“距离”（运费）矩阵 对铁路，用其费用进行转换，得局部最短“距离”（运费）矩阵 令（3）对得到的A，在使用一次弗洛伊德算法，得到全局的最短距离，实际上就是每两点间最小运费矩阵。从中抽取出到之间的子矩阵；（4）为了便于计算，将的单价加到中对应的列上，得到最小费用矩阵然而，由于题意中不考虑铁路公路间转运的中转费用，也不限制转运次数，因此在自行设计的算法中很容易考虑不够周全，例如：在计算到点的购运单位时，先通过铁路（共1130公里）再通过公路（70公里），从而得到单位运费77万元的结果，但事实上，最小的单位运价应当是先通过公路（从到然后折返的路段共40公里），然后经铁路（共1100公里）在经公路（70公里）运到点，这时的单位运价为76万元。其次，对于每一段待铺设的管线中的任意铺设点P而言，从某一钢厂将钢管运到P点不外乎有通过和通过两种可能。显然，这两种走法的运费是不同的，为此，要计算到点P的费用，还应该比较这两种走法的大小，对于每一段管线，都会有一个平衡点（即两种走法运价相同的点）。在该平衡点的两侧，应该分别采用两种走法。值得注意的是，对于同一段管线，这种运价的平衡点又会因为运出钢厂的不同而异。因此决不可以将运到枢纽点和运到具体的铺设点割裂开来考虑。那种采用普通的运输问题模型先将各厂的钢管运到各枢纽点，再由起向各方向铺设的两步走的模型将是完全错误的。2、关于最小购运费用模型及求解：模型一：运输问题模型假若将待铺设的主管道全线，按照1公里作为一个单位分割成5171个点，以记一个单位钢管从运到的最小费用（含订购费），记从运到的运量（决策变量），那么，根据题意，便可构造出如下模型： 约束条件为： 其中为第i个钢厂的最大产量以及 这种模型与普通运输问题模型的区别在于约束条件，因为题目给出的要求“一个钢厂如果承担制造这种钢管，至少需要生产500个单位”。而普通的运输问题相应的约束条件则是 这个类似运输问题的模型的最大优点是其目标函数为线性函数，处理起来比较简单。而这种模型的最大缺点是规模太大，决策变量太多。一般的求解线性规划的软件会因为变量太多而无法工作。为此，可以先期比较运费将从供应商中删除，根据图形特点将供需点归类等手段，尽可能减少决策变量。应当指出，这种分析方法事实上只能针对本题的情况采用，不具有一般性。模型二：二次规划模型若记为一个单位钢管从第i个钢厂运到第j个枢纽点的最小运价，为到的运量。再把得到的钢管分解为向路段铺设和向路段铺设的两部分，记两部分的数量分别为和，路段的长度（需铺设的钢管的数量）为。于是根据题意有：从到的购运总费用为，而向两边铺设的费用为 于是问题的目标为： min+约束条件有：, , , 露天矿生产的车辆安排钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基地。许多现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务。露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多能安置一台电铲，电铲的平均装车时间为5分钟。卸货地点（以下简称卸点）有卸矿石的矿石漏、2个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。从保护国家资源的角度及矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为29.5%1%，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（8小时）内满足品位限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为3分钟。所用卡车载重量为154吨，平均时速28。卡车的耗油量很大，每个班次每台车消耗近1吨柴油。发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次。卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是满载运输。每个铲位到每个卸点的道路都是专用的宽60的双向车道，不会出现堵车现象，每段道路的里程都是已知的。一个班次的生产计划应该包含以下内容：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次（因为随机因素影响，装卸时间与运输时间都不精确，所以排时计划无效，只求出各条路线上的卡车数及安排即可）。一个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求，而一个好的计划还应该考虑下面两条原则之一： 1.总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；2.利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。请你就两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。针对下面的实例，给出具体的生产计划、相应的总运量及岩石和矿石产量。某露天矿有铲位10个，卸点5个，现有铲车7台，卡车20辆。各卸点一个班次的产量要求：矿石漏1.2万吨、倒装场1.3万吨、倒装场1.3万吨、岩石漏1.9万吨、岩场1.3万吨。铲位和卸点位置的二维示意图如下，各铲位和各卸点之间的距离（公里）如下表：铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏5.265.194.214.002.952.742.461.900.641.27倒装场1.900.991.901.131.272.251.482.043.093.51岩场5.895.615.614.563.513.652.462.461.060.57岩石漏0.641.761.271.832.742.604.213.725.056.10倒装场4.423.863.723.162.252.810.781.621.270.50各铲位矿石、岩石数量(万吨)和矿石的平均铁含量如下表：铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石量095105100105110125105130135125岩石量125110135105115135105115135125铁含量30%28%29%32%31%33%32%31%33%31%露天矿生产的车辆安排露天矿的生产调度一般都要牵涉到车辆的调度安排这样一个组合问题，目前关于这类问题，还没有好的算法求解。还属于开放性问题。一、问题分析：本题与一般的运输问题的区别： 运输矿石和岩石两种物资； 属于产量大于销量的不平衡运输问题； 为了完成品位约束，矿石要搭配运输； 产地、销地均有单位时间流量的限制； 运输车辆只有一种，每次都是满载运输，154吨车次； 铲位数多与铲车数意味着要最优的选择不多于7个产地作为最后结果中的产地； 不仅要求最佳物流，最后还要求出各条路线上的派出车辆数及安排一般情况下，一个运输问题对应着一个线性规划问题。在本问题中，以上各点对规划的影响不同，其中1第1、2、3、4条可以通过变量设计和调整约束来实现；2第5条的整数要求使得该问题变为整数规划；3第6条不容易通过线性规划实现，比较简单的方法是从个整数规划中取最优的即得到最佳物流但是这种方法的工作量非常大，几乎是不可能完成的，于是我们可以采用下面两种方法来解决：可以给每个铲位一个符号标志，这将增加10个01变量，将来通过0规划实现；先不考虑电铲数量的约束，直接来解决整数线性规划，再对解中运量最少的几个铲位进行筛选4第7条的完成可由最佳物流算出各条线路上的最少派出车辆数，然后再给出具体安排即可。解决问题的难度集中在：怎样处理在10个铲位安排7台电铲的问题；从铲位到卸点的流量均为154吨的整数倍。这个问题的核心是采用何种算法减少证书规划所耗费的时间；模型中应有道路能力约束；派车问题本质为组合优化问题，如何快速解决。露天矿生产的车辆安排模型一一、摘 要本文引入车流密度与0-1变量作为目标函数的决策变量，按原则一要求，建立了双目标非线性规划模型，通过线性加权法求解了该问题；按原则二要求，建立了单目标非线性规划模型，并求得了最优解。原则二模型的特色是：目标函数具有集合的形式。通过两模型的求解结果，按照就近组合原则与整台次原则，给出一个班次生产计划的快速算法。由所给实例，对于原则一，出动7台电铲，分别安排在铲位1