运筹学/单纯形法

我们可以使用上一节中概述的图形方法轻松地求解两个变量 $(x_{2},s_{2})$ 线性规划模型，但对于三变量问题，例如，当我们的公司生产三种产品时，我们必须做出决策，我们该怎么做？四变量或五变量问题又该如何？这就是单纯形法发挥作用的地方。它是一种迭代方法，通过反复使用，可以为任何 n 变量线性规划模型提供解决方案。

线性规划模型的标准形式

让我们定义一个线性规划模型，如果它满足以下两个条件，则为标准形式

除非负约束外，所有约束都是具有非负右边的方程。

所有变量都非负。

例如，

最大化

z=5x_{1}+4x_{2}

受制于，

6x_{1}+4x_{2}+s_{1}=24

,

x_{1}+2x_{2}+s_{2}=6

,

x_{2}-x_{1}+s_{3}=1

,

x_{2}+s_{4}=2

,

x_{1},x_{2},s_{1},s_{2},s_{3},s_{4}\geq 0

是一个标准形式的线性规划模型。请注意，通常的 $\leq$ 符号已等效地用 $s_{n}$ 变量（s 代表 slack）和 $=$ 符号替换。

我们如何将给定模型转换为标准模型，同时保留其含义？这可以通过以下方式完成

如果存在类型为 $6x_{1}+4x_{2}\leq 24$ 的约束，则等式右侧通常表示资源的某种限制（例如，可用原材料的数量），等式左侧表示该资源的使用量（即，实际使用的原材料数量），因此它们的差表示资源的松弛或未使用的数量。因此，为了转换为等式，我们必须在等式左侧添加一个表示松弛量的变量。该变量被称为松弛变量，显然也是非负的。如果用 $s_{1}$ 表示它，则约束将转换为等式 $6x_{1}+4x_{2}+s_{1}=24$ 。在类型为 $6x_{1}+4x_{2}\geq 24$ 的约束的情况下，也做类似的事情。这里等式左侧比等式右侧存在剩余或额外数量，因此必须减去一个非负的剩余变量，比如 $s_{2}$ ，才能得到等式 $6x_{1}+4x_{2}-s_{2}=24$ 。

如果给定变量 $x_{i}$ 是非正的，那么它的负数 $y_{i}=-x_{i}$ 显然是非负的，可以代入问题中。真正的困难在于当变量可以取任何符号时。这种情况被称为无限制变量。解决这个问题的方法是使用替换 $x_{i}=x_{i}^{-}-x_{i}^{+}$ ，其中 $x_{i}^{-},x_{i}^{+}$ 都是非负的。直观地说，如果变量 $x_{i}$ 是正的，那么 $x_{i}^{-}$ 是正的，而 $x_{i}^{+}$ 是零；如果变量 $x_{i}$ 是负的，那么 $x_{i}^{-}$ 是零，而 $x_{i}^{+}$ 是正的。如果 $x_{i}$ 是零，那么显然 $x_{i}^{-},x_{i}^{+}$ 都为零。

需要注意的是，原始线性规划模型和标准模型的目标函数是相同的。

线性规划的代数解法

现在让我们尝试用代数方法分析线性规划模型。标准线性规划模型的解将是原始模型的解（因为松弛变量和剩余变量一旦移除，就会使方程恢复到原来的不平衡），并且出于类似的推理，原始模型的解也将对应于标准模型的解。由于目标函数对两个模型都是相同的，因此标准模型的最优解也将是原始模型的最优解。因此，我们只需要关注标准模型。

那么哪些解是最佳解的候选者呢？它们是等式约束的解。我们只需要找出这些解，然后检查哪一个解在代入目标函数时能得到最优值。现在通常在线性规划模型中，约束的数量，比如 m，少于变量的数量，比如 n，因此约束方程组有无限多个解。我们不可能检查所有无限个解。但是，由于一个数学结果，我们的工作简化了。这个结果是，如果在 n 个变量中，将 n-m 个变量设为零，然后如果可以解出约束方程组，那么这个解将对应于 n 维空间中的一个角点。这样的解被称为基本解（初始解）。如果它除了是基本解之外，还恰好满足原始问题的可行性，那么它被称为基本可行解（通常缩写为 BFS）。由于最优解是在角点上得到的（正如我们在图形上观察到的），因此我们只需要检查所有基本可行解（其数量最多为 ${n \choose m}$ ，反映了从总共 n 个变量中选择 n-m 个变量为零的方式数量），然后决定哪一个解能使目标函数的值最大化。

让我们考虑一个例子

考虑以下线性规划模型

最大化 z = $2x_{1}+3x_{2}$

受制于，

$2x_{1}+x_{2}\leq 4$ ,

$x_{1}+2x_{2}\leq 5$ ,

$x_{1},x_{2}\geq 0$ .

我们首先将其转换为标准形式

最大化 z = $2x_{1}+3x_{2}$

受制于，

$2x_{1}+x_{2}+s_{1}=4$ ,

$x_{1}+2x_{2}+s_{2}=5$ ,

$x_{1},x_{2},s_{1},s_{2}\geq 0$ .

约束系统有 m=2 个约束和 n=4 个变量。因此我们需要将 4-2=2 个变量设置为零以获得基本解。例如，将 $x_{1}=0$ 和 $x_{2}=0$ 我们得到一个解 $s_{1}=4$ 和 $s_{2}=5$ 。这显然是可行的，因此是基本可行解。设置为零的变量，即 $x_{1},x_{2}$ 被称为非基变量，而 $s_{1},s_{2}$ 被称为基变量。这些解（基解和非基解）在目标函数中代入后得到的目标值（即在目标函数中代入解后得到的值）为零。

下表总结了该问题的所有基本解

非基变量	基变量	基本解	可行	目标值
$(x_{1},x_{2})$	$(s_{1},s_{2})$	(4,5)	是	0
$(x_{1},s_{1})$	$(x_{2},s_{2})$	(4,-3)	否	-
$(x_{1},s_{2})$	$(x_{2},s_{1})$	(2.5,1.5)	是	7.5
$(x_{2},s_{1})$	$(x_{1},s_{2})$	(2,3)	是	4
$(x_{2},s_{2})$	$(x_{1},s_{1})$	(5,-6)	否	-
$(s_{1},s_{2})$	$(x_{1},x_{2})$	(1,2)	是	8

请注意，我们没有费心计算不可行解的目标值。最优解是目标值最高的解，即 $x_{1}=1,x_{2}=2$ 。因此，我们已经通过代数方法解决了线性规划模型。

这种解决线性规划模型的方法适用于任何数量的变量，但在约束和变量数量较多时，实施起来非常困难。例如，对于 m = 10 和 n = 20，需要解决 ${20 \choose 10}=184756$ 组方程，这显然是一项艰巨的任务。使用单纯形法，你只需要求解其中几组方程，专注于那些能提高目标值的方程。

单纯形法

简单来说，该方法是这样工作的。你从标准形式线性规划的基本可行解开始（通常是所有松弛变量都等于相应的右手边，而其他所有变量都为零），然后用当前非基本变量替换一个基本变量，以获得新的基本可行解（因为 n-m 个变量仍然为零）。这样做是为了确保新的基本可行解是可行的，并且其目标值至少与先前的基本可行解相同。重复此过程，直到很明显当前基本可行解无法再获得更好的目标值。通过这种方式，可以找到最优解。

很明显，有一个因素对该方法至关重要：哪个变量应该替换哪个。被替换的变量称为“离开变量”，而替换它的变量称为“进入变量”。单纯形法的设计就是为了在选择这两个变量的过程中实现两件事。首先，新的目标值是改进（或至少等于）当前目标值的；其次，新的解是可行的。

现在让我们通过一个例子来解释该方法。考虑我们之前提到的化工厂问题，其标准形式如下：

最大化 z = $5x_{1}+4x_{2}$

受制于，

$6x_{1}+4x_{2}+s_{1}=24$ ,

$x_{1}+2x_{2}+s_{2}=6$ ,

$x_{2}-x_{1}+s_{3}=1$ ,

$x_{2}+s_{4}=2$ ,

$x_{1},x_{2},s_{1},s_{2},s_{3},s_{4}\geq 0$ .

现在，通过将所有 $x_{i}$ 设置为零，可以立即获得一个基本可行解。（很明显，这样得到的解对于原始问题来说是可行的，因为右手边都是非负数，这正是我们的解。）如果考虑我们的目标函数 z = $5x_{1}+4x_{2}$ ，那么很明显，增加 $x_{1}$ 或 $x_{2}$ 将会提高我们的目标值。（请注意，目前这两个变量都是零，是不可行的）。 $x_{1}$ 增加一个单位将使目标值增加 5 倍，而 $x_{2}$ 增加一个单位将使目标值增加 4 倍。很明显，我们应该选择在下次迭代中将 $x_{1}$ 作为进入变量。

在单纯形法的表格形式中，目标函数通常表示为 $z-5x_{1}-4x_{2}=0$ 。此外，该表格还包含约束系统以及获得的基本可行解。通常只写系数，正如处理线性系统时通常的做法那样。

基本变量	z	$x_{1}$	$x_{2}$	$s_{1}$	$s_{2}$	$s_{3}$	$s_{4}$	BFS
z	1	-5	-4	0	0	0	0	0
$s_{1}$	0	6	4	1	0	0	0	24
$s_{2}$	0	1	2	0	1	0	0	6
$s_{3}$	0	-1	1	0	0	1	0	1
$s_{4}$	0	0	1	0	0	0	1	2

现在进入下一轮迭代，我们需要确定进入变量和离开变量。进入变量是 $x_{1}$ ，正如我们所讨论的。事实上，由于我们对目标函数的重新排列，单纯形表中 z 行中最小的负值将始终是下一轮迭代的进入变量。这被称为 *最优性条件*。离开变量呢？我们必须考虑下一基本解是可行的。因此，选择离开变量时必须考虑到这一点。

为了确定离开变量，我们应用有时被称为 *可行性条件* 的方法。即：我们计算解坐标（分别为 24、6、1 和 2）与进入变量 $x_{1}$ （分别为 6、1、-1 和 0）的约束系数的商。得到以下比率：24/6 = 4，6/1 = 6，1/-1 = -1 和 2/0 = 未定义。忽略负比率和未定义比率，我们现在继续选择其他两个比率中最小的一个，即 4，它是通过将 24（ $s_{1}$ 的值）除以 6 得出的。由于最小值涉及除以 $s_{1}$ 的当前值，我们取离开变量为 $s_{1}$ 。

这个过程背后的理由是什么？是这样的。最小比率实际上代表了约束在 $x_{1}$ 轴上的截距。要了解这一点，请查看以下图形

由于目前所有 $x_{i}$ 都为 0，我们正在考虑与原点相对应的 BFS。现在，在下一轮迭代中，根据单纯形法，我们应该获得一个新的 BFS，即移动到图形上的一个新的角点。我们可以通过使一个变量成为进入变量来一次诱导一个变量值的增加，并且由于 $x_{1}$ 是我们的进入变量，我们的计划是增加 $x_{1}$ 的值。从图中我们可以看到， $x_{1}$ 的值必须增加到点 (4,0) 的 4，这是与 $x_{1}$ 轴的最小非负截距。超出该点的增加是不可行的。此外，在 (4,0) 处，松弛变量 $s_{1}$ 取值为零，因为第一个约束在该点满足为等式，因此 $s_{1}$ 成为离开变量。

现在的问题是确定新的解决方案。尽管在这个阶段可以应用任何求解线性方程组的方法，但通常应用 *高斯-约旦消元法*。它基于线性代数中的一个结果，即对系统 [A|b] 进行初等行变换到 [H|c] 不会改变系统的解。根据它，表中对应于基本变量的列被赋予单位矩阵的形状。（熟悉线性代数的读者会认识到这意味着由基本变量列组成的矩阵被转换为行最简阶梯形。）然后可以从最右边的解列中直接读出解（因为 n-m 个变量被置为零，而其余变量，包括 z，在每个约束中都有系数 1）。由于 z 也是一个变量，所以它的行被视为线性方程组中包含的约束之一。

进入变量列称为 *主元列*，离开变量行称为 *主元行*。主元列和离开变量列的交点称为 *主元元素*。在我们的示例中，第二行（ $s_{1}$ ）是主元行，第二列（ $x_{1}$ ）是主元列。

生成新的基本解所需的计算如下

用进入变量替换“基本”列中的离开变量。
新的主元行 = 当前主元行 ÷ 主元元素

对于其他行，包括 z 行

新行 = 当前行 - （它的主元列系数）×（新的主元行）

在我们的例子中，计算如下进行

