Question

BUST 252 BONUS TAKE-HOME 1) ABC company_wants to transport goods from three factories to three distribution centers. Information about the move is given below. Source Supply A 200 Destination Demand X 50 Y B 100 125 с 150 Z 125 O Destination Source X Y X A 3 2 5 B 9 10 С 5 6 4 (Source B cannot ship to destination 2) a) Give the network model of the problem b) Write the_linear programming model for this problem and solve the problem with excel. c) Interpret the solution 2) Ali Ayşe and Mehmet can do three different jobs in a computer company about the project related to distance education. They receive a premium for each project. Find which employee should be assigned to which project to minimize the premium payment of the company? The premium amounts to be earned for each project are given in the table below. You can solve your problem with 0-1 integer programming method by using Excel or you can solve the problem by using Hungarian method. Employee Ali Ayşe Mehmet Software Design 15 8 PREMIUMS Software Development 10 5 Quality Control 9 12 5 6 7

The Hungarian algorithm: An example

We consider an example where four jobs (J1, J2, J3, and J4) need to be executed by four workers (W1, W2, W3, and W4), one job per worker. The matrix below shows the cost of assigning a certain worker to a certain job. The objective is to minimize the total cost of the assignment.

	J1	J2	J3	J4
W1	82	83	69	92
W2	77	37	49	92
W3	11	69	5	86
W4	8	9	98	23

Below we will explain the Hungarian algorithm using this example. Note that a general description of the algorithm can be found here.

Step 1: Subtract row minima

We start with subtracting the row minimum from each row. The smallest element in the first row is, for example, 69. Therefore, we substract 69 from each element in the first row. The resulting matrix is:

	J1	J2	J3	J4
W1	13	14	0	23	(-69)
W2	40	0	12	55	(-37)
W3	6	64	0	81	(-5)
W4	0	1	90	15	(-8)

Step 2: Subtract column minima

Similarly, we subtract the column minimum from each column, giving the following matrix:

	J1	J2	J3	J4
W1	13	14	0	8
W2	40	0	12	40
W3	6	64	0	66
W4	0	1	90	0
				(-15)

Step 3: Cover all zeros with a minimum number of lines

We will now determine the minimum number of lines (horizontal or vertical) that are required to cover all zeros in the matrix. All zeros can be covered using 3 lines:

	J1	J2	J3	J4
W1	13	14	0	8
W2	40	0	12	40	x
W3	6	64	0	66
W4	0	1	90	0	x
			x

Because the number of lines required (3) is lower than the size of the matrix (n=4), we continue with Step 4.

Step 4: Create additional zeros

First, we find that the smallest uncovered number is 6. We subtract this number from all uncovered elements and add it to all elements that are covered twice. This results in the following matrix:

	J1	J2	J3	J4
W1	7	8	0	2
W2	40	0	18	40
W3	0	58	0	60
W4	0	1	96	0

Now we return to Step 3.

Step 3: Cover all zeros with a minimum number of lines

Again, We determine the minimum number of lines required to cover all zeros in the matrix. Now there are 4 lines required:

	J1	J2	J3	J4
W1	7	8	0	2	x
W2	40	0	18	40	x
W3	0	58	0	60	x
W4	0	1	96	0	x

Because the number of lines required (4) equals the size of the matrix (n=4), an optimal assignment exists among the zeros in the matrix. Therefore, the algorithm stops.

The optimal assignment

The following zeros cover an optimal assignment:

	J1	J2	J3	J4
W1	7	8	0	2
W2	40	0	18	40
W3	0	58	0	60
W4	0	1	96	0

This corresponds to the following optimal assignment in the original cost matrix:

	J1	J2	J3	J4
W1	82	83	69	92
W2	77	37	49	92
W3	11	69	5	86
W4	8	9	98	23

Thus, worker 1 should perform job 3, worker 2 job 2, worker 3 job 1, and worker 4 should perform job 4. The total cost of this optimal assignment is to 69 + 37 + 11 + 23 = 140.

Answer 1

A Network Diagram: SOURCE DESTINATION 3 200 A Х 50 2 5 9 10 100 B Y 125 5 6 Z 150 125 B) Decision variables: Xij = Quantity shipped from Source i (=A,B,C) to destination ; (=X,Y,Z) Objective Function: Min 3Xax + 2Xay + 5Xaz + 9Xbx + 10Xby + 5Xcx + 6Xcy + 4Xcz Subject to constraints, Xax + Xay + Xaz <= 200 Xbx + Xby + Xbz <= 100 Xcx + Xcy + Xcz <= 150 Xax + Xbx + Xcx = 50 Xay + Xby + Xcy = 125 Xaz + Xbz + Xcz = 125 Xij >= 0

Optimal Solution, using Excel Solver: A B c. D E F G н тік L M N OP 1 2 Xb Xby Xbz Xex Хcy Xcz LHS RHS Xax 1 Xay 1 Xaz 1 3 A 125 0 200 100 1 1 1 C 1 1 1 150 5 5 7 x 1 1 1 50 150 50 125 125 1 1 1 = 8 Y z Total 1 1 1 = 125 9 3 2 5 9 10 5 0 4 900 Destination Variable 125 0 0 O 0 0 0 a 125 10 11 12 13 14 15 Therefore, Optimal objective value = 900 Solver Parameters х Set Objective: SL $10 To: Max Min Value of: 0 By Changing Variable Cells: $C$11 Subject to the Constraints: SL $3:$L$5 <= $N$3:$N$5 SL $6: $L$8 <= $N$6: SN$8 Add Change Delete Reset All Load/Save Make Unconstrained Variables Non-Negative Select a Solving Method: Simplex LP Options Solving Method Select the GRG Nonlinear engine for Solver Problems that are smooth nonlinear. Select the LP Simplex engine for linear Solver Problems, and select the Evolutionary engine for Solver problems that are non-smooth. Help Solve Close

c). The optimal shipping schedule is X Y Z A 50 125 0 В 0 0 0 125 O Minimized shipping cost = 900