Problem 2: Multiple Choice Questions (32 pts) 2. Consider the feasible region (in blue) of the linear program below: 00 1. Consider the network below with nodes represented in red circles and links in black lines. All links are bi-directional and have the same cost in both directions. The number next to each link is the cost of this link. 35 50 8 7 45 3 411 4 9 2 35 90 4 11 0 8 14 4 25 211 6 8 10 -15 7 6 5 10 5 5 Let node O be the source node. In which order are the nodes visited when implementing Dijkstra's algorithm to this network? (8 pts) 0 10 5 S 10 15 20 25 30 35 40 45 50 55 60 -5 a. 0, 1, 7, 6, 5, 2, 8, 3, 4 b. 0,1,7,6, 2, 5, 8, 3, 4 c. 0, 1, 7, 6, 5, 2, 3, 8,4 If the x-axis represents variable x1 and the y-axis represents variable x2, and if the objective function is: maximise 25*1 + 25*x2, what is the optimal solution of this problem? (6 pts) a. x1=50, X2-0 b. x1=0, x2 = 55 C. x1-20, X2-45 3. Select the statements which are true. (6 pts) Select one or more: a. In an integer program, the number of solutions is always lesser or equal than the number of constraints. b. In an integer program, relaxing the the integrality restriction on the decision variables does not always change the optimal solution. In an integer program, the number of solutions is always greater than the number of constraints. d. In an integer program, if a solution exists, the optimal solution cannot have fractional values. C