Capı́tulo 1

Introducción

1.1. Objetivo asignatura: toma de decisiones en el ámbi-

to empresarial (optimización)
La asignatura tiene como objetivo la familiarización con la teorı́a de optimización.
Optimizar significa elegir la mejor alternativa lo que, desde la perspectiva de las ma-
temáticas, significa que esa elección se realiza maximizando o minimizando una función
en un conjunto de posibles alternativas, al que se denomina conjunto factible (o conjun-
to de oportunidades). Este primer capı́tulo introductorio nos servirá para entender estas
cuestiones y ser conscientes de la aplicabilidad de las técnicas matemáticas a través de
algunos ejemplos que nos ilustrarán qué significa optimizar. Este concepto se traducirá,
según el contexto, en:

minimizar costes

maximizar beneficios/ingresos/producción/...

maximizar eficiencia

minimizar residuos

maximizar la utilidad de un consumidor

minimizar los riesgos (laborales, de una inversión, ...)

...

1
CAP 1 MATEMÀTIQUES 2 ADE-MÀRQUETING curs 24-25

1.2. Restricciones: condiciones técnicas, legales, ... que

debe cumplir la solución
Casi todas las decisiones que deben tomarse están sujetas a restricciones. A veces
presupuestarias (no tengo tanto dinero como quisiera). A veces legales (no puedo cons-
truir mi nave industrial dónde quiera por la normativa urbanı́stica). A veces técnicas
(no es posible unir con un puente la isla de Mallorca con Barcelona). Ejemplos de res-
tricciones habituales en el ámbito económico/empresarial son:

minimizar costes para producir una determinada cantidad de output

maximizar la utilidad que puede obtener un consumidor que no puede gastar más
de lo que le permite su presupuesto

minimizar residuos sin disminuir la productividad

maximizar eficiencia sin aumentar la contaminación

minimizar el coste de conexión en una red de transmisión (de datos, agua, elec-
tricidad, . . . ) de modo que todos estén conectados

planificación óptima de la producción para cubrir una determinada demanda

ubicación óptima de un centro de distribución, o un centro comercial para atender

al máximo número de clientes

...

Por otro lado, las variables que aparecen en los mencionados problemas (precios, can-
tidades, . . . ) son normalmente no negativos por definición, lo que ya establece restric-
ciones en los valores que puede tomar la solución de un problema.

2 Begoña Subiza i Josep E. Peris. MQiTE. Universitat d’Alacant

CAP 1 MATEMÀTIQUES 2 ADE-MÀRQUETING curs 24-25

Vamos a empezar viendo un ejemplo tı́pico de aplicación de la teorı́a de optimización

matemática para resolver un problema real.

Ejemplo 1 El problema de la dieta: Este fue uno de los primeros problemas sobre optimi-
zación planteados formalmente, motivado por el deseo del ejército americano de asegurar
unos requerimientos nutricionales al menor coste posible. El problema fue planteado
en la década de 1930 y analizado y resuelto por George Stigler usando la programación
lineal en 1947. A continuación vemos una versión simplificada de este problema, aplicado
a alimentación animal.
Ejemplo: Una granja se enfrenta al siguiente problema para alimentación de sus animales:

existen dos compuestos alimenticios A, B, o marcas de alimentos, con precios unita-

rios pA , pB

hay dos tipos de nutrientes: tipo 1 (carbohidratos, proteı́nas y grasas, que proporcio-
nan energı́a), y tipo 2 (vitaminas y minerales, importantes para diversas funciones
fisiológicas) de los que se requieren al menos las cantidades q1 , q2 , respectivamente

cada compuesto alimenticio posee cantidades distintas de cada uno de los nutrientes:

• a11 : cantidad del nutriente tipo 1 que posee el compuesto A

• a12 : cantidad del nutriente tipo 2 que posee el compuesto A
• a21 : cantidad del nutriente tipo 1 que posee el compuesto B
• a22 : cantidad del nutriente tipo 2 que posee el compuesto B

objetivo: minimizar costes de alimentación, cumpliendo los requerimientos nutricio-

nales (al menos q1 , q2 del nutriente tipo 1 y 2, respectivamente)

¿cuántas unidades xA , xB de cada compuesto alimenticio se comprarán para cumplir

el objetivo?

El problema de optimización al que se enfrenta es, decidir las cantidades que se compran,
xA , xB , de los compuestos alimenticios para

Minimizar pA xA ` pB xB

Las restricciones (aparte de las obvias de no–negatividad, no se pueden comprar cantida-

des negativas de un producto) indican que los requerimientos de nutrientes se cumplen:

Con xA , xB unidades de los compuestos alimenticios se obtiene a11 xA ` a21 xB nu-

triente 1. Por tanto, la restricción es

