最优化例题讲解

例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由于只有σ20，说明表中基可行解不是最优解，所以确定x2为换入非基变量；以x2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。242)24,110(min因此确定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-11231234123123min2..210,248,244,0,1,,4.jxxxstxxxxxxxxxxxj123123412351236max2..210,248,244,0,1,,6.jxxxstxxxxxxxxxxxxxj检验数σ3=30，当前基可行解仍然不是最优解。继续“换基”，确定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，表明已求得最优解：T)0,0,8,5,12,0(*X。去除添加的松弛变量，原问题的最优解为：T)8,5,12,0(*X,最小值为-19例2用大M法求解下列问题：12312312313min3..211,243,21,0,1,,3.jxxxstxxxxxxxxxj解引进松弛变量x4、、剩余变量x5和人工变量x6、x7，解下列问题：1234567123412356137min300()..211243210,1,2,,7jxxxxxMxxstxxxxxxxxxxxxxj用单纯形法计算如下：表1cj→11-300MMCB基bx1x2x3x4x5x6x70x4111-211000Mx6321-40-110Mx71[1]0-20001cj-zj4M1-3M1-M-3+6M0M00由于σ1σ20，说明表中基可行解不是最优解，所以确定x1为换入非基变量；以x1的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。111)11,23,111(min因此确定1为主元素（表1中以防括号[]括起），意味着将以非基变量x1去置换基变量x7，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x1的系数列(1,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σ30，说明表中当前基可行解仍不是最优解，所以确定x2为换入非基变量；以x2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。因此确定1为主元素，意味着将以非基变量x2去置换基变量x6，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将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由于只有σ30，表中当前基可行解仍不是最优解，所以确定x3为换入非基变量；又由于x3的系数列的正分量只有3，所以确定3为主元素，意味着将以非基变量x3去置换基变量x4，对约束方程组的系数增广矩阵实施初等行变换，将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值），求得原问题的最优解：9*1x，1*2x，4*3x，最小目标函数值为-2。例3用两阶段法求解下列问题：121212112max2..2,1,3,,0.xxstxxxxxxx解将原问题化成标准形为：1212312415125min2..213,,0xxstxxxxxxxxxxx第一阶段用单纯形法求解第一阶段的线性规划问题：671236124715127min..213,,0xxstxxxxxxxxxxxxx求解过程见表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/20x13/210-1/2-1/201/21/20x53/2001/21/21-1/2-1/2cj-zj00000021因此，第一阶段求得最优解为12345313(,,,)(,,0,0,)222TTxxxxx，，基变量为x1、x2和x5，不包含人工变量。第二阶段以第一阶段的最终单纯形表为基础，除去人工变量x6、x7及其系数列，恢复目标价值向量为C=（2,-1,0,0,0）T，重新计算检验数，继续迭代，见表2。表2cj→-21000CB基bx1x2x3x4x51x21/201-1/2[1/2]0-2x13/210-1/2-1/200x53/2001/21/21cj-zj-5/200-1/2-3/200x4102-110-2x1211-1000x310-1[1]01cj-zj-403-2000x4201011-2x13100010x310-1101cj-zj-601002因此，求得原问题的最优解为12345(,,,)(3,0,1,2,0)TTxxxxx，，最大目标函数值为6。例4用K—T条件求下列问题221212121212min(,)(1)(2)..200010fxxxxstxxxxxx解该问题的Lagrange函数是2212112213212(,,)(1)(2)2(1)LXxxxxxxxx（-）-由于2111)1(2xxL3122)2(2xxL故该问题的K—T条件是11122311221321232(1)02(2)0(2)000,,0xxxxxx作为K—T点，除满足上述条件，自然还应满足可行性条件0,00102212121xxxxxx为使求解易于进行，从互补松紧条件入手讨论：1°设01x，02x，01由互补松紧条件知023，由K—T条件知0)2(2,0)1(221xx再由可行性条件0121xx得到0,2,121xx，但是显然不满足可行性0221xx，故此解舍弃。2°设01由互补松紧条件知0221xx，再加上可行性条件0121xx知23,2121xx，从而由互补松紧条件知032，将已知值代入易得1=1，0，易知这时K—T条件和可行性条件满足，因而TX)23,21(*为K—T点。易见12(,)fxx和11212,2gxxxx为凸函数，1212,1hxxxx是线性函数，所以由定理3.6知TX)23,21(*为全局最优解。（21220(,)02fxx正定）例5用0.618法求解问题30min()21xfxxx的近似最优解，已知()fx的单峰区间为]3,0[，要求最后区间精度5.0。解3,0ba，146.1)(382.01abax，2131.0)(11xff；1854.1)(618.02abax，6648.3)(22xff；因为21ff，所以向左搜索，则854.1,02xba，2131.0,146.11212ffxx；708.0)(382.01abax，0611.0)(11xff；因为21ff，所以向左搜索，则146.1,02xba，0611.0,7086.01212ffxx；438.0)(382.01abax，208.0)(11xff；因为21ff，所以向右搜索，则146.1,438.02xba，0611.0,7086.02121ffxx；876.0)(618.02abax，0798.0)(22xff；因为21ff，所以向右搜索，则146.1,708.02xba，0798.0,876.02121ffxx；9787.0)(618.02abax，0199.0)(22xff；因为5.0438.0ab，所以算法停止，得到927.02146.1708.02*bax。例6用FR共轭梯度法求解问题2212min2fxxx，要求选取初始点05,5x610。解2142)(xxxf，20100g，201000gd，2200)205(2)105(205105)(fdxf，令05001800)(00dxfdd，则1850，于是959200001dxx；则920940)(11xfg，95201g，81400110ggggTT，81100814000011dgd，2211)9201(8150)9201(81400)(dxf，令0)(11dxfdd，则2091，于是001112dxx；则00)(22xfg，02g，故002*xx为所求。例7用外罚函数法求解：解即于是令得：01.1min22221xtsxxxf222122,(1)min0,1PxMxxMx221222221222(1),10,(1)1,10xxxPxMxxMxx112(1)Pxx2222222,1221,1xxPxMxxx021xPxP1211MxMxMM最优值：当时，，例8用内罚函数