Operations Research 1

CH.2: MODELING WITH LINEAR

PROGRAMMING
Fall19 Dr. Ahmed Alhasani
 Chapter Objectives
1) Two-Variable LP Model
2) Graphical LP Solution
3) Four Special Cases in LP
4) Selected LP Applications
5) Computer Solution with Excel Solver

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 2

 Introduction
qMany management decisions involve trying to make the most
effective use of limited resources:
ØMachinery, labor, money, time, warehouse space, raw materials.
qLinear programming (LP): is a widely used mathematical modeling
technique designed to help managers in planning and decision
making relative to resource allocation.
qBelongs to the broader field of mathematical programming.
qIn this sense, programming refers to modeling and solving a
problem mathematically.
Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 3
 Requirements of a LP Problem
qLP has been applied in many areas over the past 50 years.
qAll LP problems have 4 properties in common:
1) All problems seek to maximize or minimize some quantity (the
objective function).
2) The presence of restrictions or constraints that limit the degree
to which we can pursue our objective.
3) There must be alternative courses of action to choose from.
4) The objective and constraints in problems must be expressed in
terms of linear equations or inequalities.
Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 4
 Examples of Successful
LP Applications
qDevelopment of a production schedule that will:
ØSatisfy future demands for a firm’s production.
ØWhile minimizing total production and inventory costs.
qDetermination of grades of petroleum products to yield the
maximum profit.
qSelection of different blends of raw materials to feed mills to
produce finished feed combinations at minimum cost.
qDetermination of a distribution (transportation) system that will
minimize total shipping cost from several warehouses to various
market locations.
Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 5
 LP Properties and Assumptions
qProperties of LP:-
1) One objective function.
2) One or more constraints.
3) Alternative courses of action.
4) Objective function and constraints are linear.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 6

 LP Properties and Assumptions
qAssumption of LP:-
1) Certainty.
2) Proportionality.
3) Additivity.
4) Divisibility.
5) Nonnegative variables.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 7

 Basic Assumptions of LP
qWe assume conditions of certainty exist and numbers in the
objective and constraints are known with certainty and do not
change during the period being studied.
qWe assume proportionality exists in the objective and constraints:
ØConstancy between production increases and resource utilization –
if 1 unit needs 3 hours then 10 require 30 hours.
qWe assume additivity in that the total of all activities equals the
sum of the individual activities.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 8

 Basic Assumptions of LP
qWe assume divisibility in that solutions need not be whole
numbers.
qAll answers or variables are nonnegative as we are dealing with
real physical quantities.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 9

 Formulating LP Problems
qFormulating a linear program involves developing a mathematical
model to represent the managerial problem.
qThe steps in formulating a linear program are:
1) Completely understand the managerial problem being faced.
2) Identify the objective and constraints.
3) Define the decision variables.
4) Use the decision variables to write mathematical expressions for
the objective function and the constraints.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 10

 Formulating LP Problems
qOne of the most common LP applications is the product mix
problem:
qTwo or more products are produced using limited resources such
as personnel, machines, and raw materials.
qThe profit that the firm seeks to maximize is based on the profit
contribution per unit of each product.
qThe company would like to determine how many units of each
product it should produce so as to maximize overall profit given its
limited resources.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 11

 Two-Variable LP Model
qThis section deals with the graphical solution of a two-variable LP.
qThough two-variable problems hardly exist in practice, the
treatment provides concrete foundations for the development of the
general simplex algorithm.
qStarting with Solution of a Maximization Model.
qNext, Solution of a Minimization Model.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 12

 Solution of a Maximization Model
Example 2.1-1 The Reddy Mikks Co.
qReddy Mikks produces both interior and exterior paints from two
raw materials, M1 and M2.
qThe following table provides the basic data of the problem:

Tons of Raw Material per Ton of

Exterior Paint Interior Paint Maximum Daily Availability (Tons)
Raw Material (M1) 6 4 24
Raw Material (M2) 1 2 6
Profit per Ton ($1000) 5 4

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 13

 Example 2.1-1 The Reddy Mikks Co.
