1

Topic One
Linear Programming (LP) Model
Linear Programming Model Formulation
The LP model has three basic components. These components are:
1. Decision variables that we seek to determine (Unknowns).
2. The objective function that we need to optimize (maximize or minimize).
3. Constraints that the solution must satisfy.

Problem Example (1)

Reddy Mikks produces both interior and exterior paints from two raw
materials, Ml and M2. The following table provides the basic data of the problem:

A market survey indicates that the daily demand for interior paint cannot
exceed that for exterior paint by more than 1 ton. Also, the maximum daily
demand for interior paint is 2 tons.
Reddy Mikks wants to determine the optimum (best) product mix of
interior and exterior paints that maximizes the total daily profit.
Required: Formulate a linear programming model for this problem.
 2

Solution
1. Decision variables (Unknowns):
We need to determine the daily amounts to be produced of exterior and
interior paints. Thus the variables of the model are defined as
𝒙𝟏 = Tons produced daily of exterior paint
𝒙𝟐 = Tons produced daily of interior paint
2. Objective function:
To construct the objective function, note that the company wants to
maximize (i.e., increase as much as possible) the total daily profit of both paints.
Given that the profits per ton of exterior and interior paints are 5 and 4
(thousand) dollars, respectively, it follows that
Total profit from exterior paint = 𝟓𝒙𝟏 (thousand) dollars
Total profit from interior paint = 𝟒𝒙𝟐 (thousand) dollars
Letting 𝒛 represent the total daily profit (in thousands of dollars), the
objective of the company is
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝒛 = 𝟓𝒙𝟏 + 𝟒𝒙𝟐
3. Constraints:
Next, we construct the constraints that restrict raw material usage and
product demand.
• Raw material restrictions:
− Raw material MI

The raw material restriction is expressed verbally as

Usage of a raw material Maximum raw material
( )≤( )
by both paints availability
The daily usage of raw material MI is 6 tons per ton of exterior paint and 4 tons
per ton of interior paint. Thus
 3

Usage of raw material 𝑀l by exterior paint = 𝟔𝒙𝟏 tons/day

Usage of raw material 𝑀l by interior paint = 𝟒𝒙𝟐 tons/day
Hence
Usage of raw material 𝑀l by both paints = 𝟔𝒙𝟏 + 𝟒𝒙𝟐 tons/day
Because the daily availabilities of raw material Ml is limited to 24 tons, the
associated restriction is given as
𝟔𝒙𝟏 + 𝟒𝒙𝟐 ≤ 𝟐𝟒 (Raw material 𝑀I)
− Raw material M2

In a similar manner,
Usage of raw material 𝑀2 by both paints = 𝟏𝒙𝟏 + 𝟐𝒙𝟐 tons/day
Because the daily availabilities of raw material M2 is limited to 6 tons, the
associated restriction is given as
𝒙𝟏 + 𝟐𝒙𝟐 ≤ 𝟔 (Raw material 𝑀2)
• Demand restrictions:
The first demand restriction stipulates that the excess of the daily production of
interior over exterior paint, x2 − x1 , should not exceed 1 ton, which translates to
𝒙𝟐 − 𝒙𝟏 ≤ 𝟏
Rearranging gives:
−𝒙𝟏 + 𝒙𝟐 ≤ 𝟏 (Market limit)
The second demand restriction stipulates that the maximum daily demand of
interior paint is limited to 2 tons, which translates to
𝒙𝟐 ≤ 𝟐 (Demand limit)
An implicit (or "understood-to-be") restriction is that variables 𝒙𝟏 and 𝒙𝟐 cannot
assume negative values. The nonnegativity restrictions, 𝒙𝟏 , 𝒙𝟐 ≥ 𝟎, account for
this requirement.
 4

The complete Reddy Mikks model is

Important notes:
Any values of 𝒙𝟏 and 𝒙𝟐 that satisfy all five constraints constitute a
feasible solution. Otherwise, the solution is infeasible.
The goal of the problem is to find the best feasible solution, or the
optimum, that maximizes the total profit. Before we can do that, we need to
know how many feasible solutions the Reddy Mikks problem has. The answer, as
we will see from the graphical solution, is "an infinite number," which makes it
impossible to solve the problem by enumeration. Instead, we need a systematic
procedure that will locate the optimum solution in a finite number of steps. The
graphical and simplex methods will explain how this can be accomplished.

