Optimizing the max-min function with a constraint on a two-sided linear system

1.   Introduction

Problems on algebraic structures, in which pairs of operations $(\max, +)$ or $(\max, \min)$ replace addition and multiplication of the classical algebra, appear in the literature from approximately the sixties of the last century, see e. g., ^[3,18]. A systematic theory of such algebraic structures was likely published for the first times in ^[3].

The behavior of discrete event systems, in which the individual components move from event to event rather than varying continuously through time, is often described using max-plus or max-min algebra. Max-min algebra is a convenient algebraic setting for some types of optimization problems, see ^[4]. It can be used in a range of practical problems related to scheduling and optimization, fuzzy discrete dynamical systems, graph theory, knowledge engineering, cluster analysis, fuzzy systems and for describing the diagnosis of technical devices ^[17,20], medical diagnosis ^[16] and offer many new problems. Discrete dynamical systems and the related algebraic structures were studied using max-min matrix operations in ^[3,5,15]. In recent decades, there has been significant effort to study systems of max-min linear equations in the form $A{\otimes} x = b$, where the elements of $A$ and $b$ represent capacities, relationships between certain objects, equipment reliability, and the like. In practice, these values are not precise numbers but are usually contained in some intervals. Interval arithmetic is an efficient way to represent matrices in a guaranteed way on a computer. Interval systems of linear equations of the form ${{\boldsymbol{A}}}{\otimes} x = {{\boldsymbol{b}}}$ have been intensively studied, see ^{[11,12,13,14,15]}.

Since the operation of maximum replacing addition is not a group operation, but only a semi-group one, there is substantial difference between solving systems with variables on one side of equation and systems with variables occurring on both sides, i. e., $A{\otimes} x = B{\otimes} x$. Two-sided max-min linear systems were studied in ^[6], where a simple polynomial algorithm was described.

The issue of linear programming (optimization) in classical algebra is well known and intensively researched. M. Hladík has dealt with interval versions of linear optimization in classical algebra in several publications, e.g., ^[7,8]. In max-plus algebra, max-linear programming (optimization) was introduced by Aminu and Butkovič in ^[1]. A special type of max-linear programming has been studied in ^[2]. Optimization problems of classical linear functions under an max-min equation constraint have been studied in ^[9,19].

In this paper, we shall deal with a two-sided system of linear equations of the form $A{\otimes} x{\oplus} c = B{\otimes} x{\oplus} d$, where $A$, $B$ are given square matrices, $b$, $d$ are column vectors and operations $\oplus$ and ${\otimes}$ are extended to matrices and vectors in the same way as in the classical algebra. We give an equivalent condition for its solvability. For a given objective function $f$, we shall deal with an optimization problem of type $f^\top{\otimes} x\rightarrow \max\text{ or } \min$ such that $A{\otimes} x{\oplus} c = B{\otimes} x{\oplus} d$. We will also solve an equation of the form $f(x) = v$ on the solution set of the equation $A{\otimes} x{\oplus} c = B{\otimes} x{\oplus} d$. Replacing an objective function $f$ and a number $v$ with an interval function ${{\boldsymbol{f}}}$ and an interval value ${{\boldsymbol{v}}}$ leads to the definition of several types of the reachability of interval value ${{\boldsymbol{v}}}$ by interval function ${{\boldsymbol{f}}}$.

The following example is a modified and extended version of the example listed in ^[6].

Example 1.1. Let us take a manufacturing company that transports components to produce a specific product from places $P_1, P_2, P_3$. Transportation means of different size are transporting these components from places $P_i, \ i = 1, 2, 3$ to place $T$, where the assembly line is located. The goods are unloaded in $T$, assembled and the transportation means with completed products have to return to $P_i$. We assume that the connection between $P_i$ and $T$ is only possible via one of the places $Q_j, \, j = 1, 2$, the roads between $P_i$ and $Q_j$ are one-way roads, and the capacity of the road in the direction from $P_i$ to $Q_j$ is equal to $a_{ij}$. The transport from $T$ to $P_i$ is carried out via other one-way roads between places $Q_j$ and $P_i$ with capacities of the road in the direction from $Q_j$ to $P_i$ equal to $b_{ij}$.

In Figure 1, there is an arrow $(P_i\, Q_j)$, if there exists a connection from $P_i$ to $Q_j$, and there is an arrow $(Q_j\, P_i)$ if there exists a connection from $Q_j$ to $P_i$, where $i = 1, 2, 3, 4, \ j = 1, 2, 3$. We have to join places $Q_j$ with $T$ by a two-way road with the same capacity $x_j$ in both directions. The maximum reachable capacity of the connection from $P_i$ to $T$ is therefore equal to $\max\limits_{j}\min\{a_{ij}, x_j\}$. Since the roads between $T$ and $Q_j$ are two-way roads, the maximum reachable capacity of the connection from $T$ to $P_i$ is equal to $\max\limits_{j}\min\{b_{ij}, x_j\}$ for $i = 1, 2, 3, 4$.

We assume that the transportation means can only pass through some roads with a capacity which is not smaller than the capacity of the transportation mean. So that each of the transportation means may return to $P_i$, it is natural to require for each $i = 1, 2, 3, 4$ that the maximal reachable capacity of the connection from $P_i$ to $T$ is equal to the maximal reachable capacity of the connection from $T$ to $P_i$ on the way back. We obtain

In general, suppose that there are $m$ places $P_1, P_2, \dots, P_m$ and $n$ transfer points $Q_1, Q_2, \dots, Q_n$. If the road from $P_{i}$ to $Q_j$ (from $Q_j$ to $P_{i}$) does not exist, we set $a_{ij} = 0$ ($b_{ij} = 0$).

Our task is to choose the appropriate capacities $x_{j}$ for any $j\in N, \, N = \{1, \; 2, \dots, \; n\}$ such that

for all $i\in M, \ M = \{1, 2, \dots, m\}$.

Assume that the amount of components in $T$ delivered from $P_i$ has to be at least $c_i$ and the missing goods are replenished from the stock. Similarly, the amount of completed products in $P_i$ delivered from $T$ has to be at least $d_i$. Therefore, we are looking for the solution of the equation

for each $i\in M$.

Let us provide more information about the organization of the paper and the results achieved. The next section is occupied by definitions and notations. Section 3 is devoted to the solvability of two-sided linear equations. The already known results for the solvability of the equation $A{\otimes} x = B{\otimes} x$ are extended by other properties. Besides that, the problem of solvability of the system $A{\otimes} x{\oplus} c = B{\otimes} x{\oplus} d$ is introduced. Theorem 3.1 gives an equivalent condition for its solvability. Section 4 deals with the problem of linear optimization. We give the range of values for the objective function $f$ on the set satisfying $A{\otimes} x{\oplus} c = B{\otimes} x{\oplus} d$. The main result is obtained in Theorem 4.3. In the last section we define the concept of reachability of the interval value by the interval objective function. We define eleven types of reachability. Theorems 5.2–5.5 provide equivalent conditions for them.

2.   Preliminaries

Max-min algebra is the triple $({\mathcal{I}}, \oplus, \otimes)$, where ${\mathcal{I}} = [O, I]$ is a linearly ordered dense set with the least element $O$ and the greatest element $I$, and $\oplus, \, {\otimes}$ are binary operations defined as follows:

