Optimisation and Decision Making: GroupAssignment 2020Master in Business Analytics, Melbourne Business SchoolDue date: April 15, 2pmInstructionsThe solution to the problems should take not more than 3 pages perproblem. All answers shall be self-contained with final conclusions, LP formulations(where required) and brief explanations stated succinctly for eachproblem. All code/spreadsheets are to be provided in an accompanying fileor appendix as supplementary material only. One should be able to understandwhat you have done in the assignment without the need to open thefiles/codes. The clarity of the explanations and the development of the solutionare as important as the solution itself. If you think the informationprovided in a question is inadequate, please make reasonable assumptionsfor answering it.Problem 1: Graph Coloring (30 points)Definition 1. A undirected graph G = (V, E) is an ordered pair in whichV = {1, . . . , n} is a finite set of nodes and E ⊆ V × V is a set of edgeswhere if (x, y) ∈ E, then node x is connected to node y. (This relationshipis 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 acolor) to each node, with the restriction that any two nodes that have anedge in between cannot be assigned the same number (or color).Definition 3. The chromatic number of a graph is k ∈ N if there existsa coloring that uses k colors, but there is no coloring that uses less than kcolors. In other words, the chromatic number is the minimum number ofcolors needed to have a coloring of a graph.The chromatic number of a graph has many applications in ManagementScience. Prominent examples are timetabling, scheduling, and assignmentproblems.Part 1:(1) Explain in words a (very) trivial coloring algorithm for an undirectedgraph with n nodes. Give an upper bound on the number of colorsneeded 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 boundfound 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 nodesand 301 edges and one possible coloring uses only 14 colors. Thereare, however, colorings of the graph that use less than 14 colors.You must find the chromatic number of this graph. This is a hardinstance to solve, and it may take some time for the solver to comewith an answer, so be patient.A Sudoku puzzle is a problem where there is an incomplete 9x9 table ofnumbers which must be filled according to the following rules:• The table can be divided into 9 individual 3x3 boxes. In each ofthese boxes, every number (i. e., a color) between 1 to 9 must appearat least (and at most) once.• Within any column of the 9x9 grid, each number between 1 to 9 mustbe appear at least (and at most) once.• Within any row of the 9x9 grid, each numbers between 1 to 9 mustbe appear at least (and at most) once.Part 2:(4) Suppose that you have available a costly and efficient software to findthe chromatic number of any given graph. In addition, this softwarealso allows you to force any vertex to have a specific colour. Explain(in at most one page) how would you transform a Sudoku instanceinto an instance of the coloring problem so that after your softwareobtains a coloring on the constructed instance, you are able to easilyfind 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. Providethe solution as well as the complete formulation in paper (and alsoprovide 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 integerlinear programming formulation that returns 1 if the solution s to3Figure 1. A 16x16 sudokuthe Sudoku S is not unique and it is infeasible if the solution s isunique for S.(7) Using the previous ILP model (question item 6), determine whetherthe Sudoku given in Table 1 has a unique solution.(8) In a 16x16 Sudoku, there are 16 rows and 16 columns. Each cellmust 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 directextension of the rules for the standard Sudoku. Explain how wouldyou change the ILP provided for the 3x3 Sudoku to solve this largergame. Implement an ILP and solve the Sudoku in Figure 1. (Youdon’t need to write all the ILP again in the assignment. You can justexplain how do you need to change it. Naturally, the source code ofyour implementation must be provided).Problem 2: A rostering problem (20 points)A major metropolitan hospital is keen to improve the roster for its nursingstaff. They have three different shifts that is: early shift (ES) from 7:00 to416:00, late shift (LS) from 13:00 to 23:00, and night shift (NS) shift from22:00 to 8:00 on next day, and they employ nurses having four skill levelswhich are proficient (4), competent (3), beginner (2), and naive (1). Thehospital requires that the minimum number of nurses with sufficient expertisesare available on each shift. The aggregate numbers of nurses requiredon each shift type are R for ES or LS and RN for NS on working days, andRh 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 atleast competent. Here, average skill level is defined as the average ofskill levels of all the rostered nurses. For example, if only three nurseseach with the skill level proficient (4), competent (3), and beginner(2) are scheduled for a shift, then the average skill level at that shiftis competent ((4 + 3 + 2)/3 = 3).(2) There should be at least 50% proficient and no more than 20% naivenurses 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 nursecannot be scheduled for another shift immediately after he or shefinishes a shift.(5) Nurses are rostered for at least four shifts each week, no more thansix 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 afortnight and at least two rostered days off each fortnight should betogether.(7) The NS should be fairly assigned to all the nurses so that no individualis 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 n1naive 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 thefirst week’s Monday, 2 denotes the Tuesday and so on. Hospital pays $Cdwfor 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 playersis a mathematical representation of a situation in which each participant’sgain (or loss) of utility is exactly the loss (or gain) of the utility of the otherparticipant.Formally, each player can choose one action out of a set of N possibleactions. Let A ∈ RN×N , be the payoff matrix. The payoff of player 1 isdefined as follows: Aij is the payoff of player 1, when player 1 chooses actioni and player 2 chooses action j. Given that we are in the case of a zero-sumgame, the payoff of player 2 is defined as follows: −Aij is the payoff of player2, when player 1 chooses action i and player 2 chooses action j.For example, consider a penalty shootout in a soccer game consisting ofa shooter (player 1) and a goalie (player 2). For simplification the ball canonly be shoot to the left or to the right. The payoffs of the shooter arerepresented in the left table, and the payoffs of the goalie are represented inthe right table.For instance, if the shooter shoots to the left and the goalie dives to theright, shooter’s payoff is 1 and goalie’s payoff is -1. The payoff matrix of thegame isA =−1 1 1 −1Suppose the game is played sequentially as follows:• The goalie chooses an strategy that consists in playing left or rightwith certain probabilities. That is, the goalie with probability y1 ∈[0, 1] will dive to the left and with probability y2 = 1 − y1 to theright. We denote the goalie strategy as a vector yT = (y1, y2) (where the yTstands for the transpose vector of y).• The vector selected by the goalie yT = (y1, y2) is communicated tothe shooter.• The shooter then chooses xT = (x1, x2) knowing yT, where x1 ∈ [0, 1]is the probability the shooter will shoot to the left and x2 = 1 − x1is the probability he shoots to the right.6The expected utility v of the shooter can be expressed in matrix form asv = xT Ay=x1 x2−1 11 −1 y1 y2= (−y1 + y2) (x1 − x2)Similarly, the expected payoff c of the goalie can be expressed in matrix formas c = yT(−A)x = xT(−A)y = −v. Notice that the expected payoff of theshooter is equal to minus the expected payoff of the goalie.Since the shooter knows that the goalie has chosen y and knows that fora given x, the outcome is xT Ay, then the shooter wants to choose x tomaximize xT Ay, giving him an outcome ofmaxT Ay = maxx(−y1 + y2) (x1 − x2).Notice that if (−y1 + y2) ≥ 0, then the optimal strategy of the shooter isx1 = 1, x2 = 0. If (−y1 + y2) is x1 = 0, x2 = 1. Therefore, v = maxx xT Ay can be written asmaxT 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 givenoutcome, he chooses to minimize the payoff of the shooter. Thus, the finaloutcome will beThe minimizing y above is called the min max strategy.(1) Formulate a linear programming (LP) model to find the optimalmin max strategy y. Hint: Notice that the objective function isnot linear, so consider using an auxiliary variable v to representmax ((−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 thenthe goalie selects his action y, knowing x. In this case, the shooterwill choose a strategy x, such that,That is, the shooter will choose a max min strategy. Formulate thelinear 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). Usingthis fact, what can you say about the optimal objective value of thesecond 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 matrixFind the min max strategy y and the max min strategy x with thisnew payoff matrix.Problem 4: Robotic Assembly Line Balancing (30 points)An assembly line is a product-oriented layout with workstations placed ina sequential and linear order, also known as flow-shop. They are commonlyemployed in high-volume industries to produce standardised products. Aflow-shop diagram is shown in Figure 2. The pace in such lines is dictatedby the most loaded station, namely the bottleneck. The terminology appliedto understand the assembly line balancing problem is hereafter presented.Station 1 Station 2 ... Station nProduct to be processedProcessed productFigure 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. Theprocessing time in a station is the sum of the task durations assigned to it.Precedence relations between tasks: sequence or order in which tasksmust be performed given by a partial ordering graph.Precedence graph: a graph constructed from the precedence relationst代写Analytics作业、代做R编程设计作业、代写data语言作业、代做R课程设计作业 代写R语言编程|代做留学生Pro better visualise their order. Tasks are represented by circles, its indexby the number inside the circle, and arrows represent precedence relations.Figure 3 illustrates a precedence graph. For example, in order to performtask 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 generallylinked by conveyor belts. Each station processes only one task at a time.Cycle time: line’s output rate. For instance, if an assembly line produces120 units of a given product in one hour, its throughput rate is 2 units/minuteand, consequently, its cycle time is 0.5 minute/product. As stations layoutis sequential, the cycle time is determined by the most loaded station, i.e.by the station that has the greatest sum of task processing timesA common simplification found in the Simple Assembly Line BalancingProblem (SALBP) is that all stations are capable to perform any task. With8this idea in mind, the concept of a SALBP is to assign all tasks to stations inan assembly line while respecting precedence relations. As for the objectives,the type-1 version (SALBP-1) aims at the minimisation of stations whenproduction rate requirements are fixed, for example, when the demand isknown and must be met. On the other hand, the type-2 (SALBP-2) aims atthe minimisation of the cycle time (and therefore maximisation of productionrate) given a certain number of available stations.The following example shows an electronic industry (Amp-Opt) manufacturingan amplifier. The product has 12 assembly tasks, each of them witha given duration (in minutes) and subjected to one or more precedence relations,which are specified in Table 2. The precedence graph is presented inFigure 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 13 PCB with pre-amplifier assembly 7 14 Amplifier filter assembly 6 25 Push-pull circuit assembly 4 26 PCBs connections 8 2,37 Pre-amplifier circuit placement and welding 9 38 Connectors adjustments 11 69 Push-pull heat sink placement 2 4,5,810 Protection board placement 13 8,1111 Electrostatic protection assembly 4 712 Finishing&Packing 3 9,10Figure 3. Precedence graph for an amplifier.The manager of this assembly line wished to distribute (assign) thesetasks to 4 stations and minimise the cycle time (workload in the bottleneckstation), resulting in a SALBP-2 instance. Figure 4 illustrates the scenariounder 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 and9 to station 3; and 10, 11 and 12 to station 4. However, as this assembly9In OutStation 1 Station 2 Station 3 Station 4Figure 4. Assembly line balancing problem under study.line only works 8 hours per day on business days, such production rate isnot 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 thecurrent configuration (4 stations)? What is the minimum cycle timeAmp-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 andparameters. (Hint: use variables to state which task is assigned towhich station and precedence constraints for each pair of tasks)(3) The solution should describe how many stations is required to achievethe minimum cycle time, as well as where each task has been assignedto.Multiple Types of RobotsBy revisiting the simplification hypothesis (SH) that tasks can be performedin any station as long as precedence relations are respected, weobserve that such SH was valid when workforce was homogeneous and composedof humans. Nonetheless, modern assembly lines heavily rely on roboticlabour to execute tasks. In particular, the automotive industry employsrobots for precision, quality, and security reasons. This new feature givesrise to the Robotic Assembly Line Balancing (RALB) problem.For instance, the Resistance Spot Welding (RSW) technique is widely usedin order to perform welding tasks in the body-in-white stage, in which thecar’s “body” is built. This process unites metal sheets by using welding guns.Metal sheet joining tasks must respect geometric tolerances, demanding highquality robots and tools for precision purposes. Such tasks are called geometrytasks. Furthermore, the RSW technique is also used for reinforcementwelding and screw adding points, namely finishing and stud tasks, respectively.Differently from geometry tasks, these ones do not require strictassurance 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,10however, require a specific tool, and therefore these tasks must be exclusivelyperformed by robots equipped with the stud gun.Figure 5 is the precedence graph of a given car model produced in thecompany under study, geometry and stud tasks are indicated in the graph.Table 3 presents the task durations of that model, where geometry tasks arebold-faced, stud tasks are italicised, and the remaining ones are finishingtasks – higher processing times are for the cheaper robot. The prices of themost precise robot (Robot 1) and its cheaper version (Robot 2) to performwelding tasks are $20 and $10 monetary units, respectively, while the pricefor the stud robots (Robot 3) is $18 monetary units. The cycle time for thisline is 250 time units. (Note: these data has been normalised from the actualvalues to preserve industrial confidentiality.)Figure 5. Precedence diagram for a vehicle model. Geometry(G) and Stud (S) tasks are indicated in the graph, whilethe 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 longerthe minimisation of stations. When the desired production rate isgiven, the objective is to minimise the total cost to implement suchassembly line. Formulate an integer linear programming (ILP) modelfor this problem and solve it with the required cycle time to meetthe demand. Present your model by explaining all your variables,constraints and parameters. Which assortment of robots did youchoose? Where are they assigned to? Which tasks are they performing?(Hint: use variables to state which task is assigned to whichstation and performed by which robot. Notice that the actual processingtime depends on the robot you are using.)(2) Now supposed that you have a limited budget of $90 monetary unitsto built your robotic assembly line. Modify your previous model totackle this problem and solve it with the budget limitation. Presentyour model by explaining all your variables, constraints and parameters.Which assortment of robots did you choose? Where are theyassigned to? Which tasks are they performing?(3) Assume this assembly line has a 2-year lifespan and works 20 businessdays per month and 8 hours per day. After this time, the model hasto be updated to a new version and the robots replaced. You havebeen given a flexible budget to spend between $80 and $100 monetaryunits in building the line. Each unit of the manufactured productgives you a profit of $0.12. What budget should you ask for in thisrange ($80 to $100)? Explain your decision in detail. Consider eachtime 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 (FactoriesA 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 Bare 400 and 300 units, respectively. The unitary production cost at factoriesA and B are $8 and $10, respectively. A maximum of 100 units of inventorycan be held in each factory, at a cost of $1.50 per unit of the product permonth. Each consumer centre has a known demand for the product, andthere are different costs associated with transporting products from eachfactory to each consumer center, depending on the distance.Consumer centre 1 2 3Table 4. Three month demand window for product acrossconsumer centres.Table 5. Transportation costs (per unit) from factories toconsumer centers.Questions.(1) Write a linear program to model and find the optimal distributionplan to ensure that demand at the consumer centers is met whileminimising the combined cost of production, transportation and inventory.(2) Modify the model from (1) to account for the fact that the transportationcost between a factory and a center in a period is given bya fixed amount of $200 per month1 plus the cost of transportationper unit.(3) Modify the model from (2) to account for the fact that you can shipproducts from one factory to the other with a cost of $2 per unittransported.Problem 6: Energy provision (20 points)The state of Victoria primarily relies on brown coal sources for electricitygeneration. Here, we wish to consider a simple variant of the problem ofintroducing, locating and sizing renewable energy resources, namely windand 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 andR = {W ind, Solar, Hydro, Biomass} be the set of renewable resource types.At most two renewable resource types are to be installed at any candidatelocation l ∈ L. If some renewable resource type r ∈ R is installed at locationl ∈ L, we need to allocate at least SMINlr and at most SMAXlr units of theresource. A one-off cost, lr, is incurred when a farm with renewable resourcetype r ∈ R is setup at location l ∈ L; and it costs Clr for each unit of therenewable resource type installed at the location.Renewable resource locations and farm-size decisions are driven by demandfor electricity and the prospect/potential of a location for renewableenergy generation. For this simple problem variant, the renewable resourcesare not to be used to replace existing brown coal generation sources, but areinstead used to cope with demand fluctuations beyond the base electricitysupply generated by brown coal sources. Therefore, the “demand for electricity”is defined here as the amount of electricity to be supplied solely bythe renewable resources.Let the set of discrete, equally-sized, time periods be T. Each time periodmay, for example, represent a 30-minute interval and the length of the1That must be paid if there is transportation between the factory and the center.13planning 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 canproduce Plrt amount of electricity during time t ∈ T per unit of renewableresource 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 renewableenergy generation be “reasonable”. To achieve a “reasonable” variability, anydeviation from the total average generation for any given day is penalizedas follows: one unit of positive deviation is penalized at CP and one unit ofnegative deviation is penalized at CM. For instance, consider a three-periodexample with total renewable generations G1 , G2 and G3 on time periods1, 2, and 3, respectively. The average total generation is A =G1+G2+G3andsuppose G1 A. The total penalty for this exampleis given by CM(A − G1) + 0 + CP (G3 − A).Formulate a mixed-integer linear program (MILP) that will locate the renewableresources and determine their farm sizes such that the total farmestablishment costs plus the total variability penalty is minimized, and demandfor electricity is met.转自：http://www.6daixie.com/contents/18/5054.html