数学建模学习辅导

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

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

3、生产，使总利润达到最大？设生产第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、据如下表表41项目数据产品甲车间加工（时/件）乙车间加工（时/件）检验销售（元/件）利 润（元/件）2150100133075工厂领导希望给出一个可行性生产方案，使生产销售及检验等方面都能达标.问题分析与模型假设经与工厂总经理交谈，确定下列几条：p1: 检验和销售费每月不超过4600元；p2: 每月售出产品I不少于50件；p3: 两车间的生产工时充分利用（重要性权系数按两车间每小时费用比确定）；p4：甲车间加班不超过20小时；p5：每月售出产品不少于80件；p6：两车间加班总时数要有控制（对权系数分配参照第三优先级）.模型建立设x1,x2分别为产品和的月产量,先建立一般约束条件组,依题设检验销

5、售费用售出量两车间总工时设d1表检验销售费偏差，则希望达最小，有相应的目标约束为 = 4600；表产品I售量偏差，则希望达最小，有相应的目标约束以d3、d4表两车间生产工时偏差，则由于充分利用，故希望达最小，考虑到费用比例为80：20=4：1，有.相应的目标约束应为和=150，以d5表甲车间加班偏差,则有相应目标约束为，以d6表产品售量偏差，则希望达最小，有相应约束为最后优先级p6可利用表示，考虑到权系数,有其目标约束由于利用超生产工时,已在工时限制中体现,于是得到该问题的目标规划模型为5最小树问题一个图中若有几个顶点及其边的交替序列形成闭回路，我们就说这个图有圈；若图中所有连顶点间都有边相接

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

7、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标号中选取最小

8、者并把它改为P标号这样，每次都把一个T标号点改为P标号点，因为网络中总共有n个结点，故最多只需n-1次就能把终点vt改为P标号这意味着已求得了vs到vt的最短路狄克斯屈标号法的计算步骤如下：1°令S=vs为固定标号点集，为临时标号点集，再令，；2°检查点vi，对其一切关联边（vi, vj）的终点,计算并令3°从一切中选取并令选取相应的弧（vi, vr）再令4°若，则停止，即vs到vj的最短路长，特别即vs到vt的最短路长，而已选出的弧即给出vs到各点的最短路；否则令，返2°注意：若只要求vs到某一点vt的最短路，而没要求vs到其他各点的最短路，

9、则上述步骤4°可改为4°若r = t则结束，即为所求最短路长；否则令，返2°. 典型例题 一、填空题： A 1如图1是一个邮路，邮递员从邮局A出发走遍所有正方形街路后再返回邮局若每个小正方形街路的边长均为1km，则他至少要走km解：本题属于图模型中的一笔画问题由于图中奇点个数为8个，故不可能一笔画出相邻奇点间都连上一条边（边长均为1）， 图1便使奇点个数变成零从而可以一笔画出，由此可知邮递员至少要走3´4´2+4 = 28（km）应该填写：28（km） 2设某种物资有两个产地，其产量分别为10、20，两个销地的销量相等均为15如果从任意产地到任

10、意销地的单位运价都相等为a，则最优运输方案与运价具有 两个特点解：因为该问题从任意产地到任意销地的单位运价都相等故其具有最优运输方案不惟一；总运费均相等特点应该填写： 最优运输方案不惟一；总运费均相等二、分析判断题： 1一家保姆公司专门向顾主提供保姆服务根据估计，下一年的需求是：春季6000人日，夏季7500人日，秋季5500人日，冬季9000人日公司新招聘的保姆必须经过5天的培训才能上岗，每个保姆每季度工作（新保姆包括培训）65天，保姆从该公司而不从顾主那里得到报酬，每人每月工作800元春季开始时公司拥有120名保姆，在每个季度结束后，将有15%的保姆自动离职 （1）如果公司不允许解雇保姆，