a11 xA ` a21 xB • q1

Begoña Subiza i Josep E. Peris. MQiTE. Universitat d’Alacant 3

CAP 1 MATEMÀTIQUES 2 ADE-MÀRQUETING curs 24-25

Con xA , xB unidades de los compuestos alimenticios se obtiene a21 xA ` a22 xB nutriente 2.

Por tanto, la restricción es
a21 xA ` a22 xB • q2

Vamos a plantear el problema con los valores pA “ 2, pB “ 3, q1 “ 50, q2 “ 40, a11 “ 4,

a12 “ 2, a21 “ 3, a22 “ 4. El objetivo, si se compran xA , xB unidades de los compuestos
alimenticios es:
Minimizar 2xA ` 3xB
Las restricciones (aparte de las obvias de no–negatividad, no se pueden comprar cantida-
des negativas de un producto) indican que los requerimientos de nutrientes se cumplen:

4xA ` 3xB • 50 2xA ` 4xB • 40 xA • 0, xB • 0

Como solo hay dos variables, las anteriores condiciones (tomadas con igualdad) se corres-
ponden a rectas en el plano, que podemos dibujar, y nos da lugar al posible conjunto de
valores pxA , xB q que cumplen las restricciones. En este ejemplo, se tiene:

15

10

5 10 15 20
¿Se puede ver intuitivamente cuál será la solución?

La función de costes (que queremos minimizar) es C “ 2xA ` 3xB . Podemos ver qué puntos
pxA , xB q tienen un coste pre-establecido para observar el comportamiento de la función
de costes y ası́ deducir dónde será mı́nimo el coste. Por ejemplo, si dibujamos C “ 74,
es decir 2xA ` 3xB “ 74, esta recta nos dará todas las combinaciones de compuestos
alimenticios que cuestan exactamente 74 euros. Lo mismo si dibujamos, para C “ 54, la
recta 2xA ` 3xB “ 54, o hacemos lo mismo para C “ 34, C “ 24. El mı́nimo estará en

4 Begoña Subiza i Josep E. Peris. MQiTE. Universitat d’Alacant

CAP 1 MATEMÀTIQUES 2 ADE-MÀRQUETING curs 24-25

la recta de coste menos posible que toque el conjunto. En este caso, vemos que el mı́nimo
está en el punto p8, 6q, siendo dicho coste mı́nimo C “ 34.

15
C “ 74
C “ 54
10

(8,6)

5 C “ 34
C “ 24

5 10 15 20

Nota 1 ¿Se podrı́a aplicar tal cual a la alimentación humana? ¿Habrı́a que añadir más
restricciones? La solución del problema inicial (alimentación de los soldados) proponı́a
una dieta a base de alimentos naturales con un coste anual de 40$ por soldado (unos
900$ actuales, 830e al año, 2.3e actuales al dı́a). Realmente, el coste de alimentación era
muy bajo. Lo malo es que el tipo de alimentos que se seleccionaban era poco adecuado (y
apetecible) para la población humana: las personas no estaban dispuestas a comer “pienso”.
En el siguiente ejemplo se plantea una versión de este problema que resulta más aplicable
a la alimentación humana.

Ejemplo 2 Un estudiante de ADE asiste a la universidad (mañana y tarde) los 5 dı́as de

la semana. En su hora de comida tiene 3 opciones:
1. ir a uno de los comedores de la universidad

2. comprar un sándwich en una de las máquinas de la universidad

3. traer un tupper con comida preparada desde casa

Cada opción tiene un aporte nutritivo distinto que está representado en la siguiente tabla,
ası́ como su coste.

Begoña Subiza i Josep E. Peris. MQiTE. Universitat d’Alacant 5

CAP 1 MATEMÀTIQUES 2 ADE-MÀRQUETING curs 24-25

por cada comida: coste (e) contenido N1 (gr) contenido N2 (gr)

comedor 8 20 30
sándwich 4 15 10
tupper 5 25 5
necesidades de nutrientes: 100 50

El estudiante busca cumplir sus necesidades de nutrientes gastando lo menos posible ya que
la beca/asignación semanal no da para mucho y prefiere ahorrar algo para ocio.
Este problema ya tiene más sentido, y el estudiante deberá decidir cuántos dı́as irá al
comedor, x, cuántos dı́as se comprará un sándwich, y, cuántos dı́as traerá un tupper de
casa, z. Con esto, el problema queda formalmente como:

Minimizar 8x ` 4y ` 5z

con las restricciones:

(a) x, y, z P t0, 1, 2, 3, 4, 5u (las variables representan el número de dı́as de la semana que

elige cada opción; por tanto, son números enteros y toman valores entre 0 y 5)

(b) x ` y ` z “ 5 (en total, come 5 dı́as en la universidad)

(c) 20x ` 15y ` 25z • 100 (al menos, 100 unidades de N1)

(d) 30x ` 10y ` 5z • 50 (al menos, 50 unidades de N2)

Nota 2 Se puede comprobar que la solución a este problema es x “ 1, y “ 2, z “ 2, con

un coste mı́nimo de 26 e semanales.

1.3. Un inventario de ejemplos

Al margen del problema de la dieta, uno de los más conocidos en la teorı́a de op-
timización (lineal), existen muchos otros que ilustran cómo el uso de la optimización
(maximizar/minimizar) está presente en el dı́a a dı́a. En esta sección vamos a comen-
tar (brevemente) unos cuantos ejemplos que ilustrarán el contenido de los capı́tulos
siguientes.

E1 Maximizar producción con coste de producción prefijado:

Con una combinación adecuada de varios inputs se obtiene una cantidad de out-
put, que depende de los inputs utilizados (esta dependencia nos la indica una
función de producción conocida). El objetivo es maximizar la producción con unos
costes prefijados de antemano (si no hay lı́mite de coste, podrı́amos producir tanto
como quisiéramos).

6 Begoña Subiza i Josep E. Peris. MQiTE. Universitat d’Alacant

CAP 1 MATEMÀTIQUES 2 ADE-MÀRQUETING curs 24-25

Formalmente, las variables a determinar son las cantidades de inputs: x, y, . . . Por

ejemplo, si solo hay dos inputs x,y con precios unitarios px “ 2e, py “ 4e, la
función de producción es qpx, yq “ xy, y para la producción solo tenemos 200e, el
problema serı́a
Maximizar qpx, yq “ xy 2x ` 4y “ 200 x • 0, y • 0
Estamos suponiendo que gasta todo el dinero disponible para producción. Ya ve-
remos que, en general, no es razonable exigir que gaste todo el capital disponible,
en cuyo caso cambiaremos la igualdad en la restricción por una desigualdad.

