BRICS RS-96-48 A. Peke� c: Scalings in Linear Programming

BRICS

Basic Research in Computer Science

Scalings in Linear Programming: Necessary and Suf�cient Conditions for Invariance

Aleksandar Peke� c

BRICS Report Series RS-96-48 ISSN 0909-0878 December 1996 Copyright \begin{matrix}c \\ ◯ \end{matrix} 1996, BRICS, Department of Computer Science

University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent publications in the BRICS Report Series. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK - 8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through World Wide Web and anonymous FTP:

http://www.brics.dk/
ftp://ftp.brics.dk/pub/BRICS

This document in subdirectory RS/96/48/

Scalings in Linear Programming: Necessary and Sufficient Conditions for Invariance

Aleksandar Pekeč

BRICS^{∗}

Department of Computer Science University of Aarhus Ny Munkegade DK-8000 Aarhus C, Denmark

                  http://www.brics.dk/∼pekec/

Abstract

We analyze invariance of the conclusion of optimality for the linear programming problem under scalings (linear, affine, …) of various problem parameters such as: the coefficients of the objective function, the coefficients of the constraint vector, the coefficients of one or more rows (columns) of the constraint matrix. Measurement theory concepts play a central role in our presentation and we explain why such approach is a natural one.

Keywords: Sensitivity Analysis, Scaling, Measurement

∗ Basic Research in Computer Science, Centre of the Danish National Research Foundation.

1 Introduction

In this paper we analyze robustness of an optimal solution to the linear programming problem^{1}

max P (x; w) = w^{T} x

subject to:

x ∈ F := {x ∈ R^{n} : x ≥ 0 & Ax = b}

(1)

More precisely, we give conditions under which an optimal solution (or basic variables determining it) is invariant under scaling of various problem parameters such as the coefficients of the objective function w_{1}, …, w_{n}, coefficients of the constraint matrix A (a_{ij}, i, j = 1, …, n), and coefficients of the constraint vector b = (b_{1}, …, b_{m})^{T}. By scaling of parameters p_{1}, …, p_{k} by a function Φ from some set of functions S, we mean replacing p_{1}, …, p_{k} by Φ(p_{1}), …, Φ(p_{k}). Although scaling would usually mean scaling by increasing linear functions (i.e., S = {Φ : R → R : Φ(x) = αx, α > 0}), we also consider cases where various problem parameters are scaled by increasing affine functions S = {Φ : R → R : Φ(x) = αx + β, α > 0}), and by even more general sets of functions. This approach to analyzing robustness of an optimal solution to the problem (1) is different than the standard sensitivity analysis approach where only the effects of small perturbations of problem parameters are considered. So, why should one be interested in the perturbations of data that arise from scalings? For mathematical purists, there is no justification needed since characterizing invariance of the conclusion of optimality under scaling of certain parameters by functions from a set S is an interesting mathematical question per se. Moreover, any characterization of this type might give better understanding of the linear programming problems. However, our motivation comes from situations that might arise in practice: whenever problem parameters represent data that can be measured in more than one acceptable way (e.g., costs/profits can be measured in US dollars, Danish kroner, Croatian kunas, or any other currency; time can be measured in seconds, minutes, hours,....). As will be shown (in Section 3), the way data is measured gives rise to a set of scaling functions in a natural way.

1Throughout we use a notational convention that boldfaced letters denote vectors, that is x = (x_{1}, …, x_{n})^{T}. We also assume that A ∈ M_{m,n}(R) is of full rank and we assume that m ≤ n, i.e., rank(A) = m.

Example 1 Consider the production problem where n items could be produced and each produced unit of the j-th item brings the net profit/loss of w_{j}. Suppose that the production of any item requires m different resources (machines, raw materials, etc.) and suppose that one unit of the j-th item requires a_{ij} of the i-th resource. Further suppose that there is at most b_{i} of the i-th resource. Then the problem of maximizing the profit can be formulated as the linear programming problem (1)^{2}.

There are numerous problem parameters that can be presented in different but equally acceptable ways. For example, the coefficients of the objective function w_{1}, …, w_{n} can be expressed in US dollars but they can be expressed in German marks or any other currency. Note that any transformation from one monetary unit to another is an increasing linear function. If a flat fee needs to be paid for every currency conversion (say, price of an option to buy a currency at a given exchange rate), then a transformation from one monetary unit to another is an increasing affine function.

Similarly, for any i, there might be more than one way to represent a_{i1}, …, a_{in}, b_{i}. For example, a_{ij} might represent time that the j-th item needs to spend on the i-th machine. This time can be measured in seconds, minutes, hours,…. In fact, relationship between any two acceptable ways to represent such data is described by an increasing linear transformation.^{3}

Our presentation is built up on measurement theory concepts. In particular scales of measurement (see Section 2) and the concept of meaningfulness (see Section 3) are central notions of our presentation. The main reason for such approach is not only to expose a natural connection between meaningfulness and invariance under scalings, but also to show that invariance under scalings of problem parameters is a natural object of sensitivity analysis. This paper is an attempt to illustrate this type of analysis in the case of the linear programming problem which is the most widely used mathematical model for optimization problems arising in practice. However, investigation of meaningfulness of the conclusion of optimality is a theme that goes far beyond the scope of this paper. Roberts [7, 8] was first to point out a variety of problems concerning meaningfulness of the statements that can be drawn from various mathematical models that are commonly used to solve operations research problems. Detailed treatment of the meaningfulness of the conclusion of optimality in combinatorial optimization problems can be found in [4] (in fact, this paper is an improved version of part of work presented there). Also, systematic analysis of the meaningfulness of the conclusion of optimality for single machine scheduling problems can be found in [3].

2Note that we may assume that all constraints are in fact equalities. For example, any unused portion of the i-th resource can be viewed as another production item (it can be resold, stored, disposed,… at some per unit profit/loss w_{n+i})

3Of course, it is trivial to see that the conclusion of optimality is invariant under such transformations of problem parameters. The point of this example was to illustrate how measurement of problem parameters gives rise to scaling functions

In most of the situations that will be analyzed here, it will be clear that there cannot be an optimal solution invariant under the given set of scaling functions. However, we will characterize situations in which the set of basic variables that defines the optimal basis and, hence, an optimal solution is invariant to such scalings. In some sense, the set of the basic variables determining an optimal solution is a natural object of our analysis. It describes only fundamental relationship between the set of feasible solutions F and the objective function P, eliminating actual numerical values of the problem parameters to the largest possible extent.

Let us introduce the notation by briefly defining basics about optimality of the problem (1):

Ax = b can be written as

A_{1}x_{1} + A_{2}x_{2} + … + A_{n}x_{n} = b  (2)

where A_{i} denotes the i-th column of A. For any m linearly independent columns of A: A_{i_{1}}, …, A_{i_{m}}, there exists a unique solution (x_{i_{1}}, …, x_{i_{m}}) to the system of m linear equalities:

A_{i_{1}}x_{i_{1}} + A_{i_{2}}x_{i_{2}} + … + A_{i_{m}}x_{i_{m}} = b

This solution can be extended to a solution of the system Ax = b by setting x_{k} = 0 for all k ∉ {i_{1}, …, i_{m}}. Such a solution is called a basic solution to the system Ax = b and variables i_{1}, …, i_{m} are called basic variables while the other n − m variables are called non-basic variables. We say that x is a basic feasible solution if x is a basic solution and x ≥ 0^{4}.

An m × m non-singular matrix whose k-th column is A_{i_{k}} will be denoted by B. We will call B a basis since by giving B we actually prescribe basic variables. w_{B} will denote the vector (w_{i_{1}}, w_{i_{2}}, …, w_{i_{m}})^{T} and x_{B} will denote the vector (x_{i_{1}}, x_{i_{2}}, …, x_{i_{m}})^{T}. In this notation, the basic variables for the basic feasible solution x corresponding to a basis B are given by x_{B} = B^{−1}b (since Bx_{B} = b). Moreover, we have w^{T} x = w_{B}^{T} x_{B} since for every nonbasic variable k, x_{k} = 0.

