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...
- 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
| id |
UNACIONAL2_94dfd3ffc6001ac04803dc6a88ca0b0f |
|---|---|
| oai_identifier_str |
oai:repositorio.unal.edu.co:unal/28732 |
| network_acronym_str |
UNACIONAL2 |
| network_name_str |
Universidad Nacional de Colombia |
| repository_id_str |
|
| dc.title.spa.fl_str_mv |
Una búsqueda de "direcciones factibles" para la solución de problemas de programación lineal |
| title |
Una búsqueda de "direcciones factibles" para la solución de problemas de programación lineal |
| spellingShingle |
Una búsqueda de "direcciones factibles" para la solución de problemas de programación lineal 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 |
| title_short |
Una búsqueda de "direcciones factibles" para la solución de problemas de programación lineal |
| title_full |
Una búsqueda de "direcciones factibles" para la solución de problemas de programación lineal |
| title_fullStr |
Una búsqueda de "direcciones factibles" para la solución de problemas de programación lineal |
| title_full_unstemmed |
Una búsqueda de "direcciones factibles" para la solución de problemas de programación lineal |
| title_sort |
Una búsqueda de "direcciones factibles" para la solución de problemas de programación lineal |
| dc.creator.fl_str_mv |
Malpica Angarita, Jaime U |
| dc.contributor.author.spa.fl_str_mv |
Malpica Angarita, Jaime U |
| dc.subject.proposal.spa.fl_str_mv |
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 |
| topic |
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 |
| description |
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". |
| publishDate |
2003 |
| dc.date.issued.spa.fl_str_mv |
2003 |
| dc.date.accessioned.spa.fl_str_mv |
2019-06-26T10:23:08Z |
| dc.date.available.spa.fl_str_mv |
2019-06-26T10:23:08Z |
| dc.type.spa.fl_str_mv |
Artículo de revista |
| dc.type.coar.fl_str_mv |
http://purl.org/coar/resource_type/c_2df8fbb1 |
| dc.type.driver.spa.fl_str_mv |
info:eu-repo/semantics/article |
| dc.type.version.spa.fl_str_mv |
info:eu-repo/semantics/publishedVersion |
| dc.type.coar.spa.fl_str_mv |
http://purl.org/coar/resource_type/c_6501 |
| dc.type.coarversion.spa.fl_str_mv |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
| dc.type.content.spa.fl_str_mv |
Text |
| dc.type.redcol.spa.fl_str_mv |
http://purl.org/redcol/resource_type/ART |
| format |
http://purl.org/coar/resource_type/c_6501 |
| status_str |
publishedVersion |
| dc.identifier.uri.none.fl_str_mv |
https://repositorio.unal.edu.co/handle/unal/28732 |
| dc.identifier.eprints.spa.fl_str_mv |
http://bdigital.unal.edu.co/18780/ |
| url |
https://repositorio.unal.edu.co/handle/unal/28732 http://bdigital.unal.edu.co/18780/ |
| dc.language.iso.spa.fl_str_mv |
spa |
| language |
spa |
| dc.relation.spa.fl_str_mv |
http://revistas.unal.edu.co/index.php/ingeinv/article/view/14703 |
| dc.relation.ispartof.spa.fl_str_mv |
Universidad Nacional de Colombia Revistas electrónicas UN Ingeniería e Investigación Ingeniería e Investigación |
| dc.relation.ispartofseries.none.fl_str_mv |
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 |
| dc.relation.references.spa.fl_str_mv |
Malpica Angarita, Jaime U (2003) 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 . |
| dc.rights.spa.fl_str_mv |
Derechos reservados - Universidad Nacional de Colombia |
| dc.rights.coar.fl_str_mv |
http://purl.org/coar/access_right/c_abf2 |
| dc.rights.license.spa.fl_str_mv |
Atribución-NoComercial 4.0 Internacional |
| dc.rights.uri.spa.fl_str_mv |
http://creativecommons.org/licenses/by-nc/4.0/ |
| dc.rights.accessrights.spa.fl_str_mv |
info:eu-repo/semantics/openAccess |
| rights_invalid_str_mv |
Atribución-NoComercial 4.0 Internacional Derechos reservados - Universidad Nacional de Colombia http://creativecommons.org/licenses/by-nc/4.0/ http://purl.org/coar/access_right/c_abf2 |
| eu_rights_str_mv |
openAccess |
| dc.format.mimetype.spa.fl_str_mv |
application/pdf |
| dc.publisher.spa.fl_str_mv |
Universidad Nacional de Colombia - Facultad de Ingeniería |
| institution |
Universidad Nacional de Colombia |
| bitstream.url.fl_str_mv |
https://repositorio.unal.edu.co/bitstream/unal/28732/1/14703-44154-1-PB.pdf https://repositorio.unal.edu.co/bitstream/unal/28732/2/14703-44154-1-PB.pdf.jpg |
| bitstream.checksum.fl_str_mv |
e8d69cefbf1dc8e9ecb6fc1077ddc569 299a4b4a3de7d30a0d26001443b336d6 |
| bitstream.checksumAlgorithm.fl_str_mv |
MD5 MD5 |
| repository.name.fl_str_mv |
Repositorio Institucional Universidad Nacional de Colombia |
| repository.mail.fl_str_mv |
repositorio_nal@unal.edu.co |
| _version_ |
1814089971805454336 |
| spelling |
Atribución-NoComercial 4.0 InternacionalDerechos reservados - Universidad Nacional de Colombiahttp://creativecommons.org/licenses/by-nc/4.0/info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2Malpica Angarita, Jaime U673933eb-b66d-4206-bb10-ed9ba742e2533002019-06-26T10:23:08Z2019-06-26T10:23:08Z2003https://repositorio.unal.edu.co/handle/unal/28732http://bdigital.unal.edu.co/18780/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.application/pdfspaUniversidad Nacional de Colombia - Facultad de Ingenieríahttp://revistas.unal.edu.co/index.php/ingeinv/article/view/14703Universidad Nacional de Colombia Revistas electrónicas UN Ingeniería e InvestigaciónIngeniería e InvestigaciónIngenierí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-5609Malpica Angarita, Jaime U (2003) 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 .Una búsqueda de "direcciones factibles" para la solución de problemas de programación linealArtículo de revistainfo:eu-repo/semantics/articleinfo:eu-repo/semantics/publishedVersionhttp://purl.org/coar/resource_type/c_6501http://purl.org/coar/resource_type/c_2df8fbb1http://purl.org/coar/version/c_970fb48d4fbd8a85Texthttp://purl.org/redcol/resource_type/ARTlinear programmingsimplex methodpolyhedral characteristicsprimal and dual linear programs relationskarush-kuhn-tucker optimality criteriaprogramación linealmétodo simplexcaracterísticas poliédricasrelaciones de los programas lineales principal y dualcriterios de optimalidad Karush-Kuhn-TuckerORIGINAL14703-44154-1-PB.pdfapplication/pdf1307256https://repositorio.unal.edu.co/bitstream/unal/28732/1/14703-44154-1-PB.pdfe8d69cefbf1dc8e9ecb6fc1077ddc569MD51THUMBNAIL14703-44154-1-PB.pdf.jpg14703-44154-1-PB.pdf.jpgGenerated Thumbnailimage/jpeg6044https://repositorio.unal.edu.co/bitstream/unal/28732/2/14703-44154-1-PB.pdf.jpg299a4b4a3de7d30a0d26001443b336d6MD52unal/28732oai:repositorio.unal.edu.co:unal/287322022-11-18 23:02:34.51Repositorio Institucional Universidad Nacional de Colombiarepositorio_nal@unal.edu.co |