Método Simplex

Método simplex

            El método simplex es un algoritmo. Cualquier procedimiento iterativo de solución es un algoritmo. Un algoritmo es simplemente un proceso en el que se repite (se itera) un procedimiento sistemático una y otra vez hasta obtener el resultado deseado. Cada vez que se lleva a cabo el procedimiento sistemático se realiza una iteración. En consecuencia, un algoritmosustituye un problema difícil por una serie de procesos fáciles.
            Además de las iteraciones, los algoritmos incluyen un procedimiento para iniciar y un criterio para determinar cuándo detenerse:
















            El método simplex es un procedimiento algebraico en el que cada iteración contiene la solución de un sistema de ecuaciones para obtener una nueva solucióna la que se le aplica la prueba de optimalidad. No obstante, también tiene una interpretación geométrica muy útil. Para poder entender los conceptos geométricos generales se utilizará la solución gráfica del siguiente problema: 
“ Un farmacéutico produce un medicamento en comprimidos de dos tipos para los del tipo A utiliza 1 unidad de vitamina B1 y 1 unidad de vitamina B2 y para las del tipo Butiliza 1 unidad de vitamina B1 y 2 unidades de vitaminaB2. Tiene 120 unidades de vitamina B2 y 90 unidades de vitamina B1. Si por cada producto de tipo A tiene un beneficio de $50 y por cada producto de tipo B tiene un beneficio de $80. ¿Cuántos medicamentos de cada tipo debe producir para obtener un máximo beneficio?”
X1: Cantidad de medicamentos de tipo A
X2: Cantidad de medicamentos de tipoB
F. O.: Z= 50 x1 + 80 x2
Restricciones:
x1 + 2x2 ≤ 120 FORMA CANÓNICA
x1+ x2 ≤ 90
x1, x2 ≥ 0


















Para resolver el problema por el método simplex debemos armar la tabla simplex, tenemos que expresar el enunciado en formato tableau:
1. Debemos pasar el enunciado expresado en forma canónica a la forma estándar, para ello debemos transformar lasdesigualdades en igualdades:
x1 + 2x2 ≤ 120 Significa que puede ocurrir que utilicen las 120 unidades de vitamina B1 o menos. Por lo tanto debemos agregar una nueva variable llamada de holgura o slack en el primer miembro, S1:
x1 + 2x2 ≤ 120 X1 + 2x2 +S1 =120
S1 representa la cantidad de unidades de B1 sin utilizar, por ejemplo, si se utilizaran 100 unidades de B1, entonces,S1=20, quedarían 20 unidades de B1 sin utilizar
En la segunda inecuación agregamos otra variable de holgura S2:
x1+ x2 ≤ 90 x1+ x2 + S2 = 90 con S2 ocurre lo mismo que con S1, representa la cantidad de vitamina B2 sin utilizar.
2. Despejamos Z, de manera tal que todas las variables queden en el primer miembro:
Z= 50x1+80x2 -50x1-80x2+Z=0
3. Debemos escribir en todas las ecuacionestodas las variables, completamos con coeficientes 0:
x1 + 2x2 +S1 =120 x1 + 2x2 + S1 + 0S2 + 0z =120
x1+ x2 + S2 = 90 x1 + x2 +0S1+ S2 + 0z = 90
-50x1-80x2 +z = 0 -50x1- 80x2 +0S1+ 0S2 + z = 0
Con x1, x2, S1, S2 ≥ 0Tanto S1 como S2 no representan utilidad, las agregamos a la ecuación de Z con coeficientes 0.
Escribamos, entonces, en la tabla:

x1
x2
S1
S2
Z
Constantes
*S1
1
2
1
0
0
120
**S2
1
1
0
1
0
90
***Z
-50
-80
0
0
1
0
Estas tres columnas forman lo que se denomina MATRIZ IDENTIDAD, a las variables cuyos coeficientes pertenecen a esta matriz se lasdenomina básicas, estas son S1, S2 y Z. Las variables que no pertenecen a la base son x1 y x2.
Solución factible básica inicial:
x1=x2=0 => reemplazamos en la ecuación 1: 0 + 2. 0 + S1 + 0S2 + 0z =120 => S1=120*,
Reemplazamos en la ecuación 2: 0 + 0 +0S1+ S2 + 0z = 90 => S2=90**,
Reemplazamos en la ecuación 3: -50. 0- 80....