L8 - Linear Programming and Simplex Method

Question 1

Define linear programming…

Answer 1

A mathematical technique for finding the max or min of a linear function with multiple variables.

Question 2

What are we trying to find in a linear problem?

Answer 2

The max or min of the linear function based on certain constraints.

Question 3

What does it mean to optimise a function?

Answer 3

Find the max or min value of the function.

Question 4

What are the extreme values of a linear function?

Answer 4

A vertex at which the max or min value of the function is obtained. I.e for a f(x,y) = 5x + 7y, it will be the coordinates where f(x,y) is min, y is max, x is max, f(x,y) is max.

Question 5

What are the steps to solving a linear programming problem?

Answer 5

1. Establish the linear function
2. Establish constraints that the function has to adhere to.
3. Graph functions viable region by graphic the constraints. The feasible region is the area within the constraint lines.
4. Vertices of the viable region give us the extreme points.
5. Calculate the coordinates of the optimal point
   1. Solve equations for Y
   2. Solve for X
   3. Plug X into Y equations
   4. Plug X,Y into original function to get coordinates.

Question 6

What is the ISO Line?

Answer 6

The line that runs through the maximum point.

Question 7

What does each linear equation ( constraint ) represent? What does the set of constraint lines construct?

Answer 7

1. A plane that divides the graph space into viable and non-viable areas for the function.
   
   2. it constructs the viable region of the linear function.

Question 8

What method do we use if we have an equation with more than 2 dimensions?

Answer 8

Simplex method ( Dantzig’s Algorithm )

Question 9

What are the steps of the Simplex algorithm?

Answer 9

1. Convert into slack form
   1. Create new transposed equations from the constraint equations.
2. Check a basic solution exists
   1. Set original variables to 0, slack variables to the largest constants of each slack equation. If the sum is above 0, a solution is possible.
3. Pivot
   1. Use variable with highest coefficient in z
   2. Find equation where that variable is tightest
   3. Transpose equation for variable
   4. Substitute new equation and simplify all other equations
4. Iterate
5. Termination
   1. If maximising, termination occurs when all coefficients of the objective function are negative.
   2. The optimal value of the problem is the number in the equation.

Question 10

In the pivot stage, how do we choose the entering variable?

Answer 10

The variable with the most positive coefficient in the original objective function.

Question 11

In the pivot stage, how do we choose the tightest constraint?

Answer 11

The slack equation that reaches 0 the fastest when the value of the entering variable is increased.

Question 12

What is the termination criteria of the Simplex Algorithm when maximising or minimising?

Answer 12

Maximising -> When coefficients of the objective function are negative.

Minimising -> When coefficients of the objective function are positive.