《数学建模与大学生数学建模竞赛.ppt》由会员分享，可在线阅读，更多相关《数学建模与大学生数学建模竞赛.ppt（149页珍藏版）》请在三一办公上搜索。
1、数学建模与大学生数学建模竞赛,一、数学建模,数学建模是一门新兴的学科，20世纪70年代初诞生于英、美等现代工业国家。由于新技术特别是计算机技术的飞速发展，大量的实际问题需要用计算机来解决，而计算机与实际问题之间需要数学模型来沟通，所以这门学科在短短几十年的时间迅速辐射至全球大部分国家和地区。80年代初，我国高等院校也陆续开设了数学建模课程，随着数学建模教学活动（包括数学建模课程、数学建模竞赛和数学建模试验课程等）的开展，这门学科越来越得到重视，也深受广大师生的喜爱。,什么是数学模型呢？数学模型（Mathematical Model）是指对于现实世界的某一特定对象，为了某个特定的目的，做出一些必
2、要的简化和假设，运用适当的数学工具得到一个数学结构。数学结构是指数学符号、数学关系式、数学命题、图形图表等，这些基于数学思想与方法的数学问题。总之，数学模型是对实际问题的一种抽象，基于数学理论和方法，用数学符号、数学关系式、数学命题、图形图表等来刻画客观事物的本质属性与其内在联系。,什么是数学建模呢？数学建模（Mathematical Modeling）就是建立数学模型，建立数学模型的过程就是数学建模的过程。数学建模是一种数学的思考方法，是运用数学的语言和方法，通过抽象、简化建立能近似刻画并解决实际问题的一种强有力的数学手段。,二、数学建模采用的主要方法,（一）、机理分析法：根据对客观事物特性
3、的认识从基本物理定律以及系统的结构数据来推导出模型。1、比例分析法：建立变量之间函数关系的最基本最常用的方法。2、代数方法：求解离散问题（离散的数据、符号、图形）的主要方法。3、逻辑方法：是数学理论研究的重要方法，对社会学和经济学等领域的实际问题，在决策，对策等学科中得到广泛应用。4、常微分方程：解决两个变量之间的变化规律，关键是建立“瞬时变化率”的表达式。5、偏微分方程：解决因变量与两个以上自变量之间的变化规律。,（二）、数据分析法：通过对量测数据的统计分析，找出与数据拟合最好的模型1、回归分析法：用于对函数f（x）的一组观测值（xi,fi）i=1,2,n，确定函数的表达式，由于处理的是静态
4、的独立数据，故称为数理统计方法。2、时序分析法：处理的是动态的相关数据，又称为过程统计方法。,二、数学建模采用的主要方法,（三）、仿真和其他方法1、计算机仿真（模拟）：实质上是统计估计方法，等效于抽样试验。离散系统仿真，有一组状态变量。连续系统仿真，有解析表达式或系统结构图。2、因子试验法：在系统上作局部试验，再根据试验结果进行不断分析修改，求得所需的模型结构。3、人工现实法：基于对系统过去行为的了解和对未来希望达到的目标，并考虑到系统有关因素的可能变化，人为地组成一个系统。,二、数学建模采用的主要方法,三、大学生数学建模竞赛,1985年在美国出现了一种叫做MCM的一年一度的大学生数学模型竞赛
5、（Mathematical Contest in Modeling,缩写MCM）。我国自1989年首次参加这一竞赛，历届均取得优异成绩。经过数年参加美国赛表明，中国大学生在数学建模方面是有竞争力和创新联想能力的。,为了在国内推广这一活动，1992年由中国工业与应用数学学会（CSIAM）组织了第一次中国大学生数学建模竞赛（简称CMCM），1994年起由教育部高教司和CSIAM共同举办，每年一次（9月），现在已经成为全国高校规模最大的课外科技活动。,三、大学生数学建模竞赛,竞赛题目一般由工程技术、管理科学中的实际问题简化而成，没有事先设定的标准答案，但留有充分余地供参赛者发挥其聪明才智和创造精神。
6、竞赛形式：三名大学生组成一队，可以自由地收集资料、调查研究，使用计算机、互联网和任何软件，在三天时间内分工合作完成一篇论文。评奖标准：假设的合理性、建模的创造性、结果的正确性、文字表述的清晰程度。每年出两道题，大学：A、B题，大专：C、D题，任选一题。A、C为连续型题目，B、D为离散型题目。优秀论文登在工程数学学报（2001年后），数学的实践与认识（2001年前）来年第1期上。,三、大学生数学建模竞赛,数学模型竞赛与通常的数学竞赛不同之处在于它来自实际问题或有明确的实际背景，它的宗旨是培养大学生用数学方法解决实际问题的意识和能力，培养创新意识、团队精神，鼓励参与、提倡公平竞争，提高学生综合素质
7、。整个比赛要完成一篇包括问题的阐述分析，模型的假设和建立，计算结果及讨论的论文。通过训练和比赛，同学们不仅用数学方法解决实际问题的意识和能力有很大提高，而且在团结合作发挥集体力量攻关，以及撰写科技论文等方面将都会得到十分有益的锻炼。,三、大学生数学建模竞赛,四、赛题题型结构形式的组成部分,（一）、实际问题背景、涉及面宽，有社会，经济，管理，生活，环境，自然现象，工程技术，现代科学中出现的新问题等。、一般都有一个比较确切的现实问题。,四、赛题题型结构形式的组成部分,（二）、若干假设条件1、只有过程、规则等定性假设，无具体定量数据；2、给出若干实测或统计数据；3、给出若干参数或图形；4、蕴涵着某些
8、机动、可发挥的补充假设条件，或参赛者可以根据自己收集或模拟产生数据。,四、赛题题型结构形式的组成部分,（三）、要求回答的问题，往往有几个问题（一般不是唯一答案）1、比较确定性的答案（基本答案）；2、更细致或更高层次的讨论结果（往往是讨论最优方案的提法和结果）。,（一）、标题、摘要部分1、题目：写出较确切的题目（不能只写A题、B题）。2、摘要：200-300字，包括模型的主要特点、建模方法和主要结果。3、内容较多时最好有个目录。,五、竞赛答卷（三大部分）,（二）、中心部分1、问题提出，问题分析。2、模型建立：补充假设条件，明确概念，引进参数；模型形式（可有多个形式的模型）；模型求解；模型性质；3
9、、计算方法设计和计算机实现。4、结果分析与检验。5、讨论：模型的优缺点，改进方向，推广新思想。6、参考文献：注意格式。,五、竞赛答卷（三大部分）,（三）、附录部分1、计算程序、框图。2、各种求解演算过程，计算中间结果。3、各种图形、表格。,五、竞赛答卷（三大部分）,中国大学生数学建模竞赛题目汇集,（注：A、B是大学组赛题，C、D题是大专组赛题，任选其一。）,1992A、施肥效果分析；B、实验数据分析。1993A、非线性交调的频率设计；B、足球队排名次。1994A、逢山开路；B、锁具装箱。1995A、一个飞行管理问题；B、天车与冶炼炉的作业调度。1996A、最优捕鱼策略；B、节水洗衣机。1997
10、A、零件的参数设计；B、截断切割。1998A、投资的收益与风险；B、灾情巡视路线。1999A、自动化车床管理；B、钻井布局；C、煤矸石堆积；D、钻井布局（注:比B稍易）,2000A、DNA序列分类；B、钢管订购和运输；C、飞越北极；D、空洞探测。2001A、血管的三维重建；B、公交车调度；C、基金使用计划；D、公交车调度。2002A、车灯线光源优化设计；B、彩票中的数学；C、车灯线光源计算；D、赛程安排。2003A、SARS的传播；B、露天矿生产的车辆安排；C、SARS的传播；D、抢渡长江。2004A、奥运会临时超市网点设计；B、电力市场的输电阻塞管理；C、饮酒驾车；D、公务员招聘。2005
11、A、长江水质的评价和预测；B、DVD在线租赁；C、雨量预报方法的评价；D、DVD在线租赁。,线性规划（概论）线性规划（Linear Programming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“Linear Programming and Extension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar提出“投影梯度法”线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。,1-1 线性规划基本概念生产计划问题如何合理使
12、用有限的人力，物力和资金，使得收到最好的经济效益。如何合理使用有限的人力，物力和资金，以达到最经济的方式，完成生产计划的要求。,例1.1 生产计划问题（资源利用问题）胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30元/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？,解：将一个实际问题转化为线性规划模型有以下几个步骤：1确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量2确定目标函数
13、：家具厂的目标是销售收入最大 max z=50 x1+30 x23确定约束条件：4x1+3x2 120（木工工时限制）2x1+x2 50（油漆工工时限制）4变量取值限制：一般情况，决策变量只取正值（非负值）x1 0,x2 0,1-2 线性规划问题的数学模型例1.2 营养配餐问题 假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？,各种食物的营养成分表,解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：min S=1
14、4x1+6x2+3x3+2x4 s.t.1000 x1+800 x2+900 x3+200 x4 3000 50 x1+60 x2+20 x3+10 x4 55 400 x1+200 x2+300 x3+500 x4 800 x1，x2，x3，x4 0,其他典型问题：合理下料问题运输问题生产的组织与计划问题投资证券组合问题分派问题生产工艺优化问题,用于成功决策的实例：美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决策美国国防部关于如何从现有的一些基地向海湾运送海湾战争所需要的人员和物资的决策 Chessie道路系统关于购买和修理价值40亿美圆货运汽车决策,用于成功决策的实
15、例：魁北克水利部门关于用哪几个水库来满足每天电力需求决策农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年共计60亿美圆）来维持发展决策北美长途运输公司关于每周如何调度数千辆货车的决策埃克森炼油厂关于调节冶炼能力去适应关于无铅燃料生产的法律更改的决策,线性规划问题的一般形式：Max(Min)S=c1x1+c2x2+.+cnxns.t.a11x1+a12x2+.+a1nxn(=,)b1 a21x1+a22x2+.+a2nxn(=,)b2.am1x1+am2x2+.+amnxn(=,)bm x1,x2.xn 0,线性规划问题隐含的假定：比例性假定：决策变量变化引起的目标
16、函数的改变量和决策变量的改变量成比例，同样，每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例。可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数贡献的总和。,线性规划问题隐含的假定：连续性假定：线性规划问题中的决策变量应取连续值。确定性假定：线性规划问题中的所有参数都是确定的参数。线性规划问题不包含随机因素。,线性规划问题隐含的假定：比例性假定可加性假定连续性假定确定性假定,线性规划问题的标准形式(1)：Max S=c1x1+c2x2+.+cnxns.t.a11x1+a12x2+.+a1nxn=b1 a21x1+a22x2
17、+.+a2nxn=b2.am1x1+am2x2+.+amnxn=bm x1,x2.xn 0其中：bi 0(i=1,2,.m),线性规划问题的标准形式(2)：n Max S=cjxj j=1 n s.t.aijxj=bi(i=1,2,.n)j=1 xj 0(j=1,2,.m),线性规划标准型的矩阵形式(3)：Max S=CX s.t.AX=b X 0,a11 a12.a1n b1 A=a21 a22.a2n b=b2.am1 am2.amn bn,c1 x1 0 c2 x2 0C=X=0=.cn xn 0,如何将一般问题化为标准型：若目标函数是求最小值 Min S=CX 令 S=-S,则 Max
18、 S=-CX若约束条件是不等式若约束条件是“”不等式 n aijxj+yi=bi j=1 yi 0是非负的松驰变量,如何将一般问题化为标准型：若约束条件是“”不等式 n aijxj-zi=bi j=1 zi 0是非负的松驰变量,如何将一般问题化为标准型：若约束条件右面的某一常数项 bi=0 令xj=xj-xj”（可正可负）任何形式的线性规划总可以化成标准型,例1.3 将下列问题化成标准型:Min S=-x1+2x2-3x3s.t.x1+x2+x3 7 x1-x2+x3 2-3x1+x2+2x3=5 x1,x2 0 x3 无非负限制,Max S=x1-2x2+3x3-3x3”s.t.x1+x2+
19、x3-x3”+x4=7 x1-x2+x3-x3”-x5=2-3x1+x2+2x3-2x3”=5 x1,x2,x3,x3”,x4,x5 0,1-3 线性规划问题解的概念,（二维）线性规划问题图解法：（1）满足约束条件的变量的值，称为可行解。（2）使目标函数取得最优值的可行解，称为最优解。例1.1的数学模型 max S=50 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1,x2 0,x2,50,40,30,20,10,10,20,30,40,x1,4x1+3x2 120,由 4x1+3x2 120 x1 0 x2 0围成的区域,x2,50,40,30,20,10,10,
20、20,30,40,x1,2x1+x2 50,由 2x1+x2 50 x1 0 x2 0围成的区域,x2,50,40,30,20,10,10,20,30,40,x1,2x1+x2 50,4x1+3x2 120,可行域,同时满足：2x1+x2 504x1+3x2 120 x1 0 x2 0的区域可行域,x2,50,40,30,20,10,10,20,30,40,x1,可行域,O（0，0）,Q1（25，0）,Q2（15，20）,Q3（0，40）,可行域是由约束条件围成的区域，该区域内的每一点都是可行解，它的全体组成问题的解集合。该问题的可行域是由O，Q1，Q2，Q3作为顶点的凸多边形,x2,50,4
21、0,30,20,10,10,20,30,40,x1,可行域,目标函数是以S作为参数的一组平行线x2=S/30-（5/3）x1,x2,50,40,30,20,10,10,20,30,40,x1,可行域,当S值不断增加时，该直线x2=S/30-（5/3）x1沿着其法线方向向右上方移动。,x2,50,40,30,20,10,10,20,30,40,x1,可行域,当该直线移到Q2点时，S（目标函数）值达到最大：Max S=50*15+30*20=1350此时最优解=（15，20）,Q2（15，20）,二个重要结论：满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。最优解必定能在
22、凸多边形的某一个顶点上取得，这一事实也可以推广到更多变量的场合。,解的讨论：最优解是唯一解；无穷多组最优解：例1.1的目标函数由 max S=50 x1+30 x2变成：max S=40 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1,x2 0,x2,50,40,30,20,10,10,20,30,40,x1,可行域,目标函数是同约束条件：4x1+3x2 120平行的直线x2=S/30-（4/3）x1,x2,50,40,30,20,10,10,20,30,40,x1,可行域,当S的值增加时，目标函数同约束条件：4x1+3x2 120重合，Q1与Q2之间都是最优解。,
23、Q1（25，0）,Q2（15，20）,解的讨论：无界解：例：max S=x1+x2 s.t.-2x1+x2 40 x1-x2 20 x1,x2 0,x2,50,40,30,20,10,10,20,30,40,x1,该可行域无界，目标函数值可增加到无穷大，称这种情况为无界解或无最优解。,解的讨论：无可行解：例：max S=2x1+3x2 s.t.x1+2x2 8 x1 4 x2 3-2x1+x2 4 x1,x2 0,该问题可行域为空集，即无可行解，也不存在最优解。,解的情况：有可行解有唯一最优解有无穷最优解无最优解无可行解,1-2 实例分析12000年全国大学生数模竞赛B题,2000B 钢管订购
24、和运输,由钢管厂订购钢管，经铁路、公路运输，铺设一条钢管管道,1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计）,（1）制定钢管的订购和运输计划，使总费用最小.,（2）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？,（3）讨论管道为树形图的情形,问题1的基本模型和解法,总费用最小的优化问题,总费用：订购，运输（由各厂Si经铁路、公路至各点Aj,i=1,7;j=1,15），铺设管道Aj Aj+1（j=1,14),由Si至Aj的最小购运费用路线及最小费用cij 由Si至Aj的最优运量xij由Aj向Aj Aj-1段铺设的长度zj及向A
25、j Aj+1段铺设的长度yj,最优购运计划,约束条件,钢厂产量约束：上限和下限（如果生产的话）运量约束：xij对i求和等于zj 加yj；yj与 zj+1之和等于Aj Aj+1段的长度lj,基本模型,由Aj向Aj Aj-1段铺设的运量为 1+zj=zj(zj+1)/2由Aj向Aj Aj+1段铺设的运量为 1+yj=yj(yj+1)/2,二次规划,求解步骤,1）求由Si至Aj的最小购运费用路线及最小费用cij,难点：公路运费是里程的线性函数，而铁路运费是里程的分段阶跃函数，故总运费不具可加性。因而计算最短路常用的Dijkstra算法、Floyd算法失效。,A1,需要对铁路网和公路网进行预处理，才能
26、使用常用算法，得到最小购运费用路线。,如S7至A10的最小费用路线,先铁路1130km，再公路70km,运费为77（万元）,先公路（经A15）40km,再铁路1100km，再公路70km,运费为76（万元）,实际上只有S4和S7需要分解成子问题求解,3)每个子问题是标准的二次规划，决策变量为xij,yj,zj,不超过135个。,问题1的其它模型和解法,1）运输问题的0-1规划模型,将全长5171km的管道按公里分段，共5171个需求点，钢厂为7个供应点，构成如下的运输问题,cij为从供应点i到需求点j的最小购运费,xij=1表示从点i到点j购运1单位钢管,求解时要针对规模问题寻求改进算法,2）
27、最小费用网络流模型,线性费用网络(只有产量上限),非线性费用网络(只有产量上限),边的标记（流量上限，单位费用）,用标准算法(如最小费用路算法)求解,无单位费用概念(f(f+1)/2),需修改最小费用路算法,2）最小费用网络流模型,产量有下限ri时的修正,3)最小面积模型,作图：Si到管道x单位钢管的最小购运费用c,由各条Si首尾相连(横坐标)组成的一条折线对应一个购运方案，折线下面的面积对应方案的费用,在产量约束下找面积最小的折线,论文中发现的主要问题,1）针对题目给的数据用凑的方法算出结果，没有解决这类问题的一般模型,2）局部最优，如将管道分为左右两段，分别寻求方案；如将问题分为购运和铺设
28、两部分，分别寻优（会导致每段管道都从两端铺到中点）,4）由Si至Aj的最小购运费用路线及最小费用cij 不对,5）数字结果相差较大(如最小费用应127.5至128.2亿元),问题2：分析对购运计划和总费用影响（哪个钢厂销价的变化影响最大；哪个钢厂产量上限的变化影响最大）,规划问题的灵敏度分析,问题3：管道为树形图,(jk)是连接Aj,Ak的边，E是树形图的边集，ljk是(jk)的长度，yjk是由Aj沿(jk)铺设的钢管数量,1-3 实例分析21998年全国大学生数模竞赛A题,投资的效益和风险(1998年全国大学生数学建模竞赛A题),原题还有一组 n=25的数据，现略去。,问题分析,优化问题,决
29、策,每种资产的投资额（投资组合）,目标,净收益最大,整体风险最小,在一定风险下收益最大的决策,在一定收益下风险最小的决策,收益和风险按一定比例组合最优的决策,一组解(如在一系列风险值下收益最大的决策),二者矛盾,冒险型投资者从中选择高风险下收益最大的决策,保守型投资者则可从低风险下的决策中选取,模型建立,用数学符号和式子表述决策变量、构造目标函数、确定约束条件。,xi对Si(i=0,1,n)的投资,S0表示存入银行.,目标函数,总收益投资Si的净收益减去交易费，对i求和,总体风险投资Si的风险，对i求最大值,对Si的投资xi加交易费，对i求和，不超过给定资金M.,决策变量,约束条件,1）投资S
30、i的交易费、净收益、风险、资金表达式,交易费,净收益,(收益率ri),风险,资金,(风险损失率qi),2）投资方案总收益、总体风险、资金表达式,投资方案,总收益,总体风险,资金,3）两目标（总收益、总体风险）优化模型,4）单目标优化模型,模型简化,交易费,资金约束,设M=1,投资Si的比例,设M=1,线性规划模型LP1,模型M1的简化,M1,模型M2的简化,M2,极大极小规划模型,线性规划模型LP2,模型M3的简化,M3,线性规划模型LP3,模型求解,LP1,LP2,LP3都很容易用MATLAB,MATHEMATICA或其它数学软件求解,线性规划模型LP1,LP1的结果,风险水平取k=02.5
31、%,得投资比例y0y4,LP1的结果,LP3的结果,与LP1相同,1-4 实例分析1,灵敏度分析又称为后优化分析,1.4 线性规划的灵敏度分析,线性规划是静态模型参数发生变化，原问题的最优解还是不是最优哪些参数容易发生变化C,b,A每个参数发生多大的变化不会破坏最优解灵敏度越小，解的稳定性越好,边际值(影子价)qi,以(max,)为例边际值(影子价)qi 是指在最优解的基础上，当第 i 个约束行的右端项 bi 减少一个单位时，目标函数的变化量,例,关于影子价的一些说明,影子价是资源最优配置下资源的理想价格，资源的影子价与资源的紧缺度有关松弛变量增加一个单位等于资源减少一个单位剩余变量增加一个单
32、位等于资源增加一个单位资源有剩余，在最优解中就有对应松弛变量存在，且其影子价为 0影子价为 0，资源并不一定有剩余应用，邮电产品的影子价格,价值系数 cj 的灵敏度分析,cj 变动可能由于市场价格的波动，或生产成本的变动cj 的灵敏度分析是在保证最优解的基变量不变的情况下，分析cj 允许的变动范围cj cj 的变化会引起检验数的变化，有两种情况非基变量对应的价值系数变化，不影响其它检验数基变量对应的价值系数变化，影响所有非基变量检验数1、非基变量对应的价值系数的灵敏度分析,例,2、基变量对应的价值系数的灵敏度分析,由于基变量对应的价值系数在CB中出现，因此它会影响所有非基变量的检验数只有一个基
33、变量的 cj 发生变化，变化量为 cj 令 cj 在CB中的第k行，研究非基变量xj 机会成本的变化,设x4的价值系数增加c4，对应k=2，,有一边为空集如何处理,为什么akj=0不出现在任何一边的集合中,与对偶单纯型法找入变量的公式一样,2.4.3 右端项 bi 的灵敏度分析,设 XB=B1b 是最优解，则有XB=B1b0b 的变化不会影响检验数b 的变化量 b 可能导致原最优解变为非可行解,右端项 bi 的灵敏度分析,以b2为例,x6是对应的初始基变量，所以有,技术系数 aij 的灵敏度分析,技术系数aij变化的影响比较复杂对应基变量的 aij，且资源bi已全部用完对应基变量的 aij，但
34、资源bi未用完 对应非基变量的 aij，且资源bi全用完或未用完1、对应基变量的 aij，且资源bi已全部用完 aij=02、对应基变量的 aij，但资源bi未用完 aij xn+i/xj上述两个公式不充分，为什么？B1发生变化，从而引起非基变量检验数 cj zj 的变化3、对应非基变量的 aij只影响对应非基变量xj的检验数 cj zj 若 aij 0，不会破坏最优解若 aij 0，必须保证 cj zj 0,x1,x3为非基变量，q1=0,q2=0.25,q3=1,故有,x2,x4为基变量，x5=100,b1有剩余，故有,新增决策变量的分析,例中，若新增产品 x8，问是否生产？已知 c8=9
35、,a18=5,a28=4,a38=3计算 x8 的检验数可知生产是否有利,结论：生产x8有利。将B1P8加入最优单纯型表中，以x8为入变量进行迭代,新增约束条件的分析,1、将最优解代入新的约束条件，若满足，则最优解不变2、若不满足，则当前最优解要发生变化；将新增约束条件加入最优单纯型表，并变换为标准型3、利用对偶单纯型法继续迭代为什么可以利用对偶单纯型法,例 第2步,注意：最优解的目标函数减少了25个单位,灵敏度分析举例,例 某工厂生产三种产品 A,B,C，有五种生产组合方案。下两表给出有关数据。规定每天供应 A产品至少110 个，求收益最大的生产方案。,例,解：设xj为已选定各种组合方案的组
36、数(j=1,2,5)，x6为A产品的剩余变量，x7，x8分别为工人工时和机器工时的松弛变量。,例,最优解的B1是什么产品A的影子价为多少第II组方案的生产费用提高2元，是否要调整生产组别若工人加班费为1元/小时，是否要采取加班措施若通过租借机器增加工时，租费的上限应为多少A产品的订购合同是否有利若要选用第IV组方案，该组的生产费用应降低多少若工人加班费为0.3元/小时，最多允许加班时间多少若机器租费低于44元/小时，问租几部机器才合适(每天8小时计)若第III组方案使机器工时减少0.5小时，能否被选入,参数线性规划,前面讨论了aij,bi,cj 只有一个发生变化，多个同时发生变化则很难解析但在
37、一些特殊情况下，用参数表示变化量，也可以用来进行多个系数的灵敏度分析 参数cj的变化分析i 第i 种资源的单位费用变化量，i 不限i i 变化对 cj 的影响率,例 资源b1单价变化量1，价格影响率j=a1j,例 资源b1单价变化量1 与c5,参数 bi 的变化分析,例中，将b1,b2,b3理解为三个车间的周工时资源。假设从第2向1车间调动工人 个，每个工人的周工时为 40小时，问调动多少工人不会破坏最优产品组合,整数规划,例1、集装箱运货,2.1 数学模型,解：设X1,X2 为甲、乙两货物各托运箱数,maxZ=20 X1+10 X2,例2、背包问题,背包可再装入8单位重量，10单位体积物品,
38、解：Xi为是否带第 i 种物品,maxZ=20X1+30X2+10X3+18X4+15X5,一般形式：,整数,(1)、Xi为i 物品携带数量 ai为i 物品单位重量 ci为i 物品重要性估价 b为最大负重,(2)、投资决策 Xi为在i 地区建厂规模 ai为在i 地区建厂基建费用 ci为在i 地区建厂单位利润 b为最大资本,(3)、Xi 取0或1时，可作项目投资模型,例3、选址问题,问：选择适当地点建仓库，在满足商店需求条件下，总费用最小。,解：设Xi(i=1,2,3)为是否在 Ai 建仓库 yij(i=1,2,3,j=14)由 i仓库向 j商店运货量,y11+y21=d1y12+y22+y32
39、=d2y23+y33=d3y14+y24+y34=d4x1+x2+x3=2y11+y12+y14 a1x1y21+y22+y23+y24a2x2y32+y33+y34 a3x3xi 为01，yij 0,混合整数规划,01决策变量的应用,可用于相互排斥计划中,例1、运输方式：火车、船。火车：5X1+4X2 24(体积)船：7X1+3X2 45(体积),maxZ=20X1+10X2,当 X3=0 火车 X3=1 船,2.2 整数规划解法,(一)、整数规划的解：可行域为其相应线性规划问题的可行域的子集,例1、,LP:X=(4.8,0)maxZ=96 ILP:X=(4,1)maxZ=90,(1)、四舍
40、五入法 可估近似解，例中X=(4,0),Z=80 80 Z*96 0Z*-8016,(2)、穷举法 当100个01变量，计算机，几亿年,分枝定界法割平面法隐枚举法,(二)、常用方法,(三)、分枝定界法,基本思路,(B)为(A)的松弛问题。,maxZ=40X1+90X2,例：,解：先解(1)的松弛问题,选X1分枝,选(2)继续分枝,分枝定界法一般步骤：,(1)、(A),先解(A)的松弛问题(B),(2)、(B)无可行解(A)无可行解。(B)最优解符合(A)要求，停。(B)最优解不符合(A)要求，转(3)。,(3)、估整数解S0，作下界,(4)、选(B)解中不符合整数条件的分量Xj(Xj=bj)分
41、枝，作(B)的后续问题(C)、(D)。(C)：(B）加约束Xj bj(D)：(B)加约束Xj bj+1,(6)、全部枝剪完，停,优点：,(1)、任何模型均可用；,(2)、思路简单、灵活；,(3)、速度快；,(4)、适合上机。,分枝定界法注意事项：,(1)、分枝变量选择原则：按目标函数系数：选系数绝对值最大者变 量先分。对目标值升降影响最大。选与整数值相差最大的非整数变量先分枝。按使用者经验，对各整数变量排定重要性 的优先顺序。,(2)、分枝节点选择：,广探法：选目标函数当前最大值节点，找到的整数 解质量高。慢。,深探法(后进先出法)：最后打开的节点最先选，尽快找到整数解。整数解质量可能不高。,01问题的分枝定界法（背包问题),松弛问题(B)为,解:“单位重量价值大的先放”,144,隐枚举法,(二)、简单隐枚举法(max),原则：(1)、用试探法，求出一个可行解，以它的目标值作为当前最好值Z0(2)、增加过滤条件Z Z0(3)、将xi 按ci由小大排列,解：观察得解(x1,x2,x3)=(1,0,0)Z0=3过滤条件：3x1-2x2+5x3 3 将(x1 x2 x3)(x2 x1 x3),
