PART I Linear programming problem setup

PART 1.1 Standard form of linear programming

Maximise  Z  = c1x1  + c2x2  +... + cnxn

Subject to  a11x1  + a12x2  +... + a1nxn  ≤ b1

a21x1  + a22x2  +... + a2nxn  ≤ b2

… …

am1x1  + am2x2  +... + amnxn  ≤ bm

with      x1, x2,  ... , xn  ≥  0

Definitions

a) Objective function

b) Decision variables

c) Cost coefficients

d) Constraint matrix

e) Resource vector

f) Feasible solution

g) Feasible region

h) Optimal solution

Exercise 1: the following is the final simplex tableau for linear programming problems:

a) What are the non-basic variables?

b) What is the optimal value of the objective functions?

c) Identify the solution vertex (x1, x2, x3 )

PART 1.2 The simplex algorithm

Algebraic representation of corner points

a) At the corner point, basic variables are non-zero and non-basic variables are zero.

b) Two corner points are adjacent if they differ in precisely one non-basic variable (or equivalently, in precisely one basic variable)

The simplex algorithm

Aim: move from one FCP to an adjacent FCP with largest potential increase in the objective function

Z

.

a) Initialization: start on a feasible corner point (FCP).

i.e by setting decision variables to zero and slack variables to resource constraints b) Iteration steps: move to an adjacent FCP with best potential increase of Z.

1)   Which non-basic variable enters the basis?

Largest coefficient rule: increasing the non-basic variable Xl to Xl  >  0 with the largest cost coefficient cl might yield the largest increase of Z

2)   Which basic variables leave the basis?

Choose X  such that    bl     is minimal

c) Stopping rule: stop at FCP if its Z is greater than the Z-value of all its adjacent FCPs. Stop when all

modified cost coefficient c  ≥  0.

Exercise 2: Use the simplex algorithm to solve the system by hand

Max Z  = −  3x1  +  2x2  +  3x3

Subject to   2x1  + x2  + x3  ≤  12

3x1  − x2  +  3x3  ≤  8

with x1, x2, x3  ≥  0

Exercise 3:

John Smith instals and demonstrates burglar alarms. There are two burglar alarms that he instals, type A and B. Type A requires 1 hour to install and  hour to demonstrate. Type B requires 2 hours to      install and   hour to demonstrate. Union rules require Smith to work a minimum of 20 hours per      week as an installer and a maximum of 20 hours per week as a demonstrator. If he gets paid $13 per

hour for installing and $10 per hour as a demonstrator, how many alarms of each type should Smith install and demonstrate each week to maximise his earnings?

Exercise 4: The following is the final simplex tableau for a linear programming problem:

a) What are the basic and non-basic variables?

b) What is the optimal value of the objective function?

c) What is the optimal solution(s)?

Exercise 5: The following is the final simplex tableau for a linear programming problem:

Exercise 6: Use the Simplex method to solve the system by hand:

Max  Z  =  2x1  +  2x2

Subject to  x1  +  2x2  ≤  11

2x1  + x2  ≤  10

x1  + x2  ≤  6

with x1, x2  ≥  0

PART 1.3 Potential problems of the simplex algorithm

Tie-breaking rules

a) Largest coefficient rule ambiguity

Solution: choosing either will work.

b) Smallest non-negative ration ambiguity

Solution: choosing either will work.

Smallest index rule: to break a tie, always choose the variable with smallest index 

No variable leaving the basis

Degeneracy

The equations in a tableau do not permit any increment of the selected non-basic variables, and it may be impossible to increase the objective function in a single pivot step.

Multiple optimal solutions

If contours of the objective function are parallel to a boundary, there may be a family of solutions.

PART 1.4 Efficiency of the simplex algorithm

Klee-Minty cube

The set of feasible solutions is a deformed n-dimensional cube, constructed such that the   simplex algorithm passes through all its vertices: 2n  −  1 iterations are needed with a fixed pivoting rule (worst case).