其单纯形表应为 xB 基 变 量 b x B?1A xS B?1 B?1b ?CBB?1b C?CBB?1A ?CBB?1 在上面的单纯形表中，当检验数：
?1 C?CA?0 ， ?CBB?1?0 时， BB原问题得到最优解。若令y??CBB?1，则上式即为：
?yA?c ??y?01因y??CBB?1，故yb??CBB?b?z，而y的上界为无限大，所以存在最小值。于
是得到另一个线性规划：
minw?ybyA?cy?0称为线性规划（?）的对偶规划。
(??)
§2.2 线性规划的对偶理论
1． 原问题与对偶问题的关系
原问题maxz?cxAx?bx?0
对偶问题minw?ybyA?cy?0
列表表示原问题与对偶问题的关系 原问题（或对偶问题） 目标函数maxz n 个 对偶问题 （或原问题） 目标函数minw ?0 ?0 极大的变量 与 n 个 ? ? 24
变 量 m 个 约 束 无约束 ? ? = 约束项右端 目标函数变量的系数 极小的约束 一致 极大的约束 与 极小的变量 相反 约 束 m 个 变 量 = ?0 ?0 无约束 目标函数变量的系数 约束项右端 例1. 试求下述线性规划的对偶问题
minz?2x1?3x2?5x3?x4x1?x2?3x3?x4?52x1?2x3?x4?4x2?x3?x4?6x1?0,x2,x3?0,x4无约束
maxz?x1?2x2?3x3?4x4?x1?x2?x3?3x4?56x1?7x2?3x3?5x4?8 12x1?9x2?9x3?9x4?20x1,x2?0,x3?0,x4无约束2．对偶问题的基本性质
（I）对称性 对偶问题的对偶是原问题。
（II）弱对偶性 设x,y分别是原问题与对偶问题的可行解，则cx?yb （III）无界性 若原问题（对偶问题）有可行解而无最优解，则对偶问题（原问题）无可行解。
（IV）设x,y分别是原问题与对偶问题的可行解，若cx?yb，则x,y是最优解。 （V）对偶性 若原问题有最优解，则对偶问题也有最优解，且目标函数值相等。
?,?（VI）互补松弛性 设xy分别是原问题与对偶问题的可行解，那么?yxs?0，?,???0的充要条件是xy是最优解。 ysx（VII）设原问题是
maxZ?cxAx?xs?b
x,xs?0
25
它的对偶问题是
minw?yb yA?ys?cy,ys?0
则原问题的单纯形表的检验数行的相反数对应其对偶问题的一个基本解。 xB 基 变 量 例1. 已知线性规划
b x B?1A xS B?1 B?1b ?CBB?1b C?CBB?1A ?ys ?CBB?1 ?y minw?2y3y1?2?
5y?32y?43y5y1?y2?2y3?y??5443y2y1?y2?3y3?y?4y?53
yj?0,j?1,2,3,4,543并知其对偶问题的最优解为x1*?,x2*?，试用对偶理论求原问题的最优解。
55
例2. 已知线性规划
maxZ?2x1?x2?5x3?6x42x1?x3?x4?82x1?2x2?x3?2x4?12xj?0,j?1,2,3,4
** 其对偶问题的最优解为y1?4,y2?1，试用对偶理论求原问题的最优解。
26
§2.3 对偶问题的经济解释——影子价格
设线性规划为
maxz?cxAx?bx?0将其化为标准形
maxz?cxAx?xs?bx,xs?0 设B是最优基，则矩阵描述的单纯形表为
xB 基 变 量 b x B?1A xS B?1 B?1b ?CBB?1b C?CBB?1A ?CBB?1 在最后一行中，每一项都含有CBB?1（称为单纯形乘子）。 下面说明y?CBB?1的经济意义： 由原问题与对偶问题的关系，有
z*?CBB?1b?y*b
这里Z*是原问题的最优值，y*是对偶问题的最优解。 由于
?z*?CBB?1?y* ?b所以变量yi*的经济意义是在其他条件不变的情况下，单位资源的变化所引起的目标函数的最优值的变化。
27
例1．
maxz?2x1?3x2x1?2x2?84x1?16 4x2?12xj?0,j?1,2最终单纯形表 xB x1 x5 x2 b x1 1 0 0 0 x2 0 0 1 0 x3 0 -2 1 23? 2x4 1 41 21? 81? 8x5 0 1 0 0 4 4 2 14 从表可以看出y1*?1.5,y2*?0.125,y3*?0。这说明其他条件不变的情况下，若设备增加一台时，该厂按最优计划安排生产可多获利1.5元；原料A增加1kg，可多获利0.125元；原料B增加1kg，对获利无影响。
这一点可以从图解法得到验证。若设备增加一台时，则解为(4,2.5)；若原料A增加1kg ，则解为(4.25,1.875)；若原料B增加1kg，则最优解不变。 在该厂现有资源和现有生产方案的条件下，设备每小时租费为1.5元，1kg原料A的转让费为除成本外再附加0.125元，1kg原料B可按原成本转让，则该厂的收入与自己组织生产时获利相等。
yi的值代表对第i种资源的估价，这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称这为“影子价格”。
在完全市场经济的条件下：
资源市场价格?影子价格，企业买进，扩大生产；
资源市场价格?影子价格，企业卖出。
影子价格对市场有调节作用。
28