Operations Research & Linear Programming

• Operations research (OR) uses advanced analytical methods for better decision-making.
• OR is considered a subfield of mathematics, computer science, and industrial engineering.
• OR assists organizations in achieving goals by providing optimal solutions to complex problems.
• These problems usually concern the allocation of scarce resources.
• The field uses problem-solving techniques and methods to improve decision-making and efficiency.
• OR uses mathematical modeling, statistics, and optimization to find optimal or near-optimal solutions.

Linear Programming (LP)

• Linear programming (LP) is a mathematical technique to find the best outcome using linear relationships.
• LP optimizes a linear objective function subject to linear equality and inequality constraints.
• A linear program has decision variables, an objective function, and constraints.
• Decision variables are the quantities that the decision-maker controls.
• The objective function is a linear expression of the decision variables, which the decision-maker wants to maximize or minimize.
• Constraints are linear equalities or inequalities.
• LP problems are solved using graphical, simplex, and interior-point methods.

Key Concepts in Linear Programming

• Objective Function: A mathematical expression representing the goal (maximize or minimize).
• Constraints: Limitations expressed as linear equations or inequalities.
• Decision Variables: Unknowns to be determined for the optimal solution.
• Feasible Region: The set of solutions that satisfy all constraints.
• Optimal Solution: The point in the feasible region that gives the best objective function value.
• Non-negativity Constraints: Decision variables must be non-negative (≥ 0).

Assumptions of Linear Programming

• Linearity: Relationships between variables are linear.
• Divisibility: Decision variables can take fractional values.
• Certainty: Parameters are known and constant.
• Additivity: Total objective function value and resource usage are sums of individual contributions.
• Non-negativity: Decision variables must be non-negative.

Standard Form of a Linear Programming Problem

• Maximize or minimize: Z = c1x1 + c2x2 + ... + cnxn
• Subject to:
  • a11x1 + a12x2 + ... + a1nxn ≤ b1
  • a21x1 + a22x2 + ... + a2nxn ≤ b2
  • ...
  • am1x1 + am2x2 + ... + amnxn ≤ bm
  • xi ≥ 0 for all i (non-negativity constraints)
• Where:
  • Z is the value to be optimized.
  • xi are the decision variables.
  • ci are objective function coefficients.
  • aij are constraint coefficients.
  • bi are the right-hand side values of the constraints.

Graphical Method

• The graphical method solves linear programming problems with two decision variables.
• Each constraint is graphed as a line on a coordinate plane.
• The feasible region satisfies all constraints simultaneously.
• Determine the corner points of the feasible region.
• Evaluate the objective function at each corner point to find the optimal solution.
• The corner point with the best objective function value is the optimal solution.

Applications of Linear Programming

• Resource Allocation: Optimizing the use of limited resources.
• Production Planning: Determining optimal production levels to meet demand at minimum cost.
• Inventory Management: Managing inventory to minimize costs and avoid stockouts.
• Transportation and Logistics: Finding efficient routes and schedules.
• Financial Planning: Optimizing investment portfolios.
• Blending Problems: Determining the optimal mix of ingredients to meet requirements at minimum cost.

The Simplex Method

• The simplex method is an iterative algorithm for solving linear programming problems.
• It systematically examines corner points of the feasible region to find the optimal solution.
• Convert the linear programming problem into standard form.
• Introduce slack, surplus, and artificial variables to convert inequalities into equalities.
• Set up the initial simplex tableau.
• Perform iterations until the optimal solution is reached.
• In each iteration, select the entering variable (most negative coefficient in the objective row) and the leaving variable (determined by the minimum ratio test).
• Update the tableau using row operations.

Duality in Linear Programming

• Every linear programming problem (primal) has a dual problem.
• The dual problem provides insights into the economic interpretation of the primal problem.
• The optimal solution to the dual problem gives information about shadow prices.
• Shadow price is the change in the optimal objective function value for a one-unit increase in a resource.
• If the primal is maximization, the dual is minimization, and vice versa.
• Dual problem variables correspond to primal problem constraints, and vice versa.
• Dual objective function coefficients are the right-hand side values of primal constraints, and vice versa.

Sensitivity Analysis

• Sensitivity analysis assesses how changes in input parameters affect the optimal solution.
• It helps understand the solution's robustness and identify critical parameters.
• Shadow Prices: Indicate the change in the optimal objective function value for a one-unit increase in resource availability.
• Allowable Increase/Decrease: Specifies the range within which variable coefficients or constraint values can change without affecting the optimality.
• Reduced Cost: The amount by which the objective function coefficient of a non-basic variable must improve before it becomes part of the optimal solution.

Integer Programming

• Integer programming (IP) restricts some or all variables to be integers.
• It is employed when decision variables represent discrete, non-fractional entities.
• Types of IP:
  • Pure Integer Programming restricts all decision variables to integers.
  • Mixed Integer Programming allows some decision variables to be integers, while others are continuous.
  • Binary Integer Programming restricts decision variables to 0 or 1.

Common Techniques for Solving Integer Programming Problems

• Branch and Bound: Explores the feasible region by dividing it into subproblems and setting bounds.
• Cutting Plane Methods: Add constraints to reduce the feasible region towards integer values.
• Heuristic Methods: Provide near-optimal solutions quickly.

Applications of Integer Programming

• Facility Location: Determines the optimal location of facilities.
• Scheduling Problems: Schedules tasks, jobs, or resources.
• Capital Budgeting: Selects the optimal set of investment projects.
• Set Covering and Partitioning: Covers or partitions sets of elements.

Limitations of Linear Programming

• Linear programming assumes linearity, which may not hold in real-world problems.
• The certainty assumption may be invalid due to uncertainty.
• The divisibility assumption may not be appropriate for integer variables.
• Models can become complex for large-scale problems.

Software for Solving Linear Programming Problems

• Software packages available:
  • CPLEX
  • Gurobi
  • LINDO
  • MATLAB
  • Excel Solver
• These packages use advanced algorithms to solve large-scale problems.