当前位置:今期特马刘伯温玄机图 > 人工约束 >

运筹学第一章 14 大M法和两阶段法ppt

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  等式约束左端引入人工变量的目的 使约束方程的系数矩阵中出现一个单位阵,用单位阵的每一个列向量对应的决策变量作为“基变量”,这样,出现在单纯形表格中的B(i)列(即约束方程的右边常数)值正好就是基变量的取值。 (注意:用非基变量表示基变量的表达式) 表格单纯形法求解步骤 大M法举例 建立辅助线性规划问题得: * * 四、单纯形法的一般描述: ? 1、 初始可行解的确定 (1)初始可行基的确定 观察法—系数矩阵中是否含有现成的单位阵? LP限制条件中全部是“≤”类型的约束 将新增的松弛变量作为初始基变量,对应的系数列向量构成单位阵; 先将约束条件标准化,再引入非负的人工变量, 以人工变量作为初始基变量,其对应的系数列向量构成单位阵,称为“人造基”; 然后用大M法或两阶段法求解; 线性规划限制条件都是“≥”或“=”类型的约束—— ①如果限制条件中既有“≤”类型的约束,又有“≥”或“=”类型的约束,怎麽办? 构造“不完全的人造基”! 讨 论 ②为什麽初始可行基一定要选单位阵? b列正好就是基变量的取值,检验数行 和b列交叉处元素也正好对应目标函数值, 因此称b列为解答列 (2)写出初始基本可行解—— 根据“用非基变量表示基变量的表达式”,非基变量取0,算出基变量,搭配在一起构成初始基本可行解。 2、建立判别准则: (1)两个基本表达式的一般形式 LP限制条件中全部是“≤”类型约束,新增的松弛变量作为初始基变量的情况来描述: 此时LP的标准型为 非基变量 基变量 初始可行基 : 初始基本可行解: 一般(经过若干次迭代),对于基B, 用非基变量表出基变量的表达式 为: 用非基变量表示目标函数的表达式: 若 是对应于基B的基本可行解, 是非基变量 的检验数,若对于一切非基变量的角指标j,均有 ≤0,则X(0)为最优解。 (2)最优性判别定理 (3)无“有限最优解”的判别定理 若 为一基本可行解,有一非基变量xk,其检验数 , 而对于i=1,2,…,m,均有 ,则该线性规划问题没有“有限最优解”。 举例:用非基变量表示基变量的表达式 代表两个约束条件: x2对应的系数列向量P2=(1,3)T, 设:当前的换入变量是 X2,按最小比值原则确定换出变量: 要求: 于是: 如果x2的系数列变成P2’=(-1,0)T,则用非基变量表示基变量的表达式就变成; 可行性自然满足,最小比值原则失效,意即x2的值可以任意增大→原线性规划无“有限最优解”。 3、进行基变换 (1)选择进基变量——原则:正检验数(或最大正检验数)所对应的变量进基,目的是使目标函数得到改善(较快增大); 进基变量对应的系数列称为主元列。 (2)出基变量的确定——按最小比值原则确定出基变量,为的是保持解的可行性; 出基变量所在的行称为主元行。 主元行和主元列的交叉元素称为主元素。 4、主元变换(旋转运算或枢运算) 按照主元素进行矩阵的初等行变换——把主元素变成1,主元列的其他元素变成0(即主元列变为单位向量) 写出新的基本可行解,返回最优性检验。 例1.8的表格单纯形法计算过程: 第一步:将LP化为标准型,并加以整理。 引入适当的松驰变量、剩余变量和人工变 量,使约束条件化为等式,并且约束方程组的 系数阵中有一个单位阵。 (这一步计算机可自动完成) 确定初始可行基,写出初始基本可行解 第二步:最优性检验 计算检验数,检查: ?所有检验数是否≤ 0? 是——结束,写出最优解和目标函数最优值; ?还有正检验数——检查相应系数列≤ 0? 是——结束,该LP无“有限最优解”! ?不属于上述两种情况,转入下一步—基变换。 确定是停止迭代还是转入基变换? 选择(最大)正检验数对应的系数列为主元列,主元列对应的非基变量为换入变量; 最小比值对应的行为主元行,主元行对应的基变量为换出变量。 第三步:基变换 确定进基变量和出基变量。 利用矩阵的初等行变换把主元列变成单位向量,主元素变为1,进基变量对应的检验数变成0,从而得到一张新的单纯形表,返回第二步。 第四步 换基迭代(旋转运算、枢运算) 完成一次迭代,得到新的基本可行解和相应的目标函数值 该迭代过程直至下列情况之一发生时停止 ? 检验数行全部变为非正值; (得到最优解)或 ?主元列≤ 0 (最优解无界) 停止迭代的标志(停机准则) 依据:最优性检验的两个定理 最优性判别定理;无“有限最优解”判断定理 五、各种类型线、分类及处理原则: (1)类型一:目标要求是“Max”,约束条件是“≤”类型——左边加上非负松弛变量变成等式约束(约束条件标准化),将引入的松弛变量作为初始基变量,则初始可行基是一个单位阵,用原始单纯形法求解。 (2)类型二:目标要求是“Max”,约束条件是“=”类型——左边引入非负的人工变量,并将引入的人工变量作为初始基变量,则初始可行基是一个单位阵,然后用大M法或两阶段法求解。 (3)类型三:目标要求是“Max”,约束条件是“≥”类型——约束条件标准化,左边减去非负的剩余变量,变成等式约束,化为类型二。 2、处理人工变量的方法: (1)大M法——在约束条件中人为地加入非负的人工变量,以便使它们对应的系数列向量构成单位阵。 问题:加入的人工变量是否合理?如何处理? 在目标函数中,给人工变量前面添上一个绝对值很大的负系数-M(M0),迭代过程中,只要基变量中还存在人工变量,目标函数就不可能实现极大化——惩罚! ① 最优表中,基变量不包含人工变量,则最优解就是原线性规划的最优解,不影响目标函数的取值; ② 最优表中,基变量中仍含有人工变量,表明原线性规划的约束条件被破坏,线性规划没有可行解,也就没有最优解! 结 果 问题 结果②中求得的最优解是哪个线性规划的最优解?为什麽? 加入松弛变量、剩余变量和人工变量: 六、迭代过程中可能出现的问题及处理方法 1、为确定出基变量要计算比值,该比值=解答列元素/主元列元素。对于主元列的0元素或负元素是否也要计算比值? (此时解的可行性自然满足,不必计算;如果主元列元素全部为0元素或负元素,则最小比值失效,线性规划无“有限最优解”) 2、出现若干个相同的最小比值怎麽办? (说明出现了退化的基本可行解,即非0分量的个数小于约束方程的个数。按照“摄动原理”所得的规则,从相同比值对应的基变量中选下标最大的基变量作为换出变量可以避免出现“死循环”现象) 3、选择进基变量时,同时有若干个正检验数,怎麽选? (最大正检验数或从左至右第1个出现的正检验数所对应的非基变量进基) *

  “原创力文档”前称为“文档投稿赚钱网”,本网站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】

http://aqilabutik.com/rengongyueshu/403.html
点击次数:??更新时间2019-07-03??【打印此页】??【关闭
  • Copyright © 2002-2017 DEDECMS. 织梦科技 版权所有  
  • 点击这里给我发消息
在线交流 
客服咨询
【我们的专业】
【效果的保证】
【百度百科】
【因为有我】
【所以精彩】