Advanced Engineering Mathematics

Optimization Techniques
III Sem CS ( 3CS2-01)

Unit V

Prof.(Dr.) Ashok Singh Shekhawat

Department of Mathematics
JECRC, Jaipur
CONTENTS OF UNIT-II:-

INTRODUCTION AND DEFINATION

LINEAR PROGRAMMING MODEL

APPLICATION AND REQUIREMENT

FORMULATION AND METHOD OF SOLVING LPP

RESTRICTION IN LPP

DUALITY OF LPP

CONCLUSION
 INTRODUCTION AND DEFINATION
 Mathematical programming is used to find the best or
optimal solution to a problem that requires a decision
or set of decisions about how best to use a set of limited
resources to achieve a state goal of objectives.
 Steps involved in mathematical programming

Conversion of stated problem into a mathematical model

that abstracts all the essential elements of the problem.

 Exploration of different solutions of the problem.

 Finding out the most suitable or optimum solution.

 Linear programming requires that all the mathematical
functions in the model be linear functions.
 The Linear Programming Model (1)
Requirement: Maximization of the linear function Z.
Z = c1X1 + c2X2 + c3X3 + ………+ cnXn …..Eq (1)
subject to the following constraints:
c

….Eq (2)

Where a ij , bj and cj are given constants.

The Linear Programming Model (2)
 The linear programming model can be written in more
efficient notation as:

….Eq (3)

The decision variables X1 , X 2 ,......X n represent levels of n

competing activities.
 Applications of linear programming
1. Scheduling school buses to minimize total distance
traveled
2. Allocating police patrol units to high crime areas in order
to minimize response time to 911 calls
3. Scheduling tellers at banks so that needs are met during
each hour of the day while minimizing the total cost of
labor
4. Selecting the product mix in a factory to make best use of
machine- and labor-hours available while maximizing the
firm’s profit
5. Picking blends of raw materials in feed mills to produce
finished feed combinations at minimum costs
6. Determining the distribution system that will minimize
total shipping cost
Requirements of an LP problem

1. LP problems seek to maximize or minimize some

quantity (usually profit or cost) expressed as an objective
function
2. The presence of restrictions, or constraints, limits the
degree to which we can pursue our objective
3. There must be alternative courses of action to choose
from
4. The objective and constraints in linear programming
problems must be expressed in terms of linear equations
or inequalities
Formulating LP Problems
 The product-mix problem at Shader Electronics

 Two products
1. Shader X-pod, a portable music player
2. Shader BlueBerry, an internet-connected
color telephone
 Determine the mix of products that will produce
the maximum profit
Formulating LP Problems
Hours Required
to Produce 1 Unit
X-pods BlueBerrys Available Hours
Department (X1) (X2) This Week
Electronic 4 3 240
Assembly 2 1 100
Profit per unit $7 $5

Decision Variables:
X1 = number of X-pods to be produced
X2 = number of Blue Berrys to be produced
Formulating LP Problems
 Objective Function:
Maximize Profit = 7X1 + 5X2
There are three types of constraints
 Upper limits where the amount used is ≤ the
amount of a resource
 Lower limits where the amount used is ≥ the
amount of the resource
 Equalities where the amount used is = the amount
of the resource
Formulating LP Problems
 First Constraint:

Electronic Electronic
time used is ≤ time available

4X1 + 3X2 ≤ 240 (hours of electronic time)

Second Constraint:
Assembly Assembly
is ≤
time used time available

2X1 + 1X2 ≤ 100 (hours of assembly time)

Graphical method

Can be used when there are two decision variables

1. Plot the constraint equations at their limits by
converting each equation to an equality
2. Identify the feasible solution space
3. Create an iso-profit line based on the objective
function
4. Move this line outwards until the optimal point is
identified
Graphical solution

X2

100 –
–
Number of Blue Berrys

80 –
Assembly (constraint B)
–
60 –
–
40 –
– Electronics (constraint A)
20 – Feasible
–
region
|– | | | | | | | | | | X1
0 20 40 60 80 100
Number of X-pods
Graphical Solution
Iso-Profit
X
Line Solution Method
2

Choose a100
possible
– value for the objective function
–
80 –
Number of Watch TVs

Assembly (constraint B)
– $210 = 7X1 + 5X2
60 –
Solve for the axis
– intercepts of the function and plot the line
40 –
– Electronics (constraint A)
X = 42
20 – Feasible
2 X1 = 30
region
–
|– | | | | | | | | | | X1
0 20 40 60 80 100
Number of X-pods
Graphical solution
X2

100 –
–
Number of Blue Berrys

80 –
–
60 – $210 = $7X1 + $5X2
–
(0, 42)
40 –
–
20 – (30, 0)
–
|– | | | | | | | | | | X1
0 20 40 60 80 100
Number of X-pods
Graphical solution

X2

100 –
– $350 = $7X1 + $5X2
Number of Blue Beryys

80 –
$280 = $7X1 + $5X2
–
60 – $210 = $7X1 + $5X2
–
40 –
–
$420 = $7X1 + $5X2
20 –
–
|– | | | | | | | | | | X1
0 20 40 60 80 100
Number of X-pods
Graphical solution

X2

100 –
– Maximum profit line
80 –
Number of Blue Berrys

–
60 – Optimal solution point
– (X1 = 30, X2 = 40)
40 –
–
$410 = $7X1 + $5X2
20 –
–
|– | | | | | | | | | | X1
0 20 40 60 80 100
Number of X-pods
Corner point method

X2

100 –
2 –
Number of Blue Berrys

80 –
–
60 –
–
3
40 –
–
20 –
–
|– | | | | | | | | | | X1
1
0 20 40 60 80 100
4
Number of X-pods
Corner-Point Method
 The optimal value will always be at a corner
point
 Find the objective function value at each
corner point and choose the one with the
highest profit

Point 1 : (X1 = 0, X2 = 0) Profit $7(0) + $5(0) = $0

Point 2 : (X1 = 0, X2 = 80) Profit $7(0) + $5(80) = $400
Point 4 : (X1 = 50, X2 = 0) Profit $7(50) + $5(0) = $350
Point 3 : (X1 = 30, X2 = 40) Profit $7(30) + $5(40) = $410
The Simplex Method
 The geometric method of solving linear programming
