Tablas

EJERCICIO

RESPUESTA

MÉTODO SIMPLEX DE LAS DOS FASES

Min z=80X1 + 124X2 

s.a:

 X1 + 0.8X2 ≥ 100

 X1 + 2X2 ≥ 200

 X1, X2 ≥ 0

1)

Min z=0X1 + 0X2 + 0H1 + 0H2 + 1A1 + 1A2

s.a

 X1 + 0.8X2 - H1 + A1 = 100

X1 + 2X2 - H2 + A2 = 200

X1, X2, H1, H2, A1, A2 ≥ 0

Donde H es una variable de holgura y A una variable artificial.

PRIMERA FASE

TABLA 1 

En la primera fila se ubican los coeficientes de la función objetivo, por eso la fila inicia en la tercera columna con la notación Cj (costos de la función objetivo), que como se podrá ver son 0, 0, 0, 0, 1,1. En la segunda fila aparecen los nombres de las seis variables (X1, X2, H1, H2, A1, A2) coincidiendo cada variable con los valores o costos de la primera fila.

· En la primera columna ubicamos la notación XB que representa a las variables básicas y puede ver que bajo de ella aparecen, A1, A2. Cuando se inicia la primera fase del Simplex se debe empezar con las variables artificiales como variables básicas.

En la segunda columna, segunda fila ubicamos la notación CB, esta notación representa a los coeficientes o costos de las variables básicas que aparecen en la primera columna, los cuales son: A1=1 y A2=1. Como se muestra en la tabla.

En la tercera columna, segunda fila ubicamos la notación “b” que representa los valores de los lados derechos de las ecuaciones o restricciones del problema.

En la cuarta columna, segunda fila ubicamos la variable X1 y debajo de ella los coeficientes respectivos en cada una de las dos ecuaciones.

En la quinta columna, segunda fila ubicamos la variable X2 y debajo de ella los coeficientes respectivos en cada una de las dos ecuaciones.

En la sexta columna, segunda fila ubicamos la variable H1 y debajo de ella los coeficientes respectivos en cada una de las dos ecuaciones.

En la séptima columna, segunda fila ubicamos la variable H2 y debajo de ella los coeficientes respectivos en cada una de las dos ecuaciones.

En la octava columna, segunda fila ubicamos la variable A1 y debajo de ella los coeficientes respectivos en cada una de las dos ecuaciones.

En la novena columna, segunda fila ubicamos la variable A2 y debajo de ella los coeficientes respectivos en cada una de las dos ecuaciones.

En la décima columna ubicamos la palabra “Ratio” y debajo de ella los cocientes que resultan de dividir el valor de cada “b” por el coeficiente de la variable que se elija como entrante a las básicas.

En la quinta fila ubicamos la notación Zj que representa el resultado de multiplicar cada costo de las variables básicas por cada columna donde se ubican las variables del modelo.

En la sexta fila ubicamos la notación Cj – Zj que es la diferencia entre los costos y los valores de Zj que calculamos en la fila anterior

ITERACIÓN 1

Una vez que hemos llenado la tabla procedemos a realizar el proceso de optimización (1ra. Fase) para lo cual se debe: -0.4*F4+F3 0.5*f4

1. Observamos la sexta fila y buscamos los Cj – Zj < 0 y podemos ver que hay dos valores -2 y -2.8, seleccionando al más negativo, o sea -2.8 correspondiente a la variable X2, que será la variable que entrará a ser básica.

2. Una vez seleccionada X2 procederemos obtener los cocientes de cada b entre los coeficientes de X2. 100 0.8 ⁄ = 120; 200 2 ⁄ = 100, el cociente más pequeño es 100, esto indica que la variable básica que saldrá es A2. 3. El número pivote es 2, por lo que procedemos a multiplicar por la fila por 0.5, con el propósito de que el número pivote sea uno. (ver tabla 2) 4. Ahora debemos hacer cero el valor 0.8 encima del valor pivote para ello multiplicamos la fila 4 por -0.4 y el resultado se lo sumamos a la fila 3. (ver tabla 2)

5. Ahora calculamos los Zj en cada columna de las variables del tabloide (ver tabla 2)

6. Calculamos los Cj – Zj y los resultados los vemos en la tabla 2.

TABLA 2

ITERACIÓN 2

1. Observamos la sexta fila y buscamos los Cj – Zj < 0 y podemos ver que hay dos valores -0.6 y -0.4, seleccionando al más negativo, o sea -0.6 correspondiente a la variable X1, que será la variable que entrará a ser básica.

2. Una vez seleccionada X1 procederemos obtener los cocientes de cada b entre los coeficientes de X1. 20 0.6 ⁄ = 33.33; 100 0.5 ⁄ = 200, el cociente más pequeño es 33.33, esto indica que la variable básica que saldrá es A1.

