In all the DP models we presented, the state at any stage is represented by a single element.

**PROBLEM OF DIMENSIONALITY**

In all the DP models we presented, the *state* at any stage is represented by a single element. For example,
in the knapsack model (Section 10.3.1), the only restriction is the weight of
the item. More realistically, the volume of the knapsack may also be another
viable restriction. In such a case, the *state*
at any stage is said to be two-dimensional because it consists of two elements:
weight and volume.

The increase in the number of state variables increases the computations
at each stage. This is particularly clear in DP tabular computations because
the number of rows in each tableau corresponds to all possible combinations of
state variables.

This computational difficulty is sometimes referred to in the literature
as the **curse of dimensionality**.

The following example is chosen to demonstrate the *problem of dimensionality.* It also
serves to show the relationship between linear and dynamic programming.

**Example 10.4-1**

Acme
Manufacturing produces two products. The daily capacity of the manufacturing
process is 430 minutes. Product 1 requires 2 minutes per unit, and product 2
requires 1 minute per unit. There is no limit on the amount produced of product
1, but the maximum daily demand for product 2 is 230 units. The unit profit of
product 1 is $2 and that of product 2 is $5. Find the optimal solution by DP.

The
problem is represented by the following linear program:

The
elements of the DP model are

*1. **Stage i *corresponds to product* i, *i* *=* *1,* *2.

*2. **Alternative **x _{i}*

*3. **State (v _{2}, *w

*4. **State **(v _{1}*

**Stage 2. **Define *f*_{2}(v_{2},w_{2}) as the
maximum profit for stage 2 (product 2), given the state *(v _{2},*w

The
optimization of stage 1 requires
the solution of a (generally difficult) minimax problem. For the present
problem, we set *v _{1}* = 430 and w

You can
verify graphically that the optimum value of f* _{1}*
(430,230) occurs at x

2. In the
*n-item* knapsack problem of Example
10.3-1, suppose that the weight and volume limitations are Wand *V,*
respectively. Given that *w _{i},*
v

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Operations Research: An Introduction : Deterministic Dynamic Programming : Problem of Dimensionality- Dynamic Programming |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.