Chapter 3

Linear
Programming:
Simplex Method
By:
Jessabel Daruca
Dianne Pearl Delfin
Ma. Gilyn Besana
Shirly Calubia
Chapter Outline:

3.1 Basic Concepts

3.2 Standard Linear Programming Model: Maximization Problem
3.3 Standard Linear Programming Model: Minimization Problem
3.4 Non-standard Linear Programming Model
3.5 Special Cases In Linear Programming Problems
3.1 Basic Concepts
The simplex method requires that all constraints be
expressed as equations. Mathematically, it is easier to
solve system of linear equations than systems of
inequalities. Therefore, all the inequalities shall be
converted into equations or in the standard form of linear
programming problem.

Simplex method – is an iterative technique that

begins with a feasible solution that is not optimal, but
serves as a starting point.
With the use of algebraic manipulation, the solution is improved
until no further improvement is possible. It is more convenient to
solve linear programming models in simplex method with more
two unknown variables because geometrically it is difficult to
graph.

The idea of the simplex method is to start at the corner

where all the unknowns are 0 and then walk around the resign
from one corner to another the value of the objective function
always increases (for maximization) and always decreases (for
minimization) until the best corner is determined.
A. General Linear Programming Model
A linear programming problem in n unknowns 𝑋1 , 𝑋2 , 𝑋3 ,…, 𝑋𝑛
is one which we are to determine the maximum or the minimum
value of the objective function.

A1x1 + a2 x2 + a3 x3 + …+ an xn ,
Where a1 , a2 , a3 ,… an are constants,
Subject to a linear constraints of the form
B1x1 + b2 X2 + b3 X3 + …+ bn xn < c or
B1 X1 + b2 X2 + b3 X3 + …+ bn xn > c or
B1 X1 + b2 X2 + b3 X3 + …+ bn xn = c
Where b1 , b2 , b3 ,…, bn and c are numbers.
B. Standard Linear Programming Maximization Model

A standard linear programming maximization model are

required to maximize an objective function of the form.

MAXIMIZE: P = a1X1 + a2X2 + a3X3 + …+ anXn

SUBJECT TO:
b1X1 + b2X2 + b3X3 +…+ bnXn < C structural constraints X1 > 0,
X2 > 0, X3 > 0, …, Xn > 0 non-negativity constraints Where c >
0 and the inequality in the structural constraints is strictly “<“.
C. Standard Linear Programming Minimization Model

A standard linear programming minimization model are

required to minimize an objective function of the form.

MINIMIZE: C = a1 X1 + a2 X2 + a3 X3 + …+ an Xn
SUBJECT TO:
b1 X1 + b2 X2 + b3 X3 +…+ bn Xn > c ----- structural constraints
X1 > 0, X2 > 0, X3 > 0, …, Xn > 0 ----- non-negativity constraints
Where c > 0 and the inequality in the structural constraints is
strictly “>”.
3.2 Standard Linear Programming Model:
Maximization Problem
The maximality test will note an optimal solution if and only if
the last row of a simplex tableau, corresponding to the objective
function, no negative entries.

Steps In Solving Standard Lp Maximization Model

Using Simplex Method

1. Set up problem in an LP model.

2. Introduce the necessary slack variables.
3. Establish the initial tableau.
4. Examine the simplex tableau for optimal solutions. If the
basic feasible solution is maximal, the problem is solved.
Otherwise, proceed to step 5.
5. Compute a new simplex tableau: select the pivot column, find
pivot row, and pivot about the pivot entry.
6. Proceed to step 4.
Example 1:

A local boutique produced two designs of gowns A and B and

has the following materials available: 18 square meters of cotton,
20 square meters of silk, and 5 square meters of wool. Design A
requires the following: 3 square meters of cotton, 2 square meters
of silk and 1 square meter of wool. Design B requires the following:
2 square meters of cotton , 4 square meters of silk. If Design A
sells for 1,200 and Design B for 1,600, how many of each garment
should the boutique produce to obtain the maximum amount of
money?
Solution:
In order to solve a standard linear programming
maximization model using simplex method it is necessary to follow
the steps.
Step 1: Represent the unknown in the problem.
Let X1 be the number of Design A gowns, and
X2 be the number of Design B gowns.
Step 2: Tabulate the data about the facts (if necessary).
Materials Design A (X1 ) Design B (X2 ) Available
Cotton 3 2 18
Silk 2 4 20
Wood 1 0 5
Profit P 1,200 P 1,600
Step 3: Formulate the objective function and constraints by
restating the information in mathematical form.
The objective function is:
Maximize: P = 1,200X1+ 1,600X2
The constraints are:
3X1+ 2X2 < 18 Cotton
2X1+ 4X2 < 20 Silk Structural Constraints
X1 < 5 Wool
X1 > 0, X2 > 0 Non-negativity Constraints
Step 4: Convert to a system of linear equations. Take note that
3X1+2X2 < 18 are less convenient than equations. We have to
add a slack variable denoted by Sn > 0. This is known as standard
form, it is a way of expressing the constraints of a Linear
Programming problem as equalities with all variables on the left
side of the equation and a constant on the right side . Thus, we
can say that slack variables are variables added to constraints to
convert them into equations.
Let Sn represents the slack variables .
3X1+ 2X2 + S1 =18 1st Constraint
2X1 + 4X2 + S2 = 20 2nd Constraint
X1 + S3 = 5 3rd Constraint
-1,200X1 -1,600X2 +P=0, Objective Function
Step 5: Set up the initial tableau.
Tableau 1
BV X1 X2 S1 S2 S3 P RHS
S1 3 2 1 0 0 0 18
1st Constraint
S2 2 4 0 1 0 0 20 2nd Constraint
S3 1 0 0 0 1 0 5 3rd Constraint
P -1,200 -1,600 0 0 0 1 0 Objective Function
Step 6: Select the pivot column. (It is the column that contains the
most negative entry in the bottom row). In this example it is the
column of X1 which contains -1,600.
BV X1 X2 S1 S2 S3 P RHS
S1 3 2 1 0 0 0 18
S2 2 4 0 1 0 0 20
S3 1 0 0 0 1 0 5
P -1,200 -1,600 0 0 0 1 0