Problem Example (2)

Determine the best feasible solution among the following (feasible and
infeasible) solutions of the Reddy Mikks model:
a. 𝑥1 = 3, 𝑥2 = 1
b. 𝑥1 = 4, 𝑥2 = 1
c. 𝑥1 = 1, 𝑥2 = 4
d. 𝑥1 = 2, 𝑥2 = 2
e. 𝑥1 = 3, 𝑥2 = 1.5
f. 𝑥1 = 2, 𝑥2 = 1
g. 𝑥1 = 2, 𝑥2 = −1
 5

Solution
a. (𝒙𝟏 , 𝒙𝟐 ) = (𝟑 , 𝟏)
Substitute (𝑥1 = 3, 𝑥2 = 1) in the left-hand side of each constraint.
− In nonnegativity restrictions (constraint 5) we have
𝑥1 ≥ 0 and 𝑥2 ≥ 0
𝑥1 = 3 > 0 and 𝑥2 = 1 > 0
− In constraint (1) we have
6𝑥1 + 4𝑥2 ≤ 24
6 × 3 + 4 × 1 = 22 < 24 (the right-hand side of the constraint)
− In constraint (2) we have
𝑥1 + 2𝑥2 ≤ 6
1 × 3 + 2 × 1 = 5 < 6 (the right-hand side of the constraint)
− In constraint (3) we have
−𝑥1 + 𝑥2 ≤ 1
−1 × 3 + 1 × 1 = −2 < 1 (the right-hand side of the constraint)
− In constraint (4) we have
𝑥2 ≤ 2
1×1=1 < 2 (the right-hand side of the constraint)
∴ The solution, x1 = 3 and x2 = 1, is feasible because it does not violate any of
the constraints, including the nonnegativity restrictions.
Finally, substitute (𝑥1 = 3, 𝑥2 = 1) in the right-hand side of the objective
function, we get
𝑧 = 5𝑥1 + 4𝑥2
𝑧 =5×3+4×1
𝒛 = 𝟏𝟗 (thousand) dollars
 6

b. (𝒙𝟏 , 𝒙𝟐 ) = (𝟒 , 𝟏)
(𝑥1 , 𝑥2 ) >0
6 × 4 + 4 × 1 = 28 ≤ 24 → Infeasible
c. (𝒙𝟏 , 𝒙𝟐 ) = (𝟏 , 𝟒)
(𝑥1 , 𝑥2 ) >0
6 × 1 + 4 × 4 = 22 < 24
1×1+2×4=9 ≤ 6 → Infeasible
d. (𝒙𝟏 , 𝒙𝟐 ) = (𝟐 , 𝟐)
(𝑥1 , 𝑥2 ) >0
6 × 2 + 4 × 2 = 22 < 24
1×2+2×2=6 =6 Feasible
−1 × 2 + 1 × 2 = 0 <1
1×2 = 2 =2

𝑧 =5×2+4×2
𝒛 = 𝟏𝟖 (thousand) dollars
e. (𝒙𝟏 , 𝒙𝟐 ) = (𝟑 , 𝟏. 𝟓)
(𝑥1 , 𝑥2 ) >0
6 × 3 + 4 × 1.5 = 24 = 24
1 × 3 + 2 × 1.5 = 6 =6 Feasible
−1 × 3 + 1 × 1.5 = −1.5 < 1
1 × 1.5 = 1.5 <2

𝑧 = 5 × 3 + 4 × 1.5
𝒛 = 𝟐𝟏 (thousand) dollars
 7

f. (𝒙𝟏 , 𝒙𝟐 ) = (𝟐 , 𝟏)
(𝑥1 , 𝑥2 ) >0
6 × 2 + 4 × 1 = 16 < 24
1×2+2×1=4 <6 Feasible
−1 × 2 + 1 × 1 = −1 <1
1×1 = 1 <2

