版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1.图解法的局限图解法只可解决两个变量的线性规划问题,而在实际应用中还有多个变量的线性规划问题无法解决。因此,
1947年G.B.Dantzig提出的单纯形法提供了方便、有效的通用算法求解线性规划。
1.图解法的局限图解法只可解决两个变量的线性规划问题,而在实2基:已知A是约束条件的m×n系数矩阵,其秩为m。若B是A中m×m阶非奇异子矩阵(即可逆矩阵),则称B是线性规划问题中的一个基。基向量:基B中的一列即称为一个基向量。基B中共有m个基向量。非基向量:在A中除了基B之外的一列则称之为基B的非基向量。基变量:与基向量pi相应的变量xi叫基变量,基变量有m个。非基变量:与非基向量pj相应的变量xj叫非基变量,非基变量有n-m个。基本概念2基:已知A是约束条件的m×n系数矩阵,其秩为m。若B是A中一、单纯形法的基本原理
顶点的逐步转移
即从可行域的一个顶点(基本可行解)开始,转移到另一个顶点(另一个基本可行解)的迭代过程,转移的条件是使目标函数值得到改善(逐步变优),当目标函数达到最优值时,问题也就得到了最优解。一、单纯形法的基本原理
顶点的逐步转移即从可基本思路:基本思路:
根据线性规划问题的可行域是凸多边形或凸多面体,一个线性规划问题有最优解,就一定可以在可行域的顶点上找到。
于是,若某线性规划只有唯一的一个最优解,这个最优解所对应的点一定是可行域的一个顶点;若该线性规划有多个最优解,那么肯定在可行域的顶点中可以找到至少一个最优解。顶点转移的依据根据线性规划问题的可行域是凸多边形或凸多面体表格单纯形法例题1:用单纯形法求解线性规划问题
maxf=3x1+4x2x1+2x2≤63x1+2x2≤12x2≤2x1≥0,x2≥0表格单纯形法例题1:用单纯形法求解线性规划问题首先将此现行规划问题化为标准形式得到:minf’=-f=-3x1-4x2x1+2x2+x3=63x1+2x2+x4=12x2+x5=2x1≥0,x2≥0,x3≥0,x4≥0,x5≥0首先将此现行规划问题化为标准形式表格单纯形法:1、初始单纯形表的建立(1)表格结构:
-3-4000常数dx1x2x3x4x50x31210060x432010120x5010012检验数b340000cjxjxBcB表格单纯形法:-3-4000常数x1x2x3x4x50x31单纯形表的列法:原方程中自带的变量称为非基变量,如x1,x2;为解题而设出的变量称为基变量,如x3,x4,x5。cj:目标函数中变量的系数;xj:变量;xB:基变量;cB:基变量在目标函数中对应的系数;d:各约束条件的常数项;检验数:单纯形表的列法:求例题的检验数:b01=0*1+0*3+0*0-(-3)同理求得b02,b03,b04,b05则最右下角的我们称之为b0,所以b0=0求例题的检验数:解答:(1)确定换入基的变量。只要有检验数b﹥0,对应的变量xj就可作为换入基的变量,当有一个以上检验数大于零时,一般从最大的开始。因此在本题的检验数中找到最大的正检验数。-3-4000常数dx1x2x3x4x50x31210060x432010120x5010012检验数b340000cjxjxBcB解答:-3-4000常数x1x2x3x4x50x312100这说明我要调整非基变量x2,使其成为基变量,并相应调出一个基变量为非基变量。(2)确定换出基的变量。为确定哪个基变量调出首先计算:所以本题有:则此最小值对应x5,所以我们将x5行与x2列相交的数值“1”圈起来。即要将x2与x5进行调整。“1”被称为旋转元素。这说明我要调整非基变量x2,使其成为基变量,并相应调出一个(3)用换入变量xj替换换出变量xB,得到一个新的基。对应这个基找出新的基可行解并列出新的单纯性表。ⅰ)首先将旋转元变为“1”,即将所要转换的基变量行除以旋转元。因为本题中旋转元已经为“1”,所以x5行不用调整。ⅱ)将旋转元所在行转换后的整行数字乘以(-aij),加到表中的第i行数字上,即将要转化为基变量的列变为除转换元为“1”外,其他数字都为“0”的列。在本题中,即是将x5行中的各数乘以(-2),分别加到x3和x4行上。再将x5行乘以(-4)加到检验行上。使得x2列上除了旋转元变为“1”,其余数字都变为“0”。并将xB列中的x5调为x2,表示x2调入基变量,x5调入非基变量。因此得到下表。(3)用换入变量xj替换换出变量xB,得到一个新的基。对应这-3-4000常数dx1x2x3x4x50x31010-220x43001-28-4x2010012检验数b3000-4-8cjxjxBcB以上不过程称之为迭代。如果检验数中任然存在大于“0”的数字,则重复以上3个步骤。直至检验数中所有数字均小于等于0,此时所的的结果即为最优解。-3-4000常数x1x2x3x4x50x31010-220以上线性规划问题所得的最后检验数都小于或等于“0”的单纯形法表格如下:-3-4000常数dx1x2x3x4x5-3x110-1/21/2030x500-3/41/411/2-4x2013/4-1/403/2检验数b00-3/2-1/20-15cjxjxBcB因此得到当x1=3,x2=3/2,x3=x4=0,x5=1/2时,目标函数最大值f=15.以上线性规划问题所得的最后检验数都小于或等于“0”的单纯形法练习1:练习1:①将线性规划问题化成标准型②建立初始单纯形表③计算各非基变量xB的检验数
若所有b≤0,则问题已得到最优解,停止计算,否则转入下步。④在大于0的检验数中,若某个bj﹥0,而所对应的列中没有正数,则此问题是无界解,停止计算,否则转入下步。二、单纯形法的计算步骤
①将线性规划问题化成标准型二、单纯形法的计算步骤⑤根据max{dj|dj>0}=dk原则,确定xk为换入变量(进基变量),再按
规则计算:
=min{bi′/aik′|aik′>0}=bl′/aik′
确定出换出变量。建立新的单纯形表,此时换入非基变量取代了换出基变量的位置。以aik′为主元素进行迭代,把xk所对应的列向量变为单位列向量,即aik′变为1,同列中其它元素为0。后转第③步。
⑤根据max{dj|dj>0}=dk原则,确定xk为换入变量练习2:练习2:人工变量法
用单纯形法解题时,需要有一个单位阵作为初始基。当约束条件都是“≤”时,加入松弛变量就形成了初始基。但实际存在“≥”或“=”型的约束,没有现成的单位矩阵。人工变量
采用人造基的办法:人工构造单位矩阵在没有单位列向量的等式约束中加入人工变量,构成原线性规划问题的伴随问题,从而得到一个初始基。人工变量是在等式中人为加进的,只有它等于0时,约束条件才是它本来的意义。处理方法有两种:大M法两阶段法人工变量法用单纯形法解题时,需要有一个单位阵作为初始基。人例题2:大M法例题2:大M法大M法:本题化为标准形式后,发现只有x4一个基变量,但题中需要三个基变量,于是,加入行x6,x7两个人工变量。其目标函数中的系数为M,M代表任意大的正值。大M法:本题化为标准形式后,发现只有x4一个基变量,但题中需练习3:练习3:两阶段法:第一阶段:先求解一个目标函数中只包含人工变量的线性规划问题,即令目标函数中的其他变量系数取零,人工变量的系数取某个正的常数(一般取1),在保持原问题约束条件不变的情况下求这个目标函数极小化的解。显然在第一阶段中,当人工变量取值为零时,目标函数值为零。这个时候的最优解就是原线性规划问题的一个基可行解。如果第一阶段求解结果最优解的目标函数值不为零,即最优解的非基变量中含有非零的人工变量,表明线性规划问题无可行解。第二阶段:当第一阶段求解结果表明问题有可行解,则此阶段在原问题中去除人工变量,并从此可行解出发继续寻找最优解。两阶段法:第一阶段:先求解一个目标函数中只包含人工变量的线性例3:两阶段法例3:两阶段法单纯形法一般还可证明:1.解的情况:(1)如果在单纯形表中所有检验数
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 城市照明设施施工协议模板
- 劳动合同变更与解除协议
- 物流行业合作协议模板
- 工业建筑改造合同
- 山东学校劳务合同模板
- 挤塑板订购合同范例
- 新加坡华文教师合同范例
- 新加坡物业租房合同范例
- 学校雕塑定购合同模板
- 家具生产 安装合同范例
- GB/T 41715-2022定向刨花板
- YC/T 384.3-2018烟草企业安全生产标准化规范第3部分:考核评价准则和方法
- 夏商周考古课件 第5章 西周文化(3节)
- GB/T 7324-2010通用锂基润滑脂
- GB/T 4459.1-1995机械制图螺纹及螺纹紧固件表示法
- 危险化学品安全告知牌硝酸、盐酸、硫酸、氢氧化钠
- GB/T 29163-2012煤矸石利用技术导则
- 上海英文介绍课件
- 上交所个股期权基础知识课件
- 最新山羊、绵羊人工授精技术及新技术介绍(含人工授精视频)课件
- 2022年征信知识竞赛基础题题库(含各题型)
评论
0/150
提交评论