




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
单纯形法的计算步骤例1.10用单纯形法求下列线性规划的最优解将问题化为标准型,加入松驰变量x3、x4则标准型为:12/23/2022单纯形法的计算步骤2)求出线性规划的初始基可行解,列出初始单纯形表。cj3400θicBXBbx1x2x3x40x34021100x4301301检验数003?12/23/2022单纯形法的计算步骤3)进行最优性检验如果表中所有检验数,则表中的基可行解就是问题的最优解,计算停止。否则继续下一步。4)从一个基可行解转换到另一个目标值更大的基可行解,列出新的单纯形表确定换入基的变量。选择,对应的变量xj作为换入变量,当有一个以上检验数大于0时,一般选择最大的一个检验数,即:,其对应的xk作为换入变量。确定换出变量。根据下式计算并选择θ
,选最小的θ对应基变量作为换出变量。 12/23/2022单纯形法的计算步骤cj3400θicB基变量bx1x2x3x40x34021100x430130134000x34x23x14x2换入列bi/ai2,ai2>04010换出行将3化为15/311801/301/3101-1/3303005/30-4/3乘以3/5后得到103/5-1/51801-1/5-2/5400-1-1最优解:最优值:12/23/2022单纯形法的计算步骤例1.11用单纯形法求解解:将数学模型化为标准形式:不难看出x4、x5可作为初始基变量,列单纯形表计算。12/23/2022单纯形法的计算步骤cj12100θicB基变量bx1x2x3x4x50x4152-32100x5201/31501121000x42x220-x221/3150120753017131/30-90-22560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3最优解:最优值:12/23/2022单纯形法的进一步讨论-人工变量法一、人工变量法: 前面讨论了在标准型中系数矩阵有单位矩阵,很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵,为了得到一组基向量和初始基可行解,在约束条件的等式左端加一组虚拟变量,得到一组基变量。这种人为加的变量称为人工变量,构成的可行基称为人工基,用大M法或两阶段法求解,这种用人工变量作桥梁的求解方法称为人工变量法。1、大M法
通过引进人工变量,构造一个辅助的线性规划问题,然后由辅助的线性规划问题找出原问题的第一个初始可行基,在此基础上,利用单纯形方法求出原问题的最优解。12/23/2022单纯形法的进一步讨论-人工变量法故人为添加两个单位向量,得到人工变量单纯形法数学模型:其中:M是一个很大的抽象的数,不需要给出具体的数值,可以理解为它能大于给定的任何一个确定数值;再用前面介绍的单纯形法求解该模型,计算结果见下表。12/23/2022
2、两阶段法在原来问题引入人工变量后分两个阶段求解线性规划问题的方法。其中,第一阶段在原来问题中引入人工变量,设法构造一个单位阵的初始可行基,另外在目标函数中令非人工变量的系数全部为0,人工变量的系数为1,构造一个新的辅助目标函数。在此基础上,建立辅助线性规划问题。然后运用单纯形方法求解,直到辅助目标函数值为0时为止。第二阶段重新回到原来的问题,以第一阶段得到的可行基为初始可行基,运用单纯形方法以求出原来问题的解。12/23/2022
例4.2
用两阶段法求解线性规划问题minΖ=-3x1+x2+x3s.t.x1-2x2+x3≤11-4x1+x2+2x3≥3-2x1+x3=1x1,x2,x3,≥0解:先在约束条件中加入人工变量,写出辅助规划问题。MinW=x6+x7s.t.x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1+x3+x7=1xi≥0,i=1,2,…,712/23/2022
用单纯形法进行第一阶段的计算如下表12/23/2022
人工变量x6=x7=0,第一阶段目标函数W=0,则(0,1,1,12,0)T是原线性规划问题的基可行解,转第二阶段的计算12/23/2022
由表可得最优解为:x1=4,x2=1,x3=9;目标函数值Z=-212/23/2022单纯形法的进一步讨论-人工变量法 解的判别:1)唯一最优解判别:最优表中所有非基变量的检验数非零,且基变量中无非零的人工变量,则线规划具有唯一最优解。2)多重最优解判别:最优表中存在非基变量的检验数为零,且基变量中无非零的人工变量,则线则性规划具有多重最优解(或无穷多最优解)。3)无界解判别:某个σk>0且aik≤0(i=1,2,…,m)则线性规划具有无界解。4)无可行解的判断:当用大M单纯形法计算得到最优解并且存在人工变量>0时,则表明原线性规划无可行解。5)退化解的判别:存在某个基变量为零的基本可行解。12/23/2022单纯形法小结建立模型个数取值右端项等式或不等式极大或极小新加变量目标系数两个三个以上xj≥0xj无约束xj≤0
bi
≥0bi<0≤=≥maxZminZxs
xa求解图解法、单纯形法单纯形法不处理令xj=
xj′
-xj″
xj′
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025网络版自建房买卖合同书
- 保姆三方合同样本
- led灯珠合同样本
- 个体商合伙合同样本
- 企业电缆出售合同标准文本
- 业务员用工合同样本
- 农村水管收购合同样本
- 农民工法律援助合同样本
- 冰糖代加工合同样本
- 2025年蔬菜采购合同范本
- 2025年全球及中国包裹接收和追踪软件行业头部企业市场占有率及排名调研报告
- 小学校长学校管理讲座
- 河道水毁清理维护施工合同
- DB32T 4355-2022 建筑施工附着式升降设施安全技术规程(修)
- 农村初级电工培训
- 2025年国家粮食和物资储备局垂直管理系统事业单位招聘(869人)历年管理单位笔试遴选500模拟题附带答案详解
- 电力拖动自动控制系统试卷带答案
- 肌肉注射护理讲课课件
- 车辆油箱盖产品入市调查研究报告
- 工业大数据采集处理与应用
- 皮肤科(规培)练习题库与答案
评论
0/150
提交评论