CHAPTER THREE

INTRODUCTION TO LINEAR
PROGRAMMING
 CHAPTER THREE
INTRODUCTION TO LINEAR PROGRAMMING
Linear Programming- is an optimization method, which shows
how to allocate scarce resources such as money, materials or time
and how to do such allocation in the best possible way subject to
more than one limiting condition expressed in the form of
inequalities and/or equations.
 It enables users to find optimal solution to certain problems in
which the solution must satisfy a given set of requirements.
 Optimization in linear programming implies either maximization
(such as profit, revenue, sales, and market share) or minimization
(such as cost, time, and distance) a certain objective function.
 It implies that in LP we cannot max/min two quantities in one
model.
 It involves linearly related multi-variate functions, i.e., functions
with more than one independent variable.
 Linear Programming Models (LPM)
 LPM are mathematical representations of LP problems.
 LP Models have certain characteristics in common.
 Knowledge of these characteristics enables us to recognize
problems that are amenable to a solution using LP models and to
correctly formulate a LP model.
 The characteristics can be grouped into two categories:
Components and Assumptions.
 The components relate to the structure of a model, whereas the
assumptions reveal the conditions under which the model is valid.
Components of LP model
1) The Objective Function- is the mathematical or quantitative
expression of the objective of the company/model. The objective
in problem solving is the criterion by which all decisions are
evaluated.
 Cont’d
 In LPMs a single quantifiable objective must be specified by the
decision maker. For example, the objective might relate to profits,
or costs, or market share, but to only one of these.
 Moreover, because we are dealing with optimization, the objective
will be either maximization or minimization, but not both.
2) The Decision Variables - represent unknown quantities to be
resolved for. These decision variables may represent such things
as the number of units of different products to be sold, the amount
of Birr to be invested in various projects, the number of ads to be
placed with different media.
3) The constraints - are restrictions which define or limit the
feasibility of a proposed course of action. They limit the degree to
which the objective can be pursued.
 A typical restriction embodies scarce resources (such as labor
supply, raw materials, production capacity, machine time, storage
 Cont’d

space), legal or contractual requirements (e.g. Product standards,

work standards), or they may reflect other limits based on
forecasts, customer orders, company policies etc.
4) Parameters - are fixed values that specify the impact that one unit
of each decision variable will have on the objective. Example:
Maximize: 4X1 + 7X2 + 5X3 (Profit) objective function
Subject to:
2X1 + 3X2 + 6X3  300
5X1 + X2 + 2X3  200 System constraints
3X1 + 5X2 + 2X3  360
X1 = 30
X2  40 Individual constraints
X1, X2, X3  0 Non-negativity constraints
 Assumption of LP Models
1) Linearity - The linearity requirement is that each decision variable
has a linear impact on the objective function and in each constraint
in which it appears.
 In the above example, producing one more unit of product 1 adds
birr 4 to the total profit. This is true over the entire range of
possible values of X1. The same applies to each of the constraints.
2) Divisibility - The divisibility requirement pertains to potential
values of decision variables.
 It is assumed that non-integer values are acceptable. For example:
3.5 TV Sets/hr would be acceptable  7 TV Sets/2hrs.
3) Certainty - Refers to with respect to model parameters (i.e., the
numerical values) – It is assumed that these values are known and
constant.
 In the above example each unit of product 1 requires 2 labor it is
known and remain constant.
 4) Non-negativity - The non-negativity constraint is that negative
values of variables are unrealistic and, therefore, will not be
considered in any potential solution; only positive values and zero
will be allowed.
Formulating LP Models
 Once a problem has been defined, the attention of the analyst shifts
to formulating a model.
 Just as it is important to carefully define a problem, it is important
to carefully formulate the model that will be used to solve the
problem. If the LP model is ill formulated, ill-structured, it can
easily lead to poor decisions.
Formulating LPM involves the following steps:
1) Define the problem/problem definition
 To determine the # of type 1 and type 2 products to be produced
per month so as to maximize the monthly profit given the
restrictions.
2) Identify the decision variables or represent unknown quantities
 Let X1 and X2 be the monthly quantities of Type 1 and type 2
