Operations Research

Dr. Sarat K Jena

Tour decision
Imagine that you have a 5 week business commitment between Goa and
Mumbai. You will fly out of Goa on Mondays and return on
Wednesdays. A regular round-trip ticket cost Rs.8000, but a 20%
discount is granted if the round-trip dates span weekend. A one way
ticket in either direction costs 75% of the regular price. How should you
buy the tickets for the 5-week period?
We look at the situation

• What are the decision alternatives?

• Under what restrictions is the decision made?

• What is an appropriate objective criterion for evaluating the

alternatives?
Three plausible alternatives
• Buy five regular Goa-Mum-Goa for departure on Monday and return
on Wednesday of the same week.
cost=5*8000=40,000
• Buy one Goa-Mumbai, four Mum-Goa-Mub that span weekends, and
one Mum-Goa.
Cost = .75*8000 + 4(.8*8000)+.75*8000=37,600
• Buy one Goa-Mum-Goa to cover Monday of the first week and
Wednesday of the last week and four Mum-Goa-Mum to cover the
remaining legs. All tickets in this alternative span at least one
weekend.
Cost=5*(.8*8000)=32,000
Question arises
• How each component is developed?
• How the resulting model is solved?

Consider forming a maximum-area rectangle out of piece of wire length

L inches. What should be the best width and height of the rectangle?

Here, the number of alternatives are not finite. Because the width and
height of the rectangular can assume an infinite number of values.

w = Width of the rectangular

h = height of the rectangular in inches
• Restriction: 1. Width of the rectangular+ height of the rectangle=Half
the length of the wire. 2. Width and height cannot be negative.
Algebraically, we can define
• 2(w+h)=L
• w ≥0, h ≥ 0
Our question is to maximize the are(z)
Maximize z= wh
subject to
2(w+h)=L
w, h ≥ 0
Nurse allocation

• Nurse scheduling is multi-objective problem. Systematic approach for

nurse allocation is needed to ensure continuous and adequate level of
patient care services while maintaining the legislative requirements as
well as internal policies. This problem becomes complex when
addition factors such as patient admission, nurse qualification or
license to practice, type of disease as well unforeseen accidents.
The personal needs of the nurses such as vacation or work shift
preferences add a new dimension to the scheduling problem. The need
to balance all the various dimension of the problem makes nurse
scheduling a particularly daunting manual task.
There are various grades of nurses ranging from registered nurse to junior
nurse. Some the nurses might be trained to manage certain medical
conditions or skilled in certain area such as intensive care. Due to the
varied trainings and specializations, certain type of nurses has to be staffed
for wards requiring those skills. These varied conditions cause manual
nurse scheduling to consume a significant amount of time. Even when the
schedule has been planned manually, it does not necessarily guarantee the
fairness of distribution of work such as the number of night shifts or
weekend shifts. While the nurses might have indicated their preferences,
the planner might not have taken all these into consideration resulting in
poorly designed schedules which has to be modified by the nurses
swapping duties or working under undesired conditions. Occasionally, the
plans did not attempt to efficiently utilize the manpower properly.
 What is operations research?
• Operations research is a scientific approach to decision making, which seeks to
determine how best to design and operate a system, under the condition requiring
the allocation of scarce resources.

• Extensive applications in Engineering, business and public system

• It was invented/originated during world war II, when British military asked
scientists and mathematicians to analyse the military problems and also to optimize
the loading of cargo on ships and planes and to manage other critical resources.

• Today it is called Management Science

 Solving the model
The most prominent OR techniques are
• Linear programming
• Integer programming
• Dynamic programming
• Network programming
• Nonlinear programming
 Linear programming
•Linear Programming consists of the two words
• Linear : it is used to describe the relationships between variables which are
directly proportional
• Programming: It means planning of activities in a manner that achieves
some optimal result with available resources.
•Linear programming indicates the planning of decision variables which are
directly proportional to achieve the optimal result considering the limitations
within which the problem to be sold.
•Decision variable: It refers to the economic or physical quantities which are
competing with one another for sharing the given limited resources.
• The linear model consists of the following components:
• A set of decision variables.
• An objective function.
• A set of constraints.

• The Importance of Linear Programming

• Many real world problems lend themselves to linear programming modeling.
• Many real world problems can be approximated by linear models.
• There are well-known successful applications in:
• Manufacturing
• Marketing
• Finance (investment)
• Advertising
• Agriculture
Assumptions of linear programming
• Non-negativity restriction: All decision variables must take on
values equal or greater than zero
• Divisibility: The numerical values are continuous
• Proportionality: The effect of a decision variable in any one
equation is proportional to a constant quantity.
• Certainty: All models are known constant
• Additivity: The combined effect of the decision variables in any
one equation is the algebraic sum of their individual
weighted effects
 The Linear Programming Model
Let: X1, X2, X3, ………, Xn = decision variables
Z = Objective function or linear function
Requirement: Maximization of the linear function Z.
Z = c1X1 + c2X2 + c3X3 + ………+ cnXn …..Eq (1)
subject to the following constraints:

where aij, bi, and cj are given constants.

.
Contd.
The linear programming model can be written in more efficient notation as:

The decision variables, xI, x2, ..., xn, represent levels of n competing activities.
 Examples of LP Problems

1. A Product Mix Problem

• A manufacturer has fixed amounts of different resources such as raw
material, labor, and equipment.
• These resources can be combined to produce any one of several different
products.
• The quantity of the ith resource required to produce one unit of the jth
product is known.
• The decision maker wishes to produce the combination of products that
will maximize total income.
2. A Blending Problem
• Blending problems refer to situations in which a number of components (or
commodities) are mixed together to yield one or more products.
• Typically, different commodities are to be purchased. Each commodity has
known characteristics and costs.
• The problem is to determine how much of each commodity should be
purchased and blended with the rest so that the characteristics of the mixture
lie within specified bounds and the total cost is minimized.
 3. A Production Scheduling Problem

• A manufacturer knows that he must supply a given number of items of a

certain product each month for the next n months.
• They can be produced either in regular time, subject to a maximum each
month, or in overtime. The cost of producing an item during overtime is
greater than during regular time. A storage cost is associated with each item
not sold at the end of the month.
• The problem is to determine the production schedule that minimizes the sum
of production and storage costs.
4. A Transportation Problem

• A product is to be shipped in the amounts al, a2, ..., am from m shipping

origins and received in amounts bl, b2, ..., bn at each of n shipping
destinations.
• The cost of shipping a unit from the ith origin to the jth destination is
known for all combinations of origins and destinations.
• The problem is to determine the amount to be shipped from each origin
to each destination such that the total cost of transportation is a
minimum.
 Developing LP Model
• The variety of situations to which linear programming has been
applied ranges from agriculture to zinc smelting.

• Steps Involved:
• Determine the objective of the problem and describe it by a
criterion function in terms of the decision variables.
• Find out the constraints.
• Do the analysis which should lead to the selection of values for the
decision variables that optimize the criterion function while
satisfying all the constraints imposed on the problem.
Example: Product Mix Problem
The N. Dustrious Company produces two products: I and II. The raw
material requirements, space needed for storage, production rates, and
selling prices for these products are given in Table 1.

The total amount of raw material available per day for both products is 15751b. The
total storage space for all products is 1500 ft2, and a maximum of 7 hours per day can
be used for production.
Example Problem
All products manufactured are shipped out of the storage area at the end of the day.
Therefore, the two products must share the total raw material, storage space, and production
time. The company wants to determine how many units of each product to produce per
day to maximize its total income.

Solution
• The company has decided that it wants to maximize its sale income, which depends on
the number of units of product I and II that it produces.
• Therefore, the decision variables, x1 and x2 can be the number of units of products I and
II, respectively, produced per day.
• The object is to maximize the equation:
Z = 13x1 + 11x2
subject to the constraints on storage space, raw materials, and production time.
• Each unit of product I requires 4 ft2 of storage space and each unit of product II requires 5 ft2. Thus a
total of 4x1 + 5x2 ft2 of storage space is needed each day. This space must be less than or equal to the
available storage space, which is 1500 ft2. Therefore,
4X1 + 5X2  1500
• Similarly, each unit of product I and II produced requires 5 and 3 1bs, respectively, of raw material.
Hence a total of 5xl + 3x2 Ib of raw material is used.
• This must be less than or equal to the total amount of raw material available, which is 1575 Ib.
Therefore,
5x1 + 3x2  1575
• Product A can be produced at the rate of 60 units per hour. Therefore, it must take1
minute or 1/60 of an hour to produce I unit. Similarly, it requires 1/30 of an hour to
produce 1 unit of product B. Hence a total of x1/60 + x2/30 hours is required for the daily
production. This quantity must be less than or equal to the total production time
available each day. Therefore,
x1 / 60 + x2 / 30  7
or x1 + 2x2  420

• Finally, the company cannot produce a negative quantity of any product, therefore x1
and x2 must each be greater than or equal to zero.
• The linear programming model for this example can be summarized as:
Graphical Solution to LP Problems
 Question

A company makes two kinds of leather belts. Belt A is a high quality belt,
and belt B is of lower quality. The respective profits are Re. 0.40 and Re.
0.30 per belt. Each belt of type A requires twice as much time as a belt of
type B, and if all belts were of type B, the company could make 1,000 per
day. The supply of leather is sufficient for only 800 belts per day (both A
and B combined). Belt A requires a fancy buckle, and only 400 per day are
available. There are only 700 buckles a day available for belt B.

What should be the daily production of each type of belt? Formulate the
linear programming problem.
• Let x1 = Number of Belt A to be produced
• x2 = Number of Belt B to be produced Since the objective is to maximize the
profit,
• the objective function is given by —
Maximize Z = .40x1 + .30x2
Subject to constraints:
2x1 + x2 ≤ 1000 (Total availability of time)
x1 + x2 ≤ 800 (Total availability of leather)
x1 ≤ 400 (Availability of buckles for belt A)
x2 ≤ 700 (Availability of buckles for belt B)
x1, x2 ≥ 0 (Non-negativity constraint)
Question

A publisher of textbooks is in the process of presenting a new book to the

market. The book may be bound by either cloth or hard paper. Each cloth
bound book sold contributes Rs. 24, and each paper-bound book contributes
Rs. 23. It takes 10 minutes to bind a cloth cover, and 9 minutes to bind a
paperback. The total available time for binding is 800 hours. After
considerable market survey, it is predicted that the cloth-cover sales will
exceed at least 10,000 copies, but the paperback sales will be not more than
6,000 copies. Formulate the problem as a LP problem.
 Solution
• Let x1 = Number of books bound by cloth
• x2 = Number of books bound by hard paper
• Since the objective is to maximize the profit, the objective function is
given by —
Maximize Z = 24x1 + 23x2
Subject to constraints:
10x1 + 9x2 ≤ 48,000 (Total time available in minutes)
x1 ≥ 10,000 (Minimum sales of cloth-cover books)
x2 ≤ 6,000 (Maximum sales of hard paper books)
x2 ≥ 0 (Non-negativity constraint)
 Question
A manufacture produces three models, I, II, and III, of a certain product
using raw materials A and B. The following tables gives the data for the
problem:
Requirements per unit
R/M I II III Availability
A 2 3 5 4000
B 4 2 7 6000
Minimum demand 200 200 150
Price per unit($) 30 20 50

The labour time per unit of model I is twice that of II and three times of III.
The entire labour force of the factory can produce the equivalent of 1500
units I. Market requirements specify the ratios 3:2:5 for the production of
the three respective models. Formulate the problems as a linear program.
 Some Examples
• A garment manufacturer has a production line making two styles of shirts, Style I
requires 200 grams of cotton thread, 300 grams of Dacron thread, and 300 grams of
linen thread. Style II requires 200grams of cotton thread, 200 grams of Dacron thread
and 100 grams of linen thread. The manufacturer makes a net profit of Rs.19.50 on
style I, Rs.15.90 on Style II. He has in hand an inventory of 24 kg of cotton thread, 26
kg of Dacron thread and 22 kg of linen thread. His immediate problem is to determine
a production schedule, given the current inventory to make maximum profit.
Formulate the LPP model
• A person requires 10,12,& 12 units chemicals A, B,& C respectively for his garden. A
liquid product contains 5, 2 and 4 units of A, B & C respectively per jar. A dry products
contains 1, 2 & 4 units of A, B and C per carton. If the liquid product sells for Rs.3 per
jar and the dry product sells for Rs.2 per carton. How many should be purchased in
order to minimize the cost and meet the requirements. Formulate the LPP model
The Galaxy Industries Production Problem : A Prototype Example
• Galaxy manufactures two toy doll models:
• Space Ray.
• Zapper.
• Resources are limited to
• 1000 pounds of special plastic.
• 40 hours of production time per week.

• Marketing requirement
• Total production cannot exceed 700 dozens.
• Number of dozens of Space Rays cannot exceed number of
dozens of Zappers by more than 350.
• Technological input
– Space Rays requires 2 pounds of plastic and
3 minutes of labor per dozen.
– Zappers requires 1 pound of plastic and
4 minutes of labor per dozen.
• The current production plan calls for:
• Producing as much as possible of the more profitable product, Space Ray ($8
profit per dozen).
• Use resources left over to produce Zappers ($5 profit per dozen), while
remaining within the marketing guidelines.
• The current production plan consists of:
8(450) + 5(100)
Space Rays = 450 dozen
Zapper = 100 dozen
Profit = $4100 per week

Management is seeking a
production schedule that will
increase the company’s profit.
 The Galaxy Linear Programming Model
• Decisions variables:
• X1 = Weekly production level of Space Rays (in dozens)
• X2 = Weekly production level of Zappers (in dozens).

Max 8X1 + 5X2 (Weekly profit)

• Objective Function: subject to
• Weekly profit, to be maximized 2X1 + 1X2 £ 1000 (Plastic)
3X1 + 4X2 £ 2400 (Production Time)
X1 + X2 £ 700 (Total production)
X1 - X2 £ 350 (Mix)
Xj> = 0, j = 1,2 (Non negativity)
The Graphical Analysis of Linear Programming

The set of all points that satisfy all the

constraints of the model is called
a

FEASIBLE REGION
Using a graphical presentation
we can represent all the constraints,
the objective function, and the three
types of feasible points.
 Steps
• Consider any type of inequality constraint(≥ & ≤) as = one.
• Now, draw the line corresponding to equality constraint and
corresponding to x ≥ 0, y≥0 and shade the region corresponding to the
segment in he first quadrant.
• Repeat the steps(1), (2),and(3) above for all the constraints given in the
problem.
• Find the region( in the first quadrant) which is the most common to all
the constraints. The region, if it exists, is the feasible region.
• If either the feasible region is convex and bounded or has a lower
bound(bounded below) then the optimal solution to the problem exists on
at least of the vertices.(Practically, we find all the vertices of the convex
region, evaluate the objective function at these vertices, and pick up the
optimum value and corresponding vertex/vertices).
Graphical Analysis – the Feasible Region

X2

The non-negativity constraints

X1
 Graphical Analysis – the Feasible Region

X2

1000 The Plastic constraint

2X1+X2 £ 1000
700 Total production constraint:
X1+X2 £ 700 (redundant)
500

Infeasible
Production Feasible
Time
3X1+4X2 £ 2400 X1
500 700 800
 Graphical Analysis – the Feasible Region
