Clasificación de la programación entera
Los modelos de Programación Entera se pueden clasificar en dos grandes áreas:
- Programación Entera Mixta (PEM): A esta categoría pertenecen aquellos problemas de optimización que consideran variables de decisión enteras o binarias, pero no de forma exclusiva.
- Programación Entera Pura (PEP): En esta categoría encontramos aquellos modelos que consideran exclusivamente variables de decisión que adoptan valores enteros o binarios.
Ejemplos de programación entera mixta
- Incorporación de costos fijos.
- Problemas de localización y transporte.
- Problema de generación.
Modelos en la programación entera pura
- Problema de la mochila.
- Problema de asignación.
Ejemplos de programación entera pura
- Problema de la mochila.
- Problema de asignación.
- Problema de corte de rollos.
- Selección de invitados a una boda.
- Programación de la explotación forestal.
¿Qué es el problema de la mochila?
El Problema de la Mochila (conocido también como Knapsack Problem o simplemente KP) es un problema clásico de la Investigación de Operaciones y, en particular, de la Programación Entera. Consiste en un excursionista que debe preparar su mochila, la cual tiene una capacidad limitada. El objetivo es seleccionar un subconjunto de objetos que maximice la utilidad sin sobrepasar la capacidad de carga.
Elementos de un modelo matemático del problema de la mochila
- Variables de decisión.
- Función objetivo.
- Restricciones.
28 y 29. ¿Qué es el problema de transbordo?
El Problema de Transbordo (o intertransporte) es una variación del modelo original de transporte que permite enviar unidades mediante nodos fuentes, destinos y transitorios, a diferencia del modelo tradicional que solo permite envíos directos.
Elementos de un problema de transbordo
- a. El problema: Modelar mediante programación lineal el problema de transbordo esbozado en un grafo.
- b. Variables de decisión: Deben representar la cantidad de unidades enviadas por medio de cada ruta.
- c. Restricciones:
- i. Restricciones de oferta.
- ii. Restricciones de demanda.
- iii. Restricciones de balanceo para nodos únicamente transitorios.
- iv. Restricciones de balanceo para nodos transitorios con requerimientos.
- d. Función objetivo: Se limita a la consignación de cada ruta con su respectivo costo bajo el criterio de minimización.
¿Qué es la programación no lineal?
Es el proceso de resolución de un sistema de igualdades y desigualdades sujetas a restricciones sobre variables reales, donde la función objetivo o alguna de las restricciones no son lineales.
Tipos de problemas de programación no lineal
- Optimización no restringida.
- Optimización linealmente restringida.
- Programación cuadrática.
- Programación convexa.
- Programación separable.
- Programación no convexa.
- Programación geométrica.
- Programación fraccional.
¿Existe un método para resolver todos los problemas de programación no lineal?
No, debido a que los problemas son tan diversos que no existe un algoritmo único capaz de resolver todas sus variantes.
Métodos para la optimización no restringida
Búsqueda directa y el algoritmo de gradiente.
Optimización linealmente restringida
Se caracteriza por restricciones que se ajustan a la programación lineal (funciones g(x) lineales), pero con una función objetivo no lineal.
Programación cuadrática
Los problemas tienen restricciones lineales, pero la función objetivo f(x) debe ser cuadrática.
Programación convexa
Abarca una clase de problemas donde f(x) es cóncava y cada g(x) es convexa.
Programación separable
Caso especial de programación convexa donde las funciones f(x) y g(x) pueden separarse en una suma de funciones de variables individuales.
Programación no convexa
Incluye problemas que no satisfacen las suposiciones de la programación convexa. No hay garantía de que un máximo local sea un máximo global.
Programación geométrica
Se aplica en diseño de ingeniería donde las funciones son polinomios positivos generalizados (posinomiales) y se busca minimizar.
Programación fraccional
Se presenta cuando la función objetivo tiene la forma de una fracción o cociente de dos funciones.
42 y 43. Teoría de colas
La Teoría de Colas es el estudio matemático del comportamiento de las líneas de espera. Consiste en tres componentes: población fuente, sistema de servicio y condición de salida de los clientes.
Procesos de nacimiento y muerte
Describen situaciones donde la cantidad de entes en el sistema aumenta o disminuye en una unidad (+1 o -1).
Modelo de Poisson
Distribución discreta utilizada frecuentemente para describir el patrón de llegadas a un sistema de colas.
Servidor
Explicación del concepto de servidor en un sistema de colas. 