# LINEAR PROGRAMMING

For more detailed notes and interesting problems, see:  http://mathsci2.appstate.edu/~hph/SageMath/

## Let's begin with a simple problem:

A doll factory wants to plan how many Barbie and Ken dolls to manufacture in a week to maximize company profit.  A Barbie doll earns $6.00 in profit and is made of 12 ounces of plastic for her body and 5 ounces of nylon for her hair. A Ken doll earns$6.50 and is made of 14 ounces of plastic.  Each doll goes in a box made of 4 ounces of cardboard.  The company can only get one weekly shipment of raw materials, including 100,000 ounces of plastic, 30,000 ounces of nylon and 35,000 ounces of cardboard.

Setting this up is easy:

The first task is to identify the variables.  The Barbie and Ken problem asks us that in the first sentence - “How many Barbie and Ken dolls ...?” so we let:

B = the number of Barbies to make per week

K = the number of Kens to make per week

The objective of a linear programming problem will always be to maximize or minimize a quantity.  In the first sentence of the problem we see “maximize company profit.”  Profit is $6.00 for each Barbie and$6.50 for each Ken, so the total amount of money, Z, that they get will be 6B + 6.50K.  We can state this as:

Maximize Z = 6B + 6.5K

Now we have to translate all the limiting conditions or constraints.

1)  Plastic is in short supply; the information about plastic says we must use less than or equal to 100,000 oz.  12B is the amount of plastic we use in making Barbies.  Similarly, 14K is the amount of plastic we use in making Kens.  So 12B + 14K is the total amount of plastic used, and it must be less than 100,000:

12B + 14K ≤ 100,000

2)  Nylon is used only in Barbie dolls, at  5 oz. per doll.  That gives:

5B ≤ 30,000

3)  Cardboard is in short supply just like the plastic.  We proceed the same way:

4B + 4K ≤ 35,000

The complete mathematical model is below.  The last pair of constraints is to remind us that making negative numbers of dolls is not realistic.  Even the obvious must be stated in the mathematical formulation.

B = the number of Barbies to make per week,

K = the number of Kens to make per week.

Maximize   Z =  6B + 6.5K  (profit)

Subject to: 12B + 14K ≤ 100,000  (plastic)

5B  ≤ 30,000   (nylon)

4B +  4K ≤ 35,000   (cardboard)

B ≥ 0 and K ≥ 0     (non-negativity)

So how do we solve this?  We need to calculate the (B,K) pair with the largest profit that still fits within the constraints.  A point that satisfies all the constraints is called feasible. The feasible region is the set of points that satisfy all the inequalities.  Let’s start by sketching the feasible region.  (Note that this would be difficult with more than two variables.)

We will graph B ≥ 0 and K ≥ 0 by using only the positive parts of the axes.  Now we graph the rest of the inequalities on the same coordinate system, shading the side that doesn’t work; the region with no shading will be the feasible region!

var('B, K') plastic = implicit_plot(12*B+14*K==100000, (B, 0, 10000), (K, 0, 10000)) nylon=implicit_plot(5*B==30000, (B, 0, 10000), (K, 0, 10000)) cardboard=implicit_plot(4*B+4*K==35000, (B, 0, 10000), (K, 0, 10000)) region=region_plot([12*B+14*K<100000, 5*B<30000, 4*B+4*K<35000], (B,0,10000), (K,0,10000), incol="white", outcol="yellow") show(region+plastic+nylon+cardboard)

Let’s look at the plastic constraint.  There’s no room left in this constraint when 12B + 14K = 100,000.  Graphically, this happens on the line we drew for the plastic constraint.  So where on the graph will constraints have no room left?  On the border of the region.  Exactly which part of the border?  We need to use the objective (which is also a line) to test where we leave the feasible region.  Consider a few of the graphs below, on which the objective is drawn for various Z-values.

object20000 = implicit_plot(6*B+6.5*K==20000, (B, 0, 10000), (K, 0, 10000)) show(object20000+region)
object40000 = implicit_plot(6*B+6.5*K==40000, (B, 0, 10000), (K, 0, 10000)) show(object40000+region)
object49000 = implicit_plot(6*B+6.5*K==49000, (B, 0, 10000), (K, 0, 10000)) show(object49000+region)
object55000 = implicit_plot(6*B+6.5*K==55000, (B, 0, 10000), (K, 0, 10000)) show(object55000+region)

As we raise the objective value, the line moves up through the feasible region -- 20000 and 40000 are too low; 50000 is a little too high.

In the first two graphs, a portion of the objective line is within the region.  In the third graph, the line has been pushed up until it touches exactly one point of the region (a corner).  The fourth graph shows that increasing the objective value more results in the line no longer intersecting the region.  So it appears that the objective value can be increased until the objective line intersects the region at a point, namely a corner. This is the fundamental idea for the method we’ll use to solve these problems - find the corner of the region and the answer will be the one that is "best."

From the graph above, we know the best is the corner where the vertical line (nylon) crosses plastic.  Let's solve for that corner:

solve([12*B+14*K==100000, 5*B==30000], (B,K))
6*6000+6.5*2000 #The objective value!

Solving a two variable linear programming problem graphically is straight-forward.  It is also possible to solve a three variable problem graphically, but the corner points become more difficult to locate visually.  It is impossible to solve a problem with more than three variables using our graphical method.  The corner points of the feasible region must be found somehow using algebra and then checked for the optimal value.  The Simplex algorithm developed by Danzig solves the problem using this idea.

#Call up the algorithm and define the variables: KenBarbie = MixedIntegerLinearProgram() B, K = KenBarbie['B'], KenBarbie['K']
#Set up the objective: KenBarbie.set_objective(6*B + 6.5*K)