Optimización 1

Concepto

Características.

Criterio de Optimalidad.

Minimización: Solución óptima cuando Cj≥0 para todo Xj.

(Se encuentra solución óptima cuando todos los coeficientes Cj de las variables Xj son positivas).

Maximización: Solución óptima cuando Cj≤0 para todo Xj.

(Se encuentra solución óptima cuando todos los coeficientes Cj de las variables Xj son negativos).

Criterio de Variable de Entrada.

Minimización: Sea Cj= mínimo {Cj|Cj<0}.

(Se toma el coeficiente mínimo de los coeficientes Cj negativos).

Maximización: Sea Cj= máximo {Cj|Cj>0}

(Se toma el coeficiente máximo de los coeficientes Cj positivos).

Criterio de Variable de Salida.

Razón: min {Bi/yi|yi>0}

(Se toma la razón entre el vector solución dividido por los valores encontrados en el vector de la variable de entrada, siempre que sean diferentes de cero, y sean positivos).

Método Simplex.

Funcionalidad con n variables.

Detección de soluciones no acotadas y múltiples.

No detecta soluciones factibles.

Se requiere el origen en la región factible.

Método de la M Grande.

Se transporta afuera del origen.

Utiliza variables artificiales.

Detecta soluciones no factibles.

Aplicación de Simplex con variables M.

Método de las 2 Fases.

No utiliza a la variable M en el Simplex.

Se aplica dos veces el método Simplex.

Se generan dos funciones objetivo, w y z.

W es función con relación a las variables artificiales.

Z es función con relación a las variables de decisión.

W se minimiza en la primera fase (eliminación de las variables artificiales).

Z se aplica según sea el caso, con la base generada en la fase uno (fase dos).

Método Gráfico.

Método visual.

Se aplica a cualquier tipo de restricción.

No puede aplicarse a n variables.

Se aplica a lo más a 3 variables.

Método Simplex Revisado

Elimina las operaciones de más aplicadas en el Simplex.

Utilización de matrices para la resolución del Simplex.

Pensado para problemas con poca información.

Planeado para ser programado.

Solución Básica Factible.

Es aquella Base que se encuentra dentro de la región factible y que representa un vértice del dominio de factibilidad.

Variable Artificial.

Variable empleada mediante un artificio matemático (no demostrado) que permite convertir inecuaciones en ecuaciones en el método de la M Grande y 2 Fases. Lo cual nos permite trabajar fuera del origen.

Forma canónica de maximización

Modelo maximizado con todas las restricciones menor o igual y el vector b mayor que cero , con el vector x mayor que cero.

Forma canónica de minimización

Modelo minimizado con todas las restricciones mayores o iguales y el vector b mayor que cero, con el vector x mayor que cero.

Equivalencias

Formas de reinterpretar variables de tal modo que el sistema pueda representarse de la forma estándar o canónica de maximización o minimización.

Variables de holgura

Variables positivas agregada al lado izquierdo de una restricción menor o igual que convierte a la restricción en una igualdad.

Variables de exceso

Variables negativas agregadas al lado izquierdo de una restricción mayor o igual que convierte a la restricción en una igualdad.

Forma estándar

Una función objetivo, con variables básicas no negativas y con restricciones representadas con igualdades.

Solución básica

Se cumple al tener al menos n-m variables iguales a cero.

Solución básica factible

Se cumple al tener todas sus variables básicas mayores a cero, (gráficamente se habla de los puntos extremos de la región).

Variables básicas

Son variables que representadas en la forma matricial o en tablas con un vector columna de ceros y un uno o vector identidad, toman valores mayores a cero en la solución del problema.

Variables no básicas

Son variables que valen cero en la solución del problema.

Ejercicio 1.

Respuesta: (Método Simplex Revisado)

Max Z = 3x1 + 2x2

- x1 + 2x2 + x3 = 4

3x1 + 2x2 + x4 = 14

x1 - x2 + x5 = 3

xi ≥ 0

Cj 3 2 0 0 0

CB Base   x1   x2   x3   x4   x5 b

0      x3     -1    2      1     0    0   4

 0     x4      3    2      0     1    0  14

0      x5      1   -1      0     0    1   3

          Cj     3    2       0     0    0   Z = 0

CB Base   x1   x2   x3   x4   x5   b

 0      x3    0     1      1     0    1    7

0       x4    0     5       0    1    -3    5

3       x1    1    -1      0      0     1   3

          Cj     0     5     0      0     -3   Z = 9

CB Base    x1   x2   x3   x4   x5   b

0     x3       0     0      1 -1/5  8/5 6

2     x2       0      1      0 1/5 -3/5 1

3       x1      1      0      0 1/5 2/5 4

         Cj      0       0      0 -1      0   Z = 14

CB  Base x1 x2   x3      x4     x5   b

 0     x5    0   0   5/8   -1/8    1   15/4

2      x2    0   1   3/8   1/8     0   13/4

3      x1    1   0   -1/4   1/4    0   5/2

         Cj     0    0   0      -1       0   Z = 14

Ejercicio 2.

Respuesta: (Método de las 2 Fases)

Min z= -3x1+5x2

s.a

x1≤4

x2≤6

3x1+2x2≥18

xi≥0

1.- Escribirla función en su forma ampliada:

Min z= -3x1+5x2

s.a.

x1+x3=4

x2+x4=6

3x1+2x2-x5+a1=18

Xi,ai≥0

Recordando que las variables artificiales ai se colocan siempre que existan variables de exceso e igualdades en la función objetivo principal.

2.- Generar la función objetivo w minimizada.

Min w=a1

s.a.

x1+x3=4

x2+x4=6

3x1+2x2-x5+a1=18

Xi,ai≥0

Recordando que siempre se buscará minimizar a la función objetivo nueva (w) con el fin de eliminar la(s) variables artificiales que nos permiten trabajar fuera del origen.

3.- Calculamos wj-cj y zj-cj:

Wj-cj= -a1

Zj-cj= 3x1-5x2

4.- Aplicamos el método simplex de forma simultanea a wj-cj como a zj-cj.

TABLA 1:

             X1      X2       X3      X4       X5     a1    Sol

Wj-cj    0         0         0         0         0       -1      0

Zj-cj      3        -5         0        0         0        0       0

X3         1         0         1        0         0        0       4     

X4         0         1         0        1         0        0       6

a1         3         2         0        0         -1       1       18

Por lo que se puede apreciar que el vector de a1 por ser variable básica debe de tener un vector unitario, efectuando las operaciones necesarias para que esto se cumpla se genera una nueva tabla.

TABLA 2:

             X1      X2       X3      X4       X5     a1    Sol

Wj-cj    3         2         0         0        -1       0      18

Zj-cj      3        -5         0        0         0        0       0

X3         1         0         1        0         0        0       4     

X4         0         1         0        1         0        0       6

a1         3         2         0        0         -1       1       18

Teniendo nuestra nueva tabla corregida, aplicando el criterio de variable de entrada procedemos a calcular la razón de cada uno, generando así las variables de salida (criterio de variable de salida) que quedan de la forma:

V.E.= X1

V.S.= X3

Por lo que la nueva tabla, aplicando simplex queda de la siguiente manera.

TABLA 3:

             X1      X2       X3      X4       X5     a1    Sol

Wj-cj    0         2         -3       0        -1       0       6

Zj-cj      0        -5        -3        0         0       0      -12

X1         1         0         1        0         0        0       4     

X4         0         1         0        1         0        0       6

a1         0         2         -3       0         -1       1       6

Aplicando de nuevo los criterios tenemos que las nuevas variables de entrada y salida son:

V.E.=X2

V.S.=a1

Por lo que la nueva tabla queda de la siguiente manera.

TABLA 3:

             X1      X2       X3      X4       X5     a1    Sol

Wj-cj    0         0         0         0         0      -1      0

Zj-cj      0         0     -21/2     0      -5/2     0       3

X1         1         0         1        0         0        0       4     

X4         0         0       3/2      1       1/2     1/2    3

X2         0         1      -3/2      0     -1/2     1/2     3

Como podemos observar la variable artificial ya fue eliminada de la base, y como se aplicó el método simplex simultáneamente a zj-cj podemos pasar a la fase 2, partiendo con zj-cj como nuestra función objetivo principal, sin embargo, aplicando el criterio de variable de entrada, nos damos cuenta que todas las cj de las xj se encuentran de forma negativa, por lo que directamente se puede concluir lo siguiente:

X1=4

X2=3

X3=X5=a1=w=0

X4=3

Z=3