The set of all $m\times n$ matrices over ${\mathcal{I}}$ is denoted by ${\mathcal{I}}(m, n)$, and the set of all column $n$-vectors over ${\mathcal{I}}$ by ${\mathcal{I}}(n)$. Specifically, $O(m, n)$ ($I(m, n)$) will be used for the matrix with all entries equal to $O$ ($I$). Operations $\oplus$ and ${\otimes}$ are extended to matrices and vectors in the same way as in the classical algebra. We consider the ordering $\leq$ on the sets ${\mathcal{I}}(m, n)$ and ${\mathcal{I}}(n)$ defined as follows:

● for $A, C\in {\mathcal{I}}(m, n):\ A\leq C$ if $a_{ij}\leq c_{ij}$ for each $i\in M$ and for each $j\in N$,

● for $x, y\in {\mathcal{I}}(n):\ x\leq y$ if $x_j\leq y_j$ for each $j\in N$.

We will use the monotonicity of ${\otimes}$, which means that for each $A, B\in {\mathcal{I}}(m, n)$ and for each $x, \ y\in {\mathcal{I}}(n)$, the implication

holds. Let $A\in {\mathcal{I}}(m, n)$ and $b\in {\mathcal{I}}(m)$. We can write the system of max-min linear equations in the matrix form

It is well known (see ^[3,21]) that system (2.1) is solvable if and only if the vector $x^*(A, b)$, defined by

for any $j\in N$, where $\min\emptyset = I$, is its solution. The vector $x^*(A, b)$ is called a principal solution of system (2.1).

Theorem 2.1. ^[3,21] Let $A \in {\mathcal{I}}(m, n)$ and $b \in {\mathcal{I}}(m)$ be given.

(ⅰ) If $A\otimes x = b$ for $x \in {\mathcal{I}}(n)$, then $x\leq x^*(A, b).$

(ⅱ) $A \otimes x^*(A, b)\leq b$.

(ⅲ) The system $A\otimes x = b$ is solvable if and only if $x^*(A, b)$ is its solution.

The properties of the principal solution are expressed in the following assertions.

Lemma 2.1. ^[3] Let $A \in {\mathcal{I}}(m, n)$ and $b, d\in {\mathcal{I}}(m)$ be given and let $b\leq d$. Then, $x^*(A, b)\leq x^*(A, d).$

3.   Two-sided systems of linear equations

In this section we will deal with the solution of systems with variables occurring on both sides of the equation. The already known results for the solvability of the equation $A{\otimes} x = B{\otimes} x$ are extended by other properties. Besides that, the problem of the solvability of the system $A{\otimes} x{\oplus} c = B{\otimes} x{\oplus} d$ is introduced.

3.1.   Solvability of $A{\otimes} x=B{\otimes} x$

Let $A\in{\mathcal{I}}(m, n)$, $B\in{\mathcal{I}}(m, n)$. Let us consider the system of the form

Let us note that (3.1) is always solvable, since for $\alpha\leq \min\{a_{ij}, b_{ij}, i\in M, \, j\in N\}$, the vector $x = (\alpha, \alpha, \dots, \alpha)\in{\mathcal{I}}(n)$ is its solution. In ^[6], the algorithm for finding the greatest solution of (3.1) such that $x\leq {\overline{x}}$, where ${\overline{x}}\in{\mathcal{I}}(n)$, was provided. We introduce this algorithm with slightly modified notations as it will be used in the main part of the paper. Some notations are necessary to do this. Set

Further, define

Suppose that ${\overline{x}}\notin S(A, B)$. It should be noted that if we exchange the $i$th row of matrix $A$ and the $i$th row of matrix $B$, we get a new system that has the same set of solutions as the original system. It follows that we may assume w.l.o.g. that $a_i({\overline{x}})\leq b_i({\overline{x}})$ for each $i\in M$. Let us set

and let us introduce the following notations for any given upper bound ${\overline{x}}$:

Algorithm: Greatest Solution

Input: matrices $A, \ B\in {\mathcal{I}}(m, n)$, vector ${\overline{x}}\in{\mathcal{I}}(n)$

Output: $x^*(A, B, {\overline{x}})$ – the greatest element of $S(A, B, {\overline{x}})$

begin

$\boxed{1}$ If ${\overline{x}}\in S(A, B, {\overline{x}})$ then $x^*(A, B, {\overline{x}}): = {\overline{x}}$; STOP;

$\boxed{2}$ Swap the rows of the matrices $A, \, B$ so that $a_i({\overline{x}})\leq b_i({\overline{x}})$ holds for all $i\in M$;

$\boxed{3}$ Compute $\alpha({\overline{x}})$, $M^ < (\alpha({\overline{x}}))$, $M^ = (\alpha({\overline{x}}))$, $J(\alpha({\overline{x}}))$;

$\boxed{4}$Set $\tilde x_j: = \alpha({\overline{x}})$ if $j\in N(\alpha({\overline{x}}))$, $\tilde x_j: = {\overline{x}}_j$ otherwise;

$\boxed{5}$ If $\tilde x\in S(A, B, {\overline{x}})$ then $x^*(A, B, {\overline{x}}): = \tilde x$; STOP;

$\boxed{6}$ Set ${\overline{x}}: = \tilde x$; go to $\boxed{2}$.

end

If we set ${\overline{x}} = I\in{\mathcal{I}}(n)$, the Greatest Solution algorithm finds the greatest element of $S(A, B)$, denoted by $x^*(A, B)$. On the other hand, there are several minimal solutions of (3.1), but it is not known whether there is the smallest element of $S(A, B)$.

Example 3.1. Let ${\mathcal{I}} = [0, 10]$. Find the greatest solution of the two-sided equation $A{\otimes} x = B{\otimes} x$, whereby

Solution. We have ${\overline{x}} = (10, 10, 10, 10, 10)^\top$.

$\boxed{1}$Since $A{\otimes}{\overline{x}} = (7, 6, 5, 5)^\top$ and $B{\otimes} {\overline{x}} = (6, 5, 8, 8)^\top$, ${\overline{x}}\notin S(A, B, {\overline{x}})$;

$\boxed{2}$ We swap the $1$st and $2$nd rows of $A$ and $B$ and obtain

$\boxed{3}$ Since $A{\otimes} {\overline{x}} = (6, 5, 5, 5)^\top$ and $B{\otimes} {\overline{x}} = (7, 6, 8, 8)$, we obtain $\alpha({\overline{x}}) = 5$, $M^ < (5) = \{2, 3, 4\}$, $M^ = (5) = \emptyset$, $N(5) = \{1, 2, 3\}$

$\boxed{4} < /p > < p > ● {\tilde x}: = (5, 5, 5, 10, 10)^\top$;

$\boxed{5}$Since $A{\otimes}{\tilde x} = (6, 5, 5, 5)^\top$; $B{\otimes}{\tilde x}: = (7, 5, 5, 5)^\top$, ${\tilde x}\notin S(A, B)$;

$\boxed{6} < /p > < p > ● {\overline{x}}: = (5, 5, 5, 10, 10)^\top$;

------------------------------------------------------------------------------------------

$\boxed{3}$ $\alpha({\overline{x}}) = 6$, $M^ < (6) = \{1\}$, $M^ = (6) = \emptyset$, $N(6) = \{4\}$;

$\boxed{4} < /p > < p > ● {\tilde x}: = (5, 5, 5, 6, 10)^\top$;

$\boxed{5}$Since $A{\otimes}{\tilde x} = (6, 5, 5, 5)^\top = B{\otimes}{\tilde x}$, ${\tilde x}\in S(A, B)$; $x^*(A, B, {\overline{x}}): = (5, 5, 5, 6, 10)^\top$; STOP

Answer: The greatest solution of the given equation is $x^*(A, B) = (5, 5, 5, 6, 10)^\top$.

