Introducción al método símplex

Versión juego adaptivo

Este tutorial: Parte A: Introducción al método símplex

Ir a Parte B: Método simplex: de principio a fin

(Se puede encontrar este tema en la Sección 6.3 en el libro Matemáticas finitas y cálculo aplicado)

¿Qué es un tutorial juego adaptivo? ▶

No me gusta este tutorial. ¡Llévame de vuelta a la versión antigua!

Recursos

Herramienta método simplex

Herramienta pivotar Gauss-Jordan

Herramienta pivotar Gauss-Jordan Excel

Problemas de maximización estándar y variables de holgura

%%Note Para intender este tutorial, debes saber como se resuelven los sistemas de ecuaciones lineales mediante la reducción por filas como se describe en el %%gjtut o en la Sección 6.3 en el libro Matemáticas finitas y cálculo aplicado. En particular, debes saber cómo representar sistemas de ecuaciones en forma de matriz, cómo hacer operaciones de renglon y, en particular, cómo "pivotar" o "limpiar una columna" en una matriz. Debes revisar ese material si es necesario.

%%Q Recuérdame qué es un problema de programación lineal.
%%A Un problema de programación lineal (PL) es un problema en lo que debemos hallar el valor máximo o mínimo de una función objetiva lineal

$p = a_1x_1 + a_2x_2 + ... + a_nx_n \qquad$ \t %%Example $p = 3x - 2y + z$

sujeta a un conjunto de restricciones lineales de la forma

$b_1x_1 + b_2x_2 + ... + b_nx_n \leq c \qquad$ \t %%Example $x + y - 3z \leq 12$ \\ #[or][o]# \\ $b_1x_1 + b_2x_2 + ... + b_nx_n \geq c \qquad$ \t %%Example $3x+y-z \geq 0$

donde $b_1, b_2, ..., b_n, c$ son constantes con $c$ no negtiva.

El valor deseado más grande (o más pequeño) de la función objetiva se llama el valor optimal, y un conjunto de valores para las incógnitas $x_1, x_2, ..., x_n$ que nos da el valor óptimo es una solución óptima. Las variables $x_1, x_2, ..., x_n$ se llaman las variables decisión

Problemas maximización estándar son tipos específicos de los problemas de programación lineal:

Problema maximización estándar
Un problema de programación lineal (PL) se llama un problema de maximización estándar si:

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.

%%Examples
1. #[The following is a standard maximization problem:][El siguiente es un problema de maximización estándar:]#

#[Maximize][Maximizar]# \t $p = 2x - 3y + z$ \t #[Objective function][Función objectiva]# \\ #[subject to][sujeto a]# \t $3y + z \leq 0$ \\ \t $2x + y - z \leq 10$ \t #[Constraints][Restricciones]# \\ \t $x \geq 0, y \geq 0, z \geq 0$.

2. #[The following LP problem is not standard as presented, but can be rewritten a standard maximization problem:][El siguiente problema de PL no es estándar como se presenta, pero 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 \geq -5$ \\ \t $3y+5z \geq 0$ \\ \t $x \geq 0, y \geq 0, z \geq 0$.

Podemos invertir la desigualdad en la primera y segunda restricción multiplicando ambos lados por $-1$ para obtener el siguiente problema problema de maximización estándar:

#[Maximize][Maximizar]# \t $p = 3x-3y-8z$ \\ #[subject to][sujeto a]# \t $-x + z \leq 5$ \\ \t $-3y - 5z \leq 0$ \\ \t $x \geq 0, y \geq 0, z \geq 0$.

Uno para ti

Forma de ecuación de un problema de PL

El método que se utiliza con más frecuencia para resolver problemas de PL es el método simplex, del que hablaremos en el resto de este tutorial. El primer paso es reescribir todo el problema como un sistema de ecuaciones lineales:

Convertir a forma de ecuación
Aquí hay un truco para convertir cualquier desigualdad en una ecuación: si, por ejemplo,

$x \leq 5$,

entonces podemos hacer que el lado izquierdo sea igual a $5$ añadiéndole algo, llamado holgura.:

$x + s = 5 \qquad$ \t #[s is a nonnegative quantity called a slack variable.][s es una cantidad no negativa llamada una variable de holgura.]#

Entonces, por ejemplo, si $x = 1$ entonces $s$ sería igual a $4$ para dar el resultado de 5. Usamos esta técnica para reescribir todo el problema de PL como un sistema de ecuaciones como se muestra en el siguiente ejemplo.

%%Example A
#[Consider the following LP problem.][Vamos a considerar el siguente problema PL:]#

#[Maximize][Maximizar]# \t $p = 2x - 3y + z$ \\ #[subject to][sujeto a]# \t $x + y + z \leq 10$ \\ \t $4x - 3y + z \leq 3$ \\ \t $2x + y - z \leq 10$ \\ \t $x \geq 0, y \geq 0, z \geq 0$.

