–
I. Formulación de problemas de programación entera mixta y uso de variables binarias.
1. Una universidad se encuentra en un proceso de formar una comisión. Diez personas han sido nominadas:
Ana, Beatriz, Camila, Daniela, Elena, Felipe, Guillermo, Hernán, Ignacio y Jaime. El reglamento obliga a que sean
incluidos en dicha comisión al menos una mujer, un hombre, un estudiante, un administrativo y un profesor.
Además, el número de mujeres debe ser igual que el de hombres y el número de profesores no debe de ser
inferior al de administrativos. Ana, Beatriz, Camila y Jaime son estudiantes, Elena y Felipe son administrativos y
Daniela, Guillermo, Hernán e Ignacio son profesores
Formule el problema usando programación entera, de modo que cumpla con las restricciones y buscando que
la comisión sea lo más reducida posible
2. Ford tiene cuatro plantas para fabricar automóviles. En cada una es posible producir el Taurus, Lincoln o el
Escort, pero sólo es posible fabricar uno de ellos. El costo fijo por operar cada planta por un año y los costos
variables por producir un automóvil de cada tipo se proporcionan:
Planta Costo Fijo (dólares)
Costo variable (dólares)
Taurus Lincoln Escort
1 7000 millones 12.000 16.000 9.000 2 6000 millones 15.000 18.000 11.000 3 4000 millones 17.000 19.000 12.000 4 2000 millones 19.000 22.000 14.000
Ford se enfrenta a las restricciones siguientes:
a) Se puede producir sólo un tipo de automóvil en cada planta.
b) La producción total de cada tipo de automóvil tiene que ser en una sola planta; es decir, si se fabrican
algunos Taurus en la planta 1, entonces todos los Taurus se tienen que hacer ahí.
c) Si se usan las plantas 3 y 4, la planta 1 se debe utilizar también.
Ford tiene que producir todos los años 500.000 unidades de cada tipo de automóvil. Formule un Problema de
programación Entera cuya solución le indique a Ford cómo minimizar el costo anual en la producción de
automóviles.
3. Una minera explota dos minas para obtener mineral de hierro. Este mineral de hierro se envía a una de dos
instalaciones de almacenamiento. Cuando se necesita se manda a las plantas de acero de la compañía; la
compañía no puede sobrepasar las 80 ton de material almacenado. El siguiente diagrama describe la red de
distribución, donde M1, M2 y M3 son las dos minas, S1, S2 y S3, los dos almacenes y P1, P2, P3 son las plantas
procesamiento del mineral. También muestra las cantidades máximas producidas en las minas y las necesarias
en las plantas, al igual que el costo de envío y la cantidad máxima que se puede enviar al día por cada vía. Se
debe cumplir una cota mínima de envío desde las minas hacia los almacenes. Los datos se muestran en la
siguiente tabla.
Mina Almacén Ton mínima de material
1 1 10
2 10
2
1 15
2 15
3 12
3 2 12
3 12
La empresa no cuenta con una infraestructura vial entre la mina M1 y el almacén S3, la mina M3 y el almacén
S1; tampoco hay vías de acceso entre el almacén S3 y la planta P1, ni entre el almacén S1 y la planta P3.
Además, se incurre en un costo muy alto si se envía simultáneamente material desde la mina M3 al almacén S2
y de la mina M1 al almacén S2, también si se envía material desde el almacén S2 a las plantas P1 y P3 en
simultánea; por lo que la administración quiere eliminar estos costos. La administración desea determinar el
plan más económico de envío del mineral de las minas a las plantas.
Formule el anterior problema usando programación entera mixta
4. Un Municipio desea abrir unos puestos de salud en dos años. Se han definido 5 posibles localizaciones i, las
cuales atenderían la demanda de las 5 zonas j, según las siguientes condiciones:
A cada zona de demanda j le corresponde una población demandante del servicio hj
La construcción de cada puesto de salud implica un costo fijo de construcción cfi, y un costo variable cvi
por cada habitante en el año que atenderían.
Cada puesto de salud tiene una capacidad máxima de número de habitantes que podría atender
anualmente Cqi
Si un puesto de salud se abre en el año 1, puede atender tanto ese año como el año siguiente (es decir
que la población atendida cuenta los dos años)
Cada año se cuenta con un presupuesto máximo Pt.
Se desea elegir cuáles puestos de salud abrir en cada año y determinar cuántos pacientes se atienden en la
zona j por el puesto de salud ubicado en i, en el año t, de modo que se maximice la población atendida.
5. Las reglas del Sudoku son simples: hay que llenar la matriz de forma que cada fila, cada columna y cada
submatriz de 3X3 contenga los números del 1 al 9 exactamente una vez. El problema del Sudoku es tan
restringido que es posible hallar la solución del sudoku usando programación entera mixta (específicamente
usando variables binarias), sin necesidad de una función objetivo específica.
Formule las variables de decisión y las restricciones necesarias para resolver este sudoku. ¿Cuántas variables
son necesarias?, ¿cuántas restricciones?
II. Solución de problemas enteros por ramificación y acotamiento
6. Resuelva mediante el método de ramificación y acotamiento los siguientes problemas de programación
entera. Para cada ejercicio indique si la solución del problema relajado de progamación lineal es factible para el
problema de programación entera, realice el árbol de ramificación y acotamiento e indique por cuál variable
hizo la ramificación.
Max Z = 13X1 + 8X2
S.A X1 + 2X2 ≤ 10
5X1 + 2X2 ≤20
X1, x2 ≥0,
X1, X2 enteros
Max Z = 2X1 + X2
S.A: 5X1 + 2X2 ≤ 8
X1 + X2 ≤ 3
X1, x2 ≥0,
X1 entera, X2 real
Max Z = X1 - 3X2
S.A: -X1 + 2X2 ≤ 6
X1 + X2 ≤ 5
X1 - 7X2 ≤ 2
X1, x2 ≥0, X1, X2 enteros
III. Problemas de redes
7. Logis S.A mueve mercancía desde 6 plantas a 8 mercados. Los costos de transporte de la mercancía entre
planta y mercado (cij) dependen de la distancia recorrida (dij) y de la cantidad de toneladas que se transportan
(xij). La capacidad de producción en cada planta está dada por un vector Ofertai, cada planta puede enviar
como máximo su capacidad de producción. La demanda de cada mercado está dada por un vector Demandaj,
2
2 5
7 3 4
2 1 3 4
6 4 8 5 9
9 5 2 1
3 4 8
9 1
1
se espera que a cada mercado llegue al menos la cantidad demandada de mercancía. La empresa desea
minimizar los costos de transporte, de modo que se cumpla con las restricciones de oferta y demanda.
Formule el problema y resuelva usando el Solver de Excel.
Distancia en km (dij) Mercados (j) Oferta en Ton
(Ofertai) m1 m2 m3 m4 m5 m6 m7 m8
Pla
nta
s (i
)
p1 84 28 91 29 83 44 87 28 500
p2 85 87 20 30 97 24 71 62 450
p3 42 79 25 65 12 16 60 43 350
p4 44 55 63 36 73 25 18 43 600
p5 31 25 68 36 18 78 39 56 400
p6 90 54 42 28 84 99 96 41 500
Demanda en Ton (Demandaj) 350 300 400 200 400 400 400 350
Ahora suponga que llega un nuevo gerente a la empresa y decide que sólo enviará mercancía de una planta a
un mercado si y sólo si la cantidad que es transportada en ese trayecto es mayor o igual a 200 toneladas.
Formule nuevamente el problema teniendo en cuenta esta nueva restricción y resuelva nuevamente usando el
Solver de Excel. Compare los resultados.
8. Todos los problemas de red vistos en clase son casos especiales del problema de flujo de costo mínimo: al
igual que el problema de flujo máximo, éste considera flujos en las redes con capacidades, al igual que el
problema del camino más corto, éste considera un costo por flujo hacia un arco, al igual que el problema de
transporte, éste permite múltiples orígenes y destinos. Por lo tanto, todos estos problemas pueden ser vistos
como casos especiales del problema de flujo de costos mínimo. El problema es minimizar el costo total sujeto a
la disponibilidad y la demanda de algunos nodos, y de la conexión superior de flujo a través de cada arco.
Formule el problema de flujo de costo mínimo para la siguiente red, donde cada par ordenado en las aristas
corresponde a (costo, capacidad):
Recommended