Introduction to

Operations
Research
 Introduction to Operations
Research
• Operations research/management science
– Winston: “a scientific approach to decision making, which
seeks to determine how best to design and operate a
system, usually under conditions requiring the allocation of
scarce resources.”
– Kimball & Morse: “a scientific method of providing
executive departments with a quantitative basis for
decisions regarding the operations under their control.”
 Introduction to Operations
Research
• Provides rational basis for decision making
– Solves the type of complex problems that turn up in the
modern business environment
– Builds mathematical and computer models of organizational
systems composed of people, machines, and procedures
– Uses analytical and numerical techniques to make
predictions and decisions based on these models
 Introduction to Operations
Research
• Draws upon
– engineering, management, mathematics
• Closely related to the "decision sciences"
– applied mathematics, computer science,
economics, industrial engineering and systems
engineering
Methodology of OR
The Seven Steps to a Good OR Analysis
Identify the Problem Feedback loops
or Opportunity at all levels!

Understand the System

Formulate a
*Adapted from
Mathematical Model
Winston, Wayne L.,
Operations Research:
Verify the Model
Applications and
Algorithms,
Select the Best Alternative 3rd Edition, Duxbury
Press, 1994, p. 2.
Present the Results of
the Analysis

Implement and Evaluate

Methodology of OR
The Seven Steps to a Good OR Analysis
Identify the Problem • What are the
or Opportunity
objectives?
Understand the System
• Is the proposed
Formulate a
Mathematical Model problem too
narrow?
Verify the Model

• Is it too broad?
Select the Best Alternative

Present the Results of

the Analysis

Implement and Evaluate

 Methodology of OR
The Seven Steps to a Good OR Analysis
Identify the Problem
• What data should
or Opportunity be collected?

Understand the System • How will data be

collected?
Formulate a
Mathematical Model
• How do different
Verify the Model
components of the
system interact with
each other?
Select the Best Alternative

Present the Results of

the Analysis

Implement and Evaluate

 Methodology of OR
The Seven Steps to a Good OR Analysis

Identify the Problem

or Opportunity • What kind of
model should be
Understand the System used?
Formulate a • Is the model
Mathematical Model
accurate?
Verify the Model
• Is the model too
Select the Best Alternative complex?

Present the Results of

the Analysis

Implement and Evaluate

 Methodology of OR
The Seven Steps to a Good OR Analysis

• Do outputs
Identify the Problem
or Opportunity match current
observations for
Understand the System current inputs?

Formulate a • Are outputs

Mathematical Model
reasonable?
Verify the Model
• Could the model
be erroneous?
Select the Best Alternative

Present the Results of

the Analysis

Implement and Evaluate

 Methodology of OR
The Seven Steps to a Good OR Analysis

Identify the Problem

or Opportunity
• What if there are
Understand the System conflicting
objectives?
Formulate a
Mathematical Model • Inherently the most
difficult step.
Verify the Model

• This is where
Select the Best Alternative software tools will
help us!
Present the Results of
the Analysis

Implement and Evaluate

 Methodology of OR
The Seven Steps to a Good OR Analysis

Identify the Problem • Must communicate

or Opportunity
results in layman’s
Understand the System
terms.

Formulate a
• System must be user
Mathematical Model friendly!

Verify the Model

Select the Best Alternative

Present the Results of

the Analysis

Implement and Evaluate

 Methodology of OR
The Seven Steps to a Good OR Analysis
Identify the Problem • Users must be
or Opportunity
trained on the
Understand the System new system.

Formulate a • System must be

Mathematical Model observed over
time to ensure it
Verify the Model works properly.

Select the Best Alternative

Present the Results of

the Analysis

Implement and Evaluate

 Applications of OR
– Accounting
– Construction
– Facilities Planning
– Finance
– Manufacturing
– Marketing
– Organizational Behavior / Human Resources
 Tools and techniques used in OR
• Linear Programming
• Game Theory
• Decision Theory
• Queuing Theory
• Inventory Models
• Simulation
• Network Scheduling
 Linear Programming
• Linear Programming is a special and
versatile technique
• Applicable to a variety of management
problems viz. Advertising, Distribution,
Investment, Production, Refinery Operations,
and Transportation analysis.
• Applicable in problems characterized by the
presence of decision variables, objective
functions and constraints.
 Example 2.1

• Suppose an industry is manufacturing two types of products

P1 and P2. The profits per kg of the two products are Rs. 30
and Rs. 40 respectively. These two products require
processing in three types of machines. The following table
shows the available machine hours per day and the time
required on each machine to produce one kg of P1 and P2.
 Example 2.1
