Topic 4: Linear Programming

Introduction to Linear Programming

Linear Programming sounds really difficult, but it’s just a neat way to use math to find out the best way to do things, For example, how many things to make or buy. It usually involves a system of linear inequalities, called constraints, but in the end, we want to either maximize something (like profit) or minimize something (like cost). Whatever we’re maximizing or minimizing is called the objective function.


Linear Programming Problem:

A linear programming problem is one in which we are to find the maximum or minimum value of a linear expression

Ax + By + Cz + ...

(called the objective function), subject to a number of linear constraints of the form 

Ax + By + Cz + ... ≤ N

or

or Ax + By + Cz + ... ≥ N

The largest or smallest value of the objective function is called the optimal value, and a collection of values of x, y, z, ... that gives the optimal value constitutes an optimal solution. The variables x, y, z, ... are called the decision variables.

For Example;

Find the maximum value of

p = 3x - 2y + 4z

subject to

4x + 3y - z ≥ 3 

x + 2y + z ≤ 4

x ≥ 0, y ≥ 0, z ≥ 0

The objective function is p = 3x - 2y + 4z. The constraints are 

4x + 3y - z ≥ 3 

x + 2y + z ≤ 4 

x ≥ 0, y ≥ 0, z ≥ 0

Question:

Wait a minute! Why can't I simply choose, say, z to be really large (z = 1,000,000 say) and thereby make p as large as I want? 

Answer:

You can't because   Select one that would make p too large. z has a negative coefficient in the first constraint. you have to change x first. it would violate the first constraint. it would violate the second constraint. None of the above. Take me to the tutorial! Get me out of here! 

Sketching the Solution Set of a Linear Inequality:

To sketch the region represented by a linear inequality in two variables:

A. Sketch the straight line obtained by replacing the inequality with an equality.

B. Choose a test point not on the line ((0,0) is a good choice if the line does not pass through the origin, and if the line does pass through the origin a point on one of the axes would be a good choice).

C. If the test point satisfies the inequality, then the set of solutions is the entire region on the same side of the line as the test point. Otherwise it is the region on the other side of the line. In either case, shade out the side that does not contain the solutions, leaving the solution region showing.

For Example;

To sketch the linear inequality

3x - 4y ≤ 12

First sketch the line 3x - 4y = 12

Next, choose the origin (0, 0) as the test point (since it is not on the line). Substituting x = 0, y = 0 in the inequality gives

3(0) - 4(0) ≤ 12

Since this is a true statement, (0, 0) is in the solution set, so the solution set consists of all points on the same side as (0, 0). This region is left unshaded, while the (grey) shaded region is blocked out.

Feasible Region:

The feasible region determined by a collection of linear inequalities is the collection of points that satisfy all of the inequalities.

To sketch the feasible region determined by a collection of linear inequalities in two variables: Sketch the regions represented by each inequality on the same graph, remembering to shade the parts of the plane that you do not want. What is unshaded when you are done is the feasible region.

For Example;

The feasible region for the following collection of inequalities is the unshaded region shown below (including its boundary).

3x - 4y ≤ 12, 

x + 2y ≥ 4 

x ≥ 1 

y ≥ 0.