线性规划这一类问题求解完成之后,光看最后给出的目标值,还有每个变量具体取了多少,往往还不能说就把模型里的信息全弄清楚了。很多做模型分析的人都会关心两件事:一个是到底怎么把每个约束条件对应的对偶值给找出来,另一个就是当这些对偶值发生变化的时候,背后说明的是什么经济学或者业务上的道理。在CPLEX提供的文档里,对偶值有时候也会被直接叫做影子价格,而且可以通过内置的命令或者编程接口,把每个约束条件后面的那个对偶值读出来进一步分析。
一、在CPLEX里怎样查看对偶值
对偶值这个指标,主要是在线性规划模型或者说连续松弛的情况下才有比较直观的解释意义。模型需要已经被求解器成功算过一遍,并且确实存在一个可以用的最优解。如果当前跑的是一个整数规划模型,那么在没有经过特殊处理的情况下,直接去看对偶值往往没有太大参考价值,因为整数解并不一定对应着对偶意义上的那套价格。所以第一步最好先确认一下自己手里的模型类型,再看看求解状态是不是“已经达到最优”。
1、在交互式命令行里直接查
如果平时习惯用CPLEX自带的交互式命令行工具,那么求解完成以后,在提示符后面直接敲入:
display solution dual-
系统就会按照顺序,把模型里每一条约束的名字,以及这条约束对应的对偶价格或者影子价格,一行一行地列出来。在CPLEX官方给出的示例里,也是用这条命令来显示这一类信息的。
2、通过编程接口去读
如果用的是C#、Java、C++这一类高级语言去调用CPLEX的库,可以对着具体的线性约束对象,调一下它的getDual方法,或者功能相近的读取接口。根据IBM文档里的说明,这个方法专门用来返回某条范围约束的对偶解数值,而且调用之前一定得保证那条约束确实在当前的活跃模型里面,否则会读不到有效的值。
3、动手之前先把约束名字写好
因为对偶值是按照一条一条约束分别返回的,所以一开始在建模的时候,最好就顺便给那些比较关键的约束取一个好认的名字,比如说“产能约束”“预算约束”“供需平衡约束”之类的。要是没有取名字,结果出来以后就只能看到系统自动生成的那种编号,等到后面再去对照哪一条对应哪一个业务条件,就会变得很麻烦,还要额外翻回去对着模型抄写一遍。
二、对偶值发生变化到底说明什么
当求解完成后观察到的对偶值跟之前比不一样了,或者模型里不同约束的对偶值有大有小,这通常是在说,某一条约束在当前这个最优解附近,对于目标函数的影响力,也就是它的边际价值,发生了变化。这里不能简单用“重要还是不重要”去判断,更准确的理解是:在最优解这个点的附近,如果把这条约束稍微松一松,让它右端项多出那么一个单位,整个目标函数会朝着什么样的方向变化、大概变化多少。
1、对偶值刚好为零
这种情况一般表明,在目前找到的这个最优解位置上,这条约束没有真正限制住全局。比如说某种资源还剩下一些没用完,机器的产能没有全部排满,那么继续追加这种资源的可用量,对于进一步改善目标值来说其实起不了什么作用,所以它的影子价格自然就是零。
2、对偶值的绝对值变得比较大
当某个对偶值的绝对值明显比其他约束要大时,往往说明目标函数对这条约束的反应比较灵敏。拿资源类的限制来举例子,一条容量已经被用得特别紧的产线,它对偶值很可能会偏高,这代表只要能给它额外增加一个单位的产能,带来的成本下降或者利润上升的幅度,就会比别的已经比较宽松的约束更加显著。IBM的线性规划教程里面,也是把对偶价格解释成右端项发生单位变化时,目标值对应会发生的那一点边际改变。
3、要留意符号跟模型设定方向之间的关系
对偶值的正负号不是单纯靠绝对值来判断好坏的,因为它跟模型本身设定的是最大化还是最小化,以及这条约束是“小于等于”还是“大于等于”这些方向设定,都绑在一起。不能一看到负数就觉得约束设置得不好。正确的做法是先回到模型里面,看清楚这条约束的数学写法,再分析当右端项增加一个单位后,对于被最小化的成本来说,是改善了还是恶化了;对于被最大化的利润来说,又会是往哪个方向走。
三、怎样复核对偶值分析出来的结论
要是想把这些对偶值拿去指导业务决策,在用它来下判断之前,还得先做几件事,确认一下模型和求解结果本身是靠谱的。不然拿出来的数字看起来再精确,一旦跟实际业务脱了节,解释起来反而会把人引到错误的方向。
1、确认当前模型确实是LP或者松弛之后的连续模型
如果一开始建的是一个混合整数规划模型,那么要特别谨慎,不要直接拿整数规划跑完以后的那个“对偶值”去做解释,因为它可能并不是标准的经济学意义。更常见的做法是先去查看这个模型的LP relaxation,也就是把整数变量放成连续变量以后的结果,或者是在固定了整数变量的取值以后,再去分析剩下的那个连续子问题的对偶值,这样会更稳妥一些。
2、把多个场景下的结果放在一起比着看
单独只看一次求解出来的对偶值,其实不太容易判断某条约束到底只是在这个局部偶然敏感,还是说它属于长期都会起作用的瓶颈。可以试着改变一下模型里的产能、需求量或者成本系数,分别求解几个不同参数下的场景,然后去观察对偶值是不是按照预期的那套规律在变化,以及目标值实际的变化幅度跟对偶值预测的趋势能不能对上。
3、解释的时候记得给对偶值带上具体的业务单位
对偶值绝对不是一个可以脱离单位随便报的数字。在汇报或者跟业务同事交流时,要能把它翻译成“每多增加一台设备,目标成本大约能下降多少”,或者“每多给一个小时的加工时间,预期利润会增加多少”这样的具体表述。没有配上单位就去讨论对偶值,在评审环节常常会被别人拿到错误的语境里去理解,甚至会误以为是指别的指标。
总结
总结起来看,在CPLEX里面去查看对偶值,既可以通过交互式命令直接输入display solution dual-,也可以在写代码时通过API读取对应约束的dual value。在解释这些对偶值的时候,不能孤立地只看数字本身,还得结合约束的松弛量、模型的优化方向还有右端项的具体业务单位一起看。
