#math881##tex2html_wrap_inline8740# under a set of #tex2html_wrap_inline8742# linear constraints:
#math882# #tex2html_wrap_indisplay20108#
(200)
The LP problem can be more concisely represented in matrix form:
#math883# #tex2html_wrap_indisplay20110#
(201)
where
#math884# #tex2html_wrap_indisplay20112#
(202)
and the smaller or greater than sign in a vector inequality
should be understood as an element-wise relationship between
the corresponding elements of the vectors on both sides.
For example, the objective function could be the total profit,
the constraints could be some limited resources. Specifically,
#math885##tex2html_wrap_inline8744# may represent the quantities of #tex2html_wrap_inline8746# different
types of products, #math886##tex2html_wrap_inline8748# represent their unit prices,
and #tex2html_wrap_inline8750# represent the consumption of the ith resource by
the jth product, the goal is to maximize the profit
#math887##tex2html_wrap_inline8752# subject to the constraints imposed by
the limited resources #math888##tex2html_wrap_inline8754#.
Here all variables are assumed to be non-negative. If there
exists a variable that is not restricted, it can be eliminated.
Specifically, we can solve one of the constraining equations for
the variable and use the resulting expression of the variable to
replace all its appearances in the problem. For example:
#math889# #tex2html_wrap_indisplay20120#
(203)
Solving the first constraining equation for the free variable
#tex2html_wrap_inline8756#, we get #math890##tex2html_wrap_inline8758#. Substituting this into the objective
function and the other constraint, we get #math891##tex2html_wrap_inline8760#
and #tex2html_wrap_inline8762#, the problem can be reformulated as:
#math892# #tex2html_wrap_indisplay20126#
(204)
Given the primal LP problem above, we can further find its dual
problem. We first construct the Lagrangian of primal problem:
#math893# #tex2html_wrap_indisplay20128#
(205)
where #math894##tex2html_wrap_inline8764# contains the Lagrange multipliers
for the inequality constraints #math895##tex2html_wrap_inline8766#, and
#math896##tex2html_wrap_inline8768# according to Table #PolarityTable#4585>. We
define the dual function as the maximum of #tex2html_wrap_inline8770# over
#tex2html_wrap_inline8772#:
#math897# #tex2html_wrap_indisplay20135#
(206)
To find the value of #tex2html_wrap_inline8774# that maximizes #tex2html_wrap_inline8776#, we set
its gradient to zero and get:
#math898# #tex2html_wrap_indisplay20139#
(207)
Substituting this into #math899##tex2html_wrap_inline8778# we get:
#math900##tex2html_wrap_inline8780#, which is the upper bound of
#tex2html_wrap_inline8782#, under the constraint that
#math901##tex2html_wrap_inline8784# so that
#math902##tex2html_wrap_inline8786# contributes negatively
to #tex2html_wrap_inline8788# (as #tex2html_wrap_inline8790#):
#math903# #tex2html_wrap_indisplay20148#
(208)
This upper bound needs to be minimized with respect to #tex2html_wrap_inline8792#,
to become the tightest upper bound, i.e., the original primal
problem of maximization in Eq. (#LPmax#4654>) has now been converted
into the following dual problem of minimization:
#math904# #tex2html_wrap_indisplay20151#
(209)
Following the same approach, we can also find the dual of a
minimization primal problem:
#math905#
| #tex2html_wrap_indisplay20153# |
#tex2html_wrap_indisplay20154# |
#tex2html_wrap_indisplay20155# |
|
| |
#tex2html_wrap_indisplay20156# |
#tex2html_wrap_indisplay20157# |
(210) |
Moreover, we can show that the dual of a dual problem is the
original primal problem.
If either the primal or the dual is feasible and bounded, so is
the other, and they form a strong duality, the solution #tex2html_wrap_inline8794# of
the dual problem is the same as the solution #tex2html_wrap_inline8796# of the primal
problem. Also, as the primal and dual problems are completely
symmetric.
An inequality constrained LP problem can be converted to an
equality constrained problem by introducing <#4722#>slack variables<#4722#>:
#math906# #tex2html_wrap_indisplay20161#
(211)
so that it can be reformulated to take the <#4727#>standard form<#4727#>:
#math907# #tex2html_wrap_indisplay20163#
(212)
We further redefine the following:
Now the LP problem can be expressed in the standard form (original form
on the left, with #tex2html_wrap_inline8828# and #tex2html_wrap_inline8830# redefined on the right):
#math916# #tex2html_wrap_indisplay20186#
(215)
An LP problem can be viewed geometrically. If normalize
#tex2html_wrap_inline8832# so that #tex2html_wrap_inline8834#, then the objective function
#math917##tex2html_wrap_inline8836# becomes the projection of #tex2html_wrap_inline8838#
onto #tex2html_wrap_inline8840#. Each of the #tex2html_wrap_inline8842# equality constraints in
#math918##tex2html_wrap_inline8844# represents a hyper-plane in the N-D
vector space perpendicular to its normal direction
#math919##tex2html_wrap_inline8846#:
#math920# #tex2html_wrap_indisplay20196#
(216)
Also, each of the #tex2html_wrap_inline8848# non-negativity conditions #tex2html_wrap_inline8850# in
#math921##tex2html_wrap_inline8852# corresponds to a hyper-plane perpendicular
to the jth standard basis vector #tex2html_wrap_inline8854#. In general, in an
N-D space, if none of the hyper-planes is parallel to any others,
then no more than #tex2html_wrap_inline8856# hyper-planes intersect at one point. For
example, in a 2-D or 3-D space, two straight lines or three
surfaces intersect at a point. Here for the LP problem in the
N-D space, the total number of intersection points formed by
the #tex2html_wrap_inline8858# hyper-planes is
#math922# #tex2html_wrap_indisplay20204#
(217)
The polytope enclosed by these #tex2html_wrap_inline8860# hyper-planes is called the
feasible region, in which the optimal solution must lie. The
vertices of the polytopic feasible region are a subset
of the #tex2html_wrap_inline8862# intersections.
<#4848#>Fundamental theorem of linear programming<#4848#>
The optimal solution #tex2html_wrap_inline8864# of a linear programming problem
formulated above is either a vertex of the polytopic feasible
region #tex2html_wrap_inline8866#, or lies on a hyper-surface of the polytope, on which
all points are optimal solutions.
<#20209#>Figure<#20209#> 2.23:
<#20210#>Fundamental Theorem of Linear Programming<#20210#>
| [width=70mm]<#4851#>figures/LPtheorem.eps<#4851#> |
<#4855#>Proof:<#4855#>
Assume the optimal solution #math923##tex2html_wrap_inline8868# is interior to
the polytopic feasible region #tex2html_wrap_inline8870#, then there must exist some
#tex2html_wrap_inline8872# such that the hyper-sphere of radius #tex2html_wrap_inline8874#
centered at #tex2html_wrap_inline8876# is inside #tex2html_wrap_inline8878#. Evaluate the objective
function at a point on the hyper-sphere
#math924# #tex2html_wrap_indisplay20219#
(218)
we get
#math925#
| #tex2html_wrap_indisplay20221# |
#tex2html_wrap_indisplay20222# |
#tex2html_wrap_indisplay20223# |
|
| |
#tex2html_wrap_indisplay20224# |
#tex2html_wrap_indisplay20225# |
(219) |
i.e., #tex2html_wrap_inline8880# cannot be the optimal solution as assumed. This contradiction
indicates that an optimal solution #tex2html_wrap_inline8882# must be on the surface of #tex2html_wrap_inline8884#,
either at one of its vertices or on one of its surfaces. Q.E.D.
Based on this theorem, the optimization of a linear programming problem
could be solved by exhaustively checking each of the #tex2html_wrap_inline8886# intersections
formed by #tex2html_wrap_inline8888# of the #tex2html_wrap_inline8890# hyper-planes to find (a) whether it is feasible
(satisfying all #tex2html_wrap_inline8892# constraints), and, if so, (b) whether the objective
function #tex2html_wrap_inline8894# is maximized at the point. Specifically, we choose
#tex2html_wrap_inline8896# of the #tex2html_wrap_inline8898# equations for the the constraints and solve this N-equation
and N-unknown linear system to get the intersection point of #tex2html_wrap_inline8900# corresponding
hyper-planes. This brute-force method is most straight forward, but the
computational complexity is high when #tex2html_wrap_inline8902# and #tex2html_wrap_inline8904#, and therefore #tex2html_wrap_inline8906#,
become large.
<#4889#>Example:<#4889#>
#math926# #tex2html_wrap_indisplay20241#
where
#math927# #tex2html_wrap_indisplay20243#
<#20244#>Figure<#20244#> 2.24:
<#20245#>Simplex Algorithm Example (Original Problem)<#20245#>
| [width=100mm]<#4937#>figures/SimplexEx0.eps<#4937#> |
This problem has #tex2html_wrap_inline8908# variables with the same number of non-negativity
constraints and #tex2html_wrap_inline8910# linear inequality constraints. The #tex2html_wrap_inline8912# straight
lines form #math928##tex2html_wrap_inline8914# intersections, out of which 5 are the
vertices of the polygonal feasible region satisfying all constraints.
The value of the objective function #math929##tex2html_wrap_inline8916#
is proportional to the projection of the 2-D variable vector
#math930##tex2html_wrap_inline8918# onto the coefficient vector #math931##tex2html_wrap_inline8920#.
The goal of this linear programming problem is to find a point
#tex2html_wrap_inline8922# inside the polygonal feasible region with maximum
#math932##tex2html_wrap_inline8924# (the projection of #tex2html_wrap_inline8926# onto
vector #tex2html_wrap_inline8928# if #tex2html_wrap_inline8930#). Geometrically, this can be
understood as to push the hyper-plane #math933##tex2html_wrap_inline8932#, here a
line in 2-D space, its normal direction #tex2html_wrap_inline8934#, away from the
origin along to eventually arrive at the vertex of the polytopic
feasible region farthest away from the origin.
This LP problem can be converted into the standard form:
#math934# #tex2html_wrap_indisplay20262#
Listed in the table below are the #math935##tex2html_wrap_inline8936# intersections
#tex2html_wrap_inline8938#, called basic solutions, together with the corresponding
slack variables #math936##tex2html_wrap_inline8940# and the objective function value
#tex2html_wrap_inline8942# (proportional to the projection of #tex2html_wrap_inline8944# onto
#tex2html_wrap_inline8946#). We see that out of the ten basic solutions, five are
feasible (vertices of the polytopic feasible region) with all
#tex2html_wrap_inline8948# variables taking non-negative values, while the remaining
five are not feasible, as some of the slack variables are negative,
and thereby violating the constraints. Out of the five feasible
solutions, the one at #math937##tex2html_wrap_inline8950# is optimal with maximum
objective function value
#math938##tex2html_wrap_inline8952#.
#math939# #tex2html_wrap_indisplay20273#
This primal maximization problem can be converted into the dual
minimization problem:
#math940# #tex2html_wrap_indisplay20275#
The five planes, #tex2html_wrap_inline8954# from the constraining inequalities, and #tex2html_wrap_inline8956#
for the non-negative constraints #tex2html_wrap_inline8958#, #tex2html_wrap_inline8960#, and #tex2html_wrap_inline8962#
for the three variables, form #tex2html_wrap_inline8964# intersection points:
#math941# #tex2html_wrap_indisplay20283#
We see that at the feasible point #tex2html_wrap_inline8966#, the dual function
#math942##tex2html_wrap_inline8968# is minimized to be #tex2html_wrap_inline8970#, the same
as the maximum of the primal function #math943##tex2html_wrap_inline8972# at #tex2html_wrap_inline8974#.
<#20289#>Figure<#20289#> 2.25:
<#20290#>Simplex Algorithm Example (Dual Problem)<#20290#>
| [width=90mm]<#5045#>figures/LPdual1.eps<#5045#> |
<#5049#>Homework:<#5049#>
Develop the code to find all #tex2html_wrap_inline8976# intersections formed by
#tex2html_wrap_inline8978# given hyper-planes in an N-D space in terms of their
equations #math944##tex2html_wrap_inline8980#
and #math945##tex2html_wrap_inline8982#, identify which of them are vertices of
the polytope surrounded by these hype-planes, and find the vertex
corresponding to the optimal solution that maximizes
#math946##tex2html_wrap_inline8984# for a given #tex2html_wrap_inline8986#.