The balanced linear programming problem

作     者：Ahuja, RK 

作者机构：Department of Industrial and Management Engineering Indian Institute of Technology Kanpur 208016 India 

出 版 物：《EUROPEAN JOURNAL OF OPERATIONAL RESEARCH》 (Eur J Oper Res)

年 卷 期：1997年第101卷第1期

页      面：29-38页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：linear programming parametric programming network programming minimax optimization 

摘      要：The Balanced Linear Programming Problem (BLPP) arises in situations which require equitable distribution of a scarce resource. The BLPP can be transformed to the standard form of the linear programming problem by introducing 2\N\+2 additional variables and 2\N\ additional constraints. This transformation is not desirable from the computational point of view for larger values of \N\ as it increases the problem size substantially. It is also undesirable from a theoretical perspective as it might affect the special structure of the constraint matrix. In this paper, we develop an algorithm for the BLPP which does not require problem enlargement. The algorithm is based on the relationship between the BLPP and the minimax linear programming problem, and solving the latter problem parametrically. Our algorithm, in essence, performs steps that are similar to those performed in the parametric simplex method with parametric right hand side. We then adapt our algorithm for the network flow problem and this specialized algorithm can be applied on the network directly without maintaining the simplex tableau. (C) 1997 Elsevier Science B.V.