# InfoCoBuild

## Linear Programming and Extensions

Linear Programming and Extensions. Instructor: Prof. Prabha Sharma, Department of Mathematics and Statistics, IIT Kanpur. 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. Topics covered in this course include Simplex algorithm; Duality theory and its ramifications; Basic ideas of the ellipsoid algorithm and Karmarkar's algorithm; Special cases of LPP; and Dynamic programming and PERT/CPM algorithms. (from nptel.ac.in)

 Introduction to Linear Programming Problems

 Lecture 01 - Introduction to Linear Programming Problems Lecture 02 - Vector Space, Linear Independence and Dependence, Basis Lecture 03 - Moving from One Basic Feasible Solution to Another, Optimality Criteria Lecture 04 - Basic Feasible Solutions, Existence and Derivation Lecture 05 - Convex Sets, Dimension of a Polyhedron Faces, Example of a Polytope Lecture 06 - Direction of a Polyhedron, Correspondence between BFS and Extreme Points Lecture 07 - Representation Theorem, LPP Solution is a BFS Lecture 08 - Development of the Simplex Algorithm, Unboundedness, Simplex Tableau Lecture 09 - Simplex Tableau and Algorithm, Cycling, Bland's Anti-Cycling Rules Lecture 10 - Big-M Method, Graphical Solutions, Adjacent Extreme PTS and Adjacent BFS Lecture 11 - Progress of Simplex Algorithm on a Polytope, Bounded Variables LPP Lecture 12 - LPP Bounded Variable, Revised Simplex Algorithm, Duality Theory, Weak Duality Theorem Lecture 13 - Weak Duality Theorem, Economic Interpretation of Dual Variables, Fundamental Theorem of Duality Lecture 14 - Examples of Writing the Dual Complementary Slackness Theorem Lecture 15 - Complementary Slackness Conditions, Dual Simplex Algorithm Lecture 16 - Primal-Dual Algorithm Lecture 17 - Starting Dual Feasible Solutions, Shortest Path Problem Lecture 18 - Shortest Path Problem, Primal-Dual Method Lecture 19 - Shortest Path Problem-Complexity, Interpretation of Dual Variables, Changes in the Cost Vector Lecture 20 - Post-Optimality Analysis, Changes in B, Adding a New Constraint Lecture 21 - Parametric LPP-Right Hand Side Vector Lecture 22 - Parametric Cost Vector LPP Lecture 23 - Parametric Cost Vector LPP, Introduction to Min-Cost Flow Problem Lecture 24 - Min-Cost Flow Problem, Transportation Problem Lecture 25 - Transportation Problem Degeneracy, Cycling Lecture 26 - Sensitivity Analysis Lecture 27 - Sensitivity Analysis (cont.) Lecture 28 - Bounded Variable Transportation Problem, Min-Cost Flow Problem Lecture 29 - Min-Cost Flow Problem Lecture 30 - Starting Feasible Solution, Lexicographic Method for Preventing Cycling, Strongly Feasible Solution Lecture 31 - Shortest Path Problem, Shortest Path between Any Two Nodes, Detection of Negative Cycles Lecture 32 - Min-Cost-Flow Sensitivity Analysis, Shortest Path Problem Sensitivity Analysis Lecture 33 - Min-Cost Flow Changes in ARC Capacities, Max-Flow Problem Lecture 34 - Min-Cut Max-Flow Theorem, Labelling Algorithm Lecture 35 - Max-Flow-Critical Capacity of an ARC, Starting Solution for Min-Cost Flow Problem Lecture 36 - Improved Max-Flow Algorithm Lecture 37 - Critical Path Method (CPM) Lecture 38 - Programme Evaluation and Review Technique (PERT) Lecture 39 - Simplex Algorithm is not Polynomial Time - An example Lecture 40 - Interior Point Methods

 References Linear Programming and Extensions Instructor: Prof. Prabha Sharma, Department of Mathematics and Statistics, IIT Kanpur. The objective of this course is to introduce those real life problems which can be formulated as Linear Programming Problems (LPP).