Linear programming and Extensions

Linear programming and Extensions
Linear programming and Extensions by Prof. Prabha Sharma, Department of Mathematics and Statistics, IIT Kanpur For more details on NPTEL visit http://nptel.iitm.ac.in
Mod-01 Lec-01 Introduction to Linear Programming Problems.
Mod-01 Lec-02 Vector space, Linear independence and dependence, basis.
Mod-01 Lec-03 Moving from one basic feasible solution to another, optimality criteria.
Mod-01 Lec-04 Basic feasible solutions, existence & derivation.
Mod-01 Lec-05 Convex sets, dimension of a polyhedron, Faces, Example of a polytope.
Mod-01 Lec-06 Direction of a polyhedron, correspondence between bfs and extreme points.
Mod-01 Lec-07 Representation theorem, LPP solution is a bfs, Assignment 1
Mod-01 Lec-08 Development of the Simplex Algorithm, Unboundedness, Simplex Tableau.
Mod-01 Lec-09 Simplex Tableau & algorithm ,Cycling, Bland's anti-cycling rules, Phase I & Phase II.
Mod-01 Lec-10 Big-M method,Graphical solutions, adjacent extreme pts and adjacent bfs
Mod-01 Lec-11 Assignment 2, progress of Simplex algorithm on a polytope, bounded variable LPP
Mod-01 Lec-12 LPP Bounded variable, Revised Simplex algorithm, Duality theory, weak duality theorem.
Mod-01 Lec-13 Weak duality theorem, economic interpretation of dual variables
Mod-01 Lec-14 Examples of writing the dual, complementary slackness theorem.
Mod-01 Lec-15 Complementary slackness conditions, Dual Simplex algorithm, Assignment 3.
Mod-01 Lec-16 Primal-dual algorithm.
Mod-01 Lec-17 Problem in lecture 16, starting dual feasible solution, Shortest Path Problem.
Mod-01 Lec-18 Shortest Path Problem, Primal-dual method, example.
Mod-01 Lec-19 Shortest Path Problem-complexity, interpretation of dual variables
Mod-01 Lec-20 Assignment 4, postoptimality analysis, changes in b, adding a new constraint
Mod-01 Lec-21 Parametric LPP-Right hand side vector.
Mod-01 Lec-22 Parametric cost vector LPP
Mod-01 Lec-23 Parametric cost vector LPP, Introduction to Min-cost flow problem.
Mod-01 Lec-24 Mini-cost flow problem-Transportation problem.
Mod-01 Lec-25 Transportation problem degeneracy, cycling
Mod-01 Lec-26 Sensitivity analysis
Mod-01 Lec-27 Sensitivity analysis.
Mod-01 Lec-28 Bounded variable transportation problem, min-cost flow problem.
Mod-01 Lec-29 Min-cost flow problem
Mod-01 Lec-30 Starting feasible solution, Lexicographic method for preventing cycling
Mod-01 Lec-31 Assignment 6, Shortest path problem, Shortest Path between any two nodes
Mod-01 Lec-32 Min-cost-flow Sensitivity analysis Shortest path problem sensitivity analysis.
Mod-01 Lec-33 Min-cost flow changes in arc capacities , Max-flow problem, assignment 7
Mod-01 Lec-34 Problem 3 (assignment 7), Min-cut Max-flow theorem, Labelling algorithm.
Mod-01 Lec-35 Max-flow - Critical capacity of an arc, starting solution for min-cost flow problem.
Mod-01 Lec-36 Improved Max-flow algorithm.
Mod-01 Lec-37 Critical Path Method (CPM)
Mod-01 Lec-38 Programme Evaluation and Review Technique (PERT).
Mod-01 Lec-39 Simplex Algorithm is not polynomial time- An example.