最优化模型2——线性规划

《最优化模型2——线性规划》由会员分享，可在线阅读，更多相关《最优化模型2——线性规划（9页珍藏版）》请在金锄头文库上搜索。

1、2012/3/171数学建模讲义数学建模讲义数学建模讲义数学建模讲义主讲人:穆学文主讲人:穆学文西安电子科技大学数学系西安电子科技大学数学系 Email:最优化模型最优化模型-线性规划-线性规划优化模型应用的广泛性优化模型应用的广泛性1. 系统分析，即生产计划和经营决策中的优化 问题。例如：合理计划生产系统分析，即生产计划和经营决策中的优化 问题。例如：合理计划生产:运输，分配，布局，选 址，指派，下料、配料等优化问题（运输，分配，布局，选 址，指派，下料、配料等优化问题（linear programming）; 合理开发合理开发（或配置或配置）资源资源:可再生资源的持续开可再生资源的持续开合

2、理开发合理开发（或配置或配置）资源资源:可再生资源的持续开可再生资源的持续开 发发,不可再生资源的优化配置（不可再生资源的优化配置（linear programming） 合理运行设备） 合理运行设备:设备的最有运行（维修）方案设备的最有运行（维修）方案. 合理组合投资合理组合投资:追求最大受益、最小风险的投资 组合方案（追求最大受益、最小风险的投资 组合方案（Multiobjective programming）2. 工程设计和控制中的非线性分析 （工程设计和控制中的非线性分析 （Non-linear programming and optimal control） 例如： 结构系统最优设计

3、（人字架设计） 机械零件或部件的最优化设计） 例如： 结构系统最优设计（人字架设计） 机械零件或部件的最优化设计(轮轴颈轮轴颈,凸轮设计凸轮设计) 化工设备最优设计化工设备最优设计（单件或连锁设备优化设计单件或连锁设备优化设计）化工设备最优设计化工设备最优设计（单件或连锁设备优化设计单件或连锁设备优化设计） 电力网络和水力网络的优化设计（平衡条件电力网络和水力网络的优化设计（平衡条件）历届数模竞赛所涉及的优化问题：历届数模竞赛所涉及的优化问题：94年A题逢山开路（工程设计优化问题） 目标：工程造价最低 决策：在若干约束下选择一条最佳线路94年A题逢山开路（工程设计优化问题） 目标：工程造价最低

4、 决策：在若干约束下选择一条最佳线路 95年B题：天车调度问题（生产操作优化问题） 目标：年钢产量最大95年B题：天车调度问题（生产操作优化问题） 目标：年钢产量最大 决策：天车调度的最优方案设计决策：天车调度的最优方案设计?96年A题：最优捕鱼策略（开发资源优化问题） 目标：可持续捕捞的努力量及最大捕捞量 决策：在平衡条件下确定五年内最佳捕捞方案96年A题：最优捕鱼策略（开发资源优化问题） 目标：可持续捕捞的努力量及最大捕捞量 决策：在平衡条件下确定五年内最佳捕捞方案?97年A题：零件参数设计（产品参数优化设计） 目标：产品总造价最低（产品质量损失费用 零件制造成本费用） 决策：零件参数的最

5、佳水平组合方案97年A题：零件参数设计（产品参数优化设计） 目标：产品总造价最低（产品质量损失费用 零件制造成本费用） 决策：零件参数的最佳水平组合方案?98年A题：组合投资问题（风险决策优化问题） 目标（二目标）：收益最大，风险最小98年A题：组合投资问题（风险决策优化问题） 目标（二目标）：收益最大，风险最小 决策决策组合投资方案组合投资方案决策决策：组合投资方案组合投资方案?99年A题：自动化车床管理（排队-更新问题） 目标：生产工序的效益（费用最低）最大 决策：最佳检验间隔河刀具更换策略99年A题：自动化车床管理（排队-更新问题） 目标：生产工序的效益（费用最低）最大 决策：最佳检验间

