CAPÍTULO 9

Programación lineal entera

Aplicación de la vida real. Optimización de las cargas de camiones de remolque

en PFG Building Glass
PFG utiliza camiones de remolque (de quinta rueda) especialmente equipados para
entregar paquetes de hojas de vidrio plano a clientes. Los paquetes varían tanto en ta-
maño como en peso, una carga puede incluir diferentes paquetes, según los pedidos re-
cibidos. Los reglamentos gubernamentales limitan los pesos sobre los ejes y la coloca-
ción de los paquetes en el remolque es crucial para determinar estos pesos. El
problema tiene que ver con la determinación de la carga óptima de los paquetes sobre
la cama del camión para satisfacer los límites de peso sobre los ejes. El problema se re-
suelve como un programa entero. El caso 7 del capítulo 26 en el sitio web proporciona
los detalles del estudio.

9.1 APLICACIONES ILUSTRATIVAS

Por lo general, las aplicaciones de programación lineal entera (PLE) caen dentro de
dos categorías: directa y transformada. En la categoría directa, la naturaleza de la situa-
ción impide la asignación de valores fraccionarios a las variables del modelo. Por ejem-
plo, el problema puede implicar la determinación de si se emprende o no un proyecto
(variable binaria), o la determinación del número óptimo de máquinas necesarias para
realizar una tarea (variable general entera). En la categoría transformada se utilizan
variables enteras auxiliares para convertir analíticamente situaciones insolubles en
modelos que pueden resolverse por medio de algoritmos de optimización disponibles.
Por ejemplo, en la secuencia de dos trabajos, A y B, en una sola máquina, el trabajo A
puede preceder al trabajo B o viceversa. La naturaleza “o” de las restricciones es lo
que hace al problema analíticamente insoluble, porque todos los algoritmos de progra-
mación matemáticos tratan con sólo restricciones “y”. La sección 9.1.4 muestra cómo
se utilizan las variables binarias auxiliares para transformar las restricciones “o” en
“y”, sin modificar la naturaleza del modelo.

315

www.FreeLibros.com
316 Capítulo 9 Programación lineal entera

Por comodidad, un problema se define como programa entero puro cuando todas
las variables son enteras. En caso contrario, es un programa entero combinado (PEC)
que implica una combinación de variables enteras y continuas.

9.1.1 Presupuesto de capital

La toma de decisiones de emprender o no un proyecto suele hacerse conforme a con-
sideraciones y prioridades preestablecidas de presupuesto limitado. El siguiente ejem-
plo presenta una de estas situaciones.

Ejemplo 9.1-1 (Selección de un proyecto)

Se están evaluando cinco proyectos a lo largo de un horizonte de planeación de 3 años. La si-
guiente tabla presenta los rendimientos esperados y los gastos anuales que conllevan.

Gastos ($ millones)/año

Proyecto 1 2 3 Rendimientos ($ millones)

1 5 1 8 20
2 4 7 10 40
3 3 9 2 20
4 7 4 1 15
5 8 6 10 30
Fondos disponibles ($ millones) 25 25 25

¿Cuáles proyectos deben seleccionarse a lo largo del periodo de 3 años?

El problema se reduce a una decisión “sí-no” para cada proyecto. Defina la variable binaria
xj como
xj = e
1, si se selecciona el proyecto j
0, si no se selecciona el proyecto j
El modelo de PLE es
Maximizar z = 20x1 + 40x2 + 20x3 + 15x4 + 30x5
Sujeto a
5x1 + 4x2 + 3x3 + 7x4 + 8x5 … 25
x1 + 7x2 + 9x3 + 4x4 + 6x5 … 25
8x1 + 10x2 + 2x3 + x4 + 10x5 … 25
x1, x2, x3, x4, x5 = (0, 1)
La solución óptima entera (obtenida con AMPL, Solver, o TORA)1 es x1 5 x2 5 x3 5 x4 5 1,
x5 5 0, con z 5 95 ($ millones). La solución excluye el proyecto 5 de la combinación de proyectos.

