第三章线性规划的解法习题解答090426y

矩阵中凑出一个单位矩阵来。人工变量在目标函数中的系数为“—M”，M是充分大的正数。通过用单纯形法解这个新的线性规划问题(不妨称为大M问题)来求解原来的线性规划，这种方法叫大M法。

2．两阶段法。这种方法解决与大M法相同的问题，即约束方程组系数矩阵中没有现成的单位矩阵时，可用两阶段法求解线性规划问题，但该方法将分成两个阶段计算：第一阶段是以所有人工变量的和为目标函数，求极小值，约束条件是原来问题的约束条件添加了松弛变量(如果需要添加的话)以及人工变量后的约束条件。第二个阶段则是利用第一个阶段的结果，或者说明原来题目无可行解，或者利用第一个阶段求得的原来问题的标准形式的一个可行基，接下来继续计算原问题。

3．检验准则(运用于有人工变量的问题，仅就大M法叙述，两阶段法有同样结论)

1)当所有检验数均大于或等于零而且单纯形表的基变量没有取值非零的人工变量时，表明已得到原问题的最优解；

2)当所有检验数均大于或等于零，但基变量中还有不为零的人工变量时，表明原问题无可行解；

3)如果所解的大M问题有无界解(即有可行解但无最优解)，则当人工变量全为零时，表明原来问题也有无界解，而当人工变量不全为零时，表明原问题无可行解。

例3-6 用大M法求解下列线性规划问题

maxZ?3x1?x2?x1?x2?2 ?s.t?2x1?x2?1?x,x?0?12解: 添加松弛变量和人工变量，使系数矩阵中能够直接找到秩等于约束条件个数的单位矩阵。添加松弛变量x3，剩余变量x4和人工变量x5，将约束条件化为标准形式；在最大化目标函数中，人工变量的系数是-M，在最小化目标函数中，人工变量的系数为M，M是任意大的正数。化为标准型为：

maxZ?3x1?x2?0x3?0x4?Mx5?x1?x2?x3?2?s.t?2x1?x2?x4?x5?1?x,x,x,x,x?0?12345表3-6 Cj

建立初始单纯形表，计算检验数，如表3-6所示。

3 1 0 0 -M ?i 25

CB 0 XB x3 x5 b 2 1 -M x1 x2 x3 x4 x5 2/1 1/2 1 [2] -3-2M 1 1 -1-M 1 0 0 0 -1 M 0 1 0 -M zj -C j 确定进基变量，比较检验数的大小时。可直接看M的系数，也可用减法来计算，如?(3?2M)?[?(1?M)]??2?M?0，所以?3?2M小。用单纯形法计算，最终单纯形表如表3-7所示

表3-7 Cj CB 0 XB x3 x1 3 1 x2 0 x3 0 x4 -M x5 ?i b 3 2 6 x1 0 1 0 1 1 2 2 1 3 1 0 0 -1 0 M 3 zj -C j 表中的基变量已不含人工变量，且检验数全部非负，因此，此时的基可行解X?(x1,x2)T?(2,0)T就是最优解，对应的最优值为maxZ?3x1?x2?6。

要点：此题是用人工变量法(大M法)求解有唯一最优解的线性规划问题。做此类题时一定要分清哪些变量是松驰变量，哪些变量是人工变量；另外，人工变量的系数是-M还是M也要弄清楚。

例3-7 用两阶段法求解下列线性规划问题

maxZ?3x1?x2?x1?x2?2 ?s.t?2x1?x2?1?x,x?0?12 解: 添加松弛变量x3，剩余变量x4和人工变量x5。将约束条件化为标准形式；第一阶段的目标函数仅含人工变量，且对人工变量求最小值，据此建立第一阶段的数学模型：

min??x5?x1?x2?x3?2 ?s.t?2x1?x2?x4?x5?1?x,x,x,x,x?0?12345用单纯形法求解，得到第一阶段问题的计算表，如表3-8所示。

