《管理运筹学》课件02-单纯形法.ppt
《《管理运筹学》课件02-单纯形法.ppt》由会员分享,可在线阅读,更多相关《《管理运筹学》课件02-单纯形法.ppt(34页珍藏版)》请在三一办公上搜索。
1、第2章 单纯形法,1,第二章 单纯形法,Simplex Method,SM,第2章 单纯形法,2,2.1 单纯形法的基本思想2.2 单纯形法的计算过程2.3 人工变量法2.4 单纯形法补遗,第2章 单纯形法,第2章 单纯形法,3,2.1 单纯形法的基本思想,单纯形法有三种形式:方程组形式 表格形式 矩阵形式2.1.1 方程组形式的单纯形法思路:由一个基本可行解转化为另一个基本可行解。,z-3x1-5x2=0,例1 范例,等价改写为,目标方程,第2章 单纯形法,4,2.1 单纯形法的基本思想,0 00 1 00 0 1,典式,条 典,当前基:m阶排列阵 目标方程中:一切基变量 的系数 j=0,最
2、优性检验:,一切j 0?,初始基本可行解 X0=(0,0,8,12,36)T z0=0,排列阵:每行每列有且仅有一个元素为1,其余元素全为0 的方阵。,1=-3 0,2=-5 0,当前解 X0 非优;,+0 x3+0 x4+0 x5,须由X0 转化为另一个基本可行解 X1。,满足条典的方程组称为典式(方程组)。,思路:让X0 中的一个非基变量进基,去替换原来的一个基变量(离基)。,第2章 单纯形法,5,2.1 单纯形法的基本思想,x1仍为非基变量,其值为0。,x2 12/2 x2 36/4,离基(最小比值规则):x2 min,12/2,36/4=6 x2=min,12/2,36/4=6,x4,
3、x4为离基变量,进基(最小检验数规则):在负检验数中选择最小的进基。min jj0=k xk 进基 min-3,-5=-5=2 x2 进基,0,0,0,=,=12,X1=,(,12,0,6,8,0,)T,由 有,第2章 单纯形法,6,2.1 单纯形法的基本思想,主方程,0,主列,主元,z-3x1-5 x2=0,x1+x3=8,2 x2+x4=12,3x1+4 x2+x5=36,(),-69,比值,min,以主列中正值元素为分母,同行右端常数为分子,求比值;,按最小比值规则确定主方程和主元素,以及离基变量。,第2章 单纯形法,7,X0=(0,0,8,12,36)T z0=0,(),x1+x3=8
4、,3x1-2x4+x5=12,得,X1=,z0=30,称为单纯形法的一次迭代。,(,12,0,6,8,0,)T,换基运算方程组的初等变换目的是把主列变为单位向量:主元变为1,其余变为0。,用换基运算将X0 转化为另一个基本可行解 X1。,0010,2.1 单纯形法的基本思想,第2章 单纯形法,8,2.1 单纯形法的基本思想,(),(),x1+x3=8,3 x1-2x4+x5=12,得,X*=(4,6,4,0,0)T,z*=42,8-4,min,比值,10,第2章 单纯形法,9,2.1 单纯形法的基本思想,2.1.2 单纯形法的几何意义,z=0,脊线,(4,6,4,0,0)T,(0,0,8,12
5、,36)T,(0,6,8,0,12)T,z 法向,或棱线,第2章 单纯形法,10,单纯形表范例:基于典式标准形,cj,基,解,x1 x2 x3 x4 x5,3 5 0 0 0,比 值,1 0 1 0 0,x3x4 x5,81236,0 2 0 1 0,00 0,3 4 0 0 1,0 0 0,0,-3,-5,检验行,CB,b,3,5,2.2 单纯形法的计算过程,检验行计算公式,j=1,2,n,第2章 单纯形法,11,2.2 单纯形法的计算过程,初始单纯形表的一般形式,第2章 单纯形法,12,2.2 单纯形法的计算过程,2.2.2 单纯形法的计算步骤1 把LP问题化为标准形。2 在系数阵中找出或
6、构造一个m阶排列阵作为初始 可行基,建立初始单纯形表。3 最优性检验:若所有检验数j 0,就得到一个 最优基本解,停止计算;否则转4。4 解无界判断:在所有j 0中,只要有一个r 0 所对应的系数列向量 ar 0,即一切 air 0,i=1,2,m 则该LP问题解无界,停止计算;否则转5。,预备步骤,迭代步骤,第2章 单纯形法,13,2.2 单纯形法的计算过程,5 确定主元 先按最小检验数规则 min jj 0=k 确定进基变量 xk 和主列ak;再按最小比值规则,确定主元al k,同时也就确定第l 行的基变量 xr 离基。6 以al k为主元对当前表格进行一次换基运算,得到 一个新单纯形表,
7、返3。,迭代步骤,第2章 单纯形法,14,2.2 单纯形法的计算过程,2.2.3 单纯形法计算之例范例 第0次迭代,-6 9,min,2,第2章 单纯形法,15,2.2 单纯形法的计算过程,第一次迭代,x3x2 x5,05 0,1/2,8 1 0 1 0 0,-2,5/2,4,min,1,6,0,0,0,12,3,0,0,1,30,-3,0,0,0,8,-,第2章 单纯形法,16,2.2 单纯形法的计算过程,cj,基,解,x1 x2 x3 x4 x5,3 5 0 0 0,比 值,1 0 1 0 0,x3x2 x5,8612,0 1 0 1/2 0,05 0,3 0 0-2 1,30-3 0 0
8、 5/2 0,x3x2 x1,05 3,6 0 1 0 1/2 0,4 0 0 1 2/3-1/3,4 1 0 0-2/3 1/3,42 0 0 0 1/2 1,8-4,min,3,X*=(4,6,4,0,0)T,z*=42,第二次迭代,第2章 单纯形法,17,2.2 单纯形法的计算过程,cj,基,解,x1 x2 x3 x4,3 2 0 0,-2 1 1 0,x3x4,23,1-3 0 1,00,0-3-2 0 0,1,3 1-3 0 1,x3x1,03,8 0-5 1 2,9 0-11 0 3,解无界,例2 求解下述LP问题,第2章 单纯形法,18,2.3 人工变量法,考虑标准型(M):分别
9、给每个约束方程硬性加入一个非负变量 a11x1+a12x2+a1nxn+xn+1=b1(0)a12x1+a22x2+a2nxn+xn+2=b2(0)am1x1+am2x2+amnxn+xn+m=bm(0),n个,xn+1,xn+2,xn+m 称为人工变量。初始基本可行解:(人造基本解)X0=(0,0,0,b1,b2,bm)T,(2.1),第2章 单纯形法,19,基本思想:人造解 X0 不是原LP问题的基本可行解。但若能通过单纯形法的迭代步骤,将虚拟 的人工变量都替换出去,都变为非基变量(即 人工变量xn+1=xn+2=xn+m=0),则X0的 前n个分量就构成原LP问题的一个基本可行解。反之,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 管理运筹学 管理 运筹学 课件 02 单纯

链接地址:https://www.31ppt.com/p-5903519.html