2

UNIT 2: Linear Programming

UNIT

LINEAR
PROGRAMMING

This unit discusses the application, advantages,

and limitations of Linear Programming.

It focuses on the formulation of Linear

Programming models and the use of the
graphical procedure to solve them.

It covers the use of Simplex Solution as a

method of analysis.

IT 305: QUANTITATIVE METHODS 35

UNIT 2: Linear Programming

WHAT DO YOU ALREADY

PRETEST

KNOW?

Name: Date:
Course & Section: Result:

Let us find out how much you already know about this lesson. Choose the letter
that corresponds to your answer. Take note of the questions that you were not
able to answer correctly. Find the right answer as you go through this module.

1. Linear Programming is a
a. Constrained optimization c. The technique for economic
technique allocation of limited resources
b. Mathematical technique d. All of the above
2. A constraint in the linear programming model restricts
a. Value of a decision variable c. Use of the available resources
b. Value of an objective function d. All of the above
3. Constraints of a linear programming model represent
a. limitations c. Balancing limitations and
requirements
b. requirements d. All of the above
4. How many decision variables can be used in a graphical method?
a. 4 c. 2
b. 3 d. 1
5. What is the area bounded by the constraints?
a. Feasible region c. key region
b. Pivotal region d. None of the above
6. What is another term for key elements common to the incoming and outgoing
vector in the simplex method?
a. Artificial c. pivotal
b. slack d. surplus
7. What variable represents the amount by which solution value exceeds a
resource?
a. slack c. artificial
b. surplus d. None of the above
8. What variable represents unused resources and is added to the original
objective function with zero coefficients?
a. slack c. artificial
b. surplus d. None of the above

IT 305: QUANTITATIVE METHODS 36

 LESSON 1:
UNIT 2: Linear Programming

INTRODUCTION TO LINEAR
PROGRAMMING

OBJECTIVES:

At the end of the lesson, you should be able to:

 Explore linear programming basic requirements

 Locate areas of application and its scope

Time Duration: 1 hour

IT 305: QUANTITATIVE METHODS 37

Introduction
UNIT 2: Linear Programming

Every organization aims for optimal utilization of its limited or scarce

resources like men, money, materials, machines, methods, and time to reach the
objectives. The results can be measured in terms of profits, losses, return on money
invested, etc. To attain these results, the decision-maker has to have thorough
knowledge about the tasks or jobs and the relationships among them. Linear
Programming is one of the important Quantitative Methods tools used to have an
optimal way of allocating scarce resources so it can optimize the results either by
maximizing the profits or minimizing the costs.
George B. Dantzig innovated this technique while he was working for U.S. Air
force during World War II, 1947. This technique was initially used to solve tough
logistic problems like assignment and transportation, but later on this technique has
been used widely to almost every functional area of management, production
planning, and control, personnel management, advertising, and promotion.

What is Linear Programming (LP)?

 It is the process of taking linear inequalities relating to some situation

and finding the "best" value obtainable under those conditions.
 It is a mathematical model technique designed to optimize the usage of
limited resources that have been developed to help managers or
administrators in decision-making.
 Linear programming is a collection of procedures for maximizing (profit)
or minimizing (cost) linear functions subject to given linear constraints.
 The solution of typical real-life linear programming problems requires
the implementation of specific procedures on a computer; it is not this
computer programming to which the "programming" of linear
programming refers.
 “Programming” in the LP means the development of
effective algorithms for solving problems.
 The effectiveness of such algorithms is largely dependent
upon the particular applications from which the problems
arise.
 LP will not only allow us to solve many different types of
problems in many different contexts but will provide
deeper insights into the fields in which LP is used.
 It is particularly helpful in solving problems concerning
resource allocation and scheduling that are very common in
the business world.

IT 305: QUANTITATIVE METHODS 38

Basic Requirements
UNIT 2: Linear Programming

1. Decision Variables and their Relationships.

- The decision variable refers to any candidate (person, service,
projects, jobs, tasks) competing with other decision variables for
limited resources.
- These variables are interrelated in terms of utilization of
resources and need simultaneous solutions, i.e., the relationship
should be linear.
- These provide choices available to the decision-maker in terms of
amounts of either inputs or outputs.
2. Objective Function.
- The Linear Programming Problem must have a well-defined
objective function to optimize the results.
- It is expressed as a linear function of decision variables (Z =
X1 + X2, where Z represents the objective, i.e.,
minimization/maximization, X1 and X2 are the decision variables
directly affecting the Z value).
- A maximization problem involves profits, revenues, efficiency, or
rate of return. A minimization problem involves a cost in time
distances traveled, or scrap.
3. Constraints.
- These are limitations that restrict the alternatives available to
decision- makers, each of which is either linear equality or linear
inequality.
4. Alternative Courses of Action.
- There must be a presence of alternative solutions for the purpose
of choosing the best or optimum one.
5. Non-Negativity Restrictions.
- The decision variables should always have non-negative values
means the values for decision variables should be greater than or
equal to 0
- If any of the these variables is unrestricted in sign, a tool can be
employed, which will enforce the negativity without changing the
original information of a problem.
6. Linearity and Divisibility.
- All relationships (objective function and constraints) must exhibit
linearity with an assumption that decision variables are continuous.
7. Deterministic.
- In Linear Programming, it is assumed that all model coefficients
are completely known.

Typical examples are as follows:

 Determining the "best" production levels for maximum profits under
 limited materials and labor.

IT 305: QUANTITATIVE METHODS 39

UNIT 2: Linear Programming

 Determining the best way to allocate a fixed advertising budget among

alternative advertising media that would maximize advertising
effectiveness.
 Selecting the proper warehouse where it should ship the right quantity
of products to customers in order to minimize the total transportation
costs.
 Developing productions schedule and an inventory policy that will
satisfy sales demand in the future periods while minimizing the
production and inventory costs.

Advantages of Linear Programming:

1. It helps in proper and optimum utilization of scarce resources.
2. It improves the quality of decisions.
3. The decision-maker becomes more objective and less subjective.
4. It helps in considering other constraints operating outside the problem.
5. It hints the manager about the difficulties faced during the production activities.

