# Linear programming and Extensions

- Institution: IIT Kanpur
- Department: Mathematics
- Teacher: Prof. Prabha Sharma
- Level: Undergraduate
- Language: English
- Subjects: Mathematics
- Source: [NPTEL](https://nptel.ac.in/courses/111104027)
- Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.)
- Syllabus: [at the source](https://nptel.ac.in/courses/111104027)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

## Lectures

1. [Lecture_01_Introduction to Linear Programming Problems.](https://invisiblenetwork.ai/learn/nptel/111104027/f18c62d05ea7) (Video)
2. [Lecture_02_ Vector space, Linear independence and dependence, basis.](https://invisiblenetwork.ai/learn/nptel/111104027/75fc82f8e907) (Video)
3. [Lec_03_Moving from one basic feasible solution to another, optimality criteria.](https://invisiblenetwork.ai/learn/nptel/111104027/8b81e3622b05) (Video)
4. [Lecture_04_Basic feasible solutions, existence & derivation.](https://invisiblenetwork.ai/learn/nptel/111104027/509d4c27c7bc) (Video)
5. [Lecture_5_Convex sets, dimension of a polyhedron, Faces, Example of a polytope.](https://invisiblenetwork.ai/learn/nptel/111104027/e6c4c6362a8e) (Video)
6. [Lecture_6_Direction of a polyhedron, correspondence between bfs and extreme points.](https://invisiblenetwork.ai/learn/nptel/111104027/26ac5d9f0518) (Video)
7. [Lecture_7_Representation theorem, LPP solution is a bfs, Assignment 1.](https://invisiblenetwork.ai/learn/nptel/111104027/9c7bab70e7c1) (Video)
8. [Lecture_08_Development of the Simplex Algorithm, Unboundedness, Simplex Tableau.](https://invisiblenetwork.ai/learn/nptel/111104027/25da440bdb1e) (Video)
9. [Lecture_9_ Simplex Tableau & algorithm ,Cycling, Bland’s anti-cycling rules, Phase I & Phase II.](https://invisiblenetwork.ai/learn/nptel/111104027/f46ce48ef46b) (Video)
10. [Lecture_10_ Big-M method,Graphical solutions, adjacent extreme pts and adjacent bfs.](https://invisiblenetwork.ai/learn/nptel/111104027/ee15e0447224) (Video)
11. [Lecture_11_Assignment 2, progress of Simplex algorithm on a polytope, bounded variable LPP.](https://invisiblenetwork.ai/learn/nptel/111104027/9e5e1b5ea42a) (Video)
12. [Lecture_12_LPP Bounded variable, Revised Simplex algorithm, Duality theory, weak duality theorem.](https://invisiblenetwork.ai/learn/nptel/111104027/b5d19e111d2b) (Video)
13. [Lecture_13_Weak duality theorem, economic interpretation of dual variables, Fundamental theorem of duality.](https://invisiblenetwork.ai/learn/nptel/111104027/d34f78a82233) (Video)
14. [Lecture_14_Examples of writing the dual, complementary slackness theorem.](https://invisiblenetwork.ai/learn/nptel/111104027/521769f2acfd) (Video)
15. [Lecture_15_Complementary slackness conditions, Dual Simplex algorithm, Assignment 3.](https://invisiblenetwork.ai/learn/nptel/111104027/98d5c3c2cb84) (Video)
16. [Lecture_16_Primal-dual algorithm.](https://invisiblenetwork.ai/learn/nptel/111104027/3266022879a7) (Video)
17. [Lecture_17_Problem in lecture 16, starting dual feasible solution, Shortest Path Problem.](https://invisiblenetwork.ai/learn/nptel/111104027/c11c5507714e) (Video)
18. [Lecture_18_Shortest Path Problem, Primal-dual method, example.](https://invisiblenetwork.ai/learn/nptel/111104027/7399182198ea) (Video)
19. [Lecture_19_Shortest Path Problem-complexity, interpretation of dual variables, post-optimality analysis-changes in the cost vector.](https://invisiblenetwork.ai/learn/nptel/111104027/f02144b63a5e) (Video)
20. [Lecture_20_ Assignment 4, postoptimality analysis, changes in b, adding a new constraint, changes in {aij} , Parametric analysis.](https://invisiblenetwork.ai/learn/nptel/111104027/1c26e5699d11) (Video)
21. [Lecture_21_Parametric LPP-Right hand side vector.](https://invisiblenetwork.ai/learn/nptel/111104027/9467e8862b89) (Video)
22. [Lecture_22_Parametric cost vector LPP.](https://invisiblenetwork.ai/learn/nptel/111104027/57d6169ed12d) (Video)
23. [Lecture_23_Parametric cost vector LPP, Introduction to Min-cost flow problem.](https://invisiblenetwork.ai/learn/nptel/111104027/ec133866d920) (Video)
24. [Lecture_24_Mini-cost flow problem-Transportation problem.](https://invisiblenetwork.ai/learn/nptel/111104027/d3b386df1f35) (Video)
25. [Lecture_25_Transportation problem degeneracy, cycling](https://invisiblenetwork.ai/learn/nptel/111104027/140833e7b1ce) (Video)
26. [Lecture_26_ Sensitivity analysis.](https://invisiblenetwork.ai/learn/nptel/111104027/63b9810390cf) (Video)
27. [Lecture_27_ Sensitivity analysis.](https://invisiblenetwork.ai/learn/nptel/111104027/61a263a03cca) (Video)
28. [Lecture_28_Bounded variable transportation problem, min-cost flow problem.](https://invisiblenetwork.ai/learn/nptel/111104027/98bd9861e29b) (Video)
29. [Lecture_29_Min-cost flow problem](https://invisiblenetwork.ai/learn/nptel/111104027/e7ae7f690f9b) (Video)
30. [Lecture_30_Starting feasible solution, Lexicographic method for preventing cycling ,strongly feasible solution](https://invisiblenetwork.ai/learn/nptel/111104027/a87082438271) (Video)
31. [Lecture_31_Assignment 6, Shortest path problem, Shortest Path between any two nodes,Detection of negative cycles.](https://invisiblenetwork.ai/learn/nptel/111104027/eff49ac96851) (Video)
32. [Lecture_32_ Min-cost-flow Sensitivity analysis Shortest path problem sensitivity analysis.](https://invisiblenetwork.ai/learn/nptel/111104027/812fe7200241) (Video)
33. [Lecture_33_Min-cost flow changes in arc capacities , Max-flow problem, assignment 7](https://invisiblenetwork.ai/learn/nptel/111104027/df7aa52b4993) (Video)
34. [Lecture_34_Problem 3 (assignment 7), Min-cut Max-flow theorem, Labelling algorithm.](https://invisiblenetwork.ai/learn/nptel/111104027/47b0d2f74044) (Video)
35. [Lecture_35_Max-flow - Critical capacity of an arc, starting solution for min-cost flow problem.](https://invisiblenetwork.ai/learn/nptel/111104027/f651d3cea4b2) (Video)
36. [Lecture_36_Improved Max-flow algorithm.](https://invisiblenetwork.ai/learn/nptel/111104027/d77754b7e3d0) (Video)
37. [Lecture_37_Critical Path Method (CPM).](https://invisiblenetwork.ai/learn/nptel/111104027/7dc13f20984a) (Video)
38. [Lecture_38_Programme Evaluation and Review Technique (PERT).](https://invisiblenetwork.ai/learn/nptel/111104027/4f2409637ca1) (Video)
39. [Lecture_39_ Simplex Algorithm is not polynomial time- An example.](https://invisiblenetwork.ai/learn/nptel/111104027/a7de410a6a09) (Video)
40. [Lecture_40_Interior Point Methods .](https://invisiblenetwork.ai/learn/nptel/111104027/eb5dd47e0919) (Video)