設備數의 制限을 갖는 設備入地選定問題의 解法에 관한 硏究

Abstract

設備數의 제약을 갖는 설비입지선정 문제(p-median)는 문제의 크기가 큰 I.P문제이다. 특히 x??≤y?,와 같은 제약식(VUB제약식)으로 문제를 모형화하면 문제의 크기는 더욱 더 커지는데 반면에 이 VUB의 특성 때문에 L·P의 해가 대개 I·P의 해가 된다. 따라서 이 VUB의 특성을 잘 살려 문제를 간단하게 할 수 있으면 VUB제약식이 효율적일 수 있다. 본 논문에서는 修正單體法을 이용하여 이 문제의 해법을 연구하였는데 VUB의 특성을 이용하여 逆行列을 쉽게 구할 수 있게 하였고 修正單體法의 과정도 쉽게 구할 수 있게 하였다.

The p-median warehouse location problem is very interesting part of Integer Programming. In this paper, we developed an algorithm for the p-median problem. In special form of p-median problem, large numbers of VUB constraints, which are tight constraints of the p-median problems, are appeared. In revised simplex method for the p-median problem, the inverse matrix of basis and the procedure of the revised simplex method can be simplified by use of the VUB's characteristics.

The p-median warehouse location problem is very interesting part of Integer Programming. In this paper, we developed an algorithm for the p-median problem. In special form of p-median problem, large numbers of VUB constraints, which are tight constraints of the p-median problems, are appeared. In revised simplex method for the p-median problem, the inverse matrix of basis and the procedure of the revised simplex method can be simplified by use of the VUB's characteristics.