Limitations of Linear Programming:

1. The treatment of variables having non-linear relationships is the greatest
limitation.
2. It can come out with non-integer solutions too, which would be many times
meaningless.
3. It rules out the effect of time and uncertainty conditions.
4. The objective set will be single, and on the contrary, in the real, there might be
several objectives.
5. Large-scale problems tend to be unaccommodative to solve under LP.

IT 305: QUANTITATIVE METHODS 40

 HOW DO YOU APPLY
APPLICATION
UNIT 2: Linear Programming ACTIVITY FOR LESSON 1

WHAT YOU HAVE LEARNED?

Name: Date:
Course & Section: Result:

Answer the following questions briefly.

1. Why is Linear Programming important in Quantitative Methods?

2. Explain the limitations of Linear Programming.

3. Differentiate Decision Variables and Constraints.

IT 305: QUANTITATIVE METHODS 41

 LESSON 2:
UNIT 2: Linear Programming

THE LINEAR PROGRAMMING

MODEL

OBJECTIVES:
At the end of the lesson, you should be able to:

 Apply the linear programming algorithm

 Analyze and solve the linear programming problems

Time duration: 2 hours

IT 305: QUANTITATIVE METHODS 42

Linear Programming Family
UNIT 2: Linear Programming

The family of LP consists of:

1. Formulation of Linear Programming Problems. (LPP)
2. LP – Graphical Solutions
3. LP – Simplex Method
4. LP – Assignment Problems
5. LP – Transportation Problems

Formulation of LP Models
Steps for Formulating LPP
1. Identify the decision variables, if the problem is a maximization (P-profit) or
minimization (C- cost).
2. Write the objective function.
3. Formulate the constraints.
4. State the non-negativity constraints.

Example 1 :

Alpha Company manufactures two types of products Sam & Sung, and sells
them at a profit of $2 on type Sam and $3 on type Sung. Each product is processed
on 2 machines M & B. Type Sam, requires 1 minute of processing time on M and 2
minutes on B. Type Sung requires one minute on M &1 minute on B. The machine
M is available for not more than 6 hours and 40 minutes, while machine B is
available for 10 hours during any working day. Formulate the problem as LPP.
Solution:

Time in Products (mins.) Total time

Machines Type Sam Type Sung available
( in mins.)
M 1 1 400
B 2 1 600
Profit Per Unit $2 $3

Table 2.2.1. Showing the Time (in minutes) Available and the Profit

Step 1. Identify the decision variables.

Let X1 be the no. of products of type Sam
X2 be the no. of products of type Sung

IT 305: QUANTITATIVE METHODS 43

UNIT 2: Linear Programming

Step 2. Write the objective function.

Since the profit on type Sam is $2 per product, 2X 1- will be the profit on
selling X1 units of type Sam. Similarly, 3X2 will be the profit of selling X2 units of
type Sung.
Hence the objective function will be:

Maximize P = 2X1 + 3X2

Step 3. Formulate the constraints.

Since machine ‘M’ takes one minute on ‘Sam’ and one minute on
‘Sung’, the total number of minutes required is given by X1 + X2. Similarly, on
machine ‘B’ ,2X1 +X2. But ‘M’ is not available for more than 400 minutes.
Therefore, X1 + X2  400 and ‘B’ is not available for more than 600 minutes;
therefore, 2X1 +X2  600.

Subject to:
X1 + X2  400
Time availability constraints
2X1 +X2 
600

Step 4: State the non-negativity constraints.

X1 , X2 ≥ 0 Non-negativity constraints

Final Answer:

Maximize P = 2X1 + 3X2

Subject to:
X1 + X2  400
2X1 +X2 
600 X1 , X2 ≥ 0

IT 305: QUANTITATIVE METHODS 44

 UNIT 2: Linear Programming

Example 2 :

A firm manufactures three types of products A, B and C. The profits are $3,
$2, and $4, respectively. The firm has two machines, and below is the required
processing time in minutes for each machine from the product.
MACHINE PRODUCT
A B C
GAMMA 4 3 5
PHI 3 2 4

Machine GAMMA and PHI have 4,000 and 4,500 machine minutes, respectively.
The company must manufacture 100 A's, 200 B's, and 50 C's but not more than 150 A's.
Formulate an LPP to maximize the profit.

Solution:
Let X1 be the type of product A
X2 be the type of product B
X3 be the type of product C

Maximize P = 3X1 + 2X2 + 4X3

Subject to:
4X1 + 3X2 + 5X3  4,000
3X1 + 2X2 + 4X3  4,500
X1  150
X2  200
X3  50
X 1, X 2, X 3 ≥ 0

IT 305: QUANTITATIVE METHODS 45

UNIT 2: Linear Programming

Example 3 :

Maximization Case with Mixed Constraints:

The manager of SHELL Co. must decide on the optimal mix of two
possible blending processes, of which the input and output per production run are
given as follows:

PROCESS INPUT (units) OUTPUT (units)

CRUDE A CRUDE B GASOLINE GASOLIBE B
X
I 5 3 5 8
II 4 5 4 4

The maximum amount available of crude A and B is 200 units and 150
units, respectively. Market requirements show that at least 100 units of
gasoline X and 80 units of gasoline Y must be produced. The profit per
production run from process I and process II are $300 and $400 respectively.
Formulate the above problem as LPP.

Solution:
Let X1 represent process I
X2 represent process II

Maximize P = 300X1 + 400X2

Subject to:
5X1 + 4X2  200
3X1 + 5X2  150
5X1 + 4X2 ≥ 100
8X1 + 4X2 ≥ 80
X 1, X 2, ≥0

IT 305: QUANTITATIVE METHODS 46

UNIT 2: Linear Programming

Example 4 :

A city hospital has the following daily requirements of the nurses on duty at a
minimal level:
PERIOD CLOCK TIME MINIMAL NO. OF
(24 HRS.A DAY) NURSES REQUIRED
1 6 am – 10 am 2
2 10 am – 2 pm 7
3 2 pm – 6 pm 15
4 6 pm – 10 pm 8
5 10 pm – 2 am 20
6 2 am – 6 am 6

Nurses report to the hospital at the beginning of each period and work for 8
consecutive hours. They want to determine minimal number of nurses to be
employed so that there will be a sufficient number of nurses available for each
period. Formulate this as LP model by setting up appropriate constraints and
objective function.
Solution:
Let X1 be the no. of nurses working during period 1
X2 be the no. of nurses working during period 2
X3 be the no. of nurses working during period 3
X4 be the no. of nurses working during period 4
X5 be the no. of nurses working during period 5
X6 be the no. of nurses working during period 6

Minimize C = X1 + X2 + X3 + X4 + X5 + X6
Subject to:
X1 + X 2 ≥ 2
X2 + X 3 ≥ 7
X3 + X4 ≥ 15
X4 + X 5 ≥ 8
X5 + X6 ≥ 20
X6 + X 1 ≥ 6
X 1, X 2, X 3, X 4, X 5, X 6 ≥ 0

IT 305: QUANTITATIVE METHODS 47

 UNIT 2: Linear Programming
APPLICATION ACTIVITY FOR LESSON 2

HOW DO YOU APPLY

WHAT HAVE YOU

Name: Date:
Course & Section: Result:

Answer the following briefly:

1. Explain the linear programming problem giving two examples.

2. What are the important characteristics of a linear programming model?

IT 305: QUANTITATIVE METHODS 48

 UNIT 2: Linear Programming

Formulate the following problems as a standard LP:

3. One of the interesting Linear Programming problems is that of a balanced
diet. For dieticians, a balanced diet must contain certain quantities of nutrients
such as proteins, minerals, vitamins, etc. Suppose that you are asked to find
out the food that should be recommended from a large number of alternative
sources of these nutrients so that the total cost of food satisfying the minimum
requirements of a balanced diet is the lowest. The medical experts and the
dieticians tell us that it is necessary for an adult to consume at least 75 g. of
proteins, 85 g. of fats, and 300 g. of carbohydrates daily. The following table
gives the different items (which are readily available in the market); Item
analysis, and their respective costs.

FOOD FOOD VOLUME (PER 100 gram) COST/KG

PROTEIN FATS CARBOHYDRATES
1 8 1.5 35 1
2 18 15 -- 3
3 16 4 7 4
4 4 20 2.5 2
5 5 8 40 1.5
6 2.5 --- 25 3
MIN. DAILY 75 85 300
REQTS.

IT 305: QUANTITATIVE METHODS 49

UNIT 2: Linear Programming

4. A firm manufacturer headache pills in two sizes A and B. Size A contains I

grains of aspirin, 5 grains of bicarbonate, and 1 grain of codeine. It is found by
uses that it requires at least 12 grains of aspirin, 74 grains of bicarbonate, and
24 grains of codeine for providing an immediate effect. It is required to
determine the least number of pills a patient should take to get immediate
relief.

IT 305: QUANTITATIVE METHODS 50

 LESSON 3:
UNIT 2: Linear Programming

LINEAR PROGRAMMING –
GRAPHICAL SOLUTION

OBJECTIVES:

At the end of the lesson, you should be able to:

 Graph solution sets of linear programming

 Find the vertices of the feasible region

 Determine the maximum/minimum value of the objective

function

Time duration: 3 hours

IT 305: QUANTITATIVE METHODS 51

Solving an LP through Graphical Method
UNIT 2: Linear Programming

 Linear programming problems with two variables can be represented

and solved easily by the graphical method.
 This method will help to understand the simplex method.
 Since X1, X2,…Xn ≥ 0, only the first quadrant will be considered.

Example 1 :

Ayala Company manufactures two products: A and B. Each unit of product A

contains 2 kilos of aluminum and 1 kilo of steel. Each unit of B contains 14 kilos of
aluminum and 2 kilos of steel. Each unit of B contains 14 kilos of aluminum and 2
kilos of steel. Ayala has an available supply of 70 kilos of aluminum and 20 kilos of
steel. Ayala makes a profit of $20 on each unit of A and $50 on each unit of B. Find
Ayala Company's maximum profit and the number of units of A and B it must
manufacture in order to obtain its maximum profit.

Solution:

Step 1: Formulate the LPP.

Let x = Number of units of product A that Ayala can manufacture

y = Number of units of product B that Ayala can manufacture

Maximize P = 20x+ 50y

Subject to:
2x + 14y  70 or x + 7y 
35 x + 2y  20
x, y ≥ 0

Step 2. Change ≤ to = and find the x - and y–intercepts.

x-intercept y - intercept
x + 7y = 35 ( 35 , 0) (0, 5)
x + 2y = 20 ( 20 , 0) (0, 10)

IT 305: QUANTITATIVE METHODS 52

 UNIT 2: Linear Programming

Step 3. Graph the lines and shade the area that satisfies each linear inequality. The
solution/feasible region is the intersection of the shaded areas.

10 x + 2y = 20
9
8
7
6
B5 (0,5) 2x + 14y = 70
4
3 D
2
1
0A C (20,0)
0 feas5ible 15 20 25 30 35 40
re1g0ion

Step 4: Find the vertices of the feasible region.

The vertices of the feasible region are A (0, 0), B (0, 5), C (20, 0) and the point
of intersection of lines 2x + 14y = 70 and x + 2y = 20 which is D (14, 3).
Therefore the feasible region is "ABCD".

Step 5: Substitute the value of the vertices into the objective function.

Corner Points Vertex Objective Function:

P = 20x + 50y

A (0, 0) P = 20(0) + 50(0) = $0

B (0, 5) P = 20(0) + 50(5) = $250

C (20, 0) P = 20(20) + 50(0) = $400

D (14, 3) P = 20(14) + 50(3) = $430

Step 6: Since the objective function is maximization, we need to get the highest
value of the profit.

Therefore, Ayala Company should produce 14 units of product A and 3 units

of product B for a maximum profit of $430.

IT 305: QUANTITATIVE METHODS 53

 UNIT 2: Linear Programming

Example 2 :

A diabetic patient needs to take at least 40 units of vitamin A, at least 30 of

