Question  1  (8  marks) Consider the following linear constraints on variables x and y and a parameter k ∈ R.

3x + y   ≤   12

2x + y   ≥   4

x − y   ≥   k

x, y   ≥   0

(a) Let k = 1 and draw the feasible region.

(b)  Still for k = 1, consider the objective function:

f(x, y) = x + y .

Use the graphical method to identify the optimal solution in your graph in (a) by indicating some level curves of the objective function  (including the level curve that crosses the optimal solution).  Then solve the appropriate system of linear equations to obtain the optimal values for x and y .

(c) For which value(s) of k , if any, the problem:

(i) has a single feasible solution. (ii) is infeasible.

(iii) is unbounded.

Question 2 (7 marks)

A furniture manufacturer produces three different products using long and short pieces of wood. Product 1 uses 2 long pieces and 1 short piece. Product 2 uses 3 long pieces and 4 short pieces. Product 3 uses 2 long pieces and 2 short pieces. The manufacturer can sell whatever he is able to produce. The revenue for each unit of products 1, 2 and 3 is AUD 210, AUD 300 and AUD 400, respectively. The manufacturer has 100 long pieces and 80 short pieces of wood available.

(a)  Clearly define your variables and propose a linear programming model for the problem of

maximising the manufacturer revenue given the amount of wood available.  You do not need to solve the model.

(b) Now assume that the manufacturer decide to change his process for producing product 3.

This new process requires 4 long pieces of wood and generates  one short piece of wood as leftover from the cutting of the long pieces.  This short piece of wood has the same length and characteristics of the short pieces of wood the manufacturer had initially and, therefore, can be used in the production of products 1 and 2. Modify (but do not solve) your model to represent this new situation.

Question 3 (5 marks) Consider the following optimisation problem:

max3x1 + 2x2 + x3

s.t

3x1 − 3x2 + 2x3     ≤   3

−x1 + 2x2 + x3     ≤   6

x1 , x2 , x3     ≥   0

(a)  Represent the problem in canonical form.

(b)  Solve the problem using the simplex algorithm.  What are the optimal values for x1 , x2

and x3 ? What is the optimal value of the objective function?

Question 4 (8 marks) Consider the following optimisation problem:

maxx1 + x2

s.t

x1 − 2x2     ≤   4

x1 − x2     ≥   −4

x1 , x2     ≥   0

(a) Use the simplex algorithm to show that this problem is unbounded.  (Clearly explain how

you came to the conclusion that the problem is unbounded).

(b)  Obtain the dual of the optimisation problem.

(c) Express the dual you obtained in (b) in canonical form.

(d) Use phase-1 of the simplex algorithm to show that the dual is infeasible.  (Clearly explain how you came to the conclusion that the problem is infeasible).

Question 5 (6 marks) Consider the following optimisation problem:

max2x1 + x2

s.t

(a) Write the dual of the problem.

(b) Write all equations defining the complementarity slackness conditions.

(c) Using your answer in (b), say whether the points (x1 , x2 ) = (3, 5) is optimal for the primal problem.

(d) Using your answer in (b), say whether the points (x1 , x2 ) = (4, 1) is optimal for the primal problem.

Question 6 (10 marks) Consider the following linear program:

maxc1x1 + 9x2 + x3

s.t

3x1 + 2x2 + 2x3 + x5     = 15

x1 , x2 , x3 , x4 , x5      ≥ 0

(a) For c1 = 1, b1 = 9, the variables in the optimal basis are x2 , x5 . Use this information and

the algebra of the simplex method, to obtain the optimal tableau in this case.  (Do not solve the simplex algorithm to obtain this tableau).

(b) Use your answer in (a) to determine:

(i)  The range of values of c1  (the coefficient in the objective function for variable x1 , currently at 1) for which the basis x2 , x5  remains optimal.

(ii)  The range of values for b1  (the right hand-side of the first constraint, currently at 9)

for which the basis x2 , x5  remains optimal.

Question 7 (7 marks)

Consider the following project, described in terms of its activities and precedences in the table below:

Activity    Time    Precedence(s)

A B C D E F G H I J

2

3

4

8

2

3

4

5

2

1

-

A

B

C

-

E

F,J

G

-

I

(a)  Draw the Activity on Node network associated with this project.

(b)  Build a table for the Earliest Start times (ES), Earliest Finish times (EF), Latest

Start times (LS), Latest finish times (LF) and Total Float for all tasks.

(c) What is the critical path and the minimum completion time of the project? (d) What is the Free Float (FF) for task J.

(e)  Show that in any project scheduling, for any task i, FFi  ≤ TFi .

Question 8 (8 marks) Consider the following graph:

(a)  Calculate the node-betweenness centrality for node D.

(b) Use Breadth-First Search to find the length of the shortest path from A to G.

(c) Find the number of shortest paths from node A to node G in the graph using the recursive formula for µ(A|G).

(d) Use min-plus matrix algebra to compute the length of the shortest path from node B to all other nodes.

Question 9 (8 marks) Consider the following graph:

(a) Is the graph chordal? Explain.

(b) Is the graph bipartite? Explain.

(c) What is the edge-chromatic number of this graph? State the theorem that allow you to obtain this value directly, without the need to explicitly colour the graph.

(d)  Consider a matching with edges (6,8), (5,7) and (3,4).  Use an augmenting path for this matching to obtain a new matching with 4 edges.

(e)  Construct  the  dendogram  for  the  graph  using  the  Girvan-Newman  algorithm.

Note: vertices have been labelled from 1 to 12. All steps of the algorithm must be shown but explicit calculations of edge-betweenness centrality are not necessary.

Question 10 (9 marks) Three players, P1 , P2  and P3  need to divide three items for which they have placed values according to the table below.

(a)  Consider the division in which P1  gets item 1, P2  gets item 2 and P3  gets item 3.

Is this division equitable, pareto-optimal and envy-free?  Explain your reasoning for each criterion.

(b)  Divide the items using the method of sealed bids.