بحوث العمليات للسنة الثالثة قسم علوم الحاسوب

18.1 Introduction to Assignment Problem
In assignment problems, the objective is to assign a number of jobs to the equal number of
persons at a minimum cost of maximum profit.
lecture 18
Assignment problem :
Introduction and Hungarian method
Suppose there are ‘n’ jobs to be performed and ‘n’ persons are available for doing these jobs.
Assume each person can do each job at a time with a varying degree of efficiency. Let cij be the
cost of ith person assigned to jth job. Then the problem is to find an assignment so that the total
cost for performing all jobs is minimum. Such problems are known as assignment problems.
These problems may consist of assigning men to offices, classes to the rooms or problems to the
research team etc.
Mathematical formulation
Cost matrix: cij= c11 c12 c13 … c1n
c21 c22 c23 … c2n
.
.
.
cn1 cn2 cn3 … cnn
Subject to restrictions of the form
Where xij denotes that jth job is to be assigned to the ith person.
This special structure of assignment problem allows a more convenient method of solution in
comparison to simplex method.
1
18.2 Algorithm for Assignment Problem (Hungarian Method)
Step 1
Subtract the minimum of each row of the effectiveness matrix, from all the elements of the
respective rows (Row reduced matrix).
Step 2
Further modify the resulting matrix by subtracting the minimum element of each column from all
the elements of the respective columns. Thus first modified matrix is obtained.
Step 3
Draw the minimum number of horizontal and vertical lines to cover all the zeroes in the resulting
matrix. Let the minimum number of lines be N. Now there may be two possibilities
? If N = n, the number of rows (columns) of the given matrix then an optimal assignment
can be made. So make the zero assignment to get the required solution.
? If N < n then proceed to step 4
Step 4
Determine the smallest element in the matrix, not covered by N lines. Subtract this minimum
element from all uncovered elements and add the same element at the intersection of horizontal
and vertical lines. Thus the second modified matrix is obtained.
Step 5
Repeat step 3 and step 4 until minimum number of lines become equal to number of rows
(columns) of the given matrix i.e. N = n.
Step 6
To make zero assignment - examine the rows successively until a row-wise exactly single zero is
found; mark this zero by ‘1’‘to make the assignment. Then, mark a ‘X’ over all zeroes if lying in
the column of the marked zero, showing that they cannot be considered for further assignment.
Continue in this manner until all the rows have been examined. Repeat the same procedure for
the columns also.
Step 7
Repeat the step 6 successively until one of the following situations arise
? If no unmarked zero is left, then process ends
? If there lies more than one of the unmarked zeroes in any column or row, then mark
‘1’‘one of the unmarked zeroes arbitrarily and mark a cross in the cells of remaining
zeroes in its row and column. Repeat the process until no unmarked zero is left in the
matrix.
Step 8
Exactly one marked zero in each row and each column of the matrix is obtained. The assignment
corresponding to these marked zeroes will give the optimal assignment.
2
18.3 Worked Examp les
Example 1
A department head has four subordinates and four tasks have to be performed. Subordinates
differ in efficiency and tasks differ in their intrinsic difficulty. Time each man would take to
perform each task is given in the effectiveness matrix. How the tasks should be allocated to each
person so as to minimize the total man-hours?
Tasks
Subordinates
I II III IV
A 8 26 17 11
B 13 28 4 26
C 38 19 18 15
D 19 26 24 10
Solution
Row Reduced Matrix
0 18 9 3
9 24 0 22
23 4 3 0
9 16 14 0
I Modified Matrix
N = 4, n = 4
Since N = n, we move on to zero assignment
Zero assignment
Total man-hours = 8 + 4 + 19 + 10 = 41 hours
3
Example 2
A car hire company has one car at each of five depots a, b, c, d and e. a customer requires a car
in each town namely A, B, C, D and E. Distance (kms) between depots (origins) and towns
(destinations) are given in the following distance matrix
a b c d e
A 160 130 175 190 200
B 135 120 130 160 175
C 140 110 155 170 185
D 50 50 80 80 110
E 55 35 70 80 105
Solution
Row Reduced Matrix
30 0 45 60 70
15 0 10 40 55
30 0 45 60 75
0 0 30 30 60
20 0 35 45 70
I Modified Matrix
N < n i.e. 3 < 5, so move to next modified matrix
II Modified Matrix
N = 5, n = 5
Since N = n, we move on to zero assignment
Zero assignment
4
Minimum distance travelled = 200 + 130 + 110 + 50 + 80 = 570 kms
5

