近年來，越來越多單身男女希望能夠透過網路交友平台找到自己的另一半。本論文考慮一個網路交友平台的經營，期望能夠讓每位參與者都找到適合彼此的另一半。我們使用工作指派問題的數學模型整合配對問題及穩定室友問題的概念建構男女配對問題的數學模型。並且考慮多位交友對象、拒絕對象與分級制度等問題，分別提出不同的數學模型。最後，我們使用隨機產生的資料模擬參與者的雙向配度，以GAMS軟體求解，分析不同的配對結果，亦探討不同模型的難易度及求解所需之運算時間。 / In recent years, more and more single women and men hope that they can find their Mr. or Mrs. Right through the internet dating platform. This paper considers the operation of an internet dating platform which expects each participant to find the other half of each other. We propose mathematical models of the women and men matching problem by using the mathematical model of the assignment problem and integrating the idea of matching problem as well as the stable roommate problem. We also consider the problems of multiple dating objects, matching with rejection, and classification member. Finally, a simulate study will be performed by using the randomly generating data to simulate the two-way matching degree of each pair of participants. We analyze the different matching results obtained by the different models. We also present the difficulty of different models and the solution times.

著色問題(graph coloring problem)的研究已行之有年，並衍生出廣泛的實際應用，但還缺乏一般化的著色問題模型。本論文建構一般化的著色問題模型，其目標函數包含顏色成本的固定支出和點著色變動成本。此著色模型為0/1整數線性規畫模型，其限制式含有選點問題(node packing problem)的限制式。我們利用圖中的極大團(maximal clique)所構成的強力限制式，取代原有的選點限制式，縮短求解時間。我們更進一步舉出一個特殊指派問題並將此著色模型應用於此指派問題上。本論文亦針對此指派問題發展了一個演算法來尋找極大團。計算結果顯示極大團限制式對於此著色問題模型的求解有極大的效益。 / The graph coloring problem (GCP) has been studied for a long time and it has a wide variety of applications. A straightforward formulation of graph coloring problem has not been formulated yet. In this paper, we formulate a general GCP model that concerns setup cost and variable cost of different colors. The resulting model is an integer program that involves the packing constraint. The packing constraint in the GCP model can be replaced by the maximal clique constraint in order to shorten the solution time. A special assignment problem is presented which essentially is a GCP model application. An algorithm of finding maximal cliques for this assignment problem is developed. The computational results show the efficiency of maximal clique constraints for the GCP problem.