Biochemical Reaction Networks
173
Note 5.7 The concept of linear programming
To illustrate the concept of linear programming consider a very simple system with only two variables, .t
andy related through a constraint (which can be interpreted as a metabolic model):
2x + y = 4
(1)
The constraint specifies that the solution lies on the straight line AB (see Fig. 5.13), which in this case
represents the null space of the system. In addition to eq. (1), another representation common in linear
programming problems is that all variables (in this casex and y) are required to be nonnegative, i.e.
x -
0
and
y -
0
(
2
)
The elements of the flux vector v may be either positive or negative, and in order to apply linear
programming it is therefore necessary to consider reactions in both directions. Thus, for all reactions that
may operate as reversible reactions in the network both a forward and a backward reaction has to be
included in the model. Hereby it is possible to apply the constraint that all fluxes (or all elements of the
flux vector v) must be positive. With the constraints x - 0 and y - 0 the solutions of the preceding
problem are restricted to those lying in the positive quadrant of
(x,y)
space.
The next step is to identify a unique solution by applying the requirement that
the solution maximizes or
minimizes a certain cost (or objective) function.
For example, if we want to maximize the objective
function 2x + 3y, then the problem is to find a solution that lies on the line AB and at the same time
maximizes this function. A family of cost lines is shown in Fig. 5.13. The line that yields the largest
value for the objective function and at the same time satisfies the constraint is given by 2x + 3y = 12. It
intersects with the line AB at x = 0 and y = 4.
Figure 5.13 The concept of linear programming. The solution to the problem is constrained to be on the
line AB in the first quadrant, and some solutions indicated by the vector v are indicated. The objective
function consists of a family of lines (of which three are shown as broken lines). The line that maximizes
the objective function intercepts the constraint line AB at (x,y) = (0,4), which represents the solution for
this optimization problem.