Pivot Column
 Iteration is a simplex method which consist of the sequence
of steps (row operations) performed in moving one basic feasible
solution to another. Simplex Tableau is a table use to keep track
of the calculations made when the simplex method is employed.
Right-Hand-Side (RHS) is the column in a simplex tableau
indicating the quantities of the variables is in a solution. Basic
Variables (BV) are the variable included in a basic solution.
Pivot Column is the column in any solution to a
maximization problem which has the lowest negative value in the
last row. Intersectional Elements are elements common to both
the pivot column and the rows representing variables in the
solution.
 Pivot Row is the row in the simplex tableau corresponding
to the basic variables that will leave the solution. It is determined
by the test ratio and it is being computed by dividing the right-
hand-side (RHS) by the intersectional elements (IE).

Pivot is the element of the simplex tableau that is in both

the pivot row and the pivot column. The test ratio result always
be a positive number (meaning negative number and infinity
cannot be chosen as pivot row). After applying the test ratio
choose the smallest positive. In cases, that two or more
candidates choose any one. This process of going from one
simplex tableau to the next is called pivoting.
Step 7: Identify the pivot row using the test ratio by dividing the
RHS values by the non-zero and non-negative entries in the pivot
column (or intersectional element).
The second row of the constraints coefficient has the smallest
positive quotient, which is 5; second row will be the pivot row.
Tableau 1 Pivot Row
BV X1 X2 S1 S2 S3 P RHS Test ratio
S1 3 2 1 0 0 0 18 18/2=9
S2 2 4 0 1 0 0 20 20/4=
S3 1 0 0 0 1 0 5 5/0= not
permissible
P -1,200 -1,600 0 0 0 1 0
Tableau 1
BV X1 X2 S1 S2 S3 P RHS

S1 3 2 1 0 0 0 18
S2 2 0 1 0 0 20
S3 1 0 0 0 1 0 5
P -1,200 -1,600 0 0 0 1 0

Pivot
Other parts of the simplex table are:
Entering variable
Tableau 1 Leaving variable

BV X1 X2 S1 S2 S3 P RHS
S1 3 1 0 0 0 18
2 0 1 0 0 20
S3 1 0 0 1 0 5
P -1,200 -1,600 0 0 0 1 0

Intersectional Elements
Then initiate the following steps.
Tableau 1

BV X1 X2 S1 S2 S3 P RHS
S1 3 2 1 0 0 0 18 R11
S2 2 4 0 1 0 0 20 R21
S3 1 0 0 0 1 0 5 R31
P -1,200 -1,600 0 0 0 1 0 R41
Before we start with the computation for the solution, let us be
aware of the following: Tableau
number
Tableau number
Rnm Pnm

Replacing/ Row
Remaining Number Row
row Number
Pivot
Step 8:Compute the values of the replacing row by dividing all the
entries by the pivot 4.
Replacing Row = Pivot Row/ Pivot
R22 = R21 / P21 = (2, 4, 0, 1, 0, 0, 20) /4= ( ½ , 1, 0, ¼, 0, 0, 5)
Step 9:Compute the new values for the remaining rows using the
formula.
Remaining Row = Previous Row – (Intersectional Element x
Replacing Row)
R12 = R11 – 2R22 = (3, 2, 1, 0, 0, 0, 18) – (2)( ½, 1, 0, ¼, 0, 0, 5)
= (3, 2, 1, 0, 0, 0, 18) – (1, 2, 0, ½, 0, 0, 10) = (2, 0, 1,- ½, 0, 0, 8)
R32= R31 – 0R22 = (1, 0, 0, 0, 1, 0, 5) – (0) ( ½, 1, 0, ¼, 0, 0, 5)
= (1, 0, 0, 0, 1, 0, 5) – (0, 0, 0, 0, 0, 0, 0) = (1, 0, 0, 0, 1, 0, 5)
R42 = R41 + 1600 R22 = (-1200, -1600, 0, 0, 0, 1, 0) + (1600)( ½, 1,
0, ¼, 0, 0, 5)
= (-1200, -1600, 0, 0, 0, 1, 0) + (800, 1600, 0, 400, 0, 0, 8000) =
(-400, 0, 0, 400, 0, 1, 8000)
Enter the results in Tableau 2.
Tableau 2 BV X1 X2 S1 S2 S3 P RHS
S1 2 0 1 -½ 0 0 8
R12
X2Note; The pivot
½ entry transforms
1 to 1 and0all other entries
¼in the pivot0column transform
0 to 0’s. 5
R22
S3 1 0 0 0 1 0 R32
5
P -400 0 0 400 0 1 8,000 R42

Note: The pivot entry transform to 1 and all other

entries in the pivot column transform to 0’s.
Return to Step 6, since the last row still contains a negative
entry.

Step 6-7: Select the pivot column , identify the pivot row and the
pivot of Tableau 2.
Tableau 2 BV X1 X2 S1 S2 S3 P RHS Test ratio
S1 2 0 1 -½ 0 0 8 8÷2=4
X2 ½ 1 0 ¼ 0 0 5 5÷½ =10
S3 1 0 0 0 1 0 5 5÷1=5
P -400 0 0 400 0 1 8,000
Step 8-9: Compute for replacing row and the remaining rows of
Tableau 3.

Tableau 2
BV X1 X2 S1 S2 S3 P RHS
S1 2 0 1 -½ 0 0 8
R12
X2 ½ 1 0 ¼ 0 0 5 R22
S3 1 0 0 0 1 0 5 R32
R 2
P -400 0 0 400 0 1 8,000 4
Replacing Row = Pivot Row Pivot

