1,4线性规划问题的解的概念 求解线性规划问题： maxz=∑c,x 2a,x,=b,(i=l,m） i= x,≥0 (=l,.,n) 就是从满足约束方程组和约束不等式的决策变量取 值中，找出使得目标函数达到最大的值。 2025/4/6
2025/4/6 17 求解线性规划问题： 就是从满足约束方程组和约束不等式的决策变量取 值中，找出使得目标函数达到最大的值。 = = = = = = （ ， ， ） （ ， ， ） x j n a x b i m z c x j i n j i j j n j j j 0 1 1 max 1 1 1.4 线性规划问题的解的概念
可行解：满足约束条件的解称为可行解，可行解的集 合称为可行域。 最优解：使目标函数达到最大值的可行解。 基约束方程组的一个满秩子矩阵称为规划问题的一 个基，基中的每一个列向量称为基向量，与基向量对应 的变量称为基变量，其他变量称为非基变量。 基解：在约束方程组中，令所有非基变量为0，可以 解出基变量的唯一解，这组解与非基变量的0共同构成 基解。 基可行解：满足变量非负的基解称为基可行解 可行基.对应于基可行解的基称为可行基 2025/4/6 18
2025/4/6 18 可行解：满足约束条件的解称为可行解，可行解的集 合称为可行域。 最优解：使目标函数达到最大值的可行解。 基：约束方程组的一个满秩子矩阵称为规划问题的一 个基，基中的每一个列向量称为基向量，与基向量对应 的变量称为基变量，其他变量称为非基变量。 基解：在约束方程组中，令所有非基变量为0，可以 解出基变量的唯一解，这组解与非基变量的0共同构成 基解。 基可行解：满足变量非负的基解称为基可行解 可行基：对应于基可行解的基称为可行基
例：考察下述线性规划问题： maxz=2x1+3x2+0x3+0x4+0x5 2x1+2x2+x3 =12 4X1 +X4 =16 s.t. 5x2 +x5=15 x,≥0，i=1,2,.5 2025/4/6
2025/4/6 19 例：考察下述线性规划问题： = + = + = + + = = + + + + 0, 1,2,.5 5 15 4 16 2 2 12 . . max 2 3 0 0 0 2 5 1 4 1 2 3 1 2 3 4 5 x i x x x x x x x st z x x x x x i
(1) 可行解，如(0,0,12,16,15)或(3,3,0,4,0) 满足约束条件，所以是可行解。 (2) 基 PPP PP 2 2100 系数矩阵A: A- 4 0 0 10 105 001 其中 100 220 B=(P,P4,P)= 010 或B2=(E,P)= 400 001 051 都构成基。而(PPP)不构成基。 2025/4/6 30
2025/4/6 20 （1） 可行解，如 (0,0,12,16,15) 或 (3,3,0,4,0) 满足约束条件，所以是可行解。 （2） 基 系数矩阵A： = 0 5 0 0 1 4 0 0 1 0 2 2 1 0 0 A P1 P2 P3 P4 P5 其中 = = 0 0 1 0 1 0 1 0 0 ( , , ) B1 P3 P4 P5 或 = = 0 5 1 4 0 0 2 2 0 ( , , ) B2 P1 P2 P5 都构成基。而 ( ) P1 P3 P4 不构成基
(3)基向量、基变量 P,P,P是对应于基B,的三个基向量，而 X,x2,x是对应于这三个基向量的基变量。 (4)基解、基可行解、可行基 (0,0,12,1615)是对应于基B,的一个基解、基可行解。 (4,2,O,0,5)是对应于基B的一个基解、基可行解。 B,B2均是可行基。 练习：P14,例4 2025/4/6
2025/4/6 21 （3）基向量、基变量 1 2 5 P, P , P 是对应于基 B2 的三个基向量，而 1 2 5 x , x , x 是对应于这三个基向量的基变量。 （4）基解、基可行解、可行基 (0, 0, 12, 16 15) 是对应于基 B1 的一个基解、基可行解。 (4,2,0,0,5) 是对应于基 B2 的一个基解、基可行解。 1 2 B ,B 均是可行基。 练习：P14，例4