1

Chapter Two
Linear Programing
 Introduction to Linear Programming 2

 A Linear Programming model seeks to maximize or minimize a linear

function, subject to a set of linear constraints.
 The linear model consists of the following
components:

• A set of decision variables.

• An objective function.

• A set of constraints.
 Cot’d 3
 The term linear implies that all the mathematical relations used in the
problem are linear or straight-line relations, while
 the term programming refers to the method of determining a particular
program or plan of action.
 the term linear programming refers to a family of mathematical
techniques for determining the optimum allocation of resources and
obtaining a particular objective when there are alternative uses of the
limited or constrained resources.
 Linear programming models are mathematical representations of LP
problems.
 Introduction to Linear Programming 4
 The Importance of Linear Programming
 Many real world problems lend themselves to linear
programming modeling.
 Many real world problems can be approximated by linear models.
 There are well-known successful applications in:
Manufacturing
Marketing
Finance (investment)
Advertising
Agriculture
 Characteristics of LP 5
 These characteristics can be grouped as components and assumptions. The
components relate to the structure of a model, where as the assumptions reveal
the conditions under which the model is valid.
COMPONENTS OF LP MODELS
 There are four major components of LP models including: Objective function,
decision variables, constraints and parameters.
 Objective and Objective Function
 The objective in problem solving is the criterion by which all decisions are
evaluated.
 It provides the focus for problem solving.
Cont’d……Component 6

 Is the goal or objective of a management, stated as an intent to maximize or

to minimize some important quantity such as profits or costs.
 Decision variables
 They represent unknown quantities to be solved for.
 Constraints
 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.
 Only solutions that satisfy all constraints in a model are acceptable and are referred
to as feasible solutions. 7
 Generally speaking, a constraint has four elements:
 A right hand side (RHS) quantity that specifies the limit for that constraint.
It must be a constant, not a variable.
 An algebraic sign that indicates whether the limit is an upper bound that
cannot be exceeded, a lower bound that is the lowest acceptable amount, or
an equality that must be met exactly.
 The decision variables to which the constraint applies.
 The impact that one unit of each decision variable will have on the right-
hand side quantity of the constraint.
 Constraints can be arranged into three groups: 8

 System constraints – involve more than one decision variable,

 Individual constraints – involve only one variable, and

 Non-negativity constraints – specify that no variable will be allowed to

take on a negative value.

 Parameters
 The objective function and the constraints consist of symbols that represent the decision
variables (e.g., X1, X2, etc.) and numerical values called parameters.

 The parameters are fixed values that specify the impact that one unit of each decision variable
will have on the objective and on any constraint
 Steps in Formulating LP Models
9
 Formulating linear programming models involves the
following steps:
1. Define the decision variables.
2. Determine the objective function.
3. Identify the constraints.
4. Determine appropriate values for parameters and
determine whether an upper limit (<=), lower limit (>=), or
equality (=) is called for.
5. Use this information to build a model.
6. Validate the model.
 Expressing optimization problems mathematically
 Decision variables
X1 , X2 , X3 , … , Xn
e.g. the quantities of different products
Index n = the number of product types

 Constraints
 a less than or equal to constraint : f(X1 , X2 , X3 , … , Xn) < b
 a greater than or equal to constraint : f(X1 , X2 , X3 , … , Xn) > b
 an equal to constraint : f(X1 , X2 , X3 , … , Xn) = b

 Objective
 MAX(or MIN) Z : f(X1 , X2 , X3, …, Xn) 10
Example: The Micro Computer Problem
11

 A firms that Assembles computer and computer equipment is about to

start production of two new microcomputers. Each type of
microcomputer will require assembly time, inspection time and
storage space. The amounts of each of these resources that can be
devoted to the production of the microcomputer is limited. The
manager of the firm would like to determine the quantity of each
microcomputer to produce in order to make maximize the profit
generated by sales of these microcomputers.
Additional information 12
1. A Discussion with experts, in order to develop the model a
manager obtained the following information:
Type 1 Type 2
Profit per unit $60 $50
Assembly time per unit 4 hours 10 hours

Inspection time per unit 2 hours 1 hours

Storage space per unit 3 cubic feet 3 cubic feet

2. Manager also obtained the following information on availability of resource:

Resource Amount available
Assembly time 100 hours
Inspection time 22 hours
Storage space 39 cubic feet

3. Note that, no demand limit. That mean what ever the combination of Microcomputer produced will be
sold.
Formulate the model 13
1. Identify the Decision Variable;
 the decision variable will is determining the quantity of each microcomputer to produce.
 Therefore:

X1= Quantity of type 1 to be produced

X2 = Quantity of type 2 to be produced

2. Formulate objective function:

 Profit on each type 1 is $60 and for each type2 is $50
 So, the appropriate objective function is:
Maximize z = 60x1 + 50x2
 Formulate the model (Cont.) 14
3. Formulate the constraints:
 As for resources we have three resources with limited availability, i.e.
Limited means these constraints will be

a. Tpe1 requires 4 hours of assembly time and type2 requires 10 hours assembly time
so,
b. Tpe1 requires 2 hours of inspection time and type2 requires 1 hours inspection time
so,
c. Both Tpe1 and Type 2 requires 3 cubic feet each so,
 Formulate the model (Cont.) 15

4. Formulate Non-negativity
Both type of quantity may not have opportunity to be negative, i.e. if produced
there is value above zero otherwise equal to Zero if not produced.
Therefore,

Model Summary : 
Subject to:
Assembly

Inspection
Storage
Methods of Solving LP model 16

Two Methods:
Graphical Methods
Simplex Methods
 Graphical Method to Solve LP model 17

 Thismethod can be used only to solve problems that involve two

decision variables.
 The graphical approach:
1. Plot
each of the constraints. Convert each inequality equation into
equality
2. Determine the region or area that contains all of the points that
satisfy the entire set of constraints.
3. Determine the optimal solution.

Using previous example solve graphically

Figure 2-1 Feasible Region Based on a Plot of the First Constraint (assembly time) and the
Non-negativity Constraint
18
 Figure 2–2 A Completed Graph of the Server Problem Showing the
Assembly and Inspection Constraints and the Feasible Solution Space 19
Figure 2–3 Completed Graph of the Server Problem Showing All of the
Constraints and the Feasible Solution Space
20
 Finding the Optimal Solution
21

 The extreme point approach

Involves finding the coordinates of each corner point
that borders the feasible solution space and then
determining which corner point provides the best value
of the objective function.
– The extreme point theorem
If a problem has an optimal solution at least one
optimal solution will occur at a corner point of the
feasible solution space.
 The Extreme Point Approach
22
1. Graph the problem and identify the feasible solution space.
2. Determine the values of the decision variables at each corner
point of the feasible solution space.
3. Substitute the values of the decision variables at each corner
point into the objective function to obtain its value at each
corner point.
4. After all corner points have been evaluated in a similar
fashion, select the one with the highest value of the objective
function (for a maximization problem) or lowest value (for a
minimization problem) as the optimal solution.
Figure 2–5 Graph of Server Problem with Extreme Points of the
Feasible Solution Space Indicated 23
Table 2–3 Extreme Point Solutions for the Server Problem
24
Table 3–5 Computing the Amount of Slack for the Optimal Solution to
the Server Problem 25
Minimization Problem 26
 Minimize Z with inequalities of constraints in > form
 Example:
 Suppose that a machine shop has two different types of machines;
machine 1 and machine 2, which can be used to make a single
product .These machines vary in the amount of product produced per hr.,
in the amount of labor used and in the cost of operation.
 Assume that at least a certain amount of product must be produced and
that we would like to utilize at least the regular labor force. How much
should we utilize each machine in order to utilize total costs and still
meets the requirement?
27
28
Cont’d 29
Figure 2–8 A Comparison of Maximization and Minimization
Problems 30
 Exercise 31

1. Formulate the LP
ABC Furniture manufacturer produces two products: Beds and Chairs. Each unit of
Bed requires 3 hrs in molding unit, 4hrs in painting unit, and 1 hr in finishing. On the
other hand, each unit of Chair requires 3 hrs in molding unit, 2 hrs in the paint shop
and 2 hours in finishing. Each week, there are 210 hrs available in molding, 200hrs in
painting, and 120 hrs in finishing unit. The demand for Beds cannot exceed 40 units
per week. Each unit of Bed contributes Birr 20 to profit, while each unit of chair
contributes Birr 30.

2. Maximize Z 3x + 4y
3. Minimize Z: 10x + 4y
S.T.
S.T.
5x + 4y ≤ 200 3x + 6y ≥ 250
3x + 5y ≤ 150 15x + y ≥ 150
5x + 4y ≤ 100 2x + 9y ≥ 200
8x + 4y ≤ 80 X,y ≥ 0
 Some Special Issues
32
 No Feasible/Infeasible Solutions
 Occurs in problems where to satisfy one of the constraints, another
constraint must be violated.

In the graph, there is no common

point in the shaded area.
All constraints cannot be satisfied
simultaneously and there is no
feasible solution to the problem.
Unbounded Problems
33
 Existswhen the value of the objective function can be
increased without limit.
Note
Here that the two corners of the region are A(0,3) and .B(2,1).
The value of Max Z(A)=6 and Max Z(B)=8. But there exist
number of points in the shaded region for which the value of
the objective function is more than 8.
For example, the point (10, 12) lies in the region and the
function value at this point is 70 which is more than 8.

Remark:
An unbounded solution does not mean that there
is no solution to the given LPP, but implies that
there exits an infinite number of solutions.
Redundant Constraints
 A constraint that does not form a unique boundary of the feasible solution 34
space; its removal would not alter the feasible solution space.
 Ifa constraint when plotted on a graph doesn’t form part of the boundary
making the feasible region of the problem that constraint is said to be
redundant.

Note:
The packaging hour’s constraint does not form
part of the boundary making the feasible region.
Thus, this constraint is of no consequence and is
therefore, redundant.
The inclusion or exclusion of a redundant
constraint does not affect the optimal solution of
the problem.
Multiple Optimal Solutions 35
Problems in which different combinations of values of the
decision variables yield the same optimal value.

 Both C and D are optimal solutions. Any point

on the line segment CD will also lead to the
same optimal solution.

 Multiple optimal solutions provide more

choices for management to reach their
objectives.
 The Simplex approach to solving LP 36

problems
 The graphical approach is useful in solving linear programming
models having only two variables.
 When the model has more than two variables, the appropriate
approach is the Simplex procedure.
 Itbegins with a feasible solution which is not optimal, and the
solution is improved through continuous algebraic
manipulations (iterations) until the optimal solution is
determined.
 Cont’d (Simplex) 37
 The graphical method to solving LPPs provides fundamental concepts for
fully understanding the LP process. However, the graphical method can
handle problems involving only two decision variables (say X1 and X2).
 Simplex Method which is an efficient approach to solve applied problems
containing numerous constraints and involving many variables that
cannot be solved by the graphical method.
 The simplex method is an ITERATIVE or “step by step” method or
repetitive algebraic approach that moves automatically from one basic
feasible solution to another basic feasible solution improving the situation
each time until the optimal solution is reached at.
Steps in solving LP using simplex approach 38

() constraints
Step 1: To solve LP model convert it in to Standard Form:
 To Write in to standard form follow the following rules:
1. Introduce or add a slack variable for each constraint of the form
2. Introduce or subtract a surplus variable and add an artificial variable in each
constraint.
3. Introduce an artificial variable in each = constraint.
4. For each artificial variable A, add -MA to the objective function. Use the same
constant M for all artificial variables.

Illustrated in the following Slides:

 B. Simplex Method

Steps in Simplex Method

 Step 1 Formulate LPP Model
 Step 2 Standardize the problem
