单纯形法的解题步骤.doc

单纯形法的解题步骤.doc

ID:58476721

大小:60.50 KB

页数:6页

时间:2020-05-15

单纯形法的解题步骤.doc_第1页
单纯形法的解题步骤.doc_第2页
单纯形法的解题步骤.doc_第3页
单纯形法的解题步骤.doc_第4页
单纯形法的解题步骤.doc_第5页
资源描述:

《单纯形法的解题步骤.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、三、单纯形法的解题步骤第一步:作单纯形表.(1)                                                                    (1)把原线性规划问题化为标准形式;(2)                                                                    (2)找出初始可行基,通常取约束方程组系数矩阵中的单位矩阵;(3)                                                   

2、                 (3)目标函数非基化;(4)                                                                    (4)作初始单纯形表.第二步:最优解的判定.(1)若所有检验数都是非正数,即,则此时线性规划问题已取得最优解.(2)若存在某个检验数是正数,即,而所对应的列向量无正分量,则线性规划问题无最优解.如果以上两条都不满足,则进行下一步.第三步:换基迭代.(1)找到最大正检验数,设为,并确定所在列的非基变量为进基变量.(2)对最大正检验数

3、所在列实施最小比值法,确定出主元,并把主元加上小括号.主元是最大正检验数所在列,用常数项与进基变量所对应的列向量中正分量的比值最小者;(3)换基:用进基变量替换出基变量,从而得到新的基变量.也就是主元所在列的非基变量进基,所在行的基变量出基;(4)利用矩阵的行初等变换,将主元变为1,其所在列其他元素都变为零,从此得到新的单纯形表;(5)回到第二步,继续判定最优解是否存在,然后进行新一轮换基迭代,直到问题得到解决为止.例3求.解(1)化标准型:令,引进松弛变量,其标准型为求(2)作单纯形表:在约束方程组系数矩阵中的系数构成单位

4、矩阵,故取为基变量,目标函数已非基化了,作初始单纯形表并“换基迭代”(见表6.8). x1x2x3x4x5常数x3x4x510100120100(1)0015104S′130000x3x4x210100(1)001-201001524S′1000-3-12x3x1x2001-121001-201001324S′000-1-1-14表6.8             (3)最终结果:此时检验数均为非正数,线性规划问题取得最优解,最优解为目标函数取得最优值.原线性规划问题的最优解为:.目标函数的最优值为14,即.例4用单纯形方法解

5、线性规划问题.求.解此数学模型已是标准型了,其中约束方程含有一个二阶单位矩阵(1、2行,3、4列构成),取为基变量,而目标函数没有非基化.从约束方程找出,,代入目标函数,经整理后,目标函数非基化了.作单纯形表,并进行换基迭代(见表6.9).最大检验数,由最小比值法知:为主元,对主元所在列施以行初等变换,基变量出基,非基变量进基.表6.9 x1x2x3x4常数x3x41-110-3(1)0124S23000x3x2-2011-310164S1100-312 目前最大检验数,其所在列没有正分量,所以该线性规划问题没有最优解.例5

6、用单纯形方法解线性规划问题.求解此数学模型已是标准型了,其中约束方程含有一个二阶单位矩阵,取为基变量,而目标函数没有非基化.从约束方程找出,,代入目标函数,经整理得,目标函数已非基化.作单纯形表,并进行换基迭代(见表6.10).最大检验数,由最小比值法知:为主元,对主元所在列施以行初等变换,基变量出基,非基变量x2进基,先将主元化为1,然后再将主元所在列的其他元素化为零.表6.10 x1x2x3x4常数x3x4-2(2)10310146S-220010x2x4-11040-124S’00-106         至此,检验数

7、均为非正数,故得基础可行解.原问题的最优解为:.最优值为6,即.如果我们再迭代一次,将基变量出基,非基变量进基(见表6.11).表6.11 x1x2x3x4常数x2x4-110(4)0124S’00-106x2x1011031S’00-1 06           可得到另一个基础可行解,原问题的最优解为:,最优值仍为6,说明该线性规划问题有无穷多最优解,其最优解均为6.如何知道线性规划问题有无穷多最优解呢?这主要反映在单纯形表中.如果非基变量所对应的检验数为0,我们可对此列继续进行换基迭代,就可以得到另一个基础可行解.以此

8、作下去,可得到许多基础可行解,即相对应的最优解有无穷多个.1.若不给自己设限,则人生中就没有限制你发挥的藩篱。2.若不是心宽似海,哪有人生风平浪静。在纷杂的尘世里,为自己留下一片纯静的心灵空间,不管是潮起潮落,也不管是阴晴圆缺,你都可以免去浮躁,义无反顾,勇往直前,轻松自如地走好人生路上的

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。