用 $x_{1}$ 替换“基本”列中的 $s_{1}$
新的主元 $x_{1}$ 行 = 当前 $s_{1}$ 行 ÷ 6 = ${\begin{pmatrix}0&1&{\frac {2}{3}}&{\frac {1}{6}}&0&0&0&4\end{pmatrix}}$
新的 z 行 = 当前 z 行 - (-5)×新的 $x_{1}$ 行 = ${\begin{pmatrix}1&0&{\frac {-2}{3}}&{\frac {5}{6}}&0&0&0&20\end{pmatrix}}$
新的 $s_{2}$ 行 = 当前 $s_{2}$ 行 - (1)×新的 $x_{1}$ 行 = ${\begin{pmatrix}0&0&{\frac {4}{3}}&{\frac {-1}{6}}&1&0&0&2\end{pmatrix}}$
新 $s_{3}$ 行 = 当前 $s_{3}$ 行 - (-1)×新 $x_{1}$ 行 = ${\begin{pmatrix}0&0&{\frac {5}{3}}&{\frac {1}{6}}&0&1&0&5\end{pmatrix}}$
新 $s_{4}$ 行 = 当前 $s_{4}$ 行 - (0)×新 $x_{1}$ 行 = ${\begin{pmatrix}0&0&1&0&0&0&1&2\end{pmatrix}}$

因此，我们的新表是

基本变量	z	$x_{1}$	$x_{2}$	$s_{1}$	$s_{2}$	$s_{3}$	$s_{4}$	BFS
z	1	0	${\frac {-2}{3}}$	${\frac {5}{6}}$	0	0	0	20
$x_{1}$	0	1	${\frac {2}{3}}$	${\frac {1}{6}}$	0	0	0	4
$s_{2}$	0	0	${\frac {4}{3}}$	${\frac {-1}{6}}$	1	0	0	2
$s_{3}$	0	0	${\frac {5}{3}}$	${\frac {1}{6}}$	0	1	0	5
$s_{4}$	0	0	1	0	0	0	1	2

现在，最优性条件表明 $x_{2}$ 是进入变量。可行性条件得出比率：4/(2/3) = 6, 2/(4/3) = 1.5, 5/(5/3) = 3 和 2/1 = 2，其中最小值为 1.5，它是通过将 $s_{2}$ 行（即基本变量 $s_{2}$ 系数为 1 的行）的系数相除得到的。所以 $s_{2}$ 成为离开变量。再次应用高斯-约旦消元法得到以下表格

基本变量	z	$x_{1}$	$x_{2}$	$s_{1}$	$s_{2}$	$s_{3}$	$s_{4}$	BFS
z	1	0	0	${\frac {3}{4}}$	${\frac {1}{2}}$	0	0	21
$x_{1}$	0	1	0	${\frac {1}{4}}$	${\frac {-1}{2}}$	0	0	3
$x_{2}$	0	0	1	${\frac {-1}{8}}$	${\frac {3}{4}}$	0	0	${\frac {3}{2}}$
$s_{3}$	0	0	0	${\frac {3}{8}}$	${\frac {-5}{4}}$	1	0	${\frac {5}{2}}$
$s_{4}$	0	0	0	${\frac {1}{8}}$	${\frac {-3}{4}}$	0	1	${\frac {1}{2}}$

根据最优性条件，与非基变量相关的 z 行系数 $s_{1}$ 和 $s_{2}$ 均为负数。因此，最后一个表是最优的。最优解可以读为 $x_{1}=3,x_{2}={\frac {3}{2}},s_{3}={\frac {5}{2}}$ 以及 $s_{4}={\frac {1}{2}}$ ，最优值为 z = 21。显然，变量 $s_{1}$ 和 $s_{2}$ 为零。我们最初只涉及 $x_{1}$ 和 $x_{2}$ 的问题，显然也有相同的解（只需忽略松弛变量）。

我们已经处理了最大化问题。如果是最小化情况，因为 min z = max (-z)（如果 z 是线性函数，它就是），所以我们可以将问题转换为最大化问题或颠倒最优性条件。我们可以选择 z 行中系数最正的变量作为进入变量，而不是选择系数最负的变量。其余步骤相同。

使用单纯形法在线解决问题的工具

练习问题

