单纯形法基本原理及实例演示[教师助手].ppt
《单纯形法基本原理及实例演示[教师助手].ppt》由会员分享,可在线阅读,更多相关《单纯形法基本原理及实例演示[教师助手].ppt(35页珍藏版)》请在三一文库上搜索。
1、单纯形法求解动态演示,在求解LP问题时,有人给出了图解法,但对多维变量时,却无能为力,于是 美国数学家GBDantgig(丹捷格)发明了一种“单纯形法”的代数算法,尤其是方便于计算机运算。这是运筹学史上最辉煌的阶段。,1,学校课堂,线性规划问题标准型的矩阵形式: 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,学校课堂,基矩阵 示例:,0,0,0,0,3,2,0,2,0,0,0,1,0,1,0,x1,x2,x4,x3
2、,0,0,1,3,0,0,3,2,1,=,目标函数,约束条件,行列式0 基矩阵,X1,x2,x3为基变量,x4为非基变量,3,学校课堂,因为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-1b,设 A=(B , N)(B为一个基,即线性无关向量组R(A)=R(B)) XT= (XB , XN) T (XB 为基变量,XN为非基变量) C= (CB , C
3、N) (CB 为基变量系数,CN为非基变量系数) 则有: Z= (CB , CN) (XB , XN) T= CB XB+CN XN AX =( B , N) (XB , XN) T = B XB+ N XN = b,1、单纯形法原理:,4,学校课堂,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-
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 教师助手 单纯 基本原理 实例 演示 教师 助手
链接地址:https://www.31doc.com/p-11169077.html