Dear Parag

1. The dual values or shadow prices produced by solving the dual equation set that you display, are values for the constraints and they have the same units as the objective function. However, you don’t need to solve the dual, since once you solve the primal problem you also get the dual values.

2. For a certain constraint, say ‘Inspection capacity’ its dual value indicates how much will the objective function increase when this capacity is incremented in one unit.

Let’s see:

The solution to your primal problem is x1 = 933 units an x2 = 133 units with a Z=  $346,667.

The respective shadow prices are only for constraints ‘Soldering capacity’ and ‘Assembly capacity’ which respective values are: u2= 233.33 and u3 = 33.33. The other restrictions don’t have shadow prices and thus don’t play any role for this objective. Therefore, these are the only two restrictions or criteria you are interested on.

Consequently, if you increment one unit the soldering capacity from 1200 to 1201, the functional Z will increase as Z + u2 = 346,667 + 233= $346,900 (rounding).

If you further increment in one unit the assembly capacity from 2000 to 2001, the functional Z will increase as Z + u3 = 346,900 + 33 = $346,933.

I did this by each constraint but you can increment both criteria simultaneously and get the same results.

Now, how much can you increment the soldering capacity? Indefinitely?

No, you can increment its capacity up to a certain limit, and the same for the assembly capacity. These limits are given automatically by the LP software.

Within these limits the increase of Z is constant and equal to the respective shadow price or to their sum, that is, it is a straight line with the same slope for different increments, and you can also have it graphically displayed.

If you increment either of both criteria past their respective limits, then, one of these criteria or may be both will be no longer significant and other will take their place.

The increase of the objective function will then change and it will be a curve instead of a straight line, because the slope changed since you have now a new shadow price corresponding to the new criterion.

3. Why can’t the objective function be minimized?

Of course it can!

If instead of profits you put costs as Z coefficients, they will be minimized.

The same concept as explained holds. The only difference is that a unit increment of the corresponding criterion will decrease the Z function value, which is what you want.  If instead of incrementing one unit you decrement one unit, the same holds, and Z will increase.

4. I don’t understand your last paragraph. If you consider costs, your objective function must be minimized and not maximized as you imply with your ‘OK’ .

In addition, in your example, constraints are not related with profits and costs; they are only related to the available existing capacities.

Suppose that you want to minimize your cost. You can do that, however, because in your example all criteria call for maximization the minimum cost of the solutions polygon will be 0, that is, no solution. You can see this graphically and very easily since you have only two products. You will see that the minimum point of the polygon that the Z can tangent is the origin of coordinates, or zero.

In you example  you can change it by changing one of the criterion to a minimum, say for instance  ‘Inspection capacity’ and you also have to reduce  the availability, for instance  to 3000 from 5000. In that case the optimal solution is to produce 600 units of  x2, and zero units of x1.

5. I don’t know which LP software you are using but I recommend SOLVER that is an Excel Add in. There you will see that you can choose maximise or minimize the objective function and even equalizing it.

I believe that you are confused regarding criteria and objectives.

You can have a criterion calling for maximization of your costs and another for maximization for your profits, but in this case the objective function must call for maximization or minimization for something different, for instance ‘Inspection capacity’.

If my explanation does not satisfy you for whatever reasons, just write me in RG or privately to [email protected]. I will be very happy to help is I can.

Shadow price is an indication of the worth of the respective resource , when that resource is FULLY utilized 

In this case, the molding capacity is UNDERUTILIZED. Hence the shadow price is Zero (u1=0) whereas the shadow price of second constraint(Soldering resource)  is 233.33 meaning that the soldering constraint is FULLY UTILIZED and if one unit of that resource is increased, the profit is going to increase by 233.33 units !

Dear Deshmukh

You are absolutely correct and for that reason I said that only two criteria,, those with shadow prices, need to be considered in this example..

As you said, shadow prices are an indication of the worth of rthe respective resourcfe.

I use them in SIMUS / IOSA  MCDM model for sensitivity analysis and thus working with real values , instead of  employing arbitrary criteria weights as done today, which are completely irrelevant for this analysis

Thank you so much Prof. Munier for your nice and valuable explanation. Actually, I would like to ask what is meant by u? Is it cost of operation/hr/unit or profit of operation/hr/unit?

If I consider cost of operation/hr/product, then the objective function is ok because the we want to minimize the cost in dual version. But if we look at the constraints, then for each product the cost should be greater than 300 or 500. But in the question 300 or 500 is treated as profit, not cost.

Again if I consider u is profit of operation/hr/product, then the constraints are ok as we want at least a profit of 300 or 500. But the objective function becomes minimizing the profit. But profit cannot be minimized. 

So, how the dual problem should be formed? Is it based on some 'renting concept' of the available resources?

Dear Parag

Since matrix operations don't show well in RG screen, please  access  the attached file

I hope it helps

Parag - The extensive answers provided are great, but you still asked afterwards "what is meant by u? Is it cost of operation/hr/unit or profit of operation/hr/unit?" and I wanted to tackle that directly. There is one ui for each constraint of the primal model (model in the xj variables). The ui are "the change in the objective function given a one-unit change in the right-hand-side for that constraint". So, since your primal model objective is to maximize "profit", the ui must be the profit change per one-unit change in the right-hand-side. Good luck. David....

Dear David

I wish I could explain this subject in very simple ways as you do.

Thanks to all as I was wandering to understand the concept of "Shadow price". Now, I got it.

The answers you already got are great. I only want to give you an example of the usefullness of the dual variables related to more complex problems. I am used to play with logistics networks optimization and transportation problems such as goods production and distribution problems, in which you may have dozens of constraints related to factories and distribution centers (DC) capacities. You usually want to minimize the total cost of distribution of the goods produced in a certain period of time. Once you get the solution, suppose several DCs had their capacities reached. The dual variables related to each of these DC capacity constraint will show you which DC can provide you the best reduction in the objective function if you increase its capacity by one unit. So,in practice, you are directed to increase the capacity of that particular DC. The issue is that the dual variable gives you the improvement value in the objective function for the increase of only one unit of capacity of that DC. In general,  the behaviour of the cost curves do not guarantee you that by increasing the DC capacity of more than one unit, that the DC will remain as the best one to have its capacity increased. So, you need further analyses. But it at least directs you to increase the capacity of that DC at first and a possibility is to increase the DC capacity by a certain amount feasible in practice, to run the problem again and to compare the dual variables again. But, without the values of  the dual variables, you do not have a clear direction on how to improve the solution you get.

Dear Nicolau

Nicolau. The dual variables related to each of these DC capacity constraint will show you which DC can provide you the best reduction in the objective function if you increase its capacity by one unit.

NM. This is correct, but I think that it is worth to mention, just for the reader’s sake, that it does not apply to any constraint, only to those that have shadow prices. Incrementing or decrementing  the capacity of the other constraints does not have any effect in the objective function.

Nicolau. So,in practice, you are directed to increase the capacity of that particular DC. The issue is that the dual variable gives you the improvement value in the objective function for the increase of only one unit of capacity of that DC.

NM. And very important, you know exactly with what criteria to work with!

Not using criteria weights as done now!

Nicolau. In general,  the behaviour of the cost curves do not guarantee you that by increasing the DC capacity of more than one unit, that the DC will remain as the best one to have its capacity increased. So, you need further analyses.  

NM. This is also right;  you can’t Increase or decrease the DC or criterion  indefinitely because its corresponding shadow price has a lower and a higher limit, not necessarily symmetric, and it could even be, that the DC does not allow even for a one unit increment or decrement.  This  informs the DM about the criticality of a criterion..

When these limits are exceeded your DC ceases to be the best and another DC takes its place.

Because the increase/decrease of the objective function is constant and equal to the shadow price, this is only true when the increments are within the variation range of the shadow price. This information is also given by the model. For this reason, when the criteria capacity is incremented more that the maximum or decremented  less that the minimum, the objective function curve is no longer a straight line but a curve.

Nicolau But it at least directs you to increase the capacity of that DC at first and a possibility is to increase the DC capacity by a certain amount feasible in practice, to run the problem again and to compare the dual variables again. But, without the values of the dual variables, you do not have a clear direction on how to improve the solution you get.

NM. Exactly, and this is the reason by which sensitivity analysis should be performed by considering shadow prices instead of using criteria arbitrary weights, as done today, which are completely irrelevant and don’t provide reliable results.

