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 30: | Zeile 30: | ||
| <math>y_A</math> || style="background:#fedcba" | <math>\frac{36}{11}</math> || <math>\frac{1}{11}</math> | | | <math>y_A</math> || style="background:#fedcba" | <math>\frac{36}{11}</math> || <math>\frac{1}{11}</math> | | ||
|- style="height: 50px;" | |- style="height: 50px;" | ||
| − | |<math>x_2 </math> || <math> \frac{3}{11} </math> || <math> \frac{1}{11} </math> | | + | |<math>x_2 </math> || <math> \frac{3}{11} </math> || <math> \frac{1}{11} </math> | |
| − | + | ||
Version vom 26. Juni 2013, 13:07 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.): -\frac{21}{11} | |||
