Linear Programming: introduction

• Operational Research (OR) is a discipline that deals with the application of advanced analytical methods to help make better decisions
• It often involves mathematical modeling and analysis of complex systems

Linear Programming

• Linear programming (LP) is a mathematical technique used to find the best outcome, such as maximum profit or lowest cost, for a linear model
• It is subject to a set of linear constraints, represented by linear equations and linear inequalities

Key Components of a Linear Programming Problem

• Decision Variables: These are the variables that the decision-maker controls to achieve the objective
• Objective Function: This is a linear mathematical function that represents the goal, which could be maximization (e.g., profit) or minimization (e.g., cost)
• Constraints: These are linear inequalities or equalities that limit the values of the decision variables
• Non-negativity Constraints: These constraints specify that the decision variables must be non-negative (greater than or equal to zero)

Assumptions of Linear Programming

• Linearity: The relationship between variables is linear, meaning that the objective function and constraints can be written as linear equations
• Divisibility: Decision variables can take on fractional values
• Certainty: The parameters in the objective function and constraints are known with certainty
• Additivity: The total value of the objective function and each constraint is the sum of the individual contributions of the decision variables
• Non-negativity: Decision variables must be non-negative

Standard Form of Linear Programming

• Objective function is maximized/minimized
• All the constraints are expressed as equalities
• All variables are non-negative

Basic Solutions

• Basic Solution: A solution obtained by setting n - m variables (non-basic variables) to zero and solving for the values of the remaining m variables (basic variables), where n is the number of variables and m is the number of constraints
• Basic Feasible Solution (BFS): A basic solution that also satisfies all the constraints (i.e., it is feasible)
• Optimal Solution: A feasible solution that results in the best possible value of the objective function

Methods to Solve Linear Programming Problems

• Graphical Method: Used for problems with two decision variables
• Simplex Method: An iterative algebraic procedure to find the optimal solution
• Revised Simplex Method: A more efficient version of the simplex method, especially for computer implementation
• Dual Simplex Method: Used when the initial solution is not feasible but optimal
• Interior Point Methods: Alternative to the simplex method, especially for large problems

Graphical Method

• Plot the constraints on a graph
• Identify the feasible region (the area satisfying all constraints)
• Determine the corner points (vertices) of the feasible region
• Evaluate the objective function at each corner point
• Select the corner point that optimizes the objective function

Simplex Method

• Convert the LP problem into standard form by introducing slack, surplus, and artificial variables
• Set up the initial simplex tableau
• Select the entering variable (pivot column) based on the most negative coefficient in the objective row (for maximization)
• Select the leaving variable (pivot row) based on the minimum ratio test
• Perform row operations to make the pivot element 1 and all other elements in the pivot column 0
• Repeat steps until all coefficients in the objective row are non-negative (for maximization) or non-positive (for minimization)

Duality in Linear Programming

• Every LP problem (the primal) has a related LP problem called the dual
• The optimal solution of the dual problem provides information about the shadow prices (marginal values) of the resources in the primal problem
• Weak Duality: The objective function value of the dual problem is always greater than or equal to the objective function value of the primal problem (for maximization primal and minimization dual)
• Strong Duality: At the optimal solution, the objective function values of the primal and dual problems are equal

Sensitivity Analysis

• Sensitivity analysis examines how the optimal solution changes with variations in the input parameters
• It helps in understanding the robustness of the solution and identifying critical parameters
• Key areas include:
  • Changes in objective function coefficients
  • Changes in the right-hand side values of the constraints
  • Addition of new variables or constraints

Applications of Linear Programming

• Product Mix: Determining the optimal mix of products to manufacture to maximize profit, given resource constraints
• Blending Problems: Determining the optimal blend of ingredients to meet certain quality standards at minimum cost
• Diet Planning: Planning a diet to meet specific nutritional requirements at the lowest cost
• Transportation: Determining the optimal shipping schedule to minimize transportation costs while meeting demand
• Assignment Problems: Assigning tasks to individuals to minimize total cost or maximize efficiency

Integer Programming

• Integer Programming (IP) is a variant of linear programming where some or all of the decision variables are restricted to be integers
• Types of Integer Programming:
  • Pure Integer Programming: All decision variables are integers
  • Mixed Integer Programming: Some decision variables are integers, and others are continuous
  • Binary Integer Programming: Decision variables are restricted to be 0 or 1

Methods for Solving Integer Programming Problems

• Branch and Bound: Divides the feasible region into smaller subproblems and systematically explores them
• Cutting Plane Methods: Adds new constraints to the problem to cut off non-integer solutions
• Heuristic Algorithms: Provide good but not necessarily optimal solutions in a reasonable amount of time

Advantages of Linear Programming

• Optimality: LP guarantees finding the optimal solution if one exists
• Modeling Flexibility: LP can model a wide range of problems with linear relationships
• Sensitivity Analysis: LP provides insights into how changes in parameters affect the optimal solution
• Availability of Solvers: Efficient software packages are available to solve LP problems

Limitations of Linear Programming

• Linearity Assumption: Real-world relationships are often non-linear, which may limit the applicability of LP
• Deterministic Parameters: LP assumes that parameters are known with certainty, which may not be realistic
• Divisibility Assumption: LP assumes that decision variables can take on fractional values, which may not be appropriate for all problems
• Complexity for Large Problems: Solving large LP problems can be computationally intensive