Linear programming and Extensions

Overview

The objective of this course is to introduce those real life problems which can be formulated as Linear Programming Problems ( LPP ). The course will be taught as a first course in optimization, hence all the concepts will be properly motivated and explained with examples. Following will be discussed in particular: Linear models such as; Product mix problem, Nutrition Problem,a BlendingProblem, Formulation of these problems as Linear Programming problems (LLP). Axioms of linearity, General form of LPP, Slack and Surplus Variables. Standard Form of LPP. Basic concepts of rank of a matrix, Solution of a system of linear equations, Examples. Basic feasible solution (bf s), degenerate and non-degenrate, examples of basic solutions which are not feasible. Upper bound on the number of bf s. Upper bound on the absolute value of the basic variables. Existence of bf s, Moving from one bfs to another and improving the value of the objective function. Optimality Criteria. Optimal solution is a bfs. Simplex algorithm through a simple example. Simplex algorithm - geometrically interpretation. Definition of an affine space, Polyhedron P, faces of a polyhedron facets, edges and vertices. Representation of a polyhedron in terms of extreme points and extreme rays. A basic feasible solution is an extreme point of the corresponding Polyhedron. More about degeneracy. Supporting hyperplane of a polyhedron. Characterisation of an optimal solution in terms of supporting hyperplane. Graphical illustrations. Simplex Algorithm- Tableau format. Simplex algorithm Starting feasible solution, Artificial variables, Phase I and Phase II methods. Bounded variables case; modification of the Simplex algorithm. Revised Simplex algorithm. Define the Dual problem and its various forms. Fundamental Theorem of Duality. Farkas theorem. Complementary Slackness theorem. Dual Simplex algorithm; Motivation , theory and a numerical example. Primal Dual algorithm: Motivation , theory and a numerical example. Sensitivity Analysis of the objective function coefficient, right hand side components and elements of the matrix A. Adding of constraints and activities. A comprehensive numerical example. Parametric analysis. Min-cost flow problem- formulation and derivation of special cases such as Transportation problem, Assignment problem, Max-flow problem and the shortest path problem. Integer bfs property of Transportation problem. Simplified Simplex algorithm for Transportation problem. Sensitivity Analysis and Bounded Variable case. Formulation of Shortest Path Problem, Dijkstras algorithm. More general shortest Path algorithms, Sensitivity analysis. Applications of Max-flow problem. Algorithms and Sensitivity Analysis. Network Simplex Algorithm for Min cost flow problem.(2) Project Planning Control with PERT / CPM, linear programming formulations. (3) Dynamic Programming: Principle of Optimality with proof. Discrete and continuous problems.(2) Backward and forward formulations. Probabilistic cases.(2) Game theory. Two-person Zero-sum game. Pure and mixed strategies with examples. Saddlepoint and graphical solutions. Linear programming iterative solution method. Computational complexity of Simplex algorithm. To show through an example that the Simplex algorithm can go through all the extreme points before reaching the optimal extreme point solution. Ellipsoid algorithm- basic concepts and its applications. Basic idea behind Karmarkars algorithm and its applications.