Chapter 2

Linear Programming Problem

Habtamu H. (Dr.)
 Learning Objectives
When you complete this module you should be able
to:
• Formulate linear programming models, both objective
function and constraints

• Solve a LP problem with graphical technique

• Solve a LP problem with the simplex method

• Solve a LP problem using Excel Solver and GAMS

softwares

• Interpret sensitivity analysis and shadow prices

 Optimization Models – In general

• Optimization models are mathematical programming techniques.

• They are characterized by a mathematical statement of the

objective function, and a formal search procedure to determine
the values of decision variables, for optimizing the objective
function.

• In development projects, in general, decision has to be taken by

the planners or designers to optimize the constraints associated
with the project.

• Goals of such decisions is Optimization:

➢ to minimize the effort required/cost incur, or
➢ to maximize the desired benefit/profit

Optimization: Maximization or Minimization!

3
 Optimization Models – In general

• Components of any optimization problem:

➢ An objective function is a mathematical function which mainly

depends upon decision variables that needs to be optimized.

➢ Unknown or Decision variables which control the value of the

objective function.

➢ A set of Constraints are the limitations for optimization.

For example: limited land resources.

Optimization Problem: To find values of the decision variables that

minimize or maximize the objective function while satisfying the
constraints.

4
 Optimization Models – In general

• A general optimization problem may be expressed as:

Max. or Min. f(X) subject to

gi (X)  = ≥ bi, i=1,2.3,…, m
and, X ≥ 0
Where,
f(X) is an objective function to be optimized.
gj(X) is set of constraints
bj = constants (limits to the resources)
X is a vector of decision variables, X = {x1, x2, …, xn} which is
non-negative.

➢ Therefore, in this representation, there are n decision variables

and m constraints.

5
 Optimization Models – In general

• There are several types of optimization models,

➢ Linear Programming problem

✓ both the objective function and the constraints are linear
✓ Has wider application in engineering

➢ Non-linear programming problem

✓ the objective function and/or any of the constraints
involve non-linear terms.
✓ Has limited application in engineering

➢ Dynamic programming problem

✓ It is a multi-stage decision making model
✓ It could offer a solution procedure for linear or nonlinear
problems

6
 Linear Programming Problem - Definition

• Linear Programming Problem (LPP) is a special type of

mathematical model where all relationships between parts of the
system being modeled can be represented linearly (a straight
line).

• When to use LPP: if a problem has too many dimensions and

alternative solutions and to find the one that best meets the
objective of the business problem
Examples of application areas:
• A product mix problem
• A blending problem
• A product scheduling problem
• A transportation problem
• A flow capacity problem

7
 Examples of LP - Problem (1)

1. A Product Mix Problem

• A manufacturer has fixed amounts of different resources such as

raw material, labor, and equipment.

• These resources can be combined to produce any one of several

different products.

• The quantity of the ith resource required to produce one unit of the
jth product is known.

• The decision maker wishes to produce the combination of products

that will maximize total income.

Example: production of tables of different quality

 Examples of LP - Problem (2)

2. A Blending Problem

• Blending problems refer to situations in which a number of

components (or commodities) are mixed together to yield one or
more products.

• Typically, different commodities are to be purchased. Each

commodity has known characteristics and costs.

• The problem is to determine how much of each commodity should

be purchased and blended with the rest so that the characteristics
of the mixture lie within specified bounds and the total cost is
minimized.

Example: Feed mix problem for Animals

 Examples of LP - Problem (3)

3. A Production Scheduling Problem

• A manufacturer knows that he must supply a given number of

items of a certain product each month for the next n months.
• They can be produced either in regular time, subject to a
maximum each month, or in overtime. The cost of producing an
item during overtime is greater than during regular time. A
storage cost is associated with each item not sold at the end of
the month.
• The problem is to determine the production schedule that
minimizes the sum of production and storage costs.
Example: Soft drink company – to produce and supply
different product types as per the demand
 Examples of LP - Problem (4)

4. A Transportation Problem

• A product is to be shipped in the amounts a1, a2, ..., am from m

shipping origins and received in amounts b1, b2, ..., bn at each of
n shipping destinations.
• The cost of shipping a unit from the ith origin to the jth
destination is known for all combinations of origins and
destinations.

• The problem is to determine the amount to be shipped from each