表3-8 Cj

0 0 26

0 0 1 ?i CB 0 XB x3 x5 b 2 1 1 3/2 1/2 0 x1 x2 x3 x4 x5 2/1 1/2 1 [2] 2 0 1 0 1 1 1 1/2 1/2 0 1 0 0 1 0 0 0 -1 -1 1/2 -1/2 0 0 1 0 -1/2 1/2 -1 1 0 zj -C j x3 x1 0 zj -C j 辅助问题是要求最小化，而表中的检验数全非正，故第一阶段的最优解为X?(x5)T?(0)T，目标函数值为min??x5?0，说明原问题存在基可行解，因此，

再进行第二阶段的计算。将第一阶段计算得到的最终表，除去人工变量，以原问题的目标函数maxZ?3x1?x2，作为第二阶段的目标函数，并将此目标函数的系数替换第一阶段目标函数系数行的系数和基变量列的系数，作为第二阶段计算的初始表，重新计算检验数，进行迭代运算，如表3-9所示。

表3-9 Cj CB 0 XB x3 x1 3 1 x2 0 x3 0 x4 ?i 3 b 3/2 1/2 3/2 3 2 6 x1 0 1 0 0 1 0 1/2 1/2 1/2 1 1 2 1 0 0 2 1 3 [1/2] -1/2 -3/2 1 0 0 3 0 zj -C j x4 x1 3 zj -C j 因为原问题是求最大化，表中检验数全为非负。所以最优解为X?(2,0)T，最有值为maxZ?3x1?x2?6。

从例3-6和例3-7可见，大M法和两阶段法所求结果相同。

要点：此题是用两阶段法求解唯一最优解的线性规划问题。解此类题的关键在于：第一，第一阶段的目标函数一定是求极小化，且目标函数中的变量只含有人工变量；第二，第一阶段的目标函数的最优值只有为0时，原问题才有可行解；第三，在进行第二阶段计算时，一定要除去人工变量，并用原问题的目标函数的系数进行计算。

题型V 求解线性规划的应用问题

例3-8 一个投资者打算100元进行投资，有两种投资方案可供选择。第一种投资保证每1元投资一年后可赚5角钱。第二种投资保证每1元投资两年后可

27

赚1元。但对第二种投资，投资时必须是两年的倍数才行。为了使投资者在第三年年底赚到的钱最多，他应该怎样投资?请将该问题表示成线性规划问题求解。 解：设xi1和xi2是第一种方案和第二种方案在第i年年初的投资额，Z是总利润，于是这个问题的目标函数是：

maxZ?2x22?1.5x31

约束条件有：

x11?x12?100x21?x22?1.5x11x31?1.5x21?2x12xij?0(i?1,2,3j?1,2)经整理得一般形式的线性规划模型为：

maxZ?2x22?1.5x31?x11?x12?100??1.5x?x?x?0?112122 s..t??2x?1.5x?x?0122131??xij?0(i?1,2,3;j?1,2)?

用单纯形表法得出的该问题的初始单纯形表如3-10。

表3-10 Cj CB 0 XB x6 x22 0 0 x12 0 x21 2 x22 1.5 x31 0 x6 ?i 3 b 100 0 0 0 x11 1 -1.5 0 -3 1 0 -2 -3 0 1 -1.5 -0.25 0 1 0 0 0 0 1 0 1 0 0 0 2 1.5 x31 zj -C j 该问题的最终单纯形表如表3-11。

表3-11 Cj CB 0 XB x11 x21 0 0 x12 0 x21 2 x22 1.5 x31 0 x6 ?i b 100 150 225 337.5 x11 1 0 0 0 1 0 0.25 3/8 0 1 1 0 0 1 1.5 0.25 0 0 1 0 1 0 2.25 27/8 0 1.5 x31 zj -C j 所以，该投资者应该只采取方案1就能获得最大利润为337.5元。

28