文档介绍：6 6
6
2 2 2
Ξ
É Π
É
¨
¨
应用数学 2 2 3
MATHEMATICA3 APPL ICATA
2
2001 ,14 (增) :163~166
线性分式规划最优解集的求法
3
3
薛声家1 ,薛学明2
(1. 暨南大学管理学院, 广东广州 510632 ;2. 广州华侨医院信息科,广东广州 510630)
Ξ
摘要:本文使用多面集的表示定理,导出了线性分式规划最优解集的结构,并给出确
定全部最优解的计算步骤.
关键词:线性分式规划;最优解集;表示定理;既约梯度;凸单纯形法
中图分类号:O221. 2 AMS( 2000) 主题分类:90C ;49M
文献标识码:A 文章编号:1001 9847 (2001) 增 0163 04
线性分式规划在经济管理领域中有着广泛的应用. 本文刻画了线性分式规划最优解集的
结构,给出确定全部最优解的计算步骤.
考虑如下形式的线性分式规划
p T x + α
max f ( x) = T ,
(L FP) q x +β
s. t . A x = b , x ≥0
其中, A 为 m × n 矩阵, p , q , x ∈ En , b ∈ Em ,α,β∈ E1 . 不失一般性可设 rank ( A ) = m <
n.
记(L FP) 的可行集为 S . 我们假设 S ≠; x ∈S 有 q T x +β≠0 ,不妨设 q T x +β> 0.
由多面集的表示定理[7 ,8 ] 知: x ∈ S 当且仅当 x 可表示为
k l
i j
x = λi x + μj d , (1)
i = 1 j = 1
k
1 2 k 1 2 l
其中 x , x , ⋯, x 是 S 的极点; d , d , ⋯, d 是 S 的极方向. λi = 1 ,λi ≥0 , i = 1 , ⋯, k ;
i = 1
μj ≥0 , j = 1 , ⋯, l . 设(L FP) 的最优解集 S ≠. 我们注意到,虽然(L FP) 不是凸规划,但不
难证明 S 为一凸集(可使用广义凸性的结果[8 ,9 ] 或直接证明) . 由[8 ] 知,若(L FP) 有最优解,
则必存在最优极点. 记最优极点集为{ x i | i ∈ I} . 对于 x ∈ S 有
( q T x +β) p - ( p T x +α) q p - f ( x ) q
f ( x ) = = (2)
( q T x +β) 2 q T x +β
由于在最优解 x 处的所有可行方向都不是 f 的上升方向,因此对于所有极方向 dj 有
f ( x ) T dj ≤0 , j = 1 , ⋯, l (3)
收稿日期:2001 08 10
基金项目:国家自然科学基金基金资助(19801009)
作者简介:薛声家(1944 ) ,男,汉,广东潮阳人,教授,研究方向:最优化,管理科学与管理决策.
© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserve