Linear Programming Model

Linear Programming
Many major decisions faced by a manager of a business focus on the best way to achieve the
objectives of the firm, subject to the restrictions placed on the manager by the operating
environment. These restrictions can take the form of limited resources, such as time, labor,
energy, material, or money; or they can be in the form of restrictive guidelines, such as a
recipe for making cereal or engineering specifications. One of the most frequent objectives of
business firms is to gain the most profit possible or, in other words, to maximize profit. The
objective of individual organizational units within a firm (such as a production or packaging
department) is often to minimize cost. When a manager attempts to solve a general type of
problem by seeking an objective that is subject to restrictions, the management science
technique called linear programming is frequently used.

Objectives of a business frequently are to maximize profit or minimize cost.

Linear programming is a mathematical optimization technique used to determine

the best possible outcome—such as maximum profit or minimum cost—within a
given set of linear constraints. It involves maximizing or minimizing a linear
objective function based on variables subject to linear inequality or equality
constraints

There are three steps in applying the linear programming technique. First, the problem must
be identified as being solvable by linear programming. Second, the unstructured problem must
be formulated as a mathematical model. Third, the model must be solved by using established
mathematical techniques. The linear programming technique derives its name from the fact
that the functional relationships in the mathematical model are linear, and the solution
technique consists of predetermined mathematical steps that is, a program. In this chapter
we will concern ourselves with the formulation of the mathematical model that represents the
problem and then with solving this model by using a graph.

Model Formulation / Components of LP Model

A linear programming model consists of certain common components and characteristics. The
model components include decision variables, an objective function, and model constraints,
which consist of decision variables and parameters. Decision variables are mathematical
symbols that represent levels of activity by the firm. For example, an electrical manufacturing
firm desires to produce x1 radios, x2 toasters, and x3 clocks, where x1, x2, and x3 are symbols
representing unknown variable quantities of each item. The final values of x1, x2, and x3, as
determined by the firm, constitute a decision (e.g., the equation x1 = 100 radios is a decision
by the firm to produce 100 radios).

Decision variables are mathematical symbols that represent levels of activity.

The objective function is a linear mathematical relationship that describes the

objective of the firm in terms of the decision variables. The objective function always

Page 1 of 17
 Linear Programming Model

consists of either maximizing or minimizing some value (e.g., maximizes the profit or minimizes
the cost of producing radios).

The objective function is a linear relationship that reflects the objective of an

operation.

The model constraints are also linear relationships of the decision variables; they represent
the restrictions placed on the firm by the operating environment. The restrictions can be in
the form of limited resources or restrictive guidelines. For example, only 40 hours of labor
may be available to produce radios during production. The actual numeric values in the
objective function and the constraints, such as the 40 hours of available labor, are
parameters.

A constraint is a linear relationship that represents a restriction on decision making.

Parameters are numerical values that are included in the objective functions and constraints.

The next section presents an example of how a linear programming model is formulated.
Although this example is simplified, it is realistic and represents the type of problem to which
linear programming can be applied. In the example, the model components are distinctly
identified and described. By carefully studying this example, you can become familiar with the
process of formulating linear programming models.

Characteristics of Linear Programming Problems

Now that we have had the opportunity to construct several linear programming models, let's
review the characteristics that identify a linear programming problem.

The components of a linear programming model are an objective function, decision variables,
and constraints.

A linear programming problem requires a choice between alternative courses of action (i.e., a
decision). The decision is represented in the model by decision variables. A typical choice task
for a business firm is deciding how much of several different products to produce, as in the
Beaver Creek Pottery Company example presented earlier in this chapter. Identifying the
choice task and defining the decision variables is usually the first step in the formulation
process because it is quite difficult to construct the objective function and constraints
without first identifying the decision variables.

The problem encompasses an objective that the decision maker wants to achieve. The two
most frequently encountered objectives for a business are maximizing profit and minimizing
cost.