R13=R12/P12= (2,0,1,-1Τ2,0,0,8) 2 = (1,0,1Τ2,-1Τ4,0,0,4)

Remaining Row = Previous Row – (Intersectional Element x
Replacing Row)
R23 = R22-1Τ2R13 = (1Τ2 ,1,0,1Τ4,0,0,5) – (1Τ2) (1,0,1Τ2, -1Τ4,0,0,4)
=(1Τ2, 1, 0,1Τ4 ,0,0,5) – (1Τ2,0,1Τ4,−1Τ80,0,2)=(0,1,-1Τ4,3Τ8,0,0,3)
R33= R32-1R13= (1,0,0,0,1,0,5)-(1)(1,0,1/2,-1/4,0,0,4)
= (1,0,0,0,1,0,5)-(1,0,1/2,-1/4,0,0,4) = (0,0,-1/2,1/4,1,0,1)
R43 = R42+ 400R13=(-400,0,0,400,0,1,8000)+(400)(1,0,1/2,-
1/4,0,0,4)
=(-400,0,0,400,0,1,8000)+(400,0,200,-100,0,0,1600)
=(0,0,200,300,0,1,9600)
 BV X1 X2 S1 S2 S3 P RHS

S1 1 0 ½ -1/4 0 0 4 R13
X2 0 1 -1/4 3/8 0 0 3 R23
S3 0 0 -1/2 ¼ 1 0 1 R33
R 3
P 0 0 200 300 0 1 9,600 4

Notice that there are no negative entries in the last row, thus, the
tableau is already optimal.
Step 10: The decision is to make Tableau 3
Tableau 3
BV X1 X2 S1 S2 S3 P RHS
S1 1 0 ½ -1/4 0 0 4
X2 0 1 -1/4 3/8 0 0 3
S3 0 0 -1/2 ¼ 1 0 1
P 0 0 200 300 0 1 9,600

Decision
X1 = 4 Design A gowns S1 = 0
X2 = 3 Design B gowns S2 = 0
P = P9,600 profit S3 = 1
Example 2:
Ecomoda, a clothing line manufacturer that produces men’s
shirts and pants, has two (2) primary resources available, sewing
machine time (in the sewing department) and cutting machine ( in
the cutting department). Over the next week, Ecomoda can
schedule up tp 24 hours of work in the sewing department and 30
hours of work in the cutting department. Each shirt produced
requires one (1) hour of sewing machine time and 2 hours of
cutting machine time. Producing each pair of pants requires two
(2) hours of sewing machine time and 1 hour of cutting machine
time. If profit is 30 pesos per shirt and 40 pesos per pant,
determine the best possible combination of shirts and pants to
produce and sell in order to realize the maximum profit.
Manufacturing Problem Information:

Hours required for 1 unit of

product
Total Hours
Department
Available
Shirt (x) Pants
(y)
Sewing 1 2 24
Department
Cutting 2 1 30
Department
Profit per Unit 30 40
To maximize: z = 30x + 40y
Subject to:
X + 2y < 24
2x + y < 30
x, y > 0

Add a slack variable for every constraint.

Hence:
To maximize: z = 30x + 40y + 0S1 + 0S2
X + 2y + S1 = 24
2x + y + S2 = 30
 𝑪𝒋 30 40 0 0
PM Qty x y S1 S2
0 S1 24 1 2 1 0 (PR)
0 S2 30 2 1 0 1
0 0 0 0 0
𝒁𝒋 0 0 0 0 0
𝑪𝒋 - 𝒁𝒋 30 40 0 0
 𝑪𝒋 30 40 0 0
PM Qty x Y S1 S2
40 Y 12 ½ 1 ½ 0
0 S2 18 1½ 0 -½ 1 (PR)
𝒁𝒋 480 20 40 20 0
𝑪𝒋 - 𝒁𝒋 10 0 -20 0
 𝑪𝒋 30 40 0 0
PM Qty x y S1 S2
40 Y 6 0 1 2ൗ −1ൗ
3 3
30 x 12 1 0 −1ൗ 2ൗ
3 3
𝒁𝒋 600 30 40 16.67 6.67
𝑪𝒋 - 𝒁𝒋 0 0 -16.67 -6.67
The optimum solution is:
x = 12 shirts
y = 6 pants
z = 600
3.3 Standard Linear Programming Model:
Minimization Problem
We will use the same example presented in Chapter 2. The
steps below will guide us in solving standard linear programming
minimization problem.
Steps in solving Standard LP Minimization Model using
Simplex Method
1. Set up problem in an LP Model.
2. Introduce the necessary surplus variables.
3. Establish the initial tableau and put a star in all rows that give a
negative for the associated basic variable.
4. Start with the first starred row and apply the test ratio.
5. Repeat step 4 until no starred row remains.
6. If there are any negative entries in last row (except in the
RHS column), apply standard maximality test.
Example 1:

A Drug Company produces a drug from two ingredients.

Each ingredient contains the same three antibiotics in different
proportions. Each ingredient A produced results Ᵽ80 in cost;
each ingredient B results 50 in cost. The production of the
antibiotics is dependent on the availability of limited resources.
The resource requirements for the production are as follows.

Antibiotic Resources Requirement Minimum

Requirement
Ingredient A Ingredient B
Antibiotic 1 3 units 1 unit 6
Antibiotic 2 1 unit 1 unit 4
Antibiotic 3 2 units 6 units 12
The company wants to determine the quantity of each ingredient
A and B that must go in to drug in order to meet the antibiotics
minimum requirements at the minimum cost.

Solution:
In order to solve the problem it is necessary to formulates
first the standard form of the model.
Step 1: Represent the unknown in the problem.
Let X1 be the quantity of ingredient A, and
Let X2 be the quantity B.
Step 2: Tabulate the data about the facts (if necessary).

