A Recurrence Method for Simple Continuous Linear Programming Problems

以遞迴方法求解連續型的線性規劃問題

溫慶豐(Ching-Feng Wen) ； 吳炎崑(Yan-Kuen Wu) ； 盧永毅(Yung-Yih Lur)

《工業工程學刊》 26卷2期 (2009/03) Pp. 147-155

https://doi.org/10.29977/JCIIE.200903.0008

摘要

本文主要探討一種特殊情況下的連續型線性規劃問題，簡稱爲(SP)問題。針對此一問題，本文提出一種有效率的方法來找尋(SP)問題的近似最佳解及近似最佳值，此法只需要利用遞迴關係求解一個有限維的線性規劃問題，即可找出原問題的近似最佳解及近似最佳值。本文就(SP)問題的求解程序提出一個演算法，此演算法不僅能容易的求解(SP)問題，並能估算近似值的誤差。最後列舉例子來證實本文所提演算法的可行性。

關鍵字

連續型線性規劃問題 ； 遞迴方法

並列摘要

In this paper, we discuss a special class of continuous linear programming problems which can be called simple continuous linear programming problems (SP). A practical and efficient method for finding an approximate optimal value and optimal solution of (SP) is presented. The main work of computing an approximate optimal value in the provided method is only to solve finite linear programming problems by using recurrence relations. Furthermore, a simple algorithm can be employed not only to easily solve the (SP) problem but also to provide an error bound of optimal value as well. Some numerical examples are given to implement the algorithm.

並列關鍵字

continuous linear programming problems ； recurrence method

參考文獻

Anderson, E. J.(1978).A Continuous Model for Job-shop Scheduling.University of Cambridge.

Anderson, E. J.(1981).A new continuous model for job-shop scheduling.International Journal of Systems Science.12,1469-1475.

Anderson, E. J.,P. Nash(1987).Linear Programming in Infinite Dimensional Spaces.NY:John Wiley and Sons.

Anderson, E. J.,A. B. Philpott(1989).Erratum a continuous time network simplex algorithm.Networks.19,823-827.

Anderson, E. J.,M. C. Pullan(1996).Purification for separated continuous linear programs.Mathematical Methods of Operations Research.43,9-33.