第二章线性规划的对偶理论2.1对偶线性规划问题的提出任一线性规划问题都存在另一与之伴随的线性规划问题，他们从不同角度对一个实际问题提出并描述，组成一对互为对偶的线性规划问题。
一、对偶线性规划问题某工厂计划安排生产Ⅰ、Ⅱ两种产品，已知每种单位产品的利润、生产单位产品所需的设备台时及A、B两种原材料的消耗、现有原材料和设备台时的定额如下表所示：【例1】ⅠⅡ设备128台时原材料A4016Kg原材料B0412Kg每单位产品利润（万元）23⏹原问题的策略:⏹问应如何安排生产才能使工厂获利最大？⏹现在的策略:⏹假设不生产Ⅰ、Ⅱ产品,而是计划将现有资源出租或出售,从而获得利润,这时需要考虑如何定价才合理?2132x x f +=max ⎪⎪⎩⎪⎪⎨⎧≥≤≤≤+0x ,x 12x 4 16 x 48x 2x .t .s 212121设x 1、x 2分别表示计划生产产品Ⅰ、Ⅱ的单位数量，由题意原问题的模型为：工厂获得最大利润符合资源限制原材料A 原材料B0412Kg每单位产品利润（万元）23原问题的模型改变策略后，需要考虑如何给资源定价的问题！设y 1、y 2 、y 3分别表示出租单位设备台时的租金和出售单位原材料A 、B 的利润.y 1+4y 2≥2，2y 1+4y 3≥3则：❑工厂出租设备、原材料的租金要大于生产的利润才合算。
321y 12y 16y 8g min ++=工厂把所有设备台时和资源都出租和出让，用户支付为：❑要寻找使租用者支付的租金最少的策略。
原材料A 原材料B0412Kg每单位产品利润（万元）23⏹新问题的模型工厂改变策略以后的数学模型为：321y 12y 16y 8g min ++=⎪⎩⎪⎨⎧=≥≥+≥+3,2,1,034y 2y 24y y ..3121i y t s i工厂获得相应利润用户所付租金最少32112168min y y y g ++=⎪⎩⎪⎨⎧=≥≥+≥+3,2,1,034y 2y 24y y ..3121i y t s i2132x x f +=max ⎪⎪⎩⎪⎪⎨⎧≥≤≤≤+0,12416482..212121x x x x x x t s 联系在于，它们都是关于工厂生产经营的模型,并且使用相同的数据；原模型和对偶模型既有联系又有区别区别在于,它们所反映的实质内容是完全不同的：前者是站在工厂经营者的立场上追求工厂的销售收入最大，而后者则是站在谈判对手的立场上寻求应付工厂租金最少的策略。
对偶线性规划对偶线性规划是一种常见的优化问题求解方法，它可以用于解决线性规划问题。
对偶线性规划的基本思想是通过引入对偶变量来转化原始问题为对偶问题，从而求解原始问题的最优解。
假设我们有一个线性规划问题：\begin{align*}\text{min } &C^TX\\\text{s.t. } &AX \ge b\\&X \ge 0\end{align*}其中，$X$是一个$n$维向量，$C$为目标函数的系数矩阵，$A$为约束条件的系数矩阵，$b$为约束条件的右边常数。
对偶问题的定义为：\begin{align*}\text{max } &b^TY\\\text{s.t. } &A^TY \le C\end{align*}其中，$Y$为对偶变量。
对于原始问题的每一个约束 $i$，引入一个对应的对偶变量$Y_i$。
根据线性规划的对偶性定理，如果原始问题存在最优解$X^*$ 和对偶问题存在最优解 $Y^*$，那么它们满足以下关系：\begin{align*}C^TX^* &= b^TY^*\\\text{且 } AX^* &\ge b\\A^TY^* &\le C\\X^* &\ge 0\end{align*}通过求解对偶问题，可以得到原始问题的最优解。
对偶问题的最优解 $Y^*$ 可以通过对偶问题的约束条件进行求解，这些约束条件是由原始问题的约束条件得到的。
而原始问题的最优解 $X^*$ 可以通过计算 $X^* = A^TY^*$ 来获得。
对偶线性规划的重要应用是在解决具有特殊结构的线性规划问题时，通过引入对偶变量可以有效地简化问题的求解过程。
对偶问题的最优解可以提供关于原始问题的有用信息，如最优解的界限、敏感性分析等。
总结起来，对偶线性规划是一种有效的优化问题求解方法，通过引入对偶变量，可以将原始问题转化为对偶问题，并通过求解对偶问题来得到原始问题的最优解。