vitamin C, and at least 30 of vitamin E each day. Each Brand X multivitamin capsule
contains 4 units of A, 6 of C, and 2 of E; each Brand Y capsule contains 5 units of A,
3 of C, and 5 of E. If each Brand X capsule costs $6 and each Brand Y capsule costs
$9, how many capsules should the patient take each day in order to minimize the cost?

Solution:

Step 1: Formulate the LPP

Let x = number of Brand X capsules to take each day

y = number of Brand Y capsules to take each day

Minimize C = 6x + 9y

subject to 4x + 5y ≥ 40
6x + 3y ≥ 30 or 2x + y ≥ 10
2x + 5y ≥ 30
x, y ≥ 0

Step 2. Change ≤ to = and find the x - and y–intercepts.

x - intercept y - intercept
4x + 5y = 40 (10 , 0) (0, 8)
2x + y = 10 ( 5 , 0) (0,10)
2x + 5y = 30 (15 , 0) (0, 6)

The vertex (5,20) was obtained as the point of intersection of the lines
3 3
4x + 5y = 40 and 6x + 3y = 30 and that the vertex (5, 4) was obtained as the point of
intersection of the lines 2x + 5y = 30 and 4x +5y = 40.

IT 305: QUANTITATIVE METHODS 54

 UNIT 2: Linear Programming

Step 3. Graph the lines and shade the area that satisfies each linear inequality. The
solution/feasible region is the intersection of the shaded areas.

A(0,10)
10
9
8
7

B (5,20)
6
3
5 3

4
3
2x + y = 10 C (5, 4)
2
1
0
0 2 4 6 8 10 12 14 1 6
D ( 1 5,
0)

4x + 5y = 40 2x + 5y = 30

Step 4: Find the vertices of the feasible region.

The vertices of the feasible region are A(0, 10), B (5,20) , C (5,4) and D (15, 0)..
3 3

Step 5: Substitute the value of the vertex into the objective function.

Vertex Objective Function:

C = 6x + 9y

A (0, 10) C = 6(0) + 9(10) = $90

B (35,203) C = 6(5/3) + 9(20/3) = $70
C (5, 4) C = 6(5) + 9(4) = $66
D (15, 0) C = 6(15) + 9(0) =$ 90

Step 6: Since the objective function is Minimization, we need to get the lowest value
of the cost.
At $66, the minimum cost per day occurs if the patient takes 5 Brand X
capsules and 4 Brand Y capsules per day.

IT 305: QUANTITATIVE METHODS 55

 HOW DO YOU APPLY
APPLICATION
UNIT 2: Linear Programming ACTIVITY FOR LESSON 3

WHAT YOU HAVE

Name: Date:
Course & Section: Result:

Answer the following briefly:

1. What do you understand by ‘Graphical Method’? Give its limitations.

2. Discuss the graphical method of solving a Linear programming Model

involving two variables.

IT 305: QUANTITATIVE METHODS 56

 UNIT 2: Linear Programming

Completely solve the following LPP graphically:

3. Max Z = 50X + 120Y
Subject to :
100X + 200Y ≤ 10,000
10X + 30Y ≤ 1200
X + Y ≤ 110
X ≥ 0, Y ≥ 0

IT 305: QUANTITATIVE METHODS 57

UNIT 2: Linear Programming

4. Armour Corporation makes household cleansers in two strengths: weak and

strong. Each gallon of the weak cleanser contains 1 liter of acid solution and 10
grams of emulsifier. Each gallon of the strong cleanser contains 2 liters of acid
and 30 grams of emulsifiers. According to contracts the corporation has signed
with its suppliers, Armour Corporation must use at least 40 liters of acid solution
and 450 grams of emulsifiers each week. It costs the company P25 to make a
gallon of weak cleanser and P30 to make each gallon of strong cleanser. How
many gallons of each should the firm make each week in order to minimize its
costs?

IT 305: QUANTITATIVE METHODS 58

 LESSON 4:
UNIT 2: Linear Programming

LINEAR PROGRAMMING:
THE SIMPLEX METHOD

OBJECTIVES:

At the end of the lesson, you should be able to:

 Explain the meaning of the word “simplex” and the logic of using
simplex method

 Convert LPP into its standard form by adding slack, surplus and
artificial variables

 Solve and find the optimum solution of LPP using simplex method

Time duration: 3 hours

IT 305: QUANTITATIVE METHODS 59

What is Simplex Method?
UNIT 2: Linear Programming

Simplex Method is one of the most powerful & known methods for linear
programming. It is an iterative procedure for getting the most feasible solution. It
involves an iteration of one basic feasible solution to another. An initial simplex
tableau will be constructed out of different kinds of variables together with their
coefficients from the modified set of equality constraints, which is called the new
program of equality constraints. This tabular presentation of the solution is derived
from the concept of reducing the augmented and elementary matrices to its echelon
form.

In any type of linear programming model, whether maximization or

minimization, the following assumptions should be taken into consideration.

1. A set of variables: basic, slack, and artificial variables are constrained to be

non-negative since these variables would present measurable quantities.

2. A set of linear constraints, each of which contains a ≤, ≥, or = signs, is

converted to a new program of equality constraints for the purpose of
transferring its coefficients and variables to the simplex tableau.

3. A linear objective function is either maximization or minimization.

4. The basic variables, usually denoted by X₁, X₂, …. , Xn, represents the
product mix; or i.e., the desired units that will yield an optimum or feasible
solution.

5. The slack variables, denoted by S₁, S₂, … , Sj, represent the unused
resources or the surplus and, therefore, these will demonstrate negligible or
zero profit cost contribution.

6. The artificial variables, denoted by A₁, A₂, …, Aj, represent the most
expensive resources substitutes; thus, they will demonstrate the highest cost
contribution to the objective function. It is suggested that the students will use
any of the powers of 10 (e.g., 10, 100, 1,000, 10,000…) for the coefficient of
A, in the objective function as long as it is the highest among the given
coefficients of the variables.

Solving LP Problems Using Simplex Method

Steps in Solving Linear Programming Problems by the Simplex Method

Step 1. Convert the functional inequality constraints to equivalent equality

