Lectures |
Topic/s |

1 |
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. |

2 |
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. |

3 |
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. |

4 |
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. |

5 |
A basic feasible solution is an extreme point of the corresponding Polyhedron. More about degeneracy. |

6 |
Supporting hyperplane of a polyhedron. Characterisation of an optimal solution in terms of supporting hyperplane. Graphical illustrations. |

7 |
Simplex Algorithm- Tableau format. |

8 |
Simplex algorithm – Starting feasible solution, Artificial variables, Phase I and Phase II methods. |

9 |
Bounded variables case; modification of the Simplex algorithm. |

10 |
Revised Simplex algorithm. Define the Dual problem and its various forms. |

11 |
Fundamental Theorem of Duality. Farka’s theorem. Complementary Slackness theorem. |

12 |
Dual Simplex algorithm; Motivation , theory and a numerical example. |

13 |
Primal Dual algorithm: Motivation , theory and a numerical example. |

14 |
Sensitivity Analysis of the objective function coefficient, right hand side components and elements of the matrix A. |

15 |
Adding of constraints and activities. A comprehensive numerical example. |

16 |
Parametric analysis. |

17 |
Min-cost flow problem- formulation and derivation of special cases such as Transportation problem, |

18 |
Assignment problem, Max-flow problem and the shortest path problem. |

19 |
Integer bfs property of Transportation problem. |

20 |
Simplified Simplex algorithm for Transportation problem. |

21 |
Sensitivity Analysis and Bounded Variable case. |

22 |
Formulation of Shortest Path Problem, Dijkstra’s algorithm. |

23 |
More general shortest Path algorithms, Sensitivity analysis. |

24 |
Applications of Max-flow problem. |

25 |
Algorithms and Sensitivity Analysis. |

26 |
Network Simplex Algorithm for Min – cost flow problem.(2) |

27 |
Project Planning Control with PERT / CPM, linear programming formulations. (3) |

28 |
Dynamic Programming: Principle of Optimality with proof. Discrete and continuous problems.(2) |

29 |
Backward and forward formulations. Probabilistic cases.(2) |

30 |
Game theory. Two-person Zero-sum game. Pure and mixed strategies with examples. |

31 |
Saddlepoint and graphical solutions. |

32 |
Linear programming iterative solution method. |

33 |
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. |

34 |
Ellipsoid algorithm- basic concepts and its applications. |

35 |
Basic idea behind Karmarkar’s algorithm and its applications. |