1
Para utilizar TORA, seleccione el menú Integer Programming de la barra de menús Main. Después de in-
gresar los datos del problema, diríjase a la pantalla de resultados, y seleccione Automated B&B para obte-
ner la solución óptima. Solver se utiliza igual que en la PL, sólo que las variables deben declararse enteras.
La opción entera (int o bin) está disponible en el cuadro de diálogo Solver Parameters cuando agrega una
nueva restricción. La implementación de AMPL para programación entera es la misma que en la PL, ex-
cepto que algunas o todas las variables se declaran enteras agregando la palabra clave integer (o binary)
en la instrucción de definición de las variables. Por ejemplo, la instrucción var x {J}>= 0, integer; decla-
ra a xj como entera no negativa para todas las j e J. Si xj es binaria, la instrucción se cambia a var x{J}>=0,
binary;. Para su ejecución, la instrucción option solver cplex; debe preceder a solve;.

www.FreeLibros.com
 9.1 Aplicaciones ilustrativas 317

Comentarios. Es interesante comparar la solución de PL continua con la solución del PLE. La

solución óptima de PL, obtenida reemplazando xj 5 (0,1) con 0 # xj # 1 para todas las j, da por
resultado x1 5 .5789, x2 5 x3 5 x4 5 1, x5 5 .7368, y z 5 108.68 ($ millones). La solución no tiene
sentido porque la x1 y x5 binarias asumen valores fraccionarios. Podemos redondear la solución
al entero más cercano, lo que da x1 5 x5 5 1. Sin embargo, la solución resultante infringe las res-
tricciones. Además, el concepto de redondeo carece de sentido en este caso porque xj representa
una decisión “sí-no”.

CONJUNTO DE PROBLEMAS 9.1A2

1. Modifique y resuelva el modelo de presupuesto de capital del ejemplo 9.1-1 para tener
en cuenta las siguientes restricciones adicionales:
(a) Debe seleccionarse el proyecto 5 ya sea que se seleccionen el proyecto 1 o el proyecto 3.
(b) Los proyectos 2 y 3 son mutuamente excluyentes.
2. Se van a cargar cinco artículos en un buque. A continuación se tabulan el peso wi, el vo-
lumen vi y el valor ri del artículo i.

Artículo i Peso unitario, wi (toneladas) Volumen unitario, vi (yd3) Valor unitario, ri ($100)

1 5 1 4
2 8 8 7
3 3 6 6
4 2 5 5
5 7 4 4

El peso y el volumen de la carga máximos permisibles son de 112 toneladas y 109

yd3, respectivamente. Formule el modelo de programación lineal entera, y determine la
carga más valiosa.
*3. 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 res-
tricciones del PLE, y halle una solución. (Sugerencia: Use una función objetivo ficticia en
la que todos los coeficientes objetivo sean ceros.).
4. Un excéntrico jeque dejó testamento para distribuir un rebaño de camellos entre sus tres
hijos: Tarek recibe la mitad del rebaño, Sharif obtiene una tercera parte y Maisa recibe
un noveno. El resto se destina a la caridad. El testamento no específica el tamaño del re-
baño, sólo dice que es un número impar de camellos y que la institución de caridad nom-
brada recibe exactamente un camello. Use la PLE para determinar cuántos camellos dejó
el jeque en el testamento y cuántos obtiene cada hijo.
5. Una pareja de granjeros envía a sus tres hijos al mercado para que vendan 90 manzanas;
Karen, la mayor, lleva 50 manzanas; Bill el de en medio, lleva 30; y John, el más joven,
lleva sólo 10. Los padres han estipulado cinco reglas: (a) el precio de venta es de $1 por
7 manzanas o $3 por 1 manzana; o una combinación de los dos precios. (b) Cada hijo
puede ejercer una o ambas opciones del precio de venta. (c) Cada uno debe regresar con
exactamente la misma cantidad de dinero. (d) El ingreso de cada hijo debe ser de dólares
enteros (no se permiten centavos). (e) La cantidad recibida por cada hijo debe ser la má-
xima posible según las condiciones estipuladas. Dado que los tres hijos son capaces de

