A distillery produces custom-blended whiskey. A particular blend consists of rye

Question

A distillery produces custom-blended whiskey. A particular blend consists of rye and bourbon whiskies. The company has received an order for a minimum of 400 gallons of this custom-blended whiskey. The customer has specified that the order must contain at least 40% rye and not more than 250 gallons of bourbon. The customer has also specified that the blend should be mixed in the ratio of two parts rye to one part bourbon. The company can produce 500 gallons per week regardless of the blend, and it wants to complete this order in one week. The blend is sold for $5 per gallon. The brewing company’s cost per gallon is $2 for rye and $1 for bourbon. The company wants to determine the blend mix that will meet customers requirements and maximize profits. Formulate a LP model for this problem

Explanation / Answer

Linear programming formulation examples
A cargo plane has three compartments for storing cargo: front, centre and rear. These compartments have the following limits on both weight and space:

Compartment Weight capacity (tonnes) Space capacity (cubic metres)
Front 10 6800
Centre 16 8700
Rear 8 5300
Furthermore, the weight of the cargo in the respective compartments must be the same proportion of that compartment's weight capacity to maintain the balance of the plane.

The following four cargoes are available for shipment on the next flight:

Cargo Weight (tonnes) Volume (cubic metres/tonne) Profit (£/tonne)
C1 18 480 310
C2 15 650 380
C3 23 580 350
C4 12 390 285
Any proportion of these cargoes can be accepted. The objective is to determine how much (if any) of each cargo C1, C2, C3 and C4 should be accepted and how to distribute each among the compartments so that the total profit for the flight is maximised.

Formulate the above problem as a linear program
What assumptions are made in formulating this problem as a linear program?
Briefly describe the advantages of using a software package to solve the above linear program, over a judgemental approach to this problem.
Solution

Variables

We need to decide how much of each of the four cargoes to put in each of the three compartments. Hence let:

xij be the number of tonnes of cargo i (i=1,2,3,4 for C1, C2, C3 and C4 respectively) that is put into compartment j (j=1 for Front, j=2 for Centre and j=3 for Rear) where xij >=0 i=1,2,3,4; j=1,2,3

Note here that we are explicitly told we can split the cargoes into any proportions (fractions) that we like.

Constraints

cannot pack more of each of the four cargoes than we have available
x11 + x12 + x13 <= 18
x21 + x22 + x23 <= 15
x31 + x32 + x33 <= 23
x41 + x42 + x43 <= 12

the weight capacity of each compartment must be respected
x11 + x21 + x31 + x41 <= 10
x12 + x22 + x32 + x42 <= 16
x13 + x23 + x33 + x43 <= 8

the volume (space) capacity of each compartment must be respected
480x11 + 650x21 + 580x31 + 390x41 <= 6800
480x12 + 650x22 + 580x32 + 390x42 <= 8700
480x13 + 650x23 + 580x33 + 390x43 <= 5300

the weight of the cargo in the respective compartments must be the same proportion of that compartment's weight capacity to maintain the balance of the plane
[x11 + x21 + x31 + x41]/10 = [x12 + x22 + x32 + x42]/16 = [x13 + x23 + x33 + x43]/8

Objective

The objective is to maximise total profit, i.e.

maximise 310[x11+ x12+x13] + 380[x21+ x22+x23] + 350[x31+ x32+x33] + 285[x41+ x42+x43]

The basic assumptions are:

The advantages of using a software package to solve the above linear program, rather than a judgemental approach are:

Linear Programming
A linear program is a mathematical optimization model that has a linear objective function and a set of linear constraints. To provide a quick overview, we describe below what is known as the product-mix problem.

The Product-Mix Problem

A company manufactures two models of a product, which we call the regular model and the enhanced model. Two resources, A and B, are needed for the manufacturing of units of this product; and the detailed resource requirements are given in the following table:

Regular Model   Enhanced Model
Resource A   3   4
Resource B   2   3
This means, for example, 3 units of Resource A and 2 units of Resource B are consumed in the manufacturing of each unit of the regular model. The resources could represent hours of labor, amounts of raw material, available electrical power, and so on.
Suppose further that the company has 650 units of Resource A and 500 units of Resource B available per week, and that the net profits for selling units of the regular model and the enhanced model are given respectively as $5 and $7 per unit. The question of interest is: What are the optimal weekly production levels for these two models?

To formulate this problem, we first define a set of decision variables. Let

xr = weekly production level for the regular model,
xe = weekly production level for the enhanced model.
Clearly, these variables should be nonnegative, as they represent physical quantities.
Next, suppose our goal is to maximize weekly total profit. Then, in terms of these decision variables, we have:

Weekly Total Profit = 5 xr + 7 xe;
and we wish to choose a pair of values for xr and xe that yields the highest possible weekly total profit. However, from the table above, we see that there are limitations or constraints on the possible values of these variables. Specifically, we have:
Weekly Requirement for Resource A = 3 xr + 4 xe,
Weekly Requirement for Resource B = 2 xr + 3 xe.
Therefore, the values of xr and xe should be such that these requirements do not exceed 650 and 500, respectively.
Our problem can now be stated formally as:

Maximize   5 xr + 7 xe
Subject to:  
3 xr + 4 xe £ 650
2 xr + 3 xe £ 500
xr ³ 0, xe ³ 0.

What we have just formulated is called a linear program. In this example, it has two decision variables, xr and xe, an objective function, 5 xr + 7 xe, and a set of four constraints. The objective function is to be maximized subject to the specified constraints on the decision variables. It is customary to refer to the first group of constraints,

3 xr + 4 xe £ 650
2 xr + 3 xe £ 500,
as the functional constraints; and the remaining group,
xr ³ 0, xe ³ 0,
as the nonnegativity constraints.
Notice that each term in the objective function has the form cx, where c is a constant and x is a variable. In other words, the objective function is linear in the decision variables xr and xe. Notice further that the left-hand-side expressions in all four constraints are also linear. This is why we call the above problem a linear program.

If a term such as 3x2 appears in a formulation, then the resulting problem is said to be nonlinear.

More generally, a linear program with m functional constraints and n decision variables (or "activities"), x1, x2, ..., xn, has the following general format:

Maximize or Minimize   c1 x1 + c2 x2 + ... + cn xn
Subject to:  
a11 x1 + a12 x2 + ... + a1n xn £, =, or ³ b1
a21 x1 + a22 x2 + ... + a2n xn £, =, or ³ b2
.....
am1 x1 + am2 x2 + ... + amn xn £, =, or ³ bm
x1, x2, ..., xn ³ 0,
where the cj's, the aij's, and the bi's are given parameters. Notice that three types of constraints are allowed: "£", "=", or "³". Strict inequalities, i.e., "<" or ">", are not allowed in a linear program, because they may lead to ill-defined problems (e.g., maximize x subject to x < 1).
In any formulation effort, one has to make simplifying assumptions. We now describe more formally a number of important assumptions in a linear-programming formulation:

Proportionality: The total contribution of any variable (or activity), say x, to either the objective function or a constraint is proportional to x; i.e., the total contribution assumes the form cx, where c is a constant. In the product-mix problem, for example, the total contributions to the net profit from the sale of the regular model and the enhanced model are assumed to be given, respectively, by 5xr and 7xe.
Additivity: The combined contribution from different variables, say x1 and x2, to either the objective function or a constraint is the sum of their individual contributions; i.e., the combined contribution assumes the form c1x1 + c2x2. In the product-mix problem, for example, the total net profit equals the sum of 5xr and 7xe.
Divisibility: Every decision variable can assume fractional values; i.e., all variables are continuous. This assumption may not be valid in the product-mix problem, since the product under consideraton could be, say, cars.
Certainty: All input parameters of the problem (i.e., the cj's, the aij's, and the bi's) are assumed to be known with certainty, i.e., deterministic.
For a more thorough discussion of these assumptions, read Section 3.3 of the text.
Other assumptions that are implicit in our formulation of the product-mix problem include:

All manufactured products can be sold.
The setup cost for production is ignored.
Decisions are made on a weekly basis.
In general, in formulating a problem, one should strive for a good balance between realism and mathematical tractability.
The product-mix problem can be solved by the Simplex method, which is an efficient mathematical procedure for solving linear programs. It can be shown that the optimal solution to our product-mix problem is to produce a "mix" of: 0 regular model and 162.5 enhanced models. This solution achieves an objective-function value of 1137.5.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.