Variable nonbasic

The variables xl9. .., xm are associated with the columns of B and are called basic variables. They are also called dependent, because if values are assigned to the nonbasic, or independent variables, xm+l,..., , then xl9..., xm can be determined immediately. In particular, if w+1,. .., are all assigned zero values then we obtain the basic solution... 

Dependent (basic) variables Independent (nonbasic) variables Constants... 

The reduced costs also indicate if there are multiple optima. Let all Cj 0 and let ck = 0 for some nonbasic variable xk. Then, if the constraints allow that variable to be made positive, no change in/results, and there are multiple optima. It is possible, however, that the variable may not be allowed by the constraints to become positive this may occur in the case of degenerate solutions. We consider the effects of degeneracy later. A corollary to these results is the following ... 

This gives the basic feasible solution (7.24), as predicted. It also indicates that the present solution although better, is still not optimal, because c2, the coefficient of 2 in the/equation, is —1. Thus we can again obtain a better solution by increasing 2 while keeping all other nonbasic variables at zero. From Equation (7.25), the current basic variables are then related to 2 by... 

Because all reduced costs for the nonbasic variables are positive, this solution is the unique minimal solution of the problem, by the corollary of the previous section. The optimum has been reached in two iterations. 

Having decided on the variable xs to become basic, we increase it from zero, holding all other nonbasic variables zero, and observe the effects on the current basic variables. By Equation (7.12), these are related to xs by... 

The basic variable xr then becomes nonbasic, to be replaced by xs. We saw from the example in Equations (7.16)-(7.28) that a new canonical form with xs replacing xr as a basic variable is easily obtained by pivoting on the term arsxs. Note that the previous operations may be viewed as simply locating that pivot term. Finding cs = min Cj < 0 indicates that the pivot term was in column s, and finding that the minimum of the ratios bt/ais for ais> 0 occurred for i = r indicates that it was in row r. 

Iteration 1. Because c2 = min(c1,c2) = — 3 < 0, x2 becomes basic. To see which variable becomes nonbasic, we compute the ratios bi/ai2 for all i such that ai2 > 0. This gives... 

For the problem given in 7.9, find the next basis. Show the steps you take to calculate the improved solution, and indicate what the basic variables and nonbasic variables are in the new set of equations. (Just a single step from one vertex to the next is asked for in this problem.)... 

If dof(x) = n — act(x) = d > 0, then there are more problem variables than active constraints at x, so the (n-d) active constraints can be solved for n — d dependent or basic variables, each of which depends on the remaining d independent or nonbasic variables. Generalized reduced gradient (GRG) algorithms use the active constraints at a point to solve for an equal number of dependent or basic variables in terms of the remaining independent ones, as does the simplex method for LPs. 

Let the starting point be (1, 0), at which the objective value is 6.5 and the inequality is satisfied strictly, that is, its slack is positive (s = 1). At this point the bounds are also all satisfied, although y is at its lower bound. Because all of the constraints (except for bounds) are inactive at the starting point, there are no equalities that must be solved for values of dependent variables. Hence we proceed to minimize the objective subject only to the bounds on the nonbasic variables x and y. There are no basic variables. The reduced problem is simply the original problem ignoring the inequality constraint. In solving this reduced problem, we do keep track of the inequality. If it becomes active or violated, then the reduced problem changes. 

To solve this first reduced problem, follow the steps of the descent algorithm outlined at the start of this section with some straightforward modifications that account for the bounds on x and y. When a nonbasic variable is at a bound, we must decide whether it should be allowed to leave the bound or be forced to remain at that bound for the next iteration. Those nonbasic variables that will not be kept at their bounds are called superbasic variables [this term was coined by Murtaugh and Saunders (1982)]. In step 1 the reduced gradient off(x,y) is... 

Because we now have reached an active constraint, use it to solve for one variable in terms of the other, as in the earlier equality constrained example. Let x be the basic, or dependent, variable, and y and s the nonbasic (independent) ones. Solving the constraint for x in terms of y and the slack s yields... 

Table El 1.4E lists the optimal solution to the linear program posed by Equations (fl)-(g). Basic and nonbasic (zero) variables are identified in the table the minimum cost is 1268.75/h. Note that EP + PP must sum to 12,000 kWh in this case the excess power is reduced to 761 kWh.

