代写Analytics、代做R编程设计、代写data语言、代做R设计

日期：2020-04-06 08:57

Optimisation and Decision Making: Group

Assignment 2020

Master in Business Analytics, Melbourne Business School

Due date: April 15, 2pm

Instructions

The solution to the problems should take not more than 3 pages per

problem. All answers shall be self-contained with final conclusions, LP formulations

(where required) and brief explanations stated succinctly for each

problem. All code/spreadsheets are to be provided in an accompanying file

or appendix as supplementary material only. One should be able to understand

what you have done in the assignment without the need to open the

files/codes. The clarity of the explanations and the development of the solution

are as important as the solution itself. If you think the information

provided in a question is inadequate, please make reasonable assumptions

for answering it.

Problem 1: Graph Coloring (30 points)

Definition 1. A undirected graph G = (V, E) is an ordered pair in which

V = {1, . . . , n} is a finite set of nodes and E ? V × V is a set of edges

where if (x, y) ∈ E, then node x is connected to node y. (This relationship

is reflexive: if x is connected to y then y is also connected to x).

Definition 2. A coloring of a graph G consist in assigning a number (or a

color) to each node, with the restriction that any two nodes that have an

edge in between cannot be assigned the same number (or color).

Definition 3. The chromatic number of a graph is k ∈ N if there exists

a coloring that uses k colors, but there is no coloring that uses less than k

colors. In other words, the chromatic number is the minimum number of

colors needed to have a coloring of a graph.

The chromatic number of a graph has many applications in Management

Science. Prominent examples are timetabling, scheduling, and assignment

problems.

Part 1:

(1) Explain in words a (very) trivial coloring algorithm for an undirected

graph with n nodes. Give an upper bound on the number of colors

needed for your coloring algorithm.

(2) Formulate the chromatic number problem of a graph G = (V, E),

V = {1, . . . , n} as an integer linear program. Use the upper bound

found above to set the maximum number of colors available.

Table 1. A 3x3 sudoku

(3) A graph is given in the file graph2020.dat. It contains 74 nodes

and 301 edges and one possible coloring uses only 14 colors. There

are, however, colorings of the graph that use less than 14 colors.

You must find the chromatic number of this graph. This is a hard

instance to solve, and it may take some time for the solver to come

with an answer, so be patient.

A Sudoku puzzle is a problem where there is an incomplete 9x9 table of

numbers which must be filled according to the following rules:

? The table can be divided into 9 individual 3x3 boxes. In each of

these boxes, every number (i. e., a color) between 1 to 9 must appear

at least (and at most) once.

? Within any column of the 9x9 grid, each number between 1 to 9 must

be appear at least (and at most) once.

? Within any row of the 9x9 grid, each numbers between 1 to 9 must

be appear at least (and at most) once.

Part 2:

(4) Suppose that you have available a costly and efficient software to find

the chromatic number of any given graph. In addition, this software

also allows you to force any vertex to have a specific colour. Explain

(in at most one page) how would you transform a Sudoku instance

into an instance of the coloring problem so that after your software

obtains a coloring on the constructed instance, you are able to easily

find a solution of the original Sudoku problem.

(5) Based on the integer linear programming formulation found in Part 1,

write down an ILP to solve the Sudoku given in Table 1. Provide

the solution as well as the complete formulation in paper (and also

provide the code).

(6) Suppose you are given a Sudoku S and a feasible solution s to it.

Based on the previous ILP (question item 5), write down an integer

linear programming formulation that returns 1 if the solution s to

3

Figure 1. A 16x16 sudoku

the Sudoku S is not unique and it is infeasible if the solution s is

unique for S.

(7) Using the previous ILP model (question item 6), determine whether

the Sudoku given in Table 1 has a unique solution.

(8) In a 16x16 Sudoku, there are 16 rows and 16 columns. Each cell

must contain one out of the following 16 symbols: {0, 1, 2, 3, 4, 5, 6,

7, 8, 9, A, B, C, D, E, F}. The rules are of this game are a direct

extension of the rules for the standard Sudoku. Explain how would

you change the ILP provided for the 3x3 Sudoku to solve this larger

game. Implement an ILP and solve the Sudoku in Figure 1. (You

don’t need to write all the ILP again in the assignment. You can just

explain how do you need to change it. Naturally, the source code of

your implementation must be provided).

Problem 2: A rostering problem (20 points)

A major metropolitan hospital is keen to improve the roster for its nursing

staff. They have three different shifts that is: early shift (ES) from 7:00 to

