Antes de iniciar el estudio de esta unidad es importante que usted haya resuelto problemas de investigación de operaciones con dos variables mediante el método gráfico, pues en esta unidad dicho método se extenderá a varias variables mediante un algoritmo algebraico sistemático: el método simplex.

El método simplex consiste en un algoritmo iterativo que permite ir mejorando la solución en cada paso. Haciendo una analogía con el método gráfico, consiste en caminar por cada vértice del poliedro de la región factible de tal forma que aumente o disminuya de un vértice a otro según la función objetivo. Dado que el número de vértices que presenta un poliedro solución es finito siempre se hallará solución.

Propósito general

Solucionar problemas de programación en varias variables mediante el método simplex.

Propósitos específicos

• Explicar de manera exhaustiva el método simplex en un problema de programación lineal para maximización.

• Solucionar problemas de minimización con el método simplex.

• Apropiar herramientas informáticas como Solver y QSB para la solucionar problemas de programación lineal.

Para resolver problemas de programación lineal que involucran dos variables de decisión es conveniente usar el método gráfico, ya que visualiza el valor óptimo para una función objetivo (máximo o mínimo) como uno de los vértices de la región establecida de acuerdo a las restricciones del problema. Sin embargo, en la práctica de la administración de operaciones aparecen problemas con múltiples variables y varias restricciones, en cuyo caso se sugiere usar uno de los algoritmos más adaptables que existen: el método simplex.

Este método fue desarrollado por el matemático estadounidense George Dantzig en 1946 y se entiende como una manera sistemática y secuencial (iterativa) para llegar a la solución óptima de un problema de programación lineal.

De acuerdo con Larson y Edwars (2002), es posible afirmar que un problema de programación lineal está en la forma estándar si:

a) todas las restricciones son igualdades;

b) todas las variables son no negativas, y

c) las limitaciones (lado derecho de la restricción) son positivas.

Cuando un problema presenta restricciones en ambos sentidos (≥ y ≤) es más difícil optimizar el algoritmo, ya que las variables de holgura cambian de signo según la desigualdad. En estos casos es necesario realizar tanteos, escogiendo como primer pivote la menor razón no negativa entre las variables de holgura que se restan. Si no se llega a la solución óptima, se prueba con las razones que le siguen a este criterio.

De acuerdo con Martínez (2007), el método simplex está diseñado para ser aplicado solo hasta que el problema se encuentre en la forma estándar.

Previamente se trabajó el método simplex estándar con restricciones menores o iguales a cero. Ahora bien, en este apartado se extenderá el método a problemas en los que la función objetivo debe minimizarse. Para tal fin, es posible establecer el modelo de minimización en forma estándar así:

Donde x_i =0 y b_m ≥ 0.

Cuando en un problema de minimización se tienen desigualdades en ambos sentidos se deben cambiar los signos de la función objetivo y aplicar el algoritmo simplex estándar (maximización).

Haga clic sobre el enlace para ver un ejemplo de aplicación del método símplex para minimización con restricciones mixtas.

Recuerde que el dual de un problema dual es el primal.

Antes de pasar al resumen de la unidad le sugerimos desarrollar la actividad de aprendizaje que encontrará en el esquema interactivo, la cual le permitirá repasar los temas estudiados hasta este punto.

Material de apoyo

El método simplex es un algoritmo que permite mejorar la solución de la función objetivo en cada paso. El razonamiento matemático consiste en si se lleva a dos variables en el plano x, y, caso en el cual se obtendrá una región factible donde el método pasa de un vértice a otro vecino de manera que aumente o disminuya según lo determine la función objetivo. Dado que el número de vértices de un polígono es un número finito, siempre se llegará a una solución óptima.

Matemáticamente el método simplex trabaja la función objetivo, y las restricciones iniciales que son inecuaciones se trasforman en ecuaciones, agregando o restando variables de holgura relacionadas con el recurso o restricción. Posteriormente se realizan los pivotes hasta obtener la solución óptima.

Actividad de aprendizaje

Con el fin de permitirle poner en práctica sus competencias en la resolución de problemas de programación lineal, lo invitamos a realizar el siguiente ejercicio.