对偶线性规划
每个线性规划问题都有一个与之对应的对偶问题。对偶问题是以原问题的约束条件和目标函数为基础构造而来的。对联问题也是一个线性规划问题，因此可以采用单纯形法求解。对偶问题的最优解也可以通过原问题的最优解得到，反之亦然。而且，在某些情况下，利用对偶理论求解线性规划问题更为简单，而且有助于深入了解待求问题的本质。
概述
对偶线性规划的经济背景是：若原问题是利用有限资源安排最优生产方案，以获得最大总产值的线性规划问题，则它的对偶问题就是在相同资源的条件下，正确估计资源的使用价值，以达到支付最少费用的线性规划问题。简言之，若原问题为求解资源的最优配置问题，则对偶问题就是求解估价资源的使用价值问题。
构建方法
原问题中的每个变量都变为对偶问题中的一个限制条件；原问题中的每个限制条件都变为对偶问题中的一个变量；原问题若是求目标函数的最大值，则对偶问题是求最小值，反之亦然。
对偶定理
对于互相对偶的最大化问题甲与最小化问题乙，我们有如下两个定理。
弱对偶定理
若{\displaystyle x\in \mathbb {R} ^{n}}、{\displaystyle y\in \mathbb {R} ^{m}}分别满足问题甲、乙的限制条件，则：{\displaystyle c^{T}x\leq b^{T}y}。
强对偶定理
若{\displaystyle x^{*}\in \mathbb {R} ^{n}}、{\displaystyle y^{*}\in \mathbb {R} ^{m}}分别满足问题甲、乙的限制条件，则：{\displaystyle x^{*},y^{*}}分别为问题甲、乙的最优解（即{\displaystyle x^{*}=\operatorname {argmax} _{x}c^{T}x}，{\displaystyle y^{*}=\operatorname {argmin} _{y}b^{T}y}），当且仅当{\displaystyle c^{T}x^{*}=b^{T}y^{*}}。换言之，若甲、乙均有解，则{\displaystyle \max _{x}c^{T}x=\min _{y}b^{T}y}。
无限值解与无解问题
若原问题有无限值解，则其对联问题无解；
若对偶问题有无限值解，则其原问题无解。
但是，原问题和对偶问题可同时无解。
基本性质
原始线性规划与对偶线性规划问题不仅在数学模型的形式上存在着相互对应的关系，而且它们的目标函数、可行解及最优解之间也存在着确定的联系。
设有一对线性规划问题为：
（1）原始问题
求
满足
（2）对联问题
求
满足
定理：互为对偶的线性规划（1）和（2）有最优解的充分必要条件是它们同时有可行解。
证明：必要性是显然的，下面来证明充分性。
设 是（1）的可行解, 是 (2) 的可行解。
则有
若 是 (1) 的任意一个可行解, 则有
成立。用 左乘 式子，得
用右乘不等式 的两边，得
由 和 两个式子，得
上式说明原始问题 (1) 的目标函数 在可行解集合上有上界，所以 (1) 有最优解。
设 是 (2) 的任意一个可行解，用同样的推理方法可得
上式表示对偶问题（2）的目标函数 在可行解集合上有下界，所以（2）有最优解。证明完毕。