constraints. An inequality of the type ≤ or ≥ can be converted to an equation
by augmenting its left hand side with a slack, surplus or artificial variable. The
constraints to a new program of equality constraints by following these rules:
IT 305: QUANTITATIVE METHODS 60
UNIT 2: Linear Programming

For Maximization Problem:

 If the symbol is “≤”, then add slack variables Sj to the left side then
change the sign to equality “=”.
 If the symbol is “=”, then add slack variables, Sj, to the left hand side
and retain the equality “=” sign.
 If the symbol is ‘’≥’’ then multiply both sides by (-1), add slack variable.
Sj, to the left side and change the sign to “=”.

For Minimization Problems:

 If the symbol is ≤, then add slack variables Sj to the left-hand side and
change the sign to “=”.
 If the symbol is “=”, then add artificial variables Aj to the left-hand side
and retain the “=” sign.
 If the symbol is “≥”, then subtract surplus variables Sj but add artificial
variable on the left side and change the sign to “=”.

Step 2. Tabulate the data into the first iteration of Simplex Method

Basic Pj Quantity x y S1 S2 Minimum

Variable Ratio
(BV)
S1

S2

Zj

Pj - Z j

Step 3. Determine the entries for Zj row and (Pj – Zj) row for a maximization
problem and every variable column entry. Zj row entries are obtained by
taking the sum of the products of P j column entries (Cj column entries for a
minimization problem) and every variable column entries. P j row entries are
obtained by subtracting the Zj row entries from Pj row entries (Cj row entries
for a minimization problem).

Step 4. Determine the entering variable of the optimum column, i.e., the
column with the highest positive entry of P j – Zj row. Encircle the optimum
column. (For minimization problem, choose the column with the most negative
entry of Cj – Zj row).

IT 305: QUANTITATIVE METHODS 61

UNIT 2: Linear Programming

Step 5. Determine the outgoing variable of the pivot row, i.e., the row with
least positive quotient between quantity column entries and optimum column
entries. Encircle the pivot row.

Step 6. Determine the New Pivotal Row (NPR) by dividing each pivotal row
with the pivot element. This pivot element is the entry along intersections of
pivot row and optimum column. Encircle the New Pivot Row.

New Pivot Row = Pivot Row + Pivot Element

Step 7. Determine the new remaining rows. This is done by taking the sum of
the entries from an old row and new pivot row multiplied by the negative of an
element along the intersection of Optimum Column and the Old Row, which is
being evaluated.

New Rj = old R + (-ej) NPR

where:
R = Row
e = Pivot element
NPR = New Pivot Row

Step 8. Construct the next tableau by entering the values obtained from Steps
6 and 7. If there is no positive entry found on the Pj – Zj row, then the process
stops for the final or optimum table has been obtained. For the minimization
problem, an optimum table is obtained if there is no negative entry found on
the Cj – Zj row.

IT 305: QUANTITATIVE METHODS 62

 UNIT 2: Linear Programming

Example 1:

Maximize P = ₱5x + ₱4y

Subject to x+y≤6
2x + y ≤ 8
x≥0
y≥0
Solution:

Step 1: Conversion of inequalities into equalities by adding slack variables.

Adding the slack variables S1 and S2 and modifying the objective function, the
new program of constraints will be

Maximize P = 5x + 4y + 0S1 + 0S2

Subject to x + y + S1 = 6
2x + y + S2 = 8
x≥0
y≥0
S1 ≥ 0
S2 ≥ 0

Steps 2 and 3: The initial simplex tableau. Determine the entries for Zj row and (Pj –
Zj) row for a maximization problem and every variable column entry.

Initial Tableau/Table 1:
Basic Pj Quantity x y S1 S2 Minimum
Variable Ratio
(BV)
S1 0 6 1 1 1 0
S2 0 8 2 1 0 1
Zj 0 0 0 0 0
Pj 5 4 0 0
Pj - Z j 5 4 0 0

Step 4. Determine the entering variable of the optimum column(O.C.), i.e., the
column with the highest positive entry of Pj – Zj row. Encircle the optimum column.

Basic Pj Quantity x y S1 S2 Minimum

Variable (Qty) Ratio
(BV) (Qty ÷
O.C.)
S1 0 6 1 1 1 0 6÷1 = 6
S2 0 8 2 1 0 1 8÷2 = 4
Zj 0 0 0 0 0
Pj 5 4 0 0
Pj - Z j 5 4 0 0

optimum column
IT 305: QUANTITATIVE METHODS 63
UNIT 2: Linear Programming

Step 5. Determine the outgoing or departing variable of the pivot row. The
variable corresponding to the smaller positive ratio is the entering or replaced
variable; thus, S2 is the outgoing variable.

replaced variable

Basic Pj Quantity x y S1 S2 Minimum

Variable (Qty) Ratio
(BV) (Qty ÷
O.C.)
S1 0 6 1 1 1 0 6÷1 = 6

S2 0 8 2 1 0 1 8÷2 = 4

Zj 0 0 0 0 0

Pj 5 4 0 0

Pj - Z j 5 4 0 0

outgoing variable pivot row optimum column

pivot element

Step 6. Determine the New Pivotal Row (NPR) by dividing each pivotal row
with the pivot element. This pivot element is the entry along intersections of
pivot row and optimum column. Encircle the New Pivot Row.

New Pivot Row = Pivot Row(P.R.)÷ Pivot Element(P.E.)

Basic Pj Quantity x y S1 S2 Minimum

Variable (Qty) Ratio
(BV) (Qty ÷ O.C.)
S1 0 6 1 1 1 0
x 5 4 1 0
Zj 20 5 0

3
Pj 5 4 0 0

2
Pj - Z j 0

New Pivot Row (NPR)

IT 305: QUANTITATIVE METHODS 64

 UNIT 2: Linear Programming

Qty x y S1 S2
NPR (x)
= P.R. ÷ P.E. 8÷2 2÷2 1÷2 0÷2 1÷2
Answer: (x) 4 1 0

Step 7. Determine the new remaining rows and form the second tableau.

New Rj = old R + (-ej) NPR

New S1 = Old S1 + (-1) (NPRtable 1)

