2.1 Linear programming

Linear programming is a powerful optimization technique that originated during World War II to solve complex military logistics problems. It has since become a fundamental tool in operations research and scientific computing, enabling efficient resource allocation and decision-making across various fields.

The core components of linear programming include the objective function, decision variables, and constraints. These elements work together to formulate and solve optimization problems, subject to key assumptions like proportionality, additivity, divisibility, and certainty.

Origins of linear programming

• Linear programming (LP) is a mathematical optimization technique that originated in the 1940s during World War II to solve complex military logistics problems
• It was developed by a team of mathematicians and economists, including George Dantzig, who formulated the simplex method, a powerful algorithm for solving LP problems
• LP has since become a fundamental tool in operations research, management science, and various fields of engineering, including applications of scientific computing, due to its ability to optimize resource allocation and decision-making processes

Components of linear programming model

Objective function

Top images from around the web for Objective function

• 

  How a Profit-Maximizing Monopoly Chooses Output and Price · Economics View original

  Is this image relevant?

• 

  How a Profit-Maximizing Monopoly Chooses Output and Price | OS Microeconomics 2e View original

  Is this image relevant?

• 

  Frontiers | A Review of the Use of Linear Programming to Optimize Diets, Nutritiously ... View original

  Is this image relevant?

• 

  How a Profit-Maximizing Monopoly Chooses Output and Price · Economics View original

  Is this image relevant?

• 

  How a Profit-Maximizing Monopoly Chooses Output and Price | OS Microeconomics 2e View original

  Is this image relevant?

1 of 3

Top images from around the web for Objective function

• 

  How a Profit-Maximizing Monopoly Chooses Output and Price · Economics View original

  Is this image relevant?

• 

  How a Profit-Maximizing Monopoly Chooses Output and Price | OS Microeconomics 2e View original

  Is this image relevant?

• 

  Frontiers | A Review of the Use of Linear Programming to Optimize Diets, Nutritiously ... View original

  Is this image relevant?

• 

  How a Profit-Maximizing Monopoly Chooses Output and Price · Economics View original

  Is this image relevant?

• 

  How a Profit-Maximizing Monopoly Chooses Output and Price | OS Microeconomics 2e View original

  Is this image relevant?

1 of 3

• The objective function represents the goal of the optimization problem, which is to maximize or minimize a linear function of the decision variables
• It is a mathematical expression that quantifies the performance measure or criterion to be optimized, such as profit, cost, or efficiency
• The objective function is typically expressed as $Z = c_1x_1 + c_2x_2 + ... + c_nx_n$, where $c_i$ are the coefficients and $x_i$ are the decision variables

Decision variables

• Decision variables represent the unknowns or controllable factors in the optimization problem that need to be determined to achieve the objective
• They are typically denoted by $x_1, x_2, ..., x_n$ and represent quantities such as production levels, resource allocations, or investment decisions
• The values of the decision variables are subject to the constraints of the problem and must be non-negative in most LP formulations

Constraints

• Constraints are the limitations or restrictions that the decision variables must satisfy in the optimization problem
• They represent the physical, economic, or technological limitations of the system, such as resource availability, production capacities, or demand requirements
• Constraints are expressed as linear equations or inequalities in terms of the decision variables, such as $a_1x_1 + a_2x_2 + ... + a_nx_n \leq b$, where $a_i$ are the coefficients and $b$ is the right-hand side value

Assumptions in linear programming

Proportionality

• The proportionality assumption states that the contribution of each decision variable to the objective function and the constraints is directly proportional to its value
• This means that doubling the value of a decision variable will double its contribution to the objective function and the constraints
• Proportionality ensures that the relationships between variables are linear and allows for the formulation of the problem as a linear program

Additivity

• The additivity assumption implies that the total contribution of the decision variables to the objective function and the constraints is the sum of their individual contributions
• This means that the effect of changing one variable is independent of the values of other variables, and there are no interactions or synergies between them
• Additivity allows for the decomposition of the problem into separate terms and the application of linear programming techniques

Divisibility