19.1
Unbalanced Assignment Problems
If the number of rows and columns are not equal then such type of problems are called as
unbalanced assignment problems.
Example
A company has 4 machines on which to do 3 jobs. Each job can be assigned to one and only one
machine. The cost of each job on each machine is given in the following table
Machines
Jobs
W X Y Z
A 18 24 28 32
B 8 13 17 19
C 10 15 19 22
Solution
Lecture 19
Assignment problem :
Unbalanced and maximal Assignment Problems
18 24 28 32
8 13 17 19
10 15 19 22
0 0 0 0
Row Reduced matrix
0 6 10 14
0 5 9 11
0 5 9 12
0 0 0 0
I Modified Matrix
N < n i.e. 2 < 4
II Modified Matrix
1
N < n i.e. 3 < 4
III Modified Matrix
N = n
Zero assignment
Multiple assignments exists
Solution -I
Minimum cost = 18 + 13 + 19 = Rs 50
Solution -II
Minimum cost = 18 + 17 + 15 = Rs 50
2
19.2 Maximal Assignment Problem
Example
A company has 5 jobs to be done. The following matrix shows the return in terms of rupees on
assigning ith ( i = 1, 2, 3, 4, 5 ) machine to the jth job ( j = A, B, C, D, E ). Assign the five jobs to
the five machines so as to maximize the total expected profit.
Jobs
Machines
A B C D E
1 5 11 10 12 4
2 2 4 6 3 5
3 3 12 5 14 6
4 6 14 4 11 7
5 7 9 8 12 5
Solution
Subtract all the elements from the highest element
Highest element = 14
9 3 4 2 10
12 10 8 11 9
11 2 9 0 8
8 0 10 3 7
7 5 6 2 9
Row Reduced matrix
7 1 2 0 8
4 2 0 3 1
11 2 9 0 8
8 0 10 3 7
5 3 4 0 7
I Modified Matrix
N < n i.e. 3 < 5
II Modified Matrix
3
N < n i.e. 4 < 5
III Modified Matrix
N = n
Zero assignment
Optimal assignment 1 – C 2 – E 3 – D 4 – B 5 – A
Maximum profit = 10 + 5 + 14 + 14 + 7 = Rs. 50
4

