Optimization Techn Industr Eng exam

Final Exam

Instead of floating point arithmetic, it is recommended to do arithmetic with fractions. Solve the problems using the methods you learned in class (Optional ways you google will not earn any point).

 

 

NAME:

SIGN:

Total:               /25

 

 

1-1	1-2	1-3	1-4	1-5
/0	/2	/2	/2	/3

 

 

2-1	2-2	2-3	2-4	3-1
/2	/2	/2	/3	/3

 

 

3-2
/4

 

 

1. We are solving the max flow problem.

1-1. (0 point) The initial flow is as follows with the flow value = 3.

Variable	Value
xs1	1
xs3	2
x12	0
x14	1
x32	2
x34	0
x2t	2
x4t	1
Flow Value =	3

 

 

 

 

1-2. (2 points) The residual network of the flow in 1-1 is illustrated as follows. Fill in the residual capacities in the table. Overdraw an augmenting path with the solid lines. What is the capacity of the augmenting path?

 

Arc	Residual Capacity		Arc	Residual Capacity
(s,1)			(1,s)
(s,3)			(3,s)
(1,2)			(2,1)
(1,4)			(4,1)
(3,2)			(2,3)
(3,4)			(4,3)
(2,t)			(t,2)
(4,t)			(t,4)
Capacity of the augmenting path =                          .

 

 

 

 

 

 

 

 

 

 

 

 

 

1-3. (2 points) What is the new flow augmented by the path flow in 1-2? (Fill in the blanks in the table on the right.) And, what is the new flow value?

Variable	Value
xs1
xs3
x12
x14
x32
x34
x2t
x4t
Flow Value =

 

 

 

 

1-4. (2 points) Fill in the blanks of the table with the residual capacities on the residual network of the new flow.

 

Arc	Residual Capacity		Arc	Residual Capacity
(s,1)			(1,s)
(s,3)			(3,s)
(1,2)			(2,1)
(1,4)			(4,1)
(3,2)			(2,3)
(3,4)			(4,3)
(2,t)			(t,2)
(4,t)			(t,4)

 

 

 

 

 

 

 

 

 

 

 

 

 

1-5. (2 points) Certify with a cut (S, T), s  S and t  T, that the new flow is optimal. Explicitly write the nodes of S and T, and overdraw the cut edges with solid lines on the figure. What is the cut capacity?

 

Answer: S = {                                 }, T = {                                   }, Cut Capacity =                     .

 

 

 

 

 

2. Perform the network simplex method to solve the minimum cost network flow problem beginning with the initial basis B = {x_s2 = 3, x_2t = 3, x_1t = 5, x_3t = 4}. The non-basic variables are x_s1 = 5 and x_s3 = 4, x₂₁ = 0 and x₂₃ = 0. In every iteration, dual variable π_s = 0.

2-1. (2 points) Overdraw the initial basic arcs with the solid lines in the following figure. Calculate and write the dual variables. Calculate and write the reduced costs of the non-basic variables.

 

Dual variable	Value
πs	0
π1
π2
π3
πt

 

Non-basic variable	Value	Reduced cost
xs1	5
xs3	4
x21	0
x23	0

 

 

 

2-2. (2 points) Is the initial basis optimal? Circle (Yes/No) If No, overdraw with solid arcs the cycle along which the circular flow θ flows in the figure and fill in the blanks in the table.

Variable	Value	Basic/non-basic (B/N?)	Reduced Cost	Check the entering arc ( v )	Value update over the cycle (old ± θ = new)	Check the leaving arc and write the value of θ
xs2	3	B	0
x2t	3	B	0
x1t	5	B	0
x3t	4	B	0
xs1	5	N
xs3	4	N
x21	0	N
x23	0	N

 

2-3. (2 points) Overdraw the basic arcs with the solid lines in the following figure. Calculate and write the dual variables. Calculate and write the reduced costs of the non-basic variables.

 

Dual variable	Value
πs	0
π1
π2
π3
πt

 

Non-basic variable	Value	Reduced cost

 

 

 

2-4. (2 points) Is the basis optimal? Circle (Yes/No) If No, overdraw with solid arcs the cycle along which the circular flow θ flows in the figure and fill in the blanks in the table.

Variable	Value	Basic/non-basic (B/N?)	Reduced Cost	Check the entering arc ( v )	Value update over the cycle (old ± θ = new)	Check the leaving arc and write the value of θ
xs2
x2t
x1t
x3t
xs1
xs3
x21
x23

 

 

3. Consider the assignment problem with the following cost matrix C = ( c­_ij ), where c_ij is the cost to assign worker i to job j.

5    8    7    3    2

4    3    3    7    5

4    8    5    3    3

3    6    5    2    5

2    7    5    6    8

 

3-1. (3 points) Explicitly write down an LP formulation of the assignment problem.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3-2. (4 points) Solve the problem using Excel Solver and submit your Excel Worksheet.