Hey there! Sign in to join this conversationNew here? Join for free
    • Community Assistant
    • Thread Starter
    Offline

    18
    ReputationRep:
    Community Assistant
    Unfortunately I don't have the answer booklet, so some questions were too difficult to format correctly. There may be mistakes.
    Question 1 : 10 Marks
    Spoiler:
    Show
    (a) In the classical problem each vertex each vertex must be visited only once.
    In the practical problem each vertex must be visited at least once.

    (b) Nearest neighbour routes:
    A_{12}D_{16}C_{19}F_{25}B_{14}E_  {41}G_{22}A
    length = 149

    A_{12}D_{16}C_{19}F_{25}G_{41}E_  {14}B_{31}A

    length = 158

    (c) Using prim's algorithm; RMST is : BE,BC,CD,CF,BD
    weight = 86
    add AD and AC, lower bound = 86+12+15 =113

    (d)  113<optimal\leq 149
    Question 2 : 8 Marks
    Spoiler:
    Show
    (a) Saturated Arcs: SB, SC, AE, DT FT

    (b) Initial flow = 59

    (c)  C_{1} = 72, C_{2} = 86

    (d) Flow augmenting route: SABCFET

    (e) Minimum cut is the cut going through the arcs DT, AE,BC and SC; minimum cut = max flow = 62, therefore maximal.
    Question 3 ( Down the LHS is Alexa, Ewan, Faith, Zak) - 9 Marks
    Spoiler:
    Show
    \begin{bmatrix} 61& 50 &47  &23 \\  71&62  &20  &61 \\  70&49  & 48 & 49\\  72& 68 &67  &67 \end{bmatrix}

    Adapt for maximisation
    \begin{bmatrix} 11& 22 &25  &49 \\  1&10 &52  &11 \\  2&23  & 24 & 23\\  0& 4 &5  &5\end{bmatrix}

    Reduce rows

    \begin{bmatrix} 0& 11 &14  &38 \\  0&9 &51  &10 \\  0&21  & 22 & 21\\  0& 4 &5  &5\end{bmatrix}

    Reduce columns

    \begin{bmatrix} 0& 7 &9  &33 \\  0&5 &46  &5 \\  0&17 & 17 & 16\\  0& 0 &0  &0\end{bmatrix}

    \begin{bmatrix}

  0& 2 &4  &28 \\  0&0 &41 &0 \\  0&12 & 12 & 11\\  5& 0 &0  &0\end{bmatrix}

    \begin{bmatrix}

  0& 0 &2  &26 \\  

 2&0 &41 &0 \\  0&10 & 10 & 0\\ 7& 0 &0  &0\end{bmatrix}

    Allocation: A - 2 , E - 4, F - 1, Z - 3

    (b) maximum score = 248
    Question 4 : 9 Marks
    Spoiler:
    Show
    (a)  x was increased first as it has replaced the slack variable s in the b.v column

    (b) Name:  simplex.png
