Mod-01 Lec-19 Shortest Path Problem-complexity, interpretation of dual variables

Course Lectures

• Mod-01 Lec-01 Introduction to Linear Programming Problems.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-02 Vector space, Linear independence and dependence, basis.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-03 Moving from one basic feasible solution to another, optimality criteria.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-04 Basic feasible solutions, existence & derivation.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-05 Convex sets, dimension of a polyhedron, Faces, Example of a polytope.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-06 Direction of a polyhedron, correspondence between bfs and extreme points.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-07 Representation theorem, LPP solution is a bfs, Assignment 1

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-08 Development of the Simplex Algorithm, Unboundedness, Simplex Tableau.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-09 Simplex Tableau & algorithm ,Cycling, Bland's anti-cycling rules, Phase I & Phase II.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-10 Big-M method,Graphical solutions, adjacent extreme pts and adjacent bfs

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-11 Assignment 2, progress of Simplex algorithm on a polytope, bounded variable LPP

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-12 LPP Bounded variable, Revised Simplex algorithm, Duality theory, weak duality theorem.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-13 Weak duality theorem, economic interpretation of dual variables

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-14 Examples of writing the dual, complementary slackness theorem.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-15 Complementary slackness conditions, Dual Simplex algorithm, Assignment 3.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-16 Primal-dual algorithm.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-17 Problem in lecture 16, starting dual feasible solution, Shortest Path Problem.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-18 Shortest Path Problem, Primal-dual method, example.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-19 Shortest Path Problem-complexity, interpretation of dual variables

  Prof. Prabha Sharma

  Playing
• Mod-01 Lec-20 Assignment 4, postoptimality analysis, changes in b, adding a new constraint

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-21 Parametric LPP-Right hand side vector.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-22 Parametric cost vector LPP

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-23 Parametric cost vector LPP, Introduction to Min-cost flow problem.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-24 Mini-cost flow problem-Transportation problem.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-25 Transportation problem degeneracy, cycling

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-26 Sensitivity analysis

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-27 Sensitivity analysis.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-28 Bounded variable transportation problem, min-cost flow problem.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-29 Min-cost flow problem

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-30 Starting feasible solution, Lexicographic method for preventing cycling

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-31 Assignment 6, Shortest path problem, Shortest Path between any two nodes

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-32 Min-cost-flow Sensitivity analysis Shortest path problem sensitivity analysis.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-33 Min-cost flow changes in arc capacities , Max-flow problem, assignment 7

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-34 Problem 3 (assignment 7), Min-cut Max-flow theorem, Labelling algorithm.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-35 Max-flow - Critical capacity of an arc, starting solution for min-cost flow problem.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-36 Improved Max-flow algorithm.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-37 Critical Path Method (CPM)

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-38 Programme Evaluation and Review Technique (PERT).

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-39 Simplex Algorithm is not polynomial time- An example.

  Prof. Prabha Sharma

  Play
• Mod-01 Lec-40 Interior Point Methods

  Prof. Prabha Sharma

  Play