般地,记松弛变量的向量为X,则 AX<6 AX+ⅣX=b st s t X≥0 XX≥0 ax>6 AX-X=b s t st X≥0 XX≥0 问题:松弛变量在目标中的系数为何?——-0 3)当模型中有某变量x没有非负要求,称 为自由变量,则可令x=x-x,x,x"≥0 化为标准型
一般地，记松弛变量的向量为 Xs，则 0 . . X AX b st + = , 0 . . s s X X AX IX b st 0 . . X AX b st − = , 0 . . s s X X AX IX b st 问题：松弛变量在目标中的系数为何？ —— 0。 3) 当模型中有某变量 xk 没有非负要求，称 为自由变量, 则可令 , , 0 / // / // xk = xk − xk xk xk 化为标准型
2基本概念 (1)可行解与最优解 可行解:满足全体约束的解,记为X 最优解:可行解中最优的,记为X,则对任可行 解X,有CX≤CX。 直观上,可行解是可行域中的点,是一个可行的方案; 最优解是可行域的角点,是一个最优的方案
2.基本概念 （1）可行解与最优解 可行解：满足全体约束的解，记为X； 解 ，有 。 最优解：可行解中最优的，记为 则对任可行 * , X CX CX X 直观上，可行解是可行域中的点，是一个可行的方案； 最优解是可行域的角点，是一个最优的方案
(2)基矩阵与基变量 基矩阵(简称基):系数阵A中的m阶可逆子阵,记 为B;其余部分称为非基矩阵,记为N 基向量:基B中的列;其余称非基向量。 基变量:与基向量P对应的决策变量x,记其组成的 向量为XB;与非基向量对应的变量称非基变 量,记其组成的向量为XN 例3:下面为某线性规划的约束 +2x+ 2x1-x2+x4=3 x1,…x4≥0 请例举出其基矩阵和相应的基向量、基变量
（2）基矩阵与基变量 基矩阵(简称基)：系数阵A中的m阶可逆子阵，记 为B；其余部分称为非基矩阵，记为N。 基向量：基B中的列；其余称非基向量。 基变量：与基向量Pj对应的决策变量xj，记其组成的 向量为XB；与非基向量对应的变量称非基变 量，记其组成的向量为XN。 1 2 3 1 2 4 1 4 3 2 1 2 3 , , 0 x x x x x x x x + + = − + = 例 ：下面为某线性规划的约束 请例举出其基矩阵和相应的基向量、基变量
例3:下面为某线性规划的约束 +2x,+ x,-x2 +x 3 x,≥0 请例举出其基矩阵和相应的基向量、基变量。 1210 解:本例中,A 2-101}4中的阶可逆子阵有 B 其相应的基向量为,P,基变量为x,x,X 2 B 其相应的基向量为P,P,基变量为x,x,X 问题:本例的A中一共有几个基? 般地,m×n阶矩阵基的个数最多有多少个?——C个
1 2 3 1 2 4 1 4 3 2 1 2 3 , , 0 x x x x x x x x + + = − + = 例 ：下面为某线性规划的约束 请例举出其基矩阵和相应的基向量、基变量。 解：本例中， ， 中的2阶可逆子阵有 1 0 0 1 1 2 2 1 A A − = —— 6个。 一般地，m×n 阶矩阵A中基的个数最多有多少个？ — —C 个。 , , , ; 1 0 0 1 4 3 1 3 4 3 4 1 = = x x B ，其相应的基向量为P P 基变量为x x ，X 其相应的基向量为 基变量为 。 = − = 2 1 2 1 2 1 2 2 , , , , , 1 2 2 1 x x B P P x x X 问题：本例的A中一共有几个基？
(3)基本解与基本可行解 当A中的基B取定后,不妨设B表示A中的前m列,则可记A=(BN) 相应地X=(X。X),约束中的AX=b可表示为BN b 即X2=Bb-BNX当取X,=0时,有X。=Bb、X(Bb 0 称AX=b的解X= (Bb 为线性规划的一个基本解 可见:一个基本解是由一个基决定的。 注意:基本解仅是资源约束的解,并未要求其非负,因此其未必可行。 称非负的基本解为基本可行解(简称基可行解)
（3）基本解与基本可行解 ( ) ( ) . 0 , 0 , , , , 1 1 1 1 = − = = = = = = = − − − − B b X B b B N X X X B b X b X X X X X A X b B N A B B A m A B N 即 当取 时，有 相应地 约束中的 可表示为 当 中的基 取定后，不妨设 表示 中的前 列，则可记 （ ） 称 的解 为线性规划的一个基本解； = = − 0 B b A X b X 可见：一个基本解是由一个基决定的。 注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。 称非负的基本解为基本可行解（简称基可行解）