problems presented before. The graphical method is useful
only for problems involving two decision variables and
relatively few 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.
Standard Maximization Problems in Standard Form
A linear programming problem is said to be a standard
maximization problem in standard form if its
mathematical model is of the following form:
Maximize the objective function
Z max  P  c1x1  c2 x2  ...  cn xn

Subject to problem constraints of the form

a1x1  a2 x2  ...  an xn  b ,b  0
With non-negative constraints

x1, x2 ,..., xn  0
Slack Variables
If a constraint has a sign  , then in order to make it an
equality we have to add some positive quantity to the left
hand side .
The positive variables which are added to left hand side of the
constraints to convert into equations are called the slack
variables.
Ex . x1  x2  x3  5 x1 , x2 , x3  0

Can be converted to
Ex . x1  x2  x3  x4  5 x1 , x2 , x3 , x4  0

Then x4 is called the slack variable.

Surplus variables
 If constraint has a sign  then in order to make it an
equality we have to subtract some positive quantity
from left hand side .
 The positive variables which are subtracted from the
left hand side of the constraints to convert them into
equalities are called the surplus variables.
 Ex. 2x1  5x2  200
 Can be converted to
2 x1  5x2  x3  200

 then x3 is the surplus variable.

Example 1: A Simple Maximization Problem

Max 5x1 + 7x2 OBJECTIVE

FUNCTION
s.t. x1 < 6
2x1 + 3x2 < 19 REGULAR
CONSTRAINTS
x1 + x2 < 8
x1 > 0 and x2 > 0 NON-
NEGATIVEITYC
ONSTRAINTS
Working steps of simplex method
we follow the following steps:
Step-1 if the problem is not of maximization convert it to
maximization problem.
As Min.Z = - Max.Z assume z  z
'
. Work on the
problem with objective function as Max. Z '
Step-2 if any entry of vector b  b1 , b2 ,......bn T is negative ,
multiply the corresponding constraint by (-1) to make it
positive . (all entries of b should be non- negative )
Step-3 add (subtract ) slack (surplus) variables, where ever
needed to convert inequalities to equalities.
Step-4 if needed add artificial variables to get initial basic
matrix B  I m
Step-5 in objective function , slack and surplus variables are
added with coefficients zero. The coefficient of artificial
variables are decided by the method.
Step-6 calculate z j  c j for every (column ) vector a j . If the
most negative value of z j  c j occur for j equal to k , then ,
k thvector will be the entering vector in the new basis .
 ( X B )i 
, Y 
Step-7 calculate mini. Ratio  Y ik  . If this value of i is
0
 ik 

r then r is the departing vector .
Step-8 from the new simplex table. Repeat steps 6,7 and 8
until z j  c j  0 for all j is optimal.
Example of simplex method
 Solve the following L.P.P by simplex method
Maximize Z = 5x1 + 2x2 + x3

subject to the constraints

x1 + 3x2 - x3 ≤ 6,

x2 + x3 ≤ 4,

3x1 + x2 ≤ 7,

x1, x2, x3 ≥ 0.
  Step-1 covert into standard form

a11 x1 + a12 x2 + ••• + a1n xn ≤ b1, a11 x1 + a12 x2 + ••• + a1n xn + xn+1 = b1,

a21 x1 + a22 x2 + ••• + a2n xn ≥ b2, a21 x1 + a22 x2 + ••• + a2n xn - xn+2 = b2,

am1 x1 + am2 x2 + ••• + amn xn ≤ bm, am1 x1 + am2 x2 + ••• + amn xn + xn+k = bm,

In our example problem

x1 + 3x2 - x3 + x4 = 6,
x1 + 3x2 - x3 ≤ 6,
x2 + x3 + x5 = 4,
x2 + x3 ≤ 4,
3x1 + x2 + x6 = 7,
3x1 + x2 ≤ 7,
x1, x2, x3, x4, x5, x6 ≥ 0.
x1, x2, x3 ≥ 0.

Here x4, x5, x6 are slack variables

 Simplex: Step 2
Step 2. Start with an initial basic feasible solution (b.f.s.)
and set up the initial table.
In our example
Maximize Z = 5x1 + 2x2 + x3

x1 + 3x2 - x3 + x4 = 6,

x2 + x3 + x5 = 4,

3x1 + x2 + x6 = 7,
cB Basis cj Constants
x1, x2, x3, x4, x5, x6 ≥ 0. 5 2 1 0 0 0
x1 x2 x3 x4 x5 x6
0 x4 1 3 -1 1 0 0 6
0 x5 0 1 1 0 1 0 4
0 x6 3 1 0 0 0 1 7
c row 5 2 1 0 0 0 Z=0
 Step 2: Explanation
Adjacent Basic Feasible Solution
If we bring a non basic variable xs into the basis, our system
changes from the basis, xb, to the following (same notation as the
book):
x1 + ā1sxs= b
1
xi = bi  a is for i =1, …, m
xr + ārsxr= b r xs = 1

xm + āmsxs= bs xj = 0 for j=m+1, ..., n and js

The new value of the objective function becomes:

m
Z  c (b  a
i 1
i i is )  c s

Thus the change in the value of Z per unit increase in xs is

cs = new value of Z - old value of Z
m This is the Inner Product rule
cs  c a
i 1
i is
 Simplex: Step 3
Use the inner product rule to find the relative profit coefficients

cB Basis cj Constants
5 2 1 0 0 0
x1 x2 x3 x4 x5 x6
0 x4 1 3 -1 1 0 0 6
0 x5 0 1 1 0 1 0 4
0 x6 3 1 0 0 0 1 7
c row 5 2 1 0 0 0 Z=0

c j  c j  cB Pj
c1 = 5 - 0(1) - 0(0) - 0(3) = 5 -> largest positive
c2 = ….
c3 = ….
Step 4: Is this an optimal basic feasible solution?

31
 Simplex: Step 4
Apply the minimum ratio rule to determine the basic variable to
leave the basis.
The new values of the basis variables:
xi = bi  a is x s for i = 1, ..., m

 bi 
max x s  min  
a is 0 a is
 
In our example:
cB Basis cj Constants
5 2 1 0 0 0 Row Basic Variable Ratio
x1 x2 x3 x4 x5 x6 1 x4 6
0 x4 1 3 -1 1 0 0 6 2 x5 -
0 x5 0 1 1 0 1 0 4 3 x6 7/3
0 x6 3 1 0 0 0 1 7
c row 5 2 1 0 0 0 Z=0

32
 Simplex: Step 5
Perform the pivot operation to get the new tableau and the b.f.s.
cB Basis cj Constants
5 2 1 0 0 0
x1 x2 x3 x4 x5 x6
0 x4 1 3 -1 1 0 0 6 Key element is 3
0 x5 0 1 1 0 1 0 4
0 x6 3 1 0 0 0 1 7
c row 5 2 1 0 0 0 Z=0
New iteration:
find entering
cB Basis cj Constants
variable: 5 2 1 0 0 0
c j  c j  c B Pj x1 x2 x3 x4 x5 x6
0 x4 0 8/3 -1 1 0 0 11/3
0 x5 0 1 1 0 1 0 4
cB = (0 0 5)
5 x1 1 1/3 0 0 0 1/3 7/3
c2 = 2 - (0) 8/3 - (0) 1 - (5) 1/3 = 1/3 c row 0 1/3 1 0 0 -5/3 Z=35/3
c3 = 1 - (0) (-1) - (0) 1 - (5) 0 = 1
c6 = 0 - (0) 0 - (0) 0 - (5) 1/3 = -5/3
33
 Final Table
cB Basis cj Constants x3 enters basis,
5 2 1 0 0 0 x5 leaves basis
x1 x2 x3 x4 x5 x6
0 x4 0 8/3 -1 1 0 0 11/3
0 x5 0 1 1 0 1 0 4
5 x1 1 1/3 0 0 0 1/3 7/3
c row 0 1/3 1 0 0 -5/3 Z=35/3

cB Basis cj Constants
5 2 1 0 0 0
x1 x2 x3 x4 x5 x6
0 x4 0 11/3 0 1 1 0 23/3
1 x3 0 1 1 0 1 0 4
5 x1 1 1/3 0 0 0 1/3 7/3
c row 0 -2/3 0 0 -1 -5/3 Z=47/3

The optimal solution will be X1=7/3 X2=0 X3=4 Max.z=47/3

34
Artificial Variable Technique
(The Big-M Method and Two
phase Method)
 Artificial variables :- the simplex algorithm requires a starting
basic feasible solution (BFS) . We find a starting BFS by using
the slack variables as our basic variables. If an LPP has  or
equality constraints , a starting BFS may not be readily
apparent . To start , we need a canonical from:
 (1) if we have a  constraints with a non-negative right hand
side , it will contain an obvious basic variable after introducing
a slack variable.
 (2)if we have equality constraints , it contains no obvious
variable .
 (3) if we have a  constraints with a non-negative right hand
side , it contains no obvious basic variable even after
introducing a surplus variable.
 For example :
2 x  3 y  5  2 x  3 y  s  5, ( s, basic )

 If 2 x  3 y  5, this is infeasible if x=y=0.

And 2 x  3 y  5  2 x  3 y  s  5, ( s  0) is
infeasible if x=y=0 .
 An artificial variable is a non-negative quantity added to the
left side of exactly one constraint of an LPP in standard form.
Enough artificial variables are added to the constraints so that
the resulting coefficient matrix contains an m m identity sub
matrix. although they are initially basic variables when we
apply the simplex method , artificial variables must be driven
out of the basic so that their values are zero in the final
solution.if this is not possible, then the problem is infeasible
(i.e. its feasible region has no extreme points)
 For instance , if we have 4x1  3x2  12 then introducing
surplus variable we have 4x1  3x2  s1  12 this equation
will not contribute to BFS ,therefore , we need to
introduce an artificial variable A1 as 4x1  3x2  s1  A1  12 .
 There are two standard methods for handling artificial
variables within the simplex method:
 The Big-M Method
 The Two-Phase Method
 These methods complete the study of the simplex
method and allow us to solve any L.P.P to find its
optimal solution or discover whether it is unbounded
or infeasible.
 Big –M Method

 Big –M Method is also called penalty method as for introducing

the artificial variables , we have to pay penalties . Following are
the steps for solving a problem having artificial variables using
Big-M Method :
 (1) write the given LPP in standard form .
 (2) add an artificial variable Ai to the constraints identified as 
 or = constraints. Also add the sign restriction Ai >0 .
 (3) if the LPP is a max problem , add (for each artificial
variable)  MAi to the objective function where M denotes a
very large positive number.
 (4) solve the transformed problem by the simplex . Since each
artificial variable will be in the starting basis, all artificial
variables must be eliminated from Z- row . In choosing the
entering variable, remember that M is a very large positive
number.
 For example, 4M-2 is more positive than 3M+900 and -6M-5 is
more negative than -5M-40 .
 (5) in the final simplex table observe that :
 (a) if all artificial variables are equal to zero in the optimal
solution , we have found the optimal solution to the original
problem.
 (b) if any artificial variables are positive in the optimal solution
, the original problem is infeasible .
Example: Minimize Z= 600X1+500X2
subject to constraints,
2X1+ X2 >or= 80
X1+2X2 >or= 60 and X1,X2 >or= 0
Step1: Convert the LP problem into a system of linear
equations.
We do this by rewriting the constraint inequalities as equations by
subtracting new “surplus & artificial variables" and assigning them
zero & +M coefficients respectively in the objective function as
shown below.
So the Objective Function would be:
Z=600X1+500X2+0.S1+0.S2+MA1+MA2
subject to constraints,
2X1+ X2-S1+A1 = 80
X1+2X2-S2+A2 = 60
X1,X2,S1,S2,A1,A2 >or= 0
Step 2: Obtain a Basic Solution to the problem.
We do this by putting the decision variables X1=X2=S1=S2=0,
so that A1= 80 and A2=60.
These are the initial values of artificial variables.
Step 3: Form the Initial Tableau as shown.

