Integer linear optimization: Cutting Planes 3: Unterschied zwischen den Versionen

Version vom 26. Juni 2013, 12:19 Uhr

Example:

Objective Function: ${\displaystyle 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

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 ${\displaystyle {\frac {13}{18}}}$. Also the fraction of the objective function can be chosen if this would be the greatest! After that we construe an artificial restriction by separating the fractions of the coefficients from integer parts in the equation with the greatest fraction.

${\displaystyle 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}

To determine the 1st cutting plane we have to insert the values of the variables in the initial problem in the new restriction.

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

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Leftrightarrow y_A -\tfrac{4}{9}(-2x_1+x_2+9) - \tfrac{1}{18}(-2x_1-8x_2+31)= -\tfrac{13}{18}

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

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Leftrightarrow y_A + x_1 =5

respectively Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.):  x_1 \le 5

Now we have to add the new restriction to the 1st optimal solution. The new pivot element is be chosen by the dual simplex method and so it has to be the smallest negative quotient of the objective function coefficient and the corresponding element in the row of the new restriction. After that the iteration is equal to the 'normal' simplex method.