E2 Minimizar costes de producción con una producción prefijada:

El problema dual del anterior consistirı́a en, una vez decidida la cantidad a pro-
ducir q ˚ determinar la combinación de inputs que nos permitan obtener esta pro-
ducción al menor coste posible. Observemos que si solo exigimos minimizar costes
(de los inputs) sin predeterminar qué producción (cantidad de output) queremos,
el problema serı́a obvio: no produciendo nada, el coste de producción es cero (su-
ponemos que no hay costes fijos). Como antes, las variables a determinar son las
cantidades de inputs: x, y, . . . Por ejemplo, si solo hay dos inputs x,y con precios
px “ 2e, py “ 4e, suponemos la misma función de producción es qpx, yq “ xy, y
queremos producir 1250 unidades de output, el problema serı́a
Minimizar cpx, yq “ 2x ` 4y xy “ 1250 x • 0, y • 0

Nota 3 Cuando veamos cómo resolver los problemas anteriores E1, E2, comproba-
remos que ambos tienen la misma solución x “ 50, y “ 25. Entonces, la cantidad
óptima (máxima) de output que obtenemos con 200e es q ˚ “ 1250, mientras que
el coste óptimo (mı́nimo) de producir 1250 unidades de output es 200e. Por esto se
denominan problemas duales: solucionando uno, resolvemos ambos.

E3 Teorı́a del consumidor:

Este es un ejemplo tı́pico en los textos de economı́a, que puede plantearse (de for-
ma simplificada) del siguiente modo. Un consumidor dispone de una renta m que
puede gastar en x unidades de un bien al precio unitario p, o puede ahorrar para
gastar en otros bienes (o en inversión). El consumidor se enfrenta a la restricción
presupuestaria px ` y “ m, siendo y la cantidad que ahorra. Si las preferencias
del consumidor están representadas por una función de utilidad upx, yq que de-
pende de las unidades del bien que compro y del dinero que ahorro, en términos
matemáticos el consumidor debe resolver el problema:
Maximizar upx, yq px ` y “ m x • 0, y • 0
Si, por ejemplo, consideramos los valores p “ 2e, m “ 100e y la función de
utilidad es upx, yq “ xy, gráficamente el problema es:

Begoña Subiza i Josep E. Peris. MQiTE. Universitat d’Alacant 7

CAP 1 MATEMÀTIQUES 2 ADE-MÀRQUETING curs 24-25

Veremos en el capı́tulo 4 que la solución de este problema se alcanza en el punto

p25, 50q, es decir el consumidor compra 25 unidades del bien y ahorra 50e, y su
utilidad máxima es u˚ “ 1250.

E4 Envase óptimo: Una empresa productora de refrescos está estudiando modificar

sus envases cilı́ndricos, decidiendo cuál será su altura h y el radio de la circunfe-
rencia de la base r. El objetivo es minimizar la superficie de aluminio utilizada en el
envase, para un volumen de 333.3 cm3 .

área lateral A “ 2⇡r2 ` 2⇡rh

