Calculadora online del método símplex dual con pasos

F =

x1

 +

x2

 +

x3

 +

x4

x1

 +

x2

 +

x3

 +

x4

x1

 +

x2

 +

x3

 +

x4

x1

 +

x2

 +

x3

 +

x4

x1

 +

x2

 +

x3

 +

x4

Comentarios de la solución
Sin descripción (solo respuesta)

a

b

c

d

x

y

z

AC

i

ab
x2
xn

Randomize

Formato numérico
313131313135151515151552188552198585858586
Redondea a
Dígitos después del punto decimal
10
=Resolver

  Acerca de la calculadora del método símplex dual

Resuelva problemas de programación lineal usando el método símplex dual en línea con el tableau símplex y solución detallada paso a paso. con descripción completa y detallada paso a paso de las soluciones, que resuelve problemas de programación lineal de hasta 20×20 con coeficientes de tipo: números decimales y fracciones.

Para iniciar el cálculo, primero hay que introducir las dimensiones del problema en los campos de entrada en la parte superior de la pantalla y elegir la operación deseada en el menú lateral.

Un poco más abajo encontrará una ventana de entrada donde se deben ingresar los coeficientes, las restricciones y los valores del lado derecho usando el teclado. Aquí también se encuentra el panel de control de entrada, que simplifica el trabajo con los problemas de PL y contiene los siguientes elementos de control:

  • El primer elemento permite expandir la ventana de entrada. Esto puede ser especialmente útil cuando la tabla no cabe completamente en la pantalla. Si la tabla aún no es totalmente visible después de expandir la ventana, puede cambiar la escala con los botones + / -;
  • El segundo elemento copia los datos de entrada del problema actual al búfer de memoria. Esto puede ser útil cuando se resuelve con frecuencia el mismo problema de PL o se necesita transferir datos entre operaciones;
  • Y el último elemento pega los datos de entrada copiados anteriormente, lo que permite restaurar los datos del problema en pocos clics en lugar de volver a ingresarlos manualmente;

Y más abajo encontrará una barra de herramientas que permite personalizar la calculadora y facilitar su uso. Está dividida visualmente en tres partes, cada una de las cuales se encarga de la siguiente funcionalidad:

  • La primera parte permite seleccionar el formato numérico utilizado al mostrar el resultado de la solución. También puede desactivar los comentarios paso a paso si ya conoce el método y solo necesita verificar sus propios cálculos, u ocultar la solución paso a paso por completo si solo necesita la respuesta final;
  • La segunda parte contiene botones que permiten modificar las dimensiones de la tabla de entrada, borrar coeficientes individuales o toda la entrada, y el botón principal con el signo igual que lleva a la pantalla de solución. Todos estos botones tienen atajos de teclado. Pase el cursor sobre un botón para ver la tecla correspondiente en un tooltip. También puede usar las teclas de flecha para mover el cursor entre los campos de entrada;
  • Y la última parte permite elegir el número de dígitos después del punto decimal para redondear resultados no enteros. Una vista previa en tiempo real muestra cómo aparecerán los valores redondeados;

  ¿Qué es el método símplex dual?

El método símplex dual resuelve programas lineales explotando la relación dual con el símplex estándar. Es especialmente útil cuando el problema primal comienza siendo infactible pero dual-factible — situación que surge naturalmente al añadir nuevas restricciones a un PL ya resuelto o al minimizar un problema con todos los lados derechos negativos. A diferencia del símplex primal, que mantiene la factibilidad primal en todo momento, el símplex dual mantiene la factibilidad dual y conduce el tableau hacia la factibilidad primal.

  ¿Cómo resolver un problema de programación lineal con el método símplex dual?

