数学建模——运筹模型1

《数学建模——运筹模型1》由会员分享，可在线阅读，更多相关《数学建模——运筹模型1（82页珍藏版）》请在金锄头文库上搜索。

1、数学建模与运筹模型上海海事大学 邓伟 线性规划 运输问题 指派问题 网络优化 动态规划目录 例 某工厂在计划期内要安排，两种产品的生产，已知生 产 单位产品所需的设备台时及A，B两种原材料的消耗、资源的 限制，如下表。问题：工厂应分别生产多少单位，产品才 能使工厂获利最多？ 线性规划例 下料问题 某工厂要做100套钢架，每套用长为 2.9m，2.1m，1.5m的圆钢各一根，已知原料每根长 7.4m。应如何下料，可使所用原料最省？解：共可设计下列5种下料方案线性规划建模步骤：(1)确定决策变量：我们需要作出决策或者选择的 量，一般情况下，题目问什么就设什么为决策变量。(2)找出约束条件：即决策

2、变量受到的所有的约束 。(3)写出目标函数：即问题所要达到的目标，并明 确是求max还是min。线性规划例 混合配料问题 某糖果厂用原料1、2、3加工三 种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中 原料1、2、3的含量、原料每月限用量、三种牌号糖 果的加工费及售价，如下表所示。该厂每月如何生产 才能获利最大？线性规划解：用i=1,2,3代表原料1,2,3, j=1,2,3代表糖果甲、乙、 丙。Xij表示第j中产品中原料i的含量，则对于原料1： x11, x12, x13;对于原料2： x21, x22, x23;对于原料3： x31, x32, x33;对于甲： x11, x21, x31

3、;对于乙： x12, x22, x32;对于丙： x13, x23, x33;目标函数：利润最大，利润=收入-原料成本-加工费约束条件：原料用量限制，含量限制线性规划线性规划求解方法：1.图解法 适合含有两个决策变量的模型； max z = x1+3x2s.t. x1+ x26 -x1+2x28x1 0, x20可行域目标函数等值线最优解64-860x1x2线性规划2.单纯形法(人工变量法、对偶单纯形法)软件求解：lingo，lindo，MatlabMin f= 0.4x1+1.5x2+x3+1.3x4 S.t. 0.3x1+3x2 + +1.5x4=3200.5x1+ +2x3+x4 =24

4、0 1.4x1+ +0.7x4=420 线性规划将某种物资从m个产地遇到n个销地，每个产地都有一定的产量ai，i=1,2,m，每个销地都对物资有一定的需求 量bj,j=1,2,n。已知从第i个产地向第j个销地运送单位 物资的运价为cij，总产量等于总需求量( )。如何调 运物资，才能使总运费最小？设xij为从产地Ai运往销地Bj的运输量，运输问题运输表：(产销平衡的运输问题)求解方法：1.确定初始基本可行解（西北角法、最小元素法、vogal法）2.最优性检验；3.迭代求新的基本可行解。运输问题例 某食品公司下属的三个食品厂A1、A2、A3生产食品，3个 厂每月的生产能力分别为7吨、4吨、9吨，

5、食品被运到B1、B2 、B3、B4四个销售点，它们对方便食品的月需求量分别为3吨 、6吨、5吨、6吨，运输表如下表，试制定最优运送方案。运输问题解：1.确定初始基可行解最小元素法：运输问题解：1.确定初始基可行解(最小元素法)初始基本可行解对应的目标函数值：f=3*4+10*3+1*3+2*1+4*6+5*3=86运输问题解：2.最优性检验(1)位势： ui+vj =cij (i=1,2,m,j=1,2,n)其中cij 为基本可行解中基变量对应的单位运价。注：m+n-1个方程，m+n个变量。(2)利用位势求非基变量检验数检验数计算公式： cij -ui-vj(3)检验数全都大于等于零时对应的解

6、为最优解。运输问题位势：检验数：运输问题3.迭代求新基本可行解(1)负检验数中最小者对应的变量进基；(2)在运输表中找一个包含进基变量的闭回路，这个回路上 其他顶点均为基变量。依次对闭回路的四个顶点标号，将顶 点分为奇点格和偶点格；(3)偶点格的最小值作为调整量，所有奇点格+调整量；偶 点格-调整量，即一次迭代。(4)按位势方程求新解对应的位势及检验数，判别最优性。运输问题闭回路：运输问题迭代及新基本可行解的检验数计算：运输问题产销不平衡运输问题：1. 供大于求，引入虚拟销售点，并假设它的需求量 为 供不应求，引入虚拟的产地，并假设它的产量为由于虚拟销地是不存在的，实际上这个差值是在产地贮存的

7、，故从产地到虚拟销地的单位运价为0；同理，由于虚拟产地是不存在的，所以虚设的产地到各个销地的单位运价也为0.运输问题例 2个化肥厂供应3个地区的化肥，试决定运费最小的调运方 案。解：增加虚设的销地B4，销量为10，构造产销平衡的运输表 。运输问题初始基可行解及其检验数：迭代求新基本可行解：运输问题n项任务，恰好有n个人承担，由于每个人的专长不同， 完成各工作的效率不同，于是产生了应指派哪个人去完成哪项 ，使得完成n项任务的总效率最高的问题，这类问题称为指派问 题。例 有一份说明书，需要译成英、日、德、俄四种文字，现 有甲乙丙丁四个人，他们将说明书译成不同文字所需要的时间 如下表所示，问应指派哪