Cj 600 500 0 0 M M
Min.Ratio
Basic
Basic (XB/Pivotal
CB Variab X1 X2 S1 S2 A1 A2 Col.)
Soln(XB)
le (B)
M A1 80 2 1 -1 0 1 0 80
M A2 60 1 2 0 -1 0 1 60
Zj 3M 3M M M M M
Cj - Zj 600-3M 500-3M M M 0 0
It is clear from the tableau that X2 will enter and A2 will leave
the basis. Hence 2 is the key element in pivotal column. Now ,
the new row operations are as follows:
R2(New) = R2(Old)/2
R1(New) = R1(Old) - 1*R2(New)

Cj 600 500 0 0 M
Min.Ratio
Basic
Basic (XB/Pivota
CB Variab X1 X2 S1 S2 A1 l Col.)
Soln(XB)
le (B)
M A1 50 3 2 0 -1 1 2 1 100/3
500 X2 30 1 2 1 0 - 1/2 0 60
Zj 3M/2+250 500 M M/2-250 M
Cj - Zj 350-3M/2 0 M 250-M/2 0
It is clear from the tableau that X1 will enter and A1 will leave
the basis. Hence 2 is the key element in pivotal column.
Now,the new row operations are as follows:
R1(New) = R1(Old)*2/3
R2(New) = R2(Old) – (1/2)*R1(New)
Cj 600 500 0 0 Min.
Basic Ratio
Varia Basic (XB/P
CB X1 X2 S1 S2 ivotal
ble Soln(XB)
Col.)
(B)
600 X1 100/3 1 0 2 3 1 3
500 X2 40/3 0 1 1 3 2 3
Zj 600 500 700 3 400 3
Cj - Zj 0 0 700 3 400 3
Since all the values of (Cj-Zj) are either zero or positive and also
both the artificial variables have been removed, an optimum
solution has been arrived at with X1=100/3 X2=40/3

Z=80,000/3
Two –Phase Method

As the name suggests it contains two phases:

Phases-I In this phase , we change the objective function . All the
cost values , except for the artificial variables, are zero . Artificial
variables are given the cost values of (-1) each and the objective
function is maximized . Constraints are taken as they are given in
the equation. The problem is solved by simplex method . Once
we get rid of any artificial variable from the basis , we do not even
write it in the simplex table. When all the artificial variables are
removed from the basis , and z j  c j  0j then the value of the
new objective function will be zero. We end the phase-I.
Phase –II Starting table for this phase is the same as the last table of
phase-I (i.e. we start with the feasible solution obtained in phase
one). But the objective function is taken as the original given
objective function in maximization form and we proceed to optimize
it.
Example solve the following LPP by Two –Phase Method.

Min.z  x1  x2
s.to
2 x1  x2  4
x1  7 x2  7
x1 , x2  0
Solution: we first convert the minimization problem to

maximization Max.z   Min.z
s.to
2 x1  x2  x3  x5  4
x1  7 x2  x4  x6  7
xi  0, i  1to6
Phase –I The problem of phase –I is

Max.z  0.x1  0.x2  0.x3  0.x4  x5  x6

Here x5 , x6 are artificial variables.

Simplex table(1)
cj 0 0 0 0 -1 -1

CB B.V XB Y1 Y2 Y3 Y4 Y5 Y6 Mini ratio

-1 X5 4 2 1 -1 0 1 0 4/1

-1 X6 7 1 70 -1 0 1 7/7

Z j  CJ -3 -8 1 1 0 0
Simplex table(2)
cj 0 0 0 0 -1 -1

-1 X5 3 13/7 0 -1 1/7 1 - 1/7 21/13

0 X2 1 1/7 1 0 -1/7 0 1/7 7/1

Z j  CJ -13/7 0 1 -1/7 0 8/7

Incoming Out going

13/7 is the key element

Simplex table(3)
cj 0 0 0 0 -1 -1

0 x1 21/13 10 -7/13 1/13 7/13 -1/13

0 x2 10/13 0 1 1/13 -14/91 -1/13 14/91

Z j  CJ 0 0 0 0 1 1

All Z j  C J  0 j =1 to 6 . Max Z1 =0 and no artificial

variable in the basis.
Phase –II table(1)
cj -1 -1 0 0
B.V Y1 y2 y3 y4
CB XB
-1 X1 21/13 1 0 -7/13 1/13

-1 X2 10/13 0 1 1/13 -14/13

Z j  CJ 0 0 6/13 1/13

Z j  C J  0j  1,2,3,4.Thus the optimal solution is given by

X1=21/13 X2=10/13 Min.Z =31/13

Review question

Q.1solve the following L.P.P by simplex method.

Max.Z  4 x1  5 x2
s.to
x1  x2  3,3 x1  4 x2  10, all , x1 , x2  0
Q.2 solve the following L.P.P by big M- method.
Max.Z  x1  2 x2  3 x3  x4
s.to
x1  2 x2  3 x3  15,
2 x1  x2  5 x3  20
x1  2 x2  x3  x4  10
, all , x1 , x2 , x3 , x4  0
Review questions

Q.3 use two phase method to solve the following L.P.P.

Mini .Z  10 x1  3 x2
s.to
x1  2 x2  3,
x1  4 x2  4,
all , x1 , x2  0
Duality in linear programming
1. In physics and chemistry ,wave particle duality is a
conceptualization that all objects in our universe exhibits
properties of both waves and particles.
2. According to dictionary definition, dual means double. As
applied to linear programming , duality implies that a double
meaning can be attached to every linear programming
problem. It can be thought of as a primal problem or as the
dual problem. Unless we are told , it is not possible to
determine which interpretation someone is placing on a
given problem. Thus each LPP can be analyzed in two
different ways (primal and its dual),but having equivalent
solutions.
Each LPP (both maximization and minimization) stated in its
original form has association with another LPP called dual LPP or
in short dual , which is unique and is based on the same data. It is
immaterial which one of the two is called as the primal and which
one as dual as dual of the dual is primal:
if the general L.P problem is taken as
Max.Z p  cX
s.to
Eq.(I)
AX  b
X 0
where c  c1 , c2 ,......cn 1n

 a11 , a12    a1n 

 x1  a , a 
x   21 22        a2 n 
X   2  , A  ........................  and
 .   
  ........................ 
 xn  a , a    a 
 m1 m 2 mn 