A third characteristic of a linear programming problem is that restrictions exist, making

unlimited achievement of the objective function impossible. In a business firm these
restrictions often take the form of limited resources, such as labor or material; however, the

Page 2 of 17
 Linear Programming Model

sample models in this chapter exhibit a variety of problem restrictions. These restrictions, as
well as the objective, must be definable by mathematical functional relationships that are
linear. Defining these relationships is typically the most difficult part of the formulation
process.

Key Assumptions of Linear Programming (LP)

1. Linearity (Proportionality): The relationship between decision variables and the

objective function (e.g., profit) or constraints (e.g., resources) must be linear. Doubling
the input (e.g., production volume) doubles the output (e.g., resource usage).

2. Certainty (Determinism): All parameters—such as cost, profit per unit, and resource
availability—are known with absolute certainty and do not change during the study
period.

3. Additivity: The total resource usage or profit is the sum of the contributions from
each individual variable. There are no interaction effects between activities.

4. Divisibility (Continuity): Decision variables can take on non-integer (fractional) values,

meaning you can produce, for example, 10.5 units, allowing for continuous solutions.

5. Non-negativity: All decision variables must be zero or positive ( ≥ 0); negative values
for resources or production quantities are physically impossible.

6. Finiteness: The model assumes a finite number of variables and constraints to

compute an optimal solution.

7. Optimality: In linear programming problems of maximum profit solution or minimum

cots solution always occurs at a corner point of the set of the feasible solution.

The graphical approach to the solution of linear programming problems is not a very efficient
means of solving problems. For one thing, drawing accurate graphs is tedious. Moreover, the
graphical approach is limited to models with only two decision variables. However, the analysis
of the graphical approach provides valuable insight into linear programming problems and their
solutions.

In the graphical approach, once the feasible solution area and the optimal solution point have
been determined from the graph, simultaneous equations are solved to determine the values of
x1 and x2 at the solution point.

Page 3 of 17
 Linear Programming Model

Standard form of LP Problem

Page 4 of 17
 Linear Programming Model

A Product Mix Example

Quick-Screen is a clothing manufacturing company that specializes in producing commemorative shirts

immediately following major sporting events such as the World Series, Super Bowl, and Final Four. The
company has been contracted to produce a standard set of shirts for the winning team, either State
University or Tech, following a college football bowl game on New Year's Day. The items produced
include two sweatshirts, one with silk-screen printing on the front and one with print on both sides, and
two T-shirts of the same configuration. The company has to complete all production within 72 hours
after the game, at which time a trailer truck will pick up the shirts. The company will work around the
clock. The truck has enough capacity to accommodate 1,200 standard-size boxes. A standard-size box
holds 12 T-shirts, and a box of 12 sweatshirts is three times the size of a standard box. The company
has budgeted $25,000 for the production run. It has 500 dozen blank sweatshirts and T-shirts each in
stock, ready for production. The resource requirements, unit costs, and profit per dozen for each type
of shirt are shown in the following table:

Processing Time (hr.) per Dozen Cost per Dozen Profit per Dozen

SweatshirtF 0.10 $36 $ 90

SweatshirtB/F 0.25 48 125

T-shirtF 0.08 25 45

T-shirtB/F 0.21 35 65

The company wants to know how many dozen (boxes) of each type of shirt to produce in order to
maximize profit.

Following is a review of the model formulation steps for this problem:

Summary of Linear Programming Model Formulation Steps

Step 1. Define the decision variables

How many (dozens of) T-shirts and sweatshirts of each type to produce

Step 2. Define the objective function

Maximize profit

Step 3. Define the constraints

The resources available, including processing time, blank shirts, budget, and shipping
capacity

Page 5 of 17
 Linear Programming Model

Decision Variables

This problem contains four decision variables, representing the number of dozens (boxes) of each type
of shirt to produce:

x1 = sweatshirts, front printing

x2 = sweatshirts, back and front printing

