2023年11月25日

图算法代写｜Graph Algorithms CW1

这是一个英国的图算法代写Courswwork

Problem 1 [10 marks]

A furniture manufacturer makes two types of bedroom suites, a white suite and a more pro…table teak suite, by applying a di¤erent …nish to the same basic body, of which 2000 are available each week. It takes twice as long to …nish a teak suite as it does to …nish a white suite, and su¢ cient time is available to …nish 2400 white suites per week.

Each teak suite requires one special …tting; only 720 …ttings are available each week. The manufacturer makes a pro…t of £ 60 on each white suite and £ 80 on each teak suite. It is,however, the manufacturer’s policy to produce at least 400 white suites per week.

Model the problem of maximising the manufacturer’s weekly pro…t. Do not attempt to solve it.

Explain the meaning of the variables you introduce.

Present the …nal ILP.

Explain how you model the underlined constraint.

Problem 2 [18 marks]

For all parts of Problem 2, please present your answers on one (or two) pages. Your answers can be handwritten, but please follow the outline provided as a template (a separate …le in Minerva).

2.1 Consider Problem A presented below. Solve it graphically. [5 marks]

Please mark the solution region clearly.

For each line, specify two points it passes through.

Specify coordinates of the corner points of the feasible region.

Present the line for the objective function, together with the equation used to plot it,and indicate the direction in which the line should be moved.

State the optimal values of the variables and the optimal value of the objective function.

2.2 Solve Problem A by the simplex method (in the tableau format). [3 marks]

Present all tableaux, indicating the choice of the pivot row and pivot column, and the pivot element. State the …nal answer: the optimal values of the variables and the optimal value of the objective function.

2.3 Reconsider the graphical solution from Part 2.1. On the same plot, mark the solutions obtained consecutively at all iterations of the simplex method and indicate the order in which they are obtained. [1 mark]

2.4 Consider Problem B, which is the dual for Problem A: [5 marks]

Solve Problem B graphically.

Follow the same instructions as in Part 2.1. Additionally specify the scale for the axes.

2.5 Solve Problem B by the dual simplex method. [3 marks]

Present all tableaux, indicating the choice of the pivot row and pivot column, and the pivot element. State the …nal answer: the optimal values of the variables and the optimal value of the objective function.

2.6 Reconsider the graphical solution from Part 2.4.

On the same plot, mark the solutions obtained consecutively at all iterations of the dual simplex method and indicate the order in which they are obtained. [1 mark]