UNIDAD 3

UNIDAD 3: METODO SIMPLEX

EL METODO SIMPLEX: Transición del método grafico al método Simplex

Como ya vimos el método gráfico indica que la solución óptima, de un programa lineal, siempre está asociada a un punto esquina del espacio de soluciones factibles. Este resultado es la clave del Método Simplex algebraico, y en general para resolver cualquier modelo de programación lineal.

La transición de la solución del punto esquina geométrico, hasta el método simplex, implica un procedimiento de computo que determina en forma algebraica los puntos esquinas. Esto se logra convirtiendo primero a todas las restricciones del modelo, de desigualdades a ecuaciones (el modelo en forma estándar), para luego manipular esas ecuaciones en forma sistemática.

Una propiedad general del método Simplex es que resuelve la programación lineal en iteraciones. Cada iteración desplaza la solución a un nuevo punto esquina,  que tiene potencial de mejorar el valor de la función objetivo. El proceso termina cuando ya no se pueden tener mejoras. El método simplex implica cálculos voluminosos y tediosos, lo que hace que la computadora sea una herramienta esencial para resolver los problemas de programación lineal. Por consiguiente las reglas computacionales del método simplex se adaptan para facilitar el cálculo.

Como ya dijimos, el método simplex usa un procedimiento inteligente de búsqueda, diseñado para llegar al punto esquina óptimo en forma eficiente. El algoritmo simplex aumenta el valor de las variables una por una, hasta llegar al punto óptimo.  El método Simplex proporciona una regla definida, para determinar que variable aumentar, esto para facilitar el desarrollo de un programa de computo.

El Método Simplex: Calculo del Algoritmo Simplex.

Como ya dijimos, el método simplex usa un procedimiento inteligente de búsqueda, diseñado para llegar al punto esquina óptimo en forma eficiente. El algoritmo simplex aumenta el valor de las variables una por una, hasta llegar al punto óptimo.  El método Simplex proporciona una regla definida, para determinar que variable aumentar, esto para facilitar el desarrollo de un programa de computo.

En forma específica como se está maximizando, la variable no básica que tenga el coeficiente positivo más grande, en la función objetivo, es la que se selecciona para aumentar primero.

Téngase en cuenta que solo se trata de una regla fácil que, de acuerdo con la experiencia, generalmente conduce a la menor cantidad de iteraciones. En la terminología del método Simplex X₁ y S₁ en el punto A se llama variable de entrada y de salida respectivamente.

Detalles de cálculo del algoritmo Simplex.

Los detalles de cálculo de una iteración Simplex, que incluye las reglas para determinar las variables de entrada y de salida, así como para determinar los cálculos cuando se llega a la solución óptima, los veremos utilizando el modelo de Comex, ya conocido.

En la forma estándar (de ecuaciones) el modelo Comex se representa así:

Maximizar: Z = 5 X₁ + 4 X₂ + 0S₁ + 0S₂ +0S₃ + 0S₄

Sujeto a:          6 X₁ + 4 X₂ + S₁                   = 24

                          X₁ + 2 X₂      +S₂              = 6

                        - X₁ +   X₂             +S₃            = 1

                                   X₂                   +S₄   = 2

                                  X₁, X_2, S_1, S_2, S₃  y S₄ ≥0

Ya sabemos que S_1, S_2, S₃  y S₄ representa las holguras asociadas a las restricciones respectivas. Luego expresaremos la función objetivo así:

Z - 5X₁ – 4X₂ + 0S₁ + 0S₂ +0S₃ + 0S₄ = 0

De esta forma la tabla inicial del Simplex se expresa así:

Tabla 1: Tabla de inicio Simplex

Básica	Z	X1	X2	S1	S2	S3	S4	Solución.
Z	1	-5	-4	0	0	0	0	0	Renglón Z
S1	0	6	4	1	0	0	0	24	Renglón S1
S2	0	1	2	0	1	0	0	6	Renglón S2
S3	0	-1	1	0	0	1	0	1	Renglón S3
S4	0	0	1	0	0	0	1	2	Renglón S4

Como X_{1 =} 0  y  X₂ = 0 (Se inicia en el origen por ser no básicas), sin más cálculos, de la tabla se determina que:

S₁ = 24      S₂ = 6     S₃ = 1     S₄ = 2  y  Z = 0   ;  (X_{1 =} 0  y  X₂ = 0)

Esta solución se muestra en la tabla con la lista de las variables básicas, en la columna básica de la izquierda, y sus valores en la columna solución de la derecha.

