Spelling suggestions: "subject:"matrix analytical methods""
1 |
Shipment Consolidation in Discrete Time and Discrete Quantity: Matrix-Analytic MethodsCai, Qishu 22 August 2011 (has links)
Shipment consolidation is a logistics strategy whereby many small shipments are combined into a few larger loads. The economies of scale achieved by shipment consolidation help in reducing the transportation costs and improving the utilization of logistics resources.
The fundamental questions about shipment consolidation are i) to how large a size should the consolidated loads be allowed to accumulate? And ii) when is the best time to dispatch such loads? The answers to these questions lie in the set of decision rules known as shipment consolidation policies.
A number of studies have been done in an attempt to find the optimal consolidation policy. However, these studies are restricted to only a few types of consolidation policies and are constrained by the input parameters, mainly the order arrival process and the order weight distribution. Some results on the optimal policy parameters have been obtained, but they are limited to a couple of specific types of policies.
No comprehensive method has yet been developed which allows the evaluation of different types of consolidation policies in general, and permits a comparison of their performance levels. Our goal in this thesis is to develop such a method and use it to evaluate a variety of instances of shipment consolidation problem and policies.
In order to achieve that goal, we will venture to use matrix-analytic methods to model and solve the shipment consolidation problem. The main advantage of applying such methods is that they can help us create a more versatile and accurate model while keeping the difficulties of computational procedures in check.
More specifically, we employ a discrete batch Markovian arrival process (BMAP) to model the weight-arrival process, and for some special cases, we use phase-type (PH) distributions to represent order weights. Then we model a dispatch policy by a discrete monotonic function, and construct a discrete time Markov chain for the shipment consolidation process.
Borrowing an idea from matrix-analytic methods, we develop an efficient algorithm for computing the steady state distribution of the Markov chain and various performance measures such as i) the mean accumulated weight per load, ii) the average dispatch interval and iii) the average delay per order. Lastly, after specifying the cost structures, we will compute the expected long-run cost per unit time for both the private carriage and common carriage cases.
|
2 |
Shipment Consolidation in Discrete Time and Discrete Quantity: Matrix-Analytic MethodsCai, Qishu 22 August 2011 (has links)
Shipment consolidation is a logistics strategy whereby many small shipments are combined into a few larger loads. The economies of scale achieved by shipment consolidation help in reducing the transportation costs and improving the utilization of logistics resources.
The fundamental questions about shipment consolidation are i) to how large a size should the consolidated loads be allowed to accumulate? And ii) when is the best time to dispatch such loads? The answers to these questions lie in the set of decision rules known as shipment consolidation policies.
A number of studies have been done in an attempt to find the optimal consolidation policy. However, these studies are restricted to only a few types of consolidation policies and are constrained by the input parameters, mainly the order arrival process and the order weight distribution. Some results on the optimal policy parameters have been obtained, but they are limited to a couple of specific types of policies.
No comprehensive method has yet been developed which allows the evaluation of different types of consolidation policies in general, and permits a comparison of their performance levels. Our goal in this thesis is to develop such a method and use it to evaluate a variety of instances of shipment consolidation problem and policies.
In order to achieve that goal, we will venture to use matrix-analytic methods to model and solve the shipment consolidation problem. The main advantage of applying such methods is that they can help us create a more versatile and accurate model while keeping the difficulties of computational procedures in check.
More specifically, we employ a discrete batch Markovian arrival process (BMAP) to model the weight-arrival process, and for some special cases, we use phase-type (PH) distributions to represent order weights. Then we model a dispatch policy by a discrete monotonic function, and construct a discrete time Markov chain for the shipment consolidation process.
Borrowing an idea from matrix-analytic methods, we develop an efficient algorithm for computing the steady state distribution of the Markov chain and various performance measures such as i) the mean accumulated weight per load, ii) the average dispatch interval and iii) the average delay per order. Lastly, after specifying the cost structures, we will compute the expected long-run cost per unit time for both the private carriage and common carriage cases.
|
3 |
Fast solution of large-body problems using domain decomposition and null-field generation in the method of momentsKillian, Tyler Norton, Rao, S. M. January 2009 (has links)
Thesis (Ph. D.)--Auburn University. / Abstract. Vita. Includes bibliographical references (p. 70-71).
|
4 |
Méthodes numériques pour le calcul des valeurs propres les plus à droite des matrices creuses de très grande tailleCallant, Julien 20 December 2012 (has links)
Méthodes numériques pour le calcul des valeurs propres les plus à droite des matrices creuses et non-hermitiennes de très grande taille / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished
|
5 |
Evaluation of applying Crum-based transformation in solving two point boundary value problemsJogiat, Aasif January 2016 (has links)
A dissertation submitted to the Faculty of Engineering and the Built Environment, University of the
Witwatersrand, in ful llment of the requirements for the degree of Master of Science in Engineering, Johannesburg, 2016 / The aim of this research project is evaluating the application of the Crum-based transformation
in solving engineering systems modelled as two-point boundary value problems. The boundary
value problems were subjected to the various combinations of Dirichlet, Non-Dirichlet and Affine
boundary conditions. The engineering systems that were modelled were in the elds of electrostatics,
heat conduction and longitudinal vibrations. Other methods such as the Z-transforms and iterative
methods have been discussed. An attractive property of the Crum-based transformation is that
it can be applied to cases where the eigenparameters (function of eigenvalues) generated in the
discrete case are negative and was therefore chosen to be explored further in this dissertation. An
alternative matrix method was proposed and used instead of the algebraic method in the Crum-
based transformation. The matrix method was tested against the algebraic method using three unit
intervals. The analysis revealed, that as the number of unit intervals increase, there is a general
increase in the accuracy of the approximated continuous-case eigenvalues generated for the discrete
case. The other observed general trend was that the accuracy of the approximated continuous-
case eigenvalues decrease as one ascends the continuous-case eigenvalue spectrum. Three cases:
(Affine, Dirichlet), (Affine, Non-Dirichlet) and (Affine, Affine) generated negative eigenparameters.
The approximated continuous-case eigenvalues, derived from the negative eigenparameters, were
shown not to represent true physical natural frequencies since the discrete eigenvalues, derived from
negative eigenparameters, do not satisfy the condition for purely oscillatory behaviour. The research
has also shown that the Crum-based transformation method was useful in approximating the shifted
eigenvalues of the continuous case, in cases where the generated eigenparameters were negative:
since, as the number of unit intervals increase, the post-transformed approximated eigenvalues
improved in accuracy. The accuracy was also found to be better in the post-transformed case than
in the pre-transformed case. Furthermore, the approximated non-shifted and shifted continuous-
case eigenvalues (except the approximated continuous-case eigenvalues generated from negative
eigenparameters) satis ed the condition for purely oscillatory behaviour. / MT2017
|
6 |
An algorithmic look at phase-controlled branching processes / Un regard algorithmique aux processus de branchement contrôlés par des phasesHautphenne, Sophie 15 October 2009 (has links)
Branching processes are stochastic processes describing the evolution of populations of individuals which reproduce and die independently of each other according to specific probability laws. We consider a particular class of branching processes, called Markovian binary trees, where the lifetime and birth epochs of individuals are controlled by a Markovian arrival process. <p><p>Our objective is to develop numerical methods to answer several questions about Markovian binary trees. The issue of the extinction probability is the main question addressed in the thesis. We first assume independence between individuals. In this case, the extinction probability is the minimal nonnegative solution of a matrix fixed point equation which can generally not be solved analytically. In order to solve this equation, we develop a linear algorithm based on functional iterations, and a quadratic algorithm, based on Newton's method, and we give their probabilistic interpretation in terms of the tree. <p><p>Next, we look at some transient features for a Markovian binary tree: the distribution of the population size at any given time, of the time until extinction and of the total progeny. These distributions are obtained using the Kolmogorov and the renewal approaches. <p><p>We illustrate the results mentioned above through an example where the Markovian binary tree serves as a model for female families in different countries, for which we use real data provided by the World Health Organization website. <p><p>Finally, we analyze the case where Markovian binary trees evolve under the external influence of a random environment or a catastrophe process. In this case, individuals do not behave independently of each other anymore, and the extinction probability may no longer be expressed as the solution of a fixed point equation, which makes the analysis more complicated. We approach the extinction probability, through the study of the population size distribution, by purely numerical methods of resolution of partial differential equations, and also by probabilistic methods imposing constraints on the external process or on the maximal population size.<p><p>/<p><p>Les processus de branchements sont des processus stochastiques décrivant l'évolution de populations d'individus qui se reproduisent et meurent indépendamment les uns des autres, suivant des lois de probabilités spécifiques. <p><p>Nous considérons une classe particulière de processus de branchement, appelés arbres binaires Markoviens, dans lesquels la vie d'un individu et ses instants de reproduction sont contrôlés par un MAP. Notre objectif est de développer des méthodes numériques pour répondre à plusieurs questions à propos des arbres binaires Markoviens.<p><p>La question de la probabilité d'extinction d'un arbre binaire Markovien est la principale abordée dans la thèse. Nous faisons tout d'abord l'hypothèse d'indépendance entre individus. Dans ce cas, la probabilité d'extinction s'exprime comme la solution minimale non négative d'une équation de point fixe matricielle, qui ne peut être résolue analytiquement. Afin de résoudre cette équation, nous développons un algorithme linéaire, basé sur l'itération fonctionnelle, ainsi que des algorithmes quadratiques, basés sur la méthode de Newton, et nous donnons leur interprétation probabiliste en termes de l'arbre que l'on étudie.<p><p>Nous nous intéressons ensuite à certaines caractéristiques transitoires d'un arbre binaire Markovien: la distribution de la taille de la population à un instant donné, celle du temps jusqu'à l'extinction du processus et celle de la descendance totale. Ces distributions sont obtenues en utilisant l'approche de Kolmogorov ainsi que l'approche de renouvellement.<p><p>Nous illustrons les résultats mentionnés plus haut au travers d'un exemple où l'arbre binaire Markovien sert de modèle pour des populations féminines dans différents pays, et pour lesquelles nous utilisons des données réelles fournies par la World Health Organization.<p><p>Enfin, nous analysons le cas où les arbres binaires Markoviens évoluent sous une influence extérieure aléatoire, comme un environnement Markovien aléatoire ou un processus de catastrophes. Dans ce cas, les individus ne se comportent plus indépendamment les uns des autres, et la probabilité d'extinction ne peut plus s'exprimer comme la solution d'une équation de point fixe, ce qui rend l'analyse plus compliquée. Nous approchons la probabilité d'extinction au travers de l'étude de la distribution de la taille de la population, à la fois par des méthodes purement numériques de résolution d'équations aux dérivées partielles, ainsi que par des méthodes probabilistes en imposant des contraintes sur le processus extérieur ou sur la taille maximale de la population. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished
|
7 |
Fluid Queues: Building Upon the Analogy with QBD processesda Silva Soares, Ana 11 March 2005 (has links)
Les files d'attente fluides sont des processus markoviens à deux dimensions, où la première composante, appelée le niveau, représente le contenu d'un réservoir et prend des valeurs continues, et la deuxième composante, appelée la phase, est l'état d'un processus markovien dont l'évolution contrôle celle du niveau. Le niveau de la file fluide varie linéairement avec un taux qui dépend de la phase et qui peut prendre n'importe quelle valeur réelle.
Dans cette thèse, nous explorons le lien entre les files fluides et les processus QBD, et nous appliquons des arguments utilisés en théorie des processus de renouvellement pour obtenir la distribution stationnaire de plusieurs modèles fluides.
Nous commençons par l'étude d'une file fluide avec un réservoir de taille infinie; nous déterminons sa distribution stationnaire, et nous présentons un algorithme permettant de calculer cette distribution de manière très efficace. Nous observons que la distribution stationnaire de la file fluide de capacité infinie est très semblable à celle d'un processus QBD avec une infinité de niveaux. Nous poursuivons la recherche des similarités entre les files fluides et les processus QBD, et nous étudions ensuite la distribution stationnaire d'une file fluide de capacité finie. Nous montrons que l'algorithme valable pour le cas du réservoir infini permet de calculer toutes les quantités importantes du modèle avec un réservoir fini.
Nous considérons ensuite des modèles fluides plus complexes, de capacité finie ou infinie, où le comportement du processus markovien des phases peut changer lorsque le niveau du réservoir atteint certaines valeurs seuils. Nous montrons que les méthodes développées pour des modèles classiques s'étendent de manière naturelle à ces modèles plus complexes.
Pour terminer, nous étudions les conditions nécessaires et suffisantes qui mènent à l'indépendance du niveau et de la phase d'une file fluide de capacité infinie en régime stationnaire. Ces résultats s'appuient sur des résultats semblables concernant des processus QBD.
Markov modulated fluid queues are two-dimensional Markov processes, of which the first component, called the level, represents the content of a buffer or reservoir and takes real values; the second component, called the phase, is the state of a Markov process which controls the evolution of the level in the following manner: the level varies linearly at a rate which depends on the phase and which can take any real value.
In this thesis, we explore the link between fluid queues and Quasi Birth-and-Death (QBD) processes, and we apply Markov renewal techniques in order to derive the stationary distribution of various fluid models.
To begin with, we study a fluid queue with an infinite capacity buffer; we determine its stationary distribution and we present an algorithm which performs very efficiently in the determination of this distribution. We observe that the equilibrium distribution of the fluid queue is very similar to that of a QBD process with infinitely many levels. We further exploit the similarity between the two processes, and we determine the stationary distribution of a finite capacity fluid queue. We show that the algorithm available in the infinite case allows for the computation of all the important quantities entering in the expression of this distribution.
We then consider more complex models, of either finite or infinite capacities, in which the behaviour ff the phase process may change whenever the buffer is empty or full, or when it reaches certain thresholds. We show that the techniques that we develop for the simpler models can be extended quite naturally in this context.
Finally, we study the necessary and sufficient conditions that lead to the independence between the level and the phase of an infinite capacity fluid queue in the stationary regime. These results are based on similar developments for QBD processes.
|
8 |
An algorithmic look at phase-controlled branching processes/ Un regard algorithmique aux processus de branchement contrôlés par des phasesHautphenne, Sophie 15 October 2009 (has links)
Branching processes are stochastic processes describing the evolution of populations of individuals which reproduce and die independently of each other according to specific probability laws. We consider a particular class of branching processes, called Markovian binary trees, where the lifetime and birth epochs of individuals are controlled by a Markovian arrival process.
Our objective is to develop numerical methods to answer several questions about Markovian binary trees. The issue of the extinction probability is the main question addressed in the thesis. We first assume independence between individuals. In this case, the extinction probability is the minimal nonnegative solution of a matrix fixed point equation which can generally not be solved analytically. In order to solve this equation, we develop a linear algorithm based on functional iterations, and a quadratic algorithm, based on Newton's method, and we give their probabilistic interpretation in terms of the tree.
Next, we look at some transient features for a Markovian binary tree: the distribution of the population size at any given time, of the time until extinction and of the total progeny. These distributions are obtained using the Kolmogorov and the renewal approaches.
We illustrate the results mentioned above through an example where the Markovian binary tree serves as a model for female families in different countries, for which we use real data provided by the World Health Organization website.
Finally, we analyze the case where Markovian binary trees evolve under the external influence of a random environment or a catastrophe process. In this case, individuals do not behave independently of each other anymore, and the extinction probability may no longer be expressed as the solution of a fixed point equation, which makes the analysis more complicated. We approach the extinction probability, through the study of the population size distribution, by purely numerical methods of resolution of partial differential equations, and also by probabilistic methods imposing constraints on the external process or on the maximal population size.
/
Les processus de branchements sont des processus stochastiques décrivant l'évolution de populations d'individus qui se reproduisent et meurent indépendamment les uns des autres, suivant des lois de probabilités spécifiques.
Nous considérons une classe particulière de processus de branchement, appelés arbres binaires Markoviens, dans lesquels la vie d'un individu et ses instants de reproduction sont contrôlés par un MAP. Notre objectif est de développer des méthodes numériques pour répondre à plusieurs questions à propos des arbres binaires Markoviens.
La question de la probabilité d'extinction d'un arbre binaire Markovien est la principale abordée dans la thèse. Nous faisons tout d'abord l'hypothèse d'indépendance entre individus. Dans ce cas, la probabilité d'extinction s'exprime comme la solution minimale non négative d'une équation de point fixe matricielle, qui ne peut être résolue analytiquement. Afin de résoudre cette équation, nous développons un algorithme linéaire, basé sur l'itération fonctionnelle, ainsi que des algorithmes quadratiques, basés sur la méthode de Newton, et nous donnons leur interprétation probabiliste en termes de l'arbre que l'on étudie.
Nous nous intéressons ensuite à certaines caractéristiques transitoires d'un arbre binaire Markovien: la distribution de la taille de la population à un instant donné, celle du temps jusqu'à l'extinction du processus et celle de la descendance totale. Ces distributions sont obtenues en utilisant l'approche de Kolmogorov ainsi que l'approche de renouvellement.
Nous illustrons les résultats mentionnés plus haut au travers d'un exemple où l'arbre binaire Markovien sert de modèle pour des populations féminines dans différents pays, et pour lesquelles nous utilisons des données réelles fournies par la World Health Organization.
Enfin, nous analysons le cas où les arbres binaires Markoviens évoluent sous une influence extérieure aléatoire, comme un environnement Markovien aléatoire ou un processus de catastrophes. Dans ce cas, les individus ne se comportent plus indépendamment les uns des autres, et la probabilité d'extinction ne peut plus s'exprimer comme la solution d'une équation de point fixe, ce qui rend l'analyse plus compliquée. Nous approchons la probabilité d'extinction au travers de l'étude de la distribution de la taille de la population, à la fois par des méthodes purement numériques de résolution d'équations aux dérivées partielles, ainsi que par des méthodes probabilistes en imposant des contraintes sur le processus extérieur ou sur la taille maximale de la population.
|
9 |
The development and application of random matrix theory in adaptive signal processing in the sample deficient regimePajovic, Milutin January 2014 (has links)
Thesis: Ph. D., Joint Program in Applied Ocean Science and Engineering (Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science; and the Woods Hole Oceanographic Institution), 2014. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 237-243). / This thesis studies the problems associated with adaptive signal processing in the sample deficient regime using random matrix theory. The scenarios in which the sample deficient regime arises include, among others, the cases where the number of observations available in a period over which the channel can be approximated as time-invariant is limited (wireless communications), the number of available observations is limited by the measurement process (medical applications), or the number of unknown coefficients is large compared to the number of observations (modern sonar and radar systems). Random matrix theory, which studies how different encodings of eigenvalues and eigenvectors of a random matrix behave, provides suitable tools for analyzing how the statistics estimated from a limited data set behave with respect to their ensemble counterparts. The applications of adaptive signal processing considered in the thesis are (1) adaptive beamforming for spatial spectrum estimation, (2) tracking of time-varying channels and (3) equalization of time-varying communication channels. The thesis analyzes the performance of the considered adaptive processors when operating in the deficient sample support regime. In addition, it gains insights into behavior of different estimators based on the estimated second order statistics of the data originating from time-varying environment. Finally, it studies how to optimize the adaptive processors and algorithms so as to account for deficient sample support and improve the performance. In particular, random matrix quantities needed for the analysis are characterized in the first part. In the second part, the thesis studies the problem of regularization in the form of diagonal loading for two conventionally used spatial power spectrum estimators based on adaptive beamforming, and shows the asymptotic properties of the estimators, studies how the optimal diagonal loading behaves and compares the estimators on the grounds of performance and sensitivity to optimal diagonal loading. In the third part, the performance of the least squares based channel tracking algorithm is analyzed, and several practical insights are obtained. Finally, the performance of multi-channel decision feedback equalizers in time-varying channels is characterized, and insights concerning the optimal selection of the number of sensors, their separation and constituent filter lengths are presented. / by Milutin Pajovic. / Ph. D.
|
10 |
Algorithmic Analysis of a General Class of Discrete-based Insurance Risk ModelsSinger, Basil Karim January 2013 (has links)
The aim of this thesis is to develop algorithmic methods for computing particular performance measures of interest for a general class of discrete-based insurance risk models. We build upon and generalize the insurance risk models considered by Drekic and Mera (2011) and Alfa and Drekic (2007), by incorporating a threshold-based dividend system in which dividends only get paid provided some period of good financial health is sustained above a pre-specified threshold level. We employ two fundamental methods for calculating the performance measures under the more general framework.
The first method adopts the matrix-analytic approach originally used by Alfa and Drekic (2007) to calculate various ruin-related probabilities of interest such as the trivariate distribution of the time of ruin, the surplus prior to ruin, and the deficit at ruin. Specifically, we begin by introducing a particular trivariate Markov process and then expressing its transition probability matrix in a block-matrix form. From this characterization, we next identify an initial probability vector for the process, from which certain important conditional probability vectors are defined. For these vectors to be computed efficiently, we derive recursive expressions for each of them. Subsequently, using these probability vectors, we derive expressions which enable the calculation of conditional ruin probabilities and, from which, their unconditional counterparts naturally follow.
The second method used involves the first claim conditioning approach (i.e., condition on knowing the time the first claim occurs and its size) employed in many ruin theoretic articles including Drekic and Mera (2011). We derive expressions for the finite-ruin time based Gerber-Shiu function as well as the moments of the total dividends paid by a finite time horizon or before ruin occurs, whichever happens first. It turns out that both functions can be expressed in elegant, albeit long, recursive formulas.
With the algorithmic derivations obtained from the two fundamental methods, we next focus on computational aspects of the model class by comparing six different types of models belonging to this class and providing numerical calculations for several parametric examples, highlighting the robustness and versatility of our model class. Finally, we identify several potential areas for future research and possible ways to optimize numerical calculations.
|
Page generated in 0.088 seconds