• The divisibility assumption states that the decision variables can take on any non-negative real value, including fractional values
• This means that the variables are continuous and can be divided into smaller units as needed to achieve the optimal solution
• Divisibility is a simplifying assumption that allows for the application of continuous optimization methods, although in some cases, integer programming may be required for problems with discrete variables

Certainty

• The certainty assumption implies that all the parameters of the linear programming model, such as the coefficients in the objective function and the constraints, are known with certainty
• This means that there is no uncertainty or randomness in the input data, and the problem can be formulated as a deterministic optimization model
• In practice, sensitivity analysis can be performed to assess the impact of changes in the parameters on the optimal solution, relaxing the certainty assumption to some extent

Formulating linear programming problems

Identifying decision variables

• The first step in formulating an LP problem is to identify the decision variables that represent the unknowns or controllable factors in the system
• Decision variables should be clearly defined and labeled, typically using symbols such as $x_1, x_2, ..., x_n$
• Examples of decision variables include production quantities (units produced of each product), resource allocations (hours of machine time, labor hours), or investment decisions (funds allocated to different projects)

Defining objective function

• The objective function represents the goal or performance measure to be optimized in the LP problem, expressed as a linear function of the decision variables
• It should be clearly stated whether the objective is to maximize (profit, efficiency) or minimize (cost, waste) the function
• The objective function is typically written in the form $Z = c_1x_1 + c_2x_2 + ... + c_nx_n$, where $c_i$ are the coefficients representing the contribution of each variable to the objective

Specifying constraints

• Constraints are the limitations or restrictions that the decision variables must satisfy, expressed as linear equations or inequalities
• They represent the physical, economic, or technological limitations of the system, such as resource availability (raw materials, machine capacity), production requirements (demand, inventory), or policy restrictions (budget, regulations)
• Constraints are typically written in the form $a_1x_1 + a_2x_2 + ... + a_nx_n \leq b$, $a_1x_1 + a_2x_2 + ... + a_nx_n \geq b$, or $a_1x_1 + a_2x_2 + ... + a_nx_n = b$, where $a_i$ are the coefficients and $b$ is the right-hand side value

Non-negativity restrictions

• In most LP formulations, the decision variables are required to be non-negative, as negative values may not have a practical interpretation in the context of the problem
• Non-negativity restrictions are typically written as $x_1 \geq 0, x_2 \geq 0, ..., x_n \geq 0$ and are included as additional constraints in the LP model
• These restrictions ensure that the optimal solution is feasible and meaningful in the real-world context of the problem

Graphical solution for linear programming

Feasible region

• The feasible region is the set of all points in the decision variable space that satisfy all the constraints of the LP problem
• It represents the area where all the constraints intersect and where the optimal solution must lie
• The feasible region is typically represented graphically in two dimensions for problems with two decision variables, with each constraint represented as a straight line or a half-plane

Optimal solution

• The optimal solution is the point within the feasible region that yields the best value of the objective function, either the maximum or minimum value, depending on the problem
• In the graphical method, the optimal solution is found by identifying the corner points of the feasible region and evaluating the objective function at each point
• The corner point with the best objective function value (highest for maximization, lowest for minimization) is the optimal solution

Corner point method

• The corner point method is a systematic approach to finding the optimal solution in the graphical method for LP problems with two decision variables
• It involves the following steps:
  1. Plot the constraints as straight lines and identify the feasible region
  2. Determine the corner points of the feasible region by solving the simultaneous equations of the constraint lines
  3. Evaluate the objective function at each corner point
  4. Select the corner point with the best objective function value as the optimal solution
• The corner point method exploits the fact that the optimal solution of an LP problem always occurs at a corner point of the feasible region, simplifying the search process

Simplex method for linear programming

Standard form

• The standard form is a canonical representation of an LP problem that facilitates the application of the simplex method
• In standard form, the objective function is maximized, all constraints are expressed as equalities with non-negative slack variables, and all variables are non-negative
• The standard form of an LP problem is written as:
  • Maximize $Z = c_1x_1 + c_2x_2 + ... + c_nx_n$
  • Subject to:
    • $a_{11}x_1 + a_{12}x_2 + ... + a_{1n}x_n = b_1$
    • $a_{21}x_1 + a_{22}x_2 + ... + a_{2n}x_n = b_2$
    • ...
    • $a_{m1}x_1 + a_{m2}x_2 + ... + a_{mn}x_n = b_m$
    • $x_1 \geq 0, x_2 \geq 0, ..., x_n \geq 0$

