5.3定义和定理 对n维线性规划问题的求解,已不能使用图 解法。为了用代数方法求解,我们需要相应的概 念和定理,首先给出线性规划标准形式的矩阵表 示。 min f=c x s.t. aX=b (54) X>0 点击此处结束放映
5.3 定义和定理 对n维线性规划问题的求解，已不能使用图 解法。为了用代数方法求解，我们需要相应的概 念和定理，首先给出线性规划标准形式的矩阵表 示。 （5.4）
下面是基本解,基矩阵,基变量,非 基变量,基本可行解的定义。 设的A秩为m,且在[刷M,其中B是 可逆矩阵。如果的前m列线性相关,则可 通过列调换,使前m线性无关。因此,关 于逆的假设不失一般性。 点击此处结束放映
下面是基本解，基矩阵，基变量，非 基变量，基本可行解的定义。 设的A秩为m，且A=[BN]，其中B是m阶 可逆矩阵。如果A的前m列线性相关，则可 通过列调换，使前m列线性无关。因此，关 于B可逆的假设不失一般性
设X=B,其中的分量与肿 的列对应,的分量与N中的列对应。 于是,可以把Ab写成 B b 点击此处结束放映
设 ，其中的XB分量与B中 的列对应，XN的分量与N中的列对应。 于是，可以把AX=b写成
从而,B+M=b。对该式两端左乘B1,可 得到B4b-B1M。的分量就是“线性代数” 中所说的自由分量。它们取不同的值,就会得到 方程组不同的解。令=0,则得到 xX B 6 称其为AX=b的一个基本解。B称为基矩阵。 X的各分量称为基变量。X的各分量称为非 基变量。当B1b>0时,则称X为满足约束条件 AX=b,X≌0的基本可行解。 点击此处结束放映
从而，BXB+NXN=b。对该式两端左乘B -1 ，可 得到XB=B -1 b-B -1NXN 。XN的分量就是“线性代数” 中所说的自由分量。它们取不同的值，就会得到 方程组不同的解。令XN＝0，则得到 称其为AX=b的一个基本解。B称为基矩阵。 XB的各分量称为基变量。XN的各分量称为非 基变量。当B-1b≥0时，则称X为满足约束条件 AX=b，X≥0的基本可行解
54单纯形算法 由定理1我们已经知道,最优解必从基本 可行解中得到。因此,需要构造一种计算方 法:只考察基本可行解序列,且这一序列的 目标值应逐渐减小,直到达到最优值为止。 表5-2是依据问题5.5)的目标函数和等式 约束条件得到的。 点击此处结束放映
5.4 单纯形算法 由定理1我们已经知道，最优解必从基本 可行解中得到。因此，需要构造一种计算方 法：只考察基本可行解序列，且这一序列的 目标值应逐渐减小，直到达到最优值为止。 表5-2是依据问题(5.5)的目标函数和等式 约束条件得到的