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
संबंधित प्रश्न
Solve the following minimal assignment problem :
| Machines | A | B | C | D | E |
| M1 | 27 | 18 | ∞ | 20 | 21 |
| M2 | 31 | 24 | 21 | 12 | 17 |
| M3 | 20 | 17 | 20 | ∞ | 16 |
| M4 | 21 | 28 | 20 | 16 | 27 |
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 |
A job production unit has four jobs A, B, C, D which can be manufactured on each of the four machines P, Q, R and S. The processing cost of each job for each machine is given in the following table:
| Jobs | Machines (Processing Cost in ₹) |
|||
| P | Q | R | S | |
| A | 31 | 25 | 33 | 29 |
| B | 25 | 24 | 23 | 21 |
| C | 19 | 21 | 23 | 24 |
| D | 38 | 36 | 34 | 40 |
Find the optimal assignment to minimize the total processing cost.
Choose the correct alternative :
In an assignment problem if number of rows is greater than number of columns then
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
Find the optimal solution for the assignment problem with the following cost matrix.
| Area | |||||
| 1 | 2 | 3 | 4 | ||
| P | 11 | 17 | 8 | 16 | |
| Salesman | Q | 9 | 7 | 12 | 6 |
| R | 13 | 16 | 15 | 12 | |
| S | 14 | 10 | 12 | 11 | |
Choose the correct alternative:
Number of basic allocation in any row or column in an assignment problem can be
Choose the correct alternative:
North – West Corner refers to ______
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 |
