P.

Lineal

LA PROGRAMACI ON L I NEA L

1. INTRODUCCIÓN: la programación lineal como método de optimación

La complejidad de nuestra sociedad en cuanto a organización general y económica exige
disponer de métodos para la planificación y organización de la industria, de los transportes y para la
asignación de trabajos en forma óptima. La programación lineal (iniciada por Dantzig en 1947), que
es una pequeña parte de todo un cuerpo matemático que se ha venido consolidando en el siglo XX
con el nombre de optimización, abarca métodos de resolución de problemas en los que se buscan
los valores máximos o mínimos de funciones del tipo:
f= a 1x 1 + a 2x 2+....+ a nx n (llamada función objetivo ) cuyas variables x 1,x2 ,...,xn están
sujetas a unas condiciones restrictivas que se expresan por medio de desigualdades.
2 n
Estudiaremos en esta unidad sólo el caso de dos variables y para su resolución métodos grá-
ficos, ya que no se pretende dar una solución general al problema, ni mucho menos agotar todas sus
aplicaciones.
Ejemplo de un problema tipo de programación lineal
Una empresa fabrica dos clases de lápices. De la clase A a 20 ptas. la unidad y de la clase B
a 15 ptas. unidad. En la producción diaria se sabe que: el número de la clase B no supera en 1000
unidades a los de A; entre las dos clases no superan a 3000 unidades y los de la clase B no bajan de
1000 unidades. Hallar el costo máximo y mínimo de la producción diaria.
Vamos a traducir el enunciado al lenguaje algebraico:
Sea x el número de unidades fabricadas por día de la clase A
Sea y el número de unidades fabricadas por día de la clase B
el beneficio obtenido al vender x unidades de A e y envases de B será :
20x + 15y, entonces consideramos la función
f(x,y)= 20x + 15y ,
que llamaremos función objetivo, y queremos hallar x, y para que sea máximo o mínimo; x e y están
sujetas a las siguientes condiciones (restricciones) :
y ≤ x + 1000
x + y ≤ 3000, y ≥ 1000
Además debe ser:

CV 41
P. Lineal

x≥0
Por tanto el problema consiste en hallar x, y de forma que el valor
f= 20x + 15y ( función objetivo ) sea máximo con las condiciones:
y ≤ x + 1000
x + y ≤ 3000
y ≥1000
x ≥0
El conjunto de puntos que cumplen estas condiciones se llama conjunto de puntos factibles (
o región factible).
La solución factible que haga óptima la función objetivo se llama solución óptima.
Planteado el problema veremos a lo largo del tema como resolverlo.
2. Concepto de región factible. Puntos extremos.
Repaso de inecuaciones lineales con dos incógnitas.
*Una inecuación lineal es una desigualdad algebraica del tipo:
ax + by + c ≤ 0 ( ≥; <, ó > )
Sus soluciones serán los pares de números (x,y) que hagan cierta la desigualdad.
Ejemplo: 2x-5y <0 (1,1) es una solución, (1,0) no lo es....
Para resolver las inecuaciones se utilizan las propiedades de las desigualdades:
1) si a ≥ b y b ≥ c entonces a ≥ c
2) si a ≥ b entonces a+c ≥ b+c, para todo c
3) si a ≥ b, y c > 0 a.c ≥ b.c
y c<0 a.c ≤ b.c
Ejemplo 1: La inecuación 2x-y > x-2y+4 es equivalente a x+y-4>0 , por tanto es lineal.
Representación gráfica del conjunto solución.
Proposición. Dada una inecuación equivalente a:
ax + by + c > 0 ó ax + by + c < 0
el conjunto solución es uno de los semiplanos cuya frontera es la recta:
ax + by + c=0 (la llamaremos recta auxiliar)
La inecuación puede escribirse para b≠ 0
− ax c − ax c
y> − (1) y< − (2)
b b b b

CV 42
P. Lineal

y los puntos de la recta auxiliar verifican:

− ax c
y= −
b b
Los puntos del semiplano superior verifican (1) y los del inferior verifican (2) (la demostra-
ción es inmediata).
(2) (1)

Ejemplo 2: Resolver gráficamente la inecuación: 2x-5y <0

Solución
Consideramos la recta 2x-5y=0 y la representamos en el plano
x y
0 0
5 2

La recta divide al plano en dos semiplanos, en este caso, como la inecuación se puede escri-
bir y > 2 x / 5 , la solución es el semiplano superior.
Para señalar que no esta incluida la recta en el conjunto de las soluciones se ha dibujado ésta
con trazo discontinuo. Si estuviera incluida se dibujaría con trazo continuo.
Sistemas de inecuaciones lineales.
*Un sistema de inecuaciones lineales es un conjunto de dos o más inecuacioness.
Resolver un sistema de inecuaciones es encontrar las soluciones comunes a todas ellas.
También la solución es gráfica
Se utilizará la representación gráfica para dar el conjunto solución de un sistema de inecua-
ciones, que será la intersección de los semiplanos. La región del plano que determinan dichas inter-
secciones se llama región factible.
Ejemplo 3:
Representar gráficamente las soluciones del sistema:

y ≤ x + 1000
x + y ≤3000
y ≥1000

CV 43
P. Lineal

x ≥0

*Un conjunto convexo es una zona del plano tal que para dos cualesquiera de sus puntos, el
segmento que los une está contenido íntegramente en dicho conjunto. Es fácil comprobar que la in-
tersección de conjuntos convexos es un conjunto convexo.
Ejercicio 1. Indicar de los siguientes conjuntos cuál es convexo y cuál no lo es.

Un semiplano es un conjunto convexo (trivial la demostración). Por tanto, la solución de un

sistema de inecuaciones (es decir la región factible) es un conjunto convexo (es una región polígona
convexa), incluidos los casos extremos de recta, semirrecta, segmento, punto o vacío (ya que serían
intersecciones de conjuntos convexos).
Puntos extremos de un conjunto poligonal convexo
Los segmentos de frontera que limitan el conjunto solución se denominan bordes o lados y a
sus intersecciones vértices. Los vértices y puntos de los bordes que pertenezcan a la región factible
se llaman puntos extremos.
Las regiones factibles pueden ser cerradas o abiertas, respecto a cada borde o vértice, según
se incluya o no en la solución. Puede ser acotada o no acotada según posea área finita o infinita.
Ejemplo 4: Dado el sistema de inecuaciones:
2x + y ≤ 4
x-y≥0
y≥0
Calcular los puntos extremos de la región factible solución del sistema.
Son las intersecciones
2x+y= 4
x-y =0 Solución (4/3,4/3)
x-y= 0
y=0 Solución (0,0)
2x+y=4
y=0 Solución (2,0)
Ejercicio 2. Comprobarlo gráficamente representando el conjunto solución.
3. La función objetivo y la programación lineal.

CV 44
P. Lineal

Como ya hemos indicado en la introducción los problemas de programación lineal consisten

en hallar los valores óptimos (máximo o mínimo) de una función del tipo
f(x,y)= ax + by + c, llamada función objetivo, cuando las variables están sujetas a unas con-
diciones que vienen expresadas por inecuaciones lineales y eventualmente también por ecuaciones
lineales. Dichas condiciones se denominas las restricciones.
4. Resolución de problemas de programación lineal. Método gráfico.
Como ya se ha comentado para el nivel de este curso sólo se estudiará el método gráfico, que
expongo a continuación:
Consideremos el problema de obtener el valor máximo y mínimo de una función lineal
f = ax + by sujeta a las restricciones:
 a11 x + a12 y + b1 ≥ 0
 a x + a y +b ≥ 0
 21 22 2
R: 
 ......................
a k 1 x + a k 2 y + bk ≥ 0

