# Python算法代写｜Assignment 3: The Auction Algorithm

This assignment requires writing both explanations and some code to be written. You may use any of Matlab, Julia or Python to write your code. All of your answers and code must be submitted as a single PDF file to Moodle by the due date. In addition, also submit your code (as notebook, text or zip file). Note that if you write all of your answers into a Jupyter notebook is possible to can be downloaded directly as PDF document. However, you can also just write everything in some separate document. To make this assignment easier, a Jupyter notebook is provided on Moodle with template code samples in Julia, Python & Matlab.

This assignment is out of 15 is worth 6% of the final MTH3330 unit mark.

Note: Honours and Masters students are expected to complete an extra question so their assignments are out of 20

A primary school principal wants your help to organise her classes in response to the COVID-19 epidemic. With a large number of students staying home, there are a different number of students in each class attending school each day. The principal wants to assign classes to the available classrooms that are of different sizes so as to minimise the average number of students per square meter. This assignment is about creating the tools that would allow her to quickly find a solution each day.

Basic notation and rules:

Q1 Basic Formulation (5 marks)

Hint for Question 1.2: You can prove that no other solution can be optimal by showing that any assignment that doesn’t satisfy this ordering can be improved by swapping the room assignment for two classes.

Q2 Solution via Linear Programming (5 marks)

The principal of the primary school has got feedback from her teachers that this arbitrary assignment of classes to rooms purely based on size is a significant inconvenience to them. The teachers want to be able to provide some preferences of their own for how well each of the rooms are suited to their needs. They have collected a preference matrix 𝑃 where for each class 𝑖 ∈ 𝐶 the teacher of that class has provided the preference for room 𝑗 ∈ 𝑅 as value 𝑃𝑖𝑗 ∈{1, … , 𝑛}. From the point of view of the teachers, minimising the average preference value of the room assignments is the best solution.

Implement a function using a linear programming solver that finds the best assignment vector 𝑎 where 𝑎𝑖 ∈ 𝑅 is the room for class 𝑖 ∈ 𝐶 for an arbitrary cost matrix. Use this function to solve the classroom assignment problem for the following three objective functions:

Note: This approach of using a weighted sum of multiple objective functions is often used in practical problems where different criteria have to be traded-off against each other. Depending on the relative weight of the two objectives different “optimal” solutions are obtained.