CHAPTER THREE

INTRODUCTION TO LINEAR PROGRAMMING

3.1. Concepts of Linear Programming

Linear programming- is an optimization method which shows how to allocate scarce resources 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 optional solution to certain problems in which the solution must satisfy a given set
of requirements or constraints.
 optimization in linear programming implies either maximization of: - Profit, Revenue, Sales, Market
share or minimization of:- Cost, Time, Distance or a certain objective function.
*We can’t max/min two quantities in one model!

 involves linearly related multi-variety functions i.e. functions with more than one independent
variables.
 The goal in linear programming is to find the best solution given the constraints imposed by the
problem, hence the term constrained optimization.
Linear Programming Models (LPM)
LP models are mathematical representation of LP problems. Some models have a specialized format where as
others have a more generalized format. Characteristics of LP model can be grouped in to two categories, such
as Components and Assumptions. The components relate to the structure of a model, where as the assumptions
describe the conditions under which the model is valid.

Components Assumption
1. Objective Function 1. Linearity
2. Decision Variables 2. Divisibility
3. Constraints Model structure 3. Certainty Model Validity
4. Parameters and 4. Additivity
right hand side } 5. Non-negative }
values

1. Components of LP models
 Objective Function:- is the mathematical/ quantitative expression of the objective of the company/
model. The objective in problem solving is the criterion by which all decisions are evaluated. It is the
mathematical or quantitative expression of the objective of the company. In LPM a single quantifiable
objective must be specified by the decision maker.
 Decision variables:- Represent unknown quantity to be solved for (x1, x2 and etc).
 Constraints:-They are restrictions which define of limit the degree to which the objective can be followed.

Page | 1
  Parameters:- They are fixed values that specify the impact that one unit of each decision variable will
have on the objective and on any constraint it pertains to as well as to the numerical values of each
constraint.
Example describing Components
Maximize: 10x1 + 2X2 + 9X3 (profit) …. Objective Function
2x1 + 5x2 + 3x3
6X1 + 2X2 }System Constraints
3X1 + X2 + 5X3
X1=40 and X2 are individual Constraints
X1, X2, X3 Non negativity constraints
X1, X2 and X3 are quantity of product 1, 2, and 3 respectively and decision variables.

System constraints- involve more than one decision variables

Individual constraint- involve only one decision variable.
None-negativity constrains- specify that no variable will be allowed to take on a negative value. The non
negativity constraints typically apply in a LP model, whether they are explicitly stated or not.
2. Assumption of LP models
 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. Taking the above example, producing one more
unit of products add br 4 to the total profit. This is true over the entire range of possible values of x1.
The same applies (true) to each of the constraints.

 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
7TV sets/ 2hr.

 Certainty:- The parameters are known and constant. The certainty requirement involves two aspects
of LP models. The constraint equations do not change.
(1) With respect to model parameters (i.e. the numerical values) –It is assumed that these values are known
and constant. Eg. In the above example each unit of product 1 requires 2 labor hours is known and remain
constant, and also the 300 labor available is deemed to be known and constant.
(2) All the relevant constraints identified and represented in the model are as they are.

 Additivity:-The objective function is the sum of all what produce.

 Non-negativity:- The non-negativity constraint is that negative values of variables are unrealistic and,
therefore, will not be considered in any potential solutions, only positive values and zero will be allowed.

Page | 2
 3.2. Formulating of Linear Programming Models (LPM)

Once a problem has been defined, the attention of the analyst shifts to formulating a model. Just as 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 lend to poor decisions. Formulating linear programming models
involves the following steps:
Step 1. Define the problem: Determining number of all types of product to be produced per given period to
. maximize profit.

Step 2. Identify the decision variable or represent unknown quantities.

Step 3. Determine objective function.

Step 4. Identify the constraints - System constraint: More than one variables

- Individual constraints: One variable - Non- negativity constraints

Step 5. Determine appropriate values for parameters and determine whether upper limit, lower limit or equality.

Step 6. Use this information to build a model. Step 7. Validate the model.

3.3. The Maximization Problem