New S1 row = Qty x y S1 S2

Old S1 + (-1) (NPRtable 1)
Old S1 6 1 1 1 0
+ (-1) (NPRtable 1) -4 -1 -0
- -
Answer: (S1) Row 2 0 1
-

New Zj row:

New Z1 row = Qty x y S1 S2

(Pj * QtyS1) + (Pj * Qtyx)
Pj * QtyS1) + (Pj * Qtyx) 0(2) + 5(4) 0(0) + 5(1) 0(1) + 5(0)
0( ) + 5( ) 0( ) + 5( )
Answer: (Zj) Row 20 5 0
-

New (Pj - Zj) row:

Qty x y S1 S2
Pj - Z j 5 - 5 0- 0

3
4 - -

2
Answer: 0 0 0
Pj - Zj Row

IT 305: QUANTITATIVE METHODS 65

 UNIT 2: Linear Programming

Second Tableau:

Basic Pj Quantity x S1 S2 Minimum

Variable (Qty) Ratio
(BV) (Qty ÷ O.C.)
S1 2 1
- 2÷ =4
x 5 4 1 0
4÷ =8
Zj 20 5 0
Pj 5 4 0
3
2
Pj - Z j 0

outgoing variable optimum column (O.C)

Step 8: Construct the next tableau by entering the values obtained from Steps 6
and 7.

Solution for Third Tableau:

Qty x y S1 S2
NPR (y)
= P.R. ÷ P.E. 2÷½ 0÷½ ½÷½ 1÷½
- ÷
Answer: (y) 4 0 1 2 -1

New x Row:

New x row = Qty x y S1 S2

Old x + (- ) (NPRtable 2)
Old x 4 1 0

+ (- ) (NPRtable 2) - (4) - (0) - (1) - (2) - (-1)

Answer: (x) Row 2 1 0 -1 1

New Zj row:

New Zj row = Qty x y S1 S2

(Pj * QtyS1) + (Pj * Qtyx)
Pj * QtyS1) + (Pj * Qtyx) 5(2) + 4(4) 0(4) + 5(1) 1(4) + 5(0) 2(4)+5(-1) -1(4)+1(5)
Answer: (Zj) Row 26 5 4 3 1

IT 305: QUANTITATIVE METHODS 66

 UNIT 2: Linear Programming

New (Pj - Zj) row:

Qty x y S1 S2
Pj - Z j 5 - 5 4 - 4 0- 3 0-1
Answer: 0 0 -3 -1
(Pj - Zj) Row

Third and Final Tableau:

Basic Pj Quantity x y S1 S2 Minimum

Variable (Qty) Ratio
(BV) (Qty ÷ O.C.)
y 4 4 0 1 2 -1

x 5 2 1 0 -1 1

Zj 26 5 4 3 1

Pj 5 4 0 0
Pj - Z j 0 0 -3 -1

Since there is no positive entry found on the (Pj – Zj) row, the process stops for
the final or optimum table. Therefore, for every x = 2 and y = 4, Z = 26.

IT 305: QUANTITATIVE METHODS 67

 UNIT 2: Linear Programming

Example 2 :

Consider the problem of cost minimization:

Minimize C = 25x + 30y

Subject to x + 2y ≥ 40
10x + 30y ≥ 450
x≥0
y≥0

y≥0
Solution:

Step 1: Conversion of inequalities into equalities.

Adding the slack variables S1 and S2 and the artificial variables A1 and A2, the
linear programming problem can be stated as follows as the new program of
constraints:

Minimize C = 25x + 30y + MA1 +

MA2 Subject to x + 2y – S1 + A1 =

40
10x + 30y – S2 + A2 = 450
x, y, S1, S2, A1, A2 ≥ 0

Steps 2 and 3: The initial simplex tableau. Determine the entries for Zj row and
(Cj – Zj) row for a minimization problem and every variable column entry.

Instead of using M1, use powers of 10 like 10, 100, 1000, etc, depending on
the highest coefficient of x and y. In this example, since the highest coefficient is 30,
then we can use 100.

The initial simplex tableau/Table 1:

Basic Cj Quantity x y S1 S2 A1 A2 Minimum

Variable (Qty) Ratio
(BV) (Qty ÷ O.C.)
A1 100 40 1 2 -1 0 1 0 40÷2 =20
A2 100 450 10 30 0 -1 0 1 450÷30 = 15
Zj 49000 1100 3200 -100 -100 100 100
Cj 25 30 0 0 100 100
Cj - Zj -1075 -3170 100 100 0 0

IT 305: QUANTITATIVE METHODS 68

 UNIT 2: Linear Programming

Step 4. Determine the entering variable of the optimum column, i.e., the column
with the highest negative entry in the (Cj – Zj) row. Encircle the optimum column.

Basic Cj Quantity x y S1 S2 A1 A2 Minimum

Variable (Qty.) Ratio
(BV) (Qty ÷ O.C.)
A1 100 40 1 2 -1 0 1 0 40÷2 =20
A2 100 450 10 30 0 -1 0 1 450÷30 = 15
49000 1100 3200 -100 -100 100 100
Zj 25 30 0 0 100 100
Cj - Zj -1075 -3170 100 100 0 0

optimum column (O.C.)

Step 5. Determine the outgoing or departing variable of the pivot row. The
variable y corresponding to the smaller positive ratio is the entering or replaced
variable; thus, A2 is the outgoing variable.

Basic Cj Quantity x y S1 S2 A1 A2 Minimum

Variable (Qty) Ratio
(BV) (Qty ÷ O.C.)
A1 100 40 1 2 -1 0 1 0 40÷2 =20
A2 100 450 10 30 0 -1 0 1 450÷30 = 15
Zj 49000 1100 3200 -100 -100 100 100

Cj 25 30 0 0 100 100
Cj - Zj -1075 -3170 100 100 0 0

replaced variable
outgoing variable pivot element

pivot row

The variable allocated to enter at the next step is y because it has the most
negative value in (Cj – Zj) row and the variable to be replaced is A2 since
A1: 40÷2 =20 and A2: 450 ÷ 30 = 15