Una vez representada gráficamente la región factible R, es decir, la solución del sistema de
restricciones, como queremos que f sea óptima en R representamos sobre los mismos ejes la recta:
ax + by = 0 (3),
Todas las rectas ax + by = k son paralelas a (3), y mas alejadas de ella cuanto mas aumenta
k, por lo tanto elegiremos la paralela a ella, con las siguientes condiciones:
-Ha de pasar por alguno de los puntos factibles (ese punto tendrá las coordenadas buscadas)
-Debe estar lo más alejada posible a (3) si buscamos el máximo, o la más próxima si busca-
mos un mínimo.
Pondremos algunos ejemplos que ayudarán a entender el método.
Ejemplo 5.
Hallar el máximo de la función objetivo sujeta a las restricciones .

CV 45
P. Lineal

y≥ 0
y≤x
y≤ 2 - x
Solución
Dibujamos las rectas auxiliares: 2x+3y=5
y=0, y=x, y=2-x

y la región factible que es la parte rayada.

Representamos la recta 2x+3y=0, y las paralelas a ella se observa que la mas alejada es la que toca a R en el
punto (1,1), luego el valor máximo es 5 y se alcanza en el (1,1), que es un vértice de R.
Ejemplo 6. Averiguar si la función lineal f = x + 4y tiene máximo y mínimo sobre el conjunto solución de :
y - x ≥ -3
y+x≥1
Solución
Dibujamos el conjunto solución:

-(-2,-1)

es el área rayada. Vemos que no está acotado.

En el gráfico está dibujada la recta x + 4y = 0 y el haz de rectas paralelas a la misma, observamos que k puede
tomar el valor tan grande como se quiera, por lo que no existe el máximo de f en ese conjunto. El mínimo se alcanza en
el único punto extremo (2,-1) en que f vale -2.

5. Pasos para resolver un problema de programación lineal en el plano.

Los siguientes "pasos" resumen como resolver un problema de p.l. en el plano
Paso 1. Identificar las variables del problema.
Paso 2. Confeccionar una tabla que resuma la información facilitada.
Expresar las restricciones o limitaciones dadas en el problema mediante
un sistema de desigualdades relativo a las variables.
Paso 3. Representación gráfica del sistema de desigualdades, determinando el llama-
do conjunto factible.
Paso 4. Establecer la función objetivo lineal, que deberá ser maximizada o minimizada.
Paso 5. Resolver el problema planteado.

CV 46
P. Lineal

Paso 6. Interpretar los resultados.

Ejemplo 7. Una fábrica de tejidos tiene almacenados 3600 m de tela blanca, 2340 m de tela roja y 1500 m de
tela azul. Para distribuirlas a las sastrerías las empaquetan de dos formas A y B:
paquete A: 30m de tela blanca, 18 de tela roja y 10 de tela azul
paquete B: 20m de tela blanca, 15 roja y 10 azul.
El paquete A cuesta 13500 pta. y el B cuesta 11000 pta. ¿Cuántos paquetes debe hacer de cada tipo para maxi-
mizar los ingresos?.
Solución
Paso 1.
Llamamos x al número de paquetes de tipo a e y al número de paquetes de tipo B.
Paso 2.
nº blanca roja azul
paquete A x 30x 18x 10x
paquete B y 20y 15y 10y
totales 3600 2340 1500

Restricciones
30x + 20y < 3600 R1
18x + 15y < 2340 R2
10x + 10y < 1500 R3
Además cómo el número de paquetes no puede ser negativo se tiene:
x>0
y>0
Paso 3. Dibujamos las rectas auxiliares, r1, r2, r3
x y x y x y
0 180 0 156 0 150
120 0 130 0 150 0
puntos de corte de r1 puntos de corte de r2 puntos de corte de r3
(para no tener que repetir la región factible la pongo sólo en el paso 5)
Paso 4. La función objetivo es:
f(x,y) = 13500x + 11000y
que debe ser maximizada.

CV 47
P. Lineal

