R76197

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 quese 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 sedefina. 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 puedetenerse 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 elmé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 deprogramació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 puedeser 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 delcapital.
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 modelodel 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...