𝑧 =5×2+4×1
𝒛 = 𝟏𝟒 (thousand) dollars
g. (𝒙𝟏 , 𝒙𝟐 ) = (𝟐 , −𝟏)
𝑥1 > 0 , 𝑥2 < 0 → Infeasible

Conclusion: (e) gives the best feasible solution

Problem Example (3)
A company that operates 10 hours a day manufactures two products on
three sequential processes. The following table summarizes the data of the
problem:

Required: Formulate a linear programming model for this problem.

Solution
1. Decision variables (Unknowns):
𝒙𝟏 = Daily units of prpduct (1)
𝒙𝟐 = Daily units of prpduct (2)
2. Objective function:
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑧 = 2𝑥1 + 3𝑥2
 8

3. Constraints:
− Process 1: 10𝑥1 + 5𝑥2 ≤ 600 (10 hours × 60 minutes )
− Process 2: 6𝑥1 + 20𝑥2 ≤ 600 (10 hours × 60 minutes )
− Process 3: 8𝑥1 + 10𝑥2 ≤ 600 (10 hours × 60 minutes )
Nonnegativity restrictions
𝑥1 , 𝑥2 ≥ 0
The complete model is
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑧 = 2𝑥1 + 3𝑥2
Subject to
10𝑥1 + 5𝑥2 ≤ 600
6𝑥1 + 20𝑥2 ≤ 600
8𝑥1 + 10𝑥2 ≤ 600
𝑥1 , 𝑥2 ≥ 0

Problem Example (4)

The Gutchi Company manufactures purses, bags, and backpacks. The
construction includes leather and synthetics, leather being the scarce raw
material. The production process requires two types of skilled labor: sewing and
finishing. The following table gives the availability of the resources, their usage
by the three products, and the profits per unit.
Resource requirements per unit
Resource Purse Bag Backpack Daily availability
Leather 2 1 3 42
Sewing 2 1 2 40
Finishing 1 .5 1 45
profits per unit 24 22 45
Required: Formulate the problem as a linear program.
 9

Solution
1. Decision variables (Unknowns):
𝒙𝟏 = Number of purses per day
𝒙𝟐 = Number of bags per day
𝒙𝟑 = 𝑁𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑏𝑎𝑐𝑘𝑝𝑎𝑐𝑘𝑠 𝑝𝑒𝑟 𝑑𝑎𝑦
2. Objective function:
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑧 = 24𝑥1 + 22𝑥2 + 45𝑥3
3. Constraints:
− Leather: 2𝑥1 + 𝑥2 + 3𝑥3 ≤ 42
− Sewing: 2𝑥1 + 𝑥2 + 2𝑥3 ≤ 40
− Finishing: 𝑥1 + .5𝑥2 + 𝑥3 ≤ 45
Nonnegativity restrictions
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
The complete model is
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑧 = 24𝑥1 + 22𝑥2 + 45𝑥3
Subject to
2𝑥1 + 𝑥2 + 3𝑥3 ≤ 42
2𝑥1 + 𝑥2 + 2𝑥3 ≤ 40
𝑥1 + .5𝑥2 + 𝑥3 ≤ 45
𝑥1 , 𝑥2 , 𝑥3 ≥ 0

Problem Example (5)

ChemLabs uses raw materials I and II to produce two domestic cleaning
solutions, A and B. The daily availabilities of raw materials I and II are 150 and
145 units, respectively. One unit of solution A consumes .5 unit of raw material l
and .6 unit of raw material II, and one unit of solution B uses .5 unit of raw
material l and .4 unit of raw material II. The profits per unit of solutions A and B
are $8 and $10, respectively. The daily demand for solution A lies between 30
and 150 units, and that for solution B between 40 and 200 units. Formulate the
problem as a linear program.
 10

Solution
Raw material consumption per unit
Raw materials Solution A Solution B Daily availability
Raw material I .5 .5 150
Raw material II .6 .4 145
Profits per unit 8 10

1. Decision variables (Unknowns):