4

16:00, late shift (LS) from 13:00 to 23:00, and night shift (NS) shift from

22:00 to 8:00 on next day, and they employ nurses having four skill levels

which are proficient (4), competent (3), beginner (2), and naive (1). The

hospital requires that the minimum number of nurses with sufficient expertises

are available on each shift. The aggregate numbers of nurses required

on each shift type are R for ES or LS and RN for NS on working days, and

Rh for ES or LS and RNh for NS on other days (weekends and holidays).

Along with this, there are a number of other requirements which are as follows:

(1) Average skill level of the rostered nurses on each shift should be at

least competent. Here, average skill level is defined as the average of

skill levels of all the rostered nurses. For example, if only three nurses

each with the skill level proficient (4), competent (3), and beginner

(2) are scheduled for a shift, then the average skill level at that shift

is competent ((4 + 3 + 2)/3 = 3).

(2) There should be at least 50% proficient and no more than 20% naive

nurses on each shift.

(3) Nurses are rostered for no more than one shift per day.

(4) No nurse is rostered for two consecutive shifts. This means a nurse

cannot be scheduled for another shift immediately after he or she

finishes a shift.

(5) Nurses are rostered for at least four shifts each week, no more than

six shifts in a week, and no more than ten shifts in a fortnight.

(6) For each nurse, there must be at least four rostered days off in a

fortnight and at least two rostered days off each fortnight should be

together.

(7) The NS should be fairly assigned to all the nurses so that no individual

is scheduled for many night shifts.

Consider a set of all nurses Sn : {1, 2, 3, .., n} is given to you where the first

{1, .., n1} nurses belongs to naive (1) level, the next {n1 + 1, .., n1 + n2}

belongs to beginner (2) level, and so on. This means that there are n1

naive nurses, n2 beginner nurses, n3 competent nurses, and n4 expert nurses.

Furthermore, use a set of days Days : {1, 2, .., 14} where day 1 denotes the

first week’s Monday, 2 denotes the Tuesday and so on. Hospital pays $Cdw

for each ES or LS on working days, $Cnw for each NS on working days,

5

$Cdh for each ES or LS on other days, and $Cnh for each NS on other days.

Formulate a MIP model to develop a fortnight’s minimum cost roster.

Problem 3: Zero-Sum Game (20 points)

In game theory and economic theory, a zero-sum game with two players

is a mathematical representation of a situation in which each participant’s

gain (or loss) of utility is exactly the loss (or gain) of the utility of the other

participant.

Formally, each player can choose one action out of a set of N possible

actions. Let A ∈ R

N×N , be the payoff matrix. The payoff of player 1 is

defined as follows: Aij is the payoff of player 1, when player 1 chooses action

i and player 2 chooses action j. Given that we are in the case of a zero-sum

game, the payoff of player 2 is defined as follows: ?Aij is the payoff of player

2, when player 1 chooses action i and player 2 chooses action j.

For example, consider a penalty shootout in a soccer game consisting of

a shooter (player 1) and a goalie (player 2). For simplification the ball can

only be shoot to the left or to the right. The payoffs of the shooter are

represented in the left table, and the payoffs of the goalie are represented in

the right table.

For instance, if the shooter shoots to the left and the goalie dives to the

right, shooter’s payoff is 1 and goalie’s payoff is -1. The payoff matrix of the

game is

A =?1 1 1 ?1

Suppose the game is played sequentially as follows:

? The goalie chooses an strategy that consists in playing left or right

with certain probabilities. That is, the goalie with probability y1 ∈

[0, 1] will dive to the left and with probability y2 = 1 ? y1 to the

right. We denote the goalie strategy as a vector y

T = (y1, y2) (where the yT

stands for the transpose vector of y).

? The vector selected by the goalie y

T = (y1, y2) is communicated to

the shooter.

? The shooter then chooses x

T = (x1, x2) knowing yT, where x1 ∈ [0, 1]

is the probability the shooter will shoot to the left and x2 = 1 ? x1

is the probability he shoots to the right.

6

The expected utility v of the shooter can be expressed in matrix form as

v = x

T Ay=x1 x2?1 1

1 ?1 y1 y2= (?y1 + y2) (x1 ? x2)

Similarly, the expected payoff c of the goalie can be expressed in matrix form

as c = y

T(?A)x = x

T(?A)y = ?v. Notice that the expected payoff of the

shooter is equal to minus the expected payoff of the goalie.