b1 
b 
 2
b  . 
 
. 
bm 
  m1
Then attached to it , there exist another problem,

Min .Z D  b W T

s.to
Eq.(II)
A W c
T T

W 0
Where T , stands for the transpose of the matrix/vector and
 w1 
w 
 2
W  : 
 
: 
 wm 
  m1
 if (I) represent the primal problem, then (II) is the dual . In fact it
is immaterial , which problem is designated as the primal , since
the dual of a dual is primal. If the optimal solution of one is
known , the optimal solution to the other can be obtained from it
(without solving ) . These two problem possess very closely
related properties.
Note: if one of the constraints , in the primal , appear with an
equality sign.(say i th ) , then the corresponding variable wi will
be unrestricted in sign .
i.e. if ai1 x1  ai 2 x2  .........ain xn  bi then wi is unrestricted in
sign . We can give the following relationship between the primal
and its dual.
Relation between the primal and dual
Primal problem Dual problem

1. Objective function Minimize Z D  bTW

maximize Z p  cX
2. constraints: AX  b AT W  c T
th
3. i Constraint is an Wi  0
inequality
i th constraint is an Wi is unrestricted in sign
equation
4. X i  0 j th constraint is an
inequality
Xi is unrestricted in j th constraint is an
sign equation
5. Right hand side vector: b Right hand side vector : c T

6. Cost coefficients c Cost coefficients b T

Note: for every primal constraint there is a dual variable and
for every dual constraint is a primal variable.
About the optimal solution.
1.Max Z p= min Z D

2.(i) if the primal problem has an unbounded solution , then

the dual has no feasible solution .

(ii) if the primal solution has no solution then dual has

either no solution or an unbounded solution .
Example: if primal has no solution then dual also has no solution
Consider the primal problem as
x2
Max.Z  3 x1  4 x2
s.to
x1  x2  1
 x1  x2  0
x1 , x2  0

x1
 w2
Its dual is
Min.Z D   w1
s.to
w1  w2  3
 w1  w2  4 w1
w1 , w2  0

It is clear from the above example that

Primal and dual both can have no feasible solution
 Example write the dual of the following L.P.P
Max.Z P  2 x1  4 x2
s.to
2 x1  3 x2  48
x1  3 x2  42
x1  x2  21
x1 , x2  0

Solution: it is a maximization problem with all constraints having 

Sign .
 Max.Z P  2 x1  4 x2
s.to
2 x1  3 x2  48
x1  3 x2  42
x1  x2  21
x1 , x2  0

The dual is
Min.Z D  48w1  42 w2  21w3
s.to
2 w1  w2  w3  2
3w1  w2  w3  4
w1 , w2 , w3  0
https://www.youtube.com/watch?v=zDch07vVBxI
https://www.youtube.com/watch?v=8IRrgDoV8Eo
https://www.youtube.com/watch?v=aw7NBSje2iM
https://www.youtube.com/watch?v=MZ843Vvia0A
https://www.youtube.com/watch?v=oZqVDGFckZE
https://www.youtube.com/watch?v=UsqtzA9XmQE
https://www.youtube.com/watch?v=gmDwUCvOJQ8
Conclusion

Conclusion of this unit is that the term linear programming define

A particular class of optimization problems in which the
constraints of the system can be expressed as linear equations or
inequalities and the objective function is a linear function of the
design variables.
Linear programming (LP) techniques are widely used to solve a
number of military , economic , industrial and societal problems.
The primary reasons for its wide use are the availability of
commercial software to solve very large problems and the easy
with which data variation (sensitivity analysis) can be handled
through LP models.
Thank you
Mr. PRADEEP KUMAR
Assistant Prof. (Maths)
Dept. AIET
CONTENTS OF UNIT-III:-

INTRODUCTION

SOLUTION OF TRANSPORTATION PROBLEM

OPTIMALITY TEST

ASSIGNMENT PROBLEM

CONCLUSION
Introduction and definition
 Distributing any commodity from any group of supply centers, called
sources, to any group of receiving centers, called destinations, in such a
way as to minimize the total distribution cost (shipping cost).
 Total supply must equal total demand.
 If total supply exceeds total demand, a dummy destination, whose
demand equals the difference between the total supply and total
demand is created. Similarly if total supply is less than total demand, a
dummy source is created, whose supply
 equals the difference.
 All unit shipping costs into a dummy destination or out of a dummy
source are 0.
Example :1
Transportation Table:
Initial Solution of transportation problem
 1. North-west Corner rule
 1. Select the remaining variable in the upper left (northwest) corner
and note the supply remaining in the row, s, and the demand
remaining in the column, d.
 2. Allocate the minimum of s or d to this variable. If this minimum is s,
eliminate all variables in its row from future consideration and reduce
the demand in its column by s; if the minimum is d, eliminate all
variables in the column from future consideration and reduce the
supply in its row by d.
 REPEAT THESE STEPS UNTIL ALL SUPPLIES HAVE BEEN
ALLOCATED.
Total sipping cost = 2250
 2. Lowest Cost entry method
 1. For the remaining variable with the lowest unit cost,
determine the remaining supply left in its row, s, and the
remaining demand left in its column, d (break ties
arbitrarily).
 2. Allocate the minimum of s or d to this variable. If this
minimum is s, eliminate all variables in its row from future
consideration and reduce the demand in its column by s;
if the minimum is d, eliminate all variables in the column
from future consideration and reduce the supply in its row
by d.
 REPEAT THESE STEPS UNTIL ALL SUPPLIES HAVE
BEEN ALLOCATED.
Total sipping cost = 2065
 3. Vogel’s Approximation Method (VAM)
 1. For each remaining row and column, determine the difference
between the lowest two remaining costs; these are called the row
and column penalties.
 2. Select the row or column with the largest penalty found in step 1
and note the supply remaining for its row, s, and the demand
remaining in its column, d.
 3. Allocate the minimum of s or d to the variable in the selected row
or column with the lowest remaining unit cost. If this minimum is s,
eliminate all variables in its row from future consideration and reduce
the demand in its column by s; if the minimum is d, eliminate all
variables in the column from future consideration and reduce the
supply in its row by d.
 REPEAT THESE STEPS UNTIL ALL SUPPLIES HAVE BEEN
