Management Science Finally, the method indicates when the

optimum solution has been reached.

by
 Most real-life linear programming
Asst. Prof. Sami Fethi
problems have more than two variables, so
Chapter Topics a procedure called the simplex method is
used to solve such problems. This
 Simplex Method
procedure solves the problem in an iterative
 Characteristics of Simplex Method
manner, that is, repeating the same set of
 Why we should study the Simplex Method? procedures time after time until an optimal
 Summary of the Simplex Method solution is reached. Each iteration brings a
 Examples solved by conducting tabular higher value for the objective function so
method that we are always moving closer to the
SIMPLEX METHOD optimal solution.

Linear programming models could be solved  The simplex method requires simple
algebraically. The most widely used algebraic mathematical operations (addition,
procedure for solving linear programming problem subtraction, multiplication, and division),
is called the Simplex Method. The simplex method but the computations are lengthy and
is a general-purpose linear-programming algorithm tedious, and the slightest error can lead to a
widely used to solve large scale problems. good deal of frustration. For these reasons,
Although it lacks the intuitive appeal of the most users of the technique rely on
graphical approach, its ability to handle problems computers to handle the computations
with more than two decision variables makes it while they concentrate on the solutions.
extremely valuable for solving problems often Still, some familiarity with manual
encountered in production/operations management. computations is helpful in understanding
Thus simplex method offers an efficient means of the simplex process. The student will
solving more complex linear programming discover that it is better not to use his/her
problems. calculator in working through these
problems because rounding can easily
Characteristics of Simplex Method distort the results. Instead, it is better to
 In the simplex method, the computational work with numbers in fractional form.
routine is an iterative process. To iterate Why we should study the Simplex Method?
means to repeat; hence, in working toward
the optimum solution, the computational • It is important to understand the ideas used
routine is repeated over and over, following to produce solution. The simplex approach
a standard pattern. yields not only the optimal solution to the
 Successive solutions are developed in a xi variables, and the maximum profit (or
systematic pattern until the best solution is minimum cost) but valuable economic
reached. information as well.
 Each new solution will yield a value of the • To be able to use computers successfully
objective function as large as or larger than and to interpret LP computer print outs, we
the previous solution. This important need to know what the simplex method is
feature assures us that we are always doing and why.
moving closer to the optimum answer.
 • We begin by solving a maximization Each chair requires 2 hours in assembly and 4
problem using the simplex method. We hours in finishing. Profit is $8 per table and $6 per
then tackle a minimization problem. chair.
SUMMARY OF THE SIMPLEX METHOD
Step 1. Formulate a LP model of the problem.
Step 2. Add slack variables to each constraint to
obtain standard form.
Tabular solution for Example 1/1
Step 3. Set up the initial simplex tableau.
Step 4. Choose the nonbasic variable with the
largest entry in the net evaluation row
(Cj – Zj) to bring into the basis. This
identifies the pivot (key) column; the column
associated with the incoming variable.
Step 5. Choose as the pivot row that row with the
smallest ratio of “bi/ aij”, for aij >0
where j is the pivot column. This identifies
the pivot row, the row of the variable leaving
the basis when variable j enters.
Step 6. a). Divide each element of the pivot row
by the pivot element.
b). According to the entering variable, find
the new values for remaining variables. Tabular solution for Example 1/2
Step 7. Test for optimality. If Cj – Zj  0 for all
columns, we have the optimal
solution. If not, return to step 4.
Example 1
A Furniture Ltd., wants to determine the most
profitable combination of products to manufacture
given that its resources are limited. The Furniture
Ltd., makes two products, tables and chairs, which
must be processed through assembly and finishing
departments. Assembly has 60 hours available;
Finishing can handle up to 48 hours of work.
Manufacturing one table requires 4 hours in
assembly and 2 hours in finishing.
Tabular solution for Example 1/3

Tabular solution for Example 1/6

Tabular solution for Example 1/4

Tabular solution for Example 1/7

Tabular solution for Example 1/5

Tabular solution for Example 1/8 Cutting & dyeing dept 630 hrs
Sewing dept 600 hrs
Finishing 708 hrs
Inspection & packaging 135 hrs
The company’s problem is to determine how many
standard and deluxe bags should be produced in
the next 3 months?

Example 2
PAR Inc. produces golf equipment and decided to
move into the market for standard and deluxe golf Tabular solution for Example 2/1
bags. Each golf bag requires the following
operations:
Cutting and dyeing the material,
Sewing,
Finishing (inserting umbrella holder, club
separators etc.),
Inspection and packaging.
Each standard golf-bag will require 7/10 hr. in the
cutting and dyeing department, 1/2 hr. in the Tabular solution for Example 2/2
sewing department, 1 hr. in the finishing
department and 1/10 hr. in the inspection &
packaging department.
Deluxe model will require 1 hr. in the cutting and
dyeing department, 5/6 hr. for sewing, 2/3 hr. for
finishing and 1/4 hr. for inspection and packaging
The profit contribution for every standard bag is
10 MU and for every deluxe bag is 9 MU.
In addition the total hours available during the
next 3 months are as follows:
Tabular solution for Example 2/3 The deskpro generates a profit contribution of
$50/unit, and portable generates a profit
contribution of $40/unit. For next week’s
production, a max of 150 hours of assembly time
is available. Each unit of deskpro requires 3 hours
of assembly time. And each unit of portable
requires 5 hours of assembly time.
High Tech currently has only 20 portable display
components in inventory; thus no more than 20
units of portable may be assembled. Only 300 sq.
feet of warehouse space can be made available for
new production. Assembly of each Deskpro
Tabular solution for Example 2/4 requires 8 sq. ft. of warehouse space, and each
Portable requires 5 sq. ft. of warehouse space.

Tabular solution for Example 3/1

Tabular solution for Example 2/5

Tabular solution for Example 3/2

Example 3
High Tech industries import components for
production of two different models of personal
computers, called deskpro and portable. High
Tech’s management is currently interested in
developing a weekly production schedule for both
products.
Tabular solution for Example 3/3  Thus,
Objective Function Max Z = 50X1 + 40X2
Subjective to: 3 X1 + 5 X2  150 Assembly time
 1X1  20 Portable display
 8X1 + 5 X2  300 Warehouse space
 1X1 + 1X2  25 Min. total production
 X1 , X2  0
Tabular solution for Example 4/2
 First, we use three slack variables and one
surplus variable to write the problem in std.
Form.
 Max Z = 50X1 + 40X2 + 0S1 + 0S2 +
0S3 + 0S4
Subject to 3X1 + 5X2 + 1S1 = 150
 1X2 + 1S2 = 20
 8X1 + 5X2 + 1S3 = 300
 1X1 + 1X2 - 1S4 = 25
 All variables  0
 For the initial tableau X1 = 0 X2 = 0
 S1= 150 S2 = 20
 S3 = 300 S4 = -25
Tabular solution for Example 4/3
Tableau Form : The Special Case
 Clearly this is not a basic feasible solution
 Obtaining tableau form is somewhat more since
complex if the LP contains  constraints, =
S4 = -25 violates the nonnegativity
constraints, and/or “-ve” right-hand-side
requirement.
values. Here we will explain how to
develop tableau form for each of these  We introduce new variable called ARTIFICIAL
situations. VARIABLE.
Tabular solution for Example 4/1  Artificial variables will be eliminated
before the optimal solution is reached. We
 Suppose that in the high-tech industries
assign a very large cost to the variable in
problem, management wanted to ensure
the objective function.
that the combined total production for both
models would be at least 25 units.  Objective function
50X1 + 40X2 + 0S1 + 0S2 + 0S3 + 0S4 - MA4
Tabular solution for Example 4/4

Tabular solution for Example 4/7

 IMPORTANT!!
 Since A4 is an artificial variable that was
added simply to obtain an initial basic
feasible solution, we can drop its associated
Tabular solution for Example 4/5 column from the simplex tableau.
 Indeed whenever artificial variables are
used, they can be dropped from the simplex
tableau as soon as they have been
eliminated from the basic feasible solution.
Tabular solution for Example 4/8

Tabular solution for Example 4/6

Tabular solution for Example 4/9 6X1 + 4X2 - 5X3 = 30 6X1 + 4X2 -
5X3 + 1A1 = 30
 One of the properties of the tableau form of
a linear program is that the values on the
right-hand sides of the constraints have to
be nonnegative.
 e.g. # of units of the portable model
(X2) has to be less than or equal to the # of
units of the deskpro model (X1) after
setting aside 5 units of the deskpro for
internal company use.
X2  X1 - 5
 - X1 + X2  -5
(Min)Multiply by –1  (Max) X1 - X2  5
One more iteration is required. This time X2
comes into the solution and S1 is eliminated.  We now have an acceptable nonnegative
After performing this iteration, the following right-hand-side value. Tableau form for this
simplex tableau shows that the optimal solution constraint can now be obtained by
has been reached. subtracting a surplus variable and adding an
artificial variable.
Tabular solution for Example 4/10
Tabular solution for Example 5/1
 Livestock Nutrition Co. produces specially
blended feed supplements. LNC currently
has an order for 200 kgs of its mixture.
 This consists of two ingredients
X1 ( a protein source )
X2 ( a carbohydrate source )
 The first ingredient, X1 costs LNC 3MU a
kg. The second ingredient, X2 costs LNC
8MU a kg. The mixture can’t be more than
40% X1 and it must be at least 30% X2.
 LNC’s problem is to determine how much
EQUALITY CONTRAINTS of each ingredient to use to minimize cost.
NEGATIVE RIGHT-HAND SIDE VALUES Tabular solution for Example 5/2
Simply add an artificial variable A1 to create a  The cost function can be written as
basic feasible solution in the initial simplex
tableau. Cost = 3X1 + 8X2 Min!
 LNC must produce 200 kgs of the mixture
– no more, no less.
 X1 + X2 = 200 kgs Tabular solution for Example 5/5
 The mixture can’t be more than 40% X1, so Minimize : Cost = 3X1 + 8X2 + 0S1 + 0S2
we may use less than 80 kgs. (40% X 200 = + MA1 + MA2
80). However, we must not exceed 80 kgs.
Subject to : X1 + X2 + A1 = 200
X1  80 kgs
X1 + S1 = 80
 The mixture must be at least 30% X2. Thus
X2 - S2 + A2 = 60
we may use more than 60 kgs, not less than
60 kgs. (30% X 200 = 60) All variables  0
 X2  60 kgs Tabular solution for Example 5/6
Tabular solution for Example 5/3
Minimize : Cost = 3MU X1 + 8MU X2
Subject to X1 + X2 = 200 kgs
X1  80 kgs
X2  60 kgs
X1 , X2  0
 An initial solution: X1 + X2 = 200 kgs
 X1 + X2 + A1 = 200
Artificial variable : A very expensive substance
must not be represented in optimal solution.
Tabular solution for Example 5/4 Tabular solution for Example 5/7
 An artificial Variable is only of value as a
computational device; it allows 2 types of
restrictions to be treated.
 The equality type
  type
X1  80 kgs constraint on protein
 X1 + S1 = 80 kgs
X2  60 kgs constraint on carbohydrates
 X2 - S2 + A2 = 60
X1 , X2 , S1, S2, A1, A2  0
   
0MU 0MU M M
Tabular solution for Example 5/8

Tabular solution for Example 5/11

Tabular solution for Example 5/9

Tabular solution for Example 5/12

Tabular solution for Example 5/10