MAST20018 – Discrete Mathematics and Operations Research

MAST20018 – Discrete Mathematics and Operations Research

Assignment 3

Upload to  Gradescope by 5pm  Wed  18th September 2024

Question 1

In assignment 1, you considered the following project with 8 activities, labelled A to H:

Clearly define variables and propose a linear programming model to find the project’s earliest com- pletion time.

Question 2

Consider a company that manufactures n products and wants to plan its production over the next T time periods.  The demand for each product i ∈ {1,..., n} in each period t ∈ T of the planning horizon is given by dit.  In each period,  a single resource is required for production.  This resource is limited and renewable, i.e., in each period, the amount of the resource available does not depend on how it was used in previous periods.  Examples of renewable resources include labor, electricity, and machine hours, while non-renewable resources are, for example, raw materials that remain from one period and can be used in subsequent periods. Let Rt  be the amount of the renewable resource available dai 写MAST20018 – Discrete Mathematics and Operations Researchin period t ∈ T. Also let ri  be the quantity of the resource required to produce one unit of item i ∈ {1,..., n}.  The production cost depends on the product and on the period it is produced and is given by cit.  There is the possibility of storing products from one period to the next.   If a product is stored at the end of period t to be used later, a cost hit  is incurred.  There is no inventory at the beginning of the planning period.

a)  Clearly define your variables and model the production planning problem to meet the demand while minimising total costs as a linear programming model.

b)  Update your model to include backlogging, which occurs when some or all of the demand for a product in one period is fulfilled in a later period.  Let bit  be the cost of having one unit of product i in backlog at the end of period t.  Additionally, ensure that all demand is fully met by the end of the planning period. Write out the full linear programming model, not just the changes, and clearly define all variables used.

Question 3

The shaded area in the figure below depicts the feasible region of a linear programming model with 2 variables.

a) Write the constraints of the problem. Label them as blue, green and red constraints.

b)  Given the objective function f(x) = maxax1 +bx2 , determine all possible values of a and b for which the problem will have two distinct extreme points in the set of optimal solutions.