Course

Mathematics - Linear programming and Extensions

Indian Institute of Technology Kanpur

The objective of this course is to introduce those real life problems which can be formulated as Linear Programming Problems ( LPP ). The course will be taught as a first course in optimization, hence all the concepts will be properly motivated and explained with examples.

Following will be discussed in particular:

Simplex Algorithm
Duality theory and its ramifications
Basic ideas of the Ellipsoid algorithm and Karmarkar’s algorithm
Special cases of LPP such as Transportation, Assignment and Network – flow
Dynamic programming and PERT/CPM algorithms

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

Play
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