Let’s take a look at a problem that requires a bit of ingenuity to put into standard minimization form.
Problem – Garton’s Seeds has a seed mixture containing three types of seeds: bluegrass, rye, and Bermuda. The cost per pound of the three seeds are 16 cents, 14 cents and 12 cents. Bluegrass seed must be at least 25% of the each batch. The amount of Bermuda must be no more than 2/3 the amount of rye in each batch. To fill current orders, Garton’s must make at least 6000 lbs of the mixture. How many pounds of each seed should be in the batch so that the cost of the batch is minimized?
Solution Start by defining the variables to represent the seeds.
y1 – lbs of bluegrass in the mixture
y2 – lbs of rye in the mixture
y3 – lbs of Bermuda in the mixture
Since cost is to be minimized, let C be the cost of the mixture. We know the cost per pound on each type of seed. By multiplying the cost per pound times the number of pounds, we can find the cost of each type of seed. Adding the cost for each type gives
C = 16y1 + 14y2 + 12y3
where C is in cents.
Now let’s look at the constraints. The easiest one to recognize relates to the requirement that at least 6000 lbs of the mixture must be made. This means that the sum of the variables representing the total amount of the mixture is greater than or equal to 6000,
y1 + y2 + y3 > 6000
In this format the inequality fits the form needed for a standard minimization. In this format the variables appear linearly on the left side of the inequality and are greater than or equal to a nonnegative number. Each of the inequalities must have this form to apply the Simplex Method.
Since the amount of Bermuda must be no more than 2/3 the amount of rye in each batch, we can write
y3 < 2/3 y2
To put this in the proper format, subtract y3 from both sides and flip-flop the inequality to yield
2/3 y2 – y3 > 0
This has the proper format, but will be easier to deal with in the Simplex Method if there is no fraction. Multiply each term by 3 to give
2y2 – 3y3 > 0
The statement “Bluegrass seed must be at least 25% of the each batch” is a bit more difficult to interpret. On the surface, you might write
y1 > 0.25(6000)
thinking that 25% of the 6000 lb mixture must be bluegrass. But this would be incorrect since the batch will be at least 6000 lbs. Instead of 6000 lbs, write the total amount of the batch as y1 + y2 + y3. Now we can interpret the information as
y1 > 0.25(y1 + y2 + y3)
Remove the parentheses and move all of the terms to the left side of the inequality. This yields
0.75y1 – 0.25y2 – 0.25y3 > 0
We can make this a bit more palatable by multiplying each term by 4,
3y1 – y2 – y3 > 0
Adding the nonnegativity constraints give the standard minimization problem:
Minimize C = 16y1 + 14y2 + 12y3 subject to
y1 + y2 + y3 > 6000
2y2 – 3y3 > 0
3y1 – y2 – y3 > 0
y1 > 0, y2 > 0, y3 > 0
With the standard minimization problem established, we can now write out the dual problem and apply the Simplex Method.