Primero convertimos todas las restricciones excepto las de la última línea en ecuaciones utilizando variables de holgura (una para cada desigualdad) como variables de decisión adicionales:

$x + y + z + s = 10$ \\ $4x - 3y + z + t = 3$ \\ $2x + y - z + u = 10$

Luego, como última ecuación, agregamos la ecuación objetivo, pero con todas las incógnitas llevadas al lado izquierdo:

$-2x + 3y - z + p = 0$.

Ahora tenemos un sistema de cuatro ecuaciones lineales con 7 incógnitas $x, y, z, s, t, u, p$:

$x + y + z + s = 10$ \\ $4x - 3y + z + t = 3$ \\ $2x + y - z + u = 10$ \\ $-2x + 3y - z + p = 0$.

Nota Las variables de decisión en este problema ampliado son las incógnitas originales $x, y, z$ junto con las variables de holgura $s, t, u$. No se permite que ninguna de estas cantidades sea negativa (aunque $p$, que no es una variable de decisión, puede o no ser negativa; por ejemplo, si $p$ representa ganancia,entonces un valor negativo indicaría una pérdida).

%%Q ¿Qué pasa con las desigualdades $x \geq 0, y \geq 0, z \geq 0$ en la última línea del problema PL?
%%A Omitimos las restricciones $x \geq 0, y \geq 0, z \geq 0$ ya que el método simplex asuma que todas las variables de decisión son no negativas. Estos incluyen $x, y, z,$ y también $s, t, u$ como comentamos anteriormente.

Uno para ti

Tablas simplex y variables soluciones

Siempre que tengamos un sistema de ecuaciones lineales podemos expresarlo en forma matricial usando la matriz aumentada del sistema de ecuaciones como se describe en el %%gjtut. En la situación aquí, tipicamente tenemos más ecuaciones que incógnitas, por lo que podemos esperar ver soluciones generales en las que algunas de las variables se pueden elegir arbitrariamente para obtener soluciones particulares (consulta %%gjtutC).

Recuerda que luego obtuvimos la solución general del sistema de la siguiente manera: usar operaciones de pivote para reducir la matriz aumentada, luego escribir el resultado en forma de ecucaciones y finalmente despejar a la primera variable en cada ecuación. El método símplex funciona haciendo algo similar, pero no por reducir primero la matriz de la forma habitual.

Echa un vistazo a la forma matricial aumentada del sistema de ecuaciones que obtuvimos en Ejemplo A arriba:

Este diseño tabular en particular se llama tabla simplex o, a veces, tableau simplex, y las variables enumeradas en la parte superior a veces se denominan variables de decisión.

Note importante: Evitar las fracciones y decimales Preferimos trabajar completamente con números enteros siempre que sea posible, como lo hacemos en el %%gjtutB. Por lo tanto, si hay fracciones o decimales racionales en tu tabla, primero debes eliminarlos si es posible multiplicando cada fila que contiene fracciones por un número entero adecuado. (Consulte Paso 1: Borrar todas las fracciones y/o decimales en aquello tutorial.)

#[Notice something funny: if we reorder the columns of the matrix with those of the last four variables $s, t, u$, and $p$ first, we get][Nota algo extraño: si reordenamos las columnas de la matriz con las de las últimas cuatro variables $s, t, u$, y $p$ primero, obtenemos]#

que ¡ya está en forma reducida! (las entradas en los recuadros cuyas columnas se borran se denominan pivotes). Como en %%gjtutC podemos volver a traducir a ecuaciones y así obtener la solución general de este sistema en la siguente forma:

$s = 10 - x - y - z$ \\ $t = 3 - 4x + 3y - z$ \\ $u = 10 - 2x - y + z$ \\ $p = 2x - 3y + z$, \\ $x, y, z$ #[arbitrary][arbitrarias]#

En el método simplex, elegimos que todas las variables arbitrarias sean cero (y las llamamos inactivas), lo que nos da lo que llamamos una solución básica:

$s = 10$ \t Variables activas \\ $t = 3$ \\ $u = 10$ \\ $p = 0$, \\ $x = 0, y = 0, z = 0$. \gap[20] \t Variables inactivas

Las variables que no se especificaron como arbitrarias son las correspondientes a los pivotes, y las llamamos variables activas (también pueden resultar cero, como vemos en el caso de la última, $p$). En lugar de reorganizar las columnas como hicimos anteriormente, indicamos las variables activas agregándolas como etiquetas a cada fila:

#[Each row label is the active variable coresponding to its pivot. We can directly read off the values of the active variables as shown:][Cada etiqueta de fila es la variable activa que corresponde a su pivote. Podemos leer directamente los valores de las variables activas como se muestra:]#