4Every basic feasible solution corresponds to an extreme point of F and every extreme point of F corresponds to (one or more) basic feasible solutions (see, for example, [1, 2]).

The notation

z_{j} := w_{B}^{T}B^{−1}A_{j}

will be used throughout this paper

It is straightforward to show (see, for example, [1] or [2]) that basic feasible solution x^{∗} corresponding to basis B is an optimal solution to problem (1) if and only if

z_{j} − w_{j} ≥ 0, j = 1, …, n.  (3)

This characterization of an optimal solution to problem (1) is known as the optimality criterion. The basis B corresponding to an optimal solution x^{∗} is called an optimal basis.

As already mentioned, in the next section we will introduce the measurement theory terminology. Throughout the paper, this terminology will be used to describe and analyze invariance under various scalings. Section 3 is conceptually the most important part of this paper: in this section we define the concept of meaningfulness, overview our results, and give proofs for some simple cases. The cases that are technically more complicated will be analyzed in Section 4. Finally, we give some closing remarks in Section 5.

2 Background–Measurement Theory Terminology

Invariance of the conclusion of optimality under scaling of certain parameters of the problem (1) might not only be a nice property of an optimal solution, but it is often a necessary condition if the linear programming formulation is used to model a problem whose parameters are numerical representations of problem data. We will show how the information about the scale type of data often gives rise to a set of scaling functions S with the property that the conclusion of optimality must be invariant under scalings by functions from S. We first introduce some basic measurement theory concepts (following [6]).

Obviously, measurement has something to do with assigning numbers that correspond to or “preserve” certain observed relations. Formally, objects being measured together with relations that should be preserved define a relational system, i.e., an ordered (p + q + 1)-tuple (A, R_{1}, …, R_{p}, o_{1}, …, o_{q}), where A is a set of objects, R_{1}, …, R_{p} are (not necessarily binary) relations on A, and o_{1}, …, o_{q} are binary operations on A. The type of the relational system is a sequence (r_{1}, …, r_{p}; q) of length p + 1 where r_{i} denotes that R_{i} is an r_{i}-ary relation (i.e., R_{i} ⊆ A^{r_{i}}). A scale of measurement is defined by a mapping (into some relational system on R) that preserves relations and binary operations of the relational system whose elements are being measured, i.e., a scale of measurement is a triple (A, B, f) where A and B are relational systems of the same type (and B is a relational system on R.), and f : A → B is a homomorphism of relational systems (that is, for all a_{1}, a_{2}, …, a_{r_{i}} ∈ A, R_{i}(a_{1}, a_{2}, …, a_{r_{i}}) ⇔ R′_{i}(f(a_{1}), f(a_{2}), …, f(a_{r_{i}})) i = 1, …, p, and for all a, b ∈ A, f(ao_{i}b) = f(a)o′_{i}f(b), i = 1, …, q). Every scale of measurement (A, B, f) defines a representation A → B.

As already point out, usually there is more than one acceptable way to measure objects from A (i.e., there can be more than one representation A → B). Let S_{1} = (A, B, f) and S_{2} = (A, B, g) be two scales of measurement. If there exists Φ : f(A) → R such that Φ ∘ f = g, then we say that Φ is an admissible transformation of S_{1} (since g = Φ ∘ f defines S_{2}, i.e., another acceptable way to measure objects from A). The set of all admissible transformations of f (which defines S_{1}) is denoted by AT (f). f is a regular homomorphism (and S_{1} is a regular scale) if for any other scale (A, B, h), there exists Φ_{h} ∈ AT (f) such that h = Φ_{h} ∘ f. Regular scales are important since (A, B, f) and the corresponding AT (f) define any other scale (A, B, h). If any scale (A, B, f) is regular then we say that A → B is a regular representation.

All the homomorphisms (scales, representations) that will be considered in the rest of this paper are assumed to be regular.^{5}

The set AT (f) defines the scale type of f. If all homomorphisms of a representation A → B have the same scale type (as will be the case with all scales that will be considered) then the scale type of a representation A → B is defined to be the scale type of any of its homomorphisms. We will refer to the following scale types that often appear in practice:

• Absolute scales. f is an absolute scale if AT (f) = {id}. The scale values are predetermined here and there is a unique way to measure data.

5This is a natural assumption since it can be shown that any homomorphism can be reduced to a regular one in a natural way [4, 6].

• Ratio scales. f is a ratio scale if AT (f) is the set of all increasing linear transformations. It is not hard to see that in this case the scale value is determined up to choice of a unit. Examples of ratio scales are measurement of cardinal utility (i.e., monetary amounts), time, length, mass, …

• Interval scales. f is an interval scale if AT (f) is the set of all increasing affine transformations. In other words, the scale value is determined up to choice of a unit and choice of a zero point. For example, temperature is measured on an interval scale. Also, cardinal utility with one unknown parameter (for example per-unit production cost with the unknown fixed start-up cost), or time with one unknown parameter (e.g., calendar time, or per-unit processing time with unknown fixed start-up time) are examples interval scale type data.

• Ordinal scales. f is an ordinal scale if AT (f) is the set of all increasing functions. Hence, the scale value is determined only up to order. For example, whenever only the ordering among objects being measured is known, we have an ordinal scale.

If AT (f) ⊆ AT (g), we say that the scale of f is stronger than or equal to the scale of g (or the scale of g is weaker than or equal to the scale of f). For example, we can order scales introduced here from the strongest towards the weakest: absolute, ratio, interval, ordinal.

3 Meaningfulness of the conclusion of optimality

The central measurement theory concept that will be used throughout this paper is that of meaningfulness. We say that a statement involving scales of measurement is meaningful if its truth value is unchanged whenever every scale (A, B, f) is replaced by another (acceptable) scale (A, B, Φ ∘ f), Φ ∈ AT (f). In other words a statement is meaningful if it has the same truth value (always true or always false) regardless of the choice of the homomorphism f : A → B. Therefore, meaningful statements are unambiguous in their interpretation and they say something about fundamental relations among the objects being measured. Statements which are not meaningful are meaningless. In other words, a statement involving scales is meaningless if there exists a scale (A, B, f) and a scale (A, B, Φ ∘ f), Φ ∈ AT (f), such that the statement is false. Obviously, we cannot put much weight behind such statements since their truth value is an accident of the choice of an (acceptable) way to measure the objects in question.

In this paper we analyze the meaningfulness of the conclusion of optimality for the linear programming problem (1). It should be noted that we may assume that every parameter of the problem (1) (i.e., coefficients of the objective function w_{1}, …, w_{n}, coefficients of the constraint matrix a_{11}, … a_{mn} and coefficients of the resource vector b_{1}, …, b_{m}) and the value of every variable x_{1}, …, x_{n} represent data measured on some scale of measurement (since everything is being measured on at least an absolute scale of measurement).

We say that x^{∗} is a meaningful optimal solution to the problem (1) if and only if x is an optimal solution and the conclusion of optimality is a meaningful statement (with respect to all scales of measurement). More formally, suppose that there are k different scales of measurement involved in formulation of the problem (1) and suppose that f_{1}, …, f_{k} are regular homomorphisms representing all the data. Then an optimal solution x^{∗} for problem (1) is meaningful if and only if, for any choice of Φ_{1}, …, Φ_{k} (Φ_{i} ∈ AT (f_{i}), i = 1, …, k), x̄^{∗} is an optimal solution to the problem

max P (x, w̄) = w̄^{T} x

subject to:

x ∈ F̄ := {x ∈ R^{n} : x ≥ 0 & Āx = b̄}

where x̄_{s} := Φ_{i(x_{s})}(x_{s}), w̄_{s} := Φ_{i(w_{s})}(w_{s}), the coefficients of matrix Ā are ā_{rs} := Φ_{i(a_{rs})}(a_{rs}), and b̄_{r} := Φ_{i(b_{r})}(b_{r}) for x_{s}, w_{s}, a_{rs}, b_{r} being data measured on the i(x_{s})-th, i(w_{s})-th, i(a_{rs})-th, and i(b_{r})-th scale of measurement, respectively (that is, for any r and s Φ_{i(x_{s})} is a regular homomorphism representing x_{s}, Φ_{i(w_{s})} is a regular homomorphism representing w_{s}, Φ_{i(a_{rs})} is a regular homomorphism representing a_{rs}, and Φ_{i(b_{r})} is a regular homomorphism representing b_{r}). In what follows we adopt the convention that if only the scale of some of the parameters is mentioned, it is assumed that the other parameters are fixed (i.e., measured on an absolute scale). Remark. Suppose that x^{∗} is an optimal solution to problem (1). Let {p_{1}, …, p_{l}} be some set of the problem parameters (i.e., each p_{i} is a coefficient of either w or A or b). Let S be a scale of measurement with a property that there exists a set of functions G such that for every homomorphism f, the set of admissible transformations AT (f) = G. Then the following are equivalent:

(a) x^{∗} is a meaningful optimal solution if {p_{1}, …, p_{l}} are measured on a common scale of measurement S.

(b) The conclusion that x^{∗} is an optimal solution to problem (1) is invariant under scaling of {p_{1}, …, p_{l}} by any function from G.

For example, invariance of the conclusion of optimality of x^{∗} under scaling of {p_{1}, …, p_{l}} by increasing linear (affine) transformations is equivalent to x^{∗} being a meaningful optimal solutions if {p_{1}, …, p_{l}} represent data measured on a ratio (interval) scale of measurement.

In what follows we will discuss several situations:

• Coefficients of the objective function (w_{1}, …, w_{n}) are measured on a (common) scale of measurement (Theorem 2, and Corollary 3).

• Coefficients of the i-th row of the matrix A (a_{i1}, …, a_{in}) together with b_{i} (i-th coordinate of the vector b) are measured on a (common) scale of measurement S_{i} (Proposition 4 and Corollary 5).

• Coefficients of the i-th row of the matrix A (a_{i1}, …, a_{in}) are measured on a (common) ratio scale of measurement or b_{i} is measured on some scale of measurement S_{i} (Proposition 6, Theorem 8, Corollary 9, Corollary 10, Theorem 12, and Corollary 13).

• Coefficients of the j-th column of the matrix A (a_{1j}, …, a_{mj}) together with w_{j} (j-th coefficient of the objective function) are measured on a (common) scale of measurement S_{i} (Proposition 15).

• Coefficients of the j-th column of the matrix A (a_{1j}, …, a_{mj}) are measured on a (common) ratio scale of measurement or w_{j} is measured on some scale of measurement S_{i} (Theorem 17, Corollary 18, Theorem 19, Corollary 20, and Theorem 21).

The following notation will be used in the proof of the next theorem and throughout the rest of the paper: for Φ:R→R, and x =(x_{1}, …, x_{n})^{T} ∈ R^{n}, we denote Φ(x) := (Φ(x_{1}), …, Φ(x_{n}))^{T}.

Theorem 2 Let x^{∗} be an optimal solution for problem (1).

1. x^{∗} is a meaningful optimal solution if w_{1}, …, w_{n} are measured on a ratio scale.

2. Suppose that w_{1}, …, w_{n} are measured on an interval scale. Then x^{∗} is a meaningful optimal solution if and only if x_{1} + x_{2} + … + x_{n} is a constant on F.

Proof: 1. follows from the fact that (αw)^{T} x = αw^{T} x, i.e., for any α > 0, (αw)^{T} x^{∗} ≥ (αw)^{T} y if and only if w^{T} x^{∗} ≥ w^{T} y.

In order to prove 2., first note that, for any Φ(t) = αt + β, [Φ(w)]^{T} x = αw^{T} x + β(1, …, 1)x. Hence, for any α > 0, [Φ(w)]^{T} x^{∗} ≥ [Φ(w)]^{T} y if and only if

w^{T} x^{∗} ≥ w^{T} y + \frac{β}{α}(1, …, 1)(x − y).

If x_{1} + x_{2} + … + x_{n} is a constant on F (i.e., if for any x, y ∈ f, (1, …, 1)(x − y) = 0), then [Φ(w)]^{T} x ≥ [Φ(w)]^{T} y if and only if w^{T} x ≥ w^{T} y. Conversely, if x_{1} + x_{2} + … + x_{n} is not a constant on F, then there exists y ∈ F such that (1, …, 1)(x − y) ≠ 0 and we can find α > 0 and β such that [Φ(w)]^{T} x^{∗} < [Φ(w)]^{T} y. In other words, x^{∗} is not a meaningful optimal solution.

It should be noted that Theorem 2 holds as long as the objective function is linear, i.e., we need no assumptions whatsoever on the structure of the set F. (In fact, the theorem also holds for more general objective functions; see [4])

We use the special structure of the set of feasible solutions F to obtain

Corollary 3 Suppose that w_{1}, …, w_{n} are measured on an interval scale and let x^{∗} be an optimal solution for problem (1). Then x^{∗} is a meaningful optimal solution if and only if there exists λ ∈ R^{m} such that λ^{T} A = (1, 1, …, 1).

Proof: By Theorem 2, if w_{1}, …, w_{n} are measured on interval scale then x^{∗} is a meaningful optimal solution if and only if x_{1} + x_{2} + … + x_{n} is a constant on F := {x ≥ 0 : Ax = b}. Note that any x ∈ F can be written as x_{0} + y ≥ 0 where x_{0} is some fixed element from F and Ay = 0. Moreover, x_{1} + x_{2} + … + x_{n} is a constant on F if and only if y_{1} + y_{2} + … + y_{n} = 0 for every y such that x_{0} + y ∈ F. Since rank(A) = m all the rows of A are linearly independent and

{y : Ay = 0}  (4)

is an (n − m)-dimensional subspace of R^{n}. By adding an additional equality (an additional row in A) y_{1} + y_{2} + … + y_{n} = 0, the set

{y : Ay = 0, y_{1} + y_{2} + … + y_{n} = 0}

will be the same as the set (4) if and only if (1, …, 1) can be expressed as a linear combination of the rows of A. Of course, this will be the case if and only if there exists a λ ∈ R^{m} such that λ^{T} A = (1, 1, …, 1)

Proposition 4 Suppose that a_{i1}, a_{i2}, …, a_{in}, b_{i} are measured on a scale of measurement S.

1. If S is a ratio scale then every optimal solution x^{∗} to problem (1) is meaningful.

2. If S is an interval scale and if

x_{1} + x_{2} + … + x_{n} = 1  (5)

for all x ∈ F, then then every optimal solution x^{∗} to problem (1) is meaningful.

Proof: Obviously,

a_{i1}x_{1} + a_{i2}x_{2} + … + a_{in}x_{n} = b_{i}

holds if and only if

αa_{i1}x_{1} + αa_{i2}x_{2} + … + αa_{in}x_{n} = αb_{i}

holds for any α > 0 and this proves 1. Similarly, 2. follows directly from the obvious fact that for any choice of α > 0 and β

(αa_{i1} + β)x_{1} + (αa_{i2} + β)x_{2} + … + (αa_{in} + β)x_{n} = αb_{i} + β

if and only if

a_{i1}x_{1} + a_{i2}x_{2} + … + a_{in}x_{n} = b_{i}.

(This is because x_{1} + x_{2} + … + x_{n} = 1.)

Corollary 5 Suppose that a_{i1}, a_{i2}, …, a_{in}, b_{i} are measured on a scale of measurement S_{i}, i = 1, …, m.

1. If for every i = 1, …, m, S_{i} is a ratio scale or stronger, then every optimal solution x^{∗} to problem (1) is meaningful.

2. If for every i = 1, …, m, S_{i} is an interval scale and if (5) holds for all x ∈ F, then then every optimal solution x^{∗} to problem (1) is meaningful.

