求线性规划问题的最优解

《求线性规划问题的最优解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、求线性规划问题的最优解：方法1：图解法。（P15图1-3）方法2：求出所有的基可行解，然后比较目标值的大小得到最优解。（P14表1-1）方法3：单纯形法。第一步，将模型转化为标准型。秩A=3第二步，求初始基可行解。取作为初始基矩阵，为基变量，为非基变量，令得到初始基可行解，目标值第三步，对初始基可行解进行最优性检验。基可行解对应的目标值为，因为，只要或者，目标值都会比大，即之一作为基变量，目标值都会增大，故初始基可行解不是最优解。第四步，作基变换，求目标值比更大的基可行解。①确定换入基变量。由第三步可知

2、，都可作为换入基变量，一般地，。作为换入基变量。这里称为基可行解非基变量的检验数。②确定换出基变量。作为换入基变量，仍为非基变量，下面确定另一个非基变量，由方程组（1）（2）（3）得到令且得到，解不等式得到。当时，，都不能作为非基变量，但中必须有一个被换出来作为非基变量，我们注意到当时，，说明可以作为非基变量。③求目标值更大的基可行解。由①②知，新的基可行解中是基变量，是非基变量，注意方程组（1）（2）（3）中的系数列向量已经是单位矩阵的第一列和第二列，的系数列向量应变换为单位矩阵的第三列，而方程组只能

3、是恒等变形，所以让第三个方程，然后让第三个方程再加到第一各方程上，可得到下列与（1）（2）（3）等价的方程组令得到新的基可行解，目标值第五步，对基可行解进行最优性检验。将目标函数用非基变量表示，因为的检验数，故从非基变量取0变为大于0，不会使得目标函数值增大，反而更小，但是的检验数，故从非基变量取0变为大于0，目标函数值还可以增大，故基可行解仍然不是最优解。第六步，作基变换，求目标值比更大的基可行解。①确定换入基变量。由第五步可知，只有，即是换入基变量，②确定换出基变量。作为换入基变量，仍为非基变量，下

4、面确定另一个非基变量，由方程组得到令且得到，解不等式得到。当时，，都不能作为非基变量，但中必须有一个被换出来作为非基变量，我们注意到当时，，说明可以作为非基变量。③求目标值更大的基可行解。由①②知，新的基可行解中是基变量，是非基变量，注意方程组中的系数列向量已经是单位矩阵的第三列和第二列，的系数列向量应变换为单位矩阵的第一列，而方程组只能是恒等变形，所以让第一个方程，然后让第一个方程再加到第二个方程，可得到下列与等价的方程组令得到新的基可行解，目标值第七步，对基可行解进行最优性检验。将目标函数用非基变量

5、表示，因为的检验数都小于0，故或者从非基变量取0变为大于0，都不会使得目标函数值增大，反而更小，故基可行解是最优解。