i.e. Convert constraint inequality into equality form by introducing
a variable called Slack variable.
Slack Variables:
A slack variable(s) is added to the left hand side of a < constraint
to covert the constraint inequality in to equality.
Cont’d (Steps in Simplex Method)
40
 The value of the slack variable shows unused resource.
 Slack variables represent unused resource or idle capacity.
 Thus, they don’t produce any product and their contribution to profit is zero.
 A slack variable emerges when the LPP is a maximization problem.
 Slack variables are added to the objective function with zero coefficients.
 Let that s1, s2, and s3 are unused labor, machine and marketing hrs. respectively.
 Example 41
Taking the microcomputer problem its standard form is as follows:
Solve the problem using the simplex approach

Zmax = 60X1 + 50X2

4X1 + 10X2  100

2X1 + X2  22

3X1 + 3X2  39

X1, X2  0
 42
Standard form
Zmax = 60X1 + 50X2 + 0S1 + S2 + 0S3

4X1 + 10X2 + S1 = 100

2X1 + X2 + S2 = 22
3X1 + 3X2 + S3 = 39

X1, X2, S1, S2, S3  0

Cont’d 43
 Torepresent the data, the simplex method uses a table called the
simplex table or the simplex matrix.
 In
constructing the initial simplex tableau, the search for of the
optimal solution begins at the origin. Indicating that nothing can be
produced;
 Thus, first assumption, No production implies that x1 =0 and x2=0
Cont’d 44
 4X1 + 10X2 + S1 +0 s2+ 0 s3= 100
4(0) +0 + s1 +0 s2+ 0 s3= 100
s1= 100 – Unused assembly time.
Therefore,
Max.Z=60x1 +50x2 + 0 s1 +0 s2+ 0 s3
 2x1+1x2 +0 s1 + s2+ 0 s3= 22 =60(0) +50(0) + 0(100) +0(22) + 0(39)
2(0) +1(0) + 0s1 + s2+ 0 s3= 22 =0

s2= 22 – Unused inspection time.

 3x1+3x2+ 0s1 +0s2+ s3= 39

3(0 )+3(0)+ 0s1 +0 s2+ s3= 39
Step 3. Construct the initial tableau 45

The initial tableau always represents the “Do Nothing” strategy, so

that the decision variables are initially non-basic.
List the variables across the top of the table and write the objective
function coefficient of each variable jut above it.
There should be one row in the body of the table for each constraint.
List the slack variables in the basis column, one per raw.
In the Cj column, enter the objective function coefficient of zero for each
slack variable. (Cj - coefficient of variable in the objective function)
Compute values for row Zj
Computer values for Cj – Zj.
46
 Interpretation
 Cj = the coefficient of the variables in the objective function in the standard form.
 Cb = the coefficient of basic variables in the obj. fun.
 X1, X2, ..Xn = decision variables .
 S1, s2, Sn = basic variables (slack).
 a11, a12,… coefficient of DV in the constraint set.
 1, 0, 1 are coefficient of basic variables in the constraints set.
 RHSV = the right hand side value of the constraints.

47
Step 3 cont’d
Cj 60 50 0 0 0
48
RHSV Ratio
Basic X1 X2 S1 S2 S3
variable

S1 0 4 10 1 0 0 100 100/4 = 25

S2 0 2* 1 0 1 0 22 22/2 = 11

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

Zj 0 0 0 0 0 0

Cj-Zj 60 50 0 0 0 0
Evaluate, the initial Tableau, does it 49

optimal or not?

Based on the above explanation it is not optimal:

Current Solution is x1= X2 =0, and S1= 100, S2= 22
and S3 =39
Decision: S2 departing and X1 is entering variable
Step 4.
50
 Choose the “incoming” or “entering” variables
 Note:

 The entering variable is the variable that has the most positive value in
the Cj - Zj row also called as indicator row.
 Or the entering variable is the variable that has the highest contribution
to profit per unit.
a) X1 in our case is the entering variable
b) The column associated with the entering variable is called key or
pivot column ( X1 column in our case )
Step 5

51
Choose the “leaving “or “outgoing” variable
 In this step, we determine the variable that will leave the solution for X1 (or entering variable)
Note:
 The row with the minimum or lowest positive (non-negative) replacement ratio
shows the variable to leave the solution.
Replacement Ratio (RR) = Solution Quantity (Q)
Corresponding values in pivot column
Note: RR>0

 The variable leaving the solution is called leaving variable or outgoing variable.
 The row associated with the leaving variable is called key or pivot row (s3 column in our
case)
 The element that lies at the intersection of the pivot column and pivot row is called pivot
element(No 2 in our case)
Step 6: Develop subsequent tableaus 52

 Repeat step 3-5 till optimum basic feasible solution is obtained.

Or: repeat step 3-5 till no positive value occurs in the Cj - Zj row.

 Note:
o Divide each element of the pivot row by the pivot element to find new
values in the key or pivot row.
o Perform row operations to make all other entries for the pivot column
equal to zero.
Raw operation= old Raw Value – Key column Value (New raw value
Cont’d 53
Cj 60 50 0 0 0
Basic RHSV Ratio
variable
X1 X2 S1 S2 S3

S1 0 0 8 1 -2 0 56 56/8 = 7
X1 60 1 1/2 0 1/2 0 11 11/. 5 = 22
S3 0 0 3/2 0 -3/2 1 6 6/1.5 = 4

Zj 60 30 0 30 0 660
Cj-Zj 0 20 0 -30 0 0
Optimal table 54
Cj 60 50 0 0 0 Ratio

Basic RHSV
variable 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

Cj-Zj 0 0 0 -10 -40/3

Cont’d 55

 Since all the Cj - Zj < 0 optimal solution is reached at

X1 = 9
X2 = 4
S1 = 24 hrs
Z = Birr 740
 “A simplex solution is a maximization problem is optimal if the Cj
– Zj row consists entirely of zeros and negative numbers (i.e., there
are no positive values in the bottom row).”
MINIMIZATION PROBLEMS 56
 There are two methods to solve minimization LP problems:
1. Direct method/Big M-method/
Using artificial variables
2. Conversion method
Minimization by maximizing the dual
 Surplus Variable (-s):
 A variable inserted in a greater than or equal to constraint to create equality. It
represents the amount of resource usage above the minimum required usage.
 Surplus variable is subtracted from a > constraint in the process of converting the
constraint to standard form.
 Neither the slack nor the surplus is negative value. They must be positive or zero.
Cont’d

57
Example:
• 2x1+x2 < 40 ==>is a constraint inequality
x1= 12 and x2= 11==> 2x1+x2+s = 40 ==>2(12)+11+s = 40
==> s=5 unused resource
• 5x1+3x2 < 45
x1= 12 and x2= 11==> 5x1+3x2+s = 45 ==>5(12)+3(11)+s = 45
==> s=0 unused resource (No idle resource)
• 5x1+2x2 >20
x1= 4.5 and x2= 2==> 5x1+2x2- s = 20 ==>5(4.5)+2(2)-s = 20
==> s=6 unused resource
• 2x1+x2 >40
x1= 0 and x2= 0(No production)==> 5x1+2x2- s = 20 ==>5(4.5)+2(2)-s = 20
==> s=-6 (This is mathematically unaccepted)
Artificial variable
58
 Thus, in order to avoid the mathematical contradiction, we have to add
artificial variable (A)
 Artificial variable is a variable that has no meaning in a physical sense but acts as a tool to create an initial
feasible LP solution.
 Note:
Type of constraint To put into standard form
< --------------------------------------------- Add a slack variable
= ---------------------------------------------Add an artificial variable
> ---------------------- Subtract a surplus variable and add artificial variable
Big M-method
59
 The Big-M Method is a method which is used in removing artificial
variables from the basis.
 Inthis method; we assign coefficients to artificial variables,
undesirable from the objective function point of view.
 Ifobjective function Z is to be minimized, then a very large
positive price (called penalty) is assigned to each artificial variable.
 Similarly, if Z is to be maximized, then a very large negative price
(also called penalty) is assigned to each of these variables.
Characteristics of Big-M Method: 60
A. High penalty cost (or profit) is assumed as M
B. M is assigned to artificial variable A in the objective function Z.
C. Big-M method can be applied to minimization as well as maximization problems with the
following distinctions:
 Minimization problems
-Assign +M as coefficient of artificial variable A in the objective function Z
 Maximization problems:
-Here –M is assigned as coefficient of artificial variable A in the objective function Z
D. Coefficient of S (slack/surplus) takes zero values in the objective function Z
E. For minimization problem, the incoming variable corresponds to the highest negative value
of Cj-Zj.
F. Solution is optimal when there is no negative value of Cj-Zj.(For minimization case)
Example: 61

 1. Minimize Z=25x1 +30x2

Subject to:
20x1+15x2 > 100
2x1+ 3x2 > 15
x1, x2 >0
Solution 62
Step 1: Standardize the problem
Minimize Z=25x1 +30x2 +0s1+0s2 +MA1+MA2

Subject to:
20x1+15x2- s1+A1 = 100
2x1+ 3x2 –s2+A2 = 15
x1, x2 , s1, s2 ,A1 ,A2 > 0
Step 2: Initial simplex tableau
The initial basic feasible solution is obtained by setting x 1= x2= s1= s2=0
No production, x1= x2= s1=0==>20(0) +15(0) - 0+A1 = 100 ==> A1 = 100
x1= x2= s2=0==>0(0)+3(0) - 0+A2 =15==> A2 = 15
 Initial simplex tableau
Cont’d
63

Note:
Once an artificial variable has left the basis, it has served its purpose and can therefore be removed from the simplex
tableau. An artificial variable is never considered for re-entry into the basis.
2 Simplex Tableau
nd
Cont’d
64
 Cont’d
3rd Simplex Tableau 65
Cont’d 66

Cj - Zj > 0==>Optimal solution is reached

X1=5/2
X2=10/3 and
MinZ=162.5

Note:
As long as an “A” variable is available in the solution variable column, the
solution is infeasible.
Maximization with mixed constraints 67

 The simplex method requires that all the constraints be in standard

form.
 Constraints that are ≤ can be put in to standard form by adding a
slack variable in the constraint.
 Constraints with ≥or = sign are handled a bit differently.
 Cont’d 68

 Tochange equality constraints to standard form add artificial

variables
 Toconvert this inequality to standard form subtract surplus
variable first and add artificial variable
 69
Solve using simplex method

Max! 6X + 8Y
Subject to: Y≤4
X+Y=9
6X+ 2Y ≥ 24
X, Y ≥ 0
 70
In standard form

Max! 6X + 8Y + 0S1 + 0S3 – MA2 – MA3

Subject to: Y+ S1 = 4
X+Y + A2 = 9
6X+ 2Y –S3 + A3 = 24
All variables ≥ 0
Initial table 71

BV CBV X Y S1 S3 A2 A3 Quantity
6 8 0 0 -M -M

S1 0 0 1 1 0 0 0 4
A2 -M 1 1 0 0 1 0 9
A3 -M 6 2 0 -1 0 1 24

Z -7M -3M 0 M -M -M -33M

C-Z 6+ 7M 8+3M 0 -M 0 0
 Second table 72

BV CBV X Y S1 S3 A2 A3 Quantity
6 8 0 0 -M -M

S1 0 0 1 1 0 0 0 4
A2 -M 0 2/3 0 1/6 1 -1/6 5
X 6 1 1/3 0 -1/6 0 1/6 4

Z 6 2-2M/3 0 -1M/6 -1 -M 1+M/6 24 - 5M

C-Z 0 6+2M/3 0 1+ M/6 0 -1-m/6
Third table 73
BV CBV X Y S1 S3 A2 Quantity
6 8 0 0 -M

Y 0 0 1 1 0 0 4
A2 -M 0 0 -2/3 1/6 1 7/3
X 6 1 0 -1/3 -1/6 0 8/3

Z 6 8 6 + 2M/3 -M/6 -1 -M 48 -7M/3

C-Z 0 0 -6-2M/3 1+ M/6 0
Fourth table 74
BV CBV X Y S1 S3 Quantity

6 8 0 0

Y 8 0 1 1 0 4
S3 0 14
X 6 0 0 -4 1 5
Reading Assignment

Sensitivity Analysis and Duality