3. El número pivote es 0.6, por lo que procedemos a multiplicar por la fila por 1/0.6, con el propósito de que el número pivote sea uno. (ver tabla 3)

4. Ahora debemos hacer cero el valor 0.5 debajo del valor pivote para ello multiplicamos la fila 3 por -0.5 y a la fila 4 por 0.6. y sumamos dichas filas (ver tabla 3).

5. Ahora calculamos los Zj en cada columna de las variables del tabloide (ver tabla 3)

6. Calculamos los Cj – Zj y los resultados los vemos en tabla 3.

TABLA 3

Vemos los Cj-Zj de la tabla 3 y vemos que no hay ningún valor menor que cero, es decir que todos los Cj-Zj ≥ 0. Por lo que hemos llegado al fin de la 1ra. Fase. Esto nos permite pasar a la 2da. Fase.

SEGUNDA FASE

· Se sustituyen los Cj por los originales y se recalcula la solución

· Se eliminan las variables artificiales de la última tabla.

· Recalcula los Zi y los Cj-Zj

Obtenemos la siguiente tabla:

• Observamos la sexta fila y buscamos los Cj – Zj ≥0 por lo que hemos llegado al óptimo.

Por lo que la solución óptima será:

X1=33.33 

X2=83.33 

Z=80*33.33 + 124*83.33= 12,999.32=13,000

MÉTODO SIMPLEX

MaxZ= 100X1 + 200X2 

S.A.

 4X1 + 2X2  16 (Ecuación 1) 

8X1 + 8X2 16 (Ecuación 2) 

2X2 10 (Ecuación 3) X1, X2 0

1. Agregar variables de holgura

Max Z = 100X1 + 200X2 + 0S1 + 0S2 + 0S3 = 0

S.A

4X1 + 2X2 + S1 = 16 (Ecuación 1)

8X1 + 8X2 + S2 = 16 (Ecuación 2)

2X2 + S3 = 10 (Ecuación 3)

X1, X2, 0S1, 0S2, 0S3 0

2. Determinar las variables básicas y las no básicas.

3. Elaborar la tabla inicial del Simplex.

4. Elección de la columna pivote (variable que entra).El coeficiente de Z más negativo = Columna X2

5. Elección de la fila pivote (variable que sale).

Razón = Solución / Coeficiente columna pivote

Razón Menor = Fila perteneciente a S1.

6. Elaborar la nueva tabla del simplex.

La nueva tabla Simplex:

Como no hay más iteraciones debido a que no existen coeficientes de Z negativos en la nueva tabla el valor máximo se alcanza para:

X2 = 2

Z = 400.

CONCEPTO

CARACTERÍSTICA DEL CONCEPTO

ALGORITMO SIMPLEX

Busca el óptimo de un problema de P.L. recorriendo sólo algunos de los vértices del poliedro que representa el conjunto de soluciones factibles.

• Se requiere forma estándar.
• Sólo se incluye variables de holgura.
• Las bi’s deben ser positivas.
• Las variables deben ser no negativas.

PASOS:

1. Convierta el modelo PL a su forma estándar.

2. Obtenga una SBF a la forma estándar.

3. Determine si la SBF es óptima: Si hay una variable no básica cuyo aumento hace que el valor actual de la función a maximizar suba, entonces la solución actual no es óptima.

4. Si la SBF no es óptima, determine la variable no-básica que debería convertirse en básica (la de mayor impacto en la función objetivo) y cual variable básica debería convertirse en una no-básica (la que impone una restricción mayor a la variable de mayor impacto). Con la selección anterior y usando operaciones elementales de renglón determine una SBF nueva adyacente a la anterior.

5. Reinicie con el paso 3 con la nueva SBF

EMPATE EN VARIABLE DE ENTRADA

Cuando se produce un empate en la condición de decisión de la variable entrante se puede optar por cualquiera de ellas sin que esto afecte a la solución final. Por contra si influye en el número de iteraciones necesarias para obtener dicha solución. Se aconseja optar a favor de las variables básicas ya que ellas son las que formarán parte de la solución óptima.

EMPATE EN VARIABLE DE SALIDA

Se puede nuevamente optar por cualquiera de ellas. Sin embargo, a fin de no alargar el problema y evitar la entrada en un bucle infinito (caso degenerado), se discrimina a favor de las variables de decisión haciendo que permanezcan en la base.

EQUIVALENCIAS

REGLAS DE EQUIVALENCIA:

• Maximizar Z es equivalente a minimizar –Z
• Minimizar Z es equivalente a Maximizar –Z
• Una desigualdad AX ≤ B es equivalente a –AX ≥ -B
• Una desigualdad AX ≥ B es equivalente a –AX ≤ -B
• Toda restricción de la forma AX = B se puede establecer como la intersección de dos desigualdades AX ≤ B y AX ≥ B

FORMA AUMENTADA

Cuando el origen no pertenece a la solución inicial se agregan variables artificiales, estas sólo se agregan en las restricciones que no contienen variables de holgura, a este modelo se le conoce como forma aumentada.

FORMA CANÓNICA

Un problema de P.L. está en la forma canónica si para un problema de:

• Maximización: Las restricciones son del tipo ≤ y las variables son no-negativas.
• Minimización: Las restricciones son del tipo ≥ y las variables son no-negativas.

FORMA ESTANDAR

Un modelo de PL se dice que está en su forma estándar si cada restricción es una igualdad y las restricciones de signo para cada variable son del tipo mayor o igual que cero. M ecuaciones con N incógnitas (incluye variable de holgura y/o exceso)

MÉTODO DE LAS DOS FASES

El Método de las Dos Fases es una variante del Algoritmo simplex, que es usado como alternativa al Método de la M grande, donde se evita el uso de la constante M para las variables artificiales.

FASE 1. Formule un nuevo problema reemplazando la función objetivo por la suma de las variables artificiales.

La nueva función objetivo se minimiza sujeta a las restricciones del problema original. Si el problema tiene un espacio factible el valor mínimo de la función objetivo óptima será cero, lo cual indica que todas las variables artificiales son cero. En este momento pasamos a la fase 2.

* Si el valor mínimo de la función objetivo óptima es mayor que cero, el problema no tiene solución y termina anotándose que no existen soluciones factibles.

FASE 2. Utilice la solución óptima de la fase 1 como solución de inicio para el problema original. En este caso, la función objetivo original se expresa en términos de las variables no básicas utilizando las eliminaciones usuales Gauss-Jordan.

MÉTODO M GRANDE

El método M grande comienza con la programación lineal en forma de ecuación. Una ecuación i que no tenga una holgura (o una variable que pueda hacer el papel de una holgura). Se aumenta con una variable artificial, A₁, para formar una 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 en forma automática de hacer que esas variables tengan un nivel cero. En otras palabras, la solución final será como si las variables artificiales nunca hubieran existido en primer lugar. El resultado deseado se obtiene penalizando las variables artificiales en la función objetivo.

Pasos:

1. Se debe llevar a la forma estándar cambiando cada restricción por una igualdad.

2. Se debe Penalizar la Función Objetivo

3. Antes de pasar al paso inicial debemos a cada restricción que posea una variable inicial, se debe multiplicar por M y sumarla con a la función objetivo.

4. Crear la tabla con la función objetivo resultante.

5. Aplicar el método Simplex Conocido (iterar por Gauss Jordan).

OPTIMALIDAD

En problemas de maximización, el P.L. es óptimo si todos los costes reducidos
 
 ( son menores o iguales que cero. En problemas de minimización cada coste reducido debe ser mayor o igual que cero.

SOLUCIÓN BÁSICA

Es aquella que tiene al menos n-m componentes nulos o variables no básicas, el resto de las variables (m) se resuelven con sistema de ecuaciones.

SOLUCIÓN BÁSICA FACTIBLE

Todas las variables básicas son mayores o iguales que cero y n-m valen 0 (puntos extremos de la región factible)

VARIABLE ARTIFICIAL

Una variable artificial es un truco matemático para convertir inecuaciones "≥" en ecuaciones, o cuando aparecen igualdades en el problema original, la característica principal de estas variables es que no deben formar parte de la solución, dado que no representan recursos. Estas variables se representan por la letra "A", siempre se suman a las restricciones.

VARIABLE DE ENTRADA

Se refiere a la variable no básica en el renglón “z” con el coeficiente más negativo, si se trata de una maximización, o el coeficiente más positivo, si se trata de una minimización que en el siguiente punto adyacente se convierte en variable básica.

VARIABLE DE EXCESO

Son variables que se restan en las restricciones con signo ≥

VARIABLE DE HOLGURA

Son variables que se suman en las restricciones con signo ≤

VARIABLE DE SALIDA 

Variable básica asociada con la mínima razón no negativa con el coeficiente más negativo, si se trata de una maximización, o el coeficiente más positivo, si se trata de una minimización, la cual, en la tabla de solución siguiente, pasará a ser variable no básica.

VARIABLES BÁSICAS

Variable de decisión que se conserva dentro del nuevo sistema y se utiliza para resolverlo.

VARIABLES NO BÁSICAS

Variable de decisión que deliberadamente se hace cero.

VARIABLES NO RESTRINGIDAS

Algunas veces las variables de decisión pueden tomar cualquier valor real.

Xi s.r.s

Cambio de variable Xi = Ui – Vi

Ui …. Parte positiva de Xi

Vi …. Parte negativa de Xi