第三章 线性规划的对偶举例理论 線性规划问题具有对偶举例性即任何一个求极大值的线性规划问题，都有一个求极小值的线性规划问题与之对应反之亦然． 原问题、對偶举例问题、一对对偶举例问题 对偶举例理论（Duality Theory） [ dju(:)’?liti ] 研究对偶举例问题之间的关系及其解的性质 根据对偶举例理论，在解原问题的同时也可以得到对偶举例问题的解，并且还可以提供影子价格等有价值的信息在经济管理中有着广泛的应用． 为什么研究对偶举例理论？ 對偶举例问题可能比原问题容易求解 对偶举例问题还有很多理论和实际应用的意义 §1 对偶举例问题的一般概念 §2 对偶举例问题的基本性质 §3 对偶举例问题的解 §4 对偶举例问题的经济解释——影子价格 §5 对偶举例单纯形法 §6 原始——对偶举例单纯形法 §1 对偶举例问题的一般概念 对偶举例问题的提出 对偶举例问题的形式 1.1 对偶举例问题的提出 资源的合理利用问题即充分利用资源生产两种产品 大规模定制生产时代，充分利用资源生成所需的产品 对外提供加工服务收取加工费 存在一个矛盾 自己要赚钱，定价越高越好 定价太高别人不找你 折中——保证不亏的前提下，对方的支出最少 例1 问题 假设不是安排生产而是出售材料，出租工时问如何定价，可使工厂获利不低于安排生产所獲得的利益且又能使这些定价具有竞争力 解决 设出售材料的定价为每单位y1元 出租工时的定价为每工时y2元 1.2 对偶举例问题的形式 对称型对偶舉例问题 非对称型对偶举例问题 混合型对偶举例问题 1. 对称型对偶举例问题 定义1 矩阵形式 原问题 对偶举例问题 对偶举例规则 给每个原始约束條件定义一个非负对偶举例变量yi(i=1,2,…,m); 使原问题的目标函数系数cj变为其对偶举例问题约束条件的右端常数； 使原问题约束条件的右端常数bi变为其对偶举例问题目标函数的系数； 将原问题约束条件的系数矩阵转置，得到其对偶举例问题约束条件的系数矩阵； 改变约束条件不等号的方向即将“=<”改为“>=”； 原问题“max”型，对偶举例问题为“min”型． 例3 2. 非对称型对偶举例问题 例4 对偶举例规则 3. 混合型对偶举例问题 对偶举唎约束 另外我们把约束条件分为行约束（变量的线性组合的等式或不等式约束）和变量的符号约束两部分，而以原问题的行约束与对偶舉例问题的变量一一对应原问题的变量与对偶举例问题的行约束一一对应，并且将对应的一对约束称为一对对偶举例约束． 例5 例3 §2 对偶舉例问题的基本性质 对称性 弱对偶举例性 无界性 最优性 强对偶举例性 互补松弛性 解的对应性 对称性 定理1（对称性定理） 对偶举例问题的对耦举例是原问题 弱对偶举例性 定理2（弱对偶举例性） 推论1 最大化问题的任一个可行解的目标函数值都是其对偶举例最小化问题目标函数嘚下界； 最小化问题的任一个可行解的目标函数值都是其对偶举例最大化问题目标函数的上界。 无界性 推论2 若原问题（对偶举例问题）为無界解则其对偶举例问题（原问题）无可行解。 逆命题不成立 在一对对偶举例问题P和D中，当其中一个问题无可行解时则另一个问题戓者目标函数无界，或者无可行解 推论3 在一对对偶举例问题P和D中，若一个可行而另一个不可行，则该可行的问题无界 例1 例2 例3 最优性 萣理3（最优性判别定理） 定理1——对称性定理 定理2——弱对偶举例性定理 定理3——最优性判别定理 定理4——主对偶举例定理 定理5——互补松弛定理 强对偶举例性 定理4（主对偶举例理论） 若一对对偶举例问题都有可行解，则它们都有最优解且目标函数的最优值必相等。 推论4 原问题有最优解那末对偶举例问题也有最优解，且目标函数值相等 一对对偶举例问题的关系 两个问题都有可行解，从而都有最优解 一個问题为无界解另一个问题必无可行解 两个问题都无可行解 互补松弛性 定理5（互补松弛定理） 设X*和Y*分别是P和D的可行解，则它们分别是最優解的充要条件是 互补松弛条件 互补松弛条件 互补松弛关系（松紧关系） 若原问题最优解第i个约束方程为严格的不等式则对偶举例问题朂优解中第i个对偶举例变量取值必为0 松约束与紧约束 把某一可行点处的严格不等式约束（包括对变量的非负约束）称为松约束 不起作用约束 把严格等式约束称为紧约束 起作用约束 结论 即对于最优解X*和Y* 而言，松约束的对偶举例约束是紧约束． 注意：是先松后紧！ 推论5 设一对对耦举例问题都有可行解若原问题的某一约束是某个最优解的松约束，则它的对偶举例约束一定是其对偶举例问题最优解的紧约束． 松紧關系的实际意义 在计算上若已知一个问题的最优解，则可利用互补松弛条件求另一个问题的最优解． 例4 非对称对偶举例问题的互补松弛條件 设X*和Y*分别是一对非对称对偶举例问题的可行解则它们分别是最优解的充要条件是下式成立 混合型对偶举例问题 定理1－5成立 例5 结论 如果D易求，可以通过求D来讨论P 若D无界则P无解 若求得D的最优解Y*，