Lemma 3.1. Let $x^*(A, B)$ be the greatest solution of (3.1). Then

for each $j\in N$, where $e^* = A{\otimes} x^*(A, B) = B{\otimes} x^*(A, B)$.

Proof. It is easy to see that, for each $e\in{\mathcal{I}}(m)$, the equality $A{\otimes} x = B{\otimes} x = e$ implies $e\leq e^*$. Since $A{\otimes} x^*(A, B) = e^*$ in accordance with Theorem 2.1, we obtain $x^*(A, B)\leq x^*(A, e^*)$. Similarly, $B{\otimes} x^*(A, B) = e^*$ implies $x^*(A, B)\leq x^*(B, e^*)$. Hence, $x^*(A, B)\leq\min\{x^*(A, e^*), x^*(B, e^*)\}$. Since $x^*(A, B)$ is the greatest solution of (3.1), the equality holds.

Denote $H(A, B) = \{a_{ij}, \, b_{ij}, i\in M, \, j\in N\}$. For a given $x\in{\mathcal{I}}(n)$, denote by ${\tilde x}$ the vector given by

Lemma 3.2. If $x\in S(A, B)$ then ${\tilde x}\in S(A, B)$.

Proof. Suppose that $x\in S(A, B)$. Then, for each $i\in M$, the equality $[A{\otimes} x]_i = [B{\otimes} x]_i$ is satisfied. Let $i\in M$ be arbitrary, but fixed. We shall prove that $[A{\otimes} {\tilde x}]_i = [B{\otimes} {\tilde x}]_i$. We shall distinguish three possibilities (not necessarily disjoint) for which we refer to Cases 1–3.

Case 1. If $[A{\otimes} x]_i = a_{ir}$ and $[B{\otimes} x]_i = b_{is}$ for some $r, \, s\in N$, then $a_{ir}\leq {\tilde x}_r$, $b_{is}\leq {\tilde x}_s$ and ${\tilde x}_r, {\tilde x}_s\neq O$, which implies $a_{ir}{\otimes} {\tilde x}_r = a_{ir}$ and $b_{is}{\otimes} {\tilde x}_s = b_{is}$. Together with $a_{ij}{\otimes} {\tilde x}_j\leq a_{ij}{\otimes} x_j$ and $b_{ij}{\otimes} {\tilde x}_j\leq b_{ij}{\otimes} x_j$, for each $j\in N$ we obtain $[A{\otimes} {\tilde x}]_i = a_{ir}$ and $[B{\otimes} {\tilde x}]_i = b_{is}$. Hence, $[A{\otimes} {\tilde x}]_i = [B{\otimes} {\tilde x}]_i$.

Case 2. If $[A{\otimes} x]_i = x_r$ and $[B{\otimes} x]_i = x_s$ for some $r, \, s\in N$, then $a_{ir}{\otimes} {\tilde x}_r = {\tilde x}_r\geq \bigoplus_{j\neq r}a_{ij}{\otimes} {\tilde x}_j$ and $b_{is}{\otimes} {\tilde x}_s = {\tilde x}_s\geq \bigoplus_{j\neq s}b_{ij}{\otimes} {\tilde x}_j$. Then, $[A{\otimes} {\tilde x}]_i = [B{\otimes} {\tilde x}]_i = {\tilde x}_r = {\tilde x}_s$ (the last equality follows from $x_r = x_s$).

Case 3. ⅰ) If $[A{\otimes} x]_i = x_r$ and $[B{\otimes} x]_i = b_{is}$ for some $r, \, s\in N$, then $x_r = b_{is}$, which implies ${\tilde x}_r = x_r$. Further, ${\tilde x}_s\geq b_{is}$. Since $x_r = {\tilde x}_r\geq \bigoplus_{j\neq r}a_{ij}{\otimes} {\tilde x}_j$ and $b_{is}{\otimes} {\tilde x}_s = b_{is}\geq \bigoplus_{j\neq s}b_{ij}{\otimes} {\tilde x}_j$, we obtain $[A{\otimes} {\tilde x}]_i = [B{\otimes} {\tilde x}]_i = x_r = b_{is}$.

ⅱ) If $[A{\otimes} x]_i = a_{ir}$ and $[B{\otimes} x]_i = x_s$ for some $r, \, s\in N$, the proof is similar to the proof of part ⅰ).

3.2.   Solvability of $A{\otimes} x{\oplus} c=B{\otimes} x{\oplus} d$

Let $A, \, B\in{\mathcal{I}}(m, n)$ and $c, \, d\in{\mathcal{I}}(m)$ be given. Let us consider the system

Returning to Example 1.1, we can see that using max-min algebra, (1.1) can be written in the form of (3.3).

We shall discuss the solvability of (3.3). If $c = d$, then system (3.3) is still solvable, since at least the solution of the system $A{\otimes} x = B{\otimes} x$ is also a solution of system (3.3). Suppose that $c\neq d$. In this case, system (3.3) may or may not have a solution. If we exchange $c_i$ and $d_i$ and at the same time we exchange the $i$th row of matrix $A$ and the $i$th row of matrix $B$ (that is, the matrices $A, \ B$ will change) so that $c_i\geq d_i$, the solution of the original equation is the same as the solution of the equation after changing the rows. So we can assume without loss of generality that $c\geq d$.

Denote by $M^ >$ the set $M^ > = \{i\in M; \, c_i > d_i\}$. The following lemma provides the necessary condition for the solvability of (3.3).

Lemma 3.3. If system (3.3) with $c\geq d$ is solvable then for each $i\in M^ >$ there exists $j\in N$ such that $b_{ij}\geq c_i.$

Proof. Suppose that there exists $i\in M$ such that $c_i > d_i$ and $b_{ij} < c_i$ for each $j\in N$. Then, $[B{\otimes} x]_i < c_i$ for each $x\in {\mathcal{I}}(n)$. Together with $d_i < c_i$, we obtain $[B{\otimes} x{\oplus} d]_i < c_i$. Since $[A{\otimes} x{\oplus} c]_i\geq c_i$, we obtain $[A{\otimes} x{\oplus} c]_i\neq [B{\otimes} x{\oplus} d]_i$ for each $x\in{\mathcal{I}}(n)$. Hence, (3.3) is not solvable.

