Předmět Introd. to linear programm.& game theory (KMA / WULPH)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KMA / WULPH - Introd. to linear programm.& game theory, Přírodovědecká fakulta, Ostravská univerzita v Ostravě (OU).

Materiál	Typ	Datum	Počet stažení

Obsah

Programme of the course1.Introduction. General problem of optimization. Basic classification of optimization problems (linear, quadratic, convex, non-linear, non-convex problems). Examples of linear programming problems (the diet problem, the optimal plan of production (blending problem), the classical transportation problem).2.General linear programming problem. Set of feasible solutions. Convex combination, convex set. Convex polyhedron, its face, vertex. Fundamental Theorem of linear programming.3.Standard and canonical form of LP problem. Primal and dual problem. Conversion of a general LP problem into the standard, normal, and canonical form. Weak Duality Theorem and its corollaries.4.Foundations of duality theory. Farkas' Lemma. Gale's Theorem. Optimality condition for the primal problem.5.Foundations of duality theory. Optimality condition for the dual problem. Duality Theorem. Theorem on existence of optimal solutions for LP problems. Corollaries of the Duality Theorem and of the Existence Theorem.6.Foundations of duality theory. Economic interpretation of dual variables.7.Introduction. Concept of game. Basic classification of games (parlour etc.). Classification of games: games of two and more players, non-cooperative and cooperative, finite and infinite, with complete and incomplete information; games without and with a random mechanism (e.g. lottery), games with an unintelligent opponent. Strategic (normal) form game. Concept of the Nash equilibrium. Zero-sum game. Matrix game. Saddle point. Examples of matrix games: Blotto games and their interpretation (military, auction by sealed tender, presentation and gaining contracts on markets), Hide and Attack (attack on a convoy), hand game Morra, air protection model; operation on an injured person. Problem of the existence of a saddle point of a matrix and the way of finding it (max min and min max).8.Explicit form games. Examples of explicit form games (draughts, chess, removing matches ? Nim, noughts and crosses ? connect five, reversi). Concept of the strategy in an explicit form game. Existence of equilibrium strategies and the way of finding them. Possibility of conversion into a matrix or bimatrix game.9.Matrix games. Saddle point and problem of its existence. Value of game. Mixed extension of a matrix game. Fundamental Theorem of matrix games.10.Matrix games. Symmetric matrix games and their properties (zero value, symmetry of mixed extension). Conversion of a matrix game into a symmetric matrix game.11.Connections between linear programming and matrix games. Duality Theorem, weak duality and saddle point. Finding a solution of a linear programming problem by finding a saddle point of a mixed extension of a matrix game.12.General theorem on existence of saddle points. Relation between sup inf and inf sup (max min and min max). Characterization of saddle point. Classical Nikaidô-Isoda Theorem (in the case of two players and general number of players; without proof).13.Revision

Literatura

Guéret, C.; Prins, C.; Sevaux, M. Applications of optimization with Xpress-MP. Dash optimization, 2002. ISBN 0-9543503-0-8.Brickman, L. Mathematical Introduction to Linear Programming and Game Theory. Springer, 1989. ISBN 0-387-96931-2.Franklin, J. N. Methods of Mathematical Economics: Linear and Nonlinear Programming, Fixed-Point Theorems. SIAM, 2002. ISBN 0-89871-509-1.

Požadavky

To successfully pass the exam, the student must study regularly, actively participate in the classes, and regularly submit set homework tasks. Without achieving these requirements, the student´s examination result is automatically classified as "fail". The examination is oral. To obtain the grade "good", the student must demonstrate knowledge of the subjects that have been taught, i.e. students must understand the concepts and relations amongst them, including definitions, propositions, theorems etc. To obtain the grade "very good", the student must be able to apply the introduced concepts and relations amongst them to derive new properties or relations or to solve problems, i.e. the student must know short or simple proofs as well as understanding their application or solution. To obtain the grade "excellent", the student must know the subject to the full extent, including an understanding of more detailed aspects (especially the Duality Theorem and the Fundamental Theorem of matrix games), the connections between them and their derivation, i.e. the student must know complicated proofs and must understand their structure.The evaluation of the course including the classification is carried out in accordance with the Study and Examination Regulations OU.

Garant

doc. RNDr. David Bartl, Ph.D.

Vyučující

doc. RNDr. David Bartl, Ph.D.doc. RNDr. David Bartl, Ph.D.