Reduced gradient method. This technique is based on the resolution of a sequence of optimization subproblems for a reduced space of variables. The process constraints are used to solve a set of variables (zd), called basic or dependent, in terms of the others, which are known as nonbasic or independent (zi). Using this categorization of variables, problem (5.3) is transformed into another one of fewer dimensions ... 

The feasibility approach FA rounds the relaxed NLP solution to an integer solution with the least local degradation by successively forcing the superbasic variables to become nonbasic based on the reduced cost information. 

This artificial system has an obvious feasible solution, namely Ui = 11, u 2 = 34, and u a = 1, with all of the other variables zero. Such a solution, in which there is one nonzero variable for each constraint, is called a basic solution of the system, and the set of nonzero variables is called a basis. The variables not in the basis are called the nonbasic variables. We want to find a basic solution that is also feasible and which satisfies the side condition that all of the artificial variables must be zero. Since all variables are nonnegative, this side condition is equivalent in our case to... 

Our procedure will be to manipulate the nonbasic variables one at a time in such a way that the sum u 2 + u a is always decreased, at the same time keeping the artificial solution feasible. Eventually this procedure will reduce the sum to zero, or else show clearly that no further reduction is possible (indicating that no real feasible solution exists). 

At each stage of the calculation, the basic variables and the sum u i + u a are expressed in terms of the nonbasic variables. This immediately makes the effects of manipulations of the nonbasic variables clear. The three constraint equations already express each basic variable only in terms of nonbasic variables, since there is only one basic variable in each equation. It remains to express (u 2 + u a) in terms of nonbasic variables only. This is done by adding together the second and third constraint equations to obtain... 

Next we must express the function (u 2 + u a) and all of the variables in the new basis in terms of the new nonbasic variables. It is particularly easy to do this for the newest basic variable x3, since the second equation contains only xa and nonbasic variables. Dividing this equation by 40, the coefficient of x3> we obtain... 

In the previous example, the technique used to reduce the artificial variables to zero was in fact Dantzig s simplex method. The linear function optimized was the simple sum of the artificial variables. Any linear function may be optimized in the same manner. The process must start with a basic solution feasible with the constraints, the function to be optimized expressed only in terms of the variables not in the starting basis. From these expressions it is decided what nonbasic variable should be brought into the basis and what basic variable should be forced out. The process is iterated until no further improvement is possible. 

It is desired to find non-negative values of xu x2, and xa that minimize this function and at the same time satisfy the constraints of the previous example. We shall begin with the basis xa, u1( and u2, which was shown to be feasible in the last example. At the end of the last example these variables were expressed in terms of the nonbasic variables Xi and x2) and so it only remains to express the new cost function in terms of these variables. Eliminating xa with the second line of the final table there gives... 

This basis is optimal, since neither of the nonbasic variables Xi and Ui can be brought into the basis without increasing the unit cost. Hence the optimal composition is xt = 0, x2 = 0.157, and xa = 0.843. The vapor pressure is 11, just at the limit, while the mean molecular weight is 2.86 above the minimum, or 36.86. The minimum unit cost is 2.84 per pound mole. 

Reaction of halides with silver nitrate to give nitrate esters has been known for years, but its synthetic application is more recent. Komblum showed that the nitrate esters derived from a-bromo ketones and esters decompose smoothly with catalytic sodium acetate in DMSO to give the a-dicarbonyl compounds in high yield. It was found unnecessary to isolate the nitrate ester after reaction of the halide with silver nitrate the solution was filtered to remove AgBr, concentrated, and added to DMSO containing catalytic sodium acetate. The method complements the others for the synthesis of a-dicarbonyl compounds since it employs nonacidic, nonbasic conditions. Unfortunately, the method gave variable results with benzyl halides. The application of the method to bromo esters other than bromoacetates was not reported. Some related oxidations are shown in equations (41) and (42), and Schemes 9 and 10. The oxidation of an iminium salt is notable. 

In the generalized reduced gradient method, the independent variables are separated into basic and nonbasic ones. There are m basic variables Xb, and (n - m) nonbasic variables x b from Eqs. (2) and (3) with the inequalities converted to equalities using slack and surplus variables. In theory, the m constraint equations could be solved for the m basic variables in terms of the n - m) nonbasic variables, i.e.. 

The names of basic and nonbasic variables are from linear programming. Similarly, the gradient of the objective function bounds and the Jacobian matrix J may be partitioned as follows ... 

---