Every primal linear programming has a dual problem. Consider the previous primal problem.
linear program
var
x1 "Galaxy bars (lots)"
x2 "Continental bars (lots)"
max
2 x1 + 3 x2 "profit ($)"
st
3 x1 + 1 x2 <= 18 "milk (tons)"
1 x1 + 2 x2 <= 12 "cocoa (tons)"
3 x1 + 3 x2 <= 21 "sugar (tons)"
end
The dual of this problem is as follows.
var
y1 "marginal value of milk"
y2 "marginal value of cocoa"
y3 "marginal value of sugar"
min
18 y1 + 12 y2 + 21 y3 "cost"
st
3 y1 + 1 y2 + 3 y3 >= 2 "profit of Galaxy bars (lot)"
1 y1 + 2 y2 + 3 y3 >= 3 "profit of Continental bars (lot)"
end
Note the following.
The objective of the primal is to maximize, the objective of the dual is to minimize.
The "<=" constraints in the primal are "<=" constraints in the dual.
The column and row coefficients in the primal constraints are transposed in the dual.
In intuitive terms, the primal approaches the optimum solution from one direction while the dual approaches the optimum solution from the other direction. It may be the case that one of them is easier to solve than the other. In this case, since the primal has only two variables, the primal can be easily solved graphically, while, since the dual has three variables, the dual is not easily solved graphically.
The output is as follows.
LPSolves (v0.1, 08-13-97)
Copyright (c) 1996 by Robin Snyder
File: F:\RLP\cbars-02.rlp
Time: 1997/11/24 at 08:42
Title: "Chocolate bars"
Author: "Robin Snyder"
Source: "Robin Snyder"
Variables:
1. y1 "marginal value of milk"
2. y2 "marginal value of cocoa"
3. y3 "marginal value of sugar"
Problem:
Minimize 18 y1 + 12 y2 + 21 y3 "cost"
Such that
3 y1 + y2 + 3 y3 >= 2 "profit of Galaxy bars (lot)"
y1 + 2 y2 + 3 y3 >= 3 "profit of Continental bars (lot)"
End
Phase 1:
A basic feasible solution has been found.
Phase 2:
R E S U L T S : (* = basis variable)
-------------
Objective coefficient ranges: (solution unchanged)
Coefficient Lower Current Upper
of variable limit value limit
----------- ----- ------- -----
y1 11 18 none marginal value of milk
*y2 8.5 12 14 marginal value of cocoa
*y3 18 21 25.2 marginal value of sugar
Solution (variable) results:
Reduced
Variable Value cost
-------- ----- -------
y1 0 7 marginal value of milk
*y2 1 0 marginal value of cocoa
*y3 0.333 0 marginal value of sugar
Shadow
Variable Value price
---------- ----- ------
_4 0 2 Surplus (profit of Galaxy bars (lot))
_5 0 5 Surplus (profit of Continental bars (lot))
Right hand side ranges: (solution unchanged)
Right side Lower Current Upper
constraint limit value limit
----------- ----- ------ -----
1. 1.5 2 3 profit of Galaxy bars (lot)
2. 2 3 4 profit of Continental bars (lot)
Objective (overall) result:
Objective Value
--------- -----
z 19 cost
