Profesor: Rafa González Jiménez

Instituto “Santa Eulalia”

TEMA 3: PROGRAMACIÓN LINEAL ÍNDICE 3.1.- Inecuaciones lineales con 2 incógnitas. 3.2.- Sistemas de inecuaciones lineales con 2 incógnitas. 3.3.- La programación lineal. 3.4.- Solución gráfica de un problema de programación lineal. 3.4.1.- solución gráfica (método gráfico) de un problema de p.l. 3.4.2.- solución algebraica de un problema de p.l. 3.5.- Albunos casos particulares. 3.5.1.- Problemas de programación lineal con múltiples óptimos. 3.5.2.- Problemas de programación lineal con región factible no acotada. 3.5.3.- Problemas de programación lineal con región factible vacía. 3.5.4.- Programación lineal entera. 3.1.- INECUACIONES LINEALES CON 2 INCÓGNITAS. Una inecuación lineal con 2 incógnitas puede tener uno de los siguientes aspectos: ax + ax + ax + ax +

by ≤ by < by ≥ by >

c c c c

La resolución de este tipo de inecuaciones es siempre gráfica (ya lo conoces por el curso pasado), y responde al siguiente esquema práctico: o Considero la recta ax + by = c y procedo a representarla, teniendo en cuenta que el trazo empleado será continuo si la desigualdad fuese de la forma ≤ o ≥ , y será discontinuo en los otros dos casos. o Se determinará cuál de los dos semiplanos originados es la solución; para ello bastará con comprobar un punto cualquier de uno de los 2 semiplanos (sustituyendo para ello sus coordenadas en la inecuación). EJEMPLO: Resuelve − 2 x + y ≤ - 3 . SOLUCIÓN: En primer lugar considero la recta de la forma − 2 x + y = − 3 . Seguidamente, mediante una tabla de valores, obtenemos 2 puntos de dicha recta y la dibujamos (con trazo continuo porque la desigualdad que aparece es “ ≤ ”). Esa recta ha dividido al plano en 2 semiplanos, para ver cuál es la solución se ha de tomar un punto que no esté en la recta, por ejemplo, el (0 , 0). Se procede así: (0 , 0) ⇒ - 2 ⋅ 0 + 0 ≤ - 3

¡FALSO!

Luego el semiplano solución es el que no contiene a este punto y la solución queda como en el dibujo. Matemáticas aplicadas a las Ciencias Sociales II

Tema 3, 1

Profesor: Rafa González Jiménez

Instituto “Santa Eulalia”

3.2.- SISTEMAS DE INECUACIONES LINEALES CON 2 INCÓGNITAS. Para resolver un sistema de inecuaciones con 2 incógnitas se aplica el siguiente esquema: 1º.- Se numeran todas las inecuaciones. 2º.- Se resuelven una a una, dibujando las regiones solución sobre el mismo eje de coordenadas (habrá que cuidar la escala en ambos ejes). 3º.- La intersección de todas las regiones solución será la solución al sistema. x− y ≤ 0 EJEMPLO: Resuelve el sistema  .  y ≥ − 2x SOLUCIÓN: Numeramos las inecuaciones del sistema (para evitar confusiones a la hora de dibujar las soluciones): x− y≤ 0   y ≥ − 2x

(1) x - y ≤ 0 La recta es x – y = 0

(1) (2)

(2) y ≥ 2x La recta es y = 2x

(0,1) ⇒ 0 - 1 ≤ 0 CIERTO (1,1) ⇒ 1 ≥ 2 ⋅ 1 FALSO 3.3.- LA PROGRAMACIÓN LINEAL. Seguramente te habrás pasado toda la E.S.O. y lo que llevas de Bachillerato repitiendo sin cesar la siguiente pregunta a tu sufrido profesor de Mate:

Y esto …. ¿Para qué sirve? Posiblemente serás uno mas de los que engordan las estadísticas que recogen las opiniones de aquellos que dudan de la aplicación práctica de las Matemáticas … … Y sin embargo día a día intentas estudiar lo menos posible, gastar lo máximo posible de tu paga (ahorrando a la vez lo máximo posible), maximizar el tiempo que pasas con tus amigos, o tu novio o tu novia… En fin, resolviendo problemas de programación lineal (¡¡Matemáticas al fin y al cabo!!). ¿Qué es la programación lineal? Se puede definir la programación lineal como una técnica de optimización que permite distribuir los recursos de la mejor forma posible. Optimizar un determinado recurso supone obtener lo mejor de él; la programación lineal comprende, por ello, dos tipos diferentes de problemas: -

MAXIMIZAR: Existen ocasiones en las que lo mejor que se puede conseguir es obtener lo máximo. Por ejemplo: El dinero que te gastas los fines de semana, el número de minutos que hablas por el móvil …

Matemáticas aplicadas a las Ciencias Sociales II

Tema 3, 2

Profesor: Rafa González Jiménez

-

Instituto “Santa Eulalia”

MINIMIZAR: Existen otras ocasiones en las que lo mejor que se puede conseguir es lo mínimo. Por ejemplo: El coste de la factura del móvil, el número de suspensos,…

