mpa 定量法第十一,十二章07.ppt
36页1、第十一章 单纯形法 (Simplex Method),本章授课内容: 单纯形法的解题思路 单纯形法的计算步骤,1947年夏末, George Dantzig 提出求解线形规划问题的一般方法-单纯形法,单纯形法的基本原理,求解LP问题的单纯形法的基本原理是:从一个初始基本可行解出发,通过对基变量的迭代运算(每次更换一个基变量,即从一个可行极点移动到与之相邻的一个可行极点),而得到下一个基本可行解,同时使目标函数得到改善;经过有限次的迭代运算,就可得到LP的最优解。,单纯形法的解题思路,找出一个基本可行解,最优吗?,是,停止计算,否,从一个基本可行解转移到另一个基本可行解,并使目标函数值进一步增大,利用图解法中的例, 了解基解在几何中的对应关系,= 10个,X (1) = ( 0,0,4,2,2 ) T O 点,,X (2) = ( 0,4,0,-6,6 ) T H1点,,X (3) = ( 0,1,3,0,3 ) T A 点,,X (4) = ( 0,-2,6,6,0 ) T H2点,,X (5) = ( 4,0,0,6,-2 ) T H3点,,X (6) = (-2,0 ,6,0,4
2、) T H4点,,X ( 7) = ( 2,0,2,4,0 ) T D 点,,X (8) = ( 2,2,0,0,2 ) T B 点,,X (9) = ( 3,1,0,3,0 ) T C 点,,X (10) = (6,4,-6,0,0 ) T H5点。,非基列,( P1 P2 ),( P1 P3 ),( P1 P4 ),( P1 P5 ),( P2 P3 ),( P2 P4 ),( P2 P5 ),( P3 P4 ),( P3 P5 ),( P4 P5 ),结论:,上例中,基可行解有: X(1),X(3),X(7),X(8),X(9) 分别与约束域顶点 O,A,D,B,C 对应。,基解不一定是可行解。,即基可行解与(LP)约束域顶点: 构成了一一对应关系。,二、基本定理,经严格的数学证明,可以得出如下结果: 定理1 线性规划(LP)的基可行解 与其约束域的顶点构成一一对应。 定理2 对于线性规划(LP)问题: 1、若存在一个可行解, 则一定存在基可行解; 2、若最优解存在, 则一定在某个(些)基可行解处达到。,案例1 最优生产计划问题,设某厂生产甲、乙、丙三种产品,要经过三道工序加工,
3、每种产品在各道工序的加工时间,各工序的生产能力和各产品的单位利润如下: 问:应如何安排生产计划,可使总利润为最大?试建立此问题的LP模型。,案例1 分析,设X1,X2,X3分别为产品甲,乙,丙的计划日产量,X0为每天的总利润,则: 目标函数:max X0=3X1+2X2+5X3 约束条件: X1+2X2+ X3430 3X1 +2X3460 X1+4X2 420 X1,X2,X30,用Excel求解案例1的输入格式,案例1的计算机求解,设X1,X2,X3分别为产品甲,乙,丙的计划日产量,X0为每天的总利润,则LP模型为: max X0=3X1+2X2+5X3 X1+2X2+ X3430 3X1 +2X3460 X1+4X2 420 X1,X2,X30 使用 Excel 【工具】“规划求解”,可得最优解为: X1*=0,X2*=100,X3*=230,X0*=1350 此外输出的“运算结果报告”还给出了最优解中松弛变量的值,为:S1=S2=0,S3=20,说明第一、二道工序的能力已用完,第三道工序则每天有20分钟的富裕能力。,作业,P52 : 2.2中的(2) 用单纯形法求解:,第十二章
4、 对偶理论(Duality Theory),授课内容 对偶问题(Dual Problem)的提出 线性规划的对偶关系 线性规划的对偶性质 影子价格(Shadow Price),第一节 对偶问题的提出,对偶问题的概念 从经济意义提出的对偶问题,一、对偶问题的概念,内容一致但从相反角度提出的一对问题称为对偶问题,原问题 (Primal Problem),对偶问题 (Dual Problem),内容一致 角度相反,二、从经济意义提出的对偶问题,例1. 某工厂在计划期内要生产产品I和产品II这两种产品,已知生产单位产品所需的设备台时及A、B、c、D两种设备计划期的有效台时,如下表: 问如何安排生产最有利?,y1 y2 y3 y4,生产产品的数学模型,设产品I和产品II的产量分别为x1和x2件, 利润为Z, 则:,Max Z = 2 x1 + 3 x2 2 x1 + 2 x2 12 x1 + 2 x2 8 4x1 + 0 x2 16 0x1 + 4 x2 12 x1 , x2 0,不生产产品(出租设备)的数学模型,设设备A、B、C、D每小时的租金分别为y1 、 y2、 y3、 y4, 则:,2y
《mpa 定量法第十一,十二章07.ppt》由会员小**分享,可在线阅读,更多相关《mpa 定量法第十一,十二章07.ppt》请在金锄头文库上搜索。
2020年高考真题——理科综合(全国卷Ⅲ)+Word版含答案
2021年绝味鸭脖策划书
2021年熟食店创业方案
2021年熟食店开店策划
2021年卤菜店创业计划书
2021年周黑鸭网络营销策划方案
东大21年1月考试《现代设计方法》考核作业
谈我国行政管理效率的现状及其改观对策(论文)
单证员考试-备考辅导-复习资料:无贸易背景信用证案分析.docx
土木工程毕业生答辩自述.docx
建筑学毕业后工作状态真实写照.doc
C#代码规范(湖南大学).doc
xx区食药监局2019年工作总结及2020年工作计划
2019年中医院药物维持治疗门诊工人先锋号先进事迹
2019年度xx乡镇林长制工作总结
2019年性艾科工作计划书
2019年人才服务局全国扶贫日活动开展情况总结
关于组工信息选题的几点思考
摘了穷帽子 有了新模样
2019年某集团公司基层党支部书记培训班心得体会
2024-01-31 15页
2024-01-31 21页
2024-01-31 37页
2024-01-31 30页
2024-01-31 22页
2024-01-31 48页
2024-01-31 32页
2024-01-31 40页
2024-01-31 31页
2024-01-31 20页