Advertisements
Advertisements
प्रश्न
Give mathematical form of Assignment problem
उत्तर
Consider the problem of assigning n jobs to n machines (one job to one machine).
Let Cij be the cost of assigning ith job to the jth machine and xij represents the assignment of ith job to the jth machine.
Then, xij = `{{:(1",", "if" "i"^"th" "job is assigned to" "j"^"th" "machine"),(0",", "if" "i"^"th" "job is assigned to" "j"^"th" "machine"):}`
| Machines | ||||||
| 1 | 2 | … | n | Supply | ||
| 1 | `""^((x_11))"C"_11` | `""^((x_12))"C"_12` | … | `""^((x_(1n)))("C"_(1n))` | 1 | |
| 2 | `""^((x_21))"C"_21` | `""^((x_22))"C"_22` | … | `""^((x_(2n)))("C"_(2n))` | 1 | |
| Jobs | : | : | : | : | 1 | |
| m | `""^((x_"ij"))"C"_("n"1)` | `""^((x_(m2)))"C"_("n"1)` | … | `""^((x_"ij"))("C"_"nn")` | 1 | |
| Demand | b1 | b2 | … | bn | ||
xij is missing in any cell means that no assignment is made between the pair of job and machine.
i.e xij = 0.
xij is presents in any cell means that an assignment is made their.
In such cases xij = 1
The assignment model can written in LPP as follows:
Minimize Z = `sum_("i" = 1)^"m", sum_("j" = 1)^"n" "C"_"ij" "X"_"ij"`
Subject to the constrains
`sum_("i" = 1)^"n" "X"_"ij"` = 1, j = 1, 2, …. n
`sum_("i" = 1)^"n" "X"_"ij"` = 1, i = 1, 2, …. n and xij =0 or 1 for all i, j
APPEARS IN
संबंधित प्रश्न
A departmental head has three jobs and four subordinates. The subordinates differ in their capabilities and the jobs differ in their work
contents. With the help of the performance matrix given below, find out which of the four subordinates should be assigned which jobs ?
| Subordinates | Jobs | ||
| I | II | III | |
| A | 7 | 3 | 5 |
| B | 2 | 7 | 4 |
| C | 6 | 5 | 3 |
| D | 3 | 4 | 7 |
The objective of an assignment problem is to assign ______.
Solve the following problem :
A dairy plant has five milk tankers, I, II, III, IV and V. These milk tankers are to be used on five delivery routes A, B, C, D and E. The distances (in kms) between the dairy plant and the delivery routes are given in the following distance matrix.
| I | II | III | IV | V | |
| A | 150 | 120 | 175 | 180 | 200 |
| B | 125 | 110 | 120 | 150 | 165 |
| C | 130 | 100 | 145 | 160 | 175 |
| D | 40 | 40 | 70 | 70 | 100 |
| E | 45 | 25 | 60 | 70 | 95 |
How should the milk tankers be assigned to the chilling center so as to minimize the distance travelled?
Choose the correct alternative:
The assignment problem is generally defined as a problem of ______
Choose the correct alternative:
The assignment problem is said to be balanced if ______
What is the Assignment problem?
Three jobs A, B and C one to be assigned to three machines U, V and W. The processing cost for each job machine combination is shown in the matrix given below. Determine the allocation that minimizes the overall processing cost.
| Machine | ||||
| U | V | W | ||
| Jobs | A | 17 | 25 | 31 |
| B | 10 | 25 | 16 | |
| C | 12 | 14 | 11 | |
(cost is in ₹ per unit)
Choose the correct alternative:
The solution for an assignment problem is optimal if
A car hire company has one car at each of five depots a, b, c, d and e. A customer in each of the fine towers A, B, C, D and E requires a car. The distance (in miles) between the depots (origins) and the towers(destinations) where the customers 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 |
How should the cars be assigned to the customers so as to minimize the distance travelled?
Five wagons are available at stations 1, 2, 3, 4 and 5. These are required at 5 stations I, II, III, IV and V. The mileage between various stations are given in the table below. How should the wagons be transported so as to minimize the mileage covered?
| I | II | III | IV | V | |
| 1 | 10 | 5 | 9 | 18 | 11 |
| 2 | 13 | 9 | 6 | 12 | 14 |
| 3 | 7 | 2 | 4 | 4 | 5 |
| 4 | 18 | 9 | 12 | 17 | 15 |
| 5 | 11 | 6 | 14 | 19 | 10 |
