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

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

2、新的要求之后转化为目标规划模型.另外,关于图论模型的问题涉及到最短路问题,具体说来用双标号法来求解一个最短路模型.这之前恐怕要善于将一个实际问题转化为图论模型.还有一个最小数的问题,该如何把一个网络中的最小数找到.另外在个别场合可能会涉及一笔划问题.1 .营养配餐问题的数学模型miZn=C1x1+C2x+Cnxn?a11x1+a12x2+a1nxnb?,a21x1+a22x2+a2nxn?s?b2,?ax+ax+axb,m22mmn1m?xj0(j=1,2,n或更简洁地表为miZn=ECxjj=1nj?n?Eaijxj?j=1S?t?x0(i=1,2,m?jj=1,2,n?其中的常数Cj表示第

3、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),那么有maZx=C1x1+C2x2+Cnxn?a11x1+a12x2+a1nxn?ba121x1+a22x2+a2nxn?s?电bl,?ax+ax+ax0(j=1,2,n或更简单地写为mazx=Z2Cj=1njxj?n?Eaijxj

4、?j=1bsi?t?i=1,2,m?x0j=1,2,?j?3.运输问题模型运输问题也是一种线性规划问题,只是决策变量设置为双下标变量.假设问题具有m个产地和n个销地,第i个产地用Ai表示,其产量为ai(i=1,2,m),第j个销地用Bj表示,其销量为bj(j=1,2,n),从Ai运往Bj的运价为cij,而写成为Eai=1mi=Ebj加产销平衡.那么产销平衡运输问题的一般模型可以minZ=ZjZjcijxij1 =1j=1mn?n?Exij=ai?j=1?ms?t?Exij=bj?i=1?i=1,2,m?xij0j=1,2?4.目标规划模型某工厂生产代号为I、R的两种产品,这两种产品都要经甲、乙

5、两个车间加工,并经检验与销售两部门处理.甲、乙两车间每月可用生产工时分别为120小时和150小时,每小时费用分别为80元和20元,其它数据如下表表4-1产、甲车间加工乙车间加工(时/许)检验错S?元州0利涮?死/件)1个1100n1330T5工厂领导希望给出一个可行性生产方案,使生产销售及检验等方面都能达标问题分析与模型假设经与工厂总经理交谈,确定以下几条：p1:检验和销售费每月不超过4600元；p2:每月售出产品I不少于50件；p3:两车间的生产工时充分利用重要性权系数按两车间每小时费用比确定；p4:甲车间加班不超过20小时；p5:每月售出产品II不少于80件；p6:两车间加班总时数要有限制

6、对权系数分配参照第三优先级模型建立设x1,x2分别为产品I和R的月产量,先建立一般约束条件组,依题设50x1+30x2x2802x1+x2飘初向总工时x1+3x20,dl,dl0=4600=50=120=150=20=80(l=1,2,65 .最小树问题一个图中假设有几个顶点及其边的交替序列形成闭回路,我们就说这个图有圈；假设图中所有连顶点间都有边相接,就称该图是连通的；假设两个顶点间有不止一条边连接,那么称该图具有多重边.一个图被称为是树意味着该图是连通的无圈的简单图.在具有相同顶点的树中,总赋权数最小的树称为最小树最小树的求法有两种,一种称为避圈法,一种是被圈法,两法各具优缺点,它们具有共

7、同的特征一一去掉图中的圈并且每次都是去掉圈中边权较大的边.6 .最短路问题的数学模型最短路问题一般描述如下：在一个图(或者说网络)中,给定一个始点vs和一个终点vt,求vs到vt的一条路,使路长最短(即路的各边权数之和最小).狄克斯屈(E.D.Dijkstra)双标号法该法亦称双标号法,适用于所有权数均为非负(即一切wij0w表示顶点vi与vj的边的权数)的网络,能够求出网络的任一点vs到其它各点的最短路,为目前求这类网络最短路的最好算法.该法在施行中,对每一个点vj都要赋予一个标号,并分为固定标号P(vj)和临时标号T(vj)两种,其含义如下：P(vj)从始点vs到vj的最短路长；T(vj)

8、从始点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为固定标号点集,=Vvs为临时标号点集,再令P(vi=0,vtCS;2检查点vi,对其一切关联边(vi,vj)的终点vjC,计算并令minT(vj,P(vi+wij?T(vj3从一切vjC中选取并令minT(vj=T(vr?T(vr选取相应的弧(vi,vr).再令Svr?S,vr?=?,那么停止,P(vj即vs至IJvj的最短路长,特另IP(v