Parametric Approach to Some Linearly Constrained Optimization Problems Using Simplex-Type Methods

參數化探索單形型法求解線性限制最佳化問題

吳光耀(Kuang-Yao Wu)

《工業工程學刊》 23卷3期 (2006/05) Pp. 215-221

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

摘要

本文建立一個求解架構，用以使用單形型法處理一些具線性限制式的最佳化問題，其包括線性規劃、線性分式規劃、以及廣義型線性分式規劃。本研究將此三問題參照到一個標準模式，其內含單一參數目標式與參數化線性等式。透過參數化基底式解的分析，我們提出一元化的單形型求解方法，並討論所提參數化模式與求解程序的適應性。特別的是相較於傳統的單形法，本文所提演算法在處理線式規劃問題時能避免落入演算循環的情況。

關鍵字

線性限制式 ； 參數化建模 ； 單形型法 ； 基底式解 ； 退化與循環

並列摘要

This paper establishes a framework for solving some optimization problems with linear constraints using simplex-type methods. The problems include those found in linear programs, linear fractional programs, and generalized linear fractional programs. In this study, these problems refer to a standard form of minimizing a single parameter subject to parameterized linear equations. Based on the analysis of parameterized basis-based solutions, a unified simplex-type approach is proposed. The adaptability of the parameterized model and that of the solution procedure are discussed. In particular, the proposed algorithm can prevent cycling when compared with the conventional simplex method used for solving linear programs.

並列關鍵字

linear constraints ； parametric modeling ； simplex-type methods ； basis-based solution ； degeneracy and cycling

參考文獻

Bajalinov, E. B.(2003).(Linear-Fractional Programming: Theory, Methods, Applications and Software).

Crouzeix, J. P.,J. A. Ferland(1991).Algorithms for generalized fractional programming.(Mathematical Programming).

Ellero, A.,E. Moretti,Mazzoleni, P.(1994).A parametric simplex-like algorithm for a quadratic fractional programming problem.(Optimization of Generalized Convex Problems in Economics).

Fang, S. C.,S. Puthenpura(1993).(Linear Optimization and Extensions: Theory and Algorithms).

Floudas, C. A.,P. M. Pardalos(2001).(Encyclopedia of Optimization).