求解多目标线性规划问题的内点新算法

doi:10.3863/j.issn.1000-2634.2000.04.022

西南石油大学学报(自然科学版) ›› 2000, Vol. 22 ›› Issue (4): 80-83.DOI: 10.3863/j.issn.1000-2634.2000.04.022

求解多目标线性规划问题的内点新算法

钟仪华¹ 王昱²江茂泽³

1.西南石油学院计算机科学系,四川南充637001; 2.西南石油学院成人教育学院; 3.西南石油学院教务处

收稿日期:2000-04-06 修回日期:1900-01-01 出版日期:2000-11-20 发布日期:2000-11-20

NEW ALGORITHM OF INTERIOR POINT TO SOLVE MOLP PROBLEMS

ZHONG Yi-hua WANG Yu JIANG Mao-ze

Southwest Petroleum inst

Received:2000-04-06 Revised:1900-01-01 Online:2000-11-20 Published:2000-11-20

摘要/Abstract

摘要： 通过对内点多目标线性规划中采用有效鞍点来产生搜寻方向一文的研究,提出了新的仿射尺度内点多目标算法。该方法首先求出每个目标函数在最优规划中所作的贡献率,然后解一个单目标线性规划问题,其解作为有效鞍点的初始值。在迭代过程中,投影单个价值向量(单个目标函数的系数)以求出投影方向,然后求出这些投影方向及现行迭代点到鞍点的方向对最优解的较真实的贡献率,从而获得下一次迭代的方向。在进行下次迭代前,求出新的边界点与鞍点对最优解的较真实贡献率,以确定新的边界点是否取代鞍点。新算法组合使用了层次分析法(AHP)中
的标权转换法和内点法,将q个有效鞍点减少为一个。实例计算表明,该方法是可行的。

关键词: 多目标线性规划(MOLP), 有效鞍点, 层次分析法(AHP), 标权转换法, 仿射尺度内点法

Abstract: According to the efficient anchoring point for generating search directions in interior multiobjective linear programming (MOLP), the paper presented the new affine-scaling interior MOLP algorithm. First the contribution rate of each objective function to optimal solution was found as the initial value, then
a single - objective linear programming problem was solved and got an efficient anchor point with which to start the iterative process. During the iterative process, in light of the projected individual cost vectors (the coefficient of objective function) ,we can get the projected gradients and real contribution rates of them to optimal solution for the anchor point. Using these contribution rates, we generate a combined step direction along
which the next step is taken. Before proceeding the next iteration, use the scale - weight transformation method in AHP to confirm whether anchor point is always efficient. Scale weight transformation method in AHP and affinescaling interior points algorithm reduced the number of efficient anchor
points to one. The computing examples proved that this method is feasible.

Key words: multiobjective linear programming, efficient anchor points, analytic hierarchy process, scale weight transformation method, affine scaling interior point algorithm

中图分类号: