174
Chapter 5
In this simple example one feasible solution is obtained, but one may encounter situations where there is
1) no feasible solution, 2) infinitely many solutions or 3) solutions where one or more elements of the
flux vector is infinitely large. Case 1) is found if the objective function is x = _
6
, case 2) when the
objective function is 2x+y, where infinitely many pairs (x,y) give the value 4 for the objective function.
In practice the dimensions are very large, and the network may operate in many different ways and still
fulfill the optimum criterion. If e.g. the two pathways to lysine shown in Fig. 5.7 are included, the model
cannot discriminate between them, and for overall operation of the cell it does not matter which pathway
is chosen. The flux through each of the two pathways may therefore take any arbitrary value, whereas the
sum of the two fluxes may indeed be very important for the overall operation of the network. This
illustrates the situation where a solution is found, but the resulting flux vector v is not unique.
Consequently the use of linear programming to metabolic networks can be specified as:
r = T r v
;
Z = cv
;
max(Z)
(3)
where the stoichiometric matrix is formulated such that all elements in the flux vector are non-negative,
i.e., for reversible reactions the stoichiometry is given both for the forward and the reverse reaction. Z is
the objective function. It is a linear combination of the elements in the flux vector, possibly with weight
factors for some of the fluxes, i.e. some of the fluxes may have a larger influence on the objective
function than others (many elements in the weight factor vector c may be zero). The objective function
may be the specific growth rate of the cells, in which case the operation of the network that gives the
maximum specific growth rate is identified.
Finding the optimal solution to the problem of eq. (3) may be complicated due to the potentially large
number of feasible solutions that satisfy all the constraints. However, the solution is always located at the
end (or comer) of the set of feasible solutions (a result of the linearity of both the constraints and the
objective functions), just like the situation for the simple example of Fig. 5.13. It is therefore (in
principle) possible to find the solution by, first, enumerating all solution comers and, second, evaluating
the objective function at each point of the space of feasible solutions. This approach is, however,
practically infeasible due to the very large number of comers of the cone, even for relatively small
simplex
method is often used. Applied to find a minimum the
method works as follows:: First locate a comer of the feasible set and then proceed from comer to comer
along the edges of the feasible solutions. At a given comer there are several edges to choose from, some
one moves along the edge that is guaranteed to decrease the objective function. That edge leads to a new
comer with a lower value, with no possibility of returning to any comer that yields a higher value for the
objective function. Eventually, a specific comer is reached, from which all edges lead to higher or
identical objective function values, and this comer represents the optimal solution.___________________
Example 5.11 The use of linear programming for analysis of
E. coli
metabolism
Optimal flux distributions have been obtained by linear programming for several metabolic models.
In this example, we will consider the analysis of
E. coli
metabolism as described by Varma
et al.
(1993a,b). Based on a detailed stoichiometric model for
E. coli
metabolism, the authors analyzed glucose