线性规划对偶问题

出处：按学科分类—经济 湖北人民出版社《企业管理公式辞典》第352页（1410字）

实质相同但从不同角度提出不同提法的一对问题，称互为对偶的问题。对偶现象是许多管理与工程实际中存在的一种普遍现象。例如，企业怎样充分利用现有人力、物力去完成更多的任务和怎样用最少的人力、物力消耗去完成给定任务，就是互为对偶的一对问题。线性规划问题中存在的对偶性关系，在线性规划的理论及其应用上都是极为重要的。

(1)对偶模型

一个线性规划问题，都存在一个与之相联系的对偶问题。线性规划原问题与对偶问题在模型上有如下对应关系：

典型形式的线性规划模型，根据上述对应关系，应有：

原问题

对偶问题

线性规划模型条目中，举例模型

其对偶模型为

(2)对偶问题的基本性质

①对称性：对偶问题与原问题互为对偶。

②对偶不等式：若X是原问题的可行解，Y是对偶问题的可行解，则有：CX≤Yb

③强对偶性：若X*是原问题的最优解，Y^*是对偶问题的最优解，则有：CX^*=Y^*b

④检验数与解的对应关系：原问题松弛变量(或剩余变量)的检验数，对应对偶变量的解。反之亦然。

⑤松紧性：若、分别是原问题决策变量与松弛变量的最优解；y₁^*，分别是对偶问题对偶变量与剩余变量的最优解，则有：

根据上述性质的3、4，我们求解出一个线性规划问题，相当于对其对偶问题也作出了求解。

例如，根据对线性规划模型条目中例题求解的单纯形最终表(见求解线性规划模型单纯形法表格)，可立即写出其对偶模型的解：

(3)对偶解的经济含义——影子价格

线性规划对偶问题对偶变量的最优解，表示在最优计划情况下，对原问题中各种资源的评价值。具体的数量定义是，表示增加一个单位的某种资源，对目标函数的贡献。例如，上述对偶解y₂^*=1．36，表示电力资源增加一个单位，能使目标增加1．36万元；y₃^*=0．52，表示人工资源增加一个单位，能使目标增加0．52万元。这个评价值常称为资源的边际价格或称资源的影子价格。