Comience con un tableau dual-factible (todos los costos reducidos no negativos para un problema de minimización) pero no necesariamente primal-factible (algunas variables básicas pueden ser negativas). En cada iteración, aplique primero la regla de la variable saliente: seleccione la variable básica más negativa como saliente. Luego aplique la regla de la variable entrante: entre todas las columnas con coeficiente negativo en la fila saliente, elija aquella con la menor razón absoluta de costo reducido sobre ese coeficiente. Realice el pivote y repita hasta que todas las variables básicas sean no negativas, obteniendo la solución primal-factible óptima.

  Ejemplo de resolución de un problema de programación lineal con el método símplex dual

Transición al símplex dual
F(x) = 3x1+4x2 → max
2x1+x2600
225
5x1+4x21000
-2x2-150
0
Z(t) = 600t1+225t2+1000t3-150t4+0t5 → min
2t1+5t33
t1+4t3-2t44

Reglas de transición

1) Los coeficientes del lado derecho de las restricciones del problema directo se convierten en los coeficientes de la función objetivo del símplex dual;

2) Los coeficientes del lado izquierdo de las restricciones del símplex dual se forman transponiendo la matriz de coeficientes del lado izquierdo de las restricciones del problema directo;

3) Los coeficientes del lado derecho de las restricciones del símplex dual se forman a partir de los valores de la función objetivo del problema directo con las variables controladas correspondientes;

4) Si F → max , entonces Z → min
Si ≤ , entonces ≥
Si = , entonces ≥

5) Si F → min , entonces Z → max
Si ≥ , entonces ≤
Si = , entonces ≤

Descripción
F(x) = 600x1+225x2+1000x3-150x4+0x5 → min
F(x) = 600x1+225x2+1000x3-150x4+0x5+0x6+0x7+Mx8+Mx9 → min
2x1+5x33
2x1+5x3-x6+x8 = 3
x1+4x3-2x44
x1+4x3-2x4-x7+x9 = 4

La etapa preliminar comienza con la necesidad de eliminar los valores negativos en la parte derecha de las restricciones. Para ello, las restricciones correspondientes se multiplican por -1. Tras esta operación, el signo de la desigualdad se invierte.

A continuación, hay que eliminar las desigualdades, para lo cual introducimos variables de holgura en el lado izquierdo de las desigualdades. Si la desigualdad es de la forma ≤, la variable de holgura lleva signo +; si la desigualdad es de la forma ≥, la variable de holgura lleva signo -. Las variables de holgura se incluyen en la función objetivo del problema con coeficiente cero.

Ahora, en el sistema de restricciones, es necesario encontrar un número suficiente de variables básicas. Cada restricción debe tener una variable básica. Una variable básica es aquella que tiene coeficiente 1 y aparece en una sola restricción. Si en alguna restricción no hay variables básicas, las añadimos artificialmente; las variables artificiales entran en la función objetivo con coeficiente -M si la función objetivo tiende a max, y M si tiende a min.

Descripción
2
Iteración 1
BCbPx1x2x3x4x5x6x7x8x9Q
6002251000-150000MM
x8M320500-101035
x9M4104-200-1011
min7M3M-600-2259M-1000-2M+1500-M-M00

Elementos de la columna base (B)

Trasladamos a la tabla los elementos básicos identificados en la etapa preliminar:

B1 = x8;

B2 = x9;

Elementos de la columna Cb

Cada celda de esta columna es igual al coeficiente que corresponde a la variable básica de la fila correspondiente.

Cb1 = M;

Cb2 = M;

Valores de las variables y columna P

En esta etapa no se realizan cálculos; simplemente se transfieren los valores de la etapa preliminar a las celdas de la tabla correspondientes:

P1 = 3;

P2 = 4;

x1,1 = 2;

x1,2 = 0;

x1,3 = 5;

x1,4 = 0;

x1,5 = 0;

x1,6 = -1;

x1,7 = 0;

x1,8 = 1;

x1,9 = 0;

x2,1 = 1;

x2,2 = 0;

x2,3 = 4;

x2,4 = -2;

x2,5 = 0;

x2,6 = 0;

x2,7 = -1;

x2,8 = 0;

x2,9 = 1;

Valor de la función objetivo

Calculamos el valor de la función objetivo multiplicando elemento a elemento la columna Cb por la columna P y sumando los productos.

MinP = (Cb1 * P1) + (Cb2 * P2) = (M * 3) + (M * 4) = 7M;

Estimaciones de las variables controladas

Calculamos las estimaciones para cada variable controlada multiplicando elemento a elemento el valor de la columna de la variable por el valor de la columna Cb, sumando los productos y restando el coeficiente de la función objetivo para esa variable.

Minx1 = ((Cb1 * x1,1) + (Cb2 * x2,1)) - kx1 = ((M * 2) + (M * 1)) - 600 = 3M-600;

Minx2 = ((Cb1 * x1,2) + (Cb2 * x2,2)) - kx2 = ((M * 0) + (M * 0)) - 225 = -225;

Minx3 = ((Cb1 * x1,3) + (Cb2 * x2,3)) - kx3 = ((M * 5) + (M * 4)) - 1000 = 9M-1000;

Minx4 = ((Cb1 * x1,4) + (Cb2 * x2,4)) - kx4 = ((M * 0) + (M * -2)) - -150 = -2M+150;

Minx5 = ((Cb1 * x1,5) + (Cb2 * x2,5)) - kx5 = ((M * 0) + (M * 0)) - 0 = 0;

Minx6 = ((Cb1 * x1,6) + (Cb2 * x2,6)) - kx6 = ((M * -1) + (M * 0)) - 0 = -M;

Minx7 = ((Cb1 * x1,7) + (Cb2 * x2,7)) - kx7 = ((M * 0) + (M * -1)) - 0 = -M;

Minx8 = ((Cb1 * x1,8) + (Cb2 * x2,8)) - kx8 = ((M * 1) + (M * 0)) - M = 0;

Minx9 = ((Cb1 * x1,9) + (Cb2 * x2,9)) - kx9 = ((M * 0) + (M * 1)) - M = 0;

Elementos de la columna Q

Como hay valores positivos entre las estimaciones de las variables controladas, la tabla actual aún no tiene solución óptima. Por lo tanto, introducimos en la base la variable con la estimación positiva más alta.

El número de variables en la base es siempre constante, por lo que es necesario elegir qué variable sacar de la base, para lo cual calculamos Q.

Los elementos de la columna Q se calculan dividiendo los valores de la columna P entre el valor de la columna correspondiente a la variable que entra a la base:

Q1 = P1x1,3 = 35 = 35;

Q2 = P2x2,3 = 44 = 1;

Sacamos de la base la variable con el valor positivo más pequeño de Q.

En la intersección de la fila que corresponde a la variable que sale de la base y la columna que corresponde a la variable que entra a la base se encuentra el elemento resolutivo.

Este elemento nos permitirá calcular los elementos de la tabla de la siguiente iteración.

Descripción
3
Iteración 2
BCbPx1x2x3x4x5x6x7x8x9Q
6002251000-150000MM
x3100035250100-150150
x9M135-3500-2045-1-4512
min135M+600-35M-200-2250-2M+150045M-200-M-145M+2000

Elementos de la columna base (B)

Con los resultados de los cálculos de la iteración anterior, extraemos de la base la variable x8 y en su lugar introducimos x3. El resto de las celdas permanece sin cambios.

Elementos de la columna Cb

Cada celda de esta columna es igual al coeficiente que corresponde a la variable básica de la fila correspondiente.

Cb1 = 1000;

Cb2 = M;

Valores de las variables y columna P

(Los datos de la iteración anterior se toman como datos iniciales)

Llenamos con ceros todas las celdas correspondientes a la variable que acaba de entrar a la base:

(El elemento resolutivo permanece sin cambios)

x2,3 = 0;

Trasladamos la fila con el elemento resolutivo de la tabla anterior a la tabla actual, dividiendo elemento a elemento sus valores entre el elemento resolutivo:

x1,1 = x1,1x1,3 = 25 = 25;

x1,2 = x1,2x1,3 = 05 = 0;

x1,3 = x1,3x1,3 = 55 = 1;

x1,4 = x1,4x1,3 = 05 = 0;

x1,5 = x1,5x1,3 = 05 = 0;

x1,6 = x1,6x1,3 = -15 = -15;

x1,7 = x1,7x1,3 = 05 = 0;

x1,8 = x1,8x1,3 = 15 = 15;

x1,9 = x1,9x1,3 = 05 = 0;

P1 = P1x1,3 = 35 = 35;

Las celdas vacías restantes, excepto la fila de estimaciones y la columna Q, se calculan usando el método del rectángulo respecto al elemento resolutivo:

x2,1 = (x2,1 * x1,3) - (x2,3 * x1,1)x1,3 = (1 * 5) - (4 * 2)5 = -35;

x2,2 = (x2,2 * x1,3) - (x2,3 * x1,2)x1,3 = (0 * 5) - (4 * 0)5 = 0;

x2,4 = (x2,4 * x1,3) - (x2,3 * x1,4)x1,3 = (-2 * 5) - (4 * 0)5 = -2;

x2,5 = (x2,5 * x1,3) - (x2,3 * x1,5)x1,3 = (0 * 5) - (4 * 0)5 = 0;

x2,6 = (x2,6 * x1,3) - (x2,3 * x1,6)x1,3 = (0 * 5) - (4 * -1)5 = 45;

x2,7 = (x2,7 * x1,3) - (x2,3 * x1,7)x1,3 = (-1 * 5) - (4 * 0)5 = -1;

x2,8 = (x2,8 * x1,3) - (x2,3 * x1,8)x1,3 = (0 * 5) - (4 * 1)5 = -45;

x2,9 = (x2,9 * x1,3) - (x2,3 * x1,9)x1,3 = (1 * 5) - (4 * 0)5 = 1;

P2 = (P2 * x1,3) - (x2,3 * P1)x1,3 = (4 * 5) - (4 * 3)5 = 135;

Valor de la función objetivo

Calculamos el valor de la función objetivo multiplicando elemento a elemento la columna Cb por la columna P y sumando los productos.

MinP = (Cb1 * P1) + (Cb2 * P2) = (1000 * 35) + (M * 135) = 135M+600;

Estimaciones de las variables controladas

Calculamos las estimaciones para cada variable controlada multiplicando elemento a elemento el valor de la columna de la variable por el valor de la columna Cb, sumando los productos y restando el coeficiente de la función objetivo para esa variable.

Minx1 = ((Cb1 * x1,1) + (Cb2 * x2,1)) - kx1 = ((1000 * 25) + (M * -35)) - 600 = -35M-200;

Minx2 = ((Cb1 * x1,2) + (Cb2 * x2,2)) - kx2 = ((1000 * 0) + (M * 0)) - 225 = -225;

Minx3 = ((Cb1 * x1,3) + (Cb2 * x2,3)) - kx3 = ((1000 * 1) + (M * 0)) - 1000 = 0;

Minx4 = ((Cb1 * x1,4) + (Cb2 * x2,4)) - kx4 = ((1000 * 0) + (M * -2)) - -150 = -2M+150;

Minx5 = ((Cb1 * x1,5) + (Cb2 * x2,5)) - kx5 = ((1000 * 0) + (M * 0)) - 0 = 0;

Minx6 = ((Cb1 * x1,6) + (Cb2 * x2,6)) - kx6 = ((1000 * -15) + (M * 45)) - 0 = 45M-200;

Minx7 = ((Cb1 * x1,7) + (Cb2 * x2,7)) - kx7 = ((1000 * 0) + (M * -1)) - 0 = -M;

Minx8 = ((Cb1 * x1,8) + (Cb2 * x2,8)) - kx8 = ((1000 * 15) + (M * -45)) - M = -145M+200;

