物流运筹学 课件 第3章 对偶理论x

第3章线性规划对偶理论及其应用例1

穗羊公司的例子3.1线性规划的对偶问题生产计划问题（LP1）III每周可使用量A（千克）125B（吨）214C（百工时）439单位产品利润（万元）32III每周可使用量A（千克）125B（吨）214C（百工时）439单位产品利润（万元）32穗羊公司如果要出让其拥有的资源:单价y1,y2,y3y1y2y3生产每件产品的资源出让后获得的收益应该不低于该件产品的收益.产品I:产品II:接手其所有资源的厂家期望出价越低越好:资源定价问题（LP2）比较原问题（生产计划）对偶问题（资源定价）3.1.2规范形式的线性规划问题原问题（LP）对偶问题（DLP）

规范形式最大化问题:约束条件全为型决策变量全部非负最小化问题:约束条件全为型决策变量全部非负规范形式的对偶关系原问题对偶问题目标函数:maxCX目标函数:minb´Ym个约束条件:AXbm个决策变量:Y0n个决策变量:X0n个约束条件:A´YC´原问题对偶问题非规范形式的对偶关系对非规范形式的对偶关系，只需对上述表进行相应修改即可：例如对于一个最小化问题，若某个决策变量yi

0,则其对偶的约束条件为型的;若其某个约束条件是型,则其对应的对偶变量是非正的.3.1.3非规范形式线性规划的对偶问题1变量取值范围不符合非负要求的情况3.1.3非规范形式线性规划的对偶问题2约束方程不是“≤”的情况

3.1.4总结约束条件对变量，变量对约束条件；正常对正常，不正常对不正常；变量正常是非负，约束条件正常看目标(max≤，min≥)。

例2.5求解下面线性规划的对偶规划LPDLP3.2对偶规划的基本性质3.2.1对称性定理：线性规划的对偶问题的对偶问题是原问题。证明：

对偶定义令w’=-w；约束方程左右同乘“-1”对偶定义令z=-z’；约束方程左右同乘“-1”3.2对偶规划的基本性质3.2.2弱对偶性定理：如果X、Y分别是原问题和对偶问题的一个可行解，则其对应的原问题的目标函数值不大于对偶问题的目标函数值，也即证明：因为X、Y分别是原问题（3.1）与对偶问题（3.2）的可行解，故：

所以推论一：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。推论二：如果原问题存在无界解，则对偶问题一定无可行解；反之，如果对偶问题存在无界解，原问题也一定不存在可行解。3.2.3最优性定理也就是说若原问题与对偶问题各存在一个可行解,且它们对应的目标函数值相等,则它们分别是原问题与对偶问题最优解.如果原问题存在最优解X*，则其对偶问题一定具有最优解Y*，且初始单纯形表的矩阵表示CBCN0CSxBxNxS0BNISbCBCN00最优单纯形表的矩阵表示CBCN0CBxBxNxSCBIB－1NB-1B-1b0CN-CBB－1N-CBB－1CBB－1b令则Y*>=0,且故Y*即为对偶问题的最优解。又因为3.2.4强对偶性定理（对偶定理）B-1B-1B-1B-1在初始单纯形表中单位矩阵经过迭代后变为基矩阵B的逆在初始单纯形表给出的解中基变量Xs=b,而在迭代后的表给出的解中基变量

XB=B-1b系数矩阵的变化:[A,I]B-1[A,I]在初始单纯形表中变量xj的系数为Pj经过迭代后变为Pj′,并且Pj′=B-1Pj若迭代后的单纯形表为最终表则该表也同时给出对偶问题的最优解

32000

CBXBx1x2x3x4x5b0x3

0015/2-3/23/23x1

1003/2-1/23/22x2010-211

000-1/2-1/213/2

32000

CBXBx1x2x3x4x5b0x3

1210050x4

2101040x5430019

320000例3.1的初始表与最终表B?B-1例3.1的原问题与对偶问题最终单纯形表的比较

32000

CBXBx1x2x3x4x5b0x3

0015/2-3/23/23x1

1003/2-1/23/22x2010-211

000-1/2-1/213/2

54900

y1y2y3y4y5

4y2-5/210-3/221/29y33/2011/2-11/2

3/2003/2113/2