Since the shooter knows that the goalie has chosen y and knows that for

a given x, the outcome is x

T Ay, then the shooter wants to choose x to

maximize x

T Ay, giving him an outcome of

max

T Ay = max

x(?y1 + y2) (x1 ? x2).

Notice that if (?y1 + y2) ≥ 0, then the optimal strategy of the shooter is

x1 = 1, x2 = 0. If (?y1 + y2) < 0, then the optimal strategy of the shooter

is x1 = 0, x2 = 1. Therefore, v = maxx x

T Ay can be written as

max

T Ay = max{(?y1 + y2),(y1 ? y2)}.

Where max{x, y} is a function that returns x if x ≥ y and y otherwise.

Since the goalie knows what the shooter will do and will know the given

outcome, he chooses to minimize the payoff of the shooter. Thus, the final

outcome will be

The minimizing y above is called the min max strategy.

(1) Formulate a linear programming (LP) model to find the optimal

min max strategy y. Hint: Notice that the objective function is

not linear, so consider using an auxiliary variable v to represent

max ((?y1 + y2),(y1 ? y2)) using two constraints.

(2) Solve the above linear programming model.

(3) Now consider that the shooter chooses his strategy x first and then

the goalie selects his action y, knowing x. In this case, the shooter

will choose a strategy x, such that,

That is, the shooter will choose a max min strategy. Formulate the

linear programming model to find the max min strategy x.

(4) Notice that the LP in part (1) is the dual of the LP in part (3). Using

this fact, what can you say about the optimal objective value of the

second LP based on the solution obtained in part (2)?

(5) Solve the LP model of part (3).

7

(6) Consider the same game but with the following payoff matrix

Find the min max strategy y and the max min strategy x with this

new payoff matrix.

Problem 4: Robotic Assembly Line Balancing (30 points)

An assembly line is a product-oriented layout with workstations placed in

a sequential and linear order, also known as flow-shop. They are commonly

employed in high-volume industries to produce standardised products. A

flow-shop diagram is shown in Figure 2. The pace in such lines is dictated

by the most loaded station, namely the bottleneck. The terminology applied

to understand the assembly line balancing problem is hereafter presented.

Station 1 Station 2 ... Station n

Product to be processed

Processed product

Figure 2. Flow-shop diagram.

Task: an indivisible work-unit, each of them with a deterministic duration.

Each task must be assigned to only one station.

Duration of tasks: the time necessary to perform a given task. The

processing time in a station is the sum of the task durations assigned to it.

Precedence relations between tasks: sequence or order in which tasks

must be performed given by a partial ordering graph.

Precedence graph: a graph constructed from the precedence relations

to better visualise their order. Tasks are represented by circles, its index

by the number inside the circle, and arrows represent precedence relations.

Figure 3 illustrates a precedence graph. For example, in order to perform

task 6, both tasks 2 and 3 must have been performed. To perform task 8,

task 6 has to be performed and, consequently, tasks 1, 2, and 3 as well.

Station: a physical location where a particular set of tasks is performed.

Stations in an assembly line are displayed as a flow-shop and are generally

linked by conveyor belts. Each station processes only one task at a time.

Cycle time: line’s output rate. For instance, if an assembly line produces

120 units of a given product in one hour, its throughput rate is 2 units/minute

and, consequently, its cycle time is 0.5 minute/product. As stations layout

is sequential, the cycle time is determined by the most loaded station, i.e.

by the station that has the greatest sum of task processing times

A common simplification found in the Simple Assembly Line Balancing

Problem (SALBP) is that all stations are capable to perform any task. With

8

this idea in mind, the concept of a SALBP is to assign all tasks to stations in

an assembly line while respecting precedence relations. As for the objectives,

the type-1 version (SALBP-1) aims at the minimisation of stations when

production rate requirements are fixed, for example, when the demand is

known and must be met. On the other hand, the type-2 (SALBP-2) aims at

the minimisation of the cycle time (and therefore maximisation of production

rate) given a certain number of available stations.

The following example shows an electronic industry (Amp-Opt) manufacturing

an amplifier. The product has 12 assembly tasks, each of them with

a given duration (in minutes) and subjected to one or more precedence relations,

which are specified in Table 2. The precedence graph is presented in

Figure 3.

Table 2. Task and predecessor list for an amplifier.

Task Description Duration Predecessor(s)

1 Assembly box preparation 3 -

2 Printed circuit board (PCB) with power module assembly 6 1

3 PCB with pre-amplifier assembly 7 1

4 Amplifier filter assembly 6 2

5 Push-pull circuit assembly 4 2

6 PCBs connections 8 2,3

7 Pre-amplifier circuit placement and welding 9 3

8 Connectors adjustments 11 6

9 Push-pull heat sink placement 2 4,5,8

10 Protection board placement 13 8,11

11 Electrostatic protection assembly 4 7

12 Finishing&Packing 3 9,10

Figure 3. Precedence graph for an amplifier.

The manager of this assembly line wished to distribute (assign) these

tasks to 4 stations and minimise the cycle time (workload in the bottleneck

station), resulting in a SALBP-2 instance. Figure 4 illustrates the scenario

under study:

The optimal solution in this case would be a cycle time of 20 minutes,

with tasks 1, 2, 3 and 5 assigned to station 1; 6 and 8 to station 2; 4, 7 and

9 to station 3; and 10, 11 and 12 to station 4. However, as this assembly

9

In Out

Station 1 Station 2 Station 3 Station 4

Figure 4. Assembly line balancing problem under study.

line only works 8 hours per day on business days, such production rate is

not enough to meet the monthly demand of 600 units for their amplifiers.

Considering 20 business days per month:

Part 1:

(1) How many amplifiers per month can Amp-Opt manufacture with the

current configuration (4 stations)? What is the minimum cycle time

Amp-Opt has to achieve to meet its demand?

(2) Formulate an integer linear programming (ILP) model for the SALBP-

1 and solve it with the required cycle time to meet the demand.

Present your model by explaining all your variables, constraints and

parameters. (Hint: use variables to state which task is assigned to

which station and precedence constraints for each pair of tasks)

(3) The solution should describe how many stations is required to achieve

the minimum cycle time, as well as where each task has been assigned

to.

Multiple Types of Robots

By revisiting the simplification hypothesis (SH) that tasks can be performed

in any station as long as precedence relations are respected, we

observe that such SH was valid when workforce was homogeneous and composed

of humans. Nonetheless, modern assembly lines heavily rely on robotic

labour to execute tasks. In particular, the automotive industry employs

robots for precision, quality, and security reasons. This new feature gives

rise to the Robotic Assembly Line Balancing (RALB) problem.

For instance, the Resistance Spot Welding (RSW) technique is widely used

in order to perform welding tasks in the body-in-white stage, in which the

car’s “body” is built. This process unites metal sheets by using welding guns.

Metal sheet joining tasks must respect geometric tolerances, demanding high

quality robots and tools for precision purposes. Such tasks are called geometry

tasks. Furthermore, the RSW technique is also used for reinforcement

welding and screw adding points, namely finishing and stud tasks, respectively.

Differently from geometry tasks, these ones do not require strict

assurance for geometric tolerances and can be performed by simpler robots.

Finishing tasks can be performed by either this simpler (and cheaper) robot,

or by the most precise (and more expensive) one in less time. Stud tasks,

10

however, require a specific tool, and therefore these tasks must be exclusively

performed by robots equipped with the stud gun.

Figure 5 is the precedence graph of a given car model produced in the

company under study, geometry and stud tasks are indicated in the graph.

Table 3 presents the task durations of that model, where geometry tasks are

bold-faced, stud tasks are italicised, and the remaining ones are finishing

tasks – higher processing times are for the cheaper robot. The prices of the

most precise robot (Robot 1) and its cheaper version (Robot 2) to perform

welding tasks are $20 and $10 monetary units, respectively, while the price

for the stud robots (Robot 3) is $18 monetary units. The cycle time for this

line is 250 time units. (Note: these data has been normalised from the actual

values to preserve industrial confidentiality.)

Figure 5. Precedence diagram for a vehicle model. Geometry

(G) and Stud (S) tasks are indicated in the graph, while

the remaining ones are finishing tasks.

Table 3. Task durations (time units) for a vehicle model.

Task Robot(s) Duration(s) Task Robot(s) Duration(s)

Part 2:

(1) In this context, the objective for a type-1 RALB problem is no longer

the minimisation of stations. When the desired production rate is

given, the objective is to minimise the total cost to implement such

assembly line. Formulate an integer linear programming (ILP) model

for this problem and solve it with the required cycle time to meet

the demand. Present your model by explaining all your variables,

constraints and parameters. Which assortment of robots did you

choose? Where are they assigned to? Which tasks are they performing?

(Hint: use variables to state which task is assigned to which

station and performed by which robot. Notice that the actual processing

time depends on the robot you are using.)

