Page 1 of 9

Name :
Course and Year :

Subject : Management Science

Class Schedule :
Instructor :

Module 5: Linear Programming – The Simplex

Minimization Method
Intended Learning Outcomes
 Enumerate the steps in solving a minimization problem
 Discuss how to convert constraints to equations
 Discuss how to solve minimization problems with constraints expressed in equality and
inequalities.
 Solve minimization problems through simplex method:

Activity
As we start with this lesson, please answer the question below:
Why is it important to minimize costs?

Analysis
Minimizing costs will basically lead into profit maximization, and the benefit of the
latter has been discussed in the previous module. Furthermore, another good reason why
cost minimization is desirable is the consideration of market demands. When costs are
lower, the entity can also set lower price in the market. Lower price means greater chance
to compete in the market. The basic rule of economics suggests that products of lower
price will call for greater demands in the market. Therefore, the marketability of a product
which would lead to the company’s profitability can be highly dependent on cost
minimization. Thus it is very important to learn techniques on achieving such state. In this
module, we will learn how to minimize cost through linear programming, using the simplex
method.

Abstraction

1. Simplex Minimization Method

a. Although ≥ and = symbols are occasionally used in constraints of maximization
problems, these are more common in minimization problems.
Review:
- In solving maximization problems, it must be remembered that:
- For constraints with ≤, add slack variable and convert to equation
(equal sign)
Maximize:
Constraint: x+y ≤ 100
x+y+Sn=100

- For constraints with = sign, add slack variable (technically it is just

an artificial variable, with zero coefficient, used for the sake of
computation) and retain the equal sign
Maximize:
Constraint: x+y = 100
x+y+Sn=100

- For constraints with ≥, multiply by -1, add slack variable and convert
to equation (equal sign)
Maximize:
Constraint: x+y ≥ 100
-1(x+y≥100)-1
-x – y ≤ -100
-x-y+Sn=-100
 Page 2 of 9

b. Subtraction of slack variables permitted in minimization, but not in

maximization, because if we intent to minimize, it is but logical to subtract, but
if we intent to maximize, it is otherwise.
c. Common sense tells us that to change a constraint with ≥ to equation; we
simply subtract a slack variable from the left member.
d. But in particular case, if other variables are zero, the slack variable will have a
negative value.
e. But the general rule in linear programming is that all variables must be greater
than or equal to zero, hence, there is a need to use another kind of variable
that will save the slack variable from becoming negative – let this be
known as the artificial variable (An)
f. Artificial Variable has a large value which is used as a computational device
that prevents an equality constraint from equating a constant zero, and prevents
the slack variable from becoming negative.
g. Thus, the rule in minimization:
- For constraints with ≤, add slack variable and convert to equation (equal
sign) – similar to maximization rule
- For constraints with = sign, add artificial variable and retain the equal sign
(similar to maximization rule, but different in terms of coefficient)
- or constraints with ≥: subtract a slack variable, but add an artificial
variable (different from maximization)

h. Slack variables do not contribute any amount to cost, but artificial variables
contribute the biggest amount to cost in minimization problem.
i. It contributes to the objective an amount greater than any of the coefficients of
solution variables.
j. For convenience, in representing the contribution of an artificial variable to the
objective, we may use quantity which is a power of ten, greater than any of the
coefficients found in the constraints and objective. Powers of ten are
numerals such as 10, 100, 1000, etc.

Maximization Minimization
≤ + Sn = +Sn =
≥ *(-1)+Sn = -Sn + An =
= +Sn = +An =

MAXIMIZE MINIMIZE
(PROFIT) (COST)
RULE 1: for less than or equal to constraints
Given LESS THAN OR Given LESS THAN OR
Constraint : x+y EQUAL TO Constraint : EQUAL TO
≤ 100 x+y ≤ 100
x+y + Sn =100 Add slack variable, x+y + Sn =100 Add slack variable,
convert to equation convert to
equation
RULE 2: for equal to constraints
Given Constraint: EQUAL TO Given Constraint: EQUAL TO
x+y = 100 x+y = 100
x+y + Sn =100 Add slack variable, x+y+An = 100 Add an artificial
convert to equation variable,
convert to
equation
RULE 3: for greater than or equal to constraints
Given Constraint: GREATER THAN Given Constraint: GREATER THAN
x+y ≥ 100 OR EQUAL TO x+y ≥ 100 OR EQUAL TO
-1(x+y≥100)-1 1. Multiply to x+y-Sn+An = 100 1. Subtract a
-x – y ≤ -100 negative one, slack
convert to less variable, add
than or equal to an artificial
-x-y+Sn=-100 2. Add slack variable,
variable, convert convert to
to equation. equation