IT 305: QUANTITATIVE METHODS 69

 UNIT 2: Linear Programming

Step 6 and 7. Determine the New Pivotal Row (NPR) by dividing each
pivotal row with the pivot element. This pivot element is the entry along
intersections of pivot row and optimum column. Encircle the New Pivot Row.

New Pivot Row = Pivot Row ÷ Pivot Element

Second Tableau:

Basic Cj Quantity x y S1 S2 A1 A2 Minimum

Variable (Qty) Ratio
(BV) (Qty ÷ O.C.)
A1 100 10 0 -1 1
10÷ = 30
y 30 15 1 0 0
15÷ = 45
Zj 1450 30 -100 100

Cj 25 30 0 0 100 100
Cj - Zj 0 100 0

The variable to enter at the next step is X and the variable to be replaced is A1,
since

A 1: = 30

Y: = 45

Third Tableau:

Basic Cj Quantity x y S1 S2 A1 A2 Minimum

Variable (Qty) Ratio
(BV) (Qty ÷ O.C.)
x 25 30 1 0 -3 3
- 30 ÷ = 150
y 30 5 0 1 1 -1

Zj 900 25 30 -45 2 45 -2

Cj 25 30 0 0 100 100
Cj - Zj 0 0 45 -2 55 102

Since there is still a negative entry in the (Cj – Zj) row, then it is not yet optimal.
The variable to enter is S2, and the variable to be replaced is x.

IT 305: QUANTITATIVE METHODS 70

 UNIT 2: Linear Programming

Step 8: Construct the next tableau by entering the values obtained from Steps 6 and
7.

The revised simplex is shown in the fourth tableau.

Fourth and Final Tableau:

Basic Cj Quantity x y S1 S2 A1 A2 Minimum

Variable (Qty) Ratio
(BV) (Qty ÷ O.C.)
x 0 150 5 0 -15 1 15 -1

y 30 20 1 0 0

Zj 15 30 -15 0 15 0
600
Cj 25 30 0 0 100 100
Cj - Zj 10 0 15 0 85 100

The absence of negative entries in (Cj – Zj) row indicates that the optimal solution has
been obtained.

Solution in Second Tableau:

Qty x y S1 S2 A1 A2
NPR (y)
= P.R. ÷ 450÷30 10 ÷ 30 30 ÷ 30 0 ÷ 30 -1 ÷ 30 0 ÷ 30 1 ÷ 30
P.E.
Answer: 15 1 0 0
(y)

New A1 = Old A1 + (-2) (NPRtable 1)

New A1 row = Qty x y S1 S2 A1 A2

Old A1 + (-2) (NPRtable 1)
Old A1 40 1 2 -1 0 1 0
+ (-2) (NPRtable 1) -2(15) -2(1) -2(0) -2 (0)
-2( ) -2( )
Answer: (A1) Row 10 0 -1 1
-

IT 305: QUANTITATIVE METHODS 71

 UNIT 2: Linear Programming

New Zj row:

New Zj row = Qty x y S1 S2 A1 A2

(Cj * QtyA1) +
(Cj * Qtyy)
Cj * QtyA1) + 100(10) 100(0) 100(-1) + 100(1)
(Cj * Qtyy) + 100( ) + 30( ) + 30(1) 30(0) 100( )+ +30 100(- )
30(15) (0)
30( ) +30 ( )
Answer: (Zj) 1450 30 -100 100
Row

New (Cj - Zj) row:

Qty x y S1 S2 A1 A2
Cj - Zj 30 - 30 0 – (-100) 100 - 100 –
25 - 0- 100
( )
Answer: 0 100 0
(Cj - Zj) row

Solution in Third Tableau:

Qty x y S1 S2 A1 A2
NPR (x)
= P.R. ÷
P.E. 10÷ ÷ 0÷ -1 ÷ ÷ 1÷ - ÷
Answer: 30 1 0 -3 3
(x) -

New y = Old y + (- ) (NPRtable 2)

New y row = Qty x y S1 S2 A1 A2

Old y + (- ) (NPRtable 2)
Old y 15 1 0 0

+ (- ) (NPRtable 2) +(- )30 +(- )1 +(- )0 +(- )(- +(- )( ) +(- +(- )
3) )(3)
(- )
Answer: (y) Row 5 0 1 1 -1

IT 305: QUANTITATIVE METHODS 72

 UNIT 2: Linear Programming

New Zj row:

New Zj row = Qty x y S1 S2 A1 A2

(Cj * QtyA1) +
(Cj * Qtyy)
Cj * QtyA1) + 25(30) 25(1) 25(0) 25(-3) 25(3)
(Cj * Qtyy) + 30(5) + 30(0) + 30(1) +30(1) 25 ( ) + 30(-1) 25 (- )
+ 30 ( ) + 30 ( )
Answer: (Zj) 900 25 30 -45 2 45 -2
Row

New (Cj - Zj) row:

Qty x y S1 S2 A1 A2
Cj - Zj 25 - 25 30 – 30 0 – (-45) 0–2 100 - 45 100 – (-2)
Answer: 0 0 45 -2 55 102
(Cj - Zj) row

Solution in Fourth Tableau:

Qty x y S1 S2 A1 A2
NPR (x)
= P.R. ÷
P.E. 30÷ 1÷ 0÷ -3 ÷ ÷ 3÷ - ÷
Answer: 150 5 0 -15 1 15 -1
(x)

New y = Old y + (-)(- ) (NPRtable 3)

New y row Qty x y S1 S2 A1 A2

=Old y + (-)(- ))
(NPRtable 3)
Old y 5 0 1 1 -1

+ (-)(- ) (NPRtable 3) +( )150 +( )5 +( )0 +( )(-15) +( +( +( )

)(1) )(15) (- 1)
Answer: (y) Row 20 1 0 0

IT 305: QUANTITATIVE METHODS 73

 UNIT 2: Linear Programming

New Zj row:

New Zj row = Qty x y S1 S2 A1 A2

