METODO SIMPLEX Y METODO
SIMPLEX DUAL
3 DE NOVIEMBRE DE 2022
INVESTIGACION DE OPERACIONES.
INSTITUTO TECNOLOGICO DE SAN LUIS POTOSI.
Método
Simplex:
El Método Simplex es un método analítico de solución de problemas de programación
lineal, capaz de resolver modelos más complejos que los resueltos mediante el método
gráfico, sin restricción en el número de variables y con una mayor capacidad de análisis de
sensibilidad.
El Método Simplex es un método analítico de solución de problemas de programación
lineal, capaz de resolver modelos más complejos que los resueltos mediante el método
gráfico, sin restricción en el número de variables y con una mayor capacidad de análisis de
sensibilidad.
Los pasos por seguir para llevar el método acabo son:
LUIS FERNANDO PANTOJA RODRIGUEZ. 20181092
1- Definir el problema en la forma estándar y generar nuestra
matriz.
Donde x1, x2 … xn son las variables del problema.
Antes de llevar nuestro modelo a la forma estándar debemos verificar que todas las
restricciones tienen el lado derecho no negativo. Es decir:
b1, b2 … bm ≥ 0
2- Determinar la solución básica inicial.
Como habíamos mencionado, el método simplex parte de un vértice de la región
factible, es decir, un punto extremo. Con cada iteración avanzaremos de vértice en
vértice hasta llegar a la solución óptima.
En nuestro caso, en la matriz elaborada podemos ver la solución básica inicial que
sería S1=35, S2=18 y S3=26 (cada variable del vector solución se iguala al valor que
se encuentra en la columna R. Estas variables se denominan variables básicas. El
valor de Z inicial también se muestra en la columna R que es .
LUIS FERNANDO PANTOJA RODRIGUEZ. 20181092
Las variables que no se encuentran en la base se denominan variables no básicas y
en este caso serían X1 y X2. Ambas tienen un valor de 0. ¿Con esta solución
tenemos el mejor valor de Z? Para saberlo debemos continuar al siguiente paso:
3- Seleccionar la variable de entrada utilizando la condició n de
optimalidad. Si no se puede seleccionar una variable de
entrada, quiere decir que estamos en la condición óptima y
finalizan las iteraciones. De otro modo se continúa con el
siguiente paso.
Con nuestra matriz finalizada e identificada nuestra solución básica inicial
revisaremos la condición de optimalidad.
Condición de Optimalidad:
La condición de optimalidad consiste en verificar si la solución actual que tenemos en
nuestra matriz es la óptima o si se puede mejorar. Se verifica de la siguiente manera:
En un problema de maximización si todos los coeficientes del vector de
costes reducidos son mayores o iguales que cero, quiere decir que estamos en
el punto óptimo y finaliza el problema.
En un problema de minimización si todos los coeficientes del vector de
costes reducidos son menores o iguales que cero, quiere decir que estamos en
el punto óptimo y finaliza el problema.
Siguiendo con el ejemplo, siendo el problema de maximización, podemos ver que en el
vector de costes reducidos existen valores negativos, lo que significa que no estamos en el
óptimo. Eso quiere decir que debemos iniciar las iteraciones seleccionando la variable de
entrada.
Variable de Entrada
La variable de entrada hace referencia a una de las variables no básicas que ingresará a la
base y formará parte de la solución del problema.
Los criterios para seleccionar la variable de entrada dependen si el problema es de
maximización o minimización:
Para problemas de maximización, la variable de entrada será la variable no
básica con el coeficiente más negativo en el vector de costes reducidos.
Para problemas de minimización, la variable de entrada será la variable no
básica con el coeficiente más positivo en el vector de costes reducidos.
La columna donde está ubicada la variable se denomina columna pivote.
LUIS FERNANDO PANTOJA RODRIGUEZ. 20181092
En el ejemplo nuestra variable de entrada sería X1 dado que tiene el valor más negativo en
el vector de costes reducidos, es decir “-3”:
4- Seleccionar la variable de salida utilizando la condició n
de factibilidad.
Variable de Salida
Para determinar la variable que sale de la base se debe dividir el valor correspondiente a
la columna R con su respectivo coeficiente en la columna de la variable de entrada
(siempre y cuando este coeficiente sea estrictamente positivo).
De los resultados obtenidos, el menor valor corresponde a la fila que contiene a la variable
de salida. Esta fila la llamaremos fila pivote
Veremos su aplicación con el ejemplo:
La variable de salida sería S2. El número que se encuentra al cruzar la fila pivote y la
columna pivote es el elemento pivote; en nuestro caso sería 3:
LUIS FERNANDO PANTOJA RODRIGUEZ. 20181092
5- Actualizar nuestra matriz realizando las operaciones de
Gauss-Jordan. (Volver al paso número 3).
Una vez determinado nuestro elemento pivote, realizaremos las operaciones de Gauss-
Jordan para formar nuestra matriz identidad. El nuevo valor de cada fila se calculará de la
siguiente manera:
Para la fila pivote: El nuevo valor se obtendrá dividiendo el valor actual
entre el elemento pivote.
Nuevo Valor Fila Pivote = Valor Actual Fila Pivote / Elemento Pivote
Para las otras filas: El nuevo valor se calcula restando del valor actual, la
multiplicación del elemento de la fila que se encuentra en la columna pivote
por el nuevo valor calculado en la fila pivote.
Nuevo Valor = Valor Actual – (Elemento Fila Columna Pivote*Nuevo Valor Fila Pivote).
Para entenderlo mejor, continuaremos resolviendo el ejemplo. Iniciaremos con la fila
pivote:
LUIS FERNANDO PANTOJA RODRIGUEZ. 20181092
En las otras filas realizaremos los cálculos de forma diferente. Iniciaremos con la fila
de S1:
LUIS FERNANDO PANTOJA RODRIGUEZ. 20181092
LUIS FERNANDO PANTOJA RODRIGUEZ. 20181092
Cómo puedes ver la posición donde se encontraba nuestro elemento pivote ahora
es 1 y los elementos que lo acompañan en la columna se convierten en 0. Es así
como empezamos a formar nuestra matriz identidad.
Volver al paso número 3
Con este último resultado, volveremos al paso 3 y repetiremos el proceso. Cómo existen
valores negativos en el vector de costes reducidos, podemos seguir optimizando.
El único valor negativo es -4, por lo que la variable que ingresará es X2.
Para elegir la variable que va a salir, dividimos cada valor de la columna R por su contraparte
de la columna X2 (este último valor debe ser positivo)
23/(19/3) = 69/19 = 3.632
El valor en la columna X2 es negativo por lo que no se toma en cuenta.
14/(16/3) = 21/8 = 2.625
El menor valor se encuentra en la fila de S3, por lo que es la variable que saldrá de la base.
El elemento pivote es 16/3.
Realizamos nuevamente las iteraciones obteniendo el siguiente resultado:
LUIS FERNANDO PANTOJA RODRIGUEZ. 20181092
En esta última matriz vemos que el vector de costes reducidos ya no tiene ningún valor
negativo, lo que quiere decir que nos encontramos en el valor óptimo. Obtendremos los
valores de las variables básicas y de Z de la siguiente forma:
Las variables que no se encuentran en la base tendrán valor de 0.
Solución: X1= 31/4, X2= 21/8, S1= 51/8, S2= 0, S3= 0, Z = 57/2
EJEMPLO:
EJERCICIO RESUELTO – MÉTODO SIMPLEX PARA MINIMIZA R
En este problema, resolveremos un caso de minimización con el método simplex, donde
no se utilizan variables artificiales.
Al no utilizarse variables artificiales no será necesario usar el método de las 2 fases o de la
M grande.
Minimizar 2x1 – x2
Sujeto a:
2x1 + 3x2 ≤ 10
x1 + x2 ≤ 6
x1, x2 ≥ 0
LUIS FERNANDO PANTOJA RODRIGUEZ. 20181092
El problema se adecuará al modelo estándar de programación lineal, agregando las
variables de holgura, exceso y/o artificiales en cada una de las restricciones:
Restricción 1: Tiene signo “≤” (menor igual) por lo que se agregará la
variable de holgura S1.
Restricción 2: Tiene signo “≤” (menor igual) por lo que se agregará la
variable de holgura S2.
A continuación, se muestra el problema en la forma estándar. Se colocará el coeficiente 0
(cero) donde corresponda para crear nuestra matriz:
SOLUCION:
Matriz inicial.
LUIS FERNANDO PANTOJA RODRIGUEZ. 20181092
Ingresa la variable X2 y sale de la base la variable S1. El elemento pivote es 3
La solución óptima es Z = -10/3
X1= 0, X2= 10/3, S1= 0, S2= 8/3
LUIS FERNANDO PANTOJA RODRIGUEZ. 20181092
METODO SIMPLEX DUAL:
Como sabemos, el método simplex es un algoritmo iterativo que iniciando en una solución básica
factible pero no óptima, genera soluciones básicas factibles cada vez mejores hasta encontrar la
solución óptima (sí esta existe). Nótese que la base de su lógica es mantener la factibilidad,
mientras busca la optimalidad. Pero surge la posibilidad de usar otro esquema igualmente iterativo,
que, como contraparte del simplex, comienza en una solución básica óptima, pero no factible y
mantiene la inmejorabilidad mientras busca la factibilidad. Con este procedimiento se llega
igualmente a la solución óptima.
Algoritmo Dual-Simplex para un modelo de maximizació n.
Primero se debe expresar el modelo en formato estándar, agregando las variables de holgura y de
exceso que se requieran.
Enseguida, en las ecuaciones que tengan variables de exceso (resultantes de restricciones de
tipo >), se debe multiplicar por (-1) en ambos lados, para hacer positivo el coeficiente de la variable
de exceso, y formar así un vector unitario que nos permita tomar esta variable de exceso como una
variable básica inicial. sin necesidad de agregar una variable artificial en esa restricción.
1. Al hacer lo anterior se logra que debajo de las variables básicas aparezca una matriz
identidad, que es la que el simplex siempre toma como base inicial.
2. Obtendremos que los términos del lado derecho de las ecuaciones multiplicadas por (-1)
quedan con signo negativo, lo cual hace que la solución inicial sea infactible.
3. Es importante destacar que este proceso es muy útil ya que en muchos modelos evita la
inclusión de variables artificiales en el momento de transformar un modelo a formato
estándar.
El algoritmo para resolver un modelo de maximización es el siguiente:
Paso 1: Hallar una solución básica inicial infactible e inmejorable
Escribir el tablero inicial tomando a las variables de holgura y de exceso como variables básicas
iniciales
Paso 2: Prueba de factibilidad
Si todas las variables básicas son no negativas, la actual solución es la óptima.
Si hay al menos una variable básica negativa, seleccionar como variable de salida,
(llamémosla (XB)s), a aquella con el valor más negativo. Los empates se pueden romper
arbitrariamente.
LUIS FERNANDO PANTOJA RODRIGUEZ. 20181092
Paso 3: Prueba de inmejorabilidad
Sí en el renglón de la variable básica de salida (XB)s todos los coeficientes de reemplazo con las
variables no básicas son no negativos, la solución del modelo es óptima ¡limitada. Se termina el
proceso.
Si en el renglón de la variable básica de salida (XB)s, hay al menos un coeficiente de intercambio
negativo, se efectúan los cocientes entre el efecto neto de cada variable no básicas y su
correspondiente coeficiente de intercambio negativo. Es decir, siendo (XB)s la variable de salida
se calculan todos los cocientes.
Se toma como variable de entrada (Llamémosla Xe) a aquella que corresponda al mínimo de los
cocientes del anterior conjunto
Si la variable de entrada es Xe el elemento pivote será el elemento (Se)s
El empate se puede romper arbitrariamente.
Aplicar la operación de pivoteo para generar la nueva tabla, en la cual aparezca Xe como variable
básica en lugar de la variable de salida (XB)s
Repetir el algoritmo a partir del paso 2.
EJEMPLO:
Sea el siguiente modelo:
LUIS FERNANDO PANTOJA RODRIGUEZ. 20181092
Pasamos a forma estándar:
Multipliquemos por (-1) en ambos lados de las ecuaciones, para formar los vectores unitarios,
requeridos para contar con una base inicial unitaria.
Paso 1.
Tomando las variables básicas iniciales hacemos lo siguiente:
LUIS FERNANDO PANTOJA RODRIGUEZ. 20181092
Paso 2
Sale E2 = (XB)2 o sea s = 2
Paso 3
Calculando los cocientes para todo (Sj)2 < 0 obtenemos:
Es decir que X3 es la variable de entrada (entonces e = 3) y el elemento pivote es el (Se)s = (S3)2 = -
9
Efectuando el pivoteo obtenemos la tabla siguiente:
LUIS FERNANDO PANTOJA RODRIGUEZ. 20181092
Repitiendo el algoritmo desde el paso 1, obtenemos:
Sale E1 = (XB)1 y entra X2 por lo cual obtenemos la siguiente tabla
Como se observa, ahora estamos en el óptimo.
En definitiva:
X2* = 11/7
X3* = 13/7
Z* = – 61/7
LUIS FERNANDO PANTOJA RODRIGUEZ. 20181092
La aplicación del método simplex dual es especialmente útil en el análisis de sensibilidad. Se usa
cuando después de haber obtenido la solución óptima, se desea agregar una nueva restricción al
modelo si la nueva restricción no se cumple.
BIBLIOGRAFIAS:
[Link]
programacion-lineal-con-el-metodo-simplex-dual/
[Link]
[Link]
LUIS FERNANDO PANTOJA RODRIGUEZ. 20181092