Esto define el punto esquina actual especificando las variables básicas y sus valores. Así como el valor de la función objetivo Z. Recuerden que las variables no básicas, las que no aparecen en la columna básica, siempre son iguales a cero.

Ya dijimos que para determinar las variables de entrada a la solución básica (para la siguiente iteración), se selecciona la variable no básica con mayor coeficiente positivo en la función Objetivo (cuando es de maximizar). Esta regla se basa en la función objetivo original Z=5X₁ + 4X₂.

Como la tabla Simplex expresa la función objetivo en la forma Z - 5X₁ - 4X₂ = 0, la variable de entrada es X_1, porque tiene el coeficiente más negativo en la función objetivo (y es de maximización).

Si todos los coeficientes de la función objetivo fueran ≥ 0, no sería posible mejorar Z y eso indicaría que se habría llegado al óptimo.

Para determinar la variable de salida, en forma directa con la tabla, se calculan las iteraciones, o coordenadas (X₁) al origen, de todas las restricciones con la dirección no negativa del eje X₁ (por ser X₁  la variable de entrada). Esas iteraciones son las razones del lado derecho de las ecuaciones (columna solución), entre los coeficientes de las restricciones correspondientes, abajo de la variable de entrada X₁, como se muestra en la siguiente tabla:

Tabla 2: Definición de Variable de Salida

Básicas	Entrada X1	Solución	Razón o iteración
S1	6	24	X1 = 24/6 = 4	Mínimo
S2	1	6	X1 =   6/1 = 6
S3	-1	1	X1 =  1/-1 = -1	Ignorar.
S4	0	2	X1 = 2/0 =∞ (indefinido)	Ignorar.

La razón no negativa mínima corresponde a S₁ básica, lo que indica que es la variable que tiene que salir (variable de salida). Esto indica que tomara el valor de cero, en la nueva iteración.

El valor de la variable de entrada X₁ en la nueva solución (iteración) es igual a la razón mínima: X₁ = 4 (compárelo con el punto B de la gráfica). El aumento correspondiente a Z es $5 x 4 = $20.00.

El resultado del intercambio de variables de entrada y de salida es que el nuevo punto se define así:

Variable no básicas (= 0),  (S_1, X₂)   ;         Variables básicas    (X₁, S₂, S_3, S₄)

Ahora se deben manipular las ecuaciones de la última tabla, de modo que la columna básica y la columna solución identifiquen la nueva solución. El proceso se llama operaciones de renglón (o fila) de Gauss – Jordan.

Nuevamente veamos la tabla de inicio y asociémosla a la columna Pivote y al reglón Pivote con las variables de entrada y de salida respectivamente. A la intercesión de la columna Pivote y el renglón Pivote se le llama Pivote o elemento Pivote. 

 

                  Entra   Tabla 3: Renglón Pivote, Columna Pivote y Elemento Pivote

Básica	Z	X1	X2	S1	S2	S3	S4	Solución
Z	1	-5	-4	0	0	0	0	0
S1	0	6	4	1	0	0	0	24	Renglón Pivote
S2	0	1	2	0	1	0	0	6
S3	0	-1	1	0	0	1	0	1
S4	0	0	1	0	0	0	1	2
		Columna Pivote	Elemento Pivote.

Para nuestra nueva tabla Simplex, y como producto de los cálculos con Gauss y Jordan tenemos que:

1.      Renglón Pivote:

Nuevo renglón Pivote= Renglón Pivote Actual / Elemento Pivote.

2.      Todos los demás renglones (incluyendo Z)

Nuevo Renglón: Renglón Actual – (su coeficiente en la columna Pivote)(Renglón Pivote Nuevo).       

Tabla 4: Primera iteración

Básica	Z	X1	X2	S1	S2	S3	S4	Solución
Z	1	0	-2/3	5/6	0	0	0	20
X1	0	1	2/3	1/6	0	0	0	4
S2	0	0	4/3	-1/6	1	0	0	2
S3	0	0	5/3	1/6	0	1	0	5
S4	0	0	1	0	0	0	1	2

                 

Puede notarse que la nueva tabla presenta las mismas características de la tabla anterior, por lo tanto, la nueva columna solución muestra la solución, para cada una de las variables básicas (Columnas básicas).

Entonces: X₁ = 4;  S₂ = 2;  S₃ = 5 y S₄= 2.  El Nuevo valor objetivo es: Z= 20

Z = 5(4) + 4(0) + 0(0) + 0(2) +0(5) + 0(2) = 20

Este acontecimiento de la tabla es producto de las operaciones de fila (renglón) de Gauss y Jordan.