qA 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.
qReddy Mikks wants to determine the optimum (best) product mix
of interior and exterior paints that maximizes the total daily profit.
qThe LP model, as in any OR model, has three basic components:
1) Decision variables that we seek to determine.
2) Objective (goal) that we need to optimize (maximize or minimize).
3) Constraints that the solution must satisfy.
Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 14
 Example 2.1-1 The Reddy Mikks Co.
Decision Variables:
x1 = Tons produced daily of exterior paint.
x2 = Tons produced daily of interior paint.
Objective Function:
For the Reddy Mikks problem, we need to determine the daily
amounts to be produced of exterior and interior paints.
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.
Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 15
 Example 2.1-1 The Reddy Mikks Co.
Given that the profits per ton of exterior and interior paints are 5 and
4 (thousand) dollars, respectively:
Total profit from exterior paint = 5x1 (thousand) dollars
Total profit from interior paint = 4x2 (thousand) dollars
Letting z represent the total daily profit (in thousands of dollars), the
objective of the company is:
Maximize z = 5x1+ 4x2

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 16

 Example 2.1-1 The Reddy Mikks Co.
Constraints:
Next, we construct the constraints that restrict raw material usage
and product demand. The raw material restrictions are expressed
verbally as:
(Usage of Raw Material by both Paints) ≤ (Max Raw Material Availability)
The daily usage of raw material M1 is 6 tons per ton of exterior paint
and 4 tons per ton of interior paint:
Usage of raw material M1 by exterior paint = 6x1 tons/day
Usage of raw material M1 by interior paint = 4x2 tons/day
Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 17
 Example 2.1-1 The Reddy Mikks Co.
Hence:
Usage of raw material M1 by both paints = 6x1+ 4x2 tons/day
In a similar manner:
Usage of raw material M2 by both paints = 1x1+ 2x2 tons/day

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 18

 Example 2.1-1 The Reddy Mikks Co.
Because the daily availabilities of raw materials M1 and M2 are
limited to 24 and 6 tons, respectively, the associated restrictions are
given as:
6x1+ 4x2 ≤ 24 (Raw Material M1)
x1+ 2x2 ≤ 6 (Raw Material M2)

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 19

 Example 2.1-1 The Reddy Mikks Co.
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:
x2 – x1 ≤ 1 (Market Limit)
The second demand restriction stipulates that the maximum daily
demand of interior paint is limited to 2 tons, which translates to:
x2 ≤ 2 (Demand limit)

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 20

 Example 2.1-1 The Reddy Mikks Co.
An implicit (or "understood-to-be") restriction is that variables x1 and
x2 cannot assume negative values.
The nonnegativity restrictions:
x1 ≥ 0; x2 ≥ 0

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 21

 Example 2.1-1 The Reddy Mikks Co.
qThe Complete Reddy Mikks Model is:
Maximize z = 5x1+ 4x2
Subject to
Slack Variable = s1 6x1+ 4x2 ≤ 24 (1)
6x1 + 4x2 + s1 = 24
x1+ 2x2 ≤ 6 (2)
–x1+ x2 ≤ 1 (3)
x2 ≤ 2 (4)
x1, x2 ≥ 0 (5)
Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 22
 Example 2.1-1 The Reddy Mikks Co.
qTypes of Solutions:-
A. Feasible Solution: Any values of x1 and x2 that satisfy all FIVE
constraints. Otherwise, the solution is infeasible.
vFor example the following solution is Feasible because it doesn’t
violate any of the constraints including the nonnegativity restriction:
Feasible Solution
x1 = 3 tons per day
x2 = 1 tons per day

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 23

 Example 2.1-1 The Reddy Mikks Co.
vVerification Step: We substitute (x1 = 3, x2 = 1) in the left-hand side
of each constraint:

6(3) + 4(1) ≤ 24 (1)

(3)+ 2(1) ≤ 6 (2)
–(3)+(1) ≤ 1 (3)
(1) ≤ 2 (4)
(3), (1) ≥ 0 (5)

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 24

 Example 2.1-1 The Reddy Mikks Co.
qThe feasible solution of the complete Reddy Mikks Model is:
The total tons produced daily of exterior paint = 3
The total tons produced daily of interior paint = 1
Maximize z = 5(3)+ 4(1)
z = 15 + 4
z = 19
The total daily profit = $19,000
The total daily profit of exterior paint = $15,000
The total daily profit of interior paint = $4,000
Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 25
 Example 2.1-1 The Reddy Mikks Co.
qThe unused amounts of raw materials M1 and M2:
Usage of raw material M1 by both paints = 6(3) + 4(1) tons/day
Usage of raw material M1 by both paints = 22 tons/day

Usage of raw material M2 by both paints = 1(3) + 2(1) tons/day

Usage of raw material M2 by both paints = 5 tons/day
Exterior Paint Interior Paint Maximum Daily Availability (Tons)
Raw Material (M1) 6 4 24
Raw Material (M2) 1 2 6
Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 26
 Example 2.1-1 The Reddy Mikks Co.
B. Infeasible Solution: Any values of x1 and x2 that does not satisfy
ANY of the FIVE constraints.
vFor example the following solution is Infeasible because it violates
the 1st and 4th constraints:
Infeasible Solution
x1 = 4 tons per day
x2 = 1 tons per day

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 27

 Example 2.1-1 The Reddy Mikks Co.
vVerification Step: We substitute (x1 = 4, x2 = 1) in the left-hand side
of each constraint:

6(4) + 4(1) ≤ 24 (1) ×

(4)+ 2(1) ≤ 6 (2)
–(4)+(1) ≤ 1 (3)
(4) ≤ 2 (4) ×
(4), (1) ≥ 0 (5)

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 28

 Example 2.1-1 The Reddy Mikks Co.
qThe infeasible solution of the complete Reddy Mikks Model is:
The total tons produced daily of exterior paint = 4
The total tons produced daily of interior paint = 1
Maximize z = 5(4)+ 4(1)
z = 20 + 4
z = 24
The total daily profit = $24,000
The total daily profit of exterior paint = $20,000
The total daily profit of interior paint = $4,000
Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 29
 Example 2.1-1 The Reddy Mikks Co.
qThe unused amounts of raw materials M1 and M2:
Usage of raw material M1 by both paints = 6(4) + 4(1) tons/day
Usage of raw material M1 by both paints = 28 tons/day
×
Usage of raw material M2 by both paints = 1(4) + 2(1) tons/day
Usage of raw material M2 by both paints = 6 tons/day
Exterior Paint Interior Paint Maximum Daily Availability (Tons)
Raw Material (M1) 6 4 24 ×
Raw Material (M2) 1 2 6
Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 30
 Example 2.1-1 The Reddy Mikks Co.
C. The Optimum Solution: The goal of the problem is to find the
best feasible solution that maximize the total profit.
vBefore we can do that, we need to know how many feasible
solutions the Reddy Mikks problem has.
vThe answer, as we will see from the graphical solution in the next
section, is “an infinite number”, which makes it impossible to solve
the problem by enumeration.
vInstead, we need a systematic procedure that will locate the
optimum solution in a finite number of steps.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 31

 Homework
1) For the Reddy Mikks model, construct each of the following
constraints and express it with a linear left and right-hand side:
a) The daily demand for interior paint exceeds that of exterior paint
by at least 1 ton.
b) The daily usage of raw material M2 in tons is at most 6 and at
least 3.
c) The demand for interior paint cannot be less than the demand for
exterior paint.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 32

 Homework
d) The minimum quantity that should be produced of both the
interior and the exterior paint is 3 tons.
e) The proportion of interior paint to the total production of both
interior and exterior paints must not exceed 0.5.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 33

 Homework
2) Determine the best feasible solution among the following
(feasible and infeasible) solutions of the Reddy Mikks model:
a) x1 = 1, x2 = 4.
b) x1 = 2, x2 = 2.
c) x1 = 3, x2 = 1.5.
d) x1 = 2, x2 = 1.
e) x1 = 2, x2 = – 1.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 34

 Homework
3) For the feasible solution x1 = 2, x2 = 2 of the Reddy Mikks model,
determine the unused amounts of raw materials M1 and M2?

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 35

 Graphical LP Solution
qThe 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.
qThe procedure uses two examples to show how maximization and
minimization objective functions are handled.
qIt is the easiest way to solve a small LP problem is with graphical
solution approach.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 36

 Graphical LP Solution
qThe graphical method only works when there are just two decision
variables.
qWhen there are more than two variables, a more complex
approach is needed as it is not possible to plot the solution on a
two-dimensional graph.
qThe graphical method provides valuable insight into how other
approached work.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 37

 Graphical LP Solution of
Example 2.1-1 The Reddy Mikks Co.
Step 1: Determination of the Feasible Solution Space.
First, we account for the nonnegativity constraints x1 ≥ 0 and x2 ≥ 0.
In the next graph, the horizontal axis x1 and the vertical axis x2
represent the exterior- and interior-paint variables, respectively.
Thus, the nonnegativity of the variables restricts the solution- space
area to the first quadrant that lies above the x1-axis and to the right
of the x2-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.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 38

 Graphical LP Solution of
Example 2.1-1 The Reddy Mikks Co.
For example, after replacing 6x1 + 4X2 ≤ 24 with the straight line
6x1 + 4X2 = 24, we can determine two distinct points by first setting x1
= 0 to obtain x2 = 6 and then setting x2 = 0 to obtain x1 = 4.
Thus, the line passes through the two points (0,6) and (4,0), as shown
by line (1) in the next graph.
Next, consider the effect of the inequality. All it does is divide the (x1,
x2)-plane into two half-spaces, one on each side of the graphed line.
Only one of these two halves satisfies the inequality.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 39

 Graphical LP Solution of
Example 2.1-1 The Reddy Mikks Co.
To determine the correct side, choose (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
6x1 + 4x2 ≤ 24.
Because 6 x 0 + 4 x 0 = 0 is less than 24, the half-space representing
the inequality includes the origin (as shown by the arrow in the plot).
It is convenient computationally to select (0,0) as the reference point,
unless the line happens to pass through the origin, in which case any
other point can be used.
Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 40
 Graphical LP Solution of
Example 2.1-1 The Reddy Mikks Co.
For example, if we use the reference point (6,0), the left-hand side of
the first constraint is 6 X 6 + 4 X 0 = 36, which is larger than its right-
hand side (= 24), which means that the side in which (6,0) lies is not
feasible for the inequality 6x1 + 4x2 ≤ 24.
The conclusion is consistent with the one based on the reference
point (0,0).
Application of the reference-point procedure to all the constraints of
the model produces the constraints shown in the plot(verify!).

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 41

 Graphical LP Solution of
Example 2.1-1 The Reddy Mikks Co.
The feasible solution space of the problem represents the area in the
1st quadrant in which all the constraints are satisfied simultaneously.
In the plot, 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.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 42

Graphical Representation of a Constrain
x2

100 –
– This Axis Represents the interior Nonnegative Constraint x2 ≥ 0
Number of Tons 80 –
–
60 –
–
40 –
– This Axis Represents the Exterior Nonnegative Constraint x1 ≥ 0
20 –
–
– | | | | | | | | | | | |
0 20 40 60 80 100 x1
Number of Tons

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 43

 6xl + 4x2 = 24, we can determine two distinct points by first setting XI = 0 to
obtain X2 = ¥ = 6 and then setting X2 = 0 to obtain XI = = 4. Thus, the line
passes through the two points (0,6) and (4,0), as shown by line (1) in Figure 2.1.

Graphical Representation of the

Next, consider the effect of the inequality. All it does is divide the (xJ, x2)-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, choose (0,0) as a

Constrains of the Reddy Mikks Model

reference point. If it satisfies the inequality, then the side in which it lies is the

FIGURE 2.1
Feasible space of the Reddy Mikks model

Constraints:
6
6xI + 4x2:$ 24 CD
Xl + 2x2 :$ 6 @
5
-Xl + x2:$ 1 CD
x2:$ 2 (1)
4
XI 2: 0 @

3
x22: 0 ®

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 44

 Graphical LP Solution of
Example 2.1-1 The Reddy Mikks Co.
Step 2: Determination of the Optimum Solution.
The feasible space in the plot 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.
The determination of the optimum solution requires identifying the
direction in which the profit function z = 5x1 + 4x2 increases (recall
that we are maximizing z).
Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 45
 Graphical LP Solution of
Example 2.1-1 The Reddy Mikks Co.
We can do so by assigning arbitrary increasing values to z. For
example, using z = 10 and z = 15 would be equivalent to graphing the
two lines 5x1 + 4x2 = 10 and 5x1 + 4x2 = 15. Thus, the direction of
increase in z is as shown the plot.
The optimum solution occurs at C, which is the point in the solution
space beyond which any further increase will put z outside the
boundaries of ABCDEF.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 46

 Graphical LP Solution of
Example 2.1-1 The Reddy Mikks Co.
The values of x1 and x2 associated with the optimum point C are
determined by solving the equations associated with lines (1) and (2):
6x1 + 4x2 = 24
x1 +2x2 = 6
The solution is x1 = 3 and x2 = 1.5 with z = 5 X 3 + 4 X 1.5 = 21.
This calls for a daily product mix of 3 tons of exterior paint and 1.5
tons of interior paint. The associated daily profit is $21,000.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 47

 Graphical LP Solution of
Example 2.1-1 The Reddy Mikks Co.
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). This is true even if the objective function
happens to be parallel to a constraint.
For example, if the objective function is z = 6x1 + 4x2, which is parallel
to constraint 1, we can always say that the optimum occurs at either
corner point B or comer point C.
Actually any point on the line segment BC will be an alternative
optimum, but the important observation here is that the line
segment BC is totally defined by the corner points B and C.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 48

 Graphical LP Solution of
Example 2.1-1 The Reddy Mikks Co.
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 as the following table shows:
Corner Point (x1, x2) z
A (0, 0) 0
B (4, 0) 20
C (3, 1.5) 21 (Optimum – Max)
D (2, 2) 18
E (1, 2) 13
F (0, 1) 4

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 49

 Graphical LP Solution of
Example 2.1-1 The Reddy Mikks Co.
As the number of constraints and variables increases, the number of
corner points also increases, and the proposed enumeration
procedure becomes less tractable computationally.
Nevertheless, the idea shows that, from the standpoint of
determining the LP optimum, the solution space ABCDEF with its
infinite number of solutions can, in fact, be replaced with a finite
number of promising solution points-namely, the corner points, A, B,
C, D, E, and F.
This result is key for the development of the general algebraic
algorithm, called the Simplex Method.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 50

 Graphical Representation of the
Optimum Solution of the Reddy Mikks Model
18 Chapter 2 Modeling with Linear Programming

(Maximize z = 5Xl + 4x2)

,,

2
, Optimum: Xl = 3 tons
>l< / x2 = 1.5 tons
Z = $21,000

Xl
o 2', , 4 '

FIGURE 2.2
Optimum solution of the Reddy Mikks model

Operationsciated
Research: An Introduction. Hamdy A. Taha, 8thalways
An important characteristic of the optimum LP solution is that it is
Edition.
asso-
with a cornel" point of the solution space (where two lines intersect). This is
51
 Homework
4) A company that operates 10 hours a day manufactures two
products on three-sequential processes. The following table
summarizes the data of the problem:
Minutes per Unit
Product Process 1 Process 2 Process 3 Unit Profit
1 10 6 8 $2
2 5 20 10 $3

Determine the optimal mix of the two products by:

a) Formulating the problem?
b) Graphing the feasible solution and highlighting the corner points?
Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 52
 Solution of a Minimization Model
Example 2.2-2 Diet Problem
Ozark Farms uses at least 800 lb of special feed daily. The special feed
is a mixture of corn and soybean meal with the following
compositions:
lb per lb of Feedstuff
Feedstuff Protein Fiber Cost ($/lb)
Corn 0.09 0.02 0.30
Soybean Meal 0.60 0.06 0.90
The Daily Req. ≥ 30% ≤ 5%
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.
Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 53
 Example 2.2-2 Diet Problem
Decision Variables:-
Because the feed mix consists of corn and soybean meal, the decision
variables of the model are defined as:
x1 = lb of corn in the daily mix
x2 = lb of soybean meal in the daily mix
The objective Function seeks to minimize the total daily cost (in
dollars) of the feed mix and is thus expressed as:
Minimize z = 0.3x1 + 0.9x2

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 54

 Example 2.2-2 Diet Problem
The Constraints:-
The constraints of the model reflect the daily amount needed and
the dietary requirements.
The Daily Amount Needed:-
Because Ozark Farms needs at least 800 Ib of feed a day, the
associated constraint can be expressed as:

x1 + x2 ≥ 800

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 55

 Example 2.2-2 Diet Problem
The Dietary Requirements Needed:-
Protein Requirement Constraint: the amount of protein included in
x1 lb of corn and x2 lb of soybean meal is:
(0.09x1 + 0.6x2 lb).
This quantity should equal at least 30% of the total feed mix:
(x1 + x2) lb.
That is:
0.09x1 + 0.6x2 ≥ 0.3(x1 + x2) 1

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 56

 Example 2.2-2 Diet Problem
The Dietary Requirements Needed:-
Fiber Requirement Constraint: the amount of fiber included in x1 lb
of corn and x2 lb of soybean meal is:
(0.02x1 + 0.06x2 lb).
This quantity should equal at most 5% of the total feed mix:
(x1 + x2) lb.
That is:
0.02x1 + 0.06x2 ≤ 0.05(x1 + x2) 2

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 57

 Example 2.2-2 Diet Problem
The constraints (1 and 2) are simplified by moving the terms in x1 and
x2 to the left-hand side of each inequality, leaving only a constant on
the right-hand side:

– 0.21x1 + 0.3x2≥ 0 1

– 0.03x1 + 0.01x2≤ 0 2

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 58

 Example 2.2-2 Diet Problem
qThe Complete Diet Problem Model is:
Minimize z = 0.3x1 + 0.9x2
Subject to
x1 + x2 ≥ 800
– 0.21x1 + 0.30x2 ≥ 0
– 0.03x1 + 0.01x2 ≤ 0
x1, x2 ≥ 0

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 59

 Example 2.2-2 Diet Problem
qTypes of Solutions:-
A. Feasible Solution: Any values of x1 and x2 that satisfy all FOUR
constraints. Otherwise, the solution is infeasible.
vFor example the following solution is Feasible because it doesn’t
violate any of the constraints including the nonnegativity restriction:
Feasible Solution
x1 = 250 lb of Corn in the Daily Mix
x2 = 750 lb of Soybean Meal in the Daily Mix

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 60

 Example 2.2-2 Diet Problem
vVerification Step: We substitute (x1 = 250, x2 = 750) in the left-hand
side of each constraint:

250 + 750 ≥ 800 (1)

– 0.21(250) + 0.30(750) ≥ 0 (2)
– 0.03(250) + 0.01(750) ≤ 0 (3)
(250), (750) ≥ 0 (5)

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 61

 Example 2.1-1 The Reddy Mikks Co.
qThe feasible solution of the complete the Diet Problem Model is:
The total lb of Corn in the Daily Mix = 250
The total lb of Soybean Meal in the Daily Mix = 750
Minimize z = 0.3(250)+ 0.9(750)
z = 75 + 675
z = 750
The total daily Cost of the Feed Mix = $750
The total lb of Corn in the Daily Mix = $75
The total lb of Soybean Meal in the Daily Mix = $675
Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 62
 Example 2.1-1 The Diet Problem
B. Infeasible Solution: Any values of x1 and x2 that does not satisfy
ANY of the FOUR constraints.
vFor example the following solution is Infeasible because it violates
the 1st and 3rd constraints:
Infeasible Solution
x1 = 200 lb of Corn in the Daily Mix
x2 = 500 lb of Soybean Meal in the Daily Mix

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 63

 Example 2.1-1 The Diet Problem
vVerification Step: We substitute (x1 = 200, x2 = 500) in the left-hand
side of each constraint:

200 + 500 ≥ 800 (1) ×

– 0.21(200) + 0.30(500) ≥ 0 (2)
– 0.03(200) + 0.01(500) ≤ 0 (3) ×
(200), (500) ≥ 0 (5)

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 64

 Example 2.1-1 The Diet Problem
qThe infeasible solution of the complete Diet Problem Model is:
The total lb of Corn in the Daily Mix = 200
The total lb of Soybean Meal in the Daily Mix = 500
Minimize z = 0.3(200)+ 0.9(500)
z = 60 + 450
z = 510
The total daily Cost of the Feed Mix = $60
The total lb of Corn in the Daily Mix = $450
The total lb of Soybean Meal in the Daily Mix = $510
Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 65
 Example 2.1-1 The Diet Problem
