线性规划的对偶原理课件

线性规划的对偶原理第一节线性规划的对偶问题

对偶问题举例

对称型对偶关系的一般形式

非对称型对偶关系

一、对偶问题举例

例1

我们以第三章第一节的例1为例，已经得到了问题的数学模型：设计划期内甲、乙两种产品产量分别为吨、吨，则有

现在从另一个角度讨论个问题：假设该工厂的决策者打算不再自己生产甲、乙产品，而是将各设备的有限台时租让给其它工厂使用，他只收租费．这时工厂的决策者就要确定租价．设分别为设备每台时的租价．同意租让的原则应该是：将生产1吨产品甲所需的各设备的台时租让出去得到的租费不低于原利润32元．对产品乙也类似。问题的目标函数即为总的租费收入．得到该问题的数学模型为：

为什么求目标函数最小值呢？显然，如果求最大值，问题将具有无界解．即租价越高，得到的租费收入越多，但租价定得过高，就不会有人来租，问题也就没有实际意义了．因此，我们所求的是和自己生产甲、乙产品的最优情况效果相同的租价，即满足约束的最低租价．

上述两个线性规划问题是一对对偶问题。二、对称型对偶关系的一般形式

例1的一般形式为：

这种模型的特点是：

1、所有决策变量都是非负的；

2、所有约束条件都是“≤”类型；

3、目标函数是最大化类型．

如果把它做为原始问题，根据上述原始和对偶问题的对应关系可得出它的对偶问题为：原始问题和对偶问题之间的对应关系

称为对称型对偶关系。三、非对称型对偶关系

minz=CTXs.t. AX≤b X≥0maxw=bTYs.t.ATY≤CY≤0minz=CTXs.t. AX≥b X≥0maxw=bTYs.t.ATY≤CY≥0minz=CTXs.t. AX=b X≥0maxw=bTYs.t.ATY≤CY：无约束例2

写出下列线性规划的对偶问题第二节对偶单纯形法

对偶关系的基本性质

对偶单纯形法

一、对偶关系的基本性质

1、对称性：对偶问题的对偶是原始问题．minw=-bTYs.t.-ATY≥-C Y≥0maxw=bTYs.t.ATY≤C Y≥0minz=CTXs.t.AX≥b X≥0对偶的定义对偶的定义maxz’=-CTXs.t.-AX≤-b X≥02、弱对偶性：若为问题

（4.2.1）的一个可行解，为问题

（4.2.2）的一个可行解，则有：3、最优性：若是问题（4.2.1）的可行解，是问题（4.2.2）的可行解，且，则和分别为问题（4.2.1）与（4.2.2）的最优解．4、无界性：若线性规划问题（4.2.1）的目标函数无上界，则问题（4.2.2）无可行解；若问题（4.2.2）的目标函数无下界，则问题（4.2.1）无可行解．5、对偶定理：若问题（4.2.1）和（4.2.2）之一有最优解，则另一个也有最优解，并且目标函数值相等．二、对偶单纯形法

单纯形法是建立在原始问题的可行解之间进行迭代的，即先得到一个可行解，在迭代过程中，始终保持解的可行性．同时，使检验数逐步变为非正，直到所有的检验数都满足最优性条件，此时的可行解就是最优解．对偶单纯形法是假设检验数满足最优性条件，即保证对偶问题的解是可行的，而让原问题在非可行解的基础上进行迭代计算，使其逐步达到基本可行解。对偶单纯形法计算步骤

：1、根据线性规划的标准形式，列出初始单纯形表．若目标函数为求极大值，需保证所有的；若目标函数为求极小值，需保证所有的；2、在所有取值为负的基变量中，选绝对值最大者对应的变量为离基变量（设为）；3、确定进基变量．在单纯形表中记所在行的各系数为.若所有，则说明无可行解，停止计算；若存在，则计算选择对应列的非基变量为进基变量；4、以为主元，在单纯形表中进行迭代，得到新的单纯形表．5、重复1—4步，直到所有的值均为正（满足可行性），即得到最优解．例1

用对偶单纯形法求解解：将问题改写成如下等价形式

最优解，最优值为第三节对偶问题的经济意义

原始问题与它的对偶问题在数学上的对称关系，前面已经作了比较详细的讨论．本节将就这两者之间的关系进行经济意义上的阐述．概括地说，若原始问题为如何求解最优配置（利用或使用）资源问题；则它的对偶问题即为求解如何恰当估计资源的价格问题．前者为资源的最优使用，后者为资源价格的恰当估计，前者为配置问题，后者为价格问题．原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）对偶问题是资源定价问题资源限量（吨）资源价格（元/吨）总利润（元）对偶问题的最优解y1、y2、...、ym称为m种资源的影子价格1、影子价格的含义

