Blending Problem

Problem definition

The Kahuna company manufactures sausages using three kinds of meat. The relevant information about the ingredients is provided in the table below:

Ingredient

Cost (€/kg)

Availability (kg)

Pork

4.32

30

Wheat

2.46

20

Starch

1.86

17

The company makes two types of sausages:

  • Economy (>=40% Pork)

  • Premium (>=60% Pork)

One sausage is 50 grams (0.05 kg)

According to government regulations, the most starch we can use in our sausages is 25%

We have a contract with a butcher, and have already purchased 23 kg pork, that will go bad if it’s not used.

We have a demand for 350 economy sausages and 500 premium sausages.

Write a linear program to figure out how to most cost effectively blend our sausages.

Let’s model our problem

pe = Pork in the economy sausages (kg)
we = Wheat in the economy sausages (kg)
se = Starch in the economy sausages (kg)
pp = Pork in the premium sausages (kg)
wp = Wheat in the premium sausages (kg)
sp = Starch in the premium sausages (kg)

We want to minimise costs such that:

Cost = 4.32(pe + pp) + 2.46(we + wp) + 1.86(se + sp)

With the following constraints:

pe + we + se = 350 * 0.05
pp + wp + sp = 500 * 0.05
pe ≥ 0.4(pe + we + se)
pp ≥ 0.6(pp + wp + sp)
se ≤ 0.25(pe + we + se)
sp ≤ 0.25(pp + wp + sp)
pe + pp ≤ 30
we + wp ≤ 20
se + sp ≤ 17
pe + pp ≥ 23