Consider the following activity-on-arc project network,where the 12 arcs (arrows)represent the 12 activities (tasks)that must be performed to complete the project and the network displays the order in which the activities need to be performed.The number next to each arc (arrow)is the time required for the corresponding activity.Consider the problem of finding the longest path (the largest total time)through this network from start (node 1)to finish (node 9),since the longest path is the critical path.Formulate a BIP model for this problem.

Question

Quizplus · Accepted Answer

The Answer is Let

Let The time required for activity (i,j)will become the coefficient of x<sub>ij</sub> in the objective function being maximized in the BIP model.The model also will need some functional constraints to ensure that a feasible solution defines one continuous path from node 1 to node 9.In particular,the critical path needs to include exactly one activity leading out of node 1 and exactly one activity leading into node 9.Similarly,for each of the other nodes,the critical path needs to include either zero or one activity leading into that node and the same number of activities leading out of that node.These observations lead to the following BIP model.Maximize Z = 5 x<sub>12</sub> + 3 x<sub>13</sub> + 4 x<sub>24</sub> + 2 x<sub>25</sub> + 3 x<sub>35</sub> + x<sub>46</sub> + 4 x<sub>47</sub> + 6 x<sub>57</sub> + 2 x<sub>58 </sub>+ 5 x<sub>69</sub> + 4 x<sub>79</sub> + 7 x<sub>89</sub>,subject to x<sub>12</sub> + x<sub>13</sub> = 1 x<sub>12 </sub> -x<sub>24</sub>- x<sub>25</sub> = 0 x<sub>13</sub> - x<sub>35</sub> = 0 x<sub>24</sub> - x<sub>46</sub> - x<sub>47</sub> = 0 x<sub>25</sub> + x<sub>35</sub> - x<sub>57</sub> - x<sub>58</sub> = 0 x<sub>46</sub> - x<sub>69</sub> = 0 x<sub>47</sub> + x<sub>57</sub> - x<sub>79</sub> = 0 x<sub>58</sub> - x<sub>89</sub> = 0 x<sub>69</sub> + x<sub>79</sub> + x<sub>89</sub> = 1 and x<sub>ij</sub><sub> </sub> is binary,for each activity (i,j).

The time required for activity (i,j)will become the coefficient of x_ij in the objective function being maximized in the BIP model.The model also will need some functional constraints to ensure that a feasible solution defines one continuous path from node 1 to node 9.In particular,the critical path needs to include exactly one activity leading out of node 1 and exactly one activity leading into node 9.Similarly,for each of the other nodes,the critical path needs to include either zero or one activity leading into that node and the same number of activities leading out of that node.These observations lead to the following BIP model.Maximize Z = 5 x₁₂ + 3 x₁₃ + 4 x₂₄ + 2 x₂₅ + 3 x₃₅ + x₄₆ + 4 x₄₇ + 6 x₅₇ + 2 x₅₈+ 5 x₆₉ + 4 x₇₉ + 7 x₈₉,subject to x₁₂ + x₁₃ = 1 x₁₂ -x₂₄- x₂₅ = 0 x₁₃ - x₃₅ = 0 x₂₄ - x₄₆ - x₄₇ = 0 x₂₅ + x₃₅ - x₅₇ - x₅₈ = 0 x₄₆ - x₆₉ = 0 x₄₇ + x₅₇ - x₇₉ = 0 x₅₈ - x₈₉ = 0 x₆₉ + x₇₉ + x₈₉ = 1 and x_ij is binary,for each activity (i,j).

Consider the Following Activity-On-Arc Project Network,where the 12 Arcs (Arrows)represent