线性规划问题的数学模型 Page 16 4.线性规划问题的解 线性规划问题 -0 4,X,=b=12,m）-2) s.t i=l x,20,j=1,2,.,n-(3) 求解线性规划问题，就是从满足约束条件(2)、(3)的方程组 中找出一个解，使目标函数()达到最大值
线性规划问题的数学模型 Page 16 4. 线性规划问题的解 = − − − − − − = = − − = − − − − − − − − − − = = 0, 1,2, , (3) ( 1,2, , ) (2) . max (1) 1 1 x j n a x b i m s t Z c x j n j ij j i n j j j 线性规划问题 求解线性规划问题，就是从满足约束条件(2)、(3)的方程组 中找出一个解，使目标函数(1)达到最大值
线性规划问题的数学模型 Page 17 ●可行解：满足约束条件②、③的解为可行解。所有可行解 的集合为可行域。 ·最优解：使目标函数达到最大值的可行解。 ●基：设A为约束条件②的m×n阶系数矩阵(m<n),其秩为 m,B是矩阵A中m阶满秩子矩阵(|B|0),称B是规划问 题的一个基。设： B= =(P1.pn) a 称B中每个列向量P,(j=12.W为基向量。与基向量P 对应的变量x,为基变量。除基变量以外的变量为非基变量
线性规划问题的数学模型 Page 17 可行解：满足约束条件②、③的解为可行解。所有可行解 的集合为可行域。 最优解：使目标函数达到最大值的可行解。 基：设A为约束条件②的m×n阶系数矩阵(m<n)，其秩为 m，B是矩阵A中m阶满秩子矩阵（∣B∣≠0），称B是规划问 题的一个基。设： ( ) 1 1 1 1 1 m m m m m p p a a a a B = = 称 B中每个列向量Pj ( j = 1 2 . . m) 为基向量。与基向量Pj 对应的变量xj为基变量。除基变量以外的变量为非基变量
线性规划问题的数学模型 Page 18 ●基解：某一确定的基B,令非基变量等于零，由约束条件 方程②解出基变量，称这组解为基解。在基解中变量取非0 值的个数不大于方程数m,基解的总数不超过Cm ●基可行解：满足变量非负约束条件的基本解，简称基可 行解。 ·可行基：对应于基可行解的基称为可行基。 可行 基解 非坷行解 基可行解
线性规划问题的数学模型 Page 18 基解：某一确定的基B，令非基变量等于零，由约束条件 方程②解出基变量，称这组解为基解。在基解中变量取非0 值的个数不大于方程数m，基解的总数不超过 基可行解：满足变量非负约束条件的基本解，简称基可 行解。 可行基：对应于基可行解的基称为可行基。 m C n 非可行解 可 行 解 基解 基可行解
线性规划问题的数学模型 Page 19 例1.4求线性规划问题的所有基矩阵。 max Z=4x -2.x2-x; 5x1+x2-x3+x4=3 -10x,+6x2+2x3+x,=2 x,≥0，j=1,.,5 解约*方程的系数矩降为2×5矩阵4-[36}】 r(A)=2,2阶子矩阵有10个，其中基矩阵只有9个，即 [i。s[&%-[i86周 A-[iw司A=[a=[%-6]s]
线性规划问题的数学模型 Page 19 例1.4 求线性规划问题的所有基矩阵。 = − + + + = + − + = = − − 0, 1, ,5 10 6 2 2 5 3 max 4 2 1 2 3 5 1 2 3 4 1 2 3 x j x x x x x x x x Z x x x j 解: 约束方程的系数矩阵为2×5矩阵 − − = 10 6 2 0 1 5 1 1 1 0 A r(A)=2，2阶子矩阵有10个，其中基矩阵只有9个，即 = = − = − = − = = − = − = − = 0 1 1 0 6 1 1 0 2 0 1 1 2 1 1 0 1 0 0 5 1 6 0 1 1 1 0 1 5 0 6 2 1 1 1 0 6 5 1 5 6 7 8 9 1 2 3 4 B B B B B B B B B
图解法 Page 20 线性规划问题的求解方法 两个变量、直角坐标 一般有 图解法 三个变量、立体坐标 两种方法 单纯形法 适用于任意变量、但必需将 一般形式变成标准形式 下面我们分析一下简单的情况一只有两个决策 变量的线性规划问题，这时可以通过图解的方法来 求解。图解法具有简单、直观、便于初学者窥探线 性规划基本原理和几何意义等优点
图解法 Page 20 线性规划问题的求解方法 一 般 有 两种方法 图 解 法 单纯形法 两个变量、直角坐标 三个变量、立体坐标 适用于任意变量、但必需将 一般形式变成标准形式 下面我们分析一下简单的情况——只有两个决策 变量的线性规划问题，这时可以通过图解的方法来 求解。图解法具有简单、直观、便于初学者窥探线 性规划基本原理和几何意义等优点