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

这是一篇来自澳洲的关于MATLAB Julia拍卖算法的Python代写

Instructions

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

Background

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:

𝐶 and 𝑅 denotes the set of classes and rooms of size 𝑛 (𝑛 = |𝐶| = |𝑅|)

Let 𝑠𝑖 denote the number of students in class 𝑖 ∈ 𝐶 and

The room size is 𝑟𝑗 for classroom 𝑗 ∈ 𝑅 (in 𝑚2)

Each class must be assigned its own room and all students in the class go into that room.

Q1 Basic Formulation (5 marks)

Write down a formulation of the above problem as a linear programming (assignment) problem. Make sure you clearly define your variables, objective and constraints. (2 marks)

Prove that the optimal solution can be found by sorting both the classes and the rooms in decreasing order and assign the largest class to the largest room, the second largest class & room together and so on. (3 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:

𝑓𝑠(𝑎) the average number of students per square meter to get the best spread of students.

𝑓𝑝(𝑎) the average preference of the teachers for the room they are allocated (lower is better)

𝑓𝑐(𝑎) = 𝑓𝑝(𝑎) + 50𝑓𝑠(𝑎) – this is the comprompise solution which is heavily weighted towards the safety of students (minimising students per square meter) but also considers teacher preferences.

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.

In your answer to this question please provide:

The code for the function solving the assignment problem together with the code of how you are calling the function for the 3 different objectives

For each assignment vector 𝑎 found this way report (a) 𝑓𝑠(𝑎), (b) 𝑓𝑝(𝑎) (c) the vector 𝑎 itself

Comment briefly on whether you think 𝑓𝑐(𝑎) represents a reasonable compromise.

The primary school has 14 classes, two for each of the years Prep to year 6. The data for the school, is as follows. Note that both classes and rooms have been sorted in order of decreasing size already.

程序辅导定制C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB