数学建模优化模型课件

数学建模-------优化模型数学建模-------优化模型第二讲线性规划建模方法第三讲整数规划建模方法第四讲指派问题第六讲图论简介第五讲动态规划建模第一讲数学建模概论第二讲线性规划建模方法第三讲整数规划建模方法第四讲第一章数学建模概论1.1数学建模由来1.2从现实对象到数学模型1.3数学建模的重要意义1.4数学建模的方法和步骤1.5数学模型的特点和分类1.6近几年国内竞赛题1.7怎样学习数学建模与竞赛组队1.8撰写数学建模论文第一章数学建模概论1.1数学建模由来•1985年由美国工业与应用数学学会和美国运筹学会联合主办大学生数学建模竞赛（MCM)1.1数学建模由来•在上世纪70年代末和80年代初，英国著名的剑桥大学专门为研究生开设了数学建模课程

•数学建模作为一门崭新的课程在20世纪80年代进入我国高校，萧树铁先生1983年在清华大学首次为本科生讲授数学模型课程，他是我国高校开设数学模型课程的创始人•1985年由美国工业与应用数学学会和美国运筹•1992年由中国工业与应用数学学会举办全国大学生数学建模竞赛（94年起由国家教委高教司和中国工业与应用数学学会共同举办）•1987年由姜启源教授编写了我国第一本数学建模教材•2005年全国数学建模竞赛，共有来自全国30个省、市、自治区的795所高校8492支队（其中甲组6556队、乙组1936队）、25476名来自各个专业的大学生参加本次竞赛•1992年由中国工业与应用数学学会举办全国大•

95年我校参加全国大学生数学建模竞赛，最初开设选修课是因为参加数学建模竞赛的需要，选修的学生数较少，而且必须是往年成绩较优的学生才允许选修

•

97年学校决定在原有基础上，在部分专业开设数学建模必修课，并同时对其他专业开设数学建模选修课

•2000年起结合课程教学与竞赛安排，在每年五月底或六月初举办全校大学生数学建模竞赛

•近两年数学建模课程每年选课人数2000余人•95年我校参加全国大学生数学建模竞赛，最初开设选修课是因•1995-2009年学生参加全国大学生数学建模竟赛及获奖情况：

年份参赛全国全国省一等奖省二等奖省三等奖队数一等奖二等奖19953111119964111119977222111998742611999712312000101332200110213220021512351200315233362004161324422413832819302532373318

•1995-2009年学生参加全国大学生数学建模竟赛及获奖2006年获一等奖1队，二等奖3队2007年获一等奖1队，二等奖5队2008年获一等奖4队，二等奖4队2009年获一等奖2队，二等奖2队

•2006-2009年学生参加美国大学生数学建模竟赛及获奖情况：

2006年获一等奖1队，二等奖3队•2006-2009年玩具、照片、飞机、火箭模型……~实物模型地图、电路图、分子结构图……~符号模型模型是为了一定目的，对客观事物的一部分进行简缩、抽象、提炼出来的原型的替代物模型集中反映了原型中人们需要的那一部分特征1.2

从现实对象到数学模型我们常见的模型玩具、照片、飞机、火箭模型……~实物模型地图、电路图、分你碰到过的数学模型——“航行问题”用x

表示船速，y表示水速，列出方程：答：船速每小时20千米/小时.甲乙两地相距750千米，船从甲到乙顺水航行需30小时，从乙到甲逆水航行需50小时，问船的速度是多少?x=20y=5求解你碰到过的数学模型——“航行问题”用x表示船速，y表示航行问题建立数学模型的基本步骤

作出简化假设（船速、水速为常数）；

用符号表示有关量（x,y表示船速和水速）；

用物理定律（匀速运动的距离等于速度乘以时间）列出数学式子（二元一次方程）；

求解得到数学解答（x=20,y=5）；

回答原问题（船速每小时20千米/小时）。航行问题建立数学模型的基本步骤作出简化假设（船速、水速为常数学模型(MathematicalModel)和数学建模（MathematicalModeling)对于一个现实对象，为了一个特定目的，根据其内在规律，作出必要的简化假设，运用适当的数学工具，得到的一个数学结构。建立数学模型的全过程（包括表述、求解、解释、检验等）数学模型数学建模数学模型(MathematicalModel)和对于一1.3

数学建模的重要意义

电子计算机的出现及飞速发展；

数学以空前的广度和深度向一切领域渗透。数学建模作为用数学方法解决实际问题的第一步，越来越受到人们的重视。

在一般工程技术领域数学建模仍然大有用武之地；

在高新技术领域数学建模几乎是必不可少的工具；

数学进入一些新领域，为数学建模开辟了许多处女地。1.3数学建模的重要意义电子计算机的出现及飞速发展；数学建模的具体应用

分析与设计

预报与决策

控制与优化

规划与管理数学建模计算机技术知识经济如虎添翼数学建模的具体应用分析与设计预报与决策控制与优化规

数学建模的基本方法机理分析测试分析根据对客观事物特性的认识，找出反映内部机理的数量规律将对象看作“黑箱”,通过对量测数据的统计分析，找出与数据拟合最好的模型机理分析没有统一的方法，主要通过实例研究(CaseStudies)来学习。以下建模主要指机理分析。二者结合用机理分析建立模型结构,用测试分析确定模型参数1.4

数学建模的方法和步骤数学建模的基本方法机理分析测试分析根据对客观事物特性的认识

数学建模的一般步骤模型准备模型假设模型构成模型求解模型分析模型检验模型应用模型准备了解实际背景明确建模目的搜集有关信息掌握对象特征形成一个比较清晰的‘问题’数学建模的一般步骤模型准备模型假设模型构成模型求解模型分析模型假设针对问题特点和建模目的作出合理的、简化的假设在合理与简化之间作出折中模型构成用数学的语言、符号描述问题发挥想像力使用类比法尽量采用简单的数学工具

数学建模的一般步骤模针对问题特点和建模目的作出合理的、简化的假设在合理与简化之模型求解各种数学方法、软件和计算机技术如结果的误差分析、统计分析、模型对数据的稳定性分析模型分析模型检验与实际现象、数据比较，检验模型的合理性、适用性模型应用

数学建模的一般步骤模型各种数学方法、软件和计算机技术如结果的误差分析、统计分析数学建模的全过程现实对象的信息数学模型现实对象的解答数学模型的解答表述求解解释验证(归纳)(演绎)表述求解解释验证根据建模目的和信息将实际问题“翻译”成数学问题选择适当的数学方法求得数学模型的解答将数学语言表述的解答“翻译”回实际对象用现实对象的信息检验得到的解答实践现实世界数学世界理论实践数学建模的全过程现实对象的信息数学模型现实对象的解答数学模型1.5

数学模型的特点和分类模型的逼真性和可行性模型的渐进性模型的稳定性模型的可转移性模型的非预制性模型的条理性模型的技艺性模型的局限性

数学模型的特点1.5数学模型的特点和分类模型的逼真性和可行性模型的渐进数学模型的分类应用领域人口、交通、经济、生态……数学方法初等数学、微分方程、规划、统计……表现特性描述、优化、预报、决策……建模目的了解程度白箱灰箱黑箱确定和随机静态和动态线性和非线性离散和连续数学模型的分类应用领域人口、交通、经济、生态……数学方法1.6近几年全国大学生数学建模竞赛题1.6近几年全国大学生数学建模竞赛题数学建模优化模型ppt课件数学建模优化模型ppt课件数学建模优化模型ppt课件数学建模优化模型ppt课件1.7怎样学习数学建模与竞赛组队数学建模与其说是一门技术，不如说是一门艺术技术大致有章可循艺术无法归纳成普遍适用的准则想像力洞察力判断力

学习、分析、评价、改进别人作过的模型

亲自动手，认真作几个实际题目1.7怎样学习数学建模与竞赛组队数学建模与其说是一门根据数学建模竞赛章程，三人组成一队。

这三人中必须一人数学基础较好，

一人应用数学软件（如Matlab,lindo,maple等）和编程（如c,Matlab,vc++等）的能力较强，

一人科技论文写作的水平较好。

•科技论文的写作要求整篇论文的结构严谨，语言要有逻辑性，用词要准确。

•

三人之间要能够配合得起来。若三人之间配合不好，会降低效率，导致整个建模的失败。根据数学建模竞赛章程，三人组成一队。这三人中必须一人数•

如果可能的话，最好是数学好的懂得编程的一些知识，编程好的了解建模，搞论文写作也要了解建模，这样会合作得更好。因为数学好的在建立模型方案时会考虑到编程的便利性，以利于编程；编程好的能够很好地理解模型，论文写作的能够更好、更完全地阐述模型。否则会出现建立的模型不利于编程，程序不能完全概括模型，论文写作时会漏掉一些不经意的东西。•在合作的过程中，最好是能够在三人中找出一个所谓的组长，即要能够总揽全局，包括任务的分配，相互间的合作和进度的安排。•如果可能的话，最好是数学好的懂得编程的一些知识，编程好的•在建模过程中出现意见不统一——如何处理？仅我个人的经验而言，除了一般的理解与尊重外，我觉得最重要的一点就是“给我一个相信你的理由”和“相信我，我的理由是……”，不要作无谓的争论。

•在建模过程中出现意见不统一——如何处理？仅我个人的经验而言1.8撰写数学建模论文1、摘要:问题、模型、方法、结果2、问题重述3、模型假设与记号4、分析与建立模型5、模型求解6、模型检验7、模型推广8、参考文献9、附录1.8撰写数学建模论文1、摘要:问题、模型、方法、第二讲线性规划建模方法一、从现实问题到线性规划模型二、线性规划模型的求解三、线性规划建模实例四、线性规划的对偶问题第二讲线性规划建模方法一、从现实问题到线性规划模型二、线例1加工奶制品的生产计划1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1

制订生产计划，使每天获利最大35元可买到1桶牛奶，买吗？若买，每天最多买多少?

可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到30元/公斤，应否改变生产计划？每天:一、从现实问题到线性规划模型例1加工奶制品的生产计划1桶牛奶3公斤A112小1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤x1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

每天获利约束条件非负约束

线性规划模型(LP)时间480小时至多加工100公斤A1

50桶牛奶每天1桶牛奶3公斤A112小时8小时4公斤A2或获利2模型分析与假设

比例性可加性连续性xi对目标函数的“贡献”与xi取值成正比xi对约束条件的“贡献”与xi取值成正比xi对目标函数的“贡献”与xj取值无关xi对约束条件的“贡献”与xj取值无关xi取值连续A1,A2每公斤的获利是与各自产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数线性规划模型模型分析与假设比例性可加性连续性xi对目标函数的“贡A1A2现有资源设备128台时甲4016公斤乙0412公斤利润2030（元）制订生产计划,使每天获利最大例2工厂生产两种产品A1,A2,已知生产单位产品情况如表：设生产A1、A2分别x1、x2公斤

maxz=20x1+30x2(1)目标函数约束条件决策变量一、从现实问题到线性规划模型A1A2现有资源设备128台时甲4016公斤乙0412公斤线性规划模型标准型:maxz=c1x1+c2x2+…+cnxn(LP)线性规划模型标准型矩阵表示：maxz=c

x

max(min)z=c1x1+c2x2+…+cnxn线性规划模型一般形式：线性规划模型标准型:maxz=c1x1+c2x2+…1.线性规划的一般形化为标准型一般步骤(1)Minz=cx转化为maxz’=-cx(2)加松弛变量yi

(3)加剩余变量yi(4)若存在可正可负变量xi

令1.线性规划的一般形化为标准型(1)Minz=cx

maxz=20x1+30x2(1)标准型(1),

x1+2x2+x3=8(2),4

x1+0

x2+x4=16(3),0x1+4x2+x5=12

maxz=20x1+30x2

x1+2x2+x3=84

x1+0

x2+x4=160x1+4x2+x5=12x1,x2,x3,x4,x5s.tmaxz=20x1+30x2(1)标准型(1)例将下述线性规划问题化为标准型Minz=-

x1+2x2-3x3无约束标准型maxz’=

x1-2x2+3(x4–x5)+0x6+0x7(1),x3=

x4-x5,x4,x5(2),

x1+x2+x3+x6=7(3),

x1-x2+x3-x7=2例将下述线性规划问题化为标准型Minz=-x1+合理下料问题有长度为8米的某型号圆钢，现需要长度为2.5米的毛坯100根，长度为1.3米的毛坯200根，如何选者下料方式，所需总用料最省？解：可能的下料方式：2.51.3130222314406设按第i种下料方式的圆钢xi根，i=1,2,3,4

minz=x1+x2+x3+x4有一组决策变量,约束条件是决策变量的线性等式或不等式,目标函数是决策变量的线性函数,这样的规划问题称为线性规划.记为（LP）合理下料问题有长度为8米的某型号圆钢，现需要长度为2.5米的例.某小区一个24小时营业便利店,一天各时段所需服务员最少人数如下表.根据实际情况,要求每个服务员必须连续工作八小时,试建立需服务员总人数最少的排班方案数学模型.班次123456时间2-66-1010-1414-1818-2222-2人48107124解：设各班次新增服务员数分别为x1,x2,x3,x4,x5,x6,则minz=

x1+x2+x3+x4+x5+x6且xi为整数例.某小区一个24小时营业便利店,一天各时段所需服务员最少人连续投资问题某部门计划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,5x1A+x1D=100,x2A+x2C+x2D=1.06x1D,x3A+x3B+x3D=1.06x2D+1.15

x1A,x4A+x4D=1.06x3D+1.15

x2A,x5D=1.06x4D+1.15

x3A,x2C≤40,x3B≤30,xiA,xiB,xiC,

xiD≥0i=1,2,3,4,5.MaxZ=1.15x4A+1.40x2C+1.25x3B+1.06x5Ds.t.连续投资问题某部门计划5年内用一百万投资下列项目：解：设第i二、线性规划模型的求解（一）图解法（n<=3时）（二）单纯形法（三）数学软件：如LINDO软件二、线性规划模型的求解（一）图解法（n<=3时）（二）单纯形maxz=c

x(LP)可行解：满足约束条件AX=b,X最优解:可行解中使目标最优的。即X*∈D,且任意X∈D,CX*≥CX可行集：所有可行解的集合的X的值maxz=cx(LP)可行解：满足约束条件AX=b,XA1A2现有资源设备128台时甲4016公斤乙0412公斤利润2030（元）制订生产计划,使每天获利最大工厂生产两种产品A1,A2,已知生产单位产品情况如下：设生产A1、A2分别x1、x2公斤

maxz=20x1+30x2(1)A1A2现有资源设备128台时甲4016公斤乙0412公斤（一）图解法（n<=3时）(1)在平面上作出可行集ABCD34Z=60Z=140Z=0由图解法直观得:n=2时,(LP)的可行集是凸多边形,最优解可以在其某个顶点处达到.线性规划基本性质:(LP)的可行集是凸多面体,最优解可以在凸多面体的某个顶点处达到.线性规划求解思路:通过代数的方法描述高维空间凸多面体的顶点,再使用经济的方法来求出达到极值的顶点.x1x20(2)在可行集中找最优解

maxz=20x1+30x2(1)（一）图解法（n<=3时）(1)在平面上作出可行集ABCD3（二）单纯形法1.基、基本可行解的概念(顶点的代数描述)2.单纯形法一般步骤（二）单纯形法1.基、基本可行解的概念(顶点的代数描述)2.引入松弛变量x3,x4,x5,化为标准形:引入松弛变量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,解的所有变量的值都非负，则称为基可行解，此时的基称为可行基.显然A的秩为3,任取3个线性无关的列向量,如P1,P2于是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-1N≥0,则对一切可行解x,必有f(x)≥cBB-1b,此时称基可行解x=(B-1b,0)T为最优解.于是f=cBxB+cNxN,Ax=另一个基本可行解定理：(LP)的可行集的顶点与(LP)的

基本可行解一一对应。单纯形法基本思想：目标重复此更优过程单纯形法基本步骤：不是最优解更优目标重复此过程(LP)的某个基本可行解最优解(LP)的某个基基可行解另一个基基本可行解最优解另一个基定理：(LP)的可行集的顶点与(LP)的单纯形法4.基可行解是最优解的判定准则因为f=cBB-1b+(cN–cBB-1N)xN，即f-0•xB+(cBB-1N-cN)xN=cBB-1b4.基可行解是最优解的判定准则因为f=cBB-1b5.基可行解的改进5.基可行解的改进改进方法：返回改进方法：返回Maxz=2x1+3x2+x3解:本题特点是约束方程系数矩阵含单位子矩阵1111014701

A=()1001

B0=(P4,P5))=(X0=(0,0,0,3,9)TZ0=8Maxz=2x1+3x2+x3A1A2利润甲112乙143丙174资源39Max{2,3,1}=3x2进基x4=3-x1-x2-x3x5=9-x1-4x2-7x3=3-x2=9-4x2x5出基Min{3/1,9/4}=9/4)(14→)(01初等行变换111103147019

A=()→1111031/417/401/49/4

)(→3/40–3/41–1/43/41/417/401/49/4

)(B1=(P4,P2))=(1001

Maxz=2x1+3x2+x3解:本题特点是约束一、单纯形法的基本思想

1、顶点的逐步转移

即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。一、单纯形法的基本思想

1、顶点的逐步转移即

根据线性规划问题的可行域是凸多边形或凸多面体，一个线性规划问题有最优解，就一定可以在可行域的顶点上找到。

于是，若某线性规划只有唯一的一个最优解，这个最优解所对应的点一定是可行域的一个顶点；若该线性规划有多个最优解，那么肯定在可行域的顶点中可以找到至少一个最优解。顶点转移的依据？根据线性规划问题的可行域是凸多边形或凸多面体

转移条件？转移结果？使目标函数值得到改善得到LP最优解，目标函数达到最优值（单纯形法的由来？）

2．需要解决的问题：

(1)为了使目标函数逐步变优，怎麽转移？

(2)目标函数何时达到最优——

判断标准是什麽？

转移条件？二、单纯形法原理（用代数方法求解LP）劳动力原材料利润A112B143C173现有资源39例1二、单纯形法原理（用代数方法求解LP）劳动力原材料利润A11第一步：引入非负的松弛变量x4,x5,将该LP化为标准型第一步：引入非负的松弛变量x4,x5,将该LP化为标准型第二步：寻求初始可行基，确定基变量对应的基变量是x4，x5；

第三步：写出初始基本可行解和相应的目标函数值第二步：寻求初始可行基，确定基变量对应的基变量是x两个关键的基本表达式：①用非基变量表示基变量的表达式两个关键的基本表达式：②用非基变量表示目标函数的11111表达式请解释结果的经济含义——不生产任何产品，资源全部节余（x4=3，x5=9），三种产品的总利润为0！②用非基变量表示目标函数的11111表达式请解释结果的经济含第四步：分析两个基本表达式，看看目标函数是否可以改善？①分析用非基变量表示目标函数的表达式

非基变量前面的系数均为正数，所以任何一个非基变量进基都能使Z值增加通常把非基变量前面的系数叫“检验数”；第四步：分析两个基本表达式，看看目标函数是否可以改善？①②选哪一个非基变量进基？

选x2为进基变量（换入变量）问题：能否选其他的非基变量进基？

任意一个

任意一个正检验数对应的非基变量

最大正检验数对应的非基变量

排在最前面的正检验数对应的非基变量×

②选哪一个非基变量进基？任意一个×③确定出基变量：问题讨论

x2进基意味着其取值从0变成一个正数（经济意义——生产B产品），能否无限增大？

当x2增加时，x4，x5如何变化？

现在的非基变量是哪些？

具体如何确定换出变量？③确定出基变量：x2进基意味着其取值从0变成一个正数（由用非基变量表示基变量的表达式

当x2增加时，x4，x5会减小，但有限度——必须大于等于0，以保持解的可行性！于是由用非基变量表示基变量的表达式当x2增加时，x4，x5会减

当x2的值从0增加到9/4时，x5首先变为0，此时x4=3/4>0因此选x5为出基变量（换出变量）。这种用来确定出基变量的规则称为“最小比值原则”（或θ原则）。如果P1≤0，会出现什麽问题？

最小比值原则会失效！当x2的值从0增加到9/4时，x5首先变为0，此时

基变换新的基变量——x2,x4；新的非基变量x1,x3,x5；写出用非基变量表示基变量的表达式：可得新的基本可行解

X（1）=（0，9/4，0，3/4，0）T由基变换可得新的基本可行解由⑤写出用非基变量表示目标函数的表达式:可得相应的目标函数值为Z（1）=27/4检验数仍有正的返回①进行讨论。⑤写出用非基变量表示目标函数的表达式:可得相应的目标函数值第五步：上述过程何时停止？当用非基变量表示目标函数的表达式中，非基变量的系数（检验数）全部非正时，当前的基本可行解就是最优解!

为什麽？——分析用非基变量表示目标函数的表达式，如果让负检验数所对应的变量进基，目标函数值将下降！第五步：上述过程何时停止？——分析用非基变量表示目标函数的表三、表格单纯形法：

1、

初始单纯形表的建立

(1)表格结构：

x1x2x3

x4x523300z11110147013x49x523300z三、表格单纯形法：x1x2x3（2）表格设计依据：把目标函数表达式改写成方程的形式，和原有的m个约束方程组成一个具有n+m+1个变量、m+1个方程的方程组：（2）表格设计依据：取出系数写成增广矩阵的形式：

Xn+1，…，Xn+m所对应的系数列向量构成一个基取出系数写成增广矩阵的形式：Xn+1，…，Xn+m所对应的用矩阵的初等行变换将目标函数中基变量系数化为零,这时变成0，相应的增广矩阵变成如下形式：其中，，j=1，2，…，n；

用矩阵的初等行变换将目标函数中基变量系数化为零,这时（3）检验数的两种计算方法：①利用矩阵的行变换，把目标函数表达式中基变量前面的系数变为0；②使用计算公式——

增广矩阵的最后一行就是用非基变量表示目标函数的表达式，σj（j=1，2，…，n）就是非基变量的检验数。（3）检验数的两种计算方法：增广矩阵的最后2、例1的表格单纯形法计算过程：

x1x2x3x4x5

23300z111103x4147019x5

23300z3/4

0

-3/4

1

-1/43/4x41/417/401/49/4x25/40–9/40-3/4z-27/410-14/3-1/31x1012-1/31/32x200-1-5/3-1/3z-8从最优表可知:该LP的最优解是

X*=(1,2,0,0,0)T

相应的目标函数最优值是Zmax=8**2、例1的表格单纯形法计算过程：x1x2求解：Maxz=4x1+x2+x3解:本题约束方程系数矩阵不含单位子矩阵√√√*x1x2x3x4x523100z111103x4147019x523100z3/4

0

-3/4

1

-1/43/4x41/417/401/49/4x25/40–17/40-3/4z-27/4√√√*10-14/3-1/31x1012-1/31/32x200-3-5/3-1/3Z-8阶段Ⅰ：MaxW=4x1+x2+x3求解：Maxz=4x1+x2+x3解:本题约束方单纯形法小结

求解思想－－

顶点的逐步转移，

条件是使目标函数值不断得到改善。单纯形法小结求解思想－－表格单纯形法求解步骤第一步：将LP化为标准型，并加以整理。引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，并且约束方程组的系数阵中有一个单位阵。

（这一步计算机可自动完成）

确定初始可行基，写出初始基本可行解表格单纯形法求解步骤第一步：将LP化为标准型，并加以整理。第二步：最优性检验计算检验数，检查：所有检验数是否≤0？

是——结束，写出最优解和目标函数最优值；还有正检验数——检查相应系数列≤

0？是——结束，该LP无“有限最优解”！不属于上述两种情况，转入下一步—基变换。

确定是停止迭代还是转入基变换？第二步：最优性检验计算检验数，检查：

选择（最大）正检验数对应的系数列为主元列，主元列对应的非基变量为换入变量；最小比值对应的行为主元行，主元行对应的基变量为换出变量。第三步：基变换确定进基变量和出基变量。选择（最大）正检验数对应的系数列为主元列，主元列

利用矩阵的初等行变换把主元列变成单位向量，主元素变为1，进基变量对应的检验数变成0，从而得到一张新的单纯形表，返回第二步。第四步换基迭代（旋转运算、枢运算)完成一次迭代，得到新的基本可行解和相应的目标函数值利用矩阵的初等行变换把主元列变成单位向量，主元素变为该迭代过程直至下列情况之一发生时停止

检验数行全部变为非正值；（得到最优解）或主元列≤

0（最优解无界）

停止迭代的标志（停机准则）该迭代过程直至下列情况之一发生时停止停止迭代的标志计算机求解时的注意点1、输入数据中的分数，需先化为小数再执行输入过程。2、每一张迭代表格中由基变量列（Basic）和B(i)列（解答列）可以读出现行解及相应的目标函数值，同时显示进基变量和出基变量，从而很容易识别主元列、主元行和主元素。3、最终表显示最优解、最优目标函数值及总的迭代次数。如遇该线性规划无可行解或无“有限最优解”，则屏幕将显示有关信息：

NOfeasiblesolution.

或**unboundedsolution!!!计算机求解时的注意点1、输入数据中的分数，需先化为小数再执行求解：Maxz=5x1+x2+3x3化为标准性Maxz=5x1+x2+3x3约束方程的系数矩阵不含单位子矩阵，两段法求解：1.构造辅助规划求得原问题的初始可行基;2.单纯形表求解原问题求解：Maxz=5x1+x2+3x3化为标准性M（2）

两阶段法

第一阶段：建立辅助线性规划并求解，以判断原线性规划是否存在基本可行解。辅助线性规划的结构：目标函数W为所有人工变量之和的相反数，目标要求是使目标函数极大化，约束条件与原线性规划相同。Maxw=-x5(FP)x5人工变量（2）两阶段法Maxw=-x5(FP)x5人工变量

求解结果①W最优值=0——即所有人工变量取值全为0（为什麽？），均为非基变量，最优解是原线性规划的一个基本可行解，转入第二阶段；②W最优值=0——但人工变量中有等于0的基变量，构成退化的基本可行解，可以转化为情况①；如何转化？

选一个不是人工变量的非基变量进基，把在基中的人工变量替换出来③W最优值>0——至少有一个人工变量取值>0,说明基变量中至少有1个人工变量,表明原问题没有可行解,讨论结束。求解结第二阶段：

将第一阶段的最优解作为初始可行解，目标函数换成原问题的目标函数，进行单纯形迭代，求出最优解。问题讨论:如何实施?需要重新建立初始单纯形表吗？

实施中，在第一阶段最优表格中划去人工变量列，将表头部分和CB列的价值系数换成原问题的价值系数(把目标函数换成原线性规划的目标函数)，继续迭代，直至求出最优解。第二阶段：实施中，在第一阶段最优表格中划去人工变

x5

0000-1w211103x4-120014x5

-12000w+45/2

0

1

1

-1/21x4-1/21001/22x20000-1w从最优表可知:该FP的最优解是X*=(0,2,0,1,0)T相应的目标函数最优值是Wmax=0x1x2x3x4

5130z5/2

0

1

1

1x4-1/21002x211/2030z-21

0

2/5

2/52/5x1011/5

1/5

11/5x2004/5-11/5z-21/55/2

0

1

1

1x3-1/21002x2-200-3z-5从最优表可知:原(LP)的最优解X*=(0,2,1,0)T

相应的目标函数最优值Zmax=5***

例1加工奶制品的生产计划1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1

制订生产计划，使每天获利最大35元可买到1桶牛奶，买吗？若买，每天最多买多少?

可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到30元/公斤，应否改变生产计划？每天:三、线性规划建模实例例1加工奶制品的生产计划1桶牛奶3公斤A112小1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤x1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

每天获利约束条件非负约束

线性规划模型(LP)时间480小时至多加工100公斤A1

50桶牛奶每天1桶牛奶3公斤A112小时8小时4公斤A2或获利2模型分析与假设

比例性可加性连续性xi对目标函数的“贡献”与xi取值成正比xi对约束条件的“贡献”与xi取值成正比xi对目标函数的“贡献”与xj取值无关xi对约束条件的“贡献”与xj取值无关xi取值连续A1,A2每公斤的获利是与各自产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数线性规划模型模型分析与假设比例性可加性连续性xi对目标函数的“贡模型求解

图解法

x1x20ABCDl1l2l3l4l5约束条件目标函数

