线性规划对偶理论

35 第三章 线性规划的对偶理论

内涵一致但从相反角度提出的一对问题互为对偶（Dual）问题。例如，我们可以问当四边形的周长一定时，什么形状的面积最大？答案当然是正方形；我们也可以这样来问，四边形的面积一定时，什么形状的周长最短？答案同样是正方形。对偶现象相当普遍，它广泛地存在于数学、物理学、经济学等诸多领域。

每一个线性规划问题都有和它相伴随的另一个问题，一个问题称为原问题，则另一个则称为其对偶问题。原问题与对偶问题有着非常密切的关系，以至于可以根据一个问题的最优解，得出另一个问题最优解的全部信息。然而，对偶性质远不仅是一种奇妙的对应关系，它在理论和实践上都有着广泛的应用。

§1对偶问题的提出

对偶理论是以对偶问题为基础的，研究对偶理论，首先必须讨论对偶问题的提出。对偶问题可以从经济学和数学两个角度来提出，本教材仅限于从经济学角度提出对偶问题。

[例3-1] 构造例2-1的对偶问题

我们已构造了例2-1追求最大利润的数学模型（见第6页），现在让我们从另外一个侧面来反映一下该问题。倘若工厂有意放弃甲、乙两种产品的生产，而将其所拥有的资源转让出去；假设有一厂商要购买该工厂的三种资源，那么对三种资源的报价问题将成为关注的焦点。设1y、2y和3y分别代表厂商对A、B、C三种资源的报价，那么站在厂商的立场上，该问题的数学模型又将是什么样子的呢？首先分析一下厂商购买所付出的代价32112168yyyw。自然，作为买方厂商当然是希望价格压得越低越好，因此厂商追求的应是付出代价的最小值，即：

32112168minyyyw

然而，价格能否无限地压低呢？答案当然是否定的，因为最低报价必须以卖方能够接受为前提，否则报价再低也是没有意义的。落实到这一问题上就是必须保证企业让出资源的收益不低于自己生产创造的利润，即：

1y + 42y  2

21y +43y 3

第１０卷第３期　２０１５年９月　贵阳学院学报（自然科学版）　（季刊）　ＪＯＵＲＮＡＬ　ＯＦ　ＧＵＩＹＡＮＧ　ＣＯＬＬＥＧＥ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅｓ（Ｑｕａｒｔｅｒｌｙ）　Ｖ０１．１０　ＮＯ．３　Ｓｅｐ．２０１５　

线性规划对偶理论的矩阵形式的推导　

肖　瑾，何方玉，苏维东，蔡珊　

（中山大学数学与计算科学学院，广东广州５１０２７５）　

摘要：运筹学教材中给出的线性规划原问题与对偶问题关系的推导过程一般不够完整，并且是基于线性规　

划的展开形式。针对线性规划问题的矩阵形式五种非对称的情况，给出较为完整的对偶理论的推导过程。　

关键词：运筹学；线性规划；对偶问题；矩阵形式　中图分类号：０２１１．２　文献标识码：Ａ　文章编号：１６７３—６１２５（２０１５）０３—０００５—０２　

Ｔｈｅ　Ｄｅｒｉｖｅｄ　ｏｆ　Ｄｕａｌ　Ｔｈｅｏｒｙ　ｏｆ　Ｌｉｎｅａｒ　Ｐｒｏｇｒａｍｍｉｎｇ　ｉｎ　Ｍａｔｒｉｘ　Ｆｏｒｍ　

ＸＩＡ０　Ｊｉｎ，ＨＥ　Ｆａｎｇ．ｙｕ，ＳＵ　Ｗｅｉ—ｄｏｎｇ，ＣＡＩ　Ｓｈａｎ　（Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｓｃｉｅｎｃｅ　Ｓｃｈｏｏｌ，Ｚｈｏｎｇｓｈａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｇｕａｎｇｚｈｏｕ　５１０２７５，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｄｅｒｉｖａｔｉｏｎ　ｐｒｏｃｅｓｓ　ｏｆ　ｔｈｅ　ｒｅｌａｔｉｏｎｓｈｉｐ　ｂｅｔｗｅｅｎ　Ｌｉｎｅａｒ　Ｐｒｏｇｒａｍｍｉｎｇ　ａｎｄ　ｉｔｓ　ｄｕａｌ　ｐｒｏｂｌｅｍ　ｉｓ　ｎｏｔ　ｃｏｍｐｌｅｔｅ　ｉｎ　ｍｏｓｔ　Ｏｐｅｒａｔｉｏｎａｌ　ｒｅｓｅａｒｃｈ　ｍａｔｅｒｉａｌｓ，ａｎｄ　ｉｔ’Ｓ　ｅｘｐｒｅｓｓｅｄ　ｂｙ　ｅｘｐａｎｓｉｏｎ　ｆｏｒｍ．Ｔｈｅ　ｄｅｒｉｖａｔｉｏｎ　ｐｒｏｃｅｓｓ　ｄｕａｌ　ｐｒｏｂｌｅｍ　ｏｆ　Ｌｉｎｅ—　ａｒ　Ｐｒｏｇｒａｍｍｉｎｇ　ｉｓ　ｖｅｎ　ｒｅｌａｔｉｖｅｌｙ　ｃｏｍｐｌｅｔｅ　ｆｏｒ　ｔｈｅ　ｍａｔｒｉｘ　ｆｏｒｍ　ｏｆ　ｆｉｖｅ　ａｓｙｍｍｅｔｒｉｃ　ｓｉｔｕｌａｔｉｏｎ．　Ｋｅｙ　ｗｏｒｄｓ：Ｏｐｅｒａｔｉｏｎａｌ　ｒｅｓｅａｒｃｈ；Ｌｉｎｅａｒ　Ｐｒｏｇｒａｍｍｉｎｇ；Ｄｕａｌ　ｐｒｏｂｌｅｍ；Ｍａｔｒｉｘ　ｆｏｒｍ　

