Optimal allocations in Excel

Optimal allocations

Solving an optimal allocation consists of calculating how much each process must operate so that the system achieves the greatest possible magnitude of the objective.

For an introduction to optimal allocations, see Chapter 17 of Notes on the Structure and Evolution of Societies.

We call feasible allocations those in which, for all materials throughout the analysis period, the quantities consumed do not exceed those available, for example, because they have been produced since the previous moment.

We call optimal allocations those feasible allocations for which a certain function, called the objective function, is maximized. Here, "optimal" does not mean "good," but simply that something is maximized.

An optimal allocation is a constrained maximization problem, where we look for the variables that, while satisfying the constraints that determine whether an allocation is feasible, achieve the greatest possible objective.

For this problem to have a solution, certain maximum conditions must be met, involving auxiliary variables called Lagrange multipliers. In economics, Lagrange multipliers can be interpreted as values, and the maximum conditions as accounting.

MLTB

MLTB is the optimal allocation where the objective is to Maximize Long-Term Benefit. Solving for MLTB involves calculating the intensities (the number of times) with which the production processes must operate so that the profit at the end of the analysis period is as high as possible.

MLTB is a type of optimal allocation, the Von Neumann model is a special case of MLTB when the system evolves exponentially, and the Leontief or Sraffa equations are a special case of Von Neumann. In MLTB the system changes over time, while in the Von Neumann model only one instant in time is studied because the system grows exponentially.

Example: calculating MLTB in our simulation

Suppose we seek to solve MLTB with the data from our simulation in Capital: An Experiment.

In our case, throughout the analysis period, we have the three processes of the Capital experiment: the first process uses 280 arrobas of wheat and 12 tons of iron as inputs to produce 575 arrobas of wheat; The second process consumes 120 arrobas of wheat and 8 tons of iron to produce 20 tons of iron; the third process consumes a certain amount of wheat and iron and produces half that amount. As explained in the presentation, this third process can be described in the matrices of inputs A and outputs B as two processes, so we have a total of four processes in the matrices. The outputs are obtained at a time after the inputs are consumed.

We wrote our simulation problem in spreadsheets, with 4 processes and 2 materials per time step, and with inputs as negative numbers and outputs as positive numbers. We ordered the processes and materials so that the first processes and materials refer to the initial instant, the next to the following instant, and so on, following a diagonal structure to link consumption at one instant with production at the previous instant, across 14 time steps.

We start with 1000 arrobas of wheat and 1000 tons of iron at the initial time, which we write in the first two elements of D.

The objective is the weighted production at the final time, which we write in the last four elements of C, where we have used the prices from the Von Neumann model to weight the production.

(In our example, the processes don't change over time, but we can pose other problems where they do. Also with objectives at C that differ from the final profit, or with flows at D that occur at different times than the initial.)

Instructions for solving an optimal allocation in Excel

We will follow these steps:

1. We will check that our Excel has the Solver add-in loaded. Solver is available in all versions of Excel under Windows or Mac, but it must be loaded to be used.

2. Open the Capitalaoprimal.xls file and you will see a spreadsheet (with the simulation data already incorporated).

If a message similar to "Be careful: files from the Internet can contain viruses. Unless you need to edit, it's safer to stay in Protected View" appears, click the “Enable Editing” button.

3. Adjust the number of rows to the number of processes and the number of columns to the number of materials in the problem. (It's already adjusted on our sheet)

The spreadsheet originally shows 56 processes or rows, and 28 materials or columns. To delete a column, right-click (on Windows; on Mac, hold down the CTRL key and click) in the cell with the column name and select "Delete" from the context menu. You can select multiple columns to delete them at once. To add a column, right-click on any column name, for example, column E, select "Copy" from the context menu, right-click again on the column name E, and select "Insert Copied Cells" from the context menu. The same procedure applies to rows.

4. Enter the problem data in the yellow cells, the flows of the processes in F, with the consumptions with a negative sign and the products with a positive sign, the objective in C, and the materials incorporated or extracted in D.

5. Click on “Solver”. In modern versions of Excel, you will find it on the “Data” tab as an icon on the right, and in Excel 2004 and earlier versions as an option in the “Tools” menu. A dialog box will appear, whose parameters we do not need to define or modify,

and we will click on the “Solve” button.

6. If Solver has found a solution, a dialog box will appear.

We will click the “Ok” button.

The blue cells tell us about the solution to the problem, about the intensities X with which the processes operate over time: at the first instant the intensities are 3.57, 0.00, 0.00 and 957.14; at the second instant 7.00, 0.79, 0.00 and 388.31; etc.

The green cells indicate that the constraints are met; if any constraint were not met (for the predefined margin of 0.000001) it would appear in red.

Advanced Instructions

Accounting and Values

If before clicking "Ok" we click on "Sensitivity",

We can access this report in the tabs below:

In the table above, under the "Final Value" label, we can see the magnitudes of the intensities, and under the "Reduced Cost" label, the accounting balances of the processes: zero for processes that are operating and non-positive for those that are not.

In the table below

Under the label "Final Value" we can consult the magnitudes of the material balances, and under the label "Shadow Price" the values (with the sign changed) of the materials over time: in the first instant, 53.51254216 for wheat and 50.84902196 for iron; in the second instant, 27.11947838 for wheat and 101.6980439 for iron; etc.

Duality

In the linear case, the problem of solving an optimal allocation results in a linear program. We can formulate the following equivalent problems, following the same instructions:

An allocation problem, which we call primal: calculate the intensities that, while satisfying the material balances, achieve the greatest magnitude of the objective in C; it can be solved with aoprimal.xls.

The blue cells represent the variables, the intensities of the processes; the green cells represent the constraints, the material balances. The Lagrange multipliers are the values of the materials, and the maximum conditions are the accounting balances.

A valuation problem, which we call dual: calculate the values that, while satisfying the accounting balances, achieve the lowest value of the endowments in D; aodual.xls can be used.

The blue cells represent the variables, the values of the materials; the green cells represent the constraints, the accounting balances. The Lagrange multipliers are the intensities of the processes, and the minimum conditions are the material balances.

A joint allocation and valuation problem, which we call primaldual: calculate the intensities and values that satisfy the material and accounting balances, as well as the complementary slacks; it is available in aoprimaldual.xls

Variables, intensities X and values Y, are shown in blue; constraints, material balances D + X F and accounting balances C + F Y, are shown in green. Complementary slacks are also shown, which should be satisfied for the problem to have a solution, but which have not been included among the conditions that Solver must meet to make it easier to find the solution (including them would make it a non-linear problem). If we write a potential solution in the blue cells of this sheet and no cell shows red color, then it is indeed a solution.

These sheets include the problem in its standard form, where material balances are written as equalities, D + X F = 0, and prices can have any sign. The sheets can also be used for the canonical form, where material balances are written as D + X F ≥ 0 and prices must be non-negative, with aocanonicaprimal.xls, aocanonicadual.xls and aocanonicaprimaldual.xls.

MLTB duals with the simulation are in Capitalaodual.xls and Capitalaoprimaldual.xls.

Español – Home / Algorithms in Excel