Integer linear optimization: Cutting Planes 3

Example:

Objective Function: $max\;G=2x_{1}+5x_{2}$
Restrictions:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 2x_1 - x_2 \le 9
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 2x_1 - 8x_2 \le 31
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1, x_2 \ge 0, integer

Initial tableau

	$x_{1}$	$x_{2}$
$G$	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -2	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -5	$0$
$y_{1}$	$2$	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -1	$9$
$y_{2}$	$2$	$8$	$31$

Optimal Solution

	$y_{1}$	$y_{2}$
$G$	${\frac {1}{3}}$	${\frac {2}{3}}$	${\frac {71}{3}}=23{\frac {2}{3}}$
$x_{1}$	${\frac {4}{9}}$	${\frac {1}{18}}$	${\frac {103}{18}}=5{\frac {13}{18}}$
$x_{2}$	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{1}{9}	${\frac {1}{9}}$	${\frac {22}{9}}=2{\frac {4}{9}}$

Two Simplex iterations lead us from the initial tableau to the optimal solution depicted above. We must consider that this solution is optimal but not integer. Now we have to determine the greatest fraction of the RHS. Here this is given by ${\frac {13}{18}}$. After that we construe an artificial restriction by separating the fractions of the coefficients from integer parts in the equation with the greatest fraction.

$x_{1}+{\tfrac {4}{9}}y_{1}+{\tfrac {1}{18}}y_{2}=5{\tfrac {13}{18}}$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Leftrightarrow x_1 + (0 + \tfrac{4}{9})y_1 + (0+ \tfrac{1}{18})y_2 = 5 + \tfrac{13}{18}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Leftrightarrow \tfrac{4}{9}y_1 + \tfrac{1}{18}y_2 = \tfrac{13}{18} + (5-x_1-0y_1-0y_2)

For the term which contains only integer coefficients a new slack variable will be introduced and a new restriction is built.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_A - \frac{4}{9}y_1 - \frac{1}{18}y_2 = -\frac{13}{18}