1. 一家从事打印机组装和分发的公司关注两种类型——激光打印机和喷墨打印机。每台激光打印机的组装需要 2 小时，而每台喷墨打印机的组装需要 1 小时，员工每天可以提供 40 人小时的组装时间。此外，仓库空间必须可用于打印机的组装和分发，每台激光打印机 1 平方米，每台喷墨打印机 3 平方米；该公司每天有 45 平方米的仓库空间可用于组装好的打印机。激光打印机的每台利润为 30 欧元，喷墨打印机的每台利润为 25 欧元，但公司运营的市场每天最多能吸收 12 台激光打印机。（喷墨打印机市场没有这种限制）。将此问题表述为线性规划问题，并使用单纯形法确定公司每天应该组装和分发每种打印机的数量，以使每日利润最大化。

最大化 $z=30x_{1}+25x_{2}$

受制于，

$2x_{1}+x_{2}\leq 40$ ,

$x_{1}+3x_{2}\leq 45$ ,

$x_{1}\leq 12,x_{1},x_{2}\geq 0$

使用 PHPSimplex 求解（参见链接以了解逐步求解过程）：最优解为 $z$ = 635，其中 $x_{1}$ = 12 且 $x_{2}$ = 11

人工初始解

在前面的问题中，我们有一个方便的初始基本可行解来应用单纯形方法，该解包含松弛变量。然而，如果问题包含剩余变量，则通过将所有 $x_{i}$ 设置为零获得的解将是基本的，但不可行（为什么？）。在这种情况下，与其随意寻找初始基本可行解，不如使用称为人工变量的变量。它们在第一次迭代中扮演松弛变量的角色，并且是问题外部的，在以后的迭代中被丢弃（通过被驱动为零）。我们将讨论一种称为两阶段法的方法，它通常用于处理人工变量问题。

让我们考虑以下问题

最小化 z = $4x_{1}+x_{2}$

受制于，

$3x_{1}+x_{2}=3$ ,

$4x_{1}+3x_{2}\geq 6$ ,

$x_{1}+2x_{2}\leq 4$ ,

$x_{1},x_{2}\geq 0$ .

现在，将问题转换为标准形式后，我们得到

最小化 z = $4x_{1}+x_{2}$

受制于，

$3x_{1}+x_{2}=3$ ,

$4x_{1}+3x_{2}-Sx_{3}=6$ ,

$x_{1}+2x_{2}+sx_{6}=4$ ,

$x_{1},x_{2},Sx_{3},sx_{6}\geq 0$ .

现在，第一个和第二个约束没有与它们关联的任何松弛变量。这意味着我们没有一个方便的初始基本可行解可用。因此，我们必须在问题中引入人工变量 $Rx_{4},Rx_{5}$ 来获得初始 BFS。

$3x_{1}+x_{2}+Rx_{4}=3$ ,

$4x_{1}+3x_{2}-Sx_{3}+Rx_{5}=6$ ,

$x_{1}+2x_{2}+sx_{6}=4$ .

两阶段法到底是什么？顾名思义，它包含两个阶段：在第一阶段，我们从一个初始的基本可行解（通过将松弛变量和人工变量设置为等式右边的值，并将其他变量设置为零来获得）开始，并努力消除人工变量。为此，我们必须最小化人工变量的总和。所以我们将目标函数更改为最小化 $z=Rx_{4}+Rx_{5}$ 。因此，我们的问题变成了

最小化 $z=Rx_{4}+Rx_{5}$

受制于，

$3x_{1}+x_{2}+Rx_{4}=3$ ,

$4x_{1}+3x_{2}-Sx_{3}+Rx_{5}=6$ ,

$x_{1}+2x_{2}+sx_{6}=4$ .

$x_{1},x_{2},Sx_{3},sx_{6},Rx_{4},Rx_{5}\geq 0$ .

当然，我们的初始 BFS 是通过将所有原始变量和剩余变量设置为零来获得的。但是，此时出现了一个问题。单纯形法中的 z 行由 $z-Rx_{4}-Rx_{5}=0$ 给出，因此整个系统以矩阵形式表示为

${\begin{pmatrix}1&0&0&0&-1&-1&0\\0&3&1&0&1&0&0\\0&4&3&-1&0&1&0\\0&1&2&0&0&0&1\end{pmatrix}}{\begin{pmatrix}z\\x_{1}\\x_{2}\\Sx_{3}\\Rx_{4}\\Rx_{5}\\sx_{6}\end{pmatrix}}={\begin{pmatrix}0\\3\\6\\4\end{pmatrix}}$