Basic vs non-basic variables

• In the simplex method, the variables are classified as either basic or non-basic variables at each iteration
• Basic variables are the variables that have a value greater than zero in the current solution and correspond to the columns of the identity matrix in the simplex tableau
• Non-basic variables are the variables that have a value of zero in the current solution and correspond to the columns of the coefficient matrix in the simplex tableau
• The number of basic variables is always equal to the number of constraints in the standard form of the LP problem

Simplex tableau

• The simplex tableau is a tabular representation of the LP problem that facilitates the iterative process of the simplex method
• It consists of a matrix of coefficients, a column for the right-hand side values, and a row for the objective function coefficients
• The tableau is updated at each iteration of the simplex method by performing pivot operations to exchange a non-basic variable with a basic variable and improve the objective function value
• The initial tableau is constructed from the standard form of the LP problem, with slack variables added to convert the inequalities into equalities

Simplex algorithm steps

• The simplex algorithm is an iterative procedure for solving LP problems using the simplex tableau
• The main steps of the simplex algorithm are:
  1. Convert the LP problem to standard form and construct the initial simplex tableau
  2. Select the entering variable (non-basic variable) with the most negative coefficient in the objective function row
  3. Select the leaving variable (basic variable) based on the minimum ratio test to maintain feasibility
  4. Perform a pivot operation to update the simplex tableau, exchanging the entering and leaving variables
  5. Repeat steps 2-4 until no negative coefficients remain in the objective function row, indicating optimality
  6. Read the optimal solution from the final simplex tableau, with the values of the basic variables and the objective function value
• The simplex algorithm terminates when either an optimal solution is found or when unboundedness or infeasibility is detected

Duality in linear programming

Primal vs dual problems

• Every LP problem, called the primal problem, has a corresponding dual problem that provides valuable insights and optimality conditions
• The primal problem is the original LP problem, typically in standard form, with the objective to maximize (or minimize) a linear function subject to linear constraints
• The dual problem is derived from the primal problem by interchanging the roles of the variables and the constraints, with the objective to minimize (or maximize) a related linear function subject to dual constraints
• The dual problem has one variable for each constraint in the primal problem and one constraint for each variable in the primal problem

Weak duality theorem

• The weak duality theorem states that the objective function value of any feasible solution to the primal problem is always less than or equal to the objective function value of any feasible solution to the dual problem
• In other words, the value of the primal objective function at any feasible point is a lower bound on the value of the dual objective function at any feasible point
• The weak duality theorem provides a useful bound on the optimal value of the primal and dual problems and can be used to verify the optimality of a solution

Strong duality theorem

• The strong duality theorem states that if the primal problem has an optimal solution, then the dual problem also has an optimal solution, and the optimal objective function values of the primal and dual problems are equal
• This means that if either the primal or the dual problem has an optimal solution, then both problems have optimal solutions, and the optimal values coincide
• The strong duality theorem establishes a fundamental relationship between the primal and dual problems and is a key result in LP theory
• It allows for the interpretation of the dual variables as shadow prices or marginal values associated with the constraints of the primal problem

Sensitivity analysis in linear programming

Changes in objective function coefficients

• Sensitivity analysis investigates the impact of changes in the parameters of an LP problem on the optimal solution and the objective function value
• Changes in the objective function coefficients, $c_j$, affect the relative importance of the decision variables in the optimization process
• The allowable range for each $c_j$ can be determined, within which the current optimal solution remains optimal
• If a $c_j$ value falls outside its allowable range, the optimal solution may change, and the problem needs to be re-solved

Changes in right-hand side values

• Changes in the right-hand side values, $b_i$, of the constraints represent variations in the available resources or the requirements of the system
• The allowable range for each $b_i$ can be determined, within which the current optimal basis (set of basic variables) remains unchanged
• If a $b_i$ value falls outside its allowable range, the optimal basis may change, and the problem needs to be re-solved using the dual simplex method or by updating the simplex tableau