2. STEPS IN SOLVING MINIMIZATION PROBLEM

- Steps in solving a minimization problem are similar to maximization except for 3
processes:
 Page 3 of 9

1. The Cj column of the initial table begins with the coefficients of artificial
variables and of slack variables in the objective with positive
coefficients in the constraints.
2. Instead of looking for the most positive quantity in C j-Zj row for the
optimum column, look for the most negative entry.
3. The optimum table or final table has entries in the C j-Zj row which are
either zero or positive.

EXAMPLE 1: Consider the following linear program:

Minimize: Z=60 x+50 y
Subject to: 3x +5y ≤15
4x + 4y ≥16
x≥0; y≥0

Solution:
The new program:
Minimize: Z=60x+50y+ 0S1- 0S2+100A1
Subject to: 3x + 5y + S1 = 15
4x + 4y – S2 + A1 = 16
x≥0; y≥0; S1≥0; S2≥0
10*10*10*10 = options: 10, 100, 1000, 10,000, 100,000, 1,000,000,
Note:
- The slack variables have zero coefficients in the objective function
- Artificial variable contributes 100, which is a power of ten greater than any
coefficient in the program.

Setting up the INITIAL Table

60 50 0 0 100
Cj Prod Qty
x y S1 S2 A1
0 S1 15 3 5 1 0 0
100 A1 16 4 4 0 -1 1
Zj 16000 400 400 100 -100 100
Cj-Zj -340 -350 -100 100 0
Note:
- The Product will initially take S1 and A1. S2 is ignored since it is negative.

Compute for the Zj row:

0 (15 3 5 1 0 0) = 0 0 0 0 0 0
100 (1,600 40 400 10 -100 100) = 1600 40 400 10 -100 100
0 0 0 0
Zj 1600 40 400 10 -100 100
0 0

Choosing the optimum column:

- Since it is a minimization problem, look for the most negative figure in the C j-
Zj row. In this case, y column is the optimum column.

Choosing the pivotal row:

Ro Divisor (under the Quotien
Qty
w optimum Column) t
S1 15 ÷ 5 3
A1 16 ÷ 4 4
- Choose the smaller quotient.
- In this case it is quotient 3, which belongs to the S1 row, thus it is the pivotal
row, and the pivot is 5.

TABLE 2:
Computing the new entries for the pivotal row (S1, which will become “y”
in the next table) – FIRST ROW
Old Entries 15 3 5 1 0 0 (Goal: to make the value of pivot equal to one
Divide by ÷ ÷ ÷ ÷ ÷ ÷ (1) in the next table)
pivot 5 5 5 5 5 5
 Page 4 of 9

New Entries 3 3 1 1 0 0
5 5