Proof: Same as the proof of Proposition 4. Remark. Without the condition (5) the conclusion of feasibility of x is a meaningless statement in general and, consequently, the conclusion of optimality might be a meaningless statement. It might be the case that a particular x is in F for any choice of Φ(a_{i1}), Φ(a_{i2}), …, Φ(a_{in}), Φ(b_{i}). It is possible that there exists a meaningful optimal solution and that the conditions of Corollary 5 are not met. For example, consider problem (1) where

w^{T} = (1, 0, 0, 0), A = ( \begin{matrix}1 & 0 & 1 & 0 \\ 2 & 1 & 0 & 1 \end{matrix} ) , b^{T} = ( 1 2 )

It is easy to see that x^{∗} = (1, 0, 0, 0)^{T} is a meaningful optimal solution whenever a_{21}, a_{22}, a_{23}, a_{24}, b_{2} are measured on an interval scale. This is because x^{∗} ∈ F for any choice of αa_{21} + β, αa_{22} + β, αa_{23} + β, αa_{24} + β, αb_{2} + β and because x_{1} ≤ 1 (this follows from the first equality and x_{i} ≥ 0).

If we just change w^{T} in the example to be (1, 1, 0, 0), the conclusion of optimality won’t be a meaningful statement anymore. x^{∗} = (1, 1, 0, 0)^{T} is not even feasible whenever β ≠ 0.

4 Invariance of basic variables

In this section we will consider situations where the statement “x ∈ F ” will be obviously meaningless. However, one might be interested in determining if there exists a basis such that the corresponding x^{∗} is optimal regardless of the choice of acceptable ways to measure problem data. In other words, we will investigate the meaningfulness of the statement “the basic variables of the basis B determine an optimal basis”.

The first such situation is where only b_{i} are measured on scales of measurement S_{i}. Any transformation Φ_{i}(b_{i}), can be viewed as replacing b_{i} with b_{i}′ := α_{i}^{−1}b_{i} where α_{i} := b_{i}/Φ(b_{i}). Obviously, in this case, the statement “x ∈ F ” is meaningful if and only if b_{i} = b_{i}′. However, we will be interested in determining if there exists a basis such that the corresponding x^{∗} is optimal for any choice of Φ_{i}(b_{i}), where Φ_{i} is an admissible transformation for the scale of measurement of b_{i}. This question is equivalent to analyzing whether there exists a basis which is optimal whenever a_{i1}, a_{i2}, …, a_{in} are replaced by α_{i}a_{i1}, α_{i}a_{i2}, …, α_{i}a_{in}. For example, if b_{i} is measured on a ratio scale, then α_{i} can be any positive real number. Even if b_{i} (note that b ≥ 0 by the definition of problem (1)) were measured on an interval, ordinal or even nominal scale on R_{+} we still have α ∈ R_{+} and we can view this problem as a problem where a_{i1}, a_{i2}, …, a_{in} are measured on a ratio scale.

The simplest possible example is when all b_{i} are measured on the same ratio scale S.

Proposition 6 Suppose that b_{1}, …, b_{m} are measured on a (common) ratio scale. Then the conclusion that B is an optimal basis for problem (1) is a meaningful statement.

Proof: Clearly, for any α > 0, w^{T} x^{(1)} ≤ w^{T} x^{(2)} if and only if w^{T} (αx^{(1)}) ≤ w^{T} (αx^{(2)}). Furthermore, for any α > 0, B is a basis for a basic feasible solution x of Ax = b if and only if B is a basis for a basic feasible solution αx of Ax = αb

We now turn our attention to the case where only one b_{i} is measured on some scale of measurement (i.e., S_{k}, k ≠ i, are absolute scales). As already mentioned, there is a natural correspondence between b_{i} being measured on a scale S and a_{i1}, …, a_{in} being measured on a (common) ratio scale.

Example 7 (Production problem revisited) Consider the production problem presented in Example 1. It is possible that the exact amount of the i-th resource is not known exactly (for example, the total time machine i can be used might be proportional to the outside temperature) while the exact amount of other resources is known exactly. This can be viewed as b_{i} being measured on some scale of measurement S (if b_{i} is proportional to the outside temperature, then it is easy to see that S is an interval scale).

Also, for this fixed i, a_{i1}, …, a_{in} might be numerical representations of some measure of the i-th resource (which might be different than the measure of w_{j} or a_{kj}, k ≠ i). For example, a_{ij} might represent the processing time of a unit of the j-th product on the i-th machine. These processing times might depend on the quality of some raw material used in the working process (the higher the quality, the shorter the processing times), so the numbers a_{i1}, a_{i2}, …, a_{in} are not known precisely. However, it is possible that (for a fixed i) all the ratios r_{jk} = a_{ij}/a_{ik} are known (i.e., it might be known that the j-th item needs r_{jk} times more time than the i-th item). Hence, it is possible that a_{i1}, …, a_{in} are measured on a common (ratio) scale of measurement.

The following notation will be used throughout: for any α ≠ 0 and i = 1, …, n we define

I(α; i) := Diag(1, …, 1, α, 1, …, 1)

where α is the (i, i) entry of I(α; i).

Theorem 8 Let B be an optimal basis for problem (1). If a_{i1}, a_{i2}, …, a_{in} are measured on a ratio scale, then the statement that the basic variables of B define an optimal basis for problem (1) is meaningful if and only if (B^{−1})_{i} ≥ 0 (the i-th column of B^{−1} has no negative entries) and

∑_{k=1}^{m} b_{k}(B^{−1})_{k} ≥ b_{i}(B^{−1})_{i}.  (6)

Proof: Replacing a_{i1}, a_{i2}, …, a_{in} by αa_{i1}, αa_{i2}, …, αa_{in} can be written in matrix form as replacing matrix A by matrix

A_{α} := [I(α; i)]A.

In this notation

B_{α} = [I(α; i)]B

and

B_{α}^{−1} = B^{−1}[I(α^{−1}; i)] = B^{−1} + B^{−1}[Diag(0, …, 0, \frac{1}{α} − 1, 0, …, 0)].

B_{α} is an optimal basis if and only if the corresponding basic solution x_{α}^{∗} is feasible and the optimality criterion holds. We need to show that the statement “B_{α} is an optimal basis for problem (1) where A is replaced by A_{α}” is a true statement for any α > 0 if and only if (6) holds. (Note that the statement is true for α = 1 by hypothesis.)

Note that (A_{α})_{j} = [I(α; i)]A_{j} and we have

B_{α}^{−1}(A_{α})_{j} = B^{−1}[I(α^{−1}; i)][I(α; i)]A_{j} = B^{−1}A_{j}.

Consequently,

w_{B}^{T} B_{α}^{−1}(A_{α})_{j} − w_{j} = w_{B}^{T} B^{−1}A_{j} − w_{j}

and, for any α > 0, the optimality criterion holds for B_{α} since it holds for B by hypothesis.

Feasibility corresponds to the condition

(x_{α}^{∗})_{B_{α}} = B_{α}^{−1}b ≥ 0,

since B(x^{∗})_{B} = b.

B_{α}^{−1}b = B^{−1}b + B^{−1}[Diag(0, …, 0, \frac{1}{α} − 1, 0 …, 0)]b
= x_{B}^{∗} + (B^{−1})_{i}(\frac{1}{α} − 1)b_{i}
= x_{B}^{∗} + b_{i} \frac{1 − α}{α}(B^{−1})_{i}.

Therefore, B_{α}^{−1}b ≥ 0 if and only if

x_{B}^{∗} ≥ b_{i} \frac{α − 1}{α}(B^{−1})_{i}.  (7)

Hence, it remains to show that (7) holds for any α > 0 if and only if both (B^{−1})_{i} ≥ 0 and (6) hold. Inequality (7) is required to hold for any α > 0. Since f(α) := C \frac{α−1}{α} is a monotone function on R_{+} we only need to check that Inequality (7) holds when α → 0^{+} and when α → +∞.

When α → 0^{+} then \frac{α−1}{α} → −∞ and Inequality (7) holds if and only if (B^{−1})_{i} ≥ 0. This is because x_{B}^{∗} ≥ 0 (by feasibility) and b_{i} ≥ 0 (by definition of problem (1)).

