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

1、.运筹学模型（一）本章重点 ：线性规划基础模型、目标规划模型、运输模型及其应用、图论模型、最小树问题、最短路问题复习要求：1. 进一步理解基本建模过程，掌握类比法、图示法以及问题分析、合理假设的内涵.2. 进一步理解数学模型的作用与特点.本章复习重点是线性规划基础模型、运输问题模型和目标规划模型. 具体说来， 要求大家会建立简单的线性规划模型， 把实际问题转化为线性规划模型的方法要掌握，当然比较简单 . 运输问题模型主要要求善于将非线性规划模型转化为运输规化模型， 这种转化后求解相当简单 . 你至少把一个很实际的问题转化为用表格形式写出的模型， 至于求解是另外一回事， 一般不要求 . 目标模型

2、一般是比较简单的线性规模模型在提出新的要求之后转化为目标规划模型 . 另外，关于图论模型的问题涉及到最短路问题， 具体说来用双标号法来求解一个最短路模型 . 这之前恐怕要善于将一个实际问题转化为图论模型 . 还有一个最小数的问题，该如何把一个网络中的最小数找到 . 另外在个别场合可能会涉及一笔划问题 .1. 营养配餐问题的数学模型min ZC1 x1C 2 xC n xna11 x1a12 x2a1n xnb1 ,a21 x1a22 x2a2 n xnb2 ,stam1 x1am 2 x2amn xnbm ,x j0( j1,2, n)或更简洁地表为nmin ZC jxjj1naijx jbi

3、s tj 1i1,2, mx j0(j1,2,), n其中的常数 C j 表示第 j 种食品的市场价格，a ij 表示第 j 种食品含第 i 种营养的数量， bi 表示人或动物对第 i种营养的最低需求量 .2. 合理配料问题的数学模型有种资源1， 2， ， m，可用于生产n种代号为1， 2， ，n 的产品 . 单位产品j 需用资源i 的mBBBAAAAB数量为aij ，获利为j 单位，第i种资源可供给总量为i个单位 . 问如何安排生产，使总利润达到最大？Cb设生产第 j种产品xj 个单位（ j =1， 2， ， n），则有max ZC1 x1C2 x2C n xn.a11 x1a12 x2a1

4、n xnb1 ,a21 x1a22 x2a2n xnbl ,stam1x1am2 x2amn xnbm ,x j0( j1,2,n)或更简单地写为nmax zC j x jj1naijx jbisj 1ti1,2, mx j01,2, nj3. 运输问题模型运输问题也是一种线性规划问题，只是决策变量设置为双下标变量. 假如问题具有 m个产地和 n个销地，第i个产地用i表示，其产量为i （i=1，2， ， ），第j个销地用j 表示，其销量为j （=1，2， ，AamBb jmn），从i 运往j的运价为cij ， 而aib j表示产销平衡 . 那么产销平衡运输问题的一般模型可以nABi1j1写成为

5、mnmin Zcij xiji 1j 1nxijaij1mstxijb ji1xij0i1,2, mj1,2, n4. 目标规划模型某工厂生产代号为、的两种产品，这两种产品都要经甲、乙两个车间加工，并经检验与销售两部门处理 . 已知甲、乙两车间每月可用生产工时分别为 120 小时和 150 小时，每小时费用分别为 80 元和 20 元，其它数据如下表表 4-1项目甲车间加工乙车间加工检验销售利 润数据（时/件）（元/ 件）（元/件）（时/件）产品2150100133075.工厂领导希望给出一个可行性生产方案，使生产销售及检验等方面都能达标.问题分析与模型假设经与工厂总经理交谈，确定下列几条：p

6、1： 检验和销售费每月不超过4600 元；2： 每月售出产品 I 不少于 50件；p3： 两车间的生产工时充分利用（重要性权系数按两车间每小时费用比确定）；pp4：甲车间加班不超过 20 小时；p5：每月售出产品不少于80 件；6：两车间加班总时数要有控制（对权系数分配参照第三优先级）.p模型建立设 x1 ，x2 分别为产品和的月产量，先建立一般约束条件组，依题设50 x1 30x2 4600x150检验销售费用售出量x2802x1x2120两车间总工时x13x2150设 d1 表检验销售费偏差，则希望d1 达最小，有p1d1, 相应的目标约束为5x130 x2d1d1= 4600 ；d 2