Paso 5. Utilizando regla y cartabón se localiza el vértice de la región factible más alejado; es el (60,80).

(0,150) •

(80,60)

•
(120,0)

Paso 6.
La solución es 80 paquetes de A y 60 paquetes de B.

6. Teorema fundamental y cálculo analítico de soluciones.

Sólo se dejará usar este método como comprobación de la solución por el método gráfico
en los caso de que debido a las condiciones (por ejemplo vértices muy próximos) del problema pue-
dan surgir dudas.
Teorema. Si R es un conjunto acotado de soluciones de un sistema de inecuaciones lineales
(conjunto poligonal convexo) con dos incógnitas los valore máximo y mínimo de f, función objeti-
vo, se alcanzan en puntos extremos. (No se demuestra)
Teniendo en cuenta el teorema anterior para resolver un problema de programación lineal,
por el método analítico, haremos lo siguiente:
1) Dibujar la región factible R y ver si está acotada.
2) Hallar los vértices de R.
3) Calcular los valores de f en estos puntos extremos.
El valor máximo de f en estos puntos es el máximo de f en R. el mínimo de f en estos puntos
es el mínimo de f en R.

CV 48
P. Lineal

Ejemplo 8. Resolveremos el ejercicio planteado en la introducción al tema.

La función objetivo es en este caso
f= 20x+15y
La región factible se dibujó en el ejemplo 3.
Los extremos de R son A(0,1000), B(1000,2000), y C(2000,1000).
El valor de f en esos puntos es:
f(0,1000)=15000 , f(1000,2000)=50000, f(2000,1000)=55000, luego el valor máximo de f es 55000 y el míni-
mo 15000.

7. Problemas "tipo" de programación lineal.

El problema de la dieta
El problema siguiente es un caso particular del denominado problema de la dieta, estudiado
por el economista norteamericano Stigler. Se trata de encontrar un mínimo en una región factible no
acotada.
Ejemplo 9. Una persona para recuperarse de una cierta enfermedad tiene que tomar en su alimentación dos
clases de componentes que llamaremos A y B. Necesita tomar 70 unidades de A y 120 unidades de B. El médico le da
dos tipos de dietas en las que la concentración de dichos componentes es:
dieta D1: 2 unidades de A y 3 unidades de B
dieta D2: 1 unidad de A y 2 unidades de B.
Sabiendo que el precio de la dieta D1 es 2500 ptas. y el de la dieta D2 es 1450 ptas. ¿cuál es la distribución óp-
tima para el menor coste?
Solución: lo resolveremos gráficamente.
Sean x e y el número de dietas D1 y D2 respectivamente.
La función objetivo es:
C(x,y) = 2500 x + 1450 y
Las restricciones son :
2x + y ≥ 70
3x + 2y ≥ 120
x ≥ 0 , y≥ 0 (20,30)

x y
0 0
29 -50
Los vértices de la región factible son: (0,60), (20,30) y (40,0)

CV 49
P. Lineal

Se observa en el gráfico que la solución óptima es 20 D1 y 30 dietas D2.

Ejercicio 3. Comprobarlo utilizando el método analítico
Problema del transporte
Fue planteado por Hichcok en 1941. Estudiaremos aquí una versión muy sencilla de este tipo
de problemas de p.l.
Ejemplo 10. Una empresa compra 26 locomotoras a tres fábricas: 9 a A, 10 a B y 7 a C. Las locomotoras deben
comenzar a prestar servicios en dos estaciones distintas: 11 de ellas en la estación N y 15 en la S. Los costes de traslados
son, por cada una, los que se indican en la tabla ( en cientos de miles ):
A B C
N 6 15 3
S 4 20 5

Averigua como conviene hacer el reparto para que el coste sea mínimo.
Solución (método analítico)
sean x e y el número de locomotoras que se mandan a las estaciones A y B respectivamente. La tabla indica el reparto
consiguiente :
A B C
x y 11-(x+y)
9-x 10 - y x+y - 4

