线性规划及单纯形法(IV)

《线性规划及单纯形法(IV)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章线性规划及单纯形法1.2线性规划问题解的基本理论一、LP问题的各种解可行解、最优解（最优值）求解LP问题:求出问题的最优解和最优值。1、可行解：满足约束条件和非负条件的决策变量的一组取值。2、最优解:使目标函数达到最优值的可行解。3、最优值：最优解对应目标函数的取值。对于线性规划标准型MaxZ=c1x1+c2x2+…..+cnxns.t.a11x1+a12x2+….+a1nxn=b1a21x1+a22x2+….+a2nxn=b2………………….am1x1+am2x2+….+amnxn=bmx1,x

2、2….xn0其中：bi0(i=1,2,….m)即：s.t.可行解:满足AX=b,X>=0的解X称为线性规划问题的可行解。最优解：使Z=CX达到最大值的可行解称为最优解。二、与线性规划问题解有关的基本概念1.基：设A是约束方程组m×n的系数矩阵，A的秩R(A)＝m，B是A中m×m阶非奇异子式,即

3、B

4、≠0,则称B是LP问题的一个基。基向量、基变量、非基变量、基本解？基向量：矩阵B=（P1，P2….Pm)，其列向量Pj称为对应基B的基向量。基变量和非基变量：与基向量Pj相对应的变量xj就称为基变量，其余

5、的就称为非基变量。不妨设：例1-1将该LP化为标准型12100A=（P1,P2,P3,P4,P5）=4001004001A矩阵包含以下10个3×3的子矩阵：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以外都是基）。对应的基变量是x3x4x

6、5基本解：对于某一特定的基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

7、(10)=(0,0,8,16,12)T（对应B10）结合图形法分析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—0x2

8、

9、

10、

11、

12、

13、

14、

15、

16、123456789x1X(7)(0,3)X(9)(0,0)X(5)(4,0)基本可行解：基本解不一定都是可行的。满足非负限制的基本解，称为基本可行解。可行基：与基本可行解对应的基，称为可行基。可行解、基本解、基本可行解的关系？解的集合：非可行解可行解解的集合：基本解解的集合：可行解基本解基本可行解解的

17、集合：可行解基本解最优解基本可行解作业：找出下列线性规划问题的基本解、基本可行解和可行基Maxz=1500x1+2500x2s.t.3x1+2x2≤652x1+x2≤403x2≤75x1,x2≥0注意，线性规划的基本解、基本可行解和可行基只与线性规划问题标准形式的约束条件有关。32100A=（P1,P2,P3,P4,P5）=2101003001A矩阵包含以下10个3×3的子矩阵：B1=（p1，p2，p3）B2=（p1，p2，p4）B3=（p1，p2，p5）B4=（p1，p3，p4）B5=（p1，p3，p

18、5）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，解线性方程组：3x1+2x2=652x1+x2=403x2+x5=75得到x1=15，x2=10，x5=45，对应的基本解：x（3）=(x1，x2，x3，x4，x5)T=(15，1

19、0，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）是基本可行解;因此，可行基有五个，分别是B2B3B5B7B10。x(3)=(0,32.5,0,7.5,-22.5)T（对