10.2.1 Parametrizing the Objective Function

Given the above optimal basic feasible solution, let us replace by where θ is a nonnegative scalar parameter and S is a specified, albeit arbitrary, (n × 1) vector that determines a given direction of change in the coefficients c_j, j = 1, …, n. In this regard, the c^*_j, j = 1, …, n, are specified as linear functions of the parameter θ. Currently, or If C^* is partitioned as

where S_B (S_R) contains the components of S corresponding to the components of within C_B(C_R), then, when C^* replaces . The revised optimality condition becomes

(10.1)

or, in terms of the individual components of (10.1),

(10.1.1)

(Note that the parametrization of f affects only primal optimality and not primal feasibility since X_B is independent of .) Let us now determine the largest value of θ (known as its critical value, θ_c) for which (10.1.1) holds. Upon examining this expression, it is evident that the critical value of θ is that for which any increase in θ beyond θ_c makes at least one of the values negative, thus violating optimality.

How large of an increase in θ preserves optimality? First, if or the θ can be increased without bound while still maintaining the revised optimality criterion since, in this instance, (10.1.1) reveals that Next, if for some particular value of j, then for

Hence, the revised optimality criterion is violated when θ > θ_c for some nonbasic variable x_Rj. Moreover, if for two or more nonbasic variables, then

(10.2)

So if θ increases and the minimum in (10.2) is attained for j = k, it follows that or With the case of multiple optimal basic feasible solutions obtains, i.e. the current basic feasible solution (call it ) remains optimal and the alternative optimal basic feasible solution (denoted ) emerges when r_k is pivoted into the basis (or x_Rk enters the set of basic variables). And as θ increases slightly beyond θ_c, so that becomes the unique optimal basic feasible solution.

What about the choice of the direction vector S? As indicated above, S represents the direction in which the objective function coefficients are varied. So while the components of S are quite arbitrary (e.g. some of the c_j values may be increased while others are decreased), it is often the case that only a single objective function coefficient c_j is to be changed, i.e. S = e_j (or −e_j). Addressing ourselves to this latter case, if and x_k is the nonbasic variable x_Rk, then (10.1.1) reduces to for j ≠ k; while for j = k, If θ increases so that or then the preceding discussion dictates that the column within the simplex matrix associated with x_k is to enter the basis, with no corresponding adjustment in the current value of f warranted. Next, if x_k is the basic variable x_Bk, (10.1.1) becomes In this instance (10.2) may be rewritten as

(10.2.1)

If the minimum in (10.2.1) is attained for j = r, then Then r_r may be pivoted into the basis so that, again, the case of multiple optimal basic feasible solutions holds. Furthermore, when x_Rr is pivoted into the set of basic variables, the current value of f must be adjusted by an amount Δf = Δc_Bkx_k = θ_cx_Bk as determined in Chapter 8.

10.2.2 Parametrizing the Requirements Vector

Given that our starting point is again an optimal basic feasible solution to a linear programming problem, let us replace b by b^* = b + φt, where φ is a nonnegative scalar parameter and t is a given (arbitrary) (m × 1) vector that specifies the direction of change in the requirements b_i, i = 1, …, m. Hence, the vary linearly with the parameter φ. Currently, primal feasibility holds for X_B = B⁻¹b ≥ O or x_Bi ≥ 0, i = 1, …, m. With b^* replacing b, the revised primal feasibility requirement becomes

(10.3)

where β_i devotes the ith row of B⁻¹. In terms of the individual components of (10.3),

(10.3.1)

(Since the optimality criterion is independent of b, the parametrization of the latter affects only primal feasibility and not primal optimality.) What is the largest value of φ for which (10.3.1) holds? Clearly the implied critical value of φ, φ_c, is that for which any increase in φ beyond φ_c violates feasibility, i.e. makes at least one of the values negative.

To determine φ_c, let us first assume that β_it ≥ 0, i = 1, …, m. Then φ can be increased without bound while still maintaining the revised feasibility criterion since, in this instance, Next, if β_it < 0 for some i, for

Hence, the revised feasibility criterion is violated when φ > φ_c for some basic variable x_Bi. Moreover, if β_it < 0 for two or more basic variables, then

(10.4)

Now, if φ increases and the minimum in (10.4) is attained for i = k, it follows that And as φ increases beyond so that b_k must be removed from the basis to preserve primal feasibility, with its replacement vector determined by the dual simplex entry criterion.

Although the specification of the direction vector t is arbitrary, it is frequently the case that only a single requirement b_i is to be changed, so that t = e_i(or − e_i). With respect to this particular selection of t, if b^* = b + φe_k, then (10.3.1) simplifies to For this choice of t then, (10.4) may be rewritten as

(10.4.1)

If the minimum in (10.4.1) is attained for If φ then increases above this critical value, turns negative so that b_l is pivoted out of the basis to maintain primal feasibility. Moreover, as b_k changes, f must be modified by an amount Δf = u_kΔb_k = u_kφ_c.

One final point is in order. In the preceding two example problems, we parametrized b directly. However, if we consider the associated dual problems, then parametrizing b can be handled in the same fashion as parametrizing the objective function.

10.2.3 Parametrizing an Activity Vector

Given that we have obtained an optimal basic feasible solution to the problem

let us undertake the parametrization of a column of the activity matrix With previously partitioned as it may be the case that: some nonbasic vector r_j is replaced by or a basic vector b_i is replaced by where τ represents a nonnegative scalar parameter and V is an arbitrary (m × 1) vector that determines the direction of change in the components of either r_j or b_i. In each individual case, the said components are expressed as linear functions of τ.

Let us initially assume that r_k is replaced by in R = [r₁, …, r_k, …, r_n − m] so that the new matrix of nonbasic vectors appears as Since the elements within the basis matrix B are independent of the parametrization of r_k, primal feasibility is unaffected (we still have X_B = B⁻¹b ≥ O) but primal optimality may be compromised. In this regard, for Upon parametrizing r_k, the revised optimality criterion becomes

where

(10.5)

and is a (1 × m) vector of nonnegative dual variables. Since primal optimality will be preserved if (10.5) holds. Now, as τ increases, primal optimality must be maintained. Given this restriction, what is the largest value of τ (its critical value, τ_c) for which (10.5) holds?

To find τ_c, we shall first assume that U^′V ≥ 0. Then τ can be increased indefinitely while still maintaining the revised optimality criterion. Next, if U^′V < 0, then for

(10.6)

In this regard, as τ increases to τ_c, it follows that so that the case of multiple optimal solutions emerges. That is, the current basic feasible solution (call it ) remains optimal and an alternative optimal basic feasible solution () obtains when r_k is pivoted into the basis, with the primal simplex criterion determining the vector to be removed from the current basis. And as τ increases a bit beyond τ_c, it follows that so that becomes the unique optimal basic feasible solution.

As indicated above, the choice of the direction vector V is completely arbitrary. However, if only a single component r_ik of the activity vector r_k is to change, then V = e_i(or − e_i). In this regard, if then (10.5) becomes So for this choice of V, with u_l ≥ 0, τ may be increased without bound while still preserving primal optimality. Next if (10.5) simplifies to In this instance, (10.6) may be rewritten as

(10.6.1)

If τ then increases above this critical value, turns negative so that r_k is pivoted into the basis to maintain primal optimality.

When τ is increased slightly above it may be the case that: τ may be increased without bound while still preserving primal optimality; or there exists a second critical value of τ beyond which the new basis ceases to yield an optimal feasible solution. Relative to this latter instance, since r_k has entered the optimal basis, we now have to determine a procedure for parametrizing a basis vector. Before doing so, however, let us examine Example 10.4.

Next, to parametrize a vector within the optimal basis, let us replace the kth column b_k of the basis matrix so as to obtain Since it follows that

From (10.A.1) of Appendix 10.A,

And from (10.A.2), and thus

Since must be primal feasible, we require that

If 1 + τβ_kV > 0, then, upon solving the second inequality for τ and remembering that τ must be strictly positive,

(10.7)

Since (10.7) must hold for all i ≠ k when 1 + τβ_kV > 0, it follows that the upper limit or critical value to which τ can increase without violating primal feasibility is

(10.8)

To determine the effect of parametrizing the basis vector upon primal optimality, let us express the revised optimality criterion as

or, in terms of its components

(10.9)

If we now add and subtract the term

on the left‐hand side of (10.9), the latter simplifies to

(10.9.1)

If 1 + τβ_kV > 0, and again remembering that τ must be strictly positive, we may solve (10.9.1) for τ as

(10.10)

Since (10.10) is required to hold for all j = 1, …, n − m when 1 + τβ_kV > 0, we may write the critical value to which τ can increase while still preserving primal optimality as

(10.11)

As we have just seen, the parametrization of a basis vector may affect both the feasibility and optimality of the current solution. This being the case, the critical value of τ that preserves both primal feasibility and optimality simultaneously is simply

(10.12)

Finally, the effect on the optimal value of f parametrizing b_k can be shown to be

(10.13)

As far as the specification of the arbitrary direction vector V is concerned, it is sometimes the case that only a single component of b_i is to change, i.e. V = e_i (or − e_i) so that

We know that to obtain a new basic feasible solution to a linear programming problem via the simplex method, we need change only a single vector in the basis matrix at each iteration. We are thus faced with the problem of finding the inverse of a matrix that has only one column different from that of a matrix B whose inverse is known. So given B = [b₁, …, b_m] with B⁻¹ known, we wish to replace the rth column b_r of B by r_j so as obtain the inverse of Since the columns of B form a basis for R^m, r_j = BY_j. If the columns of are also to yield a basis for R^m, then it must be true that y_rj ≠ 0. So if

with y_rj ≠ 0, then

Hence b_r has been removed from the basis with r_j entered in its stead. If we next replace the rth column of the mth order identity matrix we obtain

(10.A.1

where, as previously defined, e_j is the jth unit column vector. Now it is easily demonstrated that so that

(10.A.2