ALLOCATED.
Total sipping cost = 2030
The Stepping-Stone Method
 1. Find the current Cij–Zij values for each nonbasic variable
and select the one with the most negative Cij–Zij value as
the entering variable; if all Cij–Zij values are nonnegative,
the current solution is optimal.

 2. Determine which basic variable reaches 0 first when the

entering variable is increased.

 3. Determine a new basic solution and repeat the steps.

Step 1: Determine the Cij–Zij Values for the Nonbasic
Variables
 1. If Ui is the dual variable associated with the i-th supply
constraint, and Vj is the dual variable associated with the j-
th demand constraint, then for shipments from node i to
node j, one can find the corresponding Zij value by Zij = Ui -
Vj. Thus the Cij–Zij value for variable Xij is found by
 Cij - Zij = Cij - (Ui - Vj) = Cij - Ui + Vj
 2. Given that there is a redundant equation among the m n
constraints (and any of the m n constraints can be
considered the redundant one), one can show that the Ui or
Vj associated with the redundant equation is 0. Thus one Ui
or Vj can arbitrarily be selected and set to 0. Arbitrarily
choose U1 = 0.

 3. Since the Cij–Zij values for basic variables are 0 (i.e., Cij -
Ui + Vj = 0 for basic variables), we can easily solve for the
remaining values of the Ui’s and Vj’s from the m + n - 1
equations for the basic variables.
 4. Once the Ui’s and Vj’s have been determined, the Cij–Zij
values for the nonbasic variables can be calculated by
 Cij - Zij = Cij - Ui + Vj
Non-basic cells:

Note: X13 is the entering variable.

Step 2: Determine Which Current Basic Variable
Reaches 0 First

Note: 1. Cycle property

2. X12 is the leaving variable
Step 3: Determine the Next Transportation Table

Total shipping cost = 2020

{Improvement = 2 (-5) = 10 }
 2-(MODI) Method
 Find an initial basic feasible solution by some starting procedure. Then,
 1. Set U1 0. Solve for the other Ui’s and Vj’s by:
 Cij – Ui + Vj = 0 for basic variables.
 Then calculate the Cij–Zij values for nonbasic variables by:
 Cij – Zij = Cij – Ui + Vj
 Choose the nonbasic variable with the most negative Cij–Zij value as the
entering variable. If all Cij–Zij values are nonnegative, STOP; the current
solution is optimal.
 2. Find the cycle that includes the entering variable and some of the BASIC
variables. Alternating positive and negative changes on the cycle,
determine the “change amount” as the smallest allocation on the cycle at
which a subtraction will be made.
 3. Modify the allocations to the variables of the cycle found in step 2 by the
“change amount” and return to step 1.
 Note: there must be m + n - 1 basic variables for
the transportation simplex method to work!
 Add dummy source or dummy destination, if
necessary
 (m of sources and n of destinations)
Example:
Building Brick Company (BBC) has orders for 80 tons
of bricks at three suburban locations as follows:
Northwood -- 25 tons, Westwood -- 45 tons, and
Eastwood -- 10 tons. BBC has two plants, each of
which can produce 50 tons per week.
How should end of week shipments be made to
fill the above orders given the following delivery cost
per ton:
Northwood Westwood Eastwood
Plant 1 24 30 40
Plant 2 30 40 42
 Initial Transportation Table
Since total supply = 100 and total demand = 80, a
dummy destination is created with demand of 20 and
0 unit costs.
Northwood Westwood Eastwood Dummy Supply
24 30 40 0
Plant 1 50

30 40 42 0
Plant 2 50

Demand 25 45 10 20
Example:
 Lowest cost entry method
 Iteration 1: Tie for least cost (0), arbitrarily select x14.
Allocate 20. Reduce s1 by 20 to 30 and delete the
Dummy column.
 Iteration 2: Of the remaining cells the least cost is 24 for
x11. Allocate 25. Reduce s1 by 25 to 5 and eliminate the
Northwood column.
 Iteration 3: Of the remaining cells the least cost is 30 for
x12. Allocate 5. Reduce the Westwood column to 40 and
eliminate the Plant 1 row.
 Iteration 4: Since there is only one row with two cells
left, make the final allocations of 40 and 10 to x22 and
x23, respectively.
Example:
 Initial table

Northwood Westwood Eastwood Dummy Supply

24 30 40 0
Plant 1 25 5 20 50

30 40 42 0
Plant 2 40 10 50

Demand 25 45 10 20

Total transportation cost is $2770

 Iteration 1
 MODI Method
1. Set u1 = 0
2. Since u1 + vj = c1j for occupied cells in row 1, then
v1 = 24, v2 = 30, v4 = 0.
3. Since ui + v2 = ci2 for occupied cells in column 2,
then u2 + 30 = 40, hence u2 = 10.
4. Since u2 + vj = c2j for occupied cells in row 2,
then
10 + v3 = 42, hence v3 = 32.
 Iteration 1
 MODI Method (continued)
Calculate the reduced costs (circled numbers on the
next slide) by cij - ui + vj.
Unoccupied Cell Reduced Cost
(1,3) 40 - 0 - 32 = 8
(2,1) 30 - 24 -10 = -4
(2,4) 0 - 10 - 0 = -10
•Since some of the reduced cost are negative, the current solution is
not optimal.
• Cell (2,4) has the most negative; therefore, it will be the basic variable
that must be occupied in the next iteration.
Iteration 1 Table:
Northwood Westwood Eastwood Dummy ui

Plant 1 24 30 40 0 0
25 5 +8 20

30 40 42 0
Plant 2 10
-4 40 10 -10

vj 24 30 32 0
 Iteration 1
 Stepping Stone Method
The stepping stone path for cell (2,4) is (2,4), (1,4),
(1,2), (2,2). The allocations in the subtraction cells are
20 and 40, respectively. The minimum is 20, and
hence reallocate 20 along this path. Thus for the next
tableau:
x24 = 0 + 20 = 20 (0 is its current allocation)
x14 = 20 - 20 = 0 (blank for the next tableau)
x12 = 5 + 20 = 25
x22 = 40 - 20 = 20
The other occupied cells remain the same.
 Northwood Westwood Eastwood Dummy Supply

