Activa JavaScript para disfrutar de los vídeos de la Mediateca.
AL4. 1. Introducción - Contenido educativo
Ajuste de pantallaEl ajuste de pantalla se aprecia al ver el vídeo en pantalla completa. Elige la presentación que más te guste:
Hola a todos, soy Raúl Corraliza, profesor de matemáticas de bachillerato en el IES
00:00:12
arquitecto Pedro Gumiel de Alcalá de Henares y os doy la bienvenida a esta serie de videoclases
00:00:18
de la unidad AL4 dedicada a la programación lineal. En la videoclase de hoy estudiaremos
00:00:23
los elementos fundamentales de la programación lineal.
00:00:34
En esta videoclase iniciamos el estudio de la programación lineal. Como podéis leer
00:00:38
en un problema de programación lineal buscamos optimizar, ya sea maximizar o minimizar, una
00:00:51
determinada función que llamaremos función objetivo, que va a ser una función lineal,
00:00:57
de ahí el nombre programación lineal. Nosotros vamos a trabajar habitualmente problemas con
00:01:02
dos variables a las que llamaremos siempre x e y, de tal forma que las funciones objetivo
00:01:06
con las que nosotros trabajaremos van a tomar la forma coeficiente por x más coeficiente
00:01:12
por y, una combinación lineal de esas dos variables. Las variables no van a poder tomar
00:01:16
valores cualesquiera sino que van a estar sujetas a un conjunto de restricciones que va a ser un
00:01:22
sistema de inequaciones lineales, de ahí el nombre de programación lineal. Esas restricciones van a
00:01:27
tomar la forma coeficiente por x más coeficiente por y, combinaciones lineales de las variables,
00:01:33
y vamos a tener dos posibilidades, bien mayor o igual que un término independiente o bien menor
00:01:39
igual que un término independiente. Así pues, para comenzar, para poder expresar de una forma
00:01:45
adecuada en términos matemáticos un problema de programación lineal, lo primero que hemos de hacer
00:01:51
es determinar cuáles son las dos variables con las que estamos trabajando, x e y, determinar cuál es
00:01:55
la función objetivo, que buscamos bien maximizar, bien minimizar y expresarla como combinación lineal
00:02:02
de las dos variables. Y finalmente buscar ese conjunto de restricciones, ese sistema de
00:02:08
en ecuaciones lineales, al cual están sujetas las variables y que deben cumplir necesariamente.
00:02:14
Vamos a ver esto con un ejemplo.
00:02:19
A lo largo de estas videoclases utilizaremos este ejercicio 1a como ejemplo
00:02:24
que vamos a desarrollar para comprender bien cómo funciona la programación lineal.
00:02:28
Como podéis ver, todos estos ejercicios están dados en la forma de un enunciado más o menos largo
00:02:33
que contiene toda la información necesaria para determinar las variables,
00:02:38
la función objetivo a maximizar o minimizar y el conjunto de restricciones. Vamos a leer con
00:02:43
cuidado el enunciado de este ejercicio 1a. Leemos que en una empresa de alimentación se dispone de
00:02:48
24 kilogramos de harina de trigo y 15 kilogramos de harina de maíz, que se utilizan para obtener
00:02:55
dos tipos de preparados A y B. A continuación se nos describen los preparados de tipo A. Se nos
00:03:00
dice que cada ración de preparado A va a contener 200 gramos de harina de trigo y 300 gramos de
00:03:07
harina de maíz con 600 calorías de valor energético. A continuación se nos describe el preparado de
00:03:12
tipo B. Se nos dice que cada ración de B contiene 200 gramos de harina de trigo y 100 gramos de
00:03:18
harina de maíz con 400 calorías de valor energético. Habitualmente en la primera parte del enunciado
00:03:24
vamos a obtener un montón de información numérica, pero hasta que no lleguemos al final y se nos haga
00:03:30
una pregunta no vamos a saber con claridad cuáles son las variables y cuál es la función objetivo y
00:03:35
cuál es el conjunto de restricciones.
00:03:42
Toda la información va a estar ahí codificada,
00:03:43
pero de momento no sabemos quién es quién.
00:03:45
Nos hacemos una idea de qué va y ahora leemos
00:03:48
cuántas raciones de cada tipo hay que preparar
00:03:50
para obtener el máximo rendimiento energético total
00:03:53
y calcula cuál es ese rendimiento máximo.
00:03:56
En la pregunta es donde vamos a obtener la información precisa
00:03:59
de cuáles son las variables, x e y,
00:04:02
y cuál es la función objetivo que queremos bien maximizar, bien minimizar.
00:04:04
Expresamente se nos pregunta
00:04:09
¿Cuántas raciones de cada tipo hay que preparar?
00:04:11
Así pues, llamaremos x a las raciones de preparado de tipo A que necesitamos preparar
00:04:13
e y a las raciones de preparado de tipo B que necesitamos preparar.
00:04:19
Ya tenemos las variables x e y.
00:04:23
Número de raciones de tipo A, número de raciones de tipo B.
00:04:25
Y fijaos, esto es importante.
00:04:29
Número de x es una variable numérica.
00:04:31
No puedo decir x son raciones de tipo A, y son raciones de tipo B.
00:04:34
O peor todavía, X es el preparado A, Y es el preparado B.
00:04:39
X es el número de raciones de tipo A que hay que preparar.
00:04:44
Y es el número de raciones de preparado de tipo B que hay que preparar.
00:04:48
Lo siguiente que se nos decía era para obtener el máximo rendimiento energético total.
00:04:54
Así pues, nuestro objetivo es maximizar una cierta función objetivo
00:05:00
que tenemos que formar calculando cuál será el rendimiento energético total.
00:05:04
Necesitamos encontrar en la parte primera que habíamos leído con toda la información numérica
00:05:10
dónde se encuentra ese rendimiento energético.
00:05:15
Bien, pues aquí tenemos que las raciones de preparado A aportan 600 calorías de valor energético
00:05:19
y las de tipo B aportan 400 calorías de valor energético.
00:05:26
Esto cada ración de preparado A, cada ración de preparado B.
00:05:30
¿Cómo podemos calcular el rendimiento energético total?
00:05:34
Multiplicando el rendimiento de cada ración por el número de raciones.
00:05:38
Así pues, dado que x es el número de raciones de tipo A y y es el número de raciones de tipo B que preparamos,
00:05:42
el rendimiento energético total que buscamos maximizar, por cierto, se calculará multiplicando.
00:05:49
600 por x más 400 por y.
00:05:55
El rendimiento energético es una magnitud, así pues tiene unidades y tendremos que expresarlo así. Nuestra función objetivo es 600 por x más 400 por y en calorías y lo que buscamos es maximizarla.
00:05:59
El resto de información que había contenida en el enunciado va a estar referida a este conjunto de restricciones.
00:06:17
Tenemos que interpretar toda la información que se nos da en términos de un sistema de inequaciones lineales.
00:06:24
Algunas de esas inequaciones que son necesarias, son imprescindibles para resolver correctamente el problema,
00:06:31
en realidad no se nos dan en el enunciado.
00:06:36
Son restricciones que se llaman triviales.
00:06:39
Son tan básicas, tan elementales, que no se nos da información ni se nos menciona.
00:06:42
Pero nosotros tenemos que saber que existen y tenemos que escribirlas.
00:06:46
En este caso en concreto tenemos dos restricciones triviales, que son x mayor o igual que cero, y mayor o igual que cero.
00:06:50
Por su propia naturaleza, x y y son números de raciones que tenemos que fabricar.
00:06:58
Sabemos que van a ser números enteros. Yo puedo fabricar una, dos, tres, ciento cincuenta y siete raciones.
00:07:03
Pero no tiene sentido que el número de raciones que yo fabrique sea un número negativo
00:07:08
Sí puede ser cero, puede ser que no fabrique raciones de tipo A o de tipo B
00:07:14
O de ninguna de las dos, sería una cosa muy rara
00:07:18
Pero lo que no tiene sentido es que yo fabrique un número negativo de raciones
00:07:21
Así pues, x tiene que ser mayor o igual que cero, y tiene que ser mayor o igual que cero
00:07:25
Son restricciones de sentido común, son restricciones triviales
00:07:29
Insisto, no se nos dicen, no se nos da información sobre ella
00:07:33
pero debo escribirlas porque sin ellas no tiene sentido el problema.
00:07:37
El resto de restricciones son no triviales.
00:07:42
No vienen dadas por la propia naturaleza de las variables,
00:07:45
sino que vienen expresadas en términos de la información contenida en el enunciado.
00:07:48
Por ejemplo, leemos que en una empresa de alimentación se dispone de 24 kg de harina de trigo y 15 kg de harina de maíz.
00:07:53
Así pues, yo puedo gastar como mucho hasta 24 kilos de esta harina y como mucho hasta 15 kilogramos de esta otra.
00:08:01
Aquí tengo las dos restricciones que estaba buscando.
00:08:10
¿Cómo sé cuánta harina de trigo o cuánta harina de maíz voy a consumir?
00:08:13
Bueno, pues en la composición de los preparados de tipo A y de tipo B me dan esa información.
00:08:17
Una ración de tipo A consume 200 gramos de harina de trigo y 300 gramos de harina de maíz, de estos 24 y 15 que tenía inicialmente.
00:08:23
Mientras que cada ración de B va a consumir 200 gramos de harina de trigo y 100 gramos de harina de maíz, una vez más, insisto, de los 24 y 15 kilos que tenía inicialmente.
00:08:32
Así pues, tengo dos restricciones que son, como mucho puedo gastar 24 kilos de harina de trigo, como mucho puedo gastar 15 kilogramos de harina de maíz.
00:08:43
Tened cuidado en que las magnitudes con las que estamos trabajando tienen unidades y en este caso no tengo unidades homogéneas.
00:08:51
La composición de cada una de las raciones viene dada en gramos, mientras que la cantidad, la masa total de que dispongo viene dada en kilos.
00:08:59
Así pues, todo en gramos o todo en kilogramos.
00:09:08
Yo, por ejemplo, voy a elegir en este momento utilizar las magnitudes en gramos y entonces voy a escribir las restricciones de esta manera.
00:09:10
Ahora, consumo de harina de trigo. 200 por X, puesto que 200 gramos es la masa de harina de trigo que gasto con los preparados de tipo A, más 200 por Y, nuevamente 200 gramos es la masa de harina de trigo que gasto en cada ración de B, tiene que ser menor o igual que 24.000, puesto que como mucho tengo 24.000 gramos de harina de trigo.
00:09:18
La otra restricción hace referencia a la harina de maíz y escribiría 300 por x más 100 por y menor o igual que 15.000.
00:09:44
Puesto que gasto 300 gramos con cada ración de tipo A, gasto 100 gramos con cada ración de tipo B, como mucho tengo 15.000 gramos de harina de maíz.
00:09:53
¿Cómo lo escribiría a la hora de resolver el ejercicio? Pues como podéis ver.
00:10:05
Variables. X, número de raciones de tipo A. Y, número de raciones de tipo B.
00:10:09
Insisto en que no es X tipo A, Y tipo B, ni siquiera es raciones de tipo A.
00:10:15
Tened cuidado. Número de raciones de tipo A, número de raciones de tipo B.
00:10:22
Función objetivo. Es el rendimiento energético.
00:10:27
La combinación lineal de las variables que forma la función objetivo es 600X más 400Y.
00:10:31
Cuidado con indicar las unidades, en este caso el rendimiento energético está expresado en calorías,
00:10:37
y también importante, esta función objetivo buscamos maximizarla.
00:10:42
Hay dos posibilidades, tenemos que indicar de cuál se trata.
00:10:46
Restricciones, pues aquí viene el conjunto de restricciones,
00:10:50
el conjunto de inequaciones lineales que nos van a dar cuáles son esos valores posibles de las variables.
00:10:52
Tenemos las dos triviales, x mayor o igual que 0, y mayor o igual que 0,
00:10:59
y después las dos que comentaba acerca de las masas de harina de trigo y de maíz consumidas.
00:11:04
Mencionaba hace un momento 200X más 200Y menor o igual que 24.000, 300X más 100Y menor o igual que 15.000.
00:11:09
He añadido otras dos restricciones triviales, y es que la masa de harina de trigo consumida y de trigo, perdón, de harina de maíz consumida
00:11:18
no puede ser un valor negativo, de tal forma que esta masa tiene que ser a su vez mayor o igual que 0.
00:11:26
Estas dos restricciones triviales son redundantes, puesto que si x e y son ambas mayores o iguales que 0,
00:11:33
desde luego 200x más 200y y también 300x más 100y van a ser mayores o iguales que 0.
00:11:40
Pero yo las he añadido para que esté todo completo.
00:11:46
Algo que va a ser habitual es no utilizar las restricciones tal cual con las cifras que nosotros podamos obtener del enunciado,
00:11:50
sino que busquemos trabajar siempre con las inequaciones más sencillas posibles.
00:11:57
De tal forma que siempre que sea posible simplificaremos los coeficientes en las inequaciones, nunca en la función objetivo, pero sí en las restricciones.
00:12:02
Y en este caso, como veis, pues todos los coeficientes de la primera inequación son divisibles por 200, todos los coeficientes de la segunda son divisibles por 100,
00:12:13
y entonces me quedan las restricciones no triviales, x más y menor o igual que 120, 3x más y menor o igual que 150.
00:12:23
Continuamos la videoclase hablando de la región factible.
00:12:32
Es, como podéis leer, el conjunto de puntos del plano que verifican todas las restricciones.
00:12:35
Fijaos que dado que tenemos dos variables x e y, podemos representar toda la información dentro del plano cartesiano xy,
00:12:41
el plano bidimensional al cual estamos acostumbrados.
00:12:49
Con un eje x que pintaremos habitualmente horizontal e y que pintaremos habitualmente vertical.
00:12:51
positivo hacia la derecha positivo hacia arriba lo habitual en el caso de las
00:12:56
matemáticas cada una de estas restricciones
00:13:01
coeficiente por x más coeficiente por y mayor o igual o menor o igual que un
00:13:04
determinado coeficiente va a ser un semiplano dentro del plano xy si
00:13:09
nosotros representáramos la función coeficiente por x más coeficiente por y
00:13:16
idénticamente igual al término independiente obviando la desigualdad
00:13:20
tendríamos una recta y el hecho de tener mayor o igual que o bien menor o igual que el término
00:13:24
independiente lo que hace es que tomemos no sólo la semirrecta sino también uno de los dos
00:13:30
semiplanos. Así pues, los puntos del plano que verifican cada una de las restricciones vienen
00:13:35
dados por un semiplano. La región factible será la intersección de todos estos semiplanos y
00:13:41
dependiendo de cómo sean nos podemos encontrar con dos situaciones. Una región factible que sea
00:13:50
una región poligonal convexa cuando esté acotada o bien un politopo convexo cuando no esté acotado.
00:13:56
Vamos a ver un par de ejemplos. En este primer ejemplo vemos representada la región factible
00:14:04
que corresponde al ejemplo que estamos desarrollando, al ejercicio 1a. La primera restricción que
00:14:12
teníamos era x mayor o igual que 0. Si representamos la recta x igual a 0, se corresponde con el eje
00:14:17
de las y y el semiplano con x mayor o igual que 0 se corresponde con el semiplano a la derecha del
00:14:23
eje de las y, incluyéndolo. La recta y igual a 0 se corresponde con el eje de las x y el
00:14:29
semiplano que tiene las y mayor o igual que 0 se corresponde con el semiplano por encima del eje
00:14:37
de las x incluyendo. Si representamos la recta x más y igual a 120 lo que tenemos es esta recta
00:14:43
que vemos aquí y todos los puntos con x más y menor o igual que 120 son los que se encuentran
00:14:51
hacia debajo de esta recta incluyéndola. Y si representamos la recta 3x más y igual a 150
00:14:56
tendríamos esta otra recta que tenemos aquí. Los puntos del plano que verifican 3x más y menor o
00:15:03
igual que 150, son los que están hacia la izquierda de esta recta, incluyéndola, y entonces los puntos
00:15:09
del plano que cumplen simultáneamente esas cuatro restricciones, x mayor o igual que 0, y mayor o
00:15:15
igual que 0, x más y menor o igual que 120, 3x más y menor o igual que 150, es esta región que tenemos
00:15:21
aquí sombreada de azul, limitada por todos estos segmentos rectos. De ahí el nombre, región poligonal,
00:15:28
puesto que los límites son segmentos rectos
00:15:36
y lo que tenemos es un polígono convexo
00:15:40
puesto que este polígono es un polígono convexo.
00:15:43
No siempre nos encontraremos con una región acotada, limitada
00:15:46
como es esta, sino que en alguna situación
00:15:49
nos podemos encontrar con una región como esta que tenemos aquí
00:15:52
en donde valores arbitrariamente grandes de x y de y
00:15:55
formen parte de la región objetivo.
00:15:59
En este caso tenemos una limitación
00:16:02
que sería esta semirrecta, este trozo del eje de las íes, estos dos segmentos rectos, la otra
00:16:04
limitación, la otra frontera de la región sería esta otra semirrecta que incluye una parte del eje
00:16:10
de las x, pero no hay limitación hacia arriba y hacia la derecha, hacia valores arbitrariamente
00:16:15
grandes de x y de y. En este caso las fronteras siguen siendo segmentos o semirrectas y en este
00:16:20
caso no tenemos una región poligonal, puesto que no está acotada, sino que a esta figura le llamaremos
00:16:26
politopo convexo. Continuamos esta video clase con la última definición que
00:16:32
necesitamos, la de solución óptima. En un programa de programación lineal buscamos
00:16:39
optimizar una función objetivo. Bien, pues la solución óptima va a ser el punto de
00:16:43
la región factible, de ese conjunto de puntos de plano donde se verifican
00:16:48
simultáneamente todas las restricciones, donde la función objetivo alcanza ese
00:16:52
valor máximo o mínimo que estamos buscando. ¿Dónde podemos buscar la
00:16:56
solución óptima. Hay un teorema que es el teorema fundamental de la programación lineal que nos dice
00:17:01
que si un problema de programación lineal tiene solución óptima hay un vértice de la región
00:17:07
factible donde se alcanza dicha solución óptima. Y esto nos va a dar una idea de cómo resolver los
00:17:12
problemas de programación lineal. ¿Dónde vamos a buscar la solución óptima? En los vértices de la
00:17:20
región factible. De tal forma que en la próxima videoclase, en donde hablemos de la resolución de
00:17:27
problemas de programación lineal, veremos que uno de los pasos que tenemos que seguir es, una vez
00:17:32
tenemos la región factible, determinar los vértices, puesto que en alguno de ellos encontrará esa
00:17:37
solución óptima en el caso de que exista. Vamos a finalizar esta videoclase con la clasificación de
00:17:42
los problemas de programación lineal, dependiendo de cuál sea la función objetivo y la región
00:17:50
factible del problema. Tenemos problemas que se llaman infactibles, que son aquellos en
00:17:55
los que la región factible es el conjunto vacío. No hay ningún punto del plano que
00:18:00
verifique simultáneamente todas las restricciones. Y llamaremos factible a un problema de programación
00:18:05
lineal con región factible que no esté vacía. Hay al menos uno, posiblemente infinitos puntos
00:18:11
del plano, que verifican simultáneamente todas las restricciones. Si un problema de
00:18:17
formación lineal es factible habrá al menos un punto donde se alcance la solución óptima,
00:18:23
posiblemente. Esa solución óptima puede ser única, en cuyo caso tenemos un problema factible con
00:18:29
solución única, o bien múltiple, puesto que puede darse la circunstancia en que la solución óptima
00:18:36
se alcance no en un único vértice de la región factible, sino en dos vértices adyacentes, de tal
00:18:43
forma que todos los puntos del segmento que unen esos dos vértices adyacentes van a poder ser parte
00:18:49
de la solución factible, perdón, de la solución óptima. De tal forma que en este caso tendríamos
00:18:56
a priori infinitos puntos, los infinitos puntos del segmento que unen esos dos vértices de la
00:19:01
relación factible, en donde se alcanza esa solución óptima. La función objetivo alcanza ese mismo
00:19:06
valor, bien máximo, bien mínimo. Por último nos podemos encontrar con problemas factibles con
00:19:12
solución no acotada. Esto ocurre cuando la región factible no es un polígono convexo acotado, sino
00:19:17
que tenemos un politopo convexo no acotado y resulta que el óptimo se alcanza no en uno de
00:19:25
los vértices donde nos encontramos con la frontera, sino para valores de las incógnitas arbitrariamente
00:19:30
grandes. Con esto que hemos discutido podríamos ya resolver estos ejercicios 1a, b y c. El ejercicio
00:19:36
1a lo he resuelto en esta videoclase como ejemplo, en clase veremos estos ejercicios 1b y 1c y también
00:19:44
en alguna videoclase posterior. En el aula virtual de la asignatura tenéis disponibles otros recursos
00:19:51
y cuestionarios. Asimismo, tenéis más información en las fuentes bibliográficas y en la web. No dudéis
00:20:00
en traer vuestras dudas e inquietudes a clase o al foro de dudas en el aula virtual. Un saludo y hasta pronto.
00:20:07
- Idioma/s:
- Autor/es:
- Raúl Corraliza Nieto
- Subido por:
- Raúl C.
- Licencia:
- Reconocimiento - Compartir igual
- Visualizaciones:
- 10
- Fecha:
- 15 de septiembre de 2024 - 18:28
- Visibilidad:
- Público
- Centro:
- IES ARQUITECTO PEDRO GUMIEL
- Duración:
- 20′ 40″
- Relación de aspecto:
- 1.78:1
- Resolución:
- 1280x720 píxeles
- Tamaño:
- 55.35 MBytes
