数学建模运筹学模型(一)

运筹学模型（一）本章重点：线性规划基础模型、目标规划模型、运输模型及其应用、图论模型、最小树问题、最短路问题复习要求：1.进一步理解基本建模过程，掌握类比法、图示法以及问题分析、合理假设的内涵.2.进一步理解数学模型的作用与特点.本章复习重点是线性规划基础模型、运输问题模型和目标规划模型.具体说来，要求大家会建立简单的线性规划模型，把实际问题转化为线性规划模型的方法要掌握，当然比较简单.运输问题模型主要要求善于将非线性规划模型转化为运输规化模型，这种转化后求解相当简单.你至少把一个很实际的问题转化为用表格形式写出的模型，至于求解是另外一回事，一般不要求.目标模型一般是比较简单的线性规模模型在提出新的要求之后转化为目标规划模型.另外，关于图论模型的问题涉及到最短路问题，具体说来用双标号法来求解一个最短路模型.这之前恐怕要善于将一个实际问题转化为图论模型.还有一个最小数的问题，该如何把一个网络中的最小数找到.另外在个别场合可能会涉及一笔划问题.1.营养配餐问题的数学模型nnxCxCxCZ211min),,2,1(0,,,22112222212111212111njxbxaxaxabxaxaxabxaxaxatsjmnmnmmnnnn或更简洁地表为njjjxCZ1min),,2,1,,2,1(01njmixbxatsjnjijij其中的常数Cj表示第j种食品的市场价格，aij表示第j种食品含第i种营养的数量，bi表示人或动物对第i种营养的最低需求量.2.合理配料问题的数学模型有m种资源B1，B2，…，Bm，可用于生产n种代号为A1，A2，…，An的产品.单位产品Aj需用资源Bi的数量为aij，获利为Cj单位，第i种资源可供给总量为bi个单位.问如何安排生产，使总利润达到最大？设生产第j种产品xj个单位（j=1，2，…，n），则有nnxCxCxCZ2211max),,2,1(0,,,2211222212111212111njxbxaxaxabxaxaxabxaxaxatsjmnmnmmlnnnn或更简单地写为njjjxCz1maxnjmixbxatsjnjijij,,2,1,,2,1013.运输问题模型运输问题也是一种线性规划问题，只是决策变量设置为双下标变量.假如问题具有m个产地和n个销地，第i个产地用Ai表示，其产量为ai（i=1，2，…，m），第j个销地用Bj表示，其销量为bj（j=1，2，…，n），从Ai运往Bj的运价为cij，而minjjiba11表示产销平衡.那么产销平衡运输问题的一般模型可以写成为minjijijxcZ11minnjmixbxaxtsijmijijnjiij,,2,1,,2,10114.目标规划模型某工厂生产代号为Ⅰ、Ⅱ的两种产品，这两种产品都要经甲、乙两个车间加工，并经检验与销售两部门处理.已知甲、乙两车间每月可用生产工时分别为120小时和150小时，每小时费用分别为80元和20元，其它数据如下表表4-1项目数据产品甲车间加工（时/件）乙车间加工（时/件）检验销售（元/件）利润（元/件）Ⅰ2150100Ⅱ133075工厂领导希望给出一个可行性生产方案，使生产销售及检验等方面都能达标.问题分析与模型假设经与工厂总经理交谈，确定下列几条：p1：检验和销售费每月不超过4600元；p2：每月售出产品I不少于50件；p3：两车间的生产工时充分利用（重要性权系数按两车间每小时费用比确定）；p4：甲车间加班不超过20小时；p5：每月售出产品Ⅱ不少于80件；p6：两车间加班总时数要有控制（对权系数分配参照第三优先级）.模型建立设x1，x2分别为产品Ⅰ和Ⅱ的月产量，先建立一般约束条件组，依题设4600305021xx检验销售费用501x802x120221xx150321xx设d1表检验销售费偏差，则希望1d达最小，有,11dp相应的目标约束为1121305ddxx=4600；2d表产品I售量偏差，则希望2d达最小，有,22dp相应的目标约束,50221ddx以d3、d4表两车间生产工时偏差，则由于充分利用，故希望43,dd达最小，考虑到费用比例为80：20=4：1，有)4(433ddp.相应的目标约束应为12023321ddxx和44213ddxx=150，以d5表甲车间加班偏差，则有,54dp相应目标约束为20553ddd，以d6表产品Ⅱ售量偏差，则希望6d达最小，有相应约束为80662ddx.最后优先级p6可利用43dd表示，考虑到权系数，有),4(436ddp其目标约束由于利用超生售出量两车间总工时产工时，已在工时限制中体现，于是得到该问题的目标规划模型为65544332211)4(mindpdpddpdpdpz)4(436ddp)6,,2,1(0,,0,802015031202504600305021662553442133212211121lddxxddxdddddxxddxxddxddxxtsll5.最小树问题一个图中若有几个顶点及其边的交替序列形成闭回路，我们就说这个图有圈；若图中所有连顶点间都有边相接，就称该图是连通的；若两个顶点间有不止一条边连接，则称该图具有多重边.一个图被称为是树．意味着该图是连通的无圈的简单图.在具有相同顶点的树中，总赋权数最小的树称为最小树.最小树的求法有两种，一种称为“避圈法”，一种是“破圈法”，两法各具优缺点，它们具有共同的特征——去掉图中的圈并且每次都是去掉圈中边权较大的边.6.最短路问题的数学模型最短路问题一般描述如下：在一个图（或者说网络）中，给定一个始点vs和一个终点vt，求vs到vt的一条路，使路长最短（即路的各边权数之和最小）.狄克斯屈（E.D.Dijkstra）双标号法该法亦称双标号法，适用于所有权数均为非负（即一切0ijwwij表示顶点vi与vj的边的权数）的网络，能够求出网络的任一点vs到其它各点的最短路，为目前求这类网络最短路的最好算法.该法在施行中，对每一个点vj都要赋予一个标号，并分为固定标号P（vj）和临时标号T（vj）两种，其含义如下：P（vj）——从始点vs到vj的最短路长；T（vj）——从始点vs到vj的最短路长上界.一个点vj的标号只能是上述两种标号之一.若为T标号，则需视情况修改，而一旦成为P标号，就固定不变了.开始先给始点vs标上P标号0，然后检查点vs，对其一切关联边（vs，vj）的终点vj，给出vj的T标号wij；再在网络的已有T标号中选取最小者，把它改为P标号.以后每次都检查刚得到P标号那点，按一定规则修改其一切关联边终点的T标号，再在网络的所有T标号中选取最小者并把它改为P标号.这样，每次都把一个T标号点改为P标号点，因为网络中总共有n个结点，故最多只需n-1次就能把终点vt改为P标号.这意味着已求得了vs到vt的最短路.狄克斯屈标号法的计算步骤如下：1°令S={vs}为固定标号点集，}{\svVS为临时标号点集，再令0)(ivP，Svt；2°检查点vi，对其一切关联边（vi，vj）的终点Svj，计算并令)(})(),(min{jijijvTwvPvT3°从一切Svj中选取并令)()()}(min{rrjvTvTvT选取相应的弧（vi，vr）.再令SvSSvSrr}{\,}{4°若S，则停止，)(jvP即vs到vj的最短路长，特别)(tvP即vs到vt的最短路长，而已选出的弧即给出vs到各点的最短路；否则令irvv，返2°.注意：若只要求vs到某一点vt的最短路，而没要求vs到其他各点的最短路，则上述步骤4°可改为4°若r=t则结束，)(rvP即为所求最短路长；否则令irvv，返2°.