Question 1 (10 marks)

A student wants to do well in life and he understands that the best way to do so is by obtaining good marks in his exams for Semester 2 2020.  He is taking 4 subjects:  A, B, C and D. He estimates that his mark on the exam for a given subject is proportional to the number of hours he studies for that exam, with the mark capped at 100. The constants of proportionality, p, for each subject are given by pA  = 3, pB  = 5, pC  = 7 and pD  = 10 for subjects A, B, C and D, respectively.  This means, for example, that if he studies 20 hours for subject A, he will get a mark equal to 20 x pA = 60 but if he studies 40h for subject A he will get 100 (40 x pA = 120, capped at 100).

(a)  The student is planning on studying a total of 40h for his four exams. Define appropriate

variables and formulate a linear programming model with the goal of maximising the sum of the marks the student obtains in the exams.

Subjects require a minimum of 50 points in the exam for a pass. Using the same variables as in (a), propose constraints to ensure that the model will only accept solutions that ensure that the student pass in all his subjects.

(c) The student realises that he actually wants to maximise his WAM and not the raw sum of his marks. At the University website, he reads:  “The WAM provides an indication of overall academic performance in each course that a student has undertaken, reflecting both the numeric mark (45 or 87, for example) and the number of credit points of each subject you complete.  It is calculated progressively as your subject results are added in my.unimelb, meaning a 25 point subject will be weighted double that of a 12.5 point subject in your WAM.”

Subjects A and B are 25 point subjects while subjects C and D are 12.5 point subjects. Change the model to reflect the student’s new objective.

(d) Stressed with life, the student decides that all he wants is to pass the exams, with the minimum possible effort.  Write a model that ensures the student passes all subjects while minimising the hours he needs to study.

Question 2 (10 marks)

Consider the following linear programming model, parametrised on a parameter a: max z = x1 + x2

x1 - x2     >   -4

x1     <   a

xi     >   0,    i = 1, 2

(a) Write the problem in canonical form.

(b)  Draw the feasible space for a = 4, enumerate all basic feasible solutions and all basic

infeasible solutions. Which of these solutions is optimal and what is its objective value?

(c) Write the dual of the presented model.

(d) Draw the feasible space of the dual problem in (c) and use the graphical method on this dual model to obtain the optimal solution for all values of parameter a in the range -& < a < &.

Question 3 (10 marks)

Use the Phase-I method of the Simplex algorithm to show that the problem below has no feasible solutions.

max z = x1 + x2

x1 - x2     >   2

x1 + x2     <   1

xi     >   0,    i = 1, 2

Question 4 (10 marks)

Consider the following linear program:

max z = x1 + 2x2

2x1 - x2 - x3     >   -2

x1 - x2 + x3     >   -1

xi     >   0,    i = 1, 2, 3

Use the Simplex algorithm to verify that this problem is unbounded.

(b) Use your solutions in (a) to obtain a feasible solution for the problem with objective value at least 300.  (You must use your results from (a).  Trial and error solutions or solutions with no clear explanations will not be considered correct.)

(c) Derive the expression for the reduced cost of a variable, starting with the equation known as ‘general solution of the system’:  xB  = AB(−)1 b - AB(−)1 ANxN .  Explain the meaning of the reduced cost expression you obtain.

Question 5 (10 marks)

Answer the following questions. Use only the space provided.

(a)  “The basic variables in a basic feasible solution found by the Simplex algorithm are

always zero” . Is this statement true or false? Justify your answer.

(d)  “If there is a non-basic variable with zero reduced cost in the optimal Simplex tableau, then the problem is unbounded” . Is this statement true or false? Justify.

(e)  “If a problem is infeasible, then it’s dual must be infeasible ” . Is this statement true or

false? Justify.

Question 6 (10 marks)

Consider the following problem:

max z = c1x1 + 2x2 + x3 + x4

2x1 + x2 + 3x3 + x4     <   b1

2x1 + 3x2             + 4x4     <   12

3x1 + x2 + 2x3                 <   18

xi     >   0,    1 < i < 4

Consider c1  = 1 and b1  = 8.  After adding slack variables x5 , x6  and x7  and solving by the Simplex method, we obtain the final tableau below:

(a) For cost coefficient c1 , calculate the range of values for which the above solution remains optimal.

(b) For parameter b1 , compute the range of values for which the above solution remains optimal.

Question 7 (10 marks)

In this question, 3 players A, B and C seek to divide a cake.

(a)  Suppose A cuts the pieces according to the lone divider method. What are the valuations

of the three pieces from A’s viewpoint?

(b) Suppose the valuations of players B and C of the three pieces are (2/3, 1/6, 1/6) and (2/3, 1/12, 1/4) respectively.  Which piece(s) is  (are) acceptable to B and C? Justify your answer.

(c) Suppose piece 1 is given to player A. Use cut and choose to determine the allocation of portions of pieces 2 and 3 to B and C, with B the cutter.

(d)  Show that the final allocation among the 3 players is not envy free.

Question 8 (10 marks)

Student council is holding elections for president. There are 4 candidates (labelled A,B ,C and D for convenience). The preference schedule for the election is:

Find the winner of the election using the Borda count committee scoring method.

(b) Find the winner of the election using the extended Smith set method, which ensures (at least a weak) condorcet winner.

Question 9 (10 marks)

Consider the following graph:

What is node centrality? Compute the node centrality metric known as ‘degree central- ity’ for vertices 1, 7 and 11.

State four possible real-world applications for the theory of node centrality in complex networks.

(c) Construct the dendogram for the following graph using the Girvan-Newman algorithm. Note: vertices have been labelled from 1 to 11. All steps of the algorithm must be shown, but explicit calculations of edge-betweenness centrality are not necessary.

(a)  Draw the bipartite graph corresponding to the matrix.  Clearly label the nodes of your

bipartite graph if the columns of the matrix are y1 , . . . , y4  and the rows are x1 , . . . , x4

(b) Find a matching in your bipartite graph from (a) which includes all vertices of maximum

degree.