Materials Ingredients A (X1) Ingredient B (X2) Requirement

Antibiotic 1 3 1 6
Antibiotic 2 1 1 4
Antibiotic 3 2 6 12
Cost Ᵽ80 Ᵽ50

Step 3: Formulate the objective function and constraints by

restating the information in mathematical form.
The objective function is:
Minimize: C = 80X1 + 50X2
The constraints are:
3X1 + X2 ≥ 6 Antibiotic 1
X1 + X2 ≥ 4 Antibiotic 2
2X1 + 6X2 ≥ 12 Antibiotic 3
X1 , X2 ≥ 0

We need to convert first the minimization problem into

maximization problem. Minimizing C is the same as maximizing
P= -C. Thus, C= 80X1 + 50X2 is now replaced by P= -80X1 - 50X2.
Now our LP model would be
Maximize: P = -30X1 - 50X2
3X1 + X2 ≥ 6 , X1 + X2 ≥ 4 , 2X1 + 6X2 ≥ 12 , X1 , X2 ≥ 0
Step 4: Convert to a system of linear equations. Take note that
3X1 + X2 ≥ 6 are less convenient than equations. We have to
subtract a surplus variable denoted by. Thus , we can say that
surplus variable are variables subtracted to constraints to
convert them into equations.

Let Sn represents the surplus variables.

3X1 + X 2 - S = 6 1st Constraint

X1 – X2 - S = 4 2nd Constraints
2X1 – 6X2 – S = 12 3rd Constraints
80X1 + 50X2+ P = 0 Objective Function
Step 5: Set up the initial tableau.

Tableau 1

1 1

3 1 -1 0 0 0 6 1st Constraint

1 1 0 -1 0 0 4 2nd Constraints

2 6 0 0 -1 0 12 3rd Constraints

80 50 0 0 0 1 0 Objective Function
Step 6: Select the pivot column. (It is the column that
contains the most positive entry in the bottom row.) In this
example it is the column of X1 which contains 80.
1 1

3 1 -1 0 0 0 6

1 1 0 -1 0 0 4

2 6 0 0 -1 0 12

80 50 0 0 0 1 0
Step 7: Identify the pivot row using the test ratio by dividing the
RHS values by the non-zero and non-negative entries in the
pivot column.
Tableau 1
Test
BV X1 X2 S1 S2 S3 P RHS
ratio
*S1 5 1 -1 0 0 0 6 6÷3=2
*S2 1 1 0 -1 0 0 4 4÷1 =4
*S3 2 6 0 0 -1 0 12 12÷2=6
P 80 50 0 0 0 1 0
 Tableau 2

1 1

3 1 -1 0 0 0 6 R11

1 1 0 -1 0 0 4 R21

2 6 0 0 -1 0 12 R31

80 50 0 0 0 1 0 R41
Step 8: Compute the values of the replacing row
and the remaining rows.
Tableau 2
BV X1 X2 S1 S2 S3 P RHS Computation

*S1 1 1ൗ -1Τ3 0 0 0 2 R12 =R12 + P11

3

*S2 0 2ൗ 1ൗ -1 0 0 2 R22 =R21 – 1R12

3 3

*S3 0 51Τ3 2ൗ 0 -1 0 8 R32 =R31 – 2R12

3

P 0 231Τ3 262Τ3 0 0 1 -160 R42 =R41 – 80R12

Return to Step 6, since there are still starred rows.

Step 6-7: Select the pivot column, identify the pivot row and the
pivot of Tableau 2.
Tableau 2
BV X1 X2 S1 S2 S3 P RHS Test ratio
*S1 1 1ൗ -1Τ3 0 0 0 2 2 ÷ 1Τ3 = 6
3
*S2 0 2ൗ 1ൗ -1 0 0 2 2 ÷ 2Τ3 = 3
3 3
*S3 0 51Τ3 2ൗ 0 -1 0 8 8 ÷ 51Τ3 = 1.5
3
P 0 231Τ3 262Τ3 0 0 1 -160
Step 8-9: Compute for replacing row and the remaining rows of
Tableau 3.
BV X1 X2 S1 S2 S3 P RHS Computation

*S1 1 0 -3Τ8 0 1ൗ 0 1 1Τ2 R13=R12 - 1Τ3R33

16
*S2 0 0 1ൗ -1 0 1 R23=R22 - 2Τ3R33
4
1ൗ - 1
*S3 0 1 8 0 3Τ
0 1Τ
R33=R32 ÷ P32
16 2

4
P 0 0 233Τ4 0 3Τ
1 -195 R43=R42 - 251Τ3R33
8
Return to Step 6, since there are still starred rows.
Step 6-7: Select the pivot column, identify the pivot row
and the pivot of Tableau 2.
Tableau 3
BV X1 X2 S1 S2 S3 P RHS Test ratio

*S1 1 0 -3Τ8 0 1ൗ 0 1 1Τ2 1 1Τ2 ÷ 1Τ16 = 24

16
*S2 0 0 1ൗ -1 0 1 1 ÷ 1Τ8 = 8
4
*S3 0 1 1ൗ 0 -3Τ16 0 1 1Τ2 1 1Τ2 ÷ ( 3Τ16) = -8
8
P 0 0 233Τ4 0 4 3Τ8 1 -195
Step 8-9: Compute for replacing row and the remaining rows of
Tableau 4.

BV X1 X2 S1 S2 S3 P RHS Computation

*S1 1 0 -1Τ2 1ൗ 0 0 1 R14=R13 - 1Τ16R24

2
*S2 0 0 2 -8 1 0 8 R24=R23 ÷P23

1ൗ -1
*S3 0 1 2 1Τ
0 0 3 R34=R33 ÷ 3Τ16R24
2

