为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

单纯形法

2012-03-09 9页 ppt 202KB 111阅读

用户头像

is_717410

暂无简介

举报
单纯形法null单纯形法的计算步骤单纯形法的计算步骤3)进行最优性检验如果表中所有检验数 ,则表中的基可行解就是问题的最优解,计算停止。否则继续下一步。4)从一个基可行解转换到另一个目标值更大的基可行解,列出新的单纯形表确定换入基的变量。选择 ,对应的变量xj作为换入变量,当有一个以上检验数大于0时,一般选择最大的一个检验数,即: ,其对应的xk作为换入变量。 确定换出变量。根据下式计算并选择θ ,选最小的θ对应基...
单纯形法
null单纯形法的计算步骤单纯形法的计算步骤3)进行最优性检验如果表中所有检验数 ,则表中的基可行解就是问的最优解,计算停止。否则继续下一步。4)从一个基可行解转换到另一个目标值更大的基可行解,列出新的单纯形表确定换入基的变量。选择 ,对应的变量xj作为换入变量,当有一个以上检验数大于0时,一般选择最大的一个检验数,即: ,其对应的xk作为换入变量。 确定换出变量。根据下式计算并选择θ ,选最小的θ对应基变量作为换出变量。 单纯形法的计算步骤单纯形法的计算步骤用换入变量Xk替换基变量中的换出变量,得到一个新的基。对应新的基可以找出一个新的基可行解,并相应地可以画出一个新的单纯形表。 5)重复3)、4)步直到计算结束为止。 单纯形法的进一步讨论-人工变量法单纯形法的进一步讨论-人工变量法一、人工变量法: 前面讨论了在型中系数矩阵有单位矩阵,很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵,为了得到一组基向量和初始基可行解,在约束条件的等式左端加一组虚拟变量,得到一组基变量。这种人为加的变量称为人工变量,构成的可行基称为人工基,用大M法或两阶段法求解,这种用人工变量作桥梁的求解方法称为人工变量法。  1、大M 法   通过引进人工变量,构造一个辅助的线性规划问题,然后由辅助的线性规划问题找出原问题的第一个初始可行基,在此基础上,利用单纯形方法求出原问题的最优解。null 2、两阶段法   在原来问题引入人工变量后分两个阶段求解线性规划问题的方法。其中,第一阶段在原来问题中引入人工变量,设法构造一个单位阵的初始可行基,另外在目标函数中令非人工变量的系数全部为0,人工变量的系数为1,构造一个新的辅助目标函数。在此基础上,建立辅助线性规划问题。然后运用单纯形方法求解,直到辅助目标函数值为0时为止。第二阶段重新回到原来的问题,以第一阶段得到的可行基为初始可行基,运用单纯形方法以求出原来问题的解。null   3)两阶段法的计算步骤  (1)不考虑原问题是否存在基可行解, 引进人工变量,构造辅助线性规划问题。  (2)用单纯形方法求解辅助问题,若辅助问题的目标函数值w≠ 0,则原问题无可行解,停止计算。 (3)若辅助问题目标函数的值w =0,则将第一阶段计算得到的最终表,除去人工变量,将目标函数行的系数换原问题的目标函数系数,作为第二阶段的初始表。   4)解的判断同单纯形法单纯形法的进一步讨论-人工变量法单纯形法的进一步讨论-人工变量法 解的判别: 1)唯一最优解判别:最优表中所有非基变量的检验数非零,且基变量中无非零的人工变量,则线规划具有唯一最优解。 2)多重最优解判别:最优表中存在非基变量的检验数为零,且基变量中无非零的人工变量,则线则性规划具有多重最优解(或无穷多最优解)。 3)无界解判别:某个σk>0且aik≤0(i=1,2,…,m)则线性规划具有无界解。 4)无可行解的判断:当用大M单纯形法计算得到最优解并且存在人工变量>0时,则表明原线性规划无可行解。 5)退化解的判别:存在某个基变量为零的基本可行解。null 二、退化、循环及其处理方法 1、退化 单纯形法计算中用θ规则确定换出变量时,有时存在两个以上相同的最小比值,这样在下一次迭代中就有一个或几个基变量等于零,这就出现退化解。 2、退化迭代的特点 (1)退化解的基变量中至少有一个取值为0。 (2)退化迭代中基在不断变化但解始终不变。 (3)退化迭代不会引起目标函数值的改进。 3、防止循环迭代的方法 (1)摄动法 (2)字典顺序法 (3)最小下标法 单纯形法小结单纯形法小结null
/
本文档为【单纯形法】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索