MA569 Summer I: Homework #2
Instructions: Solution should be written neatly and legibly. Since we moved online, it will be hard
to work with others, but you are encouraged to work with others on the assignment, but you should
write up your own solutions independently. You should reference all of your sources, including your
collaborators.
1. Two people have decided to go into business together selling crabs that they catch along the
Baltimore coast line After they catch the crabs, they bring them back to their processing plant
where they are cleaned, clawed, andwrapped to go. Following this process, they ship the crabs
to n different seafood restaurants located in a 10 mile × 10 mile square. Each restaurant i has
two coordinates (ai1,ai2) and demands di crabs.
Wewillmeasure the distance between the processing plant and the restaurant using the “Man-
hattan metric” (which is sometimes called the “taxicab metric”). That is, all streets go either
North-South or East-West, so the distance from location (xi , yi ) to (x j , yj ) is |xi − x j |+ |yi − yj |.
The unit transportation cost of shipping a crab is $c per mile (so it costs $m c per mile to ship
$m crabs).
Their goal is to locate the processing plant at a point (x , y ) inside the 10×10 square tominimize
the total transportation costs.
(a) Formulate the problem of determining where the processing plant should be located as
amathematical program tomeet all demands whileminimizing the transportation costs.
(Your answer to this part does not need to be a linear program.) (Hint: use absolute value.)
(b) Convert the mathematical program of part (a) to a linear programming problem.
(c) It is claimed that there is always an optimal solution to the linear programming problem
in which the processing plant is located at one of the restaurants. Show that this claim is
false.
(d) It is claimed that there is always an optimal solution to the linear programming problem
in which the processing plant is located at the x -coordinate of one restaurant and the y -
coordinate of one restaurant (they do not need to be the same restaurant). Show that this
claim is true.
1
2. Willy Wonka’s Candy Company produces three types of candy:
• Wonka Bars
• Bottle Caps
• Giant Sweet Tarts
In order to produce the different types of candy, Willy can run three different production pro-
cesses as described below. Each process involves blending different types of sugars in theMag-
ical Factories Mixer.
Provess 1: Running Process 1 for one hour:
Costs: $5
Requires: Two barrels of Sugar type A and three barrels of sugar type B
Output: TwoWonka Bars and One packet of Bottle Caps
Provess 2: Running Process 2 for one hour:
Costs: $4
Requires: One barrel of Sugar type A and three barrels of sugar type B
Output: Three packets of Bottle Caps
Provess 3: Running Process 3 for one hour:
Costs: $1
Requires: Three barrels of Sugar type A and three packets of Bottle Caps
Output: TwoWonka Bars and one packet of Giant Sweet Tarts
Each week we can purchase:
• 200 barrels of sugar type A and $2 Per Barrel
• 300 barrels of sugar type B at $3 Per Barrel
Assume that they can sell everything that they can produce.
• Wonka Bars are sold at $9 per bar.
• Bottle Caps are sold at $ 10 per packet.
• Giant Sweet Tarts are sold at $24 per packet.
Assume that 100 hours of mixing time are available.
(a) Formulate a Linear Programming Problem whose solution will maximize Willy Wonka’s
profits.
2
(b) Assume that instead of having 200 barrels of sugar type A and 300 barrels of sugar type B
available that you can order a total of 500 barrels. Show how to modify your Linear Pro-
gramming formulation in part (a) to account for this revised problem.
(c) Suppose that instead of selling three candies separately, they can only be sold as part of a
box consisting of one Wonka Bar, two packets of Bottle Caps, and one pack of Giant Sweet
Tarts. Each Wonka Box sells for $54. Modify your Linear Programming formulation in
part (a) to model this new scenario. Assume that you again have 200 barrels of sugar type
A and 300 barrels of sugar type B . (Hint: You may find it helpful to start by creating a
mathematical program where the objective function is a minimum of linear functions, and
then converting to a linear program.)
3
3. Suppose that the following tableau occurs while solving a linear program in standard form us-
ing the simplex algorithm, where A,B ,C ,D ,E ,F,G and H are all constants:
z x1 x2 x3 x4 s1 s2 s3
1 A 0 0 B C D 0 E
0 F 0 1 1 1 3 0 4
0 −2 1 0 2 G −1 0 2
0 −1 0 0 0 H 1 1 3
(a) What is the current CPF?
(b) For each of the following situations, give values for A through H that would make the given
condition true.
i. The current CPF is a unique optimal solution.
ii. The current CPF is not optimal, the only candidate for entering the basis is s1, and when
the next iteration is performed, x3 will leave the basis.
iii. The current CPF is not optimal, the only candidate for entering the basis is x1, and the
the problem is unbounded from above.
iv. The current CPF is optimal, and there exists exactly one other CPF that is also optimal.
v. The current CPF is optimal, and there also exists an extreme ray of alternative optimal
solutions.
4
4. Consider the following Linear Programming Problem:
Objective: Maximize 50x1 + 25x2 + 20x3 + 40x4
Subject to: 2x1 + x2 ≤ 30
x3 + 2x4 ≤ 20
x1, x2, x3, x4 ≥ 0
Work through the simplex algorithm step by step to find all of the optimal solutions. Show the
steps of the simplex algorithm — you do not need to write out every row operation, but you should
write the tableau for each iteration and indicate which variable is enter the basis and which
variable is leaving the basis.
5
5. A toy companyproduces three typesof toys—train, trucks, andcares. Theyhave threedifferent
machines that are used to make the toys: Machine A, Machine B , and Machine C .
• Creating a toy train requires 1 minute on Machine A, 3 minutes on Machine B , and 1
minute onMachine C .
• Creating a truck requires 2 minutes onMachine A and 4 minutes onMachine C .
• Creating a toy car require 1 minute onMachine A and 2 minutes onMachine B .
Machine A can be used for total of 430 minutes each day; machine B can be used for a total
of 460 minutes each day; and machine C can be used for total of 420 minutes each day. The
revenue for creating a train is $3; the revenue for a truck is $2; and the revenue for a car is $5.
(a) Formulate a linear programming problem to maximize the revenue for the toy company.
(b) Use the simplex algorithm to solve the linear programming problem. Show the steps of the
simplex algorithm — you do not need to write out every row operation, but you should write
the tableau for each iteration and indicate which variable is entering the basis and which
variable is leaving the basis.
6
6. Consider the following linear program:
Objective: Minimize 2x1 − 3x2
Subject to: x1 + 2x2 ≤ 12
2x1 + x2 ≤ 8
−x1 + x2 ≤ 12
x1 ≥ −5
(a) Graph the feasible region, and determine the coordinates of the vertices.
(b) Work through the simplex algorithm step by step to find the optimal solutions. Show the
step of the simplex algorithm.
7
7. Consider the following linear program:
Objective: Maximize 2x1 + 5x2 + 3x3
Subject to: x1 − 2x2 + x3 ≥ 20
2x1 + 4x2 + x3 = 50
x1, x2, x3 ≥ 0
Work through the simplex algorithm step by step to find the optimal solution. Show the steps of
the simple algorithm.
8
8. Consider the three-dimensional polytope shown below:
The point J lies at the origin, and the points A, B and C lie on the x−, y− and z−axes, respec-
tively. The coordinates of the vertices are given in the following table:
A (1,0,0) F (0,1,1)
B (0,1,0) G (1,1,0.5)
C (0,0,1) H (0.5,1,1)
D (1,1,0) I (1,0.5,1)
E (1,0,1) J (0,0,0)
Suppose that this polytope is the feasible region for some linear programming problem.
(a) Suppose that the simplex algorithm for the linear programming problem starts at J and
that the optimal solution occurs at H . For each of the following paths of vertices, state
whether they could be legitimate paths for simplex algorithm. If it is not a possible path for
the simplex algorithm, explain why not.
i. J → B → F →H
ii. J →D →G →H
iii. J → A→ B → F →H
iv. J → A→D → B → J →C → F →H
(b) Find an objective function Z = Ax +B y +C z so that the points A,B ,D and J are all max-
imal solutions, but the point (0,0,1) is not maximal.
(c) Find an objective function Z = Ax +B y +C z so that the points G ,H and I are all maximal
solutions, but the points (0,0,1) is not maximal.
(d) Determine the inequalities that describe the feasible region.
9
9. Consider the following linear program:
Objective: Maximize 3x1 + 2x2 + 5x3
Subject to: 3x1 − x2 − x3 ≤ −6
2x1 − x2 − x3 ≥ 3
2x1 − 3x2 + x3 ≥ 4
x1, x2, x3 ≥ 0
Work through the simplex algorithm step by step to show that there are no feasible solution to
this linear program.
10
10. During the simplex algorithm a degenerate basic variable is a basic variable that is equal to 0.
(a) Give an example of a tableau for which the following holds:
• There is a degenerate basic variable.
• There is a non-basic variable in the Z row that has a zero that has a zero coefficient.
• The current CPF is the unique optimal solution (but there may more than one optimal
tableau).
(b) Give an example of a tableau for which the following holds:
• There is a degenerate basic variable.
• There is a non-basic variable in the Z row that has a zero coefficient.
• The linear program has multiple optimal solutions, but only one CPF.
11
11. The Gemstone Tool company produces wrenches and pliers. They are both made from steel, and
the process involves molding on a Molding Machine, and assembling on an Assembly Machine.
The amount of steel used and the daily availability of steel are shown in the following table. The
table also shows the amount of machine time needed for each product as well as the availability
of machine time.
Wrenches pliers Availability
Steel (lbs.) 1.5 1.0 27000 lbs./day
Molding Machine (hrs.) 1.0 1.0 21000 hours/day
Assembly Machine (hrs.) 0.3 0.5 9000 hours/day
There is demand for at most16000wrenches and for at most15000pliers. For every1000wrenches
that are sold, the company makes $100; for every 1000 pliers which are sold, the company make
$130.
(a) Formulate a linear program to determine the optimal level of production for wrenches and
pliers that maximized the earnings.
(b) Solve the problem using Excel. What is the optimal solution to the linear program? What
is the optimal objective value?
(c) Use Excel to create the Sensitivity Report. Print out the Sensitivity Report, and include it
with your homework. Use the sensitivity report to answer the following question:
i. Suppose the amount of steel available increases to 28000 lbs./day. What is the new
optimal objective value?
ii. Suppose the Molding Machine changes to only being available for 20000 hours/day.
What is the new optimal objective value?
iii. Supoose that the demand for pliers increases to 18000 pliers. What is the new optimal
objective value?
iv. The company could purchase additional Assembly Machines to increase the amount
of Assembly Machine hours available each day. How much should they be willing to
spend to add an additional 100 hours of Assembly Machine time?
v. Suppose that the price of wrenches increases, and that as a result, for every1000wrenches
sold, the company make $110. Does this change the optimal solution? What is the new
optimal objective value.
vi. Suppose that demand for wrenches decreases to A wrenches. For what values of A is the
current solution is optimal?
12
(d) Suppose that the company institutes a new policy — they must produce at least as many
wrenches as pliers. Does the optimal solution changes? Why or why not?
13
12. Consider the following linear programming problem:
Objective: Maximize 5x1 + 3x2
Subject to: 2x1 + 3x2 ≤ 12
2x1 + x2 ≤ 6
x1, x2 ≥ 0
(a) Sketch the graph of the feasible region for this linear programming problem, and determine
the coordinates of the vertices.
(b) Create the dual linear programming problem.
(c) Sketch a graph of the feasible region for the dual problem, and determine the coordinates
of the vertices.
(d) Use the simplex algorithm to solve the primal problem (that is, the original problem, not
the dual problem).
(e) Identify the sequence of CPF solutions that the simplex algorithm uses to find the optimal
solution.
(f) Use the final tableau from part (d) to determine the optimal solution to the dual problem.
(g) Each iteration of the simplex algorithm also corresponds to a point in the dual problem (al-
though the point in the dual problem will not be a feasible solution until the final tableau).
At each iteration, the coefficients of the slack variables in the top row of the tableau cor-
respond to a point in the dual problem. Identify this sequence of points, and mark these
points on your graph in part (c).
14
13. Consider the following linear program:
Objective: Maximize 3x1 + 5x2 + 2x3
Subject to: −2x1 + 2x2 + x3 ≤ 5
3x1 + x2 − x3 ≤ 10
x1, x2, x3 ≥ 0
(a) Determine the optimal solution and optimal objective value to the linear program (using
any method you want).
(b) If we added the constraint 2x1+ x2+ x3 ≤ 70, would the optimal solution change? Explain
your answer without re-solving the linear program.
(c) What is the dual linear program?
(d) Determine the optimal solution and optimal objective value to the dual linear program
(Using any method you want).
(e) Suppose we add an new variable x4 to the original linear program as follows:
Objective: Maximize 3x1 + 5x2 + 2x3 + 20x3
Subject to: −2x1 + 2x2 + x3 + x4 ≤ 5
3x1 + x2 − x3 + 3x4 ≤ 10
x1, x2, x3, x4 ≥ 0
How does the new variable change the dual program?
(f) Does the new variable changes the optimal solution to the dual program? Explain your
answer without solving the new dual program.
(g) Does the new variable changes the optimal solution to the original linear program? Explain
you answer without solving the new primal program.
15