物流优化技术课件 第3章3.6 对偶原理

换个角度审视生产计划问题例3-1要求制定一个生产计划方案，在劳动力和原材料可能供应的范围内，使得产品的总利润最大。3．6对偶原理（用于生产第i种产品的资源转让收益不小于生产该种产品时获得的利润）

它的对偶问题就是一个价格系统，使在平衡了设备资源和原材料的直接成本后，所确定的价格系统最具有竞争力：

对偶变量的经济意义可以解释为对工时及原材料的单位定价；若工厂自己不生产产品Ⅰ、Ⅱ，将现有的设备及原材料转而接受外来加工时，那么上述的价格系统能保证不亏本又最富有竞争力（包工及原材料的总价格最低）

当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值是相等的：

Zmax=Wmin=14

考察原问题和对偶问题的解，给作决策的管理者另一个自由度；

怎样通过增加更多的资源来增加利润？

怎样使用不同类型的资源来增加利润？

3、饮食与营养问题

例3-2采购甲、乙、丙、丁4种食品量分别为x1，x2，x3，x4，在保证人体所需维生素A、B、C前提下，使总的花费最小。

构建的线性规划模型：

换一个角度，生产营养药丸的制药公司力图使营养师相信，各种营养药丸勿须通过多种食品的转换就能供营养师调剂。

制药公司面对的问题是为营养药丸确定单价，以获得最大的收益，同时与真正的食品竞争。于是，营养药丸的单位成本不能超过相应食品的市场平均价。由此得到下面的对偶问题：二、原问题和对偶问题的关系1、对称形式的对偶关系（1）若原问题是

这两个式子的变换关系称为“对称形式的对偶关系”。

(2)其对偶问题为（2）对称形式的对偶关系的矩阵描述(D)(L)例3-3写出下面线性规划的对偶问题：

（1）原问题对偶问题（特点：对偶变量符号不限，系数阵转置）(特点：等式约束)2、非对称形式的对偶关系：（2）怎样写出非对称形式的对偶问题？把一个等式约束写成一个不等式约束，再根据对称形式的对偶关系定义写出；按照原始-对偶表直接写出；（3）原始-对偶表

原问题（或对偶问题）

对偶问题（或原问题）

目标函数MaxZ目标函数MinW约束条件数：m个第i个约束条件类型为“≤”第i个约束条件类型为“≥”第i个约束条件类型为“=”

对偶变量数：m个第i个变量≥0第i个变量≤0第i个变量是自由变量

决策变量数：n个第j个变量≥0第j个变量≤0第j个变量是自由变量

约束条件数：n第i个约束条件类型为“≥”第i个约束条件类型为“≤”第i个约束条件类型为“=”

例3-4写出下面线性规划的对偶问题：

三、对偶定理对偶定理是揭示原始问题的解与对偶问题的解之间重要关系的一系列定理。定理2-1对称性定理——对偶问题的对偶是原问题。定理2-2弱对偶定理——若一对对称形式的对偶线性规划L）

和D）

均有可行解，分别为和，则C≤b。•关于“界”的结果；极小化问题有下界——推论1

极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。•极大化问题有上界——推论2

极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。•关于最优解无界情况与对偶问题的关系；原始问题可行，且目标函数值上无界对偶问题不可行

最优性准则定理——若、分别为对称形式对偶线性规划的可行解，且两者目标函数的相应值相等，即C=b，则，分别为原始问题和对偶问题的最优解。

定理2-3最优性准则定理定理2-4主对偶定理若原始问题和对偶问题两者均可行，则两者均有最优解，且此时目标函数值相同。四、对偶最优解（影子价格）的经济含义1、

对偶最优解的经济解释

讨论例3-1的图解法时，提出了它的对偶规划，并用图解法求出了最优解。同时提到“影子价格”，确切的定义是：一个线性规划对偶问题的最优解（简称为“对偶最优解”）。在经济上可以解释为约束条件所付出的代价。当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值相等，即有

Zmax=CX*=2x*1+3x*2

Wmin=Y*b=8y*1+16y*2+12y*3=14

其中X*是原问题的最优解，Y*是对偶问题最优解。||

说明目标函数值增加一个单位，这就是放宽一个约束条件所产生的附加贡献。就是说，影子价格确定了为得到一个附加单位的约束因素所应花费的成本上限。

劳动工时！因为它的变化对产品总利润的影响最大，因此劳动力是最关键的生产环节，若能采取有力措施增加劳动总工时，则产品总利润将得到较大的提高。

在计算机求解结果中将约束条件的影子价格和变量的机会成本统称为机会成本（opportunitycost）。

当前最敏感的资源是什麽？

求解结果总表

SummarizedResultedforCase1

VariablesNo.NamesOpportunityCost

VariablesNo.NamesOpportunityCostSolutionSolution1x14.00000.00004s20.00000.12502x22.00000.00005s34.00000.00003s10.00001.5000

MaximumValue