x3 = T-shirts, front printing

x4 = T-shirts, back and front printing

The Objective Function

The company's objective is to maximize profit. The total profit is the sum of the individual profits
gained from each type of shirt. The objective function is expressed as

Maximize Z = $90x1 + 125x2 + 45x3 + 65x4

Model Constraints

The first constraint is for processing time. The total available processing time is the 72-hour period
between the end of the game and the truck pickup:

0.10x1 + 0.25x2 + 0.08x3 + 0.21x4 ≤ 72 hr

The second constraint is for the available shipping capacity, which is 1,200 standard-size boxes. A box of
sweatshirts is three times the size of a standard-size box. Thus, each box of sweatshirts is equivalent in
size to three boxes of T-shirts. This relative size differential is expressed in the following constraint:

3x1 + 3x2 + x3 + x4 ≤ 1,200 boxes

The third constraint is for the cost budget. The total budget available for production is $25,000:

$36x1 + 48x2 + 25x3 + 35x4 ≤ $25,000

The last two constraints reflect the available blank sweatshirts and T-shirts the company has in storage:

x1 + x2 ≤ 500 dozen sweatshirts

x3 + x4 ≤ 500 dozen T-shirts

Page 6 of 17
 Linear Programming Model

Model Summary

The linear programming model for Quick-Screen is summarized as follows:

Maximize Z = $90x1 + 125x2 + 45x3 + 65x4

Subject to:
0.10x1 + 0.25x2 + 0.08x3 + 0.21x4 ≤ 72

3x1 + 3x2 + x3 + x4 ≤ 1,200

$36x1 + 48x2 + 25x3 + 35x4 ≤ $25,000

x1 + x2 ≤ 500

x3 + x4 ≤ 500

x1, x2, x3, x4 ≥ 0

Solution Analysis

The model solution is

x1 = 175.56 boxes of front-only sweatshirts

x2 = 57.78 boxes of front and back sweatshirts

x3 = 500 boxes of front-only T-shirts

Z = $45,522.22 profit

The manager of Quick-Screen might have to round off the solution to send whole boxes for example, 175
boxes of front-only sweatshirts, 57 of front and back sweatshirts, and 500 of front-only T-shirts. This
would result in a profit of $45,375.00, which is only $147.22 less than the optimal profit value of
$45,522.22.

After formulating and solving this model, Quick-Screen might decide that it needs to produce and ship
at least some of each type of shirt. Management could evaluate this possibility by adding four
constraints that establish minimum levels of production for each type of shirt, including front and back
T-shirts, x4, none of which are produced in the current solution. The manager might also like to
experiment with the constraints to see the effect on the solution of adding resources. For example, the
dual value for processing time shows profit would increase by $233.33 per hour (up to 98.33 hours, the
upper limit of the sensitivity range for this constraint quality value). Although the 72-hour limit seems
pretty strict, it might be possible to reduce individual processing times and achieve the same result.

Page 7 of 17
 Linear Programming Model

A Diet Example

Breathtakers, a health and fitness center, operates a morning fitness program for senior citizens. The
program includes aerobic exercise, either swimming or step exercise, followed by a healthy breakfast in
the dining room. Breathtakers' dietitian wants to develop a breakfast that will be high in calories,
calcium, protein, and fiber, which are especially important to senior citizens, but low in fat and
cholesterol. She also wants to minimize cost. She has selected the following possible food items, whose
individual nutrient contributions and cost from which to develop a standard breakfast menu are shown in
the following table:

Breakfast Fat Cholesterol Iron Calcium Protein Fiber

Food Calories (g) (mg) (mg) (mg) (g) (g) Cost

1. Bran cereal (cup) 90 0 0 6 20 3 5 $0.18

2. Dry cereal (cup) 110 2 0 4 48 4 2 0.22

3. Oatmeal (cup) 100 2 0 2 12 5 3 0.10

4. Oat bran (cup) 90 2 0 3 8 6 4 0.12

5. Egg 75 5 270 1 30 7 0 0.10

6. Bacon (slice) 35 3 8 0 0 2 0 0.09

7. Orange 65 0 0 1 52 1 1 0.40

8. Milk2% (cup) 100 4 12 0 250 9 0 0.16

9. Orange juice (cup) 120 0 0 0 3 1 0 0.50

10. Wheat toast (slice) 65 1 0 1 26 3 3 0.07

The dietitian wants the breakfast to include at least 420 calories, 5 milligrams of iron, 400 milligrams of
calcium, 20 grams of protein, and 12 grams of fiber. Furthermore, she wants to limit fat to no more than
20 grams and cholesterol to 30 milligrams.

Decision Variables

This problem includes 10 decision variables, representing the number of standard units of each food item
that can be included in each breakfast:

x1 = cups of bran cereal x2 = cups of dry cereal

x3 = cups of oatmeal x4 = cups of oat bran
x5 = eggs x6 = slices of bacon
x7 = oranges x8 = cups of milk
x9 = cups of orange juice x10 = slices of wheat toast

Page 8 of 17
 Linear Programming Model

The Objective Function

The dietitian's objective is to minimize the cost of a breakfast. The total cost is the sum of the
individual costs of each food item:

Minimize z = $ 0.18x1 + 0.22x2 + 0.10x3 + 0.12x4 + 0.10x5 + 0.09x6 + 0.40x7 + 0.16x8 + 0.50x9 + 0.07x10

Model Constraints

The constraints are the requirements for the nutrition items:

90x1 + 110x2 +100x3 + 90x4 + 75x5 + 35x6 + 65x7 + 100x8 + 120x9 + 65x10 ≥ 420 calories
2x2 +2x3 + 2x4 + 5x5 + 3x6 + 4x8 + x10 ≤ 20 g of fat
270x5 + 8x6 + 12x8 ≤ 30 mg of cholesterol
6x1 + 4x2 + 2x3 + 3x4 + x5 + x7 + x10 ≥ 5 mg of iron
20x1 + 48x2 + 12x3 + 8x4 + 30x5 + 52x7 + 250x8 + 3x9 + 26x10 ≥ 400 mg of calcium
3x1 + 4x2 + 5x3 + 6 x4 + 7x5 + 2x6 + x7 + 9x8 + x9 + 10 x10 ≥ 20 g of protein
5x1 + 2x2 + 3x3 + 4x4 + x7 + 3x10 ≥ 12 g of fiber

Model Summary

The linear programming model for this problem can be summarized as follows:

Minimize z = 0.18x1 + 0.22x2 + 0.10x3 + 0.12x4 + 0.10x5 + 0.09x6 + 0.40x7 + 0.16x8 + 0.50x9 + 0.07x10
Subject to
90x1 + 110x2 +100x3 + 90x4 + 75x5 + 35x6 + 65x7 + 100x8 + 120x9 + 65x10 ≥ 420
2x2 +2x3 + 2x4 + 5x5 + 3x6 + 4x8 + x10 ≤ 20
270x5 + 8x6 + 12x8 ≤ 30
6x1 + 4x2 + 2x3 + 3x4 + x5 + x7 + x10 ≥ 5
20x1 + 48x2 + 12x3 + 8x4 + 30x5 + 52x7 + 250x8 + 3x9 + 26x10 ≥ 400
3x1 + 4x2 + 5x3 + 6 x4 + 7x5 + 2x6 + x7 + 9x8 + x9 + 10 x10 ≥ 20
5x1 + 2x2 + 3x3 + 4x4 + x7 + 3x10 ≥ 12
xi ≥ 0

Solution Analysis

The solution is:

x3 = 1.025 cups of oatmeal

x8 = 1.241 cups of milk

x10 = 2.975 slices of wheat toast
Z = $0.509 cost per meal

