Prabha Sharma: Linear programming and Extensions (IIT Kanpur)

# playlist of the 40 videos (click the up-left corner of the video)

source: nptelhrd    2012年1月29日
Mathematics - 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

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