Proving the convergence of the iterative method for solving a game-type combinatorial optimization problem on arrangemen
- PDF / 117,855 Bytes
- 12 Pages / 594 x 792 pts Page_size
- 48 Downloads / 182 Views
PROVING THE CONVERGENCE OF THE ITERATIVE METHOD FOR SOLVING A GAME-TYPE COMBINATORIAL OPTIMIZATION PROBLEM ON ARRANGEMENTS O. A. Iemetsa† and E. V. Olkhovskaja a‡
UDC 519.85
Abstract. We consider a game-type combinatorial optimization problem where constraints defined by arrangements are imposed on the strategies of one player and propose a theoretical justification for the iteration method of the solution to combinatorial optimization problems. Keywords: Euclidean combinatorial optimization, game-type combinatorial optimization problem, iterative method, convergence of a method.
Recent decades have seen an active development of the theory and methods of discrete and combinatorial optimization [1–6], in particular Euclidean one [7–14]. Many problems in various fields can be described and solved with the use of combinatorial models [2, 5–14]. Among these are game-type problems with constraints defined by combinatorial conditions. There are iterative algorithms to solve this class of problems [15, 21]. As numerical experiments have shown, the method may converge. In the paper, we will prove the convergence of the iterative method of the solution of combinatorial optimization problems. PROBLEM STATEMENT AND NECESSARY NOTATION The paper [21] considers a two-player manufacturing problem and proposes its mathematical model. Let us present a mathematical interpretation of this problem. To introduce the necessary notation, let Pix be an element from a set x P x = ( P1x , P2x , K , PM ) of M real numbers that satisfies the inequality 0 £ Pix £ 1 , i Î J M = {1, 2, ... , M }, where J M is the
set of the first M natural numbers, X = ( x1 , x 2 , K , x m ) be a vector whose elements are arrangements of M elements, i.e., ( P x ) , where E m ( P x ) is the set of m arrangements of elements of the set P x [8]. x i Î P x , and X = ( x1 , x 2 , K , x m ) Î E m M M m
The following conditions are also satisfied in the mathematical model from [21] for X :
å xi i =1
= 1; $P jx Î P x ; x m = P jx .
In what follows, we denote the vector of the first m -1 coordinates of the vector X by X : X = ( x1 , x 2 , K , x m -1 ) , then -1 X = ( x1 , x 2 , K , x m -1 ) Î E m ( P x ). M The game is as follows: the first player can choose a vector X = ( x1 , x 2 , K , x m ) Î E m ( P x ) , and the second j Î J n ; M the payoffs of the first player to the second player are a1 j , K , a mj with probabilities x1 , K , x m , respectively, where a ij are some real numbers "i Î J m ; j Î J n . Denote by A¢ a matrix whose element a¢ij is an element of the payoff of the first player to the second one. The payoff of the first player to the second player (if they chose strategies X Î E m ( P x ) and j Î J n , respectively) is defined by the M a
Poltava University of Economics and Trade, †[email protected]; ‡[email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 1, January–February, 2013, pp. 102–114. Original article submitted November 28, 2011. 86
1060-0396/13/4901-0086
©
2013 Springer Science+Business Media New York
m
f
Data Loading...
