OSCM 230Homework 02

Homework #2

Linear Programming (LP) Formulation

3-2. Let C = number of canvas backpacks produced. P, N, L defined similarly.

Objective:Maximize profit=(Canvas revenue – Canvas cost)*C + (Plastic revenue – Plastic cost)*P +

(Nylon revenue – Nylon cost)*N + (Leather revenue – Leather cost)*L

=Maximize $14.88C + $18.80P + $12.80N + $27.83L

Subject to:

2.25C /  / 200 / Canvas available
2.40P /  / 350 / Plastic available
2.10N /  / 700 / Nylon available
2.60L /  / 550 / Leather available
1.5C / + 1.5P /  / 90 / Canvas & Plastic labor
1.7N /  / 42.5 / Nylon labor
1.9 L /  / 80 / Leather labor
C, / P, / N, / L /  / 40 / Max production
C, / P, / N, / L /  / 15 / Min production

Solution: See File P3-2.XLS.

Produce 20 Canvas, 40 Plastic, 25 Nylon, and 40 Leather backpacks. Profit = $2,483.58.

3-5. Let C = number of cheese pizzas to order. P and V defined similarly.

Objective: Maximize profit = $1.45C + $1.75P + $1.98V

Subject to:

C

/

+ P

/ + V /  / 350 / Total pizzas
C /  / 120 / Max cheese
P /  / 150 / Max pepperoni
V /  / 100 / Max vegetarian

C

/  / 0.2(C+P+V) / Min cheese
P /  / 0.5(C+P+V) / Min pepperoni
C, / P, /

V

/  / 0Non-negativity

Solution: See file P3-5.XLS.

Order 60 cheese, 150 pepperoni, and 90 vegetarian pizzas. Profit = $527.70.

3-6.Let C = number of Chaunceys mixed. S, B, and R defined similarly.

Objective: Maximize total drinks = C + S + B + R

Subject to

1C + 4B  64(bourbon limit, oz)

1C + 1S  38(brandy limit oz)

1C + 3R  70(vodka limit oz)

1S +1R  30(dry vermouth limit oz)

1C + 2S  40(sweet vermouth limit oz)

C, S, B, R  0

Solution: See file P3-6.XLS.

Mix 16 Chaunceys, 12 Sweet Italians, 12 Bourbon on the rocks, and 18 Russian martinis.

Total = 58 drinks.

3-18. Let Xi= number of workers starting work at period i (with i= 1, 2, 3, 4, 5, or 6)

Objective: Minimize staff size = X1 + X2 + X3 + X4 + X5 + X6

Subject to:

X1 + X2 12

X2 + X3 16

X3 + X4 9

X4 + X5 11

X5 + X6 4

X1 + X6 3

All variables  0

Solution: See file P3-18.XLS.

Hire 30 workers. 12 start at 7am, 4 start at 11am, 10 start at 3pm, 1 starts at 7pm, and 3 start at 11pm. There are multiple optimal solutions.

3-29. Let Xij= acres of crop i planted on parcel j where i= 1 for wheat, 2 for alfalfa, 3 for barley, and j = 1 to 5 for SE, N, NW, W, and SW parcels.

Objective:Maximize total profit= Wheat profit + Alfalfa profit + Barley profit

Wheat profit = $2/bushel*(50 bushels/acre)*(X11+ X12+ X13 + X14 + X15)

Alfalfa profit = $40/ton*(1.5 tons/acre)*(X21+ X22+ X23 + X24 + X25)

Barley profit = $50/ton*(2.2 tons/acre)*(X31+ X32+ X33 + X34 + X35)

Subject to:

Irrigation limits:

1.6X11 + 2.9X21 + 3.5X31 3,200(acre-feet in SE)

1.6X12 + 2.9X22 + 3.5X32 3,400(acre-feet in N)

1.6X13 + 2.9X23 + 3.5X33 800(acre-feet in NW)

1.6X14 +2.9X24 + 3.5X34 500(acre-feet in W)

1.6X15 + 2.9X25 + 3.5X35 600(acre-feet in SW)

1.6X11 + 2.9X21 + 3.5X31 + 1.6X12 + 2.9X22 +

3.5X32 + 1.6X13 + 2.9X23 + 3.5X33 +1.6X14 +

2.9X24 + 3.5X34 + 1.6X15 + 2.9X25 + 3.5X35 7,400(water acre-feet total)

Sales limits:

X11+ X12+ X13 + X14 + X15  2,200(wheat in acres)

X21+ X22+ X23 + X24 + X25 1,200(alfalfa in acres)

X31+ X32+ X33 + X34 + X35 1,000(barley in acres)

Acreage availability:

X11 + X21 + X31 2,000(acres in SE parcel)

X12 + X22 + X32 2,300(acres in N parcel)

X13 + X23 + X33 600(acres in NW parcel)

X14 +X24 + X34 1,100(acres in W parcel)

X15 + X25 + X35 500(acres in SW parcel)

All variables  0

Solution: See file P3-29.XLS. Multiple optimal solutions exist.

Plant 1,762.50 acres of Wheat in SE, 437.50 acres of Wheat in N, 131.03 acres of Alfalfa in SE, 771.43 acres of Barley in N, and 228.57 acres of Barley in NW. Profit = $337,862.07.

3-34. Let A = pounds of oat product per horse each day, G = pounds of enriched grain per horse each day, and M = pounds of mineral product per horse each day

Objective: Minimize cost = 0.09A + 0.14G + 0.17M

Subject to:

2A + 3G +1M  6(ingredient A)

0.5 A +1G +0.5M  2(ingredient B)

3A +5G +6M  9(ingredient C)

1A +1.5 G +2M  8(ingredient D)

0.5A + 0.5G +1.5 M  5(ingredient E)

