Tutorial: El método simplex: Solucionar problemas general de programación lineal
Versión juego adaptivo
(Se puede encontrar este tema en la Sección 6.4 en el libro Matemáticas finitas y cálculo aplicado) No me gusta este tutorial. ¡Llévame de vuelta a la versión antigua!Recursos
 Herramienta pivotar Gauss-Jordan |
Herramienta pivotar Gauss-Jordan Excel |
Herramienta método simplex |
Problemas de maximización no estándar; variables de holgura y excendente
%%Note Necesita saber cómo hacer problemas de maximización estándar para poder seguir este tutorial, así que vuelva a %%lpstd si es necesario.
En el %%lpstd aprendimos que un problema de maximización estándar es un problema de PL donde:
- Necesitamos hallar el valor máximo (no mínimo) de la función objetiva.
- Todos las variables $x_1, x_2, ..., x_n$ son restringidas a ser no negativas.
- Cada restricción adicional tiene la forma $bx_1 + bx_2 + ... + bx_n \bold{\color{#b50b0b}{\leq}} c$ (y no $\geq c$), y $c$ no puede ser negativa.
Problema maximización general
Un problema de maximización general es un problema de PL que satisface (1) y (2) anteriores, pero donde las restricciones adicionales pueden tener la forma
Un problema de maximización general es un problema de PL que satisface (1) y (2) anteriores, pero donde las restricciones adicionales pueden tener la forma
$bx_1 + bx_2 + ... + bx_n \bold{\color{#b50b0b}{{}\leq{}} c$
con $c$ no negativo en problemas estándares de mazimización, o también $bx_1 + bx_2 + ... + bx_n \bold{\color{#b50b0b}{{}\geq{}} c$
con $c$ positivo. (Si $c = 0$ multiplicamos por $-1$ para convertirlo en una desigualdad ${}\leq 0$ como lo haríamos con los problemas estándar de mazimización).
%%Examples
1. #[The following is a general maximization problem:][El siguiente es un problema de maximización general:]#
2. El siguiente problema de PL se puede reescribirse como un problema de maximización estándar:
1. #[The following is a general maximization problem:][El siguiente es un problema de maximización general:]#
#[Maximize][Maximizar]# \t $p = 2x - 3y + z$
\\ #[subject to][sujeto a]# \t $3y + z \leq 0$
\\ \t $2x + y - z \geq 10$
\\ \t $x \geq 0, y \geq 0, z \geq 0$.
2. El siguiente problema de PL se puede reescribirse como un problema de maximización estándar:
#[Maximize][Maximizar]# \t $p = 3x-3y-8z$
\\ #[subject to][sujeto a]# \t $x-z = 5$
\\ \t $3y+5z \geq 3$
\\ \t $9x-2z \geq 0$
\\ \t $x \geq 0, y \geq 0, z \geq 0$.
Mira la primera restricción: decir que $x-z$ es igual a 5 es lo mismo que decir que $x-z$ es simultáneamente $\geq 5$ y $\leq 5$. Por lo tanto, podemos reemplazar la restricción de igualdad por dos restricciones de desigualdad:
#[Maximize][Maximizar]# \t $p = 3x-3y-8z$
\\ #[subject to][sujeto a]# \t $x-z \geq 5$
\\ \t $x-z \leq 5$
\\ \t $3y+5z \geq 3$
\\ \t $9x-2z \geq 0$
\\ \t $x \geq 0, y \geq 0, z \geq 0$.
Finalmente, convertimos las restricciones de ${}\geq 0$ en restricciones de ${}\leq 0$ al multiplicar ambos lados por $-1$, lo que nos deja con un problema general de maximización:
#[Maximize][Maximizar]# \t $p = 3x-3y-8z$
\\ #[subject to][sujeto a]# \t $x-z \geq 5$
\\ \t $x-z \leq 5$
\\ \t $3y+5z \geq 3$
\\ \t $-9x+2z \leq 0$
\\ \t $x \geq 0, y \geq 0, z \geq 0$.
Convertir a forma de ecuación
Si, por ejemplo, tenemos la restricción $3x-y+z \geq 8$, entonces para obtener una ecuación, necesitamos restar una cualidad no negativa, llamada excedente del lado izquierdo:
Si, por ejemplo, tenemos la restricción $3x-y+z \geq 8$, entonces para obtener una ecuación, necesitamos restar una cualidad no negativa, llamada excedente del lado izquierdo:
$3x-y+z - s = 8 \qquad$ \t #[s is a nonnegative quantity called a surplus variable.][s es una cantidad no negativa llamada una variable de excendente.]#
%%Example A
#[Consider the following general LP maximization problem.][Vamos a considerar el siguente problema PL de maximización:]#
#[Consider the following general LP maximization problem.][Vamos a considerar el siguente problema PL de maximización:]#
#[Maximize][Maximizar]# \t $p = 2x + 3y + z$
\\ #[subject to][sujeto a]# \t $x + y + z \leq 40$
\\ \t $-y + z \geq 10$
\\ \t $2x + y - z \geq 10$
\\ \t $x \geq 0, y \geq 0, z \geq 0$.
Luego, convertimos todas las restricciones excepto las de la última línea en ecuaciones utilizando variables de holgura y excendente (una para cada desigualdad):
$x + y + z + s = 40$ \t $s$ es ina variable de holgura.
\\ $-y + z - t = 10$ \t $t$ es ina variable de excendente.
\\ $2x + y - z - u = 10$ \t $u$ es ina variable de excendente.
\\ $-2x - 3y - z + p = 0$ \t Función objetiva
Uno para ti
%%A Los valores actuales de $t$ y $u$ son ambos negativos, lo que indica que la solución básica actual con $x = y = z = 0$ no es factible:
$0 + 0 + 0 \leq 40 \qquad$ \t ✔
\\ $-0 + 0 \geq 10$ \t ✘
\\ $2(0) + 0 - 0 \geq 10$ \t ✘
En el método simplex, ninguna de las variables de decisión puede ser negativa. Si una variable de holgura o excedente es negativa, eso indicaría que la desigualdad asociada no se satisface, como vemos arriba. Por lo tanto,
Fase 1: Deshacerse de las estrellas
Para motivar lo que haremos, hacemos la siguiente observación: como las reglas de "razón de prueba" para seleccionar un pivote en una columna dada garantizan que la variable de decisión entrante no sea negativa (y la saliente será cero) y así no se pueden crear nuevas estrellas, se sigue que si un pivote está en una fila marcada con estrella, ¡esa estrella desaparecerá para siempre! Por lo tanto, en la Fase 1, hacemos todo lo posible para encontrar pivotes que estén en las filas destacadas, independientemente de lo que esté sucediendo en la fila. fila inferior, usando la siguiente regla:
Cómo elegir los pivotes en la Fase 1
Al igual que con el método simplex para problemas de maximización estándar, primero escogeremos una columna, y luego una entrada espicífica en esa columna. Columna pivote La regla para escoger una columna pivote is la siguiente: Mira todos los números en la primera fila marcada con estrella, excluyendo la última entrada a la derecha (en la columna Resultado). Entre aquellos, escoge el número positivo con el valor más grande; su columna es entonces la columna pivote. Si hay dos o más candidatos, escoge alguno de aquellos. Si no hay números positivos para elegir, eso indica que la región factible está vacía, por lo que el problema de PL no tiene solución.
Al igual que con el método simplex para problemas de maximización estándar, primero escogeremos una columna, y luego una entrada espicífica en esa columna. Columna pivote La regla para escoger una columna pivote is la siguiente: Mira todos los números en la primera fila marcada con estrella, excluyendo la última entrada a la derecha (en la columna Resultado). Entre aquellos, escoge el número positivo con el valor más grande; su columna es entonces la columna pivote. Si hay dos o más candidatos, escoge alguno de aquellos. Si no hay números positivos para elegir, eso indica que la región factible está vacía, por lo que el problema de PL no tiene solución.
%%Example
En la tabla inicial del problema PL demonstración, la entrada positiva más grande en la primera fila marcada con estrella es el 1, así seleccionamos la columna-z como la columna pivote. El pivote en sí estará en alguna parte de esta columna.
En la tabla inicial del problema PL demonstración, la entrada positiva más grande en la primera fila marcada con estrella es el 1, así seleccionamos la columna-z como la columna pivote. El pivote en sí estará en alguna parte de esta columna.
Seleccionar el pivote Usamos las mismas reglas que usamos para los problemas de maximización estándar para decidir qué entrada usar como pivote en la columna pivote, pero con una regla de desempate diferente:
- El pivote debe ser positivo (números negativos o ceros no son permitidos como pivotes).
- Para cada entrada positiva $b$ en la columna pivote, calcule la razón $a/b$, donde $a$ es el número en la columna más a la derecha de esa fila. A esto lo llamamos razón de prueba.
- Entre estas razones, escoge la más pequeña. La entrada correspondiente $b$ es el pivote.
- Regla de desempate: Si las razones de prueba para dos o más entradas en la columna pivote califican como las más pequeñas, elija una que esté en una fila destacada si sea posible.
%%Example
#[In the demonstration example we are working with, the pivot will be one of the 1s in the z-column. Here are the test ratios for these candidates:][En el ejemplo demonstración con el que estamos trabajando, el pivote será uno de los 1 en la columna-z. Aquí están las razones de prueba para estos candidatos:]# Ya que la razón de prueba más pequeña ocurre en fila 2, nuestro pivote será la 1 resaltada como mostrado. #[Because the pivot is in a starred row, pivoting there will result in the star being (permanently) removed from that row becuase the entering variable ($z$) is non nogative:][Debido a que el pivote está en una fila marcada con estrella, pivotar allí hará que la estrella se elimine (permanentemente) de esa fila porque la variable entrante ($z$) no es negativa:]# Si el pivote no hubiera estado en una de las filas marcadas con estrella, ambas estrellas habrían permanecido por el momento, pero eventualmente el proceso descrito aquí da como resultado que se eliminen todos las estrellas.
#[In the demonstration example we are working with, the pivot will be one of the 1s in the z-column. Here are the test ratios for these candidates:][En el ejemplo demonstración con el que estamos trabajando, el pivote será uno de los 1 en la columna-z. Aquí están las razones de prueba para estos candidatos:]# Ya que la razón de prueba más pequeña ocurre en fila 2, nuestro pivote será la 1 resaltada como mostrado. #[Because the pivot is in a starred row, pivoting there will result in the star being (permanently) removed from that row becuase the entering variable ($z$) is non nogative:][Debido a que el pivote está en una fila marcada con estrella, pivotar allí hará que la estrella se elimine (permanentemente) de esa fila porque la variable entrante ($z$) no es negativa:]# Si el pivote no hubiera estado en una de las filas marcadas con estrella, ambas estrellas habrían permanecido por el momento, pero eventualmente el proceso descrito aquí da como resultado que se eliminen todos las estrellas.
Fase 2: proceder como con el problema de maximización estándar.
Una vez que hemos eliminado las estrellas, seleccionamos el pivote como es habitual en la columna de una variable de decisión con la entrada más negativa y así avanzamos hasta que se resuelva el problema.
El método simplex para problemas mximización general: de principio a fin
Pasos en la solución de un problema de maximización general
- Convierte el problema en la forma de ecuación usando variables de holgura y excendente. (Elimine decimales y fracciones si es posible, ya sea multiplicando ambos lados de las restricciones por enteros positivos adecuados, o multiplicando ambos lados de las ecuaciones resultantes por enteros positivos adecuados.)
- Configura la primera tabla, donde las variables activas son las variables de holgura y excendente. Marca on estrellas todas las vvariables activas cuyas valores son negativos. En la primera tabla, estas van a ser las variables de excedente.
- Fase 1: deshacerse de las estrellas Si hay filas marcadas con estrellas, seleccione una columna de una variable de decisión cuya entrada en la primera fila marcada con estrella sea la más positiva.
- En aquella columna, selecciona un pivote cuya razón de prueba es lo maás baja entre otras tales entradas.
- Pivota sobre la entrada seleccionada usando operaciones de fila del tipo específico descrito en %%gjtutB, recordando indicar también la variable activa entrante en la fila del pivote.
- Si el pivote estaba en una fila marcada con estrella, la nueva entrante variable activa es positiva, por lo que se debe quitar la estrella. Si, además, otras variables activas en filas destacadas se vuelven cero, elimina esas estrellas también, pero multiplica esas filas por $-1$.
- Repite los pasos 3 a 6 hasta que no quedan filas marcadas con esrellas.
- Fase 2: Continúa pivoteando como en el método símplex para problemas de maximización estándar hasta que no haya indicadores negativos en la fila inferior. La solución básica en ese punto da una solución al problema de PL.
%%Example
#[Here is the complete solution to the LP problem we looked at above in Example A.][Aquí está la solución completa al problema de LP que vimos arriba en Ejemplo 1]#
Tu tarea principal en este tutorial es hacer un cálculo completo de principio a fin para un problema de PL no estándar:
#[Here is the complete solution to the LP problem we looked at above in Example A.][Aquí está la solución completa al problema de LP que vimos arriba en Ejemplo 1]#
#[Maximize][Maximizar]# \t $p = 2x + 3y + z$
\\ #[subject to][sujeto a]# \t $x + y + z \leq 40$
\\ \t $-y + z \geq 10$
\\ \t $2x + y - z \geq 10$
\\ \t $x \geq 0, y \geq 0, z \geq 0$.
- Convierte el problema en la forma de ecuación usando variables de holgura y excendente.
$x + y + z + s = 40$ \\ $-y + z - t = 10$ \\ $2x + y - z - u = 10$ \\ $-2x - 3y - z + p = 0$.
- Configura la primera tabla, donde las variables activas son las variables de holgura y excendente. Marca on estrellas todas las vvariables activas cuyas valores son negativos.
- Fase 1: deshacerse de las estrellas Si hay filas marcadas con estrellas, seleccione una columna de una variable de decisión cuya entrada en la primera fila marcada con estrella sea la más positiva.
- En aquella columna, selecciona un pivote cuya razón de prueba es lo maás baja entre otras tales entradas.
- Pivota sobre la entrada seleccionada usando operaciones de fila del tipo específico descrito en %%gjtutB, recordando indicar también la variable activa entrante en la fila del pivote.
↓
- Si el pivote estaba en una fila marcada con estrella, la nueva entrante variable activa es positiva, por lo que se debe quitar la estrella. Si, además, otras variables activas en filas destacadas se vuelven cero, elimina esas estrellas también, pero multiplica esas filas por $-1$. #[Here, the star is removed from Row 2. No other stars can be removed.][Aquí, la estrella se elimina de la Fila 2. No se pueden eliminar otras estrellas.]#
- Repite los pasos 3 a 6 hasta que no quedan filas marcadas con esrellas.
Como todavía hay una fila marcada con estrella, escogemos su valor más positivo y necesitamos pivotar en esa columna:↓#[Therefore we pivot on the boxed 1.][Por lo tanto, pivotamos en la 1 encajada.]#↓Ya que no quedan ningunas filas marcadas de estrellas, hemos completada la Fase 1, y así pasamos a la Fase 2: #[The most negative indicator in the bottom row is the $-4$ in the $y$-column, and the only possible pivot we can use is the $4$ in the first row:][El indicador más negativo en la fila inferior es $-4$ en la columna $y$, y el único pivote posible que podemos usar es $4$ en la primera fila:]#↓Como no hay más entradas negativas en la fila inferior debajo de las variables de decisión, hemos terminado, por lo que la solución al problema de PL es la solución básica actual:$x = 20/2 = 10$; \t $y = 40/4 = 10$ \\ $z = 80/4 = 20$; \t $s = 0$; (#[inactive][inactiva]#) \\ $t = 0$; (#[inactive][inactiva]#); \t $u = 0$; (#[inactive][inactiva]#) \\ $p = 70/1 = 70$; \t (#[Maximum value of $p$][Valor má'ximo de $p$]#)
Problemas PL generales de minimización
#[You might wonder why we have concentrated on maximization problems so much. What about minimization problems?][Quizás te preguntes por qué nos hemos concentrado tanto en los problemas de maximización. ¿Qué pasa con los problemas de minimización?]#
Solucionar problemas PL generales de minimización
Tratamos los problemas de minimización simplemente convirtiéndolos en problemas de maximización, como se ilustra en el siguiente ejemplo:
Tratamos los problemas de minimización simplemente convirtiéndolos en problemas de maximización, como se ilustra en el siguiente ejemplo:
%%Example
#[Here is a general LP minimization problem.][Aquí está un problema PL de minimización:]#
#[Here is a general LP minimization problem.][Aquí está un problema PL de minimización:]#
#[Minimize][Minimizar]# \t $c = 2x - 3y + 4z + w$
\\ #[subject to][sujeto a]# \t $4x + 2y + w \leq 10$
\\ \t $4x - 3y + z + w \geq 3$
\\ \t $2x + y - z \leq 10$
\\ \t $x \geq 0, y \geq 0, z \geq 0$.
#[In general, the minimum value of $c$ would be the maximum vaue of its negative, we can instead maximize the negative of $c$, which we will call $p$:][En general, el valor mínimo de $c$ sería el valor máximo de su negativo, en su lugar podemos maximizar el negativo de $c$, que llamaremos $p$:]#
#[Maximize][Maximizar]# \t $p = -2x + 3y - 4z - w$
\\ #[subject to][sujeto a]# \t $4x + 2y + w \leq 10$
\\ \t $4x - 3y + z + w \geq 3$
\\ \t $2x + y - z \leq 10$
\\ \t $x \geq 0, y \geq 0, z \geq 0$,
#[which we can now solve according to the instructions for general maximization problems.][que ahora podemos resolver de acuerdo con las instrucciones para problemas generales de maximización.]#
#[If you want to see the tableaus in solving this problem, simply copy and paste the following text in the][Si deseas ver los cuadros para resolver este problema, simplemente copie y pegue el siguiente texto en la]# Herramienta pivotar Gauss-Jordan.
Maximize p = -2x + 3y - 4z - w subject to
4x + 2y + w <= 10
4x - 3y + z + w >= 3
2x + y - z <= 10
Ahora prueba algunos de los ejercicios en la Sección 6.4 en el libro Matemáticas finitas y cálculo aplicado.
Derechos de autor © 2020 Stefan Waner y Steven R. Costenoble