Integer linear optimization: Cutting Planes 4: Unterschied zwischen den Versionen
Aus Operations-Research-Wiki
| [unmarkierte Version] | [unmarkierte Version] |
Kbrill (Diskussion | Beiträge) (→Example) |
Kbrill (Diskussion | Beiträge) (→Example) |
||
| Zeile 63: | Zeile 63: | ||
|} | |} | ||
<br>We reached the minimum.<br> | <br>We reached the minimum.<br> | ||
| − | <math>x_1 = \frac{5}{3}</math>, <math>x_2 = \frac{20}{3}</math>, <math>c^Tx = -15</math> | + | ::<math>x_1 = \frac{5}{3}</math>, <math>x_2 = \frac{20}{3}</math>, <math>c^Tx = -15</math> |
| + | The objective function is integer, but the solution not. | ||
| + | We need to import a new restriction. | ||
| + | ::<math>\frac{1}{3}x_1 + \frac{2}{3}x_2\geq \frac{2}{3}</math> | ||
Version vom 26. Juni 2013, 13:37 Uhr
Idea
The cutting plane algorithm was developed in 1950 by Delbert Ray Fulkerson and George Dantzig and later costumized by Egon Balas and Ralph Gomory. Today it is one of the standart methodes for solving a integer optimisation problem. The basic idea behind this methode is to treat your linear programm not as usual as an integer linear programm. Instead you should consider it as a LP-Relaxation and add further inequalities untill an integer solution is found.
Example
- max
- s.t. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 2x_{1}+x_{2} \leq 10
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -x_{1}+x_{2} \leq 5
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1} \leq 4
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}\geq0
integer
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}\geq0
integer
Now we transfer it into an minimum problem
- min Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -x_{1}-2x_{2}
- s.t. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 2x_{1}+x_{2} \leq 10
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -x_{1}+x_{2} \leq 5
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1} \leq 4
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}\geq0
integer
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}\geq0
integer
The correspondending Tableau is:
| 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.): -2 | ||
| Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -1 | |||
Now we use the Simplex Algorythm.
Pivot operation leads to:
| Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -3 | |||
| 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.): -1 | |||
2. Iteration
| Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{1}{3} | |||
| Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{1}{3} |
We reached the minimum.
- , , Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c^Tx = -15
The objective function is integer, but the solution not. We need to import a new restriction.
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{1}{3}x_1 + \frac{2}{3}x_2\geq \frac{2}{3}