𝒙𝟏 = Units of solution 𝐴
𝒙𝟐 = Units of solution 𝐵
2. Objective function:
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑧 = 8𝑥1 + 10𝑥2
3. Constraints:
. 5𝑥1 + .5𝑥2 ≤ 150 (Raw material 𝐼)
. 6𝑥1 + .4𝑥2 ≤ 145 (Raw material 𝐼𝐼)
𝑥1 ≥ 30
(Daily demand for solution 𝐴)
𝑥1 ≤ 150
𝑥2 ≥ 40
(Daily demand for solution 𝐵)
𝑥2 ≤ 200
Nonnegativity restrictions
𝑥1 , 𝑥2 ≥ 0
The complete model is
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑧 = 8𝑥1 + 10𝑥2
Subject to
. 5𝑥1 + .5𝑥2 ≤ 150
. 6𝑥1 + .4𝑥2 ≤ 145
𝑥1 ≥ 30
𝑥1 ≤ 150
𝑥2 ≥ 40
𝑥2 ≤ 200
𝑥1 , 𝑥2 ≥ 0
 11

Problem Example (6)

Ozark Farms uses at least 800 pounds of special feed daily. The special
feed is a mixture of corn and soybean meal with the following compositions:
Pound per pound of
feedstuff
Feedstuff Protein Fiber Cost ($/Pound)
Corn .09 .02 .30
Soybean .60 .06 .90
The dietary requirements of the special feed are at least 30% protein and
at most 5% fiber. Ozark Farms wishes to determine the daily minimum-cost feed
mix.
Required: Formulate the problem as a linear program.

Solution
1. Decision variables (Unknowns):
Because the feed mix consists of corn and soybean meal, the decision
variables of the model are defined as
𝒙𝟏 = Pound of corn in the daily mix
𝒙𝟐 = Pound of soybean in the daily mix
2. Objective function:
The objective function seeks to minimize the total daily cost (in dollars) of
the feed mix and is thus expressed as
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑧 = .30𝑥1 + .90𝑥2
3. Constraints:
− The daily amount needed:
Because Ozark Farms needs at least 800 pounds of feed a day, the
associated constraint can be expressed as
𝑥1 + 𝑥2 ≥ 800
 12

− The dietary requirement:

As for the protein dietary requirement constraint, the amount of protein
included in 𝑥1 pounds of corn and 𝑥2 pounds of soybean is (. 09𝑥1 + .60𝑥2 )
pounds. This quantity should equal at least 30% of the total feed mix (𝑥1 + 𝑥2 )
pounds -that is,
. 09𝑥1 + .60𝑥2 ≥ .30(𝑥1 + 𝑥2 )
The constraint is simplified by moving the terms in x1 and 𝑥2 to the left-
hand side of the inequality, leaving only a constant on the right-hand side as
follows
. 09𝑥1 + .60𝑥2 ≥ .30(𝑥1 + 𝑥2 )
. 09𝑥1 + .60𝑥2 ≥ .30𝑥1 + .30𝑥2
. 09𝑥1 + .60𝑥2 − .30𝑥1 − .30𝑥2 ≥ 0
−.21𝑥1 + .30𝑥2 ≥ 0
In a similar manner, the fiber requirement of at most 5% is constructed as
. 02𝑥1 + .06𝑥2 ≤ .05(𝑥1 + 𝑥2 )
. 02𝑥1 + .06𝑥2 ≤ .05𝑥1 + .05𝑥2
. 02𝑥1 + .06𝑥2 . −05𝑥1 − .05𝑥2 ≤ 0
−.03𝑥1 + .01𝑥2 ≤ 0
Nonnegativity restrictions
𝑥1 , 𝑥2 ≥ 0
The complete model is
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑧 = .30𝑥1 + .90𝑥2
Subject to
𝑥1 + 𝑥2 ≥ 800
−.21𝑥1 + .30𝑥2 ≥ 0
−.03𝑥1 + .01𝑥2 ≤ 0
𝑥1 , 𝑥2 ≥ 0
 13

Graphical LP Solution
The graphical procedure includes two steps:
1. Determination of the feasible solution space.
2. Determination of the optimum solution from among all the feasible points
in the solution space.
The procedure uses two examples to show how maximization and
minimization objective functions are handled.
Solution of a Maximization Model
Problem Example
Consider the following LP:

Required: Determine the optimal solution for this problem using the
graphical method. Use (0,0) as a reference point.
 14

