Algunos ejemplos de PD

1.2 Algunos Ejemplos de PD.

En esta sección se presentan otros ejemplos de PD. Los primeros cuatro ejemplos implican formulaciones y cálculos de modelos. El último ejemplo presenta una comparación entre las ecuaciones recursivas de avance y de retroceso. Conforme el lector estudie esta sección advertirá que le será de utilidad coda modelo como una sola red. Cuando se haga esto, cerciórese de que se tenga un entendimiento claro de los elementos básicos del modelo: (1) etapas, (2) estados en cada etapa y (3) alternativas de decisión (propuesta) en cada etapa.

Como se indicó antes, el concepto de estado suele ser el más importante o sutil. Nuestra experiencia indica que el entendimiento del concepto de estado se ve acrecentado al intentar “cuestionar la validez” en la forma en que éste se defina. Pruébese una definición diferente que pueda parecer “más lógica” y utilícese en los cálculos recursivos. El lector descubrirá por último que la definición que se da aquí no es incorrecta y, en la mayoría de los casos, puede ser la única definición correcta. En el proceso el lector podrá comprender el significado absoluto del concepto de estado.

Ejemplo 1.2-1 (Problema del cargamento)

Considere que se carga un barco con N artículos. Cada unidad del artículo i tiene un peso wi y un valor de vi (i = 1,2,..., N). El peso de carga máximo es W. Se requiere determinar la cantidad de carga más valiosa sin que se exceda el peso máximo disponible en el barco. Especialmente, considere al caso siguiente de tres artículos y suponga que W = 5.

Nota: la solución óptima de este ejemplo puede tenerse por inspección. Un problema típico usualmente implica un número más grande de artículos y por tanto, la solución no será tan obvia. Ver la descripción al final de este artículo.

Considere primero el problema general de N artículos. Si ki es el número de unidades del artículo i, el problema será:

Si no está restringido a valores enteros, la solución se determina fácilmente por el método simplex. En efecto, ya que existe solamente una restricción, será básica únicamente una variable y el problema se reduce a seleccionar el artículo i para el cual vi W / wi es máximo. Ya que la programación lineal no es aplicable aquí, se intentará resolver el problema por programación dinámica. Debe notarse que este problema también es típico de los que pueden resolverse con técnicas de programación entera.

El modelo de PD se construye considerando en primer término sus tres elementos básicos:

- La etapa j está representada por el artículo j, j = 1,2,..., N.

- El estado yj en la etapa j es el peso total asignado a las etapas j, j + 1,..., N; y1 = W y yj = 0,1,..., W para j = 2,3,...N.

- La alternativa kj en la etapa j es el número de unidades del artículo j. El valor de kj puede ser tan chico como cero o tan grande como [W / wj], donde [W / wj] es el mayor entero incluido en [W / wj].

Existe una similitud sorprendente entre este problema y el ejemplo del problema del capital, ya que ambos son el tipo de asignación de recursos. Tal vez la única diferencia será que las alternativas del modelo del cargamento están dadas directamente como el modelo del presupuesto del capital.

Sea

fj (yj) = valor óptimo de las etapas j, j + 1, ...,N dado es estado y1

La ecuación recursiva (de retroceso) está dada como:

Nótese que el valor factible máximo de kj está dado por [yj / wj]. Este límite suprimirá automáticamente todas las alternativas infactibles para un valor dado del estado yj.

Ejemplo 1.2-2

Establezca la relación existente entre Rj (kj) y cj (kj) en el modelo del presupuesto de capital y los modelos correspondientes del modelo de cargamento.

[Resp. Rj (kj) corresponden a vjkj y cj (kj) es equivalente a wj kj].

Para el ejemplo especial dado, los cálculos de las etapas se efectúan como sigue.

Etapa 3

Etapa 2

Etapa 1

Dada y1=W=5, la solución óptima asociada es (k1, k 2, k3) = (2, 0,1), con un valor total de 160.

Obsérvese que en la etapa 1, basta con construir la tabla para y1= 0, 1, 2, 3, 4 y 5, es posible estudiar cambios en la solución óptima cuando la asignación del peso máximo se reduce por debajo de W = 5. Esta es una forma de análisis de sensibilidad que ofrecen automáticamente los cálculos de programación dinámica.

Ejemplo 1.2-3

Obtenga la solución óptima al problema del cargamento en cada uno de los casos siguientes.

(1) W = 3.

[Resp. (k1, k 2, k3) = (1, 0,1); valor total = 95]

(2) W = 4.

[Resp. (k1, k 2, k3) = (2, 0,0); valor total = 130]

Aparentemente el problema del cargamento puede resolverse en general calculando las relaciones vj /wj para todas las variables kj asignando luego sucesivamente las cantidades enteras más grandes, a las variables en el orden descendente de sus relaciones hasta que se termine el recurso. (Este procedimiento realmente produce la solución óptima en el ejemplo1.1.2) desafortunadamente, esto no es cierto siempre, como lo muestra el siguiente contraejemplo:

Las relaciones para k1, k2, k3 son 1.7, 1.156 y 1.75. Ya que k2 tiene la relación más grande permisible por la restricción, o sea, k2 = [50/41] = 1. La cantidad restante del recurso es ahora 50 – 41 = 9, cantidad que no es suficiente para asignar ningún valor entero positivo a k1 o k3. Por consiguiente, la solución de ensayo es k1 = k3 = 0, y k2 = 1 con el valor de la función objetivo igual a 72. Este no es el óptimo ya que la solución factible (k1 = 1, k2 = 0, k3 = 2) proporciona un mejor valor de la función objetivo igual a 87.

Ejemplo 1.2-4 (Problema de confiabilidad)

Considere el diseño de un dispositivo electrónico que consta de tres componentes principales. Las tres componentes están dispuestas en serie de manara que la falla de una de ellas hará que falle todo el dispositivo. La confiabilidad (la probabilidad de que no haya ninguna falla) del dispositivo se puede mejorar a través de la instalación de unidades de reserva en cada componente. El diseño requiere de una o dos unidades de reserva, lo que significa que cada componente principal puede incluir hasta tres unidades en paralelo. El capital total disponible para el diseño del dispositivo es $10,000. Los datos de la confiabilidad Rj (kj) y el costo cj (kj) de la j-ésima componente ( j = 1, 2,3) dadas kj unidades en paralelo se resumen a continuación. El objetivo consiste en determinar el número de unidades paralelas, kj, en el componente j que maximizará la confiabilidad del dispositivo sin exceder el capital asignado.

Por definición la confiabilidad total R de un dispositivo de N componentes en serie y kj unidades en paralelo en la componente j ( j = 1,2,..., N) es el producto de las confiabilidades individuales. Por lo tanto, el problema se transforma en:

Donde C es el capital total disponible. (Nótese que la alternativa kj = 0 no tiene ningún significado en este problema).

El problema de confiabilidad es análogo al problema del presupuesto de capital con la excepción de que la función de rendimiento R es el producto, y no la suma, de los rendimientos de las componentes individuales. Por lo tanto, la ecuación recursiva está basada en la descomposición multiplicativa y no en la aditiva.

Los elementos del modelo de PD se definen de la siguiente manera.

 La etapa j representa la componente principal j.

 El estado yj es el capital total asignado a las componentes j, j + 1,..., N.

 La alternativa kj es el número de unidades paralelas asignadas a la componente principal j.

Sea fj (yj) la confiabilidad óptima total de las componentes j, j + 1,..., N, dado el capital yj.

Las ecuaciones recursivas se escriben como:

Como se vio antes, el número de operaciones de cálculo en la etapa j depende directamente del número de valores tomados para el estado yj. Aquí mostramos como podemos calcular límites más estrechos sobre los valores de yj.Comenzando con la etapa tres, ya que la componente principal 3 debe incluir cuando menos una unidad (en paralelo), vemos que y3 debe ser igual cuando menos a c3 (1) = 2. Por el mismo razonamiento y3 no puede exceder 10 – (3 + 1) = 6; de lo contrario el capital restante no será suficiente para proporcionar a las componentes principales 1 y 2 cuando menos una unidad (en paralelo) a cada una. Siguiendo el mismo razonamiento vemos que y2 = 5,6,..., o 9 y y1 = 6,7,..., o 10. (Verifíquese esto).

Etapa 3.

Etapa 2

Etapa 1

La solución óptima dado C = 10 es (k1, k 2 , k3) = (2, 1, 3) con R = 0.504.

Ejemplo 1.2-5

Supóngase que se agrega (en serie) una cuarta componente principal al dispositivo electrónico. Los costos y confiabilidades de utilizar una, dos o tres unidades en paralelo en la nueva componente son R4 (1) = 0.4, c4 (1) = 1; R4 (2) = 0.8, c4 (2) = 3; y R4 (3) = 0.95, c4 (3) = 7. Determine los límites sobre los valores de y4, y3, y2, y y1.

[Resp. 1 y4 4, 3 y3 6, 6 y2 9, 7 y1 10].

¿La definición de estado del inciso necesita (a) que se vuelvan a calcular las soluciones óptimas en todas las etapas?

[Resp. Sí, porque la etapa 4 de debe determinar primero, con lo cual se afectan los cálculos de las etapas 3, 2 y 1].

¿Puede usted obtener la solución óptima a todo el problema utilizando directamente las operaciones del cálculo dadas para las tres etapas?

[Resp. Sí pero esto requerirá

...