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