En base a la última tabla, vamos a definir las nuevas variables de entrada y salida.

Como: Z= 2/3 X₂ – 5/6 S₁ + 20     o    (Z- 2/3 X₂ + 5/6 S₁ = 20)

                                  Entra         Columna Pivote.

Básica	Z	X1	X2	S1	S2	S3	S4	Solución
Z	1	0	-2/3	5/6	0	0	0	20
X1	0	1	2/3	1/6	0	0	0	4
S2	0	0	4/3	-1/6	1	0	0	2
S3	0	0	5/3	1/6	0	1	0	5
S4	0	0	1	0	0	0	1	2

Entonces: La nueva variable de entrada es: X₂. Ahora para la variable de salida, generamos la tabla de razones (intersecciones):

Tabla 5: Definición de Variable de Salida

Básicas	Entrada  X2	Solución	Razón o iteración
X1	2/3	4	X2 = 4 / (2/3) = 6
S2	4/3	2	X2 = 2 / (4/3) = 3/2	Mínimo
S3	5/3	5	X2 = 5 /  (5/3) = 3
S4	1	2	X2 = 2 /  1       = 2

La variable de salida es S₂, y nuestra nueva tabla simplex, queda así:

Tabla 6: Segunda Iteración/Solución óptima

Básica	Z	X1	X2	S1	S2	S3	S4	Solución
Z	1	0	0	3/4	1/2	0	0	21
X1	0	1	0	1/4	-1/2	0	0	3
X2	0	0	1	-1/8	3/4	0	0	3/2
S3	0	0	0	3/8	-5/4	1	0	5/2
S4	0	0	0	1/8	-3/4	0	1	1/2

Como ninguno de los coeficientes del renglón, son negativos, esta última tabla es Óptima.

De la última tabla concluimos que:

X₁ = 3              Hay que producir 3 toneladas diarias de Pintura externa.

X₂ =3/2              Hay que producir 1.5 toneladas diarias de Pintura interna.

Z= 21                La utilidad diaria es de $21,000.00

Los valores de S₁  y S₂ es Cero y S₃ =5/2 y S₄ = ½

La tabla Simplex muestra una gran cantidad de información adicional que comprende:

1.      El estado de los recursos.

2.      El valor por unidad de los recursos (precios duales).

3.      Todos los datos necesarios para efectuar un análisis de sensibilidad.

Estado de los recursos: un recurso se llama escaso si las actividades (variables) del modelo la usan por completo, en caso contrario se dice que es abundante. Esta información se obtiene en la tabla óptima, revisando el valor de la variable de holgura asociada con la restricción que representa al recurso. Si la variable de holgura es cero, el recurso se usa por completo, y el recurso es escaso. Una holgura positiva indica que el recurso es abundante.

Si revisamos la tabla óptima del ejemplo Comex, tenemos:

Recursos	Variables de Holgura	Estado o condición
Mat. Prima M1	S1 =0	Escasa.
Mat. Prima M2	S2 = 0	Escasa.
Límite de Demanda 1	S3 =5/2	Abundante.
Límite de Demanda 2	S4 = ½	Abundante.

Tabla 7: Estado de los Recursos

El estado de los recursos indica que está garantizado un aumento en la disponibilidad de las materias primas M1 y M2, porque las dos son escasas. La cantidad del aumento se establece mediante el análisis de sensibilidad que veremos más adelante.

En una minimización la selección de la variable de salida es igual que en el caso de maximización. Para la variable de entrada, en el caso de minimización, se selecciona la variable no básica con el coeficiente más positivo de la función objetivo (renglón Z) y se llega de Z mínimo (Optimo) cuando todos los coeficientes del renglón Z  son no positivos.

Las reglas para definir las variables de entrada y de salida se llaman condiciones de Optimalidad y de Factibilidad.

Resumen del Método Simplex:

 Hasta ahora nos hemos ocupado en maximización. El problema de minimización, la condición de Optimalidad requiere seleccionar la variable de entrada, como la variable no básica, con el coeficiente objetivo, más positivo en la ecuación objetivo (renglón Z), la regla es aptamente opuesta al caso de maximización. En cuanto a la condición de factibilidad para seleccionar la variable de salida la regla no cambia.

Condición de Optimalidad.

La variable  de entrada en un problema de maximización (o minimización), es la variable no básica con el coeficiente más negativo (positivo), en el renglón Z los vínculos se rompen arbitrariamente. El óptimo se alcanza en la iteración en la cual los coeficientes, en el renglón Z son no negativos (o no positivos).

Condición de Factibilidad:

Tanto en problema de maximización y minimización la variable de salida, es la variable básica, asociada con la razón mínima no negativa con el denominador estrictamente positivo. Los vínculos se rompen arbitrariamente  (dos razones mínimas iguales).

Los pasos del Método Simplex son:

1.      Determine la solución factible básica inicial.

2.      Seleccione una variable de entrada, utilizando la condición de Optimalidad. Deténgase si no hay variable de entrada. La última condición es óptima. De otro modo prosiga con el paso 3.

3.      Seleccione una variable de salida utilizando una condición de factibilidad.

4.      Aplique los pasos de Gauss – Jordan, para determinar la solución básica  y vaya al paso 2

METODO M: Solución Artificial de Inicio.

Como puede observarse el Método Simplex lo hemos utilizado en un modelo de programación lineal donde todas las restricciones son de la forma ≤, con el lado derecho no negativo. Esto ofrece una cómoda solución básica factible de inicio con todas las holguras. Los modelos donde hay restricciones del tipo ≥ o = no ofrece esta solución básica de inicio. A estos modelos se les llama programas lineales de mal comportamiento.

El procedimiento para iniciar la resolución de estos programas lineales (con restricciones ≥ e =) permite que variables artificiales desempeñen el trabajo de holguras, en la primera iteración, para después en alguna iteración posterior, desecharla de forma legítima. Para ello se puede hacer uso de dos métodos muy relacionados entre sí, el método M y el método de dos fases.

El Método M o Método de Penalización:

Comienza con la programación lineal en forma de ecuación (forma estándar).

Una ecuación i, que no tenga una holgura positiva, se aumenta con una variable artificial R_i, para formar una solución de inicio parecida  a la solución básica con todas las holguras. Sin embargo como las variables artificiales son ajenas al modelo de programación lineal, se usa un mecanismo de retroalimentación en el que el proceso de optimización trata de forma automática de hacer que esas variables tengan nivel cero.

Esto significa que al final, la solución será como si las variables artificiales nunca hubiesen existido. El resultado deseado, se obtiene penalizando las variables artificiales en la función objetivo.

Dado M, un valor positivo suficientemente grande, (matemáticamente  M         ∞) el coeficiente objetivo de una variable artificial, representa una penalización adecuada si: 

       

 Al usar esta penalización, el proceso de optimización forzara en forma automática a las variables artificiales para que sean cero (siempre que el problema tenga una solución factible)

Ejemplo:

Minimizar: X0 = 4X₁ + X₂

Sujeto a:         3X₁ +   X₂ = 3

                      4X₁ + 3X₂ ≥ 6

                        X₁ + 2X₂ ≤ 4                       

                           X₁ y X₂ ≥ 0

Modelo en forma Estándar:

Minimizar:   X0 = 4X₁ +  X₂

  Sujeto a:         3X₁ +  X₂                     = 3

                        4X₁ + 3X₂ - S₁       = 6

                          X₁ + 2X₂         +S₂    = 4                       

                           X_1, X_2, S₁ y S₂         ≥ 0

Debido a que existen restricciones ≥ e =, el modelo se transforma en:

Minimizar: X0 = 4X₁ + X₂ + MR₁ + MR₂

Sujeto a:         3X₁ +  X₂           + R₁                       = 3

                      4X₁ + 3X₂ – S₁       + R₂             = 6

                        X₁ + 2X₂                                + S₂  = 4                       

                           X_1,  X_2,  S_1,  S_2, R₁ y R₂    ≥ 0

Como  m= 3 ecuaciones  y  n= 6 variables;

Entonces:  n-m = 6-3 = 3 variables no básicas.

X0 = 4X₁ + X₂ + MR₁ + MR₂    se transforma en:          X0 - 4X₁ - X₂ - MR₁ - MR₂ = 0

Y se tiene la tabla:

Tabla 1: Tabla de inicio (no simplex)

Básicas	X1	X2	S1	R1	R2	S2	Solución
X0	-4	-1	0	-M	-M	0	0
R1	3	1	0	1	0	0	3
R2	4	3	-1	0	1	0	6
S2	1	2	0	0	0	1	4

Debido a que esta solución presenta inconsistencia en la columna solución con el renglón z,  (X0 = 4X₁ + X₂ + MR₁ + MR₂         X0 = 4(0)+ (0) + M(3) + M(6) = 9M) deberá transformarse el renglón z, haciendo uso de la fórmula:

Nuevo Renglón X0= Renglón anterior X0 + (M_X Renglón R₁ + M_X Renglón R₂)

                             Entra

