Linear programming and Extensions

0( 0 REVIEWS )

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.

Course Curriculum

Introduction to Linear Programming Problems. Details 49:17
Vector space, Linear independence and dependence, basis. Details 58:32
Moving from one basic feasible solution to another, optimality criteria. Details 1:2:38
Basic feasible solutions, existence & derivation. Details 1:46
Convex sets, dimension of a polyhedron, Faces, Example of a polytope. Details 1:30
Direction of a polyhedron, correspondence between bfs and extreme points. Details 48:9
Representation theorem, LPP solution is a bfs, Assignment 1 Details 59:32
Development of the Simplex Algorithm, Unboundedness, Simplex Tableau. Details 56:52
Simplex Tableau & algorithm ,Cycling, Bland’s anti-cycling rules, Phase I & Phase II. Details 1:1:7
Big-M method,Graphical solutions, adjacent extreme pts and adjacent bfs Details 59:1
Assignment 2, progress of Simplex algorithm on a polytope, bounded variable LPP Details 1:2:26
LPP Bounded variable, Revised Simplex algorithm, Duality theory, weak duality theorem. Details 53:43
Weak duality theorem, economic interpretation of dual variables Details 57:17
Examples of writing the dual, complementary slackness theorem. Details 53:56
Complementary slackness conditions, Dual Simplex algorithm, Assignment 3. Details 50:38
Primal-dual algorithm. Details 59:46
Problem in lecture 16, starting dual feasible solution, Shortest Path Problem. Details 56:30
Shortest Path Problem, Primal-dual method, example. Details 57:38
Shortest Path Problem-complexity, interpretation of dual variables Details 51:56
Assignment 4, postoptimality analysis, changes in b, adding a new constraint Details 56:11
Parametric LPP-Right hand side vector. Details 52:30
Parametric cost vector LPP Details 59:8
Parametric cost vector LPP, Introduction to Min-cost flow problem. Details 47:52
Mini-cost flow problem-Transportation problem. Details 56:28
Transportation problem degeneracy, cycling Details 1:6:19
Sensitivity analysis Details 1:21
Sensitivity analysis I Details 54:53
Bounded variable transportation problem, min-cost flow problem. Details 58:55
Min-cost flow problem Details 58:19
Starting feasible solution, Lexicographic method for preventing cycling Details 59:23
Assignment 6, Shortest path problem, Shortest Path between any two nodes Details 55:4
Min-cost-flow Sensitivity analysis Shortest path problem sensitivity analysis. Details 49:41
Min-cost flow changes in arc capacities , Max-flow problem, assignment 7 Details 55:43
Problem 3 (assignment 7), Min-cut Max-flow theorem, Labelling algorithm. Details 1:1:26
Max-flow – Critical capacity of an arc, starting solution for min-cost flow problem. Details 1:4:6
Improved Max-flow algorithm. Details 56:54
Critical Path Method (CPM) Details 55:40
Programme Evaluation and Review Technique (PERT). Details 45:42
Simplex Algorithm is not polynomial time- An example. Details 58:42
Interior Point Methods Details 53:48

Course Reviews


  • 5 stars0
  • 4 stars0
  • 3 stars0
  • 2 stars0
  • 1 stars0

No Reviews found for this course. All rights reserved.

Setup Menus in Admin Panel