7、表产品 I售量偏差，则希望d2 达最小，有p2 d2 , 相应的目标约束x1d 2d 250,以 d3 、d4 表两车间生产工时偏差，则由于充分利用，故希望d3 , d4 达最小，考虑到费用比例为80：20=4：1，有 p3 (4d 3d 4 ) . 相应的目标约束应为2x1x2d3d3120 和 x1 3x2d4d 4 =150，以 d5 表甲车间加班偏差，则有p4 d5 , 相应目标约束为d 3d 5d520 ，以 d6 表产品售量偏差，则希望d6 达最小，有相应约束为x2d6d680 .最后优先级 p6 可利用 d 3d4 表示，考虑到权系数， 有 p6 (4d3d 4 ), 其目标约束

8、由于利用超生.产工时，已在工时限制中体现，于是得到该问题的目标规划模型为min zp1d1p2 d 2p3 (4d 3d4 )p4d 5p5 d 6 p6 ( 4d3 d4 )50x130 x2d1d14600x1d2d2502x1x2d 3d 3120s tx13x2d 4d 4150d3d 5d 520x2d6d680x1, x20, dl, d l0(l 1,2,6)5. 最小树问题一个图中若有几个顶点及其边的交替序列形成闭回路，我们就说这个图有圈；若图中所有连顶点间都有边相接，就称该图是连通的；若两个顶点间有不止一条边连接，则称该图具有多重边.一个图被称为是树意味着该图是连通的无圈的简

9、单图.在具有相同顶点的树中，总赋权数最小的树称为最小树.最小树的求法有两种，一种称为“避圈法”，一种是“破圈法” ，两法各具优缺点，它们具有共同的特征去掉图中的圈并且每次都是去掉圈中边权较大的边.6. 最短路问题的数学模型最短路问题一般描述如下：在一个图（或者说网络）中，给定一个始点vs 和一个终点vt ，求s 到tvv的一条路，使路长最短（即路的各边权数之和最小）.狄克斯屈（ E.D.Dijkstra）双标号法该法亦称双标号法，适用于所有权数均为非负（即一切w0ij表示顶点vi 与vj的边的权数）的ijw网络，能够求出网络的任一点vs 到其它各点的最短路，为目前求这类网络最短路的最好算法.该

10、法在施行中，对每一个点vj 都要赋予一个标号，并分为固定标号（j）和临时标号（j ）两种，P vT v其含义如下：（j ）从始点vs到vj 的最短路长；P vT（ vj ）从始点vs 到 vj 的最短路长上界 .一个点 vj 的标号只能是上述两种标号之一. 若为 T 标号，则需视情况修改， 而一旦成为 P 标号，就固定不变了 .开始先给始点vs 标上P标号 0，然后检查点vs，对其一切关联边（vs，vj ）的终点j，给出vj 的T标v号ij ；再在网络的已有T标号中选取最小者，把它改为P标号 . 以后每次都检查刚得到P标号那点，按一w定规则修改其一切关联边终点的T 标号，再在网络的所有T 标号

11、中选取最小者并把它改为P标号 . 这样，每次都把一个 T 标号点改为 P 标号点，因为网络中总共有n 个结点，故最多只需n-1次就能把终点 vt 改为 P标号 . 这意味着已求得了vs 到 vt 的最短路 .狄克斯屈标号法的计算步骤如下：1°令 =vs 为固定标号点集，S V vs 为临时标号点集，再令 P(vi )0 ， vtS ；S2°检查点vi ，对其一切关联边（vi ， v j ）的终点 v jS ，计算并令min T (v j ), P(vi ) wij T ( vj ).3°从一切 v jS 中选取并令min T (v j )T (vr ) T (vr )选取相应的弧（ vi ， v r ）. 再令S vr S, S vr S4°若 S，则停止， P(v j ) 即 vs 到 vj 的最短路长，特别P(vt