MTH 242 – OPERATIONS RESEARCH CSMJACOB

HANDOUT #2 – Linear Programming: The Simplex Method

Simplex algorithm – a general procedure for solving linear programming (LP) problems developed by George Dantzig in
1947
– requires the LP model to be in standard form

Advantages and Characteristics of the simplex method

i. More realistic approach as it is not limited to problems with two decision variables
ii. Systematically examines basic feasible solutions for an optimal solution.
iii. Based on the solutions of linear equations (equalities) using slack variables to achieve equality.

Properties of the LP model in standard form:

i. All the constraints are equations with non-negative right-hand-side (RHS) values.
ii. All the variables are non-negative.
iii. The objective of the problem is to either maximize or minimize the objective function value.

Constraints
1. A constraint of the type ≤ can be converted into an equation by adding a slack variable to the left side of the
constraint.
Ex.4 x+5 y ≤ 8 is converted into 4 x+5 y + s1=8 in the standard form, with s1 ≥0 .
If the constraint represents the limit on the availability of a resource, s1 will represent the slack or unused amount of
that resource.

2. A constraint of the type ≥ can be converted into an equation by adding a surplus variable to the left side of
the constraint.
Ex. 2 x+ 4 y−6 z ≥ 9is converted into 2 x+ 4 y−6 z −s 2=9 in the standard form, with s2 ≥0 .
If the constraint represents the minimum production requirement, s2 will represent the items produced beyond the
minimum required.

3. The RHS can be made non-negative by multiplying both sides by -1, and the direction of an inequality is
reversed when both sides are multiplied by a negative number.
Ex.−3 x+ 7 y ≤−15 is equivalent to 3 x−7 y ≥15 and is then converted into 3 x−7 y−s3 =15 in the standard
form with s3 ≥0.

Objective Function
The maximization of a function is equivalent to the minimization of the negative of the same function.
Equivalence means that for the same set of constraints, the optimum values of the variables are the same in both cases,
although the values of the objective functions will appear with opposite signs but the same magnitude.

The Simplex Method

The simplex algorithm considers the corner point feasible (CPF) solutions as the candidates for the optimal mix.
It starts at the origin, referred to as the starting solution, then moves to an adjacent corner point, the choice dependent
on which point will improve the value of the objective function more. The iterative process is repeated by moving to
another adjacent corner point, until the corner point where the value of the objective function is optimized, is finally
reached.
The simplex algorithm is governed by two general rules:
1. The next corner point must be adjacent to the current one. Thus, moving from one corner point to the next
involves moving along the edges of the solution area, and never across it.
2. The solution can never go back to a previously considered extreme point.

MTH 242/HANDOUT 2/CSMJACOB |1

I. Maximization
Recall the example of the furniture manufacturer that produces wooden tables and chairs, formulated below:
Maximize: Z=6 X +8 Y
Subject to: 30 X +20 Y ≤300
5 X +10 Y ≤110
X , Y ≥0

The standard form of the LP model is given by:

Maximize: Z=6 X +8 Y +0 S1 +0 S2
Subject to: 30 X +20 Y + S1=300
5 X +10 Y + S2=110
X , Y , S1, S2≥ 0

The solution area is shown below, with the corner points denoted by A, B, C, and D, and every point in the solution space
represented in terms of the variables X, Y, S1, and S2 of the standard form.
Y

30X + 20Y + S1 = 300

B

5X + 10Y +S2 = 110

A D X

Identifying the corner points algebraically:

Corner Point Zero Variables Nonzero Variables
A X, Y S1, S2
B X, S2 Y, S1
C S1, S2 X, Y
D Y, S1 X, S2

From the table above, it can be observed that:

i. Since the standard form has two equations and four unknowns, each corner point must have two (4-2=2) variables at
zero level. In general, given m equations and n variables, all feasible corner points are determined by considering all the
unique non-negative solutions of the m equations in which n-m are set equal to zero. Such unique solutions are called
basic solutions. If a basic solution satisfies the non-negativity constraints, it is called a basic feasible solution. The
variables set equal to zero are called nonbasic variables, the remaining ones are called basic variables.

ii. Adjacent corner points differ only in one variable. Thus, movement from a current corner point to an adjacent one
would involve interchanging a current nonbasic (zero) variable into a basic one. The basic-to-nonbasic interchange
results in the following terms: the entering variable is a current nonbasic variable that will “enter” the set of basic

MTH 242/HANDOUT 2/CSMJACOB |2

variables at the next (adjacent corner point); the leaving variable is a current basic variable that will “leave” the basic
solution in the next iteration.

Exercise:
Complete the constraints inequalities based on the shaded solution space below.
Maximize: Z = 3X + 2Y
Subject to: X + 2Y 6 1
2X + Y 8 2
-X + Y 1 3
Y 2 4
X, Y, ≥ 0

Y
2

1 4

3 C D
B E

A
F X

2. Give the standard form of the LP model above.

3. Complete the table below.

MTH 242/HANDOUT 2/CSMJACOB |3
Corner Point Nonbasic Variables Basic Variables
A X, Y
B
C
D
E
F

5. Based on the graph of the solution space, determine the entering and leaving variables when the solution moves
between the pairs of adjacent corner points shown below.
a. B C ___________ enters and ____________ leaves
b. C D ___________ enters and ____________ leaves
c. E F ___________ enters and ____________ leaves

Solving an LP Problem by the Simplex Algorithm

Step 0. Using the standard form, determine a starting basic feasible solution by setting n – m appropriate variables at
zero level.
Step 1. Select an entering variable from among the current nonbasic variables which, when increased above zero, can
improve the value of the objective function. If none exists, stop; the current basic solution is optimal. Otherwise,
go to step 2.
Step 2. Select a leaving variable from among the current basic variables that must be set to zero when the entering
variable becomes basic.
Step 3. Determine the new basic solution by making the entering variable basic and the leaving variable nonbasic. Go to
step 1.

Illustration:
A manufacturing firm produces two products, A and B. Each of these products must be processed through two
different machines. One machine has 12 hours and the second machine has 8 hours of available capacity. Each unit of
product A requires two hours of time on both machines. Each unit of product B requires three hours of time on the first
machine and one hour on the second machine. The incremental profit is P300 per unit of product A and P350 per unit of
product B, and the firm can sell as many units of each product as it can manufacture.
The objective of the firm is to maximize profits. The problem is to determine how many units of product A and
product B should be produced within the limits of available machine capacities.

Formulation
Let X1 – number of units of product A to be produced
X2 – number of units of product B to be produced

Maximize: Z = 300X1 + 350X2 (objective function/profit function –computes the total profit with any
given value of the basic variables X 1 and X2)
Subject to: 2X1 + 3X2 ≤ 12 (constraint on the limited availability of Machine I)
2X1 + X2 ≤ 8 (constraint on the limited availability of Machine II)
X1 , X2 ≥ 0 (non-negativity constraints)

The standard form of the model is:

MTH 242/HANDOUT 2/CSMJACOB |4
Maximize: Z = 300X1 + 350X2 + 0S1 + 0S2 (Since any unused machine time does not contribute to profit, the
coefficients of the slack variables in the objective function are
zeros.)
Subject to: 2X1 + 3X2 + S1 = 12
2X1 + X2 + S2 = 8
X1 , X2, S1, S2 ≥ 0

Illustration of the effect of the different production levels on the slack variable:
Quantity of Items Number of hours of
Produced Machine I used Excess Available Time of Machine I
Product A Product B Product A Product B
0 0 0 0 12 – 0 = 12 (S 1 = 12)
1 1 2 3 12 – 5 = 7 (S 1 = 7)
2 2 4 6 12 – 10 = 2 (S 1 = 2)

Note: Only the functional constraints need to be transformed into equations. The non-negativity constraints are left as
inequalities, since they are not affected by the simplex solution method.

Setting up the initial tableau

In the simplex method, an initial solution needs to be established. The simplex starting solution for the firm is to
manufacture none of either product, that is, X 1 = 0 and X2 = 0. This solution is technically feasible but not financially
attractive. It is represented in the graphical solution by the origin with coordinates (0,0). Thus,
X1 = 0
X2 = 0
S1 = 12 – 2(0) – 3(0) = 12 hours unused for Machine I
S2 = 8 – 2(0) – 0 = 8 hours unused for Machine II

This solution contains only the slack variables S 1 and S2. Substituting the values of the variables (X 1 and X2) and the slack
variables in the objective function gives the following profit:
Profit (Z) = 300X1 + 350X2 + 0S1 + 0S2
= 300(0) + 350(0) + 0(12) + 0(8)
=0
This first feasible solution is shown in the initial simplex tableau as

Basic Variables Quantity X1 X2 S1 S2 The entries in the coefficient rows

S1 12 2 3 1 0 2X1 + 3X2 + S1 = 12 come directly from the constraint
S2 8 2 1 0 1 2X1 + X2 + S2 = 8 equations

Note that the first column contains the variables in the solution. The variables in the first solution are S 1 and S2, the slack
variables. In the quantity column are the quantities of the variables that are in the solution:
S1 = 12 hours of availability of Machine I
S2 = 8 hours of availability of Machine II
Since the variables X1 and X2 do not appear in the mix, they are equal to zero, and thus are nonbasic in the initial
solution.

The partial initial simplex tableau is shown below:

MTH 242/HANDOUT 2/CSMJACOB |5
1 2 3 4 5 6 7
Cj Quantity 300 350 0 0
Basic Variables X1 X2 S1 S2
0 S1 12 2 3 1 0
0 S2 8 2 1 0 1

- The Cj column contains the profit per unit for the variables in the solution. The initial solution includes only the
slack variables S1 and S2, and since these contribute zero to profit, the entries in the C j column of the initial tableau are
zeros.
- Columns 6 and 7 consist of the coefficients of the slack variables that are added to the constraint inequalities to
make them equations.
- Columns 4 and 5 consist of the coefficients of the nonbasic variables X 1 and X2, and their elements represent
rates of substitution. For example, the element 2 in the X 1 column means that if one item of A is to be manufactured (to
bring 1 item of A in the solution), then 2 hours of Machine 1 will have to be used (decreasing the value of S 1 by 2).
Similarly, the element 3 in the X2 column means that if one item of B is to be made (to bring 1 item of B in the solution),
then 3 hours of Machine I will have to be used (decreasing the value of S 1 by 3).
- The element 1 in the S 1 column means that if 1 hour of Machine 1 is to be introduced into the solution, then 1
of the 12 hours of S1 in the solution will have to be given up.
- The element 0 in the S 2 column means that introducing 1 hour of Machine II in the solution has no effect on the
available hours of Machine I.

To find the profit for each solution and to determine whether the solution can still be improved, two more rows need to
be added to the simplex tableau: a Zj row and a Cj – Zj row, as shown below.

Cj Quantity 300 350 0 0

Basic Variables X1 X2 S1 S2
0 S1 12 2 3 1 0
0 S2 8 2 1 0 1
Zj 0 0 0 0 0
Cj - Zj 300 350 0 0

The value in the Zj row under the quantity column represents the total profit from this particular solution - 0, in this
case. In this solution, there are 12 hours of unused Machine I time (S 1 = 12) and 8 hours of unused Machine II time (S 2 =
8). The total profit from this solution is computed by multiplying the profit per unit of S 1 (0) by the quantity of S 1 in the
solution (12 hours) plus the profit per unit of S 2 (0) times the quantity of S2 in the solution (8 hours).
Total profit for the initial solution: (0)(12) + (0)(8) = 0
The four values for Zj under the variable columns (all 0) are amounts by which profit would be reduced if 1 unit of any of
the variables (X1 , X2 , S1 , S2) were added to the mix. For example, if 1 unit of X 1 is to be manufactured, the elements [ 22]
under X1 mean that 2 hours of S 1 and 2 hours of S2 must be used, decreasing the unused time. But unused time is worth
0 profit per hour; hence, there is no (0) reduction in profit. The computation for the amount of profit lost by introducing
1 unit of X1 into the product mix is shown below.
Number of hours of S1 given up = 2
times profit per unit of S 1 × 0=0
Number of hours of S2 given up = 2
times profit per unit of S 12 × 0=0
Total profit given up 0

The computation of Zj values are summarized below:

MTH 242/HANDOUT 2/CSMJACOB |6
Zj (total profit) = 0(12) + 0(8) = 0
Zj for column X1 = 0(2) + 0(2) = 0
Zj for column X2 = 0(3) + 0(1) = 0
Zj for column S1 = 0(1) + 0(0) = 0
Zj for column S2 = 0(0) + 0(1) = 0

Cj has been defined as profit per unit; for product A (X 1), Cj is P300. Hence Cj – Zj is the net profit which will result from
introducing (or adding) 1 unit of a variable to the production schedule (or the solution). For example, if 1 unit of product
X1 adds P300 of profit to the solution and if its introduction causes 0 loss, then C j – Zj = 300 – 0 = 300. Calculations of net
profit per unit of each variable follow:
Profit per unit - Profit lost per unit = Net profit per unit
Variable
Cj - Zj = C j - Zj
X1 300 - 0 = 300
X2 350 - 0 = 350
S1 0 - 0 = 0
S2 0 - 0 = 0
The values in the Cj – Zj indicate the amount by which profit would improve with the introduction of 1 units of a variable
into the solution. A negative value gives the amount by which profits would decrease with the entry of 1 unit of a
variable in the solution. It can be seen that the variable X 2 will improve the profit the most.
Setting up the second tableau

Cj Quantity 300 350 0 0

Basic Variables X1 X2 S1 S2
0 S1 12 2 3 1 0
0 S2 8 2 1 0 1
Zj 0 0 0 0 0
Cj - Zj 300 350 0 0

Determine the entering variable from the Cj-Zj equation by choosing the variable with the most positive coefficient
because this has the potential of improving the value of the objective function the most. The optimality condition of the
simplex method states that, in the case of maximization, if all the nonbasic variables have negative coefficients in the Cj-
Zj row of the current tableau, the current solution is optimal. Otherwise, the nonbasic variable with the largest
coefficient is selected as the entering variable.

From the initial tableau above, it can be seen that 1 unit of product B (X 2 = 1) contributes P350 to the profit, while 1 unit
of product A (X1 = 1) contributes only P300 to profit. Thus, X2 should be introduced into the solution, making the X 2
column the entering column. By definition, the optimal/entering column is the column which has the largest positive
value in the Cj – Zj row, or the column whose product will contribute the most profit per unit.

To determine the leaving variable, the feasibility condition is used, which selects the leaving variable as the
current basic variable that will be the first to reach zero level when the entering variable reaches its maximum value at
the adjacent corner point. From the tableau, the leaving variable is the current basic variable associated with the
smallest non-negative ratio of the RHS values to the corresponding values in the entering column. The row associated
with the leaving variable is called the pivot equation and the element at the intersection of the entering column and the
pivot equation is called the pivot element. Determining the smallest non-negative ratio involves dividing each variable’s
quantity by the corresponding coefficient in the entering column, and choosing the smallest quotient. For the tableau
above:
12hours of Mach ine I
S1 row: =¿ 4 units of product B to finish up all of S 1
3 units of product B

MTH 242/HANDOUT 2/CSMJACOB |7

8 hours of Mac h ine II
S2 row: = 8 units of product B to finish up all of S 2
1 unit of product B
Since the S1 row has the smaller positive quotient, it is called the replaced row and it will be replaced by 4 units of X 2 in
the next solution. The elements of the optimal column are called the intersectional elements.
The second tableau, row by row (with solution) is shown below.

Cj Cj 30
300 350 0 0 350 0 0
Basic Quantity Basic Quantity 0
Variables X1 X2 S1 S2 Variables X1 X2 S1 S2
1/
0 S1 12 2 3 1 0 350 X2 4 2/3 1 0
3
1 2

Figure 1 above shows the replaced row as it appears in the initial solution. Figure 2 shows the replacing row, as it
appears in the second and improved solution, with the introduction of 4 units of product B (X 2 = 4) in the solution. The
values of the replacing row are computed by dividing each row element by the pivot, or the number common to both
the entering column and the replaced row, in this case, 3. The Cj column now shows a value of 350, since that is the
contribution to profit of 1 unit of X2.

( Element ∈replaced row ÷ pivot )=(Element ∈replacing row)

2 1
12 ÷3=4 2 ÷3= 3 ÷ 3=1 1 ÷3= 0 ÷ 3=0
3 3

Cj 300 350 0 0 Cj Basic 300 350 0 0

Basic Variables Quantity X1 X2 S1 S2 Variables Quantity X1 X2 S1 S2
350 X2 4 2/3 1 1/3 0 350 X2 4 2/3 1 1/3 0
0 S2 8 2 1 0 1 0 S2 a b C d e
Fig. 3 Fig. 4

Figure 3 above shows the old S2 row as it has not been developed yet for the second solution. The values in the new S 2
row (a, b, c, d, e) in figure 4 will be computed using the formula:

(¿Elements = Elements −¿
new row ) ( ¿ old row )

a = 8 – (1)(4) = 8–4 =4
b = 2 – (1)(2/3) = 2 – 2/3 = 4/3
c = 1 – (1)(1) = 1–1 =0
d = 0 – (1)(1/3) = 0 – 1/3 = -1/3
e = 1 – (1)(0) = 1–0 =1

The partial second tableau below shows the replaced row with the values computed above.

Cj 300 350 0 0
Basic Variables Quantity X1 X2 S1 S2
350 X2 4 2/3 1 1/3 0
0 S2 4 4/3 0 -1/3 1

MTH 242/HANDOUT 2/CSMJACOB |8

As in the initial tableau, the computations of Zj values are summarized below:

Zj (total profit) = 350(4) + 0(4) = 1400 = total profit of second solution

Zj for column X1 = 350(2/3) + 0(4/3) = 700/3 Profits given up by introducing
Zj for column X2 = 350(1) + 0(0) = 350 1 unit of each of these
Zj for column S1 = 350(1/3) + 0(-1/3) = 350/3 Variables
Zj for column S2 = 0(0) + 0(1) = 0

The computations above indicate that introducing a unit of product B would lose P350 for the firm. This is explained in
the following statements:
1. The current solution shows a production level of 4 units of product B.
2. Since a unit of product B uses 3 hours of Machine I, 4 units of product B uses up all the available
hours of Machine I.
3. To introduce another unit of product B (that needs 3 hours of Machine I) means giving up 1 of the 4
units of product B currently in the solution.
4. Giving up a unit of product B means losing P350 in profit.

Based on the above statements, can you explain why introducing 1 unit of X 1 (product A) would lose P700/3 in profit for
the firm?

Calculations of net profit per unit of each variable follow:

Profit per unit - Profit lost per unit = Net profit per unit
Variable
Cj - Zj = C j - Zj
X1 300 - 700/3 = 200/3
X2 350 - 350 = 0
S1 0 - 350/3 = -350/3
S2 0 - 0 = 0

The complete second tableau with the improved solution is shown below.
Cj Quantity 300 350 0 0
Basic Variables X1 X2 S1 S2
350 X2 4 2/3 1 1/3 0
0 S2 4 4/3 0 -1/3 1
Zj 1400 700/3 350 350/3 0
Cj - Zj 200/3 0 -350/3 0

Setting up the third tableau

A look at the Cj – Zj row of the second tableau shows that X 1 (product A) contributes a net profit of P200/3 per
unit. Thus, the entering column is the X 1 column. Product A will now be added to the solution, replacing one of the
variables X2 or S2.

The replaced row is again determined by dividing 4 and 4 in the quantity column with their corresponding
elements in the entering column, and selecting the row with the smaller non-negative ratio as the replaced row. Since 4
÷ 2/3 = 6 (in the X2 row) and 4 ÷ 4/3 = 3 (in the S2 row), the S2 row is designated as the replaced row.

MTH 242/HANDOUT 2/CSMJACOB |9

The figure below shows the entering column, replaced row, and intersectional elements of the second tableau.

Cj Quantity 300 350 0 0

Basic Variables X1 X2 S1 S2
350 X2 2/3
300 S2 4 4/3 0 -1/3 1
Zj
Cj - Zj

Replacing the S2 row with X1 gives the replacing row below.

Cj 300 350 0 0
Basic Variables Quantity X1 X2 S1 S2
350 X2 a b c d e
300 X1 3 1 0 -1/4 3/4
Zj
Cj - Zj

The new values in the X2 row are

(¿Elements
new row )=( Elements ) −¿
¿ old row

a = 4 – (2/3)(3) = 4–2 =2
b = 2/3 – (2/3)(1) = 2/3 – 2/3 =0
c = 1 – (2/3)(0) = 1–0 =1
d = 1/3 – (2/3)(-1/4) = 1/3 + 1/6 = 1/2
e = 0 – (2/3)(3/4) = 0 – 1/2 = -1/2

The computations of Zj values for the third tableau are summarized below:

Zj (total profit) = 350(2) + 300(3) = 1600 = total profit of third solution

Zj for column X1 = 350() + 300(1) = 300 Profits given up by introducing
Zj for column X2 = 350(1) + 0(0) = 350 1 unit of each of these
Zj for column S1 = 350(1/2) + 300(-1/4) = 100 variables
Zj for column S2 = 350(-1/2) + 300(3/4) = 50

Calculations of net profit per unit of each variable follow:

Profit per unit - Profit lost per unit = Net profit per unit
Variable
Cj - Zj = C j - Zj
X1 300 - 300 = 0
X2 350 - 350 = 0
S1 0 - 100 = -100
S2 0 - 50 = -50

MTH 242/HANDOUT 2/CSMJACOB | 10

The third tableau below shows all the values computed above.
Cj Quantity 300 350 0 0
Basic Variables X1 X2 S1 S2
350 X2 2 0 1 1/2 -1/2
300 X1 3 1 0 -1/4 3/4
Zj 1600 300 350 100 50
Cj - Zj -300 -350 -100 -50

Since the net profit row (C j – Zj) no longer shows any positive value, indicating that the solution can no longer be
improved upon, the third tableau shows the final optimum solution.

The final optimal solution is to produce X 1 = 3 units of product A and X 2 = 2 units of product B for a maximum profit of
P1,600.

Illustration2:
Maximize: Z=6 X 1 +8 X 2
Subject to: 30 X 1 +20 X 2 + S1=300
5 X 1 +10 X 2 + S2=110
X 1 , X 2 ≥0

Below is the initial tableau for the simplex algorithm.

Cj
Basic Variables Quantity X1 X2 S1 S2

Zj
Cj - Zj

The second iteration will result in the tableau below:

Cj
Basic Variables Quantity X1 X2 S1 S2

Zj
Cj - Zj

MTH 242/HANDOUT 2/CSMJACOB | 11

Complete tableau after iteration 3:

Cj
Basic Variables Quantity X1 X2 S1 S2

Zj
Cj - Zj

The tableau above is optimal because none of the nonbasic variables has a positive coefficient in the Cj – Zj row. This
completes the simplex method computations after 3 iterations. Thus, the optimal solution is for Margan Furniture to
produce X1 = 4 tables and X2= 9 chairs, for a maximum profit = $96.

For either maximization or minimization problems, the following conditions apply:

Optimality condition
The entering variable in maximization (minimization) is the nonbasic variable with the most positive (negative)
coefficient in the Cj –Zj row. A tie is broken arbitrarily.
Feasibility condition
For both the maximization and minimization problems, the leaving variable is the basic variable having the
smallest positive ratio. A tie is broken arbitrarily.

Exercise: Solve the following problem using the simplex method:

Maximize Z = 2X1– 4X2+ 5X3– 6X4
subject to
X1 + 4X2 – 2X3 + 8X4≤ 2
-X1 + 2X2 + 3X3 + 4X4≤ 1
X1 ,X2 , X3 , X4≥ 0

I. Minimization

To illustrate the minimization procedure, the example below will be used:

Margan Furniture makes two products – tables and chairs, which must be processed through assembly and finishing
departments. The assembly department is available for 60 hours in every production period, while the finishing
department is available for 48 hours of work. Manufacturing one table requires 4 hours in assembly and 2 hours in
finishing. Each chair requires 2 hours in assembly and 4 hours in finishing. The marketing director has promised
customers that the company will make at least 2 tables and at least 4 chairs per production period. It has been
determined that it costs P800 per unit to manufacture a table, and P320 per unit to manufacture a chair. It is desired
to minimize the total manufacturing cost of tables and chairs.
Let X1 – the number of tables to be manufactured
X2 – the number of chairs to be manufactured
The objective is to minimize cost: Z = 800X1 + 320X2
Subject to: 4X1 + 2X2£ 60 (Maximum availability of the assembly department)
2X1 + 4X2£ 48 (Maximum availability of the finishing department)
X1 ≥ 2 (Minimum supply of tables)

MTH 242/HANDOUT 2/CSMJACOB | 12

X2 ≥ 4 (Minimum supply of chairs)
X1, X2 ≥ 0
The standard forms of the constraints are:
4X1 + 2X2 + S1 = 60 (where S1 – excess hours in the assembly department)
2X1 + 4X2 + S2 = 48 (where S2 – excess hours in the finishing department)
X1 - S 3 = 2 (where S3 - surplus supply of tables)
X2 - S4 = 4 (where S4 – surplus supply of chairs)
X1, X2, S1, S2, S3, S4≥ 0

The initial solution where X1 = 0 and X2 = 0 produces the following equations:

S1 = 60
S2 = 48
- S3= 2 These violate the non-negativity constraints, as these are equivalent to
- S4 = 4 S3 = -2 and S4 = -4

To be able to provide an initial solution that will satisfy all constraints, artificial variables will be introduced. Since
artificial variables have no feasible physical meaning from the standpoint of the original problem, adding them will be
valid only if they are forced to be zero when the optimum is reached. Thus, they are used only to start the solution and
must subsequently be forced to assume a zero value at the optimal solution. Consider the constraint:
X1 ≥ 2.
Adding an artificial variable A3 will transform the constraint to:
X1 + A3 ≥ 2
Transforming the constraint into an equation:
X1 + A3 – S3 =2
A3 serves as an artificial variable for the supply of tables. Hence, it can be thought of as a very expensive substitute table
that the company can buy to satisfy the supply requirement, but is too expensive to include in the optimal solution.
Thus, when X1 = 0, A3 – S3 = 2, and A3 = 2. (Why is S3 = 0? Interpret the value of A3 = 2.)
To ensure that the artificial variables do not appear in the optimal solution, they are given very large coefficients in the
objective function for a minimization problem, and very small coefficients for a maximization problem.

The standard form of the LP model is shown below:

Minimize: Z = 800X1 + 320X2 + 0S1 + 0S2 +0S3+ 1000A3 + 0S4 + 1000A4
Subject to: 4X1 + 2X2 + S1 = 60 constraint 1
2X1 + 4X2 + S2 = 48 constraint 2
X1 + A3 - S3 = 2 constraint 3
X2 + A 4 - S4 = 4 constraint 4
X1, X2, S1, S2, A3, A4, S3, S4≥ 0
Since the solution always starts at the origin, where all decision variables are equal to zero, only the slack and artificial
variables will be basic in the first iteration.

Note: For a ≥ constraint, add an artificial variable and subtract the surplus variable before changing it into an equation.

Iteration 1
Cj 800 320 0 0 1000 0 1000 0
Basic Quantity X1 X2 S1 S2 A3 S3 A4 S4 Ratios
0 S1 60 4 2 1 0 0 0 0 0 30
0 S2 48 2 4 0 1 0 0 0 0 12
1000 A3 2 1 0 0 0 1 -1 0 0 -
1000 A4 4 0 1 0 0 0 0 1 -1 4
Zj 6000 1000 1000 0 0 1000 -1000 1000 -1000

MTH 242/HANDOUT 2/CSMJACOB | 13

Cj - Zj -200 -680 0 0 0 1000 0 1000

The optimal/entering column is the one that contains the most negative value, that is, the variable whose introduction
to the solution will decrease costs most rapidly.

The optimal column in the initial tableau above is the X 2 column (Cj - Zj = -680), and the replaced row will be theA 2 row
(ratio of Qty column and intersectional element = 4/1 = 4).

Iteration 2
Cj 800 320 0 0 1000 0 1000 0
Basic Quantity X1 X2 S1 S2 A3 S3 A4 S4 Ratios
0 S1 52 4 0 1 0 0 0 -2 2 13
0 S2 40 2 0 0 1 0 0 -4 4 20
1000 A3 2 1 0 0 0 1 -1 0 0 2
320 X2 4 0 1 0 0 0 0 1 -1 -
Zj 3280 1000 320 0 0 1000 -1000 320 -320
Cj – Zj -200 0 0 0 0 1000 680 320

Iteration 3
Cj 800 320 0 0 1000 0 1000 0
Basic Quantity X1 X2 S1 S2 A3 S3 A4 S4 Ratios
0 S1 44 0 0 1 0 -4 4 -2 2 13
0 S2 36 0 0 0 1 -2 2 -4 4 20
800 X1 2 1 0 0 0 1 -1 0 0 2
320 X2 4 0 1 0 0 0 0 1 -1 -
Zj 2880 800 320 0 0 800 -800 320 -320
Cj – Zj 0 0 0 0 200 800 680 320

The above solution is optimal since the net profit row contains no more negative coefficients. Thus, the optimal
decision is to manufacture 2 tables and 4 chairs for a minimum cost of P2,880. (Interpret the values of S 1 and S2) .

PROBLEMS:
1. A steel producer makes two types of steel: regular and special steel. A ton of regular steel requires 2 hours in the
open-hearth furnace and 3 hours in the soaking pit. A ton of special steel requires 2 hours in the open-hearth furnace
and 5 hours in the soaking pit. The open-hearth furnace is available 8 hours per day and the soaking pit is available 15
hours per day. The profit on a ton of regular steel is P40,000 and it is P60,000 on a ton of special steel. Determine how
many tons of each type of steel should be made daily to maximize the profit, considering that demand on regular steel
is at least 1 ton per day.

2. A television producer designs a program that will include a comedy portion and advertisement. The advertiser insists
on at least 15 minutes of advertising time. The producer insists on no more than 25 minutes of advertisement. The
comedian insists on at least 70 minutes of the comedy portion. The total time allotted for the comedy and
advertisement cannot exceed 2 hours. If it has been determined that each minute of advertising attracts one million
viewers and each minute of the comedy program attracts two million viewers, how many minutes should be given to
each of the comedy and advertisement in order to maximize the number of viewers?

3. The Latex Manufacturing Company produces aluminum frying pans and casserole dishes. Each frying pan and each
casserole dish requires 40 ounces of aluminum. The company’s daily supply of aluminum is limited to 560 ounces.
Each frying pan requires 20 minutes on the casting machine and each casserole dish requires 40 minutes on the
casting machine. The casting machine is available for 400 minutes daily. Each frying pan requires an insulated handle
MTH 242/HANDOUT 2/CSMJACOB | 14
and only 12 of these are available each day. Each casserole dish requires two special pick-up handles and only 16 of
these are available daily. Each frying pan contributes P250 to profit and each casserole dish contributes P200. The
objective is to find the number of casserole dishes and frying pans to manufacture daily in order to maximize profit.

4. A poultry raiser wants to mix two types of grains: A and B. Each unit of grain A costs P400 and contains 29 grams of
fat, 10 grams of protein, and 800 calories. Each unit of grain B costs P480 and contains 3o grams of fat, 30 grams of
protein and 600 calories. Suppose that the poultry raiser wants each unit of the final product to yield at least 180
grams of fat, at least 120 grams of protein, and at least 4800 calories. How many units of each type of grain should the
poultry raiser use to minimize his cost?

5. A trust fund is planning to invest up to P600,000 in two types of bonds: A and B. The preferred stock carries a dividend
of 25%, and B 20%. Suppose the fund rules state that no more than P400,000 may be invested in bond B, while at least
P150,000 must be invested in bond A, how much should be invested in each type of bond to maximize the fund’s
return?

6. Angeline’s Snack Center makes ice milk and ice cream daily. Each quart of ice milk requires 0.2 quart of milk and 0.1
quart of cream, while each quart of ice cream requires 0.1 quart of milk and 0.2 quart of cream. The store has 5 quarts
of milk and 7 quarts of cream each day. Assuming that it can sell all ice cream and ice milk on stock daily, how many
quarts of ice cream and ice milk are to be made if a quart of ice milk gives 160 profit and a quart of ice cream gives
200, to realize a maximum profit?

