Problemas complementarios lineales

Abstract

En este trabajo se estudian los problemas de Programaci´on Complementaria Lineal. La importancia de este estudio viene enfatizada por el hecho de que, entre otros, los problemas de Programaci´on Lineal, los de Programaci´on Cuadr´atica y los de Juegos Bimatriciales pueden modelizarse como problemas de Programaci´on Complementaria Lineal. Para su resoluci´on, se presenta el algoritmo de pivotaje complementario de Lemke, se estudia en detalle y se aplica a la resoluci´on de distintos casos pr´acticos. El trabajo se completa con la prolongaci´on del estudio anterior a la resoluci´on de problemas de Programaci´on Cuadr´atica convexa y Juegos Bimatriciales. Por ´ultimo, se usa la versi´on programada en python del algoritmo de Lemke, para resolver algunos ejemplos pr´acticos relevantes.

In this project the problems of Linear Complementary Programming are studied. The importance of this study is emphasized by the fact that, among others, Linear Programming, Quadratic Programming and Bimatrix Games problems can be modeled as problems of Linear Complementary Programming. For its resolution, Lemke’s complementary pivot algorithm is presented, studied in detail and applied to the resolution of different case studies. The work is completed with the prolongation of the previous study to the resolution of problems of Convex Quadratic Programming and Bimatricial Games. Finally, the python version of Lemke’s algorithm is used to solve some relevant practical examples.