Computing for the new entries in the second row (A1 row) – SECOND ROW
Pivotal row (new 3 3 1 1 0 0 (Goal: to make the value in the
entries) 5 5 optimum column equal to zero.
Multiply by: (-4) (-4) (-4) (-4) (-4) (-4) Multiply the entries of the pivotal
additive inverse row with the additive inverse of the
Add: Old Entries 16 4 4 0 -1 1 figure in the row which belongs to
New Entries 4 8 0 −4 -1 1 the optimum column
5 5

60 50 0 0 100
Cj Prod Qty
x y S1 S2 A1
50 y 3 3 1 1 0 0
5 5
100 A1 4 8 0 −4 -1 1
5 5
Zj 550 190 50 -70 -100 100
Cj-Zj -130 0 70 100 0

Compute for the Zj row:

50 (3 3 1 1 0 0) = 150 30 5 10 0 0
5 5 0
100 (4 8 0 −4 -1 1 = 400 160 0 -80 -100 100
5 5
Zj 550 190 5 -70 -100 100
0

Choosing the optimum column:

- Since it is a minimization problem, look for the most negative figure in the C j-
Zj row. In this case, x column is the optimum column.

Choosing the pivotal row:

Ro Divisor (under the
Qty Quotient
w optimum Column)
3
y 3 ÷ 5
5
8 20 5
A1 4 ÷ ∨ ∨2.5
5 8 2
- Choose the smaller quotient.
- In this case it is quotient 2.5, which belongs to the A 1 row, thus it is the
8
pivotal row, and the pivot is .
5
TABLE 3:
Computing the new entries for the pivotal row (A1, which will become “x” in
the next table) – SECOND ROW
Old Entries 4 8 0 −4 -1 1 (Goal: to make the value of pivot equal to one
5 5 (1) in the next table)
Divide by pivot 8 8 8 8 8 8
5 5 5 5 5 5
New Entries 5 1 0 −1 −5 5
2 2 8 8

Computing for the new entries in the first row (y row) – FIRST ROW
Pivotal row (new 5 1 0 −1 −5 5 (Goal: to make the value in the
entries) 2 2 8 8 optimum column equal to zero.
Multiply by: additive −3 −3 −3 −3 −3 −3 Multiply the entries of the pivotal row
inverse with the additive inverse of the figure
5 5 5 5 5 5
in the row which belongs to the
Add: Old Entries 3 3 1 1 0 0
optimum column
5 5
New Entries 3 0 1 1 3 −3
2 2 8 8
 Page 5 of 9

Prod 60 50 0 0 100
Cj Qty
x y S1 S2 A1
50 y 3 0 1 1 3 −3
2 2 8 8
60 x 5 1 0 −1 −5 5
2 2 8 8
Zj 225 60 50 -5 −75 75
4 4
Cj-Zj 0 0 5 75 325
4 4

Compute for the Zj row:

5 ¿ 0 1 1 3 −3 = 75 0 5 25 75 −75
0 2 8 8 0 4 4
)
6 ¿ 1 0 −1 −5 5 = 150 60 0 -30 −75 75
0 )
2 8 8 2 2
Zj 225 60 5 -5 −75 75
0 4 4

Since there is no more negative entry in the last row, the table is optimum.
3
Decision: y= ∨1.5
2
5
x = ∨2.5
2
Minimum Z = P225

EXAMPLE 2:
The Philippine Feeds Inc. produces specially blended feed supplements. It has an
order of 400 pounds of the mixture. This consists of two ingredients: P, a source of
protein and C, a carbohydrate source.

The first ingredient P, costs P6 a pound. The second ingredient C, costs P16 a
pound. The mixture cannot be more than 150 pounds P, and it must have at least
200 pounds C. The company’s problem is to determine how much of each ingredient
to use to minimize cost, but satisfy the requirements.

Solution:
Minimize: 6P + 16C
Subject to: P + C = 400 (total order)
P≤150 (P content)
C≥200 (C content)
P≥0
C≥0

New program:
Minimize: 6P+16C+0S1-0S2+1000A1 +1000A2
Subject to: P+C+A1 = 400 (1)
P+S1= 150 (2)
C – S2+ A2 = 200 (3)

Setting up the INITIAL Table

6 16 0 0 1000 1000
Cj Prod Qty
P C S1 S2 A1 A2
1000 A1 400 1 1 0 0 1 0
0 S1 150 1 0 1 0 0 0
1000 A2 200 0 1 0 -1 0 1
Zj 600,000 1000 2000 0 -1000 1000 1000
Cj - Z j -994 -1984 0 1000 0 0
Note:
- The Product will take slack and artificial variables with no negative coefficients
 Page 6 of 9

Compute for the Zj row:

100 (400 1 1 0 0 1 0) = 400,000 100 1000 0 0 1000 0
0 0
0 (150 1 0 1 0 0 0) = 0 0 0 0 0 0 0
100 (200 0 1 0 -1 0 1) = 200, 000 0 1000 0 -1000 0 1000
0
Zj 600,000 100 2000 0 -1000 1000 1000
0

Choosing the optimum column:

- Since it is a minimization problem, look for the most negative figure in the C j-
Zj row. In this case, C column is the optimum column (-184).

Choosing the pivotal row:

Ro Divisor (under the
Qty Quotient
w optimum Column)
A1 400 ÷ 1 400
S1 150 Exempted from computation, since divisor is zero
A2 200 ÷1 200
- Choose the smaller quotient.
- In this case it is quotient 200, which belongs to the A2 row, thus it is the
pivotal row, and the pivot is 1.

TABLE 2:
Computing the new entries for the pivotal row (A2, which will become “C”
in the next table) – THIRD ROW
Old 200 0 1 0 -1 0 1 (Goal: to make the value of pivot equal to
Entries one (1) in the next table)
(No need to divide since pivot is
already 1)
New 200 0 1 0 -1 0 1
Entries

Computing for the new entries in the first row (A1 row) – FIRST ROW

Pivotal row (new 200 0 1 0 -1 0 1 (Goal: to make the value in the

entries) optimum column equal to zero.
Multiply by (-1) (-1) (-1) (-1) (-1) (-1) (-1) Multiply the entries of the pivotal
additive inverse row with the additive inverse of
Add: Old Entries 400 1 1 0 0 1 0 the figure in the row which
New Entries 200 1 0 0 1 1 -1 belongs to the optimum column

Computing for the new entries in the second row (S1 row) – SECOND ROW
Pivotal row (new 200 0 1 0 -1 0 1 (Goal: to make the value in the
entries) optimum column equal to zero.
Multiply by (0) (0) (0) (0) (0) (0) (0) Multiply the entries of the pivotal
additive inverse row with the additive inverse of
Add: Old Entries 150 1 0 1 0 0 0 the figure in the row which
New Entries 150 1 0 1 0 0 0 belongs to the optimum column
Or
No need to multiply with additive inverse, since the
corresponding figure below pivot is already at zero.
Thus, old entries will be retained
Add: Old Entries 150 1 0 1 0 0 0
New Entries 150 1 0 1 0 0 0

6 16 0 0 1000 1000
Cj Prod Qty
P C S1 S2 A1 A2
1000 A1 200 1 0 0 1 1 -1
0 S1 150 1 0 1 0 0 0
16 C 200 0 1 0 -1 0 1
 Page 7 of 9

Zj 203, 200 1000 16 0 984 1000 -984

Cj - Z j -994 0 0 -984 0 1984

Compute for the Zj row:

100 (200 1 0 0 1 1 -1) = 200, 000 1000 0 0 1000 1000 -1000
0
0 (150 1 0 1 0 0 0) = 0 0 0 0 0 0 0
16 (200 0 1 0 -1 0 10 = 3, 200 0 16 0 -16 0 16
Zj 203, 200 1000 16 0 984 1000 -984

Choosing the optimum column:

- Since it is a minimization problem, look for the most negative figure in the C j-
Zj row. In this case, P column is the optimum column (-94).

Choosing the pivotal row:

Ro Divisor (under the
Qty Quotient
w optimum Column)
A1 200 ÷ 1 200
S1 150 ÷ 1 150
C 150 Exempted from computation, since divisor is zero
- Choose the smaller quotient.
- In this case it is quotient 150, which belongs to the S1 row, thus it is the
pivotal row, and the pivot is 1.

TABLE 3:
Computing the new entries for the pivotal row (S1, which will become “P” in
the next table) – SECOND ROW
Old 150 1 0 1 0 0 0 (Goal: to make the value of pivot equal to
Entries one (1) in the next table)
(No need to divide since pivot is
already 1)
New 150 1 0 1 0 0 0
Entries

Computing the new entries for A1 row – FIRST ROW

Pivotal row (new 150 1 0 1 0 0 0 (Goal: to make the value in the
entries) optimum column equal to zero.
Multiply by (-1) (-1) (-1) (-1) (-1) (-1) (-1) Multiply the entries of the pivotal
additive inverse row with the additive inverse of
Add: Old Entries 200 1 0 0 1 1 -1 the figure in the row which
New Entries 50 0 0 -1 1 1 -1 belongs to the optimum column

Computing the new entries for C row – THIRD ROW

Pivotal row (new 150 1 0 1 0 0 0 (Goal: to make the value in the
entries) optimum column equal to zero.
Multiply by (0) (0) (0) (0) (0) (0) (0) Multiply the entries of the pivotal
additive inverse row with the additive inverse of
Add: Old Entries 200 0 1 0 -1 0 1 the figure in the row which
New Entries 200 0 1 0 −1 0 -1 belongs to the optimum column
or
No need to multiply with additive inverse, since the
corresponding figure below pivot is already at zero.
Thus, old entries will be retained
Add: Old Entries 200 0 1 0 -1 0 1
New Entries 200 0 1 0 -1 0 1

6 16 0 0 1000 1000
Cj Prod Qty
P C S1 S2 A1 A2
1000 A1 50 0 0 -1 1 1 -1
6 P 150 1 0 1 0 0 0
16 C 200 0 1 0 -1 0 1
Zj 54, 100 6 16 -994 984 1000 -984
Cj - Z j 0 0 994 -984 0 1984

Compute for the Zj row:

100 (50 0 0 -1 1 1 -1) = 50,000 0 0 -1000 1000 1000 -1000
 Page 8 of 9

0
6 (150 1 0 1 0 0 0) = 900 6 0 6 0 0 0
16 (200 0 1 0 -1 0 1) = 3, 200 0 16 0 -16 0 16
Zj 54, 100 6 16 -994 984 1000 -984

Choosing the optimum column:

- Since it is a minimization problem, look for the most negative figure in the C j-
Zj row. In this case, S2 column is the optimum column (-84).

Choosing the pivotal row:

Ro Divisor (under the
Qty Quotient
w optimum Column)
A1 50 ÷ 1 50
P 150 ÷ Exempted from computation, since divisor is zero
C 200 Exempted from computation, since divisor is Negative
- Choose the smaller quotient.
- In this case the pivotal row is automatically A 1 row

TABLE 4:
Computing the new entries for the pivotal row (A1, which will become “S2” in
the next table) – FIRST ROW
Old 50 0 0 -1 1 1 -1 (Goal: to make the value of pivot equal
Entries to one (1) in the next table)
(No need to divide since pivot is
already 1)
New 50 0 0 -1 1 1 -1
Entries

Computing the new entries for P row – SECOND ROW

No need to multiply with additive inverse, since the
corresponding figure below pivot is already at zero.
Thus, old entries will be retained
Add: Old Entries 150 1 0 1 0 0 0
New Entries 150 1 0 1 0 0 0

Computing the new entries for C row – THIRD ROW

Pivotal row (new 50 0 0 -1 1 1 -1 (Goal: to make the value in the
entries) optimum column equal to zero.
Multiply by (1) (1) (1) (1) (1) (1) (1) Multiply the entries of the pivotal
additive inverse row with the additive inverse of
Add: Old Entries 200 0 1 0 -1 0 1 the figure in the row which
New Entries 250 0 1 -1 0 1 0 belongs to the optimum column

6 16 0 0 100 100
Cj Prod Qty
P C S1 S2 A1 A2
0 S2 50 0 0 -1 1 1 -1
6 P 150 1 0 1 0 0 0
16 C 250 0 1 -1 0 1 0
Zj 4,900 6 16 -10 0 16 0
Cj - Z j 0 0 10 0 84 100

Compute for the Zj row:

0 (50 0 0 -1 1 1 -1) = 0 0 0 0 0 0 0
6 (150 1 0 1 0 0 0) = 900 6 0 6 0 0 0
1 (250 0 1 -1 0 1 0) = 4, 000 0 16 -16 0 16 0
6
Zj 4,900 6 16 -10 0 16 0

Since there is no more negative entry in the last row, the table is optimum.
 Page 9 of 9

Decision:
P = 150 (SOURCE OF PROTEIN)
C = 250 (SOURCE OF CARBOHYDRATES)
Minimum Cost = P4, 900

Application

Write your answers in any clean piece of paper. Take a picture and submit it via Google
Classroom. Ensure that every sheet of your submission is labeled with your name. Show
your solution and box-in your final answer.

Problem 1:
A company produces two commodities x and y and wishes to minimize cost =
120x + 100y subject to constraints 2x+y≤18 and 5x + 4y≥60. Determine the
optimal quantities of each commodity

Problem 2:
How much beef at P90 a kilo which contains 80% lean meat and 20% fat and how
much pork at P75 a kilo which contains 75% lean and 25% fat shoul be
purchased to provide at most 12 kilos of lean and at least 4 kilos of fat while
keeping the cost as small as possible?

***NOTHING FOLLOWS**