数学建模运筹学模型一

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

2、线性规模模型在提出新的要求之后转化为目标规划模型. 另外，关于图论模型的问题涉及到最短路问题，具体说来用双标号法来求解一个最短路模型. 这之前恐怕要善于将一个实际问题转化为图论模型. 还有一个最小数的问题，该如何把一个网络中的最小数找到. 另外在个别场合可能会涉及一笔划问题.1. 营养配餐问题的数学模型或更简洁地表为其中的常数C j 表示第 j 种食品的市场价格， a ij 表示第 j 种食品含第i 种营养的数量， b i 表示人或动物对第i 种营养的最低需求量 .2. 合理配料问题的数学模型有m种资源1， 2 ， ，m，可用于生产n种代号为1 ， 2， ，n 的产品 . 单位产品j 需用资源

3、i 的数量为ij ，获利为j 单B BBA AAABaC位，第 i 种资源可供给总量为bi 个单位 . 问如何安排生产，使总利润达到最大？设生产第 j种产品 xj 个单位（ j =1，2， ， n），则有或更简单地写为3. 运输问题模型运输问题也是一种线性规划问题， 只是决策变量设置为双下标变量. 假如问题具有 m个产地和 n 个销地，第 i 个产地用Ai表示，mn其产量为a（ii=1，2， ， ），第个销地用j 表示，其销量为j （=1，2， ， ），从 i 运往j 的运价为cij ， 而aibjmjBb jnABi1j1表示产销平衡 . 那么产销平衡运输问题的一般模型可以写成为4. 目标规

4、划模型某工厂生产代号为、的两种产品，这两种产品都要经甲、乙两个车间加工，并经检验与销售两部门处理. 已知甲、乙两车间每月可用生产工时分别为120 小时和 150 小时，每小时费用分别为80 元和 20 元，其它数据如下表表 4-1项目甲车间加工乙车间加工检验销售利 润数据（时/ 件）（元 /件）（元/件）（时/ 件）产品2150100133075工厂领导希望给出一个可行性生产方案，使生产销售及检验等方面都能达标.问题分析与模型假设经与工厂总经理交谈，确定下列几条：p1 ： 检验和销售费每月不超过4600 元；p2 ： 每月售出产品I 不少于 50 件；p3 ： 两车间的生产工时充分利用（重要性

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

6、最小，考虑到费用比例为80：20=4：1，有 p3 (4d3d 4 ) .d相应的目标约束应为2x1x2d3d3120 和 x1 3x2d 4d 4=150，以 d5 表甲车间加班偏差，则有p4 d5 , 相应目标约束为d3d5d520 ，以 d6 表产品售量偏差，则希望d6 达最小，有相应约束为x2d6d680 .最后优先级p6 可利用 d3d4 表示，考虑到权系数，有p6 ( 4d3d4 ), 其目标约束由于利用超生产工时，已在工时限制中体现，于是得到该问题的目标规划模型为5. 最小树问题一个图中若有几个顶点及其边的交替序列形成闭回路，我们就说这个图有圈；若图中所有连顶点间都有边相接，就称

7、该图是连通的；若两个顶点间有不止一条边连接，则称该图具有多重边.一个图被称为是树 意味着该图是连通的无圈的简单图.在具有相同顶点的树中，总赋权数最小的树称为最小树.最小树的求法有两种，一种称为“避圈法”，一种是“破圈法” ，两法各具优缺点，它们具有共同的特征去掉图中的圈并且每次都是去掉圈中边权较大的边.6. 最短路问题的数学模型最短路问题一般描述如下：在一个图（或者说网络）中，给定一个始点vs 和一个终点 vt ，求 vs 到 vt 的一条路，使路长最短（即路的各边权数之和最小） .狄克斯屈（）双标号法该法亦称双标号法，适用于所有权数均为非负（即一切wij 0wij表示顶点 vi 与 vj 的

8、边的权数）的网络，能够求出网络的任一点 vs 到其它各点的最短路，为目前求这类网络最短路的最好算法.该法在施行中，对每一个点vj 都要赋予一个标号，并分为固定标号（j ）和临时标号（j ）两种，其含义如下：PvT v（ j ）从始点vs 到vj 的最短路长；P v（ j ）从始点vs 到vj 的最短路长上界 .T v一个点 vj 的标号只能是上述两种标号之一. 若为 T 标号，则需视情况修改，而一旦成为P 标号，就固定不变了 .P 标号点，因为网络中总共有开始先给始点vs 标上 P 标号 0，然后检查点vs，对其一切关联边（vs， v j ）的终点 vj ，给出 vj 的 T 标号标号中选取最

9、小者，把它改为P 标号 . 以后每次都检查刚得到P标号那点，按一定规则修改其一切关联边终点的的所有 T 标号中选取最小者并把它改为P 标号 . 这样，每次都把一个T 标号点改为wij ；再在网络的已有TT 标号，再在网络n 个结点，故最多只需 n-1 次就能把终点vt 改为 P 标号 . 这意味着已求得了vs 到 vt 的最短路 .狄克斯屈标号法的计算步骤如下：1°令 S= vs 为固定标号点集，SV vs 为临时标号点集，再令 P( vi )0 ， vtS ；2°检查点i ，对其一切关联边（vi ，vj ）的终点v jS ，计算并令v3°从一切 vjS 中选取并令选取相应的弧（vi ， v r） . 再令4°若 S，则停止， P( vj) 即 vs 到 vj 的最短路长，特别P(vt ) 即 vs 到 vt 的最短路长，而已选出的弧即给出v