Issuu

REVISTA DIGITAL PROGRAMACIÓN ENTERA

Republica Bolivariana De Venezuela

Universidad Bicentenaria De Aragua

Vicerrectorado Académico

Facultad De Ingenieria

Escuela De Sistemas

Asignatura: Investigación de Operaciones I Createc- Táchira

Autor: Yohandrick Lugo

C.I: 31.059.299

Trimestre: VII

Sección:T1

Unidad: II MSc: Claudia Hernandez

San Cristóbal, Octubre del 2025

PROGRAMACION ENTERA, MÉTODOS DE SOLUCIÓN PARA PROGRAMACIÓN ENTERA, MODELO DE TRANSBORDO CON CAPACIDADES, MÉTODO SIMPLEX DE LA RED CAPACITADA, ORIGEN DEL PERT-CPM, DIAGRAMAS DE RED O GRAFOS DE PERT-CPM, TIEMPOS EN GRAFO, RUTA CRÍTICA, HOLGURAS, PROBABILIDAD DE CONCLUIR UN PROYECTO, TIEMPO Y COSTO ÓPTIMO DE UN PROYECTO, CURVAS DE COSTO Y TIEMPO.

2025

DIRECTOR EDITORIAL

YOHANDRICK ENRIQUE LUGO GOMEZ

CONSEJO EDITORIAL

UNIVERSIDAD BICENTENARIA DE ARAGUA

UBA

INTRODUCCION

La programación entera (PE), también conocida como integer programming o programación lineal entera, es una herramienta fundamental en la optimización matemática y la investigación de operaciones (OR). A diferencia de la programación lineal continua, que permite valores fraccionarios, la PE refleja mejor situaciones reales donde no se pueden dividir recursos o decisiones (e.g., no puedes contratar 2.5 empleados).

Programacion Entera Programacion Entera

La programación entera es una técnica de optimización matemática que busca la mejor solución a problemas donde las variables deben ser númerosenteros(como0,1,2,etc.),adiferenciadelaprogramaciónlineal continua.Seformulacomomaximizarominimizarunafunciónlinealsujeta a restricciones lineales, con variables enteras, resolviéndose mediante algoritmoscomoramificaciónyacotamiento.

AplicacionesPrácticas:

Logística: Optimiza rutas de entrega y asignación de vehículos (ej. UPS reducecostosenrutas).

Producción: Planifica recursos y líneas de ensamblaje (ej. industria automotrizminimizadesperdicios).

Finanzas:Seleccionaportafoliosdeinversióndiscretos(ej.fondoscomo Vanguardmejoranretornos).

Horarios:Asignaturnosdepersonal(ej.hospitalesoptimizanscheduling médico).

Telecomunicaciones: Diseña redes y asigna frecuencias (ej. AT&T minimizainterferencias).

Programación Entera

La programación entera se resuelve con métodos exactos como ramificar y acotar, planos de corte y su combinación (branch and cut), yaqueesNP-hard.Acontinuación,unresumenconciso.

Algoritmo de Ramificar y Acotar (BranchandBound)

Funcionamiento: Relaja el problema (ignora enteros), resuelve con PL. Ramifica en subproblemas fijando variables noenteras(e.g.,x≤2ox≥3).Acotay poda nodos peores que la mejor soluciónentera.

MétodoMixto:BranchandCut Funcionamiento: Combina ambos: aplica cortes en nodos de branch and bound para fortalecer relajaciones antesderamificar.

MétododePlanosdeCorte(CuttingPlanes)

Funcionamiento: Resuelve relajación lineal; agrega desigualdades (cortes)queeliminansolucionesnoenterassinafectaróptimas(e.g., cortesdeGomory).Iterahastasoluciónentera.

Problemaenterocero-uno:Esuncasoespecialdeprogramaciónentera donde todas las variables son binarias, tomando solo valores 0 o 1. Representa decisiones sí/no, como seleccionar elementos de un conjunto. Un problema clásico de programación entera cero-uno es el de la mochila, donde se decide qué items incluir (sí/no) para maximizar elvalortotalsinexcederlacapacidaddepeso.

Modelo de Transbordo con Capacidades Modelo de Transbordo con Capacidades

Problema de flujo en redes con nodos de oferta (fuentes), demanda (sumideros)ytransbordo(intermedios).Incluyecapacidadesenarcos. Aplicaciones:Logística,transporte.

Ejemplo: Red con fuentes A/B, transbordo C, sumideros D/E. Resolver consolverscomoPuLP.

Método Simplex de la Red Capacitada Método

Simplex de la Red Capacitada

Variantedelsimplexpararedesconcapacidades.Explotaestructurade árbolparaeficiencia.

Pasos: Inicializar solución factible; verificar optimalidad con duales; pivoteoenciclos;iterar.

Ventajas: Más rápido (O(m log n)) que simplex general; usado en CPLEXparatransporte/asignación.

Origen del PERT-CPM Origen del PERT-CPM

CPM (Critical Path Method):

Desarrollado en 1957 por DuPont y Remington Rand para gestionar proyectos de construcción química. Enfocado en identificar el camino crítico (secuencia de actividades que determina la duracióntotal).

PERT (Program Evaluation and Review Technique): Creado en 1958 por la Oficina de Proyectos EspecialesdelaMarinadeEE.UU. para el proyecto Polaris (misiles balísticos). Incorpora incertidumbre en tiempos de actividades (distribuciones probabilísticas) y análisis de riesgos.

Elementos:

Diagramas de Red o Grafos de PERT-CPM

Diagramas de Red o Grafos de

PERT-CPM

Los diagramas de red en PERT/CPM son grafos dirigidos (DAG) que representanactividadesyeventosenunproyecto.

Nodos (Eventos): Puntos de inicio/fin de actividades (e.g., "inicioproyecto","fintarea").

Arcos (Actividades): Flechas con duración estimada (CPM usatiempodeterminista.

Caminos: Secuencias de actividades.Elcaminocríticoes el más largo (determina duraciónmínimadelproyecto).

TiposdeDiagramas:

Diagrama de flechas (ADM): Actividades en arcos, eventos ennodos.

Diagrama de precedencias (PDM): Actividades en nodos, conrelacionesdeprecedencia.

TiemposenGrafo:

Ejemplo Simple: Proyecto con actividades: A (2 días), B (3 días, después de A), C (1 día, después deA),D(4días,despuésdeByC).

Grafo:A → B → D,A → C → D.

Camino crítico: A → B → D (duración2+3+4=9días).

Tiempodeactividad:CPMdeterminista. Tiempotemprano(TE):Máx.depredecesores+duración.

Tiempotardío(TL):Mín.desucesores-duración.

RutaCrítica:

Camino más largo (suma máxima de duraciones); determina duraciónmínima.

Actividadesconholguracero;retrasosafectanelproyecto.

Ejemplo:A(2)→B(3)→D(4)=9días.

Holguras:

Total: TL - TE (flexibilidad sin retrasarproyecto).

Libre: Sin afectar sucesores inmediatos. =0enrutacrítica.

Probabilidad de Concluir un Proyecto:

Asume distribución normal; varianza = suma de varianzascríticas.

P(T ≤ t) = Φ((t - media)/σ), usandotablanormal.

Ejemplo: Media 20d, σ=2d; P(≤22d)≈84%.

TiempoyCostoÓptimo

Trade-off: Acelerar reduce duración pero aumenta costo directo.

Óptimo: Min. costo total para duración objetivo (costo marginal=beneficio).

CurvasdeCostoyTiempo

Directo: Aumenta al acelerar (másrecursos).

Indirecto: Disminuye al acortar (ahorrosporearlycompletion).

Total: Suma; mínimo en óptimo.

Gráfica:X=tiempo,Y=costo.

CONCLUSIÓN

La programación entera (PE), también conocida como programación lineal entera o integer linear programming (ILP), es una rama de la optimización matemática que extiende la programación lineal (PL) al requerir que algunas o todas las variables de decisión tomen valores enteros (positivos, negativos o cero). Esto la hace ideal para modelar problemas donde las decisiones son discretas, como seleccionar cantidades enteras de ítems o asignar recursos indivisibles. A diferencia delaPL(queespolinomialmenteresoluble),laPEesNP-difícilengeneral, lo que significa que no existe un algoritmo eficiente para resolver todas las instancias en tiempo razonable, especialmente para problemas grandes. Sin embargo, ha evolucionado significativamente desde sus orígenes en los años 1950-1960, impulsada por avances en algoritmos y computación.

IBM.Programacióndeenteros.Recuperadoel25deoctubrede2025

https://www.ibm.com/docs/es/icos/22.1.2?topic=integerprogramming-integerprogramming

Scribd ProgramacionLinealEntera Recuperadoel25deoctubrede2025

https://es.scribd.com/document/522553405/PROGRAMACION-LINEAL-ENTERA

Investopedia Zero-OneIntegerProgrammingMeaningandExamples Recuperado el25deoctubrede2025

https://www.investopedia.com/terms/z/zero-one-integer-programming.asp

Recuperadoel25deoctubrede2025

https://asana.com/es/resources/pert-chart

Scribd.ProblemasTransbordo.Recuperadoel25deoctubrede2025

https://es.scribd.com/document/237123056/Problemas-Transbordo

Scribd.Pert-Cpm.Recuperadoel25deoctubrede2025

https://es.scribd.com/document/131103080/1-pert-cpm

https://asana.com/es/resources/critical-path-method