C. The Optimum Solution: The goal of the problem is to find the
best feasible solution that minimize the total cost.
vBefore we can do that, we need to know how many feasible
solutions the Diet problem has.
vThe answer, as we will see from the graphical solution in the next
section, is “an infinite number”, which makes it impossible to solve
the problem by enumeration.
vInstead, we need a systematic procedure that will locate the
optimum solution in a finite number of steps.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 66

Graphical Representation of a Constrain
x2

100 –
– This Axis Represents the Soybean Meal Nonnegative Constraint x2 ≥ 0
Number of lb 80 –
–
60 –
–
40 –
– This Axis Represents the Corn Nonnegative Constraint x1 ≥ 0
20 –
–
– | | | | | | | | | | | |
0 20 40 60 80 100 x1
Number of lb

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 67

 Graphical LP Solution of
Example 2.2-2 Diet Problem
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.
However, it appears that there are only two corner points on the
feasible solution space in the Diet Problem as seen in the next plot.
In order to find these two points (the intercept of two lines)
mathematically, we need to do the following:
x1 + x2 ≥ 800 intercepts with – 0.03x1 + 0.01x2≤ 0 in Corner Point (A)
x1 + x2 ≥ 800 intercepts with – 0.21x1 + 0.30x2 ≥ 0 in Corner Point (B)

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 68

 Graphical LP Solution of
Example 2.2-2 Diet Problem
Corner Point A:-
We set the two equations equal to x2 and then equal to each others:
x1 + x2 = 800 AND – 0.03x1 + 0.01x2 = 0
– x1 + 800 = x2 AND 3x1 = x2
– x1 + 800 = 3x1
4x1 = 800
x1 = 200. So: 3(200) = x2
x1 = 200, x2 = 600
Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 69
 Graphical LP Solution of
Example 2.2-2 Diet Problem
Corner Point B:-
We set the two equations equal to x2 and then equal to each others:
x1 + x2 = 800 AND – 0.21x1 + 0.3x2 = 0
– x1 + 800 = x2 AND 0.7x1 = x2
– x1 + 800 = 0.7x1
1.7x1 = 800
x1 = 470.59 So: 0.7(470.60) = x2
x1 = 470.59, x2 = 329.41
Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 70
 Graphical LP Solution of
Example 2.1-1 The Reddy Mikks Co.
Now, the only two corner points are as the following table shows:

Minimization Problem
Corner Point (x1, x2) z
A (200, 600) 600
B (470.59, 329.41) 437.65 (Optimum)

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 71

 Graphical Solution
Example 2.2-2 Diet Problem
A = (x1,x2) = (200, 600)

B = (x1,x2) = (470.59, 329.41)

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 72

 Graphical Solution
Example 2.2-2 Diet Problem 2.2 Graphical LP Solution 25

1500
--

1000

500

Xl = 470.61b
X2 = 329.41b
z= $437.64

-'---- _ _...1..- -'- Xl

1500

FIGURE 2.3
Graphical solution of the diet model

in the remaining constraints? To find the answer, we state the new protein and fiber constraints
Operations
as Research: An Introduction. Hamdy A. Taha, 8th Edition. 73
 Summary of Graphical
Solution Methods
ISOPROFIT METHOD:-
1) Graph all constraints and find the feasible region.
2) Select a specific profit (or cost) line and graph it to find the slope.
3) Move the objective function line in the direction of increasing
profit (or decreasing cost) while maintaining the slope. The last
point it touches in the feasible region is the optimal solution.
4) Find the values of the decision variables at this last point and
compute the profit (or cost).

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 74

 Summary of Graphical
Solution Methods
CORNER POINT METHOD:-
1) Graph all constraints and find the feasible region.
2) Find the corner points of the feasible region.
3) Compute the profit (or cost) at each of the feasible corner points.
4) Select the corner point with the best value of the objective
function found in Step 3. This is the optimal solution.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 75

 Four Special Cases in LP
