Escudo de la República de Colombia
Sistema Nacional de Biliotecas - Repositorio Institucional Universidad Nacional de Colombia Biblioteca Digital - Repositorio Institucional UN Sistema Nacional de Bibliotecas UN

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

Malpica Angarita, Jaime U (2010) Una búsqueda de "direcciones factibles" para la solución de problemas de programación lineal. Ingeniería e Investigación; Vol. 23, núm. 3 (2003): (53); 39-43 Ingeniería e Investigación; Vol. 23, núm. 3 (2003): (53); 39-43 2248-8723 0120-5609 .

Texto completo

[img]
Vista previa
PDF
1MB

URL oficial: http://revistas.unal.edu.co/index.php/ingeinv/arti...

Resumen

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"., The study presents an approach to solve linear programming problems with no artificial variables. A primal linear minimization problem is standard form and its associated dual linear maximization problem are used. Initially, the dual (or a partial dual) program is solved by a "feasible direction" search, where the Karush-Kuhn-Tucker conditions help to verify its optimality and then its feasibility. The "feasible direction" search exploits the characteristics of the convex polyhedron (or prototype) formed by the dual program constraints to find a starting point and then follows line segments, whose directions are found in afine subspaces defined by boundary hyperplanes of polyhedral faces, to find next points up to the (an) optimal one. Them, the remaining dual constraints not satisfaced at that optimal dual point, if there are any, are handled as nonbasic variables of the primal program, which is to be solved by such "feasible direction" search.

Tipo de documento:Artículo - Article
Información adicional:Los autores o titulares del derecho de autor de cada artículo confieren a la revista Ingeniería e Investigación de la Universidad Nacional de Colombia una autorización no exclusiva, limitada y gratuita sobre el artículo que una vez evaluado y aprobado se envía para su posterior publicación ajustándose a las siguientes características: 1.    Se remite la versión corregida de acuerdo con las sugerencias de los evaluadores y se aclara que el artículo mencionado se trata de un documento inédito sobre el que se tienen los derechos que se autorizan y se asume total responsabilidad por el contenido de su obra ante la revista Ingeniería e Investigación, la Universidad Nacional de Colombia y ante terceros. 2.    La autorización conferida a la revista estará vigente a partir de la fecha en que se incluye en el volumen y número respectivo de la revista Ingeniería e Investigación en el Sistema Open Journal Systems y en la página principal de la revista (www.revistaingenieria.unal.edu.co), así como en las diferentes bases e índices de datos en que se encuentra indexada la publicación. 3.    Los autores autorizan a la revista Ingeniería e Investigación de la Universidad Nacional de Colombia para publicar el documento en el formato en que sea requerido (impreso, digital, electrónico o cualquier otro conocido o por conocer) y autorizan a la revista Ingeniería e Investigación para incluir la obra en los índices y buscadores que estimen necesarios para promover su difusión. 4.    Los autores aceptan que la autorización se hace a título gratuito, por lo tanto renuncian a recibir emolumento alguno por la publicación, distribución, comunicación pública y cualquier otro uso que se haga en los términos de la presente autorización.
Palabras 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
Unidad administrativa:Revistas electrónicas UN > Ingeniería e Investigación
Código ID:18780
Enviado por : Dirección Nacional de Bibliotecas STECNICO
Enviado el día :25 Junio 2014 19:43
Ultima modificación:19 Agosto 2014 04:01
Ultima modificación:19 Agosto 2014 04:01
Exportar:Clic aquí
Estadísticas:Clic aquí
Compartir:

Solamente administradores del repositorio: página de control del ítem

Vicerrectoría de Investigación: Número uno en investigación
Indexado por:
Indexado por Scholar Google WorldCat DRIVER Registry of Open Access Repositories OpenDOAR Metabiblioteca BDCOL OAIster Red de repositorios latinoamericanos DSpace BASE Open archives La referencia Colombiae Open Access Theses and Dissertations Tesis latinoamericanas CLACSO
Este sitio web se ve mejor en Firefox