Linear Programming Exercise

TRUE & FALSE

1. In the Assignment problem, all suppliers have a supply of 1 and all consumers have a supply of -1 (demand of 1). T/F

2. The Assignment problem is a special case of the Transportation problem. T/F

3. If a cycle exists in a graph, we can use Dynamic Programming for DAG to find the shortest path. T/F

4. Let P be the shortest path from some node s to some other node t in a graph. If the weight of each arc in the graph is increased by 2, P will remain as the shortest path from s to t. T/F

5. Let P be the shortest path from some node s to some other node t in a graph. If the weight of each arc in the graph is doubled, P will remain as the shortest path from s to t. T/F

6. In an Activity-On-Node graph of project management, if the arc from activity 3 to activity 5 is not on the critical path, then the shadow price of constraint

t_5 - t_3 >= d_3 where d_3 is the current duration of activity 3, is 0. T/F

7. Suppose you have a project you want to expedite. There are expediting costs for each day of each activity. There is a penalty of $30 for each day the project extends beyond 10 days and there is a reward of $40 for every day the project finishes under 10 days. You want to minimize the total cost. Can you solve this problem with a single LP?