origin to each destination such that the total cost of
transportation is a minimum.
Example: Cement factories to distribute products to warehouses at
different locations
 Examples of LP - Problem (5)

5. A Flow Capacity Problem

• One or more commodities (e.g., traffic, water, information, cash,

etc.) are flowing from one point to another through a network
whose branches have various constraints and flow capacities.
• The direction of flow in each branch and the capacity of each
branch are known.

• The problem is to determine the maximum flow, or capacity of

the network.
Example: Water supply distribution system
 Linear Programming Problem - Requirements

• Requirements of linear programming problem: This technique

to be employed, the basic conditions to be fulfilled are:

– There must be a well defined objective function

– At least some of the resources must be in limited supply,
which give rise to constraints
– Both the objective function and constraints must be linear
equations or inequalities.
– All the decision variables must be non-negative
– Deterministic – coefficients in the objective function and
constraints are known and do not change during the period
under study.

13
 Linear Programming Problem - Expression
• L.P.P can be generally described mathematically as:

– Determine x1 , x2 ,..., x,n which optimize z  c1 x1  c2 x2  ...cn xn

subject to the conditions
a11x1  a12 x2  a13 x3  ...  a1n xn ≤, ≥b1
a21x1  a22 x2  a23 x3  ...  a2n xn ≤, ≥b2
...
am1 x1  am2 x2  am3 x3  ...  amn xn ≤, ≥bm
And non-negativity restrictions, x j  0, j  1,2,..., n

Where, Cj’s, bj’s and aij’s are constants and xj’s are variables.

Finding a solution to the problem, we mean to find the non-negative

values of x1, x2,….,xn which optimize Z and satisfy all the constraints.
14
 Linear Programming Problem - Expression
n
In short: Optimize max .or min .  z   c j x j
j1

subject to
n

 a x , , b ,i  1, 2,..., m

j1
ij j i

x j  0, j  1, 2,..., n
Example:

15
 Linear Programming Problem - Formulation

Important Requirements for LPP formulation

• Understand the system and environment to which the problem

belongs
• Understand the problem and the objective to be achieved
• State the model - clear idea of problem and what can and can not
be included in the model
• Collect Data - get data/parameters/constraints and boundaries of
system and interrelationships
• Determine decisions - define decision variables - what do we need
the model to tell us?
• Formulate the model

16
 Linear Programming Problem - Formulation

The formulation of L.P.P involves the following steps.

1. Find the key decision to be made from the study of the
solution.
Example: Maximization

2. Identify the variables and assume symbols x1, x2, …

Example: x1 = area of the segment for Building A
x2 = area of the segment for Building B

3. Express the constraints mathematically in terms of decision

variables.
Example: x1 + x2 = 10000m2

4. Mention the objective quantitatively and express it as a linear

function of variables.
Example: Maximize f(x) = 2x1 + 3x2

17
 Linear Programming Problem - Formulation

Example 1:
A pineapple firm produces two products – canned pineapple and canned
juice. The specific amounts of material, labour and equipment
required to Produce each product and the availability of each of these
resources are shown below.

Canned Canned available

juice Pinapple resources

Labour (Man hours) 3 2 12

Equipment (Machine 1 2.3 6.9
hours)
Material (unit) 1 1.4 4.9

Assuming one unit of canned juice and canned pineapple has profit
Margins 2birr and 1 birr respectively. Formulate this as a LPP.

18
 Linear Programming Problem - Formulation

Solution:
Let x1 be the number of units of canned juice and x2 be the number of units
of Canned pineapple to be produced.

Constraints:
Labour : 3x1+ x2  12
Equipment: x1+ 2x2  6.9
Material : x1+ 1.4x2  4.9

Objective function: z = 2 x1+x2

Therefore, the LPP

Max. Z = 2x1+x2
subject to
3x1+ x2  12
x1+ 2x2  6.9
x1+ 1.4x2  4.9
and x1, x2  0
19
 Linear Programming Problem - Formulation

Example 2:
A firm engaged in producing two models A and B performs three operations
painting, assembly and testing. The relevant data are as follows:

Model Unit sale Hours required for each unit for

price (birr)
Assembly Painting Testing
A 500 1.0 0.2 0.0
B 800 1.5 0.2 0.1

Total number of hours available are: Assembly 600; painting 100, and testing
30. Formulate this as a LPP to maximize the profit.

20
 Linear Programming Problem - Formulation
Solution:
Decision Variables:
Let x1 be the number of Model A produced and x2 be the number of Model
B produced.

Constraints:
Working hours for assembly : x1+ 1.5x2  600
Working hours for Painting: 0.2x1+ 0.2x2  100
Working hours for testing : 0.1x2  30

Objective function:
z = 500x1+800x2
Therefore, the LPP
Max. Z = 500x1+800x2
subject to
x1+ 1.5x2  600
0.2x1+ 0.2x2  100
0.1x2  30
and x1, x2  0 21
 Linear Programming Problem - Formulation
Example 3:
A Moha soft drink company has two bottling plants in Addis Ababa, one located
at Semit(S) and the other at Gotera (G). Each plant produces three different
soft drinks 7-up, Pepsi and Mirinda. The capacities of the two plants in number
of bottles per day are as follows

Products Plants

S G

7-up 3000 1000

Pepsi 1000 1000
Mirinda 2000 6000

A market survey indicates that during the month of May, there will be a
demand for 24000 bottles of 7-up, 16000 bottles of Pepsi and 48000 bottles of
Mirinda. The operating costs per day of running S and G respectively are 60000
birr aand 40000 birr, how many days should the company run each plant in
May so that the production cost is minimized?
22
 Linear Programming Problem - Formulation

Solution:
The LPP
Min. Z = 60000x1+40000x2
subject to
3x1+ x2  24
x1+ x2  16
x1+ 3x2  24
and x1, x2  0

23
 Linear Programming Problem - Formulation

Example 4:
The total cost (fixed + variable cost) of constructing a ground water
Reservoir is given as a function of its capacity, A is as follows.

– Fixed cost = 20birr

– Variable cost :
• 2 birr per m2 of land for 0<A  10m2
• 4 birr per m2 of land for 10<A14 m2
• 3 birr per m2 of land for 14<A19m2

Formulate a linear programming problem to minimize the total cost of

construction.

24
 Linear Programming Problem - Formulation

Solution:

No. of decision variables No. of constraints

Suppose z represent the total cost and x1, x2 and x3 represent the sizes of land
area in the three segments.
– Fixed cost = 20,
– According to the problem, x1 10, x2 14 and x3 19
– Given variable cost 2 per unit land area for 0 A 10, for x1 unit, the
variable cost becomes 2x1. Similarly, for x2, 4x2 and for x3, it is 3x3
– Thus, total variable cost = 2 x1 +4x2 +3x3
– The total cost function,
Min. z = 20+ 2 x1+4x2+3x3
subject to
x1 10
x2 14
x3 19
and x1, x2, x30
25
 Linear Programming Problem - Formulation

Example 5:

• A real state company constructs two models of a residential

houses (Model A and Model B). Each model A house requires twice
as much labour time as the second model B. If all houses are
model B only, the company can construct a total of 500 houses a
year. The market limits yearly sales of model A houses and Model
B houses to 150 and 250, respectively. The profits on Model A and
B houses are 80,000birr and 50,000birr, respectively. Formulate
the problem as a LPP.

No. of decision variables No. of constraints

26
 Linear Programming Problem - Formulation
Solution:
• Let x1 be number of Model A and x2 be number of model B houses
constructed by the company.
• The problem is a maximization problem. Therefore, the objective function
is:
Z = 80,000x1+50,000x2

• However, there are three constraints. The limitations are capacity of

construction for model B; and market limitations.
– 2x1+x2  500
– x1  150
– x2  250
• Thus the complete formulation of the problem is:
Maximize Z = 80,000x1+50,000x2
Subject to
2x1+x2 500
x1 150
x2 250
and x1, x2 0
27
 Linear Programming Problem - Formulation
Example 6:
A cargo plane has three compartments for storing cargo: front, centre and rear. These
compartments have the following limits on both weight and space:

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

Any proportion of these cargos can be accepted. The objective is to determine how
much (if any) of each cargo C1, C2, C3 and C4 should be accepted and how to
distribute each among the compartments so that the total profit for the flight is
maximized.

Formulate the above problem as a linear program

28
 Linear Programming Problem - Formulation

No. of decision variables No. of constraints

12 10
Solution:
Variables:
• Let xij be tonnes of cargo i (i=1,2,3,4 for C1, C2, C3 and C4 respectively)
that is put into compartment j (j=1 for Front, j=2 for Centre and j=3 for
Rear) where xij >=0, i=1,2,3,4; j=1,2,3

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

