Math 1110 MAPLE LAB II
Math 111 Lab Number 2  Linear Programming and the Pivot on Maple
Math 111  Introduction to Linear Algebra  Lab 2 Linear Programming

The purpose of this lab is to use Maple to solve optimization problems. Just as Maple did all the algebra for matrix manipulations, it will also perform the "tableau algebra" for us. Also, just as we typed with(linalg): at the beginning of our matrix manipulation lab, we type with(simplex): at the beginning of this lab. The reason for this line is to tell Maple to find the commands associated with optimization so it will understand what we ask it to do.
>
with(simplex):
Warning, new definition for maximize
Warning, new definition for minimize
Maximization Problems
The first problem we want to look at involves maximizing an objective function subject to certain constraints.
Maximize z= 4x 1 +2x 2 +x 3 subject to the constraints:
2x 1 +3x 2 +3x 3 < 100
3x 1 +5x 2 +10x 3 < 150
x 1 > 0, x 2 > 0, x 3 > 0
The first step to doing this problem is to check to make sure the problem satisfies standard maximization form.
Next, just like when we do the problems by hand, we add in the slack variables.
2x 1 +3x 2 +3x 3 +x 4 =100
3x 1 +5x 2 +10x 3 +x 5 =150
Normally, if we do this by hand, we have to set up the simplex tableau then pivot to get our answer. But, when we use the computer, Maple will do all this for us. Simply enter the maximize command as it's listed below. Inside the parentheses we first type the objective function, then list the constraints with their slack variables inside the braces.
> maximize(4*x1+2*x2+x3,{2*x1+3*x2+3*x3+x4=100,3*x1+5*x2+10*x3+x5=150},NONNEGATIVE);
Hence, z has a maximum value when x 1 =0, x 2 =30, x 3 =0, x 4 =10, x 5 =0.
Before moving on, here are a few comments about the maximize command. First, notice that Maple doesn't read 4x 1 as 4 times x 1 . You have to enter the * yourself to get the computer to understand that you want it to multiply the 4 and the x 1 . Second, notice that after listing all the constraints I require that all the variables be greater than or equal to 0 by typing NONNEGATIVE. It is absolutely essential that you type this command (in all capital letters) after typing your constraints.
Now that we've found where the maximum occurs, we have to find out what the maximum value is. Unfortunately, Maple doesn't do this for us. But we know that the maximum value occurs when x 1 =0, x 2 =30 and x 3 =0. So, to find the maximum value z takes on simply plug these values into the objective function. z= 4(0)+2(30)+0=60. Thus, the maximum value for z is 60. So, when you do your homework problems, make sure you find both where the maximum (or minimum) value occurs (this is what the computer tells you) and what the maximum (minimum) value is (you must find this yourself). You can just write the maximum (or minimum) value on your lab after you've printed it out.
Minimization Problems
The next example we'll consider is a minimization problem.
Minimize w=y 1 +2y 2 +y 3 +5y 4 subject to the constraints:
y 1 +y 2 +y 3 +y 4 > 50
3y 1 +y 2 +2y 3 +y 4 > 100
y 1 > 0, y 2 > 0, y 3 > 0
To get Maple to do all the dirty work for us, simply enter the command:
> minimize(y1+2*y2+y3+5*y4,{y1+y2+y3+y4>=50,3*y1+y2+2*y3+y4>=100},NONNEGATIVE);
This tells us the minimum value for w occurs when y 1 =0, y 2 =0, y 3 =50 and y 4 =0.
Again, allow me to make a comment about the command line. Notice that I didn't need to convert my constraints, add slack variables, find the dual problem or any of the other "setup" work involved in doing the problem by hand, I simply typed in my constraints exactly as they were given to me.
Next, notice that although we found where the minimum occurs, we still need to find out what that minimum is. We do this by plugging the values for y 1 , y 2 , y 3 and y 4 back into the objective function. So the minimum value for w is 0+2(0)+50+5(0)=50.
Exercises:
Now, so that you can practice using Maple to do the nittygritty work for you, here are some exercises for you to do and turn in. Please make sure you write the maximum or minimum value on your lab not just where it occurs. Note: there may be more than one place where a maximum or minimum value can occur, so your answer for that part may or may not match your neighbor's answer. Your resulting maximum (or minimum) value should match but they may occur in different places.
1. Maximize z= x 1 +x 2 +4x 3+5x 4 subject to the constraints:
x 1 +2x 2 +3x 3+x 4 < 115
2x 1 +x 2 +8x 3+5x 4 < 200
x 1+x 3 < 50
x 1 > 0, x 2 > 0, x 3 > 0, x 4>0
2. Jaynata is working to raise money for the homeless by sending information letters and making followup calls to local labor organizations and church groups. She discovered that each church group requires 2 hours of letter writing and 1 hour of followup, while for each labor union she needs 2 hours of letter writing and 3 hours of followup. Jaynata can raise $100 from each church group and $200 from each union local, and she has a maximum of 16 hours of letter writing time and a maximum of 12 hours of followup time available per month. Determine the most profitable mixture of groups she could contact and the most money she can raise in a month.
3. Minimize w=4y 1 +5y 2 subject to the constraints:
10y 1 +5y 2> 100
20y 1 +10y 2> 150
y 1 > 0, y 2 > 0
4. Brand X canners produces canned corn, beans and carrots. Labor contracts require them to produce at least 1000 cases per month. Based on past sales, they should produce at least twice as many cases of corn as of beans. At least 340 cases of carrots must be produces to fulfill commitments to a major distributor. It costs $10 to produce a case of beans, $15 to produce a case of corn, and $25 to produce a case of carrots. How many cases of each vegetable should be produced to minimize costs?