Subscribe to feed
Lights off 
SEE: Guide to Download NPTEL Video Lecture
Lecture Details :
Linear programming and Extensions by Prof. Prabha Sharma, Department of Mathematics and Statistics, IIT Kanpur For more details on NPTEL visit http://nptel.iitm.ac.in
Course Description :
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:
Linear models such as; Product mix problem, Nutrition Problem,a BlendingProblem, Formulation of these problems as Linear Programming problems (LLP). Axioms of linearity, General form of LPP, Slack and Surplus Variables. Standard Form of LPP.
Basic concepts of rank of a matrix, Solution of a system of linear equations, Examples. Basic feasible solution (bf s), degenerate and non-degenrate, examples of basic solutions which are not feasible. Upper bound on the number of bf s. Upper bound on the absolute value of the basic variables.
Existence of bf s, Moving from one bfs to another and improving the value of the objective function. Optimality Criteria. Optimal solution is a bfs. Simplex algorithm through a simple example.
Simplex algorithm - geometrically interpretation. Definition of an affine space, Polyhedron P, faces of a polyhedron – facets, edges and vertices. Representation of a polyhedron in terms of extreme points and extreme rays.
A basic feasible solution is an extreme point of the corresponding Polyhedron. More about degeneracy.
Supporting hyperplane of a polyhedron. Characterisation of an optimal solution in terms of supporting hyperplane. Graphical illustrations.
Simplex Algorithm- Tableau format.
Simplex algorithm – Starting feasible solution, Artificial variables, Phase I and Phase II methods.
Bounded variables case; modification of the Simplex algorithm.
Revised Simplex algorithm. Define the Dual problem and its various forms.
Fundamental Theorem of Duality. Farka’s theorem. Complementary Slackness theorem.
Dual Simplex algorithm; Motivation , theory and a numerical example.
Primal Dual algorithm: Motivation , theory and a numerical example.
Sensitivity Analysis of the objective function coefficient, right hand side components and elements of the matrix A.
Adding of constraints and activities. A comprehensive numerical example.
Parametric analysis.
Min-cost flow problem- formulation and derivation of special cases such as Transportation problem,
Assignment problem, Max-flow problem and the shortest path problem.
Integer bfs property of Transportation problem.
Simplified Simplex algorithm for Transportation problem.
Sensitivity Analysis and Bounded Variable case.
Formulation of Shortest Path Problem, Dijkstra’s algorithm.
More general shortest Path algorithms, Sensitivity analysis.
Applications of Max-flow problem.
Algorithms and Sensitivity Analysis.
Network Simplex Algorithm for Min – cost flow problem.(2)
Project Planning Control with PERT / CPM, linear programming formulations. (3)
Dynamic Programming: Principle of Optimality with proof. Discrete and continuous problems.(2)
Backward and forward formulations. Probabilistic cases.(2)
Game theory. Two-person Zero-sum game. Pure and mixed strategies with examples.
Saddlepoint and graphical solutions.
Linear programming iterative solution method.
Computational complexity of Simplex algorithm. To show through an example that the Simplex algorithm can go through all the extreme points before reaching the optimal extreme point solution.
Ellipsoid algorithm- basic concepts and its applications.
Basic idea behind Karmarkar’s algorithm and its applications.
Other Resources :
Syllabus | Citation |
Other Mathematics Courses
- differential equations III by Other
- Trigonometry by Khan Academy
- California Standards Test: Geometry by Khan Academy
- Applied Multivariate Analysis by IIT Kanpur
- Single Variable Calculus by MIT
- Algebra by Khan Academy
- Introduction to Geometry by Other
- Math 60 - Introductory Algebra-1st Term by Portland Community College
- Calculus of Variations and Integral Equations by IIT Kanpur
- Differential Equations II by Khan Academy
» check out the complete list of Mathematics Video lectures
Mathematics Lecture Notes
- Linear Functional Analysis by Macquarie University
- Multivariable and Vector Analysis by Macquarie University
- Probabilistic Thinking by Princeton University
- Math 735: Stochastic Differential Equations by University of Wisconsin
- Math 231: Partial Differential Equations by UC San Diego
- Math 100: UBC Calculus by University of British Columbia
- First Year Calculus by Macquarie University
- MATA26Y: Calculus by University of Toronto
- Topology Education by University College Galway
- Linear Algebra by Macquarie University