11、请你为公司制定下一年的招聘计划（建立数学模型） （2）如果在每个季度结束后允许解雇保姆，请为公司制定下一年的招聘计划（建立数学模型） 解：（1）设4个季度开始时公司新招聘的保姆数量分别为x1, x2, x3, x4人，4个季度开始时保姆总数量分别为S1, S2, S3, S4人以本年度付出的总报酬最少（即4个季度开始时保姆总数量之和最小）为目标，则模型为s.t. （2）设4个季度开始时公司新招聘的保姆数量分别为x1, x2, x3, x4人，4个季度结束时解雇的保姆数量分别为y1, y2, y3, y4人，4个季度开始时保姆总数量分别为S1, S2, S3, S4人以本年度付出的总报酬最少（即

12、4个季度开始时保姆总数量之和最小）为目标，则模型为s.t. 2在文字教材4.1中给出了营养配餐问题的数学模型minZ=4x1+3x2s.t. 其中表示参与配餐的两种原料食品的采购量，约束条件（1）、（2）、（3）依次表示铁、蛋白质和钙的最低摄入量并用图解法给出了其最优解，试分析解决下述问题：（1）假如本题的目标函数不是求最小而是求最大值类型且约束条件不变，会出现什么结果？（2）本题最后定解时，只用了直线（1）与直线（3），而直线（2）未用上，这件事说明了什么？试从实际问题背景给以解释. 解：（1）因为可行域的右上方无界，故将出现目标函数趋于无穷大的情形，结果是问题具有无界解； （2）将最优解代

13、入约束条件可知第二个约束条件为严格不等式，而其他为严格等式这说明，铁和钙的摄入量达标，而蛋白质的摄入量超最低标准18个单位 3某公司经营的一种产品拥有四个客户，由公司所辖三个工厂生产，每月产量分别为3000，5000和4000件.公司已承诺下月出售4000件给客户1，出售3000件给客户2以及至少1000件给客户3，另外客户3和4都想尽可能多购剩下的件数.已知各厂运销一件产品给客户可得到的净利润如表1所示，问该公司应如何拟订运销方案，才能在履行诺言的前提下获利最多？ 表1单位：元/件 客户 利润工厂1 2 3 412365 63 62 6468 67 65 6263 60 59 60 上述问题

14、可否转化为运输模型？若可以则转化之（只需写出其产销平衡运价表即可），否则说明理由 解：可以转化为运输模型，具体做法如下： 首先确定总的产销量. 总产量显然为12000件；总需求量中，客户3的需求量在保证已承诺给客户1和2的供给量7000件条件下，最多是5000件，而客户4则最多可得4000件因此，总需求量按最高需求应为16000件，因而可视问题为供小于求的运输问题 其次，为产销平衡，虚设一个工厂4，其产量为4000件 再次，为确定需求量，将有最低需求与额外需求量的客户分别视为两个客户，并确定各自需求量，注意最低需求量不能由虚设工厂供给，从而可设其利润值是-M（M是一个充分大的正数）. 综合上述

15、讨论得产销平衡运价表如下： 表2 单位：元/件 客户利润工厂1 2 3 3 4供给量123 465 63 62 62 6468 67 65 65 6263 60 59 59 60 -M -M -M 0 03000500040004000 需 求 量 4000 3000 1000 4000 4000三、计算题 1某医院为病人配制营养餐要使用到两种食品A和B，每种食品A含蛋白质50g，钙400mg, 热量1000单位，价值14元；食品B含蛋白质60g，钙200mg，热量800单位，价值8元若病人每天需从食物中获取蛋白质,钙及热量分别为55g，800mg和3000单位，问如何选购食品才能在满足营养要

16、求条件下使花费最小？试组建线性规划模型并求解后回答：（1）问题的最优方案及最优值分别是甚麽？最优方案是否有选择余地？（2）各种营养要求的满足情况怎样？若限制蛋白质摄入量不超过100单位，会出现甚麽问题？解：本题属于简单的线性规划模型的建立与求解问题，并要求作出一点模型分析工作按要求，先来建立模型，根据题设，设购买两种食品分别为（kg），则有总花费数额函数，自然我们希望求出这样的取值，使得函数取最小值可以写为.又根据营养最低要求，应有蛋白质需求条件： 钙的需求条件： 400， 热量的需求条件： 非负性条件： 将上述条件合在一起，即可获得本问题的线性规划模型如下： 利用图解法易于得到其最优解为即食