Views: 402
Size:  9.4 KB

    (c) T is : P +13y +2r -5s = 27

    (d) P = 27 - 13y - 2r +5s , so increasing s would increase the profit; Not optimal.
    Question 5 : 12 Marks
    Spoiler:
    Show

    (a) A dummy demand is needed as total supply(99)>total demand(85), so a dummy is used to absorb the excess supply.

    (b) [add 000 and 14 to the table]

    (c) North west corner

    (d) Stepping stone (twice)

    (e) optimal as there are no negative improvement indices.
    Question 6 : 12 Marks
    Spoiler:
    Show
    (a) Row minimax (4) \neq Column maximin (0) \Rightarrow no saddle point  \Rightarrow no stable solution.

    (b) Let  P_1 be the probability of A playing row 1
    Let  P_2 be the probability of A playing row 2
    Let  P_3 be the probability of A playing row 3
    Where  P_{1},P_{2},P_{3}\geq 0

    Let  V = value of the original game to player A
    Then  V+5 = value of new game to player A

    Maximise P = V so  P - V = 0
    subject to  V -10P_{1} - 7P_{2} - P_{3} +r = 0
     V - 2P_{1} - 10P_{2} - 4P_{3} + s = 0
     V - 6P_{1} - 5P_{2} - 9P_{3} + t =0
     P_1 + P_2 + P_3 + u = 1
    all variables \geq 0

    (c) simplex table with basic variables r,s,t,u,p
    Question 7 : 15 Marks
    Spoiler:
    Show
    (a) Dynamic programming
    Jan - 3
    Feb - 3
    March - 5
    April - 5
    May - 3
    Minimum cost = £1700

    (b) Profit = £5550
    Attached Images
     
    Offline

    3
    ReputationRep:
    Thank you!!!
    Offline

    3
    ReputationRep:
    For the game theory formulating. I forgot to write V+5= new value but I rewrote the table and said add 5 to all. How many marks would I lose?
    • Community Assistant
    • Thread Starter
    Offline

    18
    ReputationRep:
    Community Assistant
    (Original post by 4nonymous)
    Thank you!!!
    You're welcome! I've made some edits, as it was late when I wrote this.
    (Original post by 4nonymous)
    For the game theory formulating. I forgot to write V+5= new value but I rewrote the table and said add 5 to all. How many marks would I lose?
    Probably 1.
    Offline

    6
    ReputationRep:
    Sorry for responding so late to this, just playing on my mind a bit.
    Q1. I forgot to return to A in both my routes, so I had the routes correct but missed the last step of the algorithm. Drop 2 marks? I got 113 correct and the interval correct with my incorrect route value, so would I have dropped 2-4 marks? Depends if I get error carried forward.
    Q2. Dropped like 4.
    Q3. Full marks. 2Nd favourite topic
    Q4. Full marks, however I will deduct 1 just in case my explanation lacked.
    Q5. I got negative and -2, -1 which I think is agreed upon for the negative solution? Full marks.
    Q6. Full marks - did so much practise on it.
    Q7. Messed up - I got 1325 although 1700 was a Final value I had in one of them, so maybe I simply missed adding a value to the 1325? Do you think I could get 5 marks for that?
    Dropped 10.
    If so that is 75-4-1-10-4 = 56. I will be harsh and say 54/75. Should that be enough for a B? If I got the DP then I would have had a solid A, dammit should have tried to revise it more so costly.
    if im generous I could have 60 but I am preparing for the worst just in case, thanks bro
    • Community Assistant
    • Thread Starter
    Offline

    18
    ReputationRep:
    Community Assistant
    (Original post by TrueDAN)
    Sorry for responding so late to this, just playing on my mind a bit.
    Q1. I forgot to return to A in both my routes, so I had the routes correct but missed the last step of the algorithm. Drop 2 marks? I got 113 correct and the interval correct with my incorrect route value, so would I have dropped 2-4 marks? Depends if I get error carried forward.
    Q2. Dropped like 4.
    Q3. Full marks. 2Nd favourite topic
    Q4. Full marks, however I will deduct 1 just in case my explanation lacked.
    Q5. I got negative and -2, -1 which I think is agreed upon for the negative solution? Full marks.
    Q6. Full marks - did so much practise on it.
    Q7. Messed up - I got 1325 although 1700 was a Final value I had in one of them, so maybe I simply missed adding a value to the 1325? Do you think I could get 5 marks for that?
    Dropped 10.
    If so that is 75-4-1-10-4 = 56. I will be harsh and say 54/75. Should that be enough for a B? If I got the DP then I would have had a solid A, dammit should have tried to revise it more so costly.
    if im generous I could have 60 but I am preparing for the worst just in case, thanks bro
    q1.) About 3-4 marks lost
    q5.) I might have got a negative solution, I can't remember.
    q7.) I have no idea how marks are allocated for Dynamic Programming, as mark schemes are vague. But i'd guess somewhere around 6/7 marks.

    I think B won't be higher than 56/75, given that you're close and these are just estimates, it's hard to tell.
    Offline

    2
    ReputationRep:
    (Original post by NotNotBatman)
    Unfortunately I don't have the answer booklet, so some questions were too difficult to format correctly. There may be mistakes.
    Question 1 : 10 Marks
    Spoiler:
    Show
    (a) In the classical problem each vertex each vertex must be visited only once.
    In the practical problem each vertex must be visited at least once.

    (b) Nearest neighbour routes:
    A_{12}D_{16}C_{19}F_{25}B_{14}E_  {41}G_{22}A
    length = 149

    A_{12}D_{16}C_{19}F_{25}G_{41}E_  {14}B_{31}A

    length = 158

    (c) Using prim's algorithm; RMST is : BE,BC,CD,CF,BD
    weight = 86
    add AD and AC, lower bound = 86+12+15 =113

    (d)  113<optimal\leq 149
    Question 2 : 8 Marks
    Spoiler:
    Show
    (a) Saturated Arcs: SB, SC, AE, DT FT

    (b) Initial flow = 59

    (c)  C_{1} = 72, C_{2} = 86

    (d) Flow augmenting route: SABCFET

    (e) Minimum cut is the cut going through the arcs DT, AE,BC and SC; minimum cut = max flow = 62, therefore maximal.
    Question 3 ( Down the LHS is Alexa, Ewan, Faith, Zak) - 9 Marks
    Spoiler:
    Show
    \begin{bmatrix} 61& 50 &47  &23 \\  71&62  &20  &61 \\  70&49  & 48 & 49\\  72& 68 &67  &67 \end{bmatrix}

    Adapt for maximisation
    \begin{bmatrix} 11& 22 &25  &49 \\  1&10 &52  &11 \\  2&23  & 24 & 23\\  0& 4 &5  &5\end{bmatrix}

    Reduce rows

    \begin{bmatrix} 0& 11 &14  &38 \\  0&9 &51  &10 \\  0&21  & 22 & 21\\  0& 4 &5  &5\end{bmatrix}

    Reduce columns

    \begin{bmatrix} 0& 7 &9  &33 \\  0&5 &46  &5 \\  0&17 & 17 & 16\\  0& 0 &0  &0\end{bmatrix}

    \begin{bmatrix}

  0& 2 &4  &28 \\  0&0 &41 &0 \\  0&12 & 12 & 11\\  5& 0 &0  &0\end{bmatrix}

    \begin{bmatrix}

  0& 0 &2  &26 \\  

 2&0 &41 &0 \\  0&10 & 10 & 0\\ 7& 0 &0  &0\end{bmatrix}

    Allocation: A - 2 , E - 4, F - 1, Z - 3

    (b) maximum score = 248
    Question 4 : 9 Marks
    Spoiler:
    Show
    (a)  x was increased first as it has replaced the slack variable s in the b.v column

    (b) Name:  simplex.png
