Learn · NPTEL

Course11110402740 lectures

Linear programming and Extensions

Prof. Prabha Sharma · IIT Kanpur

Start with lecture 1 At NPTEL

Lectures

Linear programming and Extensions

  1. Lecture_01_Introduction to Linear Programming Problems. Video
  2. Lecture_02_ Vector space, Linear independence and dependence, basis. Video
  3. Lec_03_Moving from one basic feasible solution to another, optimality criteria. Video
  4. Lecture_04_Basic feasible solutions, existence & derivation. Video
  5. Lecture_5_Convex sets, dimension of a polyhedron, Faces, Example of a polytope. Video
  6. Lecture_6_Direction of a polyhedron, correspondence between bfs and extreme points. Video
  7. Lecture_7_Representation theorem, LPP solution is a bfs, Assignment 1. Video
  8. Lecture_08_Development of the Simplex Algorithm, Unboundedness, Simplex Tableau. Video
  9. Lecture_9_ Simplex Tableau & algorithm ,Cycling, Bland’s anti-cycling rules, Phase I & Phase II. Video
  10. Lecture_10_ Big-M method,Graphical solutions, adjacent extreme pts and adjacent bfs. Video
  11. Lecture_11_Assignment 2, progress of Simplex algorithm on a polytope, bounded variable LPP. Video
  12. Lecture_12_LPP Bounded variable, Revised Simplex algorithm, Duality theory, weak duality theorem. Video
  13. Lecture_13_Weak duality theorem, economic interpretation of dual variables, Fundamental theorem of duality. Video
  14. Lecture_14_Examples of writing the dual, complementary slackness theorem. Video
  15. Lecture_15_Complementary slackness conditions, Dual Simplex algorithm, Assignment 3. Video
  16. Lecture_16_Primal-dual algorithm. Video
  17. Lecture_17_Problem in lecture 16, starting dual feasible solution, Shortest Path Problem. Video
  18. Lecture_18_Shortest Path Problem, Primal-dual method, example. Video
  19. Lecture_19_Shortest Path Problem-complexity, interpretation of dual variables, post-optimality analysis-changes in the cost vector. Video
  20. Lecture_20_ Assignment 4, postoptimality analysis, changes in b, adding a new constraint, changes in {aij} , Parametric analysis. Video
  21. Lecture_21_Parametric LPP-Right hand side vector. Video
  22. Lecture_22_Parametric cost vector LPP. Video
  23. Lecture_23_Parametric cost vector LPP, Introduction to Min-cost flow problem. Video
  24. Lecture_24_Mini-cost flow problem-Transportation problem. Video
  25. Lecture_25_Transportation problem degeneracy, cycling Video
  26. Lecture_26_ Sensitivity analysis. Video
  27. Lecture_27_ Sensitivity analysis. Video
  28. Lecture_28_Bounded variable transportation problem, min-cost flow problem. Video
  29. Lecture_29_Min-cost flow problem Video
  30. Lecture_30_Starting feasible solution, Lexicographic method for preventing cycling ,strongly feasible solution Video
  31. Lecture_31_Assignment 6, Shortest path problem, Shortest Path between any two nodes,Detection of negative cycles. Video
  32. Lecture_32_ Min-cost-flow Sensitivity analysis Shortest path problem sensitivity analysis. Video
  33. Lecture_33_Min-cost flow changes in arc capacities , Max-flow problem, assignment 7 Video
  34. Lecture_34_Problem 3 (assignment 7), Min-cut Max-flow theorem, Labelling algorithm. Video
  35. Lecture_35_Max-flow - Critical capacity of an arc, starting solution for min-cost flow problem. Video
  36. Lecture_36_Improved Max-flow algorithm. Video
  37. Lecture_37_Critical Path Method (CPM). Video
  38. Lecture_38_Programme Evaluation and Review Technique (PERT). Video
  39. Lecture_39_ Simplex Algorithm is not polynomial time- An example. Video
  40. Lecture_40_Interior Point Methods . Video

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Kanpur
Department
Mathematics
Teacher
Prof. Prabha Sharma
Level
Undergraduate
Language
English
Subjects
Mathematics
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed