Integer linear optimization: Cutting Planes 2: Unterschied zwischen den Versionen
Aus Operations-Research-Wiki
[unmarkierte Version] | [unmarkierte Version] |
(→Approach) |
(→Approach) |
||
Zeile 17: | Zeile 17: | ||
:Row r: | :Row r: | ||
::<math>BV_r+\sum (a_{ij}*NBV_j) = b_r</math> | ::<math>BV_r+\sum (a_{ij}*NBV_j) = b_r</math> | ||
− | :Converting r to: You have to break all <math> | + | :Converting r to: You have to break all <math>a_{rj}</math> and <math>b_j</math> into the integer part and the rest. |
Version vom 20. Juni 2013, 12:06 Uhr
Cutting Planes Gruppe 2
Idea
The Idea of the Cutting Plane is to add Restrictions (the Cutting Planes) to contract the solution space more and more to get integers. These restrictions cut of the non-integer parts of the solution.
Approach
First of all you should divide your restrictions trough the greates common factor.
- Example: 6x1 – 15x2 <= 120
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow
3 x1 – 5 x2 <= 40
- (1) You search for the continous Optimum with the Simplex Algorithm. If your solution is integer you are finished.
- (2) Otherwise you have to insert Cutting Planes
- Your source row is the one with the greates non integer part.
- Row r:
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): BV_r+\sum (a_{ij}*NBV_j) = b_r
- Converting r to: You have to break all and into the integer part and the rest.