Solution
Step 1. Determination of the Feasible Solution Space:
First, we account for the nonnegativity constraints 𝑥1 ≥ 0 and 𝑥2 ≥ 0. In
Figure 1, the nonnegativity of the variables restricts the solution space area to
the first quadrant that lies above the 𝑥1 − axis and to the right of the 𝑥2 − axis
To account for the remaining four constraints, first, replace each
inequality with an equation and then graph the resulting straight line by locating
two distinct points on it as follows:
− First constraint
6𝑥1 + 4𝑥2 ≤ 24
By replacing the inequality with an equation, we get:
6𝑥1 + 4𝑥2 = 24
We can determine two distinct points by:
First setting 𝑥1 = 0 to obtain 𝑥2
6 × 0 + 4𝑥2 = 24
4𝑥2 = 24
24
𝑥2 =
4
𝑥2 = 6
∴ The first point is (0,6)
Then setting 𝑥2 = 0 to obtain 𝑥1
6𝑥1 + 4 × 0 = 24
6𝑥1 = 24
24
𝑥1 =
6
𝑥1 = 4
∴ The second point is (4,0)
Thus, the line passes through the two points (0,6) and (4,0), as shown by line (1)
in Figure 1.
 15

Next, consider the effect of the inequality. All it does is divide the (𝑥1 , 𝑥2 )-
plane into two half-spaces, one on each side of the graphed line. Only one of
these two halves satisfies the inequality.
To determine the correct side, use (0,0) as a reference point. If it satisfies
the inequality, then the side in which it lies is the feasible half-space, otherwise,
the other side is.
The use of the reference point (0,0) is illustrated with the constraint
(6𝑥1 + 4𝑥2 ≤ 24). Because (6 × 0 + 4 × 0 = 0) is less than 24, the half-space
representing the inequality includes the reference point (0,0) as shown by the
arrow in Figure 1.
Note that:
It is convenient computationally to use (0,0) as the reference point, unless
the line happens to pass through the origin (when the right hand side of the
inequality is equal to zero), in which case any other point can be used.

Figure 1
 16

− Second constraint
𝑥1 + 2𝑥2 ≤ 6
𝑥1 + 2𝑥2 = 6
6
Setting 𝑥1 = 0 to obtain 𝑥2 = 2 = 3 → The first point is (0,3)
Setting 𝑥2 = 0 to obtain 𝑥1 = 6 → The second point is (6,0)
Thus, the line passes through the two points (0,3) and (6,0), as shown by line (2)
in Figure 1.
The use of the reference point (0,0) is illustrated with the constraint
(𝑥1 + 2𝑥2 ≤ 6). Because (1 × 0 + 2 × 0 = 0) is less than 6, the half-space
representing the inequality includes the reference point (0,0).
− Third constraint
−𝑥1 + 𝑥2 ≤ 1
−𝑥1 + 𝑥2 = 1
Setting 𝑥1 = 0 to obtain 𝑥2 = 1 → The first point is (0,1)
Setting 𝑥2 = 2 to obtain 𝑥1 = 1 → The second point is (1,2)
Thus, the line passes through the two points (0,1) and (1,2), as shown by line (3)
in Figure 1.
Note that:
The use of the reference point (0,0) is illustrated with the constraint
(−𝑥1 + 𝑥2 ≤ 1). Because (−1 × 0 + 1 × 0 = 0) is less than 1, the half-space
representing the inequality includes the reference point (0,0).
− Fourth constraint
𝑥2 ≤ 2
𝑥2 = 2 (Note that: in this constraint 𝑥1 = 0)
Thus, the line passes through the point (0,2) and parallels the 𝑥1 − axis, which
means that for any value of 𝑥1 , the value of 𝑥2 will equal to 2 as shown by line (4)
in Figure 1.
The use of the reference point (0,0) is illustrated with the constraint
(𝑥2 ≤ 2). Because (0 × 0 + 1 × 0 = 0) is less than 2, the half-space representing
the inequality includes the reference point (0,0).
 17