8、个人完成哪项工作，耗用的总时间最 少？指派问题一般地，有n项任务、n个完成人，第i人完成第j项任务 的代价为cij(i,j=1,2,n),为了求得总代价最小的指派方案 ，引入0-1型变量xij ,令数学模型为注：指派问题是0-1整数规划的特例，也是运输问题的特例 ，其产地和销地数均为1，各产地产量和各销地销量均为1.指派问题 指派问题的求解方法：匈牙利法。 匈牙利法基于下面的事实：如果系数矩阵的所有元素满足： cij=0，而其中有n个位于不同行不同列的一组0元素，则只要令 对应于这些0元素位置的xij=1，其余的xij=0，就得到最优解。如 则指派问题求解上例：行变换得 列变换得画出最少覆盖0

9、元素的直线，r=4=矩阵阶数 ， 则可以找到最优解,所需最少时间=4+4+9+11=28 甲-俄语从而得到最优指派：乙-日语丙-英语丁-德语 指派问题例 分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任 务，每人完成各项任务的时间如下表所示，由于任务重，人手 少，考虑以下两种情况下的最优分配方案，使得完成任务的总 时间最少。(1)任务E必须完成，其他4项任务可选3项完成，但甲不能 做A项工作；(2)其中有一人完成2项，其他人每人完成1项。解：这是一人数与任务数不等的指派问题，若用匈牙利法求 解，需作以下处理。指派问题(1)由于任务数大于人数，所以需要有一个虚拟的人，设为戊 。因为工作E必

10、须完成，故设戊完成E的时间为M(M为非常大的正 数)，即戊不能做工作E，其余的假想时间为0，建立的效率矩阵 为：采用匈牙利解法求解过程如下：指派问题(1)由于r=40，边从j到i的方向是不饱和的网络优化21 xij=0uij=521 xij=5uij=5（2，1）是不饱和的 间隙为12=x12=5给出一个初始的可行流xij=02354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0网络优化2354671f=0f=0u=6u=2u=4 u=3u=7u=4u=3u=1u=7u=9u=8

11、u=8x=0x=0x=0 x=0x=0x=0x=0x=0x=0x=0x=0x=0找到所有的不饱和边，以及各边可以调整流量的方向2354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0 =3=1=8=8x=0找到一条从1到7的不饱和链链的间隙为： = min8,3,1,8=1 调整链的流量：xij=xij+ 2354671f=1f=1u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0x=0x=0x=0x=0x=0x=0x=0x=1x=1x=1x=1调整流量，f=

12、1。继续求出网络的不饱和边2354671f=1f=1u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0x=0x=0x=0x=0x=0x=0x=0x=1x=1x=1 x=1 =1=6=9=7求出一条从1到7的不饱和链=min 7,1,6,9=1, 调整流量 xij=xij+1, f=f+1=22354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=1x=0x=0x=1x=0x=0x=0x=1x=1x=1x=1x=0调整流量，继续求出网络的不饱和边2354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=1u=

13、7u=9u=8u=8x=1x=0x=0x=1x=0x=0x=0x=1x=1x=1x=1x=0=5=8=7求出一条从1到7的不饱和链=min 7,5,8=5, 调整流量 xij=xij+5, f=f+5=2+5=72354671f=7f=7u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=0x=1x=0x=0x=0x=6x=1x=1x=6x=0调整流量，继续求出网络的不饱和边2354671f=7f=7u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=0x=1x=0x=0x=0x=6x=1x=1x=6x=0=4=4=3=6

14、求出一条从1到7的不饱和链=min 6,7,4,3=3, 调整流量 xij=xij+3, f=f+3=7+3=102354671f=10f=10u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=3x=4x=3x=0x=0x=9x=1x=1x=6x=0调整流量，继续求出网络的不饱和边2354671f=10u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=3x=4x=3x=0x=0x=9x=1x=1x=6x=0f=10=1=3=7=3求出一条从1到7的不饱和链=min 3,1,3,7=1, 调整流量 xij=xij+1,

15、f=f+1=10+1=112354671f=11f=11u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=4x=5x=3x=1x=0x=9x=2x=1x=6x=0调整流量，继续求出网络的不饱和边已找不到一条从1到7的不饱和链，从1开始可以到达的节点为1， 2，32354671f=11u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=4x=5x=3x=1x=0x=9x=2x=1x=6x=0f=11已求得最大流最大流f=11，最小割集为（2,5）（3,4）（3,5） u25+u34+u35=6+4+1=11最短路问题：给定

16、一个运输网络，两点之间连线上的数字表示两点之间的距离，试求一条从A到B的运输路线，使总距离最短。可将问题分为四个阶段：第一阶段，从A到B；第二阶段，从B到C；第三阶段，从C到D；第四阶段，从D到E。完全枚举：3*3*2*1=24条。最优解：AB3 C2 D2 E动态规划阶段：将所给问题的过程，按时间或空间特征分解成相互联系的阶段， 以便按次序求每阶段的解k描述阶段的变量 状态：表示每个阶段开始时所处的自然状况或条件，描述了研究问题的 状况。sk状态变量Sk状态集合 S1=A,S2=B1,B2,B3,S3=C1,C2,C3,S4=D1,D2动态规划中状态的性质：无后效性，即如果某个阶段状态给定之后