3 PROGRAMACIÓN LINEAL

Vista previa del material en texto

PROGRAMACIÓN LINEAL (PL) 
La Programación Lineal trata de optimizar el valor de una función lineal (llamada función 
objetivo) cuyas variables (llamadas variables de decisión) están sujetas a un conjunto de 
restricciones (que constituyen un sistema de inecuaciones no estrictas). 
Nosotros en este curso nos limitaremos a trabajar con funciones objetivos con dos variables, lo 
cual permitirá resolver los problemas de programación lineal utilizando métodos gráficos. 
Ejemplo de problema de PL: Un taller de artesanía produce figuras sencillas, que vende a 30 €, 
y figuras elaboradas, a 70 €. El personal disponible hace que la producción diaria no pueda ser 
superior a 15 figuras sencillas, a 30 elaboradas, ni a 40 en total. Suponiendo que se vende toda 
la producción, ¿cuántas figuras de cada clase interesará hacer para obtener los máximos 
ingresos? 
Llamemos 𝑥 al número de figuras sencillas a fabricar diariamente, e 𝑦 al número de figuras 
elaboradas a fabricar por día. 𝑥 𝑒 𝑦 son las variables de decisión. 
La función objetivo será la función ingreso diario, que vendrá dada por 𝐼(𝑥, 𝑦) = 30𝑥 + 70𝑦. 
Las restricciones a que están sujetas las variables de decisión son: 
𝑥 ≤ 15; 𝑦 ≤ 30; 𝑥 + 𝑦 ≤ 40; 𝑥 ≥ 0; 𝑦 ≥ 0 
Al conjunto de todas las soluciones (𝑥, 𝑦) del sistema de inecuaciones se le llama región 
factible, que puede ser acotada (si conforma una superficie cerrada del plano) o no acotada (si 
la superficie que conforma es abierta). Las regiones factibles son siempre convexas; es decir, 
el segmento que une dos puntos cualesquiera de la región factible siempre está totalmente 
contenido en ella. 
A cada solución (𝑥, 𝑦) se le llama solución factible. 
La solución óptima es la que optimiza a la función objetivo; es decir, es la solución el 
problema. 
Si entre las restricciones hay alguna que no es relevante, se le llama condición redundante. 
Ejercicios (planteamiento en contexto) 7 (a) de “Programación Lineal” 
Para representar gráficamente la función factible es muy importante que se recuerde lo 
siguiente: 
El conjunto solución de una inecuación de primer grado con dos incógnitas, geométricamente, 
es un semiplano con borde en la recta cuya ecuación es la de la inecuación, pero sustituyendo 
el signo de desigualdad por el del igual. 
Así por ejemplo, para determinar gráficamente el semiplano solución de la inecuación 
2𝑥 − 3𝑦 ≥ −6, representaremos la recta 2𝑥 − 3𝑦 = −6, que pasa por los puntos (-3,0) y (0,2) 
 
Como el punto (0,0) verifica la inecuación, el semiplano solución es el que tiene por borde la 
recta 2𝑥 − 3𝑦 = −6 y contiene al origen de coordenadas (en amarillo en la figura): 
 
 
Ejercicio (Selectividad de 2014).- Represente el recinto que determinan las inecuaciones: 
2𝑥 ≥ 10 + 𝑦; 𝑥 ≤ 2(5 − 𝑦); 𝑦 ≥ 0; 𝑥 ≥ 0 
SOLUCIÓN 
La recta 𝑟1 ≡ 2𝑥 = 10 + 𝑦 pasa por los puntos (0,-10) y (5,0). El semiplano 2𝑥 ≥ 10 + 𝑦 no 
 contiene al punto (0,0). 
La recta 𝑟2 ≡ 𝑥 = 10 − 2𝑦 pasa por los puntos (0,5) y (10,0). El semiplano 𝑥 ≤ 10 − 2𝑦 
contiene al punto (0,0). 
La recta horizontal 𝑟3 ≡ 𝑦 = 0 pasa por el origen (0,0). El semiplano 𝑦 ≥ 0 contiene al punto 
(0,1) 
La recta vertical 𝑟4 ≡ 𝑥 = 0 pasa por el origen (0,0). El semiplano 𝑥 ≥ 0 contiene al punto 
(1,0). 
 
Dibujemos estas rectas: 
 
La región factible es el recinto convexo y acotado limitado por las rectas 𝑟1, 𝑟2 𝑦 𝑟3. Obsérvese 
que la inecuación 𝑥 ≥ 0 es redundante (es irrelevante) 
El Teorema Fundamental de la Programación Lineal afirma que 
 Si la región factible está acotada, el problema siempre tiene, al menos, una solución 
óptima (tanto para maximizar como para minimizar) que se encuentra en uno de los 
vértices de la región factible. Si el valor óptimo coincide en dos vértices consecutivos, el 
problema tiene infinitas soluciones óptimas que serían los puntos correspondientes al 
lado de la región factible que une dichos vértices. 
 Si la región factible es no acotada, el problema puede no tener solución. 