P 0 0 15 35 0 1 -230 R44=R43 - 3Τ8R24

Notice that there are no starred entries in the basic solutions,
thus, the tableau is already optimal. Also , optimal solution was
triggered by non-existence of negative entries in the objective
function except for the RHS column.

Step 10: Make a decision.

Decision:
X1 = 1 Unit of ingredient 1 S1= 0
X2 = 3 Units of ingredient 2 S2= 0
C = P230 cost S3= 8
Example 2:

A manufacturer of commercial chemicals has an order for a

certain mixture consisting of 2 ingredients, x and y which cost 4
pesos and 5 pesos per kilo, respectively. The following are the
specifications: a) the weight of the mixture must be 100 kilos, b) it
cannot contain mire than 30 kilos of x, and c) it must contain at least
20 kilos of y. Find the mixture of the two ingredients, which satisfies
the customers’ requirements and still yield a minimum total cost of
raw materials.
Minimize: C = 4x + 5y
Subject to:
x + y = 100; x + y + 𝐴1 = 100
x < 30 x + 𝑆1 = 30
y > 20 y - 𝑆2 + 𝐴2 = 20
x, y > 0

Note: For the cost of 𝐴1 and 𝐴2 , use values in multiplies of 10

e.g 10, 100, 1000 depending on the highest cost of x and y.
here the highest cost is 5 pesos, then use 10 pesos.
 First Table

𝑪𝒋 4 5 0 0 10 10
PM Qty x y 𝑆1 𝑆2 𝐴1 𝐴2
10 𝐴1 100 1 1 0 0 1 0
0 𝑆1 30 1 0 1 0 0 0
10 𝐴2 20 0 1 0 -1 0 1 (PR)
𝒁𝒋 1200 10 20 0 -10 10 10
𝑪𝒋 - 𝒁𝒋 -6 -15 0 10 0 0
 Second Table

𝑪𝒋 4 5 0 0 10 10
PM Qty x y 𝑆1 𝑆2 𝐴1 𝐴2
10 𝐴1 80 1 0 0 1 1 -1
0 𝑆1 30 1 0 1 0 0 0 (PR)
5 y 20 0 1 0 -1 0 1
𝒁𝒋 900 10 5 0 5 10 -5
𝑪𝒋 - 𝒁𝒋 -6 0 0 -5 0 15
 Third Table

𝑪𝒋 4 5 0 0 10 10

PM Qty x Y 𝑆1 𝑆2 𝐴1 𝐴2
10 𝐴1 50 0 0 -1 1 1 -1 (PR)
4 x 30 1 0 1 0 0 0
5 y 20 0 1 0 -1 0 1
𝒁𝒋 720 4 5 -6 5 10 -5

𝑪𝒋 - 𝒁𝒋 0 0 6 -5 0 15
 Fourth Table
𝑪𝒋 4 5 0 0 10 10
PM Qty x Y 𝑆1 𝑆2 𝐴1 𝐴2
10 S1 50 0 0 -1 1 1 -1
4 x 30 1 0 1 0 0 0
5 y 70 0 1 -1 0 1 0
𝒁𝒋 470 4 5 -1 0 5 0
𝑪𝒋 - 𝒁𝒋 0 0 1 0 5 10
Decision: x = 30 y = 70 Cost = P470
3.4 Non-Standard Linear Programming Model

In this section we will going to examine non-standard

linear programming model both in maximization. Non-standard
linear programming model contains constraints like 2X1 + 3X2 ≥
6 or perhaps 2X1 + 3X2 = 6 for maximization problems and 2X1 +
3X2 ≥ 6 or perhaps 2X1 + 3X2 = 6 for minimization problems.
There is a slight modification of the Simplex method involving
this type of problems.
The best way to illustrate it is by means of examples. We
will begin with maximization problems.
Example 1:
Maximize: P = 4X1 + 3X2
Subject to: 2 X1 + X2 ≥ 16
2X1 + 3X2 ≥ 36
4X1 + 5X2 ≥ 28
X1 ≥ 0, X2≥ 0
Solution:
Step 1: Convert to a system of linear equation. Take note that
4X1+ 5X2 ≥ 28 are less convenient than equations. We have to
subtract a surplus variable to convert them into equations.
P = 4X1 + 3X2
Subject to: 2 X1 + X2 –S1 = 16
2X1 + 3X2 +S2 = 36
4X1 + 5X2 -S3 = 28
-4X1 - 3X2 +P = 0
Step 2: Set up the initial tableau.
Step 3: Select the pivot column, identify the pivot row and the
pivot of Tableau 1.
BV X1 X2 S1 S2 S3 P RHS Test ratio
R11
S1 2 1 1 0 0 0 16 16 ÷ 2 = 8
R21
S2 2 3 0 1 0 0 36 36÷2 = 18

*S3 4 5 0 0 -1 0 28 28÷4 = 7 R31

P -4 -3 0 0 0 1 0 R41
Step 4: Compute for replacing row and the remaining rows of
tableau 2. Return to Step 3, since the last row still contains a
negative entry.

Step 3: Select the pivot column, identifying the pivot row and
the pivot of Tableau 2.
 Tableau 2

BV X1 X2 S1 S2 S3 P RHS Computation Test Ratio

S1 0 1 1Τ2 1 0 1ൗ 0 2 R12=R11 - 2R32 2÷ 1Τ2=4

2

1ൗ 1ൗ R22=R21 - 2R32
S2 0 2 0 1 2 0 22 22÷ 1Τ2=44

11Τ4
X1 1 0 0 -1Τ4 0 7 R32=R31 ÷P31 7÷(-1Τ4)=28

F 0 2 0 0 -1 1 28 R42=R41 +4R32
Step 4: Compute for replacing row and the remaining rows
of Tableau 3. Return to step 3, since the last row and the
remaining row still contains a negative entry.