When α → +∞ then \frac{α−1}{α} → 1^{−} and we need to show that x^{∗}_{B} ≥ b_{i}(B^{−1})_{i}. Note that

x^{∗}_{B} = B^{−1}b = b_{1}(B^{−1})_{1} + … + b_{m}(B^{−1})_{m}.

Therefore, we need

b_{1}(B^{−1})_{1} + … + b_{m}(B^{−1})_{m} ≥ b_{i}(B^{−1})_{i},

which is exactly (6)

Corollary 9 Let B be an optimal basis for problem (1). Suppose that b_{i} from problem (1) is measured on a scale of measurement (A, B, f) where B is a relational system on R_{+} If (B^{−1})_{i} ≥ 0 and if (6) holds, then the statement that the basic variables of a basis B define an optimal basis for problem (1) is meaningful.

Proof: This follows directly from Theorem 8. As mentioned just before Theorem 8, replacing b_{i} by Φ(b_{i}) (Φ ∈ AT (f)) is equivalent to replacing a_{i1}, a_{i2},…, a_{in} by αa_{i1}, αa_{i2},…, αa_{in} where α = b_{i}/Φ(b_{i}). α ≥ 0 since both b_{i} and Φ(b_{i}) are in R_{+}.

The following corollary is the converse of Corollary 9.

Corollary 10 Let B be an optimal basis for problem (1). Suppose that b_{i} from problem (1) is measured on a scale of measurement (A, B, f) where B is a relational system on R_{+}. Further suppose that the set

S := \{ \frac{b_{i}}{Φ(b_{i})} : Φ ∈ AT (f)\} ⊆ R_{+}

does not have an infimum or supremum in R_{+}. If the statement that the basic variables of a basis B define an optimal basis for problem (1) is meaningful, then (B^{−1})_{i} ≥ 0 and (6) holds.

Proof: This follows from the proof of Theorem 8. Note that (7) must hold for every α ∈ S. Since inf S = 0 and sup S = ∞, we use the same argument as in the proof of Theorem 8

Example 11 Consider problem (1) where

w^{T} = (2, −1, 0, 0), A = ( \begin{matrix}1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \end{matrix} ) , b^{T} = ( 1 2 ) .

It is easy to see that x^{∗} = (1, 0, 0, 1)^{T} is the optimal solution and the basic variables are 1 and 4. The corresponding optimal basis B and its inverse B^{−1} are

B = ( \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ) , B^{−1} = ( \begin{matrix}1 & 0 \\ −1 & 1 \end{matrix} )

If b_{1} is measured on some scale of measurement, then the conclusion that the basic solution corresponding to basic variables 1. and 4. is optimal is meaningless by Corollary 10 since the first column of B^{−1}, (B^{−1})_{1}, is not a nonnegative vector. Indeed, whenever b_{1} is replaced by Φ(b_{1}) we can consider problem (1) where instead of replacing b_{1} by Φ(b_{1}), we replace A by

( \begin{matrix}\frac{1}{Φ(b_{1})} & 0 & \frac{1}{Φ(b_{1})} & 0 \\ 1 & 1 & 0 & 1 \end{matrix} )

Note that the basic solution in which 1 and 4 are basic variables is not feasible whenever Φ(b_{1}) > 2 since

( \begin{matrix}\frac{1}{Φ(b_{1})} & 0 \\ 1 & 1 \end{matrix} )^{−1} ( 1 2 )^{T} = ( \begin{matrix}Φ(b_{1}) & 0 \\ −Φ(b_{1}) & 1 \end{matrix} ) ( 1 2 )^{T} = ( Φ(b_{1}) 2−Φ(b_{1}) ) .

Therefore, such a basic solution cannot be optimal (since is not even feasible) whenever Φ(b_{1}) > 2.

Theorem 12 Let B be an optimal basis for problem (1). Suppose that for every i = 1, …, m, b_{i} from problem (1) is measured on a scale of measurement (A_{i}, B_{i}, f_{i}), where B_{i} is a relational system on R_{+}. Further suppose that for

S_{i} := \{\frac{b_{i}}{Φ_{i}(b_{i})} : Φ_{i} ∈ AT (f_{i})\} ⊆ R_{+}

inf(S_{i}) = 0, i = 1, …, m. Then the statement that the basic variables of a basis B define an optimal basis for problem (1) is meaningful if and only if B^{−1} ≥ 0.

Proof: We again note that replacing b_{i} by Φ_{i}(b_{i}) is equivalent to replacing a_{i1}, …, a_{in} by α_{i}a_{i1}, …, α_{i}a_{in} where α_{i} = b_{i}/Φ_{i}(b_{i}).

We follow the proof of Theorem 8. For any choice of Φ_{i} ∈ AT (f_{i}), i = 1, …, m, replacing b_{i} by Φ(b_{i}) can be viewed as replacing matrix A by matrix

A_{α} := (∏_{i=1}^{m}[I(α_{i}; i)])A = [Diag(α_{1}, …, α_{m})]A.

We define

B_{α} := (∏_{i=1}^{m}[I(α_{i}; i)])B = [Diag(α_{1}, …, α_{m})]B.

We want to show that the statement “B_{α} is an optimal basis for problem (1) where A is replaced by A_{α}” is a true statement for any choice of (α_{1}, …, α_{n})^{T} = α > 0. (Note that the statement is true for α = (1, …, 1)^{T} by hypothesis.) As in the proof of Theorem 8, we conclude that the optimality criterion holds for a basic solution x_{α}^{∗} (corresponding to the basis B_{α}) if and only if it holds for x^{∗} (corresponding to the basis B). This is because matrices I(α_{i}; i) and I(α_{j}; j) commute for any α_{i}, α_{j} ∈ R_{+} and any i, j ∈ [m]). Hence, for any α > 0, the optimality criterion holds for x_{α}^{∗} (because, by hypothesis, the optimality criterion holds for x^{∗} corresponding to the basis B)

In order to show feasibility of x_{α}^{∗} we need to show that (B_{α})^{−1}b ≥ 0. We have

B_{α}^{−1}b = B^{−1}b + B^{−1}[Diag(\frac{1}{α_{1}} − 1, …, \frac{1}{α_{m}} − 1)b]
= x_{B}^{∗} + ∑_{i=1}^{m}(B^{−1})_{i}(\frac{1}{α_{i}} − 1)b_{i}
= x_{B}^{∗} + ∑_{i=1}^{m} b_{i} \frac{1 − α_{i}}{α_{i}} (B^{−1})_{i}

It remains to prove that

[ ∀α > 0 : x_{B}^{∗} + ∑_{i=1}^{m} b_{i} \frac{1 − α_{i}}{α_{i}} (B^{−1})_{i} ≥ 0 ] ⇔ B^{−1} ≥ 0.

Proof of (⇒): Note that we can set any of α_{i} := 1 by choosing Φ_{i} to be the identity function (which is certainly an admissible transformation). Therefore, by setting α_{j} = 1 for all j ≠ i, we see that the condition (B_{α})^{−1}b ≥ 0 implies

x_{B}^{∗} ≥ b_{i} \frac{α_{i} − 1}{α_{i}}(B^{−1})_{i}, i := 1, …, m.  (8)

As in the proof of Theorem 8 (when α_{i} → 0^{+}), using the fact that inf S_{i} = 0, we conclude that (B^{−1})_{i} ≥ 0 for every i = 1, …, m. Hence, if x_{α}^{∗} is feasible then B^{−1} ≥ 0. Proof of (⇐): if B^{−1} ≥ 0 then

B_{α}^{−1}b = ∑_{i=1}^{m} \frac{1}{α_{i}} (B^{−1})_{i}b_{i} ≥ 0

for any choice of α_{1}, …, α_{m} ∈ R_{+} (since b_{i} ≥ 0 by definition of problem (1)).

