三:设B是一个可行基,也是基矩阵,同时对应非基矩阵为N。则A被拆分为(B,N)两块。同时X和Xs也被糅合再拆分为基变量Xb非基变量Xn。于是对应的C也被拆分为:(Cb,Cn)。
Max z=CbXb+CnXn (1)
BXb+NXn=b (2)
Xb>=0;Xn>=0 (3)
四:引入B矩阵的逆矩阵B'。(2)式左乘B',再移项,得:
Xb=B'b-B'NXn
代入目标函数,同时令非基变量为0,则得到:
z=CbB'b
这就是拉格郎日乘数法在单纯形法里的推导。
CbB'就是拉格郎日乘子,假设为Y。发现z=Yb。可能这就是引发数学家发现对偶问题的起因,有意思的是:改进单纯形法也是这样出来的。
下面推对偶问题。
一:根据单纯形法检验数的知识,达到最优解时,我们有以下两个不等式
Cn-CbB'N<=0 (1)
-CbB'<=0 (2)
二:通过(2),我们得到第一个约束条件:Y>=0
当原问题到达最优时,对应基变量的检验数为0,得到
Cb-CbB'B=0 (3)
结合(1)和(3),得到所有检验数可以表示为:
C-CbB'A<=0,代入Y=CbB',得到第二个约束条件YA>=C
三:前面的推导已经知道z=Yb,由于Y上界无限,所以存在最小值。于是目标函数为: Min w=Yb
综合之前,得到原问题的对偶问题为:
Min w=Yb
YA>=C
Y>=0
下面是最难的部分。对偶问题如何解释?我想这也是为什么要单独写一章引入影子价格的概念来说明为什么是Min而不是Max。
首先对原问题进行解释:C表示利润,X是决策变量,A是技术水平,b是资源的上限。我们要通过A的水平和b的制约,安排生产一定数量的X,乘以C就是最后的目标,当然是希望利润越大越好。所以原问题是Max。
对偶问题描述成,工厂决定拿出一部分多余资源b对外出售,但是工厂也希望对外出售的总价格不能低于生产这个产品产生的利润,否则当然就自己生产了。于是约束条件是YA>=C。但是问题是:工厂同样也希望卖出去的资产收益最大,按照道理应该是Max,但是数学分析告诉我们不可能有Max,只能有Min。那在现实世界如何解释呢?书本上给出的解释是:从接受者来看他的支付越少越好,所以工厂的决策者只能满足YA>=C的情况下,使其总收入尽可能地小,他才能时实现其愿意。
我给出两个自己的理解,希望以后再有人学习这一章的时候可以理解地更顺一点。一:市场是信息不对称的,买方怎么可能知道工厂的YA>=C,进而来进行压价?肯定有一个比较合理的市场价来平衡售价。而工厂之所以是Min其实并不是决策的时候要往低报价,而是清楚自己的心理底价。二:既然是对偶问题干脆把目标主体也对偶过去,也就是说在一个信息对称的市场里,买方知道卖方的YA>=C,进而可以以一个让自己不亏的价格来买进资源。所以是Min。
最后来说说影子价格。拉格郎日函数,其实代表资源的边际变化,对目标函数的影响程度,看w=Yb就可以得出这个结论。这也是后面进行灵敏度分析的基础。就是说单位资源每增加一个单位,对总收益的影响。比如增加一种资源Y,能让总收益增加2,但是出售这个资源可以带来3的收益,就可以把这个资源出售。或者说这一资源市场价才1,那应该在这一刻买进这种资源扩大生产。注意影子价格有一个边际的概念,也就是说会随着本身量的变化发生变化。让总收益变化的量就是影子价格,有点类似机会成本。
而影子价格的存在,不仅仅证明了商品或者资源存在一个心理最低价,同时也揭示了它的来源。没准市场价也就是这样来的,所以说市场是调节资源配置的有效手段之一,是相当有道理的。技术,资源都不是单一的影响量,是综合作用的结果。