IE 572 Linear Programming Fall 2016

Animal food production

The company CowFood produces food for farm animals that is sold in two forms: powder and granules. The
raw materials used for the production of the food are: oat, maize1 and molasses. The raw materials, except
for the molasses, first need to be ground and then all raw materials that will form a product are blended. In
the last step of the production process the product mix is either transformed to granules or sieved to obtain
food in the form of powder (see Figure 1).

Figure 1: Animal food production process

Every food product needs to fulfill certain nutritional requirements. The percentages of proteins,
lipids and fibers contained in the raw materials and the required percentages in the final products are listed
in Table 1.

Raw material Proteins (%) Lipids (%) Fiber (%)

Oat 13.6 7.1 7
Maize 4.1 2.4 3.7
Molasses 5 0.3 25
Required contents (%) ≥ 9.5 ≥2 ≤6

Table 1: Contents of nutritional components in percent.

There are limits on the availability of raw materials. Table 2 displays the amount of raw material that
is available every day and the respective prices.

Raw material Amount available (kg) Cost ($/kg)

Oat 11,900 0.13
Maize 23,500 0.17
Molasses 750 0.12

Table 2: Raw material availability and prices.

The costs of grinding, blending, granulating, and sieving a kilogram of material are 0.25, 0.05, 0.42,
0.17, respectively. With a daily demand of 9,000 kilograms of granules and 12,000 kilograms of powder, which
quantities of raw materials are required and how should they be blended to minimize the total cost?

1 Maize is a name that is often used for corn (see [Link]

1
IE 572 Linear Programming Fall 2016

General formulation
• Sets:
P : Set of products (grannules and powder)
R : Set of raw materials (oat, maize, and molasses)
N : Set of nutritional components (proteins, lipids, and fiber)
Q : Set of production processes (grinding, blending, granulating, and sieving)
• Parameters:
cr : Cost of raw material r, for r ∈ R.
siq : Cost of processing a kilogram of material r in process q, for q ∈ Q.
air : Content of nutrient i in raw material r, for i ∈ N, r ∈ R.
dp : Demand of product p, for p ∈ P.
lip : Minimum percentage of nutrient i required in product p, for i ∈ N, p ∈ P.
uip : Maximum percentage of nutrient i allowed in product p, for i ∈ N, p ∈ P.
br : Amount available of raw material r, for r ∈ R.

• Decision Variables:
xrp : Amount of raw material r used to produce product p, for r ∈ R, p ∈ P.

   
X X X X X
min cr  xrp  + srq  xrp 
r∈R p∈P q∈Q r∈R p∈P
X
s.t. xrp ≥ dp , p∈P
r∈R
X X
air xrp ≥ lip xrp , i ∈ N, p ∈ P
r∈R r∈R
X X
air xrp ≤ uip xrp , i ∈ N, p ∈ P
r∈R r∈R
X
xrp ≤ br , r∈R
p∈P

xrp ≥ 0, r ∈ R, p ∈ P

Alternatively, using the following additional variables:

yp : Amount of product p produced, for p ∈ P.

   
X X X X X
min cr  xrp  + srq  xrp 
r∈R p∈P q∈Q r∈R p∈P
X
s.t. xrp = yp , p∈P
r∈R

yp ≥ dp , p ∈ P
X
air xrp ≥ lip yp , i ∈ N, p ∈ P
r∈R
X
air xrp ≤ uip yp , i ∈ N, p ∈ P
r∈R
X
xrp ≤ br , r∈R
p∈P

xrp ≥ 0, r ∈ R, p ∈ P
yp ≥ 0, p∈P

Another option could be modeled using the following additional variables:

2
IE 572 Linear Programming Fall 2016

zr : Amount of raw matrial r used, for r ∈ R.

X X X
min cr zr + srq zr
r∈R q∈Q r∈R
X
s.t. xrp = yp , p∈P
r∈R
X
xrp = zr , r∈R
p∈P

yp ≥ dp , p ∈ P
X
air xrp ≥ lip yp , i ∈ N, p ∈ P
r∈R
X
air xrp ≤ uip yp , i ∈ N, p ∈ P
r∈R

zr ≤ br , r∈R
xrp ≥ 0, r ∈ R, p ∈ P
yp ≥ 0, p∈P
zr ≥ 0, r∈R

1 F.A.Q.
1. Q: The molasses do not need to be ground, how is this fact considered in the proposed model?
A: The cost of grinding molasses is 0 (i.e., srq is 0 for r= molasses and q=grinding).
2. Q: Why do we need lip and uip for all raw materials and nutrients? Table 1 does not contain both
upper and lower bounds for al nutrients. For example there is a maximum requirement for fiber, but
no minimum requirement.
A: If there is no lower bound, l is 0 and if there is no upper bound, u is a sufficiently large number.

3
IE 572 Linear Programming Fall 2016

Production of drinking glasses

The main activity of a company in northern France is the production of drinking glasses. It currently sells a
set of G different types of glasses that are produced in batches of p glasses. The company wishes to plan its
production for the next T weeks.

The demand of glasses of type i in week t is dit . Furthermore, for every glass type i, the initial stock is Ii0 and
the required final stock at the end of week T is Iif . The production and storage costs per batch of glass type
i are ci and hi , respectively. The required processing time for workers and machines (in hours) to produce a
batch of glass of type i are wi and mi , respectively, and the required storage space per batch of glass type
i measured in squared inches is si . The number of working hours of the personnel is limited to b hours per
week, and the machines have a weekly capacity of k hours. The available storage space is u square inches.
Which quantities of the different glass types need to be produced in every period to minimize the total cost
of production and storage?

General formulation
• Sets:
G : Set of glass types
T : Set of weeks
• Parameters:
ci : Cost of producing a batch of glass type i, for i ∈ G.
hi : Cost of storing a batch of glass type i, for i ∈ G.
wi : Processing time for workers of a batch of glass type i for i ∈ G.
mi : Processing time for machines of a batch of glass type i for i ∈ G.
si : Size a batch of glass type i for i ∈ G.
b : Number of personel working hours available.
k : Number of machine working hours available.
u : Storage space available.
dit : Demand of glasses of type i in week t, for i ∈ G, t ∈ T.
Ii0 : Initial inventory of glasses of type i, for i ∈ G.
Iif : Required final inventory of glasses of type i, for i ∈ G.
p : Number of glasses per batch.
• Decision Variables:
xit : number of batches of glass type i to produce in week t, for i ∈ G, t ∈ T.
yit : number of batches of glass type i to store in week t, for i ∈ G, t ∈ T.
XX
min (ci xit + hi yit )
i∈G t∈T
X
s.t. wi xit ≤ b, t∈T
i∈G
X
mi xit ≤ k, t∈T
i∈G
X
si yit ≤ u, t∈T
i∈G
0
yi1 = Ii + xi1 − di1 , i∈G
yit = yi,t−1 + xit − dit , i ∈ G, t ∈ T
f
yi|T | ≥ Ii , i∈G
xit ≥ 0, i ∈ G, t ∈ T
yit ≥ 0, i ∈ G, t ∈ T