The feasible solution space of the problem represents the area in the first
quadrant in which all the constraints are satisfied simultaneously. In Figure 1,
any point in or on the boundary of the area ABCDEF is part of the feasible
solution space. All points outside this area are infeasible.
Step 2. Determination of the Optimum Solution:
The feasible space in Figure 1 is delineated by the line segments joining
the points A, B, C, D, E, and F. Any point within or on the boundary of the space
ABCDEF is feasible. Because the feasible space ABCDEF consists of an infinite
number of points, we need a systematic procedure to identify the optimum
solution.
An important characteristic of the optimum LP solution is that it is always
associated with a corner point of the solution space (where two lines intersect).
The observation that the LP optimum is always associated with a corner
point means that the optimum solution can be found simply by enumerating all
the corner points A, B, C, D, E, and F.
First, we have to determine the values of 𝑥1 and 𝑥2 associated with all the
corner points A, B, C, D, E, and F as follows:
− Corner point “A”
The values of 𝑥1 and 𝑥2 associated with the corner point “A” are (0,0).
− Corner point “B”
The values of 𝑥1 and 𝑥2 associated with the corner point “B” are (4,0).
− Corner point “C”
The values of 𝑥1 and 𝑥2 associated with the corner point “C” are determined by
solving the equations associated with lines (1) and (2) -that is,
6𝑥1 + 4𝑥2 = 24
𝑥1 + 2𝑥2 = 6
Multiply the second equation by 2:
2𝑥1 + 4𝑥2 = 12
 18

Subtract the new second equation from the first one:

6𝑥1 + 4𝑥2 = 24
− 2𝑥1 + 4𝑥2 = 12
4𝑥1 = 12
12
𝑥1 =
4
𝑥1 = 3
Substitute the value of 𝑥1 into either of the original equations to find the value
of 𝑥2 :
𝑥1 + 2𝑥2 = 6
1 × 3 + 2𝑥2 = 6
3 + 2𝑥2 = 6
2𝑥2 = 6 − 3
2𝑥2 = 3
3
𝑥2 =
2
𝑥2 = 1.5
∴ The values of 𝑥1 and 𝑥2 associated with the corner point “C” are (3,1.5).

− Corner point “D”

The values of 𝑥1 and 𝑥2 associated with the corner point “D” are determined by
solving the equations associated with lines (2) and (4) -that is,
𝑥1 + 2𝑥2 = 6
𝑥2 = 2
Substitute the value of 𝑥2 into the first equation to find the value of 𝑥1 :
𝑥1 + 2𝑥2 = 6
𝑥1 + 2 × 2 = 6
𝑥1 + 4 = 6
𝑥1 = 6 − 4
𝑥1 = 2
∴ The values of 𝑥1 and 𝑥2 associated with the corner point “D” are (2,2).
 19

− Corner point “E”

The values of 𝑥1 and 𝑥2 associated with the corner point “E” are determined by
solving the equations associated with lines (3) and (2) -that is,
−𝑥1 + 𝑥2 = 1
𝑥2 = 2
Substitute the value of 𝑥2 into the first equation to find the value of 𝑥1 :
−𝑥1 + 𝑥2 = 1
−𝑥1 + 1 × 2 = 1
− 𝑥1 + 2 = 1
− 𝑥1 = 1 − 2
− 𝑥1 = −1
𝑥1 = 1
∴ The values of 𝑥1 and 𝑥2 associated with the corner point “E” are (1,2).

− Corner point “F”

The values of 𝑥1 and 𝑥2 associated with the corner point “F” are (0,1).
Now, we have to substitute the values of 𝑥1 and 𝑥2 associated with all the
corner points A, B, C, D, E, and F into the objective function as the following table
shows:

Corner point (𝑥1 , 𝑥2 ) 𝑧 = 5𝑥1 + 4𝑥2

A (0,0) 𝑧 = (5 × 0) + (4 × 0) = 0
B (4,0) 𝑧 = (5 × 4) + (4 × 0) = 20
C (3,1.5) 𝑧 = (5 × 3) + (4 × 1.5) = 21 (Optimum)
D (2,2) 𝑧 = (5 × 2) + (4 × 2) = 18
E (1,2) 𝑧 = (5 × 1) + (4 × 2) = 13
F (0,1) 𝑧 = (5 × 0) + (4 × 1) = 4