La tabla arriba es muy especial con las últimas cuatro variables las activas y las entradas pivote (encuadradas) todas iguales a 1. En el método simplex obtendremos tablas que se ven diferentes mediante pivotar (despejar la columna de una entrada de "pivote" seleccionada; ver %%gjtutB para revisar). Supongamos, por ejemplo, que pivotamos en el $4$ en la columna $x$. Luego obtenemos un nuevo tabla como se muestra.

Observa que el $4$ encuadrado es ahora el pivote de la segunda fila. Ya que el pivote de esta fila ahora está en la columna $x$, cambiamos la etiqueta de la fila de $s$ a $x$, que ingresa como una nueva variable activa en lugar de $s$ (la variable de salida).

Nota En nuestro enfoque del método símplex, no insistiremos en que los pivotes se conviertan en 1, introduciendo así fracciones; en cambio, consideramos matemáticamente más elegante (¡y mucho más fácil!) trabajar con números enteros como lo hicimos en el %%gjtut. Así, simplemente leemos las soluciones básicas como fracciones si es necesario, como vimos anteriormente.

Pasar de una tabla a otra: Elegir el pivote

En el método símplex, pasamos de una solución básica a la siguiente pivotar de tal manera que el valor resultante de $p$ sigue aumentando. Cuando no puede ir más alto, ¡hemos terminado! El secreto del método es cómo elegimos el pivote para hacer que el valor de $p$ aumente. Estas son las reglas para seleccionar el pivote en cualquier etapa.

Cómo elegir el pivote
Para escoger cada entrada pivote, 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 última fila, excluyendo la última entrada a la derecha (en la columna Resultado). Entre aquellos, escoge el número negativo con el valor absoluto 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 negativos a escoger, ¡entonces estás terminado! y la solución del problema PL es la corriente solución básica.

%%Example
#[In the initial tableau of the demonstration LP problem, the negative entry in the bottom row with the largest numerical value is the −2, so the pivot column is the x-column. The actual pivot will be somewhere in this column.][En la tabla inicial del problema PL demonstración, la entrada negativa con el valor absoluto más grande en la última fila es la −2, así seleccionamos la columna-x como la columna pivote. El pivote en sí estará en alguna parte de esta columna.]#

Seleccionar el pivote Usa las siguientes reglas para decidir cuál de las entradas en la columna que seleccionaste usar como pivote:

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. (Si hay más de uno que da la razón más baja, elija cualquiera).

%%Example
#[In the demonstration example we are working with, the pivot will be either the 4, the 1 or the 2 in the x-column. Here are the test ratios for these candidates:][En el ejemplo demonstración con el que estamos trabajando, el pivote será o la 4, la 1, o la 2 en la columna-x. Aquí están las razones de prueba para estos candidatos:]# Ya que la razón de prueba más pequeña ocurre en la fila 2, nuestro pivote será la 4 como mostrado.

Pasar de una tableau a otra: Pivotar

Una vez que hayamos seleccionado una entrada pivote, pivotaremos sobre ella utilizando el método descrito en %%gjtutB. Es decir, limpiamos su columna usando operaciones de fila de un tipo específico para que no se introduzcan fracciones en nuestros cuadros. (Nosotros no primero convertimos el pivote a un $1$ cuando nuestro cuadro consiste en números enteros, para no introducir fracciones innecesariamente). En situaciones donde el cuadro no se puede expresar con números enteros, o cuando están usando tecnología para hacer el pivote, luego se puede usar el pivote tradicional y convertir los pivotes a 1s.

Pivotar en el método simplex Una tableau de método simplex es solo una matriz aumentada, por lo que pivotamos exactamente de la misma manera como en %%gjtutB. Ten en cuenta que la columna más a la derecha y la última fila también forman parte de la matriz. La única diferencia es que las filas están etiquetadas por variables activas. Por ejemplo, en la siguiente tabla las variables activas son $s, t, u$.

#[If we pivot in the boxed entry shown above, we get :][Si pivotamos en la entrada encajada que se muestra, obtenemos]#

↓

Cómo funciona el método simplex

#[Here, we have discussed all the steps needed to completely solve a standard maximization problem using the simplex method:][Hemos discudido aquí todos los pasos para resolver completametne un problema de maximización estándar usando el mé simplex:]#

Convierte el problema en la forma de ecuación usando variables de holgura. (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.
Selecciona una columnade una variable de decisión cuya entrada en la fila inferior sea la más negativa.
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 anteriormente, recordando indicar también la variable activa entrante en la fila del pivote.
#[Repeat steps 3 to 5 until there are no negative numbers in the bottom row under the decision variables. The basic solution at that point gives a solution to the LP problem.][Repite los pasos 3 a 5 hasta que no haya números negativos en la fila inferior debajo de las variables de decisión. La solución básica en ese punto da una solución al problema de LP.]#

Ahora prueba algunos de los ejercicios en la Sección 6.3 en el libro Matemáticas finitas y cálculo aplicado.

←	Anterior Siguiente → Versión no juego Todos tutoriales Página principal Todo para cálculo Todo para mat.finitas Todo English