Las restricciones se obtiene al obligar que todas estas cantidades sean positivas. Es decir:
x ≥ 0, y ≥ 0
9 -x ≥ 0 ⇒ x ≤ 9
10 - y ≥ 0 ⇒ y ≤10
11 - (x + y )≥ 0 ⇒ x + y ≤ 11
x +y-4≥0 ⇒ x+y≥4
(la restricción y ≥ 0 es redundante).
La función objetivo es el resultado de sumar cada uno de los productos de las 6 cantidades trasladadas por sus
respectivos costes de traslado, es decir:
C(x,y)= 6x + 15 + 3[11 - (x + y)] + 4(9 - x) + 20(10 - y) + 5(x + y - 4)=
C(x,y) = 249 + 4x - 3y

CV 50
P. Lineal

Dibujamos la región factible:

Los vértices son: (0,4), (0,10), (1,10), (9,2), (9,0) y (4,0).

Los costes en los vértices son:
C(0,4)= 236),C(0,10)= 219, C(1,10)= 223, C(9,2)= 279, C(9,0)= 285 y C(4,0)= 265
Por lo tanto el mínimo se obtiene para x= 0, y= 10.
El coste total es de 21 900 000 ptas.
Ejercicio 4. Comprobar el resultado usando el método gráfico).

ACTIVIDADES
A1. Una persona dispone de 1000000 de ptas. para invertir en bolsa. Se decide por los tipos de acciones A y B.
Prevé que las acciones A le rendirán un 11% anual pero que son menos seguras que las acciones B que le rendirán sólo
un 8% anual Por este motivo decide invertir en A un máximo de 600000 ptas. y en acciones B un mínimo de 200000
ptas. Además decide que la cantidad invertida en acciones A sea igual o mayor que la invertida en B. ¿qué cantidades
exactas debe invertir para que el interés anual previsto se el máximo?
A2. Se tienen dos clases de baldosas cuadradas. De la clase A con 2 dm de lado de la clase B con tres dm de
lado. Entre las dos clases no pasan de 20 baldosas y las de la clase B superan o igualan a las de la clase A. ¿Qué superfi-
cie máxima pueden cubrir estas baldosas.
A3. En un problema de programación lineal se desea minimizar la función lineal: 3x+4y+2(10-x)+3(18-y)
con las siguientes restricciones: x≥0, y≥0, 10-x≥0, 18-y≥0, x+y≤13, (10-x)+(18-y)≤15. Se pide:
1) Representación gráfica del conjunto factible.
2) Hallar las coordenadas de todos sus vértices.
3) Hallar todas las soluciones óptimas.
A4. Una furgoneta reparte sacos del mismo tamaño y de los tipos A y B. Los de tipo A pesan 30 kg y los B 20
kg. Por cada saco de A cobra 1000 ptas. y por cada saco de B 700 ptas. ¿Cuántos sacos de cada clase debe transportar
para maximizar ganancias si la furgoneta no puede llevar más de 480 kg de estos sacos y no hay cabida para más de 18?
A5. Un fabricante produce piensos para animales mezclando dos tipos de ingredientes A y B. Cada saco debe
contener al menos 2 kg de proteínas y al menos 4 kg de hidratos de carbono. Cada kg de A contiene 200g de proteínas y
300g de hidratos de carbono y cada kg de B contiene 500g de proteínas y 400g de hidratos de carbono. El ingrediente A

CV 51
P. Lineal

