University of Tunis Spring 2021

Tunis Business School

Linear Programming
Tutorial 1: Formulation

Problem1:
The Denver advertising agency, promoting the new Breem dishwashing detergent wants to get the best
exposure possible for the product within the $100,000 advertising budget ceiling placed on it. To do
so, the agency needs to decide how much of the budget to spend on each of its two most effective
media: (1) television spots during the afternoon hours and (2) large ads in the city’s Sunday
newspaper. Each television spot costs $3,000; each Sunday newspaper ad costs $1,250. The expected
exposure based on industry ratings, is 35,000 viewers for each TV commercial and 20,000 readers for
each newspaper advertisement. The agency director knows from experience that it is important to use
both media in order to reach the broadest spectrum of potential Breem customers. She decides that at
least 5 but no more than 25 television spots should be ordered, and that at least10 newspaper ads
should be contracted. How many times should each of the two media be used to obtain the maximum
exposure while staying within the budget?

Decision variables:
X1: number of tv spots
X2: number of newspaper ads
Model:
Max Z= 35000X1+20000X2
Subject to:
(Budget constraint)
3000X1+1250X2 <= 100000
(Restrictions on number of TV spots)
X1≥ 5
X1≤ 25
(Restriction on number of newspaper ads)
X2≥10
Integrality constraints:

X1, X2 ϵ Z+ (positive integers)

1
Problem2:
A farmer is seeking to determine the optimal mix of cereals that will give his animals the
adequate amount of nutrients (proteins, calories, and iron) and keep his budget low. The
table below details the quantity of each nutrient in each type of cereal and the cost of 1 kg of
each of the cereals.
Cereal Cor Wheat Barley Minimum required
Nutrients
n
Protein mg/kg 10 9 11 20 mg

Calories /kg 100 800 850 4000 cal

0
Iron mg/kg 9 8 7 12 mg

Cost /kg 0.55 0.47 0.45

Formulate the problem as a linear model to help the farmer decide on the quantities

Decision variables:
X1: number of kgs of corn
X2: number of kgs of wheat
X3: number of kgs of barley
Model:

Min Z= 0.55X1+0.45X2+0.45X3

Subject to:

(the mix of cereals must contain at least the required amount of each nutrient)

10X1+9X2+11X3 ≥ 20

1000X1+800X2+850X3 ≥ 4000

9X1+8X2+7X3 ≥ 12

(non-negativity constraints)

X1, X2, X3 ≥ 0

Compact form:

Decision variables:

2
Xi: the number of kgs of cereal i to buy

i= {1,2,3}

1: corn

2: wheat

3: barley

Parameters:

Costi: cost of 1 kg of cereal i

Pi: amount of protein in cereal i

Ci: number of calories in cereal i

Iri: amount of iron in cereal i

Model:

Min Z=

Subject to:

For xi , i in {1,2,3}:

Xi ≥ 0

Problem3:

3
Failsafe Electronics Corporation primarily manufactures four highly technical products, which
it supplies to aerospace firms that hold NASA contracts. Each of the products must pass
through the following departments before they are shipped: wiring, drilling, assembly, and
inspection. The time requirements in each department (in hours) for each unit produced and
its corresponding profit value are summarized in this table:

Product Wiring Drilling Assembly Inspection Unit Profit

XJ201 0.5 3 2 0.5 $9
XM897 1.5 1 4 1.0 $12
TR29 1.5 2 1 0.5 $15
BR788 1.0 3 2 0.5 $11

The production time available in each department each month and the minimum monthly
production requirement to fulfill contracts are as follows:

Department Capacity (hours) Product Minimum Production

Level
Wiring 1,500 XJ201 150
Drilling 2,350 XM897 100
Assembly 2,600 TR29 200
Inspection 1,200 BR788 400

Formulate this production-mix situation as a Linear Program

Decision variables:
Xi: number of units of product i to make, i ={1,2,3,4}
Model:
Max Z= 9X1+12X2+15X3+11X4
Subject to:
Capacity constraints
0.5X1+1.5X2+1.5X3+1X4 ≤ 1500
3X1+X2+2X3+3X4 ≤ 2350
2X1+4X2+X3+2X4≤ 2600
0.5X1+X2+0.5X3+0.5 X4 ≤ 1200
Demand constraints
X1≥ 150
X2≥ 100
X3≥200
X4≥ 400
X1, X2, X3 and X4 are positive integers
4
Compact form
Decision variables:
Xi: number of units of product i to make, i = {1,2,3,4}
Parameters:
n: number of products
m: number of departments

profiti: profit of 1 unit of product i

capacityj: capacity of department j in hours
Demandi : demand of product i
Requirementij : requirement of product i in department j

Max Z= 9X1+12X2+15X3+11X4 Max Z=

Subject to: Subject to:
Capacity constraints For j=1..4
0.5X1+1.5X2+1.5X3+1X4 ≤ 1500
3X1+X2+2X3+3X4 ≤ 2350
2X1+4X2+X3+2X4≤ 2600 For i=1,..,4:
0.5X1+X2+0.5X3+0.5 X4 ≤ 1200
Xi ≥ Demandi
Demand constraints
X1≥ 150
For i=1,..4:
X2≥ 100 Xi are positive integers
X3≥200
X4≥ 400
X1, X2, X3 and X4 are positive integers

Problem4: (additional problem)

5
 An investor has $300,000 that can be invested. In addition to the money at hand, it is possible to
borrow up to $100,000 at 12% interest. This money can be used for leveraging (borrow to invest). The
investor has six alternatives, shown in Table 1. The table also shows the expected annual interest or
dividend for the investment alternatives, the expected annual increase of the value of the investment,
and an indication of the risk of the investment (per dollar).

Investment Type Exp annual interest/dividend Exp annual increase in value Average risk/dollar
Real estate 0% 18% 20
Silver 0% 10% 12
Savings account 2% 0% 1
Blue chips stocks 3% 6% 7
Bonds 4% 0% 3
Hi-tech stocks 0% 20% 30
Table 1: investment alternatives and related results

The investor attempts to maximize the expected value of the assets at the end of the planning period
(one year). The value of the assets after one year equals today’s value of the investment plus the
expected interest or dividend plus the expected change in value within a year minus the amount of
money that was borrowed (principal and interest). In addition to the restricted availability of money
already mentioned above, the decision maker faces the following constraints:

 The expected value of assets (exclusive interest) at the end of the planning period should be at
least 7% higher than at the beginning,
 Invest at least 50% of all the money invested in stocks and bonds combined,
 Invest no more than 20% of total amount available (excluding the amount borrowed) in real estate
and silver combined
 The average risk of the portfolio should not exceed 10.
Formulate the problem as a linear program.
Model:
Decision variables:
Xi : the amount of money invested in investment type i
Y: the amount to borrow
Parameters:
Inti: Exp annual interest/dividend
Value_increasei:

Riski

Model:

Max Z= (∑i Xi *(1+ Inti + Value_increasei)) – (1+0.12)*Y

Subject to:

∑i Xi -y <= 300,000
Y<=100,000

 The expected value of assets (exclusive interest) at the end of the planning period should be at
least 7% higher than at the beginning,

6
∑i Xi(1+ Inti + value_increase_i ) >= 1.07*∑i Xi
 Invest at least 50% of all the money invested in stocks and bonds combined,
X4+X5+X6 >= 0.5*∑i Xi

 Invest no more than 20% of total amount available (excluding the amount borrowed) in real estate
and silver combined
X1+X2<= 0.2*300,000

 The average risk of the portfolio should not exceed 10.

∑i Xi*Riski <= 10*∑i Xi

Non-negativity constraints:
For all i , Xi >= 0

Problem5 (additional question):

A Company sells bags of oranges and cartons of orange juice. The company grades oranges on a scale
of 1 (poor) to 10 (excellent). The company now has on hand 100,000 lb of grade 9 oranges and
120,000 lb of grade 6 oranges. The average quality of oranges sold in bags must be at least 7, and the
average quality of the oranges used to produce orange juice must be at least 8. Each pound of oranges
that is used for juice yields a revenue of $1.50 and incurs a variable cost (consisting of labor costs,
variable overhead costs, inventory costs, and so on) of $1.05. Each pound of oranges sold in bags
yields revenue of 50¢ and incurs a variable cost of 20¢. Formulate an LP to help maximize the
company’s profit.

Decision variables:
Xij: the quantity of oranges in lbs of grade i to be used in product j
Where i =1,..10 and j=1,2
Parameters
Profitj= revenuej – costsi
Availablei
Gradei = average grade of oranges
Requiredj= the average required quality of oranges in product j

Model:
Objective function:
Max z= ∑ij Xij* profit j
Problem6:

7
 A company manufactures 4 mixtures: M1, M2, M3 and M4 using three liquids: A, B and C.
Table 1 below details the maximum volume of each liquid the company can purchase and the
purchase and selling prices of each liquid:
Table 1: Availability and prices of liquids

Liquid Availability (in Purchase price Selling price

liters) ($/liter) ($/liter)
A 350 1.50 1.75
B 425 2.00 2.25
C 375 3.25 3.30
Table 2 describes the conditions the company must respect in the composition of mixtures
M1, M2, M3 and M4.

Table 2: proportion of each liquid in each mixture

Mixtures
Liquid M1 M2 M3 M4
A at least 30% at most 50% - 40%

B 25% at least 32% no more than 40% at least 10%

C at least 20% at most 36% at least 25% at least 30%

The market can absorb all the quantity produced by the company if the
current prices are held constant: 2.50$ per liter of M1, 3.25$per liter of M2, 3.85$ per liter of
M3 and 2.65$ per liter of M4. The company can also resell the primary liquids without
mixing them, unit selling prices are detailed in the last column of table 1 above. What is the
optimal production plan that maximizes the total profit of the company given that the quantity
of M2 to be produced must be at least 40% of the total quantity produced?
Decision variables:

Yi : the quantity of base liquid i to purchase, i={A,B,C}

Xj: The quantity of mixture j to make and sell , j= 1,2,3,4

Wi : the quantity of base liquid i to resell (unmixed)

Xij : quantity of base liquid i in mixture j

Parameters:

Availabilityi :

Model:

Constraints:

For i= A, B, C:

8
Yi <= Availabilityi

The quantity to mix and sell and the quantity to resell unmixed must be equal to the quantity purchased:

For i =A, B, C:

Yi= Xj + Wi

The quantity of mixtures sold is equal to the quantity made:

For mixture j =1,2,3,4:

Xj= ∑i Xij

Restriction on the production of M2:

X2 >= 0.4*∑j Xj
Composition of each mixture:
XA1 >=0.3*X1 ; XB1=0.25X1; XC1>=0.2X1
XA2 <=0.5X2 ; XB2 >= 0.32X2 , XC2 <= 0.36X2
XB3 <= 0.4X3

Non-negativity constraints