24 30 40 0
Plant 1 50
25 25

30 40 42 0
Plant 2 50
20 10 20

Demand 25 45 10 20

Total transportation cost is $2570 = 2770 – 10 (20)

 Iteration 2
 MODI Method
The reduced costs are found by calculating
the ui's and vj's for this tableau.
1. Set u1 = 0.
2. Since u1 + vj = cij for occupied cells in row 1, then
v1 = 24, v2 = 30.
3. Since ui + v2 = ci2 for occupied cells in column 2,
then u2 + 30 = 40, or u2 = 10.
4. Since u2 + vj = c2j for occupied cells in row 2,
then
10 + v3 = 42 or v3 = 32; and, 10 + v4 = 0 or v4 = -10.
 Iteration 2
 MODI Method (continued)
Calculate the reduced costs (circled numbers on
the next slide) by cij - ui + vj.
Unoccupied Cell Reduced Cost
(1,3) 40 - 0 - 32 = 8
(1,4) 0 - 0 - (-10) = 10
(2,1) 30 - 10 - 24 = -4
 Since there is still negative reduced cost for cell
(2,1), the solution is not optimal.
 Cell (2,1) must be occupied
Iteration 2 Table
Northwood Westwood Eastwood Dummy ui

Plant 1 24 30 40 0 0
25 25 +8 +10

30 40 42 0
Plant 2 10
-4 20 10 20

vj 24 30 36 -6
 Iteration 2
 Stepping Stone Method
The most negative reduced cost is = -4
determined by x21. The stepping stone path for this
cell is (2,1),(1,1),(1,2),(2,2). The allocations in the
subtraction cells are 25 and 20 respectively. Thus the
new solution is obtained by reallocating 20 on the
stepping stone path. Thus for the next tableau:
x21 = 0 + 20 = 20 (0 is its current allocation)
x11 = 25 - 20 = 5
x12 = 25 + 20 = 45
x22 = 20 - 20 = 0 (blank for the next tableau)
The other occupied cells remain the same.
 Northwood Westwood Eastwood Dummy Supply

24 30 40 0
Plant 1 50
5 45

30 40 42 0
Plant 2 50
20 10 20

Demand 25 45 10 20

Total cost is $2490 = 2570 - 4(20)

 Iteration 3
 MODI Method
The reduced costs are found by calculating
the ui's and vj's for this tableau.
1. Set u1 = 0
2. Since u1 + vj = c1j for occupied cells in row 1, then
v1 = 24 and v2 = 30.
3. Since ui + v1 = ci1 for occupied cells in column 2,
then u2 + 24 = 30 or u2 = 6.
4. Since u2 + vj = c2j for occupied cells in row 2,
then
6 + v3 = 42 or v3 = 36, and 6 + v4 = 0 or v4 = -6.
 Iteration 3
 MODI Method (continued)
Calculate the reduced costs (circled numbers on
the next slide) by cij - ui + vj.
Unoccupied Cell Reduced Cost
(1,3) 40 - 0 - 36 = 4
(1,4) 0 - 0 - (-6) = 6
(2,2) 40 - 6 - 30 = 4
Since all the reduced cost are nonnegative, the current
solution is optimal
 Iteration 3 Table
Since all the reduced costs are non-negative, this
is the optimal tableau.

Northwood Westwood Eastwood Dummy ui

24 30 40 0
Plant 1 5 45 +4 +6 0

30 40 42 0
Plant 2 20 +4 10 20 6

vj 24 30 36 -6
 Optimal Solution

From To Amount Cost

Plant 1 Northwood 5 120
Plant 1 Westwood 45 1,350
Plant 2 Northwood 20 600
Plant 2 Eastwood 10 420
Total Cost = $2,490
Review question
1. What is unbalanced transport problem?
2. What is degeneracy?

3. Solve the following transportation problem.

 Example

 https://www.youtube.com/watch?v=Q31jKiEXxdc
UNIT-III
ASSIGNMENT PROBLEM
CONTENTS

 Introduction

 Hungarian Method of Assignment Problems.

 Special Cases in Assignment Problems.

 Exercises
 The Assignment Problem (AP)
 Assignment problem is a special case of
Transportation problem with m=n and si=dj for all
i, and j.

 The Hungarian Algorithm

 solving the assignment problem of a least
 cost assignment of m workers to m jobs
 Assumptions:
 1. There is a cost assignment matrix for the m “people” to
be assigned to m “tasks.” (If necessary dummy rows or
columns consisting of all 0’s are added so that the numbers
of people and tasks are the same.)
 2. All costs are nonnegative.
 3. The problem is a minimization problem.
 The Hungarian Algorithm
 Initialization
 1. For each row, subtract the minimum number
from all numbers in that row.
 2. In the resulting matrix, subtract the minimum
number in each column from all numbers in the
column.
 Iterative Steps
 1. Make as many 0 cost assignments as possible. If all
workers are assigned, STOP; this is the minimum cost
assignment. Otherwise draw the minimum number of
horizontal and vertical lines necessary to cover all 0’s in
the matrix. (A method for making the maximum number
of 0 cost assignments and drawing the minimum number
of lines to cover all 0’s follows.)
 2. Find the smallest value not covered by the lines; this
number is the reduction value.
 3. Subtract the reduction value from all numbers not
covered by any lines. Add the reduction value to any
number covered by both a horizontal and vertical line.
 GO TO STEP 1.
 For small problems, one can usually determine the maximum
number of zero cost assignments by observation. For larger
problems, the following procedure can be used:
 Determining the Maximum Number of Zero-Cost
Assignments
 1. For each row, if only one 0 remains in the row, make that
assignment and eliminate the row and column from
consideration in the steps below.
 2. For each column, if only one 0 remains, make that
assignment and eliminate that row and column from
consideration.
 3. Repeat steps 1 and 2 until no more assignments can be made.
(If 0’s remain, this means that there are at least two 0’s in each
remaining row and column. Make an arbitrary assignment to
one of these 0’s and repeat steps 1 and 2.)

 Again, for small problems, the minimum number of lines

required to cover all the 0’s can usually be determined by
observation. The following procedure, based on network flow
arguments, can be used for larger problems:
 Drawing the Minimum Number of Lines to Cover
