下载文档原格式
![[经济学]单纯形法与对偶问题](https://uimg.taocdn.com/0043005331b765ce05081479.webp)
对偶单纯形法与单纯形法对比分析1．教学目标：通过对偶单纯形法的学习，加深对对偶问题的理解2．教学内容：1）对偶单纯形法的思想来源 2）对偶单纯形法原理3．教学进程：1）讲述对偶单纯形法解法的来源：所谓对偶单纯形法，就是将单纯形法应用于对偶问题的计算，该方法是由美国数学家C.莱姆基于1954年提出的，它并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。
2）为什么要引入对偶单纯形法：单纯形法是解线性规划的主要方法，对偶单纯形法则提高了求解线性规划问题的效率，因为它具有以下优点： （1）初始基解可以是非可行解, 当检验数都为负值时, 就可以进行基的变换, 不需加入人工变量, 从而简化计算； （2）对于变量多于约束条件的线性规划问题,用对偶单纯形法可以减少计算量,在灵敏度分析及求解整数规划的割平面法中,有时适宜用对偶规划单纯形法。
由对偶问题的基本性质可以知道，线性规划的原问题及其对偶问题之间存在一组互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w 。
据此可知，用单纯形法求解线性规划问题时，在得到原问题的一个基可行解的同时，在检验数行得到对偶问题的一个基解，并且将两个解分别代入各自的目标函数时其值相等。
我们知道，单纯形法计算的基本思路是保持原问题为可行解（这时一般其对偶问题为非可行解）的基础上，通过迭代，增大目标函数，当其对偶问题的解也为可行解时，就达到了目标函数的最优值。
那么对偶单纯形法的基本思想可以理解为保持对偶问题为可行解（这时一般原问题为非可行解）的基础上，通过迭代，减小目标函数，当原问题也达到可行解时，即达到了目标函数的最优值。
其实对偶单纯形法本质上就是单纯形法, 只不过在运用时需要将单纯形表旋转一下而已。
第六章 单纯形法的灵敏度分析与对偶• §1 单纯形表的灵敏度分析 • §2 线性规划的对偶问题 • §3 对偶规划的基本性质 • §4 对偶单纯形法§1 单纯形表的灵敏度分析一、目标函数中变量C k系数灵敏度分析1. 在最终的单纯形表里，X k 是非基变量由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与C k 没有任何关系，所以当C k 变成C k +ΔC k 时，在最终单纯形表中其系数的增广矩阵不变，又因为X k 是非基变量，所以基变量的目标函数的系数不变，即C B 不变，可知Z k 也不变，只是C k 变成了C k +ΔC k 。
这时δK = C k -Z k 就变成了C k +ΔC k - Z k =δK +ΔC k 。
要使原来的最优解仍为最优解，只要δK + ΔC k ≤0即可，也就是C k 的增量ΔC k ≤—δK 。
2. 在最终的单纯形表中， X k 是基变量当C k 变成C k + ΔC k 时，最终单纯形表中约束方程的增广矩阵不变，但是基变量的目标函数的系数C B 变了，则Z J (J=1,2,…,N)一般也变了，不妨设C B =(C B1, C B2…, C k ,…，C Bm )，当C B 变成=(C B1, C B2…,C k + ΔC k ,…,C Bm )，则：Z J =(C B1, C B2…, C k ,…，C Bm )(a’1j , a’2j ,…, a’Kj ,…, a’mj )Z’J =(C B1, C B2…, C k +ΔC k ,…，C Bm )(a’1j , a’2j ,…, a’Kj ,…, a’mj ) T = Z J + ΔC k a’Kj根据上式可知检验数δJ (J=1,2,…..,M)变成了δ’J ，有δ’ J =C J -Z’J =δJ +ΔC K a’Kj 。
要使最优解不变，只要当J ≠K 时，δ’J <=0⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧>-≤≤⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧<--≥-≤===⋅--+=-+==≤--≥<≥--≤>-≤≤+0a'a'δMin ΔC 0a'a'δMax ΔC a'δΔC a'0a'δΔC a'0a'0δ'1a'0δX ,a'ΔC Z ΔC C 'Z ΔC C δ'k j ;0a'δ,a'δΔC ,0a';0a'δ,a'δΔC ,0a'δa'ΔC 0,a'ΔC δkj kj jk kj kj j kkjjkkjkjj k kjkkkkkkK kk k k k k k k k k kjj kjj k kj kj j kj j k kj jkj k kj k j 的变化范围为，所以可知满足的，所有小于，满足的以外的所有大于于除了要使得最优解不变，对。
《管理运筹学》第四版课后习题解析第6章单纯形法的灵敏度分析与对偶1．解： （1）c 1≤24 （2）c 2≥6 （3）c s 2≤82．解：（1）c 1≥−0.5 （2）−2≤c 3≤0 （3）c s 2≤0.53．解：（1）b 1≥250 （2）0≤b 2≤50 （3）0≤b 3≤1504．解： （1）b 1≥−4 （2）0≤b 2≤10 （3）b 3≥45. 解：最优基矩阵和其逆矩阵分别为：⎪⎪⎭⎫ ⎝⎛=1401B ，⎪⎪⎭⎫ ⎝⎛-=-14011B ； 最优解变为130321===x x x ，，最小值变为-78； 最优解没有变化； 最优解变为2140321===x x x ，，，最小值变为-96；6．解：（1）利润变动范围c 1≤3，故当c 1=2时最优解不变。
（2）根据材料的对偶价格为1判断，此做法有利。
（3）0≤b 2≤45。
（4）最优解不变，故不需要修改生产计划。
（5）此时生产计划不需要修改，因为新的产品计算的检验数为−3小于零，对原生产计划没有影响。
7. 解：(1)设321,,x x x 为三种食品的实际产量，则该问题的线性规划模型为,, 4005132 4505510 35010168 325.2max 321321321321321≥≤++≤++≤++++=x x x x x x x x x x x x x x x z 约束条件：解得三种食品产量分别为0,75.43321===x x x ，这时厂家获利最大为109.375万元。
(2)如表中所示，工序1对于的对偶价格为0.313万元，由题意每增加10工时可以多获利3.13万元，但是消耗成本为10万元，所以厂家这样做不合算。
（3）B 食品的加工工序改良之后，仍不投产B ，最大利润不变；若是考虑生产甲产品，则厂家最大获利变为169.7519万元，其中667.31110,167.144321====x x x x ，，；（4）若是考虑生产乙产品，则厂家最大获利变为163.1万元，其中382.70,114321====x x x x ，，；所以建议生产乙产品。