(Cj * QtyA1) +
(Cj * Qtyy)
Cj * QtyA1) + 0(150) 0(5) 0(0) + 0(15) + 0(1) + 30(0) 0(15) + 0(-1) +
(Cj * Qtyy) + 30(20) 30(1) 30(0) 30 (0)
+ 30 ( ) 30 ( )
Answer: (Zj) 15 30 -15 0 15 0
600
Row

New (Cj - Zj) row:

Qty x y S1 S2 A1 A2
Cj - Zj 25 - 15 30 – 30 0 – (-15) 0 –0 100 - 15 100 – 0
Answer: 10 0 15 0 85 100
(Cj - Zj) row

IT 305: QUANTITATIVE METHODS 74

 HOW DO YOU APPLY
UNIT 2: Linear Programming
APPLICATION ACTIVITY FOR LESSON 4

WHAT YOU HAVE LEARNED?

Name: Date:
Course & Section: Result:

Answer the following briefly:

1. Explain the simplex procedure to solve the Linear Programming Problem.

2. How do you recognize optimality in the simplex method?

IT 305: QUANTITATIVE METHODS 75

 HOW DO YOU APPLY
UNIT 2: Linear Programming
APPLICATION ACTIVITY FOR LESSON 4

WHAT HAVE YOU LEARNED?

Name: Date:
Course & Section: Result:

3. Explain the term 'Artificial' variables briefly.

4. Explain the use of artificial variables in LP.

IT 305: QUANTITATIVE METHODS 76

 HOW DO YOU APPLY
APPLICATION
UNIT 2: Linear Programming ACTIVITY FOR LESSON 4

WHAT HAVE YOU LEARNED?

Name: Date:
Course & Section: Result:

Completely solve the following by Simplex Method:

1. Maximize P =5X + 3Y
Subject to
X + Y  25
X + 2Y  10
3X + 8Y 
12 X, Y  0

IT 305: QUANTITATIVE METHODS 77

 HOW DO YOU APPLY
UNIT 2: Linear Programming
APPLICATION ACTIVITY FOR LESSON 4

WHAT HAVE YOU LEARNED?

Name: Date:
Course & Section: Result:

2. Minimize C = - X - 2Y
Subject to
-X + 3Y 
10 X + Y 
6
X- Y 2
X, Y  0

IT 305: QUANTITATIVE METHODS 78

 HOW DO YOU EXTEND YOUR
LEARNING?
UNIT 2: Linear Programming

ASSIGNMENT/ LEARNING INSIGHT/REFLECTION

Name: Date:
Course & Section: Result:

Share your insights on the importance of Linear Programming Techniques in

business and industry.

IT 305: QUANTITATIVE METHODS 79

 HOW MUCH HAVE YOU
UNIT 2:POST - TEST
Linear Programming

LEARNED?

Name: Date:
Course & Section: Result:

Find out how much you know about this module. Choose the letter that
corresponds to your answer.

1. Linear Programming is a
a. Constrained optimization c. Technique for economic
technique allocation of limited resources
b. Mathematical technique c. All of the above
d.
2. A constraint in linear programming model restricts
a. Value of a decision variable c. Use of the available resources
b. Value of an objective function e. All of the above
f.
3. Constraints of a linear programming model represent
a. limitations c. Balancing limitations and
requirements
b. requirements d. All of the above

4. How many decision variables can be used in a graphical method?

a. 4 c. 2
b. 3 d. 1

5. What is the area bounded by the constraints?

a. a. feasible region c. key region
b. pivot region d. none of the above

IT 305: QUANTITATIVE METHODS 80

UNIT 2: Linear Programming

6. What is another term for key element common to the incoming and outgoing
vector in simplex method?
a. slack c. pivotal
b. surplus d. Artificial

7. What variable represents the amount by which solution value exceeds a

resource?
a. slack c. artificial
b. surplus d. None of the above

8. What variable represents unused resources and is added to original objective

function with zero coefficients?
a. slack c. artificial
b. Surplus d. None of the above

9. If the given problem is maximization, Zmax then locate the solution point
at the...........point of the feasible zone from the origin

a. far most c. near

b. left most d. none of the above

10. Solve the following LPP problem using simplex method.

Maximize P = 7x1 + 5x2
Subject to:
x1 + x2  64
x1 + 3x 2 12
x1, x2  0

a. P = 20 c. P = 22
b. P = 21 d. P = 23

IT 305: QUANTITATIVE METHODS 81

 RUBRIC
UNIT 2: Linear Programming

FOR
ASSESSM
Rubric (Problem Solving Activity)

Criteria & Very Needs

Excellent Satisfactory Poor Score
Rating Satisfactory Improvement
Approach Valid approach Valid approach Invalid approach Little or no 10
chosen is with minor with multiple that understanding of
clearly shown, errors that don’t errors that demonstrates how to approach
Strategic clearly disrupt impede little the problem.
Approach written & all understanding. understanding. understanding (1)
elements are (7-8) (5-6) of the problem.
valid. (2-4)
(9-10)
Appropriate Appropriate Appropriate At least one Little or no 10
concepts that concepts that concepts concept understanding of
Quantitative
are fully are mostly identified, but identified but Quantitative
Method
understood understood but not employed unable to Method
Concepts
, clearly stated employed with or understood. demonstrate concepts.
& employed errors. (5-6) understanding. (1)
correctly. (7-8) (2-4)
(9-10)
Correct starting Correct starting Correct starting Can identify at Incorrect 15
equations; All equations. equations. The least one equations;
mathematical All mathematical mathematical equation, but demonstrates
steps steps are clearly steps are hard unable to apply little
are clearly shown but minor to follow them. or no
shown and they errors yield and errors (3-6) understanding of
flow easily wrong answer. begin to mathematical
toward the OR impede concepts
Mathematical
correct answer. Correct starting application. involved.
Concepts
(13-15 ) equations with (7-9) (1-2)
correct final
result but
the
mathematical
steps are hard
to follow.
(10-12)
100% correct Correct answer Incorrect Unable to reach No answer. 15
answer analytically, but answer, but on a correct (0)
– analytically not numerically. the right path. answer on this
Answer
numerically (10-14) (7-9 pts.) path.
conceptually (1-6 pts.)
(15 )
TOTAL 50

IT 305: QUANTITATIVE METHODS 82