(2) Now supposed that you have a limited budget of $90 monetary units

to built your robotic assembly line. Modify your previous model to

tackle this problem and solve it with the budget limitation. Present

your model by explaining all your variables, constraints and parameters.

Which assortment of robots did you choose? Where are they

assigned to? Which tasks are they performing?

(3) Assume this assembly line has a 2-year lifespan and works 20 business

days per month and 8 hours per day. After this time, the model has

to be updated to a new version and the robots replaced. You have

been given a flexible budget to spend between $80 and $100 monetary

units in building the line. Each unit of the manufactured product

gives you a profit of $0.12. What budget should you ask for in this

range ($80 to $100)? Explain your decision in detail. Consider each

time unit to be equivalent to one minute and unlimited demand.

Problem 5: Distribution problem (20 points)

A company produces the same product at two different factories (Factories

A and B), and then the product has to be shipped to three consumer centers

(C, D and E). The monthly production capacities of the factories A and B

are 400 and 300 units, respectively. The unitary production cost at factories

A and B are $8 and $10, respectively. A maximum of 100 units of inventory

can be held in each factory, at a cost of $1.50 per unit of the product per

month. Each consumer centre has a known demand for the product, and

there are different costs associated with transporting products from each

factory to each consumer center, depending on the distance.

Consumer centre 1 2 3

Table 4. Three month demand window for product across

consumer centres.

Table 5. Transportation costs (per unit) from factories to

consumer centers.

Questions.

(1) Write a linear program to model and find the optimal distribution

plan to ensure that demand at the consumer centers is met while

minimising the combined cost of production, transportation and inventory.

(2) Modify the model from (1) to account for the fact that the transportation

cost between a factory and a center in a period is given by

a fixed amount of $200 per month1 plus the cost of transportation

per unit.

(3) Modify the model from (2) to account for the fact that you can ship

products from one factory to the other with a cost of $2 per unit

transported.

Problem 6: Energy provision (20 points)

The state of Victoria primarily relies on brown coal sources for electricity

generation. Here, we wish to consider a simple variant of the problem of

introducing, locating and sizing renewable energy resources, namely wind

and solar farms, hydro power, and biomass plants, in the state of Victoria.

Let L = {1, 2, . . . , n} be the set of candidate locations in Victoria and

R = {W ind, Solar, Hydro, Biomass} be the set of renewable resource types.

At most two renewable resource types are to be installed at any candidate

location l ∈ L. If some renewable resource type r ∈ R is installed at location

l ∈ L, we need to allocate at least SMIN

lr and at most SMAX

lr units of the

resource. A one-off cost,

lr, is incurred when a farm with renewable resource

type r ∈ R is setup at location l ∈ L; and it costs C

lr for each unit of the

renewable resource type installed at the location.

Renewable resource locations and farm-size decisions are driven by demand

for electricity and the prospect/potential of a location for renewable

energy generation. For this simple problem variant, the renewable resources

are not to be used to replace existing brown coal generation sources, but are

instead used to cope with demand fluctuations beyond the base electricity

supply generated by brown coal sources. Therefore, the “demand for electricity”

is defined here as the amount of electricity to be supplied solely by

the renewable resources.

Let the set of discrete, equally-sized, time periods be T. Each time period

may, for example, represent a 30-minute interval and the length of the

1That must be paid if there is transportation between the factory and the center.

13

planning horizon could be 5 days – in this case T = {1, 2, 3, . . . , 239, 240}.

Let Dt be the demand for electricity at time t ∈ T. Each location l ∈ L can

produce Plrt amount of electricity during time t ∈ T per unit of renewable

resource type r ∈ R installed.

The total renewable energy generation must be at least Dt for all t ∈ T.

There is a further requirement that the variability of the total renewable

energy generation be “reasonable”. To achieve a “reasonable” variability, any

deviation from the total average generation for any given day is penalized

as follows: one unit of positive deviation is penalized at C

P and one unit of

negative deviation is penalized at CM. For instance, consider a three-period

example with total renewable generations G1 , G2 and G3 on time periods

1, 2, and 3, respectively. The average total generation is A =G1+G2+G3

and

suppose G1 < A, G2 = A, and G3 > A. The total penalty for this example

is given by CM(A ? G1) + 0 + C

P (G3 ? A).

Formulate a mixed-integer linear program (MILP) that will locate the renewable

resources and determine their farm sizes such that the total farm

establishment costs plus the total variability penalty is minimized, and demand

for electricity is met.