《数学建模规划模型讲解》由会员分享，可在线阅读，更多相关《数学建模规划模型讲解（71页珍藏版）》请在金锄头文库上搜索。
1、主讲人:穆学文西安电子科技大学数学系 Email:数学建模讲义最优化模型-线性规划 参考书目1. 陈宝林。最优化理论与算法。清华大学出版 社.2. 谢金星，薛毅。优化建模与lindo/lingo优化软 件. 清华大学出版社.背景知识 运筹学理论的一部分 最早起源于中国古代 公元前6世纪孙武所著的孙子兵法 孙膑“斗马术”，田忌与齐王赛马，博弈论 运筹帷幄之中，决胜千里之外”。这千古名句也可以说是对张良运筹思想的赞颂和褒奖。 国外起源与发展 1738年,D.Bernoulli首次提出了效用的概念，并以此作 为决策的标准。 1896年，V.Pareto首次从数学角度提出多目标优化问题 ，引进了Par
2、eto最优的概念。 丹麦电话工程师A.K.Erlang开展了关于电话局中继线数 目的话务理论的研究，1909年发表了他将概率论应用于 电话话务理论的研究论文：“概率论与电话会话”，开排 队论研究的先河。1935-38年，英国为了正确地运用新研制的雷达系统来对 付德国飞机的空袭，在皇家空军中组织了一批科学家， 进行新战术试验和战术效率评价的研究，并取得了满意 的效果。他们把自己从事的这种工作命名为 “Operational Research”(运筹学，或直译为作战研究)。1939年，苏联的. 总结了他对生产组织 的研究，写了生产组织与计划中的数学方法一书， 是线性规划应用于工业生产问题的经典著作
3、 背景知识（续）1947年,G.B.Dantzig提出了单纯形方法后，线性规划便 迅速形成为一个独立的分支。 并逐级发展起来。英国运筹学会1948年成立（1948-53年是运筹学俱乐部， 1953年11月起改名为学会）。 。二次大战胜利后，美英各国不但在军事部门继续保留了 运筹学的研究核心，而且在研究人员、组织的配备及研 究范围和水平上，都得到了进一步的扩大和发展，同时 运筹学方法也向政府和工业等部门扩展。1951年出版了新版（1946年的原版是保密的，1948年才 撤销保密）的P.M.Morse和G.E.Kimball的运筹学方法 （Methods of Operations Researc
4、h），这是二战结束 后，对战时整个运筹学工作做系统的专业叙述的一本著 作。1951年,H.W.Kuhn与A.W.Tucker提出了Kuhn-Tucker条 件，标志着非线性规划理论的初步形成。 背景知识（续）1952年5月美国运筹学会成立，并创刊Operations Research。1953年,R.Bellman提出动态规划的名称，并阐述了最优 化原理。 1954年，D.R.Dantzig等研究旅行推销员问题时提出了分 解的思想，成为整数规划中两大方法割平面法与分枝 定界法的萌芽。 1955年,G.Dantzig首先考虑出现随机变量的线性规划问 题，这是最早提出的随机规划中的有补偿二阶段问题
5、。 1956年, L.R.Ford,Jr.与 D.R.Fulkerson提出并解决了网络 最大流问题，加强了图论与线性规划的联系，促进了优 化理论的研究。背景知识（续）1959年1月1日，国际运筹学会联合会(1FORS)正式宣告 成立，当时的联合会只包括英、美、法三个国家的运筹 学会，首任（1959-61年）主席（当时称为秘书，到1968 年第四届时才改称主席）为英国的Charles Goodeve。 背景知识（续）l运筹学理论在中国的研究与发展1957年，经中国科学院力学研究所所长钱学森的倡导， 在该所成立了由许国志领导的国内第一个运筹学研究组( 后成室)。刘源张、周华章、桂湘云等是该组最早
6、的一批 研究人员，从此在我国开始了现代运筹学的研究。当年 秋季，又有大学毕业生顾基发、董泽清、徐映波、陈锡 康、郭绍僖、李秉全等分配进入该组。 1958年，中国科学院数学研究所所长华罗庚率领广大研 究人员，包括吴文俊、越民义、万哲先、王元等在内， 也开展了运筹学应用课题的研究，并影响和带动了全国 范围内各部门、各高校的运筹学应用和推广工作。运输 和农业等部门的“图上作业法”、“打麦场设计”、“中国 邮递员问题”是典型的成果。背景知识（续）1959年2月，山东大学在数学系中设置了国内最早的一 个运筹学专门化，由谢力同与郑汉鼎执教。自当年暑假 开始，每年都有运筹学方向的学生毕业，为我国运筹学 事业
7、的发展作出了重要贡献。 1959年，中国科学院数学研究所成立了运筹学研究室， 研究人员都由所内其它室组调入。孙克定任研究室主任 ，该室最早的一批研究人员有排队论组的越民义、吴方 、徐光煇、韩继业；对策论组的吴文俊、江加禾、施闺 芳；数学规划组的朱永津、应玫茜、马仲蕃、凌开诚等 。与此同时，全国范围内很多高校也有大批教师转入运 筹学领域。 背景知识（续）1965年起，华罗庚和他的小分队在全国工业部门开始普 及推广统筹法的群众运动。在此后的二十年中，为普及 推广双法（统筹法与从1970年开始普及推广的优选法） ，他们走访了全国23个省市中几百个城市的几千个工厂 ，并向数百万人开设讲座开展工作，取得
8、了巨大的社会 效益和经济效益。 1965年华罗庚统筹方法平话及其补充一书由中国工 业出版社出版。 1970年起，华罗庚和他的小分队开始在全国范围内普及 推广优选法的群众运动。从此，统筹与优选双法变得家 喻户晓，双法的普及推广也取得了极为可观的社会、经 济效益。1971年华罗庚优选法平话及其补充一书由国防工业 出版社出版。背景知识（续）1980年4月22-26日在山东济南，召开了中国数学会运筹 学会成立暨第一届代表大会。中国运筹学倡导者之一， 中国科学院副院长华罗庚主持了会议，有来自各地科研 机构、高等院校、军事部门、工交企业等有关单位的82 名代表出席。华罗庚在大会开幕式与闭幕式上均发表了 讲
9、话，回顾了他在全国范围普及推广“双法”的经验和成 果，勉励大家以克敌攻坚的进取精神积极开展运筹学研 究。会议作了12个专题学术报告和个人成果的几十个分 组报告。中国数学会理事长华罗庚被推选兼任运筹学会 理事长，越民义、许国志、余潜修为副理事长，桂湘云 为秘书长，推选常务理事11名，理事42名。会议决定学 会挂靠在中科院应用数学所背景知识（续）优化模型应用的广泛性1. 系统分析，即生产计划和经营决策中的优化 问题。例如： 合理计划生产:运输，分配，布局，选址，指派 ，下料、配料等优化问题（linear programming）; 合理开发（或配置）资源:可再生资源的持续开 发,不可再生资源的优化
10、配置（linear programming ） 合理运行设备:设备的最有运行（维修）方案. 合理组合投资:追求最大受益、最小风险的投资 组合方案（Multiobjective programming） 2. 工程设计和控制中的非线性分析 （Non-linear programming and optimal control ） 例如：结构系统最优设计（人字架设计） 机械零件或部件的最优化设计(轮轴颈,凸轮设计) 化工设备最优设计（单件或连锁设备优化设计） 电力网络和水力网络的优化设计（平衡条件）历届数模竞赛所涉及的优化问题：94年 A题 逢山开路（工程设计优化问题） 目标：工程造价最低 决策：
11、在若干约束下选择一条最佳线路 95年 B题：天车调度问题（生产操作优化问题） 目标：年钢产量最大 决策：天车调度的最优方案设计l96年 A题：最优捕鱼策略（开发资源优化问题） 目标：可持续捕捞的努力量及最大捕捞量 决策：在平衡条件下确定五年内最佳捕捞方案l97年 A题：零件参数设计（产品参数优化设计）目标：产品总造价最低（产品质量损失费用零件制造成本费用） 决策：零件参数的最佳水平组合方案l98年 A题：组合投资问题（风险决策优化问题）目标（二目标）：收益最大，风险最小决策：组合投资方案l99年 A题：自动化车床管理（排队-更新问题）目标：生产工序的效益（费用最低）最大决策：最佳检验间隔河刀具
12、更换策略l99年 B题：钻井布局问题(生产计划优化问题)目标：最大限度利用初步、勘探时的旧井数决策：在规定精度的前提下确定系统勘探时的最 佳网络分布2002年 A题：车灯线光源的优化设计目标：线光源的功率最小决策:在满足设计规范的条件下,计算线光源的长度B题：彩票中的数学目标：最大限度地吸引彩民积极购买彩票决策：在保证彩民和彩票公司的利益上如何设置最佳 彩票方案l04年 A题：奥运会场馆周围超市设计目标：经济效益最大化，各个区域的平衡问题05年 B题：DVD在线租赁目标：满足顾客的需要，经济效益最大化06年 A题：出版社书号分配问题目标：经济效益最大化，不同学科书号的平衡问题07年 B题：北京
13、公交线路设计目标：时间最小化，车票钱最小化，转站最小化l08年 A题：中国学费的评价系统目标：经济效益最大化，考虑到老百姓的支付能力09年 医院眼科病人的等待系统目标：提高病床的周转率，降低病人的抱怨程度优化模型的一般形式x:决策变量 f(x):目标函数gi(x)0:约束条件可行解：满足约束条件的解最优解：取得最值的可行解次优解：一个较满意的可行解可行集（域）：所有可行解组成的集合，最优化问题至少有两要素：一是可能的 方案；二是要追求的目标。后者是前者的函 数。如果第一要素与时间无关就称为静态最 优化问题，否则称为动态最优化问题。建立最优化问题数学模型的三要素：（1）决策变量和参数。决策变量是
14、由数学模型 的解确定的未知数。参数表示系统的控制变量，有 确定性的也有随机性的。（2）约束或限制条件。 由于现实系统的客观物 质条件限制，模型必须包括把决策变量限制在它们 可行值之内的约束条件，而这通常是用约束的数学 函数形式来表示的。一般的模型简化工作包括以下几类：（1）将离散变量转化为连续变量。（2）将非线性函数线性化。（3）删除一些非主要约束条件。 （3）目标函数。这是作为系统决策变量的 一个数学函数来衡量系统的效率，即系统追 求的目标。l线性规划(LP)l非线性规划(NLP)l整数规划(IP)主要内容线性规划1、概念和实例。2、线性规划模型3、线性规划的性质。4、线性规划的主要算法。5
15、、用数学软件包求解线性规划问题6、建模案例选讲：投资的收益与风险线性规划：就是一个线性函数在线性等式或不等式 约束条件下的极值问题。线性规划研究的问题主要有两类：1、任务确定后，如何统筹安排，尽量做到用 尽量少的人力和物力资源来完成任务；2、有一定量的人力、物力资源，如何安排使 用他们，使完成的任务（创造的利润）最多。在生产管理和经济活动中经常提出这样一类问 题， 即如何合理地利用有限的人力、物力、财力 等资源，以便得到最好的经济效果。l线性规划的数学模型有三要素，从实际问 题提炼成数学模型时，首先寻找需求解的 未知量xj (j=1,n)，然后列举三要素： o列写与自变量（未知量）有关的若干个
16、线 性约束条件（等式或不等式）。o列写自变量xj取值限制（xj0，xj0或不 限）。o列写关于自变量的线性目标函数值（极大 值或极小值）。l其中，前两条称为可行条件，最后一条称 为优化条件。符合这三个条件的数学模型 通常称为线性规划的一般型（general）。 例1：某厂每日8小时的产量不低于1800件。为了进行质量控制 ，计划聘请两种不同水平的检验员。一级检验员的标准为：速 度25件/小时，正确率98%，计时工资4元/小时；二级检验员的 标准为：速度15小时/件，正确率95%，计时工资3元/小时。检 验员每错检一次，工厂要损失2元。为使总检验费用最省，该 工厂应聘一级、二级检验员各几名？解： 设需要一级和二级检验员的人数分别为x1、x2人, 则应付检验员的工资为：因检验员错检而造成的损失为：故目标函数为：约束条件为：线性规划模型：某车间有甲、乙两台机床，
