Winston Chapter 4.2, Page 133, Number 3 (Linear Programming)



 /  / 1

Problem Statement: Widgetco produces two products: 1 and 2. Each requires the amounts of raw material and labor, and sells for the price given in Table 3. Up to 350 units of raw material can be purchased at $2.00 per unit, while up to 400 hours of labor can be purchased at $1.50 per hour. To maximize profit, Widgetco must solve the following LP:

o.f. Max z = 2x1 + 2.5x2

s.t. x1 + 2x2 £ 350 (Raw material)

2x1 + x2 £ 400 (Labor)

x1, x2 ³ 0

Here, xj = number of units of product i produced. Demonstrate the correspondence between corner points and basic feasible solutions.

Table 3:

Product 1

/ Product 2
Raw Material / 1 unit / 2 units
Labor / 2 hours / 1 hour
Sales Price / $7 / $8

A. Summarize the problem in a table format.

B. Formulate the problem. Explain your decision variables and details of your formulation.

C. Create the first simplex tableau for this problem. Solve manually using simplex method.

D. Write a report of your solution for a hypothetical manager. Use a language understandable to most people. Do not use mathematical abbreviations.

A. Problem Summarized in Table Format:

Sales Price / Raw Material, Units / Labor, Hours
Product 1, x1: / $7.00 / 1 / 2
Product 2, x2: / $8.00 / 2 / 1
Costs: / $2.00 per unit / $1.50 per hour
Constraints: / Up to 350 units / Up to 400 hours

B. Problem Formulation:

Decision Variables:

· x1 = Number of Units of Product 1, Positive

· x2 = Number of Units of Product 2, Positive

The decision variables, x1 and x2, are representative of the unknown number of units that are needed to be produced to maximize profit.

Objective Function: The author of this problem has already formulated the objective function.

o.f. Max Z = 2x1 + 2.5x2.

3. Constraints: There are two constraints for this problem. No more than 350 units of raw material can be used. Additionally, no more than 400 labor hours can be used.

s.t. x1 + 2x2 £ 350 (Raw material)

2x1 + x2 £ 400 (Labor)

x1, x2 ³ 0

4. Quant Input and Output:

Quant Input:

Free Format Model for 0133N03

> Max 2X1+ 2.5X2

>Subject to

> (1) 1X1+ 2X2 <= 350

> (2) 2X1+ 1X2 <= 400

Quant Output:

|------|

| Summarized Report for 0133N03 Page : 1 |

|------|

|------+------+------+------+------+------+------|

| 1 | X1 | +150.00000| 0 | +2.0000000| +1.2500000| +5.0000000|

| 2 | X2 | +100.00000| 0 | +2.5000000| +1.0000000| +4.0000000|

|------|

| Maximized OBJ = 550 Iteration = 2 Elapsed CPU second = 19.27344 |

|------|

| Summarized Report for 0133N03 Page : 2 |

|------|

|Constr.| Status | RHS | Price | Surplus | RHS | RHS |

|------+------+------+------+------+------+------|

| 1 | Tight | <+350.00000| +1.0000000| 0 | +200.00000| +800.00000|

| 2 | Tight | <+400.00000| +.50000000| 0 | +175.00000| +700.00000|

| 3 | Loose | >0 | 0 | +150.00000| - Infinity| +150.00000|

| 4 | Loose | >0 | 0 | +100.00000| - Infinity| +100.00000|

|------|

| Maximized OBJ = 550 Iteration = 2 Elapsed CPU second = 19.27344 |

|------|

C. Manual Solution:

Initial Simplex Tableau:
Elementary Row Operation / Z / x1 / x2* / S1 / S2 / RHS / BFS / Ratio
R0 / 1 / -2 / -2.5 / 0 / 0 / 0 / Z=0 / None / None
R1 / 0 / 1 / (2) / 1 / 0 / 350 / S1=350 / 350/2 / 175*
R2 / 0 / 2 / 1 / 0 / 1 / 400 / S2=400 / 400/1 / 400
Above, x2 has the least-most non-negative coefficient value for row zero, making it the entering variable. The ratio test suggests row one to be the pivot row. The pivot row and entering variable intersect to give the pivot term of 2. Elementary row operations are performed below so that x2 will have a basic feasible solution.
First Iteration:
Elementary Row Operation / Z / x1* / x2 / S1 / S2 / RHS / BFS / Ratio
(2.5)R1' + R0 ® R0' / 1 / -0.75 / 0 / 1.25 / 0 / 437.5 / Z=437.5 / None / None
(0.5)R1 ® R1' / 0 / 0.5 / 1 / 0.5 / 0 / 175 / X2=175 / 175/0.5 / 350
(-1.0)R1' + R2 ® R2' / 0 / (1.5) / 0 / -0.5 / 1 / 225 / S2=225 / 225/1.5 / 150*
Above, x1 has the least-most non-negative coefficient value for row zero, making it the entering variable. The ratio test suggests row two to be the pivot row. The pivot row and entering variable intersect to give the pivot term of 1.5. Elementary row operations are performed below so that x1 will have a basic feasible solution.
Second Iteration:
Elementary Row Operation / Z / x1 / x2 / S1 / S2 / RHS / Solution
(3/4)R2'' + R0' ® R0'' / 1 / 0 / 0 / 1 / 0.5 / 550 / Z=550
(-0.5)R2'' + R1' ® R1'' / 0 / 0 / 1 / 2/3 / -1/3 / 100 / x2=100
(2/3)R2' ® R2'' / 0 / 1 / 0 / -1/3 / 2/3 / 150 / x1=150
Above, there are no non-negative coefficients within row zero, indicating that the optimal solution for this linear program has been found.

D. Report for a Manager:

The results of this problem indicate that the maximum amount of profit to be made is $550.

Each unit of Product 1 manufactured requires the costs of raw materials and labor. Since 150 units are needed of Product 1, and Product 1 requires one unit of raw materials at $2.00 each and two units of labor at $1.50 each, the cost of 150 units would be $750.

As well, each unit of Product 2 manufactured has costs of raw materials and labor. Since 100 units are needed of Product 2, and Product 2 requires two units of raw materials at $2.00 each and one unit of labor at $1.50 each, the cost of 100 units would be $550.

The total manufacturing cost of these two products is $1,300.

Finally, if all 150 units of Product 1 are sold at $7.00 and all 100 units of Product 2 are sold at $8.00, the total cash receipts would equal $1,850.

Since the profit is equal to the difference between the cash receipts and the manufacturing cost, $1,850 - $1,300, the maximized profit for manufacturing and selling these products is $550.