Model Predictive control
From power plants to sugar refining, model predictive control (MPC) schemes have established themselves as the preferred control strategies for a wide variety of processes. The second edition of Model Predictive Control provides a thorough introduction to
- PDF / 228,151 Bytes
- 24 Pages / 439.37 x 666.14 pts Page_size
- 34 Downloads / 269 Views
The Simplex method [129] is the algorithm most used for solving linear programming problems, such as the ones appearing when using a 1-norm MPC. The Simplex algorithm finds successive and better feasible solutions at the extreme points of the feasible region until it stops, in a finite number of steps, either at the optimum or finds that the optimal solution is not bound by the feasible region. This appendix is dedicated to revising the basic ideas behind the Simplex method.
A.1 Equality Constraints The problem of minimizing a linear function subject to equality constraints will be considered first Minimize ct x subject to Ax = b (A.1) x≥0 where A is a q × p real matrix with q < p and full rank. If the equality constraint equation is multiplied by a matrix T and the columns of A and corresponding components of x are interchanged in such t a way that T A = [Iq×q N ] and T b = b, the point x = [xtb xn ]t = [b 0] is a basic feasible solution. The components xb are called basic variables whereas the remaining components (corresponding to N ) are called nonbasic variables. Note that this can be done by applying elementary row transformations to matrix A and interchanging the columns of A (and the corresponding x variables) to take matrix A to the form [I N ]. If the same transformations are applied to I and b, matrix T and vector b are obtained. The objective function takes the value z0 = ctb xb + ctn xn = ctb xb . The basic variables can be expressed as a function of the nonbasic variables from the transformed constraint equation: xb = b − N x n
382
A Revision of the Simplex Method
by substituting in the cost function z = ct x = ctb (b − N xn ) + ctn xn = z0 + (ctn − ctb N )xn As xn ≥ 0, the objective function decreases if any component of (ctn − ctb N )i is negative and the corresponding nonbasic variable xni increases. This gives an indication of how to obtain a more feasible solution and is the basic idea behind the algorithm. The problem is determining which of the nonbasic variables should be increased (become basic) and which of the basic variables should leave the basis. This is done as follows: 1. Find an initial basic solution. 2. 3. 4. 5.
6.
7.
xtb xtn N b Form the following tableau: xb I J 0 cn − ctb N ctb b If cn − ctb N ≥ 0 then STOP, the actual basic solution is optimal. Choose one of the negative elements (say, the j th ) of row cn − ctb N (the most negative is usually chosen). Choose i such that the ratio bi /Nij is the minimum for all Nij > 0. If there are no nonnegative elements in that column of the tableau, the problem is not bounded. Make xnj a basic variable and xbi a non basic variable by pivoting: a) Divide the ith row of the tableau by Nij . b) Make zero the remaining elements of the j th column of the nonbasic variable block by multiplying the resulting the ith row by Nkj and subtracting it from the k th row. Go to step 2.
A.2 Finding an Initial Solution The Simplex method starts from an initial feasible extreme point. An initial point can be found by applying elementary row transformatio
Data Loading...