显然，如果我们将剩余变量和原始变量设为零，那么该系统的解将不是我们期望的右侧，因为第一行中 $Rx_{4}$ 和 $Rx_{5}$ 的系数不为零。为了更准确地说明，我们将上述系统写成如下形式： ${\Bigg \{}z{\begin{pmatrix}1\\0\\0\\0\end{pmatrix}}+x_{1}{\begin{pmatrix}0\\3\\4\\1\end{pmatrix}}+x_{2}{\begin{pmatrix}0\\1\\3\\2\end{pmatrix}}+Sx_{3}{\begin{pmatrix}0\\0\\-1\\0\end{pmatrix}}+Rx_{4}{\begin{pmatrix}-1\\1\\0\\0\end{pmatrix}}+Rx_{5}{\begin{pmatrix}-1\\0\\1\\0\end{pmatrix}}+sx_{6}{\begin{pmatrix}0\\0\\0\\1\end{pmatrix}}{\Bigg \}}{\begin{pmatrix}z\\x_{1}\\x_{2}\\Sx_{3}\\Rx_{4}\\Rx_{5}\\sx_{6}\end{pmatrix}}={\begin{pmatrix}0\\3\\6\\4\end{pmatrix}}$ .

现在我们将变量 $x_{1},x_{2},Sx_{3}$ 设为零，我们的解变为

${\Bigg \{}z{\begin{pmatrix}1\\0\\0\\0\end{pmatrix}}+Rx_{4}{\begin{pmatrix}-1\\1\\0\\0\end{pmatrix}}+Rx_{5}{\begin{pmatrix}-1\\0\\1\\0\end{pmatrix}}+sx_{6}{\begin{pmatrix}0\\0\\0\\1\end{pmatrix}}{\Bigg \}}{\begin{pmatrix}z\\Rx_{4}\\Rx_{5}\\sx_{6}\end{pmatrix}}={\begin{pmatrix}0\\3\\6\\4\end{pmatrix}}$ .

或者写成如下形式

${\begin{pmatrix}1&-1&-1&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix}}{\begin{pmatrix}z\\Rx_{4}\\Rx_{5}\\sx_{6}\end{pmatrix}}={\begin{pmatrix}0\\3\\6\\4\end{pmatrix}}$

现在这还没有处于简化行阶梯形式，因此右侧不直接提供基本可行解。在单纯形表中，最后一列应该包含解。因此，在我们开始单纯形法之前，第一行需要进行一些修改，以便系统得到简化行阶梯形式。明显的必要初等变换是

新 z 行 = 旧 z 行（即 $z-Rx_{4}-Rx_{5}=0$ ) + (1× $Rx_{4}$ 行 + 1× $Rx_{5}$ )

现在第一个方程变为 $z+7x_{1}+4x_{2}-Sx_{3}=9$ ，并且在将必要的变量置零后，我们发现右侧提供了一个方便的初始 BFS。

基本变量	$x_{1}$	$x_{2}$	$Sx_{3}$	$Rx_{4}$	$Rx_{5}$	$sx_{6}$	BFS
z	7	4	-1	0	0	0	9
$Rx_{4}$	3	1	0	1	0	0	3
$Rx_{5}$	4	3	-1	0	1	0	6
$sx_{6}$	1	2	0	0	0	1	4

请注意，我们没有费心在上面的表格中写出 z 列。这是因为初等行变换的性质，z 列将始终是 $(1,0,\cdots 0)^{T}$ 的形式，因此该列可以在每次迭代中假定。

单纯形法现在被用来得到解 $z=0,x_{1}=0.6,x_{2}=1.2,sx_{6}=1$ 。将获得的最终表格

基本变量	$x_{1}$	$x_{2}$	$Sx_{3}$	$Rx_{4}$	$Rx_{5}$	$sx_{6}$	BFS
z	0	0	0	-1	-1	0	0
$x_{1}$	1	0	${\frac {1}{5}}$	${\frac {3}{5}}$	${\frac {-1}{5}}$	0	${\frac {3}{5}}$
$x_{2}$	0	1	${\frac {-3}{5}}$	${\frac {-4}{5}}$	${\frac {3}{5}}$	0	${\frac {6}{5}}$
$sx_{6}$	0	0	1	1	-1	1	1