## Linear Programming, Transport Modelling, and Supermarket Scheduling (4 tasks) Task 1 Simple LP Optimisation A small factory has two products (A and B). In order to keep the factory running, at least 20 units of products must be produced each day. Product A costs \$100 and requires 3 hours to produce, while Product B costs \$80 and requires 4 hours to produce. The total costs must be less than \$6000 as the budget each day and the number of hours mu

Assignment 2 Engineering Simulation (PDE4905) (For January Start) [Option 2]

Choose this option only if you think your background is more appropriate to show your ability in simulation and report writing.

[Please note: Both options are equal; no option is easier than the other.] Linear Programming, Transport Modelling, and Supermarket Scheduling (4 tasks)

A small factory has two products (A and B). In order to keep the factory running, at least 20 units of products must be produced each day. Product A costs \$100 and requires 3 hours to produce, while Product B costs \$80 and requires 4 hours to produce. The total costs must be less than \$6000 as the budget each day and the number of hours must be less than 160 hours per day. In addition, the market regulations require that the number of Product B cannot exceed twice the number of Product A.

If each Product A gives a profit of \$30 and each Product B gives a profit of \$50, design a simple daily production portfolio (in terms of the numbers of Products A and B to be produced) so that the total profit is maximized.

• Write this problem as a simple linear programming problem with the objective and all appropriate constraints.

• Find its optimal solution by solving it using two different methods (e.g., graphical method and Excel Solver/Matlab/Octave).

A product has 4 suppliers (A, B, C, D) that produce a total of 1000 units. All the units produced should be distributed to 6 demand stations (P, Q, R, S, T, W). The transportation costs for transporting one unit from a supplier to a station are given as follows:

 P Q R S T W 100 140 265 170 225 100 Supplier A 1 2 3 4 5 6 S1=150 Supplier B 7 7 5 5 4 4 S2=250 Supplier C a b c d e f S3=400 Supplier D f e d c b a S4=200 Thus, its transportation cost matrix is simply 1 2 3 4 5 6 = [ 7 7 5 5 4 4 ],

where a,b,c,d,e,and f are the single digits of your student number in the format “M00abcdef”. For

example, if your number is M00152379, you have a=1, b=5, c=2, d=3, e=7 and f=9.

Let xij be the integer quantity to be distributed from Supplier (Si) to Station (j=P,Q,…,W). The objective is to distribute the product such that

 Minimize ∑4 ∑6 , subject to various constraints. =1 =1

• Write down the mathematical formulation for this problem with the objective and all relevant constraints and discuss their meanings briefly.

• Solve the problem using either Excel Solver or Matlab/Octave to find its optimal solution. Check if the solution can indeed satisfy all the constraints.

A busy supermarket is open 24 hours daily. It has a set of 20 checkout counters, though the actual number of checkouts needed ranges from 2 to 20, depending on the time of day. The number of staff needed to provide a satisfactory service varies at different hours as summarized in the Table

 Time Periods Number of counters/staff needed 9:00 am – 10:00 am 14 10:00 am – 12:00 (noon) 10 12:00 – 3:00 pm 17 3:00 pm – 8:00 pm 22 8:00 pm – 12:00 am (midnight) 12 12:00 am – 4:00 am 6 4:00 am – 9:00 am 5

The supermarket employs 14 full-time staff and a large number of part-time staff. Part-time staff typically can work either a 4-hour shift or an 8-hour shift every day and can start on the hour between 9:00 am to 3:00 pm, or at 3:00 pm, 8:00 pm, 12:00 am (midnight) or 4:00 am.

Full-time staff work at most 40 hours per week between 9:00 am to 5:00 pm with a daily wage of £100 for 8 hours per day, while part-time workers are paid at a standard rate of £9 per hour (i.e., £72 per day for 8 hours or £36 for 4 hours). The company policy only permits that up to 80% of the total working hours of any day to be part-time hours.

The main task is to schedule the staff so that the total staff costs are minimized on a daily basis.

• Formulate the scheduling problem in terms of a linear programming problem with a correct objective and all appropriate constraints. Explain in detail why your mathematical formulation is appropriate, including any assumptions that you may have used.

• Solve your staff scheduling problem using either Excel Solver or Matlab (intlinprog)/Octave (glpk). Summarize your solution procedure (including screenshots if appropriate) and present the main results with a brief discussion.

• Check if all the required numbers of counters are met.

[Note: There may be multiple (equally optimal) solutions. You only need to find one optimal solution.]

Find a real-world application (e.g., a small shop/restaurant/bookstore, etc.) to schedule their staff using linear programming. Solve it using either Excel Solver or Matlab/Octave and discuss any implications of your solution.

Report and Guidelines

Write a report that includes the following:

1. Explain your understanding of linear programming and its applications (10% of the total marks)

Show your results with screenshots and/outputs when appropriate.

The report should include your models/formulations and the main results on a series of tasks. Your mathematical formulations and programs should be clearly presented, and an evaluation of your solutions can be discussed in the light of all assumptions made and if your solutions can indeed satisfy all the constraints.

Your report must be in the form of a standard Technical Report or article to include:

Title Page

Abstract:  About 100 words, no more than 150 words.

Introduction: Include a brief review of the background and literature, and explanation of linear programming, transport/resources allocation problems, etc., citing relevant references when appropriate.

Methods: Describe your modelling technique, the structure of your model or implementations. Justify your approaches to formulating the model and cite relevant references when appropriate.

Results:  Present your main results and explain them in detail. Use graphs and/or tables when appropriate.

Discussion: Discuss your mathematical formulations, solutions to your problems/tasks and their implications for real-world systems such as the staff scheduling for a large airline or a factory in real time.

Conclusions: Draw brief conclusions and evaluate any possible limitations.

Notes:

There is no word limit, though it is typically in the range of 2500 to 4000 words (or about 10 to 15 pages, depending on the font size/style and spacing).

Submission

Submit your report and the model file via the online Moodle system (UniHub). Make sure that you submit well before the deadline.

For the final submission, you need to submit both your report file and computer source file(s) for solving the linear programming problems.