This assignment is worth 30% of your final mark (subject to the hurdles described in the FIT3158 Moodle preview [or Unit Guide] and links therein). Among other things (see     below), note the need to hit the `Submit’ button (and the possible requirement of a video and/or an interview).

Due Date: Friday 22nd  September 2023,  11:55 pm

Method of submission: Your submission should consist of 2 files:

1. A Microsoft Excel spreadsheet named as:

FamilyName-StudentId-2ndSem2023FIT3158Asst2.xlsx

2. A text-based .pdf file named as: FamilyName-StudentId-2ndSem2023FIT3158Asst2.pdf Both the files must be uploaded on the FIT3158 Moodle site by the due date and time.

The text-based .pdf file will undergo a similarity check by Turnitin at the time you submit to Moodle. Please read submission instructions here and elsewhere carefully regarding

the use of Moodle.

Total available marks: 100 marks.

Note 1: Please recall the Academic Integrity rules (and, as per Moodle week 0, you might also wish to confer with https://www.monash.edu/student-academic-success).  This is an   individual assignment.  Recall various resources from FIT3158 Moodle week 0.

In submitting this assignment, you acknowledge both that you are familiar with the relevant   policies, rules and regulations regarding Academic Integrity (including, e.g., doing your own work, not sharing your work, not using ChatGPT in particular, not using generative AI at all) and also that you are familiar with the consequences of being deemed to be in contravention  of these policies.

Note 2: And a reminder not to post even part of a proposed partial solution to a forum or

other public location. This includes when you are seeking clarification of a question.

If you seek clarification on an Assignment question then – bearing in mind the above – word your question very carefully and/or (if necessary) send private e-mail (being in mind

instructions in week 1 Introductory Lecture).  If you are seeking to understand a concept

better, then try to word your question so that it is a long way removed from the Assignment. You are reminded that Monash University takes academic integrity very seriously.

Note 3: As previously advised, it is your responsibility to be familiar with the special

consideration policies and special consideration process – as well as academic integrity.

Please see the relevant links within FIT3158 Moodle (week 0 and perhaps also elsewhere). Students should be familiar with the special consideration policies and the process for applying.

Note 4: As a general rule, don’t just give a number or an answer like `Yes’ or `No’ without

at least some clear and sufficient explanation - or, otherwise, you risk being awarded 0

marks for the relevant exercise.  Make it easy for the person/people marking your work to follow your reasoning.  Your .pdf should typically cross-reference the correspondinganswer in your spreadsheet. For each and every question, sub-question and exercise,

provide a clearly labelled separate spreadsheet tab with clear content, accompanied with

clearly cross-referenced clear .pdf explanation.  Without clear cross-reference between .pdf and spreadsheet tab – and without a separate spreadsheet tab for each sub-question -

there is the possibility that any such exercise will be awarded 0 marks.

Re-iterating a point above, for each and every question, sub-question and exercise, clearly explain your answer and clearly show any working.

Note 5: As a general rule, if there is an elegant way of answering a question without

unnecessarily re-running the Solver, try to do it that way. (Recall, e.g., sensitivity report and some notions from Week 3 and thereabouts.)  More generally, more elegant solutions are

preferable - and will at least sometimes be given more marks (possibly many more

marks).  Among other things, if a problem is a linear programming (LP) problem, then it

would be more elegant to solve it using the linear simplex model.  In a similar vein, a linking constraint (where appropriate) will be far preferable to a seemingly equivalent use of the IF() function.

Note 6: All of your submitted work should be in machine readable form, and none of your submitted work should be hand-written.

Note 7: If you wish for your work to be marked and not to accrue (possibly considerable)

late penalties, then make sure to upload the correct files and (not to leave your files

as Draft).  You then need to determine whether you have all files uploaded and that you are    ready to hit `Submit’.  Once you hit `Submit’, you give consent for us to begin marking your work.  If you hit `Submit’ without all files uploaded then you will probably be deemed not to have followed the instructions from the Notes above.  If you leave your work as Draft and