X2
1000 The Plastic constraint
2X1+X2 £ 1000
700 Total production constraint:
X1+X2 £ 700 (redundant)
500
Infeasible
Production mix
constraint:
Production Feasible X1-X2 £ 350
Time
3X1+4X2£ 2400
X1
500 700
Interior points. Boundary points. Extreme points.
• There are three types of feasible points 40
Solving Graphically for an Optimal Solution
 The search for an optimal solution

X2 Start at some arbitrary profit, say profit = $2,000...

1000 Then increase the profit, if possible...
...and continue until it becomes infeasible

700 Profit=$4360
500

X1
42
500
 Summary of the optimal solution

Space Rays = 320 dozen

Zappers = 360 dozen
Profit = $4360
• This solution utilizes all the plastic and all the production
hours.

• Total production is only 680 (not 700).

• Space Rays production exceeds Zappers production by only

40 dozens.
 Simplex Method
The geometric method of solving linear programming problems
presented before. The graphical method is useful only for problems
involving two/three decision variables and relatively few problem
constraints.

What happens when we need more decision variables and more

problem constraints?

We use an algebraic method called the simplex method, which was

developed by George B. DANTZIG (1914-2005) in 1947 while on
assignment with the U.S. Department of the air force.
The simplex technique involves generating a series of solutions in
tabular form, called tableaus. By inspecting the bottom row of each
tableau, one can immediately tell if it represents the optimal solution.
Each tableau corresponds to a corner point of the feasible solution
space. The first tableau corresponds to the origin. Subsequent tableaus
are developed by shifting to an adjacent corner point in the direction
that yields the highest (smallest) rate of profit (cost). This process
continues as long as a positive (negative) rate of profit (cost) exists.
The key solution concepts
Solution Concept 1: the simplex method focuses on CPF
solutions.
Solution concept 2: the simplex method is an iterative
algorithm (a systematic solution procedure that keeps
repeating a fixed series of steps, called, an iteration, until a
desired result has been obtained) with the following
structure:
Simplex algorithm
Initialization: setup to start iterations, including
finding an initial CPF solution

Optimality test: is the current CPF solution

optimal?

if no if yes stop

Iteration: Perform an iteration to find a

better CFP solution
 Simplex method in tabular form
2. Test for optimality:
Case 1: Maximization problem
the current BF solution is optimal if every coefficient in
the objective function row is nonnegative
Case 2: Minimization problem
the current BF solution is optimal if every coefficient in
the objective function row is nonpositive
 Slack Variables and Surplus Variable
“A mathematical representation of surplus resources.” In real life
problems, it’s unlikely that all resources will be used completely, so there
usually are unused resources.
 Slack variables represent the unused resources between the left-hand
side and right-hand side of each inequality.
 Constraints of type (≤) : for each constraint i of this type, we add a
slack variable si, such that si is nonnegative.
Example: x1 + 2x2 ≤ 10 translates into x1 + 2x2 + s1=10
 Constraints of type (≥) : for each constraint i of this type, we add a
Surplus variable si, such that si is nonnegative.
Example: x1 + 2x2 ≥ 10 translates into x1 + 2x2 - s1=10
 Basic and Nonbasic Variables
Basic variables are selected arbitrarily with the restriction that there be as
many basic variables as there are equations. The remaining variables are
non-basic variables.
x1  2 x2  s1  32
3 x1  4 x2  s2  84

This system has two equations, we can select any two of the four variables
as basic variables. The remaining two variables are then non-basic
variables. A solution found by setting the two non-basic variables equal to
0 and solving for the two basic variables is a basic solution. If a basic
solution has no negative values, it is a basic feasible solution.
To solve a linear programming problem in standard form, use
the following steps.
•   I: Check whether the objective function of the given LPP is to maximized or
Step
minimized. If it is to
be minimized then we convert it into a problem of Maximization
Min Z= -max(-Z)
Step II: Check whether all bi (i= 1, 2, 3,…m) are posistive. If any one of is negative
then multiply the in equation of the constraint by -1 so as to get all to be
positive
Step III: Express the problem in standard form by introducing slack/surplus variables,
to
convert the inequality constraints into equation.
Step IV: Create the initial simplex tableau.
Step V: Select the pivot column(entering variable) :The column with the “most
negative value” element in the last row.
 Step VI: Select the pivot row(leaving variable): The row with the smallest non-negative result when the
last element in the row is divided by the corresponding in the pivot column.)
Step VII: Use elementary row operations calculate new values for the pivot row so that the pivot is 1
(Divide every number in the row by the pivot number.) ( Pivot number: the number in the
intersection of the pivot row and pivot column)
Step VIII: Form a new basis by dropping in the leaving variable and introducing the entering variable
along with the associate value.
So new element= old element
Step X: Stopping the iteration
We stop when we reach the optimality criterion. The simplex algorithm stops when:
there is no negative solution in the last row: basic variables for maximization and there is no
positive in the last row for minimization.
 Simplex method
• Example (All constraints are )
Solve the following problem using the simplex method
• Maximize
Z = 3X1+ 5X2
Subject to
X1  4
2 X2  12
3X1 +2X2  18
X1 , X2  0
 Simplex method
• Solution
• Initialization
1. Standard form
Maximize Z, Sometimes it is called the augmented form of
the problem because the original form has been
Subject to augmented by some supplementary variables
needed to apply the simplex method
Z - 3X1- 5X2 =0

