衍生品樹狀問題之研究

Abstract

本研究提出並探討衍生品樹狀問題(derivatives tree problem)，並設計與分析其線性時間之演算法。衍生品樹為一樹狀結構，其中每一個節點代表一個有價值之衍生品，而每一個衍生品係由其父親節點依某特定比例所衍生而生成的。起初給定一衍生品樹之樹根衍生品之某特定量(其他衍生品的初始量為零)，衍生品樹狀問題係關於如何決定此衍生品樹中每個衍生品之數量，使得當滿足每個衍生品之需求量限制下總價值之最大化。在實務上，此問題可應用在輸血醫學中血液成分製劑之決策分析。雖然本研究提出可用線性規劃來解決此問題，然而線性規劃未必是有效率的解決方法。因此，本研究提出一線性時間之演算法(以節點的數目來測度)來有效率地處理衍生品樹狀問題，並包含此演算法之一些理論上的分析。

In this paper, we investigate the derivatives tree problem as well as design a linear time algorithm for solving it. In a derivatives tree, each vertex representing a derivative with a certain value is derived from its parent vertex. Initially given certain amount of the root derivative in a derivatives tree (noticing that the amount of every other derivative is zero initially), the derivatives tree problem is concerned with finding the assignment of amount of each derivative such that the total value is maximized while satisfying the demand limit of every derivative. In practice, the problem has application to the decision-making of blood component preparation in transfusion medicine. Although the derivatives tree problem can be solved by linear programming which is proposed in this paper, one should notice that the linear programming may not be an efficient approach. As a consequence, in this paper, we propose a linear time algorithm (in the size of vertices) for efficiently coping with the derivatives tree problem. Some theoretical analysis is also included in this paper.