第三章对偶理论与灵敏度分析课件

1、第三章 对偶理论与灵敏度分析1 单纯形法的矩阵描述2 改进单纯形法3 对偶问题的提出4 线性规划的对偶理论5 对偶问题的经济解释影子价格6 对偶单纯形法7 灵敏度分析第三章 对偶理论与灵敏度分析1 单纯形法的矩阵描述1 单纯形法的矩阵描述设线性规划问题设B是一个可行基，令（A，I）=（B，N，I），则：1 单纯形法的矩阵描述设线性规划问题设B是一个可行基，令1. 检验数的矩阵描述： B=CB-CBB-1B=0 N=CN-CBB-1N S=-CBB-1 =min(B-1b)i/ (B-1Pk)i| (B-1Pk)i0= (B-1b)l / (B-1Pk)lXBbXBXNXsB-1bIB-1NB-

2、1(B-1 b)i (B-1Pk)i-zCBB-1b0CN-CBB-1N-CBB-13. 单纯形表的矩阵描述：=C-CBB-1A2.的矩阵描述：1. 检验数的矩阵描述：=min(B-1b)i/ (B-2 改进单纯形法用改进单纯形法求解线性规划问题的计算步骤：1. 确定初始可行基B1。求出B1-1；2. 计算非基变量的检验数N 。若N 0已求的最优解，停止计算,否则进行下一步；3. 确定换入变量 xk；4. 计算B1-1b， B1-1 Pk及；若 0那么无最优解，停止计算，否则进行下一步；5.确定换出变量 xl;6. 计算B2-1；7. 重复27步。2 改进单纯形法用改进单纯形法求解线性规划问题

3、的计算步骤 例：用改进单纯形法求解 例：用改进单纯形法求解解： 解： 3 对偶问题的提出 例： 设备原材料A原材料B1402048 台时16 kg12 kg利润23x1minx2x1x2y1y2y33 对偶问题的提出 例： 设备128 台当该问题达到最优时有： z的上界为无限大，所以只存在最小值。于是得到另一个线性规划问题对线性规划问题对偶问题原问题当该问题达到最优时有： z的上界为无限大，所以只4 线性规划的对偶理论 4.1 原问题与对偶问题的关系4 线性规划的对偶理论 4.1 原问题与对偶原问题（对偶问题）对偶问题（原问题）例：23-51原问题（对偶问题）对偶问题（原问题）例：23-51第

4、三章对偶理论与灵敏度分析课件第三章对偶理论与灵敏度分析课件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* CX* Y*AX* Y*bCX*Y*b4.2 对偶问题的性质CX*Y*b3. 无界性 若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。4. 可行解是最优解的性质 设X是原问题的可行解，

5、Y是对偶问题的可行解，当CX= Yb时， X， Y是最优解。5. 对偶定理 若原问题有最优解，则对偶问题也有最优解，且目标函数相等。6. 互补松驰性 若X是原问题的可行解，Y是对偶问题的可行解，那么YXs=0，Ys X=0，当且仅当 X， Y为最优解。3. 无界性 若原问题（对偶问题）为无界解，则其对偶问题（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

6、 =Y(AX+XS)=YAX+YXS X是原问题的可行解，Y是对偶问题的可行解 z =YAXYS X =YAX+YXS当YXs=0，Ys X=0时z =，则X，Y是最优解。当 X，Y是最优解时 z = ，则YXs=0，Ys X=0 6. 互补松驰性 若X是原问题的可行解，Y是对偶问题例：已知线性规划问题max其对偶问题的最优解为试用对偶理论求原问题的最优解解：max例：已知线性规划问题max其对偶问题的最优解为试用对偶理论求 7. 设原问题及对偶问题的标准型是 max z =CX， AX+XS=b， X， XS 0 min=Yb， YAYS=C Y， YS 0 则原问题单纯形表的检验数行对应其

7、对偶问题的一个基解，对应关系如下表：XBXNXs0CNCBB-1NCBB-1Ys1Ys2Y证: CBB-1A(0，CN+CBB-1N)= CBB-1(B，N)(0，CN+CBB-1N)=(CB， CN)=C 7. 设原问题及对偶问题的标准型是XBXNX5 对偶问题的经济解释影子价格 设B是线性规划问题的一可行基，这目标函数为 所以变量yi的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函数值的变化。 yi的值代表对第i种资源的估价。这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。5 对偶问题的经济解释影子价格 设B是Q2 (4, 2)X2X10 1 2 3

8、 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)Q2 (4, 2)X2X10 1 6 对偶单纯形法bXBXNXsXBB-1b IB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1-Ys1-Ys2-YXBbXBXNXsXBB-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1 0变为0变为 00单纯形法对偶单纯形法6 对偶单纯形法bXBXNXsXBB-1b IB-1 对偶单纯形法的计算步骤： 1. 确定初始的基，使非基变量的检验数小于

