LP Software & Sensitivity Analysis

Standard Form in LP Problems

  • Linear Programming (LP) problems are often converted to a standard form for consistent analysis and to facilitate the application of solution algorithms like the Simplex method.

  • In this context, "standard form" implies that all decision variables are placed on the Left-Hand Side (LHS) of the constraints, while all numeric constant values are moved to the Right-Hand Side (RHS).

  • Constraints typically involve inequalities (≤≤ or ≥≥) or equalities (==).

  • Example Conversion: An expression like 3≥1+23≥1+2 needs to be rearranged. To bring it into a standard form where variables are on one side and a constant or zero on the other, it can be written as 3−1−2≥03−1−2≥0 or, if variables were involved, say 3x1≥1+2x23x1≥1+2x2, it would transform to 3x1−2x2≥13x1−2x2≥1. The objective function is usually either maximized or minimized.

Beaver Creek Pottery Problem

  • The Beaver Creek Pottery problem is a classic example of an LP problem used to demonstrate resource allocation.

  • Objective: Maximize the total profit, ZZ. The objective function is given by Z=40x1+50x2Z=40x1+50x2.

    • Here, x1x1 represents the number of units of Product 1 (e.g., bowls) to be produced, and x2x2 represents the number of units of Product 2 (e.g., mugs) to be produced.

    • The coefficients 4040 and 5050 represent the profit generated per unit of Product 1 and Product 2, respectively.

  • Constraints:

    • Labor: The first constraint represents the limited labor hours available: 1x1+2x2≤401x1+2x2≤40.

    • This means producing one unit of Product 1 requires 11 hour of labor, and one unit of Product 2 requires 22 hours of labor. The total labor available is 4040 hours.

    • Clay: The second constraint represents the limited amount of clay available: 4x1+3x2≤1204x1+3x2≤120.

    • This means producing one unit of Product 1 requires 44 units (e.g., pounds) of clay, and one unit of Product 2 requires 33 units of clay. The total clay available is 120120 units.

  • Non-negativity: The variables must be non-negative, meaning production quantities cannot be negative: x1,x2≥0x1,x2≥0. This is a fundamental requirement in most LP problems.

Excel Solver Setup

  • Excel Solver is a powerful add-in used to find optimal solutions for LP and other optimization problems.

  • Blue cells: These cells typically represent the decision variable values (e.g., x1x1 and x2x2). Solver changes these values to find the optimal solution.

  • Yellow cells: These cells are used to calculate the Left-Hand Side (LHS) of the constraints. They represent the actual resource usage based on the current decision variable values.

  • Orange cell: This cell contains the formula for the objective function, which Solver aims to maximize or minimize.

  • Equations for computations (referencing the Beaver Creek Problem values assumed to be in specific cells):

    • Profit (Objective function in cell B12B12): B12=C4⋅B10+D4⋅B11B12=C4⋅B10+D4⋅B11

    • Where C4C4 is profit per x1x1, D4D4 is profit per x2x2, B10B10 is the value of x1x1, and B11B11 is the value of x2x2.

    • Labor usage (LHS of labor constraint in cell E6E6): E6=C6⋅B10+D6⋅B11E6=C6⋅B10+D6⋅B11

    • Where C6C6 is labor per x1x1, D6D6 is labor per x2x2.

    • Clay usage (LHS of clay constraint in cell E7E7): E7=C7⋅B10+D7⋅B11E7=C7⋅B10+D7⋅B11

    • Where C7C7 is clay per x1x1, D7D7 is clay per x2x2.

Sensitivity Analysis in LP

  • Sensitivity analysis is a crucial post-optimality analysis technique in Linear Programming.

  • It examines how the optimal solution (the values of the decision variables and the objective function value) changes when there are changes in the problem's input parameters.

  • These parameters can include objective function coefficients, right-hand side values of constraints, or technological coefficients.

  • It helps decision-makers understand the robustness of their optimal strategy and guides responses to potential changes in business conditions, resource availability, or market prices.

Sensitivity Ranges for Objective Function Coefficients

  • This analysis determines the range within which an objective function coefficient (cici​) can vary without changing the current optimal basis (i.e., the set of optimal non-zero decision variables).

  • The sensitivity range for a coefficient cici indicates that as long as cici remains within these specific bounds, the current set of optimal variables will remain optimal, although the actual optimal objective function value may change.

  • If a coefficient changes beyond its sensitivity range, a different set of decision variables might become optimal, requiring a re-solution of the LP problem.

Shadow Prices

  • A shadow price (also known as a dual price) represents the change in the optimal value of the objective function for a one-unit increase in the right-hand side (RHS) of a binding constraint, assuming all other parameters remain constant.

  • It quantifies the marginal value of an additional unit of a scarce resource.

  • For example, if the shadow price for labor is 1616, it indicates that acquiring one additional hour of labor (if it is a binding constraint) would increase the total profit by 1616.

  • Shadow prices are valid only within a specific "range of feasibility" (or allowable increase/decrease) for the RHS of the constraint. Beyond this range, the shadow price for that resource might change.