单纯形法例题

运筹学演讲之单纯形法Content2132maxxxz2,10124164822121jxxxxxj求其基本可行解和最大目标值5432100032maxxxxxxz5,,2,10124164825241321jxxxxxxxxjS.T化为标准型：cj23000CBXBB﹣1bx1x2x3x4x5θ0x38121008/2=40x41640010-0x5120[4]00112/4=3检验数23000根据标准型将有关数字填入表中，得到初始单纯形表计算非基变量的检验数σ1=c1−=2−(0×1+0×4+0×0)=2σ2=c2−=3−(0×2+0×0+0×4)=3填入表1-3的底行对应非基变量处。(2)因检验数都大于零,因此继续进行计算；(3)max(σ1,σ2)=max(2,3)=3，对应的变量x2进基，计算θ根据公式求得θ的值，可知θ最小值为3则它所在行对应的x5出基，x2所在列和x5所在行的交叉处[4]称为主元素。(4)以[4]为主元素进行迭代运算，即初等行变换，使P2变换为(0,0,1)T,在XB列中将x2替换x5,于是得到新表cj23000CBXBB﹣1bx1x2x3x4x5θ0x32[1]010-1/220x4164001043x2301001/4-检验数2000-3/4因为还存在检验数0，继续进行迭代重复之前步骤因为还存在检验数0，继续进行迭代cj23000CBX1B﹣1bx1x2x3x4x5θ2x321010-1/20x4800-41[2]43x2301001/412检验数00-201/4(6)表1-6最后一行的所有检验数都已为负或零。这表示目标函数值已不可能再增大，于是得到最优解cj23000CBXBB﹣1bx1x2x3X4x5θ2x141011/400x5400-21/213x22011/2-1/80检验数00-3/2-1/80X*=X=(4,2,0,0,4)T目标函数的最大值z*=14Thankyou!