Intro to Linear Programming

Introduction to Linear Programming

• Linear Programming (LP) is a mathematical technique used to optimize a linear objective function subject to linear constraints.
• It's widely applied in economics, engineering, and logistics for effective decision-making.

Components of a Linear Programming Problem

• Objective Function: A linear function that needs to be maximized or minimized, represented as:
  • Maximize: Z = c1x1 + c2x2 + ... + cnxn
• Constraints: A set of linear inequalities that define the limits of the decision variables, expressed as:
  • a11x1 + a12x2 + ... + a1nxn ≤ b1
  • a21x1 + a22x2 + ... + a2nxn ≤ b2
  • ...
  • am1x1 + am2x2 + ... + amnxn ≤ bm
• Decision Variables: The variables that will be determined to achieve the optimal value of the objective function, such as x1, x2, ..., xn.
• Non-Negativity Constraints: Requires the decision variables to be non-negative, meaning xi ≥ 0 for all i.

Example Formulation of a Linear Programming Problem

• Problem: A company produces two types of products, A and B. Producing one unit of A takes 2 hours of labor and 1 hour of raw material. Producing one unit of B takes 3 hours of labor and 0.5 hours of raw material. The company has 120 hours of labor and 40 hours of raw material available. Product A yields a profit of $20 per unit, and product B yields $30 per unit. The goal is to find the number of units for each product to maximize profit.
• Decision Variables:
  • x1: Number of units of product A to produce
  • x2: Number of units of product B to produce
• Objective Function:
  • Maximize: Z = 20x1 + 30x2 (Total Profit)
• Constraints:
  • 2x1 + 3x2 ≤ 120 (Labor Constraint)
  • 1x1 + 0.5x2 ≤ 40 (Raw Material Constraint)
  • x1, x2 ≥ 0 (Non-Negativity Constraints)

Solving Linear Programming Problems Graphically

• Graphical Solution: A method to solve LP problems with two decision variables.
• Involves graphing the constraints on a Cartesian plane.
• The feasible region is the area where all constraints are satisfied.
• The optimal solution is found at one of the vertices of the feasible region.
• Steps:
  • Graph the Constraints: Represent each constraint as a straight line on the Cartesian plane.
  • Identify the Feasible Region: Determine the area where all constraints are satisfied.
  • Evaluate the Objective Function at the Vertices: Calculate the value of the objective function at each vertex of the feasible region.
  • Find the Optimal Solution: Select the vertex that maximizes (or minimizes) the objective function.

Simplex Method

• Simplex Method: An iterative algorithm used to solve LP problems with any number of decision variables.
• Moves from one vertex to another in the feasible region.
• Improves the value of the objective function at each step until the optimal solution is reached.
• Steps:
  • Convert to Standard Form: Transform the problem so all constraints are equalities and all variables are non-negative.
  • Create the Initial Simplex Tableau: Construct a table that represents the problem in matrix form.
  • Select the Entering Variable: Identify the non-basic variable with the most negative coefficient in the objective function row.
  • Select the Leaving Variable: Determine the basic variable to leave the basis using the minimum ratio test.
  • Perform Pivot Operations: Update the Simplex tableau so the entering variable becomes basic, and the leaving variable becomes non-basic.
  • Repeat Steps 3-5: Continue iterating until all coefficients in the objective function row are non-negative.
  • Identify the Optimal Solution: Read the values of the decision variables in the final Simplex tableau.

Sensitivity Analysis

• Sensitivity analysis helps determine how changes in the problem parameters (objective function coefficients, constraint constants) affect the optimal solution and its value.
• This helps evaluate the robustness of the solution and informs decision-making.
• Key Questions:
  • How does the optimal solution change if the objective function coefficients vary?
  • How does the optimal solution change if the constraint constants (right-hand side values) vary?
  • What is the range of variation for each parameter within which the current optimal solution remains optimal?

Duality

• Every LP problem (the primal) has an associated dual problem.
• The solution of the dual problem gives valuable information about the primal, such as shadow prices of resources.
• Relationships Between Primal and Dual:
  • If the primal is a maximization problem, the dual is a minimization problem, and vice versa.
  • The objective function coefficients of the primal become the constraint constants of the dual.
  • The constraints of the primal become the variables of the dual.

Software for Linear Programming

• Software programs that simplify the resolution of LP problems:
  • Solver in Excel: An Excel add-in for solving optimization problems.
  • Gurobi: A high-performance commercial optimizer.
  • CPLEX: An IBM commercial optimizer.
  • GLPK: An open-source optimizer.
  • LINGO: A mathematical modeler and optimizer.
• These programs help formulate LP problems, solve them efficiently, and perform sensitivity analysis.

Prérequis

• Exponential function
• Differentiation

Definition of the Natural Logarithm Function

• The natural logarithm function, denoted as ln, is defined on ]0; +∞[ as the inverse of the exponential function.
• For all x ∈ ]0; +∞[ and all y ∈ ℝ, y = ln(x) ⇔ x = e^y.

Examples of Natural Logarithms

• ln(1) = 0 because e^0 = 1.
• ln(e) = 1 because e^1 = e.
• ln(√e) = 1/2 because e^(1/2) = √e.

Remark

• For every real number x, ln(e^x) = x, and for every real number x > 0, e^(ln(x)) = x.

Algebraic Properties

• For all strictly positive real numbers a and b, and for every integer n:
  • ln(ab) = ln(a) + ln(b)
  • ln(1/a) = -ln(a)
  • ln(a/b) = ln(a) - ln(b)
  • ln(a^n) = n * ln(a)
  • ln(√a) = (1/2) * ln(a)

Function Study

• Limits:
  • lim x→0+ ln(x) = -∞
  • lim x→+∞ ln(x) = +∞

Dérivée

• The ln function is differentiable on ]0; +∞[ and its derivative is defined by:
  • ln'(x) = 1/x

Variations

• The ln function is strictly increasing on ]0; +∞[

Tableau de variations

Graphical Representation

• The graph of y = ln(x) starts from negative infinity as x approaches 0 from the right, crosses the x-axis at x = 1 (where y = 0), and slowly increases towards positive infinity as x increases.
• The function is not defined for x ≤ 0 due to the vertical asymptote at x = 0.