Denote by $S(A, B, c, d)$ the set of all solutions of (3.3. If $S(A, B, c, d)\neq \emptyset$, we use the notation $x^*(A, B, c, d)$ for the greatest solution (3.3 which can always be calculated using the Greatest Solution algorithm.

Denote by ${(A|c)}$ and ${(B|d)}$ the matrices arising from $A$ and $B$, respectively, by adding columns $c$ and $d$, respectively. System (3.3) can be converted to the system

with unknown $x\in{\mathcal{I}}(n+1)$.

Theorem 3.1. System (3.3) is solvable if and only if $x^*_{n+1}({(A|c)}, {(B|d)}) = I$.

Proof. If (3.3) is solvable then there exists $x\in{\mathcal{I}}(n+1)$ satisfying (3.4) such that $x_{n+1}\geq\max\limits_{i\in M}\{c_i, \ d_i\}$. Then the vector $\hat x$ given by $\hat x_j = x_j$ for $j\in N$ and $\hat x_{n+1} = I$ is a solution of (3.4), too. It follows that $x^*_{n+1}({(A|c)}, {(B|d)}) = I$.

Conversely, if $x^*_{n+1}({(A|c)}, {(B|d)}) = I$, then $x^*(A, B, c, d)\in {\mathcal{I}}(n)$ such that $x_j^*(A, B, c, d) =$ $x_j^*({(A|c)}, {(B|d)})$ for $j\in N$ is a solution of (3.3).

4.   Optimization problems

Let us start with the extension of Example 1.1.

Example 1.1-continuation. The capacities $a_{ij}, \ b_{ij}, \ x_j$ do not necessarily have to be considered as absolute values of the number of components or products transported. We assume that these capacities express the ratio of the number of objects to a fixed value of the upper bound of this number. Then, all capacities are expressed by a number from the interval 0 to 1.

In practice, we may be interested not only in the capacity of a particular connection, but also in its reliability. A connection with high capacity but low reliability may be less advantageous than others with less capacity but high reliability. Let the reliability of the connection between $Q_j$ and $T$ in both directions be expressed by the number $f_j$. Then, the utility of the connection between $Q_j$ and $T$ is equal to $\min\{f_j, x_j\}$ and the maximum utility of the system is $f(x) = \max\limits_{j\in N}(f_j{\otimes} x_j) = f^\top{\otimes} x$. This leads to the question how to find $x\in{\mathcal{I}}(n)$ which satisfies (3.3) and ensures sufficient utility.

In this section, we develop methods for finding $x\in{\mathcal{I}}(n)$ that minimizes (maximizes) the function $f(x) = f^\top{\otimes} x$, where $f = (f_1, f_2, \dots, f_n)^\top\in{\mathcal{I}}(n)$ subject to Eq (3.3).

As it was mentioned in previous part, we can assume that $c\geq d$. In the case that (3.3) does not have a solution, the task does not make sense. Suppose that $S(A, B, c, d)\neq\emptyset$, and let

We start by calculating the upper bound, that is, $M(f)$.

Theorem 4.1. Let $A, \, B\in{\mathcal{I}}(m, n)$, $c, \, d\in{\mathcal{I}}(m)$ and $f\in{\mathcal{I}}(n)$ be given. Then,

Proof. Since $x\leq x^*(A, B, c, d)$ for each $x\in S(A, B, c, d)$, in accordance with the monotonicity of ${\otimes}$ we obtain ${f^\top}{\otimes} x\leq {f^\top}{\otimes} x^*(A, B, c, d)$.

Now, we shall discuss the lower bound. Define

Lemma 4.1. If $c\geq d$, then $f(x)\geq L$ for every $x\in S(A, B, c, d)$.

Proof. Let $x\in S(A, B, c, d)$ and $r\in M^ > .$ Then, $[B{\otimes} x]_r\geq c_r,$ which implies that there exists $k\in N$ such that $b_{rk}{\otimes} x_k\geq c_r$, and consequently $x_k\geq c_r$. Hence,

Since the previous inequality holds for each $r\in M^ >$, we obtain

The value of $L$ given by (4.1) gives us a lower bound that may or may not be reached by some solution of (3.3). Hence, $m(f)\geq L$.

Let $v\in{\mathcal{I}}$ be given. If we ask whether there exists $x\in S(A, B, c, d)$ such that $f(x) = v$, we are looking for the solution of the following non-homogeneous system:

where $O(n)$ denotes the row vector with any element equal to $O$. The above system can be converted to the system

where ${{(A|c)}^{O|v}}$ is the matrix formed from ${(A|c)}$ by adding the row $(O\ O\dots O\ v)$ as the last row, and ${{(B|d)}^{f|O}}$ is the matrix formed from ${(B|d)}$ by adding the row $(f_1\ f_2\dots f_n\ O)$ as the last row.

Lemma 4.2. Let $v\in{\mathcal{I}}$ be given. Then, there exists $x\in S(A, B, c, d)$ such that $f(x) = v$ if and only if

Proof. The proof is similar to the proof of Theorem 3.1.

Denote by $x^*(A, B, c, d, f, v)$ the greatest solution of (3.3) such that $f(x) = v$. It is easy to see that

for each $i\in N$.

Denote by ${{{\rm{Rv}}}}(f)$ the range of values of $f$ on $S(A, B, c, d)$, i. e.,

and set $H(A, B, c, d, f) = H(A, B)\cup\{c_i, d_i; \, i\in M\}\cup\{f_j; \, j\in N\}$.

Theorem 4.2. Let $v\in {{{\rm{Rv}}}}(f)$ be such that $v\notin H(A, B, c, d, f)$. Then, there exists ${\tilde v}\in H(A, B, c, d, f)$ such that ${\tilde v} < v$ and ${\tilde v}\in {{{\rm{Rv}}}}(f)$.

Proof. If there exists $x\in S(A, B, c, d)$ such that $f(x) = v\notin H(A, B, c, d, f)$, then $f(x) = \bigoplus\limits_{j = 1}^n f_j{\otimes} x_j = f_k{\otimes} x_k = x_k < f_k$ for some $k\in N$. Then, for the vector ${\tilde x}\in S(A, B, c, d)$ defined similarly as in (3.2) by formula

we obtain

for some $r\in N$. Denote ${\tilde v} = f({\tilde x})$. Since $f_r, {\tilde x}_r\in H(A, B, c, d, f)$, we obtain ${\tilde v}\in H(A, B, c, d, f)$ and ${\tilde v} < v$.

It follows from Theorem 4.2 that, in finding the value $m(f)$, it is sufficient to consider only the elements of the set $H(A, B, c, d, f)$.

Algorithm: Minimal value

Input: $A, \, B, \, c, \, d, \, f$

Output: minimal value $m(f)$

begin

$\boxed{1}$ Order the elements of $H(A, B, c, d, f)$ in such way that $h_1 < h_2 < \!\dots \! < h_s$.

$\boxed{2}$ Find $k$ such that $L = h_k$; $i: = k$;

$\boxed{3}$ $v: = h_i$; compute $x^*({{(A|c)}^{O|v}}, {{(B|d)}^{f|O}})$ using the Greatest Solution algorithm;

$\boxed{4}$ If $x^*_{n+1}({{(A|c)}^{O|v}}, {{(B|d)}^{f|O}}) = I$ then $m(f): = v$, STOP;

$\boxed{5}$ $i: = i+1$; go to $\boxed{2}$;

end

Once the values of $m(f)$ and $M(f)$ are calculated, the question which arises is whether all values between $m(f)$ and $M(f)$ can be achieved by some $x\in S(A, B, c, d)$. The following theorem gives an answer to this question.

Theorem 4.3. Let $A, \, B\in{\mathcal{I}}(m, n)$, $c, \, d\in{\mathcal{I}}(m)$ and $f\in{\mathcal{I}}(n)$ be given. Then,

Proof. {First, let $u\in {{{\rm{Rv}}}}(f)$. There then exists $x\in S(A, B, c, d)$ such that $f(x) = u$. Then,

We obtain that ${{{\rm{Rv}}}}(f)\subseteq [m(f), M(f)]$. To prove that $[m(f), M(f)]\subseteq {{{\rm{Rv}}}}(f)$ suppose that $v\in [m(f), M(f)]$. }To simplify notations, we shall use $m$ and $M$ instead of $m(f)$ and $M(f)$, respectively. Since $m\in{{{\rm{Rv}}}}(f)$ and $M\in{{{\rm{Rv}}}}(f)$, in accordance with Lemma 4.2 we have $x^*_{n+1}({{(A|c)}^{O|m}}, {{(B|d)}^{f|O}}) = I$ and $x^*_{n+1}({{(A|c)}^{O|M}}, {{(B|d)}^{f|O}}) = I$. We have to prove that $x^*_{n+1}({{(A|c)}^{O|v}}, {{(B|d)}^{f|O}}) = I$.

Denote by $e^m$, $e^M$ and $e^v$ the vectors

Suppose that $x^*_{n+1}({{(A|c)}^{O|v}}, {{(B|d)}^{f|O}}) = u\neq I$, which is equivalent to $e_{n+1}^v = u < v$.

Since $x^*({{(A|c)}^{O|v}}, {{(B|d)}^{f|O}})$ is a solution of (3.3), we have $u\geq \max\limits_{i\in M}\{c_i, d_i\}$. Let us take the vector

We obtain ${{(A|c)}^{O|v}}{\otimes} \hat x = \hat e^v$, where $\hat e^v_i = e^v_i$ for $i\in M$ and $\hat e^v_{n+1} = v$.

We have $e^m\leq \hat e^v\leq e^M$, $e^m_{n+1} = m$ and $e^M_{n+1} = M$. Since $x_{n+1}^*({{(B|d)}^{f|O}}, e^m) = x_{n+1}^*({{(B|d)}^{f|O}}, e^M) = I$, in accordance with Lemma 2.1 we obtain $x_{n+1}^*({{(B|d)}^{f|O}}, \hat e^v) = I$.

Since ${{(A|c)}^{O|v}}{\otimes} \hat x = {{(B|d)}^{f|O}}{\otimes}\hat x = \hat e^v$ and $\hat e^v_{n+1} = v$, we obtain the contradiction to that $x_{n+1}^*({{(A|c)}^{O|v}}, {{(B|d)}^{f|O}})\neq I$.

Denote by ${x^*}(A, B, c, d, f, v)$ the greatest solution of (3.3) such that $f(x)\; = \; v$. The following theorem gives the necessary and sufficient condition for the solvability of the system of inequalities.

Theorem 4.4. Let $A, B\in{\mathcal{I}}(m, n)$, $c, \, d\in{\mathcal{I}}(m)$, $f_1, \, f_2\in {\mathcal{I}}(n)$ and $v_1, \, v_2\in{\mathcal{I}}$ be given. Then, the system of inequalities

has a solution $x\in{S(A, B, c, d)}$ if and only if either

or there exists $x\in{S(A, B, c, d)}$ such that

Proof. If condition (4.5) is satisfied, then the equalities $M(f_1) = f_1(x^*(A, B, c, d))$, $M(f_2) = f_2(x^*(A, B, c, d))$ imply that the vector $x^*(A, B, c, d)$ is a solution of the systems (4.3) and (4.4).

In the second case, if (4.6) holds, then $x^*(A, B, c, d, f_1, v_1)$ is a solution of the systems (4.3) and (4.4).

For the converse implication suppose that systems (4.3) and (4.4) are solvable and condition (4.5) is not satisfied. We have to prove that condition (4.6) is satisfied.

If system (4.3) and (4.4) are solvable and $f_2(x^*(A, B, c, d)) < v_2$, then $f_2(x) < v_2$ for each $x\; \in\; {S(A, B, c, d)}$, which is incompatible with the solvability of systems (4.3) and (4.4). This means that this assumption is never fulfilled, hence the implication holds.

If systems (4.3) and (4.4) are solvable and $M(f_1) > v_1$, then, in accordance with Theorem 4.3, there exists $x\in{S(A, B, c, d)}$, $x\leq x^*(A, B, c, d, f_1, v_1)$ such that $f_1(x) = v_1$. Since for each $x\in{S(A, B, c, d)}$ such that $f_1(x) = v\leq v_1$ the inequality $x\leq x^*(A, B, c, d, f_1, v)\leq x^*(A, B, c, d, f_1, v_1)$ holds, the existence of $x$ such that $f_2(x)\geq v_2$ implies $f_2(x^*(A, B, c, d, f_1, v_1))\geq v_2$.

Example 4.1. Let ${\mathcal{I}} = [0, 10]$. Check whether the system $A{\otimes} x{\oplus} c = B{\otimes} x{\oplus} d$ is solvable and in positive case find the range of values ${{{\rm{Rv}}}}(f)$, if

We have $M^ > = \{2, \, 3, \, 4\}$. Since for each $i\in M^ >$ there exists $j\in N$ such that $b_{ij}\geq c_i$, the necessary condition for the solvability of $A{\otimes} x{\oplus} c = B{\otimes} x{\oplus} d$ given by Lemma 3.3 is satisfied. We shall continue with computing the greatest solution of the system ${(A|c)}{\otimes} x = {(B|d)}{\otimes} x$, namely,

The above system was solved in Example 3.1, so we have $x^*({(A|c)}, {(B|d)}) = (5, 5, 5, 6, 10)^\top$. Since $x_5^*({(A|c)}, {(B|d)}) = 10 = I$, the system $A{\otimes} x{\oplus} c = B{\otimes} x{\oplus} d$ is solvable and $x^*(A, B, c, d) = (5, 5, 5, 6)^\top$.

We compute the value $M(f) = f^\top{\otimes} x^*(A, B, c, d) = 6$. To find the value $m(f)$ we first compute the value $L$ by formula (4.1). We obtain

so $f(x)\geq 3$ for each $x\in{S(A, B, c, d)}$.

For checking whether there exists $x\in{S(A, B, c, d)}$ such that $f(x) = v$, we solve the matrix equation

For $v = 3$ we obtain $x^*({{(A|c)}^{O|v}}, {{(B|d)}^{f|O}}) = (3, 3, 3, 3, 3)^\top$. Since $x_5^*({{(A|c)}^{O|v}}, {{(B|d)}^{f|O}})\neq I$, there is no $x\in {S(A, B, c, d)}$ such that $f(x) = 3$.

We continue with $v = 4$. We obtain $x^*({{(A|c)}^{O|v}}, {{(B|d)}^{f|O}}) = (5, 4, 5, 4, 10)^\top$. Hence, there exists $x\in{S(A, B, c, d)}$, namely $x = (5, 4, 5, 4)^\top$ such that $f(x) = 4$. Hence, $m(f) = 4$ and $x^*(A, B, c, d, f, 4) = (5, 4, 5, 4)^\top$. In accordance with Theorem 4.3, we have

5.   Interval optimization

In this part, we shall deal with the case that the entries of the objective function $f$ are not exact values, but they are in intervals of possible values. Define an interval function ${{\boldsymbol{f}}}$ as follows:

In this way ${{\boldsymbol{f}}}$ denotes a real vector-interval as is usual in interval mathematics. Further, denote

Theorem 5.1. Let $A\in{\mathcal{I}}(m, n), \ B\in{\mathcal{I}}(m, n)$, $c, \, d\in{\mathcal{I}}(m)$ and ${{\boldsymbol{f}}}$ be given. Then,

Proof. It is clear that ${{{\rm{Rv}}}}({{\boldsymbol{f}}}) = \mathop \cup \limits_{f\in{{\boldsymbol{f}}}}{{{\rm{Rv}}}}(f) = {{{\rm{Rv}}}}({\underline f})\cup(\mathop \cup \limits_{f\in{{\boldsymbol{f}}}, f\neq{\underline f}}{{{\rm{Rv}}}}(f))$. According to Theorem 4.3 we have ${{{\rm{Rv}}}}({\underline f}) = [m({\underline f}), M({\underline f})]$, so ${{{\rm{Rv}}}}({\underline f})$ is a dense continuous set. Since $M(f) = f({x^*}(A, B, c, d))$ for each $f\in{{\boldsymbol{f}}}$, we obtain that $M(f)$ is a continuous function defined on the set ${{\boldsymbol{f}}}$, and hence $\{M(f); \, f\in{{\boldsymbol{f}}}\} = [M({\underline f}), M({\overline f})]$, which is a dense set. In accordance with those, for each $v\in [M({\underline f}), M({\overline f})]$ there exists $f\in{{\boldsymbol{f}}}$ such that $v = M(f)$. Then, ${{{\rm{Rv}}}}({{\boldsymbol{f}}}) = [m({\underline f}), M({\underline f})]\cup(\mathop \cup \limits_{f\in{{\boldsymbol{f}}}, \ f\neq{\underline f}}[m(f), M(f)]) = [m({\underline f}), M({\overline f})]$.

In the following, we will deal with the situation where we require the values of the function $f\in{{\boldsymbol{f}}}$ to be in a given range of allowable values ${{\boldsymbol{v}}} = [{\underline v}, {\overline v}]$. We say that the value $v$ is reachable by $f$, if $f(x) = v$ for some $x\in {S(A, B, c, d)}$.

We can define several types of interval reachability. For example, we can require the existence of $v\in{{\boldsymbol{v}}}$ such that $f(x) = v$ for some $f\in{{\boldsymbol{f}}}$ and for some $x\in{S(A, B, c, d)}$. Another possibility is to require the existence of such a vector $x\in{S(A, B, c, d)}$ so that $f(x)\in{{\boldsymbol{v}}}$ for each $f\in{{\boldsymbol{f}}}$. By using general and existential quantifiers for $x, f$ and $v$ in different orders, we obtain many types of interval reachability.

Definition 5.1. Let $A, B\in{\mathcal{I}}(m, n)$, $c, \, d\in{\mathcal{I}}(m)$, ${{\boldsymbol{f}}}$ and ${{\boldsymbol{v}}}$ be given. An interval value ${{\boldsymbol{v}}}$ is

ⅰ) weakly possibly reachable by ${{\boldsymbol{f}}}$ if there exist $x\in{S(A, B, c, d)}$, $f\in{{\boldsymbol{f}}}$ and $v\in{{\boldsymbol{v}}}$ such that $f(x) = v$,

ⅱ) possibly reachable by ${{\boldsymbol{f}}}$ if for each $x\in{S(A, B, c, d)}$ there exist $f\in{{\boldsymbol{f}}}$ and $v\in{{\boldsymbol{v}}}$ such that $f(x) = v$,