Corollary 13 Let B be an optimal basis for problem (1) such that B^{−1} ≥ 0. If for every i = 1, …, m, b_{i} from problem (1) is measured on a scale of measurement (A_{i}, B_{i}, f_{i}), where B_{i} is a relational system on R_{+}, then the statement that the basic variables of a basis B define an optimal basis for problem (1) is meaningful.

Proof: This is just one direction (sufficiency) of Theorem 12. Note that in the proof of sufficiency, we did not need the assumption inf S_{i} = 0.

Now we turn our attention to the case when w_{j}, a_{1j}, a_{2j}, …, a_{nj} are measured on the same scale of measurement.

Example 14 We consider the production problem from Example 1 again. Changing the definition of the unit of the j-th item will change all of w_{j}, a_{1j}, a_{2j},…, a_{nj}. (Of course, it is possible that all n items are measured on the same scale of measurement. In this case we would need to change w and A completely.) In the simplest possible case, if the new unit of the j-th item is α×(old unit), then w_{j}, a_{1j}, a_{2j},…, a_{nj} need to be replaced by αw_{j}, αa_{1j}, αa_{2j},…, αa_{nj}. In matrix form, this change can be written as multiplying both w^{T} and A from the right by the matrix I(α; j).

Proposition 15 Suppose that, for every j = 1, …, n, w_{j}, a_{1j}, a_{2j}, … a_{nj} are measured on a scale S_{j} which is stronger than or equal to a ratio scale. Then the statement that the basic variables of a basis B define an optimal basis for problem (1) is meaningful. Moreover, (x_{1}, …, x_{n})^{T} is an optimal solution for the original problem if and only if

x̄ = (\frac{1}{α_{1}} (x_{1}), …, \frac{1}{α_{n}} (x_{n}))^{T}

is an optimal solution for problem (1) where w_{j}, a_{1j}, a_{2j}, …, a_{nj} are replaced by α_{j}(w_{j}), α_{j}(a_{1j}), α_{j}(a_{2j}), …, α_{j}(a_{nj}), j = 1, … n.

Proof: Note that for any y ∈ R^{n}, (α_{1}w_{1}, …, α_{n}w_{n})ȳ = w^{T} y. Also note that replacing a_{1j}, a_{2j}, …, a_{nj} by α_{j}(a_{1j}), α_{j}(a_{2j}), …, α_{j}(a_{nj}), j = 1, … n, can be written in matrix form as replacing matrix A by matrix

A_{α} := A ∏_{j=1}^{n}[I(α_{j}; j)] = A[Diag(α_{1}, …, α_{n})].

Since ȳ = [Diag(α_{1}, …, α_{n})]^{−1}y, we have Ay = b ⇔ A_{α}ȳ = b. Finally, α_{1} > 0, …, α_{n} > 0 implies y ≥ 0 ⇔ ȳ ≥ 0.

Finally, we consider situations where w_{j}, j = 1, …, n, are not known precisely or where w_{j} are measured on some scale of measurement. In other words, Φ(w_{j}) is an acceptable replacement for w_{j} whenever Φ is an admissible transformation of the scale of measurement of w_{j}. We will make the (reasonable) assumption that Φ(w_{j}) and w_{j} have the same sign, i.e., w_{j}Φ(w_{j}) > 0 for all Φ. Similar to our analysis of the admissible transformations of b_{i}, here we can change the unit of the j-th item by replacing Φ(w_{j}), a_{1j}, a_{2j}, …, a_{nj} by w_{j} = αΦ(w_{j}), αa_{1j}, αa_{2j}, …, αa_{nj} where α = w_{j}/Φ(w_{j}) (> 0 by assumption).

Similar to our analysis of the meaningfulness of the conclusion of optimality in the case when b_{i} are measured on some scale of measurement, we will first give a detailed analysis of the case when just one w_{j} is measured on some scale of measurement (i.e., w_{k}, k ≠ j, are measured on an absolute scale) and then extend these results to the case when all w_{j}’s are measured on (possibly different) scales of measurement (Theorem 21).

Example 16 We turn once more to the production problem described in Example 1. The exact profit per unit of the j-th item, w_{j}, might not be known exactly (for example it might be proportional to the current market price). This can be viewed as w_{j} being measured on some scale of measurement S.

Also, for a fixed j, the numbers a_{1j}, a_{2j}, …, a_{nj} might not be known precisely but all the ratios q_{kl} = a_{jk}/a_{kl} might be known. For example, the production of the the j-th item might require a different amount of resources depending on the outside temperature (provided that the production process must be kept at the constant temperature) but it is known that the j-th item contains q_{kl} times more of the k-th ingredient(resource) than l-th ingredient(resource). In such a case, a_{1j}, a_{2j}, …, a_{nj} represent data measured on a common ratio scale.

The first step is to analyze the situation when a_{1j}, a_{2j}, …, a_{nj} are measured on a ratio scale of measurement.

Theorem 17 Let x^{∗} be an optimal solution for problem (1). Furthermore, let x^{∗} be a basic feasible solution of Ax = b and let j be a non-basic variable for x^{∗}. Suppose that a_{1j}, a_{2j}, …, a_{nj} are measured on a ratio scale of measurement. Then x^{∗} is a meaningful optimal solution to problem (1) if and only if z_{j} ≥ 0 ≥ w_{j}.

Proof: x^{∗} is a meaningful optimal solution if and only if x^{∗} is feasible and satisfies the optimality criterion whenever A is replaced by A[I(α; j)], α > 0.

Since j is non-basic, x_{j}^{∗} = 0 and x^{∗} = [I(α; j)]^{−1}x^{∗}. Therefore, for any α, A[I(α; j)]x^{∗} = b.

Hence it remains to show that the optimality criterion holds whenever A is replaced by A[I(α; j)] if and only if z_{j} ≥ 0 ≥ w_{j}. We first note that B remains unchanged since the j-th column of A is not a column of B. For any k ≠ j, A_{k} remains unchanged and consequently z_{k} − w_{k} remains unchanged and z_{k} − w_{k} ≥ 0 since x^{∗} is an optimal solution to problem (1). It remains to check the optimality criterion for k = j:

w_{B}^{T} B^{−1}(αA_{j}) − w_{j} ≥ 0.

This is equivalent to

z_{j} = w_{B}^{T} B^{−1}A_{j} ≥ \frac{1}{α}w_{j}.  (9)

Note that (9) holds for all α ≥ 0 (i.e., x^{∗} is a meaningful optimal solution) if and only if z_{j} ≥ 0 ≥ w_{j}.

Corollary 18 Let x^{∗} be an optimal solution for problem (1). Furthermore, let x^{∗} be a basic feasible solution of Ax = b and let j be a non-basic variable for x^{∗}. Suppose that w_{j} is measured on a scale of measurement S. Further suppose that the set

S := \{\frac{w_{j}}{Φ(w_{j})} : Φ ∈ AT (f)\} ⊆ R_{+}

is unbounded in R_{+} (i.e., inf S = 0 and sup S = ∞). Then x^{∗} is a meaningful optimal solution to problem (1) if and only if z_{j} ≥ 0 ≥ w_{j}

Proof: This follows directly from the proof of Theorem 17 and the fact that replacing w_{j} by Φ(w_{j}) is equivalent to replacing a_{1j}, …, a_{nj} by αa_{1j}, …, αa_{nj} where α = w_{j}/Φ(w_{j}). Note that x^{∗} is a meaningful optimal solution if and only if (9) holds for all α ∈ S. The latter is equivalent to z_{j} ≥ 0 ≥ w_{j} since inf S = 0 and sup S = ∞.

In what follows, (B^{−1})_{(r)} will denote the r-th row of the matrix B^{−1}.

Theorem 19 Let B be an optimal basis for problem (1) and let j be a basic variable for the corresponding optimal solution x^{∗}. Suppose that a_{1j}, a_{2j},…, a_{nj} are measured on a (common) ratio scale of measurement. Then the statement that the basic variables of a basis B define an optimal basis for problem (1) is meaningful if and only if

z_{k} − w_{k} ≥ w_{j}((B^{−1})_{(j)})A_{k} ≥ 0  (10)

