Chapter 2

Linear Programming Models

 Introduction
• Linear Programming which is one of the most
popular tools of operations research.

• LP models enable users to find optimal solutions to

problems in which the solution must satisfy a given
set of requirements/ constraints.

• The term linear implies that all the mathematical

relations used in the problem are linear or straight-
line relations
 What is LPP?

• LPP is composed of one variables to the firs

degree, or constants and one variables to the firs
degree, or constant(to the right side) separated by
plus, minus or equality sign.

Class activity
Write at least three examples of non linear prgram
 Cont’d

• The usefulness of this technique is enhanced by

the availability of several user-friendly software
such as STORM, TORA, QSB+, LINDO, etc.
However, there is no general package for building
an LP model.

• Therefore, “Model building” is an art of

practice.
 Components of LP model

 Objectives function
 Is the function which represent the goal of
the economic agent
 In LP model, a single, quantifiable objective
must be specified by the decision maker
 Cont’d

• Every LP problem will be either maximization or a

minimization problem.

• Hence, objective function can be:

-maximization e.g. profit, market share, audience,
interest amount etc
-Minimization e.g. cost, risk, defective production rate
etc

e.g. if a unit price of product “N” is birr 10 and its unit cost is birr
7 while a unit price of product “M” is birr 15 while its cost is
birr 11, then the objective func. Can be:
Max.Z= 3X1+4X2
 Cont’d
 Decision variables(controllable variables)- will be
defined in terms of quantity to be produced

• Decision variables: represent unknown quantities to

be solved for.
• The decision maker can control the value of the
objective, which is achieved through choices in the
levels of decision variables.

• For example, how much of each product should be

produced in order to obtain the greatest profit
• Based on the above example, X1 & X2 are decision variables
 Cont’d
 Problem constraints
o Our objective function is subject to resource constraints.

o The ability of a decision maker to select values of the decision

variables in an LP problem is subject to certain restrictions or
limits coming from a variety of sources.
o The restrictions may reflect:
• availabilities of resources (like RM, labor hrs, machine hrs,
storage area etc)
• legal or contractual requirements (e.g., product standards,
work standards, etc.),
• technological requirements (e.g., necessary compressive
strength or tensile strength) or
• they may reflect other limits based on forecasts, customer
orders, company policies, and so on.
 Cont’d
• Minimum requirement represents by >
• Maximum availability represents by <
• Exact requirement represents by =

e.g. X+2y< 6
3x+2y<12
• x& y are decision variables to the first power
• 2, 6, 3 and 12 are coefficient, parameters or constants
 Cont’d

 Non negativity constraints

• express the fact that production level can
not assume negative value

i.e. all decision variables > 0

e.g. x, y >0
Application areas of Operation research
 Linear Programming (LP) Can Be Used for Many
Managerial Decisions:
• Product mix
• Make-buy
• Media selection
• Marketing research
• Portfolio selection
• Shipping & transportation
• Multiperiod scheduling
 Steps in Developing a LP Model
1) Formulation of the problem
-Convert the verbal expressions(data) obtained from Managers,
engineers marketers records etc in to algebraic expression

2) Solution
-Find the optimum solution using Graphical or simplex methods

3) Interpretation and Sensitivity Analysis

Interprets the solution in manner that give meaning for the
decision makers
 Formulation of LP model
• Identify the decision variables
• Determine the objective function
• Identify the constraints

• Determine appropriate value for parameter and

determine whether an upper limit(<), lower
limit(>) or equality(=) is called for

• Use this information to build the model

• Validate the model
 Examples of LPP formulation
Example 1: Flair Furniture Co.
• Flair Furniture Co. manufactures two types of
chairs-type A and type B made of wood. Type
A requires 3 minutes each for cutting and 7
minutes each for assembling. On the other
hand, type B requires 8 minutes for cutting
and 10 minutes for assembling. There are 4
hrs and 20 minutes available for cutting and 5
hrs available for assembling. The profit per
unit is $50 for type A and $60 for type B
• Required: formulate the LPP
 Solutions

• Summarize the information

Decision variables
Let x be number of type A chair produced and sold
y be number of type B chair produced and sold

Then the constraints are: cutting hrs<260