Constraints:
• cannot pack more of each of the four cargos than we have available
x11 + x12 + x13 ≤ 18
x21 + x22 + x23 ≤ 15
x31 + x32 + x33 ≤ 23
x41 + x42 + x43 ≤ 12
29
 Linear Programming Problem - Formulation

Solution:
Constraints:
• the weight capacity of each compartment must be respected
x11 + x21 + x31 + x41 ≤ 10
x12 + x22 + x32 + x42 ≤ 16
x13 + x23 + x33 + x43 ≤ 8

• the volume (space) capacity of each compartment must be respected

480x11 + 650x21 + 580x31 + 390x41 ≤ 6800
480x12 + 650x22 + 580x32 + 390x42 ≤ 8700
480x13 + 650x23 + 580x33 + 390x43 ≤ 5300

Objective:
• The objective is to maximize total profit, i.e.
Max. Z= 310[x11+ x12+x13] + 380[x21+ x22+x23] + 350[x31+ x32+x33] + 285[x41+ x42+x43]

30
 Linear Programming Problem - Formulation

Solution:
Therefore,
Max. Z= 310[x11+ x12+x13] + 380[x21+ x22+x23] + 350[x31+ x32+x33] + 285[x41+ x42+x43]
Subject to
x11 + x21 + x31 + x41 ≤ 10
x12 + x22 + x32 + x42 ≤ 16
x13 + x23 + x33 + x43 ≤ 8
x11 + x12 + x13 ≤ 18
x21 + x22 + x23 ≤ 15
x31 + x32 + x33 ≤ 23
x41 + x42 + x43 ≤ 12
480x11 + 650x21 + 580x31 + 390x41 ≤ 6800
480x12 + 650x22 + 580x32 + 390x42 ≤ 8700
480x13 + 650x23 + 580x33 + 390x43 ≤ 5300
and
x11, x21, x31 , x41 , x12 , x22 , x32 , x42 , x13 , x23 , x33 , x43 ≥ 0

31
 Linear Programming Problem - Formulation

Exercise 1:

• A manufacturer of furniture makes two products, chairs and

tables. Processing of these products is done on two machines A
and B. A chair requires 2 hours on machine A and 6 hours on
machine B. A table requires 5 hours on machine A and no time on
machine B. There are 16 hours of time per day available on
machine A and 30 hours on machine B. Profit gained by the
manufacturer from a chair and a table is birr 20 and 100
respectively. Formulate the LPP.

32
 Linear Programming Problem - Formulation

Exercise 2:
Medroc Cement company plans on building a maximum of 11 new
stores in Addis Ababa and Nazareth. The company will build these
stores in one of three sizes - a small store, medium store, and
large sized store. The small sized store requires birr 4.125 million
to build and 30 employees to operate. The medium sized store
requires birr 8.25 million to build and 15 employees to operate.
The large sized store requires birr 12.375 million to build and 45
employees to operate. The corporation can dedicate birr 82.5
million in construction capital, and 300 employees to staff the
stores. On the average, the small store nets birr1.2 million
annually, the medium store nets birr 2 million annually, and the
large store nets birr 2.6 million annually. How many of each
should the company build to maximize revenue? Formulate the
LPP.

33
 Graphical Solution of L.P.P

Graphical method of solving the LPP involves the following steps.

i. Formulate the problem mathematically.
ii. Convert each inequality in the constraint equation be written in the
form of equality. Thus we get equation of straight line. Draw all the
straight lines thus obtained from each constraints equations on the
graph with X1 as x-axis and X2 as Y-axis.
iii. Identify the feasible region. i.e. the area which satisfies all the
constraint simultaneously (convex region). For greater than and
greater than or equal to constraint, the feasible region will be the
area which lies above the constraint line and below otherwise.
iv) corner point method is used to get the solution. Identify each of the
corner, or extreme points of the feasible region either by visual
inspection or the method of simultaneous equations.
v) compute the profit/cost at each corner point by substituting that
points coordinates into the objective function.
vi) Identify the optimal solution at corner point that give highest profit
in a maximization problem or lowest cost in a minimization problem.

34
 Graphical Solution of L.P.P

A region or set of points is said to be convex if the line joining any two
points lies completely within the region.

35