资源描述：
《最新数学建模运筹模型1教学讲义PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数学建模运筹模型1例某工厂在计划期内要安排Ⅰ，Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A，B两种原材料的消耗、资源的限制，如下表。问题：工厂应分别生产多少单位Ⅰ，Ⅱ产品才能使工厂获利最多？线性规划例下料问题某工厂要做100套钢架，每套用长为2.9m，2.1m，1.5m的圆钢各一根，已知原料每根长7.4m。应如何下料，可使所用原料最省？解：共可设计下列5种下料方案线性规划解：用i=1,2,3代表原料1,2,3,j=1,2,3代表糖果甲、乙、丙。Xij表示第j中产品中原料i的含量，则对于原料1：x11,x12,x13;对于原料2：x21,x22,x23;对于原料3：x31
2、,x32,x33;对于甲：x11,x21,x31;对于乙：x12,x22,x32;对于丙：x13,x23,x33;目标函数：利润最大，利润=收入-原料成本-加工费约束条件：原料用量限制，含量限制线性规划线性规划求解方法：1.图解法适合含有两个决策变量的模型；maxz=x1+3x2s.t.x1+x2≤6-x1+2x2≤8x1≥0,x2≥0可行域目标函数等值线最优解64-860x1x2线性规划2.单纯形法(人工变量法、对偶单纯形法)软件求解：lingo，lindo，MatlabMinf=0.4x1+1.5x2+x3+1.3x4S.t.0.3x1+3x2++1.5x4>=3200.5
3、x1++2x3+x4>=2401.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个
4、厂每月的生产能力分别为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)利用位势求非基变量检验数检验数计算公式：c
5、ij-ui-vj(3)检验数全都大于等于零时对应的解为最优解。运输问题位势：检验数：运输问题3.迭代求新基本可行解(1)负检验数中最小者对应的变量进基；(2)在运输表中找一个包含进基变量的闭回路，这个回路上其他顶点均为基变量。依次对闭回路的四个顶点标号，将顶点分为奇点格和偶点格；(3)偶点格的最小值作为调整量，所有奇点格+调整量；偶点格-调整量，即一次迭代。(4)按位势方程求新解对应的位势及检验数，判别最优性。运输问题闭回路：运输问题迭代及新基本可行解的检验数计算：运输问题产销不平衡运输问题：1.供大于求，引入虚拟销售点，并假设它的需求量为供不应求，引入虚拟的产地，并假设它的产
6、量为由于虚拟销地是不存在的，实际上这个差值是在产地贮存的，故从产地到虚拟销地的单位运价为0；同理，由于虚拟产地是不存在的，所以虚设的产地到各个销地的单位运价也为0.运输问题例2个化肥厂供应3个地区的化肥，试决定运费最小的调运方案。解：增加虚设的销地B4，销量为10，构造产销平衡的运输表。运输问题初始基可行解及其检验数：迭代求新基本可行解：运输问题n项任务，恰好有n个人承担，由于每个人的专长不同，完成各工作的效率不同，于是产生了应指派哪个人去完成哪项，使得完成n项任务的总效率最高的问题，这类问题称为指派问题。例有一份说明书，需要译成英、日、德、俄四种文字，现有甲乙丙丁四个人，他们
7、将说明书译成不同文字所需要的时间如下表所示，问应指派哪个人完成哪项工作，耗用的总时间最少？指派问题一般地，有n项任务、n个完成人，第i人完成第j项任务的代价为cij(i,j=1,2,……,n),为了求得总代价最小的指派方案，引入0-1型变量xij,令数学模型为注：指派问题是0-1整数规划的特例，也是运输问题的特例，其产地和销地数均为1，各产地产量和各销地销量均为1.指派问题指派问题的求解方法：匈牙利法。匈牙利法基于下面的事实：如果系数矩阵的所有元素满足：cij>=0，而其中有n个位于不同行不