9、等于零。 2. 若b 0,则已求得最优解，停止计算，否则进行下一步。 3. 确定换出变量。计算 min(B-1b)i| (B-1b)i0= (B-1b)l则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

10、/5 1/511/5 1 0 7/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 -2 -3 7 灵敏度分析 灵敏度分析的内容： 1. 当决定线性规划问题的参数aij，bi，cj有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化。 2. 当决定线性规划问题的参数aij，bi，cj在什么范围内变化时，线性规划问题的最优解或最优基不变。7 灵敏度分析 灵敏度分析的内容： 7.1 资源数量变化的分析 设b变化为b+b ，这时最终单纯形表变为XBbXBXNXsB-1b+ B-1bIB-1NB-1-z

11、CBB-1b0CN-CBB-1N-CBB-1 当B-1(b+b) 0时，最优基不变; 当B-1(b+b)中有负分量时，可利用对偶单纯形法求解。 7.1 资源数量变化的分析XBbXBXNX 例：第一章例1中，若该厂又从别处抽出4台时用于生产，求这时该厂生产的最优方案。解：计算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

12、 例：第一章例1中，若该厂又从别处抽出4台时 例：第一章例1中，资源A在什么范围内变化最优基不变。 解：资源A的变化量b满足下式时最优基不变。 例：第一章例1中，资源A在什么范围内变化最优 7.2 目标函数中价值系数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 中有正分量时，可利用单纯形法求解。 7.2 目标函数中价值系数cj的变化XB 2. 若cj是基变量xj 的

13、系数，则当CB变化CB后，最终单纯形表的检验数行变为:XBbXBXNXsB-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1 当非基变量检验数0时，最优解不变； 当非基变量检验数中有正分量时，可利用单纯形法求解。-z CBB-1b- CBB-1b0CN-CBB-1N- CBB-1N-CBB-1- CBB-1CB 2. 若cj是基变量xj 的系数，则当CB变 例：第一章例1中，基变量x2在目标函数中的系数c2在什么范围内变化最优解不变。 解：基变量x2 在目标函数中的系数c2的变化量c2满足下式时最优解不变。 4 1 0 0 1/4 0 4 0 0 -2 1/2 1 2 0

14、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中，基变量x2在目标函数中的系 例：第一章例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 +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 例：第一章例1中，出售资

15、源A可获利1/2元，7.3 技术系数aij的变化 1. 增加一列Pn+1。则最终单纯形表增加一列B-1Pn+1，检验数为n+1= cn+1-CBB-1Pn+1例：第一章例1中，该厂开发一种新产品，已知生产新产品,每件需消耗原材料A，B各为6kg，3kg，使用设备2台时;每件可获利5元。问该厂是否应该生产该产品和生产多少？解：计算7.3 技术系数aij的变化 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/

16、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 4 1 0 2. 改变一列Pj。若 Pj变为Pj，则最终单纯形表增加一列B-1Pj，检验数为j= cj -CBB-1Pj ，删除一列Pj。 例：第一章例1中，该厂生产产品的工艺结构有了改进，已知生产产品,每件需消耗原材料A，B各为5kg，2kg，使用设备2台时;每件可获利4元。试分析对原最优计划有什么影响？ 解：计算 2. 改变一列Pj。若 Pj变为Pj，则最 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 4/5 0 1 1/2 -1/5 0-15.2 0 0 -3/2 -1/5 0 5/4 1/2 3/84 4 1 0 例：第一章例1中，该厂生产产品的工艺结构有了改进，已知生产产品,每件需消耗原材料A，B各为5kg，2kg，使用设备4台时;每件可获利4元。试分析对