2
Los problemas 3 a 6 son una adaptación de Malba Tahan, El Hombre que Calculaba, Editorial Limusa,
México, DF, págs. 39-182, 1994. Los problemas 13 a 16 son una adaptación de acertijos compilados en http:
www.chlond.demon.co.uk/puzzles/puzzles1.html. Desde luego sin tomar en cuenta las letras compuestas CD
y LL. (N. del T).

www.FreeLibros.com
318 Capítulo 9 Programación lineal entera

vender todo lo que llevan, use la PLE para mostrar cómo se pueden satisfacer las condi-
ciones de sus padres.
*6. Un capitán de un barco mercante deseaba recompensar a tres miembros de la tripulación
por su valiente esfuerzo al salvar la carga del barco durante una inesperada tormenta en
alta mar. El capitán apartó una suma de dinero en la oficina del sobrecargo e instruyó al
primer oficial para que la distribuyera en partes iguales entre los tres marineros después
de que el barco atracara. Una noche, uno de los marineros, sin que los otros supieran, se
dirigió a la oficina del sobrecargo y decidió reclamar un tercio (equitativo) del dinero de
forma anticipada. Después de que dividió el dinero en tres partes iguales sobró una mo-
neda, la que el marinero decidió conservar (además de un tercio del dinero). La noche si-
guiente, el segundo marinero tuvo la misma idea y repitió la misma división en tres partes
con lo que quedó, y terminó quedándose con una moneda extra. La tercera noche el ter-
cer marinero también tomó un tercera parte de lo que quedaba, más una moneda extra
que no podía dividirse. Cuando el barco arribó, el primer oficial dividió lo que restaba del
dinero en partes iguales entre los tres marineros, quedando de nuevo una moneda extra.
Para simplificar las cosas, el primer oficial apartó la moneda extra y les dio a los marine-
ros sus partes iguales asignadas. ¿Cuánto dinero había en la caja fuerte al inicio? Formule
el problema como una PLE, y halle la solución. (Sugerencia: El problema tiene una infini-
tud de soluciones enteras. Por comodidad, supongamos que nos interesa determinar la
suma mínima de dinero que satisfaga las condiciones del problema. Luego, aumente uno
a la suma resultante, y agréguelo como cota inferior para obtener la siguiente suma míni-
ma. Continuando de esta manera, emergerá un patrón de solución general.)
7. Weber (1990). 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 5 1 y terminando con Z 5 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 1 6 1 20 5 27. 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:

a b 6 a b 6 a b
suma de las calificaciones suma de las calificaciones suma de las calificaciones
de la letra 1 de la letra 2 de la letra 3
Formule el problema como una PLE y halle la solución óptima.
8. Resuelva el problema 7 dado que, además de que la suma total es la máxima, la suma de la
columna 1 y la suma de la columna 2 también serán las máximas. Halle la solución óptima.
9. Weber (1990). Considere los siguientes grupos de palabras:

Grupo 1 Grupo 2

AREA ERST
FORT FOOT
HOPE HEAT
SPAR PAST
THAT PROF
TREE STOP

Todas las palabras en los grupos 1 y 2 pueden formarse con las nueve letras A, E. F, H, O,
P, R, S y T. Desarrolle un modelo para asignar un valor numérico único del 1 al 9 a estas
letras, de modo que la diferencia entre las calificaciones totales de los dos grupos será lo
más pequeña posible. Nota: La calificación para una palabra es la suma de los valores
numéricos asignados a sus letras individuales.

www.FreeLibros.com
 9.1 Aplicaciones ilustrativas 319

*10. La compañía Record-a-Song contrató a una estrella en ascenso para que grabe ocho can-
ciones. Los tamaños en MB de las diferentes canciones son de 8, 3, 5, 5, 9, 6 y 12, respecti-
vamente. Record-a-Song utiliza dos CD para la grabación. La capacidad de cada CD es
de 30 MB. A la compañía le gustaría distribuir las canciones en los dos CD de modo que
el espacio utilizado en cada uno sea aproximadamente el mismo. Formule el problema
como una programación lineal entera y determine la solución óptima.
11. En el problema 10, suponga que la naturaleza de las melodías dicta que las canciones 3 y
4 no pueden grabarse en el mismo CD. Formule el problema como una PLE. ¿Sería posi-
ble utilizar un CD de 25 MB para grabar las ocho canciones? Si no, utilice la PLE para
determinar la capacidad mínima del CD para realizar la grabación.
*12. Graves and Asoociates (1993). La Universidad de Ulern utiliza un modelo matemático
que optimiza las preferencias de los estudiantes tomando en cuenta la limitación del
salón de clases y el profesorado. Para demostrar la aplicación del modelo, considere el
caso simplificado de 10 estudiantes a los que se les pidió que seleccionaran dos cursos de
entre seis ofrecidos. La tabla siguiente muestra las calificaciones que representan la pre-
ferencia de cada estudiante por los cursos individuales, con 100 como la calificación más
alta. Para simplificar, se supone que la calificación de la preferencia de una selección de
dos cursos es la suma de las calificaciones individuales. La capacidad del curso es el nú-
mero máximo de estudiantes que pueden tomar la clase.

Calificación de preferencia por curso

Estudiante 1 2 3 4 5 6

1 20 40 50 30 90 100
2 90 100 80 70 10 40
3 25 40 30 80 95 90
4 80 50 60 80 30 40
5 75 60 90 100 50 40
6 60 40 90 10 80 80
7 45 40 70 60 55 60
8 30 100 40 70 90 55
9 80 60 100 70 65 80
10 40 60 80 100 90 10
Capacidad del curso 6 8 5 5 6 5

Formule el problema como una PLE y halle la solución óptima.

13. Tiene tres denominaciones de moneda con 11 monedas de cada una. El valor total (de las
11 monedas) es de 15 bits para la denominación 1, 16 para la denominación 2, y 17 bits
para la 3. Usted necesita comprar un artículo de 11 bits. Use la PLE para determinar la
cantidad mínima de monedas de las tres denominaciones que se requiere para realizar
la compra.
14. Tiene un tablero de 4 3 4 casillas y un total de 10 fichas. Use la PLE para colocar las fichas
en el tablero de modo que cada fila y cada columna tengan un número par de fichas.
15. A un vendedor callejero que vende aparatos electrónicos le robaron toda su mercancía.
Cuando denunció el hecho a la policía, el vendedor no supo decir cuántos aparatos que
tenía pero declaró que cuando dividía el total en lotes de 2, 3, 4, 5 o 6, siempre sobraba un
aparato. Por otra parte, no sobraba ninguno cuando el total se dividía en lotes de 7. Use
PLE para determinar el total de aparatos que el vendedor tenía.
16. Dado que i 5 1, 2,…, n, formule un modelo de PLE (para cualquier n) para determinar el
número mínimo y que, cuando se divide entre la cantidad entera 2 1 i, siempre producirá
un remanente igual a i; es decir, y mod (2 1 i) 5 i.

www.FreeLibros.com
320 Capítulo 9 Programación lineal entera

17. Un acertijo muy conocido requiere que se asigne un solo dígito distinto (del 0 al 9) a cada
letra de la ecuación SEND 1 MORE 5 MONEY. Formule el problema como un progra-
ma entero y halle la solución. (Sugerencia: Éste es un modelo de asignación con condicio-
nes colaterales.)
18. El acertijo lógico japonés mundialmente conocido, Sudoku, se compone de una cuadrícu-
la de 9 3 9 subdividida en 9 subcuadrículas de 3 3 3 que no se traslapan. El acertijo con-
siste en asignar los dígitos numéricos del 1 al 9 a las celdas de la cuadrícula de modo que
cada fila, cada columna y cada subcuadrícula, contenga dígitos distintos. Algunas de las
celdas pueden fijarse con anticipación.
Formule el problema como un programa entero, y halle la solución para el caso
dado a continuación.

6 1 4 5

8 3 5 6

2 7

8 4 7 6

6 3

7 9 1 4

5 2

7 2 6 9

4 5 8 7

[Sugerencia: sea xijk 5 1 si se coloca el dígito k en la celda (i,j), i,j,k 5 1, 2,…,n, n 5 9. Si uti-
liza AMPL, tenga en cuenta que con n 5 9, la cantidad de variables que resulte excederá la
capacidad de la versión estudiantil de AMPL. Si no tiene acceso a la versión completa de
AMPL, puede desarrollar un modelo general para n 5 4 o 9, y luego resolverlos para el
caso más sencillo (casi trivial) de una cuadrícula de 4 3 4 con una subcuadrícula de 2 3 2.

9.1.2 Problema de cobertura de conjunto

En esta clase de problemas, varias plantas ofrecen servicios que se traslapan a varias insta-
laciones. El objetivo es determinar la cantidad mínima de plantas que cubren (es decir, que
satisfacen las necesidades de servicio de) cada instalación. Por ejemplo, se pueden construir
plantas de tratamiento de agua en varios lugares, y cada planta sirve a un grupo de ciuda-
des. El traslape ocurre cuando a una ciudad dada le da servicio más de una planta.

Ejemplo 9.1-2 (Instalación de teléfonos de seguridad)

Para promover la seguridad en el campus el Departamento de Seguridad Pública de la Universidad
de Arkansas se encuentra en proceso de instalación de teléfonos de emergencia en lugares seleccio-
nados. El departamento desea instalar una cantidad mínima de estos aparatos que presten servicio
a cada una las calles principales del campus. La figura 9.1 es un mapa de dichas calles.
Es lógico maximizar la utilidad de los teléfonos si se les coloca en intersecciones de calles.
De este modo, una sola unidad puede prestar servicio al menos a dos calles.
Defina

xj = e
1, se instala un teléfono en el lugar j, j = 1, 2, . . . , 8
0, en caso contrario

www.FreeLibros.com
 9.1 Aplicaciones ilustrativas 321

Calle A 2 Calle B
1 3

Calle K
Calle I
Calle G

F
Calle C

lle
Ca
4 5

Calle J
Calle H
Calle E Calle D

6 7 8

FIGURA 9.1
Mapa de las calles del campus de la Universidad de Arkansas

Las restricciones del problema requieren que se instale al menos un teléfono en cada una de las
11 calles (A a K). Por lo tanto, el modelo es

Minimizar z = x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8

Sujeto a
x1 + x2 Ú 1 (Calle A)
x2 + x3 Ú 1 (Calle B)
x4 + x5 Ú 1 (Calle C)
x7 + x8 Ú 1 (Calle D)
x6 + x7 Ú 1 (Calle E)
x2 + x6 Ú 1 (Calle F)
x1 + x6 Ú 1 (Calle G)
x4 + x7 Ú 1 (Calle H)
x2 + x4 Ú 1 (Calle I)
x5 + x8 Ú 1 (Calle J)
x3 + x5 Ú 1 (Calle K)
xj = (0, 1), j = 1, 2, . . . , 8
La solución óptima del problema requiere que se instalen cuatro teléfonos en las intersecciones
1, 2, 5 y 7.

Comentarios. En el sentido estricto, los problemas de cobertura se caracterizan por los si-
guientes criterios: (1) Las variables xj, j 5 1, 2,…,n son binarias; (2) los coeficientes del lado iz-

www.FreeLibros.com
322 Capítulo 9 Programación lineal entera

quierdo de las restricciones son 0 o 1; (3) el lado derecho de cada restricción es de la forma ($1),
y (4) la función objetivo minimiza c1x1 1 c2x2 1 … 1 cnxn, donde cj . 0 para toda j 5 1, 2,...,n.
En este ejemplo, cj 5 1 para todas las j. Si cj representa el costo de instalación en la intersección
j, entonces estos coeficientes pueden asumir valores diferentes de 1. Las variaciones del proble-
ma de cobertura incluyen condiciones colaterales adicionales, como se describe por medio de al-
gunas de las situaciones descritas en los problemas del conjunto 9.1b.

Momento de AMPL
El archivo amplEx9.1-2.txt proporciona un modelo general para cualquier problema de cobertu-
ra. La formulación se detalla en la sección C.9 en el sitio web.

CONJUNTO DE PROBLEMAS 9.1B

*1. ABC es una compañía de transporte de menos de una carga de camión que entrega cargas
a diario a cinco clientes. La siguiente lista proporciona los clientes asociados con cada ruta:

Ruta Clientes atendidos en la ruta

1 1, 2, 3, 4
2 4, 3, 5
3 1, 2, 5
4 2, 3, 5
5 1, 4, 2
6 1, 3, 5

Los segmentos de cada ruta dependen de la capacidad del camión que entrega las
cargas. Por ejemplo, en la ruta 1, la capacidad del camión es suficiente para entregar las
cargas a los clientes, 1, 2, 3 y 4 únicamente. La siguiente tabla enlista las distancias (en mi-
llas) entre la terminal de los camiones (ABC) y los clientes.

Millas de i a j

j ABC 1 2 3 4 5
i

ABC 0 10 12 16 9 8
1 10 0 32 8 17 10
2 12 32 0 14 21 20
3 16 8 14 0 15 18
4 9 17 21 15 0 11
5 8 10 20 18 11 0

El objetivo es determinar la distancia mínima necesaria para realizar las entregas

diarias a los cinco clientes. Aun cuando la solución puede dar por resultado que un clien-
te sea atendido por más de una ruta, la fase de implementación utilizará sólo una de esas
rutas. Formule el problema como un PLE, y halle la solución óptima.
*2. La Universidad de Arkansas va a formar un comité para atender las quejas de los estu-
diantes. La administración desea que el comité incluya al menos una mujer, un hombre,
un estudiante, un administrador y un profesor. Diez personas (identificadas, por simplici-

www.FreeLibros.com
 9.1 Aplicaciones ilustrativas 323

dad, con las letras de la a a la j) han sido nominadas, y se les ha combinado en las distin-
tas categorías siguientes:

Categoría Personas

Mujeres a, b, c, d, e
Hombres f, g, h, i, j
Estudiantes a, b, c, j
Administradores e, f
Profesores d, g, h, i

La Universidad de Arkansas desea formar el menor comité con la representación

de cada una de las cinco categorías. Formule el problema como un PLE, y halle la solu-
ción óptima.
3. El condado de Washington incluye seis poblaciones que necesitan el servicio de ambulan-
cias 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 si-
guiente tabla muestra los tiempos de manejo en minutos entre las seis poblaciones.

Tiempos en minutos de i a j

j 1 2 3 4 5 6
i

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 PLE cuya solución produzca el número mínimo de estaciones y sus

ubicaciones. Determine la solución óptima.
4. Los inmensos tesoros del Rey Tut están en exhibición en el Museo de Giza en El Cairo.
La distribución del museo se muestra en la figura 9.2 con las diferentes salas comunica-
das por puertas abiertas. Un guardia de pie en una puerta puede vigilar dos salas adya-
centes. La política de seguridad del museo requiere la presencia de un guardia en cada
sala. Formule el problema como un PLE para determinar el mínimo de guardias.

FIGURA 9.2
Distribución del museo del problema 4,
conjunto 9.1c

www.FreeLibros.com
324 Capítulo 9 Programación lineal entera

5. Bill acaba de terminar sus exámenes del año académico y desea celebrar viendo todas las
películas que se están exhibiendo en cines de su ciudad y otras ciudades vecinas. Si viaja a
otra ciudad, se quedará allí hasta que vea todas las películas que desea. La siguiente tabla in-
forma sobre las ofertas de películas y las distancias de viaje redondo a las ciudades vecinas.

Localización Ofertas de Millas de Costo por

del cine películas viaje redondo película ($)

En su ciudad 1, 3 0 7.95
Ciudad A 1, 6, 8 25 5.50
Ciudad B 2, 5, 7 30 5.00
Ciudad C 1, 8, 9 28 7.00
Ciudad D 2, 4, 7 40 4.95
Ciudad E 1, 3, 5, 10 35 5.25
Ciudad F 4, 5, 6, 9 32 6.75

El costo de conducir es de 75 centavos por milla. Bill desea determinar las ciudades
que necesita visitar para ver todas las películas, al mismo tiempo que minimiza su costo total.
6. Las tiendas Walmark están en proceso de expansión en el oeste de Estados Unidos.
Walmark planea construir durante el próximo año nuevas tiendas que prestarán servicio
a 10 comunidades geográficamente dispersas. La experiencia pasada indica que una co-
munidad debe estar a una distancia máxima de 25 millas de una tienda para atraer clien-
tes. Además, la población de una comunidad desempeña un rol importante en la ubica-
ción de una tienda, en el sentido que las comunidades grandes generan más clientes
participantes. La siguiente tabla proporciona las poblaciones y también las distancias (en
millas) entre las comunidades.

Millas de la comunidad i a la comunidad j

j 1 2 3 4 5 6 7 8 9 10 Población
i

1 20 40 35 17 24 50 58 33 12 10,000
2 20 23 68 40 30 20 19 70 40 15,000
3 40 23 36 70 22 45 30 21 80 28,000
4 35 68 36 70 80 24 20 40 10 30,000
5 17 40 70 70 23 70 40 13 40 40,000
6 24 30 22 80 23 12 14 50 50 30,000
7 50 20 45 24 70 12 26 40 30 20,000
8 58 19 30 20 40 14 26 20 50 15,000
9 33 70 21 40 13 50 40 20 22 60,000
10 12 40 80 10 40 50 30 50 22 12,000

La idea es construir el menor número de tiendas, teniendo en cuenta la restricción

de la distancia y la concentración de las poblaciones.
Especifique las comunidades donde deben ubicarse las tiendas.
*7. Guéret and Associates (2002). Sección 12.6. El presupuesto de MobileCo para construir 7
transmisores que cubran la mayor población posible en 15 comunidades geográficas con-

www.FreeLibros.com
 9.1 Aplicaciones ilustrativas 325

tiguas, es de 15 millones de dólares. A continuación se presentan las comunidades cubier-

tas por cada transmisor y los costos de construcción presupuestados.

Transmisor Comunidades cubiertas Costo (millones de $)

1 1, 2 3.60
2 2, 3, 5 2.30
3 1, 7, 9, 10 4.10
4 4, 6, 8, 9 3.15
5 6, 7, 9, 11 2.80
6 5, 7, 10, 12, 14 2.65
7 12, 13, 14, 15 3.10

La siguiente tabla proporciona las poblaciones de las diferentes comunidades:

Comunidad 1 2 3 4 5 6 7 8 9 10

Población (en miles) 10 15 28 30 40 30 20 15 60 12

¿Cuáles de los transmisores propuestos deben construirse?

8. Gavermini and Associates (2004). Las redes eléctricas modernas utilizan medidores eléc-
tricos automáticos en lugar de los más costosos medidores manuales. En el sistema au-
tomático, los medidores de varios clientes se enlazan inalámbricamente a un solo recep-
tor. El medidor envía señales cada mes a un receptor designado para reportar el
consumo de electricidad del cliente. Luego los datos se canalizan a una computadora cen-
tral para generar los recibos. El objetivo es determinar el mínimo de receptores necesa-
rios para atender a un número dado de medidores. En la vida real, el problema compren-
de miles de medidores y receptores. Este problema emplea 10 medidores y 8 posibles
localizaciones para los receptores, con las siguientes configuraciones:

Receptor 1 2 3 4 5 6 7 8

Medidores 1, 2, 3 2, 3, 9 5, 6, 7 7, 9, 10 3, 6, 8 1, 4, 7, 9 4, 5, 9 1, 4, 8

9. Resuelva el problema 8 si, además, cada receptor puede manejar cuando mucho 3 medi-
dores.

9.1.3 Problema de cargo fijo

El problema de cargo fijo tiene que ver con situaciones en que la actividad económica
incurre en dos tipos de costos: un costo fijo necesario para iniciar la actividad y un
costo variable proporcional al nivel de la actividad. Por ejemplo, el herramental inicial
de una máquina antes de iniciar la producción incurre en un costo de preparación fijo
independientemente de cuántas unidades se fabriquen. Una vez completa la prepara-
ción de la máquina, el costo de la mano de obra y del material es proporcional a la can-
tidad producida. Dado que F es el cargo fijo, c es el costo unitario variable, y x es el
nivel de producción, la función de costo se expresa como

C1x2 = e
F + cx, si x 7 0
0, en caso contrario

www.FreeLibros.com