IIT Kanpur Course , Prof. Prabha Sharma

**434**students enrolled

IIT Kanpur Course , Prof. Prabha Sharma

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. Farkas 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, Dijkstras 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 Karmarkars algorithm and its applications.

Up Next

You can skip ad in

SKIP AD >

Advertisement

- 2x
- 1.5x
- 1x
- 0.5x
- 0.25x

EMBED LINK

COPY

DIRECT LINK

COPY

PRIVATE CONTENT

OK

Enter password to view

Please enter valid password!

- Play Pause
- Mute UnMute
- Fullscreen Normal
- @Your Company Title

0:00

3.6 (30 Ratings)

Linear programming and Extensions by Prof. Prabha Sharma, Department of Mathematics and Statistics, IIT Kanpur For more details on NPTEL visit httpnptel.iitm.ac.in

47%

13%

13%

10%

17%

- 1.Introduction to Linear Programming Problems.
- 2.Vector space, Linear independence and dependence, basis.
- 3.Moving from one basic feasible solution to another, optimality criteria.
- 4.Basic feasible solutions, existence & derivation.
- 5.Convex sets, dimension of a polyhedron, Faces, Example of a polytope.
- 6.Direction of a polyhedron, correspondence between bfs and extreme points.
- 7.Representation theorem, LPP solution is a bfs, Assignment 1
- 8.Development of the Simplex Algorithm, Unboundedness, Simplex Tableau.
- 9.Simplex Tableau & algorithm ,Cycling, Blands anti-cycling rules, Phase I & Phase II.
- 10.Big-M method,Graphical solutions, adjacent extreme pts and adjacent bfs
- 11.Assignment 2, progress of Simplex algorithm on a polytope, bounded variable LPP
- 12.LPP Bounded variable, Revised Simplex algorithm, Duality theory, weak duality theorem.
- 13.Weak duality theorem, economic interpretation of dual variables
- 14.Examples of writing the dual, complementary slackness theorem.
- 15.Complementary slackness conditions, Dual Simplex algorithm, Assignment 3.
- 16.Primal-dual algorithm.
- 17.Problem in lecture 16, starting dual feasible solution, Shortest Path Problem.
- 18.Shortest Path Problem, Primal-dual method, example.
- 19.Shortest Path Problem-complexity, interpretation of dual variables
- 20.Assignment 4, postoptimality analysis, changes in b, adding a new constraint
- 21.Parametric LPP-Right hand side vector.
- 22.Parametric cost vector LPP
- 23.Parametric cost vector LPP, Introduction to Min-cost flow problem.
- 24.Mini-cost flow problem-Transportation problem.
- 25.Transportation problem degeneracy, cycling
- 26.Sensitivity analysis
- 27.Sensitivity analysis I
- 28.Bounded variable transportation problem, min-cost flow problem.
- 29.Min-cost flow problem
- 30.Starting feasible solution, Lexicographic method for preventing cycling
- 31.Assignment 6, Shortest path problem, Shortest Path between any two nodes
- 32.Min-cost-flow Sensitivity analysis Shortest path problem sensitivity analysis.
- 33.Min-cost flow changes in arc capacities , Max-flow problem, assignment 7
- 34.Problem 3 (assignment 7), Min-cut Max-flow theorem, Labelling algorithm.
- 35.Max-flow - Critical capacity of an arc, starting solution for min-cost flow problem.
- 36.Improved Max-flow algorithm.
- 37.Critical Path Method (CPM)
- 38.Programme Evaluation and Review Technique (PERT).
- 39.Simplex Algorithm is not polynomial time- An example.
- 40.Interior Point Methods

- FreeVideoLectures aim to help millions of students across the world acquire knowledge, gain good grades, get jobs, assist in getting promotions through quality learning material.

- You can write to us
- help@freevideolectures.com

2018 FreeVideoLectures. All rights reserved. FreeVideoLectures only promotes free course material from different sources, we are not endrosed by any university.