求线性规划问题的最优解.doc

求线性规划问题的最优解：

方法1：图解法。（P15图1-3）

方法2：求出所有的基可行解，然后比较目标值的大小得到最优解。（P14表1-1）

方法3：单纯形法。
第一步，将模型转化为标准型。
秩A=3
第二步，求初始基可行解。
取作为初始基矩阵，为基变量，为非基变量，
令得到初始基可行解，目标值
第三步，对初始基可行解进行最优性检验。
基可行解对应的目标值为，因为，只要或者，目标值都会比大，即之一作为基变量，目标值都会增大，故初始基可行解不是最优解。
第四步，作基变换，求目标值比更大的基可行解。
①确定换入基变量。由第三步可知，都可作为换入基变量，一般地，
。
作为换入基变量。这里称为基可行解非基变量的检验数。
②确定换出基变量。作为换入基变量，仍为非基变量，下面确定另一个非基变量，由方程组（1）（2）（3）得到
令且得到，解不等式得到。
当时，，都不能作为非基变量，但中必须有一个被换出来作为非基变量，我们注意到当时，，说明可以作为非基变量。
③求目标值更大的基可行解。
由①②知，新的基可行解中是基变量，是非基变量，注意方程组（1）（2）（3）中的系数列向量已经是单位矩阵的第一列和第二列，的系数列向量应变换为单位矩阵的第三列，而方程组只能是恒等变形，所以让第三个方程，然后让第三个方程再加到第一各方程上，可得到下列与（1）（2）（3）等价的方程组

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

令得到新的基可行解，目标值
第七步，对基可行解进行最优性检验。
将目标函数用非基变量表示，

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