使用单纯形法解线性规划问题.pdf

《使用单纯形法解线性规划问题.pdf》由会员分享，可在线阅读，更多相关《使用单纯形法解线性规划问题.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、使用单纯形法解线性规划问题 The final edition was revised on December 14th,2020.使用单纯形法解线性规划问题使用单纯形法解线性规划问题要求：要求：目标函数为：min z 3x1 x2 x3约束条件为：x12x2 x3114x x 2x 31232x1 x31x1,x2,x3 0用单纯形法列表求解，写出计算过程。解：解：1）将线性规划问题标准化如下：目标函数为：max f max(z)3x1 x2 x3x12x2 x3 x4114x x 2x x x 312356.：2x1 x3 x71x1,x2,x3,x4,x5,x6,x7 02）找出初始基变

2、量，为 x4、x6、x7，做出单纯形表如下：表一：最初的单纯形表表一：最初的单纯形表变量基变量x4x6x7-f3）x11-4-2-3x2-2101x31211x41000 x50-100 x60100 x70010bi11310换入变量有两种取法，第一种取为 x2，相应的换出变量为 x6，进行第一次迭代。迭代后新的单纯形表为：表二：第一种换入换出变量取法迭代后的单纯形表表二：第一种换入换出变量取法迭代后的单纯形表变量基变量x4x2x1-7-4x201x352x410 x5-2-1x621x700bi33x7-f-21001-100010-1101-3由于 x1和 x5对应的系数不是 0 就是负

3、数，所以此时用单纯形法得不到最优解。表一中也可以把换入变量取为 x3，相应的换出变量为 x7，进行一次迭代后的单纯形表为：表三：第二种换入换出变量取法迭代后的单纯形表表三：第二种换入换出变量取法迭代后的单纯形表变量基变量x4x6x3-fx130-2-1x2-2101x30010 x41000 x50-100 x60100 x7-1-21-1bi1011-14）表三中，取换入变量为 x2，换出变量为 x6，进行第二次迭代。之后的单纯形表为：表四：第二次迭代后的单纯形表表四：第二次迭代后的单纯形表变量基变量x4x2x3-fx130-2-1x20100 x30010 x41000 x5-2-101x6210-1x7-5-211bi1211-25）表四中，取换入变量为 x7，换出变量为 x3，进行第三次迭代。之后的单纯形表为：表五：第三次迭代后的单纯形表表五：第三次迭代后的单纯形表变量基变量x4x2x7-fx1-7-4-21x20100 x3521-1x41000 x5-2-101x6210-1x70010bi1731-3可以看出，此时 x1，x5对应的系数全部非零即负，故迭代结束，没有最优解。结论：结论：综上所述，本线性规划问题，使用单纯形法得不到最优解。