Una búsqueda de "direcciones factibles" para la solución de problemas de programación lineal

El estudio presenta un enfoque para resolver problemas de programación lineal sin el uso de variables artificiales. Se emplea la pareja dual: un problema lineal de minimización (principal) en la forma estándar y un problema lineal de maximización asociado (dual). Inicialmente, el programa dual (o un programa dual parcial) se resuelve por medio de una búsqueda de "direcciones factibles", donde las condiciones de Karush-Kuhn-Tucker ayudan, primero a verificar su optimalidad y, después, su factibilidad. La búsqueda de "direcciones factibles" explota las características del poliedro (o politopo) convexo formado por las restricciones del programa dual para hallar un punto inicial y luego sigue segmentos de rectas cuyas direcciones se encuentran en subespacios afines definidos por los hiperplanos de frontera de las caras poliédricas, para hallar los puntos siguientes hasta el (o un) punto óptimo. Luego, las restricciones duales restantes no satisfechas en aquel punto dual óptimo, si hay alguna, se manejan como variables no básicas del programa principal, que se resuelve por la misma búsqueda de "direcciones factibles".

• Autores: Malpica Angarita, Jaime U
• Tipo de recurso: Article of journal
• Fecha de publicación: 2003
• Institución: Universidad Nacional de Colombia
• Repositorio: Universidad Nacional de Colombia
• Idioma: spa
• OAI Identifier: oai:repositorio.unal.edu.co:unal/28732
• Acceso en línea: https://repositorio.unal.edu.co/handle/unal/28732; http://bdigital.unal.edu.co/18780/
• Palabra clave: linear programming; simplex method; polyhedral characteristics; primal and dual linear programs relations; karush-kuhn-tucker optimality criteria; programación lineal; método simplex; características poliédricas; relaciones de los programas lineales principal y dual; criterios de optimalidad Karush-Kuhn-Tucker
• Rights: openAccess
• License: Atribución-NoComercial 4.0 Internacional