Analysis of mathematical models and methods of solving combinatorial optimization problems on game-type permutations
- PDF / 148,057 Bytes
- 10 Pages / 595 x 842 pts (A4) Page_size
- 59 Downloads / 196 Views
ANALYSIS OF MATHEMATICAL MODELS AND METHODS OF SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS ON GAME-TYPE PERMUTATIONS
UDC 519.85
O. A. Yemets and N. Yu. Ust’yan
The paper is concerned with an optimization problem on game-type permutations, where one or both players have combinatorial constraints on their strategies. A mathematical model of such problems is constructed and analyzed. A modified graphical method is proposed to solve (2xn)- and (mx2)-dimensional problems. High-dimensional problems are reduced to linear programming and combinatorial optimization problems. Keywords: optimization problem on permutations, antagonistic game, value of game, modified graphical method, linear programming methods, combinatorial optimization.
Introduction. A problem of choosing one of the possible actions is frequently encountered in practice. If the final result completely depends on the behavior of one decision-maker, then maximum profit can be gained by solving an optimization problem. An analysis of the last studies and publications shows that many optimization problems can be described by models of Euclidean combinatorial optimization (see, for example, [1–8]), and there are methods [1, 3, 6–11] quite efficient to solve them. At present time, — when it is the market that rules — conflicting situations very often occur, where everyone tends to attain the purpose in his own way but no one decides fully the end result on his own. Such situations are known to be studied by mathematical game theory (see, for example, [12–17]). Classical game theory considers conflicting situations where each of the players may freely apply his strategies. But there may be technological constraints, for example, in economic problems, on the use of equipment during production, constraints on resources, etc. These constraints may be combinatorial, such as dispatcher’s assigning of buses of different capacity to different routes. It is impossible to consider the pure strategies of players in such problems (all the buses cannot be sent to one route), and mixed strategies cannot all be applied. Such problems with combinatorial game constraints require constructing appropriate mathematical models and developing methods that take into account specific features of the problems. PROBLEM FORMULATION We formulate and solve optimization problems on game-type permutations, where one or both players have combinatorial constraints for the use of their strategies. To solve such problems, we will apply the modified graphical method (developed here) of classical game theory, linear programming methods, and combinatorial optimization methods. Let us now set out the main material, with full substantiation of our findings. Let us consider the problems that give the above mathematical models. Problem 1. A farm cultivates m types of agricultural crops on m fields. The fields are of different areas; therefore, the amount of each crop depends on what field it is grown. Moreover, the yield of each crop, and thus the profit of the farm, depends on weather. It is necessa
Data Loading...