volumen V “ ⇡r2 h

8 Begoña Subiza i Josep E. Peris. MQiTE. Universitat d’Alacant

CAP 1 MATEMÀTIQUES 2 ADE-MÀRQUETING curs 24-25

El problema de optimización serı́a (tomando como unidades cm):

Minimizar 2⇡r2 ` 2⇡rh ⇡r2 h “ 333.3

Cuando estudiemos el Capı́tulo 4, veremos que la solución óptima del problema

es r “ 3.76 cm, h “ 7.52 cm (aproximadamente), pero una lata normal de refresco
mide entre 2.5 cm y 3 cm de radio (otras tienen un radio incluso más pequeño).
¿Encuentras alguna razón para que no se use el tamaño óptimo?

E5 Uso óptimo de los recursos de producción: Se dispone de recursos (máquinas,

trabajadores, . . . ) que pueden estar infrautilizados. Se trata de determinar el mo-
do de usar al máximo los recursos disponibles. El siguiente ejemplo ilustra esta
situación:
Una fábrica dispone de tres tipos de máquinas: (A), (B) y (C). Cada tipo de máqui-
na tiene actualmente un tiempo de inactividad diario de 6500, 10000 y 9000 mi-
nutos. Para aprovecharlos, el gerente de la empresa propone fabricar dos nuevos
productos O1 , O2 que vende en cajas de 100 unidades, y proporcionan un bene-
ficio de ⇡1 “ 3 e y ⇡2 “ 2 e, respectivamente, por cada caja. Una unidad de
O1 utiliza 5, 7 y 4 minutos de las máquinas. Una unidad de O2 utiliza 2, 9 y 12
minutos de las máquinas. ¿Cuántas cajas x1 , x2 de cada uno de los nuevos produc-
tos producirá diariamente para maximizar el beneficio que puede obtener del tiempo
disponible?
El problema de optimización serı́a:

Maximizar 3x1 ` 2x2 x1 • 0, x2 • 0 xi P Z (son cajas enteras)

500x1 ` 200x2 § 6500 700x1 ` 900x2 § 10000 400x1 ` 1200x2 § 9000

Respresentado gráficamente (ya que solo hay dos variables) los puntos que cum-
plen las restricciones, se puede deducir que la solución de este problema se alcanza
en el punto p12, 1q. Esto es, hará 12 cajas (de 100 unidades) del producto O1 y 1
caja del producto O2 .

Nota 4 Como se ha mencionado, las variables de este problema deben tomar valores
enteros (son cajas de 100 unidades que no pueden “trocearse”, y no tendrı́a sentido
proponer como solución que se produzcan 12.42 cajas del primer producto y 1.45
cajas del segundo producto, aunque esto dé un mayor beneficio). Esto ocurrirá en
algunos otros problemas, que involucran a personas, objetos indivisibles, etc., dando
lugar a la denominada programación entera. El siguiente ejemplo muestra uno de
estos casos: las variables a determinar son coches que van de plantas de montaje a
distribuidores. No es admisible una solución que indique que 20, 6 coches van de un
sitio a otro.

Begoña Subiza i Josep E. Peris. MQiTE. Universitat d’Alacant 9

CAP 1 MATEMÀTIQUES 2 ADE-MÀRQUETING curs 24-25

E6 Problema de transporte: Este es también un problema tı́pico en el estudio de la

teorı́a de optimización. Veamos un ejemplo:
Una compañı́a automovilı́stica tiene 2 plantas de montaje y 4 distribuidores re-
partidos por todo el paı́s. La compañı́a debe determinar cuántos vehı́culos suminis-
trará cada planta a cada distribuidor para minimizar los costes de transporte de los
automóviles desde las plantas a los distribuidores. La información de que dispone
es la siguiente:

distribuidor D1 D2 D3 D4
demanda 36 42 28 54

planta de montaje A B
capacidad de producción 100 90

cij D1 D2 D3 D4
coste de transporte (por coche)
A 250 360 310 200
de cada planta a cada distribuidor
B 370 230 280 350

Con estos datos, las variables que hay que determinar son:
xA1 : coches que van de la planta A al distribuidor 1
xA2 : coches que van de la planta A al distribuidor 2
xA3 : coches que van de la planta A al distribuidor 3

10 Begoña Subiza i Josep E. Peris. MQiTE. Universitat d’Alacant

CAP 1 MATEMÀTIQUES 2 ADE-MÀRQUETING curs 24-25

xA4 : coches que van de la planta A al distribuidor 4

xB1 : coches que van de la planta B al distribuidor 1
xB2 : coches que van de la planta B al distribuidor 2
xB3 : coches que van de la planta B al distribuidor 3
xB4 : coches que van de la planta B al distribuidor 4

El objetivo es minimizar el coste de transporte:

ÿ
Minimizar cij xij i “ A, B j “ 1, 2, 3, 4
ij

cij : coste de la planta i al distribuidor j.

Pero cada distribuidor debe recibir las unidades que pide, y cada planta no puede
mandar más coches de los que tiene. Escrito formalmente en el ejemplo:

Minimizar 250xA1 ` 360xA2 ` 310xA3 ` 200xA4 ` 370xB1 ` 230xB2 ` 280xB3 ` 350xB4