le cuesta a 17 ptas. el kg y el B 24 ptas. ¿Qué cantidad de cada ingrediente debe usar por saco para minimizar los costos
sabiendo que es necesario que cada saco contenga al menos un kg de B?.
A6. En un taller pueden hacer puertas del tipo A y del tipo B. En las de tipo a gastan 2m2de chapa y 5 horas en
su realización, mientras que en las de tipo B gastan 3m2 de chapa y 8 horas en su realización.
Disponen de 570m2 de chapa y pueden utilizar 1480 horas en este trabajo.
Si las ganancias por puerta del tipo A son 8000 ptas. y 14000 ptas. por la del tipo B, ¿cuántas tendrán que ha-
cer de cada tipo para que el beneficio sea máximo.(selectividad Alicante junio 1992).
*A7. Un agricultor tiene que plantar árboles de dos clases A y B en una parcela de 4400m cuadrados de área.
Cada árbol A requiere cuanto menos 25m cuadrados de tierra y uno B, 40m cuadrados. El requerimiento anual de agua
de A es de 30 unidades/árbol y el de B 15 unidades/árbol, disponiéndose como máximo de 3300 unidades. Se estimó
que la razón entre el número de árboles del tipo A al del tipo B no debe ser menor que 6/19 y no mayor que 17/8. Se
espera además que la ganancia por árbol de tipo A sea vez y media la del tipo B. ¿Cuál debe ser el número de árboles a
plantar de cada clase, para que la ganancia sea máxima? (selectividad Alicante 1988)
*A8. Para el tratamiento de cierta enfermedad hay que administrar tres vitaminas que designaremos por X, Y,
Z. A la semana es preciso consumir, al menos, 432 mg de la X, 270 de la Y y 180 de la Z. Esta vitaminas se presentan
en dos preparados: El A con comprimidos de 80 mg, que cuestan 25 ptas. y cuya composición es 20% de X, 40% de Y y
40% de z, y el B cuyos comprimidos pesan 9o mg. cuestan 30 ptas. y de composición 30% de x, 60% de Y y 10% de Z.
¿Qué número de comprimidos de cada preparado harán más económico el tratamiento?.
A9. Una fábrica produce dos tipos de zapatillas de deporte A y B. El precio de un par de la clase A es de 5000
ptas. y el precio de un par de la clase B 4000 ptas. Para que el negocio no resulte ruinoso deben fabricarse no menos de
100 pares de tipo A y no más de 150 de tipo B. Sabemos que no se pueden fabricar más de 305 pares de ambos tipos y
que el número de pares del tipo A debe ser igual o inferior al doble de los fabricados del tipo B.
a) Representar el conjunto factible.
b)Encontrar el valor óptimo que maximiza el beneficio.
c) Dado que el valor óptimo no es entero dar la solución entera más próxima.
A10. Dos yacimientos de oro A y B producen al año 2000 y 3000 kg de mineral de oro, respectivamente, que
deben distribuirse a tres puntos de elaboración C, D y E, que admiten 500, 3500 y 1000 kg de mineral, respectivamente
al año. El coste del transporte en ptas. por kg es:
C D E
A 1000 2000 3000
B 1500 1750 2000
¿Cómo ha de distribuirse el mineral para que el transporte sea lo más económico posible?

CV 52
P. Lineal

EXAMEN PROPUESTO
1. De los siguientes conjuntos del plano indica cuales pueden ser conjuntos factibles y cuales no, ra-
zonando la respuesta.

2. Si el conjunto factible (de un problema de p.l.) viene dado por las inecuaciones:
2x + y < 6
x + 2y < 4
x>0
y>0
y la función objetivo es f(x,y) = 2x + 4y ¿ Puede tener el problema solución única ?. Razona la respuesta.
Comprueba tu afirmación resolviendo el problema por el método gráfico.
3. Un almacén de confección que dispone de 70 camisetas, 120 camisas y 110 pantalones, hace liqui-
dación de existencias. Quiere ponerlo a la venta en dos tipos de lotes: el lote A, formado por 2 camisas, 1
pantalón y 1 camiseta, se venderá a 6000 ptas cada uno; el lote B, formado por 1 camisa, 2 pantalones y 1
camiseta, se venderá a 7000 ptas cada uno. Calcular cuántos lotes conviene que hagan de cada clase para ob-
tener el máximo de ganancias y cuánto dinero ingresarán.

CV 53