6、隔河刀具更换策略2012/3/172?99年 B题：钻井布局问题(生产计划优化问题) 目标：最大限度利用初步、勘探时的旧井数 决策：在规定精度的前提下确定系统勘探时的最 佳网络分布 2002年 A题：车灯线光源的优化设计 目标：线光源的功率最小 决策:在满足设计规范的条件下,计算线光源的长度99年 B题：钻井布局问题(生产计划优化问题) 目标：最大限度利用初步、勘探时的旧井数 决策：在规定精度的前提下确定系统勘探时的最 佳网络分布 2002年 A题：车灯线光源的优化设计 目标：线光源的功率最小 决策:在满足设计规范的条件下,计算线光源的长度 B题：彩票中的数学 目标：最大限度地吸引彩民积极购买

7、彩票 决策：在保证彩民和彩票公司的利益上如何设置最佳 彩票方案B题：彩票中的数学 目标：最大限度地吸引彩民积极购买彩票 决策：在保证彩民和彩票公司的利益上如何设置最佳 彩票方案?04年 A题：奥运会场馆周围超市设计 目标：经济效益最大化，各个区域的平衡问题 05年 B题：DVD在线租赁 目标：满足顾客的需要，经济效益最大化 06年 A题：出版社书号分配问题 目标：经济效益最大化，不同学科书号的平衡问题04年 A题：奥运会场馆周围超市设计 目标：经济效益最大化，各个区域的平衡问题 05年 B题：DVD在线租赁 目标：满足顾客的需要，经济效益最大化 06年 A题：出版社书号分配问题 目标：经济效益

8、最大化，不同学科书号的平衡问题 07年 B题：北京公交线路设计 目标：时间最小化，车票钱最小化，转站最小化07年 B题：北京公交线路设计 目标：时间最小化，车票钱最小化，转站最小化?08年 A题：中国学费的评价系统 目标：经济效益最大化，考虑到老百姓的支付能力 09年 医院眼科病人的等待系统 目标：提高病床的周转率，降低病人的抱怨程度08年 A题：中国学费的评价系统 目标：经济效益最大化，考虑到老百姓的支付能力 09年 医院眼科病人的等待系统 目标：提高病床的周转率，降低病人的抱怨程度优化模型的一般形式优化模型的一般形式优化模型的一般形式优化模型的一般形式1()( ),(,). .( )0,1

9、,2,T niminmaxzf xxxxst g xim=?或x:决策变量决策变量 f(x):目标函数目标函数 gi(x) 0:约束条件约束条件可行解：满足约束条件的解可行解：满足约束条件的解最优解：取得最值的可行解最优解：取得最值的可行解次优解：一个较满意的可行解次优解：一个较满意的可行解可行集（域）：所有可行解组成的集合，可行集（域）：所有可行解组成的集合，最优化问题至少有两要素：一是可能的 方案；二是要追求的目标。后者是前者的函 数。如果第一要素与时间无关就称为静态最 优化问题，否则称为动态最优化问题。最优化问题至少有两要素：一是可能的 方案；二是要追求的目标。后者是前者的函 数。如果第

10、一要素与时间无关就称为静态最 优化问题，否则称为动态最优化问题。建立最优化问题数学模型的三要素：（建立最优化问题数学模型的三要素：（1）决策变量和参数。决策变量和参数。决策变量是由数学模型 的解确定的未知数。参数表示系统的控制变量，有决策变量是由数学模型 的解确定的未知数。参数表示系统的控制变量，有 确定性的也有随机性的确定性的也有随机性的。确定性的也有随机性的确定性的也有随机性的。（2）约束或限制条件。约束或限制条件。 由于现实系统的客观物 质条件限制，模型必须包括把决策变量限制在它们 可行值之内的约束条件，而这通常是用约束的数学 函数形式来表示的。由于现实系统的客观物 质条件限制，模型必须

11、包括把决策变量限制在它们 可行值之内的约束条件，而这通常是用约束的数学 函数形式来表示的。一一般的模型简化工作包括以下几类般的模型简化工作包括以下几类：（3）目标函数。目标函数。这是作为系统决策变量的 一个数学函数来衡量系统的效率，即系统追 求的目标。这是作为系统决策变量的 一个数学函数来衡量系统的效率，即系统追 求的目标。般的模型简化工作包括以下几类般的模型简化工作包括以下几类：（1）将离散变量转化为连续变量。（）将离散变量转化为连续变量。（2）将非线性函数线性化。（）将非线性函数线性化。（3）删除一些非主要约束条件。）删除一些非主要约束条件。2012/3/173?线性规划线性规划(LP)主

12、要内容主要内容主要内容主要内容?非线性规划非线性规划(NLP)?整数规划整数规划(IP)线性规划线性规划线性规划线性规划1、概念和实例。、概念和实例。2、线性规划模型3、线性规划的性质。、线性规划模型3、线性规划的性质。4、线性规划的主要算法。4、线性规划的主要算法。5、用数学软件包求解线性规划问题、用数学软件包求解线性规划问题6、建模案例选讲：投资的收益与风险、建模案例选讲：投资的收益与风险线性规划：就是一个线性函数在线性等式或不等式 约束条件下的极值问题。线性规划：就是一个线性函数在线性等式或不等式 约束条件下的极值问题。线性规划研究的问题主要有两类：线性规划研究的问题主要有两类： 1、任

13、务确定后，如何统筹安排，尽量做到用尽量 少的人力和物力资源来完成任务；、任务确定后，如何统筹安排，尽量做到用尽量 少的人力和物力资源来完成任务； 2、有一定量的人力、物力资源，如何安排使用他 们，使完成的任务（创造的利润）最多。 在生产管理和经济活动中经常提出这样一类问 题， 即如何合理地利用有限的人力、物力、财力 等资源，以便得到最好的经济效果。、有一定量的人力、物力资源，如何安排使用他 们，使完成的任务（创造的利润）最多。 在生产管理和经济活动中经常提出这样一类问 题， 即如何合理地利用有限的人力、物力、财力 等资源，以便得到最好的经济效果。?线性规划的数学模型有三要素，从实际问 题提炼成

14、数学模型时，首先寻找需求解的 未知量线性规划的数学模型有三要素，从实际问 题提炼成数学模型时，首先寻找需求解的 未知量xj(j=1,n)，然后列举三要素：，然后列举三要素：1.列写与自变量（未知量）有关的若干个线 性约束条件（等式或不等式）。列写与自变量（未知量）有关的若干个线 性约束条件（等式或不等式）。2.列写自变量列写自变量xj取值限制（取值限制（xj0，xj0或不或不jjj限）。限）。3.列写关于自变量的线性目标函数值（极大 值或极小值）。列写关于自变量的线性目标函数值（极大 值或极小值）。?其中，前两条称为可行条件，最后一条称 为优化条件。符合这三个条件的数学模型 通常称为线性规划的

15、一般型（其中，前两条称为可行条件，最后一条称 为优化条件。符合这三个条件的数学模型 通常称为线性规划的一般型（general）。）。例例1：某厂每日某厂每日8小时的产量不低于小时的产量不低于1800件。为了进行质量控 制，计划聘请两种不同水平的检验员。一级检验员的标准为： 速度件。为了进行质量控 制，计划聘请两种不同水平的检验员。一级检验员的标准为： 速度25件件/小时，正确率小时，正确率98%，计时工资，计时工资4元元/小时；二级检验员 的标准为：速度小时；二级检验员 的标准为：速度15小时小时/件，正确率件，正确率95%，计时工资，计时工资3元元/小时。 检验员每错检一次，工厂要损失小时。

16、 检验员每错检一次，工厂要损失2元。为使总检验费用最省， 该工厂应聘一级、二级检验员各几名？元。为使总检验费用最省， 该工厂应聘一级、二级检验员各几名？解：解： 设需要一级和二级检验员的人数分别为设需要一级和二级检验员的人数分别为x1、x2人人, 则应付检验员的工资为：则应付检验员的工资为：12128 48 33224xxxx + =+因检验员错检而造成的损失为：因检验员错检而造成的损失为：1212(8 25 2%8 15 5%)2812xxxx+ =+故目标函数为：故目标函数为：2121213640)128()2432(minxxxxxxz+=+=约束条件为：约束条件为： +0, 0180015818002581800158258212121xxxxxx2012/3/174线性规划模型：线性规划模型：213640minxxz+= + 9453521 xxx