6. Linear Programming

Question 1

What are the 3 steps to formulating a linear programming problem?

Answer 1

1. Define the decision variable
2. State the objective
3. Write the constraints as inequalities

Question 2

What is the objective function?

Answer 2

The algebraic expression usually written in terms of the decision variables

Question 3

Name 3 examples of constraints

Answer 3

1. Time available
2. Raw materials available
3. Non-negativity

Question 4

What is the feasible region?

Answer 4

Region of graph that satisfies all constraints of linear programming problem

Question 5

By convention, should the feasible region be shaded or unshaded?

Answer 5

Unshaded - the rest of the graph is shaded

Question 6

How do you solve a linear programming problem?

Answer 6

Find the point in the feasible region that maximises or minimises the objective function

Question 7

Name 2 methods of finding an optimal solution

Answer 7

1. Objective line / ruler method

2. Vertex testing method

Question 8

Explain the objective line method

Answer 8

1. Draw the objective line
2. Use ruler to slide along the graph parallel to the objective line
3. For a maximum point, look for the last point covered by the objective line as it leaves the feasible region
4. For a minimum point, look for the first point covered by the objective line as it enters the feasible region

Question 9

Explain the vertex testing method

Answer 9

1. Find the co-ordinates of each vertex of the feasible region
2. Evaluate the objective function at each of these points
3. Select vertex that gives the optimal value of the objective function

Question 10

What happens when a linear programming problem needs integer solutions?

Answer 10

Consider points with integer co-ordinates near the optimal vertex and evaluate the objective function to check they lie in the feasible region