Z=0Z=2400Z=3360z=c(常数)~等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。模型求解图解法x1x20ABCDl1l2l3l4l5约束模型求解

软件实现

LINDO6.1max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产A1,30桶生产A2，利润3360元。模型求解软件实现LINDO6.1max72x1+6结果解释

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROW

SLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料无剩余时间无剩余加工能力剩余40max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end三种资源“资源”剩余为零的约束为紧约束（有效约束）结果解释OBJECTIVEFUNCTIONVA结果解释

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000NO.ITERATIONS=2最优解下“资源”增加1单位时“效益”的增量原料增加1单位,利润增长48时间增加1单位,利润增长2加工能力增长不影响利润影子价格35元可买到1桶牛奶，要买吗？35<48,应该买！

聘用临时工人付出的工资最多每小时几元？2元！结果解释OBJECTIVEFUNCTIORANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最优解不变时目标函数系数允许变化范围DORANGE(SENSITIVITY)ANALYSIS?

Yesx1系数范围(64,96)

x2系数范围(48,72)A1获利增加到30元/千克，应否改变生产计划x1系数由243=72增加为303=90，在允许范围内不变！(约束条件不变)RANGESINWHICHTHEBASISISU现工厂决策者考虑停产A1,A2,接受外来加工问：接受外来加工可行条件？设原材料每桶

y1元，机器价格每小时y2元，加工能力每公斤y3元工厂同意合作前提:另一方接受的可能性：(LP)的对偶问题现工厂决策者考虑停产A1,A2,接受外来加工问：接受外来加工

35元可买到1桶牛奶，买吗？若买，每天最多买多少?设该厂现有生产条件下原材料每桶价值y1元,机器价格每小时价值y2元,加工能力每公斤价值y3元(LP)(DP)(DP)称为(LP)的对偶问题35元可买到1桶牛奶，买吗？若买，每天最多买多少?设该厂现对称形式的对偶问题(LP)maxz=cT

x(DP)minw=bT

y性质：若x0和y0分别是(LP)和(DP)的可行解，则bTy0≥cTx0;bTy0=cTx0x0和y0分别是(LP)和(DP)的最优解对称形式的对偶问题(LP)maxz=cTx(DP)mi(LP)(DP)1.(DP)中约束与(LP)中变量符号一致2.(DP)中变量与(LP)中约束符号相反(LP)(DP)1.(DP)中约束与(LP)中变量符号一致2结果解释

RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加5335元可买到1桶牛奶，每天最多买多少？最多买10桶!(目标函数不变)结果解释RANGESINWHICHTHEBASIS例2奶制品的生产销售计划

在例1基础上深加工1桶牛奶3千克A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤0.8千克B12小时,3元1千克获利44元/千克0.75千克B22小时,3元1千克获利32元/千克制订生产计划，使每天净利润最大30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？50桶牛奶,480小时至多100公斤A1

B1，B2的获利经常有10%的波动，对计划有无影响？例2奶制品的生产销售计划在例1基础上深加工1桶牛奶1桶牛奶

3千克A1

12小时8小时4千克A2

或获利24元/千克获利16元/kg

0.8千克

B12小时,3元1千克获利44元/千克0.75千克B22小时,3元1千克获利32元/千克出售x1千克A1,

x2千克A2，

X3千克B1,x4千克B2原料供应

劳动时间

加工能力

决策变量

目标函数

利润约束条件非负约束

x5千克A1加工B1，x6千克A2加工B2附加约束

1桶牛奶3千克A112小时8小时4千克A2或模型求解

软件实现

LINDO6.1OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No模型求解软件实现LINDO6.1OBJ

OBJECTIVEFUNCTIONVALUE1)3460.800

VARIABLEVALUEREDUCEDCOST

X10.0000001.680000

X2168.0000000.000000

X319.2000010.000000

X40.0000000.000000

X524.0000000.000000

X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2结果解释每天销售168千克A2和19.2千克B1，利润3460.8（元）8桶牛奶加工成A1，42桶牛奶加工成A2，将得到的24千克A1全部加工成B1

除加工能力外均为紧约束OBJECTIVEFUNCTIONVA结果解释OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES