线性规划的基本概念课件.ppt

* Chapter 1 线性规划 Linear Programming 1.3 线性规划的标准型 Standard form of LP Chapter 1 线性规划 Linear Programming 在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。 1.3 线性规划的标准型 Standard form of LP 线性规划问题的标准型为: 1．目标函数求最大值（或求最小值） 2．约束条件都为等式方程 3．变量xj非负 4．常数bi非负 Chapter 1 线性规划 Linear Programming max(或min)Z=c1x1+c2x2+…+cnxn 1.3 线性规划的标准型 Standard form of LP 注：本教材默认标准型中目标函数是 max Chapter 1 线性规划 Linear Programming 或写成下列形式： 或用矩阵形式 1.3 线性规划的标准型 Standard form of LP Chapter 1 线性规划 Linear Programming 通常X记为： , 称Ａ为约束方程的系数矩阵，m是约束方程的个数，n是决策变量的个数，一般情况m≤n，且r(Ａ)＝m。 其中: 1.3 线性规划的标准型 Standard form of LP Chapter 1 线性规划 Linear Programming 一般形式线性规划模型的标准化准则: （前提 bi ≥0 ） 5. xj≤0 令xj =－ xj , xj ≥0 Chapter 1 线性规划 Linear Programming 【例1】将下列线性规划化为标准型 【分析】(１)因为x3无符号要求 ，即x3 可取正值也可取负值，标准型中要求变量非负，所以令 1.3 线性规划的标准型 Standard form of LP Chapter 1 线性规划 Linear Programming (3)第二个约束条件是“≥”号，在“≥”号左端减去剩余 变量(surplus variable) x5 ，x5≥0，也称松驰变量； 1.3 线性规划的标准型 Standard form of LP (2) 第一个约束条件是“≤”号， 在“≤”号左端加入松驰变量 (slack variable) x4，x4≥0, 化为等式； (4)第三个约束条件是“≤”号且常数项为负数，因此在“≤”左边加入松驰变量x6，x6≥0，同时两边乘以－1。 (5)目标函数是最小值，为了化为求最大值，令Z′=－Z, 得到 max Z′=－Z，即当Z达到最小值时Z′达到最大值。 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 Con