1
00:00:12,400 --> 00:00:18,339
Hola a todos, soy Raúl Corraliza, profesor de matemáticas de bachillerato en el IES

2
00:00:18,339 --> 00:00:23,379
arquitecto Pedro Gumiel de Alcalá de Henares, y os doy la bienvenida a esta serie de videoclases

3
00:00:23,379 --> 00:00:27,260
de la unidad AL4 dedicada a la programación lineal.

4
00:00:31,079 --> 00:00:36,579
En la videoclase de hoy estudiaremos la resolución de problemas de programación lineal.

5
00:00:37,579 --> 00:00:50,869
En esta videoclase vamos a discutir la resolución de problemas de programación lineal.

6
00:00:51,070 --> 00:00:56,130
Voy a utilizar como ejemplo el mismo ejercicio 1a que utilicé como ejemplo en la videoclase anterior.

7
00:00:56,969 --> 00:01:04,730
La base para el algoritmo que vamos a desarrollar en esta videoclase es el teorema fundamental de la programación lineal,

8
00:01:05,090 --> 00:01:07,390
que por eso se llama fundamental, porque es clave para todo ello.

9
00:01:08,409 --> 00:01:12,930
Lo primero que vamos a hacer, una vez que tengamos ya descritas las variables, que es lo más importante,

10
00:01:13,409 --> 00:01:17,370
la función objetivo y el conjunto de restricciones de nuestro problema de programación lineal

11
00:01:17,370 --> 00:01:24,010
es utilizar ese conjunto de restricciones para determinar gráficamente la región factible.

12
00:01:24,469 --> 00:01:30,750
Y vamos a distinguir tres situaciones una vez que tengamos representada la región factible

13
00:01:30,750 --> 00:01:35,129
y el tratamiento que hagamos del problema va a ser distinto dependiendo en cuál nos encontremos.

14
00:01:35,810 --> 00:01:39,049
Distinguiremos el caso en el que la región factible es un conjunto vacío.

15
00:01:39,810 --> 00:01:44,230
En ese caso nos encontramos ante un problema infactible que no tiene solución y con esto hemos terminado.

16
00:01:44,230 --> 00:01:51,370
Y vamos a distinguir el caso en el que tenemos una región poligonal convexa y el caso en el que tenemos un politopo convexo.

17
00:01:51,450 --> 00:01:58,469
En el primer caso esta región va a estar acotada y en el segundo caso esta región, el politopo convexo, no va a estar acotado.

18
00:01:59,090 --> 00:02:03,310
Vamos a pasar a nuestro ejemplo a ver cómo representamos gráficamente la región práctica.

19
00:02:06,129 --> 00:02:13,629
En el ejemplo que estamos resolviendo se nos pide maximizar la función objetivo rendimiento energético en calorías 600x más 400y,

20
00:02:13,629 --> 00:02:20,270
400y, sujeto a, en primer lugar, las dos restricciones triviales x mayor o igual que 0 e y mayor o igual que 0

21
00:02:20,270 --> 00:02:26,750
y las otras dos restricciones x más y menor o igual que 120, 3x más y menor o igual que 150.

22
00:02:27,590 --> 00:02:34,090
Las restricciones triviales x mayor o igual que 0 y mayor o igual que 0 nos indican que nos centremos en el primer cuadrante

23
00:02:34,090 --> 00:02:36,110
dentro de esta representación cartesiana.

24
00:02:37,110 --> 00:02:44,990
Fijaos en que el primer cuadrante viene delimitado por los semiejes x positivo con ecuación y igual a 0

25
00:02:44,990 --> 00:02:48,530
e y positivo con ecuación x igual que 0.

26
00:02:49,150 --> 00:02:53,150
Y el punto de corte es el origen del sistema de referencia, el punto 0, 0.

27
00:02:53,250 --> 00:02:55,509
x mayor o igual que 0, y mayor o igual que 0.

28
00:02:56,030 --> 00:02:57,770
Tenemos que utilizar el primer cuadrante.

29
00:02:58,409 --> 00:03:03,370
En cuanto a la siguiente restricción, x más y menor o igual que 120,

30
00:03:03,370 --> 00:03:10,789
lo primero que vamos a hacer siempre es representar la línea recta que corresponde con x más y igual

31
00:03:10,789 --> 00:03:17,110
a 120, opiando la desigualdad y tomando siempre la igualdad estricta. Hay distintas formas de

32
00:03:17,110 --> 00:03:21,849
representar esa recta. Podemos hacer una tabla de valores dando valores arbitrarios, viene a x,

33
00:03:21,969 --> 00:03:27,789
viene a y, calculando la otra variable. A mí lo que me gusta hacer es siempre dar, por ejemplo,

34
00:03:27,789 --> 00:03:40,330
En primer lugar, el valor x igual a 0. En ese caso, y es igual a 120. Y de esta forma tan sencilla, tengo que el punto 0, 120, este que se encuentra aquí, es uno de los puntos que pertenecen a esta recta.

35
00:03:40,870 --> 00:03:52,509
A continuación voy a dar el valor y igual a 0, con lo que tengo que x es igual a 120. Y tengo, de esta forma tan simple, que el punto 120, 0, este que tengo aquí, es también otro punto de esta recta.

36
00:03:52,509 --> 00:03:58,830
No tengo más que unir esos dos puntos. Esta es la recta. Como veis aquí, x más y igual a 120.

37
00:04:00,330 --> 00:04:07,110
Y yo lo que necesito no es esta recta, sino el semiplano que cumple que x más y es menor o igual que 120.

38
00:04:08,289 --> 00:04:13,289
Tengo varias posibilidades para elegir cuál de los dos semiplanos, el que está hacia arriba y a la derecha de la recta,

39
00:04:13,569 --> 00:04:16,370
o bien hacia abajo y a la izquierda de la recta, se corresponde.

40
00:04:17,149 --> 00:04:22,490
Una de las formas más sencillas, y es la que yo voy a utilizar, es tomar un punto cualquiera del plano,

41
00:04:22,610 --> 00:04:25,370
que yo sepa que está en uno de los dos semiplanos claramente,

42
00:04:26,050 --> 00:04:29,189
y voy a tomar el origen del sistema de referencia, el punto 0, 0,

43
00:04:29,610 --> 00:04:34,050
sustituir las coordenadas y comprobar si se cumple o no se cumple la desigualdad.

44
00:04:34,629 --> 00:04:40,430
En este caso, si sustituyo 0, 0, 0 más 0 que es igual a 0 es realmente menor o igual que 120,

45
00:04:41,009 --> 00:04:45,689
y eso quiere decir que ese punto que yo he elegido y el semiplano que lo contiene,

46
00:04:45,689 --> 00:04:50,410
o sea, de la recta hacia abajo y hacia la izquierda, cumplen esta desigualdad.

47
00:04:51,230 --> 00:04:55,750
Voy a hacer lo mismo con la otra. 3x más y menor o igual que 150.

48
00:04:56,529 --> 00:05:01,089
Voy a representar en primer lugar la recta 3x más y igual a 150,

49
00:05:01,529 --> 00:05:04,449
obviando la desigualdad, tomándole igualdad estricta.

50
00:05:05,069 --> 00:05:08,250
Si tomo x igual a 0, tengo y igual a 150.

51
00:05:08,670 --> 00:05:11,990
El punto 0, 150, es este que tengo aquí en el eje de las y.

52
00:05:12,610 --> 00:05:18,089
Si hago y igual a 0, tengo 3x igual a 150, o sea que x es igual a 50.

53
00:05:18,649 --> 00:05:24,269
Y entonces el punto 50, 0, este que tengo aquí sobre el eje de las x, también es un punto de esa recta.

54
00:05:25,430 --> 00:05:27,370
Trazo la recta que une esos dos puntos.

55
00:05:28,009 --> 00:05:33,149
Todos estos puntos cumplen 3x más y igual a 150, como veis, y tengo la misma situación.

56
00:05:33,589 --> 00:05:40,930
Debo elegir cuál de los dos semiplanos, el que está hacia arriba y hacia la derecha, hacia abajo y hacia la izquierda, cumple la desigualdad.

57
00:05:41,509 --> 00:05:57,910
Vuelvo a tomar el punto 0,0, sustituyo 3 por 0 más 0 es igual a 0, que es menor o igual que 150, así que ese punto y el semiplano que lo contiene, el que está con respecto de esta recta hacia abajo y hacia la izquierda, cumplen con la desigualdad y no el otro.

58
00:05:58,910 --> 00:06:05,189
¿Cuál es la región factible? Pues la delimitada por los segmentos que unen el origen del sistema

59
00:06:05,189 --> 00:06:11,290
de referencia y este punto A, este punto A y este punto B, este punto B y este punto C,

60
00:06:11,829 --> 00:06:18,250
este punto C y el origen del sistema de referencia. Es una región poligonal convexa la que viene

61
00:06:18,250 --> 00:06:23,870
sombreada en azul dentro de este gráfico y que viene delimitada por esos segmentos rectos que

62
00:06:23,870 --> 00:06:31,180
acabo de comentar. Una vez que hemos determinado gráficamente la región factible, el siguiente

