资源描述：
《最优化单纯形法例题讲解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、例1用单纯形法解下列问题：解：将原问题化成标准形：x4与添加的松弛变量x5，x6在约束方程组中其系数列正好构成一个3阶单位阵，它们可以作为初始基变量，初始基可行解为X=（0,0,0,10,8,4）T列出初始单纯形表，见表1。表1cj→-12-1000CB基bx1x2x3x4x5x60x41011-21000x582-140100x64-1[2]-4001cj-zj0-12-1000由于只有σ2>0，说明表中基可行解不是最优解，所以确定x2为换入非基变量；以x2的系数列的正分量对应去除常数列，最小比值所在行对应
2、的基变量作为换出的基变量。因此确定2为主元素（表1中以防括号[]括起），意味着将以非基变量x2去置换基变量x6，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x2的系数列(1,-1,2)T变换成x6的系数列(0,0,1)T，变换之后重新计算检验数。变换结果见表2。表2cj→-12-1000CB基bx1x2x3x4x5x60x483/20010-1/20x5103/20[2]011/22x22-1/21-2001/2cj-zj400300-1检验数σ3=3>0，当前基可行解仍然不是最优解。继续“换基”
3、，确定2为主元素，即以非基变量x3置换基变量x5。变换结果见表3。表3cj→-12-1000CB基bx1x2x3x4x5x60x483/20010-1/2-1x353/40101/21/42x212110011cj-zj19-9/4000-3/2-7/4此时，3个非基变量的检验数都小于0，σ1=-9/4，σ5=-3/2，σ5=-7/4，表明已求得最优解：。去除添加的松弛变量，原问题的最优解为：,最小值为-19例2用大法求解下列问题：解引进松弛变量x4、、剩余变量x5和人工变量x6、x7，解下列问题：用单纯形法
4、计算如下：表1cj→11-300MMCB基bx1x2x3x4x5x6x70x4111-211000Mx6321-40-110Mx71[1]0-20001cj-zj4M1-3M1-M-3+6M0M00由于σ1<σ2<0，说明表中基可行解不是最优解，所以确定x1为换入非基变量；以x1的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。因此确定1为主元素（表1中以防括号[]括起），意味着将以非基变量x1去置换基变量x7，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x1的系数列(1
5、,2,1)T变换成x7的系数列(0,0,1)T，变换之后重新计算检验数。变换结果见表2。表2cj→11-300MMCB基bx1x2x3x4x5x6x70x4100-23100-1Mx610[1]00-11-21x1110-20001cj-zjM+101-M-10M03M-1由于σ2<σ3<0，说明表中当前基可行解仍不是最优解，所以确定x2为换入非基变量；以x2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。因此确定1为主元素，意味着将以非基变量x2去置换基变量x6，采取的做法是对约
6、束方程组的系数增广矩阵实施初等行变换，将x2的系数列(-2,1,0)T变换成x6的系数列(0,1,0)T，变换之后重新计算检验数。变换结果见表3。表3cj→11-300MMCB基bx1x2x3x4x5x6x70x41200[3]1-22-51x210100-11-21x1110-20001cj-zj200-101M-1M+1由于只有σ3<0，表中当前基可行解仍不是最优解，所以确定x3为换入非基变量；又由于x3的系数列的正分量只有3，所以确定3为主元素，意味着将以非基变量x3去置换基变量x4，对约束方程组的系数
7、增广矩阵实施初等行变换，将x3的系数列(3,0,-2)T变换成x4的系数列(1,0,0)T，变换之后重新计算检验数。变换结果见表4。表4cj→11-300MMCB基bx1x2x3x4x5x6x7-3x340011/3-2/32/3-5/31x210100-11-21x191002/3-4/34/3-7/3cj-zj-20001/31/3M-1/3M-2/3至此，无负的检验数且基变量中不含人工变量（即人工变量在基可行解中取0值），求得原问题的最优解：，，，最小目标函数值为-2。例3用两阶段法求解下列问题：解将原
8、问题化成标准形为：第一阶段用单纯形法求解第一阶段的线性规划问题：求解过程见表1。表1cj→0000011CB基bx1x2x3x4x5x6x71x6211-100101x71[1]-10-10010x531000100cj-zj3-20110001x610[2]-1101-10x111-10-10010x52010110-1cj-zj10-21-10120x21/201-1/21/201/2-1/20
