管理会计MAchp6-线性规划.pptVIP

Chapter 1 线性规划 Linear Programming 综合起来得到下列标准型 1.3 线性规划的标准型 Standard form of LP Chapter 1 线性规划 Linear Programming 当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束 将其化为两个不等式 再加入松驰变量化为等式。 1.3 线性规划的标准型 Standard form of LP 1.4 线性规划的有关概念 Basic Concepts of LP Chapter 1 线性规划 Linear Programming 设线性规划的标准型 max Z=CX (1.1) AX=b (1.2) X ≥0 (1.3) 式中A 是m×n矩阵，m≤n并且r(A)=m，显然A中至少有一个m×m子矩阵B，使得r(B)=m。 1.4 基本概念 Basic Concepts 基 (basis)：A中 m×m子矩阵 B 并且有r(B)=m，则称B是线性规划的一个基(或基矩阵basis matrix )。 注：基矩阵B必为非奇异矩阵(可逆矩阵)即|B|≠0。 当m=n时，基矩阵惟一，当mn时，基矩阵就可能有多个，但数目不超过 Chapter 1 线性规划 Linear Programming 【例2】线性规划 求所有基矩阵。 【解】约束方程的系数矩阵为2×5矩阵 1.4 基本概念 Basic Concepts Chapter 1 线性规划 Linear Programming 容易看出r(A)=2，2阶子矩阵有C52=10个，其中第1列与第3列构成的2阶矩阵不是一个基，基矩阵只有9个，即 Chapter 1 线性规划 Linear Programming 当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为基向量(basic vector)，其余列向量称为非基向量; 基向量对应的变量称为基变量(basic variable)， 非基向量对应的变量称为非基变量 ； 在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基变量，x2、x3、x5是非基变量。基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。 1.4 基本概念 Basic Concepts Chapter 1 线性规划 Linear Programming 可行解(feasible solution): 满足式(1.2)及(1.3)的解X=（x1, x2 …, xn)T 称为可行解； 基本可行解(basic feasible solution): 若基本解是可行解 则称为是基本可行解（也称基可行解）。 基本解(basic solution) : 对某一确定的基B，令非基变量 等于零，利用式(1.2)解出基变量，则这组解称为基Ｂ 的 基本解。 最优解(optimal solution): 满足式(1.1)的可行解称为最优 解，即使得目标函数达到最大值的可行解就是最优解； 非可行解(infeasible solution) 无界解 (unbounded solution) 1.4 基本概念 Basic Concepts Chapter 1 线性规划 Linear Programming 显然，只要基本解中的基变量的解满足式(1.3)的非负要求，那么这个基本解就是基本可行解。 在上例中，对Ｂ１来说，x1, x2是基变量，x3 , x4 ，x5是非基变量，令x3=x4=x5=0，则式(1.2)为 因|B1|≠０，由克莱姆法则知，x1、x2有惟一解x1＝2/5, x2=1, 从而基本解为 1.4 基本概念 Basic Concepts Chapter 1 线性规划 Linear Programming 对B2来说，x1, x4,为基变量，令非变量x2, x3, x5为零，由式(1.2)得 ，x4=4，则基本解为 反之，可行解不一定是基本可行解，如 满足式(1.2)~(1.3)，但不是任何基矩阵的基本解。 在 中x10, 不是可行解，因此也不是基本可行解。 Chapter 1 线性规划 Linear Programming 可行基: 基可