Formulating IPs

1
2
 Formulating IPs

Dorian Auto Manufacturing

Dorian Auto is considering manufacturing three types of autos: compact, midsize,

and large. The resources required for, and the profits yielded by, each type of car are
shown in Table. Currently, 6,000 tons of steel and 60,000 hours of labor are
available. For production of a type of car to be economically feasible, at least 1,000
cars of that type must be produced. Formulate an IP to maximize Dorian’s profit.

3
 Formulating IPs
Dorian Auto Manufacturing
• Dorian Auto is considering manufacturing three types of autos: compact, midsize, and
large.
• The resources required for, and the profits yielded by each type of car are shown.
Currently, 6,000 tons of steel and 60,000 hours of labor are available.
• For production of a type of car to be economically feasible, at least 1,000 cars of that
type must be produced.
• Formulate an IP to maximize Dorian’s profit.

4 4
Formulating IPs

5 5
Formulating IPs

6 6
 Formulating IPs

If constraint for f(x) is satisfied, constraint for g(x) is also satisfied. If f(x) is not satisfied,
g(x) may or may not be satisfied. →

7 7
 Formulating IPs

Suppose we add the following constraint to the Nickles lockbox problem: If customers
in region 1 send their payments to city 1, then no other customers may send their
payments to city 1.

8
 Formulating IPs

Gandhi Cloth Company is capable of manufacturing three types of clothing: shirts,

shorts, and pants. The manufacture of each type of clothing requires that Gandhi have
the appropriate type of machinery available. The machinery needed to manufacture
each type of clothing must be rented at the following rates: shirt machinery, $200 per
week; shorts machinery, $150 per week; pants machinery, $100 per week. The
manufacture of each type of clothing also requires the amounts of cloth and labor
shown in Table 2. Each week, 150 hours of labor and 160 sq yd of cloth are available.
The variable unit cost and selling price for each type of clothing are shown in Table 3.
Formulate an IP whose solution will maximize Gandhi’s weekly profits.

9
 Formulating IPs

✓ Gandhi Cloth Company is manufacturing shirts, shorts, and pants.

✓ The machinery needed to manufacture each type of clothing must be rented.
Shirts machinery cost $200 per week; shorts machinery: $150 per week, pants
machinery: $100 per week.
✓ The manufacture of each type of clothing also requires the amounts of cloth and
labor shown in Table 2.
✓ Each week, 150 hours of labor and 160 sq yd of cloth are available.
✓ The variable unit cost and selling price for each type of clothing are shown in
Table 3.
✓ Formulate an IP whose solution will maximize Gandhi’s weekly profits.

10
Formulating IPs

11
Formulating IPs

12
 Formulating IPs

Fixed
Variable Cost
Cost

Optimal solution

13
Blending Problem 2:
SUNCO OIL’s problem

14
 SUNCO OIL’s problem
Sunco Oil manufactures three types of gasoline (gas 1, gas 2, and gas 3). Each type is
produced by blending three types of crude oil (crude 1, crude 2, and crude 3). The sales
price per barrel of gasoline and the purchase price per barrel of crude oil are given in Table.
Sunco can purchase up to 5,000 barrels of each type of crude oil daily.

The three types of gasoline differ in their octane rating and sulfur content. The crude oil
blended to form gas 1 must have an average octane rating of at least 10 and contain at most
1% sulfur. The crude oil blended to form gas 2 must have an average octane rating of at least
8 and contain at most 2% sulfur. The crude oil blended to form gas 3 must have an octane
rating of at least 6 and contain at most 1% sulfur. The octane rating and the sulfur content of
the three types of oil are given in Table. It costs $4 to transform one barrel of oil into one
barrel of gasoline, and Sunco’s refinery can produce up to 14,000 barrels of gasoline daily.

Sunco’s customers require the following amounts of each gasoline: gas 1—3,000 barrels per
day; gas 2—2,000 barrels per day; gas 3—1,000 barrels per day. The company considers it
an obligation to meet these demands. Sunco also has the option of advertising to stimulate
demand for its products. Each dollar spent daily in advertising a particular type of gas
increases the daily demand for that type of gas by 10 barrels. For example, if Sunco decides
to spend $20 daily in advertising gas 2, then the daily demand for gas 2 will increase by
20(10) 200 barrels. Formulate an LP that will enable Sunco to maximize daily profits
(profits revenues costs). 15
 SUNCO OIL’s problem
• Sunco Oil manufactures three types of gasolines (gas 1, gas 2 and gas 3) by
blending three types of crude oil (crude 1, crude 2 and crude 3).
• The sales and purchase prices :

Sales Price per Barrel ($) Purchase Price per Barrel ($)
Gas Crude
1 70 1 45
2 60 2 35
3 50 3 25

• Gasoline types differ in their octane rating and sulfur content:

– Gas 1 (2) [3] must have an average octane rating of at least 10 (8) [6] and contain at
most 1 (2) [1]% sulfur.

Crude Octane Rating Sulfur Content(%)

1 12 0.5
2 6 2.0
3 8 3.0
16
 SUNCO OIL’s problem
• It costs $4 to convert one barrel of oil into one barrel of gasoline.

• Sunco’s refinery can produce up to 14,000 barrels daily.

• Sunco must meet the demand:

– Gas 1: 3,000 barrels per day
– Gas 2: 2,000 barrels per day
– Gas 3: 1,000 barrels per day

• Sunco also has the option of advertising to stimulate demand: Assume

that each $ spent daily in advertising for a particular type of gas increases
the demand by 10 barrels.

• For each crude oil type, the maximum amount that can be purchased is
5000 barrels daily.
17
 Decision variables

• ai: dollars spent daily on advertising gas i, for i=1,2,3

• xij: barrels of crude oil j used daily to produce gas i, for

i=1,2,3 and j=1,2,3.

– Barrels of crude 2 used daily: x12 + x22 + x32

– Barrels of gas 3 produced daily: x31 + x32 + x33

• To simplify, assume that gasoline cannot be stored.

18
 Objective function: Max Profit
Daily revenues from gas sales:
70(x11 + x12 + x13)+ 60(x21 + x22 + x23)+ 50(x31 + x32 + x33)
Gas 1 Gas 2 Gas 3
Daily cost of purchasing crude oil:
45(x11 + x21 + x31)+ 35(x12 + x22 + x32)+ 25(x13 + x23 + x33)
Oil 1 Oil 2 Oil 3
Daily advertising costs:
a1 + a2 + a3

Daily production costs:

4(x11 + x12 + x13 + x21 + x22 + x23 + x31 + x32 + x33)

OBJECTIVE FUNCTION :
Max z = (70-45-4) x11+ … + (50-25-4) x33 – (a1 + a2 + a3)

19
SUNCO OIL’s problem: Constraints

20
 SUNCO OIL’s problem: Constraints

• Gas 1 produced daily should be equal to its demand.

• Daily demand for gas 1 = 3,000 + demand generated by ads

• demand generated by ads = (10 units / $ spent) * $ spent
=10 a1

x11 + x12 + x13 = 3,000 + 10 a1

x11 + x12 + x13 -10 a1 =3,000

x21 + x22 + x23 -10 a2 = 2,000
x31 + x32 + x33 -10 a3 = 1,000

21
 SUNCO OIL’s problem: Constraints

• Upper bound (5,000) on the purchased amount of crude oil:

x11 + x21 + x31 ≤ 5,000
x12 + x22 + x32 ≤ 5,000
x13 + x23 + x33 ≤ 5,000

• Refinery capacity (14,000 barrels):

x11 + x12 + x13 + x21 + x22 + x23 + x31 + x32 + x33 ≤ 14,000

22
 SUNCO OIL’s problem: Constraints
Average octane levels (at least 10, 8 and 6 required for gas 1, 2 and 3):
• If we blend 2 barrels of crude oil 1, 3 barrels of 2, and 1 barrel of 3:
(total octane)/(#barrels)=(12*2+6*3+8*1)/(2+3+1)=50/6

• Similarly, we have
(12 x11 + 6 x12 + 8 x13 ) / (x11 + x12 + x13 ) ≥ 10
12 x11 + 6 x12 + 8 x13 ≥ 10 (x11 + x12 + x13 )

2 x11 - 4 x12 – 2 x13 ≥ 0

4 x21 - 2 x22 ≥0
6 x31 + 2 x33 ≥ 0 →Redundant since x31, x33 ≥ 0 (so no need for the last one)

Crude Octane Rating Sulfur Content(%)

1 12 0.5
2 6 2.0
3 8 3.0 23
 SUNCO OIL’s problem: Constraints

% of sulfur (at most 1%, 2% and 1% required for gas 1, 2 and 3):
• (total sulfur)/(#barrels) ≤ threshold
(.005 x11 + .02 x12 + .03 x13 ) / (x11 + x12 + x13 ) ≤ 0.01

-0.005 x11 + 0.01 x12 + 0.02 x13 ≤ 0

-0.015 x22 + 0.01 x23 ≤ 0
-0.005 x31 + 0.01 x32 + 0.02 x33 ≤ 0

• Nonnegativity: xij, ai ≥ 0
Crude Octane Rating Sulfur Content(%)
1 12 0.5
2 6 2.0
3 8 3.0
24
 Complete LP Model
Max z=21x11 + 11x12 + x13 + 31x21 + 21x22 + 11x23 + 41x31 + 31x32 + 21x33 - a1- a2-a3

s.t.
x11 + x12 + x13 -10 a1 =3,000 x11 + x21 + x31 ≤ 5,000
x21 + x22 + x23 -10 a2 = 2,000 x12 + x22 + x32 ≤ 5,000
x31 + x32 + x33 -10 a3 = 1,000 x13 + x23 + x33 ≤ 5,000
x11 + x12 + x13 + x21 + x22 + x23 + x31 + x32 + x33 ≤ 14,000

2 x11 - 4 x12 – 2 x13 ≥ 0

4 x21 - 2 x22 ≥0
-0.005 x11 + 0.01 x12 + 0.02 x13 ≤ 0
- 0.015 x22 + 0.01 x23 ≤ 0
-0.005 x31 + 0.01 x32 + 0.02 x33 ≤ 0

xij, ai ≥ 0 for all i=1,2,3 j=1,2,3

25
 Optimal Solution
x11=2222.22
• 3000 barrels of gas 1
x12=444.44
x13=333.33
x21=2111.11 • 9500 barrels of gas 2
x22=4222.22
x23=3166.67
x31=666.67
• 1000 barrels of gas 3
x32=333.33
x33=0
a1=0
a2=750 • Advertise only on gas 2

a3=0
z=277,750 26