《对偶理论与灵敏度分析课件》由会员分享，可在线阅读，更多相关《对偶理论与灵敏度分析课件（41页珍藏版）》请在金锄头文库上搜索。
1、第三章第三章 对偶理论与灵敏度分析对偶理论与灵敏度分析1 1 单纯形法的矩阵描述单纯形法的矩阵描述2 2 改进单纯形法改进单纯形法3 3 对偶问题的提出对偶问题的提出4 4 线性规划的对偶理论线性规划的对偶理论5 5 对偶问题的经济解释对偶问题的经济解释影子价格影子价格6 6 对偶单纯形法对偶单纯形法7 7 灵敏度分析灵敏度分析对偶理论与灵敏度分析课件1 单纯形法的矩阵描述单纯形法的矩阵描述设线性规划问题设线性规划问题设设B是一个可行基，令（是一个可行基，令（A，I）=（B，N，I），则：），则：对偶理论与灵敏度分析课件1. 检验数的矩阵描述：检验数的矩阵描述： B=CB-CBB-1B=0 N
2、=CN-CBB-1N S=-CBB-1 =min(B-1b)i/ (B-1Pk)i| (B-1Pk)i0= (B-1b)l / (B-1Pk)lXBbXBXNXsB-1bIB-1NB-1(B-1 b)i (B-1Pk)i-zCBB-1b0CN-CBB-1N-CBB-13. 单纯形表的矩阵描述：单纯形表的矩阵描述：=C-CBB-1A2.的矩阵描述：的矩阵描述：对偶理论与灵敏度分析课件2 改进单纯形法改进单纯形法用改进单纯形法求解线性规划问题的计算步骤：用改进单纯形法求解线性规划问题的计算步骤：1. 确定初始可行基确定初始可行基B1。求出。求出B1-1；2. 计计算算非非基基变变量量的的检检验验数
3、数N 。若若N 0已已求求的的最最优优解，停止计算解，停止计算,否则进行下一步；否则进行下一步；3. 确定换入变量确定换入变量 xk；4. 计算计算B1-1b， B1-1 Pk及及；若若 0那么无最优解，停止计算，否则进行下一步；那么无最优解，停止计算，否则进行下一步；5.确定换出变量确定换出变量 xl;6. 计算计算B2-1；7. 重复重复27步。步。对偶理论与灵敏度分析课件 对偶理论与灵敏度分析课件 例：用改进单纯形法求解例：用改进单纯形法求解对偶理论与灵敏度分析课件解：解： 对偶理论与灵敏度分析课件 对偶理论与灵敏度分析课件 对偶理论与灵敏度分析课件 对偶理论与灵敏度分析课件3 对偶问题
4、的提出对偶问题的提出 例：例： 设备设备原材料原材料A原材料原材料B1402048 台时台时16 kg12 kg利润利润23x1minx2x1x2y1y2y3对偶理论与灵敏度分析课件当该问题达到最优时有：当该问题达到最优时有： z的上界为无限大，所以只存在最小值。于是得到的上界为无限大，所以只存在最小值。于是得到另一个线性规划问题另一个线性规划问题对线性规划问题线性规划问题对偶问题对偶问题原问题原问题对偶理论与灵敏度分析课件4 线性规划的对偶理论线性规划的对偶理论 4.1 原问题与对偶问题的关系原问题与对偶问题的关系对偶理论与灵敏度分析课件原问题（对偶问题原问题（对偶问题）对偶问题（原问题）对
5、偶问题（原问题）例：例：23-51对偶理论与灵敏度分析课件对偶理论与灵敏度分析课件对偶理论与灵敏度分析课件4.2 对偶问题的性质对偶问题的性质1. 对称性对称性 对偶问题的对偶是原问题。对偶问题的对偶是原问题。2. 弱弱对对偶偶性性 若若X*是是原原问问题题的的可可行行解解，Y*是是对对偶偶问问题的可行解题的可行解,则存在则存在 CX* Y*b证证 设原问题及对偶问题为设原问题及对偶问题为 max z =CX， AXb， X0 min=Yb， YAC Y0 若若X*是是原原问问题题的的可可行行解解，Y*是是对对偶偶问问题题的的可可行行解解 AX*b Y*AC Y*AX*Y*b Y*AX*CX*
6、 CX* Y*AX* Y*bCX*Y*b对偶理论与灵敏度分析课件3. 无无界界性性 若若原原问问题题（对对偶偶问问题题）为为无无界界解解，则其对偶问题（原问题）无可行解。则其对偶问题（原问题）无可行解。4. 可可行行解解是是最最优优解解的的性性质质 设设X是是原原问问题题的的可可行行解解，Y是是对对偶偶问问题题的的可可行行解解，当当CX= Yb时，时， X， Y是最优解。是最优解。5. 对对偶偶定定理理 若若原原问问题题有有最最优优解解，则则对对偶偶问问题也有最优解，且目标函数相等。题也有最优解，且目标函数相等。6. 互互补补松松驰驰性性 若若X是是原原问问题题的的可可行行解解，Y是是对对偶偶
7、问问题题的的可可行行解解，那那么么YXs=0，Ys X=0，当且仅当当且仅当 X， Y为最优解。为最优解。对偶理论与灵敏度分析课件6. 互互补补松松驰驰性性 若若X是是原原问问题题的的可可行行解解，Y是是对对偶偶问问题题的的可可行行解解，那那么么YXs=0，Ys X=0，但但且且仅仅当当 X， Y为最优解。为最优解。证：设原问题及对偶问题的标准型是证：设原问题及对偶问题的标准型是 max z =CX， AX+XS=b， X， XS 0 min=Yb， YAYS=C Y， YS 0 z =(YAYS)X=YAXYSX =Y(AX+XS)=YAX+YXS X是原问题的可行解，是原问题的可行解，Y是
8、对偶问题的可行解是对偶问题的可行解 z =YAXYS X =YAX+YXS当当YXs=0，Ys X=0时时z =，则，则X，Y是最优解。是最优解。当当 X，Y是最优解时是最优解时 z = ，则，则YXs=0，Ys X=0 对偶理论与灵敏度分析课件例：已知线性规划问题例：已知线性规划问题max其对偶问题的最优解为其对偶问题的最优解为试用对偶理论求原问题的最优解试用对偶理论求原问题的最优解解：解：max对偶理论与灵敏度分析课件 7. 设原问题及对偶问题的标准型是设原问题及对偶问题的标准型是 max z =CX， AX+XS=b， X， XS 0 min=Yb， YAYS=C Y， YS 0 则则原
9、原问问题题单单纯纯形形表表的的检检验验数数行行对对应应其其对对偶偶问问题题的的一个基解，对应关系如下表：一个基解，对应关系如下表：XBXNXs0CNCBB-1NCBB-1Ys1Ys2Y证证: CBB-1A(0，CN+CBB-1N)= CBB-1(B，N)(0，CN+CBB-1N)=(CB， CN)=C对偶理论与灵敏度分析课件5 对偶问题的经济解释对偶问题的经济解释影子价格影子价格 设设B是是线线性性规规划划问问题题的的一一可可行行基基，这这目目标标函函数为数为 所所以以变变量量yi的的经经济济意意义义是是在在其其他他条条件件不不变变的的情情况况下下，单单位位资资源源变变化化所所引引起起的的目目
10、标标函函数数值值的的变变化。化。 yi的的值值代代表表对对第第i种种资资源源的的估估价价。这这种种估估价价是是针针对对具具体体工工厂厂的的具具体体产产品品而而存存在在的的一一种种特特殊殊价价格格，称它为称它为“影子价格影子价格”。对偶理论与灵敏度分析课件Q2 (4, 2)X2X10 1 2 3 4 54321Q1(4, 0)Q3(2, 3)Q4(0, 3)OQ4Q2Q3*A增加增加4，利润增加，利润增加41/8=1/2设备增加设备增加2，利润增加，利润增加23/2=3Q (5, 3/2)Q (4, 3)对偶理论与灵敏度分析课件6 对偶单纯形法对偶单纯形法bXBXNXsXBB-1b IB-1NB
11、-1-zCBB-1b0CN-CBB-1N-CBB-1-Ys1-Ys2-YXBbXBXNXsXBB-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1 0变为0变为 00单单纯纯形形法法对对偶偶单单纯纯形形法法对偶理论与灵敏度分析课件 对偶单纯形法的计算步骤：对偶单纯形法的计算步骤： 1. 确确定定初初始始的的基基，使使非非基基变变量量的的检检验验数数小小于于等等于于零。零。 2. 若若b 0,则则已已求求得得最最优优解解，停停止止计计算算，否否则则进进行行下一步。下一步。 3. 确定换出变量。计算确定换出变量。计算 min(B-1b)i| (B-1b)i0= (B-1b)l则
12、则xl为换出变量。为换出变量。 4. 确确定定换换入入变变量量。若若所所有有aij 0，则则无无可可行行解解，停停止计算；否则计算止计算；否则计算 =minj /alj| alj0= k /alk则则xk为换入变量。为换入变量。 5. 以以alk为主元素进行迭代。为主元素进行迭代。 6. 重复重复25步。步。对偶理论与灵敏度分析课件例：例：对偶理论与灵敏度分析课件 -2 -3 -4 0 0 -3 -1 -2 -1 1 0 -4 -2 1 -3 0 1 -1 0 -5/2 1/2 1 -1/2 2 1 -1/2 3/2 0 -1/2 2/5 0 1 -1/5 -2/5 1/511/5 1 0 7
13、/5 1/5 -2/5 0 -4 -1 0 -1 0 0 -3/5 -8/5 -1/5 1 -3 4/3 / 0 / 8/5 -2 0 2对偶理论与灵敏度分析课件7 灵敏度分析灵敏度分析 灵敏度分析的内容：灵敏度分析的内容： 1. 当当决决定定线线性性规规划划问问题题的的参参数数aij，bi，cj有有一一个个或或几几个个发发生生变变化化时时，已已求求得得的的线线性性规规划划问问题题的的最优解会有什么变化。最优解会有什么变化。 2. 当当决决定定线线性性规规划划问问题题的的参参数数aij，bi，cj在在什什么么范范围围内内变变化化时时，线线性性规规划划问问题题的的最最优优解解或或最最优优基不变。
14、基不变。对偶理论与灵敏度分析课件 7.1 资源数量变化的分析资源数量变化的分析 设设b变化为变化为b+b ，这时最终单纯形表变为，这时最终单纯形表变为XBbXBXNXsB-1b+ B-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1 当当B-1(b+b) 0时，最优基不变时，最优基不变; 当当B-1(b+b)中有负分量时，可利用对偶单中有负分量时，可利用对偶单纯形法求解。纯形法求解。 对偶理论与灵敏度分析课件 例：第一章例例：第一章例1中，若该厂又从别处抽出中，若该厂又从别处抽出4台时用于台时用于生产，求这时该厂生产的最优方案。生产，求这时该厂生产的最优方案。解：计算解：计
15、算B-1b4 1 0 0 1/4 0 2 0 0 1 -1/4 -1/2 3 0 1 0 0 1/4 -17 0 0 0 -1/2 -3/4 / / 3/4 -1/4 0 +0- 8+24 1 0 0 1/4 0 4 0 0 -2 1/2 1 2 0 1 1/2 -1/8 0 -14 0 0 -3/2 -1/8 0 4-4 4对偶理论与灵敏度分析课件 例：第一章例例：第一章例1中，资源中，资源A在什么范围内变化在什么范围内变化最优基不变。最优基不变。 解：资源解：资源A的变化量的变化量b满足下式时最优基不满足下式时最优基不变。变。对偶理论与灵敏度分析课件 7.2 目标函数中价值系数目标函数中价
16、值系数cj的变化的变化 1. 若若cj是是非非基基变变量量xj 的的系系数数，则则当当CN变变化化CN 后，最终单纯形表的检验数行变为后，最终单纯形表的检验数行变为:XBbXBXNXsB-1bIB-1NB-1-zCBB-1b0CN+CN -CBB-1N-CBB-1 当当CN+CN -CBB-1N 0时，最优解不变；时，最优解不变； 当当CN+CN -CBB-1N 中中有有正正分分量量时时，可可利利用用单单纯形法求解。纯形法求解。对偶理论与灵敏度分析课件 2. 若若cj是是基基变变量量xj 的的系系数数，则则当当CB变变化化CB后，最终单纯形表的检验数行变为后，最终单纯形表的检验数行变为:XBb
17、XBXNXsB-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1 当非基变量检验数当非基变量检验数0时，最优解不变；时，最优解不变； 当非基变量检验数中有正分量时，可利用单当非基变量检验数中有正分量时，可利用单纯形法求解。纯形法求解。-z CBB-1b- CBB-1b0CN-CBB-1N- CBB-1N-CBB-1- CBB-1CB对偶理论与灵敏度分析课件 例例：第第一一章章例例1中中，基基变变量量x2在在目目标标函函数数中中的的系系数数c2在什么范围内变化最优解不变。在什么范围内变化最优解不变。 解：基变量解：基变量x2 在目标函数中的系数在目标函数中的系数c2的变化量的
18、变化量c2满满足下式时最优解不变。足下式时最优解不变。 4 1 0 0 1/4 0 4 0 0 -2 1/2 1 2 0 1 1/2 -1/8 0 -14 0 0 -3/2 -1/8 0 0 0 -3/2- -1/8+ 0 c2 /2 c2 /8c22+c2对偶理论与灵敏度分析课件 例例：第第一一章章例例1中中，出出售售资资源源A可可获获利利1/2元元，这这是是最优解发生什么变化。最优解发生什么变化。 解：当解：当 c4=1/2时，单纯形表为：时，单纯形表为： 4 1 0 0 1/4 0 4 0 0 -2 1/2 1 2 0 1 1/2 -1/8 0 -14 0 0 -3/2 -1/8 0 +
19、1/2 3/8 16 8-162 1 0 2 0 -1/2 8 0 0 -4 1 2 3 0 1 0 0 -1/4 -17 0 0 0 0 -3/4对偶理论与灵敏度分析课件7.3 技术系数技术系数aij的变化的变化 1. 增增加加一一列列Pn+1。则则最最终终单单纯纯形形表表增增加加一一列列B-1Pn+1，检验数为检验数为n+1= cn+1-CBB-1Pn+1例例：第第一一章章例例1中中，该该厂厂开开发发一一种种新新产产品品，已已知知生生产产新新产产品品,每每件件需需消消耗耗原原材材料料A，B各各为为6kg，3kg，使使用用设设备备2台台时时;每每件件可可获获利利5元元。问问该该厂厂是是否否应
20、应该该生生产产该该产品和生产多少？产品和生产多少？解：计算解：计算对偶理论与灵敏度分析课件 4 1 0 0 1/4 0 4 0 0 -2 1/2 1 2 0 1 1/2 -1/8 0 -14 0 0 -3/2 -1/8 0 5/4 8/3 2 81 1 0 3/2 -1/8 -3/4 0 2 0 0 -1 1/4 1/2 1 3/2 0 1 3/4 -3/16 -1/8 0-16.5 0 0 -1/4 -7/16 -5/8 0 3/2 2 1/4对偶理论与灵敏度分析课件 2. 改改变变一一列列Pj。若若 Pj变变为为Pj，则则最最终终单单纯纯形形表表增增加加一一列列B-1Pj，检检验验数数为为
21、j= cj -CBB-1Pj ，删除一列删除一列Pj。 例例：第第一一章章例例1中中，该该厂厂生生产产产产品品的的工工艺艺结结构构有有了了改改进进，已已知知生生产产产产品品,每每件件需需消消耗耗原原材材料料A，B各各为为5kg，2kg，使使用用设设备备2台台时时;每每件件可可获获利利4元元。试试分分析析对对原原最最优计划有什么影响？优计划有什么影响？ 解：计算解：计算对偶理论与灵敏度分析课件 4 1 0 0 1/4 0 4 0 0 -2 1/2 1 2 0 1 1/2 -1/8 0 -14 0 0 -3/2 -1/8 0 3/816/5 1 0 0 1/5 012/5 0 0 -2 2/5 1
22、 4/5 0 1 1/2 -1/5 0-15.2 0 0 -3/2 -1/5 0 5/4 1/2 3/84 对偶理论与灵敏度分析课件 例例：第第一一章章例例1中中，该该厂厂生生产产产产品品的的工工艺艺结结构构有有了了改改进进，已已知知生生产产产产品品,每每件件需需消消耗耗原原材材料料A，B各各为为5kg，2kg，使使用用设设备备4台台时时;每每件件可可获获利利4元。试分析对原最优计划有什么影响？元。试分析对原最优计划有什么影响？ 解：计算解：计算对偶理论与灵敏度分析课件 4 1 0 0 1/4 0 4 0 0 -2 1/2 1 2 0 1 1/2 -1/8 0 -14 0 0 -3/2 -1/8 0 -21/816/5 1 0 0 1/5 076/5 0 0 -2 6/5 1 -12/5 0 1 1/2 -2/5 0-15.2 0 0 -3/2 2/5 0 5/4 -7/2 11/84 0 -1 -1/2 2/5 012/5 0 0 1-M 0 -M -3/2- 2/5+ 0 0 M/2 2M/5 对偶理论与灵敏度分析课件