Four special cases and difficulties arise at times when using the
graphical approach to solving LP problems:
1) No Feasible Solution (Infeasibility).
2) Unboundedness.
3) Redundancy.
4) Alternate Optimal Solutions.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 76

 Infeasibility
1) Exists when there is no solution to the problem that satisfies all
the constraint equations.
2) No feasible solution region exists.
3) This is a common occurrence in the real world.
4) Generally one or more constraints are relaxed until a solution is
found.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 77

 Infeasibility
X2 X1+2X2 <=6 (1)
2X1+ X2 <=8 (2)
X1 >=7 (3)
8–
–
6–
–
Region Satisfying
4– Third Constraint
–
2–
–
0– | | | | | | | | | |
2 4 6 8 X1
Region Satisfying First Two Constraints

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 78

 Unboundedness
1) Sometimes a linear program will not have a finite solution.
2) In a maximization problem, one or more solution variables, and
the profit, can be made infinitely large without violating any
constraints.
3) In a graphical solution, the feasible region will be open ended.
4) This usually means the problem has been formulated improperly.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 79

 Unboundedness
Maximize profit = $3X1 + $5X2
X2 Subject to X1 ≥5
X2 ≤ 10
X1 + 2X2 ≥ 15
X1 ≥ 5
15 –
X1, X2 ≥ 0

X2 ≤ 10
10 –

Feasible Region Unbounded

5–
X1 + 2X2 ≥ 15

0 –| | | | |
5 10 15 X1

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 80

 Redundancy
1) A redundant constraint is one that does not affect the feasible
solution region.
2) One or more constraints may be more binding.
3) This is a very common occurrence in the real world.
4) It causes no particular problems, but eliminating redundant
constraints simplifies the model.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 81

 Redundancy
X2
30 –

25 –
Maximize profit = $1X1 + $2X2 2X1 + X2 ≤ 30

Subject to X1 + X2 ≤ 20 20 –

2X1 + X2 ≤ 30
15 –
X1 ≤ 25 X1 ≤ 25 (Redundant Constraint)

X1, X2 ≥ 0 10 –
X1 + X2 ≤ 20
Feasible
5–
Region

0– | | | | | |
5 10 15 20 25 30 X1
Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 82
 Alternate Optimal Solutions
1) Occasionally two or more optimal solutions may exist.
2) Graphically this occurs when the objective function’s isoprofit or
isocost line runs perfectly parallel to one of the constraints.
3) This actually allows management great flexibility in deciding
which combination to select as the profit is the same at each
alternate solution.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 83

 Alternate Optimal Solutions
X2
Maximize 3X1 + 2X2 8– A(0,6): z = $12
Subj. to: 7–
B(3,1.5): z = $12
6X1 + 4X2 < 24
6 –A
X1 <3 Optimal Solution Consists of All
Combinations of X1 and X2 Along
X 1, X 2 > 0 5–
the AB Segment
4–

3– Isoprofit Line for $8

2–
B Isoprofit Line for $12
1 – Feasible Overlays Line Segment AB
Region
0– | | | | | | | |
1 2 3 4 5 6 7 8 X1

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 84

 Homework
5) For the diet model, suppose that the daily availability of corn is
limited to 450 lb.
Identify the new solution space and determine the new optimum
solution?

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 85

 Selected LP Applications
This section presents realistic LP models in which the definition of
the variables and the construction of the objective function and
constraints are not as straight-forward as in the case of the two-
variable model.
The areas covered by these applications (e.g.) include the following:
1) Urban Planning.
2) Currency Arbitrage.
3) Investment.
4) Production Planning and Inventory Control.
5) Blending and Oil Refining.
6) Manpower Planning.
Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 86
 Computer Solution with Solver
In practice, where typical linear programming models may involve
thousands of variables and constraints, the only feasible way to solve
such models is to use the computer.
This section presents two a type of popular software: Excel Solver.
Solver is particularly appealing to spreadsheet users.

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 87

LP Solution with Excel Solver

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 88

LP Solution with Excel Solver

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 89

 Homework
6) Solve the Diet Problem using Solver and upload the excel
spreadsheet to the blackboard?

Operations Research: An Introduction. Hamdy A. Taha, 8th Edition. 90