Advertisements
Advertisements
प्रश्न
Give mathematical form of Assignment problem
Advertisements
उत्तर
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
संबंधित प्रश्न
Determine `l_92 and l_93, "given that" l_91 = 97, d_91 = 38 and q_92 = 27/59`
The assignment problem is said to be balanced if ______.
Fill in the blank :
When an assignment problem has more than one solution, then it is _______ optimal solution.
Choose the correct alternative:
The assignment problem is generally defined as a problem of ______
Choose the correct alternative:
Assignment Problem is special case of ______
Choose the correct alternative:
When an assignment problem has more than one solution, then it is ______
State whether the following statement is True or False:
The objective of an assignment problem is to assign number of jobs to equal number of persons at maximum cost
Choose the correct alternative:
In an assignment problem involving four workers and three jobs, total number of assignments possible are
A department store has four workers to pack goods. The times (in minutes) required for each worker to complete the packings per item sold is given below. How should the manager of the store assign the jobs to the workers, so as to minimize the total time of packing?
| Workers | Packing of | |||
| Books | Toys | Crockery | Cutlery | |
| A | 3 | 11 | 10 | 8 |
| B | 13 | 2 | 12 | 12 |
| C | 3 | 4 | 6 | 1 |
| D | 4 | 15 | 4 | 9 |
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 |
