# Course 1 : Linear Programming – Primer

## About Course

**1. Introduction to Operations Research:**

Operations Research (OR) is a discipline that deals with the application of advanced analytical methods to help make better decisions. It originated during World War II when military planners faced complex logistical problems and needed systematic methods to optimize resource allocation. Since then, OR has found applications in various fields, including business, engineering, healthcare, and finance.

The primary goal of OR is to provide quantitative tools and techniques to support decision-making processes. It draws upon mathematical modeling, statistical analysis, and optimization algorithms to solve complex problems efficiently. OR practitioners typically follow a structured approach involving problem formulation, model development, solution, and implementation.

Key components of Operations Research include:

- Problem Identification: Identifying the decision-making problem and its key objectives is the first step in OR. This involves understanding the problem context, stakeholders’ requirements, and constraints.
- Mathematical Modeling: OR relies heavily on mathematical models to represent real-world systems. These models abstract the problem into a mathematical framework, allowing analysts to apply quantitative techniques for analysis and optimization.
- Optimization Techniques: Optimization lies at the heart of OR. It involves finding the best possible solution from a set of feasible alternatives, considering various constraints and objectives. Common optimization methods include linear programming, integer programming, dynamic programming, and nonlinear programming.
- Simulation: Simulation is another important tool in OR, especially for analyzing complex systems where analytical solutions are difficult to obtain. It involves creating a computer-based model of the system and running experiments to observe its behavior under different conditions.
- Decision Support Systems: OR often involves developing decision support systems (DSS) to assist decision-makers in evaluating alternatives and making informed choices. These systems integrate analytical models, data, and user interfaces to facilitate decision-making processes.

Overall, Operations Research provides a systematic framework for tackling complex decision problems by leveraging mathematical and computational techniques.

**2. Mathematical Modeling Basics:**

Mathematical modeling is a fundamental concept in Operations Research and many other fields. It involves representing real-world systems using mathematical structures to gain insights, make predictions, and optimize performance. Mathematical models abstract complex phenomena into simplified representations that capture essential features of the system under study.

The process of mathematical modeling typically involves several steps:

- Problem Formulation: Clearly defining the problem to be addressed is the first step in mathematical modeling. This involves identifying the system’s components, variables, parameters, constraints, and objectives.
- Model Assumptions: Models often make simplifying assumptions to render the problem tractable. These assumptions help streamline the modeling process but may introduce some degree of approximation or error.
- Model Development: Once the problem is formulated and assumptions are made, the next step is to develop the mathematical model. This involves selecting appropriate mathematical equations, functions, or algorithms to represent the relationships between variables and parameters.
- Model Validation: Validating the model involves assessing its accuracy and reliability in representing the real-world system. This may involve comparing model predictions with empirical data or conducting sensitivity analyses to evaluate the model’s robustness.
- Model Solution: Solving the mathematical model entails applying appropriate mathematical techniques or computational algorithms to obtain solutions. This could involve analytical methods, numerical simulations, or optimization algorithms, depending on the complexity of the model.
- Model Interpretation: Once solutions are obtained, they need to be interpreted in the context of the original problem. This involves analyzing the results, drawing conclusions, and making recommendations based on the model’s insights.

Mathematical modeling can take various forms depending on the nature of the problem and the desired level of abstraction. Common types of mathematical models include deterministic models, stochastic models, continuous models, discrete models, and hybrid models.

Overall, mathematical modeling provides a powerful framework for understanding and analyzing complex systems in a wide range of disciplines, including Operations Research.

**3. Linear Programming: End-to-End Understanding (Basics, IP, MIP):**

Linear programming (LP) is a mathematical optimization technique used to determine the best possible outcome of a linear objective function, subject to a set of linear equality and inequality constraints. It is widely used in various fields, including operations research, economics, engineering, and management.

The basic components of a linear programming problem include:

- Decision Variables: These are the variables representing the quantities to be determined. They typically represent the decision-maker’s choices and are denoted by symbols like x1, x2, …, xn.
- Objective Function: The objective function defines the goal or objective of the optimization problem. It is a linear combination of decision variables and represents the quantity to be maximized or minimized.
- Constraints: Constraints are conditions that restrict the values of decision variables. They can be expressed as linear equations or inequalities and represent the limitations or requirements of the problem.

A standard form linear programming problem can be formulated as follows:

Maximize (or Minimize) Z = c1x1 + c2x2 + … + cnxn

Subject to: a11x1 + a12x2 + … + a1nxn ≤ b1 a21x1 + a22x2 + … + a2nxn ≤ b2 … am1x1 + am2x2 + … + amnxn ≤ bm x1, x2, …, xn ≥ 0

Where:

- Z is the objective function to be maximized or minimized.
- ci (for i=1 to n) are the coefficients of the objective function.
- aij (for i=1 to m and j=1 to n) are the coefficients of the constraint equations.
- bi (for i=1 to m) are the right-hand sides of the constraint equations.
- x1, x2, …, xn are the decision variables to be determined.

Linear programming problems can be solved using various methods, including the simplex method, the graphical method, and software-based optimization techniques. The simplex method is the most commonly used algorithm for solving linear programming problems. It involves iteratively moving from one feasible solution to another along the edges of the feasible region until an optimal solution is reached.

Integer programming (IP) extends linear programming by allowing some or all of the decision variables to take on integer values. Mixed-integer programming (MIP) further generalizes this concept by allowing a mix of integer and continuous decision variables. IP and MIP problems are often encountered in real-world applications where decisions need to be made in discrete units.

In summary, linear programming provides a powerful framework for optimizing resource allocation and decision-making in various domains. Its extensions, integer programming and mixed-integer programming, further enhance its applicability to real-world problems with discrete decision variables. Understanding the basics of linear programming and its variants is essential for practitioners in operations research and related fields.