最优化单纯形法例题讲解.doc

例1 用单纯形法解下列问题：解：将原问题化成标准形：x4与添加的松弛变量x5，x6在约束方程组中其系数列正好构成一个3阶单位阵，它们可以作为初始基变量，初始基可行解为X=（0, 0, 0,10, 8, 4）T列出初始单纯形表，见表1。表1cj-12-1000CB基bx1x2x3x4x5x60x41011-21000x582-140100x64-12-4001cj-zj0-12-1000由于只有2 0，说明表中基可行解不是最优解，所以确定x2为换入非基变量；以x2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。因此确定2为主元素（表1中以防括号括起），意味着将以非基变量x2去置换基变量x6，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x2的系数列(1, -1, 2)T变换成x6的系数列(0, 0, 1)T，变换之后重新计算检验数。变换结果见表2。表2cj-12-1000CB基bx1x2x3x4x5x60x483/20010-1/20x5103/202011/22x22-1/21-2001/2cj-zj400300-1检验数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，表明已求得最优解：。去除添加的松弛变量，原问题的最优解为：,最小值为-19例2 用大法求解下列问题：解 引进松弛变量x4、剩余变量x5和人工变量x6、x7，解下列问题： 用单纯形法计算如下： 表1cj11-300MMCB基bx1x2x3x4x5x6x70x4111-211000Mx6321-40-110Mx7110-20001cj-zj4M1-3M1-M-3+6M0M00由于12 0，说明表中基可行解不是最优解，所以确定x1为换入非基变量；以x1的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。因此确定1为主元素（表1中以防括号括起），意味着将以非基变量x1去置换基变量x7，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x1的系数列(1, 2, 1)T变换成x7的系数列(0, 0, 1)T，变换之后重新计算检验数。变换结果见表2。 表2cj11-300MMCB基bx1x2x3x4x5x6x70x4100-23100-1Mx610100-11-21x1110-20001cj-zjM+101-M-10M03M-1由于23 0，说明表中当前基可行解仍不是最优解，所以确定x2为换入非基变量；以x2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。因此确定1为主元素，意味着将以非基变量x2去置换基变量x6，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x2的系数列(-2, 1, 0)T变换成x6的系数列(0, 1, 0)T，变换之后重新计算检验数。变换结果见表3。 表3cj11-300MMCB基bx1x2x3x4x5x6x70x4120031-22-51x210100-11-21x1110-20001cj-zj200-101M-1M+1由于只有3 0，表中当前基可行解仍不是最优解，所以确定x3为换入非基变量；又由于x3的系数列的正分量只有3，所以确定3为主元素，意味着将以非基变量x3去置换基变量x4，对约束方程组的系数增广矩阵实施初等行变换，将x3的系数列(3, 0, -2)T变换成x4的系数列(1, 0, 0)T，变换之后重新计算检验数。变换结果见表4。表4cj11-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 用两阶段法求解下列问题： 解 将原问题化成标准形为：第一阶段 用单纯形法求解第一阶段的线性规划问题： 求解过程见表1。表1cj0000011CB基bx1x2x3x4x5x6x71x6211-100101x711-10-10010x531000100cj-zj3-20110001x6102-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因此，第一阶段求得最优解为，基变量为x1、x2和x5，不包含人工变量。第二阶段 以第一阶段的最终单纯形表为基础，除去人工变量x6、x7及其系数列，恢复目标价值向量为C =（2, -1, 0, 0, 0）T，重新计算检验数，继续迭代，见表2。表2cj2-1000CB基bx1x2x3x4x5-1x21/201-1/21/202x13/210-1/2-1/200x53/2001/21/21cj-zj5/2001/23/200x4102-1102x1210-1000x310-1101cj-zj20-32000x42010112x131-10010x310-1101cj-zj60-100-2因此，求得原问题的最优解为，最大目标函数值为6。例4 用KT条件求下列问题解 该问题的Lagrange函数是由于故该问题的KT条件是作为KT点，除满足上述条件，自然还应满足可行性条件为使求解易于进行，从互补松紧条件入手讨论：1 设，由互补松紧条件知，由KT条件知再由可行性条件得到，但是显然不满足可行性，故此解舍弃。2 设由互补松紧条件知，再加上可行性条件知，从而由互补松紧条件知，将已知值代入易得=1，易知这时KT条件和可行性条件满足，因而为KT点。易见为凸函数，且为线性函数，由定理3.1.12知为全局最优解。（正定，半正定）例5 用0.618法求解问题的近似最优解，已知的单峰区间为，要求最后区间精度。解 ， ，； ，； 因为 ，所以向左搜索，则， ； ，； 因为 ，所以向左搜索，则， ； ，； 因为 ，所以向右搜索，则，； ，； 因为 ，所以向右搜索，则，； ，； 因为，所以算法停止，得到。例6 用FR共轭梯度法求解问题，要求选取初始点 。解 ， ， 令，则，于是； 则， ， 令，则，于是