Linear Programming: In-depth Notes

Introduction to Linear Programming (LP)

• Linear programming (LP) is a mathematical modeling technique popular for planning and decision-making in resource allocation.
• It involves creating models to help managers make the most effective use of limited resources.

Requirements of a Linear Programming Problem

• LP problems share four common characteristics:
  • Objective Function: Aim to maximize or minimize some quantity.
  • Constraints: There are limitations or restrictions on resources.
  • Decision Variables: Multiple courses of action available.
  • Linear Relationships: All equations/inequalities must be linear.

LP Properties and Assumptions

• Properties of linear programs include:
  1. One Objective Function: There is one main goal (max profit/min cost).
  2. Constraints: May have one or many constraints affecting the outcome.
  3. Alternative Courses of Action: Different ways to achieve the objective exist.
  4. Linear Functions: Both objective and constraints must be linear (involving no exponents or products of decision variables).
  5. Certainty: All coefficients in analogies are constants (assuming certainty in variables).
  6. Divisibility: Decision variables can take on fractional values.
  7. Nonnegative Variables: Decision variables must be zero or positive.

Formulating LP Problems

• Steps to develop LP models:
  1. Understand the Problem: Clearly define the managerial issue at hand.
  2. Identify Objectives & Constraints: Determine what needs to be maximized or minimized and the constraints involved.
  3. Define Decision Variables: Specify what will be controlled or decided in the model.
  4. Mathematical Expressions: Create mathematical expressions using decision variables for the objective function and constraints.

Example: Flair Furniture Company Problem

• Context: Flair Furniture creates tables and chairs and seeks to maximize profits.
• Data:
  • Each table (T) takes 4 hours of carpentry and 2 hours for painting; profit = $70.
  • Each chair (C) takes 3 hours of carpentry and 1 hour for painting; profit = $50.
  • Total carpentry hours available = 240; painting hours = 100.
• Objective Function: Maximize profit = 70T + 50C
• Constraints:
  1. Carpentry Time: 4T + 3C \leq 240
  2. Painting Time: 2T + C \leq 100
  3. Nonnegative: T, C \geq 0

Graphical Solution to an LP Problem

• Graphical Method: Effective for small LP problems with two decision variables:
  • Graph the constraints to find the feasible region where all constraints overlap.
  • The feasible region is determined by plotting each constraint.

Isoprofit Line Solution Method

• Isoprofit Line: Graph the objective function and move it to maximize profit.
  • Last point touched in the feasible region provides the optimal solution.
• Example with isoprofit line for various profit levels shows maximum profit point.

Corner Point Solution Method

• Evaluates profit at each vertex (corner point) of the feasible region to find optimal profit.
  • Mathematical analysis of intersection points (solve simultaneous equations) determines corner points.

Measuring Efficiency with Slack and Surplus

• Slack: Unused resources in a ≤ constraint measured as:
  • Slack = (Available Resource) - (Used Resource)
• Surplus: Allocated beyond a minimum requirement in a ≥ constraint.

Utilization of Computer Software

• Organizations use software such as Excel Solver for complex LP problems to automate solutions.

Special Cases in LP Problems

• No Feasible Solution: Scenario where no solution meets constraints.
• Unboundedness: Occurs when infinitely better solutions exist without constraint.
• Redundancy: Constraints do not affect the feasible solution; can be ignored.
• Alternate Optimal Solutions: More than one optimal solution exists, allowing flexibility.

Sensitivity Analysis

• Examines how the optimal solution changes with variations in the parameters or constraints graphical or analytically.
  • Useful for understanding stability and the impact of changes in resources or relationships.