Saludos y bienvenidos a un nuevo blog correspondiente a la asignatura de Investigación de Operaciones I, en esta ocasión estaremos viendo un tema que está estrechamente relacionado con el Método Simplex, ya que veremos algunos casos especiales del mismo que nos llevan a modificar el proceso de solución del mismo.
Primeramente quisiera recordarte algunos aspectos del método simplex como forma de recapitulación ya que los casos que veremos más adelante correspondientes a este blog son casos que requieren el mismo proceso de solución, a salvo de algunas modificaciones, además que solo se usan en algunos casos.
ElMétodo Simplexes un algoritmo de resolución para modelos de Programación Lineal y como todoalgoritmo cuenta con un procesoiterativo que secuencialmente a través de pasos o iteraciones va aproximando el valor óptimo del problemalinealen caso de existir este último. Para aplicar el Método Simplex a un modelo de Programación Lineal se requiere que éste último se encuentre en una forma estándar.
El Método Simplex se utiliza mayormente para problemas lineales en los que intervienen múltiples variables, los cuales no pueden ser resueltos de manera gráfica pues se haría demasiado complejo. Para ello, este método hace uso de la propiedad de que la solución óptima de un problema de Programación Lineal se encuentra en un vértice o frontera del dominio de puntos factibles (esto último en casos muy especiales), por lo cual, la búsqueda secuencial del algoritmo se basa en la evaluación progresiva de estos vértices hasta encontrar el óptimo. Cabe destacar que para aplicar el Método Simplex a un modelo lineal, este debe estar en un formato especial conocido como formato estándar.
Para la solución de un problema de programación lineal usando el método SIMPLEX el planteamiento con esta forma toma el nombre de forma canónica y una vez eliminado las desigualdades entonces se denomina forma estándar.
Además te recuerdo que se deben agregar las variables de Holgura en la función objetiva con coeficientes 0.
Hasta ahora hemos visto cómo resolver un problema usando el método simplex, así como dos de sus variantes, el método M y el método de dos fases, sin embargo existen otros casos, considerados especiales, que son los de degeneración, óptimos alternativos, soluciones no acotadas y soluciones inexistentes o no factibles.
Para resolver estos problemas debemos utilizar variantes distintas del método simple, es aquí donde entran los mencionados hace un momento, y de los cuales hablaremos en esta ocasión.
El método de degeneración, es cuando al aplicar la condición de factibilidad del método simplex, se puede romper un empate en la razón mínima en forma arbitraria, entonces, cuando se presenta un empate al menos una variable básica será cero en la siguiente iteración y se dice que la nueva solución es degenerada. Si esto sucede, la solución degenerada nos lleva a un ciclado, ya que la condición indica que el modelo tiene al menos una restricción redundante.
Por otro lado, un modelo de óptimos alternativos se da cuando la función objetivo es paralela a una restricción obligatoria, es decir, una restricción que se satisface como ecuación en la solución óptima, donde la función objetivo asumirá el mismo valor óptimo en más de un punto de solución.
En el caso de la solución no acotada, se da cuando en algunos modelos de programación lineal los valores de las variables pueden aumentar en forma indefinida sin violar alguna de las restricciones, y eso significa que el espacio de soluciones es no acotado al menos en una dirección.
El resultado es que el valor objetivo puede aumentar en caso de tratarse de una maximización o disminuir si se trata de un problema de minimización en forma indefinida. En ese caso, el espacio de soluciones y el valor óptimo no están acotados, lo que apunta a la posibilidad de que el modelo esté mal construido, siendo las irregularidades más probables en esos modelos, que no se hayan tomado en cuenta restricciones no redundantes y que los parámetros o constantes de algunas restricciones puedan no haberse estimado en forma correcta.
Finalmente, la solución no factible se da cuando los modelos de programación lineal con restricciones inconsistentes no tienen solución factible. Estos casos suceden si todas las restricciones son del tipo menor o igual que, lo que hace suponer que los lados derechos son no negativos porque las holguras permiten tener una solución factible. Para otros tipos de restricciones se usan variables artificiales. Aunque estas se penalizan en la función objetivo, para obligarlas a ser cero en el óptimo, lo que solo puede suceder si el modelo tiene un espacio que sea factible, ya que en caso contrario al menos una variable artificial será positiva en la iteración óptima, este tipo de caso también indica la posibilidad de que el modelo no fue bien formulado.
Más adelante abordaremos sobre cómo darle solución a estos tipos de problemas pero queremos recordarte a modo de conclusión la importancia de conocer los 4 tipos de variantes en que se presentan estos problemas de programación así como dominar y saber identificar cuándo usar cada uno de los métodos de solución siguientes:
- Método Grafico.
- Método Simplex.
- Método Simplex. Revisado.
- Método de la M.
- Y los casos especiales del método simplex.
Te sugerimos que profundices en el tema utilizando la siguiente bibliografía:
Libro TAHA H. 2004. Investigación de operaciones. Pearson educación. Séptima edición. México. 848 p. ISBN: 970-26-0498-2
Internet
