联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp

您当前位置:首页 >> Matlab编程Matlab编程

日期:2022-03-09 09:18

MACM 203 Assignment 6

Spring 2022

This assignment is due Tuesday March 8th at 10pm. Upload your solutions to Crowdmark.

Write your solutions as a single Matlab Live Script and export the script to PDF.

Write the course number and assignment number as the title of the Matlab Live Script,

followed by the table of contents, and then create a section for each part of the question.

Keep in mind that your assignment, including the source code, is a document that will

be read in order to be marked. It has to be very clear and properly formatted.

Your Matlab code must be general enough to solve any other instance of the same problem

without modification. That is, if you are asked to run your code on some data that are

specified in the assignment, then your code must run on any similar data set (or solve

any similar problem) without modification.

Assignments should be written individually. You can discuss in groups, but you have to

write your assignment yourself. In case of plagiarism SFU policies will be applied.

Preamble

This week’s assignment focuses on linear optimization.

Question 1 (20 marks)

In the current semester, the Top of the Mountain University (TMU) offers C courses

labelled 1, 2, . . . , C. The enrollment (number of students) in each course is given in the

row vector E. That is, E(i) is the number of students taking course i. Each course has a

final exam.

The university is about to schedule the final exams, and it hires you as a consultant to

design an optimal schedule of the exams. TMU students like to write their exams early

on in the examination period, as writing exams at earlier dates effectively extends the

length of the semester break that follows after the exam period. The exams are written in

S different time slots numbered 1, 2, . . . , S and scheduled in that order. The waiting time

perceived by one student when writing an exam is the number of the slot in which the

exam is written (any slot 1 exam has waiting time 1, any slot 2 exam has waiting time 2,

etc.) Therefore a course with enrollment of e students that has the exam scheduled in

slot s generates waiting time e · s.

Certain pairs of courses can not have their exams scheduled in the same slot because

there are students taking both courses. This information is represented by matrix A which

1

is C × C upper triangular matrix with zeros on the main diagonal, such that A(i, j) = 1

if courses i and j can not have exams in the same slot, and A(i, j) = 0 otherwise.

The objective of the optimal schedule is to minimize the total waiting time, which is

the sum of waiting times of all courses, subject to the scheduling constraints defined in

the previous paragraph.

Example. Suppose that C = 3, E = [37, 29, 51], S = 2 and

A =

?

?

0 0 1

0 0 0

0 0 0

?

? .

That is, courses 1 and 3 have scheduling conflict, and there are no other conflicts. The

optimal solution is to schedule exams 2 and 3 into slot 1, and exam 1 into slot 2, at

the total waiting time 37 · 2 + 29 · 1 + 51 · 1 = 154. Another feasible solution is to

schedule exams 1 and 2 into slot 1, and exam 3 into slot 2, at the total waiting time

37 · 1 + 29 · 1 + 51 · 2 = 168. This solution is not optimal since the total waiting time is

not minimized.

Part (a)

Given C, S, E, A as above, write MATLAB code that finds an optimal schedule. You

can assume that the problem is solvable (feasible solutions exist). As a first test of your

code, use it to solve the example given above.

Hints:

- Study carefully posted solutions to Task Assignment problem and Advertisement

problem. Your solution will use ideas from these two posted solutions.

- Use C × S array x of optimization variables xi,j such that xi,j = 1 if course i has

exam scheduled in slot j, and xi,j = 0 otherwise.

- For each conflicting pair of courses i, j create the appropriate constraint by using

the sum of the i-th row of x and the j-th row of x. For simplicity you can use a double

for-loop and append the constraints one by one.

- Apply round to the optimal solution returned by MATLAB to make sure that each

entry in the optimal solution is integer 0 or 1. (MATLAB may return numerical approximations

that are not exactly 0 or 1.)

Part (b)

Download the data file a6.mat posted on the front page of Canvas, and use your code on

the data in that file to find an optimal schedule. Display the total waiting time for the

optimal schedule, and for each time slot display the courses whose exams are scheduled

into that slot.

2


相关文章

版权所有:留学生编程辅导网 2020 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp