运筹学模型(一)
本章重点:线性规划基础模型、目标规划模型、运输模型及其应用、图论模型、最小树问题、最短路问题。
复习要求:1.进一步理解基本建模过程,掌握类比法、图示法以及问题分析、合理假设的内涵。
2.进一步理解数学模型的作用与特点。
本章复习重点是线性规划基础模型、运输问题模型和目标规划模型。具体说来,要求大家会建立简单的线性规划模型,把实际问题转化为线性规划模型的方法要掌握,当然比较简单。运输问题模型主要要求善于将非线性规划模型转化为运输规化模型,这种转化后求解相当简单。
你至少把一个很实际的问题转化为用**形式写出的模型,至于求解是另外一回事,一般不要求。目标模型一般是比较简单的线性规模模型在提出新的要求之后转化为目标规划模型。另外,关于图论模型的问题涉及到最短路问题,具体说来用双标号法来求解一个最短路模型。
这之前恐怕要善于将一个实际问题转化为图论模型。还有一个最小数的问题,该如何把一个网络中的最小数找到。另外在个别场合可能会涉及一笔划问题。
1.营养配餐问题的数学模型。
或更简洁地表为。
其中的常数c表示第j种食品的市场**,a表示第j种食品含第i种营养的数量,b表示人或动物对第i种营养的最低需求量。
2.合理配料问题的数学模型。
有m种资源b1,b2,…,bm,可用于生产n种代号为a1,a2,…,an的产品。单位产品aj需用资源bi的数量为aij,获利为cj单位,第i种资源可供给总量为bi个单位。问如何安排生产,使总利润达到最大?
设生产第j种产品xj个单位(j=1,2,…,n),则有。
或更简单地写为。
3.运输问题模型。
运输问题也是一种线性规划问题,只是决策变量设置为双下标变量。假如问题具有m个产地和n个销地,第i个产地用ai表示,其产量为ai(i=1,2,…,m),第j个销地用bj表示,其销量为bj (j=1,2,…,n),从ai运往bj的运价为cij, 而表示产销平衡。那么产销平衡运输问题的一般模型可以写成为。
4.目标规划模型。
某工厂生产代号为ⅰ、ⅱ的两种产品,这两种产品都要经甲、乙两个车间加工,并经检验与销售两部门处理。已知甲、乙两车间每月可用生产工时分别为120小时和150小时,每小时费用分别为80元和20元,其它数据如下表。
表4-1工厂领导希望给出一个可行性生产方案,使生产销售及检验等方面都能达标。
问题分析与模型假设。
经与工厂总经理交谈,确定下列几条:
p1: 检验和销售费每月不超过4600元;
p2: 每月售出产品i不少于50件;
p3: 两车间的生产工时充分利用(重要性权系数按两车间每小时费用比确定);
p4:甲车间加班不超过20小时;
p5:每月售出产品ⅱ不少于80件;
p6:两车间加班总时数要有控制(对权系数分配参照第三优先级).
模型建立。设x1,x2分别为产品ⅰ和ⅱ的月产量,先建立一般约束条件组,依题设。
检验销售费用。
设d1表检验销售费偏差,则希望达最小,有相应的目标约束为。
表产品i售量偏差,则希望达最小,有相应的目标约束。
以d3、d4表两车间生产工时偏差,则由于充分利用,故希望达最小,考虑到费用比例为80:20=4:1,有。相应的目标约束应为。
和=150,以d5表甲车间加班偏差,则有相应目标约束为,以d6表产品ⅱ售量偏差,则希望达最小,有相应约束为。
最后优先级p6可利用表示,考虑到权系数,有其目标约束由于利用超生产工时,已在工时限制中体现,于是得到该问题的目标规划模型为。
5.最小树问题。
一个图中若有几个顶点及其边的交替序列形成闭回路,我们就说这个图有圈;若图中所有连顶点间都有边相接,就称该图是连通的;若两个顶点间有不止一条边连接,则称该图具有多重边。
一个图被称为是树意味着该图是连通的无圈的简单图。
在具有相同顶点的树中,总赋权数最小的树称为最小树。
最小树的求法有两种,一种称为“避圈法”,一种是“破圈法”,两法各具优缺点,它们具有共同的特征——去掉图中的圈并且每次都是去掉圈中边权较大的边。
6.最短路问题的数学模型。
最短路问题一般描述如下:在一个图(或者说网络)中,给定一个始点vs和一个终点vt,求vs到vt的一条路,使路长最短(即路的各边权数之和最小).
狄克斯屈()双标号法。
该法亦称双标号法,适用于所有权数均为非负(即一切 wij表示顶点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=为固定标号点集,为临时标号点集,再令,;
2°检查点vi,对其一切关联边(vi, vj)的终点,计算并令。
3°从一切中选取并令。
选取相应的弧(vi, vr).再令。
4°若,则停止,即vs到vj的最短路长,特别即vs到vt的最短路长,而已选出的弧即给出vs到各点的最短路;否则令,返2°.
注意:若只要求vs到某一点vt的最短路,而没要求vs到其他各点的最短路,则上述步骤4°可改为。
4°若r = t则结束,即为所求最短路长;否则令,返2°.
数学建模运筹学模型 四
运筹学模型 四 三 计算题。1.某医院为病人配制营养餐要使用到两种食品a和b,每种食品a含蛋白质50g,钙400mg,热量1000单位,价值14元 食品b含蛋白质60g,钙200mg,热量800单位,价值8元。若病人每天需从食物中获取蛋白质,钙及热量分别为55g,800mg和3000单位,问如何选购...
运筹学模型
第5章运筹学模型。5.2 图论模型。图论是运筹学的一个重要分支,它是建立和处理离散类数学模型的一个重要工具。用图论的方法往往能帮助人们解决一些用其它方法难于解决的问题。图论的发展可以追溯到1736年欧拉所发表的一篇关于解决著名的 哥尼斯堡七桥问题 的 由于这种数学模型和方法直观形象,富有启发性和趣味...
运筹学模型
源于第二次世界大战期间的运筹学研究,有效地解决了如何将有限的资源分配于各项军事活动,以取得最优的战争效果等重大军事决策问题,为盟军取得二战的胜利作出了不可磨灭的贡献。战后,该项技术不但在军事科学上不断发展,在工农业生产 科学实验 工程技术 经济管理和社会科学中都有着广泛的应用和发展。特别是计算机技术...