[拼音]:jihe guihua [外文]:geometric programming 一类特殊的非线性规划。20世纪60年代起,从工程设计费用最小化问题的研究中,发展了这类特殊非线性规划的处理方法。这类特殊规划的研究中,几何平均不等式有着根本的作用,因而称之为几何规划。它在化学和机械、土木、电气、核工程以及管理科学等方面有许多应用。 广义几何平均不等式设
式中
时,(1)中的等号成立。特别当
以上两个不等式的意义在于把不等式左方若干项的和与右方若干因子的乘积相联系。在许多实际问题中,需要最小化的目标函数(例如工程费用)常常可以写成若干项之和,根据广义几何平均不等式,它绝不小于某些因子的乘积。在某些情况下,通过适当选取w1,w2,…,wT,可使这一乘积变成一个与决策变量无关的常数,所选取的wt,即为使目标函数等于这一下界(此时也是最小值)的决策变量数值,也就是问题的最优解。这就是早期几何规划的常用方法。 正项式与正项几何规划形如
的有正变向量 人们最初研究的几何规划是正项几何规划,即有正变向量 尣>0的、目标函数和约束函数都是正项式的非线性规划 min g0(尣),s.t.gm(尣)≤1 (m=1,2,…,M), (4) 尣>0, 式中 一般地,正项式(3)未必是x的凸函数,所以正项几何规划(4)一般不是凸规划,但是通过变换zn=lnxn(n=1,2,…,N)可将 g(尣)化成 z的凸函数。因此尽管正项几何规划不一定是凸规划, 但它具有凸规划所有的优良性质:它的任何局部极小点一定也是它的整体极小点。 对偶规划记
于是,
式中
(6)的右方与尣无关,记为d(w);又,当且仅当
成立时,g0(尣)与d(w)相等。称 max d(w), s.t. w 00=1, ![]() 为正项几何规划(4)的对偶规划。因为lnd(w)是w的凹函数,所以对偶规划(8)的任何局部极大点也是它的整体极大点。由(6)可知, 对于正项几何规划(4)与对偶规划(8)的任何一对可行解x与w,(4)的目标函数值绝不小于(8)的目标函数值,并且当且仅当(7)式成立时,这两个规划的目标函数值才相等,这时x与w分别是(4)与(8)的最优解。 对偶定理设正项几何规划(4)有满足gm(尣)<1(m=1,2,…,M)的可行解并且有最优解,则对偶规划(8)也有最优解,并且这两个规划的最优值相等。 对偶定理的假设条件之一是(4)有最优解。但是在什么情况下(4)一定有最优解呢?可作如下的回答: 若(4)有可行解而(8)有分量全为正的可行解,则正项几何规划(4)必有最优解。 由于对偶规划只有线性约束条件,特别对于某些特殊情形,例如当出现在各个gm(尣) (m =0,1,…,M)中的项数总和 ![]()
来获得正项几何规划(4)的最优解。因为 近十多年来,除了正项几何规划外,对于容许系数сmt为负的符号几何规划、出现反向约束不等式gm(尣)≥1的反向几何规划以及gm(尣)是两个正项式的商的补几何规划,也有了不少的研究,特别是E.L.彼得森的工作扩大了几何规划的研究范围。
|