63
00:06:31,180 --> 00:06:36,639
paso es determinar analíticamente las coordenadas de los vértices de la región factible. No basta

64
00:06:36,639 --> 00:06:42,920
con tener determinado cuáles son, sino que necesitamos cuáles son sus coordenadas. Para

65
00:06:42,920 --> 00:06:48,800
determinar analíticamente las coordenadas de los vértices, lo que hacemos es fijarnos en cuáles

66
00:06:48,800 --> 00:06:55,759
son las rectas que forman los lados cuya intersección definen el vértice. Por ejemplo,

67
00:06:55,759 --> 00:06:59,779
El más sencillo de todos aquí es el origen del sistema de referencia, 0, 0.

68
00:07:00,360 --> 00:07:06,240
Es la intersección de las rectas x igual a 0 e y igual a 0 que dan las restricciones triviales.

69
00:07:07,000 --> 00:07:13,399
El vértice A sería la intersección de la recta x igual a 0, es la ecuación del eje de las y,

70
00:07:13,560 --> 00:07:16,879
y esta recta que era x más y igual a 120.

71
00:07:17,639 --> 00:07:23,060
Ya tengo que x es igual a 0, sustituyo y igual a 120, pues es el punto 0, 120.

72
00:07:24,060 --> 00:07:28,759
Fijaos que con la técnica que utilicé para representar gráficamente esas rectas,

73
00:07:28,860 --> 00:07:34,060
que me van a dar en última instancia los segmentos que delimitan la región poligonal convexa,

74
00:07:34,939 --> 00:07:42,120
este punto, el 0, 120, ya lo había determinado, era uno de los que utilicé para poder representar la recta x más y igual a 120.

75
00:07:42,860 --> 00:07:49,939
De igual manera, este punto c, el vértice c, ya tenía de antes cuáles eran sus coordenadas.

76
00:07:50,379 --> 00:08:01,600
Podría pensarlo como es el punto de corte de la recta con ecuación y igual a 0, que sería el eje de las x, y esta recta con ecuación 3x más y igual a 150.

77
00:08:02,379 --> 00:08:09,600
Si sustituyo y igual a 0, tengo 3x igual a 150, así que x es igual a 50 y este punto c será el 50 a 0.

78
00:08:09,600 --> 00:08:19,540
Pero os recuerdo que tal y como había determinado la forma en la que había determinado los puntos que formaban estas rectas, este punto 50 a 0 ya lo había determinado de antes.

79
00:08:19,939 --> 00:08:31,560
El que todavía no tengo son las coordenadas de este punto B. Es la intersección de las rectas 3x más y igual a 150, esta, y esta otra de aquí, x más y igual a 120.

80
00:08:32,039 --> 00:08:39,100
Tengo que resolver un sistema de dos ecuaciones con dos incógnitas. Insisto, 3x más y igual a 150, x más y igual a 120 en este caso.

81
00:08:39,500 --> 00:08:47,000
Puedo utilizar cualquiera de los sistemas que hemos visto en la ESO, sistemas métodos, ya sea reducción, sustitución, igualación, etc.

82
00:08:47,000 --> 00:08:58,460
Si hemos hecho un dibujo muy limpio, muy claro, puedo incluso utilizar el método gráfico y de cualquiera de las maneras llegaremos a la solución, a las coordenadas de este vértice B, 15, 105.

83
00:09:01,889 --> 00:09:09,870
Una vez que tenemos las coordenadas de los vértices de la región factible, podemos pasar al último paso para poder determinar cuál es la solución del problema.

84
00:09:10,590 --> 00:09:15,330
Se nos abren dos posibilidades. Una de ellas es el denominado método gráfico.

85
00:09:15,330 --> 00:09:33,889
En este caso lo que haríamos sería utilizando la función objetivo, puesto que ya hemos hecho uso del conjunto de restricciones, utilizando la función objetivo, trazar las curvas de nivel, en este caso como indico aquí serán rectas paralelas dado que la función objetivo es lineal, que pasan por los vértices de la región factible.

86
00:09:33,889 --> 00:09:45,769
Y nos quedaremos, como solución óptima, con el vértice que corresponda bien a la mayor o bien a la menor curva de nivel, dependiendo de si estamos en un problema de maximizar o bien de minimizar.

87
00:09:46,649 --> 00:09:54,029
Nosotros no emplearemos el método gráfico, sino que, con carácter general, utilizaremos la segunda posibilidad, que es el método analítico.

88
00:09:54,029 --> 00:10:12,029
En lugar de representar las curvas de nivel lo que vamos a hacer es calcular el valor de la función objetivo en cada uno de los vértices de la región factible y nos quedaremos como solución óptima como la solución que corresponde al valor óptimo máximo o mínimo dependiendo de cuál sea el problema que tengamos.

89
00:10:12,029 --> 00:10:33,330
En el caso que estamos trabajando, la función objetivo a maximizar es el rendimiento energético en calorías dado por la función 600X más 400Y y los vértices son los que acabamos de determinar O00, A0120, B15105 y C500.

90
00:10:33,330 --> 00:10:54,769
Así que vamos a hacer una tabla en la que tenemos los vértices identificados por su etiqueta O, A, B, C, las coordenadas X e Y y sustituyendo en la función objetivo vamos a calcular el contenido energético en calorías, os recuerdo que la función objetivo tiene unidades, que corresponden a estos valores de X y de Y.

91
00:10:54,769 --> 00:11:03,129
vieja. Así que, por ejemplo, vuelvo atrás, sustituyo el vértice O. 600 por 0 más 400 por 0 es igual a 0,

92
00:11:03,690 --> 00:11:12,129
este valor que tengo aquí. Sustituyo el vértice A. 600 por 0 más 400 por 120 es este valor 48.000

93
00:11:12,129 --> 00:11:19,049
que tengo aquí. Y así con todos. Una vez que tengo estos resultados, me pregunto, ¿qué quiero hacer?

94
00:11:19,570 --> 00:11:24,710
Maximizar la función objetivo. Pues lo que debo hacer es buscar cuál es el vértice en el cual la

95
00:11:24,710 --> 00:11:30,090
función objetivo alcanza su valor máximo. En este caso tengo uno único, que es el

96
00:11:30,090 --> 00:11:38,570
vértice b, con un valor de 51.000 calorías. ¿Cuál es la solución óptima para este

97
00:11:38,570 --> 00:11:45,090
problema de programación lineal? El vértice b. En concreto, debo decir que se

98
00:11:45,090 --> 00:11:50,629
deben preparar 15 raciones de tipo a, que es el valor de x, y 105 raciones de tipo

99
00:11:50,629 --> 00:11:58,110
b. Puesto que la solución, dado que me han hecho una pregunta con texto, determina el número de

100
00:11:58,110 --> 00:12:06,250
raciones d, pues no puede ser vértice b, no puede ser 105, 105, no puede ser x igual a 15 y igual a

101
00:12:06,250 --> 00:12:12,649
105, sino tiene que ser, necesitas preparar tantas, en este caso 15 raciones de tipo a y 105 raciones

102
00:12:12,649 --> 00:12:17,909
de tipo b. También se nos pedía calcular cuál era el rendimiento máximo total. Bien, pues lo vamos a

103
00:12:17,909 --> 00:12:23,730
Es decir, para obtener un rendimiento máximo total igual a, pues en este caso, 51.000 calorías.

104
00:12:24,789 --> 00:12:27,490
Esto no es más que un ejemplo, hay distintas posibilidades.

105
00:12:28,370 --> 00:12:34,610
Tal y como mencioné en la videoclase anterior, podría haberse dado la circunstancia en la que sean dos vértices consecutivos

106
00:12:34,610 --> 00:12:39,750
en donde se alcance el mismo valor máximo, o podría haber sido mínimo, de la función objetivo.

107
00:12:39,750 --> 00:12:47,769
En ese caso, la solución óptima no son los dos vértices solo, sino todos los puntos que se encuentran en el segmento,

108
00:12:47,769 --> 00:12:54,370
que los unen podría haber sido que tuviéramos como región factible un

109
00:12:54,370 --> 00:12:59,769
politopo convexo y que la solución fuera no está acotado el problema puesto que

110
00:12:59,769 --> 00:13:03,889
valores arbitrariamente grandes de x y de y fueran aquellos que maximizarán o

111
00:13:03,889 --> 00:13:09,370
minimizarán la función objetivo todos esos casos los discutiremos en los

112
00:13:09,370 --> 00:13:13,370
ejercicios propuestos que resolveremos en clase y que también resolveremos en

113
00:13:13,370 --> 00:13:21,570
alguna de las videoclases posteriores. En el aula virtual de la asignatura tenéis

114
00:13:21,570 --> 00:13:27,269
disponibles otros recursos y cuestionarios. Asimismo, tenéis más información en las

115
00:13:27,269 --> 00:13:32,470
fuentes bibliográficas y en la web. No dudéis en traer vuestras dudas e inquietudes a clase

116
00:13:32,470 --> 00:13:36,529
o al foro de dudas en el aula virtual. Un saludo y hasta pronto.