Excel数据管理与图表分析 线性规划的对偶理论

对偶性是线性规划问题最重要的内容之一。每一个线性规划问题必然会有与之相伴而生的另一个线性规划问题。例如，任何一个求最大值的线性规划问题，都有一个求最小值的线性规划问题与之相对应。

简单的说，即同一个问题可以从两个不同的方面进行研究：一方面在一定的资源条件下，如何合理的安排，获得的利润最多；而另一方面为如何才能利用最少的资源完成既定的任务。这两个方面互相对称，互为对偶。

如果把前者称为原问题，则后者为对偶问题；若把后者称为原问题，则前者为对偶问题，这就是线性规划的对偶性。其中，原问题记做P；对偶问题记做D。利用线性规划的对偶性，可以从正反两方面获得定量资料，为企业经营决策提供重要的依据。

例如，某工厂生产甲、乙两种产品，其资源限制等已知条件如表12-1所示，求应该如何安排生产计划，使得该工厂能够获得最大利润？若假设该工厂不考虑自己生产这两种产品，而是将现有资源用于接受外来加工任务，只收取加工费。试问该决策者应指定的收费标准为多少？

表12-1 已知生产条件

甲 乙

资源限制

钢材 5 2 170

煤炭 2 3 100

设备 1 5 150

单件利润 10 18

该问题的提出需要从两个方面解决，首先计算该工厂可获得的最大利润。根据已知条件，可以在Excel工作表中，创建如图12-15所示的求解模型。

图12-15 最大利润求解模型

在该求解模型中，选择D3单元格，在【编辑栏】中输入“=SUMPRODUCT($B$7:$C$7,B3:C3)”公式，并拖动其填充柄，将该公式复制到D4和D5单元格，如图12-16所示。

然后，选择目标函数所对应的单元格，即F7单元格，在【编辑栏】中，输入“=SUMPRODUCT(B7:C7,B6:C6)”公式，并按Enter键或者单击【输入】按钮即可，如图12-17所示。 产 品 资

源

建立模型

图12-16 计算合计值 图12-17 计算目标函数值

第三章 线性规划及其对偶问题

线性规划是最优化问题的一种特殊情形，也是运筹学的一个重要分支，它的实质是从多个变量中选取一组适当的变量作为解，使这组变量满足一组确定的线性式，而且使一个线性目标函数达到最优（最大或最小）．

线性规划的应用极为广泛，自1949年美国数学家G. B. Dantzing提出一般线性规划问题求解的方法——单纯形法之后，线性规划无论在理论上、计算方法和开拓新的应用领域中，都获得了长足的进步，线性规划从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都有广泛的发展和应用．本章主要从线性规划的基本概念、数学模型、单纯形法、对偶理论、灵敏度分析等方面进行介绍．

§3.1 线性规划数学模型基本原理

一、线性规划的数学模型

满足以下三个条件的数学模型称为线性规划的数学模型：

（1）每一个问题都用一组决策变量Tnxxx][21，，，表示某一方案；每一组值就代表一个具体方案．

（2）有一个目标函数，可用决策变量的线性函数来表示，按问题的不同，要求目标函数实现最大化或最小化．

（3）有一组约束条件，可用一组线性等式或不等式来表示．

线性规划问题的一般形式为

1211221111221121122222112212max(min)()()()..()0nnnnnnnmmmnnmnfxxxcxcxcxaxaxaxbaxaxaxbstaxaxaxbxxx，，，，，，，，，，，，，．

这里，目标函数中的系数nccc，，，21叫做目标函数系数或价值系数，约束条件中的常数mbbb，，，21叫做资源系数，约束条件中的系数；，，，miaij21(

)21nj，，，叫做约束系数或技术系数．

二、线性规划问题的标准形式

所谓线性规划问题的标准形式，是指目标函数要求min，所有约束条件都是等式约束，且所有决策定量都是非负的，即