assembling hrs<300
Cutting hrs required per type A & type B are 8 &3 minutes respectively
assembling hrs required per type A & type B are 7&10 minutes respectively

Profit per type A &type B are $50&$60 respectively

 Summarize in the table form
Type A Type B

• .
Hours
Profit Contribution $50 $60 Available
Cutting hrs/unit in minutes 3 8 260
Assemb.hrs/unit in minutes 7 10 300

Thus, the LPP can be formulated as”

Max Z= 50X+60Y
Subject to(constrained by)
3X+8Y<260
7X+10Y<300
X, Y> 0
 Example 2
• A manufacturer makes two products- product A
and product B. Each unit of product A requires 3
hrs in the molding department, 4 hrs in the paint
shop and 1 hr in finishing. Each unit of B requires
3 hrs in molding department, 2 hrs in the paint
shop and 2 hrs in finishing. Each week there are
210 hrs available in molding, 200 hrs in painting,
and 120 hrs in finishing. Each unit of A
contributes birr 20 to profits while each unit of
product B contribute birr 30
REQUIRED: Develop the LPP
 Example 3: Flair Furniture Co.

Flair Furniture Co. Data

Tables Chairs
(per table) (per chair)
Profit Hours
$7 $5
Contribution Available
Carpentry 3 hrs 4 hrs 2400
Painting 2 hrs 1 hr 1000

Other Limitations:
• Make no more than 450 chairs
• Make at least 100 tables
 Summary of information

Two products: Chairs and Tables

Decision: How many of each to make this

month?

Objective: Maximize profit

Decision Variables:
T = Num. of tables to make
C = Num. of chairs to make

Objective Function: Maximize Profit

Maximize $7 T + $5 C
Constraints:

Two constraints: carpentry & painting time

• Maximum carpeting time available is 2400 hrs

3 T + 4 C < 2400 (hours)

• Maximum painting time available is 1000 hrs

2 T + 1 C < 1000 (hours)

More Constraints:
• Make no more than 450 chairs
C < 450 (num. chairs)

• Make at least 100 tables

T > 100 (num. tables)

Nonnegativity:
Cannot make a negative number of chairs or tables
T>0
C>0
 Model Summary