X1 + S1 = 4
2 X2 + S2 = 12
3X1 +2X2 + S3 = 18
X1 , X2, S1, S2, S3  0
 Definitions
• A basic solution is an augmented corner point solution.
• A basic solution has the following properties:
1. Each variable is designated as either a nonbasic variable or a basic variable.
2. The number of basic variables equals the number of functional constraints.
Therefore, the number of nonbasic variables equals the total number of variables
minus the number of functional constraints.
3. The nonbasic variables are set equal to zero.
4. The values of the basic variables are obtained as simultaneous solution of the system
of equations (functional constraints in augmented form). The set of basic variables
are called “basis”
5. If the basic variables satisfy the nonnegativity constraints, the basic solution is a
Basic Feasible (BF) solution.
Initial tableau
Entering
2. Initial tableau variable

Basic X1 X2 S1 S2 S3 RHS
variable
S1 1 0 1 0 0 4
S2 0 2 0 1 0 12
S3 3 2 0 0 1 18
Z -3 -5 0 0 0 0

Leaving Pivot row

Pivot column
variable Pivot
number
 Simplex tableau
Notes:
• The basic feasible solution at the initial tableau is (0, 0,
4, 12, 18) where:
X1 = 0, X2 = 0, S1 = 4, S2 = 12, S3 = 18, and Z = 0
Where S1, S2, and S3 are basic variables
X1 and X2 are nonbasic variables
• The solution at the initial tableau is associated to the
origin point at which all the decision variables are zero.
 Optimality test
• By investigating the last row of the initial tableau, we find that there are
some negative numbers. Therefore, the current solution is not optimal
 Iteration
• Step 1: Determine the entering variable by selecting the variable with the most
negative in the last row.
• From the initial tableau, in the last row (Z row), the coefficient of X1 is -3 and the
coefficient of X2 is -5; therefore, the most negative is -5. consequently, X2 is the
entering variable.
• X2 is surrounded by a box and it is called the pivot column
• Step 2: Determining the leaving variable by using the minimum ratio test as following:
Basic Entering RHS Ratio
variable variable X2
(1) (2) (2)(1)
S1 0 4 None
S2 2 12 6
Leaving Smallest ratio
S3 2 18 9
 Iteration
• Step 3: solving for the new BF solution by using the
eliminatory row operations as following:
1. New pivot row = old pivot row  pivot number

Basic X1 X2 S1 S2 S3 RHS
variable
S1
X2 0 1 0 1/2 0 6
S3
Z
Note that X2 becomes in the basic
variables list instead of S2
 Iteration
2. For the other row apply this rule:
New row = old row – the coefficient of this row in the pivot column × (new pivot row).
For S1 Row
X1 X2 S1 S2 S3 RHS
1 0 1 0 0 4
̶
0 ×(0 1 0 1/2 0 6)
1 0 1 0 0 4
For S3 Row
3 2 0 0 1 18
̶
2 ×(0 1 0 1/2 0 6)
3 0 0 -1 1 6 Substitute this
for Z Row values in the
-3 -5 0 0 0 0 table
̶̶
-5× (0 1 0 1/2 0 6)
 Iteration
This solution is not optimal, since there is a negative numbers in the last row

Basic X1 X2 S1 S2 S3 RHS
variable
S1 1 0 1 0 0 4
X2 0 1 0 1/2 0 6
S3 3 0 0 -1 1 6
Z -3 0 0 5/2 0 30

The smallest ratio is

The most negative
6/3 =2; therefore, S3 is
value; therefore, X1
the leaving variable
is the entering
variable
 Iteration
• Apply the same rules we will obtain this solution:

Basic X1 X2 S1 S2 S3 RHS
variable
S1 0 0 1 1/3 -1/3 2
X2 0 1 0 1/2 0 6
X1 1 0 0 -1/3 1/3 2
Z 0 0 0 3/2 1 36

This solution is optimal; since there is no negative solution in the last row: basic
variables are X1 = 2, X2 = 6 and S1 = 2; the nonbasic variables are S2 = S3 = 0
Z = 36
 Problem 1
The Cannon Hill furniture Company produces tables and chairs.
Each table takes four hours of labor from the carpentry
department and two hours of labor from the finishing department.
Each chair requires three hours of carpentry and one hour of
finishing. During the current week, 240 hours of carpentry time
are available and 100 hours of finishing time. Each table produced
gives a profit of $70 and each chair a profit of $50. How many
chairs and tables should be made?
 STEP 1
All information about example
Resource Table s (x1 ) Chairs (x2 ) Constraints
Carpentry (hr) 4 3 240
Finishing (hr) 2 1 100
Unit Profit $70 $50

Objective Function Z  70 x1  50 x2

Carpentry Constraint 4 x1  3x2  240

Finishing Constraint 2 x1  1x2  100

Non-negativity conditions x1 , x2  0
The first step of the simplex method requires that each inequality be converted into an
equation. ”less than or equal to” inequalities are converted to equations by including
slack variables.
Suppose s1 carpentry hours and s2 finishing hours remain unused in a week. The
constraints become;
or

4 x1  3 x2  s1  240 4 x1  3 x2  s1  0 s2  240
2 x1  x2  s2  100 2 x1  x2  0 s1  s2  100