products
3) Determine the objective function
 Once the variables have been identified, the objective function
can be specified.
 It is necessary to decide if the problem is a maximization or a
minimization problem and the coefficients of each decision
variable.
4) Identifying the constraints
 System constraints more than one variable
 Individual constraints one variable
 Non-negative constraints
Example:
1. A firm that assembles computer and computer equipment is
about to start production of two new microcomputers. Each
type of micro-computer will require assembly time, inspection
time and storage space. The amount of each of these resources
that can be devoted to the production of microcomputers is
limited. The manger of the firm would like to determine the
quantity of each microcomputer to produce in order to
maximize the profit generated by sales of these
microcomputers.
Additional information
In order to develop a suitable model of the problem, the
manager has met with design and manufacturing personnel. As
a result of these meetings, the manger has obtained the
following information:
 Cont’d
Type 1 Type 2
Profit per unit Birr 60 Birr 50
Assembly time per unit 4hrs 10hrs
Inspection time per unit 2hrs 1hr
Storage space per unit 3cubic ft 3cubic ft

 The manager also has acquired information on the availability of

company resources. These weekly amounts are:

Resource Resource available

Assembly time 100hrs
Inspection time 22hrs
Storage space 39 cubic feet
 The manager also meet with the firm’s marketing manager and
learned that demand for the microcomputers was such that
whatever combination of these two types of microcomputer is
produced, all of the output can be sold.
o Required: Formulate the Linear programming model.
Solution:
• Step 1: Problem Definition
– To determine the number of two types of microcomputers to
be produced (and sold) per week so as to maximize the weekly
profit given the restriction.
• Step 2: Variable Representation
- Let X1 and X2 be the weekly quantities of type 1 and type 2
microcomputers, respectively.
• Step 3: Develop the Objective Function
Maximize or Zmax = 60X1 + 50X2
 Cont’d
• Step 4: Constraint Identification
System constraints: 4X1 + 10X2  100hrs Assembly time
2X1 + X2  22hrs Inspection time
3X1 + 3X2  39 cubic feet Storage space
Individual constraint No
Non-negativity constraint X 1, X 2  0
In summary, the mathematical model for the microcomputer
problem is:
Zmax = 60X1 + 50X2
Subject to: 4X1 + 10X2  100
2X1 + X2  22
X1 + 3X2  39
X 1, X 2  0
 2. An electronics firm produces three types of switching devices.
Each type involves a two-step assembly operation. The assembly
times are shown in the following table:
Assembly time per Unit (in minutes)
Station 1 Station 2
Model A 2.5 3.0
Model B 1.8 1.6
Model C 2.0 2.2
• Each workstation has a daily working time of 37.5 hrs. The
manager wants to obtain the greatest possible profit during the next
five working days. Model A yields a profit of Birr 8.25 per unit,
Model B a profit of Birr 7.50 per unit and Model C a profit of Birr
7.80 per unit. Assume that the firm can sell all it produces during
this time, but it must fill outstanding orders for 20 units of each
model type.
 Required: Formulate the linear programming model of this
problem.
Solution:
• Step 1. Problem definition
 To determine the number of three types of switching
devices to be produced and sold for the next 5 working days
so as to maximize the 5 days profit.
• Step 2. Variable representation
 Let X1, X2 and X3 be the number of Model A, B and C
switching devices respectively, to be produced and sold.
• Step 3. Develop objective function
Zmax: 8.25X1 + 7.50X2 + 7.80X3
 Step 4. Constraint identification
2.5X1 + 1.8X2 + 2.0X3  2250 minutes Ass. time station 1 SC
3.0X1 + 1.6X2 + 2.2X3  2250 minutes Ass. time station 2 SC
X1  20 Model A IC
X2  20 Model B IC
X3  20 Model C IC
X1, X2, X3  0 NNC
• In summary: Zmax: 8.25X1 + 7.50X2 + 7.80X3
2.5X1 + 1.8X2 + 2.0X3  2250 minutes
3.0X1 + 1.6X2 + 2.2X3  2250 minutes
X1  20 model A
X2  20 model B
X3  20 model C
X1, X2, X3 0 Non negativity
3. A diet is to include at least 140 mgs of vitamin A and at least
145 Mgs of vitamin B. These requirements are to be obtained
from two types of foods: Type 1 and Type 2. Type 1 food
contains 10Mgs of vitamin A and 20mgs of vitamin B per
pound. Type 2 food contains 30mgs of vitamin A and 15 mgs
of vitamin B per pound. If type 1 and 2 foods cost Birr 5 and
Birr 8 per pound respectively.

Vitamins
Foods A B
Type 1 10 20
Type 2 30 15
Required: Formulate the linear programming model of this
problem.
Solution:
• Step 1. Problem definition
 To determine the pounds of the two types of foods to be
purchased to make the diet at a minimum possible cost within
the requirements.
• Step 2. Variable representation
 Let X1 and X2 be the number of pounds of type 1 and type 2
foods to be purchased, respectively.
• Step 3. Objective function
Cmin: 5X1 + 8X2
• Step 4. Constraint identification
10X1 + 30X2  140
20X1 + 15X2  145 System constraints
X1, X2  0 Non-negativity constraints.
 4. A farm consists of 600 hectares of land of which 500 hectares
will be planted with corn, barley and wheat, according to these
conditions.
1. At least half of the planted hectar should be in corn.
2. No more than 200 hectares should be barley.
3. The ratio of corn to wheat planted should be 2:1
• It costs Birr 20 per hectar to plant corn, Birr 15 per hectar to
plant barley and Birr 12 per hectar to plant wheat.
Required: Formulate this problem as an LP model that will
minimize planting cost while achieving the specified conditions.
Solution:
• Step 1. Problem definition
 To determine the number of hectares of land to be planted with
corn, barley and wheat at a minimum possible cost meeting the
requirements.
 Step 2. Decision variable representation
 Let X1 be the number of hectares of land to be planted with
corn, X2 be the number of hectares of land to be planted with
barley, and X3 be the number of hectares of land to be planted
with wheat.
• Step 3. Objective function
 Cmin = 20X1 + 15X2 + 12X3
• Step 4. Constraints
X1 + X2 + X3 = 500 System constraint
X1  250 Individual constraint
X2  200 Individual constraint
X1 – 2X3 = 0 System constraint
X1, X2, X3  0 Non negativity
 Solution Approaches to Linear Programming Problems
The Graphic Solution Method
• It is a relatively straightforward method for determining
the optimal solution to certain linear programming
problems. It gives as a clear picture.
• This method can be used only to solve problems that
involve two decision variables.
• However, most linear programming applications
involve situations that have more than two decision
variables, so the graphic approach s not used to solve
them.
 We begin by giving some important definitions and concepts that
are used in the methods of solving linear programming problems.
1) Solution: A set of values of decision variables satisfying all the
constraints of a linear programming problem is called a solution to
that problem.
2) Feasible solution: Any solution which also satisfies the non-
negativity restrictions of the problem is called a feasible solution.
3) Optimal feasible solution: Any feasible solution which
maximizes or minimizes the objective function is called an optimal
feasible solution.
4) Feasible region: The common region determined by all the
constraints and non-negativity restriction of a LPP is called a
feasible region.
5) Corner point: A corner point of a feasible region is a point in the
feasible region that is the intersection of two boundary lines.
 Steps to solve LPP:
1. Plot each of the constraints and identify its region – make linear
inequalities into linear equations.
2. Identify the common region, which is an area that contains all of
the points that satisfy the entire set of constraints.
3. Determine the Optimal solution- identify the point which leads to
maximum benefit or minimum cost.

E.g. 1. Solving the micro-computer problem with graphic approach

Zmax = 60X1 + 50X2
4X1 + 10X2  100
2X1 + X2  22
3X1 + 3X2  39
X1, X2  0
2. Solving the diet problem with graphic approach
Cmin: 5X1 + 8X2
10X1 + 30X2  140
20X1 + 15X2  145
X1, X2  0
THANK YOU!!!

END OF THE 3rd CHAPTER!!