求线性规划问题的最优解.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,目标函数值还可以增大,故基可行解仍然不是最优解。第六步,作基变换,求目标值比更大的基可行解。① 确定换入基变量。由第五步可知,只有,即是换入基变量,②确定换出基变量。作为换入基变