Module 3 : Finite Mathematics

301 : Linear Programming

O B J E C T I V E

In this project we will graph linear inequalities in 2 dimensions and solve linear programming problems of optimizing a function over these planar regions.

S E T U P

In this project we will use the following command packages. Type and execute this line before begining the project below. If you re-enter the worksheet for this project, be sure to re-execute this statement before jumping to any point in the worksheet.

> restart; with(plots):

Warning, the name changecoords has been redefined

___________________________________________________________________________________

A. Graphing Linear Inequalities & Feasible Regions

___________________________________________________________________________________

One of the simplest regions we can create is a single inequality. The result is a half-plane.

> sys := { y >= -.8*x + 15 };

> inequal( sys, x = -5..12, y = -4..18, optionsfeasible = (color = red),
optionsexcluded = (color = blue), optionsopen = (color = white),
thickness = 1, linestyle = 3, optionsclosed = (color = coral, thickness = 2) );

The intersection of two half-planes is an unbounded triangular region.

> sys := { y < x + 7, x + y <= 16 };

> inequal( sys, x = -5..12, y = -4..18, optionsfeasible = (color = red),
optionsexcluded = (color = blue), optionsopen = (color = white),
thickness = 1, linestyle = 3, optionsclosed = (color = coral, thickness = 2) );

Completely enclosed regions can also be formed by creating a system of inequalities which bind the region in all directions.

> sys := { x + y <= 16, x > -3, x < 10, y > -2, y <= 14 };

> inequal( sys, x = -5..12, y = -4..18, optionsfeasible = (color = red),
optionsexcluded = (color = blue), optionsopen = (color = white),
thickness = 1, linestyle = 3, optionsclosed = (color = coral, thickness = 2) );

>

___________________________________________________________________________________

B. Optimization

___________________________________________________________________________________

In this section, we will solve optimization problems in linear programming. A typical problem of this sort has two basic components :
the contraints - a system of inequalities which define a feasible region.
an objective function to maximize or minimize on this region
( The regions defined and graphed above are examples of feasible regions. The one difference is that no
inequalities can be strict inequalities. In other words, every inequality must be or .)

The goal of the problem is to find a point (x,y) where the value of objective function is maximal or minimal, and what the value of the objective function is at that point. We are going to break the problem down into 5 steps.
1. Define a System of Inequalities (the constraints)
2. Graph the Feasible Region (an optional but advisable step)
3. Define the Objectiive Function, P(x,y)
4. Find the Solution, (x,y)
5. Find the Optimal Value

Lets look at an example.Well take the problem that follows and solve in Maple using these 5 steps.

1. Define a System of Inequalities

> sys := { x + y <= 20, x >=0, x <= 12, y >= 0, y <= 14 };

2. Graph the Feasible Region

> inequal( sys, x = -2..15, y = -2..18, optionsfeasible = (color = red),
optionsexcluded = (color = blue), optionsclosed = (color = coral), thickness = 2);

This is very similar to the graphs we created above.

3. Define the Objective Function

Maple defines functions in this way. Its not enough to simply type P(x,y) = 2x + 3y + 11. You need to type P := (x,y) -> and then the definition of the function followed by a semicolon.

> P := 2*x + 3*y + 11;

4. Find the Solution

Maple is able to find the solution automatically once we have defined the system and the function.

> with(simplex):

Warning, the name display has been redefined

Warning, the protected names maximize and minimize have been redefined and unprotected

> soln := maximize( P, sys);

5. Find the Optimal Value

Here we substituted the solution (x,y) into the objective function to find the maximal value.

> subs( soln, P(x,y) );

Note that the solution depends on both the region and the function. If we change the function, we can get a completely different solution and optimal value.

> P := (x,y) -> 7*x + 2*y ;

> soln := maximize( P(x,y), sys);

> subs( soln, P(x,y) );

Here is another problem.

1. Define a System of Inequalities (the constraints)

> sys := { x >= 0, x <= 16, y >= 0,
2*y <= x + 20 };

2. Graph the Feasible Region (an optional but advisable step)

> inequal( sys , x = -1..18, y = -1..20,
optionsfeasible = (color = red),
optionsexcluded = (color = blue),
optionsclosed = (color = coral,
thickness = 2) );

3. Define the Objective Function, P(x,y)

> P := (x,y) -> 15*x - 3*y;

4. Find the Solution, (x,y)

> soln := minimize( P(x,y) , sys );

5. Find the Optimal Value

> subs( soln, P(x,y) );

>