Decision variables correspond to the numbers of Kgs
of each product type to be manufactured (P1 & P2) per
day.
Kg of Product P1 = x1

Kg of Product P2 = x2

P1 P2 Total available
Profit/kg (Time in (Time in Machine
hrs.) hrs.) hours/day
Machine 1 3 2 600
Machine 2 3 5 800
Machine 3 5 6 1100
 Example 2.1
• Decision variables
– Product P1 = x1
– Product P2 = x2
• Objective function  
– Z = 30x1 + 40x
• Constraints
– 3x1 + 2x2 ≤ 600
– 3x1 + 5x2 ≤ 800
– 5x1 + 6x2 ≤ 1100
– x1 ≥ 0, x2 ≥ 0
 Example 2.2
• A company owns two flour mills viz. A and B, which have different production
capacities for high, medium and low quality flour. The company has entered a
contract to supply flour to a firm every month with at least 8, 12 and 24
quintals of high, medium and low quality respectively. It costs the company
Rs. 2000 and Rs. 1500 per day to run mill A and B respectively. On a day, Mill
A produces 6, 2 and 4 quintals of high, medium and low quality flour, Mill B
produces 2, 4 and 12 quintals of high, medium and low quality flour
respectively. How many days per month should each mill be operated in
order to meet the contract order most economically?
 Example 2.2
• Decision variables
– Mill A = x1 days
– Mill B = x2 days
 Objective
– Minimize Z=2000x1 + 1500x2
 Constraints
– 6x1 + 2x2 ≥ 8
– 2x1 + 4x2 ≥ 12
– 4x1 + 12x2 ≥ 24
– x1 ≥ 0, x2 ≥ 0
 3. Assumptions underlying linear
programming
• Based on the assumptions of

· Proportionality

· Additivity

· Continuity

· Certainty

· finite choices
 Simplex Method

• This Method provides an efficient technique

which can be applied for solving LPPs
involving more than two decision variables.
• Simplex algorithm is an iterative procedure
for finding the optimal solution to LPP.
 Standard form of LPP

• To solve the linear programming problem by Simplex

method, it has to be represented in standard form
• Standard form of LPP is explained with the help of an
example.
 Example 1

• Maximise Z = 40x1 + 35x2

• Subject to
2x1+ 3x2 ≤ 60 Raw Material
4x1+ 3x2 ≤ 96 Labour Hours
x1, x2 ≥ 0
 Example 1
Step 1: All the constraints should be
converted to equations by introducing a slack
variables s1, s2 etc. except for the non-
negativity restrictions
2x1 + 3x2 + s1 = 60
4 x1 + 3 x2+ s2 = 96
Where, s1, s2 ≥ 0
Step 2: The right side element of each
constraint should be made non-negative by
multiplying both sides by – 1, if needed.
 Example 2.1
