Constrained Quadratic Optimisation: 3.
Setting up the ‘super’-problem
[this page | pdf | references | back links]
Return to
Abstract and Contents
Next
page
3. Setting up the
‘super’-problem
To set up the superset of the original problem as described
in Solving
the canonical problem, we multiply through each row in the above tableau
(both left and right hand sides) by 
if the
relevant element of 
or 
is
negative. This means that the right-hand side of the tableau is all now
non-negative. Simultaneously we introduce a further series of ‘artificial’
variables 
, all
elements of which are 
, the first 
elements
of which, 
, are
artificial variables corresponding to the 
and the
remaining 
elements are
artificial variables corresponding to the 
. To be more
precise, if we want the speediest algorithm, we only introduce only such elements
of these variables that are needed to achieve a starting feasible solution.
The starting solution is then given by 
and:
The starting ‘basic’ variables, i.e. those whose opening
values are greater than zero are each of the 
and
whichever of the and the 
is non-zero
in the above formulae.
The complete starting tableau is then:
Subject to 
for 
,
and 
where
means
multiply through relevant row of the matrix by if
, 
means
multiply through relevant row of the matrix by if
and 
is the 
identity
matrix with each 1 replaced by a zero if the corresponding value of 
is greater
than zero.
N.B. We have ignored for the purposes of this discussion the
possibility that any of the entries on the right-hand side of the tableau are
identically zero. This degenerate case can be handled by adding a very small
number to make them positive.
We need to know which variables ‘correspond’ to each other
(i.e. appear jointly in the constraints , although
these correspondences do not change as the iteration progresses.
In addition to the Tableau, which is an 
array we
also need to keep track of the following as the iteration proceeds:
Two rows:
(a) BasicRow,
indicates with, say, a 1 whether the variable in question is ‘basic’
(b) ObjectiveRow,
initially calculated as:
Two columns:
(c) SolutionColumn,
contains the current feasible solution, i.e. the right hand side of the above
tableau ‘equation’; and
(d) BasicColumn,
contains integers indicating to which variables the entries in the SolutionColumn
currently apply (and thus which variables are basic, so there is some overlap
here with BasicRow). BasicColumn starts as:
NAVIGATION LINKS
Contents | Prev | Next