| Artículo | Peso unitario, w_i (toneladas) | Volumen unitario, v_i (yd^3) | Valor unitario, r_i ($100) |
|---|---|---|---|
| 1 | 5 | 1 | 4 |
| 2 | 8 | 8 | 7 |
| 3 | 3 | 6 | 6 |
| 4 | 2 | 5 | 5 |
| 5 | 7 | 4 | 4 |
Optimización Discreta 2024-10
Universidad Pontificia Bolivariana
Resumen
En este documento se encuentran los enunciados de algunos de los ejemplos y ejercicios que se realizarán en clase. El objetivo de esto es evitar tener que dictar o copiar largos enunciados durante las clases
Ejemplo 1 (Taha)
Se van a cargar cinco artículos en un buque. A continuación se tabulan el peso \(w_i\), el volumen \(v_i\) y el valor \(r_i\) de cada artículo.
El peso y el volumen de la carga máximos permisibles son de 16 toneladas y 15 \(yd^3\) , respectivamente. Formule el modelo de programación lineal entera que permita encontrar la carga más valiosa
Ejemplo 2 (Taha)
Supongamos que tenemos las siguientes palabras de tres letras: AFT, FAR, TVA, ADV, JOE, FIN, OSF y KEN. Supongamos que le asignamos valores numéricos al alfabeto comenzando con \(A = 1\) y terminando con \(Z = 27\). A cada palabra se le asigna una calificación sumando los códigos numéricos de sus tres letras. Por ejemplo, AFT tiene una calificación de \(1 + 6 + 21 = 28\). Debe seleccionar cinco de las ocho palabras dadas que den la calificación máxima total. Al mismo tiempo, las cinco palabras deben satisfacer las siguientes condiciones:
suma de las calificaciones de la letra 1 < suma de las calificaciones de la letra 2 < suma de las calificaciones de la letra 3
\[ \begin{pmatrix} \text{suma de las calificaciones} \\ \text{de la letra 1} \end{pmatrix} < \begin{pmatrix} \text{suma de las calificaciones} \\ \text{de la letra 2} \end{pmatrix} < \begin{pmatrix} \text{suma de las calificaciones} \\ \text{de la letra 3} \end{pmatrix} \]
Formule como un modelo de Programación Entera
Ejemplo 3 (Taha)
Suponga que tiene 7 botellas de vino llenas, 7 a la mitad y 7 vacías. Le gustaría dividir las 21 botellas entre tres individuos de modo que cada uno reciba exactamente 7. Además, cada individuo debe recibir la misma cantidad de vino. Exprese el problema como restricciones del PLE, y halle una solución. (Sugerencia: Use una función objetivo ficticia en la que todos los coeficientes objetivo sean ceros.).
Ejemplo 4 (Taha)
Tiene un tablero de 4x4 casillas y un total de 10 fichas. Use la PE para colocar las fichas en el tablero de modo que cada fila y cada columna tengan un número par de fichas.
Ejemplo 5 (Taha)
El condado de Washington incluye seis poblaciones que necesitan el servicio de ambulancias de emergencia. Debido a la proximidad de algunas poblaciones, una sola estación puede atender a más de una comunidad. La estipulación es que la estación debe estar como máximo a 15 minutos de tiempo de manejo de la población que atiende. La siguiente tabla muestra los tiempos de manejo en minutos entre las seis poblaciones.
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| 1 | 0 | 23 | 14 | 18 | 10 | 32 |
| 2 | 23 | 0 | 24 | 13 | 22 | 11 |
| 3 | 14 | 24 | 0 | 60 | 19 | 20 |
| 4 | 18 | 13 | 60 | 0 | 55 | 17 |
| 5 | 10 | 22 | 19 | 55 | 0 | 12 |
| 6 | 32 | 11 | 20 | 17 | 12 | 0 |
Formule un PE cuya solución produzca el número mínimo de estaciones y sus ubicaciones
Ejemplo 6 (Taha)
Un tablero de juego se compone de 3x3 casillas. Se requiere que coloque un número entre 1 y 9 en cada casilla de modo que la suma de los números en cada fila, cada columna y cada diagonal sea igual a 15. Además, los números en todas las casillas deben ser distintos. Use un PLE para determinar la asignación de números a las casillas.
Bibliografía
[1]
H. P. Williams, Model building in Mathematical Programming, 5th ed. John Wiley & Sons, 2013.
[2]
M. Arenales, V. Armentano, R. Morabito, y H. Yanasse, Pesquisa Operacional para cursos de Engenharia. elsevier, 2007.
[3]
F. S. Hillier y G. J. Lieberman, Introduction to Operations Research, 10th ed. McGrawHill, 2015.
[4]
H. A. Taha, Investigación de Operaciones, 9th ed. Pearson, 2012.
[5]
L. A. Wolsey, Integer Programming, 2th ed. John Wiley & Sons, 2020.
[6]
W. L. Winston, Operations Research: Applications and Algorithms. Thomson Learning, Inc., 2004.
[7]
Y. Pochet y L. A. Wolsey, Production Planning by Mixed Integer Programming, vol. 149. Springer, 2006.