- Forward


Linear Programming
A Brute Force Approach


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Background
Back SMYC Forward
  • A Problem You've Seen:
    • Minimize/maximize a function of one (or more) variable(s)
  • A Problem You May Have Seen:
    • Minimize/maximize a function of one or more variables subject to one or more constraints
Background (cont.)
Back SMYC Forward
  • Solving an Unconstrained Problem:
    • Take the derivative (or partials derivatives), set it (them) to zero, and solve
  • Solving the Constrained Problem:
    • Introduce Lagrange multipliers and treat it as an unconstrained problem
Background (cont.)
Back SMYC Forward
  • What You're Never Told:
    • This only works (in closed form) when the derivatives turn out to be "simple"
  • What About Other Problems:
    • Numerical algorithms exist that depend on the form of the problem
Linear Programming/Optimization
Back SMYC Forward
  • The Problem:
    • Minimize/maximize a linear function of \(n\) decision variables subject to \(m\) functional constraints (and \(n\) non-negativity constaints)
  • The Canonical Form:
    • \(\text{max } Z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n\)
    • subject to the constraints
    • \( \begin{array}{c c c c c c c c c} a_{11}x_1 & + & a_{12}x_2 & + & \cdots & + & a_{1n}x_n & \leq & b_1 \\ a_{21}x_1 & + & a_{22}x_2 & + & \cdots & + & a_{2n}x_n & \leq & b_2 \\ & & & \vdots \\ a_{m1}x_1 & + & a_{m2}x_2 & + & \cdots & + & a_{mn}x_n & \leq & b_m \\ \end{array} \)
    • and
    • \(x_1 \geq 0, x_2 \geq 0, \ldots, x_n \geq 0\)
Some Terminology
Back SMYC Forward
  • Decision Variables:
    • The variables whose values are being chosen (i.e., the \(x\) variables in the canonical form)
  • Feasible Solution:
    • Values for the decision variables that satisfy all of the constraints
  • Optimal Solution:
    • A "best" possible (in terms of the objective function) feasible solution
An Example with Two Decision Variables
Back SMYC Forward
  • The Setting:
    • A commercial bakery with three plants that makes two kinds of cookies. Chocolate chip cookies earn a profit of 3 (thousand) dollars per truckoad, and peanut butter cookies earn a profit of 5 (thousand) dollars per truckload. Plant 1 can only produce chocolate chip cookies, plant 2 can only produce peanut butter cookies, and plant 3 can produce both. The three plants require different amounts of resources and have different capacities.
  • The Optimization Problem:
    • \( \begin{array}{l l l l l l} \text{max} & 3 x_1 & + & 5 x_2 \\ \text{s.t.} & 1 x_1 & & & \leq & 4 \\ & & & 2 x_2 & \leq & 12 \\ & 3 x_1 & + & 2 x_2 & \leq & 18 \\ & x_1 & & & \geq & 0 \\ & & & x_2 & \geq & 0 \\ \end{array} \)
Visualizing Problems with Two Decision Variables
Back SMYC Forward
  • The Objective Function:
    • We could plot \(Z\) as a function of \(x_1\) and \(x_2\) in three dimensions, but we can also plot the level sets in two dimensions
  • The Constraints:
    • Ignoring the inequality, each constraint can be plotted as a line in two dimensions
Visualizing (cont.)
Back SMYC Forward

Level Sets of the Objective Function

linear-program_level-sets
Visualizing (cont.)
Back SMYC Forward

Functional Constraints

linear-program_constraints
Visualizing (cont.)
Back SMYC Forward

Solution

linear-program_solution
The Simplex Algorithm
Back SMYC Forward
  • An Important Observation:
    • An optimal solution must be a corner-point feasible solution (i.e., a feasible solution that does not lie on any line segment connecting two other feasible solutions)
  • The Terminology:
    • Each is a solution of solving \(n\) equations (out of \(m + n\)) in \(n\) unknowns
  • An Unfortunate Fact:
    • There can be as many as \(\frac{(m + n)!}{m!n!}\) such solutions
The Simplex Algorithm (cont.)
Back SMYC Forward
  • The Approach:
    • Move from one corner-point feasible solution to an adjacent "better" corner-point feasible solution
  • The Stopping Rule:
    • Stop when there is no "better" adjacent point
A Brute Force Algorithm
Back SMYC Forward
  • The Approach:
    • Evaluate the objective function at all corner-points and choose the feasible corner-point with the best objective function value
  • Practicality of this Approach:
    • For \(n=2\) and \(n=3\) there are 10 such points
    • For \(n=50\) and \(m=50\) there are \(10^{29}\) such points
What's Left to the Brute Force Approach?
Back SMYC Forward
  • Lines:
    • Understanding how to represent them
  • Intersections:
    • How to find them
There's Always More to Learn
Back -