Step 3: Select the pivot column, identify the pivot row and
the pivot of tableau 3.
 Tableau 3
BV S1 P RHS Computation Test Ratio
X1 X2 S2 S3

0 -3 2 0 1 0 4 R13=R12÷P12 4÷(-3)=-11Τ3
S3

0 2 -1 1 0 0 20 R23=R22- 1Τ2 R 20÷2=10

S2 3
1
1 1ൗ 1ൗ 0 0 0 8 R33=R32+ 8÷ 1Τ2 =16
X1 2 2 1Τ R 3
4 1

0 -1 2 0 0 1 32 R42=R42+1R13
P
Step 4: Compute for replacing row and the remaining rows of
Tableau 4.
Since the last row does not contain negative entries, thus, the
tableau is already optimal.
Tableau 4
BV X1 X2 S1 S2 S3 P RHS Computation

S3 0 0 1ൗ 1 1Τ2 1 0 34 R14=R13+3R24
2
S2 0 1 −1ൗ 1ൗ 0 0 10 R24=R23÷P 23
2 2
X1 1 0 3ൗ − 1ൗ 0 0 3 R34=R33+ 1Τ2 R 4
4 4
P 0 0 1 1Τ2 1ൗ 0 1 42 R44=R43+1R24
2
Step 5: Make a decision.
Decision: X1= 3; X2=10;P =42;S1= 0; S2= 0; S3= 34
Let us have another example but this time it will include
constraints involving ,=, and in one linear programming problem.
Example 2:
Maximize : P=10 X1+5 X2
Subject to: 2 X1+ X2 < 10
X2=4
X1+4X2 < 20
X1 ≥ 0, X2 ≥ 0
Solution
We first represent X2 =4 by two inequalities X2 ≥ 4 and X2 ≥
4. Thus the new LP model would be.
Maximize: P = 10 X1 + 5 X2
Subject to: 2 X1 + X2 ≥ 10
X2 ≥ 4
X2 ≥ 4
X1 + 4X2 ≥ 20
X1≥ 0, X2 ≥ 0
Step 1: Convert to a system of linear equations. Remember
that we need to subtract a surplus variable to constraints with “
≥“.
Maximize:
Subject to: 2 X1 + X2 - S1 =10
X2 - S2 =4
X2 + S3 =4
X1 + 4X2
-10 X1 -5 X2
Step 2: Set up the initial tableau.
Step 3: Select the pivot column, identify the pivot row and the
pivot of tableau 1.
Tableau 1
BV X1 X2 S1 S2 S3 S4 P RHS Computation
*S1 -2 1 -1 0 0 0 0 10 10 ÷ 2 = 5
*S2 0 1 0 -1 0 0 0 4 4÷0=
S3 0 1 0 0 1 0 0 4 4÷0=
S4 1 4 0 0 0 1 0 20 20 ÷ 1 = 20
P -10 -5 0 0 0 0 1 0
Step 4: Compute for replacing row and the remaining rows of
tableau 2. Return to step 3, since the last row still contains a
negative entry and starred variable in the BV column.

Step 3: Select the pivot column, identify the pivot row and the
pivot of tableau 2.
 Tableau 2

BV X1 X2 S1 S2 S3 S4 P RHS Computation Test ratio

X1 1 1ൗ 1ൗ2- 1Τ2 0 0 0 0 5 R12=R11÷P11 5 ÷ (- 1Τ2) = -10
2
*S2 0 1 0 -1 0 0 0 4 R22=R21+OR 24 4÷0=
S3 0 1 0 0 1 0 0 4 R32=R31-OR 4 4÷0=

S4 0 3 0 0 1 0 15 R42=R41+1R24 15 ÷ 1Τ2 = 30

P 0 0 -5 0 0 0 1 50 R52=R52+10R24
Step 4: Compute for replacing row and the remaining rows of
tableau 3. Return to step 3, since the last row still contains a
negative entry and starred variable in the BV column.

Step 3: Select the pivot column, identify the pivot row and the
pivot of tableau 3.
 Tableau 3
BV X1 X2 S1 S2 S3 S4 P RHS Computation Test ratio
1 4 0 0 0 0 0 20 R13=R12+ 1Τ2R 20 ÷ 4= 5
X1 3
4
0 1 0 -1 0 0 0 4 R23=R22+OR 43 4÷1=4
*S2
4÷1=4
S3 0 1 0 0 1 0 0 4 R33=R33-OR43
0 7 1 0 0 1 0 30 R43=R42÷ R442 30 ÷ 7= 4.2
S4
P 0 35 0 0 0 10 1 200 R53=R52+5R43
Step 4: Compute for replacing row and the remaining rows of
the tableau 4. Since the last row does not contain negative
entries, thus, the tableau I already optimal.

Tableau 4
BV X1 X2 S1 S2 S3 S4 P RHS Computation
X1 1 0 0 4 0 0 0 4 R14=R13-4R24

X2 0 1 0 -1 0 0 0 4 R24=R23÷ P 23
S3 0 0 0 1 1 0 0 0 R34=R33-1R24
S1 0 0 1 -7 0 2 0 2 R44=R43÷ R43-7R24
P 0 0 0 35 0 10 1 60 R54=R53-35R24
Step 5:
Make a decision
Example: minimize C = 9 X1 +3 X2
Subject to: X1+ 2X2 ≤ 12
X1+ X2 ≥ 8
2X1+ 3X2 ≥ 6
X1 ≥ 0, X2 ≥ 0
Solution:

Step 1: Convert to a system of linear equations. Remember that

we need to subtract a surplus variable to constraints with “ ≥ “
- X1+ 2X2 - S1 =-12
X1+ X2 - S2 =8
2X1+ 3X2 - S3 =6
9 X1 +3 X2 +P =C
Step 2: Set up the initial tableau.
Step 3: Select the pivot column, identify the pivot row and the pivot
of Tableau 1.
Tableau 1:
BV X1 X2 S1 S2 S3 P RHS Test ratio

*S1 -1 -2 -1 0 0 0 -12 12 ÷ ( -1) = -12

*S2 1 1 0 0 0 0 8 8 ÷ 1 =8
X1 2 3 0 -1 -1 0 6 6 ÷ 2 =3
P 9 3 0 0 0 1 0

Step 4: Compute for replacing row and the remaining 10ws of tableau
2. Return to step 3, since the last row still contains a positive entry and
starred variables in the basic variable column.
Step 3: Select the pivot column, identify the pivot row and the
pivot of tableau 2.

Tableau 2.

BV X1 X2 S1 S2 S3 P RHS Computation Test Ratio

0 - 1Τ2 -1 0 − 1ൗ 0 -9 R12=R11+1R32 12 ÷ (- 1Τ2) =
*S1 2
18
*S2 0 - 1Τ2 0 -1 1ൗ 0 5 R22=R21-1R 2 5 ÷ 1Τ2 =10
2
X1 1 1 1Τ2 0 0 - 1Τ2 0 3 R32=R31÷ P32 3 ÷ (- 1Τ2) = -63
P 0 -10 1Τ2 0 0 4 1Τ2 1 -27 R42=R41-9R32
Step 4: Compute for replacing row and the remaining rows of
tableau 3. Return to step 3, since the last row still contains a
positive entry and starred variable in the BV column.

Step 3: Select the pivot column, identify the pivot row and the
pivot of tableau 3.
 Tableau 3
BV X1 X2 S1 S2 S3 P RHS Computation Test Ratio
0 -1 -1 -1 0 0 -4 R13=R12+ 1Τ2R223 -4 ÷ (-1 ) =
*S1
4
0 -1 0 -2 1 0 10 R23=R22÷ P22 10 ÷ (-2) = -
S3
5
X1 1 1 0 -1 0 0 8 R33=R32+ 1Τ2 R23 8 ÷ ( -1 ) = -
8
P 0 -6 0 9 0 1 -72 R43=R42-4 1Τ2R23
Step 4: Compute for replacing row and the remaining rows of
tableau 4. Note that all starred variables were already
discarded. Thus we have to repeat step 3 and select the lowest
entry in the objective function row.

Step 3: Select the pivot column, identify the pivot row and the
pivot of tableau 4.
Tableau 4
BV X1 X2 S1 S2 S3 P RHS Computation
S2 0 1 1 1 0 4 R14=R13÷P13 4÷1=4
S3 0 1 2 0 1 18 R24=R23+ 2R14 18 ÷ 1= 18
X1 1 2 1 0 0 12 R34=R33+ 1R14 12 ÷ 2 = 6
P 0 -15 -9 0 0 -108 R44=R43-9R13

Step 4: Compute for replacing row and the remaining rows of

Tableau 4. Since the last row does not contain negative entries,
thus, the tableau is already optimal.
 Tableau 5

BV X1 X2 S1 S2 S3 P RHS Computation
X2 0 1 1 1 0 0 4 R15=R14÷P14
S3 0 0 1 -1 1 0 14 R25=R24-1R15
X1 1 0 -1 -2 0 0 4 R35=R34+ 2R15
P 0 0 6 15 0 1 -48 R45=R44-15R15
A.Multiple Optimal Solution. It is an LP model that has a multiple
optimal solution or more than one optimal solution. It arises if
there is a zero entry in the final tableau where the variable
column is located, this indicates an alternative solution.
Example 1:
Maximize: P = 100X1+200X2
Subject to: 3X1 + 2X2 < 18
2X1 + 4X2 < 20
X1 < 5
X1 ≥ 0, X2 ≥ 0
Solution:
3X1 + 2X2 + S1 = 18
2X1 + 4X2 + S2 = 20
X1 + S3 = 5
100 X1 - 200 X2 +P = 0
 Tableau 1

BV X1 X2 S1 S2 S3 P RHS Computation

S1 3 2 1 0 0 0 18 18 ÷ 2= 9

S2 2 0 1 0 0 20 20÷ 4= 5
S3 1 0 0 0 1 0 5 5 ÷ 0= 6
P -100 -200 0 0 0 1 0
 Tableau 2

BV X1 X2 S1 S2 S3 P RHS Computation

S1 2 0 1 - 1Τ2 0 0 18 R12=R11-2R22

X2 1ൗ 1 0 1ൗ 0 0 5 R22=R21÷P21
2 4
S3 1 0 0 0 1 0 5 R2=R31+ 0R22
P 0 0 0 50 0 1 1000 R42=R41-200R22
 Tableau 2

BV X1 X2 S1 S2 S3 P RHS Computation

S1 2 0 1 - 1Τ2 0 0 18 8 ÷ 2= 9

X2 1ൗ 1 0 1ൗ 0 0 5 5÷ 1Τ2= 10
2 4
S3 1 0 0 0 1 0 5 5 ÷ 1= 5
P 0 0 0 50 0 1 1000
 Tableau 3

BV X1 X2 S1 S2 S3 P RHS Computation

X1 1 0 1ൗ - 1Τ4 0 0 4 R13=R12÷P12
2
X2 0 1 - 1Τ4 3ൗ 0 0 3 R23=R22- 1Τ2 R13
8
S3 0 0 - 1Τ2 1ൗ 1 0 1 R23=R32-1R13
4
P 0 0 0 50 0 1 1000 R23=R42+0R13
B. Infeasibility it is a case where an LP model contain no feasible
solution even though all constrains are being satisfied; that is,
there are no points which satisfy all constraints.
Example 2:

Maximize: P = 2X1+X2
Subject to: 3X1 + 2X2 < 18
X1 ≥ 7
X1 ≥ 0, X1 ≥ 0

Solution:
3X1 + 2X2 + S1 = 18
X1 - S2 =7
-2X1 --X2 +P =0
 Tableau 1

BV X1 X2 S1 S2 P RHS Test ratio

S1 6 2 1 0 0 18 18 ÷ 3 = 6

*S2 1 0 0 -1 0 7 7 ÷ 1 =7

P -2 -1 0 0 1 0
Tableau 2
BV X1 X2 S1 S2 P RHS Computation
X1 1 2ൗ 1ൗ 0 0 6 R12=R11÷P11
3 3
*S2 0 − 2ൗ - 1Τ3 -1 0 1 R22=R22-1R12
3
P 0 1ൗ 2ൗ 0 1 12 R32=R31+2R12
3 3
C. Unbounded solution this is a condition of an LP model when
the objective function of a linear programming problem can be
made infinitely large without violating any of the constraints, it
occurs in maximization problems.
Example 3:

Maximize: P = 2X1+X2
Subject to: X1 ≥ 3
X2 ≥ 6
X1 ≥ 0, X2≥ 0
Solution:
X1 -S1 =18
X2 - S2 =6
-2X1 --X2 +P =0
 Tableau 1

BV X1 X2 S1 S2 P RHS Test ratio

*S1 61 0 -1 0 0 3 3 ÷ 1 = 63

*S2 0 1 0 -1 0 6 6÷ 0=0

P -2 -1 0 0 1 0
 Tableau 2

BV X1 X2 S1 S2 P RHS Test ratio Computation

X1 1 0 -1 0 0 3 3÷0=0 R12=R11-0R22

*S2 0 1 0 -1 0 6 6 ÷ 1 =6 R22=R22-P21

P 0 -1 -2 0 1 6 R32=R31+1R22
 Tableau 3

BV X1 X2 S1 S2 P RHS Test ratio

3 ÷ (-1) = -
X1 1 0 -1 0 0 3
3

S1 0 1 -1 -1 0 6 6÷ 0=

P 0 0 -1 0 1 12
D. Degeneracy (Tie for the Pivot Row).

This is a condition resulting from a tie in the test ratios

determining the replaced row, which produces a basic variable
with a zero value. The presence of degeneracy is theoretically
possible for a simplex algorithm to cycle and never find an
optimal solution but in practice cycling rarely occurs.
Example 4:
Maximize: P = 2X1+3X2
Subject to: 3X1 + 2X2 <12
X2 ≥ 73
X1 + 2X2 < 8
X1 ≥ 0, X2 ≥ 0
Solution:
3X1 + 2X2 + S1 =12
X2 +S2 =3
X1 + 2X2 +S3 =8
-2X1 --3X2 +P =0
 Tableau 1

BV X1 X2 S1 S2 S3 P RHS Test ratio

S1 3 2 1 0 0 0 12 12 ÷ 2= 6

S2 0 1 0 1 0 0 3 3÷ 1= 3

S3 1 2 0 0 1 0 8 8 ÷ 1= 4
P -2 -3 0 0 0 1 0
 Tableau 2

BV X1 X2 S1 S2 S3 P RHS Computation Test ratio

S1 3 0 1 -2 0 0 6 R12=R11-2R22 6÷ 3= 2

X2 20 1 0 1 0 0 3 R22=R21÷P21 3÷0 = 0

S3 1 0 0 -2 1 0 2 R22=R31-2R22 2 ÷ 1= 2
P -2 0 0 3 0 1 9 R22=R41+3R22
 Tableau 3

BV X1 X2 S1 S2 S3 P RHS Computation
X1 1 0 1ൗ −2ൗ 0 0 2 R13=R12÷P12
3 3
X2 0 1 0 1 0 0 3 R23=R22−0R13
S3 0 0 −1Τ -11Τ3 1 0 0 R33=R32-1R13
3

P 0 0 2ൗ 12Τ3 0 1 13 R43=R42+2R13
3
Tableau 3 is already optimal since the last row does not contain
a negative entry. It only needs 3 tableaus if we select the first
row.

Decision: X1 = 2; X2 = 3; P = 13; S1 = 0; S2 = 0; S3 = 0

Let us now examine what will happen if have chosen the third
row to serve as our pivot row in tableau 2.
 Tableau 2

BV X1 X2 S1 S2 S3 P RHS Test Ratio

S1 3 0 1 −2 0 0 6 6÷3=2

X2 0 1 0 1 0 0 3 3÷0=0

S3 1 0 0 -2 1 0 2 2÷1=2

P -2 0 0 3 0 1 9
 Tableau 3
Test
BV X1 X2 S1 S2 S3 P RHS Computation
ratio
S1 0 0 1 4 -3 0 0 R13=R12-3R33 0÷4=0

X2 0 1 0 1 0 0 3 R23=R22−0R33 3÷1=3
2 ÷ (-2) =
X1 1 0 0 -2 1 0 2 R33=R32÷P32
-2
P 0 0 0 -1 2 1 13 R43=R42+2R33
 Tableau 4

BV X1 X2 S1 S2 S3 P RHS Computation

S2 0 0 1ൗ 1 −3ൗ 0 0 R14=R13÷P13
4 4
X2 0 1 −1ൗ 0 3ൗ 0 3 R24=R23− R14
4 4
X1 1 0 1Τ 0 −1ൗ 0 2 R34=R33+2R14
2 2
P 0 0 1ൗ 0 11Τ4 1 13 R44=R43+1R14
4
Tableau 4 is already optimal since the last row does not contain a
negative entry. Choosing the alternative pivot row needs 4
tableaus to reach the optimal solution.

Decision: X1 = 2; X2 = 3; P = 13; S1 = 0; S2 = 0; S3 = 0

A choice in pivot row may require less iteration than the other but
there is no way of determining this beforehand.