Método Simplex - Historial de revisiones

Yanna ciget.ltu en 16:46 24 may 2011

2011-05-24T16:46:40Z

Rodney Jc.vcl: /* Tabla para la realización del Método Simplex */

2011-05-11T20:53:26Z

‎Tabla para la realización del Método Simplex

Rodney Jc.vcl: Página creada con '{{Definición |nombre= Método Simplex. |imagen= |tamaño= |concepto=Uno de los Métodos de Solución de la Programación Lineal. }} '''MétodoSimplex''': se basa en un proc...'

2011-05-11T20:49:59Z

Página creada con '{{Definición |nombre= Método Simplex. |imagen= |tamaño= |concepto=Uno de los Métodos de Solución de la Programación Lineal. }} '''MétodoSimplex''': se basa en un proc...'

Página nueva

{{Definición
|nombre= Método Simplex.
|imagen=
|tamaño=
|concepto=Uno de los Métodos de Solución de la [[Programación Lineal]].
}} '''MétodoSimplex''': se basa en un procedimiento algebraico y la explicación geométrica del mismo se puede interpretar a través del método gráfico.

== Conceptos Básicos del Método Simplex ==

*La aplicación del método simplex presupone que se tiene un sistema de restricciones lineales formado sólo por ecuaciones lineales. Esta transformación puede ser llevada a cabo de una forma muy simple introduciendo algunas variables adicionales, las cuales se denominan variables de holgura. Estas variables se definen una para cada restricción y si la misma tiene el signo ≤ la variable de holgura se adiciona y el signo fuera ≥ la variable de holgura se restara.
*Luego que se tiene un problema de [[Programación Lineal]] estándar, es decir, todas las restricciones tienen signos de igualdad es necesario determinar la solución básica factible inicial (S.B.F.I).
*Dado un sistema de m ecuaciones lineales con n variables (AX=b) con m<n y rango r(A)=m. Si escogemos cualquier matriz no singular de orden mxm y si todas las (n-m) variables no asociadas con estas columnas de la matriz son iguales a cero, entonces la solución al sistema de ecuaciones resultante es llamada una solución básica. Como la matriz A consta de n columnas se puede definir la matriz B formada por m columnas linealmente independientes de A, esta matriz la llamaremos matriz básica. Con las (n-m) columnas restantes de A se puede construir otra matriz que se denominará matriz no básica y la denotaremos por W. Entonces puede escribirse la matriz A de la siguiente manera: A = (B, W).
*Las variables que forman parte de la matriz B se llaman variables básicas (XB) y las que forman parte de la matriz W se llaman variables no básica.( XW ), entonces el vector X está conformado por el conjunto de variables básicas y no básicas, es decir, X = (XB, XW).
*Entonces el sistema de restricciones del problema de [[Programación Lineal]] AX=b puede escribirse de la forma siguiente: AX=BXB + WXW = b. Si asumimos que las variables no básicas tomarán valor cero, la expresión anterior quedaría BXB =b. La expresión XB = B-1 b que se obtiene a partir de la anterior, permitiría calcular la solución básica factible inicial.

== Tabla para la realización del Método Simplex ==

El método simplex se desarrolla en la tabla simplex. Cada iteración requiere de una tabla. Su formato general es el siguiente:

BASE Cj C1 C2 … Cj … Cn
CB Variables XB P1 P1 … P1 … P1
CB1 XB1 XB1 P11 P12 … P1j … P1n
CB2 XB2 XB2 P21 P22 … P2j … P2n
.
.

CBm XBm XBm Pm1 Pm2 … Pm3 … Pmn
Zj -Cj Z Z1-C1 Z2-C2 … Zj-Cj … Zn-Cn

En la primera columna se escribirán los coeficientes de la función objetivo correspondiente a las variables básicas, escribiendo en la segunda columna dichas variables. La tercera columna indica los valores que toman las variables básicas en la solución que se está representando mediante la tabla simplex. El resto de la columnas representan los vectores Pj correspondientes a cada uno de los vectores aj de la matriz A (Pj es el vector coordenado de cada vector aj respecto a la base considerada). En la última fila de la tabla aparecen los valores Zj -Cj correspondiente a cada vector aj. Los coeficientes Zj se determinan utilizando la siguiente expresión: Zj =CBPj

== Procedimiento computacional del Método Simplex ==

El procedimiento iterativo en que se basa el método simplex puede resumirse en los siguientes pasos:

*Paso1: Convertir las inecuaciones en ecuaciones con la utilización de las variables de holgura.
*Paso 2: Determinar la solución básica factible inicial XB*, los valores Z*, Pj y Zj - Cj y construir la tabla simplex que resuma toda la información sobre esta solución inicial. La solución básica inicial debe tener la característica de que la matriz básica debe ser unitaria. Esto facilita el cálculo de la matriz inversa.
*Paso 3: Examinar en la tabla simplex los valores de los coeficientes Zj – Cj.

Pueden presentarse las siguientes situaciones: Caso Máximo y Caso Mínimo.

== Caso Máximo ==

*Todos los Zj – Cj ≥ 0. En este caso se ha alcanzado la solución óptima. (criterio de optimalidad)
*Uno o más Zj – Cj < 0.En este caso debe calcularse una nueva solución básica determinando el vector ak que entra en la base mediante la siguiente expresión:

ZK –CK = MIN (Zj – Cj) para todos los aj con Zj – Cj < 0 (1)

Si para uno o más vectores se obtienen ese valor mínimo puede escogerse cualquiera como vector entrante. Una vez escogido el vector ak pueden presentarse dos casos:
*Caso 1: Los valores Pik≤0 para cada i. Esto indica la existencia de una solución no acotada.
*Caso 2: Se tiene Pik > 0 para al menos una i. En este caso puede hallarse una nueva solución básica en la cual el valor de Z mejore o sea el óptimo.

== Caso Mínimo ==

*Todos los Zj – Cj ≤ 0. En este caso se ha alcanzado la solución óptima. (Criterio de optimalidad)
*Uno o más Zj – Cj > 0.En este caso debe calcularse una nueva solución básica determinando el vector ak que entra en la base mediante la siguiente expresión (1).

Paso 4:Si se tiene que Pik > 0 para al menos una i, se determina el vector que sale mediante la expresión:

Θ = XBr / Prk = MIN {X*Bi/ Pik, Pik > 0}

Debe extraerse de la base el vector ar siendo reemplazado por el vector ak. Si para 2 o más vectores se obtienen el mismo valor de Θ puede escogerse cualquiera como vector saliente.

Paso 5: Se calculan los nuevos valores XB, Z, Pj y Zj- Cj insertando dichos valores en la nueva tabla simplex. Una vez concluido este paso, se retorna al paso 3 repitiendo el procedimiento hasta que se alcance la solución óptima.

== Fuente ==

*Felipe Pilar y otros. Programación Matemática I. Pag. 40-68.
*.Portela Silva José M. Vladimir Kuzmich. Modelo Económico Matemático I, pág. 1-19.
*Gallagher,Charles A. Watson, Hugh J. Métodos Cuantitativos para la toma de decisiones. Pág. 156-166.
*Anderson David R., Dennis J. Sweeney, Thomas A. Willians. Introducción a los modelos cuantitativos para Administración. Pág.29.

[[Category:Ciencias_Económicas]]

@@ Línea 4: / Línea 4: @@
 |tamaño=
 |concepto=Uno de los Métodos de Solución de la [[Programación Lineal]].
-}} '''MétodoSimplex''': se basa en un procedimiento algebraico y la explicación geométrica del mismo se puede interpretar a través del método gráfico.
+}} '''MétodoSimplex.''' se basa en un procedimiento algebraico y la explicación geométrica del mismo se puede interpretar a través del método gráfico.
 == Conceptos Básicos del Método Simplex  ==
@@ Línea 14: / Línea 13: @@
 *Las variables que forman parte de la matriz B se llaman variables básicas  (XB) y las que forman parte de la matriz W se llaman variables no básica.( XW ), entonces el vector X está conformado por el conjunto de variables básicas y no básicas, es decir, X = (XB, XW).
 *Entonces el sistema de restricciones del problema de [[Programación Lineal]] AX=b puede escribirse de la forma siguiente: AX=BXB + WXW = b. Si asumimos que las variables no básicas tomarán valor cero, la expresión anterior quedaría BXB =b. La expresión XB = B-1 b que se obtiene a partir de la anterior, permitiría calcular  la solución básica factible inicial.
 == Para realizar la Tabla del Método Simplex ==
@@ Línea 31: / Línea 29: @@
 Pueden presentarse las siguientes situaciones: Caso Máximo y Caso Mínimo.
 == Caso Máximo ==
@@ Línea 44: / Línea 40: @@
 *Caso 1: Los valores Pik≤0 para cada i. Esto indica la existencia de una solución no acotada.
 *Caso 2: Se tiene Pik > 0 para al menos una i. En este caso puede hallarse una nueva solución básica en la cual el valor de Z mejore o sea el óptimo.
 == Caso Mínimo ==
@@ Línea 58: / Línea 53: @@
 Paso 5: Se calculan los nuevos valores XB, Z, Pj y Zj- Cj insertando dichos valores en la nueva tabla simplex. Una vez concluido este paso, se retorna al paso 3 repitiendo el procedimiento hasta que se alcance la solución óptima.
 == Fuente  ==

@@ Línea 16: / Línea 16: @@
-== Tabla para la realización del Método Simplex ==
+== Para realizar la Tabla del Método Simplex ==
 En la primera columna se escribirán los coeficientes de la función objetivo correspondiente a las variables básicas, escribiendo en la segunda columna dichas variables. La tercera columna indica los valores que toman las variables básicas en la solución que se está representando mediante la tabla simplex. El resto de la columnas representan los vectores Pj correspondientes a cada uno de los vectores aj de la matriz A (Pj es el vector coordenado de cada vector aj respecto a la base considerada). En la última fila de la tabla aparecen los valores Zj -Cj correspondiente a cada vector aj. Los coeficientes Zj se determinan utilizando la siguiente expresión: Zj =CBPj
 == Procedimiento computacional del Método Simplex ==