xA1 ` xB1 “ 36 xA2 ` xB2 “ 42 xA3 ` xB3 “ 28 xA4 ` xB4 “ 54

xA1 ` xA2 ` xA3 ` xA4 § 100

xB1 ` xB2 ` xB3 ` xB4 § 90

xij • 0 xij P Z i “ A, B j “ 1, 2, 3, 4

Este tipo de problemas tiene muchas variables y restricciones (en el ejemplo, con
solo 2 plantas y 4 distribuidores, aparecen 8 incógnitas, 4 ecuaciones de igualdad,
2 inecuaciones, las de no-negatividad y las que indican que las variables deben ser
enteras). En estas circunstancias hay algoritmos (métodos) particulares que re-
suelven el problema. Para el problema de transporte existen varios de estos algorit-
mos (el más conocido es el denominado esquina-noroeste, por la situación gráfica
como se empieza a resolver el problema, aunque en realidad se puede comenzar
por cualquier esquina de un rectángulo que recoge los datos del problema). En la
actualidad hay programas informáticos que los resuelven instantáneamente. Por
ejemplo, con el programa

problema transport

se obtiene la solución al anterior problema que aparece en la siguiente tabla:

Begoña Subiza i Josep E. Peris. MQiTE. Universitat d’Alacant 11

CAP 1 MATEMÀTIQUES 2 ADE-MÀRQUETING curs 24-25

E7 Plan de inversión óptimo: Se trata de determinar el método óptimo (el que dé el
mayor beneficio) de invertir un determinado volumen de capital, dentro de las
posibilidades de inversión que existan. Por ejemplo:
Una compañı́a de inversión dispone de 1.5 millones de euros para invertir en tres
fondos con rentabilidad garantizada, durante los próximos tres años. El fondo A
tiene una rentabilidad anual del 7 %. El fondo B tiene una rentabilidad del 5 % el
primer año y del 8 % los dos años siguientes. El fondo C estará disponible al inicio
del segundo año y ofrece una rentabilidad del 10 % anual el segundo y tercer año.
Determina la cantidad que invertirá cada año en cada fondo.

Nota 5 Una vez invertida una cantidad, ésta queda invertida hasta el final del tercer
año, sin posibilidad de recuperación anticipada. Los beneficios no se reinvierten.

Las variables que deben determinarse son:

xAi : cantidad que se invierte en el fondo A al inicio del año i “ 1, 2, 3 (es decir,
xA1 es lo que invertirá en el fondo A al principio del primer año, xA2 es lo
que invertirá en ese fondo al inicio del segundo año, y finalmente xA3 es lo
que invertirá el tercer año)
xBi : cantidad que se invierte en el fondo B al inicio del año i “ 1, 2, 3
xCi : cantidad que se invierte en el fondo C al inicio del año i “ 2, 3 (en el fondo
C no se puede invertir el primer año ya que no está disponible)

La función que nos da el beneficio (que deseamos maximizar) es:

12 Begoña Subiza i Josep E. Peris. MQiTE. Universitat d’Alacant

CAP 1 MATEMÀTIQUES 2 ADE-MÀRQUETING curs 24-25

Maximizar ⇡ ” ⇡A ` ⇡B ` ⇡C
donde
⇡A “ 0.07xA1 ` 0.07pxA2 ` xA1 q ` 0.07pxA3 ` xA2 ` xA1 q

⇡B “ 0.05xB1 ` 0.08pxB2 ` xB1 q ` 0.08pxB3 ` xB2 ` xB1 q

⇡C “ 0.10xC2 ` 0.10pxC3 ` xC2 q