Views: 402
Size:  9.4 KB

    (c) T is : P +13y +2r -5s = 27

    (d) P = 27 - 13y - 2r +5s , so increasing s would increase the profit; Not optimal.
    Question 5 : 12 Marks
    Spoiler:
    Show

    (a) A dummy demand is needed as total supply(99)>total demand(85), so a dummy is used to absorb the excess supply.

    (b) [add 000 and 14 to the table]

    (c) North west corner

    (d) Stepping stone (twice)

    (e) optimal as there are no negative improvement indices.
    Question 6 : 12 Marks
    Spoiler:
    Show
    (a) Row minimax (4) \neq Column maximin (0) \Rightarrow no saddle point  \Rightarrow no stable solution.

    (b) Let  P_1 be the probability of A playing row 1
    Let  P_2 be the probability of A playing row 2
    Let  P_3 be the probability of A playing row 3
    Where  P_{1},P_{2},P_{3}\geq 0

    Let  V = value of the original game to player A
    Then  V+5 = value of new game to player A

    Maximise P = V so  P - V = 0
    subject to  V -10P_{1} - 7P_{2} - P_{3} +r = 0
     V - 2P_{1} - 10P_{2} - 4P_{3} + s = 0
     V - 6P_{1} - 5P_{2} - 9P_{3} + t =0
     P_1 + P_2 + P_3 + u = 1
    all variables \geq 0

    (c) simplex table with basic variables r,s,t,u,v
    Question 7 : 15 Marks
    Spoiler:
    Show
    (a) Dynamic programming
    Jan - 3
    Feb - 3
    March - 5
    April - 5
    May - 3
    Minimum cost = £1700

    (b) Profit = £5550
    for question 6 bv is rstup not v
    • Community Assistant
    • Thread Starter
    Offline

    18
    ReputationRep:
    Community Assistant
    (Original post by anonymous2410)
    for question 6 bv is rstup not v
    Yes, thank you.
    Offline

    2
    ReputationRep:
    (Original post by NotNotBatman)
    Yes, thank you.
    did you get that wrong?
    • Community Assistant
    • Thread Starter
    Offline

    18
    ReputationRep:
    Community Assistant
    (Original post by anonymous2410)
    did you get that wrong?
    No, just a mistake on here.
    Offline

    2
    ReputationRep:
    (Original post by anonymous2410)
    for question 6 bv is rstup not v
    how did you prove flow is maximal for Q2E?
    i used C1= min cut to show flow is maximal
 
 
 
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • Poll
    What's your favourite Christmas sweets?
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

    Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

    Quick reply
    Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.