Minx9 = ((Cb1 * x1,9) + (Cb2 * x2,9)) - kx9 = ((1000 * 0) + (M * 1)) - M = 0;

Elementos de la columna Q

Como hay valores positivos entre las estimaciones de las variables controladas, la tabla actual aún no tiene solución óptima. Por lo tanto, introducimos en la base la variable con la estimación positiva más alta.

El número de variables en la base es siempre constante, por lo que es necesario elegir qué variable sacar de la base, para lo cual calculamos Q.

Los elementos de la columna Q se calculan dividiendo los valores de la columna P entre el valor de la columna correspondiente a la variable que entra a la base:

Q1 = P1x1,6 = 35-15 = ;

Q2 = P2x2,6 = 13545 = 2;

Sacamos de la base la variable con el valor positivo más pequeño de Q.

En la intersección de la fila que corresponde a la variable que sale de la base y la columna que corresponde a la variable que entra a la base se encuentra el elemento resolutivo.

Este elemento nos permitirá calcular los elementos de la tabla de la siguiente iteración.

Descripción
4
Iteración 3
BCbPx1x2x3x4x5x6x7x8x9Q
6002251000-150000MM
x3100011401-1200-14014
x602-3400-21201-114-1114
min1000-350-2250-35000-250-M-M+250

Elementos de la columna base (B)

Con los resultados de los cálculos de la iteración anterior, extraemos de la base la variable x9 y en su lugar introducimos x6. El resto de las celdas permanece sin cambios.

Elementos de la columna Cb

Cada celda de esta columna es igual al coeficiente que corresponde a la variable básica de la fila correspondiente.

Cb1 = 1000;

Cb2 = 0;

Valores de las variables y columna P

(Los datos de la iteración anterior se toman como datos iniciales)

Llenamos con ceros todas las celdas correspondientes a la variable que acaba de entrar a la base:

(El elemento resolutivo permanece sin cambios)

x1,6 = 0;

Trasladamos la fila con el elemento resolutivo de la tabla anterior a la tabla actual, dividiendo elemento a elemento sus valores entre el elemento resolutivo:

x2,1 = x2,1x2,6 = -3545 = -34;

x2,2 = x2,2x2,6 = 045 = 0;

x2,3 = x2,3x2,6 = 045 = 0;

x2,4 = x2,4x2,6 = -245 = -212;

x2,5 = x2,5x2,6 = 045 = 0;

x2,6 = x2,6x2,6 = 4545 = 1;

x2,7 = x2,7x2,6 = -145 = -114;

x2,8 = x2,8x2,6 = -4545 = -1;

x2,9 = x2,9x2,6 = 145 = 114;

P2 = P2x2,6 = 13545 = 2;

Las celdas vacías restantes, excepto la fila de estimaciones y la columna Q, se calculan usando el método del rectángulo respecto al elemento resolutivo:

x1,1 = (x1,1 * x2,6) - (x1,6 * x2,1)x2,6 = (25 * 45) - (-15 * -35)45 = 14;

x1,2 = (x1,2 * x2,6) - (x1,6 * x2,2)x2,6 = (0 * 45) - (-15 * 0)45 = 0;

x1,3 = (x1,3 * x2,6) - (x1,6 * x2,3)x2,6 = (1 * 45) - (-15 * 0)45 = 1;

x1,4 = (x1,4 * x2,6) - (x1,6 * x2,4)x2,6 = (0 * 45) - (-15 * -2)45 = -12;

x1,5 = (x1,5 * x2,6) - (x1,6 * x2,5)x2,6 = (0 * 45) - (-15 * 0)45 = 0;

x1,7 = (x1,7 * x2,6) - (x1,6 * x2,7)x2,6 = (0 * 45) - (-15 * -1)45 = -14;

x1,8 = (x1,8 * x2,6) - (x1,6 * x2,8)x2,6 = (15 * 45) - (-15 * -45)45 = 0;