Step 3: All variables must have non-negative values. A variable which
is unrestricted in sign (that is + ve, – ve, or 0) is equivalent to the
difference between two non-negative variables. Thus, if x is
unconstrained in sign, it can be replaced by (x' – x") where x' and x"
are both non-negative, that is x' > 0 and x" > 0. 

Step 4 The objective function should be in maximisation form. The

minimisation of a function f (x) is equivalent to the maximisation of
the negative expression of this function f (x) that is:
Min f (x) = – Max {–f (x)}
 Example 1
Step5: The objective function in the simplex method should
contain every variable present in the system including slack
variables.
So the standard form of the LPP given in Example 1 can be
expressed as:
• Maximize
Z = 40x1 + 35x2 + 0s1 + 0s2 
• Subject to:
2x1 + 3x2 + s1 = 60
4x1 + 3x2 + s2 = 96
x1, x2, s1, s2 ≥ 0
 Basic and non basic variables
• x1, x2 are non basic variables
• s1, s2 are basic variables
• If one or more values of the basic variables are valued
at zero, then solution is said to be degenerate, whereas
if all basic variable have non-zero values, then the
solution is called non-degenerate
2.2 Simplex method computation
 Rule for testing the optimality

• Rule for testing optimality: A simplex table

depicts an optimal solution if all entries in the
∆j row, are:
• Zero or negative (i.e. all ∆j ≤ 0) when the LPP is
of maximization type.
• Zero or positive (i.e. all ∆j ≥ 0) when the LPP is
of minimization type.
• The solution is not optimal because it contains
positive values
 Improved solution
• ∆j row signifies the amount of increase in
objective function that would occur if one unit
of the variable were introduced into the
solution.
• Select the variable that has the largest ∆j value
(incoming basic variable)
 Improved solution
• The column corresponding to this variable is called the
key column.
• bi values are divided by the corresponding values in the
key column ratios bi/aij also called the replacement ratios.
• The row with the least non-negative quotient called key
row(outgoing variable, s2)
 Improved solution

Basic X1 X2 S1 S2 bi bi/aij
S1 0 2 3 1 0 60 30
24
Outgoing
S2 0 4* 3 0 1 96
variable
(key row)
cj 40 35 0 0
zj 0 0 0 0

40
Incoming
Δj 35 0 0
variable
(key column)
 Derive new table
• Divide each element of the key row
(including bi) by the key element.
• The replacement row would be:
1, ¾, 0, ¼, 24
• For each row other than the key row: New
row element = Old row element – (Row
element in the key column * Corresponding
replacement row value)
 Derive new table

Basic x1 x2 S1 S2 bi bi/aij
8
S1 0 0 3/2* 1 - 1/2 12 Outgoing
variable
x1 40 1 3/4 0 1/4 24 32
cj 40 35 0 0
zj 40 30 0 0

5
Δj 0 Incoming 0 -10
variable
 Improved solution

• The solution to the problem is: x1=24, x2=0,

s1=12, s2=0.

• Z = 40 x 24 + 35 x 0 + 0 x 12 + 0 x 0 = 960.
 Revised solution

Basic x1 x2 S1 S2 bi
x2 35 0 1 2/3 -1/3 8
x1 40 1 0 -1/2 1/2 18
cj 40 35 0 0
zj 40 35 0 0
Δj 0 0 -10/3 -25/3
 Revised solution

• This solution x1=18, x2= 8, yields the objective

function value
• Z= 40 x 18 + 35 x 8 + 0 x 0 + 0 x0 =1000.
• The values in Δj ≤ 0 indicate that the solution
is optimal
 Simplex method when some constraints are not “≤”
constraints

• We employ a mathematical “ trick” to

jumpstart the problem by adding artificial
variables to the equations.
 Simplex method when some constraints
are
Example:
not “≤” constraints (cont.)

Max 16x1+15x2+20x3-18x4
ST
2x1 + x2 + 3x3 ≤ 3000 [1]
3x1 + 4x2 + 5x3 – 60x4 ≤ 2400 [2]
x4 ≤ 32 [3]
X2 ≥ 200 [4]
X1 + x2 + x3 ≥ 800 [5]
X1 – x2 –x3 =0 [6]
Xj ≥ 0 for all J
 Simplex method when some constraints are not “≤”
constraints (cont.)
We assign a very
Example: large negative
objective function
coefficient , -M , (
Max 16x1+15x2+20x3-18x4
+M for
ST minimization
2x1 + x2 + 3x3 ≤ 3000 [1] problem) to each
3x1 + 4x2 + 5x3 – 60x4 ≤ 2400 [2] artificial variable
x4 ≤ 32 [3]
X2 ≥ 200 [4]
X1 + x2 + x3 ≥ 800 [5] We add artificial :
R4, R5, R6, respectively
X1 – x2 –x3 =0 [6]
to the fourth, fifth, and
Xj ≥ 0 for all J sixth equations.
 Simplex method when some constraints are not “≤”
constraints (cont.)
The solution
Max 16x1+15x2+20x3-18x4
–MR4 –MR5 –MR6
ST
2x1 + x2 + 3x3 + s1= 3000 [1]
3x1 + 4x2 + 5x3 – 60x4 + s2 = 2400 [2]
x4 + s3 = 32 [3]
X2 – s4 + R4 = 200 [4]
X1 + x2 + x3 – s5 + R5 = 800 [5]
X1 – x2 –x3 + R6= 0 [6]
Xj ≥ 0 The
, Sj simplex
≥ 0, Rjalgorithm
≥ 0 for can
all Jthen be used to solve this problem
Solving For the optimal solution of [Maximization]
when there are artificial variables
Example # 1:

MAX 2x1+ 5x2

ST
X1 ≥ 4
x1 + 4x2≤ 32
3x1+ 2x2 = 24
Solving For the optimal solution of [Maximization]
when there are artificial variables (cont.)
The Solution
• By adding the appropriate slack, surplus, and artificial
variables, we obtain the following:

MAX 2x1 + 5x2 –MR1 – MR3

ST
X1 – s1 + R1 =4
X1 + 4x2 + s2 = 32
3x1 + 2x2 + R3= 24

X1,x2,s1,s2,R1,R3 ≥ 0
 Solving For the optimal solution of [Maximization]
when there are artificial variables (cont.)

The initial table :

Basis X1 X2 S1 S2 R1 R3 RHS
R1 1 0 -1 0 1 0 4
R1, S2, R3 are
S2 1 4 0 1 0 0 32 basic
variables.
R3 3 2 0 0 0 1 24
Z -2 -5 0 0 +M +M 0

• Make z consistent; (R1, R3) in z-row coefficient (+M,+M) it must be zero; By apply:

New z-row = old z-row + ( -M * R1 row – M * R3 row) MAX objective function

New z-row = old z-row + ( M * R1 row +M * R3 row) MIN objective function

Solving For the optimal solution of [Maximization]
when there are artificial variables (cont.)

• Starting table:

Basis X1 X2 S1 S2 R1 R3 RHS
R1 1 0 -1 0 1 0 4
S2 1 4 0 1 0 0 32
R3 3 2 0 0 0 1 24
Z -2-4M -5-2M +M 0 -M -M -28M
 Solving For the optimal solution of [Maximization]
when there are artificial variables (cont.)

• To determine Entering Variable; We should look to the largest

negative number in z-row.

Entering Variable

Basis X1 X2 S1 S2 R1 R3 RHS
R1 1 0 -1 0 1 0 4
S2 1 4 0 1 0 0 32
R3 3 2 0 0 0 1 24
Z -2-4M -5-2M +M 0 -M -M -28M

Largest negative number

Solving For the optimal solution of [Maximization]
when there are artificial variables (cont.)

• Calculate the ratio; then, determine the smallest positive

number as Leaving Variable Leaving Variable

Basis X1 X2 S1 S2 R1 R3 RHS Ratio

R1 1 0 -1 0 1 0 4 4
S2 1 4 0 1 0 0 32 32
R3 3 2 0 0 0 1 24 8
Z -2-4M -5-2M +M 0 -M -M -28M

• Pivot element = ( 1, 0, -1, 0, 1, 0, 4)/ (1)

( 1, 0, -1, 0, 1, 0, 4)
 Solving For the optimal solution of [Maximization] when there
are artificial variables (cont.)

• First iteration

Entering Variable Leaving Variable

Basis X1 X2 S1 S2 R1 R3 RHS Ratio

X1 1 0 -1 0 1 0 4 ….
S2 0 4 1 1 -1 0 28 28
R3 0 2 3 0 -3 1 12 4
Z 0 -5-2M -2-3M 0 2+3M -M 8-12M
Solving For the optimal solution of [Maximization] when
there are artificial variables (cont.)
• Second iteration

Entering Variable Leaving Variable

Basis X1 X2 S1 S2 R1 R3 RHS Ratio

X1 1 2/3 0 0 0 1/3 8 12
S2 0 10/3 0 1 0 -1/3 24 7.2
S1 0 2/3 1 0 -1 1/3 4 6
Z 0 -11/3 0 0 0 2/3 +16
 Solving For the optimal solution of [Maximization]
when there are artificial variables (cont.)
• Third iteration

Basis X1 X2 S1 S2 R1 R3 RHS Ratio

X1 1 0 -1 0 1 0 4
S2 0 0 -5 1 5 -2 4
X2 0 1 3/2 0 -3/2 1/2 6
Z 0 0 11/3 0 -11/2 5/2 38
 Solving For the optimal solution of [Maximization]
when there are artificial variables (cont.)

points Classification Reason

X1=0, X2=0 Not Feasible R1, R3 both Positive (4, 24)
X1=4, X2=0 Not Feasible R3 positive= 12
X1=8, X2=0 Feasible but not optimal X2 is negative
X1=4, X2=6 Feasible and optimal All x1,X2 ≥0
Solving For the optimal solution of [Minimization]
when there are artificial variables
Example # 2:

Min 4x1 + x2
ST
3x1+ x2 = 3
4x1 + 3x2 ≥ 6
X1+ 2x2 ≤ 4
X1, x2 ≥ 0
Solving For the optimal solution of [Minimization]
when there are artificial variables (cont.)
The Solution
• By adding the appropriate slack, surplus, and artificial
variables, we obtain the following:

Min 4x1 + x2 + MR1 + MR2

ST
3x1+ x2 + R1= 3
4x1 + 3x2 –s1 + R2 = 6
X1+ 2x2 + s2 = 4
X1, x2 , s1, s2, R1, R2≥ 0
 Solving For the optimal solution of [Minimization] when there are
artificial variables (cont.)

• The initial table:

Basis X1 X2 S1 R1 R2 S2 RHS
R1 3 1 0 1 0 0 3
R2 4 3 -1 0 1 0 6
S2 1 2 0 0 0 1 4
Z -4 -1 0 -M -M 0 0

• New z-row = old z-row +( M * R1 row +M *

R3 row)
 Solving For the optimal solution of [Minimization]
when there are artificial variables (cont.)
• Starting table: Leaving Variable

Entering Variable

Basis X1 X2 S1 R1 R2 S2 RHS
R1 3 1 0 1 0 0 3
R2 4 3 -1 0 1 0 6
S2 1 2 0 0 0 1 4
Z -4+7M -1+4M -M 0 0 0 9M
 Solving For the optimal solution of [Minimization]
when there are artificial variables (cont.)
• First iteration
Leaving Variable
Entering Variable

Basis X1 X2 S1 R1 R2 S2 RHS
X1 1 1/3 0 1/3 0 0 1
R2 0 5/3 -1 -4/3 1 0 2
S2 0 5/3 0 -1/3 0 1 3
Z 0 (1+5M)/3 -M (4-7M)/3 0 0 4+2M
 Solving For the optimal solution of [Minimization]
when there are artificial variables (cont.)
• Second iteration
Entering Variable
Leaving Variable
Basis X1 X2 S1 R1 R2 S2 RHS
X1 1 0 1/5 3/5 -1/5 0 3/5
X2 0 1 -3/5 -4/5 3/5 0 6/5
S2 0 0 1 1 -1 1 1
Z 0 0 1/5 8/5 - M -1/5 -M 0 18/5
 Solving For the optimal solution of [Minimization]
when there are artificial variables (cont.)
• Third iteration

Basis X1 X2 S1 R1 R2 S2 RHS
X1 1 0 0 2/5 0 -1/5 2/5
X2 0 1 0 -1/5 0 3/5 9/5
s1 0 0 1 1 -1 1 1
Z 0 0 0 7/5 – M -M -1/5 17/5

• Optimal solution : x1= 2/5, x2= 9/5, z= 17/5

Solution to minimization problems
Minimise Z= 40x1 + 24x2 subject to
20x1 + 50x2 ≥ 4800
80x1 + 50x2 ≥ 7200
x1, x2 ≥ 0
• Standard form
Minimise Z = 40x1 + 24x2 + 0s1 + 0s2
20x1 + 50x2 – s1 ≥ 4800
80x1 + 50x2 – s2 ≥ 7200
x1, x2 , s1 s2 ≥ 0
 Duality in LPP
• Duality describes that linear programming
problems exist in 'pairs‘.
• Corresponding to every given linear
programming problem, there is another LPP
which may be derived from it.
 Construction of dual problem

• First, the LPP must be expressed in standard

form.
• Maximise Z = 40x, + 35x2
2x, + 3x2 ≤ 60
4x2 +3x2 ≤ 96
x1, x2 ≥ 0
 Construction of dual problem

• Convert the maximization type of primal problem into

minimization type of dual problem.
• The constraint values (60 and 96) of the primal have
become the coefficients of the dual variables y 1 and y2
in the objective function of the dual in that order.
 
 Construction of dual problem
• The coefficients of the variables in the objective function of the
primal have become the constraint values in the dual.
• The first column of the coefficients in the constraints in the
primal has become the first row in the constraints in the dual,
and the second column has similarly become the second row.
• The direction of inequalities in the dual is the reverse of that in
the primal. In the above example, the inequalities in the primal
are of the type ≤ they are of ≥ type in the dual.
 Finding the dual of an LP
• When taking the dual of a given LP, we refer to
the given LP as the primal. If the primal is a
max problem, the dual will be a min problem,
and vice versa.
• For convenience, we define the variables for
the max problem to be z, x1,x2,…,xn and the
variables for the min problem to be w,y1,y2,
…,ym.
 Finding the dual of an LP

• A normal max problem may be written as

max z  c1 x1  c 2 x 2    c n x n
s .t . a11 x1  a12 x 2    a1 n x n  b1
a 21 x1  a 22 x 2    a 2 n x n  b2
   
a m 1 x1  a m 2 x 2    a mn x n  bm
x j  0(i  1,2 , ,n)
 Finding the dual of an LP

• The dual of a normal max problem is defined to be,

min w  b1 y1  b2 y2    bm ym
s.t. a11 y1  a21 y2    am1 ym  c1
a12 y1  a22 y2    am 2 ym  c2
   
a1n y1  a2 n y2    amn ym  cn
yi  0(i  1,2 , ,m)
 Finding the dual of an LP
• A tabular approach makes it easy to find the dual of
an LP. A normal min problem is found by reading
down; the dual is found by reading across in the
table.
Finding the dual of an LP

max z
min w x1  0 x2  0 xn  0
x1 x2  xn
y1  0 y1 a11 a12  a1n  b1
y2  0 y2 a21 a22  a2 n  b2
     
ym  0 ym am1 am 2  amn  bm
 c1  c2   cn
 Finding the dual of an LP

max z  60 x1  30 x2  20 x3
s.t. 8 x1  6 x2  x3  48
4 x1  2 x2  1.5 x3  20
2 x1  1.5 x2  0.5 x3  8
x j  0(i  1,2 ,3 )
Finding the dual of an LP

max z
min w x1  0 x2  0 x3  0
x1 x2 x3
y1  0 y1 8 6 1  48
y2  0 y2 4 2 1.5  20
y3  0 y3 2 1.5 0.5 8
 60  30  20
 Finding the dual of an LP

• Then, reading down, we find the dual to be

max w  48 y1  20 y2  8 y3
s.t. 8 y1  4 y2  2 y3  60
6 y1  2 y2  1.5 y3  30
y1  1.5 y2  0.5 y3  20
x j  0(i  1,2 ,3 )
 Finding the dual of a nonnormal LP

• Many LPs are not normal max or min problem. For

example,
(18) max z  2 x1  x2 (19) min w  2 y1  4 y2  6 y3
s.t. x1  x2  2 s.t. y1  2 y2  y3  2
2 x1  x2  3 y1  y3  1
x1  x2  1 y 2  y3  1
2 y1  y2 3
x1  0, x2 urs
y1 urs, y 2 , y3  0
 Finding the dual of a nonnormal LP
• An LP can be transformed into normal form.
• To place a max problem into normal form, we
proceed as follows:
– Step 1 multiply each ≥ constraint by -1, converting it into a
≤ constraint.
– Step 2 replace each equality constraint by two inequality
constraints (a ≤ constraint and a ≥ constraint). Then
convert the ≥ constraint to a ≤ constraint.
– Step 3 replace each urs variable xi by xi=xi’-xi’’, where xi’
≥0 and xi’’ ≥0 .
 Finding the dual of a nonnormal LP

• (18) has been transformed onto the following LP:

max z  2 x1  x 2  x 2
s.t . x1  x 2  x   2
- x1  x 2  x    2
- 2 x1  x 2  x    3
x1  x 2  x   1
x1 , x 2 , x 2  0
 Finding the dual of a nonnormal LP
• Transform a nonnormal min problem into a normal
min problem:
– Step 1 multiply each ≤ constraint by -1, converting it into a
≥ constraint.
– Step 2 replace each equality constraint by two inequality
constraints (a ≤ constraint and a ≥ constraint). Then
convert the ≥ constraint to a ≤ constraint.
– Step 3 replace each urs variable yi by yi=yi’-yi’’, where yi’
≥0 and yi’’ ≥0 .
 Finding the dual of a nonnormal max problem
• Find the dual of a nonnormal max LP without going
through the transformations,
– Step 1 fill in table so that the primal can be read across.
– Step 2 making the following changes,
– (a) if the ith primal constraint is a ≥ constraint, the corresponding dual
variable yi must satisfy yi≤0.
– (b) if the ith primal constraint is an equality constraint, the dual variable yi
is now unrestricted in sign.
– (c) if the ith primal variable is urs, the ith dual constraint will be an equality
constraint.
 Finding the dual of a nonnormal max
problem
• For example,
max z
max z  2 x1  x2
min w ( x1  0) ( x2 urs)*
s.t. x1  x2  2 x1 x2
2 x1  x2  3 y1 1 1  2*
y2 2 1  3*
x1  x2  1
( y 3  0) y3 1 1 1
x1  0, x2 urs 2 1
Finding the dual of a nonnormal max
problem

max z
min w ( x1  0) ( x2 urs )
x1 x2
( y1 urs ) y1 1 1 2
( y 2  0) y2 2 1 3
( y 3  0) y3 1 1 1
2 1
 REFERENCES
• Production and Operations Management By
Bedi
• Production Management by B. S. Goyal