Programación Lineal - Investigación Operativa I - 2º Grado Estadística PDF

Tema 2. PROGRAMACIÓN LINEAL Asignatura: INVESTIGACIÓN OPERATIVA I. 2◦ Grado en Estadı́stica 1. Introducción La Programación Lineal (PL) engloba los modelos de programación matemática donde todas las funciones que aparecen en el modelo...

Tema 2. PROGRAMACIÓN LINEAL Asignatura: INVESTIGACIÓN OPERATIVA I. 2◦ Grado en Estadı́stica 1. Introducción La Programación Lineal (PL) engloba los modelos de programación matemática donde todas las funciones que aparecen en el modelo son lineales. El auge de su desarrollo tuvo lugar a partir de la Segunda Guerra Mundial para resolver principalmente problemas de asignación de recursos. Las aplicaciones posteriores han sido muy numerosas y esto ha llevado a que los modelos de optimización lineal sean una de las herramientas básicas más utilizadas de la Investigación Operativa. Ejemplos de aplicaciones son: problemas de transporte y distribución de mercancı́as, planificación de personal, producción y mezcla de productos, cubrimientos, problemas de dietas, modelos de energı́a... 2. Formulación de modelos El proceso de formulación o planteamiento del problema real a estudio es el primer paso, dependiendo del modelo que se construya se tendrá una u otra solución para el problema, por lo que una modelización errónea puede derivar en grandes pérdidas. A la hora de formular un problema, lo primero que hay que determinar son las va- riables de decisión, xj , que son los factores sujetos a cambios cuyos valores pueden variar, o al menos hacerlo dentro de unos lı́mites, según las caracterı́sticas del problema. El objetivo será encontrar una solución óptima x = (x1 , x2 ,..., xn ) para estas variables cumpliendo las condiciones establecidas del problema. En segundo lugar, se formulan las restricciones que se expresan como ecuaciones o inecuaciones lineales en las variables de decisión y que representan la limitación en la disponibilidad de algún recurso: gi (x) ≤ bi o gi (x) ≥ bi o gi (x) = bi siendo gi una función lineal en x y bi un número real. Existen también las restricciones de signo de las variables, (xj ≥ 0), que en muchos casos se evitan en la formulación porque se suponen obvias, pero que deben de cumplirse si la solución del problema lo requiere. 1  Para terminar la modelización es necesario formular la función objetivo a optimizar, que será una función lineal en las variables y que generalmente representa los deseos del decisor de maximizar un beneficio o minimizar un coste: max z = f (x) o min z = f (x) 3. Solución gráfica de problemas bidimensionales La resolución de problemas lineales con sólo dos variables de decisión, x1 y x2 , se puede realizar gráficamente permitiendo de forma visual comprender conceptos y términos que se utilizan en problemas más complejos, como son los diferentes tipos de solución que se pueden encontrar: solución única, más de una solución óptima, la no existencia de solución y la no acotación. Para encontrar la solución de un PL con dos variables, se dibuja un sistema de coor- denadas cartesianas en el que cada variable está representada por un eje. Sobre los ejes anteriores se representan las restricciones del problema (incluyendo las de no negatividad), teniendo en cuenta que si una restricción es una inecuación define una región que será uno de los semiplanos limitados por la lı́nea recta que se tiene al considerar la restricción como una igualdad. La intersección de todas las regiones determina la región factible o espacio de so- luciones que es un conjunto convexo (al ser las restricciones lineales). Para finalizar se determinan los puntos extremos de la región factible que son los candidatos a solución óptima. Se evalua el valor de estos puntos en la función objetivo y aquel o aquellos que la maximicen (o minimicen) serán la solución óptima del problema. Gráficamente la solución se alcanza dibujando la función objetivo igualada a un valor cualquiera f (x) = z0 y trazando rectas paralelas de modo que al cortar en los puntos extremos de la región factible se mejore el valor de z. Tipos de soluciones Problema no factible. Si la intersección de todas las restricciones es una región vacı́a, se dice que el problema no tiene solución y que es infactible o no factible, esto ocurre porque no se pueden encontrar valores de las variables de decisión que cumplan todas las restricciones. Solución única. El PL tiene solución única cuando el valor óptimo se encuentra en un único punto, vértice de la región factible. Infinitas soluciones. Si el valor óptimo se encuentra en dos vértices de la región factible, existen infinitas soluciones (varias en caso discreto), con el mismo valor en la función objetivo, correspondientes a los puntos del segmento que une ambos vértices. Problema no acotado. Ocurre cuando la región factible no está acotada y el óptimo se alcanza en el valor infinito. 2  Figura 1. Única solución óptima Figura 2. Múltiples soluciones óptimas Figura 3. Problema no acotado y Problema no factible 3 4. El Método del Simplex Desarrollado por Dantzig en 1947, es un procedimiento matemático para resolver los problemas de programación lineal. Se basa en la idea de que la solución óptima, si existe, se encuentra en al menos un punto extremo de la región factible. Como el conjunto de puntos extremos puede ser muy grande, este método no evalúa todos los puntos extremos, sino solamente un subconjunto reducido de él. El algoritmo parte de una solución básica factible y se mueve de una solución a otra de forma iterativa, mejorando continuamente el valor de la función objetivo. 4.1. Formulación algebraica El objetivo es determinar el valor de las variables x1 ,..., xn tal que: Max o Min z = c1 x1 + c2 x2 +... + cn xn sujeto a a11 x1 + a12 x2 +... + a1n xn (≤, ≥, =)b1 a21 x1 + a22 x2 +... + a2n xn (≤, ≥, =)b2... am1 x1 + am2 x2 +... + amn xn (≤, ≥, =)bm xj ≥ 0, j = 1,..., n donde cj , aij y bi son constantes conocidas, para todo i = 1, 2,..., m, y j = 1, 2,...n, siendo m el número de restricciones y n el número de variables. Si en el modelo anterior todas las restricciones son de igualdad, los términos independientes son positivos (bj ≥ 0) y hay que maximizar la función objetivo, se dice que el problema esta en formato estándar, y se representa en forma matricial: Max z = cT x sujeto a Ax = b x≥0 donde A es la matriz de coeficientes tecnológicos, x es el vector de variables de decisión, b es el vector de términos independientes correspondiente a los recursos, y c es el vector de costes o beneficios del problema lineal.         a11... a1n x1 b1 c1 A = .......  , x = ..  , b = ..  , c = ..  , ..  .  .  .  am1... amn xn bm cn 4  Además, se asume la hipótesis de que el rango de la matriz A es m, siendo m < n, lo que equivale a que no existen ecuaciones redundantes y el sistema es compatible indeter- minado, es decir, existen infinitas soluciones que cumplen las restricciones del problema y hay que encontrar aquella que optimice la función objetivo. El Método del Simplex se aplica a problemas de programación lineal en formato estándar, donde la función objetivo es de maximizar, las restricciones son de igualdad y todas las variables y los términos independientes de las restricciones son no negativos. Por lo que el primer paso será modificar cualquier problema de programación lineal para expresarlo en su forma estándar. ⋄ Cambio en el sentido de la optimización. Cualquier problema de minimizar se puede considerar equivalente a uno de maximizar y recı́procamente, basta cambiar el sentido de la optimización cambiando el signo de la función objetivo: n X n X min z = cj x j es equivalente a max z ′ = − cj x j j=1 j=1 y recı́procamente, de forma que z = −z ′ ⋄ Conversión de restricciones. Los términos independientes deben ser positivos, si existe bi < 0, basta con cambiar de signo toda la restricción: n X n X aij xj ≤ bi se puede escribir −aij xj ≥ −bi j=1 j=1 Cualquier inecuación se puede convertir en una igualdad introduciendo una variable no negativa como suma o resta según el signo de la desigualdad: n X n X aij xj ≤ bi se puede escribir aij xj + si = bi j=1 j=1 n X n X aij xj ≥ bi se puede escribir aij xj − ei = bi j=1 j=1 con si , ei ≥ 0, llamándose si variables de holgura (representa la cantidad de recurso correspondiente que no se habrı́a utilizado), y ei variables de exceso. ⋄ Conversión de ecuaciones en inecuaciones. Cualquier igualdad lineal se puede sustituir por dos desigualdades lineales. Dada la n X restricción aij xj = bi es equivalente al conjunto: j=1 n X n X aij xj ≤ bi y aij xj ≥ bi j=1 j=1 5 Multiplicando la segunda por -1, se pueden escribir las dos desigualdades con el mismo sentido. ⋄ Conversión de variables no restringidas. Si xj es una variable no restringida en signo, (puede tomar valores positivos o negati- vos) se transforma poniéndola como diferencia de dos variables no negativas, x′j , x′′j ≥ 0 xj = x′j − x′′j 4.2. Soluciones básicas Dado un problema de programación lineal en forma estándar: Max z = cT x sujeto a Ax = b x≥0 donde los vectores c y x son de dimensión n × 1, b es un vector m × 1 y A es una matriz m × n. Se supone que el rango de A es m, con m < n, por lo que el sistema tiene infinitas soluciones, siendo el objetivo del problema encontrar aquella que tenga el valor óptimo para la función objetivo. Definición. Un vector x se dice que es solución factible del problema si satisface Ax = b y x ≥ 0. Toda matriz cuadrada B de orden m no singular formada por un conjunto de vectores columna de A se denomina base o matriz básica. Como B es regular, la ecuación BxB = b se puede resolver de forma única, xB = B−1 b. El vector xT = (xB , 0)T es una de las múltiples soluciones de Ax = b, siendo xB las variables básicas de la solución actual. Las n − m columnas de A que no forman parte de B se las agrupa en una matriz m × (n − m) denominada matriz no básica N (asociada a las variables no básicas), en correspondencia, a estas variables no básicas de la solución se las denota por xN. Quedando la matriz de coeficientes tecnológicos dividida en dos partes: A=B|N, al igual que las variables xT = (xB , xN )T. Figura 4. Descomposición de la matriz A 6  Definición. Una solución donde los valores de todas las variables básicas son no negativos se denomina solución básica factible. Si en una solución, una o más variables básicas tienen valor nulo, la solución se denomina básica degenerada. Definición. Se llama región factible, F , al conjunto de todas las posibles soluciones factibles de un problema de programación lineal: F = {x ∈ Rn : Ax = b, x ≥ 0} si dicho conjunto es vacı́o el problema se dice que es infactible o no factible. Denotando por cBi al coeficiente de la variable básica xBi en la función objetivo, el vector cB = (cB1 ,..., cBm ) está formado por los coeficientes en la función objetivo de las variables básicas. Dada una solución básica factible xB , el valor de la función objetivo es z = cTB xB. Definición. Una solución factible se dice que es solución óptima y se representa por x∗ , si su valor en la función objetivo es mayor que el valor de cualquier solución factible (suponiendo la función objetivo de maximizar), es decir, si cT x∗ ≥ cT x para todo x ∈ F. El valor de la función objetivo en la solución óptima se denomina valor óptimo y se representa por z ∗ = cT x∗. Un problema de programación lineal se dice no acotado si no tiene un valor óptimo finito. Y se dice que tiene soluciones múltiples o alternativas, si tiene más de una solución óptima. Teorema 1. El conjunto de soluciones factibles de un problema de programación lineal estándar es un conjunto convexo y cerrado. Más aún, es un poliedro. Teorema 2. Sea A una matriz m × n con rango m, y b un vector m × 1. Sea F el poliedro convexo formado por los vectores x que verifican las restricciones del problema en forma estándar. Un vector x es una solución factible para el problema si y sólo si x es un punto extremo de la región factible, F. Teorema 3. Dado el problema de programación lineal estándar (factible y acotado), el valor óptimo de la función objetivo se alcanza en un punto extremo de la región factible F. Una base B está formada por m vectores (B1 ,..., Bm ) linealmente independientes y cada vector aj , que es un vector de dimensión m × 1 de A, se puede poner como combinación lineal de los vectores de la base. Es decir, si aj es un vector no básico (que no está en la base B), entonces m X aj = yij Bi = Byj. i=1 Al ser B no singular, también se puede escribir yj = B−1 aj , con yTj = (y1j ,..., ymj ), donde yij es un escalar en el que el subı́ndice i se refiere al vector columna Bi de B y el j al vector columna aj de A, (si B es la matriz identidad, entonces yj = aj para todo j). Otro escalar de interés es zj que está asociado a cada vector aj de A, y se define como m X zj = cTB yj = yij cBi i=1 7  4.3. Pasos del Método Sı́mplex El Método Sı́mplex es un algoritmo mediante el cual partiendo de una solución bási- ca factible inicial se busca otra solución básica factible adyacente (puntos extremos del espacio de soluciones), mejorando o por lo menos no empeorando el valor de la función objetivo. Paso 0. Iniciar la búsqueda con una solución básica factible (punto extremo). Paso 1. Determinar si el cambio a una solución básica factible adyacente puede mejorar el valor del objetivo. Si es ası́, ir al paso siguiente. En caso contrario, la solución es óptima. Paso 2. Determinar la solución básica factible adyacente que proporcione una mayor mejora en el valor de la función objetivo. Volver al Paso 1 y repetir el proceso hasta alcanzar una solución óptima o bien se tenga un problema que sea infactible o no acotado. Regla de la variable de salida. Dada la solución básica factible xB = B−1 b, si el vector columna yj de fuera de la base tiene yij > 0 para algún i, entonces puede entrar en la base en lugar de un vector Bk de la base que verifique   bk bi = mı́n , yij > 0 ykj 1≤i≤m yij Teorema 4. Optimalidad. Dada la solución básica factible xB = B−1 b, con un valor para la función objetivo de z = cTB xB , la actual solución es óptima si zj − cj ≥ 0 para la columna yj de A (z de maximizar). Si el problema es de minimización la condición zj − cj ≤ 0 para todo j indicará la optimalidad. Al término zj − cj se le llama coste reducido de la variable xj e indica cuánto cambia el objetivo si la variable no básica xj se incrementa de 0 a 1. Corolario. La solución básica factible xB = B−1 b es una solución óptima única si zj − cj > 0 para toda columna yj de fuera de la base. Teorema 5. Mejora de la solución. Sea una solución básica factible xB = B−1 b, con un valor para el objetivo z = cTB xB. Si para un vector yj no perteneciente a la base es zj − cj < 0 con al menos un yij > 0, entonces la sustitución por yj de un vector Bj de B proporciona una nueva solución básica factible con al menos el mismo valor para la función objetivo. Regla de la variable de entrada. Dadas las condiciones de mejora, la variable de en- trada en la base será aquella con el zj − cj más negativo, que será la que más incremente el valor de la función objetivo. En caso de empate se puede elegir uno arbitrariamente. Teorema 6. Óptimos alternativos. Dada una solución básica factible xB = B−1 b, si para algún vector aj de fuera de la base es zj − cj = 0, el problema tiene infinitas soluciones óptimas. 8  Como se ha visto, en la fase inicial del método del sı́mplex se necesita disponer de una solución básica factible, siendo conveniente que dicha solución inicial se pueda encontrar de una manera rápida. Para resolver este inconveniente se suman variables artificiales ai > 0 a las restricciones que originalmente fueran igualdades y a aquellas con signo ≥: n X n X apj xj ≥ bp pasará a ser apj xj − ep + ap = bp j=1 j=1 n X n X aqj xj = bq pasará a ser aqj xj + aq = bq j=1 j=1 Las variables artificiales se han añadido como un artificio para poder iniciar de manera sencilla el método del sı́mplex, lo deseable será que estas variables tomen valor cero para que no aparezcan en la solución óptima. Teorema 7. Infactibilidad. Dada una solución básica factible xB = B−1 b, supuesto que zj − cj ≥ 0 para todo vector yj , el problema es infactible si alguna de las variables en xB es artificial con valor positivo. La infactibilidad de un problema se interpreta como que los recursos del sistema no son suficientes para satisfacer las demandas o requisitos planteados. Teorema 8. No acotación. Dada la solución básica factible xB = B−1 b, si para algún vector columna yj no básico es zj − cj < 0 con yij ≤ 0, ∀i, el problema es no acotado. Por otra parte, si zj − cj = 0 para un vector yj de fuera de la base y ninguno de los coeficientes del vector yj asociado es positivo, entonces se dice que hay un rayo óptimo. En tales casos se puede afirmar que hay puntos para los que el valor del objetivo es igual a un valor óptimo finito, pero sus coordenadas se pueden hacer arbitrariamente grandes. Diremos que el problema es no acotado o que tiene un rayo óptimo. 4.4. Resolución por tablas El Método del Sı́mplex es un proceso iterativo que comienza con una solución básica factible, partiendo de la forma estándar (maximización) y se mueve a una solución básica factible adyacente con mayor o igual valor para el objetivo, teniendo en cada iteración alguna de las indicaciones de mejora, optimalidad, soluciones óptimas alternativas, no acotación o infactibilidad. Las iteraciones se expresan mediante tablas para facilitar el proceso, (existen diversas variantes de las mismas). c1... cn x1... xn cB VB z1 − c1... zn − cn z cB 1 xB1 y11... y1n b1.................. cBm xBm ym1... ymn bm 9  La información que se muestra en la tabla es la siguiente: - La columna cB está formada por los coeficientes de las variables básicas de la tabla en la función objetivo. - La columna VB contiene las variables básicas de cada paso. - La última columna recoge los valores de las variables básicas en cada tabla b y el valor de la función objetivo en cada paso z. - En la parte superior aparecen todas las variables, xj incluidas las de holgura, exceso y artificiales. Sobre ellas sus correspondientes coeficientes cj en la función objetivo. - Los valores zj − cj son los costes reducidos. - Los elementos interiores son los vectores columna yj asociados a cada una de las variables. Una versión de la tabla anterior más resumida que suele utilizarse frecuentemente es la siguiente: max z x1... xn Ld V B R0 1 z1 − c1... zn − cn cB b z R1 0 y11... y1n b1 xB1..................... Rm 0 ym1... ymn bm cBm En la cual se han eliminado los coeficientes de las variables en la función objetivo, apareciendo una primera columna que va marcando las filas o “renglones”de la tabla, que se usarán para marcar las cuentas de cada pivotaje, y donde se incluye el valor de la función objetivo, z, como una variable más del problema. Una vez construida la tabla se puede aplicar el Algoritmo del Sı́mplex tal y como se describe: Paso 0. Construir la tabla inicial del problema de maximización. Paso 1. Si hay algún indicador zj − cj < 0 (posibilidad de mejora), ir al Paso 3. Si todos zj − cj ≥ 0, ir al Paso 2 Paso 2. Si todos zj − cj ≥ 0 y no hay variables artificiales en la base con valor positivo, la actual solución es óptima (optimalidad ). Por el contrario, si hay alguna variable artificial en la base con valor positivo, el problema es infactible (infactibilidad ) y parar. Paso 3. Si para algún valor indicador zj − cj < 0 su vector asociado yj ≤ 0, el problema es no acotado (no acotación). En otro caso, es posible la mejora e ir al Paso 4. Paso 4. Variables de entrada y salida: Seleccionar como variable de entrada aquella con el valor más negativo de zj −cj , sea xk (por lo que k será la columna pivote). Seleccionar bi como variable de salida aquella que haga mı́nima la razón θi = { , yik > 0} para yik cada fila. Este cociente mı́nimo indica la restricción más restrictiva en términos de 10  la variable de entrada. El criterio de salida se basa en encontrar la variable básica que limita más la mejora de la función objetivo. La variable básica que tenga la restricción más restrictiva en relación con la variable de entrada se elige para salir de la base. Si el valor mı́nimo es θr , (r es la fila pivote), el elemento yrk es el pivote de la tabla. Paso 5. Pivotaje: Se construye la nueva tabla del sı́mplex sustituyendo la variable básica xBr de salida por la nueva variable básica xr , y cBr por cr. La fila r de la nueva tabla se obtiene dividiendo la fila r de la tabla precedente por el pivote yrk y la nueva columna k se forma con ceros salvo el lugar (r, k) en el que se pone un 1. Los demás valores de la tabla (denotados porb) se obtienen de: ybij = yij − p, bbx = bx − p, Bi Bi zbj − b cj = zj − cj − p, zb = z − p erj eik donde p = , (i ̸= r), donde erj es el elemento en la fila pivote de la columna j yrk y eik el de la fila i en la columna pivote. Obtenida la nueva tabla, volver al paso 1. Es decir, si se tiene la siguiente tabla antes de pivotar: xB1... xBr... xBm... xj... xk... z 0... 0... 0... zj − cj... zk − ck... cB b xB1 1... 0... 0... y1j... y1k... b1..................... xB r 0... 1... 0... yrj... yrk... br..................... xBm 0... 0... 1... ymj... ymk... bm siendo la variable de entrada: zk − ck = mı́n{zj − cj } → xk j ∈B /   br bi y la variable de salida: = mı́n , yik > 0 → xBr yrk 1≤i≤m yik Después de pivotar la tabla quedarı́a: xB1... xBr... xBm... xj... xk... z 0... zky−c rk k... 0... zj − cj − yrk yrj... 0... cB b − zky−c zk −ck rk k br y1k y1k y1k xB1 1... − yrk... 0... y1j − yrk yrj... 0... b1 − yrk br..................... 1 yrj br xk 0... yrk... 0... yrk... 1... yrk..................... xB m 0... − yymk rk... 1... ymj − ymk y yrk rj... 0... bm − ymk b yrk r 11 5. Método de penalización o de la M grande El algoritmo del sı́mplex parte de una solución inicial que se construye con una primera base canónica que permite iniciar el método de forma sencilla. Para obtener dicha base (matriz identidad), se añaden al problema variables artificiales (restricciones = y ≤), cuyo valor debe ser nulo en la solución final (salvo que el problema sea no factible). Por lo que parece deseable sacar de la base lo antes posible dichas las variables artifi- ciales, para que su valor sea cero en la solución final. Una forma de llevar a cero estas variables consiste en asignarles como coeficiente en la función objetivo un valor negativo muy grande (función objetivo de maximizar) que se representa por −M de manera que sea demasiado costoso mantener esas variables en la base (en caso de minimizar las variables artificiales llevarı́an coeficiente positivo M). Este procedimiento recibe el nombre de Método de la M grande o Método de Penalización, el cual se resuelve siguiendo los pasos del algoritmo del sı́mplex. Teniendo en cuenta que si en la solución óptima aparece una variable artificial con valor no nulo en la base, el problema es infactible. 6. Método de las dos Fases El Método de Penalización puede tener problemas de redondeo en el cálculo compu- tacional al tener que proporcionar un valor a M. Otro procedimiento alternativo, cuando es necesario el uso de variables artificiales para obtener la primera base B=Id, es el Método de las dos Fases. Fase 1. En este primer paso, usando las restricciones del problema, se cambia la función objetivo por una nueva función artificial que minimice la suma de todas las variables artificiales y se resuelve por el algoritmo del sı́mplex. Si el valor de la solución final de esta función objetivo es cero, se tiene una solución inicial para el problema original y se pasa a la Fase 2, en otro caso el problema es infactible. Fase 2. En esta segunda fase se aplica el método del sı́mplex al problema original utilizando la solución básica factible obtenida en la primera fase como solución inicial. Si al final de la Fase 1 hay variables artificiales en la base (con valor 0), se puede resolver el problema original asignándole coeficiente nulo a esas variables en la función objetivo original. Al principio de la Fase 2 se eliminan de la tabla del sı́mplex las columnas corres- pondientes a las variables artificiales que no estén en la base al final de la Fase 1. 12 7. Tabla final conocidas las variables básicas óptimas Los cálculos anteriores del Método del Sı́mplex permiten obtener la tabla final del Sı́mplex, sin tener que realizar todas las iteraciones del método, si se conocen las variables básicas de la solución óptima. Partiendo del problema en forma estándar, sea: VB, el conjunto de las variables básicas de la tabla óptima. xB el vector m × 1 de VB. B, la matriz formada por las columnas de las VB en el problema original. aj el vector m × 1 que se corresponde con la columna de la variable j-ésima de las restricciones del problema. b el vector m × 1 de términos independientes del problema inicial. cB el vector 1 × m de los coeficientes de las VB en la función objetivo. cN B el vector 1 × (n − m) de los coeficientes de las variables no básicas en la función objetivo. Conocidas las VB asociadas a cada restricción (hay que tener en cuenta el orden), se sabe que: Todas las VB tienen coeficiente 0 en el R0 , y forman la matriz identidad en el resto de filas o renglones, identificando la unidad, la correspondiente variable básica de cada renglón. El coeficiente de una variable no básica xj en el R0 es cB B−1 aj − cj. El coeficiente de una variable de holgura si en el R0 es el i-ésimo elemento de cB B−1. El coeficiente de una variable de exceso ei en el R0 es el i-ésimo elemento de cB B−1 cambiado de signo. El coeficiente de una variable artificial ai en el R0 es M más el i-ésimo elemento de cB B−1 , suponiendo maximización (si la función objetivo es de minimizar es -M). La inversa B−1 se encuentra en la tabla óptima del sı́mplex en las columnas de las VB iniciales del problema. La columna de una variable no básica xj en la tabla óptima es B−1 aj. El lado derecho del R0 tiene el valor de la función objetivo para la solución óptima, z = cB B−1 b. El resto de valores de la columna de los lados derechos, Ld, son los valores de las variables básicas correspondientes a cada renglón o fila xB = B−1 b. Las variables no básicas tiene valor nulo en la solución óptima. 13 8. Anexo. Nociones básicas sobre conjuntos convexos Definición. Sean x e y dos vectores de Rn. Se llama segmento cerrado que une x e y al siguiente subconjunto de Rn : [x, y] = {z ∈ Rn /z = λx + (1 − λ)y, con λ ∈ R, 0 ≤ λ ≤ 1} Definición. Sean x e y dos vectores de Rn. Se llama segmento abierto que une x e y al subconjunto de Rn : [x, y] = {z ∈ Rn /z = λx + (1 − λ)y, con λ ∈ R, 0 < λ < 1} Definición. Sea A ⊆ Rn , A ̸= ∅. Se dice que A es convexo si para todos x , y ∈ A, se cumple que el segmento cerrado está incluido en A, [x, y] ⊆ A Por convenio el conjunto vacı́o (∅) se considera convexo y si A = {x} es convexo. Definición. Sean x1 ,..., xs ∈ Rn Se llama combinación lineal convexa de x1 ,..., xs a todo z ∈ Rn tal que: z = λ1 x1 +...+λs xs donde λ1 ,... , λs ∈ R+ y siendo λ1 +...+λs = 1 Proposición. Sea S ∈ Rn un convexo no vacı́o y sean x1 ,..., xs ∈ S. Cualquier combinación lineal convexa de x1 ,..., xs pertenece a S. Proposición. El conjunto de combinaciones lineales convexas de un conjunto de pun- tos Sean x1 ,..., xs ∈ Rn es un conjunto convexo. Definición. Sea S un subconjunto de Rn. Se denomina envolvente convexa de S, Co (S), a la intersección de todos los convexos que contienen a S. Se cumple que si S es convexo entonces Co (S) = S y que si S está formado por un número finito de puntos, Co (S) es precisamente el conjunto de combinaciones lineales convexas de esos puntos. 14  Figura 5. Ejemplos de envolvente conexa Proposición. Sea A ⊂ Rn. Sea    λ1 ,... , λs ∈ R+  T = x = λ1 x1 +... + λs xs : λ1 +... + λs = 1 , ∀s ∈ N x1 ,... , xs ∈ A   Entonces Co (A) = T. Definición. Se llama poliedro convexo a la envolvente convexa de un conjunto finito de puntos. Figura 6. Poliedro convexo Definición. Sea S un convexo de Rn y x ∈ S. Se dice que x es un punto extremo o vértice de S si no puede expresarse como combinación lineal convexa de dos puntos distintos de S, es decir si no existen dos puntos distintos x1 y x2 en S tal que x = λx1 + (1 − λ)x2 para algún λ ∈ (0, 1). Por lo tanto, los puntos extremos no está en el interior de ningún segmento que une puntos de S. Un punto extremo de S está en la frontera de S, pero no todos los puntos frontera de S son extremos. Dos puntos extremos x1 , x2 ∈ S, con x1 ̸= x2 , son puntos extremos adyacentes, si el segmento que los une es una arista del conjunto convexo S. Teorema de Krein-Milman. Sea A ⊂ Rn un conjunto convexo, cerrado y acotado. Entonces, A contiene a sus puntos extremos y además es la envolvente convexa de los mismos. Teorema de Carátheodory. Sea S un subconjunto de Rn y Co (S) su envolvente 15 convexa. Entonces todo punto de Co (S) puede expresarse como combinación lineal convexa de n + 1 puntos de S. A partir de este Teorema se deduce que todo punto de un poliedro convexo de Rn puede expresarse como combinación lineal convexa de n + 1 de los vértices del poliedro. Definición. Se llama hiperplano H de vector caracterı́stico a ∈ Rn , con a ̸= 0 al conjunto H = {xRn : aT x = b}, con b ∈ R, Un hiperplano es el conjunto de soluciones de una ecuación lineal en Rn. Definición. Dado un hiperplano H, se llama semiespacios cerrados de borde H a los conjuntos: H+ = {xRn : aT x ≥ b} H− = {xRn : aT x ≤ b} Definición. Un politopo es un conjunto formado por la intersección de un número finito de semiespacios cerrados. Definición. Un politopo cónico es un conjunto formado por la intersección de un número finito de semiespacios cerrados que pasan por un punto. Por lo que un poliedro es un politopo acotado y no vacı́o. Es fácil comprobar que la intersección de conjuntos convexos es convexa y que, por lo tanto, los politopos y los poliedros son conjuntos convexos. Si un politopo es un poliedro, cualquier punto se puede expresar como combinación convexa de los vértices o puntos extremos. 16