jacoby

Método de la Gran M
Corresponde a una variación del Algoritmo simplex para penalizar la presencia de variables artificiales, mediante la introducción de una constante M definida como un valor muy grande aunque finito. También se puede usar el Método de las Dos Fases para resolver problemas que contengan restricciones de >= o =.
Algoritmo símplex
En optimización matemática, el términoalgoritmo símplex habitualmente se refiere a un conjunto de métodos muy usados para resolver problemas de programación lineal, en los cuales se busca el máximo de una función lineal sobre un conjunto de variables que satisfaga un conjunto de inecuaciones lineales. El algoritmo simplex primal fue desarrollado por el matemático norteamericano George Dantzig en 1947, y procede examinando vértices adyacentesdel poliedro de soluciones. Un algoritmo simplex es un algoritmo de pivote.
Entrada del problema
Considerar un problema de programación lineal,
maximizar
sujeto a
El algoritmo símplex requiere que el problema de programación lineal esté en la forma aumentada de la programación lineal. El problema puede ser escrito como sigue, en forma de matriz:
Maximizar en:


donde x son lasvariables desde la forma estándar, xs son las variables de holgura introducidas en el proceso de aumentación, c contiene los coeficientes de optimización, describe el sistema de ecuaciones contraídas, y Z es la variable a ser maximizada.
El sistema es típicamente no determinado, desde que el número de variables excede el número de ecuaciones. La diferencia entre el número de variables y el número deecuaciones nos da losgrados de libertad asociados con el problema. Cualquier solución, óptima o no, incluirá un número de variables de valor arbitrario. El algoritmo símplex usa cero como valor arbitrario, y el número de variables con valor cero es igual a los grados de libertad





Forma estándar
Es la igualación de las restricciones del modelo planteado, así como el aumento de variables deholgura, o bien la resta de variables de exceso.

Forma canónica
En el método Simplex es de bastante utilidad la forma canónica, especialmente para explorar la relación de dualidad.
Un problema de Programación Lineal se encuentra en la forma canónica si se cumplen las siguientes condiciones:
Para el caso de la forma canónica de maximización:
- La función objetivo debe ser de maximización.
-Las restricciones son del tipo ≤.
- Las variables de decisión son mayores o iguales a cero.
Para el caso de la forma canónica de la dieta:
- La función objetivo es minimizada.
- Las restricciones son de tipo ≥.
- Las variables de decisión son mayores o iguales a cero.

Modelo Ampliado
Cuando se introduce en cada restricción una variable artificial que no contenga una variable de holgura.Variables de entrada
Estas suelen encontrarse en un criterio que se conoce como “Condición de optimalidad”, en un modelo, ya sea de optimización o minimización, y 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 mas positivo, si se trata de una minimización, la cual, en el la tabla de solución anterior,a excepción de la primer tabla, esta variable era una variable básica.
Variables de salida
Esta variable es un punto extremo que se encuentra en un criterio conocido como “Condición de factibilidad”, en un modelo, ya sea de optimización o minimización, y se refiere a la 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 elcoeficiente mas positivo, si se trata de una minimización.
Variable degenerada
Una variable degenerada es una variable básica que vale 0. Gráficamente esto puede ocurrir cuando más de dos rectas se intersequen en el mismo punto.
Base
Conjunto de variables básicas
Variable no restringida
Variable artificial
Se usa una variable artificial cuando las restricciones son = y ≥ y sucede cuando...