restringido a
xA1 ` xA2 ` xA3 ` xB1 ` xB2 ` xB3 ` xC2 ` xC3 “ 1.5

xij • 0 i “ A, B, C j “ 1, 2, 3

E8 Flujo máximo: Este es también un problema clásico de optimización (programa-

ción) lineal. Se pretende el uso óptimo de rutas entre dos puntos de importancia.
Esto se puede aplicar a oleoductos, redes eléctricas o de transmisión de datos, ...
El objetivo es trasportar la mayor cantidad posible de una mercancı́a desde el pun-
to inicial al punto final (en el ejemplo, desde el punto INICI al punto FINAL en la
gráfica), sabiendo la capacidad máxima de cada una de las rutas por las que puede
circular la mercancı́a.

INICI
30
4
50 40

2 10
5

30 3 10

20

FINAL

Red de conexiones y capacidad de cada conexión

Las variables a determinar son las unidades de mercancı́a que circularán por cada
conexión. Como se ha comentado, se pretende maximizar el número de unidades

Begoña Subiza i Josep E. Peris. MQiTE. Universitat d’Alacant 13

CAP 1 MATEMÀTIQUES 2 ADE-MÀRQUETING curs 24-25

que llega al punto final. En el ejemplo, las variables son:

xINICI,2 xINICI,3 xINICI,4 x2,4 x4,3 x2,FINAL x3,FINAL x4,FINAL

Observamos que las rutas van solo en una dirección, por eso no hay variable x4,2 ,
ni x3,4 (si fuera posible ir en ambas direcciones dibujarı́amos dos conexiones y, en
ese caso, el flujo en cada sentido podrı́a ser distinto). Observamos también que no
hay variable x2,3 , ni x3,2 , ya que no hay una ruta entre estos dos puntos (puede
significar que hay un puente roto, que uno de los puntos está en una isla que no
está comunicada con el otro punto, . . . ). Por tanto, el objetivo es
ÿ
Maximizar xi,FINAL
i

sujeto a la restricción de que, en cada enlace i, la cantidad que sale debe coincidir
con la que entra, al margen de la no negatividad, y la posible restricción de que las
variables sean enteras (por ejemplo, si se trata de seres humanos). En la gráfica
que estamos analizando, en el punto 3 debe cumplirse xINICI,3 ` x4,3 “ x3,FINAL , o en
el punto 2 debe cumplirse xINICI,2 “ x2,4 ` x2,FINAL .
Como observamos, el número de variables es elevado, ası́ como también el núme-
ro de restricciones del problema. Por tanto, la resolución suele ser larga y tediosa.
Existen algoritmos especı́ficos que se usan para encontrar la solución de este pro-
blema y actualmente se resuelven mediante programas informáticos. Por ejemplo,
en el siguiente enlace podemos resolver el ejemplo gráfico anterior: max flow

Construcción del grafo: la “fuente” (INICI) corresponde al número 1, mientras que el

“sumidero” (FINAL) se ha denotado con el número 5.

14 Begoña Subiza i Josep E. Peris. MQiTE. Universitat d’Alacant

CAP 1 MATEMÀTIQUES 2 ADE-MÀRQUETING curs 24-25

La solución óptima (que da el flujo máximo) aparece en la siguiente figura, siendo

dicho flujo máximo Fmáx “ 55.

Configuración final de la solución de flujo máximo: En cada arista indica el uso de la

misma (sobre su capacidad). No se usa la conexión entre los nodos 2 y 4 (no aparece
ningún número indicando uso, solo aparece la capacidad).

Nota 6 Es posible que un problema de optimización tenga más de una solución. Por
ejemplo, en el flujo máximo anterior, podrı́amos cambiar el flujo en algunas de las
conexiones poniendo
x˚INICI,4 “ 10 x˚INICI,2 “ 35 x˚2,4 “ 5
y dejando el resto igual. El flujo total obtenido continua siendo Fmáx “ 55. Hay otras
posibles soluciones, pero este hecho no ocasiona conflicto, ya que el objetivo es obtener
el flujo máximo. Cualquiera que sea la solución elegida, cumple con el objetivo.

E9 Red de coste mı́nimo: Se dispone de una “fuente” (depósito de agua, central

eléctrica, ...) que debe estar conectada a todos sus posible “clientes”, bien directa-
mente o bien a través de otro cliente que está conectado. Cada conexión tendrı́a
un coste1 (si se construye) y el objetivo es construir una red que minimice el coste
total de conexión.
1
El coste podrı́a ser el precio de hacer la conexión, o podrı́a representar la distancia entre los dos
puntos, o el peaje que se debe pagar por cruzar esa conexión (puente), . . . Cuando una conexión no
aparece es porque no es posible construirla (o utilizarla) y se supondrá entonces que tiene un coste
infinito, con lo que nunca aparecerá en una red óptima.

Begoña Subiza i Josep E. Peris. MQiTE. Universitat d’Alacant 15

CAP 1 MATEMÀTIQUES 2 ADE-MÀRQUETING curs 24-25

Red de conexiones y costes de conexión (la fuente es City Hall)

Las variables sobre las que hay que decidir en este problema son categóricas: “se
usa, no se usa”, “se construye, no se construye”, “sı́, no”, . . . que, en términos
matemáticos, se convierten en un 0 o en un 1:
xij “ 1 si se construye la conexión que une i con j
xij “ 0 si no se construye la conexión que une i con j

Entonces, formalmente, el problema de optimización consiste en encontrar el

mı́nimo de la función (coste de pasar por todos):
ÿ
Minimizar cij xij xij P t0, 1u
i,j

sujeto a una serie de restricciones (debe enlazar, directa o indirectamente, todos

los clientes con la fuente). Existen diferentes algoritmos que calculan la solución
de este tipo de problemas. Estos algoritmos son fáciles de aplicar cuando el núme-
ro de nodos (agentes, casas, . . . ) a conectar es pequeño. Sin embargo, cuando el
número es elevado requiere del uso informático. Por ejemplo, la siguiente página
calcula la solución buscada

minimum cost spanning tree

16 Begoña Subiza i Josep E. Peris. MQiTE. Universitat d’Alacant

 CAP 1 MATEMÀTIQUES 2 ADE-MÀRQUETING curs 24-25

Vamos a ver un algoritmo (descubierto en 1930 por el matemático V. Jarnik y

luego de manera independiente por el cientı́fico computacional R. Prim en 1957)
que es muy intuitivo y sencillo (cuando hay pocos nodos a conectar).

A LGORITMO DE P RIM :

PASO INICIAL : conecta a la fuente el nodo con la conexión más “barata” existente (en caso
de empate, elige cualquiera de ellos)
SIGUIENTES PASOS : conecta a la fuente, o a un nodo ya conectado a la fuente, el nodo no co-
nectado con la conexión más “barata” existente (en caso de empate, elige
cualquiera de ellos)

Usando este algoritmo en el ejemplo de las casas, obtenemos la ruta de coste

mı́nimo (marcada en rojo), con un coste Cmı́n “ 79m.

Nota 7 Usando el enlace proporcionado, se puede resolver online el siguiente proble-

ma (la fuente es el nodo marcado en rojo como 1)

Begoña Subiza i Josep E. Peris. MQiTE. Universitat d’Alacant 17

CAP 1 MATEMÀTIQUES 2 ADE-MÀRQUETING curs 24-25

E10 Planificación óptima de la producción: La planta de producción de una conocida

marca de helados los distribuye a su cadena de heladerı́as. Se sabe que la demanda
global de las heladerı́as cada mes (en contenedores de 5 litros) es:

mes ene feb mar abr may jun jul ago sep oct nov dic
nº cont. 75 80 85 95 120 140 175 190 175 130 110 90
demanda mensual (nº de contenedores)

La siguiente tabla muestra la capacidad de producción mensual en horas regulares

y en horas extra, ası́ como el coste (en e por contenedor) en cada uno de los
periodos:

mes ene feb mar abr may jun jul ago sep oct nov dic
nº cont. 100 100 100 90 90 90 90 90 80 80 80 90
coste 6 6 6 6 7 7 8 8 8 7 7 6
nº extra 40 40 40 40 40 50 50 60 60 60 50 50
coste ex. 8 8 8 8 9 9 9 9 9 9 9 8
capacidad mensual (nº de contenedores) y coste por contenedor

La planta puede producir cada mes una cantidad mayor que su demanda (limitada
por la capacidad), si le resulta conveniente. El almacenaje de un contenedor tiene
un coste de 1e mensual. Debe decidir cuántos contenedores fabricará cada mes,
en tiempo regular y en tiempo extra, para minimizar costes (sumando producción y
almacenaje) y cumplir con su demanda mensual.
Las variables del problema son:
x0i : cantidad que producirá en tiempo regular el mes i “ 1, 2, . . . , 12
x1i : cantidad que producirá en tiempo extra el mes i “ 1, 2, . . . , 12

La función objetivo consiste en minimizar los costes de producción (sumando los

costes regulares y extra, y los costes de almacenaje). Las restricciones tienen que
ver, por un lado, con las posibilidades de producción mensual y, por otro, con la
demanda de cada mes que debe ser satisfecha.

E11 Asignación óptima de recursos: Se quiere encontrar la forma de asignar ciertos

recursos disponibles (máquinas o personas) para la realización de determinadas
tareas al menor coste, suponiendo que cada recurso se destina simultáneamente
a una sola tarea, y que cada tarea es ejecutada por uno solo de los recursos. Por
ejemplo:

18 Begoña Subiza i Josep E. Peris. MQiTE. Universitat d’Alacant

CAP 1 MATEMÀTIQUES 2 ADE-MÀRQUETING curs 24-25

Una empresa tiene cuatro máquinas y cuatro tareas. Cada máquina se debe asignar
a una sola tarea. El tiempo requerido por cada máquina para cada tarea se muestra
en la siguiente tabla. La empresa desea minimizar el tiempo total necesario para
completar las cuatro tareas.

máquina tarea 1 tarea 2 tarea 3 tarea 4

1 14 5 8 7
2 2 12 6 5
3 7 8 3 9
4 2 4 6 10
Tiempo en horas de cada máquina requerido por cada tarea

La empresa debe decidir qué máquina debe asignarse a cada tarea. Por tanto, las
variables son:
xij “ 1 si la máquina i se asigna a la tarea j
xij “ 0 si la máquina i no se asigna a la tarea j

La función objetivo (a minimizar) es:

ÿ
Minimizar tij xij
i,j

tij : tiempo requerido de la máquina i por la tarea j

Las restricciones, al margen que las variables son dicotómicas, xij P t0, 1u, de-
ben indicar que cada máquina se asigna a una tarea, y que cada tarea tiene una
máquina disponible. En el ejemplo:
x11 ` x12 ` x13 ` x14 “ 1; x21 ` x22 ` x23 ` x24 “ 1;
x31 ` x32 ` x33 ` x34 “ 1; x41 ` x42 ` x43 ` x44 “ 1;
x11 ` x21 ` x31 ` x41 “ 1; x12 ` x22 ` x32 ` x42 “ 1;
x13 ` x23 ` x33 ` x43 “ 1; x14 ` x24 ` x34 ` x44 “ 1

E12 Ubicación óptima de centro de distribución o gran área comercial: El coste de

transporte suele ser el componente más significativo en los costes totales de una
cadena de suministro del centro de producción a la cadena de comercios. Del mis-
mo modo, el tiempo hasta el centro comercial es fundamental para que un cliente
acuda a un centro comercial ubicado fuera de su ciudad de residencia. Por tanto,
el objetivo es encontrar la ubicación que minimice los costes de transporte/tiempos
de desplazamiento. Obviamente un aspecto relevante es el uso que cada “agente”
hace: por ejemplo, en el caso del centro comercial, importa el tamaño de cada
ciudad; o, en el caso de la central de suministros, la demanda de cada comercio.

Begoña Subiza i Josep E. Peris. MQiTE. Universitat d’Alacant 19

CAP 1 MATEMÀTIQUES 2 ADE-MÀRQUETING curs 24-25

Eligiendo un origen de coordenadas arbitrario (en el centro de la región, o en

uno de los extremos), las coordenadas de situación de las ciudades se pueden
asociar a puntos del plano. Por ejemplo, supongamos una región en la que existen
4 ciudades relevantes, cuyas poblaciones (en miles de habitantes) son p1 “ 18,
p2 “ 50, p3 “ 10, p4 “ 75. La situació de estas ciudades se puede asociar a los
puntos del plano x1 “ p1, 6q, x2 “ p´2, 8q, x3 “ p3, ´2q, x4 “ p5, 1q. Se debe decidir
la ubicación óptima de una gran superficie comercial que dé servicio a las 4 ciudades.

20 Begoña Subiza i Josep E. Peris. MQiTE. Universitat d’Alacant

CAP 1 MATEMÀTIQUES 2 ADE-MÀRQUETING curs 24-25

Las variables son las coordenadas pa, bq del punto dónde se situará el centro co-
mercial. El objetivo es que esté lo más cerca posible de los usuarios. Es decir, que
minimice la distancia (ponderada con el número de habitantes) de cada ciudad al
centro comercial.

En el ejemplo se trata de resolver el problema:2

18 a 52 a
Minimizar px ` 2q2 ` py ´ 8q2 ` px ´ 1q2 ` py ´ 6q2 `
153 153
10 a 75 a
` px ´ 3q2 ` py ` 2q2 ` px ´ 5q2 ` py ´ 1q2
153 153
En general, este tipo de problema es difı́cil de resolver (hay que derivar las funcio-
nes con raı́ces, lo que complica los cálculos posteriores; veremos un ejemplo más
adelante en el capı́tulo 3). Una solución aproximada (muy fácil de calcular) a este
problema se conoce con el nombre de centro de gravedad y propone el punto:
∞ ∞
pi xi pi yi
a“ ∞ i
b “ ∞i
i pi i pi

donde pi representa la población de la ciudad i, siendo pxi , yi q sus coordenadas de

acuerdo al origen considerado. Aplicado al ejemplo anterior, el centro de gravedad
es el punto p2.74, 3.26q, que está cerca de la solución óptima (marcada con un
triángulo rojo en la gráfica).

Nota 8 ¿Por qué crees que debe ponderarse cada distancia por el número (relativo)
de habitantes de cada ciudad?

2
Veremos más adelante
a que la distancia entre dos puntos A “ px1 , y1 q, B “ px2 , y2 q viene dada por
la expresión dpA, Bq “ px1 ´ x2 q2 ` py1 ´ y2 q2 .

Begoña Subiza i Josep E. Peris. MQiTE. Universitat d’Alacant 21