在一維度上的有界形和分割及單一形均分割問題

Abstract

最優分法問題主要是對於目標函數F:R^p到R，考慮n個物件分成p個非空部份，如何找到一個分法(最優分法)，使得F為最大值。一個最直接的方法是去比較所有分法的目標函數值。此時，我們關心所有分法的數量，因為它決定了直接法是否可行。更好的是當目標函數具備有某些性質，使得某些特定的分法類中含有一最優分法，我們就可以只關心這一些數量較小的特定分法。 每個部分容量所形成的向量我們稱為形，若一個問題對每個部分的容量分別落於一個區間內，我們稱為有限形分割問題。若每個區間為單一的點，則我們稱為單一形分割問題。在第二章，我們使用生成函數去計算對於有序及無序的有界形分割各有多少形及分法。在第三章，我們証明對於有界形和分割問題，當目標函數為Schur凸函數，必存在一不被偏形其所對應的容量連續分法為最優分法。並給出了不被偏形的數量上界及發展了找出所有不被偏等價形的演算法。在第四章， 我們証明對於單一形均分割問題，當目標函數為準凸函數，其最優分法必是一連續分法。並且對均分割問題給了一些新的結果。

The optimal partition problem considers the partition of n objects into p nonempty parts, and finding a partition(optimal partition) to maximize the objective function F:R^p-->R. A brute force method is to compare the values of objective function F(pi) for each partition pi. Thus, we are concerned with the number of all partitions which determines whether the brute force method is practical. However, a more desirable solution is to prove that the objective function has some suitable property which leads to the existence of an optimal partition in a special class of partitions. Then, we need pay attention only to this class of partitions. The vector of the size of each part is called a shape. If a partition problem has a restriction where the size of each part lies in an interval, then it is called a bounded-shape partition problem. If each interval is degenerated, then it is called single-shape partition problem. In Chapter 2, we use the generating function to count the number of ordered(unordered) shapes and the number of bounded-shape partitions. In Chapter 3, we prove that for bounded-shape sum-partition problem with Schur-convex objective function, there must be a nonmajorized shape such that the corresponding size-consecutive partition is optimal. We also bound the number of nonmajorized shapes, and develop an algorithm to find all nonmajorized shape-types. In Chapter 4, we prove that for single-shape mean-partition problem with quasi-convex objective function, there must be a consecutive optimal partition. We also give some new results for the mean-partition problems.