But to do this, you must use Linear Programming since as far as I know no MCDM method produce those shadow prices, but Linear Programming. The SIMUS / IOSA method for MCDM is based on Linear Programming and works under this principle and generates the objective function curves.

Your excellent explanation will allow many people to understand the role and utility of the dual variables.

I wish we could get more questions as those produced by  Parag.

Dear Parag,

Yes cost (minimizing) and profit (maximizing) is a specific operation for LPP duel formulation.

The Duality in Linear Programming states that every linear programming problem has another linear programming problem related to it and thus can be derived from it. The original linear programming problem is called “Primal,” while the derived linear problem is called “Dual.” Duality in linear programming is essentially a unifying theory that develops the relationships between a given linear program and another related linear program stated in terms of variables with this shadow-price interpretation. The importance of duality is twofold. complementary slackness, duel simplex method, primal –duel mathematics, mathematics economics, game theory are the important topics where duality associate with problems and solution can be handled using minimize and maximize model. By generalization, problem can be defined with maximize and minimize constraint. Weak duality, optimality, unboundness and strong duality feasibility study is also important part of duality study and optimal solution can be found using matrix operation.

In linear programming problems the shadow price of a constraint is the difference between the optimized value of the objective function and the value of the objective function, evaluated at the optional basis, when the right hand side (RHS) of a constraint is increased by one unit. A shadow price value is associated with each constraint of the model. It is the instantaneous change in the objective value of the optimal solution obtained by changing the right hand side constraint by one unit. A reduced cost value is associated with each variable of the model.If some shadow price is positive, then the corresponding constraint must hold with equality. If a constraint of the primal is not binding, then its corresponding shadow price must be zero.

A factor that is expected to be in short supply should have a shadow price higher than its market price, while a surplus factor should have a lower shadow price than its market price. Thus the shadow price is the price which would prevail if prices were equilibrium prices. The shadow price of a given constraint can be interpreted as the rate of improvement in the optimal objective function value, (e.g., Z in maximizing profit or C in minimizing cost) as RHS of that constraint increases with all other data held fixed. The sensitivity is calculated by dividing the percentage change in output by the percentage change in input. One dimensional sensitivity analysis is possible in excel.

An example of a commodity requiring shadow pricing might be the value of a park to the social well-being of a community when calculating the cost of a construction project. By assigning a numerical dollar value to the park, analysts can evaluate its value to a community with regard to the costs of new construction. In general a Shadow Price equaling zero means that a change in the parameter representing the right-hand side of such constraint (in an interval that maintains the geometry of the problem) does not have an impact on the optimal value of the problem.

Hope you like it.

Ashish

Dear Parang

I can't find the place where yesterday you asked a question and an example about dual values in Linear Programming. Fortunately I copied you request and answered it.

Since I used some tables that don't reproduce well in RG, please access the file below

Dear David

I want to make a correction.

There is not a dual value for each constraint.

Dual values appear only for those constraints that are binding, that is, which are responsible for the solution. For all others, the dual value is zero

.

.

Dear Nolberto Munier and Mubashar Shah,

I want to correct Nolberto’s constraint statement regarding the duel LP.

Each variable in the primal LP becomes a constraint in the dual LP; each constraint in the primal LP becomes a variable in the dual LP; and hence the objective direction is inversed – maximum in the primal becomes minimum in the dual and vice-versa.

A linear programming problem may be defined as the problem of maximizing or minimizing a linear function subject to linear constraints. The constraints may be equalities or inequalities.The function to be maximized (or minimized) is called the objective function.

A shadow price value is associated with each constraint of the model. It is the instantaneous change in the objective value of the optimal solution obtained by changing the right hand side constraint by one unit. A reduced cost value is can be associated with each variable of the model. If some shadow price is positive, and then the corresponding constraint must hold with equality. If a constraint of the primal is not binding, then its corresponding shadow price must be zero.Model can not be validated without constraint in duel LP.

In general a Shadow Price equaling zero means that a change in the parameter representing the right-hand side of such constraint (in an interval that maintains the geometry of the problem) does not have an impact on the optimal value of the problem.

I have enlightened constraint theme well in my first answer statement .

Hope it help you out.

Ashish

Dear Ashish

Please see my answer in the attached file