原问题对偶问题对于最大化问题,其最终表的检验数的相反数是对偶问题最优解对于最小化问题,其最终表的检验数是对偶问题最优解原问题LP（生产计划）对偶问题DLP（资源定价）3.2.5互补松弛定理原问题对偶问题变量xi或yi

0分为两种情况yi>0，变量比较松；yi=0，变量比较紧；约束条件

分为两种情况

，约束条件比较松；

，约束条件比较紧；变量同其对偶问题的约束方程之间，至多只能够有一个取松弛的情况；当其中一个取松弛的情况时，另外一个比较紧，即取严格等号。互补松弛定理例3.6已知下面的LP1和LP2为一组对偶规划，且已知LP1的最优解为X=（1.5，1）’。试运用互补松弛定理求出对偶问题的最优解Y。原问题（LP1）对偶问题（LP2）解：由X=（1.5，1）’得联立求解得：

说明资源增加1个单位，企业总利润可以增加单位。所以如果资源的市场价格低于，就要买进。3.3影子价格和灵敏度分析3.3.1影子价格 对偶变量的经济含义就是资源的定价，然而这种价格同市场价格不同，我们称之为影子价格。它反映了资源对于企业的紧缺程度、利润贡献程度等，并不能反映资源的生产成本，以及在外部市场的紧缺程度。1、影子价格是边际利润根据互补松弛定理：如果某种资源有剩余，则增加资源不会增加利润，影子价格为0；如果某种资源影子价格大于0，则一定没有剩余。如果新产品对m种资源的单位消耗量分别为则其机会成本为如果其利润大于机会成本就生产，否则不生产。2、影子价格是机会成本第i种资源减少1个单位，企业的利润减少yi。如果其他企业要购买该种资源，给出的而价格高于yi

，就要考虑卖出。如果该产品机会成本大于利润，则该产品不生产。对于原有产品，如果生产的，则其机会成本等于利润。

对偶单纯形法按对偶问题与原问题之间的关系，对最大化问题，在用单纯形法求解原问题时，最终表不但给出了原问题的最优解，而且其检验数的相反数就是对偶问题的最优解。单纯形法求解的基本思路基可行解检验数非正保持解的可行性对偶单纯形法的基本思路对偶问题基可行解（检验数非正）原问题基可行解保持对偶问题解的可行性（检验数非正（对偶问题可行解）对偶单纯形法计算步骤适用于求解这样的LP问题：标准化后不含初始基变量，但将某些约束条件两端乘以“-1”后，即可找出初始基变量。要求：初始单纯形表中的检验数满足最优性条件对满足上述条件的LP问题，对偶单纯形法的步骤是：旋转运算。然后回到第2步。作出初始单纯形表（注意要求）检查b列的数据是否非负，若是，表中已经给出最优解；否则转下一步确定换出变量：取b列最小的数对应的变量为换出变量确定换入变量：用检验数去除以换出变量行的那些对应的负系数，在除得的商中选取其中最小者对应的变量为换入变量例用对偶单纯形法求解如下的LP问题化成标准形式将各约束条件两端同乘“-1”得用对偶单纯形法求解得最优解：x1=0,x2=1/4,x3=1/2,x4=0,x5=0最优目标函数值：w*=-8.5（z*=8.5）注：通常很少直接使用对偶单纯形法求解线性规划问题。选择b列的最小(负)元素对应基变量为换出变量用检验数除以换出变量行的负的元素,取所得的最小商对应的变量为换入变量最优解：x1=0,x2=1/4,x3=1/2,x4=0,x5=0最优目标函数值：w*=-8.5（z*=8.5）注：通常很少直接使用对偶单纯形法求解线性规划问题。选择b列的最小(负)元素对应基变量为换出变量用检验数除以换出变量行的负的元素,取所得的最小商对应的变量为换入变量

甲公司的生产情况3.5灵敏度分析1、目标函数系数cj变化例3.7C由(3.2)变为(3,1)，请问最优生产计划如何变化？解：由原最优单纯形表得：基变量31000bCBxBx1x2x3x4x50x30015/2-3/23/23x11003/2-1/23/21x2010-2[1]1000-5/21/211/2