Resolución analítica de un problema de programación lineal con dos variables. 
Seguiremos los siguientes pasos: 
1. Representar gráficamente la región factible, que siempre será convexa. 
2. Obtener las coordenadas de todos los vértices de la región factible. 
3. Si la región factible está acotada, se evalúa la función objetivo en cada uno de los 
vértices obtenidos en el apartado anterior. 
4. Si se trata de maximizar, la solución óptima se encuentra en el vértice que hace mayor 
a la función objetivo; si se trata de minimizar, la solución óptima se encuentra en el 
vértice que hace menor a la función objetivo (no hay que olvidar que si la solución 
óptima se encuentra en dos vértices consecutivos, entonces hay infinitas soluciones: 
todos los puntos del lado de la región factible que une ambos vértices) 
Ejercicios 1, 2, 3, 4, 5, 6, 7(b), 8, 10, 15, 16, 18, 19, 21, 22, 25, 28, 32, 33, 37, 38, 41, 44, 46, 47, 48, 49, 53, 
55, 56, 57, 59 , 62, 63, 64, 65(b), 67, 68, 70, 71, 73(a), 74, 75, 76, 77(b), 80, 81, 85, 86, 87, 93, 95, 98, 99, 
100, 101, 102, 103, 104, 105, 107, 108(b), 109, 110, 111, 112, 114, 116, 117 de “Programación Lineal” 
Ejercicios (en contexto) 9, 11, 12, 13, 14, 17, 20, 23, 24, 26, 27, 29, 30, 31, 34, 35, 36, 39, 40, 42, 43, 45, 
50, 51, 52, 54, 58, 60, 61, 66, 69, 72, 77(a), 78, 79, 82, 83, 84, 88, 89, 90, 91, 92, 94, 96, 97, 106, 108(a), 
113, 115 de “Programación Lineal” 
Resolución gráfica de un problema de programación lineal con dos variables (a utilizar, 
necesariamente, en el caso de región factible no acotada). 
Dada la función objetivo 𝐹(𝑥, 𝑦) = 𝑎𝑥 + 𝑏𝑦 + 𝑐, Llamaremos rectas de nivel de objetivo a los 
puntos del plano en los que la función objetivo toma el mismo valor. Así, serían rectas de nivel 
de objetivo las siguientes: 
𝑎𝑥 + 𝑏𝑦 + 𝑐 = 5
𝑎𝑥 + 𝑏𝑦 + 𝑐 = 10
⋮
 
En general, la ecuación de las rectas de nivel objetivo vendría dada por: 
𝑎𝑥 + 𝑏𝑦 + 𝑐 = 𝑘, 𝑘 ∈ ℝ 
Para cada valor k de la función objetivo, tenemos la correspondiente recta de nivel objetivo. 
Ejemplo para 𝐹(𝑥, 𝑦) = 𝑥 + 𝑦 
 
Observa: 
 Todas la rectas de nivel son paralelas entre sí. 
 En todos los puntos de intersección de una recta de nivel objetivo con la región 
factible el valor de la función objetivo es siempre el mismo; así por ejemplo, en todos 
los puntos del segmento s1, la función 𝐹(𝑥, 𝑦) = 𝑥 + 𝑦 toma el valor 15. 
 Al desplazarlas paralelamente aumenta o disminuye el nivel, el valor de k. Se 
cumple lo siguiente: 
o Las rectas de la forma 𝑎𝑥 + 𝑏𝑦 = 𝑘 (a > 0) aumentan su nivel al trasladarlas 
hacia a la derecha. 
o Las rectas de la forma −𝑎𝑥 + 𝑏𝑦 = 𝑘 (a > 0) disminuyen su nivel al trasladarlas 
a la derecha. (Ver Anexo I) 
 
Para maximizar, tenemos que encontrar la recta de nivel con el mayor valor de k que no se 
salga de la región factible. De existir el máximo (en las regiones acotadas siempre existe), el 
Teorema Fundamental de la Programación Lineal nos asegura que dicha recta pasará por uno 
de los vértices de la región factible. 
Para minimizar, tenemos que encontrar la recta de nivel con el menor valor de k que no se 
salga de la región factible. De existir el mínimo (en las regiones acotadas siempre existe), el 
Teorema Fundamental de la Programación Lineal nos asegura que dicha recta pasará por uno 
de los vértices de la región factible. 
 
 
¿Cómo actuar en la práctica, en el caso de que la región factible no esté acotada? 
 
1. Representar gráficamente la región factible, que siempre será convexa. 
2. Obtener las coordenadas de todos los vértices de la región factible. 
3. Se halla el valor de la función objetivo en cada uno de los vértices. Si se trata de maximizar, 
la solución óptima, de existir, se encuentra en el vértice que hace mayor a la función 
objetivo. Si se trata de minimizar, la solución óptima, de existir, se encuentra en el vértice 
que hace menora la función objetivo (no hay que olvidar que si la solución óptima se 
encuentra en dos vértices consecutivos, entonces hay infinitas soluciones: todos los 
puntos del lado de la región factible que une ambos vértices). 
4. Hay que confirmar que la solución óptima encontrada es realmente la solución óptima, 
para lo que trazaremos una recta de nivel cualquiera (la que nos resulte más fácil de 
dibujar), y la trasladaremos a derecha o a izquierda hasta hacerla pasar por el vértice 
candidato; fijándonos en si en el traslado el nivel de k ha aumentado o ha disminuido, 
podremos confirmar o no la existencia de la solución óptima. 
 
Ejercicios (recintos abiertos) 119, 123 de “Programación Lineal” 
Ejercicios (recintos abiertos en contexto) 118, 120, 121, 122 de “Programación Lineal” 
 
 
ANEXO I 
¿Cómo aumenta o disminuye el valor de k al desplazar paralelamente las rectas de nivel? 
Supongamos que a>0 y b>0. Se presentan varios casos: 
Caso 1.- La función objetivo es de la forma 𝐹(𝑥, 𝑦) = 𝑎𝑥 + 𝑏𝑦. 
𝑎𝑥 + 𝑏𝑦 = 𝑘 ⟺ 𝑦 = −
𝑎
𝑏
𝑥 +
𝑘
𝑏
 
que es una recta de pendiente negativa y ordenada en el origen 
𝑘
𝑏
. Si desplazamos 
paralelamente la recta de nivel hacia la derecha, la ordenada en el origen aumentará, con lo 
que k aumentará y, por tanto, la recta de nivel óptima para maximizar es la que pasa por el 
último punto de contacto con la región factible, al trasladarnos hacia la derecha. 
Si por el contrario, desplazamos paralelamente la recta de nivel hacia la izquierda, la ordenada 
en el origen disminuirá, con lo que k disminuirá y, por tanto, la recta de nivel óptima para 
minimizar es la que pasa por el último punto de contacto con la región factible, al trasladarnos 
hacia la izquierda. 
Ejemplo para 𝐹(𝑥, 𝑦) = 𝑥 + 𝑦 
 
Caso 2.- La función objetivo es de la forma 𝐹(𝑥, 𝑦) = −𝑎𝑥 + 𝑏𝑦. 
−𝑎𝑥 + 𝑏𝑦 = 𝑘 ⟺ 𝑦 =
𝑎
𝑏
𝑥 +
𝑘
𝑏
 
que es una recta de pendiente positiva y ordenada en el origen 
𝑘
𝑏
. Si desplazamos 
paralelamente la recta de nivel hacia la derecha, la ordenada en el origen disminuirá, con lo 
que k disminuirá y, por tanto, la recta de nivel óptima para minimizar es la que pasa por el 
último punto de contacto con la región factible, al trasladarnos hacia la derecha. 
Si por el contrario, desplazamos paralelamente la recta de nivel hacia la izquierda, la ordenada 
en el origen aumentará, con lo que k aumentará y, por tanto, la recta de nivel óptima para 
maximizar es la que pasa por el último punto de contacto con la región factible, al trasladarnos 
hacia la izquierda. 
Ejemplo para 𝐹(𝑥. 𝑦) = −2𝑥 + 3𝑦. 
 
Caso 3.- La función objetivo es de la forma 𝐹(𝑥, 𝑦) = 𝑎𝑥 − 𝑏𝑦. 
𝑎𝑥 − 𝑏𝑦 = 𝑘 ⟺ 𝑦 =
𝑎
𝑏
𝑥 −
𝑘
𝑏
 
que es una recta de pendiente positiva y ordenada en el origen −
𝑘
𝑏
. Si desplazamos 
paralelamente la recta de nivel hacia la derecha, la ordenada en el origen disminuirá, con lo 
que k aumentará y, por tanto, la recta de nivel óptima para maximizar es la que pasa por el 
último punto de contacto con la región factible, al trasladarnos hacia la derecha. 
Si por el contrario, desplazamos paralelamente la recta de nivel hacia la izquierda, la ordenada 
en el origen aumentará, con lo que k disminuirá y, por tanto, la recta de nivel óptima para 
minimizar es la que pasa por el último punto de contacto con la región factible, al trasladarnos 
hacia la izquierda. 
Ejemplo para 𝐹(𝑥. 𝑦) = 2𝑥 − 3𝑦. 
 
Caso 4.- La función objetivo es de la forma 𝐹(𝑥, 𝑦) = −𝑎𝑥 − 𝑏𝑦. 
−𝑎𝑥 − 𝑏𝑦 = 𝑘 ⟺ 𝑦 = −
𝑎
𝑏
𝑥 −
𝑘
𝑏
 
que es una recta de pendiente negativa y ordenada en el origen −
𝑘
𝑏
. Si desplazamos 
paralelamente la recta de nivel hacia la derecha, la ordenada en el origen aumentará, con lo 
que k disminuirá y, por tanto, la recta de nivel óptima para minimizar es la que pasa por el 
último punto de contacto con la región factible, al trasladarnos hacia la derecha. 
Si por el contrario, desplazamos paralelamente la recta de nivel hacia la izquierda, la ordenada 
en el origen disminuirá, con lo que k aumentará y, por tanto, la recta de nivel óptima para 
maximizar es la que pasa por el último punto de contacto con la región factible, al trasladarnos 
hacia la izquierda.