Game theory is a type of decision theory in which one’s choice of action is determined after
taking into account all possible alternatives available to an opponent playing the same game,
rather than just by the possibilities of several outcome results. Game theory does not insist on
how a game should be played but tells the procedure and principles by which action should be
selected. Thus it is a decision theory useful in competitive situations.
Game is defined as an activity between two or more persons according to a set of rules at the end
of which each person receives some benefit or suffers loss. The set of rules defines the game.
Going through the set of rules once by the participants defines a play.
20.2 Properties of a Gam e
1. There are finite numbers of competitors called ‘players’
2. Each player has a finite number of possible courses of action called ‘strategies’
3. All the strategies and their effects are known to the players but player does not know
which strategy is to be chosen.
4. A game is played when each player chooses one of his strategies. The strategies are
assumed to be made simultaneously with an outcome such that no player knows his
opponents strategy until he decides his own strategy.
5. The game is a combination of the strategies and in certain units which determines the
gain or loss.
6. The figures shown as the outcomes of strategies in a matrix form are called ‘pay-off
matrix’.
7. The player playing the game always tries to choose the best course of action which
results in optimal pay off called ‘optimal strategy’.
8. The expected pay off when all the players of the game follow their optimal strategies is
known as ‘value of the game’. The main objective of a problem of a game is to find the
value of the game.
9. The game is said to be ‘fair’ game if the value of the game is zero otherwise it s known as
‘unfair’.
20.3 Characteristics of Game Th eory
1. Competitive game
A competitive situation is called a competitive game if it has the following four properties
1. There are finite number of competitors such that n ? 2. In case n = 2, it is called a twoperson
game and in case n > 2, it is referred as n-person game.
2. Each player has a list of finite number of possible activities.
3. A play is said to occur when each player chooses one of his activities. The choices are
assumed to be made simultaneously i.e. no player knows the choice of the other until he
has decided on his own.
20.1 Introduction to Game Theo ry
Lecture 19
Game Theory :
Solving Two Person and Zero - Sum Game
1
20
4. Every combination of activities determines an outcome which results in a gain of
payments to each player, provided each player is playing uncompromisingly to get as
much as possible. Negative gain implies the loss of same amount.
2. Strategy
The strategy of a player is the predetermined rule by which player decides his course of action
from his own list during the game. The two types of strategy are
1. Pure strategy
2. Mixed strategy
Pure Strategy
If a player knows exactly what the other player is going to do, a deterministic situation is
obtained and objective function is to maximize the gain. Therefore, the pure strategy is a
decision rule always to select a particular course of action.
Mixed Strategy
If a player is guessing as to which activity is to be selected by the other on any particular
occasion, a probabilistic situation is obtained and objective function is to maximize the
expected gain. Thus the mixed strategy is a selection among pure strategies with fixed
probabilities.
3. Number of persons
A game is called ‘n’ person game if the number of persons playing is ‘n’. The person means an
individual or a group aiming at a particular objective.
Two-person, zero-sum game
A game with only two players (player A and player B) is called a ‘two-person, zero-sum
game’, if the losses of one player are equivalent to the gains of the other so that the sum
of their net gains is zero.
Two-person, zero-sum games are also called rectangular games as these are usually
represented by a payoff matrix in a rectangular form.
4. Number of activities
The activities may be finite or infinite.
5. Payoff
The quantitative measure of satisfaction a person gets at the end of each play is called a payoff
6. Payoff matrix
Suppose the player A has ‘m’ activities and the player B has ‘n’ activities. Then a payoff matrix
can be formed by adopting the following rules
? Row designations for each matrix are the activities available to player A
? Column designations for each matrix are the activities available to player B
? Cell entry Vij is the payment to player A in A’s payoff matrix when A chooses the
activity i and B chooses the activity j.
2
? With a zero-sum, two-person game, the cell entry in the player B’s payoff matrix will be
negative of the corresponding cell entry Vij in the player A’s payoff matrix so that sum of
payoff matrices for player A and player B is ultimately zero.
7. Value of the game
Value of the game is the maximum guaranteed game to player A (maximizing player) if both the
players uses their best strategies. It is generally denoted by ‘V’ and it is unique.
20.4 Classification of Game s
All games are classified into
? Pure strategy games
? Mixed strategy games
The method for solving these two types varies. By solving a game, we need to find best
strategies for both the players and also to find the value of the game.
Pure strategy games can be solved by saddle point method.
The different methods for solving a mixed strategy game are
? Analytical method
? Graphical method
? Dominance rule
? Simplex method
20.5 Solving Two-Person and Zero-Sum Game
Two-person zero-sum games may be deterministic or probabilistic. The deterministic games will
have saddle points and pure strategies exist in such games. In contrast, the probabilistic games
will have no saddle points and mixed strategies are taken with the help of probabilities.
Definition of saddle point
A saddle point of a matrix is the position of such an element in the payoff matrix, which is
minimum in its row and the maximum in its column.
Procedure to find the saddle point
? Select the minimum element of each row of the payoff matrix and mark them with
circles.
? Select the maximum element of each column of the payoff matrix and mark them with
squares.
? If their appears an element in the payoff matrix with a circle and a square together then
that position is called saddle point and the element is the value of the game.
Solution of games with saddle point
To obtain a solution of a game with a saddle point, it is feasible to find out
3
? Best strategy for player A
? Best strategy for player B
? The value of the game
The best strategies for player A and B will be those which correspond to the row and column
respectively through the saddle point.
Examples
Solve the payoff matrix
Ex ample -1
Player B
Player A
I II III IV V
I -2 0 0 5 3
II 3 2 1 2 2
III -4 -3 0 -2 6
IV 5 3 -4 2 -6
Solution
Strategy of player A – II
Strategy of player B - III
Value of the game = 1
B1 B2 B3 B4
A1 1 7 3 4
A2 5 6 4 5
4
Example -2
A3 7 2 0 3
Solution
Strategy of player A – A2
Strategy of player B – B3
Value of the game = 4
5

21.1 Games with Mixed Strategies
In certain cases, no pure strategy solutions exist for the game. In other words, saddle point does
not exist. In all such game, both players may adopt an optimal blend of the strategies called
Mixed Strategy to find a saddle point. The optimal mix for each player may be determined by
assigning each strategy a probability of it being chosen. Thus these mixed strategies are
probabilistic combinations of available better strategies and these games hence called
Probabilistic games.
The probabilistic mixed strategy games without saddle points are commonly solved by any of the
following methods
Sl.
No. Method Applicable to
1 Analytical Method 2x2 games
2 Graphical Method 2x2, mx2 and 2xn games
3 Simplex Method 2x2, mx2, 2xn and mxn games
21.1.1 Analytical Method
A 2 x 2 payoff matrix where there is no saddle point can be solved by analytical method.
Given the matrix
Value of the game is
With the coordinates
Alternative procedure to solve the strategy