单纯形迭代得：基变量31000bCBxBx1x2x3x4x50x303/21-1/2033x111/201/2020x5010-2110-1/20-3/2-3/26

所以得到新的最优生产计划为产品I生产2件，产品II不生产，此时总利润为6万元。例3.8假设产品II的价格不变，请问产品I的价格在什么范围内波动时，最优生产计划不变？欲使最优生产计划不变，须

2000

CBXBx1x2x3x4x5b0x3

0015/2-3/23/2x1

1003/2-1/23/22x2010-211

000也即时，最优生产计划不变。解：假设c1由3变为，则2、约束条件右端向量b的变化例3.9穗羊公司仓库盘点时发现，资源B的每周可使用量可以增加到5吨，请制定新的最优生产计划。解：因为，所以需要进行对偶单纯形迭代。由原最优单纯形表得：基变量32000bCBxBx1x2x3x4x50x30015/2-3/24（1）3x11003/2-1/23（2）2x2010[-2]1-1（3）000-1/2-1/27

（4）因为x2=-1<0，所以令其岀基。拿检验数所在行除以出基变量所在行的负数，商最小的列对应的元素作为主元素。这里正数和零不能作为主元素。本题中第三行只有a34=-2<0，所以选择a34作为主元素，进行对偶迭代。迭代的目标：右端向量划为非负把基变量所在列划成单位矩阵基变量检验数化为零。基变量32000bCBxBx1x2x3x4x50x305/410-1/411/4（1）+5*（3）/43x113/4001/49/4（2）+3*（3）/40x40-1/201-1/21/2（3）*（-1/2）0-1/400-1/427/4

（4）-（3）/4迭代后得：3、增加一种新产品例3.10穗羊公司研发部门开发了一种新产品III，单位产品对A、B、C三种资源的消耗系数为（3,0,2）/，该产品单位利润为2万元。问产品III是否应该生产？如果生产，各产品生产量是多少？解：产品III机会成本

该产品的检验数，所以应该生产。将上述数据代入原最优单纯形表得下表：基变量320002bCBxBx1x2x3x4x5x60x30015/2-3/203/23x11003/2-1/2-13/22x2010-21[2]1000-1/2-1/2113/2

0x30015/2-3/203/23x11001/20022x601/20-11/211/20-1/20-11/4-107所以，新的最优生产计划是产品I和产品III分别生产2件和1/2件，产品II不生产，总利润为7万元。4、增加一个新的约束条件例3.11：穗羊公司生产部门发现生产除了受到A、B、C三种资源的约束外，还要受到资源D的约束。资源D周可用量为6，生产单位产品I、II对资源D的消耗分别为7/2和2。请制定新的最优生产计划。解：根据题意，需要在原问题后面增加新约束将原最优生产计划X=（3/2，1）’代入该约束方程得：不满足新约束条件。将约束方程添加松弛条件得：将此约束方程代入原最优单纯形表得下表：基变量310000bCBxBx1x2x3x5x5x60x30015/2-3/203/2（1）3x11003/2-1/203/2（2）1x2010-2101（3）0x67/2200016（4）000-1/2-1/2011/2

将a41、a42化为0得下表：基变量310000bCBxBx1x2x3x5x5x60x30015/2-3/203/2（1）3x11003/2-1/203/2（2）1x2010-2101（3）0x6000[-5/4]-1/41-5/4（4）000-1/2-1/2011/2对偶单纯形迭代得下表：基变量310000bCBxBx1x2x3x5x5x60x30010[-2]2-13x11000-4/56/501x201007/5-8/530x400011/5-4/510000-2/5-2/550x500-1/201-11/23x110-2/5002/52/51x2017/1000-1/523/100x4001/1010-3/59/1000-1/500-4/524/5所以新的最优生产计划是产品I和产品II分别生产2/5件和23/10件，总利润为24/5万元。

5、约束条件系数aij的变化例3.12：穗羊公司经过技术革新，将生产产品I对资源C的单位消耗量从4变为2，即P1=（1,2,4）’变为P1=（1,2,2）’。请求出新的最优生产计划。解：令将插入原最优单纯形表格得：基变量-99731000bCBxBx1x1’x2x3x4x50x30[3]015/2-3/23/2-997x112003/2-1/23/22x20-210-21102001002999/2-1001/22987/23