Search

組合せ最適化問題の多くは,線形計画問題として定式化することができるため,それぞれの問題に合った組合せ論的アルゴリズムだけでなく,線形計画問題におけるアルゴリズムを使っても解くことが出来る.本論文で取り上げる最適化問題は,フローネットワークにおける最適化問題の代表例である最短路問題と最長路問題である.最短路問題とは重みが最小となる道を求める問題で,最長路問題とはその逆に,重みが最大となる道を求める問題である.本研究の目的は,最短路問題と最長路問題の線形計画問題としての定式化と,最長路問題を解く組合せ論的アルゴリズムを見つけることである.本論文では,最短路問題の線形計画問題としての定式化は与えるが,最長路問題については,線形計画問題としてではない定式化を与えるにとどまる.最長路問題については,組合せ論的アルゴリズムを与える., Many of combinatorial optimization problems can be formulated as the linear programming (LP) problem. So they can be solved not only by their proper combinatorial algorithms but also by the algorithm in the LP problem. In the present paper, we focus on the shortest path problem and the longest path problem which are typical examples of the combinatorial optimization problem on the flow-networks. The shortest path problem is the problem for finding the path whose weight is minimal. Conversely, the longest path problem is the problem for finding the path whose weight is maximal. The purpose of our study is to formulate the shortest path problem and the longest path problem as the LP problem, and to find an algorithm for solving the longest path problem. In the present paper, we give the formulation of the shortest path problem as the LP problem. However, the longest path problem is not easy to formulate as the LP problem. So we give one formulation of the longest path problem by using rank condition, and give a combinatorial algorithm for the longest path problem.