Lecture 21
Game Theory :
Games with Mixed Strategies
( analytic and graphic methods )
1
? Find the difference of two numbers in column 1 and enter the resultant under column 2.
Neglect the negative sign if it occurs.
? Find the difference of two numbers in column 2 and enter the resultant under column 1.
Neglect the negative sign if it occurs.
? Repeat the same procedure for the two rows.
1. Solve
Solution
It is a 2 x 2 matrix and no saddle point exists. We can solve by analytical method
V = 17 / 5
SA = (x1, x2) = (1/5, 4 /5)
SB = (y1, y2) = (3/5, 2 /5)
2. Solve the given matrix
Solution
V = - 1 / 4
SA = (x1, x2) = (1/4, 3 /4)
SB = (y1, y2) = (1/4, 3 /4)
2
The graphical method is used to solve the games whose payoff matrix has
? Two rows and n columns (2 x n)
? m rows and two columns (m x 2)
Algorithm for solving 2 x n matrix games
? Draw two vertical axes 1 unit apart. The two lines are x1 = 0, x1 = 1
? Take the points of the first row in the payoff matrix on the vertical line x1 = 1 and the
points of the second row in the payoff matrix on the vertical line x1 = 0.
? The point a1j on axis x1 = 1 is then joined to the point a2j on the axis x1 = 0 to give a
straight line. Draw ‘n’ straight lines for j=1, 2… n and determine the highest point of the
lower envelope obtained. This will be the maximin point.
? The two or more lines passing through the maximin point determines the required 2 x 2
payoff matrix. This in turn gives the optimum solution by making use of analytical
method.
Example 1
Solve by graphical method
Solution
3
21.1.2 Graphical method
V = 66/13
SA = (4/13, 9 /13)
SB = (0, 10/13, 3 /13)
Example 2
Solve by graphical method
Solution
V = 8/7
SA = (3/7, 4 /7)
SB = (2/7, 0, 5 /7)
Algorithm for solving m x 2 matrix games
? Draw two vertical axes 1 unit apart. The two lines are x1 =0, x1 = 1
4
? Take the points of the first row in the payoff matrix on the vertical line x1 = 1 and the
points of the second row in the payoff matrix on the vertical line x1 = 0.
? The point a1j on axis x1 = 1 is then joined to the point a2j on the axis x1 = 0 to give a
straight line. Draw ‘n’ straight lines for j=1, 2… n and determine the lowest point of the
upper envelope obtained. This will be the minimax point.
? The two or more lines passing through the minimax point determines the required 2 x 2
payoff matrix. This in turn gives the optimum solution by making use of analytical
method.
Example 1
Solve by graphical method
Solution
5
V = 3/9 = 1/3
SA = (0, 5 /9, 4/9, 0)
SB = (3/9, 6 /9)
Example 2
Solve by graphical method
Solution
6
V = 73/17
SA = (0, 16/17, 1/17, 0, 0)
SB = (5/17, 12 /17)
7

22.1 Simplex Method
Let us consider the 3 x 3 matrix
As per the assumptions, A always attempts to choose the set of strategies with the non-zero
probabilities say p1, p2, p3 where p1 + p2 + p3 = 1 that maximizes his minimum expected gain.
Similarly B would choose the set of strategies with the non-zero probabilities say q1, q2, q3 where
q1 + q2 + q3 = 1 that minimizes his maximum expected loss.
Step 1
Find the minimax and maximin value from the given matrix
Step 2
The objective of A is to maximize the value, which is equivalent to minimizing the value 1/V.
The LPP is written as
Min 1/V = p1/V + p2/V + p3/V
and constraints ? 1
It is written as
Min 1/V = x1 + x2 + x3
and constraints ? 1
Similarly for B, we get the LPP as the dual of the above LPP
Max 1/V = Y1 + Y2 + Y3
and constraints ? 1
Where Y1 = q1/V, Y2 = q2/V, Y3 = q3/V
Lecture 22
Game Theory :
Simplex Method
Step 3
Solve the LPP by using simplex table and obtain the best strategy for the players
1
Example 1
Solve by Simplex method
Solution
We can infer that 2 ? V ? 3. Hence it can be concluded that the value of the game lies between 2
and 3 and the V > 0.
LPP
Max 1/V = Y1 + Y2 + Y3
Subject to
3Y1 – 2Y2 + 4Y3 ? 1
-1Y1 + 4Y2 + 2Y3 ? 1
2Y1 + 2Y2 + 6Y3 ? 1
Y1, Y2, Y3 ? 0
SLPP
Max 1/V = Y1 + Y2 + Y3 + 0s1 + 0s2 + 0s3
Subject to
3Y1 – 2Y2 + 4Y3 + s1 = 1
-1Y1 + 4Y2 + 2Y3 + s2 =1
2Y1 + 2Y2 + 6Y3 + s3 = 1
Y1, Y2, Y3, s1, s2, s3 ? 0
2
Cj? 1 1 1 0 0 0
Basic
Variables CB YB Y1 Y2 Y3 S1 S2 S3 Min Ratio
YB / YK
S1 0 1 3 -2 4 1 0 0 1/3?
S2 0 1 -1 4 2 0 1 0 -
S3 0 1 2 2 6 0 0 1 1/2
1/V = 0
?
-1
-1
-1
0
0
0
Y1 1 1/3 1 -2/3 4/3 1/3 0 0 -
S2 0 4/3 0 10/3 10/3 1/3 1 0 2/5
S3 0 1/3 0 10/3 10/3 -2/3 0 1 1/10?
1/V =1/3
0
?
-5/3
1/3
1/3
0
0
Y1 1 2/5 1 0 2 1/5 0 1/5
S2 0 1 0 0 0 1 1 -1
Y2 1 1/10 0 1 1 -1/5 0 3/10
1/V = 1/2
0
0
2
0
0
1/2
1/V =1/2
V = 2
y1 = 2/5 * 2 = 4/5
y2 = 1/10 * 2 = 1/5
y3 = 0 * 2 = 0
x1 = 0*2 = 0
x2 = 0*2 = 0
x3 = 1/2*2 = 1
SA = (0, 0, 1)
SB = (4/5, 1/5, 0)
Value = 2
Example 2
3
Solution
Maximin = -1
Minimax = 1
We can infer that -1 ? V ? 1
Since maximin value is -1, it is possible that value of the game may be negative or zero, thus the
constant ‘C’ is added to all the elements of matrix which is at least equal to the negative of
maximin.
Let C = 1, add this value to all the elements of the matrix. The resultant matrix is
LPP
Max 1/V = Y1 + Y2 + Y3
Subject to
2Y1 + 0Y2 + 0Y3 ? 1
0Y1 + 0Y2 + 4Y3 ? 1
0Y1 + 3Y2 + 0Y3 ? 1
Y1, Y2, Y3 ? 0
SLPP
Max 1/V = Y1 + Y2 + Y3 + 0s1 + 0s2 + 0s3
Subject to
2Y1 + 0Y2 + 0Y3 + s1 = 1
0Y1 + 0Y2 + 4Y3 + s2 = 1
0Y1 + 3Y2 + 0Y3 + s3 = 1
Y1, Y2, Y3, s1, s2, s3 ? 0
4
Cj? 1 1 1 0 0 0
Basic
Variables CB YB Y1 Y2 Y3 S1 S2 S3 Min Ratio
YB / YK
S1 0 1 2 0 0 1 0 0 1/2?
S2 0 1 0 0 4 0 1 0 -
S3 0 1 0 3 0 0 0 1 -
1/V =0
?
-1
-1
-1
0
0
0
Y1 1 1/2 1 0 0 1/2 0 0 -
S2 0 1 0 0 4 0 1 0 -
S3 0 1 0 3 0 0 0 1 1/3?
1/V =1/2
0
?
-1
-1
1/2
0
0
Y1 1 1/2 1 0 0 1/2 0 0 -
S2 0 1 0 0 4 0 1 0 1/4?
Y2 1 1/3 0 1 0 0 0 1/3 -
1/V = 5/6
0
0
?
-1
1/2
0
1/3
Y1 1 1/2 1 0 0 1/2 0 0
Y3 1 1/4 0 0 1 0 1/4 0
Y2 1 1/3 0 1 0 0 0 1/3
1/V =13/12
0
0
0
1/2
1/4
1/3
1/V =13/12
V = 12/13
y1 = 1/2 * 12/13 = 6/13
y2 = 1/3 * 12/13 = 4/13
y3 = 1/4 * 12/13 = 3/13
x1 = 1/2*12/13 = 6/13
x2 = 1/4 * 12/13 = 3/13
x3 = 1/3 * 12/13 = 4/13
SA = (6/13, 3/13, 4/13)
SB = (6/13, 4/13, 3/13)
Value = 12/13 – C =12/13 -1 = -1/13
5