Tabla 2: Tabla de inicio simplex

Básicas	X1	X2	S1	R1	R2	S2	Solución
X0	(-4 + 7M)	(-1 + 4M)	-M	0	0	0	9M
R1	3	1	0	1	0	0	3
R2	4	3	-1	0	1	0	6
S2	1	2	0	0	0	1	4

Solución básica:

R₁ = 3  ;  R₂ = 6  ;  S₂ = 4  ;  X₁ = 0  ;  X₂ = 0  y  S₁ = 0  ;  con  Z = 9M

Variable de salida:

Tabla 3: Definición de Variable de Salida

Básicas	V. Entrada  X1	Solución	Razón o iteración
R1	3	3	X1 = 3/3 = 1	Mínimo
R2	4	6	X1 = 6/4 = 3/2
S2	1	4	X1 = 4/1 = 4

Entra X₁  y Sale R₁                   Elemento Pivote = 3

                                    Entra

Tabla 4: Segunda iteración

Básicas	X1	X2	S1	R1	R2	S2	Solución
X0	0	(1+5M)/3	-M	(4-7M)/3	0	0	(4+2M)
X1	1	1/3	0	1/3	0	0	1
R2	0	5/3	-1	-4/3	1	0	2
S2	0	5/3	0	-1/3	0	1	3

Solución básica:

X₁ = 1  ;  R₂ = 2  ;  S₂ = 3  ;  R₁ = 0  ;  X₂ = 0  y  S₁ = 0  ;  con  Z = 4+2M

Variable de salida:

Tabla 5: Definición de Variable de Salida

Básicas	V. Entrada  X2	Solución	Razón o iteración
X1	1/3	1	X2 = 1/(1/3) = 3
R2	5/3	2	X2 =2/(5/3) = 6/5	Mínimo
S2	5/3	3	X2 =3/(5/3) = 9/5

                                               Entra

                                Tabla 6: Tercera iteración

Básicas	X1	X2	S1	R1	R2	S2	Solución
X0	0	0	1/5	(8/5) - M	(-1/5) - M	0	18/5
X1	1	0	1/5	3/5	-1/5	0	3/5
X2	0	1	-3/5	-4/5	3/5	0	6/5
S2	0	0	1	1	-1	1	1

Solución básica:

X₁ = 3/5  ;  X₂ = 6/5  ;  S₂ = 1  ;  R₁ = 0  ;  R₂ = 0  y  S₁ = 0  ;  con  Z = 18/5

Variable de salida:

Tabla 7: Definición de Variable de Salida

Básicas	V. Entrada  S1	Solución	Razón o iteración
X1	1/5	3/5	S1 = (3/5)/(1/5) = 3
X2	-3/5	6/5	S1 =(-3/5)/(6/5) = -1/2	Ignorar
S2	1	1	S1 =1/1 = 1	Mínimo

Tabla 8: Cuarta iteración (Tabla Óptima)

Básicas	X1	X2	S1	R1	R2	S2	Solución
X0	0	0	0	(7/5) - M	- M	-1/5	17/5
X1	1	0	0	2/5	0	-1/5	2/5
X2	0	1	0	-1/5	0	3/5	9/5
S1	0	0	1	1	-1	1	1

Solución Óptima: X₁ = 2/5  ;  X₂ = 9/5  ;  S₁ = 1  ;  R₁ = 0  ;  R₂ = 0  y  S₂ = 0 

Con  X0 _óptimo = 17/5

Observe que las variables artificiales R₁ y R₂ salen de la solución básica en las iteraciones primera y segunda. Esto resulta consistente con el concepto de penalizar las variables artificiales en la función objetivo. 

Acerca del método M se puede hacer dos observaciones:

1.      El uso de la penalización M podrá no forzar la variable artificial hasta el nivel cero en la iteración Simplex  final, si el problema de programación lineal no tiene una solución factible (es decir, si las restricciones no son consistentes). En este caso, la iteración simplex final incluirá cuando menos una variable artificial a un nivel positivo.

2.     
La aplicación de la técnica M implica, teóricamente, que M       ∞. Sin embargo, al usar la computadora M debe ser finito pero suficientemente grande. ¿Qué tan grande es ¨suficientemente grande¨? Es una pregunta abierta.

En forma específica, M debe ser lo bastante grande como para funcionar como penalización. Al mismo tiempo no debe ser tan grande como para perjudicar  la exactitud de los cálculos simplex, al manipular una mezcla de números muy grandes o muy pequeños.