A +G +M  5(maximum feed/day)

A, G, M  0(non-negativity)

Solution: See file P3-34.XLS.

Oat / Grain / Mineral
Number of pounds / 1.333 / 0.000 / 3.333
Cost / $0.09 / $0.14 / $0.17 / $0.69

3-42.Let Xi = no. of trained technicians available at start of month i, and Yi = no. of trainees beginning in month i, where i= 1 (August), 2 (September), 3 (October), 4 (November), and 5 (December)

Objective: Minimize total salaries paid = $4,500*(X1 + X2 + X3 + X4 + X5) + $2,000*(Y1 + Y2 + Y3 + Y4 + Y5)

Subject to:

130X1 - 90Y1 40,000(Aug. need, hours)

130X2 - 90Y2 45,000(Sept. need, hours)

130X3 - 90Y3 35,000(Oct. need, hours)

130X4 - 90Y4 50,000(Nov. need, hours)

130X5 - 90Y5 45,000(Dec. need, hours)

X1 = 350(starting staff on Aug. 1)

X2 =X1 +Y1 - 0.02X1(staff on Sept. 1)

X3 =X2 +Y2 - 0.02X2(staff on Oct. 1)

X4 =X3 +Y3 - 0.02X3(staff on Nov. 1)

X5 =X4 +Y4 - 0.02X4(staff on Dec. 1)

All variables  0

Solution: See file P3-42.XLS.

Tech Aug / Tech Sept / Tech Oct / Tech Nov / Tech Dec / Train Aug / Train Sep / TrainOct / Train Nov / Train Dec
Number / 350.00 / 346.15 / 339.23 / 384.62 / 376.92 / 3.15 / 0.00 / 52.17 / 0.00 / 0.00
Salary / $4,500 / $4,500 / $4,500 / $4,500 / $4,500 / $2,000 / $2,000 / $2,000 / $2,000 / $2,000 / $8,196,800

3-45*. Let M = number of medical patients, S = number of surgical patients

Objective: Maximize revenue = $2,280M + $1,515S

Subject to

8M + 5S  32,850(patient-days available= 365 days x 90 new beds)

3.1M + 2.6S  15,000(lab tests)

1M + .2S  7,000(x-rays)

S  2,800(operations/surgeries)

M, S  0(non-negativity)

Solution: See file P3-45.XLS.

M = 2,791 medical patients and S = 2,105 surgical patients. Revenue = $9,551,659 per year

To convert M and S to number of medical versus surgical beds, find the total number of hospital days for each type of patient:

Medical = (2,791 patients)(8 days/patient) = 22,328 days

Surgical = (2,105 patients)(5 days/patient) = 10,525 days

Total = 32,853 days

This represents 68% medical days and 32% surgical days, which yields 61 medical beds and 29 surgical beds. (Note that an alternative approach would be to formulate the model with M, S as number of beds.)

3-20*. Let Xi= number of technicians reporting for start of work at period i(with i= 1, 2, 3, or 4)

Objective: Minimize salaries paid = 2($756X1 + $840X2 + $882X3 + $924X4)

Note: Salaries are doubled because there are two crews for each schedule.

Subject to:

X1 + X4 10

X1 + X2 6

X2 + X3 12

X3 + X4 8

All variables  0

Solution: See file P3-20.XLS.

A and A (alt) / B and B (alt) / C and C (alt) / D and D (alt)
Number assigned / 10.00 / 4.00 / 8.00 / 0.00
Pay / $1,512.0 / $1,680.0 / $1,764.0 / $1,848.0 / $35,952.00

3-21*. The airline must assign two types of workers to four different shifts. Therefore, there are eight decision variables, one for each worker/shift combination.

(a) Objective: Minimize total number of agents hired = sum of all eight decision variables.

There are sixteen constraints: five regarding the minimum total number of agents required during each time period, five regarding the minimum number of English-only agents required during each time period, five regarding the minimum number of bilingual agents required during each time period, and non-negativity.

Solution: See file P3-21.XLS, sheet (a).

English A / English B / English C / English D / Bilingual A / Bilingual B / Bilingual C / Bilingual D
Number assigned / 6.00 / 7.00 / 9.00 / 9.00 / 6.00 / 1.00 / 3.00 / 3.00
Total agents / 1 / 1 / 1 / 1 / 1 / 1 / 1 / 1 / 44.00

(b) Objective: Minimize salaries paid = 19(A1 + B1 + C1 + D1)+23(A2 + B2 + C2 + D2)

Subject to: Same constraints as for part (a).

Solution: See file P3-21.XLS, sheet (b).

English A / English B / English C / English D / Bilingual A / Bilingual B / Bilingual C / Bilingual D
Number assigned / 12.00 / 3.00 / 9.00 / 9.00 / 4.00 / 1.00 / 3.00 / 3.00
Pay / $19 / $19 / $19 / $19 / $23 / $23 / $23 / $23 / $880

Note that the total number of agents needed is the same in both cases.

3-38*. There are two types of oils and three grades of oil blends. Hence, there are six decision variables corresponding to the six oil/grade combinations (e.g., gallons of Italian oil used in Commercial).

Objective: Minimize cost = $5.75*(total Italian oil used) + $6.50*(total Spanish oil used)

There are six constraints.

1 each for the demand for a particular grade3

Percentage of Italian in Commercial1

Percentage of Spanish in Virgin1

Non-negativity1

Solution: See file P3-38.XLS.

Ital in Comm / Ital in Virgin / Ital in Extra / Span in Comm / Span in Virgin / Span in Extra
Number of gallons / 245.00 / 2,200.00 / 630.00 / 455.00 / 0.00 / 770.00
Cost / $5.75 / $5.75 / $5.75 / $6.50 / $6.50 / $6.50 / $25,643.75

Page 1 of 6