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