PROGRAMACION LINEAL

En infinidad de aplicaciones de la industria, la economa se presenta situaciones en las

que se exige maximizar o minimizar algunas funciones que se encuentran sujetas a
determinadas limitaciones, que llamaremos restricciones.
Se llama programacin lineal al conjunto de tcnicas matemticas que pretenden resolver
la situacin siguiente:
Optimizar (maximizar o minimizar) una funcin objetivo, funcin lineal de varias variables,
sujeta a una serie de restricciones, expresadas por inecuaciones lineales.
Un problema de programacin lineal en dos variables, tiene la siguiente formulacin
estndar:

Pudiendo cambiarse maximizar por minimizar, y el sentido de las desigualdades.

En un problema de programacin lineal intervienen:
La funcin f(x,y) = ax + by + c llamada funcin objetivo y que es necesario optimizar.
En esa expresin x e y son las variables de decisin, mientras que a, b y c son constantes.
Las restricciones que deben ser inecuaciones lineales. Su nmero depende del problema
en cuestin. El carcter de desigualdad viene impuesto por las limitaciones,
disponibilidades o necesidades, que son: inferiores a ... ( menores: < o ); como mnimo de
... (mayores: > o ) .
Tanto si se trata de maximizar como de minimizar, las desigualdades pueden darse en
cualquiera de los dos sentidos.
Al conjunto de valores de x e y que verifican todas y cada una de las restricciones se lo
denomina conjunto (o regin ) factible. Todo punto de ese conjunto puede ser solucin
del problema; todo punto no perteneciente a ese conjunto no puede ser solucin.

La solucin ptima del problema ser un par de valores (x0, y0) del conjunto factible que
haga que f(x,y) tome el valor mximo o mnimo.
En ocasiones utilizaremos las siglas PPL para indicar problema de programacin lineal.
Determinacin de la regin factible
La solucin de un problema de programacin lineal, en el supuesto de que exista, debe
estar en la regin determinada por las distintas desigualdades. Esta recibe el nombre de
regin factible, y puede estar o no acotada.

La regin factible incluye o no los lados y los vrtices, segn que las desigualdades sean en
sentido amplio ( o ) o en sentido estricto (< o >).
Si la regin factible est acotada, su representacin grfica es un polgono convexo con un
nmero de lados menor o igual que el nmero de restricciones.
El procedimiento para determinar la regin factible es el siguiente:
1) Se resuelve cada inecuacin por separado, es decir, se encuentra el semiplano de
soluciones de cada una de las inecuaciones.
Se dibuja la recta asociada a la inecuacin. Esta recta divide al plano en dos regiones o
semiplanos.
Para averiguar cul es la regin vlida, el procedimiento prctico consiste en elegir un
punto, por ejemplo, el (0,0) si la recta no pasa por el origen, y comprobar si las
coordenadas satisfacen o no la inecuacin. Si lo hacen, la regin en la que est ese punto
es aquella cuyos puntos verifican la inecuacin; en caso contrario, la regin vlida es la
otra.
2) La regin factible est formada por la interseccin o regin comn de las soluciones de
todas las inecuaciones.
Como sucede con los sistemas de ecuaciones lineales, los sistemas de inecuaciones
lineales pueden presentar varias opciones respecto a sus soluciones: puede no existir
solucin, en el caso de que exista el conjunto solucin puede ser acotado o no.

Ejemplo 1: Dibujar la regin factible asociada a las restricciones:

Las rectas asociadas son :

Elegimos el punto O(0,0), que se encuentra en el semiplano situado por debajo de la recta.
Introduciendo las coordenadas (0,0) en la inecuacin x + y 4, vemos que no la satisface:
0 + 0 = 0 < 4 . Por tanto, el conjunto de soluciones de la inecuacin es el semiplano situado
por encima de la recta r : x + y = 4

Procedemos como en el paso anterior. Las coordenadas (0,0) satisfacen la inecuacin y 4

( 0 4) . Por tanto, el conjunto de soluciones de la inecuacin es el semiplano que incluye
al punto O.

La recta t asociada a la restriccin pasa por el origen, lo cual significa que si probsemos
con el punto O(0,0) no llegaramos a ninguna conclusin. Elegimos el punto (1,0) y vemos
que no satisface la inecuacin y x ( y = 0 < 1 = x ). Por tanto, el conjunto solucin de esta
inecuacin es el semiplano determinado por la recta t que no incluye al punto (1,0).

La regin factible est formada por los puntos que cumplen las tres restricciones, es decir,
se encuentran en los tres semiplanos anteriores. Como podemos observar en el siguiente
grafico.

Mtodo analtico o Mtodo de los vrtices

El siguiente resultado, denominado teorema fundamental de la programacin lineal, nos
permite conocer otro mtodo de solucionar un programa con dos variables.
En un programa lineal con dos variables, si existe una solucin nica que optimice la
funcin objetivo, sta se encuentra en un punto extremo (vrtice) de la regin factible
acotada, nunca en el interior de dicha regin.
Si la funcin objetivo toma el mismo valor ptimo en dos vrtices, tambin toma idntico
valor en los puntos del segmento que determinan.
En el caso de que la regin factible no es acotada, la funcin lineal objetivo no alcanza
necesariamente un valor ptimo concreto, pero, si lo hace, ste se encuentra en uno de
los vrtices de la regin.
La evaluacin de la funcin objetivo en los vrtices de la regin factible nos va a permitir
encontrar el valor ptimo (mximo o mnimo) en alguno de ellos.

Tipos de soluciones
Los programas lineales con dos variables suelen clasificarse atendiendo al tipo de solucin
que presentan. stos pueden ser:
1) Factibles
Si existe el conjunto de soluciones o valores que satisfacen las restricciones.
A su vez, pueden ser:
a) Con solucin nica
Ejemplo: En una urbanizacin se van a construir casas de dos tipos: A y B. La empresa
constructora dispone para ello de un mximo de 1800 millones de pesos, siendo el coste
de cada tipo de casa de 30 y 20 millones, respectivamente. La Municipalidad exige que el
nmero total de casas no sea superior a 80. Sabiendo que el beneficio obtenido por la
venta de una casa de tipo A es 4 millones y de 3 millones por una de tipo B, cuntas casas
deben construirse de cada tipo para obtener el mximo beneficio?
Variables: x = n de casas tipo A
y = n de casas tipo B
Funcin objetivo: Maximizar Z = f(x,y) = 4x + 3y
Conjunto de restricciones: El coste total 30x + 20y 1800.
La municipalidad impone x + y 80. De no negatividad: x 0, y 0.
Tiene por regin factible la regin coloreada.
Si hallamos los valores de la funcin objetivo en cada uno de los
vrtices:
f(O)
f(C)
f(D)
f(E)

=
=
=
=

f(0,0) = 0
f(60,0) = 240
f(20,60)= 260
f(0,80) = 240

La solucin es nica, y corresponde al vrtice para el que la funcin objetivo toma el valor
mximo.
En este caso es el vrtice D(20,60).
Por tanto se deben construir 20 casas de tipo A y 60 de tipo B.
Con un coste de 260 millones de pesos.

b) Con solucin mltiple

Si existe ms de una solucin....
...
Ejemplo: Maximizar la funcin Z = f(x,y) = 4x + 2y sujeta a las restricciones
2x + y 4 , x - y 1 , x 0 , y 0.

Los valores de la funcin objetivo en cada uno de los vrtices son:

f(O) = f(0,0) = 0 , f(A) = f(1,0) = 4 ; f(B)=f(5/3,2/3) = 8 , f(C) = f(0,4) = 8
La funcin objetivo alcanza el valor mximo en los vrtices B y C, por tanto, en todos los
puntos del segmento BC.
Hay infinitas soluciones, solucin mltiple, que corresponden a los puntos del segmento
situado entre dos vrtices de la regin factible.

c) Con solucin no acotada

