一、对偶问题
1、经济含义
考虑线性规划问题
在这个最大化问题中，当资源i增加一个单位（即资源i的资源限量从bi增加到bi+1)而其他资源都不变时，所引起的目标函数最优值增加的量则称为资源i的影子价格（shadow price）。
资源i的影子价格实际上就是资源i的边际利润。影子价格越大，说明这种资源相对紧缺；影子价格越小，说明这种资源相对不紧缺；如果最优生产计划下的某种资源有剩余，那么这种资源的影子价格一定等于0。
企业A生产书架、桌子和椅子三种产品，拥有48m³木材，20h制造工时，8h测试工时三项资源。已知：
书架售价60元，生产一个书架需要8单位木材、4单位制造工时和2单位测试工时；
桌子售价30元，生产一张桌子需要6单位木材、2单位制造工时和1.5单位测试工时；
椅子售价20元，生产一把椅子需要1单位木材、1.5单位制造工时和0.5单位测试工时；
求三种产品各生产多少数量时，企业A能够最大化总收入。
显然，原问题的线性规划为：
如果企业B想要收购木材、制造工时、测试工时这三样资源，就必须为每项资源报价，并且满足企业A愿意出让资源的条件，即让企业A获得不低于自己制造产品的收入。
求三项资源的单位报价各为多少时，企业B能够最小化总成本。
那么，可以写出对偶问题的线性规划是：
上面的例子，旨在从实际经济问题的角度解释「每一个线性规划问题都存在一个与其对偶的问题」这句话的合理性。后面的章节中我们会进一步阐述两个问题的解如何对应，也就是，如果我们计算出了对偶问题的最优解，如何用它推算出原问题的最优解。
2、一个SAS代码例子
我们可以不用写出对偶问题的形式，直接调用模块进行对偶问题的求解，以一个sas程序例子为例：
利用sas代码求解如下：
在上述代码中，使用CON语句进行约束条件声明的时候，分别给工时、原材料、甲产品的最小生产量、甲产品的市场需求及乙产品的市场需求等五个约束条件命名为time、resource、demand1、demand2和demand3，因此在输出影子价格时，就可以直接使用time.dual、resource.dual、demand1.dual、demand2.dual和demand3.dual。
选项SOLVER=DS指定使用对偶单纯形法对该线性规划问题进行求解，输出如图所示
从输出结果看，
- 该LP问题调用对偶单纯形法求解，经过4次迭代后达到最优，每周生产下x1=6件甲产品和x2=28件乙产品时，可以获得最大利润4320元。
- 工时约束的影子价格为120元，表示如果每周生产工时从40个小时提高到41个小时，该作坊的总利润将提高120元。
- 原材料的影子价格为0，说明原材料仍有剩余（6+1.5*28<50）。
- 甲产品和乙产品的最大需求的影子价格也是0，这表明就目前的生产状况而言，该作坊若拓展甲产品和乙产品的销售市场是没有意义的，不能给作坊带来更多的利润。
- 但是甲产品的最小需求量的影子价格为-80元，是一个负数，这是因为该约束不等式为(x1>=6)，若将该约束的右端项增加1，即约束不等式变为x1>=7，那么最大利润将减少80元。多生产1件甲产品资源够但是工时得+2h，工时影子价格120*2=240元，甲产品利润160元，160-240=-80元。
3、数学含义
从数学角度，对偶问题可以被理解为寻找原问题目标函数上界（或下界）的问题。
以原问题是求目标函数最大化为例，我们以向量形式写线性规划：
那么，最小的上界就是原问题目标函数的最优值。在所有的上界中，我们要找到最小的那一个，这个问题表述出来就是
可以发现，这就是对偶问题的形式。
反之，如果原问题是求目标函数最小化，那么对偶问题就是在寻找原问题目标函数的下界。这张图可以帮助理解：
在图中，26是目标函数最优值，两个问题分别从左右两侧逼近最优值。
4、结合两个含义
简单结合两个角度的解释。
也就是说，在这个例子里，对偶问题的任意一个可行解，都是原问题的一个上界。因为企业B用这组报价可以买到资源，所以企业A制造产品的收入不可能高于这组报价对应的成本。
当我们找到企业B所有报价里总成本最低的那一组，就是企业A能获得的总收入的最大值，是原问题的最优解。
这是一个在教材上被广泛使用的解释：如果原问题是企业A拥有m种资源（有m个约束），计划生产n种产品（有n个变量），目标是最大化总收入；那么对偶问题就是，企业B想要收购这些资源，需要确定m种资源的报价（有m个变量），目标是最小化总成本，但企业A只有在卖资源的收益不低于卖产品的时候才会同意卖资源（n个约束）。或者说，买资源的成本不低于卖产品的售价（见1、经济含义）
二、pyomo对偶问题实践
1、原问题
生产X、Y两种产品，需要原材料和两个工人A、B的工时的工时如下：需要最多40单位X产品，售价270刀，1单位X产品需要100刀原材料和A工人1小时（80小时限制，每小时50刀）和B工人2小时，也就是说X产品利润40刀。
model = ConcreteModel()
# declare decision variables
model.x = Var(domain=NonNegativeReals)
model.y = Var(domain=NonNegativeReals)
# declare objective
model.profit = Objective(
expr = 40*model.x + 30*model.y,
sense = maximize)
# declare constraints
model.demand = Constraint(expr = model.x <= 40) # 最多需要40单位X
model.laborA = Constraint(expr = model.x + model.y <= 80) # A工人最多80h
model.laborB = Constraint(expr = 2*model.x + model.y <= 100)
# solve
SolverFactory('glpk', executable='/usr/bin/glpsol').solve(model).write()
# display solution
print("Profit = ", model.profit())
print("Units of X = ", model.x())
print("Units of Y = ", model.y())
'''
#最终结果：
Profit = 2600.0
Units of X = 20.0
Units of Y = 60.0
'''2、规划问题可视化
figure(figsize=(6,6))
subplot(111, aspect='equal')
axis([0,100,0,100])
xlabel('Production Qty X')
ylabel('Production Qty Y')
# Labor A constraint
x = array([0,80])
y = 80 - x
plot(x,y,'r',lw=2)
fill_between([0,80,100],[80,0,0],[100,100,100],color='r',alpha=0.15)
# Labor B constraint
x = array([0,50])
y = 100 - 2*x
plot(x,y,'b',lw=2)
fill_between([0,50,100],[100,0,0],[100,100,100],color='b',alpha=0.15)
# Demand constraint
plot([40,40],[0,100],'g',lw=2)
fill_between([40,100],[0,0],[100,100],color='g',alpha=0.15)
legend(['Labor A Constraint','Labor B Constraint','Demand Constraint'])
# Contours of constant profit
x = array([0,100])
for p in linspace(0,3600,10):
y = (p - 40*x)/30
plot(x,y,'y--')
# Optimum
plot(20,60,'r.',ms=20)
annotate('Mixed Product Strategy', xy=(20,60), xytext=(50,70),
arrowprops=dict(shrink=.1,width=1,headwidth=5))
plot(0,80,'b.',ms=20)
annotate('Y Only', xy=(0,80), xytext=(20,90),
arrowprops=dict(shrink=0.1,width=1,headwidth=5))
plot(40,0,'b.',ms=20)
annotate('X Only', xy=(40,0), xytext=(70,20),
arrowprops=dict(shrink=0.1,width=1,headwidth=5))
text(4,23,'Increasing Profit')
annotate('', xy=(20,15), xytext=(0,0),
arrowprops=dict(width=0.5,headwidth=5))
fname = 'LPprog01.png'
fname = os.path.join('figures', fname) if os.path.exists('figures') else fname
savefig(fname, bbox_inches='tight')
3、对偶问题
str = " {0:7.2f} {1:7.2f} {2:7.2f} {3:7.2f}"
print("Constraint value lslack uslack dual")
for c in [model.demand,model.laborA,model.laborB]:
print(c, str.format(c(), c.lslack(), c.uslack(), model.dual[c]))
- 对于n个决策，您应该期望找到n个“活动”约束。
- 每个非活动约束都有一个相关的“松弛变量”。实际意义中可理解松弛变量为没有被利用的资源，当然其利润为零，故在目标函数中系数为零。这里就是产品的demand。
- 每个活动约束都有一个相关的“影子价格”。这是额外资源的附加价值。这里就是工人A和工人B。
参考
【1】经济含义和数学含义：https://www.zhihu.com/question/26658861/answer/631753103