Gruppe 1
Cutting-plane method
Cutting plane method is an approach to the solution of integer linear programming problems.First of all we do not consider that variables is an integer. But by adding linear constraints (so called cutting plane) the original feasible region will be cut.That part which was cut off contains only non-integer solution.Any integer feasible solution is kept in the ”modified” feasible region. This method is to point out how to find the right kinds of cutting planes (not necessarily only one to find), so that after cutting the feasible region finally we actually the get integer optimal solution. This method is proposed by R. E. Gomory, and it is also known as Gomory's cutting plane method.
Example
Consider the integer optimization problem
- Maximize
- Subject to
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 4x_1+5x_2 \le 20
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 2x_1+x_2 \le 6
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_i \geq 0,x_i \mbox{ an integer for } i=1,2
Introduce slack variables to produce the standard form
- Maximize
- Subject to
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_i \geq 0,x_i \mbox{ an integer for } i=1,2
We use simplex method to get the optimal solution.(See "First optimal solution")
-4 | -3 | 0 | |
4 | 5 | 20 | |
2 | 1 | 6 |
2 | -1 | 12 | |
-2 | 3 | 8 | |
3 |
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{-2}{3} | |||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{-1}{6} |
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{-2}{3} | |||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{-1}{6} | |||
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{-2}{3} | Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{-2}{3} |
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{-5}{6} | |||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{-1}{4} | |||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{-3}{2} |
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{-5}{6} | |||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{-1}{4} | |||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{-3}{2} | |||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{-1}{6} | Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{-1}{2} | 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.): -1 | |||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{-1}{2} | |||
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.): -2 |