Pero, ¿Cuál es el aspecto de un problema de programación lineal? La verdad es que no son tan diferentes en su enunciado a los problemas de toda la vida que han amenizado muchas de tus tardes de estudio a lo largo de tu trayectoria como estudiante. Sin embargo, resultan fácilmente identificables; en el enunciado del problema aparecerá en algún momento “maximizar”, “minimizar”, o cualquier sinónimo. A continuación vamos a mostrar un ejemplo que nos servirá para saber más sobre cómo resolverlos: EJEMPLO: Las restricciones pesqueras impuestas por la CEE obligan a cierta empresa a pescar como máximo 2.000 toneladas de merluza y 2.000 toneladas de rape, además, en total, las capturas de estas dos especies no pueden pasar de las 3.000 toneladas. Si el precio de la merluza es de 1.000 cts/kg y el precio del rape es de 1.500 cts/kg, ¿Qué cantidades debe pescar para obtener el máximo beneficio?

En un problema de programación lineal aparecen una serie de elementos que debes conocer. Recuerda que la estructuración correcta de tu problema hará que sumes puntos en la puntuación final del mismo.

VARIABLES DE DECISIÓN: Son el conjunto de variables o incógnitas que representan las decisiones que se deben tomar. Se designan habitualmente por x e y. En el ejemplo: X = número de toneladas de merluza. y = número de toneladas de rape. FUNCIÓN OBJETIVO: Las decisiones que se deben tomar van encaminadas a maximizar o minimizar algo que tomaremos como objetivo. Ese objetivo será una función que relacionará a las dos variables de decisión; tendrá el siguiente aspecto: z = f ( x, y ) . En el ejemplo lo que buscamos maximizar es el beneficio, por lo que z = f(x,y) = 1000x + 1500y. RESTRICCIONES: A lo largo de un problema de programación lineal aparecerán una serie de condiciones que han de satisfacer las variables de decisión y que se expresarán por medio de inecuaciones lineales que recibirán el nombre de restricciones. En el ejemplo:    

Como máximo 2000 toneladas de merluza: luego x 2000 Como máximo 2000 toneladas de rape: luego y 2000 Las capturas de estas dos especies no pueden pasar de las 3000 toneladas: x + y 3000 Además, las horas que dedique a estudiar y divertirse serán siempre positivas, luego x ≥ 0 e y ≥ 0 (estás dos desigualdades son muy comunes).

Matemáticas aplicadas a las Ciencias Sociales II

Tema 3, 3

Profesor: Rafa González Jiménez

Instituto “Santa Eulalia”

REGIÓN FACTIBLE: La región del plano que sea solución del sistema de inecuaciones formado por el conjunto de restricciones recibe el nombre de región factible. Las coordenadas de los puntos que forman parte de dicha región son posibles soluciones del problema. Lo único que hace falta es determinar cuál o cuáles de ellos son soluciones óptimas.

La región factible puede ser de 2 tipos:

REGIÓN FACTIBLE ACOTADA

REGIÓN FACTIBLE NO ACOTADA

La región factible incluye o no los lados y los vértices, según que las desigualdades sean en sentido amplio ( o ) o en sentido estricto (< o >). Si la región factible está acotada, su representación gráfica es un polígono convexo (“”que no tiene picos hacia adentro””) con un número de lados menor o igual que el número de restricciones En el ejemplo anterior, al resolver el sistema de inecuaciones que se obtiene a partir de las restricciones, es decir:

 x ≤ 2000   y ≤ 2000  x + y ≤ ≤ 3000  Se obtiene como región factible:

Cada uno de los puntos que componen la región factible son soluciones posibles al sistema. Pero, ¿Cómo determinar cuál de ellos es el mejor? NOTA: Un problema de P.L. se puede reducir a la mínima expresión indicando únicamente la función a optimizar y las restricciones a cumplir. En el ejemplo anterior, el enunciado se podría reescribir de la siguiente manera: Max s.a.

z = 1000x + 1500y x ≤ 2000 y ≤ 2000 x + y ≤ 3000 x≥ 0 y≥ 0

Matemáticas aplicadas a las Ciencias Sociales II

Tema 3, 4

Profesor: Rafa González Jiménez

Instituto “Santa Eulalia”