As unused hours result in no profit, the slack variables can be included in the objective
function with zero coefficients:
Z  70 x1  50 x2  0 s1  0 s2
Z  70 x1  50 x2  0 s1  0 s2  0
 STEP 2
Basic x1 x2 S1 S2
Variables RHS

S1 4 3 1 0 240
S2 2 1 0 1 100
Z -70 -50 0 0 0

The tableau represents the initial solution;

x1  0, x2  0, s1  240, s2  100, Z  0

The slack variables S1 and S2 form the initial solution mix. The initial solution
assumes that all avaliable hours are unused. i.e. The slack variables take the largest
possible values.
 STEP 3
Select the pivot column (determine which variable to enter into the
solution mix). Choose the column with the “most negative”
element in the objective function row.

Right
Basic x1 x2 S1 S2 hand
Variables
side
S1 4 3 1 0 240
S2 2 1 0 1 100
Z -70 -50 0 0 0

Pivot column
x1 should enter into the solution mix because each unit of x1 (a table) contributes a
profit of $70 compared with only $50 for each unit of x1 (a chair)
STEP 5
Select the pivot row (determine which variable to replace in the solution mix).
Divide the last element in each row by the corresponding element in the
pivot column. The pivot row is the row with the smallest non-negative
result.
Enter

Basic x1 x2 S1 S2
Variables RHS

S1 4 3 1 0 240 240 / 4  60

Leaving S2 2 1 0 1 100 100 / 2  50

Z -70 -50 0 0 0
Pivot row
Pivot
column
Pivot number
Should be replaced by x1 in the solution mix. 60 tables can be
made with 240 unused carpentry hours but only 50 tables can
be made with 100 finishing hours. Therefore we decide to make
50 tables.
Now calculate new values for the pivot row. Divide every
number in the row by the pivot number.

Basic x1 x2 S1 S2 Right hand

Variables side

S1
x1 1 1/2 0 1/2 50 R2
2
Z
Use row operations to make all numbers in the pivot column
equal to 0 except for the pivot number which remains as 1.

Right
Basic x1 x2 S1 S2 hand
Variables
side
S1 0 1 1 -2 40
x1 1 1/2 0 1/2 50
Z 0 -15 0 35 3500

If 50 tables are made, then the unused carpentry hours are reduced
by 200 hours (4 h/table multiplied by 50 tables); the value changes
from 240 hours to 40 hours. Making 50 tables results in the profit
being increased by $3500; the value changes from $0 to $3500.
 In this case, x1  50, x2  0, s1  40, s2  0, Z  3500
Now repeat the steps until there are no negative numbers in the last row.

Select the new pivot column. x2 should enter into the solution mix.
Select the new pivot row. S1 should be replaced by x2 in the solution mix.
Enter

Right
Basic x1 x2 S1 S2 hand
Variables
side
Exit S1 0 1 1 -2 40 40 /1  40
x1 1 1/2 0 1/2 50 50 / 0,5  100

P 0 -15 0 35 3500
New pivot
New pivot row
column
Calculate new values for the pivot row. As the pivot number is already 1,
there is no need to calculate new values for the pivot row.

Use row operations to make all numbers in the pivot column equal to
except for the pivot number.

Basic Right
x1 x2 S1 S2 hand
Variables side
x2 0 1 1 -2 40
x1 1 0 -1/2 3/2 30
Z 0 0 15 5 4100
If 40 chairs are made, then the number of tables are reduced by 20 tables (1/2
table/chair multiplied by 40 chairs); the value changes from 50 tables to 30 tables.
The replacement of 20 tables by 40 chairs results in the profit being increased by
$600; the value changes from $3500 to $4100.

As the last row contains no negative numbers, this solution gives the maximum value
of P.
 Result

This simplex tableau represents the optimal solution to the LP problem and
is interpreted as:
and profit or Z=$4100
x1  30, x2  40, s1  0, s2  0
The optimal solution (maximum profit to be made) is to company 30 tables
and 40 chairs for a profit of $4100.
Special cases of linear programming
• Infeasible solution
• Multiple solution (infinitely many solution)
• Unbounded solution
• Degenerated solution
 Notes on the Simplex tableau
1. In any Simplex tableau, the intersection of any basic variable with itself is always one and the
rest of the column is zeroes.
2. In any simplex tableau, the objective function row (Z row) is always in terms of the nonbasic
variables. This means that under any basic variable (in any tableau) there is a zero in the Z
row. For the non basic there is no condition ( it can take any value in this row).
3. If there is a zero under one or more nonbasic variables in the last tableau (optimal solution
tableau), then there is a multiple optimal solution.
4. When determining the leaving variable of any tableau, if there is no positive ratio (all the
entries in the pivot column are negative and zeroes), then the solution is unbounded.
5. If there is a tie (more than one variables have the same most negative or positive) in
determining the entering variable, choose any variable to be the entering one.
6. If there is a tie in determining the leaving variable, choose any one to be the leaving variable.
In this case a zero will appear in RHS column; therefore, a “cycle” will occur, this means that
the value of the objective function will be the same for several iterations.
7. A Solution that has a basic variable with zero value is called a “degenerate solution”.
8. If there is no Artificial variables in the problem, there is no room for “infeasible solution”
Simplex method incase of Artificial variables
“Big M method”
• Solve the following linear programming problem by using
the simplex method:
• Min Z =2 X1 + 3 X2
S.t.
½ X1 + ¼ X2 ≤ 4
X1 + 3X2  20
X1 + X2 = 10
X1, X2  0
 Big M method
