“Formulación matemática de los problemas”
Enviado por Anitamalita1 • 3 de Noviembre de 2021 • Trabajos • 794 Palabras (4 Páginas) • 52 Visitas
Universidad Católica del Norte[pic 1][pic 2]
Departamento de Ingeniería Industrial
Antofagasta
Investigación Operativa II
Trabajo 1: “Formulación matemática de los problemas”
Profesora: Javiera Auad
Ayudantes: Geraldine Barraza – Pauline Demanet – Esteban Pino – Minas Potamianos
Vehicle Routing Problem (VRP):
- Conjuntos
Conjunto de clientes.[pic 3]
Conjunto de nodos, donde 0 representa el centro de distribución [pic 4][pic 5]
Conjunto de todos los arcos entre cada nodo [pic 6][pic 7]
- Parámetros
: Costo o distancia entre nodos y el nodo , o bien del arco . [pic 8][pic 9][pic 10][pic 11]
: Carga de entrega al cliente . [pic 12][pic 13]
Capacidad de cada vehículo.[pic 14]
- Variables de decisión
Igual a 1 cuando se decide viajar en el arco cero de lo contrario.[pic 15][pic 16]
Acumulación de capacidad (carga) hasta el nodo (cliente) . [pic 17][pic 18]
- Función objetivo
El objetivo es encontrar un conjunto de rutas tal que minimice el costo o la distancia total recorrida.
[pic 19] | (1) |
- Restricciones
Las restricciones (2) y (3) establecen que los clientes deben ser visitados exactamente una vez.
[pic 20] | (2) |
[pic 21] | (3) |
Las restricciones (4) y (5) reemplazan la restricción de subtour y capacidad de vehículos, y son más eficientes que las hechas con la grande al implementarlas en Gurobi.[pic 22] | |
[pic 23] | (4) |
[pic 24] | (5) |
Las restricciones (6) y (7) representan la naturaleza de las variables de decisión.
[pic 25] | (6) |
[pic 26] | (7) |
2. Bin Packing Problem (BPP):
2.1 Conjuntos
Conjunto de ítems (indexado por )[pic 27][pic 28]
2.2 Parámetros
: Peso del ítem [pic 29][pic 30]
c: Peso máximo aceptado por cada contenedor.
: Cantidad máxima de contenedores a utilizar.[pic 31]
2.3 Variables de decisión
Igual a 1 si el ítem es asignado al contenedor ; cero de lo contrario. [pic 32][pic 33][pic 34]
Igual a 1 si el contenedor es usado; cero de lo contrario. [pic 35][pic 36]
2.4 Función objetivo
Minimizar el número de contenedores empacando todos los ítems [pic 37][pic 38]
[pic 39] | (1) |
2.5 Restricciones
La restricción (2) expresa que cada ítem debe estar en exactamente un contenedor .[pic 40][pic 41]
[pic 42] La restricción (3) señala que el peso total de los ítems en cada contenedor , no exceda el peso máximo de los contenedores usados.[pic 43][pic 44] | (2) |
[pic 45] | (3) |
La restricción (4) no es necesaria para obtener una solución óptima al problema, pero ayuda a que este sea más rápido resuelto a través de Gurobi. Esta restricción de relación entre variables señala que si un contenedor no es utilizado (), entonces no pueden ponerse ítems en él ().[pic 46][pic 47]
[pic 48] | (4) |
Las restricciones (5) y (6) representan la naturaleza de las variables de decisión.
[pic 49] | (5) |
[pic 50] | (6) |
3. Knapsack Problem:
3.1 Conjuntos
Conjunto de productos o paquetes a seleccionar para colocar en la mochila.[pic 51]
3.2 Parámetros
: Beneficio asociado al incorporar el producto en la mochila, .[pic 52][pic 53][pic 54]
: Peso del producto , .[pic 55][pic 56][pic 57]
Capacidad de la mochila.[pic 58]
3.3 Variables de decisión
Igual a 1 si decidimos incluir el objeto en la mochila, cero de lo contrario, .[pic 59][pic 60][pic 61]
3.4 Función objetivo
Determinar qué objetos debo seleccionar para incluir en la mochila, de tal manera de maximizar el beneficio total de los objetos cargados.
...