Question

Bidder Distribution Hub 1 2 3 4 A 190 175 125 230 B 150 235 155 220 C 210 225 135 260 D 170 185 190 280 E 220 190 140 240 F 270 200 130 260 a. Develop the network of the problem. (1 Marks) b. Formulate the problem as a linear programming problem. (2 Marks) c. Solve assignment that minimizes total cost. (2 Marks)

Answer 1

Answer a:

We can draw a network diagram for the given problem as mentioned below:

A 190 175 125 230 1 150 B 235 155 220 210 225 135 260 Bidder Distribution Hub 170 3 185 190 280 D 190 140 220 240 E 200 130 270 260 Cost F

Answer b:

We will formulate the given problem as a linear programming model as mentioned below:

Decision Variables:

Let i= A Particular Bidder = A, B, C, D, E, F and j = A particular distribution Hub = 1, 2, 3, 4

Then, Cij = Cost of assigning the bidder 'i' to a distribution hub 'j'

Xij = { 1 if a bidder 'i' is assigned to a distribution hub 'j' | 0 otherwise }

Objective Function:

m n Min . Z=2 EC; Xij i=1 j=1

Where m = Total No. of Bidders = 6, n = Total No. of distribution hubs = 4

Subject to Constraints:

n C1 = XX,j=1 Where j = 1, 2,...,n, and i=1 m C2 = XX,j=1 Where i = 1, 2,...,m j=1

Xij = {0 , 1}

Answer c:

As no specific information is mentioned in the question, we will solve the given assignment problem by following the steps of the Hungarian Method of Task (Job) Assignment as mentioned below:

We are given the following problem-table:

1 2 3 4 A 190 175 125 230 B 150 235 155 220 C 210 225 135 260 D 170 185 190 280 E 220 190 140 240 F 270 200 130 260

Step 1: Here given problem is unbalanced, so add 2 new columns with the cost as '0' o convert it into a balance:

1 23 5 6 + 190 175 125 23000 B 150 235 155 22000 C 210 225 135 260 0 D 170 185 190 280 0 0 E 220 190 140 240 00 F 270 200 130 26000

Step 2: Pick a minimum element from each row and subtract it from that row:

1 2 3 4 5 6 190175 125 23000 (0) B 150 235 155 22000 (0) C 210 225 135 260 0 0 (0) D 170 185 190 28000 (0) E 220 190 140 240 0 0 (0) F 270 200 130 2600 0 (0)

Step 3: Now, find out each column minimum element and subtract it from that column:

1 2 زرا 4 5 6 А 40 0 0 10 0 0 B 0 60 30 0 0 0 C 60 50 10 40 0 0 D 20 10 65 600 0 E 70 15 15 20 0 0 F 120 25 5 40 0 0 (-150) (-175) (-125) (-220) (0) (0)

Step 4: Draw a set of horizontal and vertical lines to cover all the '0s' by following the substeps as mentioned below:
a. Tick(✓) mark all the rows in which no assigned 0.
b. Examine Tick(✓) marked rows, If any 0 cell occurs in that row, then tick(✓) mark that column.
c. Examine Tick(✓) marked columns, If any assigned 0 exists in that columns, then tick(✓) mark that row.
d. Repeat this process until no more rows or columns can be marked.
e. Draw a straight line for each unmarked rows and marked columns.

Hence, we get:

1 2 3 4. 5 6 40 € o 0 10 В 0 60 300 • с 60 50 10 40 D20 1065 60 0 E 70 70 15 15 20 0 F 120 25 5 400

Step 5: Develop the new revised table by selecting the smallest element, among the cells not covered by any line (say k = 5)
Subtract k = 5 from every element in the cell not covered by a line.
Add k = 5 to every element in the intersection cell of two lines.

1 2 3 4 5 6 400 0 0 105 5 0 60 30 0 5 5 B C 55 45 5 35 00 D 155 60 5500 E 65 | 10 | 10 | 150 0 F 115 200 35 00

Step 6:

Here, follow the sub-steps as mentioned below to draw a set of horizontal and vertical lines:

1|2|3 4 3 6 A 40 10 0 10] 本 年 4-49 B 年 C 4 55 [5] $135| 中 D||5|||| 5519 65 | || 15| 中 E F 115| 22 | 35 | 中

Step 7:

Develop the new revised table by selecting the smallest element, among the cells not covered by any line (say k = 10)
Subtract k = 10 from every element in the cell not covered by a line.
Add k = 10 to every element in the intersection cell of two lines.

1 23 45 6 A 30 0005 5 B 0 7 70 40 0 15 15 с 45 45 5 5 25 0 0 D 5 5 60 45 0 0 E 55 10 10 105 50 0 F 105 200 0 25 0 0

Step 8:

Here, follow the sub-steps as mentioned below to draw a set of horizontal and vertical lines:

2 3 4 1 5 6 年 A 中 由 中 中 B gm845 並 C 45 145 「25」中 D15 5|5 60 45 | 中 E 55 |10| 015 中 F 105| 20 中 | 25 中

Step 9: Develop the new revised table by selecting the smallest element, among the cells not covered by any line (say k = 5)
Subtract k = 5 from every element in the cell not covered by a line.
Add k = 5 to every element in the intersection cell of two lines.

1 2 3 4 5 6 A 30 0 5 0 10 10 B 0 70 45 0 20 20 с 40 40 5 40 5 20 200 0 D 0 0 60 40 00 50 5 10 0 0 0 15 0 200 E F 100 150

Step 10:

Here, follow the sub-steps as mentioned below to draw a set of horizontal and vertical lines:

2 نما 4 5 6 1 30 A 0 $ 1° | 10 | 16 B 70450 20 20 с 40 40 $ 20 D 0 6040 E 50 50 $ 100 F 100 15 20

There are 6 lines required to cover all zeros, which is equal to the size of the matrix (6), so an optimal assignment exists and the algorithm stops.

Thus, we get the optimal assignments as mentioned in the below table:

1 2 3 4 5 6 30 [0] 5 50 10 10 10 B [0] 70 45 0 20 20 40 40 5 20 0010 с D 0 0 60 40 | 0 [0] E 50 5 10 [0] 0 0 F 100 15 [O] 200 0

Hence, the optimal solution:

Bidder Hub A 2 B 1 E 4 F 3 Min Cost Cost 175 150 240 130 695

Note: Bidders C and D would remain unassigned.

(Kindly raise an upvote for this answer, if you found it useful)