Integer linear optimization: Cutting Planes 3: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
Cboehm (Diskussion | Beiträge) (→Example:) |
Cboehm (Diskussion | Beiträge) (→Example:) |
||
| Zeile 29: | Zeile 29: | ||
| <math>x_1</math> || <math>\frac{4}{9}</math> || <math>\frac{1}{18}</math> || style="background:#bafedc" | <math>\frac{103}{18}=5\frac{13}{18} </math> | | <math>x_1</math> || <math>\frac{4}{9}</math> || <math>\frac{1}{18}</math> || style="background:#bafedc" | <math>\frac{103}{18}=5\frac{13}{18} </math> | ||
|- style="height: 40px;" | |- style="height: 40px;" | ||
| − | | <math>x_2</math> || <math>-\frac{1}{9}</math> || <math>\frac{1}{9}</math> || <math> | + | | <math>x_2</math> || <math>-\frac{1}{9}</math> || <math>\frac{1}{9}</math> || <math>\frac{22}{9}=2\frac{4}{9}</math> |
|} | |} | ||
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. | 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 <math>\frac{13}{18}</math>. | Now we have to determine the greatest fraction of the RHS. Here this is given by <math>\frac{13}{18}</math>. | ||
After that we construe an artificial restriction by separating the fractions of the coefficients from integer parts in the equation with the greatest fraction. | After that we construe an artificial restriction by separating the fractions of the coefficients from integer parts in the equation with the greatest fraction. | ||
Version vom 26. Juni 2013, 10:27 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
| 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 | |||
| 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.