The Maximization Problem optimization in linear programming implies maximization of Profit, Revenue,
Sales, Market share or a certain objective function of the company.
Example 1. A firm that assembles computers is about to start production of two new micro computers. Each
type of micro computers will require assembly time, inspection time, and storage space. The amount of each of
these resources that can be devoted to the production of micro computers is limited. The manager of the firm
would like to determine the quantity of each micro computer to produce in order to maximize the profit
generated by sales of these micro computers.

Additional information:- In order to develop a suitable model of the problem, the manager has met the design
and manufacturing personnel. As a result of these meetings the manager has obtained the following information.

Type1 Type2
Profit per Unit in $ 60 50
Assembly time per unit in hrs 4 10
Inspection time per unit in hrs 2 1
Storage space per unit 3 3
The manager has also acquired information on the available company resources. These amounts are

Page | 3
 Resource Resource available
Assembly time 100hrs

Inspection time 22hrs

Storage space 39cubic feet
The manager has also met the firm marketing manager and learned that the demand for the micro computers
was such that whatever the combination of these two types of micro computers was produced ,all of the output
can be sold. Solution
Step 1. Problem Definition:- To determine the number of two types of micro computers to be produced and
sold to maximize profit, given restrictions.

Step 2. Variable representation:- Let X1 and X2 be the quantity of type one and type two micro computers
. respectively

Step 3. Develop the objective function:-  Maximize or = 60X1 + 50X2

Step 4. Constraint identification

System Constraints 4X1 + 10X2 Assembly

2X1 + X2 Inspection
3X1 + 3X2 Storage
Individual constraints  No
. Non – Negativity Constraints  X1, X2

 Therefore, Z max = 60X1 + 50X2

Subject To: 4X1 + 10X2

2X1 + X2

3X1 + 3X2

X1, X2

3.4. The Minimization Problem

The Minimization Problem optimization in linear programming implies minimization of Cost, Time, Distance
or a certain objective function of the company.

Example:- Step 1. Problem Definition:-determine the number of two types of tiers that must be produced by
the two machines (M I & M II) in order to minimize costs of operating the machines.

Step 2. Variable representation:- Let X1 is the number of tiers that must be produced by M I and X2 is the
number of tiers that must be produced by M II .
Page | 4
Step 3. Develop the objective function: - cost Minimization  Z min = 50X1 + 80X2
Step 4. Constraint identification  Grade A tiers constraints: 20X1 + 30X2 1,400

 Grade B tiers constraints: 10X1 + 40X2  1,200

Individual constraints  No
Non-negative restrictions X1 , X2  0

 Therefore, Z min = 50X1 + 80X2

Subject to: 20X1 + 30X2  1,400

10X1 + 40X2 1,200

X1, X2  0

3.5. Solution Approaches to linear Programming problems

There are two approaches to solve linear programming problems.
1. Graphical Solution Method
2. The algebraic Solution/ Simplex algorithm

3.5.1. Graphical Solution Method

This method is used for solving problems that involve two decision variables only. Steps

1. Plot each constraints and identify their region

2. Identify common region
3. Determine the optional solution and identify the point which leads to maximum benefit or minimum
cost.

Example 1. solve the micro computer? The mathematical model for the microcomputer problem is:
= 60X1 + 50X2

4X1 + 10X2
2X1 + X2
3X1 + 3X2
X1, X2

 Region EGHBO is the commonest region point

 Region EGHBO is called feasible region point
 Point E Contains (0, 10)
 Point G contains (5,8) the intersection of L1 and L3
 Point H contains (9,4) the intersection of L2 and L3
 Point B Contains (11, 0)

Page | 5
To identity the maximum (minimum) value we use the corner point approach or the extreme point approach.
The corner point/ extreme point approach has one theorem. It states that:

For problems that have optional solutions, a solution will occur at an extreme, or corner point. Thus if a
problem has a single optional solution, it will occur at a corner point. If it has multiple optional solutions, at
least one will occur at a corner point consequently, in searching for an optional solution to a problem, we need
to consider the extreme points because one of those must be optional. Further, determining the value of the
objective function at each corner point, we could identify the optional solution by selecting the corner point
that has the best value (i.e. maximum or minimum, depending on the optimization case) of the objective
function. Extreme points represent interactions of constraints.

1.1 Determine the values of the decision variables at each corner point. Sometimes, this can be done by
impaction (observation) and sometimes by simultaneous equation.
1.2 Substitute the value of the decision variables at each corner point into the objective function to obtain
its value at each corner point.

Page | 6
 1.3 After all corner points have been so evaluated, select the one with the highest or lowest value
depending on the optimization case.

COORDINATES
VALUE OF THE OBJECT
CORNER X1 X2 DETERMINED BY
FUNCTION
POINTS Z=60X1 + 50X2
O 0 0 OBSERVATION 0BIRR
A 0 22 OBSERVATION 1100 BIRR
B 11 0 OBSERVATION 660 BIRR
C 13 0 OBSERVATION 780 BIRR
D 25 0 OBSERVATION 1500 BIRR
E 0 10 OBSERVATION 500 BIRR
F 0 13 OBSERVATION 650 BIRR
G 5 8 SIMULTANEOUS 700 BIRR
H 9 4 Simultaneous 740 BIRR

I 5 12 Simultaneous 900 BIRR

BASIC SOLUTION

X1 = 9 X2 = 4 Z = 740 Br. .
After we have got the optimal solution, we have to substitute the value of the decision variables into the
constraints and check whether all the resources available are used or not. If there is any unused resource we
can use it for any other purpose. The amount of unused resource is known as slack- the amount of a scarce
resource that is unused by a given solution. The slack can range from zero, for a case in which all of a
particular resource is used; to the original amount of the resource that was available (i.e. none of it is used.)

Computing the amount of slack

Constraints Originally Used time Unused time (slack)

Available
X1=9 X2=4 Available to use
Time

Assembly Time 100hr 4(9) + 10(4) = 76 100-76=24hr

Inspection Time 22hr 2(9) + 1(4) = 22 22-22=0hr

Page | 7
 Storage [Link] 3(9) + 3(4) = 39 39-39=0hr

Constraints that have no slack are sometimes referred to as binding constraints since they limit or bind the
solution. In the above cases, inspection time and storage space are binding constraints, while assembly time
has slack. Knowledge of unused capacity can be useful for planning. A manager may be able to use the
remaining assembly time for other products, or, perhaps to schedule equipment maintenance, safety seminars,
training sermons or other activities

Interpretation: The Company is advised to produce 9 units of type 1 micro computer and 4 units of type 2
micro computers per week to maximize its early profit to Br. 740, and in doing so the company would be left
with unused resource of 24 assembly hrs which can be used for other purposes.

Example 2: Solving the diet problem with graphic approach.

C min = 5X1 + 8X2

L1: 10X1 + 30X2  140
L2: 20X1 + 15X2  145
X1, X2  0

Page | 8
Basic solution X1 = 5 pounds X2 = 3 pounds C = 49 br.

Coordinates
Value of object Function
Point X1
X2 Determined by 20X1 +15X2 = 145

O 0 0 Observation 0 birr

A 0 9.67 Observation 77.3 birr

B 5 3 Simult. equation 49 birr

C 14 0 Observation 70 birr

D 7.25 0 Observation 145 birr

E 0 4.67 Observation 70.05 birr

Interpretation:- to make the diet the minimum cost of br 49 we have to purchase 5 pounds of type 1 food and
3 pounds type 2 food.

If there is a difference between the minimum required amount and the optimal solution, we call the difference
surplus; that is: surplus is the amount by which the optimal solution causes a  constraint to exceed the
required minimum amount. It can be determined in the same way that slack can: substitute the optimum values
of the decision variables into the left side of the constraint and solve. The difference between the resulting
value and the original right-hand side amount is the amount of surplus. .
Surplus can potentially occur in a  constraint.

3.5.2. THE SIMPLEX ALGORITHM/ ALGEBRAIC SOLUTION METHOD

It is an alternative technique that begins with a feasible solution that is not optimal, but serves as a starting
point. The graphical method is convenient to solve linear programming problems involving only two
Page | 9
variables. However, for problems involving more than two variables or problems involving large numbers of
constraints, it is better to use a more systematic solution, which is called the simplex method .

Slack variables (for smaller-or-equal-to constraints) Slack = Requirement – Production,

Surplus = Production – Requirement

The simplex procedure for a maximization problem with all constraints consists of the following steps.

1. Write the LPM in standard form (change by adding slack variables s). Example

Microcomputer problem Its standard form

= 60X1 + 50X2 = 60X1 + 50X2 + 0S1 + 0S2 + 0S3
4X1 + 10X2 4X1 + 10X2 + S1 =
2X1 + X2 2X1 + X2
3X1 + 3X2 3X1 + 3X2
X1, X2 (X1, X2, S1, S2, S3 )

2. Develop the initial tableau

a. List the variables across the top of the table and write the objective function coefficient of each
variable just above it.
b. There should be one row in the body of the table for each constraint. List the slack variables in
the basis column, one per row.
c. In the Cj column, enter the objective function coefficient of zero for each slack variable.
d. Compute values for row Zj
e. Compute values for Cj-Zj, Where Cj = Coefficient of variable J in the objective Function.
. Bj= RHSV of constraint i. Aij = Coefficient of variable j in
constraint i.

Initial feasible solution:- S1 = 100 Obtained by S2 = 22 equating tow

S3 =39 Variables to X1 = 0 Zero X2 = 0 Decision Z = 0 Variable

Solution Cj 60 50 0 0 0

Basis X1 X2 S1 S2 S3 RHSV

S1 0 4 10 1 0 0 100 *100/4=25
Leaving variable
S2 0 2 1 0 1 0 22 *22/2=11

S3 0 3 3 0 0 1 39 *39/3=13
39/3 = 13

Zj 0 0 0 0 0 0

Page | 10
 Cj - Zj 60 50 0 0 0

Entering variable

4 is pivot column 2 is pivot element

x1= 0 (zero) X2= 0 Decision Z= 0 Variable

3. Develop subsequent tables

3.1 Identify the entry variable –variable that has a largest positive value in the Cj – Zj row.

3.2 Identify the leaving variable –using the constraint coefficient or substitution rates in the entering

variable column divide each one into the corresponding quantity value. However do not divide by a zero or
negative value. The smalls non negative ratio that results indicate which variable will leave the solution

4. Find unique vectors for the new basic variable using row operations on the pivot element.
-1/2 R21 –4R2new + R1old, -3R2new + R3old

Solution Cj 60 50 0 0 0

Basics X1 X2 S1 S2 S3 RHSV Cj = bi/xj (aij)

S1 0 0 8 1 -2 0 56 * 56/8 = 7
X1 60 1 ½ 0 ½ 0 11 * 11/1/2 = 22
S3 0 0 3/2 0 -3/2 1 6 * 6/3/2 = 4 Leaving

Zj 60 30 0 30 0 660
Cj – Zj 0 20 0 -30 0
Incoming Variable

Cj = bi/xj (aij)

56/8 = 7

11/1/2 = 22

6/3/2 = 4 leaving

Page | 11
Solution Cj 60 50 0 0 0 RHSV

Basis X1 X2 S1 S2 S3

S1 0 0 0 1 6 -16/3 24

X1 60 1 0 0 1 -1/3 9

X2 50 0 1 0 -1 2/3 4

Zj 60 50 0 10 40/3 740
Opportunity cost
Cj – Zj 0 0 0 -10 -40/3

5. Compute Cj – Zj row
6. If all Cj – Zj Values are zeros and negatives, you have reached optimality
7. If this is not the case (step 6), repeat 2 to 5 until you get optional solution.
“A simplex solution in a maximization problem in optional if the Cj – Zj row consists entirely of zeros and
negative numbers (i.e. there are no positive values in the bottom row.)”

Note: The variables in solution all have unit vectors in their respective columns for the constraint
equations. Further, note that a zero appears in row C – Z in every column whose variable is in solution, in
row C – Z in every column whose variable is in solution, indicating that its maximum contribution to the
objective function has been realized.

Page | 12