单纯形法例题讲解_第1页
单纯形法例题讲解_第2页
单纯形法例题讲解_第3页
单纯形法例题讲解_第4页
单纯形法例题讲解_第5页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

基可行解单纯形法是针对标准形式的线性规划问题进行演算的，任何线性规划问题都可以化为标准形式。min （1）cxfs.t （2）bA（3）0x其中 TmmnmnTnn bbaaaaAxxcc ).,(, .,),.(),.( 2121 2221 112121 假设 ，并设系数矩阵 A 的秩为 m，即mn设约束方程（2）中没有多余的方程，用表示 A 的第 列，于是（2 可写成jpj（4）bpxmkjj1矩阵 A 的任意一个 m 阶非奇异子方阵为LP 的一个基（或基阵） ，若（5）),.(21jmjjppB是一个基，则对应变量 ，jmjj xx,.,21称关于 B 的基变量，其余变量成为关于 B的非基变量，若令非基变量都取零值，则（4）变为（6）bpxmkjkj1由于此方程组的系数矩阵 B 是满秩方阵，故知（6）有唯一解，记为于是按分量Tjnjj xx),.,( 0()0(2)0(1 ),.,.21(0),.3(21)0( mjjkjk jjnx所构成的向量 是约束方程组 的一个)( bAx解，称此 为 LP 的对应于基 B 的基解)0(x（或基本解） ，也可称为方程组 的一x个基解，如果 为一基解，且满足)0(x即它的所有分量都非负，则称此0)(x是 LP 的一个基可行解，基可行解对应)(的基称为可行基。设对应基阵 ，即),.(21mppB为基变量 ， 是非mxx,.21 nxx,.,21基变量，记),.,( ),.,( ),.,(212121 nmm Tnn TmB pppNxxxx从而 A=（B,N）,相应地分划 ,约),(NBcc束方程（2）可以写成 bxNBnB),(即 由此解得bxBxN（7）NB xB11这是用非基变量表达基变量的公式在（7）中令 而知 0Nx TmB xxbB ),.,( 0()0(2)(101求解线性规划问题min 421xxfts. 3512243xx5),1(0 jxj已知初始可行基 0B于是可列出 对应的单纯形表 ,如表所0B)(0BT示从表可以看出，检验数中仅有 ，故取2 为进基变量，由于最小比值2x 120min2iib1xx3x4x5xf4 0 1 -1 0 01x2 1 -2 1 0 042 0 1 -2 1 05x5 0 1 1 0 1在第 32 行取得，故取第 2 行对应的基变量为离基变量，于是元素 是上表的枢元4x 12b为求出新
人人文库> 全部分类> 应用文书 > 事务文书

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论