• Notes
M, a very large number, is used to ensure that the values of A1 and A2, …, and An will be zero in the final
(optimal) tableau as follows:
1. If the objective function is Minimization, then A1, A2, …, and An must be added to the RHS of the objective
function multiplied by a very large number (M).
Example: if the objective function is Min Z = X1+2X2, then the obj. function should be Min Z = X1 + X2+ MA1 +
MA2+ …+ MAn
OR

Z – X1 - X2- MA1 - MA2- …- MAn = 0

2. If the objective function is Maximization, then A1, A2, …, and An must be subtracted from the RHS of the
objective function multiplied by a very large number (M).
Example: if the objective function is Max Z = X1+2X2, then the obj. function should be Max Z = X1 + X2- MA1 -
MA2- …- MAn
OR
Z - X1 - X2+ MA1 + MA2+ …+ MAn = 0
Big M method
• Solution
Step 1: standard form
Min Z,
s.t.
Z – 2 X1 – 3 X2 - M A1 -M A2 =0
½ X1 + ¼ X2 + S1 =4
X1 + 3X2 - S2 + A1 = 20
X1 + X2 + A2 = 10
X1, X2 ,S1, S2, A1, A2  0
Where: M is a very large number
 Big M method
• Step 2: Initial tableau

Basic X1 X2 S1 S2 A1 A2 RHS
variables
2 3 0 0 M M

S1 ½ ¼ 1 0 0 0 4
A1 1 3 0 -1 1 0 20
A2 1 1 0 0 0 1 10
Z -2 -3 0 0 -M -M 0

Note that one of the simplex rules is violated, which is the basic variables A 1, and A2 have a non zero
value in the z row; therefore, this violation must be corrected before proceeding in the simplex
algorithm as follows.
 Big M method
• To correct this violation before starting the simplex algorithm, the
elementary row operations are used as follows:
New (Z row) = old (z row) ± M (A1 row) ± M (A2 row)
In our case, it will be positive since M is negative in the Z row, as
following:
Old (Z row): -2 -3 0 0 -M -M 0
M (A1 row): M 3M 0 -M M o 20M
M (A2 row): M M 0 0 0 M 10M
New (Z row):2M-2 4M-3 0 -M 0 0 30M
Big M method
• The initial tableau will be:
Basic X1 X2 S1 S2 A1 A2 RHS
variables
2 3 0 0 M M

S1 1/2 1/4 1 0 0 0 4
A1 1 3 0 -1 1 0 20
A2 1 1 0 0 0 1 10
Z 2M-2 4M-3 0 -M 0 0 30M

• Since there is a positive value in the last row, this solution is not optimal

• The entering variable is X2 (it has the most positive value in the last row)
• The leaving variable is A1 (it has the smallest ratio)
 Big M method
• First iteration

Basic X1 X2 S1 S2 A1 A2 RHS
variables
2 3 0 0 M M

S1 5/12 0 1 1/12 -1/12 0 7/3

X2 1/3 1 0 -1/3 1/3 0 20/3

A2 2/3 0 0 1/3 -1/3 1 10/3

Z 2/3M-1 0 0 1/3M-1 1-4/3M 0 20+10/3M

• Since there is a positive value in the last row, this solution is not optimal

• The entering variable is X1 (it has the most positive value in the last row)
• The leaving variable is A2 (it has the smallest ratio)
 Big M method
• Second iteration
Basic X1 X2 S1 S2 A1 A2 RHS
variables
S1 0 0 1 -1/8 1/8 -5/8 1/4

X2 0 1 0 -1/2 1/2 -1/2 5

X1 1 0 0 1/2 -1/2 3/2 5

Z 0 0 0 -1/2 ½-M 3/2-M 25

This solution is optimal, since there is no positive value in the last row. The
optimal solution is:
X1 = 5, X2 = 5, S1 = ¼
A1 = A2 = 0 and Z = 25
 Note for the Big M method

• In the final tableau, if one or more artificial variables (A1, A2,

…) still basic and has a nonzero value, then the problem has an
infeasible solution.
• All other notes are still valid in the Big M method.
 Special cases