3.4.- SOLUCIÓN GRÁFICA DE UN PROBLEMA DE PROGRAMACIÓN LINEAL. SOLUCIÓN ÓPTIMA: La solución óptima de un problema de programación lineal es un punto en el cual la función objetivo alcanza el máximo o el mínimo valor, según sea un problema de maximización o minimización. PRIMER RESULTADO FUNDAMENTAL DE LA PROGRAMACIÓN LINEAL: Si un problema de programación lineal tiene solución óptima, ésta se encuentra en uno de los bordes de la región factible. 3.4.1.- SOLUCIÓN GRÁFICA (MÉTODO GRÁFICO) DE UN PROBLEMA DE P.L. Se trata de un método relativamente rápido. A través de un dibujo se buscará la solución ideal al problema. Tiene un handicap: Depende en exceso de la exactitud del dibujo y puede inducir a errores. Es aconsejable aplicarlo y valorar si el resultado obtenido no plantea dudas de ningún tipo, en caso contrario se deberá acudir a otro método para asegurar el resultado. El procedimiento es el siguiente: 1. Se toma la función objetivo, f(x , y), y se iguala a 0. f(x, y) = 0 De este modo se obtiene la ecuación de una recta. 2. Se dibuja esta recta con trazo discontinuo sobre el mismo gráfico en el que tenemos la región factible. 3. Se trazan paralelas a la misma (rectas de nivel) que pasen por cada uno de los vértices de la región factible y calculamos el valor del corte de estas rectas de nivel con OY. Si se trata de un problema de maximización entonces la solución óptima será aquel punto en el que la recta de nivel correspondiente corte al eje OY en el valor mas alto. Si el problema fuese de minimización entonces se ha de buscar el corte mas bajo. 3.4.2.- SOLUCIÓN ALGEBRAICA DE UN PROBLEMA DE P.L. Existe un segundo método para determinar la solución óptima de un problema de P.L. El método analítico no es tan rápido como el anterior pero, a cambio, es mucho mas fiable. Se aplica así: 1. Se determina la región factible. 2. Se hallan las coordenadas de todos los vértices de la región factible. 3. Se sustituyen dichas coordenadas en la “x” y la “y” de la función objetivo, z = f(x,y), obteniéndose así un valor para z. 4. La solución óptima será el punto que arroje el valor mas alto para z en el caso de problemas de maximización o el que de el mínimo valor de z para los problemas de minimización. 3.5.- ALGUNOS CASOS PARTICULARES. 3.5.1.- PROBLEMAS DE PROGRAMACIÓN LINEAL CON MÚLTIPLES ÓPTIMOS. Existen problemas de P.L. (maximización o minimización) en los cuales hay 2 o mas vértices para los cuáles se alcanza un valor óptimo. En ese c aso se ha de aplicar lo que indica el siguiente resultado: Matemáticas aplicadas a las Ciencias Sociales II

Tema 3, 5

Profesor: Rafa González Jiménez

Instituto “Santa Eulalia”

SEGUNDO RESULTADO FUNDAMENTAL DE LA PROGRAMACIÓN LINEAL: Si la región factible está acotada, entonces el máximo o el mínimo de la función objetivo se encuentra en uno de los vértices de la región factible. Pero si el máximo o el mínimo se encuentran en 2 vértices adyacentes de la región factible entonces la solución factibles serán cada uno de los infinitos puntos que forman la arista que une dichos vértices. EJEMPLO:

Max s.a.

z

x÷ y

x + y≤ 6  x - y ≥ 0   3x + 2y ≥ 6 x≥ 0   y ≥ 0 

SOLUCIÓN: La solución óptima son las coordenadas de los infinitos puntos que componen la arista de la región factible que une (6 , 0) y (3 , 3).

3.5.2.- PROBLEMAS DE PROGRAMACIÓN LINEAL CON REGIÓN FACTIBLE NO ACOTADA. Ya vimos en apartados anteriores que la región factible en un problema de P.L. puede no ser acotada. Este tipo de problema requiere, además del estudio de la función objetivo en los vértices de la región factible, el análisis del comportamiento de la función objetivo en los puntos que componen los lados abiertos de la región. Pudiera ser que en alguno de esos lados la función objetivo no lorara estabilizarse, por lo que habría que considerar la no existencia de solución óptima al problema. EJEMPLO: Min s.a.

z = 7x + 10y 3x + 2y ≥ 18  2x + 8y ≥ 32  x , y∈ Ζ x≥ 0  y ≥ 0 

SOLUCIÓN: El mínimo valor de z se alcanza en el punto (4 , 3).

3.5.3.VACÍA.

PROBLEMAS DE PROGRAMACIÓN LINEAL CON REGIÓN FACTIBLE

Un problema de P.L. encierra en su interior un problema de resolución de sistema de inecuaciones (la determinación de la región factible). Ya conocer por el curso pasado que estos sistemas de inecuaciones pueden no tener solución, o lo que es lo mismo, que lno exista región alguna en el plano que satisfaga simultáneamente todas las inecuaciones. Cuando en un problema de P.L. ocurre lo anterior entonces este problema no tiene solución; no quiere decir que no exista la solución óptima, sino que ni siquiera existe solución alguna. Matemáticas aplicadas a las Ciencias Sociales II

Tema 3, 6

Profesor: Rafa González Jiménez

EJEMPLO: max s.a.

Instituto “Santa Eulalia”

z = 2x + 5y 2x + y ≤ 4  x + 3y ≤ 3   x≥ 4 y ≥ 0

3.5.4.- PROGRAMACIÓN LINEAL ENTERA. Un número importante de problemas de P.L. han de arrojar como solución final un par de valores que no pueden ser decimales (si quiero optimizar número de trabajadores, autocares…). A este tipo de problemas se les llama programación lineal entera (“entera” porque los resultados han de ser enteros). En estos problemas, a la hora de escribir las restricciones, se añade a la derecha la expresión “ x, y ∈ Ζ ”.

FIN TEMA

Matemáticas aplicadas a las Ciencias Sociales II

Tema 3, 7