Definition: Linear programming (LP) is a
mathematical modeling technique
useful for the allocation of ‘scarce’ or
‘Limited’ resources such as man
material, machine, time, space,
capacity, energy etc.
Assignment and Transportation are two
special cases of Linear Programming.
An assignment problem seeks to minimize the total
cost assignment of m workers to m jobs, given that
the cost of worker i performing job j is cij.
It assumes all workers are assigned and each job is
performed.
An assignment problem is a special case of a
transportation problem in which all supplies and all
demands are equal to 1; hence assignment
problems may be solved as linear programs.
The network representation of an assignment
problem with three workers and three jobs is shown
on the next slide.
Network Representation
c11
1 1
c12
c13
c21
2
c22 2
c23
c32
c31
3 c33 3
WORKERS JOBS
Working Rules and Guidelines
Step1: Check if Assignment matrix (AM)
is balanced. {A balanced AM is that
matrix where number of rows = no. of
columns}. If AM is balanced, no
adjustment is required. However if AM is
unbalanced, then add appropriately a
dummy row/column to balance the
matrix.
Step2: Check if AM is a cost matrix. If it is cost matrix,
the value of the cell of the dummy row/columns are taken
as ‘M’{‘M’ is a very high positive value}. However if it is a
profit matrix, the value of the dummy row/columns are
taken as ‘Zero’. Further if it is a cost matrix, no further
adjustments are required. However if it is profit matrix, then
convert it into an equivalent cost matrix, by using the
following mathematical relation.
Cij =P – Pij
› Where “Cij “is the cost value of the cell corresponding to the ith
row and jth column,
› Pij is the corresponding profit value and
› P = (Pij) max
Step3: Simplify the matrix {Cost
balanced matrix} by performing Row
Minima and Column Minima operations {
The sequence of Performing Row Minima
& Column Minima is arbitrary}
Step4: Test the simplified solution for the
optimality. If the simplified solution passes
the optimality test, we conclude that it is an
optimum solution.
However if it fails the optimality test then we
conclude that it is not an optimum solution.
In such a case, we modify the solution
through a procedure of “θ” adjustment.
Test the modify solution for optimality.
Continue the procedure of “θ” adjustment
and testing for optimality till we reach the
optimal solution.
Step5: Perform allocation of jobs to
facilities
Step6: Calculate total Cost/ total profit
with reference to the optimum allocation
using data given in the optimal sources
matrix.
Additional Notes:
Row Minima Operations: Identify for
the each row, the minimum value.
Subtract this minimum value from all the
cells of that row. Continue this procedure
for all the rows of the matrix.
Additional Notes:
Column Minima: Identify for each
column the minimum value. Subtract this
minimum value from all the cells of that
column. Continue this procedure for all
the column of the matrix.
Testing the solution for Optimality:
Proceed row wise. Identify a row with a
single zero.
Enclose this zero in a square bracket
cancel the remaining zeros with a
cross(x) corresponding to this column.
Continue this procedure till all the row
with a single zero is identified.
If in a row there is more than one zero,
leave the zeros unmarked.
Identify the row without a square bracket
and without unmarked zero.
Put √1 for the row.
Starting from this row, identify crossed zeros.
Corresponding to this column Put √2 .
Starting from this column identify square
bracket. Corresponding to this row put √3.
Continue this procedure till all the
appropriate rows and columns have been
indicated by a √.
Draw lines across the row without the √ mark
and line across the column with the √ mark.
Count the numbers of lines drawn.
If the number of lines drawn = number of
rows/columns, it means we have reached
the optimum solution.
However if number of lines drawn ≠ number
of rows/columns it means we have not
reached an optimum solution. In such cases
modify the solution through a procedure of
“θ” adjustment.
Modification of solution (“θ” adjustment ):
Select the value of θ corresponding to the
minimum value of an uncovered cell.
Subtract the value of θ from all the
uncovered cells of the matrix.
Add the value of θ to all the cell at the
intersection of the lines drawn
The remaining cells, which are covered but
which are not at the intersection of the lines
drawn, remain unchanged.
Allocation of the job facilities:
Zeros in the square brackets are the guides
for the allocation. It signifies least cost
allocation for that row.
The sequence of performing row minima &
column minima for an unbalance AM , from
the point of view of convenience of
calculations, will depend on the nature of
the adjustment e.g. If adjustment is in the
form of a dummy row, we perform row
minima first.
Six contractors submitted quotation for
six projects. It was decided that one
contractor should be given one contract
as otherwise it was feared that the time
for completion & quality of workmanship
will be affected. The estimates given by
each of them on all the contracts in
thousands of Rupees are given below:
Contra Quotation for the Project (Rs. In thousands)
ctor
I II III IV V VI
A 41 72 39 52 25 51
B 22 29 49 65 81 50
C 27 39 69 51 32 32
D 45 50 48 52 37 43
E 29 40 39 26 30 33
F 82 40 40 50 51 30
Determine the optimal allocation of the projects to
the contractors and the corresponding total cost.
Five laths are to be allotted to 5 operators.
Table below gives weekly output figures:
Operato Weekly output in Lathe Machine (L)
r
L1 L2 L3 L4 L5
A 18 20 25 30 34
B 17 21 27 32 38
C 21 26 33 37 32
D 19 22 29 35 40
E 22 26 29 34 39
Profit per piece is Rs. 10. Find the optimum
allocation of Lathe machine (L) to the operator
and the corresponding maximum profit per
week
The marketing director of a multi unit
company [Link] is faced with a
problem of assigning 5 senior and 1 junior
Marketing Mnagers for zones. From past
experience he knows that the efficiency
% judged by sales, operating cost,
increase in marketing share etc.
Depends a ot on manager- zone
combinations as shown in the table
below:
Senior Efficiency % zone
Marketi I II III IV V VI
ng
Manag
er
A 73 91 87 82 78 80
B 81 85 69 76 74 85
C 75 72 83 84 78 91
D 93 96 86 91 83 82
E 90 91 79 89 69 76
Advice Mr. Wagle as to which zone to be
given to the junior manager because of
non- availability of one more senior
marketing manager, so that the overall
efficiency is maximized.
A city corporation has decided to carry out
road repairs on 4 main arteries of the city.
The government has agreed to make a
special grant of Rs. 50 lakhs towards the
cost with the condition that the repairs must
be done at the lowest cost and the
quickest time. If conditions warrant, then a
supplementary token grant will also be
considered favourably. The corporation has
floated tenders and 5 contractors have
sent in their bids. In order to expedite work 1
road will be awarded to only 1 contractor.
The following are details of the road repairs:
Cost of repairs of the roads(Rs. Lakhs)
Contractor R1 R2 R3 R4
C1 9 14 19 15
C2 7 17 20 19
C3 9 18 21 18
C4 10 12 18 19
C5 10 15 21 16
Find the best way of assigning repairing
work to the contractors and the
corresponding costs?
If it is necessary to seek supplementary
grants, then what should be the amount
sought?
Which of the 5 contractors will be
unsuccessful in his bid?
A pen manufacturing company is engaged in
manufacturing ballpoints pens. Company has
4 machines to manufacture refills for the pens;
M1, M2, M3 & M4. Company has four operators
O1, O2, O3 & O4 to operate these machines.
Any operator can operate any type of
machine but the production output depends
on who is operating which machine. One
operator will not be allowed to work on two
machines simultaneously and so no two
operators will work on one machine. The
production manager has formulated following
matrix for the quantity (in ‘000 numbers):
Operator Machines
M1 M2 M3 M4
O1 15 13 8 12
O2 12 15 11 14
O3 16 13 8 13
O4 10 16 10 17
Find out the optimum solution to maximize
the total production
On one particular day operator O4 was on
leave. What would be the new optimum
solution with the reaming 3 operators? How
much production is lost due to this?
Operator O2 has suggested to work on
machine M2 since he can give the
maximum output on the machine. If the
production manager decides to accept his
claim, what will be the effect on the
optimum solution?
A solicitor’s firm employs typists on a
hourly price rate basis for their daily work.
There are five typists and their charges &
speed are different. According to an
early understanding only one job is given
to one typist and thee typist is paid for a
full hour even if he works for a fraction of
hour. Find thee least cost allocation for
the following data.
Typist Rates No. Of pages Job No. Of pages
per hour (Rs.) typed/hr
A 5 12 P 199
B 6 14 Q 175
C 3 8 R 145
D 4 10 S 298
E 4 11 T 178
Five men are available to do five
different jobs. From past records, the
time in hours that each man can take to
do each job is known and given in the
following table:
Man Job
I II III IV V
A 2 9 2 7 1
B 6 8 7 6 1
C 4 6 5 3 1
D 4 2 7 3 1
E 5 3 5 9 1
Determine an optimum allocation of job to
the man and the corresponding total time.
In the modification of the plant layout
four new machines M1, M2, M3 & M4 are
to be installed in a machine shop. There
are five vacant places A, B, C, D and E
available. Because of limited space
machine M2 cannot be placed at C
and M3 cannot be placed at A. The cost
of machine i at place j (in rupees) is
shown below:
Machine Location
A B C D E
M1 9 11 15 10 11
M2 12 9 - 10 9
M3 - 11 14 11 7
M4 14 8 12 7 8
Find the optimal assignment of location for the machines?
An airline company has drawn up a new
flight schedule involving five flights. To
assist in allocating five pilots to the flights,
it has asked them to state the
preference score by giving each flight a
number out of 10. The higher the
number, the greater is the preference.
Certain of these flights are unsuitable to
some pilots owing to domastic reasons.
These have been marked with an X.
Pilots Flight number
A B C D E
A 8 2 X 5 4
B 10 9 2 8 4
C 5 4 9 6 X
D 3 6 2 8 7
E 5 6 10 4 3
What should be the allocation of pilots to flights
in order to meet as many preferences as possible?