Guia docente 2020_21 Facultad de CC. Económicas y Empresariales

Contents

Topic	Sub-topic
1. The shortest path problem.	a) Definition and graphic representation. b) Labelling algorithms: Dijkstra and Floyd. c) Applications.
2. The maximum flow problem.	a) Definition and graphic representation. Dual problem: minimum capacity cut. b) Ford-Fulkerson algorithm c) Applications.
3. The transportation model.	a) Definition and graphic representation. b) Methods to obtain an initial basic feasible solution. The transportation simplex method. c) The dual problem. Sensitivity analysis. d) Applications. Particular cases: the transbord problem and assignment problem.
4. The minimum cost spanning tree problem.	a) Description of the problem. Algorithms to compute a minimum costs spanning tree: Prim, Kruskal, Boruvka. b) Allocation rules to divide the cost of the optimal tree between the nodes. Rules based in the algorithms of Prim and Kruskal. Rules based in cooperative games with transferable utility.
5. Project management, the PERT method.	a) Description of the problem. b) The critical path. Calculation of the calendar of the project. c) An example.