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

Aus Operations-Research-Wiki
Wechseln zu: Navigation, Suche
[unmarkierte Version][unmarkierte Version]
(→‎Example:)
(→‎Example:)
Zeile 37: Zeile 37:
 
:<math>\Leftrightarrow x_1 + (0 + \tfrac{4}{9})y_1 + (0+ \tfrac{1}{18})y_2 = 5 + \tfrac{13}{18} </math>
 
:<math>\Leftrightarrow x_1 + (0 + \tfrac{4}{9})y_1 + (0+ \tfrac{1}{18})y_2 = 5 + \tfrac{13}{18} </math>
 
:<math>\Leftrightarrow \tfrac{4}{9}y_1 + \tfrac{1}{18}y_2 = \tfrac{13}{18} + (5-x_1-0y_1-0y_2) </math>
 
:<math>\Leftrightarrow \tfrac{4}{9}y_1 + \tfrac{1}{18}y_2 = \tfrac{13}{18} + (5-x_1-0y_1-0y_2) </math>
−
For the term which contains only integer coefficients a new slack variable will be introduced and a new restriction is built.
+
For the term which contains only integer coefficients a new slack variable will be introduced and a '''new restriction''' is built.
−
:<math>y_A - \frac{4}{9}y_1 - \frac{1}{18}y_2 = -\frac{13}{18}</math>
+
<math> y_A - \frac{4}{9}y_1 - \frac{1}{18}y_2 = -\frac{13}{18}</math>
 +
:::To determine the '''1st cutting plane''' we have to insert the values of the variables in the initial problem in the new restriction.
 +
:::<math>y_A - \tfrac{4}{9}y_1 - \tfrac{1}{18}y_2 = -\tfrac{13}{18}</math>
 +
:::<math>\Leftrightarrow y_A -\tfrac{4}{9}(-2x_1+x_2+9) - \tfrac{1}{18}(-2x_1-8x_2+31)= -\tfrac{13}{18}</math>
 +
:::<math>\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}</math><br>
 +
:::<math> \Leftrightarrow y_A + x_1 =5 </math> respectively <math> x_1 \le 5</math>

Version vom 26. Juni 2013, 11:35 Uhr

Example:

Objective Function:
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
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
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -1
Optimal Solution
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{1}{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 . After that we construe an artificial restriction by separating the fractions of the coefficients from integer parts in the equation with the greatest fraction.

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
Von „https://www.wiwi.uni-kl.de/bisor-orwiki/index.php?title=Integer_linear_optimization:_Cutting_Planes_3&oldid=4326“