Aldrin Jewelers uses rubies and sapphires to produce two types of rings. A Type

Question

Aldrin Jewelers uses rubies and sapphires to produce two types of rings. A Type 1 ring requires 2 rubies, 3 sapphires, and 1 hour of jeweler’s labor. A Type 2 ring requires 3 rubies, 2 sapphires, and 2 hours of jeweler’s labor. Each Type 1 ring sells for $400, and each Type 2 sells for $500. All rings produced by Aldrin can be sold. Aldrin now has 100 rubies, 120 sapphires, and 70 hours of jeweler’s labor. Extra rubies can be purchased at a cost of $100 per ruby. Market demand requires that the company produce at least 20 Type 1 rings and at least 25 Type 2 rings. a. Formulate this linear programming problem and solve it. b. Formulate the dual of this linear programming problem and solve it.

Explanation / Answer

Note: Software solutions have been provided. If manual solutions are required, please let me know.

Let X1 and X2 be the number of Type 1 and Type 2 rings respectively. Also, let 'R' be the number rubies purchased.

(a)

Objective function: Maximize Z = 400X1 + 500X2 - 100R
Subject to,
2X1 + 3X2 - R 100 (Ruby availability)
3X1 + 2X2 120 (Sapphire availability)
1X1 + 2X2 70 (Labor hours availability)
X1 20 (Demand for Ring 1)
X2 25 (Demand for Ring 2)
X1, X2, R 0

Simplex iterations

Note that at the end of the fourth iteration, all Cj - Zj values are less than or equal to zero. Therefore, we conclude that optimality is reached. The optimal solution is -

X1 = 20
R = 15
X2 = 25
Z = 19000

(b)

Dual formulation

Minimize. W = 100Y1 + 120Y2 + 70Y3 - 20Y4 - 25Y5
Subject to,
2Y1 + 3Y2 + Y3 - Y4 400
3Y1 + 2Y2 + 2Y3 - Y5 500
Y1 100
Y1, Y2, Y3, Y4, Y5 0

Instead of solving the dual again, we take the final iteration of the primal,

From the duality theorems, we know that at optimality

The shadow prices are highlighted in the table. So, the optimal solution is -

Y1 = 100
Y2 = 0
Y3 = 200
Y4 = 0
Y5 = 200
W = 19000

Initial Simplex Tableau CBi Cj 400 500 -100 0 0 0 0 0 Solution Ratio Basic X1 X2 R s1 s2 s3 s4 s5 0 s1 2 3 -1 1 0 0 0 0 100 33.3 0 s2 3 2 0 0 1 0 0 0 120 60.0 0 s3 1 2 0 0 0 1 0 0 70 35.0 0 s4 1 0 0 0 0 0 -1 0 20 - 0 s5 0 1 0 0 0 0 0 -1 25 25.0 Zj 0 0 0 0 0 0 0 0 0 Cj - Zj 400 500 -100 0 0 0 0 0 First iteration CBi Cj 400 500 -100 0 0 0 0 0 Solution Ratio Basic X1 X2 R s1 s2 s3 s4 s5 0 s1 2 0 -1 1 0 0 0 3 25 8.3 0 s2 3 0 0 0 1 0 0 2 70 35.0 0 s3 1 0 0 0 0 1 0 2 20 10.0 0 s4 1 0 0 0 0 0 -1 0 20 - 500 X2 0 1 0 0 0 0 0 -1 25 -25.0 Zj 0 500 0 0 0 0 0 -500 12500 Cj - Zj 400 0 -100 0 0 0 0 500 Second iteration CBi Cj 400 500 -100 0 0 0 0 0 Solution Ratio Basic X1 X2 R s1 s2 s3 s4 s5 0 s5 0.7 0.0 -0.3 0.3 0.0 0.0 0.0 1.0 8.3 -25.0 0 s2 1.7 0.0 0.7 -0.7 1.0 0.0 0.0 0.0 53.3 80.0 0 s3 -0.3 0.0 0.7 -0.7 0.0 1.0 0.0 0.0 3.3 5.0 0 s4 1.0 0.0 0.0 0.0 0.0 0.0 -1.0 0.0 20.0 - 500 X2 0.7 1.0 -0.3 0.3 0.0 0.0 0.0 0.0 33.3 -100.0 Zj 333.3 500 -166.7 166.7 0 0 0 0 16666.67 Cj - Zj 66.67 0 66.67 -166.7 0 0 0 0 Third iteration CBi Cj 400 500 -100 0 0 0 0 0 Solution Ratio Basic X1 X2 R s1 s2 s3 s4 s5 0 s5 0.5 0.0 0.0 0.0 0.0 0.5 0.0 1.0 10.0 20.0 0 s2 2.0 0.0 0.0 0.0 1.0 -1.0 0.0 0.0 50.0 25.0 -100 R -0.5 0.0 1.0 -1.0 0.0 1.5 0.0 0.0 5.0 -10.0 0 s4 1.0 0.0 0.0 0.0 0.0 0.0 -1.0 0.0 20.0 20.0 500 X2 0.5 1.0 0.0 0.0 0.0 0.5 0.0 0.0 35.0 70.0 Zj 300 500 -100 100 0 100 0 0 17000 Cj - Zj 100 0 0 -100 0 -100 0 0 Fourth iteration CBi Cj 400 500 -100 0 0 0 0 0 Solution Ratio Basic X1 X2 R s1 s2 s3 s4 s5 400 X1 1.0 0.0 0.0 0.0 0.0 1.0 0.0 2.0 20.0 0 s2 0.0 0.0 0.0 0.0 1.0 -3.0 0.0 -4.0 10.0 -100 R 0.0 0.0 1.0 -1.0 0.0 2.0 0.0 1.0 15.0 0 s4 0.0 0.0 0.0 0.0 0.0 -1.0 -1.0 -2.0 0.0 500 X2 0.0 1.0 0.0 0.0 0.0 0.0 0.0 -1.0 25.0 Zj 400 500 -100 100 0 200 0 200 19000 Cj - Zj 0 0 0 -100 0 -200 0 -200

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.