[martiniano]

Hola. Buenos días.

Me ha surgido una duda repasando lo del método símplex y resulta que me falla algo a la hora romper empates en el criterio de salida. He consultado los apuntes que Carlos Ivorra tiene disponibles en su página web (versión antigua) y también un libro llamado Investigación de operaciones, más conocido por los apellidos de sus autores, Hillier-Lieberman (9a edición).

El caso es que lo que yo he entendido a partir estos dos materiales es que se puede romper el empate arbitrariamente y continuar el algoritmo como si nada. Es cierto que el Hillier avisa de que existen algunos casos en los que se deben tener en cuenta otras cosas, pero los tacha de muy poco habituales y los excluye de los contenidos del libro.

A mí se me debe estar escapando algo, pero creo que lo que es fundamental (así, por intuición) es que se debe comprobar que en los pasos sucesivos ningún término independiente cambia de signo. Si esto sucediese, nos estaría indicando que nos hemos salido de la región factible y que tendríamos que haber roto el empate de otra manera.

Después de elegir la variable saliente viene lo del criterio de parada. Es decir, mirar a partir del signo de los costes reducidos si la función objetivo puede mejorar o no. Si es que no, entonces estamos en el óptimo. Sin embargo, no he encontrado tampoco ningún comentario al respecto, es decir, nada que nos diga que debemos comprobar que los términos independientes sean todos positivos. Claro que esto último siempre se dará, salvo en la situación que he comentado anteriormente.

Por si queda más claro, en el Spoiler un ejemplo concreto que ilustra esto:

Spoiler

Minimizar la función:

\( F(x,y)=-3x-2y \)

Con las restricciones:

A: \( x+y\leq{10} \)
B: \( x+2y\leq{20} \)
C: \( 2x+y\leq{15} \)
D: \( 3x+y\leq{22.5} \)

En forma tabular y estándar el asunto queda así:

\( \begin{bmatrix}{...}&{x}&{y}&{h_1}&{h_2}&{h_3}&{h_4}&{b}&{\theta}\\{A}&{1}&{1}&{1}&{0}&{0}&{0}&{10}&{10}\\{B}&{1}&{2}&{0}&{1}&{0}&{0}&{20}&{20}\\{C}&{2}&{1}&{0}&{0}&{1}&{0}&{15}&{7.5}\\{D}&{3}&{1}&{0}&{0}&{0}&{1}&{22.5}&{7.5}\\{Z}&{-3}&{-2}&{0}&{0}&{0}&{0}&{0}&{...}\end{bmatrix} \)

Vemos que entra \( x \) y hay empate en la salida entre \( h_3 \) y \( h_4 \), si se nos ocurriese sacar a \( h_4 \), en la siguiente iteración parecería que todo transcurre con bastante normalidad, salvo por el hecho de que una variable básica, \( h_3 \), valga cero, cosa que, según creo, indica que antes ha habido un empate:

\( \begin{bmatrix}{...}&{x}&{y}&{h_1}&{h_2}&{h_3}&{h_4}&{b}&{\theta}\\{A}&{0}&{2/3}&{1}&{0}&{0}&{-1/3}&{2.5}&{3.75}\\{B}&{0}&{5/3}&{0}&{1}&{0}&{-1/3}&{12.5}&{7.5}\\{C}&{0}&{1/3}&{0}&{0}&{1}&{-2/3}&{0}&{0}\\{D}&{1}&{1/3}&{0}&{0}&{0}&{1/3}&{7.5}&{22.5}\\{Z}&{0}&{-1}&{0}&{0}&{0}&{1}&{22.5}&{...}\end{bmatrix} \)

Entra \( y \), sale \( h_1 \)... Y es en la siguiente iteración cuando vemos que nos hemos salido de la región factible y que habría que haber roto el empate de la otra manera, ¿no?, ya que uno de los términos independientes, el de la restricción C, nos queda negativo. Lo que me pasa es que no veo en qué paso del método símplex se tiene eso en cuenta o de qué manera arregla el entuerto. Es más, si no lo hacemos y sólo vemos que los costos reducidos son todos positivos (cosa que ocurre en este caso pero no es algo general), nos quedamos con que hemos llegado al óptimo, pero esto es falso porque estamos fuera de la región factible:

\( \begin{bmatrix}{...}&{x}&{y}&{h_1}&{h_2}&{h_3}&{h_4}&{b}&{\theta}\\{A}&{0}&{1}&{3/2}&{0}&{0}&{-1/2}&{3.75}&{...}\\{B}&{0}&{0}&{-5/2}&{1}&{0}&{1/2}&{6.25}&{...}\\{C}&{0}&{0}&{-1/2}&{0}&{1}&{1/6}&{\color{red}-1.25\color{black}}&{...}\\{D}&{1}&{0}&{-1/2}&{0}&{0}&{1/2}&{6.25}&{...}\\{Z}&{0}&{0}&{3/2}&{0}&{0}&{1/2}&{26.25}&{...}\end{bmatrix} \)

[cerrar]

¿Qué me he perdido?   

Gracias de antemano por las ayudas y comentarios. Un saludo.

[martiniano]

Hola buenas.

Esto... que se me olvidó facilitar las transformaciones que hice en el símplex en el ejemplo que puse dentro del Spoiler. Si se está algo familiarizado con el método son bastante obvias, pero bueno, las subo ahora, a ver si así alguien se anima a comentar algo  . El subíncie indica el número de fila que estoy tratando, y las "primas", o apóstrofos, que se trata de la fila correspondiente "nueva", es decir, después de la transformación.

