2. Statement of the Problem
Currently, there are many practical models of reliability, mass maintenance, and security that are adequately described by a semi-Markov controlled process (MCP) with a finite set of states.
In these models, control consists of choosing the moments of intervention in the system operation (for example, preventive repair, replacement of failed or worn-out units, frequency of determination of the current state of the system). If the studied models consider a class of randomized control strategies, then we come to the problem of functional analysis: the search for an extremum of some functional characterizing the quality of control of the set of probability measures (distributions) defining the randomized strategy. The result stated in this paper simplifies the problem (if probabilistic measures are defined on a straight line or a semi-straight line) by reducing it to the problem of mathematical analysis (the problem of finding an extremum of some function over a set of parameters), which, in principle, allows the use of software tools and to obtain a numerical result.
On some admissible set of probability measures
(the set of Markov homogeneous randomized control strategies) and the definition of the probability measure on which this extremum is reached [
6].
For controllable models of mass service, reliability, and safety, when it comes to the optimal choice of service duration or periodicity of restoration work, the control space coincides with the set of positive numbers and the probability measure is given by distribution functions where is the decision to be made.
Let us introduce two distribution functions
and define the set of admissible distributions
Now, using the accepted notations above, we can formulate the main mathematical problem: to determine the maximum of fractionally linear functional (1) over the set of admissible distributions (2) and the strategy (distribution)
on which this maximum is reached,
Note that the constraints (2) can be represented as constraints of the type of inequalities on linear functionals
Consequently, the formulated problem is a fractionally linear programming problem with an uncountable number of linear constraints.
If we use the lemma [
7] on the coincidence of the sets of probability measures on which the extremum of a fractionally linear functional and the extremum of a specially chosen linear functional are reached, the problem can be simplified by reducing it to the linear case.
Here is the formulation and proof of the lemma.
Lemma 1. If there exists a maximum of a fractional linear functional on some set then the equality of the setswhere is the set of possible controls, and the integrand function is defined by equalityand for the linear functional the relation. Proof of Lemma 1. It follows from the conditions of the lemma that among permissible distributions
, there are no distributions for which the denominator (1) is zero,
Denote
and the relations are fulfilled
Prove the equality of the two sets
where through
denotes the linear functional
For any distribution
linear functional (**) is zero, and considering that for any distribution
the linear functional (**) is less than or equal to zero
then it follows from these properties that the inclusion of
Reverse. Let . Then, by virtue of definition (**) for the fractional linear functional, we have . Since zero is the maximum of the linear functional (**), we obtain the inequality . Thus, the inverse inclusion of and inequalities (*).
A similar equality for the set
is proved by a complete repetition of the above reasoning for the fractional linear functional
and the linear functional
If , then the statement of the lemma follows from equality (*). If , then the statement of the lemma follows from equality (***). If , then the statement of the lemma follows from the obvious equality .
This completes the proof of the lemma. □
Thus, if it is established that for some probability measure of a certain structure, an extremum of the linear functional is reached and all probability measures, of the given structure, belong to the set Ω, then an extremum of the fractional-linear functional can be sought over the narrower set.
Thus, if it is found that for some probability measure, a certain structure, the extremum of the linear functional is reached and all probability measures, of the given structure, belong to the set , then the extremum of the fractionally linear functional can be sought over a narrower set. Moreover, if each probabilistic measure of a selected structure is uniquely defined by parameters (for example, measures defined on a discrete set), then the problem of functional analysis is reduced to the problem of finding an extremum of a function in the parameter space.
Here, it should be noted that the integrand function of a linear functional depends on an unknown parameter, and this creates certain difficulties when studying the structure of extreme probability measures.
3. Theorem on the Structure of the Extremal Function
Let us formulate the requirements to the integrand function and call these requirements conditions (*):
the function is defined on the half line ;
function is piecewise continuous;
has a finite number of discontinuity points;
has only discontinuities of the first kind;
at the discontinuity points the function takes a larger value;
function has a finite number of local maxima.
Let us denote the values of maxima
Let us define a maximum ordering rule for any segment of the set . Each maximum is characterized by the pair –value of the maxima and its argument.
Definition. When comparing the two maxima and :
maximum is assigned a lower number under the condition that
maximum is assigned a lower number under the condition that and .
Let us introduce the notations that we will use hereafter and for any subset of the set of definitions of the integrand function:
values of maxima and —is the number of different values of maxima, ;
is the argument of the maximum, for which the conditions are satisfied
the second index is determined by the equations
and for the other arguments, the order determines the inequality
, that is, it sets the order of maxima of the fixed level (4).
Note that this process of maximum ordering also involves the outermost points of the segment, if the maxima are reached in them.
Let us introduce the notation for the function inverse of the function . Given the properties of distribution functions (the presence of discontinuities), in the areas of uncertainty we will consider the inverse function constant, defining it so that it is nonincreasing. If the distribution function has areas in which it does not increase, then the inverse function is multivalued. In this case, we choose one of the possible values and consider the inverse function to be discontinuous.
Let us introduce notations for some areas of the independent variable.
The sets
do not intersect, and for these sets the relations are valid
Now let us formulate a basic theorem.
Theorem 1. If there exists a maximum of a linear functionalover the set of distribution functions and the integrand function satisfies conditions (*), then there exists a distribution function of the following structure among the distribution functions on which the maximum is achieved: - -
or the function coincides with one of the boundaries;
- -
or the function moves from boundary to boundary;
- -
or a piecewise constant (stepped) function.
Proof of Theorem 1. The proof of the theorem is carried out step by step: ordering of maxima, construction of reference functions, investigation of the properties of the reference functions, and the proof of the theorem statement.
The ordering of the maxima is described above, so we will use the previously introduced notations.
Next, we describe the algorithm for constructing reference functions, determine their areas of values and definitions, and examine their structure and properties.
Note that the formulation of the theorem defines distribution functions that have structures of three kinds, which we will hereafter refer to as reference functions.
For each isolated global maximum of the integrand function
we define a reference function in the area
Then, we define the area of influence of each maximum by the ratio
and in the area of
let us construct a non-decreasing, stepped, continuous function on the left
satisfying the conditions
It is easy to see that function (7) coincides with the reference functions in the area (6).
Recall that if the global maximum of the
of the integrand function
is reached on some segment
, then the maxima at the boundary points take part in the process of the maxima ordering. If for these maxima the inequality is satisfied
then add to the set
segment
and define the reference function on this set as a stepped function having a finite number of jumps and belonging to the set of admissible functions.
Let us prove one important inequality, which is true for the reference function. To this end, we introduce the function
For any admissible distribution
by virtue of the properties of the reference function
and the major function
, the following inequalities are true
In addition to this property of the reference functions, we note another interesting inequality for the reference function and for any function
. Let us denote by
and define the function
From the definition of the reference functions and functions
, it follows the fulfillment of the inequalities
If
, the theorem is proved, since
and among the optimal distributions there is a stepped function
with jumps at the points of maxima.
If , then and set the problem to determine the reference function in this area. Note that this area is a finite number of intervals, in each of which, at least at one boundary point, the integrand function equals . Let us describe the process of determining the reference functions of one of them by denoting this interval .
Then, two variants are possible:
There are no maxima within the interval;
Within the interval there are maxima and a global maximum of the level , i.e., there are interior points for which the equality is true .
In the first case, the reference function in the area
we define by equality
where
, and for it the equality is done
If there are no maxima inside the area
, then there exists a point
for which
and in the area
the integrand function does not increase, and in the area
the integrand function does not decrease. Let us introduce two functions
From the definition of these functions at
, these inequalities follow
If we consider the properties of the integrand function, it is easy to obtain an estimate by integrating over the parts
From this evaluation and the choice of the parameter
follows
This completes the construction of the reference functions for the interval in question.
Next, let us consider the case where there are maxima within the interval and the global maximum of the level , i.e., there are interior points for which the equality is true. Formally, it is necessary to reorder the maxima for the new area. We will use the previous notations in order to avoid unnecessary cumbersomeness.
Let us define the areas .
In the first area, the integrand function does not increase and the inequalities are satisfied
and in the second area the integrand function does not decrease and the same inequalities (15) are satisfied for it.
Note that if one of the areas does not fulfill the inequalities, it is no longer considered.
If
, then we define the reference function in
by the equality (12), where the parameter
is defined by the relation
Next, prove the inequality
for any admissible distribution. The proof of this inequality is reduced to the introduction of a major function
and the definition of functions
, only as a parameter
can be any point of the area
.
Finally, if
, then we define two reference functions
and two functions associated with one admissible distribution function
,
Then, two inequalities can be easily proved by integration over parts
It is easy to see that the reference functions in the area are not defined. This procedure repeats the above, only for a new narrower area and a smaller maximum.
The procedure for constructing the reference functions will end due to the finiteness of the number of maxima of the integrand function.
So, a finite set of reference functions is constructed, which fields of values do not overlap and which sum coincides with
. Denote by M the set of reference functions and define the function
Since inequalities (11), (14), (16), (19), and (20) for the reference functions are satisfied for any function
, we have the inequality
which proves the statement of the theorem. □
4. Discussion
Let us formulate useful corollaries of the proved theorem.
Given the statement of the above lemma, we give a formulation for the fractionally linear functional (1), assuming the existence of a maximum of this functional and fulfillment of the conditions of the theorem on the integrand functions.
Source 1 [
8,
9]
. If , then Source 2 [
10]
. If the function has one maximum at
, then Source 3. If the function
has no maxima in
, then The following example of a controlled mass service model in the “classical” statement, when the constraints are formulated in the form of standard inequalities on probability measures
are well known [11], so we will omit the detailed conclusions of the basic relations. Example 1. A mass service system.
We will study a mass service system, the input of which is a Poisson flow of demands with the parameter comes. The number of service channels is one, and the number of waiting places is . In Kendall’s terminology the system .
Contrary to the classical formulation, we will modify the distribution of the service time depending on the number of requests in the system at the moments of the end of service of the next request and at the moments of the arrival of requests in the free system. If at the given moment the number of demands in the system is equal to i, then we choose the service time distribution of the next demand equal to where —is random service time. Assigning a random service duration means introducing randomization into the decision making process (a Markov moment), i.e., at the moment when a decision has to be made and state i is observed, the realization of of a random variable distributed according to the law and the service duration is assigned equal to the value .
Let us introduce the cost characteristics, which determine the functional that characterizes the quality of functioning and control.
Let:
—fee (income) per one serviced claim;
—payment for one hour of channel operation;
—payment for one hour of free channel idle time,
—payment for the loss of one claim,
—payment for one hour of one requirement in the queue.
In [
11], there is an expression of fractionally linear functional (1)—the specific mathematical expectation of accumulated income for an arbitrary number of places for expectation
. We consider the solution of the above optimization problem under
and the constraints
where
are the distribution functions belonging to the set
.
With one waiting place at Markov moments (moments of end of service and moments of arrival of demands to the free system), there are either zero demands or one demand in the system.
Hence, a semi-Markov process has two states, but decisions are made only in one of them when there is one requirement in the system and the functional (1) depends on one distribution function .
In [
11], the dependence of this functional on the initial characteristics is given
Next, we will use the notation
Next, let us set the optimization problem: let there be two distribution functions
and we need to find the maximum of the functional (25) over the set of distributions
By the conditions of the theorem and lemma proved above, it is necessary to investigate the function
where
.
Let us investigate the function and prove that it satisfies the conditions of the above theorem and has one maximum.
Suppose that the inequality is true for optimal demand service since the initial data should be such that, under optimal control, the operation of the mass service system should produce a positive effect.
It is important to pay attention to the sign of the initial constants. The coefficients are negative, since they are losses from the functioning of the system; the parameter is greater than zero, because it is a profit.
The function under study (27) and all its derivatives are continuous.
The elementary ratios below
prove that this function has a maximum at some point
and in the area
it increases, and in the area
it decreases. Thus, it is proved that the function
has a maximum at some finite point. Therefore, the maximum of the functional (25) is reached on the function
the parameter
is defined as the maximum point of the function
and the functions
and
are defined by the equations
Let us note the obvious conclusion: at we have .
Example 2. Reliability model.
Let a system be defined in which the time of no-failure operation is distributed according to the law . Suppose a failure that occurs during the functioning of the system is independently detected (manifested) instantly.
At the initial moment t0 = 0, the system operation begins and the scheduled preventive update (preventive maintenance) of the system is assigned in time η ≥ 0, distributed according to the law The appointment of scheduled preventive updates of the system at random time means introduction of randomization in the decision making process, i.e., at the moment when the decision should be made, the realization of τ random variable η (=ητ), distributed according to the law , and a scheduled preventive update of the system is performed after the time τ.
If the system has not failed by the appointed time η (the event {η < ξ} has occurred), then at the time η a planned preventive update of the system is started, which by assumption completely updates the system. Let us denote the duration of this scheduled preventive (prophylactic) update by , and is a function of the distribution of this duration, .
If the system has failed by the appointed time η, an unscheduled emergency update of the system begins at the time of the failure ξ. We denote the duration of this recovery operation by , and denote the distribution law by
After possible remedial work, when the system is assumed to be completely renewed, the next precautionary remedial work is rescheduled and the entire maintenance process is repeated all over again.
Let us introduce a random process ξ (t), characterizing the state of the system at an arbitrary point in time t, by putting
ξ(t) = e0 if at time t the system is working properly;
ξ(t) = e1 if at time t the system undergoes a scheduled preventive update of the system;
ξ(t) = e3 if at time t an unscheduled emergency update of the system is performed.
The steady-state availability factor
is defined as the probability of catching the system in an operable state at an infinitely distant moment of time. In [
12], this characteristic in the notations adopted above is defined by equality
The mathematical problem is to determine the distribution
for which
Let us investigate the function
and obtain for the derivative the equality
where it is marked
Under the natural conditions and the assumption that the system is aging, that is, the function is increasing, we obtain: the derivative changes sign from plus to minus no more than once.
Then
where
.
Thus, the distribution is set
at which the maximum of the investigated functional is reached.