4 - simplex algorithm & sensitivity analysis

The Simplex Algorithm

We already know that

The Simplex Algorithm

Idea

A point is – by definition – unique, so

A point is – by definition – unique, so a corner point implies a unique solution.

Simplex Algorithm

How can we compute a corner point / solution?

Simplex Algorithm

How can we know whether a constraint holds with equality or not?

Simplex Algorithm

Putting it together

Simplex Algorithm

Example

Simplex Algorithm

What does the transition from the initial corner point to the next one entail?

Simplex Algorithm

How to quantify these changes?

Tight & Loose constraints

Simplex Algorithm

Summary

How can we solve a problem instance without relying on a graphical representation?

Simplex Algorithm: Adding the Objective Function to the SLE

Simplex Tableau

Simplex Algorithm: Tabular Form

1

Simplex Algorithm: Tabular Form

Variable notations etc

Simplex Algorithm: Tabular Form

2

The Simplex Algorithm is a fairly simple procedure that iteratively solves SLEs, but it has some downsides:

Can we avoid these downsides while maintaining the overall idea of the Simplex Algorithm? Yes – with the

Revised Simplex Algorithm

Revised Simplex Algorithm

Idea

Revised Simplex Algorithm

Blueprint

Revised Simplex Algorithm

1

Revised Simplex Algorithm

2

Revised Simplex Algorithm

Result

The (Revised) Simplex Algorithm and Duality

1

The (Revised) Simplex Algorithm and Duality

2

The (Revised) Simplex Algorithm and Duality

3

Robust optimization =

a way of incorporating uncertainty in input data in our decisions.

Difference Basis and (Basic) Solution

Difference Basis and (Basic) Solution

Example

Subsequently, we will focus on sensitivity analysis with changes to a single parameter only at a time.

Changing the Right-Hand Side

1

Changing the Right-Hand Side

2

Changing an Objective Function Coefficient

1

Changing an Objective Function Coefficient

2

Removing a Variable

Changing the Coefficient Matrix A

Adding a Variable