线性规划及单纯形法 (2)讲稿.ppt
《线性规划及单纯形法 (2)讲稿.ppt》由会员分享,可在线阅读,更多相关《线性规划及单纯形法 (2)讲稿.ppt(81页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、关于线性规划及单纯形法关于线性规划及单纯形法(2)第一页,讲稿共八十一页哦2绪 论一、运筹学发展简介一、运筹学发展简介二、运筹学的特点及研究对象二、运筹学的特点及研究对象三、运筹学的工作步骤三、运筹学的工作步骤四、运筹学内容介绍四、运筹学内容介绍第二页,讲稿共八十一页哦3一、运筹学(一、运筹学(OROR)发展简介)发展简介运筹学在国外运筹学在国外英国称为英国称为 Operational Research美国称为美国称为 Operations Research起源于二战期间的军事问题,如雷达的设置、运输起源于二战期间的军事问题,如雷达的设置、运输船队的护航舰队的规模、反潜作战中深水炸弹的深船队的
2、护航舰队的规模、反潜作战中深水炸弹的深度、飞机出击队型、军事物资的存储等。度、飞机出击队型、军事物资的存储等。二战以后运筹学应用于经济管理领域(二战以后运筹学应用于经济管理领域(LP、计算机)、计算机)1948年英国首先成立运筹学会;年英国首先成立运筹学会;1952年美国成立运年美国成立运筹学会。筹学会。1952年,年,Morse 和和 Kimball出版出版运筹学方法运筹学方法1959年成立国际运筹学联合会年成立国际运筹学联合会第三页,讲稿共八十一页哦4 运筹学在国内运筹学在国内中国古代朴素的运筹学思想(田忌赛马、都江中国古代朴素的运筹学思想(田忌赛马、都江堰工程、丁渭修复皇宫)堰工程、丁渭
3、修复皇宫)1956年中科院成立运筹学小组年中科院成立运筹学小组1957年正式将年正式将Operations Research命名为命名为“运筹学运筹学”1958年提出运输问题的图上作业法年提出运输问题的图上作业法(解决粮食合(解决粮食合理运输问题)理运输问题)1962年提出中国邮路问题年提出中国邮路问题(管梅谷)(管梅谷)1964年华罗庚推广统筹方法年华罗庚推广统筹方法1980年中国运筹学学会正式成立年中国运筹学学会正式成立1982年中国加入国际运筹学联合会年中国加入国际运筹学联合会1999年年8月我国组织了第月我国组织了第15届大会届大会第四页,讲稿共八十一页哦5齐王赛马(齐王和田忌)齐王赛
4、马(齐王和田忌)战国时期,齐威王与田忌赛马,规定双战国时期,齐威王与田忌赛马,规定双方各出上中下三个等级的马各一匹。如方各出上中下三个等级的马各一匹。如果按同等级的马比赛,齐王可获全胜。果按同等级的马比赛,齐王可获全胜。田忌的谋士孙膑提出的以下、上、中对田忌的谋士孙膑提出的以下、上、中对齐王的上、中、下对策,使处于劣势的齐王的上、中、下对策,使处于劣势的田忌战胜齐王,这是从总体出发制定对田忌战胜齐王,这是从总体出发制定对抗策略的一个著名事例。抗策略的一个著名事例。第五页,讲稿共八十一页哦6丁渭主持皇宫的修复(北宋,皇宫因火焚毁)北宋真宗年间,皇城失火,宫殿烧毁,大臣丁谓主持了皇宫修复工程。他采
5、用了一套综合施工方案:先在需要重建的大道上就近取土烧砖;在取土后的深沟中引水,形成人工河,再由此水路运入建筑材料,从而加快了工程进度;皇宫修复后,又将碎砖废土填入沟中,重修大道。使烧砖、运输建筑材料和处理废墟三项繁重工程任务协调起来,从而在总体上得到了最佳解决,一举三得,节省了大量劳力、费用和时间。第六页,讲稿共八十一页哦7运筹学为决策机构对所控制的业务活动作决策时,提供以数量运筹学为决策机构对所控制的业务活动作决策时,提供以数量为基础的科学方法为基础的科学方法Morse Morse 和和 KimballKimball运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方运筹学是把科学方法
6、应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题,其方法是发展一个科学的系统模式,并运面解决发生的各种问题,其方法是发展一个科学的系统模式,并运用这种模式预测、比较各种决策及其产生的后果,以帮助主管人员用这种模式预测、比较各种决策及其产生的后果,以帮助主管人员科学地决定工作方针和政策科学地决定工作方针和政策英国运筹学会英国运筹学会运筹学是应用分析、试验、量化的方法对经济管理系统中人力、运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排,为决策者提供有根据的最优方物力、财力等资源进行统筹安排,为决策者提供有根据的最优方案,以实现最有效的管理案,以实现
7、最有效的管理中国百科全书中国百科全书现代运筹学涵盖了一切领域的管理与优化问题,称为现代运筹学涵盖了一切领域的管理与优化问题,称为 Management ScienceManagement Science运筹学的定义运筹学的定义二、运筹学的特点及研究对象二、运筹学的特点及研究对象第七页,讲稿共八十一页哦8运筹学的特点:运筹学的特点:优化:从全局观点看问题,追求总体效果最优优化:从全局观点看问题,追求总体效果最优量化:通过建立和求解模型使问题在量化的基础量化:通过建立和求解模型使问题在量化的基础 上得到合理决策上得到合理决策综合:多学科交叉综合:多学科交叉运筹学的研究对象:运筹学的研究对象:生产与
8、经济等各种实践活动中提出来的实际问题生产与经济等各种实践活动中提出来的实际问题二、运筹学的特点及研究对象二、运筹学的特点及研究对象第八页,讲稿共八十一页哦9三、运筹学的工作步骤三、运筹学的工作步骤明确问题明确问题建立模型建立模型设计算法设计算法整理数据整理数据求解模型求解模型评价结果评价结果简化?简化?满意满意?YesNoNo明确问题明确问题建立模型建立模型设计算法设计算法整理数据整理数据求解模型求解模型评价结果评价结果第九页,讲稿共八十一页哦10四、运筹学内容介绍四、运筹学内容介绍 线性规划及单纯形法线性规划及单纯形法 对偶理论及灵敏度分析对偶理论及灵敏度分析 运输问题运输问题 整数规划整数
9、规划 动态规划动态规划 图与网络分析图与网络分析 第十页,讲稿共八十一页哦11第一章第一章 线性规划及单纯形法线性规划及单纯形法1939年年 苏苏 康托洛维奇发表康托洛维奇发表“生产组织与计划中的生产组织与计划中的数学方法数学方法”,1960年出版年出版“最佳资源利用的经济计最佳资源利用的经济计算算”获诺贝尔经济学奖获诺贝尔经济学奖1941年年 美美 Hichcock提出运输问题提出运输问题1947年年 美美 丹捷格(丹捷格(G.B.Dantzig)提出单纯形法,)提出单纯形法,1963年出版年出版“线性规划及其扩展线性规划及其扩展”在生产管理中如何有效地利用现有人力、物力完成更管理中如何有效
10、地利用现有人力、物力完成更多的任务,或在预定的任务目标下,如何耗用最少的人多的任务,或在预定的任务目标下,如何耗用最少的人力、物力去实现目标。力、物力去实现目标。第十一页,讲稿共八十一页哦12第一节第一节 线性规划问题及数学模型线性规划问题及数学模型例例1 生产计划问题生产计划问题(P4)I II 资源限量资源限量设设 备备 1 2 8台时台时 原材料原材料A 4 0 16公斤公斤原材料原材料B 0 4 12公斤公斤单位利润单位利润 2 3 设设I I、IIII两种产品的产量分别为两种产品的产量分别为x1,x2 。建建立该问题的数学模型为:立该问题的数学模型为:目标函数目标函数约束条件约束条件
11、决策变量决策变量一、实例一、实例第十二页,讲稿共八十一页哦13例例2 合理下料问题合理下料问题现要做现要做100套钢架,每套需套钢架,每套需2.9米、米、2.1米和米和1.5米的圆钢各一米的圆钢各一根。已知原料长根。已知原料长7.4米,问如何下料,使用的原料最少米,问如何下料,使用的原料最少(余料最少或根数最少)?(余料最少或根数最少)?解解:设:设 x1,x2,x3,x4,x5分别代表五种不同的原料用量方案分别代表五种不同的原料用量方案(余料最少)(余料最少)第十三页,讲稿共八十一页哦14方案方案2.9米米2.1米米1.5米米合计合计余料余料x11037.40 x22017.30.1x302
12、27.20.2x41207.10.3x50136.60.8决策变量?决策变量?目标函数?特点?目标函数?特点?约束条件?约束条件?决策方案?决策方案?最优方案?最优方案?最优值?最优值?第十四页,讲稿共八十一页哦15二、总结二、总结 目标函数用决策变量的线性函数来表示。按问题的目标函数用决策变量的线性函数来表示。按问题的不同,要求目标函数实现最大化和最小化。不同,要求目标函数实现最大化和最小化。线性规划问题(线性规划问题(LP问题)的共同特征:问题)的共同特征:每一个问题变量都用一组决策变量(每一个问题变量都用一组决策变量(x1,x2,xn)表示某)表示某一方案,这组决策变量的值代表一个具体方
13、案,这些一方案,这组决策变量的值代表一个具体方案,这些变量是非负的。变量是非负的。存在一定的约束条件,这些约束条件可以用一组线性存在一定的约束条件,这些约束条件可以用一组线性等式或线性不等式来表示。等式或线性不等式来表示。线性规划模型的一般形式与标准形式(线性规划模型的一般形式与标准形式(P7稍后讲)稍后讲)第十五页,讲稿共八十一页哦16三、两变量线性规划问题的图解法三、两变量线性规划问题的图解法1.线性不等式的几何意义线性不等式的几何意义 半平面半平面1)作出作出LP问题的可行域问题的可行域2)作出目标函数的等值线作出目标函数的等值线3)移动等值线到可行域边界得到最优点移动等值线到可行域边界
14、得到最优点2.图解法步骤图解法步骤第十六页,讲稿共八十一页哦174x1=164x2=12x1+2x2=8x1x248430例例1 (书(书P4):):Q(4,2)Z=2x1+3x2 做目标函数做目标函数2x1+3x2的等值线,与阴影的等值线,与阴影部分的边界相交于部分的边界相交于Q(4,2)点,表明最点,表明最优生产计划为:优生产计划为:生产生产I产品产品4件,生产件,生产II产品产品2件。件。最大利润:最大利润:14.基本概念:基本概念:可行解、可行域、最优解?可行解、可行域、最优解?第十七页,讲稿共八十一页哦18例例2Z=36第十八页,讲稿共八十一页哦193.图解法的作用图解法的作用 能解
15、决少量问题能解决少量问题LPLP问题问题有可行解有可行解有最优解有最优解唯一解唯一解无穷多解无穷多解无最优解(可行域为无界)无最优解(可行域为无界)无可行解(无解)无可行解(无解)规律规律1:揭示了线性规划问题的若干规律揭示了线性规划问题的若干规律见见P9-10 例题例题第十九页,讲稿共八十一页哦20结论:结论:若若LP问题有最优解,则要么最优解问题有最优解,则要么最优解唯一,要么有无穷多最优解。唯一,要么有无穷多最优解。第二十页,讲稿共八十一页哦21 规律规律2:线性规划问题的可行域为一凸集线性规划问题的可行域为一凸集线性规划问题凸集的顶点个数是有限的线性规划问题凸集的顶点个数是有限的最优解
16、肯定可在凸集的某顶点处达到最优解肯定可在凸集的某顶点处达到 第二十一页,讲稿共八十一页哦22四、四、线性规划问题的标准型线性规划问题的标准型1.一般形式一般形式第二十二页,讲稿共八十一页哦232.标准型标准型LP模型的各种表示模型的各种表示法见法见P7第二十三页,讲稿共八十一页哦243.所有所有LP问题均可化为标准型问题均可化为标准型1.目标函数最大化目标函数最大化2.约束条件为等式约束条件为等式3.变量约束为非负变量约束为非负4.约束右端项非负约束右端项非负第二十四页,讲稿共八十一页哦25例例1可化为可化为第二十五页,讲稿共八十一页哦26例例2 化标准型化标准型第二十六页,讲稿共八十一页哦2
17、7课堂作业课堂作业第二十七页,讲稿共八十一页哦28五、标准型五、标准型LPLP问题的解问题的解LP模型向量表模型向量表示法见示法见P7第二十八页,讲稿共八十一页哦29第二十九页,讲稿共八十一页哦30令令B=(P1,P2,Pm)且且|B|0,称,称A中基中基B对应的列向量对应的列向量Pj(j=1,2,m)为基向量。为基向量。与基向量与基向量Pj对应的变量对应的变量xj称为称为基变量基变量,记为记为XB=(x1,x2,xm )T,其余的变量称为其余的变量称为非基变量非基变量,记为,记为 XN=(xm+1,xm+2,xm+n )T。基变量:基变量:第三十页,讲稿共八十一页哦31基本解基本解令非基变量
18、令非基变量 XN=0,求得的一组基变量求得的一组基变量 XB的值称为基本解。的值称为基本解。基可行解(顶点)基可行解(顶点)既是基本解,又是可行解。既是基本解,又是可行解。基最优点基最优点既是基本解,又是使目标函数值达到最优的解既是基本解,又是使目标函数值达到最优的解第三十一页,讲稿共八十一页哦32如引例中:如引例中:基基 基变量基变量 非基变量非基变量 基本解基本解 是否可行是否可行 目标函数值目标函数值ZB1 x1,x2 x3,x4 (-2,3,0,0)否否B2 x1,x3 x2,x4 (3,0,1,0)是是 Z=3 B3 x1,x4 x2,x3 (4,0,0,-3)否否 B4 x2,x3
19、 x1,x4 (0,9/5,2/5,0)是是 Z=9/5B5 x1,x4 x2,x3 (2,0,0,-1)否否B3 x3,x4 x1,x2 (0,0,4,9)是是 Z=0第三十二页,讲稿共八十一页哦33 线性规划标准型问题解的关系线性规划标准型问题解的关系约束方程的约束方程的解空间解空间基解基解可行解可行解非可行解非可行解基可基可行解行解LP解的基本定解的基本定理见理见P12第三十三页,讲稿共八十一页哦34第二节第二节 单纯型法单纯型法 一、基本思想一、基本思想化化LP问题为标准型,问题为标准型,确定一个初始基本可行解确定一个初始基本可行解检验解的检验解的最优性最优性结束结束Y枢轴运算(旋转运
20、算)枢轴运算(旋转运算)确定另一个基本可行解确定另一个基本可行解N第三十四页,讲稿共八十一页哦35二、枢轴运算二、枢轴运算第三十五页,讲稿共八十一页哦36又如:又如:第三十六页,讲稿共八十一页哦37三、检验数的意义三、检验数的意义P17第三十七页,讲稿共八十一页哦38四、单纯形表四、单纯形表基变量非基变量常数项约束方程增广矩阵检验数+目标函数值P17第三十八页,讲稿共八十一页哦39第三节第三节 单纯型法的步单纯型法的步 骤骤一、步骤一、步骤1.化化LP问题为标准型问题为标准型,建立初始单纯型表建立初始单纯型表;直接求最小化问题,P23说明第三十九页,讲稿共八十一页哦40二、用单纯形表求解二、用
21、单纯形表求解LP问题实例问题实例化为标准型化为标准型例例1.1.第四十页,讲稿共八十一页哦41单纯型表单纯型表算法步骤:算法步骤:Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 0 X5 8 1612 1 2 1 0 0 4 4 0 0 1 0 -0 4 0 0 1 3 0 2 3 0 0 0以以4为枢轴元素进行旋转运算,为枢轴元素进行旋转运算,x2为换入变量,为换入变量,x5为换出变量为换出变量Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 3 X2 2 16 3 1 0 1 0 -1/2 2 4 0 0
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性规划及单纯形法 2讲稿 线性规划 单纯 讲稿
限制150内