X

Table 7.1 Primal-dual table

Primal problem

Coefficient of x2 ■ ■ ■ xn

Right side

Dual problem

ym

a11 a12 ■ ■ ■ x1n a21 a22 ■ ■ ■ x2n am1 am2 ■ ■ ■ xmn

< bm

Coeffcients for objective function (minimise)

Right side

> C1 > C2 ■ ■ ■ > cn

Coefficients for objective function (maximise)

are optimal solutions for the primal and dual problems respectively, then:

In other words: the optimal values of the objective functions of the primal and dual problem are equal.

The optimal dual variables y* are called shadow prices, because the shadow price y* for resource i represents the (maximum) unit price you should be willing to pay to increase the allocation of that resource. The shadow price y* (i.e. the optimal value of a dual variable) indicates how much the objective function changes with a unit change in the associated right-hand-side constraint bi, provided the current optimal basis remains feasible.

The latter implies that the validity of dual values (shadow prices) is limited to a certain range. Outside that range the dual value itself will change as a result of a change to a different optimal solution or the problem will become infeasible.

A corollary of the Dual Theorem is the Theorem of Complementary Slackness: Let x* for j = 1,2,..., n and y* for i = l, 2,..., m be corresponding feasible solutions to the primal and dual problems respectively. Then both are optimal if and only if:

n y* ( E ajX* - bi ) = 0 for i = 1,2,..., m j=i and m x* ( E aijy*- Cj ) = 0 for j = 1,2 n i=1

This implies that whenever a constraint in one of the problems holds with strict inequality, so that there is slack in the constraint, the corresponding variable in the other problem equals zero. Or: if there is slack in a constraint, i.e. that constraint is not determinant for the optimal solution, the shadow price of that constraint is zero.

The concept of reduced cost is similar:

Let x* = 0, i.e. activity x* does not contribute to the optimal solution (for instance profit). The dual value of activity x* is then the rate of change in the objective function (for instance profit) if x* were forced into the solution, even though it is not optimal to do so.

Such dual value is called reduced cost because it represents the amount by which the cost cj of activity x* would have to be reduced in order to make it profitable to put it into the solution. If activity x* has a positive value, its dual value will always be zero.

Reduced costs also have a range of validity outside which the optimal solution changes or the problem becomes infeasible.

To summarise: the dual values provide a first indication of the sensitivity of the objective function to changes in the coefficients concerned. Shadow prices are related to the sensitivity of the objective function to the right-hand-side constraints bi . Reduced cost refers to the changes in the coefficients cj of the objective function required to force the associated activities into the optimal solution. For instance, in the case of the Open Design of an office, let xi, x2, x3 be the number of one-person, two-person, and three-person rooms respectively, with unit cost c1, c2, c3, and xi = 0 (no one-person rooms in the optimal solution). The reduced price of x1 then indicates how much the price of a one-person room c1 must be reduced to force x1 into the optimal solution, i.e. to make it worth having some one-person rooms in the office.

Decision variables xj having a value zero in the optimal solution are called non-basic variables. Decision variables xj having a non-zero value in the optimal solution - i.e. they form part of the optimal solution - are called basic variables. Reduced prices can be seen, therefore, as the amount by which the unit cost Cj has to be reduced to change a non-basic variable Xj = 0 in the optimal solution into a basic variable (Xj > 0 in the optimal solution).

The sensitivity of the objective function Z to changes in the coefficients Cj of the basic decision variables Xj follows from the definition of Cj: contribution to Z per unit of Xj. This is only true however, within a certain range. Outside that range the optimal solution will change, as we will explain for the manufacturing allocation problem with only two decision variables X1 and X2 (Figure 3.3).

The slope of the line representing the objective function Z = c1 x1 + c2x2 is determined by the coefficients c1 and c2, specifically by the ratio c1/c2. If we keep C2 constant, we can change the slope by changing C1 and vice versa. The line representing the objective function for the optimal solution (xj, xj) will then turn around the point (xj, xj), but no more than until a next corner-point feasible solution is reached. In Figure 3.3, turning anti-clockwise, that point will be the intersection of the lines a21 x1 + a22x2 = b2 and a31 x1 + a32x2 = b3. Turning clockwise it will be the point (b1 /a11,0). The range of validity for cj, therefore, indicates how much can be changed (keeping all other parameters the same) without affecting the optimal solution (xj, xj). The ranges of validity for the coefficients cj, of basic decision variables are computed in the Simplex procedure when moving, systematically, from one corner-point feasible solution to a better one until no better one can be found.

Systematic sensitivity analysis related to the coefficients aij of the matrix is rarely used in Open Design practice. Usually, the expert knowledge of the open designer allows him to identify intuitively the few of these coefficients which might have a large impact on the objective function and could be changed to a certain degree. He can then simply verify his ideas by pilot runs with varying values for the coefficients concerned.

We will now describe how shadow prices are used to arrive at a solution at all, i.e. how to come from a zero to a positive solution space.

This involves two steps:

Step 1: modify the model by alleviating all (inequality) constraints bi until an optimal solution is achieved;

Step 2: tighten the constraints as much as possible whilst maintaining a positive solution space.

In its simplest form, Step 1, modification until an optimal solution is reached, goes as follows:

Recall that objective function Z is financial return; all stakeholders' wishes are expressed in the constraints bi. We start by alleviating all (inequality) constraints bi with the same fraction p.

So we can write:

subject to n

We then run several pilots for various values of p between 0 (no alleviation) and 1 (100% alleviation). The resulting p-value is used as starting point for Step 2.

If we wish to establish the alleviation (in all inequality constraints) more precisely, we can let the model itself provide the alleviation (p-value) which is just enough to make the solution space positive. To distinguish it from the previous one, we will denote it with a capital P. We make P endogenous:

subject to n

Of course, if P = 0, then no solution is found.

Since we wish to find the lowest possible value for P, we choose an arbitrary but high value for its coefficient Cp in the objective function (in other words: we make the unit cost of P high). With the resulting P-value, we proceed to Step 2.

The first pilot run, with the alleviation (p- or P-value) found in Step 1, provides us with the slaCk variables of the non-basic variables (the decision variables Xj not contributing to the optimal solution); the slaCk variables indicate how much the non-basic variables Xj can be increased without affecting the optimal solution.

Step 2, modification by changing the constraints as much as possible to their original values whilst maintaining a positive solution space, implies that we reduce each constraint bi to:

• either its original value;

• or until its slack variable becomes zero.

With these constraints b (i = 1,2,..., m) we can calculate shadow prices yi (i = 1,2,..., m) and their ranges of validity.

This information completes our search for crucial stakeholders, i.e. the stakeholders who will have to alleviate their constraints to make a solution possible at all.

At this point we also have a first estimate of the extent to which they will have to give in from their ideal values and what effect this will have on the objective function (shadow prices).

What we do not know at this stage is:

• To what extent each stakeholder will be prepared to give in: how lenient or stubborn he or she will be;

• How a compromise made with one crucial stakeholder will affect the required combined compromises with all the others.

This is the subject of the next section.

Real Estate Essentials

Real Estate Essentials

Tap into the secrets of the top investors… Discover The Untold Real Estate Investing Secrets Used By The World’s Top Millionaires To Generate Massive Amounts Of Passive Incomes To Feed Their Families For Decades! Finally You Can Fully Equip Yourself With These “Must Have” Investing Tools For Creating Financial Freedom And Living A Life Of Luxury!

Get My Free Ebook


Post a comment