第1章 3 线性规划及单纯形法

第一章第一章 线性规划及单纯形法线性规划及单纯形法1.2 线性规划问题解的基本理论 一、 LP问题的各种解 可行解、最优解（最优值）求解求解 LP问题问题 :求出问题的最优解和最优值。求出问题的最优解和最优值。1、可行解 ： 满足约束条件和非负条件的决策变量的一组取值。2、最优解 : 使目标函数达到最优值的可行解。3、最优值 ：最优解对应目标函数的取值。对于线性规划标准型对于线性规划标准型Max Z=c1x1+c2x2+ cnxns.t. a11x1+a12x2+.+a 1nxn=b1a21x1+a22x2+.+a 2nxn=b2.am1x1+am2x2+.+ amnxn=bmx1,x2. xn 0其中：其中： bi 0(i=1,2,.m)即： s.t.可行解可行解 :满足满足 AX=b, X=0的解的解 X称为线性规划问题的称为线性规划问题的可行解。可行解。最优解：使最优解：使 Z=CX达到最大值的可行解称为最优解。达到最大值的可行解称为最优解。二、与线性规划问题解有关的基本概念1.基 ： 设 A是约束方程组 mn的系数矩阵， A的秩 R(A) m， B是 A中 mm阶非奇异子式 , 即 |B|0, 则称 B是 LP问题的一个基。基向量、基变量、非基变量、基本解？基向量基向量 ：矩阵：矩阵 B=（ P1， P2.P m) ， 其列向其列向量量 Pj称为对应基称为对应基 B的基向量。的基向量。基变量和非基变量基变量和非基变量 ： 与基向量与基向量 Pj 相对应相对应的变量的变量 xj就称为基变量，其余的就称为非就称为基变量，其余的就称为非基变量。基变量。不妨设：例例 1-1 将该将该 LP化为标准型化为标准型1 2 1 0 0A = （ P1 ,P2 ,P3 ,P4 ,P5） = 4 0 0 1 00 4 0 0 1A矩阵包含以下 10个 33 的子矩阵：B1=（ p1 ， p2 ， p3 ） B2=（ p1 ， p2 ， p4）B3=（ p1 ， p2 ， p5） B4=（ p1 ， p3 ， p4） B5=（ p1 ， p3 ， p5） B6=（ p1 ， p4 ， p5） B7=（ p2 ， p3 ， p4） B8=（ p2 ， p3 ， p5） B9=（ p2 ， p4 ， p5） B10=（ p3 ， p4 ， p5） 经计算可知：对应 A系数矩阵可找出 8个基（除 B4 、 B8 以外都是 基）。对应的基变量是 x3 x4 x5基本解 ： 对于某一特定的基 B， 令非基变量等于零，则可由约束方程组 AX b求得一个解，这样的解称为 基本解。思考：基本解与可行解的区别？对应于每一个基，可以得到 8个基本解：x(1) = (4,3,-2,0,0)T （对应 B1）x(2) = (2,3,0,8,0)T （对应 B2）x(3) = (4,2,0,0,4)T （对应 B3）x(5) = (4,0,4,0,12)T （对应 B5）x(6)= (8,0,0,-16,12)T（对应 B6）x(7)= (0,3,2,16,0)T （对应 B7）x(9)= (0,4,0,16,-4)T （对应 B9）x(10) = (0,0,8,16,12)T （对应 B10）n 结合图形法分析X(2)(2,3) X(1)(4,3)X(3)(4,2)X(6)(8,0)X(10)(0,0)6 5 4 3 2 1 0 x2| | | | | | | | |1 2 3 4 5 6 7 8 9 x1X(7)(0,3)X(9)(0,0)X(5)(4,0)基本可行解： 基本解不一定都是可行的。 满足非负限制的基本解，称为 基本可行解 。可行基： 与基本可行解对应的基，称为 可行基。可行解、基本解、基本可行解的关系？解的集合：解的集合：非可行解非可行解 可行解可行解解的集合：解的集合：基本解基本解解的集合：解的集合：可行解可行解 基本解基本解基本可行解基本可行解解的集合：解的集合：可行解可行解 基本解基本解最优解最优解基本可行解基本可行解作业 ：找出下列线性规划问题的基本解、基本可行解和可行基Max z = 1500 x1 + 2500 x2s.t. 3 x1 + 2 x2 652 x1 + x2 403 x2 75x1 , x2 0 注意，线性规划的基本解、基本可行解和可行基只与线性规划问题标准形式的约束条件有关。3 2 1 0 0A = （ P1 ,P2 ,P3 ,P4 ,P5） = 2 1 0 1 00 3 0 0 1A矩阵包含以下 10个 33 的子矩阵：B1=（ p1 ， p2 ， p3 ） B2=（ p1 ， p2 ， p4）B3=（ p1 ， p2 ， p5） B4=（ p1 ， p3 ， p4） B5=（ p1 ， p3 ， p5） B6=（ p1 ， p4 ， p5） B7=（ p2 ， p3 ， p4） B8=（ p2 ， p3 ， p5） B9=（ p2 ， p4 ， p5） B10=（ p3 ， p4 ， p5） 其中 B4= 0，因而 B4不是该线性规划问题的基。其余均为非奇异方阵，因此该问题共有 9个基。对于基 B3=（ p1 ， p2 ， p5），令非基变量 x3 = 0， x4 = 0，即在等式约束中令 x3 = 0， x4 = 0，解线性方程组：3 x1 + 2 x2 = 652 x1 + x2 = 403 x2 + x5 = 75得到 x1 =15， x2 = 10， x5 = 45，对应的基本解：x（ 3） =(x1 ， x2 ， x3 ， x4 ， x5)T=(15， 10， 0， 0， 45)T。由于每一个分量都是大于或等于 0的，因此它是一个基本可行解。于是对应的基 B3是一个可行基。类似可得到x(2) = (5,25,0,5,0)T （对应 B2）x(7) = (20,0,5,0,75)T （对应 B5）x(8) = (0,25,15,15,0)T （对应 B7）x(9) = (0,0,65,40,75)T （对应 B10）是基本可行解 ;因此，可行基有五个，分别是 B2 B3 B5 B7 B10。x(3)= (0,32.5,0,7.5,-22.5)T（对应 B9）x(4)= (65/3,0,0,-10/3,75)T （对应 B6）x(5)= (7.5,25,-7.5,0,0)T （对应 B1）x(6) = (0,40,-15,0,-45)T