This course aims to introduce various real-life problems that can be formulated as Linear Programming Problems (LPP). It is designed as an introductory course in optimization, where all concepts will be clearly motivated and explained with examples.
The following topics will be discussed in detail:
This module introduces the fundamental concepts of Linear Programming Problems (LPP). Students will learn about the definition, importance, and applications of LPP in various fields.
In this module, students will explore vector spaces, including the concepts of linear independence and dependence. Understanding these concepts is crucial for grasping advanced topics in linear programming and optimization.
This module discusses the process of transitioning between basic feasible solutions. Students will learn about optimality criteria and how to identify optimal solutions within the framework of linear programming.
This module delves into the existence and derivation of basic feasible solutions. Students will learn how to formulate and analyze various LPPs to identify feasible solutions.
This module introduces convex sets and the dimension of a polyhedron. Students will explore the definitions and properties of faces, as well as examples of polytopes.
Students will learn about the direction of a polyhedron and the correspondence between basic feasible solutions and extreme points. This understanding is crucial in optimization.
This module focuses on the representation theorem, showing that the solution to an LPP is a basic feasible solution. It will also include an assignment for practical understanding.
In this module, the development of the Simplex Algorithm is covered. Students will learn about unboundedness and how to set up a Simplex tableau for problem-solving.
This module elaborates on the Simplex tableau, cycling issues, and introduces Bland's anti-cycling rules. Students will also learn about the two phases of the Simplex Method.
This module covers the Big-M method, graphical solutions, and the relationship between adjacent extreme points and adjacent basic feasible solutions.
Students will engage with assignment 2, focusing on the progress of the Simplex algorithm on a polytope and understanding bounded variable LPPs.
This module introduces the concepts of bounded variable LPPs and the Revised Simplex algorithm, along with duality theory and the weak duality theorem.
This module further explores the weak duality theorem along with its economic interpretations of dual variables. Students will understand the practical implications of duality.
Students will learn to write the dual of linear programming problems, examining examples to illustrate the complementary slackness theorem and its applications.
This module discusses the complementary slackness conditions and introduces the Dual Simplex algorithm. An assignment will reinforce the learning objectives.
Students will learn about the Primal-Dual algorithm, gaining insights into how dual problems relate to primal problems in optimization.
This module presents a problem from the previous lecture, focusing on starting dual feasible solutions and addressing the Shortest Path Problem.
Students will explore the Shortest Path Problem further, studying the Primal-Dual method and reviewing examples for a better understanding of the concepts.
This module investigates the complexity of the Shortest Path Problem and the interpretation of dual variables, providing a deeper understanding of these critical concepts.
In this module, students will complete assignment 4, which focuses on postoptimality analysis, considering changes in the right-hand side vector and adding new constraints.
This module introduces parametric LPPs, focusing on the right-hand side vector. Students will learn how changes in this vector affect the optimal solution.
Continuing from the previous module, students will explore parametric cost vector LPPs, understanding how variations in the cost vector impact solutions.
This module introduces the Min-cost flow problem, linking it with parametric cost vector LPPs to illustrate real-world applications and case studies.
Students will explore the Transportation problem as a specific case of the Min-cost flow problem. Various methods for solving transportation issues will be examined.
This module addresses issues related to degeneracy and cycling in the Transportation problem, providing insights into how to handle such complexities effectively.
Students will learn about sensitivity analysis, examining how changes in parameters impact the optimal solution of LPPs. This understanding is vital for practical applications.
This module further explores sensitivity analysis, reinforcing its importance in decision-making and how it can inform adjustments to optimization problems.
Students will learn about bounded variable transportation problems and the Min-cost flow problem, gaining insights into solving these types of optimization challenges.
This module investigates the Min-cost flow problem in detail, allowing students to apply their knowledge to real-world scenarios and case studies.
Students will learn about starting feasible solutions and the Lexicographic method as a strategy to prevent cycling in linear programming solutions.
This module focuses on assignment 6, which includes a Shortest Path problem analysis. Students will learn to find the shortest path between any two nodes in a graph.
Students will further explore Min-cost flow and its sensitivity analysis, applying the concepts to the Shortest Path problem to understand how variations affect outcomes.
This module addresses changes in arc capacities within the context of the Min-cost flow problem. Students will also tackle the Max-flow problem alongside assignment 7.
In this module, students will tackle assignment 7, which includes a problem related to the Min-cut Max-flow theorem and the labeling algorithm used to solve such problems.
This module discusses critical capacity of an arc in the Max-flow problem, introducing methods for determining starting solutions for Min-cost flow problems.
Students will learn about improved algorithms for solving the Max-flow problem, enabling them to approach these challenges with enhanced strategies and techniques.
This module introduces the Critical Path Method (CPM), which is essential for project management. Students will learn how to identify critical paths in project scheduling.
Students will explore the Programme Evaluation and Review Technique (PERT), learning how to analyze project tasks and timelines effectively, enhancing their project management skills.
This module discusses why the Simplex Algorithm is not polynomial time, providing a concrete example to illustrate the limitations of the algorithm in certain scenarios.
Students will learn about Interior Point Methods, which serve as alternative approaches to solving linear programming problems. This module will cover their principles and applications.