Decision - Linear Programming

Question 1

What are the steps in a linear programming question?

Answer 1

1. Formulate the problem
2. Plot constraints on a graph and identify feasible region
3. Identify the maximum/minimum point (sliding rule/vertex testing)
4. If an integer value is required, determine the integer value

Question 2

How do you formulate the problem in linear programming?

Answer 2

1. State you decision variables (let x =, let y =)
2. State your objective (minimise/ maximise P = x + y etc)
3. State your constraints (including non-negativity constraint)

Question 3

How do you plot your constraints and identify the feasible region?

Answer 3

1. Rearrange constraint for y to be subject and then plot the line (dotted/solid depending on inequality)
2. Identify the feasible region (above/below line)

Question 4

How do you find the minimum/maximum point using the sliding ruler method?

Answer 4

1. Rearrange the objective function for y to be the subject
2. Plot the objective function with a random y-intercept
3. Slide your ruler (with the same gradient as the line) up/down and find the first/last vertex of the feasible region it touches to find the minimum/maximum point
4. Using simultaneous equations (equations of the constraint lines) find the minimum/maximum point
5. Substitute values back into the objective function to find the value

Question 5

How do you find the minimum/maximum point using the vertex testing method?

Answer 5

1. Using simultaneous equations (equations of the constraint lines) find the coordinates of every vertex of the feasible region
2. Substitute values back into the objective function to find the value at each vertex
3. Select the vertex which gives the largest/lowest value to be the maximum/minimum point

Question 6

What are the 2 methods to find the maximum/minimum point?

Answer 6

*Sliding ruler method
*Vertex testing method

Question 7

How would you find integer values for the maximum/minimum point when required?

Answer 7

1. Find the coordinates of the optimal point
2. Imagine a 1x1 box enclosing the optimal point with integer values as each corner of the box
3. Test each point with each of the constraints (using a table) if they fail 1 of the constraints then do NOT consider that point any further.
4. Out of the points which satisfy all the constraints, use the objective function to determine which has the maximum/minimum value for the integer value