Linear programming and Extensions 7ET023E38S

URI	`m2://res/7ET023E38S`
Kind	course
Creators	Prabha Sharma (instructor)
Date	2012-01-29
Scope	in
Ids	course 05pjsgx75:111104027

Expressions

e1: edition

Language	en
Date	2012-01-29

m1: page, IIT Kanpur (record). nptel 111104027
m2: page, 2012-01-29 (record). nptel 111104027

Contents

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

Catalogue records

nptel: 111104027 (manifestation)
nptel_video: 111104027 (manifestation)