have not hit `Submit’ then we have not received it, and it can accrue late penalties once the    deadline passes.   In short, make sure to hit ‘Submit’ at the appropriate time to make sure that your work is submitted.  Late penalties will be as per Monash University Faculty of IT and    Monash University policies.  Within the requirements of these policies just mentioned, late

penalties will accrue at a rate of at least 5% per calendar day – where 5% refers to a

proportion of the total marks available.  It is expected that any work submitted at least  10 calendar days after the deadline will automatically be given a mark of 0.

Note 8: The notation  1E-12 corresponds to  1 x  10-12, or 0.000000000001. If you see a figure

of approximately this magnitude or comparable magnitude, then consider whether or not it might be round-off error for something else.

Note 9: Save your file regularly. Most of the time, we expect that the Solver will run quickly. But for problems with many variables and many constraints – especially involving integers     – please be mindful that if you are not careful to do some of the things mentioned in class to   help your program finish more quickly, then there is a risk that your program might possibly  go through at least tens or hundreds of thousands of subproblems and become very slow (as    you wait and wait and …).  If you save your file before starting a run that could be long and    slow, then you can safely stop the program – if it becomes very slow – with reduced risk of     losing your edit changes.

Note 10: As a general rule for solving a problem using MicroSoft Excel Solver, please

consider carefully whether the various solver (settings or) Options (which you might

be able to access after clicking on `Options’, which might be on the right about two-

thirds of the way down after you click on `Solver’) might affect the results provided

by the solver.  (As an example, if dealing with integers then give some thought to `Integer   Optimality’.)   Put another way, rather than just use the default settings, make sure to check the solver settings and be willing to appropriately modify them if and as required.

We have at least one fictitious story (by way of motivation) which you can safely skip and bypass – and then proceed straight to the questions.

Motivation could include examples given at the start of Assignment 1.

Shortest pathis an example of transhipment, which in turn is relevant to (e.g.) evacuation emergencies, etc.

The design of braille for vision-impaired people could possibly have been seen as an optimisation problem, whether or not as a linear programming (LP) problem.

Throughout this Assignment, recall all notes and instructions - including but not limited to note 6.

----

Qu 1    (14 + 5 + 5 + 5 + 5 = 34 marks)

Consider the following fictitious transportation problem.

Nodes                         Supply/Demand

From                           To                 Unit Cost

1a)

Solve this transportation problem, giving flows along all arcs and the value of the objective function.

Show all working.

1b)

Consider finding a feasible solution (not necessarily your optimal solution from Qu 1a) which has positive flow on as few edges as possible.   Paraphrasing, consider the positive integer E     such that there is a feasible solution with positive flow on E edges but there is no feasible

solution with positive flow on only (E-1) edges.  Find the optimal solution which has flow on no more than E edges.

Solve this transportation problem, giving flows along all arcs and the value of the objective function.

Show all working.

Hints: Exercise 1c below involves counting edges, so possibly do exercise  1c first before     returning here to  1b.  There is a feasible solution to  1b with flow on 12 edges, there is no    feasible solution with flow on only 1 edge.  In the spirit of note 5, be as elegant as you can.

1c)

Returning to 1a, we now introduce a cost of $400 for each edge on which there is positive flow.

Solve this transportation problem, showing any changes from  1a.

Give flows along all arcs and the value of the objective function.

Show all working.

1d)

Continuing from 1c, we introduce the additional requirement that if there is positive flow

from Bennelong Point to Wollongong then there must also be positive flow from Copenhagen to Wollongong.

Solve this transportation problem, showing any changes from  1c.

Give flows along all arcs and the value of the objective function.

Show all working.

1e)

Continuing from 1a, the cost of the flow from Bennelong Point to Wollongong is changed. A flow of up to 175 is charged at a cost of $3 per unit, as before.

But now, any flow in excess of 175 is charged at a cost of $4 per unit.

Solve this transportation problem, showing any changes from  1a.

Give flows along all arcs and the value of the objective function.

Show all working.

----

Qu 2    (15 + 6 + 6 + 6 = 33 marks)

Consider workers A, B, C, D, E being assigned to tasks V, W, X, Y, Z.

The table below shows the costs of workers being allocated to tasks.

Each worker can be allocated to at most  1 task.

Each task requires exactly  1 worker.

2a)

Assuming that we pay these costs, then set this up as an optimisation problem and solve the

optimal allocation of workers to tasks and the optimal objective function.

Show all working.

2b)

Re-visiting 2a, assume instead that these costs are the charges that we impose upon others, and so instead they contribute to our profit.

Assuming that we profit from these charges, then set this up as an optimisation problem and solve the optimal allocation of workers to tasks and the optimal objective function.

Show all working.

2c)

Re-visiting 2a, we add the requirement that if worker D is allocated to task V then worker A must be allocated to task X.

Solve this problem, showing any changes from 2a.

Set this up as an optimisation problem and solve the optimal allocation of workers to tasks

and the optimal objective function.

Show all working.

2d)

Re-visiting 2a, we add the requirement that either worker A is allocated to task V or worker B must be allocated to task X (or possibly both).

Solve this problem, showing any changes from 2a.

Set this up as an optimisation problem and solve the optimal allocation of workers to tasks and the optimal objective function.

Show all working.

----