Determinación de un Punto de Inicio en Algoritmos de Punto Interior en la Solución de Problemas de Programación Lineal

Se presenta un estudio para encontrar un punto interior en la región factible de problemas de programación lineal, un aspecto que debe ser resuelto en la etapa inicial de la implementación de los algoritmos de punto interior empleados para optimizarlos. Para este fin, se propone un procedimiento que parte de una formulación que no requiere adicionar variables de holgura ni de exceso, solamente involucra una variable adicional para generar un poliedro en un nuevo espacio ampliado y que con proyecciones sencillas encuentra un punto interior en el mismo. Se demuestra que la solución óptima del problema de programación lineal ampliado permite obtener un punto factible del problema original o concluir que el mismo no tiene soluciones factibles. This paper presents a study done to find an interior point in the feasible region of linear programming problems is an aspect that should be solved in the initial stage of the implementation of the interior point algorithms used to optimize them. Consequently, it is proposed a methodology that starts with a formulation that does not require adding surplus or slack variables. It only includes an additional variable to generate a polyhedron in a new expanded space and with simple projections finds an interior point in the same polyhedron. It is demonstrated that the optimal solution of the extended linear programming problem allows obtaining a feasible point of the original problem or concluding that it has no feasible solutions.