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

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

ID:40755762

大小:2.10 MB

页数:131页

时间:2019-08-07

线性规划及单纯形法(IV)_第1页
线性规划及单纯形法(IV)_第2页
线性规划及单纯形法(IV)_第3页
线性规划及单纯形法(IV)_第4页
线性规划及单纯形法(IV)_第5页
资源描述:

《线性规划及单纯形法(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(对

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。