Resources Data

 Dynamic Programming Data - Resources: Data

The problem addressed in this section is the allocation of scarce resources to alternative activities. The problem is often used as an introduction to dynamic programming. The resources problem, as this is page is written, is only available for the deterministic dynamic programming, DDP. As often is true for DDP models, there is a math programming model that more effectively solves the linear version of this problem. We describe the math programming model below. The amounts of left over resources are modeled explicitly so that resources not used in the allocation can be given a nonzero value.

Written as a mathematical program, the resource problem is:

This is the linear version of the problem that for most instances is easily solved by math programming solution techniques. The add-in creates a DP version of the problem. It can handle separable nonlinear as well as linear models

Data for the Resource Model

 We create the model by choosing Data from the DP Data menu. The model selection dialog is presented. Here we consider the Resource problem with a deterministic DP model. When this page is written, only the DDP model is available.

 Fill the name field with a short name with no spaces or punctuation. The name, number of items, and number of resources are fixed once the worksheet is created. The maximum of each item can be changed on the data worksheet. By checking the Make Random Problem box, the model parameters are assigned randomly. The Maximize Objective button determines the direction of optimization.
The data form is below. The yellow cells should not be changed. The white cells can be changed to reflect the current problem. The data shown was randomly generated using a fixed seed. This example has only one resource and four items.

Clicking the Build Model button on the top of the data worksheet, calls the DP Models add-in to construct the model worksheet. The Build/Modify Model button also constructs the model worksheet, but first presents the Model dialog. This allows the model parameters to be modified by the user.

Clicking the Build Data Table button constructs tables for the revenue and resource use data. This allows the representation of nonlinear forms.

The Math Programming Model

The math programming model is shown below as constructed by the Math Programming add-in. Although the problem has only one constraint, the default minimum for the add-in is two constraints. The second dummy constraint is not restricting. The model has four integer variables representing allocation amounts. The fifth variable is the unused resource.

The optimum solution two units of item 2 and one unit of item 4. The objective is 28 and all the resource is used.

The Table Option

A two constraint data table is below with data provided by random integer values.

 Clicking the Build Data Table button calls the add-in to make tables for benefits and resource use as a function of the number of items selected. The tables take data from the linear data table for the first item. The second item terms of the table are 2 times the first item value. Thus, the original table values represent the linear problem. The values in the table can be changed however, to show any separable nonlinear function of the number of items. Since the DP algorithms enumerate all possible solutions, the linearity of the revenue or resource usage terms has no affect on the model.

The math programming model for the two constraint linear problem is shown below. The solution uses two of item 2. The remainder of the resources (22 and 17) is left over. Apparently, the values of assigning the resources to one of the remaining alternatives is not justified.

The DP model and solution are described on the next page.

Operations Research Models and Methods
Internet
by Paul A. Jensen