Consider a pair of symmetric dual problems.
maxZ=CX minW=Yb
cut down on
≤b YA≥C (P)s.t. (D)s.t
X≥0 Y≥0
Let b be the optimal basis of problem (p). According to the duality theory, the optimal value of its objective function is:
z * = CBB- 1b = Y * b = Y 1 * b 1+y2 * B2+……+yi * bi+……+ym * BM
When bi becomes bi+ 1 (other constants on the right remain unchanged, assuming that this change does not affect the optimal basis b), the optimal value of the objective function becomes:
z ' * = y 1 * b 1+y2 * B2+……+yi *(bi+ 1)+……+ym * BM
Then the change of the optimal value of the objective function is
*= Z'*—Z*= yi*
From the above formula, we can see the meaning of yi*, which represents the change of the optimal value of the objective function when the terminal constant bi increases by one unit. Z* = yi*？ Bi, that is, yi* represents the rate of change of Z* to Bi, that is, the shadow price of the ith constraint.
As can be seen from the above analysis, shadow price is the optimal solution of dual variables in the dual model of linear programming, so calculating shadow price can be transformed into finding the optimal solution of dual problem Y * = CB- 1, and the shadow price can be calculated and solved by the following methods:
(1) According to primitive simplex method, the solution of dual problem can be directly found.
(2) According to the dual simplex method, the solution of the dual problem can be found directly.
(3) Find the solution of the original problem first, and then find the solution of the dual problem according to the complementary relaxation theorem:-ax *) = 0.
—C) X*=0