14线性规划问题的解的概念求解线性规划问题：max z=cjxjj=1[Za, =b. ( =. m) j=1[x,≥0(j=l,., n)就是从满足约束方程组和约束不等式的决策变量取值中，找出使得目标函数达到最大的值。2025/4/517
2025/4/5 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/518
2025/4/5 18 可行解：满足约束条件的解称为可行解，可行解的集 合称为可行域。 最优解：使目标函数达到最大值的可行解。 基：约束方程组的一个满秩子矩阵称为规划问题的一 个基，基中的每一个列向量称为基向量，与基向量对应 的变量称为基变量，其他变量称为非基变量。 基解：在约束方程组中，令所有非基变量为0，可以 解出基变量的唯一解，这组解与非基变量的0共同构成 基解。 基可行解：满足变量非负的基解称为基可行解 可行基：对应于基可行解的基称为可行基
例：考察下述线性规划问题：max z =2x, +3x2 +0x3 +0x4 +0xs= 122x, +2x2 +X3=164x+×4s.t.5x2+ xs = 15x, ≥0,i=1,2,..52025/4/5
2025/4/5 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)满足约束条件，所以是可行解。PsPPP2Ps(2）基[22100系数矩阵A：40001A=00051 其中00220或 B, =(P,P2,P)=001400B, =(P, P4,P)=00015P都构成基。而（(PP)不构成基。2025/4/520
2025/4/5 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,P2,Ps是对应于基B。的三个基向量，而是对应于这三个基向量的基变量。X2,XsXi,（4）基解、基可行解、可行基(0，0，12，16 15）是对应于基B,的一个基解、基可行解。（4,2,0,0,5）是对应于基B,的一个基解、基可行解B,Bz均是可行基。练习：P14，例42025/4/52
2025/4/5 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