Metodo Simplex

1. Presentación
2. Introducción
3. Definiciones
4. Matriz identidad
5. Formulacion del metodo simplex
6. Proceso de calculo del metodo simplex
7. Ejemplo de maximizacion
8. Ejemplo de minimizacion
9. Conclusiones
10. Bibliografía

INTRODUCCION

El Método Simplex, como parte de la programación lineal, es un método analítico capaz de resolver aquellos modelos que se vuelven complejos en el uso del método gráfico por el número de variables empleadas, por ejemplo: Si usted se traslada a su Universidad ¿cuántas opciones tiene para llegar? ¿se va caminando o en carro? Si decide irse en transporte ¿automóvil particular, transporte público, bicicleta, patines, de aventón? ¿Qué implica que usted opte por viajar en alguno de estos? ¿Cuántos recursos será necesario invertir? ¿Cuál es la ruta más corta?

Ante este panorama que en las empresas se vuelve más complejo por el uso de materia prima, recursos implicados y productos fabricados, de ahí la importancia de éste método que facilitará el camino en el proceso de tomar una decisión.

DEFINICIONES

El Método Simplex es un método analítico de solución de problemas de programación lineal capaz de resolver modelos más complejos que los resueltos mediante el método gráfico sin restricción en el número de variables.

El Método Simplex es un método iterativo que permite ir mejorando la solución en cada paso. La razón matemática de esta mejora radica en que el método consiste en caminar del vértice de un poliedro a un vértice vecino de manera que aumente o disminuya (según el contexto de la función objetivo, sea maximizar o minimizar), dado que el número de vértices que presenta un poliedro solución es finito siempre se hallará solución.

Un poco de historia

Este popular método fue creado en el año de 1947

por el estadounidense George Bernard Dantzig y el

Leonid Vitalievich Kantorovich,con el ánimo de

crear un algoritmo capaz de solucionar problemas

de m restricciones y n variables.

MATRIZ IDENTIDAD

La matriz idéntica o identidad es una matriz cuadrada (que posee el mismo número tanto de columnas como de filas) de orden n que tiene todos los elementos diagonales iguales a uno (1) y todos los demás componentes iguales a cero (0), se denomina matriz idéntica o identidad de orden n, y se denota por:

La importancia de la teoría de matrices en el Método Simplex es fundamental, dado que el algoritmo se basa en dicha teoría para la resolución de sus problemas.

EJEMPLO DE CALCULO

Al multiplicar una matriz A por una matriz identidad, como resultado se deberá obtener una matriz idéntica a la primera.

Siguiendo el principio de multiplicación de matrices, se multiplicarán los elementos de la primera fila de A por los elementos de la primera columna de Identidad, luego de la segunda y de n columnas.

Al operar de esta manera, cuando los elementos de A sean multiplicados por 1 en la matriz I se han de conservar, y los multiplicados por 0 no se reflejaran(ya que deben sumarse los resultados de de la multiplicación de fila x columna).

FORMULACIÓN DEL MÉTODO SIMPLEX

Usar un modelo matemático para la resolución de problemas es la base de la programación lineal recordando que modelo se refiere a la representación simplificada de la realidad; los modelos matemáticos en específico hacen uso de símbolos matemáticos y presentan elementos como:

Variables: representan las incógnitas del problema

Restricciones: se contemplan las limitaciones a las que se encuentra sujeta la resolución del problema considerando la escasez de recursos en tiempo y espacio.

Función objetivo: representa la meta que se pretende alcanzar y en la cual se basan las decisiones principales para maximizar lo beneficios o bien para minimizar los costos (considere que en la programación lineal el calificativo “lineal” hace referencia que las ecuaciones usadas en el modelo serán siempre de primer grado, es decir, sin exponentes).

Los resultados del modelo deberán ser usados como una base para el tomador de decisiones con el objetivo de conseguir los mejores resultados en diferentes situaciones. Por lo tanto, es importante señalar cuestiones que debe considerar la persona encargada del modelado

Entre más sencillo sea el modelo, mejor será el resultado. Un modelo complejo no siempre será la mejor solución.
El modelo debe ser validado antes de ser implementado para saber si representa la situación real y en caso de no ser así habrá que hacer los ajustes correspondientes.
Debe hacerse un minucioso análisis de la información recabada para identificar que en verdad será útil para el modelo.
Los modelos son un herramienta más el tomador de decisiones tendrá siempre la última palabra.

PROCESO DE CALCULO

Se plantea el siguiente modelo en su forma original:

Paso 1. Cambiar el modelo a forma estándar

Las desigualdades del tipo ≤ implican la cantidad no usada u holgura del recurso. Para convertirla en una igualdad y hacer uso de ella en el método simplex, se adiciona una variable holgura al lado izquierdo de la ecuación (𝑆𝑛), de tal forma que:

6𝑋1 + 4𝑋2 ≤ 24 Se convertirá en 6𝑋1 + 4𝑋2 + 𝑆1 = 24

Por su parte una restricción del tipo ≥ representará un límite inferior para las actividades a las que se encuentra sujeta la función objetivo; por lo tanto, la cantidad por la que el lado izquierdo de la ecuación es mayor al lado derecho o límite se considera un excedente y para convertirla en una igualdad será necesario restar la variable de excedencia:

𝑋1 + 𝑋2 ≥ 800 Se convertirá en 𝑋1 + 𝑋2 − 𝑆2 = 800

Deberán ponerse tantas variables holgura como restricciones existan. Por su parte, la función objetivo deberá cambiar de signo (de positivo a negativo y viceversa), de tal modo que.

𝑀𝑎𝑥 𝑍 = 100𝑋1 + 125𝑋2 Será: 𝑀𝑎𝑥 𝑍 = −100𝑋1 − 125𝑋2

De tal forma que el modelo estándar completo se escribirá así:

𝑀𝑎𝑥 𝑍 = −100𝑋1 − 125𝑋2

6𝑋1 + 4𝑋2 + 𝑆1 = 24

𝑋1 + 𝑋2 − 𝑆2 = 800

𝑋1, 𝑋2, 𝑆1 𝑆2 ≥ 0

Paso 2. Armar la tabla simplex
Los valores del modelo serán introducidos a la tabla simplex

Observe que en la primer columna se han colocado las variables holgura (𝑆𝑛) y en las filas, de acuerdo a dicha variable, se coloca la restricción que corresponde y en la última fila (ó llamado también renglón objetivo) los valores de la función objetivo. Cuando las variables holgura no aparecen el valor que tomará será cero.

Paso 3. Elegir el valor de Z más negativo

En la fila donde aparecen los datos de Z (la función objetivo) habrá que localizar el valor más negativo excluyendo la última columna. La columna en dónde se encuentre dicho valor se denominará columna de entrada o columna de trabajo.

Paso 4. Determine la variable de salida y el pivote
Dividiendo cada número de la columna solución entre los valores de la columna entrada (a excepción del renglón objetivo). Entonces:

Del resultado, se elige el valor positivo más pequeño sin tomar en cuenta los valores negativos y a la intersección se le denominará pivote

Es muy importante que el pivote tome el valor 1; si no se tiene ese valor habrá que dividir el renglón objetivo entre el valor del pivote

Los nuevos valores se colocarán en la tabla simplex, en el renglón que corresponde; en este caso 𝑠1 retomará el valor de la variable en donde se encontró la columna entrada 𝑋2.

Paso 5. Hacer ceros los demás valores de la columna entrada
Para el ejemplo los demás valores que deben hacerse cero son 1 y – 125
Para eso habrá que multiplicar el renglón 𝑋2 por el inverso del valor que se hará cero y a este resultado se le sumará al renglón que desea convertirse (donde está el inverso), de manera más precisa:

El nuevo valor encontrado se asignará en el renglón que corresponde:

Como usted puede apreciar, los valores junto al pivote en la columna entrada se han convertido en ceros, señal de que hasta este momento se han hecho los cálculos correctos.

De la misma manera puede apreciar que en el renglón de Z ya no ha quedado ningún valor negativo, por lo tanto ya ha terminado el procedimiento.

EJEMPLO DE MAXIMIZACION

Cierto fabricante produce dos artículos A y B, para lo que requiere de dos secciones de producción: sección de montaje y sección de pintura. El articulo A requiere una hora de trabajo en la sección de montaje y dos en la de pintura; y el articulo B, tres horas en la sección de montaje y una hora en al de pintura.

La sección de montaje solo puede estar en funcionamiento nueve horas diarias, mientras que la de pintura solo ocho horas cada dia. El beneficio que se obtiene produciendo el articulo B es de 40 dolares y el de A es de 20 dolares.
Calcula la producción diaria de los artículos A y B que maximiza los beneficios.

3. Escribir la tabla inicial simplex

EJEMPLO DE MINIMIZACION

Una granja de pollos se da una dieta "para engordar" con una composición mínima de 15 unidades de una sustancia A y otras 15 de una sustancia B. En el mercado solo se encuentran dos clases de compuestos: el tipo 1 con una composición de una unidad A y cinco de B, y el tipo II con una composición de cinco unidades de A y una de B. El precio del tipo 1 es de 10 dolares y el del tipo II es de 30 dolares.

Que cantidades se han de comprar de cada tipo para cubrir las necesidades con un coste mínimo?

CONCLUSIONES

El método simplex, emplea básicamente, la estrategia de resolver los problemas de programación lineal por medio de sistemas de ecuaciones lineales simultáneas siempre que se tenga una solución factible.

El óptimo, si es que existe, se determina avanzando un punto esquina adyacente a la vez y comprobando si aún existe un punto esquina que pueda mejorar el valor de la función objetivo.

El mercado, las empresas, e incluso las personas están en una búsqueda constante de mejoras, de nuevas ideas, de rendimiento y ahorro de recursos de todos los tipos, pero llevar esto acabo requiere de toma de decisiones que podrían estar mas allá de realizar una simple selección escogiendo lo que para nuestros oídos suene como la mejor opción.