ⅲ) strongly possibly reachable by ${{\boldsymbol{f}}}$ if there exists $v\in{{\boldsymbol{v}}}$ such that for each $x\in{S(A, B, c, d)}$ there exist $f\in{{\boldsymbol{f}}}$ such that $f(x) = v$.

Theorem 5.2. Let $A, B\in{\mathcal{I}}(m, n)$, $c, \, d\in{\mathcal{I}}(m)$, ${{\boldsymbol{f}}}\subseteq{\mathcal{I}}(n)$ and ${{\boldsymbol{v}}}\subseteq {\mathcal{I}}$ be given. An interval value ${{\boldsymbol{v}}}$ is

ⅰ) weakly possibly reachable by ${{\boldsymbol{f}}}$ if and only if there exists $x\in{S(A, B, c, d)}$ such that

ⅱ) possibly reachable by ${{\boldsymbol{f}}}$ if and only if

ⅲ) strongly possibly reachable by ${{\boldsymbol{f}}}$ if and only if it is possibly reachable by ${{\boldsymbol{f}}}$ and $M({\underline f})\leq m({\overline f})$.

Proof. For a fixed $x\in{S(A, B, c, d)}$, the existence of $f\in{{\boldsymbol{f}}}$ and $v\in{{\boldsymbol{v}}}$ such that $f(x) = v$ is equivalent to the existence of $f\in{{\boldsymbol{f}}}$ such that $f(x)\in{{\boldsymbol{v}}}$. Since $\{f(x); f\in{{\boldsymbol{f}}}\} = [{\underline f}(x), {\overline f}(x)]$, we obtain $[{\underline f}(x), {\overline f}(x)]\cap[{\underline v}, {\overline v}]\neq\emptyset$, which is equivalent to system (5.1).

ⅰ) The weakly possible reachability means the existence of solution of (5.1) in the set ${S(A, B, c, d)}$, which can be verified using Theorem 4.4.

ⅱ) The possible reachability means that the system (5.1) is satisfied for each $x\in{S(A, B, c, d)}$. The equality ${\underline f}(x)\leq {\overline v}$ holds for each $x\in{S(A, B, c, d)}$ if and only if $M({\underline f})\leq{\overline v}$. Similarly, validity of the equation ${\overline f}(x)\geq {\underline v}$ for each $x\in{S(A, B, c, d)}$ is equivalent to $m({\overline f})\geq {\underline v}$.

ⅲ) We can write the proof as a sequence of equivalences

because the condition $[M({\underline f}), m({\overline f})]\cap [{\underline v}, {\overline v}]\neq \emptyset$ is equivalent to the being possibly reachable.

Corollary 5.1. If an interval value ${{\boldsymbol{v}}}$ is strongly possibly reachable by ${{\boldsymbol{f}}}$, then it is possibly reachable by ${{\boldsymbol{f}}}$ and if it is possibly reachable by ${{\boldsymbol{f}}}$, then it is weakly possibly reachable by ${{\boldsymbol{f}}}$.

Definition 5.2. Let $A, B\in{\mathcal{I}}(m, n)$, $c, \, d\in{\mathcal{I}}(m)$, ${{\boldsymbol{f}}}\subseteq{\mathcal{I}}(n)$ and ${{\boldsymbol{v}}}\subseteq {\mathcal{I}}$ be given. An interval value ${{\boldsymbol{v}}}$ is

ⅰ) tolerably reachable by ${{\boldsymbol{f}}}$ if there exists $x\in{S(A, B, c, d)}$ such that for each $f\in{{\boldsymbol{f}}}$ there exists $v\in{{\boldsymbol{v}}}$ such that $f(x) = v$,

ⅱ) strongly tolerably reachable by ${{\boldsymbol{f}}}$ if for each $x\in{S(A, B, c, d)}$ and for each $f\in{{\boldsymbol{f}}}$ there exists $v\in{{\boldsymbol{v}}}$ such that $f(x) = v$,

ⅲ) weakly tolerably reachable by ${{\boldsymbol{f}}}$ if for each $f\in{{\boldsymbol{f}}}$ there exist $x\in{S(A, B, c, d)}$ and $v\in{{\boldsymbol{v}}}$ such that $f(x) = v$.

Theorem 5.3. Let $A, B\in{\mathcal{I}}(m, n)$, $c, \, d\in{\mathcal{I}}(m)$, ${{\boldsymbol{f}}}\subseteq{\mathcal{I}}(n)$ and ${{\boldsymbol{v}}}\subseteq {\mathcal{I}}$ be given. An interval value ${{\boldsymbol{v}}}$ is

ⅰ) tolerably reachable by ${{\boldsymbol{f}}}$ if and only if there exists $x\in{S(A, B, c, d)}$ such that

ⅱ) strongly tolerably reachable by ${{\boldsymbol{f}}}$ if and only if

ⅲ) weakly tolerably reachable by ${{\boldsymbol{f}}}$ if and only if

Proof. Let $x\in{S(A, B, c, d)}$ be fixed. Then for each $f\in{{\boldsymbol{f}}}$ there exists $v\in{{\boldsymbol{v}}}$ such that $f(x) = v$ if and only if $[{\underline f}(x), {\overline f}(x)]\subseteq[{\underline v}, {\overline v}]$, which is equivalent to system (5.3).

ⅰ) An interval value ${{\boldsymbol{v}}}$ is tolerably reachable by ${{\boldsymbol{f}}}$ if and only if (5.3) has a solution in ${S(A, B, c, d)}$. The necessary and sufficient condition for the solvability of (5.3) is given by Theorem 4.4.