• In the final tableau, if one or more artificial variables (A 1, A2, …) still basic
and has a nonzero value, then the problem has an infeasible solution
• If there is a zero under one or more nonbasic variables in the last tableau
(optimal solution tableau), then there is a multiple optimal solution.
• When determining the leaving variable of any tableau, if there is no positive
ratio (all the entries in the pivot column are negative and zeroes), then the
solution is unbounded.
• In simplex table more than one variable is eligible to leave the basis, and hence
the next simplex iteration produces a degenerate solution in which at least one
basic variable is zero. Then solution in a LPP is known as degeneracy.
• In degeneracy case, it may not produce improvements in the value of the
objective function, as a result, it is possible to repeat the same sequence of
simplex iteration endlessly without improvement of the solution. This concept
is known as cycling.
1. Max Z =3 X1 + 9 X2
S.t. 3. Max Z =2 X1 + 2 X2
X1 + 4 X 2 ≤ 8 S.t.
Degeneracy 2X1 + X2 ≤ 100
X1 + 2X2 ≤ 4
X1 + X2 ≤ 80 Multiple solution
X1 , X2  0
X1 ≤ 40
X1 , X2  0
2. Max Z =2 X1 + X2
S.t. Unbounded solution
4. Max Z = 2X1 + 5 X2
X1 - X2 ≤ 10 Infeasible solution
S.t.
2X1 - X2 ≤ 40 X1 + 2X2 ≤ 2
X1 , X2  0 2X1 + 6X2  12
X1 , X2  0
The two-phase simplex method
• Step 1
Modify the constraints so that the right-hand side of each constraint is nonnegative.
This requires that each constraint with a negative right-hand side be multiplied
through by -1.
• Step 1’
Identify each constraint that is now an = or ≥ constraint. In step 3, we will add an the
artificial variable to each of these constraints.
• Step 2
Convert each inequality constraint to standard form.
For ≤ constraint i, we add a slack variable si;
For ≥ constraint i, we add an excess variable ei;
The two-phase simplex method

• Step 4
For now, ignore the original LP’s objective function. Instead solve an LP
whose objective function is min w’=(sum of all the artificial variables).
This is called the Phase I LP. The act of solving the phase I LP will
force the artificial variables to be zero.
 The two-phase simplex method

Since each ai≥0, solving the Phase I LP will result in one of the following
three cases:
• Case 1
The optimal value of w’ is greater than zero. In this case, the original LP
has no feasible solution.
• Case 2
The optimal value of w’ is equal to zero, and no artificial variables are in
the optimal Phase I basis. In this case, we drop all columns in the
optimal Phase I tableau that correspond to the artificial variables. We
now combine the original objective function with the constraints from
the optimal Phase I tableau. This yields the Phase II LP. The optimal
solution to the Phase II LP is the optimal solution to the original LP.
 The two-phase simplex method

• Case 3
The optimal value of w’ is equal to zero and at least one artificial variable
is in the optimal Phase I basis. In this case, we can find the optimal
solution to the original LP if at the end of Phase I we drop from the
optimal Phase I tableau all nonbasic artificial variables and any variable
from the original problem that has a negative coefficient in row 0 of the
optimal Phase I tableau.
Phase I and II feasible solutions
• Suppose the original LP is infeasible. Then the only way to
obtain a feasible solution to the Phase I LP is to let at least
one artificial variable be positive. In this situation, w’>0
will result.
• On the other hand, if the original LP has a feasible
solution, this feasible solution is feasible in the Phase I LP
and yields w’=0. This means that if the original LP has a
feasible solution, the optimal Phase I solution will have
w’=0.
Phase I
Consists of finding an initial basic feasible solution to the original
problem. For this purpose, an artificial objective function is created
which is the sum of all the artificial variables. The artificial objective is
then minimized using the Simplex Method. If the minimum value of the
artificial problem is zero, then it follows that all of the artificial variables
are zero, and an initial basic feasible solution for the original problem has
been obtained. Otherwise, a basic feasible solution for the original
problem does not exist (the problem has no feasible solutions- referred to
as Inconsistent).
 Phase II
The basic feasible solution found at the end of Phase I is optimized with
respect to the original objective function, i.e., the final tableau of Phase I
becomes the first tableau for Phase II (the objective row is changed).
Example
 Example:
 Minimize z = -3x1+ x2 + x3
 Subject to:
  x1 - 2x2 + x3  11
-4x1 + x2 + 2x3  3
2x1 - x3 = -1
x , x2 , x3  0
  1

 The first phase of the two-phase method is given by the problem:

Minimize w = A1 + A2
Subject to:
  x1 - 2x2 + x3 + S1 = 11 (1)
-4x1 + x2 +2x3 - S2+A1 = 3 (2)
-2x1 + x3 + A2 = 1 (3)
x1, x2 , x3, S1, S2, A1, A2 0
Example (cont.)
Objective function in standard Form is
Maximize -w + A1 + A2 =0 (0)
x1 - 2x2 + x3 + S1 = 11 (1)
-4x1 + x2 + 2x3 - S2+A1 = 3 (2) A1= 3+4x1 - x2 - 2x3 + S2
-2x1 + x3 + A2 = 1 (3) A2= 1+2x1 - x3

x1, x2 , x3, S1, S2, A1, A2 0

Substituting A1, A2 into (0) we get:
-w + (3+4x1 - x2 - 2x3) + (S2 + 1+2x1 - x3) =0
 -w + 6 x1- x2 -3x3 + S2 = -4 (0)
  x1- 2x2 +x3 + S1 = 11 (1)
-4x1 + x2 + 2x3 - S2+A1 = 3 (2)
-2x1 + x3 + A2= 1(3)
Duality Theory
The theory of duality is a very elegant and important concept
within the field of operations research. This theory was first
developed in relation to linear programming, but it has many
applications, and perhaps even a more natural and intuitive
interpretation, in several related areas such as nonlinear
programming, networks and game theory.
 The notion of duality within linear programming
asserts that every linear program has associated with it
a related linear program called its dual. The original
problem in relation to its dual is termed the primal.
 It is the relationship between the primal and its dual,
both on a mathematical and economic level, that is
truly the essence of duality theory.