The result of this simplified version of a real menu planning model (see the application box "The Evolution of the Diet
Problem") is interesting in that it suggests a very practical breakfast menu. This would be a healthy breakfast for
anyone.
This model includes a daily minimum requirement of only 420 calories. The recommended daily calorie requirement for
an adult is approximately 2,000 calories. Thus, the breakfast requirement is only about 21% of normal daily adult
needs. In this model the dietitian must have felt a low-calorie breakfast was needed because the senior citizens had
Page 9 of 17
 Linear Programming Model

high-calorie lunches and dinners. An alternative approach to a healthy diet is a high-calorie breakfast followed by low-
calorie, light meals and snacks the rest of the day. However, in this model, as the calorie requirements are increased
above 420, the model simply increases the cups of oatmeal. For example, a 700-calorie requirement results in about 5
or 6 cups of oatmeal not a very appetizing breakfast. This difficulty can be alleviated by establishing upper limits on
the servings for each food item and solving the model again with a higher calorie requirement.

An Investment Example

Kathleen Allen, an individual investor, has $70,000 to divide among several investments. The alternative
investments are municipal bonds with an 8.5% annual return, certificates of deposit with a 5% return,
treasury bills with a 6.5% return, and a growth stock fund with a 13% annual return. The investments are
all evaluated after 1 year. However, each investment alternative has a different perceived risk to the
investor; thus, it is advisable to diversify. Kathleen wants to know how much to invest in each alternative
in order to maximize the return.

The following guidelines have been established for diversifying the investments and lessening the risk
perceived by the investor:

1. No more than 20% of the total investment should be in municipal bonds.

2. The amount invested in certificates of deposit should not exceed the amount invested in the
other three alternatives.
3. At least 30% of the investment should be in treasury bills and certificates of deposit.
4. To be safe, more should be invested in CDs and treasury bills than in municipal bonds and the
growth stock fund, by a ratio of at least 1.2 to 1.

Kathleen wants to invest the entire $70,000.

Decision Variables

Four decision variables represent the monetary amount invested in each investment alternative:

x1 = amount ($) invested in municipal bonds

x2 = amount ($) invested in certificates of deposit

x3 = amount ($) invested in treasury bills

x4 = amount ($) invested in growth stock fund

The Objective Function

The objective of the investor is to maximize the total return from the investment in the four
alternatives. The total return is the sum of the individual returns from each alternative. Thus, the
objective function is expressed as

maximize Z = $0.085x1 + 0.05x2 + 0.065x3 + 0.130x4

where

Z = total return from all investments

Page 10 of 17
 Linear Programming Model

Z = total return from all investments

0.085x1 = return from the investment in municipal bonds

0.05x2 = return from the investment in certificates of deposit

0.065x3 = return from the investment in treasury bills

0.130x4 = return from the investment in growth stock fund

Model Constraints

In this problem the constraints are the guidelines established for diversifying the total investment.
Each guideline is transformed into a mathematical constraint separately.

The first guideline states that no more than 20% of the total investment should be in municipal bonds.
The total investment is $70,000; 20% of $70,000 is $14,000. Thus, this constraint is

x1 ≤ $14,000

The second guideline indicates that the amount invested in certificates of deposit should not exceed the
amount invested in the other three alternatives. Because the investment in certificates of deposit is x2
and the amount invested in the other alternatives is x1 + x3 + x4, the constraint is

x2 ≤ x1 + x3 + x4

This constraint is not in what we referred to in Chapter 3 as standard form for a computer solution. In
standard form, all the variables would be on the left-hand side of the inequality (≤ ), and all the numeric
values would be on the right side. This type of constraint can be used in Excel just as it is shown here;
however, for solution with QM for Windows, all constraints must be in standard form. We will go ahead
and convert this constraint and others in this model to standard form, but when we solve this model with
Excel, we will explain how the model constraints could be used in their original (nonstandard) form. To
convert this constraint to standard form, x1 + x3 + x4 must be subtracted from both sides of the ≤ sign
to put this constraint in proper form:
x2 - x1 - x3 - x4 ≤ 0

Standard form requires all variables to be to the left of the inequality and numeric values to the right.

The third guideline specifies that at least 30% of the investment should be in treasury bills and
certificates of deposit. Because 30% of $70,000 is $21,000 and the amount invested in certificates of
deposit and treasury bills is represented by x2 + x3, the constraint is
x2 + x3 ≥ $21,000

The fourth guideline states that the ratio of the amount invested in certificates of deposit and treasury
bills to the amount invested in municipal bonds and the growth stock fund should be at least 1.2 to 1:

[(x2 + x3)/(x1 + x4)] ≥1.2

This constraint is not in standard linear programming form because of the fractional relationship of the
decision variables, (x2 + x3)/(x1 + x4). It is converted as follows:

Page 11 of 17
 Linear Programming Model

x2 + x3 ≥1.2 (x1 + x4)

or, -1.2 x1 + x2 + x3 – 1.2x4 ≥ 0

Standard form requires that fractional relationships between variables be eliminated.

Finally, the investor wants to invest the entire $70,000 in the four alternatives. Thus, the sum of all the
investments in the four alternatives must equal $70,000:

x1 + x2 + x3 + x4 = $70,000

Model Summary

The complete linear programming model for this problem can be summarized as

maximize Z = 0.085x1 + 0.05x2 + 0.065x3 + 0.130x4

subject to
x1 ≤ $14,000
x2 - x1 - x3 - x4 ≤ 0
x2 + x3 ≥ 21,000
-1.2 x1 + x2 + x3 – 1.2x4 ≥ 0
x1 + x2 + x3 + x4 = 70,000
x1, x2, x3, x4 ≥ 0

Solution Analysis

The solution is

x3 = $38,181.82 invested in treasury bonds

x4 = $31,818.18 invested in a growth stock fund
Z = $6,818.18

Notice that the dual (shadow price) value for constraint 5 (i.e., the sum of the investments must equal
$70,000) is 0.095. This indicates that for each additional $1 Kathleen Allen invests (above $70,000),
according to the existing investment guidelines she has established, she could expect a return of 9.5%.
The sensitivity ranges show that there is no upper bound on the amount she could invest and still receive
this return.

An interesting variation of the problem is to not specify that the entire amount available (in this case,
$70,000) must be invested. This changes the constraints for the first and third guidelines and the
constraint that requires that the entire $70,000 be invested.

Page 12 of 17
 Linear Programming Model

A Marketing Problem:

The Biggs Department Store chain has hired an advertising firm to determine the types and amount of
advertising it should invest in for its stores. The three types of advertising available are television and
radio commercials and newspaper ads. The retail chain desires to know the number of each type of
advertisement it should purchase in order to maximize exposure. It is estimated that each ad or
commercial will reach the following potential audience and cost the following amount:

Exposure (people/ad or commercial) Cost

Television commercial 20,000 $15,000

Radio commercial 12,000 6,000

Newspaper ad 9,000 4,000

The company must consider the following resource constraints:

1. The budget limit for advertising is $100,000.

2. The television station has time available for 4 commercials.
3. The radio station has time available for 10 commercials.
4. The newspaper has space available for 7 ads.
5. The advertising agency has time and staff available for producing no more than a total of 15
commercials and/or ads

A Transportation Problem:

The Zephyr Television Company ships televisions from three warehouses to three retail stores on a
monthly basis. Each warehouse has a fixed supply per month, and each store has a fixed demand per
month. The manufacturer wants to know the number of television sets to ship from each warehouse to
each store in order to minimize the total cost of transportation.

Each warehouse has the following supply of televisions available for shipment each month:

Warehouse Supply (sets)

1. Cincinnati 300

2. Atlanta 200

3. Pittsburgh 200

Total 700

Page 13 of 17
 Linear Programming Model

Each retail store has the following monthly demand for television sets:

Store Demand (sets)

A. New York 150

B. Dallas 250

C. Detroit 200

Total 600

Costs of transporting television sets from the warehouses to the retail stores vary as a result of
differences in modes of transportation and distances. The shipping cost per television set for each route
is as follows:

To Store

From Warehouse A B C

1 $16 $18 $11

2 14 12 13

3 13 15 17

A Blend Problem:

A petroleum company produces three grades of motor oil: super, premium, and extra from three
components. The company wants to determine the optimal mix of the three components in each grade of
motor oil that will maximize profit. The maximum quantities available of each component and their cost
per barrel are as follows:

Component Maximum Barrels Available/Day Cost/Barrel

1 4,500 $12

2 2,700 10

3 3,500 14

Page 14 of 17
 Linear Programming Model

To ensure the appropriate blend, each grade has certain general specifications. Each grade must have a
minimum amount of component 1 plus a combination of other components, as follows:

Grade Component Specifications Selling Price/Barrel

Super At least 50% of 1 $23

Not more than 30% of 2

Premium At least 40% of 1 20

Not more than 25% of 3

Extra At least 60% of 1 18

At least 10% of 2

The company wants to produce at least 3,000 barrels of each grade of motor oil

Products Mix EXAMPLE

The WYNDOR GLASS CO. produces high-quality glass products, including

windows and glass doors. It has three plants. Aluminum frames and hardware
are made in Plant 1, wood frames are made in Plant 2, and Plant 3 produces the
glass and assembles the products. Because of declining earnings, top
management has decided to revamp the company’s product line. Unprofitable
products are being discontinued, releasing production capacity to launch two
new products having large sales potential:

Product 1: An 8-foot glass door with aluminum framing

Product 2: A 4 _ 6 foot double-hung wood-framed window

Product 1 requires some of the production capacity in Plants 1 and 3, but none
in Plant 2. Product 2 needs only Plants 2 and 3. The marketing division has
concluded that the company could sell as much of either product as could be
produced by these plants. However, because both products would be competing
for the same production capacity in Plant 3, it is not clear which mix of the
two products would be most profitable. Therefore, an OR team has been
formed to study this question.

The OR team began by having discussions with upper management to identify

management’s objectives for the study. These discussions led to developing
the following definition of the problem:

Page 15 of 17
 Linear Programming Model

Determine what the production rates should be for the two products in order
to maximize their total profit, subject to the restrictions imposed by the
limited production capacities available in the three plants. (Each product will
be produced in batches of 20, so the production rate is defined as the number
of batches produced per week.) Any combination of production rates that
satisfies these restrictions is permitted, including producing none of one
product and as much as possible of the other.

The OR team also identified the data that needed to be gathered:

Table 3.1 summarizes the data gathered.

The OR team immediately recognized that this was a linear programming

problem of the classic product mix type, and the team next undertook the
formulation of the corresponding mathematical model.

Formulation as a Linear Programming Problem

To formulate the mathematical (linear programming) model for this problem,

let

x1 = number of batches of product 1 produced per week

x2 = number of batches of product 2 produced per week

Z = total profit per week (in thousands of dollars) from producing these
two products

Page 16 of 17
 Linear Programming Model

Thus, x1 and x2 are the decision variables for the model. Using the bottom
row of Table 3.1, we obtain

Z= 3x1+5x2.

The objective is to choose the values of x1 and x2 so as to maximize Z =3x1 +

5x2, subject to the restrictions imposed on their values by the limited
production capacities available in the three plants. Table 3.1 indicates that
each batch of product 1 produced per week uses 1 hour of production time per
week in Plant 1, whereas only 4 hours per week are available. This restriction is
expressed mathematically by the inequality x1 ≤ 4. Similarly, Plant 2 imposes
the restriction that 2x2 ≤ 12. The number of hours of production

Page 17 of 17