单纯形法解例1

例 1 用单纯形法解下列问题：解：将原问题化成标准形：x4 与添加的松弛变量 x5，x 6 在约束方程组中其系数列正好构成一个 3 阶单位阵，它们可以作为初始基变量，初始基可行解为 X=（0, 0, 0,10, 8, 4） T列出初始单纯形表，见表 1。表 1cj -1 2 -1 0 0 0CB 基 b x1 x2 x3 x4 x5 x60 x4 10 1 1 -2 1 0 00 x5 8 2 -1 4 0 1 00 x6 4 -1 2 -4 0 0 1cj-zj 0 -1 2 -1 0 0 0由于只有 2 0，说明表中基可行解不是最优解，所以确定 x2 为换入非基变量；以 x2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。 24),1(min因此确定 2 为主元素（表 1 中以防括号括起） ，意味着将以非基变量 x2 去置换基变量 x6，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将 x2 的系数列(1, -1, 2)T 变换成 x6 的系数列(0, 0, 1)T，变换之后重新计算检验数。变换结果见表 2。表 2cj -1 2 -1 0 0 0CB 基 b x1 x2 x3 x4 x5 x60 x4 8 3/2 0 0 1 0 -1/20 x5 10 3/2 0 2 0 1 1/22 x2 2 -1/2 1 -2 0 0 1/2cj-zj 4 0 0 3 0 0 -11234123min. 10,8,0,.jxstxx 123451236ma. 10,8,0,.jxst x检验数 3=30，当前基可行解仍然不是最优解。继续 “换基”，确定 2 为主元素，即以非基变量 x3 置换基变量 x5。变换结果见表 3。表 3cj -1 2 -1 0 0 0CB 基 b x1 x2 x3 x4 x5 x60 x4 8 3/2 0 0 1 0 -1/2-1 x3 5 3/4 0 1 0 1/2 1/42 x2 12 1 1 0 0 1 1cj-zj 19 -9/4 0 0 0 -3/2 -7/4此时，3 个非基变量的检验数都小于 0， 1= -9/4， 5= -3/2， 5= -7/4，表明已求得最优解： 。去除添加的松弛变量，原问题的最优解为： ,最T)0,85,120(*X T)85,120(*X小值为-19例 2 用大 法求解下列问题：M12313min.1,4,0,.jxstx解 引进松弛变量 x4、 、剩余变量 x5 和人工变量 x6、x 7，解下列问题：1234567137min(). 130,2,j Mxstx用单纯形法计算如下：表 1cj 1 1 -3 0 0 M MCB 基 b x1 x2 x3 x4 x5 x6 x70 x4 11 1 -2 1 1 0 0 0M x6 3 2 1 -4 0 -1 1 0M x7 1 1 0 -2 0 0 0 1cj-zj 4M 1-3M 1-M -3+6M 0 M 0 0由于 12 0，说明表中基可行解不是最优解，所以确定 x1 为换入非基变量；以 x1 的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。 1),231(min因此确定 1 为主元素（表 1 中以防括号括起） ，意味着将以非基变量 x1 去置换基变量 x7，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将 x1 的系数列(1, 2, 1)T 变换成 x7 的系数列(0, 0, 1)T，变换之后重新计算检验数。变换结果见表 2。表 2cj 1 1 -3 0 0 M MCB 基 b x1 x2 x3 x4 x5 x6 x70 x4 10 0 -2 3 1 0 0 -1M x6 1 0 1 0 0 -1 1 -21 x1 1 1 0 -2 0 0 0 1cj-zj M+1 0 1-M -1 0 M 0 3M-1由于 23 0，说明表中当前基可行解仍不是最优解，所以确定 x2 为换入非基变量；以 x2 的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。因此确定 1 为主元素，意味着将以非基变量 x2 去置换基变量 x6，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将 x2 的系数列(-2, 1, 0)T 变换成 x7 的系数列(0, 1, 0)T，变换之后重新计算检验数。变换结果见表 3。表 3cj 1 1 -3 0 0 M MCB 基 b x1 x2 x3 x4 x5 x6 x70 x4 12 0 0 3 1 -2 2 -51 x2 1 0 1 0 0 -1 1 -21 x1 1 1 0 -2 0 0 0 1cj-zj 2 0 0 -1 0 1 M-1 M+1由于只有 3 0，表中当前基可行解仍不是最优解，所以确定 x3 为换入非基变量；又由于 x3 的系数列的正分量只有 3，所以确定 3 为主元素，意味着将以非基变量 x3 去置换基变量 x4，对约束方程组的系数增广矩阵实施初等行变换，将 x3 的系数列(3, 0, -2)T 变换成 x4 的系数列(1, 0, 0)T，变换之后重新计算检验数。变换结果见表 4。表 4cj 1 1 -3 0 0 M MCB 基 b x1 x2 x3 x4 x5 x6 x7-3 x3 4 0 0 1 1/3 -2/3 2/3 -5/31 x2 1 0 1 0 0 -1 1 -21 x1 9 1 0 0 2/3 -4/3 4/3 -7/3cj-zj -2 0 0 0 1/3 1/3 M-1/3 M-2/3至此，无负的检验数且基变量中不含人工变量（即人工变量在基可行解中取 0 值） ，求得原问题的最优解： ， ， ，最小目标函数值为-2 。9*1x1*2x4*3例 3 用两阶段法求解下列问题：121212max.,3,0.stx解 将原问题化成标准形为： 1231245125max. 213,0stxx第一阶段 用单纯形法求解第一阶段的线性规划问题：671236471527min. 213,0stxxx求解过程见表 1。表 1cj 0 0 0 0 0 1 1CB 基 b x1 x2 x3 x4 x5 x6 x71 x6 2 1 1 -1 0 0 1 01 x7 1 1 -1 0 -1 0 0 10 x5 3 1 0 0 0 1 0 0cj-zj 3 -2 0 1 1 0 0 01 x6 1 0 2 -1 1 0 1 -10 x1 1 1 -1 0 -1 0 0 10 x5 2 0 1 0 1 1 0 -1cj-zj 1 0 -2 1 -1 0 1 20 x2 1/2 0 1 -1/2 1/2 0 1/2 -1/20 x1 3/2 1 0 -1/2 -1/2 0 1/2 1/20 x5 3/2 0 0 1/2 1/2 1 -1/2 -1/2cj-zj 0 0 0 0 0 0 2 1因此，第一阶段求得最优解为 ，基变量为 x1、x 2 和1234531(,)(,0,)2TTxx，x5，不包含人工变量。第二阶段 以第一阶段的最终单纯形表为基础，除去人工变量 x6、x 7 及其系数列，恢复目标价值向量为 C =（2, -1, 0, 0, 0） T，重新计算检验数，继续迭代，见表 2。表 2cj 2 -1 0 0 0CB 基 b x1 x2 x3 x4 x5-1 x2 1/2 0 1 -1/2 1/2 02 x1 3/2 1 0 -1/2 -1/2 00 x5 3/2 0 0 1/2 1/2 1cj-zj 5/2 0 0 1/2 3/2 00 x4 1 0 2 -1 1 02 x1 2 1 0 -1 0 00 x3 1 0 -1 1 0 1cj-zj 2 0 -3 2 0 00 x4 2 0 1 0 1 12 x1 3 1 -1 0 0 10 x3 1 0 -1 1 0 1cj-zj 6 0 -1 0 0 -2因此，求得原问题的最优解为 ，最大目标函12345(,)(3,2,)TTxx，数值为 6。例 4 写出下列问题的 Lagrange 函数及该问题的 K-T 条件2212131212min(,)()(). 0,(),fxxstghxx解该问题的 Lagrange 函数是+）（)()(),( 2121 XL )(2x)3由于 211)(xL32故该问题的 KT 条件是 0,)2(013211321xx例 5 用 0.618 法求解问题 的近似最优解，已知 的单谷区间为0min()1xfx()fx，要求最后区间精度 。3,0 5.解 ， ， ；,ba 146.)(382.1abax 213.0)(xf， ；856026482因为 ，所以向左搜索，则21f， ；854.1,02xba 13.0,4.2fx， ；78)(380aba 061.)(xf因为 ，所以向左搜索，则21f， ；146.,02xba 061.,76.2fx， ；438.)(380aba 208.)(xf因为 ，所以向右搜索，则21f， ；146.,438.02xba 061.,76.21fx， ；87.)(02aba 0798.)(2xf因为 ，所以向右搜索，则21f， ；146.,708.2xba 09.,6.fx， ；78)(802aba 019.)(2xf因为 ，所以算法停止，得到5.43.。97.0216*x例 6 用 FR 共轭梯度法求解问题 ，要求选取初始点 21minfxx05,x。10解 ， ， ，214)(xf 0g201gd，0 )5()15()( fdf令 ，则 ，于是 ；0518)(0dxf 185952001dx则 ， ， ，9204)(1xfg95201g8140gT，81041dgd，22