x1,9 = (x1,9 * x2,6) - (x1,6 * x2,9)x2,6 = (0 * 45) - (-15 * 1)45 = 14;

P1 = (P1 * x2,6) - (x1,6 * P2)x2,6 = (35 * 45) - (-15 * 135)45 = 1;

Valor de la función objetivo

Calculamos el valor de la función objetivo multiplicando elemento a elemento la columna Cb por la columna P y sumando los productos.

MinP = (Cb1 * P1) + (Cb2 * P2) = (1000 * 1) + (0 * 2) = 1000;

Estimaciones de las variables controladas

Calculamos las estimaciones para cada variable controlada multiplicando elemento a elemento el valor de la columna de la variable por el valor de la columna Cb, sumando los productos y restando el coeficiente de la función objetivo para esa variable.

Minx1 = ((Cb1 * x1,1) + (Cb2 * x2,1)) - kx1 = ((1000 * 14) + (0 * -34)) - 600 = -350;

Minx2 = ((Cb1 * x1,2) + (Cb2 * x2,2)) - kx2 = ((1000 * 0) + (0 * 0)) - 225 = -225;

Minx3 = ((Cb1 * x1,3) + (Cb2 * x2,3)) - kx3 = ((1000 * 1) + (0 * 0)) - 1000 = 0;

Minx4 = ((Cb1 * x1,4) + (Cb2 * x2,4)) - kx4 = ((1000 * -12) + (0 * -212)) - -150 = -350;

Minx5 = ((Cb1 * x1,5) + (Cb2 * x2,5)) - kx5 = ((1000 * 0) + (0 * 0)) - 0 = 0;

Minx6 = ((Cb1 * x1,6) + (Cb2 * x2,6)) - kx6 = ((1000 * 0) + (0 * 1)) - 0 = 0;

Minx7 = ((Cb1 * x1,7) + (Cb2 * x2,7)) - kx7 = ((1000 * -14) + (0 * -114)) - 0 = -250;

Minx8 = ((Cb1 * x1,8) + (Cb2 * x2,8)) - kx8 = ((1000 * 0) + (0 * -1)) - M = -M;

Minx9 = ((Cb1 * x1,9) + (Cb2 * x2,9)) - kx9 = ((1000 * 14) + (0 * 114)) - M = -M+250;

Respuesta

Como no hay valores positivos entre las estimaciones de las variables controladas, la tabla actual tiene una solución óptima.

El valor de la función objetivo:

F* = 1000;

Las variables presentes en la base son iguales a las celdas correspondientes de la columna P; todas las demás variables son iguales a cero:

x1 = 0;

x2 = 0;

x3 = 1;

x4 = 0;

x5 = 0;

Descripción
Answer
F → max
F* = 1000
X* = (00100)
Variables2Restricciones5ObjetivomaxF*1000

  Preguntas frecuentes

¿Qué es el método símplex dual?

El método símplex dual mantiene satisfecha la condición de optimalidad mientras restaura la factibilidad, lo contrario del símplex primal, que mantiene la factibilidad y trabaja hacia la optimalidad. Es útil cuando una base inicial es óptima pero no factible.

¿Cuándo debería usar el símplex dual en lugar del símplex primal?

Es más eficiente cuando ya dispones de una base dual-factible (óptima pero no factible), por ejemplo tras añadir una restricción a un problema ya resuelto o durante el análisis de sensibilidad, porque puede reoptimizar sin reiniciar desde cero.

¿Cómo se relaciona el símplex dual con el problema primal?

Todo programa lineal tiene un dual. El símplex dual opera sobre el tablero primal pero pivota según la factibilidad dual. En el óptimo, los valores objetivo del primal y del dual coinciden (dualidad fuerte).

¿El símplex dual da el mismo óptimo que el símplex primal?

Sí. Para un problema con un óptimo finito, ambos métodos alcanzan el mismo valor objetivo óptimo y una solución óptima; solo difieren en el camino recorrido a través de los tableros.

  Fuentes