Max 7T + 5C (profit)
Subject to the constraints:
3T + 4C < 2400 (carpentry hrs)
2T + 1C < 1000 (painting hrs)
C < 450 (max # chairs)
T > 100 (min # tables)
T, C > 0 (nonnegativity)
Example 4. Product Mix Problem:
Fifth Avenue Industries
• Produce 4 types of men's ties
• Use 3 materials (limited resources)

Decision: How many of each type of tie to

make per month?

Objective: Maximize profit

 Resource Data

Yards available
Material Cost per yard per month
Silk $20 1,000
Polyester $6 2,000
Cotton $9 1,250

Labor cost is $0.75 per tie

 Product Data
Type of Tie
Silk Polyester Blend 1 Blend 2
Selling Price
$6.70 $3.55 $4.31 $4.81
(per tie)
Monthly
6,000 10,000 13,000 6,000
Minimum
Monthly
7,000 14,000 16,000 8,500
Maximum
Total material
(yards per tie) 0.125 0.08 0.10 0.10
 Material Requirements
(yards per tie)
Type of Tie
Blend 1 Blend 2
Silk Polyester
Material (50/50) (30/70)

Silk 0.125 0 0 0

Polyester 0 0.08 0.05 0.03

Cotton 0 0 0.05 0.07

Total yards 0.125 0.08 0.10 0.10

 Decision Variables

S = number of silk ties to make per month

P = number of polyester ties to make per
month
B1 = number of poly-cotton blend 1 ties to
make per month
B2 = number of poly-cotton blend 2 ties to
make per month
 Profit Per Tie Calculation
Profit per tie =(Selling price)–[(material cost)+(labor cost)]

Silk Tie
Profit = $6.70 – [(0.125 yds)($20/yd) + $0.75] = $3.45 per tie
Polyester
Profit = $3.55.– [(0.08 yds)($6/yd) + $0.75] = $2.32 per tie
Blend 1
Profit = $4.31– [(0.05yds)($6/yd)+(0.05yds)($9/yd) +$0.75] = $2.81 per tie
Blend 2
Profit = $4.81– [(0.03 yds)($6/yd) +(0.07yds)($9/yd) +$0.75] = $3.25 per tie
 Objective Function (in $ of profit)

MaxZ= 3.45S + 2.32P + 2.81B1 + 3.25B2

Subject to the constraints:

Material Limitations (in yards)

0.125S < 1,000 (silk)
0.08P + 0.05B1 + 0.03B2 < 2,000 (poly)
0.05B1 + 0.07B2 < 1,250 (cotton)
 Min and Max Number of Ties to Make
6,000 < S < 7,000
10,000 < P < 14,000
13,000 < B1 < 16,000
6,000 < B2 < 8,500

Finally non-negativity S, P, B1, B2 > 0

 Example
• A conservative investor has $100,000 to invest. The investor
decided to use three vehicles for generating income-municipal
bond, a certificate of deposit(CD) and a money market account. After
reading financial newsletter, the investor also identified
additional restriction.
• No more than 40% of the investment should be in the bond
• The proportion allocated to the money market account should
be at least double the amount in the CD
• The annual return will be 80 %of bond ,90%of CD &70%of
money market account. Assume the entire amount will be
invested,

• Required: formulate the LP model ignoring any transaction cost

and the potential for different investment life
 Cont’d

 Decision variables
X1=amount invested in bonds
X2=amount invested in CD
X3=amount invested in the money market account

 Objective function
Max. Z=0.8X1+0.9X2+0.7X3
 Cont’d
• Constraints on bond
X1< 0.40(100000) X1<$40,000

Money market account be at least double the

amount in CD leads to:
X3> 2X2 X3-2X2>0 -2X2+X3> 0

Entire amount will be invested

X1+X2+X3<100000
 Model summary

Max. Z=0.8X1+0.9X2+0.7X3
s.t
X1<40,000
-2X2+X3> 0
X1+X2+X3<100000

X1,X2,X3 >0
Example 6. Media Selection Problem:
Win Big Gambling Club
• Promote gambling trips to the Bahamas
• Budget: $8,000 per week for advertising
• Use 4 types of advertising

Decision: How many ads of each type?

Objective: Maximize audience reached

 Data
Advertising Options
Radio Radio
TV Spot Newspaper (prime time) (afternoon)
Audience
Reached 5,000 8,500 2,400 2,800
(per ad)
Cost
$800 $925 $290 $380
(per ad)
Max Ads
12 5 25 20
Per week
 Other Restrictions
• Have at least 5 radio spots per week
• Spend no more than $1800 on radio

Decision Variables
T = number of TV spots per week
N = number of newspaper ads per week
P = number of prime time radio spots per
week
A = number of afternoon radio spots per week
Objective Function (in num. audience reached)
Max 5000T + 8500N + 2400P + 2800A
Subject to the constraints:

Budget is $8000
800T + 925N + 290P + 380A < 8000
At Least 5 Radio Spots per Week
P+A>5
 No More Than $1800 per Week for Radio
290P + 380A < 1800

Max Number of Ads per Week

T < 12 P < 25
N< 5 A < 20

Finally nonnegativity T, N, P, A > 0

 Thus, LP model can be formulated as:

Max. 5000T + 8500N + 2400P + 2800A

s.t
800T + 925N + 290P + 380A < 8000
P+A>5
290P + 380A < 1800
T < 12
N<5
P < 25
A < 20
T, N, P, A > 0
 Example 7. Blending Problem:
Whole Food Nutrition Center
Making a natural cereal that satisfies minimum
daily nutritional requirements

Decision: How much of each of 3 grains to

include in the cereal?

Objective: Minimize cost of a 2 ounce (i.e. 0.125

pounds)serving of cereal
 Grain
A B C
Minimum
$ per pound $0.33 $0.47 $0.38 Daily
Requirement
Protein per
22 28 21 3
pound
Riboflavin per
16 14 25 2
pound
Phosphorus
8 7 9 1
per pound
Magnesium
5 0 6 0.425
per pound
 Decision Variables
A = pounds of grain A to use
B = pounds of grain B to use
C = pounds of grain C to use

Note: grains will be blended to form a

2(0.125 pounds) ounce serving of cereal
Objective Function (in $ of cost)
Min 0.33A + 0.47B + 0.38C

Subject to the constraints:

Total Blend is 2 Ounces, or 0.125 Pounds

A + B + C = 0.125
 Minimum Nutritional Requirements
22A + 28B + 21C > 3 (protein)
16A + 14B + 25C > 2 (riboflavin)
8A + 7B + 9C > 1
(phosphorus)
5A + 6C > 0.425
(magnesium)

Finally nonnegativity: A, B, C > 0

 Thus, LP model can be formulated as:
Min 0.33A + 0.47B + 0.38C

s.t
A + B + C = 0.125
22A + 28B + 21C > 3
16A + 14B + 25C > 2
8A + 7B + 9C > 1
5A + 6C > 0.425

A, B, C > 0
 Finding optimum solution for LPP

A. Graphical method

B. Simplex method
A) Solution using Graphical
• Graphing an LP model helps provide
insight into LP models and their solutions.

• While this can only be done in two

dimensions, the same properties apply to
all LP models and solutions.
 Steps to find solution using Graph
1- Change the inequality constraints in to equality
2-Draw the straight line corresponding to the linear
equation on X-Y axis
3-Determine the feasible region
4-Find the coordinates of the vertices(corner point) of the
feasible region
5-Calculate the value of the objective function at each
corner
6- Based on your objective function, decide on the
solution
 Example 1
Solve the following LPP using graphical method
Max. Z=7X+4Y
s.t
X+2Y< 6
3X+2Y<12
X,Y>0
 Example 2
Solve the following LPP using graphical method
Min: Z=3X+Y
s.t
10X+2Y>84
8X+4Y>120
X,Y>0
 Example 3

Solving the following LPP using graphical method

Max. Z=3X1+X2
s.t
2X1+X2<20
10X1+X2>36
2X1+5X2>36

X1,X2>0
 Application example 1
• A special food for Ethiopian Athletes is to be developed from
two foods: food O and food R.
• The new food is to be designed so that it contains at least
16 mg of vitamin A, at least 20 mg of vitamin B and at least
12 mg of vitamin C.
• Each pound of food O costs $1.50 and contains 1 milligram
of vitamin A, 5 milligram of vitamin B and 1 milligram of
vitamin C.
• On the other hand, each pounds of food R costs $2.50 and
contains 2 milligram of vitamin A, 1 milligram of vitamin B
and 1 milligram of vitamin C.
• How many pounds of each food should be used in the
mixture in order to meet the above requirement at a
minimum cost? What is the minimum cost?
 Example 2
• Recall the Flair Furniture Example and find
the solution using Graphical method
 C
Carpentry
Constraint Line
3T + 4C = 2400 Infeasible
600
> 2400 hrs
3T
+
Intercepts 4C
=
24
00
(T = 0, C = 600) Feasible
< 2400 hrs
(T = 800, C = 0)
0
0 800 T
 C
1000
Painting
Constraint Line

2T
+
2T + 1C = 1000

1C
600

= 100
0
Intercepts
(T = 0, C = 1000)
(T = 500, C = 0) 0
0 500 800 T
 C
1000
Max Chair Line
C = 450

600
Min Table Line
450
T = 100

Feasible
Region
0
0 100 500 800 T
 C

7T
Objective

+ 5C
Function Line

=$
4,0
500
7T + 5C = Profit

40
Optimal Point
(T = 320, C = 360)

7T
400

+5
C
=$
7T
300

2,8
+5

00
C
=$
200

2,1
100 00

0
0 100 200 300 400 500 T
 C

Additional Constraint New optimal point

500 T = 300, C = 375
Need at least 75
more chairs than
tables 400 T = 320
C > T + 75 C = 360
No longer
300 feasible
Or
C – T > 75
200

100

0 100 200 300 400 500 T

 LP Characteristics

• Feasible Region: The set of points that

satisfies all constraints

• Corner Point Property: An optimal solution

must lie at one or more corner points

• Optimal Solution: The corner point with the

best objective function value is optimal
 Special Situation in LP
1. Redundant Constraints - do not affect
the feasible region

Example: x < 10
x < 12
The second constraint is redundant
because it is less restrictive.
 Special Situation in LP
2. Infeasibility – when no feasible solution
exists (there is no feasible region)

Example: x < 10
x > 15
 Special Situation in LP
3. Alternate Optimal Solutions – when
there is more than one optimal solution
C
Max 2T + 2C 10

2T
Subject to:

+
All points on

2C
T + C < 10

=
Red segment

20
6
T < 5 are optimal
C< 6
T, C > 0
0
0 5 10 T
 Special Situation in LP
4. Unbounded Solutions – when nothing
prevents the solution from becoming
infinitely large
ion
C
c t on
Max 2T + 2C ire luti
D so
Subject to: 2 of
2T + 3C > 6
T, C > 0 1

0
0 1 2 3 T
 B) Solution using simplex method

• If we have many constraints or if there are

more than two decision variables, we must
use simplex method to find the optimal
solution
 Steps in the simplex procedure

1. Write the LP model in a standard form:

When all of the constraints are written as equalities,
the linear program is said to be in standard form
To standardize:

-Adding slack(s) variables for unused resources for “<”

-Add artificial variables for “=”
-Subtract surplus(excess) and add artificial variables for “>”
-The coefficient of slack/surplus variables in objective function is zero
-The coefficient of artificial variables in objective function is big no “M”
Example of standardization for maximization

• Standardize the following LPP

Maximize Z: 60x1 + 50x2
Subject to:
4x1 + 10x2 < 100
2x1 + x2 < 22
3x1 + 3x2 < 39
x1, x2 > 0
 Cont’d

• standard form is as follows:

Maximize Z= 60x1 + 50x2 + 0s1 + 0s2 + 0s3
Subject to:
4x1 + 10x2 + s1 = 100
2x1 + x2 + s2 = 22
3x1 + 3x2 + s3 = 39
x1, x2, s1, s2, s3 > 0
 Exercise

Write the standard form for “>” and mixed constratint

• . Example1. Example2.
Standardize the following LPP using Maximize profit: 6x1 + 8x2
simplex method Subject to:
Min Z=3X1+4x2 Constraint 1: x2 < 4
s.t Constraint 2: x1 + x2 = 9
2X1+3X2>90 Constraint 3: 6x1 + 2x2 > 24
4x1+3X2>120 x1, x2 > 0
X1, X2>0
 Cont’d

