Media Storage Type : 32 GB USB Stick
NPTEL Subject Matter Expert : Prof. Prabha Sharma
NPTEL Co-ordinating Institute : IIT Kanpur
NPTEL Lecture Count : 40
NPTEL Course Size : 17 GB
NPTEL PDF Text Transcription : Available and Included
NPTEL Subtitle Transcription : Available and Included (SRT)
Lecture Titles:
Lecture 1 - Introduction to Linear Programming Problems
Lecture 2 - Vector space, Linear independence and dependence, basis
Lecture 3 - Moving from one basic feasible solution to another, optimality criteria
Lecture 4 - Basic feasible solutions, existence & derivation
Lecture 5 - Convex sets, dimension of a polyhedron, Faces, Example of a polytope
Lecture 6 - Direction of a polyhedron, correspondence between bfs and extreme points
Lecture 7 - Representation theorem, LPP solution is a bfs, Assignment 1
Lecture 8 - Development of the Simplex Algorithm, Unboundedness, Simplex Tableau
Lecture 9 - Simplex Tableau & algorithm ,Cycling, Bland’s anti-cycling rules, Phase I & Phase II
Lecture 10 - Big-M method,Graphical solutions, adjacent extreme pts and adjacent bfs
Lecture 11 - Assignment 2, progress of Simplex algorithm on a polytope, bounded variable 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, Assignment 3
Lecture 16 - Primal-dual algorithm
Lecture 17 - Problem in lecture 16, starting dual feasible solution, Shortest Path Problem
Lecture 18 - Shortest Path Problem, Primal-dual method, example
Lecture 19 - Shortest Path Problem-complexity, interpretation of dual variables, post-optimality analysis-changes in the cost vector
Lecture 20 - Assignment 4, postoptimality analysis, changes in b, adding a new constraint, changes in {aij} , Parametric analysis
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 - Mini-cost flow problem-Transportation problem
Lecture 25 - Transportation problem degeneracy, cycling
Lecture 26 - Sensitivity analysis
Lecture 27 - Sensitivity analysis
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 - Assignment 6, 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, assignment 7
Lecture 34 - Problem 3 (assignment 7), 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