Gruppe 1: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
Guihai (Diskussion | Beiträge) (→Example) |
Guihai (Diskussion | Beiträge) (→Example) |
||
(45 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
Zeile 1: | Zeile 1: | ||
− | |||
− | |||
===Cutting-plane method=== | ===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 <math> x_i </math> 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. | Cutting plane method is an approach to the solution of integer linear programming problems.First of all we do not consider that variables <math> x_i </math> 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. | ||
+ | |||
+ | ===Approach=== | ||
+ | (1) Search of a continuous optimum with simplex method. | ||
+ | ::if integer <math>\Rightarrow</math> end, otherwise continue with (2). | ||
+ | (2) Insert Cutting Plane. Continue with (1). | ||
+ | |||
+ | The step of inserting Cutting Plane: | ||
+ | ::We get from the optimal but non-integal tableau the equation <math>BV_i+\sum a_{ij}NBV_j = b_i</math> (<math>\ast</math>) | ||
+ | ::Seperate both <math>a_ij</math> and <math>b_i</math> into integer fraction <math>g</math> and the rest <math>f</math>: | ||
+ | ::Namely | ||
+ | ::::<math>a_{ij} = g_{ij} + f_{ij}</math> <math>\qquad</math> (<math>0 \leq f_{ij} < 1</math>) | ||
+ | ::::<math>b_i = g_i + f_i</math> <math>\qquad</math> (<math>0 \leq f_i < 1</math>) | ||
+ | ::We rewrite the equation (<math>\ast</math>) to | ||
+ | ::::<math>BV_i+\sum g_{ij}NBV_j -g_i= f_i-\sum f_{ij}NBV_j</math> | ||
+ | ::By introducing a new slack variable we obtain a cutting plane: | ||
+ | ::::<math>BV_i'-\sum f_{ij}NBV_j -g_i= -f_i</math> | ||
+ | |||
+ | BV: Basis variable | ||
+ | NBV: Non basis variable | ||
+ | a,b: Coefficients from tableau | ||
+ | g: integer fraction | ||
+ | f: rest | ||
===Example=== | ===Example=== | ||
Zeile 24: | Zeile 44: | ||
|+ Initial tableau | |+ Initial tableau | ||
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | | scope="col" width=" | + | | scope="col" width="50" | || scope="col" width="50" | <math>x_1</math> || scope="col" width="50" | <math>x_2</math> || scope="col" width="50" | |
|- style="height: 50px;" | |- style="height: 50px;" | ||
| <math>Z</math> || <math>-3</math> || <math>-4</math> || <math>0</math> | | <math>Z</math> || <math>-3</math> || <math>-4</math> || <math>0</math> | ||
Zeile 37: | Zeile 57: | ||
{| class="wikitable" style="text-align:center" | {| class="wikitable" style="text-align:center" | ||
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | | scope="col" width=" | + | | scope="col" width="50" | || scope="col" width="50" | <math>x_1</math> || scope="col" width="50" | <math>y_B</math> || scope="col" width="50" | |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | | <math>Z</math> || <math>\frac{ | + | | <math>Z</math> || <math>-\frac{21}{11}</math> || <math>\frac{4}{11}</math> || <math>24</math> |
|- style="height: 50px;" | |- style="height: 50px;" | ||
| <math>y_A</math> || style="background:#fedcba" | <math>\frac{36}{11}</math> || <math>\frac{1}{11}</math> || <math>18</math> | | <math>y_A</math> || style="background:#fedcba" | <math>\frac{36}{11}</math> || <math>\frac{1}{11}</math> || <math>18</math> | ||
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | |<math> | + | |<math>x_2 </math> || <math> \frac{3}{11} </math> || <math> \frac{1}{11} </math> || <math>6</math> |
|} | |} | ||
− | {| class="wikitable" style="text-align:center" | + | {| class="wikitable" style="text-align:center" |
|+ First optimal solution | |+ First optimal solution | ||
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | | scope="col" width=" | + | | scope="col" width="50" | ||scope="col" width="50" | <math>y_A</math> || scope="col" width="50" | <math>y_B</math> || scope="col" width="50" | |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | | <math>Z</math> || <math> \frac{ | + | | <math>Z</math> || <math> \frac{7}{12} </math> || <math> \frac{5}{12} </math> || <math> \frac{69}{2} </math> |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | | <math> | + | | <math>x_1</math> || <math> \frac{11}{36} </math> || <math> \frac{1}{36} </math> || <math> \frac{11}{2} </math> |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | |<math> | + | |<math>x_2 </math> || <math> -\frac{1}{12} </math> || <math> \frac{1}{12} </math> || <math> \frac{9}{2} </math> |
|} | |} | ||
+ | |||
+ | [[Image:CP1.jpg]] | ||
+ | |||
From the tableau above we can get the following equations | From the tableau above we can get the following equations | ||
− | ::<math> | + | ::<math>x_1 + \tfrac{11}{36} y_A + \tfrac{1}{36} y_B = \tfrac{11}{2}</math> |
− | ::<math> | + | ::<math>x_2 - \tfrac{1}{12} y_A + \tfrac{1}{12} y_B = \tfrac{9}{2}</math> |
− | + | We choose the first equation <math>x_1 + \tfrac{11}{36} y_A + \tfrac{1}{36} y_B = \tfrac{11}{2}</math>,which has the greatest fraction. | |
It can be written as following: | It can be written as following: | ||
− | ::<math> | + | ::<math>x_1 + \tfrac{11}{36} y_A + \tfrac{1}{36} y_B = 5+\tfrac{1}{2}</math> |
− | ::<math>\tfrac{ | + | ::<math>\tfrac{11}{36} y_A + \tfrac{1}{36} y_B = \tfrac{1}{2} + (5-x_1)</math> |
Here we introduce a new slack variable <math>y_C</math>,so the equation will be writen: | Here we introduce a new slack variable <math>y_C</math>,so the equation will be writen: | ||
− | ::<math>y_C-\tfrac{ | + | ::<math>y_C-\tfrac{11}{36} y_A - \tfrac{1}{36} y_B = -\tfrac{1}{2}</math> |
+ | The first cutting plane with original variables: <math>y_C+x_1=5</math> | ||
− | {| class="wikitable" style="text-align:center" | + | {| class="wikitable" style="text-align:center" |
|+ First optimal solution extended | |+ First optimal solution extended | ||
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | | scope="col" width=" | + | | scope="col" width="50" | ||scope="col" width="50" | <math>y_A</math> || scope="col" width="50" | <math>y_B</math> || scope="col" width="50" | |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | | <math>Z</math> || <math> \frac{ | + | | <math>Z</math> || <math> \frac{7}{12} </math> || <math> \frac{5}{12} </math> || <math> \frac{69}{2} </math> |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | | <math> | + | | <math>x_1</math> || <math> \frac{11}{36} </math> || <math> \frac{1}{36} </math> || <math> \frac{11}{2} </math> |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | |<math> | + | |<math>x_2 </math> || <math> -\frac{1}{12} </math> || <math> \frac{1}{12} </math> || <math> \frac{9}{2} </math> |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | |<math>y_C </math> || <math> \frac{ | + | |<math>y_C </math> || style="background:#fedcba" | <math> -\frac{11}{36} </math> || <math> -\frac{1}{36} </math> || <math> -\frac{1}{2} </math> |
|} | |} | ||
+ | [[Image:CP2.jpg]] | ||
− | {| class="wikitable" style="text-align:center" | + | The basic solution corresponding to this tableau is not feasible, since the right-hand |
+ | side in the last row is negative. On the other hand, the coeffcients in the first row | ||
+ | are all non-negative — indicating dual-feasibility. So we use the dual simplex method | ||
+ | to solve the relaxation.We choose pivot element <math> -\frac{11}{36} </math> here. | ||
+ | |||
+ | {| class="wikitable" style="text-align:center" | ||
|+ Second optimal solution | |+ Second optimal solution | ||
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | | scope="col" width=" | + | | scope="col" width="50" | ||scope="col" width="50" | <math>y_C</math> || scope="col" width="50" | <math>y_B</math> || scope="col" width="50" | |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | | <math>Z</math> || <math> \frac{ | + | | <math>Z</math> || <math> \frac{21}{11} </math> || <math> \frac{4}{11} </math> || <math> \frac{369}{11} </math> |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | | <math> | + | | <math>x_1</math> || <math> 1 </math> || <math> 0 </math> || <math> 5 </math> |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | |<math> | + | |<math>x_2 </math> || <math> -\frac{3}{11} </math> || <math> \frac{1}{11} </math> || <math> \frac{51}{11} </math> |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | |<math>y_A </math> || <math> \frac{ | + | |<math>y_A </math> || <math> -\frac{36}{11} </math> || <math> \frac{1}{11} </math> || <math> \frac{18}{11} </math> |
|} | |} | ||
− | {| class="wikitable" style="text-align:center" | + | So we have found the solution ,namely <math>x_1 = 5 </math> and <math>x_2 = \frac{51}{11} </math>. |
+ | This solution is non-integral, so we seek a cut. For this purpose, we choose a row | ||
+ | of the optimal tableau with a non-integral right-hand side. For instance, the second | ||
+ | row of the optimal tableau says: | ||
+ | ::<math>x_2-\tfrac{3}{11} y_C + \tfrac{1}{11} y_B = \tfrac{51}{11}</math> | ||
+ | We can introduce a new slack variable y_D and rewrite the cut as | ||
+ | ::<math>y_D-\tfrac{8}{11} y_C - \tfrac{1}{11} y_B = -\tfrac{7}{11}</math> | ||
+ | The second cutting plane with original variables: <math>y_D+x_1+x_2=9</math> | ||
+ | With this new variable and this new constraint, the simplex tableau becomes | ||
+ | |||
+ | {| class="wikitable" style="text-align:center" | ||
|+ Second optimal solution extended | |+ Second optimal solution extended | ||
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | | scope="col" width=" | + | | scope="col" width="50" | ||scope="col" width="50" | <math>y_C</math> || scope="col" width="50" | <math>y_B</math> || scope="col" width="50" | |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | | <math>Z</math> || <math> \frac{ | + | | <math>Z</math> || <math> \frac{21}{11} </math> || <math> \frac{4}{11} </math> || <math> \frac{369}{11} </math> |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | | <math> | + | | <math>x_1</math> || <math> 1 </math> || <math> 0 </math> || <math> 5 </math> |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | |<math> | + | |<math>x_2 </math> || <math> -\frac{3}{11} </math> || <math> \frac{1}{11} </math> || <math> \frac{51}{11} </math> |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | |<math>y_A </math> || <math> \frac{ | + | |<math>y_A </math> || <math> -\frac{36}{11} </math> || <math> \frac{1}{11} </math> || <math> \frac{18}{11} </math> |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | |<math>y_D </math> || <math> \frac{ | + | |<math>y_D </math> || style="background:#fedcba" | <math> -\frac{8}{11} </math> || <math> -\frac{1}{11} </math> || <math> -\frac{7}{11} </math> |
|} | |} | ||
− | {| class="wikitable" style="text-align:center" | + | [[Image:CP3.jpg]] |
+ | |||
+ | So we also use the dual simplex method to solve the relaxation. | ||
+ | Then we get | ||
+ | |||
+ | {| class="wikitable" style="text-align:center" | ||
+ | |+ Third optimal solution | ||
+ | |- style="height: 50px;" | ||
+ | | scope="col" width="50" | ||scope="col" width="50" | <math>y_D</math> || scope="col" width="50" | <math>y_B</math> || scope="col" width="50" | | ||
+ | |- style="height: 50px;" | ||
+ | | <math>Z</math> || <math> \frac{21}{8} </math> || <math> \frac{1}{8} </math> || <math> \frac{33}{8} </math> | ||
+ | |- style="height: 50px;" | ||
+ | | <math>x_1</math> || <math> \frac{11}{8} </math> || <math> -\frac{1}{8} </math> || <math> \frac{33}{8} </math> | ||
+ | |- style="height: 50px;" | ||
+ | |<math>x_2 </math> || <math> -\frac{3}{8} </math> || <math> \frac{1}{8} </math> || <math> \frac{39}{8} </math> | ||
+ | |- style="height: 50px;" | ||
+ | |<math>y_A </math> || <math> -\frac{9}{2} </math> || <math> \frac{1}{2} </math> || <math> \frac{9}{2} </math> | ||
+ | |- style="height: 50px;" | ||
+ | |<math>y_C </math> || <math> -\frac{11}{8} </math> || <math> \frac{1}{8} </math> || <math> \frac{7}{8} </math> | ||
+ | |} | ||
+ | |||
+ | This is optimal, but not integral. For our next cut, we choose the third row: | ||
+ | ::<math>x_2-\tfrac{3}{8} y_D + \tfrac{1}{8} y_B = \tfrac{39}{8}</math> | ||
+ | We introduce a new slackness variable y_E and get a new constraint: | ||
+ | ::<math>y_E-\tfrac{5}{8} y_D - \tfrac{1}{8} y_B = -\tfrac{7}{8}</math> | ||
+ | The third cutting plane with original variables: <math>y_E+x_1+2x_2=13</math> | ||
+ | The new simplex tableau is showed as following | ||
+ | |||
+ | {| class="wikitable" style="text-align:center" | ||
+ | |+ Third optimal solution extended | ||
+ | |- style="height: 50px;" | ||
+ | | scope="col" width="50" | ||scope="col" width="50" | <math>y_D</math> || scope="col" width="50" | <math>y_B</math> || scope="col" width="50" | | ||
+ | |- style="height: 50px;" | ||
+ | | <math>Z</math> || <math> \frac{21}{8} </math> || <math> \frac{1}{8} </math> || <math> \frac{33}{8} </math> | ||
+ | |- style="height: 50px;" | ||
+ | | <math>x_1</math> || <math> \frac{11}{8} </math> || <math> -\frac{1}{8} </math> || <math> \frac{33}{8} </math> | ||
+ | |- style="height: 50px;" | ||
+ | |<math>x_2 </math> || <math> -\frac{3}{8} </math> || <math> \frac{1}{8} </math> || <math> \frac{39}{8} </math> | ||
+ | |- style="height: 50px;" | ||
+ | |<math>y_A </math> || <math> -\frac{9}{2} </math> || <math> \frac{1}{2} </math> || <math> \frac{9}{2} </math> | ||
+ | |- style="height: 50px;" | ||
+ | |<math>y_C </math> || <math> -\frac{11}{8} </math> || <math> \frac{1}{8} </math> || <math> \frac{7}{8} </math> | ||
+ | |- style="height: 50px;" | ||
+ | |<math>y_E </math> || <math> -\frac{5}{8} </math> || style="background:#fedcba" | <math> -\frac{1}{8} </math> || <math> -\frac{7}{8} </math> | ||
+ | |} | ||
+ | |||
+ | [[Image:CP4.jpg]] | ||
+ | |||
+ | Again use dual simplex method to solve it.Then we can obtain | ||
+ | |||
+ | {| class="wikitable" style="text-align:center" | ||
|+ Final tableau | |+ Final tableau | ||
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | | scope="col" width=" | + | | scope="col" width="50" | ||scope="col" width="50" | <math>y_D</math> || scope="col" width="50" | <math>y_E</math> || scope="col" width="50" | |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | | <math>Z</math> || <math> | + | | <math>Z</math> || <math> 2 </math> || <math> 1 </math> || <math> 31 </math> |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | | <math> | + | | <math>x_1</math> || <math> 2 </math> || <math> -1 </math> || <math> 5 </math> |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | |<math> | + | |<math>x_2 </math> || <math> -1 </math> || <math> 1 </math> || <math> 4 </math> |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | |<math>y_A </math> || <math> | + | |<math>y_A </math> || <math> -7 </math> || <math> 4 </math> || <math> 1 </math> |
|- style="height: 50px;" | |- style="height: 50px;" | ||
− | |<math>y_C </math> || <math> | + | |<math>y_C </math> || <math> -2 </math> || <math> 1</math> || <math> 0</math> |
+ | |- style="height: 50px;" | ||
+ | |<math>y_B </math> || <math> 5 </math> || <math> -8 </math> || <math> 7</math> | ||
|} | |} | ||
+ | This is optimal and integral. The solution of our IP is thus | ||
+ | ::<math>x_1=5,x_2=4</math> | ||
+ | |||
+ | ===Reference=== | ||
+ | [http://www.maths.bris.ac.uk/~mayt/MATH32500/2007/code/IP/gomoryExample.pdf An example of the gomory cutting plane algorithm] |
Aktuelle Version vom 5. Juni 2013, 18:48 Uhr
Inhaltsverzeichnis
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.
Approach
(1) Search of a continuous optimum with simplex method.
- if integer Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow
end, otherwise continue with (2).
(2) Insert Cutting Plane. Continue with (1).
The step of inserting Cutting Plane:
- We get from the optimal but non-integal tableau the equation Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): BV_i+\sum a_{ij}NBV_j = b_i
(Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ast
)
- Seperate both and into integer fraction and the rest :
- Namely
- (Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 0 \leq f_{ij} < 1
)
- (Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 0 \leq f_i < 1
)
- We rewrite the equation (Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ast
) to
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): BV_i+\sum g_{ij}NBV_j -g_i= f_i-\sum f_{ij}NBV_j
- By introducing a new slack variable we obtain a cutting plane:
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): BV_i'-\sum f_{ij}NBV_j -g_i= -f_i
- By introducing a new slack variable we obtain a cutting plane:
BV: Basis variable NBV: Non basis variable a,b: Coefficients from tableau g: integer fraction f: rest
Example
Consider the integer optimization problem
- Maximize
- Subject to
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 3x_1-x_2 \le 12
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 3x_1+11x_2 \le 66
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1,x_2 \geq 0
and integer
Introduce slack variables to produce the standard form
- Maximize Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Z = 3x_1-x_2
- Subject to
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_A+3x_1-x_2 \le 12
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_B+3x_1+11x_2 \le 66
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1,x_2 \geq 0
and integer
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.): -4 | ||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -1 | |||
We use simplex method to get the optimal solution.(See "First optimal solution")
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{21}{11} | |||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{1}{12} |
From the tableau above we can get the following equations
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_2 - \tfrac{1}{12} y_A + \tfrac{1}{12} y_B = \tfrac{9}{2}
We choose the first equation ,which has the greatest fraction.
It can be written as following:
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \tfrac{11}{36} y_A + \tfrac{1}{36} y_B = \tfrac{1}{2} + (5-x_1)
Here we introduce a new slack variable ,so the equation will be writen:
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_C-\tfrac{11}{36} y_A - \tfrac{1}{36} y_B = -\tfrac{1}{2}
The first cutting plane with original variables:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{1}{12} | |||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{11}{36} | Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{1}{36} | Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{1}{2} |
The basic solution corresponding to this tableau is not feasible, since the right-hand side in the last row is negative. On the other hand, the coeffcients in the first row are all non-negative — indicating dual-feasibility. So we use the dual simplex method to solve the relaxation.We choose pivot element Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{11}{36}
here.
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{3}{11} | |||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{36}{11} |
So we have found the solution ,namely and . This solution is non-integral, so we seek a cut. For this purpose, we choose a row of the optimal tableau with a non-integral right-hand side. For instance, the second row of the optimal tableau says:
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_2-\tfrac{3}{11} y_C + \tfrac{1}{11} y_B = \tfrac{51}{11}
We can introduce a new slack variable y_D and rewrite the cut as
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_D-\tfrac{8}{11} y_C - \tfrac{1}{11} y_B = -\tfrac{7}{11}
The second cutting plane with original variables:
With this new variable and this new constraint, the simplex tableau becomes
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{3}{11} | |||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{36}{11} | |||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{8}{11} | Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{1}{11} | Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{7}{11} |
So we also use the dual simplex method to solve the relaxation. Then we get
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{1}{8} | |||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{3}{8} | |||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{9}{2} | |||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{11}{8} |
This is optimal, but not integral. For our next cut, we choose the third row:
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_2-\tfrac{3}{8} y_D + \tfrac{1}{8} y_B = \tfrac{39}{8}
We introduce a new slackness variable y_E and get a new constraint:
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_E-\tfrac{5}{8} y_D - \tfrac{1}{8} y_B = -\tfrac{7}{8}
The third cutting plane with original variables:
The new simplex tableau is showed as following
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{1}{8} | |||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{3}{8} | |||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{9}{2} | |||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{11}{8} | |||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{5}{8} | Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{1}{8} | Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{7}{8} |
Again use dual simplex method to solve it.Then we can obtain
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 | |||
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -7 | |||
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.): -8 |
This is optimal and integral. The solution of our IP is thus