Asignatura: Matemáticas I
Profesor: Roque Molina Legaz
Remark Este tema se ha elaborado con apuntes de los profesores del Dpto de
Matemática Aplicada y Estadística, Antonio Guillamón Frutos y Silvestre Paredes
Hernández.
TEMA 7: INTRODUCCIÓN A LA
PROGRAMACIÓN LINEAL
Programa detallado:
7.1 Introducción y ejemplos.
7.2 Solución gráfica de problemas lineales.
7.2.1 Ejemplos.
Introducción y Ejemplos
Un caso particular de problemas de optimización son los problemas de optimización o
programación lineal. Un problema de programación lineal tiene como objetivo la optimización
(maximización o minimización) de una función lineal bajo restricciones de igualdad y/o
desigualdad lineales en las incógnitas, donde tanto el número de variables como el número de
restricciones es finito.
A pesar de este planteamiento tan restrictivo, ya que el modelo se limita a la utilización de
cierto tipo de funciones que no son frecuentes en el mundo real, las técnicas de programación
lineal son utilizadas en multitud de problemas al intentar optimizar algún aspecto del
comportamiento de un sistema, como puede ser la asignación de recursos, la planificación de
producción, problemas de dietas, el tiempo de evolución de un proceso, control de
contaminación, etc.
La programación lineal ha demostrado desde hace tiempo su utilidad como modelo
significativo de numerosos problemas de distribución y de fenómenos económicos.
La programación lineal es un caso especial de optimización matemática con restricciones en
el que todas las funciones que aparecen en el problema son lineales en las incógnitas. A pesar de
este planteamiento tan restrictivo, ya que el modelo se limita a la utilización de un tipo particular
de funciones, que por otra parte no son muy frecuentes en los modelos reales, las técnicas de
programación lineal son utilizadas en muchos problemas.
Se exponen a continuación algunos ejemplos clásicos de situaciones que tienen una
formulación natural dentro del ámbito de la programación lineal.
Example (Problema de la dieta) Con este problema tratamos de determinar la dieta más
económica que satisfaga las necesidades nutritivas mínimas básicas para una buena
salud. Dicho problema lo tendría, por ejemplo, el médico encargado de la dieta de
un colegio o el dueño de una granja. Para plantear el problema supongamos que
podemos adquirir n alimentos diferentes, siendo c i el precio del i-ésimo alimento.
Para componer una dieta necesitamos una serie de nutrientes básicos como
proteínas, vitaminas, hierro, etc.; supongamos por tanto que hay m nutrientes
básicos. Con el fin de conseguir la dieta equilibrada, cada individuo debe recibir al
menos b j unidades diarias del nutriente j-ésimo. Cada alimento i contendrá una
determinada cantidad del nutriente j por unidad; sea a ji la cantidad de nutriente j
que tiene cada unidad del alimento i.
Si definimos la variable x i como número de unidades del alimento i que forman
parte de la dieta, el problema consistirá en seleccionar los valores de estas
variables x i de forma que minimicen el coste total, pero satisfaciendo las
necesidades nutritivas. El coste de los alimentos empleados estará representado
mediante la función objetivo
c1x1 cnxn
mientras que las restricciones nutritivas vendrán dadas por el sistema
a 11 x 1 a 1n x n b1
a m1 x 1 a mn x n bm
además hay que tener en cuenta que las variables son no negativas:
x j 0, j 1, , n.
Example (Problema del transporte) Supongamos que una empresa elabora un
determinado producto y dispone para ello de m sucursales en distintos puntos de m
Una empresa debe enviar las cantidades a 1 , , a m de cierto producto desde m
lugares y recibirse en cantidades b 1 , , b n en n destinos.
Si c ij es el coste de envío por unidad de producto desde el origen i hacia el
destino j, deseamos determinar las cantidades x ij a enviar desde el origen i al
destino j para que se minimice el coste total del transporte, satisfaciendo las
necesidades de demanda de cada destino.
Para formular el problema como un problema de programación lineal se
dispone la siguiente matriz:
x 11 x 1n a 1
x m1 x mn a m
b1 bn
La i-ésima fila define las variables asociadas al origen i-ésimo, mientras que la
columna j-ésima determina las variables asociadas al j-ésimo destino. El problema
consiste en situar variables no negativas, x ij , en la matriz, de modo que la suma de
la i-ésima fila sea a i , la suma de la j-ésima columna sea b j y la suma:
n m
c ij x ij
j 1 i 1
que representa el costo total del transporte sea mínima. Resulta por tanto el
siguiente problema de programación lineal:
Minimizar ij
c ij x ij
Sujeto a
n
x
j 1 ij
ai i 1, ,m
m
x
i 1 ij
bj j 1, ,n
x ij 0 i, j
Obviamente para que las restricciones:
n
x
j 1 ij
ai
m
x
i 1 ij
bj
sean consistentes, se debe dar la relación:
m n
ai bj
i 1 j 1
es decir la cantidad recibida es igual a la cantidad enviada.
Example (Problema de almacenamiento) Queremos dirigir un almacén comprando y
vendiendo la existencia de cierta mercancía con el fin de maximizar el beneficio en
un periodo de tiempo determinado. El almacén tiene una capacidad fija C y hay un
coste r por cada unidad almacenada durante un periodo de tiempo. Sabemos que el
precio de la mercancía varía en determinados periodos de tiempo (meses). En un
periodo cualquiera se mantiene al mismo precio tanto de compra como de venta.
Inicialmente el almacén está vacío y al final del periodo también tiene que estar
vacío.
Para la formulación de este problema introducimos variables para cada periodo
de tiempo. Sea x i el nivel de existencias en almacén al principio del periodo i. Sea u i
la cantidad comprada durante i y s i la cantidad vendida en ese mismo periodo. Si
queremos controlar la dirección del almacén durante n periodos de tiempo, tenemos
que plantear el siguiente problema de programación lineal:
n
Minimizar ps
i 1 i i
rx i
Sujeto a
xi 1 xi ui si i 1, ,n
0 xn un sn
xi zi C
x1 0
xi, ui, si, zi 0
Donde p i es la ganancia de cada objeto vendido, es decir, el precio de venta menos
el precio de compra.
Si por ejemplo n 3 tenemos:
u1 s1 0
x2 u2 s2 x3 0
x2 z2 C
x3 u3 s3 0
x3 z3 C
Se puede observar que la matriz de coeficientes puede separarse en bloques corres
pondientes a las variables en los distintos periodos de tiempo. Los únicos bloques
con valores distintos de 0 son los diagonales y los situados inmediatamente encima
de la diagonal. Esta estructura es la usual en los problemas que implican tiempo.
Example (Problema de producción) Sea una instalación que puede dedicarse a n
actividades productivas diferentes, y supongamos que cada actividad produce
diferentes cantidades de m productos. Cada actividad puede realizarse a cualquier
nivel x i 0, pero a nivel unitario, la actividad i-ésima cuesta c i y produce a ji
unidades del j-ésimo producto, podemos plantear el problema de minimizar costes
como un problema de programación lineal.
Si suponemos linealidad en la capacidad de producción, y se da un conjunto de
m números, b 1 , , b m , que describen las necesidades de producción de los m bienes.
Podemos pensar en producir estos a un costo mínimo, en este caso estamos
planteando un problema de programación lineal similar al primer problema
expuesto (problema de la dieta).
Ejemplos.
Example (Problema de la dieta). Con este problema tratamos de determinar la dieta más
económica que satisfaga las necesidades nutritivas mínimas básicas para una buena
salud. Dicho problema lo tendría, por ejemplo, el médico encargado de la dieta de
un colegio o el dueño de una granja.
Supongamos que podemos adquirir n alimentos diferentes, y que c i es el precio
del i-ésimo alimento. Para realizar una dieta necesitamos una serie de nutrientes
básicos como proteínas, vitaminas, hierro, etc. Supongamos por tanto que hay m
nutrientes básicos. Para conseguir la dieta equilibrada, cada individuo debe recibir
al menos b j unidades del nutriente j-ésimo cada día. Cada alimento i va a contener
una determinada cantidad del nutriente j por unidad. Sea a ji la cantidad de
nutriente j que tiene cada unidad del alimento i.
Si hacemos x i número de unidades del alimento i en la dieta, el problema
consiste en seleccionar los valores de x i de forma que minimicen el coste total:
c1x1 cnxn
Sujeto a las restricciones nutritivas:
a 11 x 1 a 1n x n b1
a m1 x 1 a mn x n bm
junto con x j 0, j 1, , n.
Ejemplo del problema de la dieta
El departamento de Nutrición del Hospital General Mountain View prepara 30 menús de
cena, uno por cada día del mes. Una comida consiste en espagueti, pavo, patatas, espinacas y
pastel de manzana. El director del departamento de Nutrición, determina que esta comida debe
proporcionar 63000 mg de proteínas, 10 mg de hierro, 15 mg de niacina, 1 mg de tiamina y 50
mg de vitamina C. Cada 100 gramos de esta comida proporciona la cantidad de nutriente y grasas
indicadas en la tabla.
Proteínas Hierro Niacina Tiamina Vit. C Grasas
Espagueti 5000 1.1 1.4 0.18 0 5000
Pavo 29300 1.8 5.4 0.06 0 5000
Patatas 5300 0.5 0.9 0.06 10 7900
Espinacas 3000 2.2 0.5 0.07 28 300
P. manzana 4000 1.2 0.6 0.15 3 14300
Para evitar demasiada cantidad de un tipo de comida, no debe incluirse en ella más de 300 g
de espagueti, 300 g de pavo, 200 g de patatas, 100 g de espinacas y 100 g de pastel de manzana.
Se desea determinar la composición de una comida que satisface los requerimientos nutricionales
y proporciona la mínima cantidad de grasas.
FORMULACIÓN
1. Variables de decisión.
x 1 número de 100 g de espaguetis a incluir.
x 2 número de 100 g de pavo a incluir.
x 3 número de 100 g de patatas a incluir.
x 4 número de 100 g de espinacas a incluir.
x 5 número de 100 g de pastel de manzana a incluir.
2. Función objetivo.
Minimizar 5000x 1 5000x 2 7900x 3 300x 4 14300x 5 (grasas)
3. Restricciones.
5000x 1 29300x 2 5300x 3 3000x 4 4000x 5 63000 (proteínas)
1. 1x 1 1. 8x 2 0. 5x 3 2. 2x 4 1. 2x 5 10 (hierro)
1. 4x 1 5. 4x 2 0. 9x 3 0. 5x 4 0. 6x 5 15 (niacina)
0. 18x 1 0. 06x 2 0. 06x 3 0. 07x 4 0. 15x 5 1 (tiamina)
10x 3 28x 4 3x 5 50 (vit, C)
0 x1 3, 0 x2 3, 0 x3 2, 0 x4 1, 0 x5 1.
Example (Problema del transporte). Una empresa dedicada a la fabricación de
componentes de ordenador tiene dos fábricas que producen, respectivamente, 800 y
1500 piezas mensuales. Estas piezas han de ser transportadas a tres tiendas que
necesitan 1000, 700 y 600 piezas, respectivamente. Los costes de transporte, en
céntimos de euro/pieza, son los que aparecen en la tabla siguiente
Tienda A Tienda B Tienda C
Fábrica I 3 7 1
Fábrica II 2 2 6
¿Cómo debe organizarse el transporte para que el coste sea mínimo?
En este tipo de problemas se exige que toda la producción sea distribuida a los
centros de ventas en las cantidades que precisa cada uno; por tanto, no pueden
generarse inventario del producto ni en las fábricas ni en los centros de ventas. En
consecuencia, los 800 artículos producidos en la Fábrica I deben distribuirse en las
cantidades x, y, z a A, B y C, de manera que
x y z 800
Pero, además, si desde la Fábrica I se envían x unidades a la Tienda A, el resto,
hasta las 1000 necesarias en A, deben ser enviadas desde la Fábrica II; esto es,
1000 x unidades serán enviadas desde la Fábrica II a la Tienda A. Del mismo
modo, si desde la Fábrica I a la Tienda B se envían y unidades, el resto necesario,
700 y, deben enviarse desde la Fábrica II. Y lo mismo para C, que recibirá z desde
I y 600 z desde II. En la siguiente tabla de distribución se resume lo dicho:
a la Tienda A a la Tienda B a la Tienda C
Envios
1000 700 600
Desde la Fábrica I
x y 800 x y
800
Desde la Fábrica II
1000 x 700 y x y 200
1500
La última columna la hemos obtenido de la siguiente forma: Como x y z 800 ,
se tiene que z 800 x y, de donde, 600 z 600 800 x y x y 200.
Ahora bien, todas las cantidades anteriores deben ser mayores o iguales que cero.
Por tanto, se obtienen las siguientes desigualdades:
x 0; 1000 x 0; y 0; 700 y 0; 800 x y 0; x y 200 0
Simplificando las desigualdades anteriores, se obtienen las siguientes inecuaciones:
1000 x 0; 700 y 0; 800 x y 0
Recordemos que nuestro objetivo es abaratar al máximo los costes de transporte.
Estos costes se hallan multiplicando las cantidades enviadas a desde cada fábrica a
cada tienda por los respectivos costes de transporte unitario. Así, se obtiene:
Z f x, y 3x 2 1000 x 7y 2 700 y 800 x y 6 x y 200
6x 10y 3000
En definitiva, el programa lineal a resolver es :
Minimizar : Z 6x 10y 3000
sujeto a : 1000 x 0
700 y 0
800 x y 0
La región factible se da en la imagen del margen. Sus vértices son A(200,0) ;
B(800,0) ; C(100,700) ; D(0,700) y E(0,200).El coste, el valor de Z en cada uno de
esos puntos, es:
ZA 4200; Z B 7800; Z C 10600; Z D 10000; Z E 5000
Por tanto el mínimo se da en A , cuando x 200 e y 0. Luego, las cantidades a
distribuir son:
a la Tienda A a la Tienda B a la Tienda C
Envios
1000 700 600
Desde la Fábrica I
200 0 600
800
Desde la Fábrica II
800 700 0
1500
Example (Problema de almacenamiento). Un barco tiene las siguientes capacidades de
almacenamiento en sus bodegas de popa, centro y proa. Los dueños del barco
pueden elegir una porción o toda la carga de los productos A, B y C, cuyas
características se tabulan a continuación.
3
BODEGA CAPACIDAD (TM) CAPACIDAD (M
PROA (1) 3. 000 130. 000
CENTRO (2) 2. 000 100. 000
POPA (3) 1. 500 30. 000
BENEFICIO
PRODUCTOS TM A TRANSPORTAR M 3 /TM
(miles euros/TM)
A 3. 500 60 8
B 2. 500 50 7
C 2. 000 25 6
Para plantear este problema, definimos las variables x ij toneladas del producto j
j A, B, C) a cargar en la bodega i (i 1, 2, 3). Así, el problema consiste en
maximizar el beneficio del viaje, o lo que es lo mismo, maximizar la función
objetivo, que viene dada por
Z 8 x 1A x 2A x 3A 7 x 1B x 2B x 3B 6 x 1C x 2C x 3C
sujeto a las siguientes restricciones: (Vemos primero las de capacidad en TM de
cada bodega; despues la capacidad en M 3 de cada bodega; y por último el límite de
capacidad de cada producto
x 1A x 1B x 1C 3. 000
x 2A x 2B x 2C 2. 000
x 3A x 3B x 3C 1. 500
60x 1A 50x 1B 25x 1C 130. 000
60x 2A 50x 2B 25x 2C 100. 000
60x 3A 50x 3B 25x 3C 30. 000
x 1A x 2A x 3A 3. 500
x 1B x 2B x 3B 2. 500
x 1C x 2C x 3C 2. 000
y por supuesto, también ha de ser
x ij 0 j A, B, C i 1, 2, 3
Example (Problema de producción / asignación de recursos). Supongamos que una
fábrica de cervezas produce tres tipos distintos: negra (N), rubia (R) y sin alcohol
(S). Para su obtención son necesarios, además de agua y lúpulo, para los cuales no
hay limite, malta y levadura, que limitan la capacidad diaria de producción. La
siguiente tabla nos da la cantidad necesaria de cada sustancia para producir un
litro de cada una de las respectivas cervezas, los kilos disponibles de cada recurso y
el beneficio por litro de cada cerveza producida. El problema del fabricante
consiste en decidir cuánto debe de fabricar de cada cerveza para que el beneficio
diario total sea el máximo.
N R S Disponibilidad
Malta 2 1 2 30
Levadura 1 2 2 45
Beneficio 4 7 3
Siguiendo el esquema inicial, tomamos como variables de decisión:
x1 producción en litros de N por día
x2 producción en litros de R por día
x3 producción en litros de S por día
Un plan para producir, x 1 litros de N, x 2 litros de R y x 3 de S se denomina plan
o programa de producción que representamos por el vector x 1 , x 2 , x 3 .
Está claro que no es posible utilizar más recursos de los disponibles, de forma
que si observamos la tabla de los datos, vemos que:
x 1 litros de N necesitan 2 x 1 kilos de malta
x 2 litros de R necesitan 1 x 2 kilos de malta
x 3 litros de S necesitan 2 x 3 kilos de malta
y que la disponibilidad diaria de malta es de 30 kilos. Por tanto, las tres
variables de decisión deben satisfacer la desigualdad:
2x 1 x 2 2x 3 30
que representan
(recursos utilizados) (recursos disponibles)
Esta imposición sobre las variables x j es una de las restricciones al problema.
Análogamente, si observamos la siguiente fila de la tabla de recursos, y teniendo en
cuenta la disponibilidad diaria de levadura, tendremos la restricción
x1 2x 2 2x 3 45
Habría que añadir también las condiciones de no negatividad de las variables
de decisión, es decir:
x j 0 j 1, 2, 3
pues no tiene sentido un plan de fabricación con cantidades negativas para las
variables x j .
Finalmente el último apartado sería la construcción de la función objetivo. En
este caso pretendemos que el beneficio total sea máximo, por tanto la función
objetivo será el beneficio diario que obtenemos por los x 1 litros diarios de N, los x 2
litros de R y los x 3 litros de S, es decir, será la función:
z 4x 1 7x 2 3x 3
que hay que maximizar. En resumen podemos formular el problema de asignación
de recursos o de planificación de producción, como el de determinar los valores
para x 1 , x 2 , x 3 que resuelven el problema
Maximizar z 4x 1 7x 2 3x 3
Sujeto a
2x 1 x2 2x 3 30
x1 2x 2 2x 3 45
x1, x2, x3 0
Solución Gráfica de Problemas Lineales
En problemas de programación lineal de 2 o 3 variables podemos utilizar un procedimiento
gráfico para resolverlos. Aunque en realidad rara vez surgen problemas de este tipo, esta técnica
es muy útil para ayudar visualmente a comprender muchos conceptos y términos utilizados
posteriormente.
Las fases del proceso de solución gráfico son:
1. Dibujar un sistema de coordenadas cartesianas, donde las variables de decisión estén
representadas por los ejes.
2. Dibujar en el sistema coordenado las restricciones del problema, incluyendo las de no
negatividad. Notar que una restricción de desigualdad define una región limitada por una
línea recta (2D) o un plano (3D) al considerar esa restricción como una igualdad. La
intersección de todas las regiones se denomina región factible o espacio de soluciones, que
es un conjunto convexo. Si esta región no es vacía seguimos en el punto siguiente, en caso
contrario, no existe ninguna solución que satisfaga simultáneamente todas las restricciones y
el problema es infactible.
3. Determinar los puntos extremos (aquellos que son intersección de dos o más restricciones)
del espacio de soluciones. Evaluar la función objetivo en esos puntos, y aquel o aquellos que
maximicen (o minimicen) el objetivo, corresponden a las soluciones óptimas del problema.
Ilustraremos este método mediante un ejemplo:
Example Tengamos el problema siguiente:
Maximizar z 2x 1 x2
Sujeto a
5x 1 2x 2 10
3x 1 5x 2 15
x1, x2 0
Solución gráfica de un problema lineal
Los extremos son A 0, 3 ; B 20/19, 45/19 ; C 2, 0 , O 0, 0 con
valores para la función objetivo 3, 85/19, 4, 0 respectivamente. Por tanto el valor
óptimo se encuentra en 20/19, 45/19 . (figura anterior).
Un método gráfico alternativo se tiene a partir de las líneas de isobeneficio (en caso de
maximización) o de isocoste (en el de minimización). Cada isolínea contiene el conjunto de
puntos en los que la función objetivo toma el mismo valor. Notar el hecho de que al ser todas las
restricciones lineales, la región factible es un conjunto convexo y al ser la función objetivo lineal,
una solución óptima estará en uno de los puntos extremos de la región factible.
Cuando dos puntos extremos del conjunto están unidos y son soluciones óptimas del
problema, entonces el problema posee soluciones óptimas alternativas, y podemos afirmar que
todos los puntos que existen en el segmento que une a los dos puntos extremos óptimos son
solución del problema. En este caso el problema posee un número infinito de soluciones óptimas.
Cuando la región factible del problema es vacía, entonces no hay ningún vector x que
satisfaga todas las restricciones simultáneamente y el problema se denomina infactible.
Si alguna de las restricciones no influye en la determinación de la región factible se dice que
es una restricción redundante.
El problema es un modelo no acotado o con solución no acotada cuando la solución óptima
del problema es , es decir para cualquier punto de la región factible, siempre se puede encontrar
otro punto factible que nos dé un menor (mayor en el caso de maximización) valor para la
función objetivo (valor infinito), o también cuando siendo el valor óptimo de la función objetivo
finito, es solución un punto cuyas componentes tienden a infinito (solución infinita). En estos
casos se debería revisar el planteamiento inicial del problema, porque no se puede esperar, por
ejemplo, que con recursos limitados obtengamos beneficios ilimitados.
Ejemplos
Damos a continuación varios ejemplos en 2 dimensiones (para una mejor visualización) de
los posibles tipos de soluciones que podemos encontrar al resolver un problema de programación
lineal.
Example (Soluciones alternativas)
Maximizar z 6x 1 10x 2
Sujeto a
5x 1 2x 2 10
3x 1 5x 2 15
x1, x2 0
Problema lineal con soluciones alternativas
Observamos en la figura que cualquier punto sobre el segmento A B es una
solución óptima del problema.
Example (Problema infactible)
Minimizar z x1 x2
Sujeto a
x1 x2 1
4x 1 2x 2 6
x1, x2 0
Problema lineal infactible
No hay intersección La región factible es vacía (figura anterior). En este caso
convienene examinar nuevamente el problema variando ligeramente las
restricciones iniciales.
Example (Restricciones redundantes)
Maximizar z 2x 1 x2
Sujeto a
x1 x2 2
x1 x2 3
3x 1 2x 2 10
x1, x2 0
Problema lineal con restricciones redundantes
Como se puede apreciar en la figura anterior, las dos últimas restricciones son
redundantes, y podemos prescindir de ellas.
Example (Problema no acotado. Valor infinito)
Maximizar z 2x 1 5x 2
Sujeto a
x1 x2 4
x1 2
x1, x2 0
Problema lineal no acotado (valor infinito)
Está claro a partir de la figura anterior que al maximizar z 2x 1 5x 2 , la solución
sería , , y por tanto el problema es no acotado. El valor de z se puede hacer tan
grande como queramos.
Example (Problema no acotado. Solución infinita)
Minimizar z 10x 1 4x 2
Sujeto a
x1 x2 2
5x 1 2x 2 16
x1, x2 0
Problema lineal no acotado (solución infinita)
El mínimo se alcanza para z 32, que es finito; pero, como se aprecia en la figura
anterior a lo largo de toda la semirecta con origen 4, 2 , hay infinitos puntos, y
también puntos solución cuyas coordenadas tienden a .
