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 3: | Zeile 3: | ||
Objective Function: | Objective Function: | ||
− | <math>max\;G = 2x_1 + 5x_2</math> | + | <math>max\;G = 2x_1 + 5x_2</math><br> |
Restrictions:<br> | Restrictions:<br> | ||
<math>2x_1 - x_2 \le 9</math><br> | <math>2x_1 - x_2 \le 9</math><br> | ||
Zeile 9: | Zeile 9: | ||
<math>x_1, x_2 \ge 0, integer</math> | <math>x_1, x_2 \ge 0, integer</math> | ||
− | {| class="wikitable | + | {| class="wikitable" style="float:left; margin-right:1em" |
|+ Initial tableau | |+ Initial tableau | ||
|- style="height: 40px;" | |- style="height: 40px;" | ||
Zeile 25: | Zeile 25: | ||
| scope="col" width="40" | || scope="col" width="40" | <math>y_1</math> || scope="col" width="40" | <math>y_2</math> || scope="col" width="40" | | | scope="col" width="40" | || scope="col" width="40" | <math>y_1</math> || scope="col" width="40" | <math>y_2</math> || scope="col" width="40" | | ||
|- style="height: 40px;" | |- style="height: 40px;" | ||
− | | <math>G</math> || <math>\frac{1}{3}</math> || <math>\frac{2}{3}</math> || <math>\frac{71}{3}=</math> | + | | <math>G</math> || <math>\frac{1}{3}</math> || <math>\frac{2}{3}</math> || <math>\frac{71}{3}=23\frac{2}{3}</math> |
|- style="height: 40px;" | |- style="height: 40px;" | ||
− | | <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> | + | | <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. | ||
+ | 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. |
Version vom 26. Juni 2013, 10:26 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} | Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\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 . After that we construe an artificial restriction by separating the fractions of the coefficients from integer parts in the equation with the greatest fraction.