Primera transformación:

\( (1/3)F_4\rightarrow{F_4'} \)
\( F_1-F_4'\rightarrow{F_1'} \)
\( F_2-F_4'\rightarrow{F_2'} \)
\( F_3-2F_4'\rightarrow{F_3'} \)
\( F_5+3F_4'\rightarrow{F_5'} \)

Segunda transformación:

\( (3/2)F_1\rightarrow{F_1'} \)
\( F_2-(5/3)F_1'\rightarrow{F_2'} \)
\( F_3-(1/3)F_1'\rightarrow{F_3'} \)
\( F_4-(1/3)F_1'\rightarrow{F_4'} \)
\( F_5+F_1'\rightarrow{F_5'} \)

Gracias de nuevo y un saludo 

[Carlos Ivorra]

No he mirado tus cuentas con detalle, pero en el símplex, si aplicas correctamente el criterio de salida, es imposible que te salgas de la región factible. Eso no tiene nada que ver con los empates. El criterio de salida garantiza precisamente que al iterar no te saldrás de la región factible.

[martiniano]

Hola Carlos. Muchas gracias por tu respuesta.

No he mirado tus cuentas con detalle, pero en el símplex, si aplicas correctamente el criterio de salida, es imposible que te salgas de la región factible. Eso no tiene nada que ver con los empates. El criterio de salida garantiza precisamente que al iterar no te saldrás de la región factible.

Pues, me dejas más preocupado de lo que estaba, ¿quieres decir que no estoy aplicando bien el criterio de salida? Y yo que pensaba que eso lo tenía claro...

A ver, yo lo que hago es mirar a ver cuál es la variable que entra. En el caso de que tuviésemos que minimizar la función objetivo, se pone la función objetivo en función de las variables no básicas y se mira cuál es la variable que tiene el coeficiente (en tus apuntes lo llamas rendimiento marginal, en los que tengo yo coste reducido) menor, es decir, más negativo.

Después, se dividen los términos independientes (\( b \) en la tabla que he puesto en el ejemplo) entre los coeficientes que en cada restricción tiene la variable que entra (obteniendo los parámetros que en la tabla he llamado \( \theta \)) y se mira qué resultado es el menor de los positivos. Saldrá la variable básica de la restricción correspondiente. Y aquí es donde me surge la duda. ¿Qué ocurres si hay un empate como en el ejemplo que he expuesto? Si saco la variable que no toca me salgo de la región factible, o al menos, eso es lo que yo veo...

Discúlpame, pero sigo sin ver qué es lo que hago mal... 

El ejemplo ilustrado gráficamente, a ver si sirve de algo:

Spoiler

En la primera iteración nos movemos desde el vértice \( O \) hasta el vértice \( C \) lo que ocurre es que si elegimos que salga la variable \( h_4 \) en lugar de la variable \( h_3 \), ya que, según he entendido yo el método, hay un empate entre ellas en el criterio de salida, en la siguiente iteración nos moveríamos sobre la recta \( r \) hasta el punto K, saliéndonos de la región factible.

Pues eso... Que a ver si me iluminas un poquito, porque no sé dónde me pierdo... Gracias.

[cerrar]

Muchas gracias, y un saludo

[Carlos Ivorra]

Ya veo el problema. Es que en tu segunda tabla entra \( y \), pero no sale \( h_1 \). Si sacas \( h_1 \), que no es la que toca, te sales del conjunto de oportunidades, como es lógico que suceda. La variable que sale es \( h_3 \), precisamente porque vale 0.

La idea del símplex es muy simple, como su nombre indica: la variable \( x \) vale 0, y el criterio de entrada te dice que si la haces aumentar, la función objetivo mejorará. Pero cuando aumentas \( x \), las demás variables básicas se van a modificar, y tienes que sacar la primera que llegue a valer \( 0 \), porque si haces cero otra, cuando ésa haya llegado a cero, la primera en hacerse cero se habrá hecho ya negativa, y te habrás salido del conjunto de oportunidades.

Para saber cuál tarda menos en llegar a cero divides su valor actual (el espacio que tiene que recorrer para llegar a 0) entre la velocidad a la que se mueve (contando únicamente las velocidades positivas, porque en realidad la velocidad positiva indica que la variable disminuye, mientras que las velocidades negativas corresponden a variables que aumentan y, por lo tanto, nunca llegarán a 0. Al dividir el espacio entre la velocidad tienes el tiempo que tardan en llegar a 0, y tienes que sacar la que menos tiempo tarda.

Ahora bien, si una variable ya es 0 (y tiene velocidad positiva) es ésa la que tienes que sacar, porque si sacas otra, esa variable parte de 0 y decrece, luego se te hará negativa, que es lo que te ha pasado.

En general: para el criterio de salida, tienes que considerar todas las variables con velocidad positiva y, de entre ellas, sacar la que dé menor cociente valor actual / velocidad, sin descartar las que tienen valor actual 0. En particular, si hay una variable que vale 0 y su velocidad es positiva, ésa es la que sale (o una cualquiera de ellas si hay varias).

[martiniano]

Hola, Carlos.

Muchísimas gracias por la respuesta, ya he resuelto mi duda. Había malinterpretado lo que había que hacer con los cocientes mínimos cuando alguno valía cero. Yo los descartaba, tal y como te has dado cuenta y eso no va así. Hay que descartar los que tienen "velocidad negativa" o nula, como dices, antes incluso de calcular los cocientes mínimos.

Vale, vale. Era eso...

Muchas gracias. Saludos.