Download 2º BT Mat II CS Teoría Álgebra Pág 1 Bloque 1: Álgebra Tema 1
Document related concepts
Transcript
2º BT M at II CS Bloque 1: Álgebra Tema 1: Matrices. 1.1.- Concepto de matriz. Igualdad de matrices. Definición : Una matriz real de orden o dimensión m x n es un conjunto de m x n números reales ordenados en m filas y n columnas encerradas entre paréntesis. a11 a 21 Μ am1 a12 a 22 Μ a m2 ... a1n ... a 2 n Μ Μ ... a mn Las matrices las representaremos con letras mayúsculas A, o de la forma (aij ). Cada a ij indica el elemento de la matriz que se encuentra situado en la fila i columna j. El símbolo (a ij ) designa la matriz completa (al igual que A), mientras que aij representa un elemento cualquiera de la misma. Definición : Dos matrices son iguales cuando tienen la misma dimensión y los elementos que ocupan el mismo lugar en ambas son iguales. En consecuencia, para conocer una matriz hay que especificar claramente su dimensión y cada uno de sus elementos. 1.2.-Ejemplos de matrices. Las matrices se emplean, entre otras muchas cosas, para almacenar información, para describir relaciones, para el estudio de sistemas de ecuaciones, etc, y aparecen de modo natural en Economía (matrices input-Output), Sociología, Psicología (Sociomatrices), Estadística, Geometría, etc. Vamos a ver algunos ejemplos de ellas. M atrices de información : Son aquéllas que presentan la información numérica en forma de tablas. Por ejemplo: Una cadena de tiendas de electrodomésticos dispone de cuatro almacenes. En un determinado momento las existencias de lavadoras, frigoríficos y cocinas son las siguientes: Almacén 1: 12 lavadoras, 8 frigoríficos y 5 cocinas. Almacén 2: 20 lavadoras, 18 frigoríficos y 9 cocinas. Almacén 3: 2 lavadoras, 3 frigoríficos y 15 cocinas. Almacén 4: 7 lavadoras, 6 frigoríficos y 1 cocina . Esos datos pueden organizarse en forma de matriz del siguiente modo: L F C Al1 12 8 5 Al 2 20 18 9 Al 3 2 3 15 Al 4 7 6 1 M atrices asociadas a grafos : Un grafo es aquélla figura que nos permite representar las relaciones existentes entre los elementos de un conjunto. (ordenadores conectados entre sí, redes de transporte de una empresa, un sistema de comunicaciones...). En un grafo, llamamos vértice a cada uno de los objetos que lo forman y ejes a las líneas o flechas que los relacionan. Una de las formas más sencillas de expresar un grafo por medio de matrices es tomar una matriz A de orden n x n, siendo n el número de vértices del grafo y en la que cada elemento a ij será uno si hay un eje que vaya del vértice i al vértice j, y cero en otro caso. Por ejemplo: Los puntos A,B,C y D del gráfico del margen representan a cuatro equipos de rescate de montaña. Las flechas indican las direcciones posibles de comunicación por radio. Por ejemplo, el Teoría Álgebra Pág 1 2º BT M at II CS equipo de rescate D puede comunicar directamente con C pero no con A. El equipo D puede comunicar con A pero a través de C. La matriz asociada al grafo sería , A B C D A B A 0 1 1 0 B 1 0 0 0 C 1 1 0 1 D 0 0 1 0 D C En el caso de que el grafo corresponda a relaciones personales, las correspondientes matrices se llaman Sociomatrices. M atrices asociadas a un sistema de ecuaciones lineales. Consideremos el sistema de ecuaciones 2x-3y + 2z =1. x-y = -2 x + 3y-z = 0 Se llama matriz de coeficientes del sistema y matriz ampliada, respectivamente, a las matrices 2 −3 2 A= 1 −1 0 1 3 −1 y 2 −3 2 1 AM = 1 −1 0 −2 3 −1 0 1 1.3. -Tipos de matrices Definición : Dada una matriz A de orden m x n, se define la matriz traspuesta de A como otra matriz de orden n x m que se obtiene cambiando en A las filas por las columnas, y se denota por At. Atendiendo a la forma de la matriz , definimos Matriz fila es aquélla cuyo orden o dimensión es 1x n, es decir, la que tiene una única fila. Matriz columna es la que tiene orden o dimensión m x 1, esto es, la que tiene únicamente una columna. Matriz cuadrada es la que tiene orden o dimensión n x n, es decir tiene el mismo número de filas que de columnas. En este caso se dice que la matriz es de orden n. Matriz rectangular es toda aquella matriz que no es cuadrada. Las matrices cuadradas constituyen un subconjunto importante dentro del conjunto de las matrices, y por ello existen definiciones propias de este subconjunto. Así, para matrices cuadradas de orden n , se llama Diagonal principal a la formada por los elementos a11 , a22,...,ann Diagonal secundaria a la formada por los elementos aij tales que i + j = n +1 De igual modo, una matriz cuadrada de orden n diremos que es: Triangular superior si todos los elementos que están por debajo de la diagonal principal son cero. Triangular inferior si todos los elementos que están por encima de la diagonal principal son cero. Simétrica si los elementos simétricos respecto a la diagonal principal son iguales, esto es, aij =aji ∀ i, j . Antisimétrica si aij = -aji ∀ i, j. Por tanto, la diagonal principal de una matriz antisimétrica es la formada por ceros. Teoría Álgebra Pág 2 2º BT M at II CS Atendiendo a los elementos de la matriz, definimos Matriz nula es la que tiene todos sus elementos iguales a 0. Matriz diagonal es la matriz cuadrada en la que todos los elementos que no están en la diagonal principal son cero; es decir, aij = 0 si i # j. Matriz escalar: es una matriz diagonal con todos los elementos de la diagonal principal iguales. Matriz identidad I es una matriz escalar con los elementos de la diagonal principal iguales a 1 1.4.-0peraciones con matrices Definición : La suma de dos matrices A= (aij ) y B= (bij ) de la misma dimensión, es otra matriz S=(Sij ) de la misma dimensión que los sumandos y con término genérico sij = aij + bij . La suma de A y B se denota por A + B. La adición de matrices posee las siguientes propiedades: -Propiedad asociativa : A +(B +C)=(A +B)+C -Propiedad conmutativa: A +B =B+A - A + 0 = A (0 es la matriz nula correspondiente) La matriz -A, que se obtiene cambiando de signo todos los elementos de A, recibe el nombre de opuesta , ya que A+(-A)=0 Definición : La diferencia de dos matrices A = (aij ) y B = (bjj ) de la misma dimensión, es otra matriz D=(dij ) de la misma dimensión que las anteriores y con término genérico dij = aij - bjj . Se denota como A-B. Definición : El producto de una matriz A=(aij ) por un numero real k es otra matriz B=(bjj ) de la misma dimensión que A y con término genérico bij = k.aij .Se denota como k.A. Al número real k se le llama también escalar, y a este producto, producto de escalares por matrices. El producto de un número por una matriz verifica las siguientes propiedades: k(A +B)=kA+kB . (k+h)A=kA+hA . k(hA)=(kh)A Definición : Producto de una matriz fila por una matriz columna : Sea A=(a1, a2, a3,..an) una matriz b1 b2 fila y B = un vector columna. bn Se define su producto A.B como el número real a1.b1 +a2.b2+a3.b3+...... +an.bn Producto de dos matrices cualesquiera : El producto de la matriz A = (aij ) de dimensión m x n por la matriz B = (bij ) de dimensión n x q , es otra matriz P = (Pij ) de dimensión m x q , tal que cada elemento Pij se obtiene multiplicando la fila i de la primera matriz por la columna j de la segunda, consideradas ambas como matrices fila y columna, respectivamente. El producto de las matrices A y B se designa como A.B. El producto de matrices verifica las siguientes propiedades, siempre y cuando las diferentes operaciones estén definidas: . - Propiedad asociativa :A.(B.C)=(A.B).C - El producto de matrices en general no es conmutativo, es decir A.B es distinto de B.A - Propiedad distributiva del producto con respecto de la suma: A.(B+C)=A.B+A.C . Teoría Álgebra Pág 3 2º BT M at II CS - Si A es una matriz cuadrada de orden n, se tiene A.In=In.A=A Definición : Se define la potencia n-ésima de una matriz cuadrada A de forma natural como An=A.A.A. ...A (n veces) Ejemplo: Volvamos al ejemplo de la matriz asociada a un grafo del apartado 1.2. Si hallamos M 2=M .M obtenemos M 2 = M. M = 2 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 0 . 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 0 = 2 1 0 1 0 1 1 0 1 1 2 0 1 1 0 1 =A La matriz M =A expresa en qué forma se pueden establecer comunicaciones entre 105 equipos a través de otro. Por ejemplo, vemos que a11 = 2 lo que significa que A puede comunicarse con A de dos formas distintas a través de otro equipo (A-B-A y A-C-A), a12=1 significa que A puede comunicarse con B de una sola forma a través de otro equipo(A-C-B), etc. De igual modo, M 3 nos indicaría las posibilidades de comunicación entre 105 diferentes puntos a través de otros dos equipos. La matriz T = M+M2 = 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 0 + 2 1 0 1 0 1 1 0 1 1 2 0 1 1 0 1 = 2 2 1 1 1 1 1 0 2 2 2 1 1 1 1 1 da las formas que tienen de comunicarse por radio los cuatro equipos, bien directamente o bien a través de otro equipo. 1.5.-Rango de una matriz Definición : Triangular una matriz consiste en convertir dicha matriz en otra que tenga nulos todos los elementos situados por debajo de la diagonal principal por medio de la aplicación sucesiva de las llamadas operaciones elementales: -Permutar el orden de colocación de dos filas . -Permutar el orden de colocación de dos columnas -M ultiplicar una fila por un número distinto de cero. -Sumar a una fila otra fila multiplicada por un número real. Definición : Se llama rango de una matriz A al número de filas no nulas de la correspondiente matriz triangularizada obtenida a partir de A con el proceso anterior. M étodo de Gauss para el cálculo del rango: Eminentemente práctico. 1.6.-M atriz inversa Si nos restringimos al conjunto de las matrices cuadradas de orden n con la operación de multiplicar, podemos considerar además de las propiedades ya citadas, la existencia de elemento inverso. Esta matriz no siempre existe, pero de existir, será única y se define de la siguiente forma. Definición :Llamamos matriz inversa de una matriz cuadrada A de orden n a otra matriz de orden n que representaremos como A-1 tal que A.A-1=A-1.A=In donde In es la matriz identidad de orden n . No todas las matrices cuadradas tienen inversa. Teoría Álgebra Pág 4 2º BT M at II CS Definición : Una matriz cuadrada de orden n es regular si tiene inversa. En caso contrario se dice que es singular. Se puede demostrar que una matriz cuadrada de orden n es regular si y sólo si su rango es n. Cálculo de la matriz inversa: Eminentemente práctico. 1.7.-Ecuaciones y sistemas matriciales A aquellas ecuaciones o sistemas en los que las incógnitas o coeficientes son matrices las llamaremos ecuaciones o sistemas matriciales. Para resolverlos procederemos de la misma forma que para resolver ecuaciones o sistemas con coeficientes e incógnitas reales, utilizando la suma, resta y producto de matrices estudiadas anteriormente. Además, habremos de tener en cuenta que el producto de matrices no es conmutativo, así como la posible no existencia de la matriz inversa. -Si la ecuación puede reducirse a la forma k.X=A, siendo k un número real, X y A matrices, la solución es inmediata, y X = 1/k.A -Si la expresión a la que podemos reducir la ecuación es de la forma A.X=B, y A posee inversa, la solución será X=A-1.B, ya que A.X=B.A-1. (A.X)=A-1.B => (A-1.A).X=A-1.B I.X=A-1.B -1 X=A .B Si A es cuadrada y no tiene inversa, la ecuación no tiene solución -Para resolver sistemas lineales de ecuaciones matriciales procederemos de la misma forma que para resolver sistemas de ecuaciones lineales, teniendo en cuenta las consideraciones anteriores. Teoría Álgebra Pág 5 2º BT M at II CS Bloque 1:Álgebra Tema 2: S istemas de ecuaciones lineales 2.1.Sistemas de ecuaciones lineales con dos incógnitas. Definición : Se llama ecuación lineal con dos incógnitas a una ecuación de la forma ax + by = c, donde a y b son números reales conocidos que se llaman coeficientes , c es el término independiente . x e y son números reales desconocidos llamados incógnitas. Definición : Se llama solución de una ecuación lineal con dos incógnitas a un par (xo,y o) que la verifique. Nota : La ecuación lineal con dos incógnitas ax + by = c, con a y b ≠0 posee múltiples soluciones. c − ax Para hallarlas basta despejar una de las incógnitas: y = ; asignando valores a x, se obtienen b los correspondientes valores de y. Como sabemos, estas soluciones, representadas en el plano cartesiano, forman una recta. Definición : Dos ecuaciones lineales con dos incógnitas se llaman equivalentes si tienen exactamente las mismas soluciones . Nota : Si a una ecuación la multiplicamos por un número distinto de cero, se obtiene una ecuación equivalente Definición : Se llama sistema de dos ecuaciones lineales con dos incógnitas a un conjunto de dos ecuaciones lineales de la forma: a1 x + b1 y = c 1 donde a1,a2,b1 ,b2 se llaman coeficientes , c1 y c2 se llaman términos a 2 x + b2 y = c 2 independientes . A x e y se les llama incógnitas . Definición : Se llama solución de un sistema de dos ecuaciones lineales con dos incógnitas a un par de números (xo,y o) que verifican simultáneamente ambas ecuaciones. Definición : Dos sistemas de dos ecuaciones lineales con dos incógnitas se llaman equivalentes si tienen exactamente las mismas soluciones. Nota : Las transformaciones que permiten convertir un sistema de dos ecuaciones lineales con dos incógnitas en otro sistema equivalente son las siguientes: - Cambiar el orden de las ecuaciones. - Cambiar el orden de las incógnitas. - M ultiplicar o dividir una de las ecuaciones por un número distinto de cero. - Sumar a una ecuación otra multiplicada por un número distinto de cero. Métodos de resolución : Existen varios métodos de resolución para un sistema de dos ecuaciones lineales con dos incógnitas, ya conocidas de cursos anteriores: M étodo de sustitución : En una de las ecuaciones del sistema se despeja el valor de una de las incógnitas y se sustituye en la otra ecuación, que de esta forma quedará transformada en una ecuación de una única incógnita. Teoría Álgebra Pág 6 2º BT M at II CS M étodo de igualación : Consiste en elegir una de las incógnitas, despejarla en las dos ecuaciones del sistema e igualar las expresiones obtenidas; de esta forma se obtiene una ecuación con una sola incógnita. M étodo de reducción : Elegimos una de las incógnitas para conseguir un sistema equivalente, de forma que los coeficientes de dicha incógnita, en las dos ecuaciones, sean iguales u opuestos. Para ello se multiplicará una o ambas ecuaciones por los números convenientes. Una vez se hayan conseguido los coeficientes iguales (u opuestos) para la incógnita elegida en las dos ecuaciones, las restaremos ( o sumaremos) y así quedará una única ecuación en la que quedará eliminada dicha incógnita. M étodo gráfico : Consiste en dibujar ambas rectas. Las soluciones de estos sistemas y la posición relativa en el plano de las rectas que lo componen se relacionan de la siguiente forma: a) Si las dos rectas son secantes, esto es, tienen un único punto en común, las coordenadas de dicho punto constituyen la solución del sistema. El sistema se llama compatible determinado . b) Si las dos rectas son paralelas, esto es, no se cortan en ningún punto, el sistema no tiene solución y se llama sistema incompatible. c) Si las dos rectas son coincidentes, el sistema tiene infinitas soluciones, y se llama sistema compatible indeterminado. ... 2.2.Sistemas de ecuaciones lineales en general. Definición :Se llama ecuación lineal a una igualdad de la forma a1x1 + a2 x2 + ...+anxn = b, donde a1, a2,...,an son números reales conocidos que se llaman coeficientes , b es el término independiente y x1 ,x2,...,xn son números reales desconocidos llamados incógnitas. Definición : Se llama solución de una ecuación lineal a una n-tupla (a1, a2,...,an) que satisfaga la ecuación. Nota : La ecuación lineal a1x1 + a2 x2 + ...+anxn = b , posee múltiples soluciones. Para hallarlas basta con despejar una de las incógnitas y; asignando valores arbitrarios a n-1 de ellas, se obtienen los correspondientes valores de la incógnita despejada. Definición : Dos ecuaciones lineales se llaman equivalentes si tienen exactamente las mismas soluciones. Nota : Si a una ecuación la multiplicamos por un número distinto de cero, se obtiene una ecuación equivalente Definición :Se llama sistema de m ecuaciones lineales con n incógnitas a un conjunto de m ecuaciones lineales de la forma: a11x 1+a12 x2 + ...... + a1n xn = b1 a21 x1+ a 22 x 2 + ...... + a 2n xn = b 2 ............................................ am 1x1+ a m 2 x2 + ...... + amn x n = bm Teoría Álgebra Pág 7 donde aij (1 ≤ i ≤ m, 1 ≤ i ≤ n ) se bj (1 ≤ i ≤ m, ) se llaman llaman coeficientes, términos independientes, xi (1 ≤ i ≤ n )se llaman incognitas . 2º BT M at II CS Definición : Se llama solución del sistema de m ecuaciones lineales con n incógnitas a una n-tupla (a1,a2,...,an) que verifique simultáneamente todas las ecuaciones. Resolver un sistema es encontrar todas sus soluciones. Definición : Dos sistemas de ecuaciones lineales con el mismo número de incógnitas (aunque no tengan el mismo número de ecuaciones) se llaman equivalentes si tienen exactamente las mismas soluciones. Nota : Las transformaciones que permiten convertir un sistema de m ecuaciones lineales con n incógnitas en otro sistema equivalente son las siguientes: - Cambiar el orden de las ecuaciones. - Cambiar el orden de las incógnitas. - M ultiplicar o dividir una de las ecuaciones por un número distinto de cero. - Sumar a una ecuación otra multiplicada por un número distinto de cero. Definición :Un sistema homogéneo es aquel cuyos términos independientes son todos nulos. Dependiendo de los términos independientes y de las soluciones, se puede hacer la siguiente clasificación de los sistemas de ecuaciones lineales: Un sistema de ecuaciones lineales queda determinado por sus coeficientes y sus términos independientes. Si situamos dichos números en una tabla, en las mismas posiciones en las que aparecen en el sistema, obtenemos la matriz de los coeficientes; si a ésta le añadimos los términos independientes, se obtiene la matriz ampliada. a11 a12 a21 a 22 ... ... a m1 a m2 a1n ... a2n ... ... ... amn ... Matriz coeficientes a11 a 12 ... a1n b1 a21 a 22 ... a 2n b2 ... ... ... ... ... am1 a m2 ... a mn b m Matriz ampliada Llamando A a la matriz de coeficientes, X a la matriz columna formada por las incógnitas, y B a la matriz columna formada por los términos independientes, el sistema puede también escribirse en la forma A.X= B. Teoría Álgebra Pág 8 2º BT M at II CS 2.3.Sistemas escalonados. M étodo de resolución de Gauss El método de Gauss, conocido también como de triangulación o de cascada, se basa en el método de reducción que, aplicado sucesivas veces, permite obtener un sistema escalonado equivalente al dado inicialmente. Definición : Un sistema de ecuaciones lineales es escalonado si tiene la forma: a11x1+ a12x2 + ...... + a1n xn = b1 a22x2 + ...... + a 2n xn = b2 ............................................ es decir, cada una de las ecuaciones tiene una incógnita a mn xn = bm menos que la anterior. Se debe observar que la resolución de este tipo de sistemas es muy sencilla, partiendo de la última ecuación. El método de Gauss consiste en transformar un sistema de m ecuaciones lineales con n incógnitas cualquiera en otro equivalente y escalonado, utilizando las transformaciones vistas anteriormente. (Práctica) TEOREM A DE ROUCHE-FROBENIUS El tipo de sistema está relacionado con el rango de la matriz de coeficientes y la matriz ampliada del siguiente modo: TEOREM A :Un sistema de m ecuaciones lineales con n incógnitas es compatible (tiene solución) si, y sólo si, el rango de la matriz de coeficientes coincide con el rango de la matriz ampliada. Además, si dicho rango es igual al número de incógnitas, el sistema es compatible determinado, e indeterminado en otro caso. 2.4.Sistemas dependientes de un parámetro. Definición : Un sistema lineal se dice dependiente de un parámetro cuando alguno de sus coeficientes o términos independientes es un parámetro. (Un número real desconocido, pero no incógnita). Discutir un sistema de ecuaciones dependiente de un parámetro es identificar para qué valores del parámetro el sistema es compatible, distinguiendo los casos en que es determinado o indeterminado. Su resolución por el método de Gauss se hace como si fuese un sistema cualquiera de los anteriormente vistos, discutiendo las distintas soluciones según los valores del parámetro. Teoría Álgebra Pág 9 2º BT M at II CS Bloque 1:Álgebra Tema 3: Programacion Lineal 3.1.-Desigualdades e inecuaciones . Definición : Dados a y b números reales cualesquiera, se dice que a ≤ b si existe un número c positivo o nulo tal que b = a +c a ≥ b si existe un número c positivo o nulo tal que a = b +c a < b si existe un número c positivo tal que b = a + c a > b si existe un número c positivo tal que a = b + c Nota : Se verifican las. siguientes propiedades: -Propiedad transitiva ∀ a, b, c ∈R, si a ≤ b y b ≤ c, entonces a ≤ c - ∀ a, b ∈R, se verifica que a < b, a = b o a > b - ∀ a, b, c, d ∈ R, si a ≤ b y c ≤ d, entonces a + c ≤ b + d Definición : Una inecuación es una desigualdad en la que intervienen incógnitas o valores desconocidos. Definición : Resolver una inecuación consiste en encontrar todos los valores de las incógnitas que verifican dicha inecuación. El conjunto de estos valores se denomina solución de la inecuación. Definición : Dos o más inecuaciones son equivalentes cuando tienen la misma solución. Nota : Para resolver una inecuación la transformaremos en otra equivalente más sencilla; para ello utilizaremos las siguientes transformaciones de equivalencia: - Si a los dos miembros de una inecuación se les suma o se les resta un mismo número o expresión algebraica, resulta una inecuación equivalente a la dada. ∀ a , b , c ∈ R, si a ≤ b a +c≤b+c - Si a los dos miembros de una inecuación se los multiplica por un número real positivo, resulta otra inecuación equivalente a la dada: ∀ a, b ∈ R y ∀ c ∈ R+ , si a ≤ b a . c ≤ b .c - Si a los dos miembros de una inecuación se los multiplica por un número real negativo, resulta otra inecuación cuyo signo de desigualdad es contrario al de la dada, y que es equivalente a ella. ∀ a, b ∈ R y ∀ c∈ R-, si a ≤ b a.c ≥ b.c 3.2. -Inecuaciones y sistemas lineales con una incógnita Definición : Una inecuación es lineal si el grado de todas sus incógnitas es uno. Así, las inecuaciones lineales con una incógnita pueden expresarse como cualquiera de las siguientes desigualdades: ax + b ≥ 0; ax + b ≤ 0; ax + b > 0; ax + b < 0, donde a y b son números reales y a no es nulo. Para resolver una inecuación lineal con una incógnita basta con aplicar las transformaciones de equivalencia necesarias hasta obtener una inecuación equivalente de una cualquiera de las siguientes formas: x ≥ a, x ≤ a, x >a, x < a. Nota : También es posible que, al transformar una inecuación en otra equivalente, desaparezcan todas las incógnitas; en este caso, si la desigualdad obtenida es cierta, su solución será todo R; en caso contrario, la solución será el conjunto vacío. Definición : Un sistema de inecuaciones lineales con una incógnita es el formado por dos o más inecuaciones lineales con una incógnita. Teoría Álgebra Pág 10 2º BT M at II CS Su solución estará formada por todos aquellos valores que satisfagan a la vez todas las inecuaciones, es decir, la solución de un sistema de inecuaciones lineales con una incógnita es la intersección de las soluciones de todas las inecuaciones que lo forman. 3.3. -Inecuaciones y sistemas de inecuaciones lineales con dos incógnitas. Definición : Se llama inecuación lineal con dos incógnitas a una inecuación que pueda expresarse mediante cualquiera de las desigualdades siguientes: ax +by +c ≤ 0; ax +by +c < 0; ax + by +c ≥ 0; ax +by + c > 0, con a, b y c números reales cualesquiera. Definición : Se llama solución general de una inecuación lineal con dos incógnitas al conjunto de pares (x, y) que la verifican y una solución particular será un punto cualquiera que satisfaga dicha desigualdad. La solución general de una inecuación lineal con dos incógnitas es un semiplano que tiene por frontera la recta ax + by +c = 0. Esta frontera estará incluida en la solución si la inecuación no es estricta. Para determinar gráficamente dicho semiplano, dibujaremos la recta de ecuación ax + by + c = 0, que dividirá al plano en dos semiplanos; a continuación tomaremos un punto de uno de dichos semiplanos y lo sustituiremos en la inecuación. - Si la verifica, el semiplano que contiene a dicho punto es la solución de la inecuación. - Si no la verifica, la solución será el semiplano que no contiene al punto. Definición : Un sistema de inecuaciones lineales con dos incógnitas es un conjunto de dos o más inecuaciones lineales con dos incógnitas. Definición : Se llama solución general de un sistema de inecuaciones lineales con dos incógnitas al conjunto de los puntos (x,y) que satisfacen simultáneamente todas las inecuaciones. Dicha solución general se puede calcular hallando la intersección de las regiones que son solución de cada una de las inecuaciones que forman el sistema. Así, el conjunto solución de un sistema de inecuaciones lineales puede ser un semiplano, una semirrecta, un segmento, un punto o el conjunto vacío. En cualquier caso, la solución de un sistema de inecuaciones lineales con dos incógnitas es un conjunto convexo que puede estar acotado o no. (Un conjunto convexo es aquel que al unir dos cualesquiera de sus puntos, el segmento obtenido queda dentro del conjunto). La frontera de este conjunto puede pertenecer o no a la solución, dependiendo de si las inecuaciones iniciales son estrictas o no. Definición : Llamaremos vértices a los puntos de la solución general que son intersección de las rectas frontera. 3.4.-Orígenes de la programación lineal Aunque los orígenes de la programación lineal se remontan al siglo XVII, en el que matemáticos como Bernouilli y Lagrange estudiaron problemas de máximos y mínimos, se considera a George Bernard Daritzing (Portland,1914) como el precursor de esta rama de la matemática, ya que fue él el que en 1947 formuló y desarrolló los algoritmos necesarios para plantear y resolver problemas de programación lineal. Uno de los episodios más llamativos de la guerra fría entre la antigua Unión Soviética y las potencias aliadas (principalmente, Inglaterra y USA) se produjo a mediados de 1948, cuando la URSS bloqueó las comunicaciones terrestres desde las zonas alemanas en poder de los aliados con la ciudad de Berlín, iniciando así el llamado bloqueo de Berlín. A los aliados se les presentaron dos posibilidades: o romper el bloqueo terrestre por la fuerza, o llegar a Berlín por el aire. Se adoptó la decisión de programar una demostración técnica de poder aéreo norteamericano; a tal efecto, se organizó un gran puente aéreo para abastecer la ciudad: en diciembre de 1948 se estaban Teoría Álgebra Pág 11 2º BT M at II CS transportando 4500 toneladas diarias; en marzo de 1949, se llegó a las 8000 toneladas, tantas como por carretera y ferrocarril antes del corte de las comunicaciones. En la planificación de los suministros se utilizó la programación lineal, y éste fue uno de sus primeros éxitos. Desde entonces, esta ciencia se ha utilizado para otras muchas aplicaciones: problemas de la dieta, del transporte, de la ruta más corta,...; en todos estos problemas se trata de hallar la ganancia máxima o el coste mínimo cuando se dispone de una serie de recursos limitados o hay que cubrir unas necesidades mínimas. Se ha estimado, de una manera general, que si un país subdesarrollado utilizase los métodos de la programación lineal, su producto interior bruto (PIB) aumentaría entre un 10 y un 15% en tan solo un año. Nosotros vamos a estudiar un caso muy concreto de programación lineal: La de dos variables. 3.5. -Planteamiento general de un problema de programación lineal Como ya se ha dicho, un problema de programación lineal pretende hallar ganancias máximas con unos recursos limitados o bien costos mínimos cubriendo ciertas necesidades. M ás concretamente: Definición : Un problema de programación lineal para dos variables consiste en optimizar (maximizar o minimizar) una función lineal de la forma f(x,y) = ax+by que llamamos función objetivo, sujeta a un sistema de desigualdades lineales: a1x + b1y ≤ c 1 a2 x + b2 y ≤ c 2 que llamamos restricciones an x + bn y ≤ c n Notas : - Las incógnitas x e y se llaman en este caso variables de decisión. - Las inecuaciones que forman las restricciones no tienen que ser necesariamente del tipo expuesto, sino que son posibles también inecuaciones del tipo ai + bi ≥ di. - En los problemas reales, dos de las inecuaciones suelen ser x ≥ 0 e y ≥ 0 (restricciones de no negatividad) - Cada desigualdad anterior determina un semiplano. El conjunto de los puntos que cumplen todas las restricciones determinan un recinto convexo, acotado o no, llamado región factible. A cada uno de los puntos del recinto, por cumplir todas las restricciones, se les denomina soluciones factibles. Definición : Se llama solución óptima a una solución factible que haga máxima o mínima (según se desee) la función objetivo. Definición : Se llama valor del programa lineal al valor que toma la función objetivo f(x,y) en la solución óptima 3.6.-Solución de un problema de programación lineal. Discusión de la solución óptima. Para resolver problemas de programación lineal tendremos que: -Encontrar la función objetivo y el conjunto de restricciones. -Determinar la región factible. -Calcular la solución factible que sea óptima. Para resolver el problema se pueden utilizar dos métodos, el método analítico o el método gráfico. Para ello tendremos que considerar el siguiente teorema: Teoría Álgebra Pág 12 2º BT M at II CS TEOREM A : Si una función lineal posee un máximo o un mínimo en un conjunto convexo, toma este valor en un vértice o en un lado de dicho conjunto. Método analítico: La región factible de un sistema de inecuaciones con dos incógnitas es un conjunto convexo; si además este conjunto es acotado, podemos asegurar la existencia de máximo y mínimo de una función lineal en este conjunto; por tanto, el teorema anterior indica que debemos determinar los vértices de esa región y calcular el valor que la función objetivo toma en dichos puntos, de forma que: -Si la función alcanza un valor máximo (o mínimo) en un único vértice, éste será la solución del problema. -Si el valor máximo (o mínimo) lo alcanza en dos vértices, la solución serán todos los puntos del lado de la región que une esos dos vértices. Si el conjunto convexo no es acotado, no podremos asegurar la existencia del máximo ni del mínimo de la función. En este caso es aconsejable usar el método gráfico. Método gráfico: Para hallar el máximo (o mínimo) de la función objetivo f(x,y) por este método dibujaremos las rectas de ecuación f(x,y) = k, donde k toma distintos valores. Estas rectas, denominadas rectas de nivel, son paralelas y proporcionan una idea de hacia dónde se desplaza f(x,y) cuando esta función aumenta o disminuye. Así, desplazándolas paralelamente, encontraremos el vértice o lado, si existe, en el que la función alcanza el máximo o el mínimo. En resumen, dependiendo de la forma de la región factible y de la función objetivo, un problema de programación lineal puede tener solución única, infinitas soluciones o carecer de solución. Líneas de nivel de la función objetivo. Se llaman líneas de nivel de la función objetivo z=ax+by a aquellas expresiones en las que función objetivo toma un determinado valor constante. También reciben el nombre de rectas de beneficio constante. En el método grafico para la obtención de la solución se suele dibuja r la línea de nivel de valor nulo, también llamada recta de beneficio nulo cuya ecuación es de la forma ax+by=0 La recta paralela a la anterior que solamente toque en un punto a la región factible es la que que proporciona la solución buscada en la resolución del problema y cuando esta solución sea única. Cuando el problema de solución lineal presenta solución múltiple, la recta de nivel puede tocar en todos los puntos de un segmento de la región factible. 1.-Determina los valores máximo y mínimo de la función z = 2x - 8y sometida a las restricciones: 3x-2y≤12; x-4y≥ -20; 3x+2y ≤ 24; x + 2y ≥ 4; ×≥0; y≥0 En el gráfico puede verse la región factible que proporcionan las restricciones. La región convexa está definida por los vértices de coordenadas: A(4, 0), B(6, 3), C(4, 6), D(0,5) y E(0,2) En el dibujo se observa que la línea de nivel que proporciona el valor máximo es la recta de ecuación 2x - 8y = 8. Esta recta pasa por el vértice A(4, 0). La línea de nivel que proporciona el valor mínimo es la recta de ecuación 2x - 8y = -40, que pasa por los vértices C(4,6) y D(0,5). Por tanto, la función objetivo alcanza el máximo en el punto A(4, 0) y el mínimo en cualquiera de los puntos del segmento determinado por los vértices C(4, 6) y D(0, 5). Teoría Álgebra Pág 13 2º BT M at II CS 2.- Determina los valores máximo y mínimo de la función z = 5x – 3y sujeta a las restricciones: x + y ≤ 3, 2x + y≥8;0 x≥0; y≥0. Puede verse en el gráfico que las restricciones no proporcionan ningún punto en la región factible. Nos encontramos ante un programa lineal no factible, es decir, que carece de soluciones. 3. - Determina los valores máximo y mínimo de la función z = 2x+y sometida a las restricciones: 0 ≤ x ≤ 6 ; 0 ≤ y ≤ 10 ; 8 ≤ 2x + y ≤ 16 La región factible que delimitan las restricciones puede verse en el gráfico. Esta región está delimitada por los vértices: A(4,0), B(6, 0), C(6,4), D(3, 10), E(0, 10) y F(0, 8) La línea de nivel que alcanza el valor máximo es la recta de ecuación 2x + y = 16. Se observa que pasa por los vértices C(6,4) y 0(3, 10). La línea de nivel que alcanza el valor mínimo es la recta de ecuación 2x + y = 8. Se observa que pasa por los vértices A(4, 0) y F(0, 8). Por tanto, la función objetivo alcanza el máximo en cualquiera de los puntos del segmento determinado por los vértices C(6,4) y O(3, 10) y el valor mínimo en cualquiera de los puntos del segmento determinado por los puntos A(4, 0) y F(0, 8). 4.- Recinto ilimitado En la región determinada por x + y ≥ 2 ; x ≤ y ; x ≥ 0 ; y ≥ 0 , halla las coordenadas de los puntos en los que la función f(x, y) = 3x + 4y alcanza su mínimo y su máximo. .Obtenemos una región infinita con vértices en (1,1) y (0,2) Representamos la dirección de las rectas z = 3 x + 4 y dibujando la que pasa por el origen de coordenadas. El mínimo se alcanza en (1,1) y es 7 No hay máximo, La función 3x + 4y se puede hacer tan grande como se quiera en el recinto propuesto 5.-Soluciones enteras Halla los valores de x e y que hacen máxima la función z = 8x + 5y, sujeta a las restricciones adjuntas: x e y deben ser números naturales. x + y ≤ 7; . 3x + y ≤ . 12 ; x ≤ 3 . Los puntos factibles son los de coordenadas naturales que están en el recinto ilimitado por las rectas: x + y = 7, 3x + y = 12, x = 3, x = 0, y = 0 Hay 25. Calculamos el valor de la función en los puntos: A(0,7), B( 1, 6), C(2, 5) y D(3, 3) ZA = 35; ZB = 38; ZC = 41 ZD = 39 El valor máximo se obtiene para x = 2, y = 5. Teoría Álgebra Pág 14