Método Simplex – Minimización
Páginas: 6 (1295 palabras)
Publicado: 17 de febrero de 2013
MATE 3012
Método Simplex – minimización
Problema de minimización estándar
Un problema de minimización de programación lineal está en la forma estándar, si la función objetiva �� = ��1 ��1 + ��2 ��2 + ��3 ��3 + ⋯ + ���� ���� debe ser minimizada, sujeto a las restricciones
El procedimiento básico utilizado para resolver este tipo de problema es • convertirlo a un problema de maximizaciónen la forma estándar (conocido como el problema se maximización dual) • aplicar el método Simplex según lo presentamos en ejercicios anteriores.
Problema de minimización estándar procedimiento
1. Formar la matriz aumentada para el sistema de desigualdades dado, y añadir en la última fila los coeficientes de la función objetiva. 2. Armar la traspuesta de la matriz aumentada. 3. Dada unamatriz A, se llama matriz traspuesta de A a la matriz que se obtiene cambiando ordenadamente las filas por las columnas. Ejemplo:
matriz A
matriz traspuesta de A se denota At
Problema de minimización estándar
4. Formar el problema de maximización dual de la traspuesta. 5. Aplicar el método simplex para el problema de maximización dual. 6. El valor máximo de z será el valor mínimo de w. 7.Los valores de x1, x2,. . . , y xn ocurren en la fila inferior de la tabla simplex final, en las columnas correspondientes a las variables de holgura.
Problema de minimización estándar
Minimizar la función objetiva dada si la función está sujeta a las siguientes restricciones
Solución: La matriz aumentada correspondiente a este problema de minimización es
Así, la matriz correspondiente alproblema de maximización dual está dada por la siguiente transpuesta.
Problema de minimización (cont.)
Minimizar la función objetiva dada si la función está sujeta a las siguientes restricciones
Solución (continuación): Esto implica que el problema de maximización dual es como sigue. Buscar el valor máximo de la función objetivo dual:
sujeto a las limitaciones:
Procedimento delMétodo Simplex
Paso 1: Introducir una variables de holgura para cada restricción en el sistema y para la función objetiva. Despesjar la función objetiva.
2��1 + ��2 + ��1 = 3 ��1 + ��2 + ��2 = 2 ��1 ≥ 0, ��2 ≥ 0, ��1 ≥ 0, ��2 ≥ 0 Z − 6��1 − 4��2 + 0��1 + 0��2 = 0
Paso 2: Tabla para cálculos.
2��1 + ��2 + ��1 = 3 ��1 + ��2 + ��2 = 2 Z − 6��1 − 4��2 + 0��1 + 0��2 = 0
Se coloca una filapara cada restricción y la una fila con los coeficientes de la función objetivo:
Solución
y1 2 1 -6
y2 1 1 -4
s1 1 0 0
s2 0 1 0
Constantes
s1 s2 Z
3 2 0
1ra iteración: Paso 1: Determinar cuál variable debe entrar en la base
y1 2 1 y2 1 1 s1 1 0 s2 0 1
Solución
Constantes
s1
3 2
s2
Z
-6
-4
0
0
0
Para escoger la variable de decisión queentra en la base, observamos la fila que muestra los coeficientes de la función objetiva y escogemos la variable con el coeficiente más negativo.
Paso 2: Determinar cuál variable de holgura debe salir de
la solución
Solución
y1 2 1 -6
y2 1 1 -4
s1 1 0 0
s2 0 1 0
Constantes
s1
s2 Z
3 2 0
3 / 2 1.5
2 /1 2
Para encontrar la variable de holgura que tiene quesalir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero .
Paso 3: Hacer que el pivote sea 1, y que hayan ceros
debajo del pivote.
Solución
y1 1
y2 0.5
s1 0.5
s2 0
Constantes
s1
s2 Z
1.5
1
-6
1
-4
0
0
1
0
2 R1 R2
0 6R R 13
Paso 4: Hacer que el pivote sea 1, y que hallan ceros
debajo del pivote. (continuación)
Solución
y1 1 0 0
y2 0.5 0.5 -1
s1 0.5 -0.5 3
s2 0 1 0
Constantes
y1 s2 Z
1.5 0.5 9
• Fin de la primera iteración. • Repetimos el proceso por que aún hay negativos en la última fila.
La solución ahora es:
��1 1.5 ��2 0 ��1 = 0 ��2 0.5 �� 9
2da iteración:
Paso 1:...
Método Simplex – minimización
Problema de minimización estándar
Un problema de minimización de programación lineal está en la forma estándar, si la función objetiva �� = ��1 ��1 + ��2 ��2 + ��3 ��3 + ⋯ + ���� ���� debe ser minimizada, sujeto a las restricciones
El procedimiento básico utilizado para resolver este tipo de problema es • convertirlo a un problema de maximizaciónen la forma estándar (conocido como el problema se maximización dual) • aplicar el método Simplex según lo presentamos en ejercicios anteriores.
Problema de minimización estándar procedimiento
1. Formar la matriz aumentada para el sistema de desigualdades dado, y añadir en la última fila los coeficientes de la función objetiva. 2. Armar la traspuesta de la matriz aumentada. 3. Dada unamatriz A, se llama matriz traspuesta de A a la matriz que se obtiene cambiando ordenadamente las filas por las columnas. Ejemplo:
matriz A
matriz traspuesta de A se denota At
Problema de minimización estándar
4. Formar el problema de maximización dual de la traspuesta. 5. Aplicar el método simplex para el problema de maximización dual. 6. El valor máximo de z será el valor mínimo de w. 7.Los valores de x1, x2,. . . , y xn ocurren en la fila inferior de la tabla simplex final, en las columnas correspondientes a las variables de holgura.
Problema de minimización estándar
Minimizar la función objetiva dada si la función está sujeta a las siguientes restricciones
Solución: La matriz aumentada correspondiente a este problema de minimización es
Así, la matriz correspondiente alproblema de maximización dual está dada por la siguiente transpuesta.
Problema de minimización (cont.)
Minimizar la función objetiva dada si la función está sujeta a las siguientes restricciones
Solución (continuación): Esto implica que el problema de maximización dual es como sigue. Buscar el valor máximo de la función objetivo dual:
sujeto a las limitaciones:
Procedimento delMétodo Simplex
Paso 1: Introducir una variables de holgura para cada restricción en el sistema y para la función objetiva. Despesjar la función objetiva.
2��1 + ��2 + ��1 = 3 ��1 + ��2 + ��2 = 2 ��1 ≥ 0, ��2 ≥ 0, ��1 ≥ 0, ��2 ≥ 0 Z − 6��1 − 4��2 + 0��1 + 0��2 = 0
Paso 2: Tabla para cálculos.
2��1 + ��2 + ��1 = 3 ��1 + ��2 + ��2 = 2 Z − 6��1 − 4��2 + 0��1 + 0��2 = 0
Se coloca una filapara cada restricción y la una fila con los coeficientes de la función objetivo:
Solución
y1 2 1 -6
y2 1 1 -4
s1 1 0 0
s2 0 1 0
Constantes
s1 s2 Z
3 2 0
1ra iteración: Paso 1: Determinar cuál variable debe entrar en la base
y1 2 1 y2 1 1 s1 1 0 s2 0 1
Solución
Constantes
s1
3 2
s2
Z
-6
-4
0
0
0
Para escoger la variable de decisión queentra en la base, observamos la fila que muestra los coeficientes de la función objetiva y escogemos la variable con el coeficiente más negativo.
Paso 2: Determinar cuál variable de holgura debe salir de
la solución
Solución
y1 2 1 -6
y2 1 1 -4
s1 1 0 0
s2 0 1 0
Constantes
s1
s2 Z
3 2 0
3 / 2 1.5
2 /1 2
Para encontrar la variable de holgura que tiene quesalir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero .
Paso 3: Hacer que el pivote sea 1, y que hayan ceros
debajo del pivote.
Solución
y1 1
y2 0.5
s1 0.5
s2 0
Constantes
s1
s2 Z
1.5
1
-6
1
-4
0
0
1
0
2 R1 R2
0 6R R 13
Paso 4: Hacer que el pivote sea 1, y que hallan ceros
debajo del pivote. (continuación)
Solución
y1 1 0 0
y2 0.5 0.5 -1
s1 0.5 -0.5 3
s2 0 1 0
Constantes
y1 s2 Z
1.5 0.5 9
• Fin de la primera iteración. • Repetimos el proceso por que aún hay negativos en la última fila.
La solución ahora es:
��1 1.5 ��2 0 ��1 = 0 ��2 0.5 �� 9
2da iteración:
Paso 1:...
Leer documento completo
Regístrate para leer el documento completo.