All 0’s
 1. Mark all rows with no assignments (with a “‧”).
 2. For each row just marked, mark each column that
has a 0 in that row (with a “‧”).
 3. For each column just marked, mark each row that
has an assignment in that column (with a “‧”).
 4. Repeat steps 2 and 3 until no more marks can be
made.
 5. Draw lines through unmarked rows and marked
columns.
Example:
Minimum uncovered
number
Minimum uncovered
number
 CONVERSION OF A MAXIMIZATION
PROBLEM TO A MINIMIZATION PROBLEM

 The Hungarian algorithm works only if the matrix is a cost

matrix. A maximization assignment problem can be converted
to a minimization problem by creating a lost opportunity matrix.
The problem then is to minimize the total lost opportunity.
 Q solve the given assignment problem. given profit
matrix Profit Matrix:
 J1 J2 J3 J4
 W1 67 58 90 55
 W2 58 88 89 56
 W3 74 99 80 22
 (D) 0 0 0 0
 The lost opportunity matrix given below is derived by
subtracting each number in the J1 column from 74, each
number in the J2 column from 99, each number in the J3
column from 90, and each number in the J4 from 56.
 J1 J2 J3 J4
 W1 7 41 0 1
 W2 16 11 1 0
 W3 0 0 10 34
 (D) 74 99 90 56

 The Hungarian algorithm can now be applied to this lost

opportunity matrix to determine the maximum profit set of
assignments.
Review questions
 Q.1 what is assignment problem ?
 Q.2 solve the following assignment problem

Machine A B C D E
jobs
1 10 20 4 24 8
2 8 20 6 28 12
3 12 26 8 32 12
4 14 28 8 36 18
5 16 28 12 36 24
 Q.3 solve the following assignment problems
(unbalanced problems)

Resources J1 J2 J3 J4
and
workers
W1 7 5 8 4

W2 5 6 7 4

W3 8 7 9 8
Problems of maxmization
 A maximization assignment problem can be converted to a
minimization problem by creating a lost opportunity matrix
using any of the following methods. The problem then is to
minimize the total lost opportunity. The first method is by
putting a negative sign before the values in the assignment
matrix and then solves the sum as a minimization case using
Hungarian methods.
 Second method is to locate the largest value in the given
matrix and subtract each element in the matrix from this value
.then one can solve this problem as a minimization case using
the new modified matrix .
Example:
 A company has a team of four salespersons and there are
four districts where the company wants to start its business
.after taking into account the capabilities of salesman and
nature of districts, the company estimates the profit per
day in rupees for each salesman for each district given in
the following table:
District I II III IV
and
salesman
A 16 10 14 11
B 14 11 15 15
C 15 15 13 12
D 13 12 14 15
Travelling salesman problem(TSP)
 Travelling salesman problem is a routine problem. It can be
considered as a typical assignment problem with certain
restrictions . Consider a salesman who is assigned the job
of visiting n different cities . He knows(is given) the
distance (or time) between all pairs of cities . He is asked to
visit each of the cities only once. The trip should be
continuous and he should come back to the city from
where he started using the shortest route . It does not
matter , from which city he starts. These restrictions imply:
 (i) no assignment should be made along the diagonal
,going directly from city i to j is not permitted . Therefore
diagonal elements are generally taken very large i.e. 
Mathematical formulation
 A travelling salesman has to visit n cities and return to the starting
point. He has to start from any one city and visit each city only once .
The objective is to select the sequence which the cities are visited in
such a way that the total travelling distance(or time) is minimized .
Suppose he starts from the kth , city and the last he visited is m. let the
cost of travel from ith , city to jth city be Cij .then the objective function
is m n
Minimize   cij xij
i 1 j 1

x
i 1
ij  1, for, i  1,2,......m, i  j ,i  m

 Subject to the constraints n

x
j 1
ij  1, for, j  1,2,......n, i  j , j  n

xmk  1
xij  0or1
Working procedure
 Step-1 solve the problem as an assignment problem using the
method used to solve the above examples.
 Step-2 (a) if the solution thus found out are cyclic in nature
,then that is the final solution.
(b) if it is not cyclic ,then go to step-3.
 Step-3 select the lowest entry in the table ( other than zero).
Delete the row and column of this lowest entry and again do
the zero assignment in the remaining matrix.
 Step-4 check whether cyclic assignment is available.If not,
include the next higher entry in the table and the procedure is
repeated until a cyclic assignment is obtained.
Example
 Consider a four city TSP for which the cost between the city
pairs are as shown in the figure below. Find the tour of the
salesman so that the cost of travel is minimal.
2
6 8
4
1 5 4

9 9
3
Solution
 Construct the cost matrix as follows:
1 2 3 4

1  6 9 5

2 6  4 8

3 9 4  9

4
5 8 9 
Step-1

1 2 3 4

1  0 5 0

2
2  4 8

3 9 4  9


4 0 3 4 
 The optimal assignment is 1  4,2  3,3  2,4  1
Which is not cyclic.
Step-2 consider the lowest entry ‘2’ of the cell (2,1) . If there is
a tie in selecting the lowest entry, then break the tie
arbitrarily. Delete the II row and I column . Do the zero
assignment in the remaining matrix . The resulting table is
:-
1 2 3 4
1  0 4 0

2 2  0 3

3 5 0  4

4 0 3 0 
 Next optimal assignment is
1  4,2  1,3  2,4  3
Which is cyclic.
https://www.youtube.com/watch?v=q7VMzOTZvqM
https://www.youtube.com/watch?v=BUGIhEecipE
 Conclusion
 The transportation problem is a special class of the linear
programming problem. It deals with the situation in which a
commodity is transported from sources(origins) to
destinations. The objective is to determine the amount of
commodity to be transported from each source to each
destination so that the total transportation cost is minimum.
 The Assignment problem is special from of the transportation
problem with equal number of sources and destination and
supply at each source and demand at each destination is limited
to one unit.
 The name “assignment problem” originates from the classical
problem where the objective is to assign a number of
origins(job) to the equal number of destinations(persons) at
minimum cost(or maximum profit) travelling salesman
problem is a special type of assignment problem.
Thank you