1.2 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

...