線形計画問題を2段階法で解くプロセスを以下に詳述します。この方法はまずフェーズ1で実行可能な初期基本解を見つけ、次にフェーズ2で実際の目的関数を最適化します。

最小化：

$\text{Minimize} \quad Z = 2x_1 + 3x_2 + x_3$

制約条件：

1. $2x_1 + 3x_2 \geq 4$
2. $x_1 + 2x_2 + 3x_3 \geq 10$
3. $x_1, x_2, x_3 \geq 0$

フェーズ1：人工変数を用いた可行解の導出

最初に不等式制約を等式に変換し、人工変数を導入します。

変換された制約条件：

1. $2x_1 + 3x_2 - s_1 = 4$ （人工変数 $s_1$ を導入）
2. $x_1 + 2x_2 + 3x_3 - s_2 = 10$ （人工変数 $s_2$ を導入）

ここで、$s_1$ と $s_2$ はスラック変数です。フェーズ1の目的関数は人工変数の和を最小化することです。

フェーズ1の目的関数：

$\text{Minimize} \quad W = s_1 + s_2$

初期の単体表は以下のようになります。

基底	$x_1$	$x_2$	$x_3$	$s_1$	$s_2$	RHS
$s_1$	2	3	0	1	0	4
$s_2$	1	2	3	0	1	10
$W$	-1	-1	0	0	0	-14

次に、この単体表を用いてフェーズ1の単体法を適用します。

フェーズ1の単体法の適用

最小値が負の中で最も負の値を持つ変数をピボット列として選びます。ここでは $x_1$ です。

ピボット操作：

$\frac{\text{RHS}}{\text{ピボット列の係数}} = \min \left( \frac{4}{2}, \frac{10}{1} \right) = 2$

ここで、行2の係数が最小値を持つため、ピボット行は行2になります。行2の $x_1$ の係数は1です。

新しい基本変数は $x_1$ です。次のように行の操作を行います。

1. 行2を $x_1$ の係数で割ります。
2. 行1と目的関数を新しい行2を用いて修正します。

新しい単体表：

基底	$x_1$	$x_2$	$x_3$	$s_1$	$s_2$	RHS
$s_1$	0	1	-6	1	-2	-6
$x_1$	1	2	3	0	1	10
$W$	0	1	-3	0	1	-4

次に、再び最小の負の値を持つ列を選びます。ここでは $x_3$ です。

ピボット操作：

$\frac{\text{RHS}}{\text{ピボット列の係数}} = \min \left( \frac{-6}{-6}, \frac{10}{3} \right) = 1$

新しい基本変数は $x_3$ です。次のように行の操作を行います。

1. 行1を $x_3$ の係数で割ります。
2. 行2と目的関数を新しい行1を用いて修正します。

新しい単体表：

基底	$x_1$	$x_2$	$x_3$	$s_1$	$s_2$	RHS
$x_3$	0	$\frac{1}{6}$	1	$\frac{1}{6}$	$\frac{-1}{3}$	1
$x_1$	1	$\frac{5}{3}$	0	$\frac{1}{6}$	$\frac{4}{3}$	7
$W$	0	$\frac{1}{2}$	0	$\frac{1}{2}$	$\frac{2}{3}$	-3

フェーズ1が終了したので、フェーズ2に移行します。

フェーズ2：実際の目的関数の最適化

フェーズ2の単体表は以下の通りです。フェーズ1の最後の表から始めます。

基底	$x_1$	$x_2$	$x_3$	$s_1$	$s_2$	RHS
$x_3$	0	$\frac{1}{6}$	1	$\frac{1}{6}$	$\frac{-1}{3}$	1
$x_1$	1	$\frac{5}{3}$	0	$\frac{1}{6}$	$\frac{4}{3}$	7
$Z$	-2	-3	-1	0	0	0

次に、目的関数の係数が負の中で最も負の値を持つ変数をピボット列として選びます。ここでは $x_1$ です。

ピボット操作：

$\frac{\text{RHS}}{\text{ピボット列の係数}} = \min \left( \frac{7}{1}, \frac{1}{0} \right) = 7$

新しい基本変数は $x_1$ です。次のように行の操作を行います。

1. 行2を $x_1$ の係数で割ります。
2. 行1と目的関数を新しい行2を用いて修正します。

新しい単体表：

基底	$x_1$	$x_2$	$x_3$	$s_1$	$s_2$	RHS
$x_3$	0	$\frac{1}{6}$	1