線形計画問題の最適解の精度保証(カオスの通信への応用,局在振動,一般)

概要

論文の詳細を見る
This paper concerns with the following linear programming problem: Maximize c^tx, subject to Ax≦b and x≧0, where A∈F^<m×n>,b∈F^m and c, x∈F^n. Here, F is a set of floating point numbers. The aim of this paper is to propose a numerical method of including an optimum point of this linear programming problem provided that a good approximation of an optimum point is given. The proposed method is base on Kantorovich's theorem and the continuous Newton method. Kantorovich's theorem is used for proving the existence of a solution for complimentarity equation and the continuous Newton method is used to prove feasibility of that solution. Numerical examples show that a computational cost to include optimum point is about 4 times than that for getting an approximate optimum solution.
2008-12-02