Lecture 6 Simplex Method: Artifical Starting Solution and ...

[Pages:17]Lecture 6 Simplex Method: Artifical Starting Solution and Some Special Cases

September 4, 2009

Outline:

? Initial table vs initial simplex table ? Artificial start: Two-phase method ? Special cases:

? Degeneracy ? Multiple optimal solutions ? Infinite optimal value ? Infeasibility of the problem

Operations Research Methods

Lecture 6 1

Lecture 6

Simplex method: started at a feasible basic solution

Illustrated on the Reddy Mikks problem

Original LP formulation

Standard LP form

maximize subject to

z = 5x1 + 4x2 6x1 + 4x2 24 x1 + 2x2 6 x1, x2 0

maximize subject to

z = 5x1 + 4x2

6x1 + 4x2 + x3

= 24

x1 + 2x2

+ x4 = 6

x1, x2, x3, x4 0

Operations Research Methods

2

Initial table vs Initial simplex table

Basis x1 x2 x3 x4 RHS Values

z -5 -4 0 0

=0

?? 6 4 1 0

= 24

?? 1 2 0 1

=6

Basis: x3 and x4

Basis x1 x2 x3 x4 RHS Values

z -5 -4 0 0

=0

x3 6 4 1 0

= 24

x4 1 2 0 1

=6

Initial table can be used as initial simplex table

Lecture 6

Operations Research Methods

3

Lecture 6

Basis: x1 and x4 Basis

x1 x2 x3 x4 RHS Values

z - 5 -4 0 0

0

x1

6 410

24

x4

1 201

6

This table cannot be used as the initial simplex table! We have to transform

the table (Gauss-Jordan elimination using x1-column elements)

Basis x1 x2 x3 x4 RHS Values

z

0

-

2 3

5 6

0

20

x1 1

2

1

0

3

6

4

x4 0

4 3

-

1 6

1

2

This table is an initial simplex table, i.e., the simplex method can start.

Operations Research Methods

4

Artificial Start: Two-phase method

Lecture 6

? Sometimes, it is not easy to find an initial feasible solution (i.e., to choose initial bases yielding a feasible point)

? Two-phase method is used in such situations

? In first phase, a feasibility problem associated with the LP is solved by a simplex method

? In the second phase, the solution from the first phase is used to start running the simplex method

Operations Research Methods

5

Lecture 6

Two-phase Method: Example

Original LP formulation

Standard LP form

minimize z = 4x1 + x2

minimize z = 4x1 + x2

subject to 3x1 + x2 = 3

subject to 3x1 + x2

=3

4x1 + 3x2 6

4x1 + 3x2 - x3

=6

x1 + 2x2 4

x1 + 2x2

+ x4 = 4

x1, x2 0

x1, x2, x3, x4 0

It is not easy to find a basis yielding a basic feasible solution!

Phase I: we first solve a feasibility problem associated with the LP:

introduce new variables R1 and R2

minimize subject to

r = R1 + R2

3x1 + x2

+ R1 = 3

4x1 + 3x2 - x3

+ R2 = 6

x1 + 2x2

+ x4

=4

x1, x2, x3, x4, R1, R2 0

Operations Research Methods

6

Phase I: Initial table

Lecture 6

Basis x1 x2 x3 x4 R1 R2 RHS Values

r 0 0 0 0 -1 -1

0

R1 3 1 0 0 1 0

3

R2 4 3 -1 0 0 1

6

x4 1 2 0 1 0 0

4

Initial simplex table

Basis x1 x2 x3 x4 R1 R2 RHS Values

r 7 4 -1 0 0 0

9

R1 3 1 0 0 1 0

3

R2 4 3 -1 0 0 1

6

x4 1 2 0 1 0 0

4

Operations Research Methods

7

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download