Rincón Matemático
Matemática => Matemática Discreta y Algoritmos => Programación lineal => Mensaje iniciado por: ferphi en 30 Junio, 2020, 12:35 am
-
Hola chicos, soy nuevo en el foro, todavía estoy aprendiendo cómo usarlo, me gustaría de ser posible que ayudaran con la solución de este problema (si puede ser explicado mejor). Gracias por adelantado.
Considere un modelo de programación en el que una máquina se pueda encender como máximo \( k \) veces durante
un horizonte de períodos de \( T \). En este modelo, hay dos conjuntos de variables: \( y_t = 1 \) si la máquina está
encendido durante el período \( t \), y \( z_t = 1 \) si la máquina está encendida en el período \( t \). Entonces las restricciones
se parece a lo siguiente:
\( \sum_{t=1}^T{z_t}\leq{k} \)
\( z_t-y_t+y_{t-1}\geq{0}\quad\forall{t=1,\dots,T} \)
\( z_t\leq{y_t},\quad\forall{t=1,\dots,T} \)
0\( \leq{}y_t, z_t\leq{1},\quad\forall{t=1,\dots,T} \)
donde \( y_t = 1 \) si la máquina está encendida en el período \( t \), y \( z_t = 1 \) si se encendió en el período \( t \). Mostrar que la matriz resultante
es TU (totalmente unimodular).
-
Hola.
Me resulta un poco extraño el enunciado. ¿Cuál es la diferencia entre \( y_t \) y \( z_t \)? Tampoco me queda claro si existe o no \( y_0 \).
Un saludo.
-
Hola
Me resulta un poco extraño el enunciado. ¿Cuál es la diferencia entre \( y_t \) y \( z_t \)? Tampoco me queda claro si existe o no \( y_0 \).
Lo escribió bien la segunda vez.
donde \( y_t = 1 \) si la máquina está encendida en el período \( t \), y \( z_t = 1 \) si se encendió en el período \( t \).
Por ejemplo si hay cinco períodos y se tiene:
\( \begin{array}{|c|c|c|c|c|c|}
\hline
{z}&{1}&{0}&{0}&{1}&{0}\\
\hline
{y}&{1}&{1}&{0}&{1}&{1}\\
\hline
\end{array} \)
Quiere decir que en el período 1 se encendió la máquina y se mantuvo encendida en los dos primeros períodos, pero se apagó para el tercero.
En el cuarto volvió a encenderse y se mantuvo encendida hasta el quinto.
La desigualdad \( y_t\leq y_{t-1}+z_t \) significa que en el período \( t-1 \) la máquina estaba apagada y no se encendió en el período \( t, \) entonces en ese período permanece apagada.
Y las demás se interpretan análogamente.
Saludos.
-
Hola
Me resulta un poco extraño el enunciado. ¿Cuál es la diferencia entre \( y_t \) y \( z_t \)? Tampoco me queda claro si existe o no \( y_0 \).
Lo escribió bien la segunda vez.
donde \( y_t = 1 \) si la máquina está encendida en el período \( t \), y \( z_t = 1 \) si se encendió en el período \( t \).
Por ejemplo si hay cinco períodos y se tiene:
\( \begin{array}{|c|c|c|c|c|c|}
\hline
{z}&{1}&{0}&{0}&{1}&{0}\\
\hline
{y}&{1}&{1}&{0}&{1}&{1}\\
\hline
\end{array} \)
Quiere decir que en el período 1 se encendió la máquina y se mantuvo encendida en los dos primeros períodos, pero se apagó para el tercero.
En el cuarto volvió a encenderse y se mantuvo encendida hasta el quinto.
La desigualdad \( y_t\leq y_{t-1}+z_t \) significa que en el período \( t-1 \) la máquina estaba apagada y no se encendió en el período \( t, \) entonces en ese período permanece apagada.
Y las demás se interpretan análogamente.
Saludos.
exacto, si me equivoque varias veces al escribir, por eso lo modifique al final. Un saludo.
-
Hola.
donde \( y_t = 1 \) si la máquina está encendida en el período \( t \), y \( z_t = 1 \) si se encendió en el período \( t \).
Por ejemplo si hay cinco períodos y se tiene:
\( \begin{array}{|c|c|c|c|c|c|}
\hline
{z}&{1}&{0}&{0}&{1}&{0}\\
\hline
{y}&{1}&{1}&{0}&{1}&{1}\\
\hline
\end{array} \)
Quiere decir que en el período 1 se encendió la máquina y se mantuvo encendida en los dos primeros períodos, pero se apagó para el tercero.
En el cuarto volvió a encenderse y se mantuvo encendida hasta el quinto.
La desigualdad \( y_t\leq y_{t-1}+z_t \) significa que en el período \( t-1 \) la máquina estaba apagada y no se encendió en el período \( t, \) entonces en ese período permanece apagada.
Y las demás se interpretan análogamente.
De acuerdo. Gracias por la aclaración. Ahora ya entiendo el enunciado. No tengo la solución, pero me parece un problema interesante.
\( \sum_{t=1}^T{z_t}\leq{k} \)
\( z_t-y_t+y_{t-1}\geq{0}\quad\forall{t=1,\dots,T} \)
\( z_t\leq{y_t},\quad\forall{t=1,\dots,T} \)
0\( \leq{}y_t, z_t\leq{1},\quad\forall{t=1,\dots,T} \)
donde \( y_t = 1 \) si la máquina está encendida en el período \( t \), y \( z_t = 1 \) si se encendió en el período \( t \). Mostrar que la matriz resultante
es TU (totalmente unimodular).
En la matriz pongo en las \( T \) primeras columnas los coeficientes de las \( z_t \) y en las \( T \) siguientes los coeficientes de las \( y_t \). Coloco las restricciones en el orden en que las enuncia ferphi. Elimino la fila \( T+1 \), porque es igual a la fila \( 2 \) y las \( 2T \) últimas porque solo tienen un uno cada una y todo lo demás ceros. Entonces, me queda una matriz de orden \( 2T \). Aquí me hubiese gustado aplicar inducción sobre \( T \), pero no he llegado a nada ni parece que sea el buen camino.
Un saludo.