Addition of new variables or constraints

• Sensitivity analysis can also be performed when new decision variables or constraints are added to the LP problem
• Adding a new variable involves expanding the simplex tableau with an additional column and updating the objective function coefficients and the constraint coefficients accordingly
• Adding a new constraint involves expanding the simplex tableau with an additional row and updating the right-hand side values and the slack variables accordingly
• The revised problem can then be solved using the simplex method, starting from the current optimal solution, to determine the new optimal solution and the impact on the objective function value

Applications of linear programming

Resource allocation problems

• LP is widely used in resource allocation problems, where the objective is to optimize the allocation of limited resources (e.g., time, money, materials) among competing activities or projects
• Examples include allocating production capacity among different products, distributing budget among various investments, or assigning personnel to different tasks
• The decision variables represent the amount of resources allocated to each activity, the constraints represent the resource limitations and other requirements, and the objective function represents the total benefit or cost to be optimized

Production planning problems

• Production planning problems involve determining the optimal production quantities of different products over a planning horizon to meet demand while minimizing costs or maximizing profits
• LP can be used to model production constraints (e.g., machine capacity, labor availability), inventory balance equations, and demand requirements
• The decision variables represent the production quantities of each product in each time period, the constraints ensure that the production plan is feasible, and the objective function represents the total production cost or profit

Transportation problems

• Transportation problems deal with the optimal distribution of goods from supply points (e.g., factories, warehouses) to demand points (e.g., customers, retailers) to minimize total transportation costs
• LP can be used to model the supply and demand constraints, the transportation costs between each supply-demand pair, and the flow balance equations
• The decision variables represent the quantity of goods shipped from each supply point to each demand point, the constraints ensure that the supply and demand requirements are met, and the objective function represents the total transportation cost

Assignment problems

• Assignment problems involve assigning a set of tasks or resources to a set of agents or recipients in an optimal manner, such as assigning workers to jobs or machines to tasks
• LP can be used to model the assignment constraints (each task is assigned to exactly one agent and each agent is assigned to at most one task) and the assignment costs or benefits
• The decision variables are binary, representing whether a task is assigned to an agent or not, the constraints ensure that each task is assigned and each agent's capacity is respected, and the objective function represents the total assignment cost or benefit

Software for linear programming

Spreadsheet solvers

• Spreadsheet software, such as Microsoft Excel or Google Sheets, includes built-in solvers that can handle small to medium-sized LP problems
• The Solver add-in in Excel allows users to define the objective function, decision variables, and constraints using cell references and formulas
• The solver then applies optimization algorithms (e.g., simplex method, interior point method) to find the optimal solution and displays the results in the spreadsheet
• Spreadsheet solvers are user-friendly and require minimal programming skills, making them suitable for quick prototyping and less complex LP problems

Specialized linear programming software

• Specialized LP software packages offer more advanced features and can handle large-scale problems efficiently
• Examples include:
  • LINDO: A comprehensive optimization software that provides a range of solvers for LP, integer programming, and nonlinear programming problems
  • CPLEX: A high-performance optimization solver developed by IBM, widely used in industry and academia for solving large-scale LP and mixed-integer programming problems
  • Gurobi: A state-of-the-art optimization solver that offers fast and reliable solutions for LP, mixed-integer programming, and quadratic programming problems
• These software packages provide APIs and interfaces for various programming languages (e.g., C++, Java, Python) and modeling environments, allowing for seamless integration with existing systems and workflows

Optimization modeling languages

• Optimization modeling languages provide a high-level, algebraic interface for formulating and solving LP problems, abstracting away the complexity of the underlying solvers
• Examples include:
  • AMPL: A powerful and flexible modeling language that supports a wide range of optimization problems, including LP, integer programming, and nonlinear programming
  • GAMS: A high-level modeling system for mathematical optimization, designed for complex, large-scale problems in various domains, such as energy, agriculture, and manufacturing
  • Pyomo: An open-source optimization modeling language in Python, which allows users to define LP problems using