7. Two machines A and B produce items at the rate of 500 per hour and 400 per hour, respectively. The production plan
indicates that the total items to be produced by the two machines must number at least 10,000. The total number of
hours that the two machines can be run is at most 24. Running machine A costs P300 per hour, while running machine
B costs P450 per hour. How many hours should each machine be used to satisfy the production requirements, and at
the same time, minimize the cost of operation?

8. In order to ensure optimal health (and thus accurate test results), a lab technician needs to feed the rabbits a daily
diet containing a minimum of 24 grams (g) of fat, 36 g of carbohydrates, and 4 g of protein. But the rabbits should be
fed no more than five ounces of food a day. Rather than order rabbit food that is custom-blended, it is cheaper to
order Food X and Food Y, and blend them for an optimal mix. Food X contains 8 g of fat, 12 g of carbohydrates, and 2 g
of protein per ounce, and costs P8.00 per ounce. Food Y contains 12 g of fat, 12 g of carbohydrates, and 1 g of protein
per ounce, at a cost of P12.00 per ounce. What is the optimal blend?

9. You have P480,000 to invest, and three different funds from which to choose. The municipal bond fund has a 7%
return, the local bank's CDs have an 8% return, and the high-risk account has an expected (hoped-for) 12% return. To
minimize risk, you decide not to invest any more than P80,000 in the high-risk account. For tax reasons, you need to
invest at least three times as much in the municipal bonds as in the bank CDs. Assuming the year-end yields are as
expected, what are the optimal investment amounts?

10. A tennis-playing golfer has $15 to spend on golf balls (x) costing $1 each and tennis balls (y) costing 60 c each. He
must buy at least 16 altogether and he must buy more golf balls than tennis balls. (a) What is the greatest number of
balls he can buy? (b) After using them, he can sell golf balls for 10c each and tennis balls for 20 c each. What is his
maximum possible income from sales?

11. A man has a spare time job spraying cars and vans. Vans take 2 hours each and cars take 1 hour each. He has 14
hours available per week. He has an agreement with one firm to do 2 of their vans every week. Apart from that he has
no fixed work. His permission to use his back garden contains the clause that he must do at least twice as many cars as
vans. Let x be the number of vans sprayed each week. Let y be the number of cars sprayed each week.
(a) Write down three inequalities which must be satisfied
(b) Draw a graph and use it to list all possible combinations of vehicles which he can spray each week.
MTH 242/HANDOUT 2/CSMJACOB | 15
12. A travel agent has to fly 1000 people and 35000 kg of baggage from London to Paris. Two types of aircraft are
available: A which takes 100 people and 2000 kg of baggage, or B which takes 60 people and 3000 kg of baggage. He
can use no more than 16 aircrafts altogether.
(a) What is the smallest number of aircraft he could use?
(b) If the hire charge for each aircraft A is $10000 and for each aircraft B is $12000, find the cheapest option available to
him.
(c) If the hire charges are altered so that each A costs $10000 and each B costs $20000, find the cheapest option now
available to him.

13. A farmer needs to buy up to 25 cows for a new herd. He can buy either brown cows (x) at $50 each or black cows (y)
at $80 each and he can spend a total of no more than $1600. He must have at least 9 of each type. On selling the cows
he makes a profit of $50 on each brown cow and $60 on each black cow. How many of each sort should he buy for
maximum profit?

14. A transport company has two types of trucks, Type A and Type B. Type A has a refrigerated Capacity of 20 m 3 and a
non-refrigerated capacity of 40 m3 while Type B has the same overall volume with equal sections for refrigerated and
non-refrigerated stock. A grocer needs to hire trucks for the transport of 3000 m 3 of refrigerated stock and 4000 m 3 of
non-refrigerated stock. The cost per kilometer of a Type A is $30, and $40 for Type B. How many trucks of each type
should the grocer rent to achieve the minimum total cost?

15. A school is preparing a trip for 400 students. The company who is providing the transportation has 10 buses of 50
seats each and 8 buses of 40 seats, but only has 9 drivers available. The rental cost for a large bus is $800 and $600 for
the small bus. Calculate how many buses of each type should be used for the trip for the least possible cost.

16. A store wants to liquidate 200 of its shirts and 100 pairs of pants from last season. They have decided to put
together two offers, A and B. Offer A is a package of one shirt and a pair of pants which will sell for $30. Offer B is a
package of three shirts and a pair of pants, which will sell for $50. The store does not want to sell less than 20
packages of Offer A and less than 10 of Offer B. How many packages of each do they have to sell to maximize the
money generated from the promotion?

MTH 242/HANDOUT 2/CSMJACOB | 16