| dc.creator | Pajilla Alejandro, Angelina | |
| dc.date | 2016-08-10T18:29:05Z | |
| dc.date | 2016-08-10T18:29:05Z | |
| dc.date | 2013 | |
| dc.date.accessioned | 2018-04-27T14:03:58Z | |
| dc.date.available | 2018-04-27T14:03:58Z | |
| dc.identifier | http://dspace.unitru.edu.pe/handle/UNITRU/1438 | |
| dc.identifier.uri | http://repositorioslatinoamericanos.uchile.cl/handle/2250/1423921 | |
| dc.description | En el presente informe exponemos las técnicas más usadas para resolver problemas de Programación Lineal Entera del tipo: (PE) ZPE = m ax{cx/x ∈ S} S = {x ∈ Zn + : Ax ≤ b} (1) donde c es un n - vector con coeficientes enteros y (A, b) es una matriz m×(n+1) con coeficientes enteros. Las técnicas que presentamos son Algoritmos Generales de Relajación Lineal: Algoritmo de Ramificación y Acotación (Branch and Bound) y el Algoritmo de Planos de Corte; son generales porque resuelven cualquier problema del tipo (1) y son de relajación Lineal porque al Problema del tipo (1) se lleva a un problema de Programación Lineal Continuo: (PL) ZPL = m ax{cx/x ∈ SPL} SPL = {x ∈ Rn + : Ax ≤ b} (2) para su resolución. De forma simplificada los Algoritmos Generales de Relajación Lineal resuelven el problema del tipo (1) siguiendo los pasos: 1) Se relaja linealmente el problema (1), es decir se lleva al problema (2), éste problema se resuelve usando el Algoritmo Simplex primal, obteniendose la solución óptima x∗. Si todas las componentes de x∗ son enteras, entonces x∗ es la solución óptima del problema (1) y su valor óptimo es ZPE. 2) Si en caso contrario, alguna de las componentes de x∗ no es entera entonces se van agregando restricciones al problema lineal (el problema (2)); En el algoritmo de Ramificación y Acotación estas restricciones vienen a ser desigualdades que van dividiendo a S en regiones más pequeñas, quitando reiv giones no factibles para el Problema Entero PE. En el algoritmo de Planos de Corte, estas restricciones vienen a ser cortes que van quitando de S la región que no contiene la solución óptima entera. Al agregar estas restricciones se procede a resolver estos problemas lineales por el Algoritmo simplex Dual, en un número finito de pasos hasta encontrar la solución óptima para PE. En el algoritmo de Ramificación y Acotación estudiamos diversos criterios para el mejor rendimiento del mismo. En el Algoritmo de Planos de Corte estudiamos dos algoritmos de éste tipo (Algoritmo Fraccional o Planos de Corte de Gomory y El Algoritmo Primal Planos de Corte), los cuales se diferencian en la manera que son generados los cortes. | |
| dc.language | spa | |
| dc.publisher | Universidad Nacional de Trujillo | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.rights | http://creativecommons.org/licenses/by-nc-nd/2.5/pe/ | |
| dc.source | Universidad Nacional de Trujillo | |
| dc.source | Repositorio Institucional - UNITRU | |
| dc.subject | algoritmos generales | |
| dc.subject | ciencias matematicas | |
| dc.title | Algoritmos generales de relajación lineal para problemas de programación entera | |
| dc.type | Tesis | |
