Operation

Chapter 4 The Simplex Algorithm – Part II

Based on Introduction to Mathematical Programming: Operations Research, Volume 1 4th edition, by Wayne L. Winston and Munirpallam Venkataramanan

Lewis Ntaimo

L. Ntaimo (c) 2005 INEN420 TAMU

1

So Far …

• • • • Modeling LPs Solving 2-variable LPs graphically Simplex method - Max LPs Simplex method - Min LPs

– Method 1: Multiply objective function by -1 – Method 2: Modify Step 3 of simplex algorithm for Max LPs

•

Simplex method – Special cases:

– Alternative optimal solutions – Unbounded LPs

L. Ntaimo (c) 2005 INEN420 TAMU

2

Degeneracy and Convergence of the Simplex Algorithm

L. Ntaimo (c) 2005 INEN420 TAMU

3

4.11 Convergence of the Simplex Method

Recall:

Max z = cT x s.t. Ax = b x≥0

Where,

⎡ x1 ⎤ ⎢x ⎥ ⎢ 2⎥ ⎢.⎥ x=⎢ ⎥ ⎢.⎥ ⎢.⎥ ⎢ ⎥ ⎢ xn ⎥ ⎣ ⎦ ⎡ c1 ⎤ ⎢c ⎥ ⎢ 2⎥ ⎢.⎥ c=⎢ ⎥ ⎢.⎥ ⎢.⎥ ⎢ ⎥ ⎢cn ⎥ ⎣ ⎦ ⎡ a11 ⎢a ⎢ 21 ⎢ . A=⎢ ⎢ . ⎢ . ⎢ ⎢am1 ⎣ a12 a22 . . . am 2 . . . . . . . . . a1n ⎤ a2 n ⎥ ⎥ . ⎥ ⎥ . ⎥ . ⎥ ⎥ amn ⎥ ⎦

⎡ b1 ⎤ ⎢b ⎥ ⎢ 2⎥ ⎢.⎥ b=⎢ ⎥ ⎢.⎥ ⎢.⎥ ⎢ ⎥ ⎢bm ⎥ ⎣ ⎦

Assumption: Constraint matrix A has n columns and m linearly independent rows. So we can form an m x m square matrix called the basis by setting (n - m) variables to zero (nonbasic variables or nbv’s). The remaining variables are the basic variables or bv’s.

L. Ntaimo (c) 2005 INEN420 TAMU

4

4.11 Convergence of the Simplex Method

Recall that for any LP with m constraints, two bfs are said to be adjacent if their sets of bv’s have (m - 1) bv’s in common. e.g. bfs of two immediate simplex tableaus are adjacent bfs.

•

If an LP in standard form has m constraints and n variables, then there may be a basic solution for each choice of nonbasic variables. From n variables, in how many different ways can a set of (n - m) nonbasic variables (or equivalently, m basic variables) be chosen?

⎛n⎞ n! ⎜ ⎟= ⎜ m ⎟ (n − m)!m! ⎝ ⎠

⎛n⎞ ⎜ ⎟ ⎜ m⎟ ⎝ ⎠

•

Thus an LP can have at most

basic solutions!

5

L. Ntaimo (c) 2005 INEN420...