影子价格()的经济含义是某种资源()增加一个单位数量而使总收益()增加的数量，即局部或个体的产出增量所获得的整体经济效果．（数值上等于最优单纯形表中松弛变量检验数的绝对值。）2、影子价格的性质

（1）影子价格可以反映资源的稀缺程度：影子价格等于0，说明该资源不是稀缺资源；影子价格大于0，说明该资源是稀缺资源，并且影子价格越大，说明该稀缺资源短缺程度越严重。

（2）影子价格与市场价格：影子价格大于市场价格，则该资源要涨价，应在涨价前购进该资源；影子价格小于市场价格，则该资源要降价，应在降价前售出该资源。

例1某企业有两条生产线，一条生产一般产品A，每小时可生产7个单位，每个单位售价为20元；另一条生产高档产品B，每小时可生产5个单位，每个单位售价30元。生产1单位A产品需1小时人工，生产1单位B产品需2小时人工；现有12名工人；另外知每增加一个工人1小时工作要花费14元，每增加1个单位A产品的生产能力要花费42元。现问企业目前应如何安排生产计划才能使总收益最大？另外若扩大再生产，应如何投资？

解：设一般产品A与高档产品B每小时的生产数量分别为、，则可建立如下线性规划模型：

先将此模型化为标准型：用单纯形法求解如下

结果为：．即生产7个单位一般产品A，生产2.5个单位高档产品B，总收益为215元．这时，人力已全部投入生产，一般产品A已达到生产能力的最大值，而高档生产线的生产能力尚有剩余．这也是目前总收益最大的生产安排．

我们由最优单纯形表可以看出松弛变量的检验数分别为-5，0，-15，即对偶变量的最优解也就是说，一般生产线的生产能力的影子价格为5元（即增加一单位的A产品生产能力，总收益可增加5元）；高档产品生产线的生产能力的影子价格为0元（即增加1单位B产品的生产能力，总收益不增加）；人工资源的影子价格为15元（即增加1小时人工，总收益可增加15元）．

企业如果要投入一定资金进行扩大再生产，为了达到最优的经济效益，就必须比较各种资源的影子价格与成本，以此来决定投资的方向．在本例中，增加1个单位A产品的生产能力要花费42元，而只能使收益增加5元（其影子价格为5元），所以不合算，而增加1个单位B产品的生产能力不论投资多少都不能增加总收益，因为其生产能力尚有剩余，而增加1小时人工的成本为14元，却能使总收益增加15元，这是合算的．所以企业应集中投资增加工人，这样可以取得更高的经济效益．第四节灵敏度分析

单纯形法的矩阵表示

灵敏度分析

线性规划数学模型的确定是以为已知常数作为基础的，但在实际问题中，这些数据本身不仅很难准确地得到，而且往往还受到诸如市场价格波动，资源供应量变化，企业的技术改造等因素的影响，因此，很自然地要提出这样的问题：当这些数据中有一个或多个发生变化时，对已找到的最优解会产生怎样的影响；或者说，当这些数据在什么范围内变化，已找到的最优基不变？这就是灵敏度分析所要研究和回答的问题．一、单纯形法的矩阵表示

对于任何线性规划问题，标准化以后可用下面矩阵形式表示：其中：为最优解中的基变量；由松弛变量和人工变量所组成，并且这些松弛变量和人工变量在约束条件中的系数构成单位矩阵；为除了以外的非基变量；、、的目标系数为、、；约束条件系数矩阵为．则初始单纯形表可表成

表4-1经过若干步迭代之后，最终单纯形表可表为表4-2二、灵敏度分析

目标函数中系数的变化

约束条件中的变化

增加一个约束条件

1、目标函数中系数的变化

从表4-2可以看出，的变化仅仅影响到检验数的变化，因此计算非基变量的检验数：若最优解保持不变；若，用单纯形法继续迭代求出最优解．2、约束条件中的变化

由表4-2看出，的变化反映在最终单纯形表上将引起最优解列数据的变化：若，用对偶单纯形法继续迭代；若，最优解保持不变．3、增加一个约束条件

先将原问题最优解代入新增的约束条件，若满足，则原最优解不变；否则，将新增约束反映到单纯形表中，同时增加一个单位向量(该约束条件的松驰变量或人工变量)，再进一步分析．

例1

线性规划模型的最优单纯形表为

（1）试求出最优基不变的的变化范围；（2）试求出最优解不变的的变化范围；（3）在原线性规划的约束条件上，增加下面的约束条件：其最优解是否变化，如变化，试求出最优解．

解：（1）假设变化，则有：因故最