数学建模优化模型ppt课件.ppt

数学建模,-优化模型,第二讲 线性规划建模方法,第三讲 整数规划建模方法,第四讲 指派问题,第六讲 图论简介,第五讲 动态规划建模,第一讲 数学建模概论,第一章 数学建模概论,1.1 数学建模由来1.2 从现实对象到数学模型1.3 数学建模的重要意义1.4 数学建模的方法和步骤1.5 数学模型的特点和分类1.6 近几年国内竞赛题1.7 怎样学习数学建模与竞赛组队1.8 撰写数学建模论文,1985年由美国工业与应用数学学会和美国运筹 学会联合主办大学生数学建模竞赛（ MCM ),1.1 数学建模由来, 在上世纪70年代末和80年代初，英国著名的剑 桥大学专门为研究生开设了数学建模课程, 数学建模作为一门崭新的课程在20世纪80年代 进入我国高校，萧树铁先生1983年在清华大学首次为本科生讲授数学模型课程，他是我国高校开设数学模型课程的创始人, 1992年由中国工业与应用数学学会举办全国大 学生数学建模竞赛（ 94年起由国家教委高教司和中国工业与应用数学学会共同举办）, 1987年由姜启源教授编写了我国第一本数学 建模教材, 2005年全国数学建模竞赛，共有来自全国30个省、市、自治区的795所高校8492支队（其中甲组6556队、乙组1936队）、25476名来自各个专业的大学生参加本次竞赛, 95年我校参加全国大学生数学建模竞赛，最初开设选修课是因为参加数学建模竞赛的需要，选修的学生数较少，而且必须是往年成绩较优的学生才允许选修, 97年学校决定在原有基础上，在部分专业开设数学建模必修课，并同时对其他专业开设数学建模选修课, 2000年起结合课程教学与竞赛安排，在每年五月底或六月初举办全校大学生数学建模竞赛,近两年数学建模课程每年选课人数2000余人, 1995-2009年学生参加全国大学生数学建模竟赛及获奖情况：,年份 参赛 全国 全国 省一等奖 省二等奖 省三等奖 队数 一等奖 二等奖 1995 3 1 1 1 11996 4 1 1 1 11997 7 2 2 2 1 11998 7 4 2 6 11999 7 1 2 3 12000 10 1 3 3 22001 10 2 1 3 22002 15 1 2 3 5 12003 15 2 3 3 3 62004 16 1 3 2 4 4 22 4 1 3 8 3 28 1 9 30 2 5 32 3 7 33 1 8,2006年获一等奖1队，二等奖3队 2007年获一等奖1队，二等奖5队2008年获一等奖4队，二等奖4队2009年获一等奖2队，二等奖2队, 2006-2009年学生参加美国大学生数学建模竟赛及获奖情况：,玩具、照片、飞机、火箭模型 , 实物模型,地图、电路图、分子结构图 , 符号模型,模型是为了一定目的，对客观事物的一部分进行简缩、抽象、提炼出来的原型的替代物,模型集中反映了原型中人们需要的那一部分特征,1.2 从现实对象到数学模型,我们常见的模型,你碰到过的数学模型“航行问题”,用 x 表示船速，y 表示水速，列出方程：,答：船速每小时20千米/小时.,甲乙两地相距750千米，船从甲到乙顺水航行需30小时，从乙到甲逆水航行需50小时，问船的速度是多少?,x =20y =5,航行问题建立数学模型的基本步骤,作出简化假设（船速、水速为常数）；,用符号表示有关量（x, y表示船速和水速）；,用物理定律（匀速运动的距离等于速度乘以 时间）列出数学式子（二元一次方程）；,求解得到数学解答（x=20, y=5）；,回答原问题（船速每小时20千米/小时）。,数学模型 (Mathematical Model) 和数学建模（Mathematical Modeling),对于一个现实对象，为了一个特定目的，根据其内在规律，作出必要的简化假设，运用适当的数学工具，得到的一个数学结构。,建立数学模型的全过程（包括表述、求解、解释、检验等）,数学模型,数学建模,1.3 数学建模的重要意义,电子计算机的出现及飞速发展；,数学以空前的广度和深度向一切领域渗透。,数学建模作为用数学方法解决实际问题的第一步，越来越受到人们的重视。,在一般工程技术领域数学建模仍然大有用武之地；,在高新技术领域数学建模几乎是必不可少的工具；,数学进入一些新领域，为数学建模开辟了许多处女地。,数学建模的具体应用,分析与设计,预报与决策,控制与优化,规划与管理,数学建模,计算机技术,知识经济,数学建模的基本方法,机理分析,测试分析,根据对客观事物特性的认识，找出反映内部机理的数量规律,将对象看作“黑箱”,通过对量测数据的统计分析，找出与数据拟合最好的模型,机理分析没有统一的方法，主要通过实例研究 (Case Studies)来学习。以下建模主要指机理分析。,二者结合,用机理分析建立模型结构,用测试分析确定模型参数,1.4 数学建模的方法和步骤,数学建模的一般步骤,模型准备,了解实际背景,明确建模目的,搜集有关信息,掌握对象特征,形成一个比较清晰的问题,模型假设,针对问题特点和建模目的,作出合理的、简化的假设,在合理与简化之间作出折中,模型构成,用数学的语言、符号描述问题,发挥想像力,使用类比法,尽量采用简单的数学工具,数学建模的一般步骤,模型求解,各种数学方法、软件和计算机技术,如结果的误差分析、统计分析、模型对数据的稳定性分析,模型分析,模型检验,与实际现象、数据比较，检验模型的合理性、适用性,模型应用,数学建模的一般步骤,数学建模的全过程,现实对象的信息,数学模型,现实对象的解答,数学模型的解答,(归纳),(演绎),表述,求解,解释,验证,根据建模目的和信息将实际问题“翻译”成数学问题,选择适当的数学方法求得数学模型的解答,将数学语言表述的解答“翻译”回实际对象,用现实对象的信息检验得到的解答,实践,现实世界,数学世界,1.5 数学模型的特点和分类,模型的逼真性和可行性,模型的渐进性,模型的稳定性,模型的可转移性,模型的非预制性,模型的条理性,模型的技艺性,模型的局限性,数学模型的特点,数学模型的分类,应用领域,人口、交通、经济、生态 ,数学方法,初等数学、微分方程、规划、统计 ,表现特性,描述、优化、预报、决策 ,建模目的,了解程度,白箱,灰箱,黑箱,确定和随机,静态和动态,线性和非线性,离散和连续,1.6 近几年全国大学生数学建模竞赛题,1.7 怎样学习数学建模与竞赛组队,数学建模与其说是一门技术，不如说是一门艺术,技术大致有章可循,艺术无法归纳成普遍适用的准则,想像力,洞察力,判断力,学习、分析、评价、改进别人作过的模型,亲自动手，认真作几个实际题目,根据数学建模竞赛章程，三人组成一队。,这三人中必须一人数学基础较好，,一人应用数学软件（如Matlab,lindo,maple等） 和编程（如c,Matlab,vc+等）的能力较强，,一人科技论文写作的水平较好。,科技论文的写作要求整篇论文的结构严谨，语言要有逻辑性，用词要准确。, 三人之间要能够配合得起来。若三人之间配合不好， 会降低效率，导致整个建模的失败。, 如果可能的话，最好是数学好的懂得编程的一些知识，编程好的了解建模，搞论文写作也要了解建模，这样会合作得更好。因为数学好的在建立模型方案时会考虑到编程的便利性，以利于编程；编程好的能够很好地理解模型，论文写作的能够更好、更完全地阐述模型。否则会出现建立的模型不利于编程，程序不能完全概括模型，论文写作时会漏掉一些不经意的东西。,在合作的过程中，最好是能够在三人中找出一个所谓的组长，即要能够总揽全局，包括任务的分配，相互间的合作和进度的安排。,在建模过程中出现意见不统一如何处理？仅我个人的经验而言，除了一般的理解与尊重外，我觉得最重要的一点就是“给我一个相信你的理由”和“相信我，我的理由是”，不要作无谓的争论。,1.8 撰写数学建模论文,1、摘要:问题、模型、方法、结果,2、问题重述,3、模型假设与记号,4、分析与建立模型,5、模型求解,6、模型检验,7、模型推广,8、参考文献,9、附录,第二讲 线性规划建模方法,一、从现实问题到线性规划模型,二、线性规划模型的求解,三、线性规划建模实例,四、线性规划的对偶问题,例1 加工奶制品的生产计划,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/公斤，应否改变生产计划？,每天:,一、从现实问题到线性规划模型,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,模型分析与假设,比例性,可加性,连续性,xi对目标函数的“贡献”与xi取值成正比,xi对约束条件的“贡献”与xi取值成正比,xi对目标函数的“贡献”与xj取值无关,xi对约束条件的“贡献”与xj取值无关,xi取值连续,A1,A2每公斤的获利是与各自产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数,A1,A2每公斤的获利是与相互产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数,加工A1,A2的牛奶桶数是实数,线性规划模型,制订生产计划,使每天获利最大,例2工厂生产两种产品A1,A2,已知生产单位产品情况如表：,设生产A1、A2分别x1、x2公斤,max z= 20 x1+30 x2 (1),目标函数,约束条件,决策变量,一、从现实问题到线性规划模型,线性规划模型标准型:,maxz= c1 x1 +c2x2 +cnxn,(LP),线性规划模型标准型矩阵表示：,max z= c x,max(min) z= c1 x1 +c2x2 +cnxn,线性规划模型一般形式：,1.线性规划的一般形化为标准型一般步骤,(1) Min z= cx 转化为max z =-cx,(2),加松弛变量yi,(3),加剩余变量yi,(4) 若存在可正可负变量xi 令,max z= 20 x1+30 x2 (1),标准型,(1), x1 +2x2 +x3 =8,(2), 4 x1 +0 x2 +x4 =16,(3), 0 x1 +4x2 +x5 =12,max z= 20 x1+30 x2,x1 +2x2 +x3 =84 x1 +0 x2 +x4 =160 x1 +4x2 +x5 =12x1 ,x2 ,x3 ,x4 ,x5,s.t,例 将下述线性规划问题化为标准型,Min z= - x1 +2x2 -3x3,无约束,标准型,max z = x1 -2x2 +3(x4 x5 )+0 x6 +0 x7,(1), x3 = x4 -x5 , x4 ,x5,(2), x1 +x2 +x3 +x6 =7,(3), x1 -x2 +x3 -x7 =2,合理下料问题,有长度为8米的某型号圆钢，现需要长度为2.5米的毛坯100根，长度为1.3米的毛坯200根，如何选者下料方式，所需总用料最省？,解：可能的下料方式：,设按第i种下料方式的圆钢xi根，i=1,2,3,4,min z= x1+x2 +x3 +x4,有一组决策变量,约束条件是决策变量的线性等式或不等式,目标函数是决策变量的线性函数,这样的规划问题称为线性规划.记为（LP）,例.某小区一个24小时营业便利店,一天各时段所需服务员最少人数如下表.根据实际情况,要求每个服务员必须连续工作八小时,试建立需服务员总人数最少的排班方案数学模型.,解：设各班次新增服务员数分别为x1,x2, x3, x4, x5, x6,则,min z= x1+x2+ x3+x4+x5+x6,且xi为整数,连续投资问题,某部门计划5年内用一百万投资下列项目：A：从第一年到第四年初需投资，此年末回收本利115%B: 第三年初需投资，第五年末回收本利125%，投资额40万C:第二年初需投资，第五年末回收本利140%，投资额30万D：每年初可购买公债，当年末归还，利息6%如何投资，五年后获利最大？,解：设第i年初投资项目A,B,C,D分别为xiA , xiB , xiC , xiD 万元,i=1,2,3,4,5,x1A+x1D=100,x2A+x2C+x2D=1.06 x1D ,x3A+x3B+x3D=1.06 x2D+1.15 x1A,x4A+x4D=1.06 x3D+1.15 x2A,x5D=1.06 x4D+1.15 x3A,x2C 40, x3B 30,xiA , xiB , xiC , xiD0 i=1,2,3,4,5.,Max Z= 1.15x4A +1.40 x2C +1.25x3B +1.06 x5D,s.t.,二、线性规划模型的求解,（一）图解法（n=3时）,（二）单纯形法,（三）数学软件：如LINDO软件,max z= c x,(LP),可行解：满足约束条件AX=b,X,最优解:可行解中使目标最优的。即X*D,且任意XD, CX* CX,可行集：所有可行解的集合,的X的值,制订生产计划,使每天获利最大,工厂生产两种产品A1,A2,已知生产单位产品情况如下：,设生产A1、A2分别x1、x2公斤,max z= 20 x1+30 x2 (1),（一）图解法（n=3时）,(1)在平面上作出可行集,A,B,C,D,3,4,由图解法直观得:n=2时,(LP)的可行集是凸多边形,最优解可以在其某个顶点处达到.,线性规划基本性质:(LP)的可行集是凸多面体,最优解可以在凸多面体的某个顶点处达到.,线性规划求解思路:通过代数的方法描述高维空间凸多面体的顶点,再使用经济的方法来求出达到极值的顶点.,x1,x2,0,(2)在可行集中找最优解,max z= 20 x1+30 x2 (1),（二）单纯形法,1.基、基本可行解的概念(顶点的代数描述),2.单纯形法一般步骤,引入松弛变量x3, x4, x5, 化为标准形:,显然A的秩为3, 任取3个线性无关的列向量,如P1 , P2 , P3称为一组基, 记为B =(P1 , P2 , P3 )。P1 , P2 , P3 称为基向量 , 基向量对应的变量 x1 ,x2 ,x3称为基变量, 其余列向量 P4 , P5 称为非基向量 , 记为N= (P4 , P5 ). 非基对应的变量 x4 ,x5 称为非基变量. A = (B, N), 相应x = (xB, xN) T, c = (cB, cN),令非基变量xN = 0, 解得基变量xB = B-1b, 称(xB, xN)为基解.,Ax = BxB + NxN = b, 则 xB = B-1b-B-1NxN ,解的所有变量的值都非负，则称为基可行解，此时的基称为可行基.,于是 f = cBxB + cNxN , Ax = BxB + NxN = b, 则 xB = B-1b-B-1NxN , f = cBB-1b + (cN cBB-1N)xN,将A写成A = (B, N), 相应x = (xB, xN) T, c = (cB, cN)基对应的变量xB称为基变量, 非基对应的变量xN称为非基变量.,令非基变量xN = 0, 解得基变量xB = B-1b, 称(xB, xN)为基解.,解的所有变量的值都非负，则称为基可行解，此时的基称为可行基.,基可行解对应的目标值为f = cBB-1b 。,若可行基进一步满足: cN cBB-1N0, 则对一切可行解x, 必有f(x) cBB-1b, 此时称基可行解x = (B-1b, 0) T为最优解.,另一个基本可行解,定理： (LP)的可行集的顶点与 (LP)的 基本可行解一一对应。,单纯形法基本思想：,目标,重复此,更优,过程,单纯形法基本步骤：,不是,最优解,更优,目标,重复此,过程,(LP)的某个基本可行解,最优解,(LP)的某个基,基可行解,另一个基,基本可行解,最优解,4. 基可行解是最优解的判定准则,因为 f = cBB-1b + (cN cBB-1N)xN，即 f - 0 xB + (cBB-1N- cN )xN = cBB-1b,5.基可行解的改进,改进方法：,返 回,Max z= 2x1 +3x2 +x3,解:本题特点是约束方程系数矩阵含单位子矩阵,A=(,),B0=(P4, P5),),=(,X0 =(0,0,0,3,9)T,Z0=8,Max z= 2x1 +3x2 +x3,Max2,3,1=3,x2进基,x4 =3-x1-x2 -x3 x5 =9-x1-4x2 -7x3,=3-x2 =9-4x2,x5出基,Min3/1,9/4=9/4,),(,),(,初等行变换,A=(,),),(,),(,B1=(P4, P2),),=(,一、单纯形法的基本思想1、顶点的逐步转移,即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。,根据线性规划问题的可行域是凸多边形或凸多面体，一个线性规划问题有最优解，就一定可以在可行域的顶点上找到。 于是，若某线性规划只有唯一的一个最优解，这个最优解所对应的点一定是可行域的一个顶点；若该线性规划有多个最优解，那么肯定在可行域的顶点中可以找到至少一个最优解。,顶点转移的依据？,转移条件？ 转移结果？ 使目标函数值得到改善 得到LP最优解，目标函数达到最优值 （单纯形法的由来？ ） 2需要解决的问题： (1)为了使目标函数逐步变优，怎麽转移？ (2)目标函数何时达到最优 判断标准是什麽？,二、单纯形法原理（用代数方法求解LP）,例1,第一步：引入非负的松弛变量x4,x5, 将该LP化为标准型,第二步：寻求初始可行基，确定基变量,对应的基变量是 x4，x5；,第三步：写出初始基本可行解和相应的目标函数值,两个关键的基本表达式：用非基变量表示基变量的表达式,用非基变量表示目标函数的11111表达式,请解释结果的经济含义 不生产任何产品，资源全部节余（x4=3，x5=9），三种产品的总利润为0！,第四步：分析两个基本表达式，看看目标函数是否可以改善？, 分析用非基变量表示目标函数的表达式 非基变量前面的系数均为正数，所以任何一个非基变量进基都能使Z值增加 通常把非基变量前面的系数叫“检验数”；, 选哪一个非基变量进基？ 选x2为进基变量（换入变量） 问题：能否选其他的非基变量进基？, 任意一个 任意一个正检验数对应的非基变量 最大正检验数对应的非基变量 排在最前面的正检验数对应的非基变量, 确定出基变量：问题讨论, x2进基意味着其取值从0变成一个正数（经济意义生产B产品），能否无限增大？ 当x2增加时，x4，x5如何变化？ 现在的非基变量是哪些？ 具体如何确定换出变量？,由用非基变量表示基变量的表达式,当x2增加时，x4，x5会减小，但有限度必须大于等于0，以保持解的可行性！于是,当x2的值从0增加到9/4时，x5首先变为0，此时x4=3/40因此选x5为出基变量（换出变量）。这种用来确定出基变量的规则称为 “最小比值原则”（或原则）。如果P10，会出现什麽问题？ 最小比值原则会失效！, 基变换新的基变量x2,x4；新的非基变量x1,x3,x5；写出用非基变量表示基变量的表达式：,可得新的基本可行解 X（1）=（0，9/4，0，3/4，0）T,由, 写出用非基变量表示目标函数的表达式:,可得相应的目标函数值为Z（1）=27/4检验数仍有正的返回进行讨论。,第五步：上述过程何时停止？当用非基变量表示目标函数的表达式中，非基变量的系数（检验数）全部非正时，当前的基本可行解就是最优解! 为什麽？,分析用非基变量表示目标函数的表达式，如果让负检验数所对应的变量进基，目标函数值将下降！,三、表格单纯形法： 1、 初始单纯形表的建立 (1)表格结构：,（2）表格设计依据： 把目标函数表达式改写成方程的形式，和原有的m个约束方程组成一个具有n+m+1个变量、m+1个方程的方程组：,取出系数写成增广矩阵的形式：,Xn+1，Xn+m所对应的系数列向量构成一个基,用矩阵的初等行变换将目标函数中基变量系数化为零,这时 变成0，相应的增广矩阵变成如下形式：,其中， ，j=1，2，n ；,（3）检验数的两种计算方法：利用矩阵的行变换，把目标函数表达式中基变量前面的系数变为0； 使用计算公式,增广矩阵的最后一行就是用非基变量表示目标函数的表达式， j（j=1，2，n）就是非基变量的检验数。,2、例1的表格单纯形法计算过程：,从最优表可知:该LP的 最优解是 X*=(1,2,0,0,0)T 相应的目标函数 最优值是Zmax=8,*,*,求解：,Max z= 4x1 +x2 +x3,解:本题约束方程系数矩阵不含单位子矩阵,*,*,阶段：,Max W= 4x1 +x2 +x3,单纯形法小结,求解思想 顶点的逐步转移， 条件是 使目标函数值不断得到改善。,表格单纯形法求解步骤,第一步：将LP化为标准型，并加以整理。 引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，并且约束方程组的系数阵中有一个单位阵。 （这一步计算机可自动完成） 确定初始可行基，写出初始基本可行解,第二步：最优性检验,计算检验数，检查：所有检验数是否 0？ 是结束，写出最优解和目标函数最优值；还有正检验数检查相应系数列 0？ 是结束，该LP无“有限最优解”！不属于上述两种情况，转入下一步基变换。 确定是停止迭代还是转入基变换？,选择（最大）正检验数对应的系数列为主元列，主元列对应的非基变量为换入变量； 最小比值对应的行为主元行，主元行对应的基变量为换出变量。,第三步：基变换,确定进基变量和出基变量。,利用矩阵的初等行变换把主元列变成单位向量，主元素变为1，进基变量对应的检验数变成0，从而得到一张新的单纯形表，返回第二步。,第四步 换基迭代（旋转运算、枢运算),完成一次迭代，得到新的基本可行解和相应的目标函数值,该迭代过程直至下列情况之一发生时停止 检验数行全部变为非正值；（得到最优解）或主元列 0 （最优解无界）,停止迭代的标志（停机准则）,计算机求解时的注意点,1、输入数据中的分数，需先化为小数再执行输入过程。2、每一张迭代表格中由基变量列（Basic）和B(i)列（解答列）可以读出现行解及相应的目标函数值，同时显示进基变量和出基变量，从而很容易识别主元列、主元行和主元素。3、最终表显示最优解、最优目标函数值及总的迭代次数。如遇该线性规划无可行解或无“有限最优解”，则屏幕将显示有关信息： NO feasible solution . 或 * * unbounded solution !,求解：,Max z= 5x1 +x2 +3x3,化为标准性,Max z= 5x1 +x2 +3x3,约束方程的系数矩阵不含单位子矩阵，两段法求解：1.构造辅助规划求得原问题的初始可行基;2.单纯形表求解原问题,（2） 两阶段法 第一阶段：建立辅助线性规划并求解，以判断原线性规划是否存在基本可行解。辅助线性规划的结构：目标函数W为所有人工变量之和的相反数，目标要求是使目标函数极大化，约束条件与原线性规划相同。,Max w= -x5,(FP),x5人工变量,求解结果W最优值=0即所有人工变量取值全为0（为什麽？），均为非基变量，最优解是原线性规划的一个基本可行解，转入第二阶段；W最优值=0但人工变量中有等于0的基变量，构成退化的基本可行解，可以转化为情况；如何转化？ 选一个不是人工变量的非基变量进基， 把在基中的人工变量替换出来,W最优值0至少有一个人工变量取值0,说明基变量中至少有1个人工变量,表明原问题没有可行解,讨论结束。,第二阶段： 将第一阶段的最优解作为初始可行解，目标函数换成原问题的目标函数，进行单纯形迭代，求出最优解。问题讨论:如何实施?需要重新建立初始单纯形表吗？,实施中，在第一阶段最优表格中划去人工变量列，将表头部分和CB列的价值系数换成原问题的价值系数(把目标函数换成原线性规划的目标函数)，继续迭代，直至求出最优解。,从最优表可知:该FP的最优解是 X*=(0,2,0,1,0)T相应的目标函数 最优值是Wmax=0,从最优表可知:原(LP)的最优解X*=(0,2,1,0)T 相应的目标函数最优值Zmax=5,*,*,*,例1 加工奶制品的生产计划,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/公斤，应否改变生产计划？,每天:,三、线性规划建模实例,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,模型分析与假设,比例性,可加性,连续性,xi对目标函数的“贡献”与xi取值成正比,xi对约束条件的“贡献”与xi取值成正比,xi对目标函数的“贡献”与xj取值无关,xi对约束条件的“贡献”与xj取值无关,xi取值连续,A1,A2每公斤的获利是与各自产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数,A1,A2每公斤的获利是与相互产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数,加工A1,A2的牛奶桶数是实数,线性规划模型,模型求解,图解法,约束条件,目标函数,z=c (常数) 等值线,在B(20,30)点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形的某个顶点取得。,模型求解,软件实现,LINDO 6.1,max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,DO RANGE (SENSITIVITY) ANALYSIS?,No,20桶牛奶生产A1, 30桶生产A2，利润3360元。,结果解释,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,原料无剩余,时间无剩余,加工能力剩余40,max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end,三种资源,“资源” 剩余为零的约束为紧约束（有效约束）,结果解释,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,最优解下“资源”增加1单位时“效益”的增量,原料增加1单位, 利润增长48,时间增加1单位, 利润增长2,加工能力增长不影响利润,影子价格,35元可买到1桶牛奶，要买吗？,35 48, 应该买！,聘用临时工人付出的工资最多每小时几元？,2元！,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,最优解不变时目标函数系数允许变化范围,DO RANGE(SENSITIVITY) ANALYSIS?,Yes,x1系数范围(64,96),x2系数范围(48,72),A1获利增加到 30元/千克，应否改变生产计划,x1系数由24 3=72增加为303=90，在允许范围内,不变！,(约束条件不变),现工厂决策者考虑停产A1,A2,接受外来加工,问：接受外来加工可行条件？,设原材料每桶 y1元，机器价格每小时y2元，加工能力每公斤y3元,工厂同意合作前提:,另一方接受的可能性：,(LP)的对偶问题,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,设该厂现有生产条件下原材料每桶 价值y1元,机器价格每小时价值y2元,加工能力每公斤价值y3元,(LP),(DP),(DP)称为(LP)的对偶问题,对称形式的对偶问题,(LP),max z= cT x,(DP),min w=bT y,性质：若x0和y0分别是(LP)和(DP)的可行解，则bT y0 cT x0;,bT y0= cT x0,x0和y0分别是(LP)和(DP)的最优解,(LP),(DP),1.(DP)中约束与(LP)中变量符号一致,2.(DP)中变量与(LP)中约束符号相反,结果解释,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,影子价格有意义时约束右端的允许变化范围,原料最多增加10,时间最多增加53,35元可买到1桶牛奶，每天最多买多少？,最多买10桶!,(目标函数不变),例2 奶制品的生产销售计划,在例1基础上深加工,制订生产计划，使每天净利润最大,30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？,50桶牛奶, 480小时,至多100公斤A1,B1，B2的获利经常有10%的波动，对计划有无影响？,出售x1 千克 A1, x2 千克 A2，,X3千克 B1, x4千克 B2,原料供应,劳动时间,加工能力,决策变量,目标函数,利润,约束条件,非负约束,x5千克 A1加工B1， x6千克 A2加工B2,附加约束,模型求解,软件实现,LINDO 6.1,OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 NO. ITERATIONS= 2,OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 NO. ITERATIONS= 2,结果解释,每天销售168 千克A2和19.2 千克B1， 利润3460.8（元）,8桶牛奶加工成A1，42桶牛奶加工成A2，将得到的24千克A1全部加工成B1,除加工能力外均为紧约束,结果解释,OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000,增加1桶牛奶使利润增长3.1612=37.92,增加1小时时间使利润增长3.26,30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？,投资150元增加5桶牛奶，可赚回189.6元。（大于增加时间的利润增长）,结果解释,B1,B2的获利有10%的波动，对计划有无影响,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 24.000000 1.680000 INFINITY X2 16.000000 8.150000 2.100000 X3 44.000000 19.750002 3.166667 X4 32.000000 2.026667 INFINITY X5 -3.000000 15.800000 2.533334 X6 -3.000000 1.520000 INFINITY ,B1获利下降10%，超出X3 系数允许范围,B2获利上升10%，超出X4 系数允许范围,波动对计划有影响,生产计划应重新制订：如将x3的系数改为39.6