The course aims to introduce the students to the algorithms for the solution of two of the most applied problems; The Linear and Network problems, as also it's applications in Informatics and in the scientific method for decision making in complicated economical and managerial decisions.
Introduction - Basic concepts. Historical review, Definitions and concepts of Linear and Network optimization, Applications of the linear problem formulation, Description of the linear problem, Linear problem formulations (normal, standard, general), Transformation between different formulations, Storage schemes of graphs and trees, Node - node adjacency matrix, Node - arc adjacency matrix, Linked lists.Network flow problems and transformations. Minimum Cost Network Flow Problems, (MCNF), Balanced and not-balanced MCNF, Special MCNF cases, Network flow problems' transformations, MCNF optimality conditions.Geometrical solution of the linear problem. Improving directions, Geometrical solution in the space of variables, Invert matrix properties, Methods of invert matrix calculation for linear optimization problems, Eta-matrices usage.Simplex type algorithms. General description of simplex type algorithms, Methodology of simplex type algorithms, The revised primal simplex algorithm, simplex algorithm's justification, Analysis of different pivoting rules, Solution of general linear problems, (two phase algorithm and big M algorithm), Implementation of simplex type algorithms.Duality theory. Relations between primal and dual linear problem, Transforming primal to dual, Weak duality theorem, Strong duality theorem, Theorem of complementarity slackness, The revised dual simplex algorithm.Minimum spanning tree algorithms. Kruscal algorithm, Prim algorithm.Sensitivity analysis. Classical sensitivity analysis, Changes in the cost variables, Changes in the right hand side.