Assignment 1

Rules:
1. The solutions should be done by hand, and you should write your name on each page in
the top right corner of the page. Ensure your assignment includes the solutions of all
exercises. In case you have not solved all exercises you get a penalty of 10 points for each
unsolved exercise.
2. Convert your assignment to PDF format before submission. If the assignment is not in PDF
format you get a penalty of 10 points.
3. Please name your PDF file appropriately, preferably with your name and the assignment
number.
4. In case of late submissions, you get a 50-point penalty, so I strongly encourage you to
submit your assignment on time.
Exercises:
1. Ralph Edmund loves steaks and potatoes. Therefore, he has decided to go on a steady
diet of only these two foods (plus some liquids and vitamin supplements) for all his
meals. Ralph realizes that this isn’t the healthiest diet, so he wants to make sure that he
eats the right quantities of the two foods to satisfy some key nutritional requirements.
He has obtained the nutritional and cost information shown at the top of the next
column. Ralph wishes to determine the number of daily servings (may be fractional) of
steak and potatoes that will meet these requirements at a minimum cost.
a) Formulate a linear programming model for this problem.
b) Use the graphical method to solve this model.

Grams of Ingredient per

Serving Daily Requirement
Ingredients Steak Potatoes (grams)
Carbohydrates 5 15 ≥ 50
Protein 20 5 ≥ 40
Fat 15 2 ≤ 60
Cost per serving $8 $4

2. A toy manufacturer preparing a production schedule for two new toys, trucks and
spinning tops, must use the information concerning its construction times given in the
following table:

Truck Spinning Top

Machine A 2hr 1hr
Machine B 3hr 1hr
Finishing 5hr 1hr

For example, each truck requires 2 hours on machine A. The available employee hours
per week are as follows: for operating machine A, 80 hours; for B, 50 hours; for finishing,
70 hours. If the profits on each truck and spinning top are $7 and $2, respectively, how
many of each toy should be made per week to maximize profit? What is the maximum
profit?

3. A firm manufactures two products, X and Y. To make 1 unit of product X requires 3 units
of raw materials and 2 units of labor. To make 1 unit of product Y requires 5 units of raw
materials and 2 units of labor. The total number of units available for raw materials and
labor is 315 and 170, respectively. The firm makes a profit of $15 for making and selling
product X. The corresponding profit for Y is $20.
 a) Formulate a linear programming problem to maximize the firm’s profits.
b) Solve the linear programming problem graphically.

4. An electronics firm has decided to launch two models of tablet, TAB1 and TAB2. The cost
of making each of type TAB1 is $120 and the cost for TAB2 is $160. The firm recognizes
that this is a risky venture, so it has decided to limit the total weekly production costs to
$4000. Also, due to a shortage of skilled labor, the total number of tablets that the firm
can produce in a week is at most 30. The profit made on each device is $600 for TAB1
and $700 for TAB2. How should the firm arrange production to maximize profit?

5. Consider the linear programming problem: Minimize 𝑍 = 𝑥 + 𝑦 subject to

2𝑥 + 𝑦 ≥ 16
2𝑥 + 3𝑦 ≥ 24
−𝑥 + 𝑦 ≤ 12
𝑥 ≥ 0, 𝑦 ≥ 0
a) Use the graphical method to solve this problem.
b) One of the five constraints is not needed for drawing the feasible region. State the
redundant constraint.
c) Find the new solution if the problem is changed to maximizing 𝑍 = 𝑥 + 𝑦 and is
subject to the same constraints.
d) Find the new solution if the problem is changed to minimizing 𝑍 = 2𝑥 + 𝑦 and is
subject to the same constraints.
e) The objective function is changed to minimizing 𝑍 = 𝑎𝑥 + 2𝑦 where a is a positive
constant. Find the largest value of a for which the linear programming problem has
the solution 𝑥 = 12, 𝑦 = 0.