ⅱ) The strongly tolerable reachability means that each $x\in {S(A, B, c, d)}$ satisfies system (5.3). Validity of the equality ${\overline f}(x)\leq {\overline v}$ for each $x\in{S(A, B, c, d)}$ is equivalent to $M({\overline f})\leq{\overline v}$. Similarly, ${\underline f}(x)\geq {\underline v}$ for each $x\in{S(A, B, c, d)}$ if and only if $m({\underline f})\geq {\underline v}$.

ⅲ) The proof of weakly tolerable reachability follows from the following equivalences

Corollary 5.2. If an interval value ${{\boldsymbol{v}}}$ is strongly tolerably reachable by ${{\boldsymbol{f}}}$, then it is possibly tolerably by ${{\boldsymbol{f}}}$ and if it is tolerably reachable by ${{\boldsymbol{f}}}$, then it is weakly tolerably reachable by ${{\boldsymbol{f}}}$.

Definition 5.3. Let $A, B\in{\mathcal{I}}(m, n)$, $c, \, d\in{\mathcal{I}}(m)$, ${{\boldsymbol{f}}}\subseteq{\mathcal{I}}(n)$ and ${{\boldsymbol{v}}}\subseteq {\mathcal{I}}$ be given. An interval value ${{\boldsymbol{v}}}$ is

ⅰ) controllably reachable by ${{\boldsymbol{f}}}$ if there exists $x\in{S(A, B, c, d)}$ such that for each $v\in{{\boldsymbol{v}}}$ there exists $f\in{{\boldsymbol{f}}}$ such that $f(x) = v$,

ⅱ) strongly controllably reachable by ${{\boldsymbol{f}}}$ if for each $x\in{S(A, B, c, d)}$ and for each $v\in{{\boldsymbol{v}}}$ there exists $f\in{{\boldsymbol{f}}}$ such that $f(x) = v$,

ⅲ) weakly controllably reachable by ${{\boldsymbol{f}}}$ if for each $v\in{{\boldsymbol{v}}}$ there exist $x\in{S(A, B, c, d)}$ and $f\in{{\boldsymbol{f}}}$ such that $f(x) = v$.

Theorem 5.4. Let $A, B\in{\mathcal{I}}(m, n)$, $c, \, d\in{\mathcal{I}}(m)$, ${{\boldsymbol{f}}}\subseteq{\mathcal{I}}(n)$ and ${{\boldsymbol{v}}}\subseteq {\mathcal{I}}$ be given. An interval value ${{\boldsymbol{v}}}$ is

ⅰ) controllably reachable by ${{\boldsymbol{f}}}$ if and only if there exists $x\in{S(A, B, c, d)}$ such that

ⅱ) strongly controllably reachable by ${{\boldsymbol{f}}}$ if and only if

ⅲ) weakly controllably reachable by ${{\boldsymbol{f}}}$ if and only if

Proof. Let $x\in{S(A, B, c, d)}$ be given. Then for each $v\in{{\boldsymbol{v}}}$ there exists $f\in{{\boldsymbol{f}}}$ such that $f(x) = v$ if and only if $[{\underline v}, {\overline v}]\subseteq[{\underline f}(x), {\overline f}(x)]$, which is equivalent to system (5.6).

ⅰ) An interval value ${{\boldsymbol{v}}}$ is controllably reachable by ${{\boldsymbol{f}}}$ if and only if (5.6) has a solution in ${S(A, B, c, d)}$, which can be checked by Theorem 4.4.

ⅱ) The strongly controllable reachability means that each $x\in {S(A, B, c, d)}$ satisfies the system (5.6). Validity of system (5.6) for each $x\in {S(A, B, c, d)}$ is equivalent to (5.7).

ⅲ) The weakly controllable reachability is equivalent to ${{\boldsymbol{v}}}\subseteq {{{\rm{Rv}}}}({{\boldsymbol{f}}})$, i. e., $[{\underline v}, {\overline v}]\subseteq [m({\underline f}), M({\overline f})]$. Hence, weakly controllable reachability is equivalent to (5.8).

Corollary 5.3. If an interval value ${{\boldsymbol{v}}}$ is strongly controllably reachable by ${{\boldsymbol{f}}}$, then it is possibly controllably reachable by ${{\boldsymbol{f}}}$, and if it is controllably reachable by ${{\boldsymbol{f}}}$, then it is weakly controllably reachable by ${{\boldsymbol{f}}}$.

Definition 5.4. Let $A, B\in{\mathcal{I}}(m, n)$, $c, \, d\in{\mathcal{I}}(m)$, ${{\boldsymbol{f}}}\subseteq{\mathcal{I}}(n)$ and ${{\boldsymbol{v}}}\subseteq {\mathcal{I}}$ be given. An interval value ${{\boldsymbol{v}}}$ is

ⅰ) universally reachable by ${{\boldsymbol{f}}}$ if there exists $v\in{{\boldsymbol{v}}}$ such that $f(x) = v$ for each $x\in{S(A, B, c, d)}$ and for each $f\in{{\boldsymbol{f}}}$,

ⅱ) weakly universally reachable by ${{\boldsymbol{f}}}$ if there exist $v\in{{\boldsymbol{v}}}$ and $x\in{S(A, B, c, d)}$ such that $f(x) = v$ for each $f\in{{\boldsymbol{f}}}$.

Theorem 5.5. Let $A, B\in{\mathcal{I}}(m, n)$, $c, \, d\in{\mathcal{I}}(m)$, ${{\boldsymbol{f}}}\subseteq{\mathcal{I}}(n)$ and ${{\boldsymbol{v}}}\subseteq {\mathcal{I}}$ be given. An interval value ${{\boldsymbol{v}}}$ is

ⅰ) universally reachable by ${{\boldsymbol{f}}}$ if and only if $m({\underline f}) = M({\overline f})\in{{\boldsymbol{v}}}$,

ⅱ) weakly universally reachable by ${{\boldsymbol{f}}}$ if and only if there exists $x\in{S(A, B, c, d)}$ such that ${\underline f}(x) = {\overline f}(x)\in{{\boldsymbol{v}}}$.

Proof. ⅰ) The universal reachability is equivalent to ${{{\rm{Rv}}}}({{\boldsymbol{f}}}) = \{v\}$ for some $v\in{{\boldsymbol{v}}}$. According to Theorem 4.3, the assertion follows.

ⅱ) Let $x\in{S(A, B, c, d)}$ be such that ${\underline f}(x) = {\overline f}(x)\in{{\boldsymbol{v}}}$. Then there exists $v\in{{\boldsymbol{v}}}$ such that for each $f\in {{\boldsymbol{f}}}$ we have $v = {\underline f}(x)\leq f(x)\leq {\overline f}(x) = v$, which implies $f(x) = v\in{{\boldsymbol{v}}}$.

The converse implication trivially follows.

Theorem 5.5 ⅱ) does not give an algorithm for checking whether there exists $x\in{S(A, B, c, d)}$ such that ${\underline f}(x) = {\overline f}(x)\in{{\boldsymbol{v}}}$. To decide on the existence of such a solution, we solve the equation

Denote by ${x^*}(A, B, c, d, {\underline f}, {\overline f})$ the greatest solution of (3.3) such that ${\underline f}(x) = {\overline f}(x)$, if such a solution exists. We shall continue as follows:

● If ${x^*}_{n+1}({{(A|c)}^{{\underline f}|O}}, {{(B|d)}^{{\overline f}|O}})\neq I$ or ${\underline f}^\top{\otimes}{x^*}(A, B, c, d, {\underline f}, {\overline f}) = {\overline f}^\top{\otimes}{x^*}(A, B, c, d, {\underline f}, {\overline f}) < {\underline v}$, then ${{\boldsymbol{v}}}$ is not weakly universally reachable by ${{\boldsymbol{f}}}$.

● If ${x^*}_{n+1}({{(A|c)}^{{\underline f}|O}}, {{(B|d)}^{{\overline f}|O}}) = I$ and ${\underline f}^\top{\otimes}{x^*}(A, B, c, d, {\underline f}, {\overline f}) = {\overline f}^\top{\otimes}{x^*}(A, B, c, d, {\underline f}, {\overline f})\in{{\boldsymbol{v}}}$ then ${{\boldsymbol{v}}}$ is weakly universally reachable by ${{\boldsymbol{f}}}$.

● If ${x^*}_{n+1}({{(A|c)}^{{\underline f}|O}}, {{(B|d)}^{{\overline f}|O}}) = I$ and ${\underline f}^\top{\otimes}{x^*}(A, B, c, d, {\underline f}, {\overline f}) =$ ${\overline f}^\top{\otimes}{x^*}(A, B, c, d, {\underline f}, {\overline f}) > {\overline v}$, then we add to matrices ${{(A|c)}^{{\underline f}|O}}$, ${{(B|d)}^{{\overline f}|O}}$ the rows $O|{\overline v}$ and ${\overline f}|O$, respectively. Then, ${{\boldsymbol{v}}}$ is weakly universally reachable by ${{\boldsymbol{f}}}$ if and only if the greatest solution of the obtained system has the $(n+1)$-st coordinate equal to $I$.

Corollary 5.4. If an interval value ${{\boldsymbol{v}}}$ is strongly universally reachable by ${{\boldsymbol{f}}}$, then it is weakly universally reachable by ${{\boldsymbol{f}}}$.

Despite the relations in Corollaries 1–4, the following implications hold:

● If an interval value ${{\boldsymbol{v}}}$ is strongly controllably reachable by ${{\boldsymbol{f}}}$, then it is strongly possibly reachable by ${{\boldsymbol{f}}}$ and strongly tolerably reachable by ${{\boldsymbol{f}}}$.

● If an interval value ${{\boldsymbol{v}}}$ is universally reachable by ${{\boldsymbol{f}}}$, then it is strongly possibly reachable by ${{\boldsymbol{f}}}$ and strongly tolerably reachable by ${{\boldsymbol{f}}}$.

● If an interval value ${{\boldsymbol{v}}}$ is weakly universally reachable by ${{\boldsymbol{f}}}$, then it is tolerably reachable by ${{\boldsymbol{f}}}$.

Example 5.1. Decide about all defined types of reachability of interval value ${{\boldsymbol{v}}} = [3, 6]$ by ${{\boldsymbol{f}}} = ([2, 4], [1, 5], [2, 3], [4, 6])^\top$ in accordance with $A{\otimes} x{\oplus} c = B{\otimes} x{\oplus} d$, where $A, \, B, \, c, \, d$ are matrices and vectors from Example 4.1.

Since the current function ${\overline f}$ is the function $f$ from Example 4.1, we have $m({\overline f}) = 4$ and $M({\overline f}) = 6$. We compute $M({\underline f}) = {\underline f}^\top{\otimes} {x^*}(A, B, c, d) = 4$ and find $m({\underline f})$ in the same way as in Example 4.1. We obtain $m({\underline f}) = 2$. We can now discuss the types of reachability.

We start with possible reachability. Since $M({\underline f}) = 4\leq 6 = {\overline v}$ and $m({\overline f}) = 4\geq 2 = {\underline v}$, in accordance with Theorem 5.2 ⅱ), ${{\boldsymbol{v}}}$ is possibly reachable by ${{\boldsymbol{f}}}$. Moreover, $M({\underline f}) = 4 = m({\overline f})$, which implies that ${{\boldsymbol{v}}}$ is strongly possibly reachable by ${{\boldsymbol{f}}}$. By the definition we obtain that ${{\boldsymbol{v}}}$ is weakly possibly reachable by ${{\boldsymbol{f}}}$, too.

For strongly tolerable reachability, we check whether inequalities (5.4) are satisfied. Since $m({\underline f}) = 2 < 3 = {\underline v}$, ${{\boldsymbol{v}}}$ is not strongly tolerably reachable by ${{\boldsymbol{f}}}$. We continue with tolerable reachability. For $x = {x^*}(A, B, c, d)$ we obtain ${\overline f}(x) = M({\overline f}) = 6 = {\overline v}$ and ${\underline f}(x) = M({\underline f}) = 4\geq {\underline v}$. Hence, ${x^*}(A, B, c, d)$ satisfies the system of inequalities (5.3) which means that ${{\boldsymbol{v}}}$ is tolerably reachable by ${{\boldsymbol{f}}}$. Then it is weakly tolerably reachable by ${{\boldsymbol{f}}}$, too.

We continue with strongly controllable reachability. Since $M({\underline f}) = 4 > {\underline v}$, the system of inequalities (5.7) is not satisfied. Hence, ${{\boldsymbol{v}}}$ is not strongly controllably reachable by ${{\boldsymbol{f}}}$. For controllable reachability, we have to solve the system of inequalities

using Theorem 4.4. Since $M({\underline f}) > {\underline v}$, we shall continue with solving equation ${\underline f}(x) = 3$. This equation is solvable with the greatest solution ${x^*}(A, B, c, d, {\underline f}, 3) = (10, 5, 5, 3)^\top$, but ${\overline f}(10, 5, 5, 3) = 5 < 6$, so the above system is not solvable. Hence ${{\boldsymbol{v}}}$ is not controllably reachable by ${{\boldsymbol{f}}}$. System of inequalities (5.8) is satisfied because $m({\underline f}) = 2\leq 3 = {\underline v}$ and $M({\overline f}) = 6 = {\overline v}$, so ${{\boldsymbol{v}}}$ is weakly controllably reachable by ${{\boldsymbol{f}}}$.

Finally, we check the conditions for universal and weakly universal reachability. Since $m({\underline f})\neq M({\overline f})$, ${{\boldsymbol{v}}}$ is not universally reachable by ${{\boldsymbol{f}}}$. For weakly universal solvability, we have to solve the matrix equation

We obtain ${x^*}(A, B, c, d, {\underline f}, {\overline f}) = (6, 5, 5, 4)^\top$. Since ${\underline f}(6, 5, 5, 4) = {\overline f}(6, 5, 5, 4) = 4\in{{\boldsymbol{v}}}$, ${{\boldsymbol{v}}}$ is weakly universally reachable by ${{\boldsymbol{f}}}$.

We will summarize the obtained results: For given $A, B, c, d, {{\boldsymbol{f}}}$ and ${{\boldsymbol{v}}}$, an interval value ${{\boldsymbol{v}}}$ is possibly, weakly possibly, strongly possibly, tolerably, weakly tolerably, weakly controllably and weakly universally reachable by ${{\boldsymbol{f}}}$.

6.   Conclusions

In this paper, we have extended the solvability of two-sided systems of equations to a more general type. We dealt with the task of optimization in max-min algebra. In addition to minimizing or maximizing the objective function, we have introduced the notion of reachability of an interval value by an interval function. We have defined eleven types of reachability for which we have derived equivalent conditions. Other types of reachability can be a challenge for further research in this area.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Conflict of interest

The authors declare that they have no conflict of interest.