∴ The optimal solution is 𝑥1 = 3 and 𝑥2 = 1.5 with 𝑧 = 21 (recall that we are

maximizing z)
 20

Solution of a Minimization Model

Problem Example:
Consider the following LP:
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑧 = .30𝑥1 + .90𝑥2
Subject to
𝑥1 + 𝑥2 ≥ 800 1

−.21𝑥1 + .30𝑥2 ≥ 0 2

−.03𝑥1 + .01𝑥2 ≤ 0 3

𝑥1 , 𝑥2 ≥ 0
Required: Determine the optimal solution for this problem using graphical
method. Use (0,0) and (100,0) as reference points.
Solution
Step 1. Determination of the Feasible Solution Space:
• Replace each inequality with an equation and graph the resulting straight
line as follows:
− First constraint
𝑥1 + 𝑥2 ≥ 800
𝑥1 + 𝑥2 = 800
Setting 𝑥1 = 0 to obtain 𝑥2 = 800 → The first point is (0,800)
Setting 𝑥2 = 0 to obtain 𝑥1 = 800 → The second point is (800,0)
Thus, the line passes through the two points (0,800) and (800,0), as shown by
line (1) in Figure 2.
The use of the reference point (0,0) is illustrated with the constraint
(𝑥1 + 𝑥2 ≥ 800). Because (1 × 0 + 1 × 0 = 0) is not greater than or equal to 800,
the half-space representing the inequality does not include the reference point
(0,0) as shown by the arrow in Figure 2.
 21

Figure 2
− Second constraint
−.21𝑥1 + .30𝑥2 ≥ 0
−.21𝑥1 + .30𝑥2 = 0
This constraint passes through the origin (0,0). To plot the associated straight
line, we need one additional point, which can be obtained by assigning a value to
one of the variables and then solving for the other variable as follows.
Setting 𝑥1 = 100 will yield:
−.21𝑥1 + .30𝑥2 = 0
−.21 × 100 + .30𝑥2 = 0
−21 + .30𝑥2 = 0
. 30𝑥2 = 21
21
𝑥2 =
. 30
𝑥2 = 70 → The second point is (100,70)
Thus, the line passes through the two points (0,0) and (100,70), as shown by line
(2) in Figure 2.
 22

Note that: (0,0) cannot be used as a reference point for this constraint, because
the line passes through the origin. Instead, any other point [e.g., (100, 0)] can be
used for that purpose.
The use of the reference point (100,0) is illustrated with the constraint
(−.21𝑥1 + .30𝑥2 ≥ 0). Because (−.21 × 100 + .30 × 0 = −21) is not greater than or
equal to 0, the half-space representing the inequality does not include the
reference point (100,0).
− Third constraint
−.03𝑥1 + .01𝑥2 ≤ 0
−.03𝑥1 + .01𝑥2 = 0
This constraint, also, passes through the origin (0,0). The second point can be
obtained as follows.
Setting 𝑥1 = 100 will yield:
−.03𝑥1 + .01𝑥2 = 0
−.03 × 100 + .01𝑥2 = 0
−3 + .01𝑥2 = 0
. 01𝑥2 = 3
3
𝑥2 =
. 01
𝑥2 = 300 → The second point is (100,300)
Thus, the line passes through the two points (0,0) and (100,300), as shown by
line (3) in Figure 2.
The use of the reference point (100,0) is illustrated with the constraint
(−.03𝑥1 + .01𝑥2 ≤ 0). Because (−.03 × 100 + .01 × 0 = −3) is less than 0, the half-
space representing the inequality includes the reference point (100,0).

• The feasible solution space of the problem represents the area in the
first quadrant in which all the constraints are satisfied simultaneously. In
Figure 2, any point in or on the boundary of the area AB is part of the
feasible solution space. All points outside this area are infeasible.
 23

Step 2. Determination of the Optimum Solution:

