Linear programming is a powerful optimization technique used to find the best solution within constraints. Standard form and variations are crucial for understanding how to structure these problems, allowing us to apply efficient solving methods and analyze results effectively.

Mastering different formulations helps us tackle real-world optimization challenges. By converting problems to standard form, we can use well-established algorithms, while understanding variations allows us to handle diverse scenarios and improve computational efficiency.

Standard form of linear programming

Components and structure

• Linear objective function maximized subject to linear equality constraints and non-negative decision variables
• Objective function expressed as linear combination of decision variables ($Z = c_1x_1 + c_2x_2 + ... + c_nx_n$)
  • $c_i$ represents coefficients
  • $x_i$ represents decision variables
• Constraints expressed as linear equations ($a_1x_1 + a_2x_2 + ... + a_nx_n = b_i$)
  • $a_i$ represents coefficients
  • $b_i$ represents right-hand side constant
• All decision variables required to be non-negative ($x_i \geq 0$ for all $i$)

Matrix notation and dimensionality

• Matrix representation: maximize $c^Tx$, subject to $Ax = b$ and $x \geq 0$
  • $c$ and $x$ are n-dimensional vectors
  • $A$ is an $m \times n$ matrix
  • $b$ is an m-dimensional vector
• Dimensionality defined by number of constraints ($m$) and decision variables ($n$)
  • Determines size of constraint matrix and vectors
  • Impacts complexity of solving the linear program (larger dimensions generally require more computational resources)

Objective function and constraints

Objective function characteristics

• Mathematical expression representing goal to be optimized (maximized or minimized)
• Coefficients represent contribution of each decision variable to overall objective value
  • Example: In a production problem, coefficients might represent profit per unit of each product
• Linear combination of decision variables
  • Example: Maximize $Z = 3x_1 + 2x_2 + 5x_3$ (profit from three products)

Constraint types and properties

• Mathematical inequalities or equations limiting feasible region of decision variables
• Slack and surplus variables convert inequality constraints to equality constraints
  • Slack variables for $\leq$ constraints ($x_1 + x_2 \leq 10$ becomes $x_1 + x_2 + s = 10$, where $s \geq 0$)
  • Surplus variables for $\geq$ constraints ($x_1 + x_2 \geq 10$ becomes $x_1 + x_2 - s = 10$, where $s \geq 0$)
• Right-hand side (RHS) represents available resources or limitations
  • Example: In a resource allocation problem, RHS might represent available machine hours or raw materials
• Binding constraints directly affect optimal solution
  • Example: If a constraint is satisfied exactly at the optimal solution, it is binding
• Non-binding constraints do not impact optimal solution value
  • Example: If a constraint is satisfied with slack at the optimal solution, it is non-binding

Feasible region

• Defined by intersection of all constraints
• Represents set of all possible solutions satisfying all constraints simultaneously
• Geometric interpretation in two-dimensional problems
  • Example: Feasible region forms a polygon in the $x_1$-$x_2$ plane for a problem with two decision variables

Converting linear programming forms

Canonical form and standard form conversion

• Canonical form maximizes objective function with all constraints in $\leq$ form and non-negative variables
• Convert minimization to maximization by multiplying objective function by -1
  • Example: min $Z = 2x_1 + 3x_2$ becomes max $Z' = -2x_1 - 3x_2$
• Convert inequality constraints to equality constraints using slack or surplus variables
  • Example: $2x_1 + x_2 \leq 10$ becomes $2x_1 + x_2 + s_1 = 10$, where $s_1 \geq 0$
• Handle unrestricted variables by replacing with difference of two non-negative variables
  • Example: $x = x^+ - x^-$, where $x^+ \geq 0$ and $x^- \geq 0$

Constraint manipulation and variable substitution

• Convert $\geq$ constraints to $\leq$ constraints by multiplying both sides by -1
  • Example: $x_1 + 2x_2 \geq 5$ becomes $-x_1 - 2x_2 \leq -5$
• Multiple steps may be required for complete conversion to standard form
  • Variable substitution (handling unrestricted variables)
  • Constraint manipulation (converting inequalities)
  • Introduction of auxiliary variables (slack and surplus)

Dual form derivation

• Derive dual form from primal form by transposing constraint matrix
• Exchange roles of objective function coefficients and right-hand side values
• Example: Primal max $Z = c^Tx$ subject to $Ax \leq b$ becomes dual min $W = b^Ty$ subject to $A^Ty \geq c$
• Useful for sensitivity analysis and alternative solution methods

Impact of variations in formulations

Computational efficiency and model complexity

• Different formulations of same problem lead to varying computational efficiency
• Choice of decision variables affects complexity and interpretability
  • Example: Modeling production as individual units vs. batches can change problem size
• Adding redundant constraints may not change optimal solution but impacts algorithm efficiency
  • Example: Adding $x_1 + x_2 \leq 15$ when $x_1 \leq 5$ and $x_2 \leq 10$ already exist

Numerical considerations and special structures

• Scaling of variables and constraints improves numerical stability and solution method performance
  • Example: Changing units from thousands to millions to reduce coefficient magnitudes
• Special structures exploited for efficient solution techniques
  • Network flow problems solved using specialized algorithms (Ford-Fulkerson for max flow)
  • Transportation problems utilizing specific solution methods (Northwest Corner Method for initial feasible solution)

Sensitivity analysis and degeneracy

• Sensitivity analysis examines how changes in problem parameters affect optimal solution
  • Example: Determining how much a resource constraint can be relaxed before changing the optimal solution
• Variations in formulation impact problem degeneracy
  • Multiple optimal solutions (alternative optimal solutions exist)
  • Basic feasible solutions with zero-valued basic variables
  • Example: In a diet problem, multiple food combinations may achieve the same minimum cost while meeting nutritional requirements