Linear Programming Applications
Chapter 4
Linear Programming Applications
1. Media Selection
a.Letx1 = number of TV ads to place
x2 = number of radio ads to place
x3 = number of newspaper ads to place
Max / 100,000x1 / + / 18,000x2 / + / 40,000x3s.t.
2,000x1 / + / 300x2 / + / 600x3 / / 18,200 / Advertising Budget
x1 / / 10 / Max TV
x2 / / 20 / Max Radio
x3 / / 10 / Max News
-0.5x1 / + / 0.5x2 / - / 0.5x3 / / 0 / Max 50% Radio
0.9x1 / - / 0.1x2 / - / 0.1x3 / / 0 / Min 10% TV
x1, x2, x3, 0
Budget $Solution: / x1 = 4 / $8,000
x2 = 14 / 4,200
x3 = 10 / 6,000
$18,200 / Audience = 1,052,000.
This information can be obtained from Storm as follows.
bubba - problem 4.1
OPTIMAL SOLUTION - DETAILED REPORT
Variable Value Cost Red. cost Status
1 TV ADS 4.0000 100000.0000 0.0000 Basic
2 RADIO ADS 14.0000 18000.0000 0.0000 Basic
3 NEWSP ADS 10.0000 40000.0000 0.0000 Basic
Slack Variables
4 ADV BUDGET 0.0000 0.0000 -51.3043 Lower bound
5 TV MAX 6.0000 0.0000 0.0000 Basic
6 RADIO MAX 6.0000 0.0000 0.0000 Basic
7 NEWSP MAX 0.0000 0.0000 -11826.0900 Lower bound
8 RAD 50%MX 0.0000 0.0000 -5217.3910 Lower bound
9 TV 10%MN 1.2000 0.0000 0.0000 Basic
Objective Function Value = 1052000
bubba - problem 4.1
OPTIMAL SOLUTION - DETAILED REPORT
Constraint Type RHS Slack Shadow price
1 ADV BUDGET <= 18200.0000 0.0000 51.3043
2 TV MAX <= 10.0000 6.0000 0.0000
3 RADIO MAX <= 20.0000 6.0000 0.0000
4 NEWSP MAX <= 10.0000 0.0000 11826.0900
5 RAD 50%MX <= 0.0000 0.0000 5217.3910
6 TV 10%MN >= 0.0000 1.2000 0.0000
Objective Function Value = 1052000
bubba - problem 4.1
SENSITIVITY ANALYSIS OF COST COEFFICIENTS
Current Allowable Allowable
Variable Coeff. Minimum Maximum
1 TV ADS 100000.0000 -18000.0000 120000.0000
2 RADIO ADS 18000.0000 15000.0000 6.2500E+35
3 NEWSP ADS 40000.0000 28173.9100 6.2500E+35
bubba - problem 4.1
SENSITIVITY ANALYSIS OF RIGHT-HAND SIDE VALUES
Current Allowable Allowable
Constraint Type Value Minimum Maximum
1 ADV BUDGET <= 18200.0000 14750.0000 32000.0000
2 TV MAX <= 10.0000 4.0000 Infinity
3 RADIO MAX <= 20.0000 14.0000 Infinity
4 NEWSP MAX <= 10.0000 0.0000 10.0000
5 RAD 50%MX <= 0.0000 -8.0500 2.9362
6 TV 10%MN >= 0.0000 -Infinity 1.2000
b.The shadow price for the advertising budget constraint is 51.3043. Thus, a $100 increase in budget ($18,300 is within the allowable range of RHS for constraint 1) should provide an increase in audience coverage of approximately 5,130.
3. Investment and Loan Planning
x1 = $ to invest in automobile loans
x2 = $ to invest in furniture loans
x3 = $ to invest in other secured loans
x4 = $ to invest in signature loans
x5 = $ to invest in "risk free" securities
Max / 0.08x1 / + / 0.10x2 / + / 0.11x3 / + / 0.12x4 / + / 0.09x5s.t.
x5 / / 600,000 / [1]
x4 / / 0.10(x1 + x2 + x3 + x4)
or / -0.10x1 / - / 0.10x2 / - / 0.10x3 / + / 0.90x4 / / 0 / [2]
x2 / + / x3 / / x1
or / - x1 / + / x2 / + / x3 / / 0 / [3]
x3 / + / x4 / / x5
or / + / x3 / + / x4 / - / x5 / / 0 / [4]
x1 / + / x2 / + / x3 / + / x4 / + / x5 / = / 2,000,000 / [5]
x1, x2, x3, x4, x5 0
Solution:
Automobile Loans / (x1) / = / $630,000Furniture Loans / (x2) / = / $170,000
Other Secured Loans / (x3) / = / $460,000
Signature Loans / (x4) / = / $140,000
Risk Free Loans / (x5) / = / $600,000
Annual Return $188,800 (9.44%)
bubba - Problem 4.3
OPTIMAL SOLUTION - DETAILED REPORT
Variable Value Cost Red. cost Status
1 AUTO LOANS 630000.0000 0.0800 0.0000 Basic
2 FURN LOANS 170000.0000 0.1000 0.0000 Basic
3 OTH SEC L 460000.0000 0.1100 0.0000 Basic
4 SIGN LOANS 140000.0000 0.1200 0.0000 Basic
5 SECURITIES 600000.0000 0.0900 0.0000 Basic
Slack Variables
6 CONSTR 1 0.0000 0.0000 -8.0000E-03 Lower bound
7 CONSTR 2 0.0000 0.0000 -0.0200 Lower bound
8 CONSTR 3 0.0000 0.0000 -0.0100 Lower bound
9 CONSTR 4 0.0000 0.0000 -1.0000E-02 Lower bound
Objective Function Value = 188800
bubba - Problem 4.3
OPTIMAL SOLUTION - DETAILED REPORT
Constraint Type RHS Slack Shadow price
1 CONSTR 1 <= 600000.0000 0.0000 8.0000E-03
2 CONSTR 2 <= 0.0000 0.0000 0.0200
3 CONSTR 3 <= 0.0000 0.0000 0.0100
4 CONSTR 4 <= 0.0000 0.0000 1.0000E-02
5 AMT TO INV = 2000000.0000 0.0000 0.0920
Objective Function Value = 188800
4. Quality Assurance
a.x1 = pounds of bean 1 to use in coffee blend
x2 = pounds of bean 2 to use in coffee blend
x3 = pounds of bean 3 to use in coffee blend
Min / 0.50x1 / + / 0.70x2 / + / 0.45x3s.t.
/ / 75
or / 10x2 - 15x3 / / 0 / Aroma
/ / 80
or / 6x1 / + / 8x2 / - / 5x3 / / 0 / Taste
x1 / / 500 / Bean 1
x2 / / 600 / Bean 2
x3 / / 400 / Bean 3
x1 / + / x2 / + / x3 / = / 1000 / 1000 pounds
x1, x2, x3 0
Refer to Storm output below.
Optimal Solution: x1 = 500, x2 = 300, x3 = 200
Optimal Cost: $550 (minimum cost)
b.Cost per pound = $550/1000 = $0.55
c.Surplus for aroma: s1 = 0; thus aroma rating = 75
Surplus for taste: s2 = 4400; thus taste rating = 80 + (4400/1000) = 84.4
d.Shadow price = 0.60. An additional pound of coffee can be produced at a cost of $0.60 per pound.
bubba - Problem 4.4
OPTIMAL SOLUTION - DETAILED REPORT
Variable Value Cost Red. cost Status
1 BEAN 1 500.0000 0.5000 0.0000 Basic
2 BEAN 2 300.0000 0.7000 0.0000 Basic
3 BEAN 3 200.0000 0.4500 0.0000 Basic
Slack Variables
4 AROMA RTG 0.0000 0.0000 0.0100 Lower bound
5 TASTE RTG 4400.0000 0.0000 0.0000 Basic
6 BEAN 1 AVL 0.0000 0.0000 0.1000 Lower bound
7 BEAN 2 AVL 300.0000 0.0000 0.0000 Basic
8 BEAN 3 AVL 200.0000 0.0000 0.0000 Basic
Objective Function Value = 550
bubba - Problem 4.4
OPTIMAL SOLUTION - DETAILED REPORT
Constraint Type RHS Slack Shadow price
1 AROMA RTG >= 0.0000 0.0000 0.0100
2 TASTE RTG >= 0.0000 4400.0000 0.0000
3 BEAN 1 AVL <= 500.0000 0.0000 -0.1000
4 BEAN 2 AVL <= 600.0000 300.0000 0.0000
5 BEAN 3 AVL <= 400.0000 200.0000 0.0000
6 COFF NEED = 1000.0000 0.0000 0.6000
Objective Function Value = 550
5. Blending Problem
Letx1 = amount (in ounces) of ingredient A per gallon of fuel
x2 = amount (in ounces) of ingredient B per gallon of fuel
x3 = amount (in ounces) of ingredient C per gallon of fuel
Min / 0.10x1 / + / 0.03x2 / + / 0.09x3s.t.
1x1 / + / 1x2 / + / 1x3 / / 10 / [1]
1x1 / + / 1x2 / + / 1x3 / / 15 / [2]
1x1 / / 1x2
or / 1x1 / - / 1x2 / / 0 / [3]
1x3 / / 1/2x1
or / -1/2x1 / + / 1x3 / / 0 / [4]
x1, x2, x3 0
Refer to Storm output below.
Optimal Solution: x1 = 4, x2 = 4, x3 = 2
Optimal Cost = $0.70 per gallon.
bubba - Problem 4.5
OPTIMAL SOLUTION - DETAILED REPORT
Variable Value Cost Red. cost Status
1 INGR A 4.0000 0.1000 0.0000 Basic
2 INGR B 4.0000 0.0300 0.0000 Basic
3 INGR C 2.0000 0.0900 0.0000 Basic
Slack Variables
4 CONSTR 1 0.0000 0.0000 0.0700 Lower bound
5 CONSTR 2 5.0000 0.0000 0.0000 Basic
6 CONSTR 3 0.0000 0.0000 0.0400 Lower bound
7 CONSTR 4 0.0000 0.0000 0.0200 Lower bound
Objective Function Value = 0.7
bubba - Problem 4.5
OPTIMAL SOLUTION - DETAILED REPORT
Constraint Type RHS Slack Shadow price
1 CONSTR 1 >= 10.0000 0.0000 0.0700
2 CONSTR 2 <= 15.0000 5.0000 0.0000
3 CONSTR 3 >= 0.0000 0.0000 0.0400
4 CONSTR 4 >= 0.0000 0.0000 0.0200
Objective Function Value = 0.7