holds for all non-basic variables k ∈ [n].

Proof: Let Φ(t) = αt, α > 0, be an admissible transformation of a_{1j}, a_{2j},…, a_{nj}. For any x ∈ R^{n} we define

x(α) := [I(α; j)]^{−1}x = (x_{1}, …, x_{j−1}, \frac{1}{α}x_{j}, x_{j+1}, …, x_{n})^{T} .

Then x ≥ 0 if and only if x(α) ≥ 0 (note that α > 0) and Ax = b if and only if A[I(α; j)]x(α) = b. Furthermore, if x is a basic feasible solution, then x(α) is also a basic feasible solution with the same basic variables.

Therefore, the meaningfulness is equivalent to the statement that, for any α > 0, x^{∗}(α) is an optimal solution for problem (1) where A is replaced by A[I(α; j)].

Note that x^{∗} is feasible for the original problem, so x^{∗}(α) is feasible for problem (1) where A is replaced by A[I(α; j)]. Therefore, we only need to check that (10) holds if and only if x^{∗}(α) satisfies the optimality criterion for any α > 0. Since j is a basic variable for x^{∗}, the matrix consisting of columns of A[I(α; j)] indexed by basic variables is just B[I(α; j)]. In other words, the basis matrix for x^{∗}(α) is just a basis matrix for x^{∗} where the j-th column is multiplied by α. Note that

(B[I(α; j)])^{−1} = [I(α; j)]^{−1}B^{−1} = [I(α^{−1}; j)]B^{−1}.

The optimality criterion trivially holds for basic variables. The optimality criterion for a non-basic variable k,

w_{B}^{T} (B[I(α; j)])^{−1}(A[I(α; j)])_{k} − w_{k} ≥ 0,

becomes

∑_{i=1}^{m}(w_{B})_{i}([I(α^{−1}; j)]B^{−1}A_{k})_{i} − w_{k} ≥ 0

since (AI(α; j))_{k} = A_{k} for every non-basic variable k. Also note that

(I(α; j)^{−1}B^{−1}A_{k})_{i} = \{ \begin{matrix}((B^{−1})_{(i)})A_{k} & if i ≠ j \\ \frac{1}{α}((B^{−1})_{(j)})A_{k} & if i = j \end{matrix}

Now we have

w_{B}^{T} (B[I(α^{−1}; j)](A[I(α; j)])_{k} − w_{k} = ∑_{i=1}^{m}(w_{B})_{i}((B^{−1})_{(i)})A_{k} − w_{k}

+w_{j}(\frac{1}{α} − 1)((B^{−1})_{(j)})A_{k}

= z_{k} − w_{k} + \frac{1 − α}{α}w_{j}((B^{−1})_{(j)})A_{k}

Therefore, the optimality criterion holds for all α if and only if for all nonbasic k,

z_{k} − w_{k} ≥ \frac{α − 1}{α}w_{j}((B^{−1})_{(j)})A_{k}  (11)

for all α > 0. It remains to show that (11) holds for all α > 0 if and only if (10) holds. As in the proof of Theorem 8 we observe that f(α) := C \frac{α−1}{α} is a monotone function on R_{+} and we only need to check that (11) holds when α → 0^{+} and when α → +∞.

When α→0^{+} then \frac{α−1}{α} →−∞ and (11) holds if and only if w_{j}((B^{−1})_{(j)})A_{k} ≥ 0. This is because z_{k} − w_{k} ≥ 0 by the optimality criterion for x^{∗}.

When α → +∞ then \frac{α−1}{α} → 1^{−} and (11) is equivalent to z_{k} − w_{k} ≥ w_{j}((B^{−1})_{(j)})A_{k}.

Corollary 20 Let B be an optimal basis for problem (1) and let j be a basic variable. Suppose that w_{j} is measured on a scale of measurement (A, B, f) where B is a relational system on R such that the set

S = \{\frac{w_{j}}{Φ(w_{j})} : Φ ∈ AT (f)\} ⊆ R_{+}

is unbounded in R_{+} (i.e., inf S = 0 and sup S = ∞) Then the statement that the basic variables of the basis B define an optimal basis for problem (1) is meaningful if and only if

z_{k} − w_{k} ≥ w_{j}((B^{−1})_{(j)})A_{k} ≥ 0

holds for all non-basic variables k ∈ [n].

Proof: This follows from the proof of Theorem 19 (in the same way as Corollary 18 follows from Theorem 17). Since inf S = 0 and sup S = ∞, we use the same argument as in the proof of Theorem 19

Theorem 21 Let B be an optimal basis for problem (1). Suppose that for every j = 1, …, n, w_{j} from problem (1) is measured on a scale of measurement (A_{j}, B_{j}, f_{j}) where B_{j} is a relational system on R. Further suppose that, for any j = 1, …, n,

S_{j} := \{\frac{w_{j}}{Φ_{j}(w_{j})} : Φ_{j} ∈ AT (f_{j})\} ⊆ R_{+}

is such that inf(S_{j}) = 0. Then the statement that the basic variables of the basis B define an optimal basis for problem (1) is meaningful if and only if

(w_{B})_{k}(B^{−1})_{(k)}A_{j} ≥ 0 ≥ w_{j}  (12)

for every basic variable k and every non-basic variable j.

Proof: We again note that replacing w_{j} by Φ_{j}(w_{j}) is equivalent to replacing a_{1j}, …,a_{mj} by α_{i}a_{1j}, …, α_{i}a_{mj} where α_{i} = w_{j}/Φ_{j}(w_{j}). For any x we define x̄ as in Proposition 15. Let x^{∗} be an optimal solution to problem (1) corresponding to B. Note that x̄^{∗} corresponds to a basis

B_{α} := B[Diag(α_{1}, …, α_{n})] = B(∏_{j=1}^{n} I(α_{j}; j)).

We also use the notation

A_{α} := A[Diag(α_{1}, …, α_{n})] = A ∏_{j=1}^{n} I(α_{j}; j).

Since B is an optimal basis by hypothesis, we need to prove that the statement “B_{α} is an optimal basis for problem (1) where A is replaced by A_{α}” is true for any α > 0 if and only if (12) holds. Note that the basic feasible solution x̄^{∗} ≥ 0 corresponding to B_{α} is always a feasible solution since A_{α}x̄^{∗} = b. Therefore, we just need to check that

(i) x̄^{∗} satisfies the optimality criterion for any choice of α_{j} ∈ S_{j}, j = 1, …, n. is equivalent to (ii) (w_{B})_{k}(B^{−1})_{(k)}A_{j} ≥ 0 ≥ w_{j} for every basic variable k and every non-basic variable j. Proof of (i) ⇒ (ii): Note that 1 ∈ S_{j} for every j since the identity function is always an admissible transformation. For any j, we set α_{i} := 1, i ≠ j, and let α_{j} → 0^{+}. If j is a non-basic variable then, as in the proof of Theorem 17, we conclude that 0 ≥ w_{j}. If j is a basic variable, then, as in the proof of Theorem 19, we conclude that (w_{B})_{j}(B^{−1})_{(j)}A_{i} ≥ 0 must hold for any non-basic variable i. Hence, (12) holds for every basic variable k and every non-basic variable j. Proof of (ii) ⇒ (i): Suppose that (12) holds for every basic variable k and every non-basic variable j and we need to show that x̄^{∗} satisfies the optimality criterion:

(w_{B})^{T} (B_{α}^{−1})(A_{α})_{j} − w_{j} ≥ 0

for every non-basic variable j (note that the optimality criterion always holds trivially for any basic variable j). Now,

(w_{B})^{T} (B_{α}^{−1})(A_{α})_{j} = ∑_{i=1}^{m}(w_{B})_{k}(B_{α}^{−1})_{(k)}(A_{α})_{j}
= ∑_{i=1}^{m}(w_{B})_{k} \frac{α_{j}}{α_{k}} (B^{−1})_{(k)}A_{j}
≥ 0
≥ w_{j}

where the first inequality holds because \frac{α_{j}}{α_{k}} > 0 and by using (12) for every basic variable k. The last inequality also holds by (12).

Example 22 Consider the problem from Example 11. Note that B, which is the optimal basis (the first and fourth variable are basic) satisfies (12). Hence, it is meaningful to say that the first and fourth variable are the basic variables of an optimal solution whenever w_{i} is measured on a scale S_{i}, i = 1, 2, 3, 4, satisfying the conditions of Theorem 21.

Example 23 To illustrate Theorem 21 we consider problem (1) where

w^{T} = (1, −1, 0, 0), A = ( \begin{matrix}1 & −2 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{matrix} ) , b^{T} = ( 1 1 ) .

It is easy to see that x^{∗} = (3, 1, 0, 0)^{T} is the optimal solution and the basic variables are 1 and 2. The corresponding optimal basis B and its inverse B^{−1} are

B = ( \begin{matrix}1 & −2 \\ 0 & 1 \end{matrix} ) , B^{−1} = ( \begin{matrix}1 & 2 \\ 0 & 1 \end{matrix} ) .

Note that (12) does not hold for k = 1 and j = 3. Hence, if w_{1} is measured on some scale of measurement satisfying the conditions of Theorem 21, the conclusion that the first and second variable are basic variables of an optimal solution is meaningless. For example, if we replace w_{1} with Φ(w_{1}), then

z_{4} − w_{4} = (Φ(w_{1}), −1) ( \begin{matrix}1 & 2 \\ 0 & 1 \end{matrix} ) ( 0 1 )) − 0 = 2Φ(w_{1}) − 1.

Hence, whenever Φ(w_{1}) < \frac{1}{2}, the basic feasible solution with basic variables 1 and 2 is not optimal since the optimality criterion does not hold.

5 Closing Remarks

We again point out (see Remark at the beginning of Section 3) that all results presented here can be easily reformulated without referring to scales of measurement and meaningfulness. For example, one could state Theorem 12 and Theorem 21 as follows: Theorem 12 (reformulated) Let B be an optimal basis for problem (1). Suppose that for every i = 1, …, m, G_{i} is a group of real-valued functions such that

S_{i} := \{\frac{b_{i}}{Φ_{i}(b_{i})} : Φ_{i} ∈ G_{i}\} ⊆ R_{+}

and such that inf(S_{i}) = 0. Then, B^{−1} ≥ 0 if and only if, for any choice of f_{1} ∈ G_{1}, …, f_{n} ∈ G_{n} the basic variables of B define an optimal basis for problem (1) where b = (b_{1}, …, b_{m})^{T} is replaced by (Φ_{1}(b_{1}), …, Φ_{m}(b_{m}))^{T} (i.e., the basic variables of an optimal basis are invariant under scaling of b_{i} by functions from G_{i}, i = 1, …, m). Theorem 21 (reformulated) Let B be an optimal basis for problem (1). Suppose that for every j = 1, …, n, G_{j} is a group of real-valued functions such that

S_{j} := \{\frac{w_{i}}{Φ_{j}(w_{j})} : Φ_{j} ∈ G_{j}\} ⊆ R_{+}

and such that inf(S_{j}) = 0. Then

(w_{B})_{k}(B^{−1})_{(k)}A_{j} ≥ 0 ≥ w_{j}

holds for every basic variable k and every non-basic variable j if and only if basic variables of B define an optimal basis for problem (1) where w = (w_{1}, …, w_{n})^{T} is replaced by (Φ_{1}(w_{1}), …, Φ_{n}(w_{n}))^{T} (i.e., the basic variables of an optimal basis are invariant under scaling of w_{j} by functions from G_{j}, j = 1, …, n).

It should be noted that the striking similarity of these two theorems as well as the presented proofs is no accident but a consequence of the duality in linear programming (more about duality can be found in any standard book on linear programming, e.g., see [1]).

Our analysis was limited to scalings by increasing linear (affine) transformations and scalings that can be related to these. It would be interesting to consider scalings by some other sets of functions and determine necessary and/or sufficient conditions for invariance of the conclusion of optimality. (Meaningfulness of the conclusion of optimality for optimization problems where the parameters of the objective function are measured on an ordinal scale is discussed in [5]). Sort of an inverse approach to the problem would also be interesting: given a problem (1) and a set of its parameters {p_{1}, …, p_{l}}, find the largest set of scaling functions, S, such that the conclusion of optimality is invariant under scaling of {p_{1}, …, p_{l}} by any function from S.

Finally, we note that characterizing invariance under scalings is not a problem that is limited to linear programming problems. In fact, such analysis can be applied to any mathematical model (invariance of the output with respect to scalings of input parameters). Of course, it is hopeless to expect some sensible results if the problem is stated in such generality. The main reason why we were able to characterize invariance of the conclusion of optimality for problem (1) under certain scalings is because of the simplicity of the objective function and the simplicity of the structure of the set of feasible solutions.

Acknowledgement. The support of the National Science Foundation under grant number SES-9211492 to Rutgers University is greatfully acknowledged. I also wish to thank Dr. Fred S. Roberts for his helpful comments.

References

[1] V. Chvatal. Linear Programming. Freeman, NY, 1983.

[2] B. Kolman and R.E. Beck. Elementary Linear Programming with Applications. Academic Press, CA, 2nd edition, 1995.

[3] N.V.R. Mahadev, A. Pekeč, and F.S. Roberts. On the meaningfulness of optimal solutions to scheduling problems: Can an optimal solution be non-optimal? Operations Research, 1997. to appear.

[4] A. Pekeč. Limitations on Conclusions from Combinatorial Optimization Models. PhD thesis, Rutgers University, 1996.

[5] A. Pekeč. Optimization under ordinal scales: When is a greedy solution optimal? Mathematical Methods of Operations Research, 46, 1997. to appear.

[6] F.S. Roberts. Measurement Theory. Addison-Wesley, Reading, MA, 1979.

[7] F.S. Roberts. Meaningfulness of conclusions from combinatorial optimization. Discr. Appl. Math., 29:221–241, 1990.

[8] F.S. Roberts. Limitations of conclusions using scales of measurement. In S.M. Pollock, M.H. Rothkopf, and A. Barnett, editors, Handbooks in OR & MS, volume 6, pages 621–671. North-Holland, NY, 1994.

Recent Publications in the BRICS Report Series

RS-96-48 Aleksandar Peke� c. Scalings in Linear Programming: Necessary and Suf�cient Conditions for Invariance. December 1996. 28 pp.

RS-96-47 Aleksandar Peke� c. Meaningful and Meaningless Solutions for Cooperative N-person Games. December 1996. 28 pp.

RS-96-46 Alexander E. Andreev and Sergei Soloviev. A Decision Algorithm for Linear Isomorphism of Types with Complexity Cn(log^{2}(n)). November 1996. 16 pp.

RS-96-45 Ivan B. Damg� ard, Torben P. Pedersen, and Birgit P�tzmann. Statistical Secrecy and Multi-Bit Commitments. November 1996. 30 pp.

RS-96-44 Glynn Winskel. A Presheaf Semantics of Value-Passing Processes. November 1996. 23 pp. Extended and revised version of paper appearing in Montanari and Sassone, editors, Concurrency Theory: 7th International Conference, CONCUR ’96 Proceedings, LNCS 1119, 1996, pages 98�114.

RS-96-43 Anna Ing� olfsd� ottir. Weak Semantics Based on Lighted Button Pressing Experiments: An Alternative Characterization of the Readiness Semantics. November 1996. 36 pp. An extended abstract to appear in the proceedings of the 10th Annual International Conference of the European Association for Computer Science Logic, CSL ’96.

RS-96-42 Gerth St�lting Brodal and Sven Skyum. The Complexity of Computing the k-ary Composition of a Binary Associative Operator. November 1996. 15 pp.

RS-96-41 Stefan Dziembowski. The Fixpoint Bounded-Variable Queries are PSPACE-Complete. November 1996. 16 pp. Presented at the 10th Annual International Conference of the European Association for Computer Science Logic, CSL ’96.