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
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.
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.)
Level Sets of the Objective Function
Visualizing (cont.)
Functional Constraints
Visualizing (cont.)
Solution
The Simplex Algorithm
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.)
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
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