| CONCEPTO | CARACTERÍSTICA DEL CONCEPTO |
| ALGORITMO SIMPLEX | Busca el óptimo de un problema de P.L. recorriendo sólo algunos de los vértices del poliedro que representa el conjunto de soluciones factibles.
1. Convierta el modelo PL a su forma estándar. 2. Obtenga una SBF a la forma estándar. 3. Determine si la SBF es óptima: Si hay una variable no básica cuyo aumento hace que el valor actual de la función a maximizar suba, entonces la solución actual no es óptima. 4. Si la SBF no es óptima, determine la variable no-básica que debería convertirse en básica (la de mayor impacto en la función objetivo) y cual variable básica debería convertirse en una no-básica (la que impone una restricción mayor a la variable de mayor impacto). Con la selección anterior y usando operaciones elementales de renglón determine una SBF nueva adyacente a la anterior. 5. Reinicie con el paso 3 con la nueva SBF |
| EMPATE EN VARIABLE DE ENTRADA | Cuando se produce un empate en la condición de decisión de la variable entrante se puede optar por cualquiera de ellas sin que esto afecte a la solución final. Por contra si influye en el número de iteraciones necesarias para obtener dicha solución. Se aconseja optar a favor de las variables básicas ya que ellas son las que formarán parte de la solución óptima. |
EMPATE EN VARIABLE DE SALIDA | Se puede nuevamente optar por cualquiera de ellas. Sin embargo, a fin de no alargar el problema y evitar la entrada en un bucle infinito (caso degenerado), se discrimina a favor de las variables de decisión haciendo que permanezcan en la base. |
EQUIVALENCIAS | REGLAS DE EQUIVALENCIA:
|
FORMA AUMENTADA | Cuando el origen no pertenece a la solución inicial se agregan variables artificiales, estas sólo se agregan en las restricciones que no contienen variables de holgura, a este modelo se le conoce como forma aumentada. |
FORMA CANÓNICA | Un problema de P.L. está en la forma canónica si para un problema de:
|
| FORMA ESTANDAR | Un modelo de PL se dice que está en su forma estándar si cada restricción es una igualdad y las restricciones de signo para cada variable son del tipo mayor o igual que cero. M ecuaciones con N incógnitas (incluye variable de holgura y/o exceso) |
MÉTODO DE LAS DOS FASES | El Método de las Dos Fases es una variante del Algoritmo simplex, que es usado como alternativa al Método de la M grande, donde se evita el uso de la constante M para las variables artificiales. FASE 1. Formule un nuevo problema reemplazando la función objetivo por la suma de las variables artificiales. La nueva función objetivo se minimiza sujeta a las restricciones del problema original. Si el problema tiene un espacio factible el valor mínimo de la función objetivo óptima será cero, lo cual indica que todas las variables artificiales son cero. En este momento pasamos a la fase 2. * Si el valor mínimo de la función objetivo óptima es mayor que cero, el problema no tiene solución y termina anotándose que no existen soluciones factibles. FASE 2. Utilice la solución óptima de la fase 1 como solución de inicio para el problema original. En este caso, la función objetivo original se expresa en términos de las variables no básicas utilizando las eliminaciones usuales Gauss-Jordan. |
MÉTODO M GRANDE | El método M grande comienza con la programación lineal en forma de ecuación. Una ecuación i que no tenga una holgura (o una variable que pueda hacer el papel de una holgura). Se aumenta con una variable artificial, A1, para formar una solución básica con todas las holguras. Sin embargo, como las variables artificiales son ajenas al modelo de programación lineal. Se usa un mecanismo de retroalimentación en el que el proceso de optimización trata en forma automática de hacer que esas variables tengan un nivel cero. En otras palabras, la solución final será como si las variables artificiales nunca hubieran existido en primer lugar. El resultado deseado se obtiene penalizando las variables artificiales en la función objetivo. Pasos: 1. Se debe llevar a la forma estándar cambiando cada restricción por una igualdad. 2. Se debe Penalizar la Función Objetivo 3. Antes de pasar al paso inicial debemos a cada restricción que posea una variable inicial, se debe multiplicar por M y sumarla con a la función objetivo. 4. Crear la tabla con la función objetivo resultante. 5. Aplicar el método Simplex Conocido (iterar por Gauss Jordan). |
| OPTIMALIDAD | En problemas de maximización, el P.L. es óptimo si todos los costes reducidos ( son menores o iguales que cero. En problemas de minimización cada coste reducido debe ser mayor o igual que cero. |
| SOLUCIÓN BÁSICA | Es aquella que tiene al menos n-m componentes nulos o variables no básicas, el resto de las variables (m) se resuelven con sistema de ecuaciones. |
| SOLUCIÓN BÁSICA FACTIBLE | Todas las variables básicas son mayores o iguales que cero y n-m valen 0 (puntos extremos de la región factible) |
VARIABLE ARTIFICIAL | Una variable artificial es un truco matemático para convertir inecuaciones "≥" en ecuaciones, o cuando aparecen igualdades en el problema original, la característica principal de estas variables es que no deben formar parte de la solución, dado que no representan recursos. Estas variables se representan por la letra "A", siempre se suman a las restricciones. |
VARIABLE DE ENTRADA | Se refiere a la variable no básica en el renglón “z” con el coeficiente más negativo, si se trata de una maximización, o el coeficiente más positivo, si se trata de una minimización que en el siguiente punto adyacente se convierte en variable básica. |
| VARIABLE DE EXCESO | Son variables que se restan en las restricciones con signo ≥ |
| VARIABLE DE HOLGURA | Son variables que se suman en las restricciones con signo ≤ |
VARIABLE DE SALIDA | Variable básica asociada con la mínima razón no negativa con el coeficiente más negativo, si se trata de una maximización, o el coeficiente más positivo, si se trata de una minimización, la cual, en la tabla de solución siguiente, pasará a ser variable no básica. |
VARIABLES BÁSICAS | Variable de decisión que se conserva dentro del nuevo sistema y se utiliza para resolverlo. |
| VARIABLES NO BÁSICAS | Variable de decisión que deliberadamente se hace cero. |
| VARIABLES NO RESTRINGIDAS | Algunas veces las variables de decisión pueden tomar cualquier valor real. Xi s.r.s Cambio de variable Xi = Ui – Vi Ui …. Parte positiva de Xi Vi …. Parte negativa de Xi |