6. Work through the simplex method step by step to solve the following problem.
Maximize 𝑍 = 4𝑥1 + 3𝑥2 + 6𝑥3 , subject to
3𝑥1 + 6𝑥2 + 3𝑥3 ≤ 30
2𝑥1 + 2𝑥2 + 3𝑥3 ≤ 40
and 𝑥1 ≥ 0, 𝑥2 ≥ 0, 𝑥1 ≥ 0.

7. Work through the simplex method step by step to solve the following problem.
Maximize Z=2x1+4x2+3x3, subject to
x1 + 2x2 + 2x3 ≤ 6
2x1 + x2 + 2x3 ≤ 4
x1 + x2 + 2x3 ≤ 8
and x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
8. Work through the simplex method step by step to solve the following problem.
Maximize Z = 2x1 − x2 + x3, subject to
3x1 + x2 + x3 ≤ 12
x1 − x2 + 2x3 ≤ 2
x1 + x2 − x3 ≤ 4
and x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.

9. Consider the following problem. Minimize Z = x1 + 4x2, subject to

x1 + 2x2 ≤8
x1 + 6x2 ≥ 12
x2 ≥ 2
and x1 ≥ 0, x2 ≥ 0.
Introduce artificial variables to reformulate this problem as a convenient artificial
problem then apply the simplex method.

10. Consider the following problem. Maximize Z=x1+2x2+3x3, subject to

x1+2x2+2x3≤6
x1−x2−x3≥1
and x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
Introduce artificial variables to reformulate this problem as a convenient artificial
problem then apply the simplex method.

11. Consider the following problem. Maximize Z = 5x1+3x2, subject to

x1+x2 ≤ 10
2x1+3x2 ≤ 24
x1 ≤ 8
(no lower bound constraint for x2).
a) Reformulate this problem so that all variables have nonnegativity constraints.
b) Work through the simplex method step by step to solve the problem.

12. Consider the following problem. Maximize Z = 2x1+3x2, subject to

x1+4x2 ≤ 20
3x1+2x2 ≤ 18
x1 ≥ − 5
(no lower bound constraint for x2).
a) Reformulate this problem so that it has only two functional constraints and all
variables have nonnegativity constraints.
b) Work through the simplex method step by step to solve the problem.
13. You are given the following linear programming problem. Maximize Z = 4x1 + 2x2,
subject to
2x1 + 3 ≤ 16 (resource 1)
x1 + 3x2 ≤ 17 (resource 2)
x1+x2 ≤ 5 (resource 3)
and x1 ≥ 0, x2 ≥ 0.
a) Work through the simplex method step by step to solve the problem.
b) Identify the shadow prices for the three resources and describe their significance.

14. Consider the following problem. Maximize Z = x1 − 7x2 + 3x3, subject to

2x1 + x2 − x3 ≤ 8 (resource 1)
4x1 − 3x2 ≤ 4 (resource 2)
−3x1 + 2x2 + x3 ≤ 6 (resource 3)
and x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
a) Work through the simplex method step by step to solve the problem.
b) Identify the shadow prices for the three resources and describe their significance.

15. Consider the following problem. Minimize Z = x1 + 2x2, subject to

−2x1 + x2 ≥ 1
x1 − 2x2 ≥ 1
and x1 ≥ 0, x2 ≥ 0.
a) Construct the dual problem.
b) Identify the optimal solution for the dual problem
c) Identify the solution for the primal problem from the final set of equations of the dual
problem.

16. Consider the following problem. Maximize Z = 5x1 + 3x2 + 4x3, subject to
2x1 + x2 + x3 ≤ 20 (resource 1)
3x1 + x2 + 2x3 ≤ 30 (resource 2)
and x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
a) Construct the dual problem for this primal problem.
b) Solve the dual problem graphically. Use this solution to identify the shadow prices for
the resources in the primal problem.
c) Confirm your results from part (b) by solving the primal problem automatically by the
simplex method and then identifying the shadow prices.