Cuando no existe lmite para la funcin objetivo
Ejemplo: Maximizar la funcin Z = f(x,y) = x + y sujeta a las restricciones y 2x , y x
2

Tiene por regin factible la zona coloreada que aparece en la figura, que es una regin no
acotada.
La funcin crece indefinidamente para valores crecientes de x e y.
En este caso no existe un valor extremo para la funcin objetivo, por lo que puede decirse
que el problema carece de solucin.
Para que suceda esta situacin la regin factible debe estar no acotada.

2) No factibles
Cuando no existe el conjunto de soluciones que cumplen las restricciones, es decir, las
restricciones son inconsistentes.
Ejemplo: Maximizar la funcin Z = f(x,y) = 3x + 8y sujeta a las restricciones
x + y 6 , x + y 2 , x 0 , y 0.

No existe la regin factible, ya que las zonas coloreadas que aparecen en la figura son
nicamente soluciones de alguna de las inecuaciones.
Por tanto, el conjunto de soluciones del sistema de desigualdades no determina ninguna
regin factible.
Este tipo de problemas carece de solucin.

EJERCICIOS
1) Maximizar Z = f(x,y) = 3x + 8y
Sujeto a:

2)

3)

4)

5)

4x + 5y 40
2x + 5y 30
x 0
y0

6)

7)

8)

9)

Un estudiante dedica parte de su tiempo al reparto de propaganda publicitaria. La

empresa A le paga 5 ptas. por cada impreso repartido y la empresa B, con folletos
ms grandes, le paga 7 pesetas por impreso. El estudiante lleva dos bolsas: una para
los impresos A, en la que caben 120, y otra para los impresos. B, en la que caben
100. Ha calculado que cada da es capaz de repartir 150impresos como mximo.
Lo que se pregunta el estudiante es: cuntos impresos habr de repartir de cada
clase para que su beneficio diario sea mximo?
En una fbrica de ampolletas se producen dos tipos de ellas, las de tipo normal valen
450 pesos y las halgenas 600 pesos. La produccin est limitada por el hecho de
que no pueden fabricarse al da ms de 400 normales y 300 halgenas ni ms de 500
en total. Si se vende en toda la produccin, cuntas de cada clase convendr
producir para obtener la mxima facturacin?
Una compaa area tiene dos aviones A y B para cubrir un determinado trayecto. El
avin A debe hacer ms veces el trayecto que el avin B pero no puede sobrepasar
120 viajes. Entre los dos aviones deben hacer ms de 60 vuelos pero no menos de
200. En cada vuelo A consume 900 litros de combustible y B 700 litros. En cada viaje
del avin A la empresa gana 300000 ptas. y 200000 por cada viaje del B. Cuntos
viajes debe hacer cada avin para obtener el mximo de ganancias? Cuntos vuelos
deben hacer cada avin para que el consumo de combustible sea mnimo?

RESULTADOS
1) La solucin ptima corresponde al vrtice (0,6) para el que la funcin objetivo tome el
valor mximo.
2) Los vrtices son A(6,0), B(8,0) , C(0,8) , D(0,4) y E(2,2). La funcin toma el mnimo valor
en el vrtice D y vale 8
3) El mximo se alcanza en (8,0) y es 8. El mnimo se alcanza en (0,5) y es 15
4) El mximo se alcanza en (3,3) y es 7. El mnimo se alcanza en (1,1) y es 1.
5) El mximo es 24 y se alcanza en todos los puntos de un segmento. Por tanto, la
solucin no es nica. Una posible solucin es (56/17,60/17)
6) Como Z = x + 2y es paralela a x + 2y - 4 = 0, cualquier punto del segmento que une
(4/3,4/3) con (4,0) maximiza Z, dando el mismo valor , 4
7) 50 de A y 100 de B
8) 200 normales y 300 halgenas
9) La mxima ganancia se obtiene con 120 viajes del avin A y 80 del avin B y es de 52
millones de pesos.
El mnimo consumo se obtiene con 30 viajes de cada avin y es 48000 litros.