ε-Optimality for bicriteria programs and its application to minimum cost flows
ε-Optimality for bicriteria programs and its application to minimum cost flows
复制标题
双标准程序的ε-最优性及其在最小成本流中的应用
作者：
G. Ruhe;B. Fruhwirth
多准则优化问题的可行解的子集∧X称为ε-optimal w.r.t.向量值函数f:X→Y
AbstractA subsetS⊂X of feasible solutions of a multicriteria optimization problem is called ε-optimal w.r.t. a vector-valued functionf:X→Y
$$ subseteq $$
ℝK if for allx∈X there is a solutionzx∈S so thatfk(zx)≤(1+ε)fk(x) for allk=1,...,K. For a given accuracy ε>0, a pseudopolynomial approximation algorithm for bicriteria linear programming using the lower and upper approximation of the optimal value function is given. Numerical results for the bicriteria minimum cost flow problem on NETGEN-generated examples are presented.ZusammenfassungEine TeilmengeS⊂X von zulässigen Lösungen eines multikriteriellen Optimierungsproblems heißt ε-optimal bezüglich einer vektorwertigen Funktionf:f:X→ℝK, wenn für jedesx∈X eine Lösungzx∈S existiert, so daßfk(zx)≤(1+ε)fk(x) für allek=1, …,K gilt. Es wird ein pseudopolynomialer Algorithmus vorgestellt, der mit Hilfe einer oberen und unteren Approximation die Kurve der effizienten Punkte eines bikriteriellen linearen Programms mit einer vorgegebenen Genauigkeit ε>0 approximiert. Ergebnisse numerischer Untersuchungen mit dem bikriteriellen Kostenfluß Problem anhand von NETGEN-Netzwerken werden präsentiert.