对偶规划

对偶规划(dual programming)一类线性规划问题，指由原线性规划问题按如下对称规律构成的新线性规划问题：若原问题(P)为maxz=CTX，满足{AX≤b，x≤0 }，则对称的新问题(D)为minw=yTb，满足{yTA≥c，y≥0 }，这里y为m维列向量，新问题(D)称为原线性规划的对偶规划。对偶规划最初是由冯·诺伊曼（vonNeu-mann，J.）于1947年提出来的，以后库恩（Kuhn，H.W.）和塔克尔(Tucker，A.W.）证明了对偶定理。哥德曼(Goldman，A.J.）和塔克尔于1956年比较系统地叙述了对偶规划的理论。