17、品A购买(kg)，B购买(kg)，最低花费元由此可回答所提问题：（1）最优解与最优目标值如上所述，最优方案无选择余地，因为最优解点是在后两个约束条件直线的交点上，而不是在可行域的某条边界线段上（2）钙和热量需求得到满足（最低量），蛋白质需求超最低标准个单位以上结论是将最优解代入各个约束条件得到的若限制蛋白质摄入量不超过100单位，则第一个约束条件应修改为 在原来的求解图上加上条件则可见可行域不存在，故无解 2某工厂生产两种产品A、B分两班生产，每周生产总时间为80小时，两种产品的预测销售量、生产率和赢利如下表 表3产品预测售量（万件/周）生产率（件/小时）单位利润（元/件）A710000.15

18、B4.510000.3制定一合理的生产方案，要求依次满足下列目标： （1）充分利用现有能力，避免设备闲置； （2）周加班时间限制在10小时以内； （3）两种产品周生产品量应满足预测销售，满足程度的权重之比等于它们单位利润之比； （4）尽量减少加班时间 解： （1）建立模型 设：每班上班时间为8小时，在上班时间内只能生产一种产品； 周末加班时间内生产哪种产品不限； 生产A产品用x班，生产B产品用y班，周加班时生产A产品用x1小时，生产B产品用y1小时则有 （2）求解 现在求满足（1）中第2，3个方程可看出：，； 将（1）中的第1个方程代入第4个方程得：现在就是在满足，条件下，使上式两端的取值尽量

19、接近显然， 因此 制定方案为，生产A，B两种产品所占总时间各一半，周加班10小时全用于生产产品B 3. 试求如表4所示运输问题的最优运输方案和最小运输费用： 表4单位：百元/吨 销地 运价产地 B1 B2 B3 B4产量A1A2A33 5 2 94 7 5 126 9 10 11201525销量10 20 15 15 解：易见，这是一个产销平衡且为最小值类型的运输问题我们有 (1) 利用最小元素法可得初始方案如表5，表5 销地 运价产地 B1 B2 B3 B4产量1515A1A2A3 3 5 2 9 4 7 5 12 6 9 10 11 20 15 25销量 10 20 15 15 （2）使用

20、闭回路法可得负检验数为= -1，故令进基 （3）使用闭回路法进行调整知出基，便得新的运输方案如表6 表615 销地 运价产地 B1 B2 B3 B4产量15A1A2A3 3 5 2 9 4 7 5 12 6 9 10 11 20 15 25销量 10 20 15 15 （4）再进行检验知，所有检验数，故得最优运销图如图2：A3B4B21015A2B2B1105A1B3B2515 图2 最小费用为385（百元） 4从城市s到城市t可经城市1-6到达,其间有直达客车的城际乘车费用依次为 = 4，=1，=3，=2，=6， =1，=3，=5，=5，=6，=3，= 4，=7单位是拾元试建立图模型以确定乘

21、直达车从城市s到各城市间的最小乘车费用及相应的乘车路线解：本题属于图模型中较为简单的最短路问题为使用图理论求解，首先要建立其图模型，然后才能使用相应的解法求解之根据题设，除去始点和终点，中间点应为6个分别以为始点、终点，根据各点之间通车情况（注意下标），从左到右画出其图模型如图3：2 ts 346514365713图323465143657130s14367t114图4 再根据Dijkstra的双标号法可得下图：再进行逆向搜索即可得到从城市到各城市间的最佳乘车路线：到城市1：或；40元； 到城市2：，10元；到城市3：，30元； 到城市4：或，60元；到城市5：或，70元；到城市6：，40元；到城市的路线有三条： ； ； 其最小乘车费用均为110元 注意：要求写出所有路线，每少写一条都要扣除相应的分数 5. 有一批货物要从厂家A运往三个销售地B、C、D，中间可经过9个转运站从A到的运价依次为3、8、7；从到的运价为4、3；从到的运价为2、8、4；从到的运价为7、6；从到的运价为10、12；从到的运价为13、5、7；从到的运价为6、8；从到的运价为9、10；从到的运价为5、10、15