2. Form the initial tableau

3. Decide the entering column and leaving row
4. Repeat the iteration till all elements in the cj-zj row
become negative or zero(for maximization) and
zero or positive (for minimization)
 Cont’d

• Example 1.
Find the solution for the following LPP using
simplex method
Max. Z=7X1+4X2
s.t
X1+2X2< 6
3X1+2X2<12
X,Y>0
 Example 2
• Find the solution for the following LPP
using simplex method
Maximize profit: x1 + 2x2
Subject to :
x1 + 5x2 <10
2x1 + 6x2 < 16
x1 , x2≥0
 Exercise

Solve the following using simplex method

Max. Z=8x1+5X2
s.t.
X1+X2<13
X1+2X2<18
2X1+X2<20
X1, X2>0
Solving minimization using simplex method

NB: The basic procedure of simplex method for minimization is the same
as maximization with some exception( see the reading materials)

Example1.
Solve the following LPP using simplex method
Min C.=7x1 + 9X2
s.t.
3X1+6X2>36
8X1+4X2>64
X1,X2>0
 Example 2
Solve the following LPP using the simplex method

Min Z=3X1+4x2
s.t
2X1+3X2>90
4x1+3X2>120
X1, X2>0
 Mixed constraints
Example 1: Solve the following problem using
the simplex approach:
Maximize profit: 6x1 + 8x2
Subject to:
Constraint 1: x2 < 4
Constraint 2: x1 + x2 = 9
Constraint 3: 6x1 + 2x2 > 24
• x1, x2 > 0
 Cont’d
The standard form to the above problem is:

Maximize profit: 6x1 + 8x2 + 0s1 + 0s3 – MA2 – MA3

s.t
x2 + s1 = 4
x1 + x2 + A2 = 9
6x1 + 2x2 – s3 + A3 = 24
x1, x2, s1, s3, A1, A3 > 0