




已阅读5页,还剩21页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第一章线性规划问题及单纯形法,线性规划问题及其数学模型图解法单纯形法原理单纯形法计算步骤单纯形法的进一步讨论,第五节单纯形法的进一步讨论,本节重点:大M法两阶段法解的存在情况判别,由于所添加的剩余变量的技术系数为1,不能作为初始可行基变量,为此引入一个人为的变量(注意,此时约束条件已为“=”型),以便取得初始基变量,故称为人工变量。由于人工变量在原问题的解中是不能存在的,应尽快被迭代出去,因此人工变量在目标函数中对应的价值系数应具有惩罚性,称为罚系数。罚系数的取值视解法而定两种方法:大M法和二阶段法。,一、人工变量的引入及其解法,1.当约束条件为“”型,引入剩余变量和人工变量,2.大M法的求解过程例1,人工变量添加前已为等式,其取值必须为0;-M称为“惩罚因子”,答:最优解为x1=2,x2=2,x3=0,OBJ=36,例1的单纯型表迭代过程,3.大M法的一些说明,(1)人工变量被迭代出去后一般就不会再成为基变量(2)大M法实质上与原单纯形法一样,M可看成一个很大的常数(3)当检验数都满足最优条件,但基变量中仍有人工变量,说明原线性规划问题无可行解(4)大M法手算不会遇到麻烦,但计算机计算很容易产生误差,因此提出了二阶段法。,4.二阶段法的求解过程,(1)第一阶段的任务是将人工变量尽快迭代出去,从而找到一个没有人工变量的基础可行解(2)若第一阶段结束时,人工变量仍在基变量中,则原问题无解(3)第二阶段以第一阶段得到的基础可行解为初始解,采用原单纯形法求解(4)为了简化计算,在第一阶段重新定义价值系数如下:,用二阶段法求解例1的第一阶段,人工变量x6不在基变量中,从最终单纯形表中去除人工变量,更换目标函数为原问题的目标函数,继续用单纯形表计算。,用二阶段法求解例1的第二阶段,1.关于退化问题当按照最小比值确定换出基变量时,存在多个相同的最小比值,从而使下一个表的基可行解中出现一个或多个基变量等于零的退化解。退化的严重性在于可能导致死循环,克服死循环的方法有“字典序”法,即Bland规则:(1)当按照最大检验数j0确定换入变量时,存在多个相同的最大检验数,始终选取下标值为最小的变量作为换入变量;(2)当按照最小比值确定换出基变量时,存在多个相同的最小比值,始终选取下标值为最小的变量作为换出变量。,二、LP解的进一步讨论,2.关于多重解问题最优单纯形表中有非基变量的检验数为0,例3的单纯型表及其迭代过程,4.关于无可行解问题,单纯形表达到最优解检验条件时,人工变量仍在基变量中,例4第一阶段的单纯型表,三、单纯形法小结如下所示:,1.线性规划模型及其变换,根据实际问题给出数学模型,进行标准化,列出初始单纯型表,见表,变,量,x,j,0,x,j,0,x,j,无约束,不需要处理,令,x,j,=,-,x,j,;x,j,0,令,x,j,=x,j,-,x,j,;,x,j,x,j,0,约,束,条,件,b0,b0计算i=bi/aik令l=mini第l个基变量为换出变量,alk为主元素,1xk替换xl2列出新的单纯形表对主元素行(第l行)其它行i(il),否,3.对目标函数求极大值标准型线性规划问题,单纯形法计算步骤的框图,例1:某糖果厂用原材料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号的糖果中A、B、C含量,原料成本,各种原料每月限制用量,三种牌号糖果的单位加工费及售价如下表所示。问该厂每月生产这三种牌号糖果多少kg,使该厂获利最大。试建立该问题的LP的数学模型。,例2:捷运公司拟在下一年度的14月份的4个月需租用仓库堆放物资。已知各月份所需仓库面积数列于下表,仓库租用费随合同期而定,期限越长,折扣越大。具体数字见下表。,租借仓库的合同每月初都可办理,每份合同都具体规定租用面积和期限。因此该厂可根据需要,在任何一个月初办理租借合同。每次办理时可签一份,也可签若干份租用面积和租借期限不同的合同,试确定该公司签订的租借合同的最优决策,目的是所付租借费用最小。,解:若用变量表示捷运公司在第个月初签定的租借期为个月的仓库面积的合同(单位为100)。因5月份起该公司不需要租借仓库,均为零。该公司希望总的租借费用为最小,故有如下的数学模型:,目标函数:,约束条件,例3某城市在一昼夜间,市内交通需要车辆数如图,对车辆的需求在昼夜间是变化的,车辆的工作制度是一天连续工作8小时,派车时间在各时间间隔的端点,一旦派出,就连续工作8小时。求保证需要的最小车辆数。,车辆数,时间,0,4,7,12,16,20,24,4,8,12,4,8,12,10,8,4,派车时间在各时间间隔的端点,一旦派出,就连续工作8小时。设:各时
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025江苏泰州市姜堰区招聘教师20人考前自测高频考点模拟试题及答案详解参考
- 2025湖北恩施州招募选派三支一扶高校毕业生2000人模拟试卷附答案详解(突破训练)
- 2025湖南湘潭市纪委监委所属事业单位选调15人考前自测高频考点模拟试题及答案详解(夺冠系列)
- 2025南昌市劳动保障事务代理中心招聘1名外包驾驶员模拟试卷及完整答案详解一套
- 2025贵州贵阳贵安统一招聘中小学(幼儿园)教师553人模拟试卷及答案详解1套
- 2025年4月广东深圳市光明区教育局招聘公办幼儿园人员考前自测高频考点模拟试题及参考答案详解
- 2025年西安凤城医院招聘(21人)模拟试卷含答案详解
- 2025年上半年甘肃陇南文县教师资证认定模拟试卷及参考答案详解1套
- 安全管控培训总结课件
- 2025湖南长沙人才集团有限公司见习人员招聘模拟试卷及一套完整答案详解
- 测绘新技术之无人机的
- 2025年新九年级数学暑假衔接讲练 (人教版)专题07 一元二次方程单元测试 (学生版)
- 气象灾害应急管理课件
- 地铁站消防维保施工方案及技术措施
- 国庆司机安全培训
- 既有建筑抗震加固性能化设计规程T-ZCEAS 1001-2024知识培训
- 十五五住房和城乡建设发展思路
- 马克思主义经典原著选读-1
- T/CUWA 60055-2023城镇排水管道螺旋缠绕内衬法修复用硬聚氯乙烯(PVC-U)带状型材
- 《职业生涯概述》课件
- 企业会计准则实施典型案例
评论
0/150
提交评论