First, we have to determine the values of 𝑥1 and 𝑥2 associated with the
corner points A and B as follows:
− Corner point “A”
The values of 𝑥1 and 𝑥2 associated with the corner point “A” are determined by
solving the equations associated with lines (1) and (3) -that is,
𝑥1 + 𝑥2 = 800
−.03𝑥1 + .01𝑥2 = 0
Multiply the first equation by .03:
. 03𝑥1 + .03𝑥2 = 24
Add the new first equation to the second one:
.03𝑥1 + .03𝑥2 = 24
−.03𝑥1 + .01𝑥2 = 0

. 04𝑥2 = 24
24
𝑥2 =
. 04
𝑥2 = 600
Substitute the value of 𝑥2 into either of the original equations to find the value
of 𝑥1 :
𝑥1 + 𝑥2 = 800
𝑥1 + 1 × 600 = 800
𝑥1 + 600 = 800
𝑥1 = 800 − 600
𝑥1 = 200
∴ The values of 𝑥1 and 𝑥2 associated with the corner point “A” are (200,600).

− Corner point “B”

The values of 𝑥1 and 𝑥2 associated with the corner point “B” are determined by
solving the equations associated with lines (1) and (2) -that is,
𝑥1 + 𝑥2 = 800
−.21𝑥1 + .30𝑥2 = 0
 24

Multiply the first equation by .21:

. 21𝑥1 + .21𝑥2 = 168
Add the new first equation to the second one:
.21𝑥1 + .21𝑥2 = 168
−.21𝑥1 + .30𝑥2 = 0

. 51𝑥2 = 168
168
𝑥2 =
. 51
𝑥2 = 329.4
Substitute the value of 𝑥2 into either of the original equations to find the value
of 𝑥1 :
𝑥1 + 𝑥2 = 800
𝑥1 + 1 × 329.4 = 800
𝑥1 + 329.4 = 800
𝑥1 = 800 − 329.4
𝑥1 = 470.6
∴ The values of 𝑥1 and 𝑥2 associated with the corner point “B” are
(470.6,329.4).

Now, we have to substitute the values of 𝑥1 and 𝑥2 associated with the

corner points A and B into the objective function as the following table shows:

Corner point (𝑥1 , 𝑥2 ) 𝑧 = .30𝑥1 + .90𝑥2

A (200,600) 𝑧 = (. 30 × 200) + (. 90 × 600) = 600
B (Optimum) (470.6,329.4) 𝑧 = (. 30 × 470.6) + (. 90 × 329.4) = 437.64

∴ The optimal solution is 𝑥1 = 470.6 and 𝑥2 = 329.4 with 𝑧 = 437.64 (recall

that we are minimizing z)
 25

Unsolved Problems:
[1] A company produces two products, A and B. The sales volume for A is at
least 80% of the total sales of both A and B. However, the company cannot
sell more than 100 units of A per day. Both products use one raw material,
of which the maximum daily availability is 240 pounds. The usage rates of
the raw material are 2 pounds per unit of A and 4 pounds per unit of B.
The profit units for A and B are $20 and $50, respectively. Determine the
optimal product mix for the company.
Required:
a. Formulate a linear programming model for this problem.
b. Determine the optimal production mix for this company using
graphical method. Use (0,0) and (100,0) as reference points.

[2] The Burroughs Garment Company manufactures men's shirts and

women's blouses for Walmark Discount Stores. Walmark will accept all
the production supplied by Burroughs. The production process includes
cutting, sewing, and packaging. Burroughs employs 25 workers in the
cutting department, 35 in the sewing department, and 5 in the packaging
department. The following table gives the time requirements and profits
per unit for the two garments:

Burroughs wants to determine the optimal hourly production schedule.

Required:

a. Formulate a linear programming model for this problem.

b. Determine the optimal hourly production schedule for this company
using graphical method. Use (0,0) as a reference point.
 26

[3] JOBCO produces two products on two machines. A unit of product 1

requires 2 hours on machine 1 and 1 hour on machine 2. For product 2, a
unit requires 1 hour on machine 1 and 3 hours on machine 2. The profits
per unit of products 1 and 2 are $30 and $20, respectively. The total daily
processing time available for each machine is 8 hours.
Required:
a. Formulate a linear programming model for this problem.
b. Determine the optimal production mix for the company. Use (0,0) as a
reference point.