数学建模运筹模型.pptVIP

数学建模与运筹模型,上海海事大学 邓伟 ,线性规划 运输问题 指派问题 网络优化 动态规划,目录,例 某工厂在计划期内要安排，两种产品的生产，已知生产 单位产品所需的设备台时及A，B两种原材料的消耗、资源的限制，如下表。问题：工厂应分别生产多少单位，产品才能使工厂获利最多？,线性规划,例 下料问题 某工厂要做100套钢架，每套用长为2.9m，2.1m，1.5m的圆钢各一根，已知原料每根长7.4m。应如何下料，可使所用原料最省？ 解：共可设计下列5种下料方案,线性规划,建模步骤： (1)确定决策变量：我们需要作出决策或者选择的量，一般情况下，题目问什么就设什么为决策变量。 (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; 对于乙： x12, x22, x32; 对于丙： x13, x23, x33; 目标函数：利润最大，利润=收入-原料成本-加工费 约束条件：原料用量限制，含量限制,线性规划,线性规划,求解方法： 1.图解法 适合含有两个决策变量的模型； max z = x1+3x2 s.t. x1+ x26 -x1+2x28 x1 0, x20,可行域,目标函数等值线,最优解,6,4,-8,6,0,x1,x2,线性规划,2.单纯形法(人工变量法、对偶单纯形法) 软件求解：lingo，lindo，Matlab Min f= 0.4x1+1.5x2+x3+1.3x4 S.t. 0.3x1+3x2 + +1.5x4=320 0.5x1+ +2x3+x4 =240 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吨，食品被运到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)检验数全都大于等于零时对应的解为最优解。,运输问题,位势： 检验数：,运输问题,3.迭代求新基本可行解 (1)负检验数中最小者对应的变量进基； (2)在运输表中找一个包含进基变量的闭回路，这个回路上其他顶点均为基变量。依次对闭回路的四个顶点标号，将顶点分为奇点格和偶点格； (3)偶点格的最小值作为调整量，所有奇点格+调整量；偶点格-调整量，即一次迭代。 (4)按位势方程求新解对应的位势及检验数，判别最优性。,运输问题,闭回路：,运输问题,迭代及新基本可行解的检验数计算：,运输问题,产销不平衡运输问题： 1. 供大于求，引入虚拟销售点，并假设它的需求量为 供不应求，引入虚拟的产地，并假设它的产量为 由于虚拟销地是不存在的，实际上这个差值是在产地贮存的，故从产地到虚拟销地的单位运价为0； 同理，由于虚拟产地是不存在的，所以虚设的产地到各个销地的单位运价也为0.,运输问题,例 2个化肥厂供应3个地区的化肥，试决定运费最小的调运方案。 解：增加虚设的销地B4，销量为10，构造产销平衡的运输表。,运输问题,初始基可行解及其检验数： 迭代求新基本可行解：,运输问题,n项任务，恰好有n个人承担，由于每个人的专长不同，完成各工作的效率不同，于是产生了应指派哪个人去完成哪项，使得完成n项任务的总效率最高的问题，这类问题称为指派问题。 例 有一份说明书，需要译成英、日、德、俄四种文字，现有甲乙丙丁四个人，他们将说明书译成不同文字所需要的时间如下表所示，问应指派哪个人完成哪项工作，耗用的总时间最少？,指派问题,一般地，有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元素的直线，r=4=矩阵阶数， 则可以找到最优解,所需最少时间=4+4+9+11=28 甲-俄语 从而得到最优指派：乙-日语 丙-英语 丁-德语,指派问题,例 分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每人完成各项任务的时间如下表所示，由于任务重，人手少，考虑以下两种情况下的最优分配方案，使得完成任务的总时间最少。 (1)任务E必须完成，其他4项任务可选3项完成，但甲不能做A项工作；(2)其中有一人完成2项，其他人每人完成1项。 解：这是一人数与任务数不等的指派问题，若用匈牙利法求解，需作以下处理。,指派问题,(1)由于任务数大于人数，所以需要有一个虚拟的人，设为戊。因为工作E必须完成，故设戊完成E的时间为M(M为非常大的正数)，即戊不能做工作E，其余的假想时间为0，建立的效率矩阵为： 采用匈牙利解法求解过程如下：,指派问题,(1)由于r=4矩阵阶数=5，需要调整0元素的分布。 从该矩阵可看出，r=5=矩阵阶数，因此能找到最优指派方案。 甲-B 乙-D 丙-E 丁-A 戊-C（戊 为虚拟人，即任务C无人完成） 最少的耗时数 z=29+20+32+24=105,指派问题,(2)思路： 方案1：甲，【甲】，乙，丙，丁 方案2：甲，乙，【乙】，丙，丁 方案3：甲，乙，丙，【丙】，丁 方案4：甲，乙，丙，丁，【丁】 方案5：甲，【甲】，乙，【乙】，丙，【丙】，丁，【丁】，工作A，B，C，D，E，虚拟工作F，G，H。 这些方案较烦琐，采用以下思路更为简便。 设有虚拟人戊，他集五人的优势为一身，即戊的费用是每人的最低，戊所做的工作即为此项工作的费用最低者的工作，效率矩阵分配表为：,指派问题,采用匈牙利解法求解： 对C3做0元素的最小直线覆盖，得r=5=n。结果为 甲-B 乙-D 丙-E 丁-A 戊-C 但戊为虚拟人，不能真做，它做C工作是借乙(此列最小时数26是C所创业绩)的优势，应由乙来做，即乙做两件工作：D、C。,指派问题,例 最大收益的最优分配问题：有5名工人完成5项不同的任务收 益如表所示： 求使总收益达到最高的任务分配方案。 解：这是一个寻求总收益为最大值的极大化问题，需要转化为极小化问题才能用匈牙利解法。 收益矩阵B=（bij），设b=maxbij，令cij=b-bij ，C=（cij），以C为效率矩阵的极小化问题即是原最大收益的极大化问题转化而来。,指派问题,b=maxbij=19，令cij=19-bij ，C=（cij）， 继续对C矩阵采用匈牙利法求解，得到C的最优分配方案为 即 甲-D 乙-B 丙-E 丁-A 戊-C ，求得的最大总收益为74.,指派问题,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,网络优化,最短路径问题：有一批货物要从节点1运送到节点8，这两点间的通路如下图，每条弧旁边的数字表明该弧的长度。总路径越短，运费越低，为节省运输费用，应该选择怎样的运输路线？,求从1到8的最短路径。,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1, w1=0,min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1 X=1,4, w4=1,w1=0,w1=0,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,4,min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2 X=1,2,4, w2=2,w1=0,w4=1,w2=2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,min c16,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3 X=1,2,4,6, w6=3,w2=2,w4=1,w1=0,w6=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3 X=1,2,4,6,7, w7=3,w2=2,w4=1,w1=0,w6=3,w7=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6 X=1,2,4,5,6,7, w5=6,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8 X=1,2,3,4,5,6,7, w3=8,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,min c38,c58,c78=min 8+6,6+4,3+8=min 14,10,11=10 X=1,2,3,4,5,6,7,8, w8=10,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,w8=10,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,8,1到10的最短路径为1，4，7，5，8，长度为10。,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,w8=10,网络优化,最大流问题：给出一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。,边的容量和流量：容量uij，流量xij 可行流： 满足以下条件的流称为可行流： 1、每一个节点流量平衡 2、0xij uij 如果xij=uij，边从i到j的方向是饱和的； 如果xijuij，边从i到j的方向是不饱和的；,网络优化,（1，2）是饱和的,（1，2）是不饱和的 间隙为12=u12-x12=5-3=2,如果xij=0，边从j到i的方向是饱和的 （2，1）是饱和的 如果xij0，边从j到i的方向是不饱和的,网络优化,（2，1）是不饱和的 间隙为12=x12=5,给出一个初始的可行流xij=0,网络优化,2,3,5,4,6,7,1,f=0,f=0,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,找到所有的不饱和边，以及各边可以调整流量的方向,2,3,5,4,6,7,1,f=0,f=0,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,=3,=1,=8,=8,x=0,找到一条从1到7的不饱和链,链的间隙为： = min8,3,1,8=1 调整链的流量：xij=xij+ ,2,3,5,4,6,7,1,f=1,f=1,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=1,x=1,x=1,x=1,调整流量，f=1。继续求出网络的不饱和边,2,3,5,4,6,7,1,f=1,f=1,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=1,x=1,x=1,x=1,=1,=6,=9,=7,求出一条从1到7的不饱和链,=min 7,1,6,9=1, 调整流量 xij=xij+1, f=f+1=2,2,3,5,4,6,7,1,f=2,f=2,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=1,x=0,x=0,x=1,x=0,x=0,x=0,x=1,x=1,x=1,x=1,x=0,调整流量，继续求出网络的不饱和边,=5,=8,=7,求出一条从1到7的不饱和链,=min 7,5,8=5, 调整流量 xij=xij+5, f=f+5=2+5=7,2,3,5,4,6,7,1,f=7,f=7,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=0,x=1,x=0,x=0,x=0,x=6,x=1,x=1,x=6,x=0,调整流量，继续求出网络的不饱和边,=4,=4,=3,=6,求出一条从1到7的不饱和链,=min 6,7,4,3=3, 调整流量 xij=xij+3, f=f+3=7+3=10,2,3,5,4,6,7,1,f=10,f=10,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=3,x=4,x=3,x=0,x=0,x=9,x=1,x=1,x=6,x=0,调整流量，继续求出网络的不饱和边,2,3,5,4,6,7,1,f=10,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=3,x=4,x=3,x=0,x=0,x=9,x=1,x=1,x=6,x=0,f=10,=1,=3,=7,=3,求出一条从1到7的不饱和链,=min 3,1,3,7=1, 调整流量 xij=xij+1, f=f+1=10+1=11,2,3,5,4,6,7,1,f=11,f=11,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=4,x=5,x=3,x=1,x=0,x=9,x=2,x=1,x=6,x=0,调整流量，继续求出网络的不饱和边,已找不到一条从1到7的不饱和链，从1开始可以到达的节点为1，2，3,2,3,5,4,6,7,1,f=11,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=4,x=5,x=3,x=1,x=0,x=9,x=2,x=1,x=6,x=0,f=11,已求得最大流,最大流f=11，最小割集为（2,5）（3,4）（3,5） u25+u34+u35=6+4+1=11,最短路问题： 给定一个运输网络，两点之间连线上的数字表示两点之间的距离，试求一条从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 动态规划中状态的性质：无后效性，即如果某个阶段状态给定之后，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。 决策：指在某阶段对可供选择状态的选择，描述的变量称为决策变量。 dk( sk )决策变量 Dk( sk )允许决策集合 D2(B1)=C1,C2,C3,动态规划,全过程策略：由所有各阶段组成的决策函数序列,简称策略。记为： P1,n(s1) 或P1,n(s1)=d1(s1), d2(s2), dn(sn) k子过程策略(后部子策略)：由k阶段开始到最后阶段结束，组成的决策函数序列。 Pk,n(sk)=dk(sk), dk+1(sk+1), dn(sn) 最优策略：使整个问题达到最优效果的策略。 P*1,n(A)=B3,C2,D2 ,E AB3 C2 D2 E 允许策略集：可供选择策略的范围，用P表示。 动态规划方法就是要从允许策略集P中找出最优策略 P*k,n,动态规划,状态转移方程： 本阶段状态与上一阶段状态和上一阶段决策的关系，用状态转移方程来表示。 sk+1=Tk(sk,dk) 该方程描述了由第k阶段到第k+1阶段的状态转移规律，又称为状态转移函数。 sk+1=dk (sk) 阶段指标：衡量某阶段决策效益优劣的策略指标，如距离，成本，利润等。 vk (sk,dk) 指标函数：衡量所选定策略优劣的数量指标。 Vk,n (sk,Pk,n)= Vk,n (sk,dk,sk+1,sn+1 ),动态规划,常见指标函数形式(分离性，递推关系) Vk,n (sk,Pk,n)= Vk,n (sk,dk,sk+1,sn+1 ) = Vk (sk,dk )+ Vk+1 (sk+1, Pk,n) Vk,n (sk,Pk,n)= Vk,n (sk,dk,sk+1,sn+1 ) = Vk (sk,dk )* Vk+1 (sk+1, Pk,n) 最优指标函数:指标函数的最优值，fk(sk)表示从第k阶段状态sk开始采用最优策略P*k,n到过程终止时的最佳效益值。 fk(sk)=opt Vk,n (sk,dk,sk+1,sn+1 ) f1(s1)表示从第1阶段状态s1采用最优策略P*1,n到过程终止时的最佳效益值。,动态规划,动态规划的基本思想： 1. 多阶段决策过程划分阶段，恰当的选取状态变量、决策变量和定义最优指标函数，从而将问题化为一族同类型的子问题逐个求解。 2. 求解时从边界条件开始，逆（或顺）过程行进方向，逐段递推寻优。 3. 既将当前一段与未来各段分开，又将当前效益与未来效益结合起来考虑的一种最优化方法。 如何建立动态规划模型： 1. 分析识别问题的多阶段特性，按时间或空间的先后顺序适当地划分满足递推关系的若干阶段。 2. 确定状态变量，满足可知性和无后效性。一般为累计量和随递推过程变化的量。 3.找到状态转移方程。 4.正确确定基本方程。,基础：最优化定理 作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态而言，以后所有的决策必定构成最优子策略。 对最短路问题而言,从最短路上任一点到终点的部分道路（最短路上的子路）也一定是从该点到终点的最短路。,动态规划,从最后一段开始计算，由后向前逐步推移至A点。 第四阶段，由D1到E只有一条线路，其长度f4(D1)=3，同理f4(D2)=4； 第三阶段，由Cj到Di均有两种选择，即 第二阶段，由Bj到Ci均有三种选择，即,动态规划,第一阶段，由A到B，有三种选择，即 f1(A)=12，说明从A到E的最短距离为12，最短路线的确定可按计算顺序反推而得，即A-B3-C2-D2-E,动态规划,一个著名的命题：一个串村走户的卖货郎，他从某个村庄出发，通过若干个村庄一次且仅一次，最后仍回到原出发的村庄，问：应如何选择行走路线，能使得总的行程最短。 设有n个城市，1,2,n。Dij表示从i城到j城的距离。 规定推销员是从城市1开始的，设推销员走到i城，记Ni2,3,i-1,i+1,n 表示由1城到i城的中间城市集合。 S表示到达i城中途所经过的城市的集合，则有S Ni 1）选取（i,S）作为状态变量，表示推销员从城市1开始走到i城，经过若干个城市，构成集合S。 2）最优值函数fk(i,S)为从城市1开始经过k个中间城市的S集到达i城的最短路线的距离。,货郎担问题 （TSP问题traveling salesperson problem）,3）递推关系式： fk(i,S)=min fk-1(j,Sj)+Dji (k=1,2, ,n-1. i=2,3,n. S Ni) 边界条件：f0(i,)= D1i 4） Pk(i,S)为最优决策函数，表示从1城开始经k个中间城市到i城的最短路线上紧挨着i城前面的那个城市。,例：当推销员从1城出发，经过每个城市一次且仅一次，最后回到1城，问按怎样的路线走，使总的行程距离最短。（四个城市，其距离矩阵如下表）,5）由边界条件可知： f0(i,)= D1i f0(2,)= D128，f0(3,)= D135，f0(4,)= D146 当k=1时，即从1城开始，中间经过一个城市到达i城的最短距离是： f1(2,3)= f0(3,)+ D325+9=14 f1(2,4)= f0(4,)+ D426+7=13 f1(3,2)= f0(2,)+ D238+8=16 f1(3,4)= f0(4,)+ D436+8=14 f1(4,2)= f0(2,)+ D248+5=13 f1(4,3)= f0(3,)+ D345+5=10,当k=2时，即从1城开始，中间经过两个城市到达i城的最短距离是： f2(2,3,4)=min f1(3, 4)+D32 f1(4, 3)+D42 =min14+9,10+7=17 P2(2,3,4)=4,f2(3,2,4)=min f1(2, 4)+D23 f1(4, 2)+D43 =min13+8 ,13+8=21 P2(3,2,4)=