版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
1、单纯形法基本原理及实例演示第1页，共34页，2022年，5月20日，3点18分，星期二线性规划问题标准型的矩阵形式： Max Z = CX （a） s.t. AX=b （ b） X 0 （c） a11 a12 . a1n b1 A= a21 a22 . a2n b = b2 am1 am2 . amn bm一、关于标准型解的若干基本概念第2页，共34页，2022年，5月20日，3点18分，星期二基矩阵 示例:000032020001010 x1x2x4x3001300321=目标函数约束条件行列式0基矩阵X1,x2,x3为基变量,x4为非基变量第3页，共34页，2022年，5月20日，3点18
2、分，星期二因为B为基, 故有 XB +B-1N XN = B-1b， 解得可行解XB=B-1b-B-1NXN，代入目标函数Z， Z = CB B-1b + (CN- CB B-1N ) XN 令非基变量XN = 0 ，则有 XT = (XB , XN) T =（ B-1b , 0) T Z = CB B-1bAX=bZ = CX设 A=（B , N）（B为一个基，即线性无关向量组R(A)=R(B)） XT= (XB , XN) T （XB 为基变量，XN为非基变量） C= (CB , CN) （CB 为基变量系数，CN为非基变量系数）则有： Z= (CB , CN) (XB , XN) T=
3、CB XB+CN XN AX =（ B , N） (XB , XN) T = B XB+ N XN = b1、单纯形法原理：第4页，共34页，2022年，5月20日，3点18分，星期二Z = CB B-1b + (CN- CB B-1N ) XN如果CN- CB B-1N小于0，无论XN取任何大于0值，只会让Z变小，因此我们可以通过CN- CB B-1N来判断Z取得是不是最大值。如果存在一个CN- CB B-1N大于0，则说明Z的值会随着XN增大而增大，说明Z有调整的余地。定理一：若某个基本可行解所对应的检验向量CN- CB B-1N =0第19页，共34页，2022年，5月20日，3点18分
4、，星期二初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000002S1011100300S2021010400 x201001250Zj=CBNjZ=CBB-1b可行解XB=B-1b-B-1NXN=0第20页，共34页，2022年，5月20日，3点18分，星期二初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000002S1011100300S2021010400 x210001001250Zj=CBNjZ=CBB-1b第21页，共34页，2022年，5月20日，3点18分，星期二初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000002S1011
5、100300S2021010400 x210001001250Zj=CBNjZ=CBB-1b第22页，共34页，2022年，5月20日，3点18分，星期二初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000002S1011100300S2021010400 x210001001250Zj=CBNjZ=CBB-1b第23页，共34页，2022年，5月20日，3点18分，星期二初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNjZ=25000第24页，共34页，2022年，
6、5月20日，3点18分，星期二初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=25000第25页，共34页，2022年，5月20日，3点18分，星期二初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=2500050000-100第26页，共34页，2022年，5月20日，3点18分，星期二初始单纯形表迭代次数基变量CBx1X2s
7、1s2S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=2500050000-100第27页，共34页，2022年，5月20日，3点18分，星期二初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=2500050000-100第28页，共34页，2022年，5月20日，3点18分，星期二初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000003S101010-1
8、50S202001-1150 x210001001250Zj=CBNjx150 x150第29页，共34页，2022年，5月20日，3点18分，星期二初始单纯形表迭代次数基变量CBx1x2s1s2S3b比值501000003x1501010-150S202001-1150 x210001001250Zj=CBNj第30页，共34页，2022年，5月20日，3点18分，星期二初始单纯形表迭代次数基变量CBx1x2s1s2S3b比值501000003x1501010-150S202001-1150 x210001001250Zj=CBNj第31页，共34页，2022年，5月20日，3点18分，星期二初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000003x1501010-150S2000-21150 x210001001250Zj=CBNjZ=27500第32页，共34页，2022年，5月20日，3点18分，星期二初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000003x1501010-150S2000-21150 x210001001250Zj=CBNj5010050050Z=27500第33页，共34页，2022年，5月20日，3点18分，星期
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论