题目
1.4 分别用大M法和两阶段法求解下列线性规划问题,并指出问题的解属于哪一类。-|||-(2) =2(x)_(1)+(x)_(2)+(x)_(3)-|||-s.t. (x)_(1)+2(x)_(2)+2(x)_(3)geqslant 4-|||-(x)_(1)+4(x)_(2)leqslant 20-|||-(x)_(1)+8(x)_(2)+2(x)_(3)leqslant 16-|||-;geqslant 0(i=1,2,3)
题目解答
答案
解析
步骤 1：引入松弛变量和人工变量
为了将问题转化为标准形式，我们引入松弛变量 ${x}_{4}$ 和 ${x}_{5}$，以及人工变量 ${x}_{6}$。原问题变为：
$$
\begin{aligned}
& \max z = 2{x}_{1} + {x}_{2} + {x}_{3} \\
& s.t. \\
& 4{x}_{1} + 2{x}_{2} + 2{x}_{3} - {x}_{4} + {x}_{6} = 4 \\
& 2{x}_{1} + 4{x}_{2} + {x}_{5} = 20 \\
& 4{x}_{1} + 8{x}_{2} + 2{x}_{3} + {x}_{5} = 16 \\
& {x}_{j} \geqslant 0, j = 1, 2, 3, 4, 5, 6
\end{aligned}
$$
步骤 2：使用大M法
大M法的目标函数变为：
$$
\max z = 2{x}_{1} + {x}_{2} + {x}_{3} - M{x}_{6}
$$
其中，$M$ 是一个足够大的正数。我们使用单纯形法求解这个目标函数。
步骤 3：使用两阶段法
第一阶段的目标函数为：
$$
\min w = {x}_{6}
$$
第二阶段的目标函数为：
$$
\max z = 2{x}_{1} + {x}_{2} + {x}_{3}
$$
我们首先求解第一阶段，然后在第二阶段中求解原问题。
步骤 4：求解
通过单纯形法求解，我们得到最优解为：
$$
{x}_{1} = 4, {x}_{2} = 0, {x}_{3} = 0, {x}_{4} = 0, {x}_{5} = 12, {x}_{6} = 0
$$
为了将问题转化为标准形式，我们引入松弛变量 ${x}_{4}$ 和 ${x}_{5}$，以及人工变量 ${x}_{6}$。原问题变为：
$$
\begin{aligned}
& \max z = 2{x}_{1} + {x}_{2} + {x}_{3} \\
& s.t. \\
& 4{x}_{1} + 2{x}_{2} + 2{x}_{3} - {x}_{4} + {x}_{6} = 4 \\
& 2{x}_{1} + 4{x}_{2} + {x}_{5} = 20 \\
& 4{x}_{1} + 8{x}_{2} + 2{x}_{3} + {x}_{5} = 16 \\
& {x}_{j} \geqslant 0, j = 1, 2, 3, 4, 5, 6
\end{aligned}
$$
步骤 2：使用大M法
大M法的目标函数变为：
$$
\max z = 2{x}_{1} + {x}_{2} + {x}_{3} - M{x}_{6}
$$
其中，$M$ 是一个足够大的正数。我们使用单纯形法求解这个目标函数。
步骤 3：使用两阶段法
第一阶段的目标函数为：
$$
\min w = {x}_{6}
$$
第二阶段的目标函数为：
$$
\max z = 2{x}_{1} + {x}_{2} + {x}_{3}
$$
我们首先求解第一阶段，然后在第二阶段中求解原问题。
步骤 4：求解
通过单纯形法求解，我们得到最优解为：
$$
{x}_{1} = 4, {x}_{2} = 0, {x}_{3} = 0, {x}_{4} = 0, {x}_{5} = 12, {x}_{6} = 0
$$