运筹学基础-对偶理论与灵敏度分析.pptx

运筹学基础毕德春毕德春辽东学院信息技术学院辽东学院信息技术学院第3章 对偶理论与灵敏度分析 线性规划线性规划对偶问题的引入与数学模型对偶问题的引入与数学模型 线性规划线性规划的的对偶对偶单纯形法单纯形法第1节 性规划对偶问题的引入与数学模型1 1对偶问题的提出 1.1.1 1.1.1 引例引例第1节 性规划对偶问题的引入与数学模型对偶问题的提出 例：例：常山机械厂生产和两种产品。生产中需使用A、B、C三种设备进行加工，加工每件产品或产品所需的设备机时数、利润值及每种设备可利用机时数列于下表，请问：充分利用设备机台时，工厂应生产和产品各多少件才能获得最大利润？试列出相应的线性规划数学模型。ABC产品利润（元件）24022053设备可用机时数（工时）121615解：解：设、产品的生产数量分别为x1和x2，建立问题数学模型如下：max z=2x1+3x2 2x1+2x212 4x1 16 5x2 15 xj0，j=1，2现假设有另一家四海机器厂，为了扩大生产想租借常山机器厂拥有的设备资源，问常山厂分别以每小时什么样的价格才愿意出租自己的设备呢？1.1.1 1.1.1 引例引例第1节 性规划对偶问题的引入与数学模型对偶问题的提出 设A、B、C设备的机时单价分别为y1、y2、y3，新的线性规划数学模型为min w=12y1+16y2+15y32y1+4y2 22y1 +5y33yj0，j=1，2，3A（y1）B（y2）C（y3）产品利润（元件）（x1）2402（x2）2053设备可用机时数（工时）121615max z=2x1+3x2 2x1+2x212 4x1 16 5x2 15 xj0，j=1，21.1.1 1.1.1 引例引例第1节 性规划对偶问题的引入与数学模型对偶问题的提出 23x1 x2 原问题12y1 221216y2 401615y30515对偶问题231.1.2 1.1.2 原原问题与对偶问题的形式问题与对偶问题的形式关系关系第1节 性规划对偶问题的引入与数学模型对偶问题的提出 X1 ,X2 ,Xnxjyi对偶问题 原问题 Min wMax ZMax Z=Min w1.1.2 1.1.2 原原问题与对偶问题的形式问题与对偶问题的形式关系关系第1节 性规划对偶问题的引入与数学模型对偶问题的提出 原始问题max z=CXs.t.AXbX 0对偶问题min w=bTYs.t.ATYCT Y 0maxbACCTATbTminmnmn1.1.2 1.1.2 原原问题与对偶问题的形式问题与对偶问题的形式关系关系第1节 性规划对偶问题的引入与数学模型对偶问题的提出 max z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm xj 0（j=1,2,n）min w=b1 y1+b2 y2+bm yms.t.a11y1+a21 y2+am1ym c1 a12y1+a22y2 +am2 ym c2 a1ny1+a2ny2+amnym cn yi 0（i=1,2,m）设设原原 LP LP 问题为问题为则称下列则称下列 LP LP 问题问题1.1.2 1.1.2 原原问题与对偶问题的形式问题与对偶问题的形式关系关系第1节 性规划对偶问题的引入与数学模型对偶问题的提出 例：例：写出下列线性规划问题的对偶问题min w=12x1+8x2+16x3+12x4 s.t.2x1+x2+4x3 2 2x1+2x2 +4x4 3 x1，x2，x3，x4 0解：该问题的对偶问题：max z=2y1+3y2 s.t.2y1+2y2 12 y1+2y2 8 4 y1 16 4y2 12 y1，y2 0y1y21.1.2 1.1.2 原原问题与对偶问题与对偶问题的形式关系问题的形式关系第1节 性规划对偶问题的引入与数学模型对偶问题的提出 例：例：写出下列线性规划问题的对偶问题 max z=10 x1+x2 +2x3 s.t.x1+x2+2x3 10 y1 4x1+2x2 -x3 20 y2 x1，x2，x3 0解：解：该问题的对偶问题：min w=10 y1+20 y2 s.t.y1+4y2 10 y1+2y2 1 2 y1-y2 2 y1，y2 01.1.2 1.1.2 原原问题与对偶问题与对偶问题的形式关系问题的形式关系第1节 性规划对偶问题的引入与数学模型对偶问题的提出 例：例：写出下列线性规划问题的对偶问题 min w=x1+2x2+3x3s.t.2x1+3x2+5x3 2 3x1+x2+7x3 3 x1，x2，x3 0解：解：用（-1）乘以第二个约束方程两边 min w=x1+2x2+3x3s.t.2x1+3x2+5x3 2 y1 -3x1-x2-7x3 -3 y2 x1，x2，x3 0该问题的对偶问题：max z=2 y1-3y2 s.t.2y1-3y2 1 3y1-y2 2 5y1-7y2 3 y1，y2 01.1.2 1.1.2 原原问题与对偶问题与对偶问题的形式关系问题的形式关系第1节 性规划对偶问题的引入与数学模型对偶问题的提出 解：解：化为对称形式。max x10,x20,x3 无约束s.t.a11x1+a12x2+a13x3 b1z=c1x1+c2x2+c3x3 a31x1+a32x2+a33x3 b3 a21x1+a22x2+a23x3=b2令令maxs.t.例：例：写出下述线性规划问题的对偶问题1.1.2 1.1.2 原原问题与对偶问题与对偶问题的形式关系问题的形式关系第1节 性规划对偶问题的引入与数学模型对偶问题的提出 maxs.t.对偶变量mins.t.对偶问题：1.1.2 1.1.2 原原问题与对偶问题与对偶问题的形式关系问题的形式关系第1节 性规划对偶问题的引入与数学模型对偶问题的提出 maxs.t.对偶变量mins.t.对偶问题：1.1.2 1.1.2 原原问题与对偶问题与对偶问题的形式关系问题的形式关系第1节 性规划对偶问题的引入与数学模型对偶问题的提出 原问题（对偶问题）对偶问题（原问题）A约束系数矩阵约束系数矩阵的转秩b约束条件右端项向量目标函数中价格系数向量c目标函数中价格系数向量约束条件右端项向量目标函数变量 xj(j=1,n)约束条件有n个xj 0cjxj 0cjxj 无约束=cj约束条件有m个变量有m个yi(i=1,m)biyi0biyi0=biyi无约束1.1.2 1.1.2 原原问题与对偶问题与对偶问题的形式关系问题的形式关系第1节 性规划对偶问题的引入与数学模型对偶问题的提出 例：例：写出原问题的对偶问题min z=7x1+4x2-3x3 -4x1+2x2-6x324 -3x1-6x2-4x3 15 5x2+3x3=30 x1 0 x2无符号限制 x3 0 max w=24y1+15y2+30y3 y1 0 y20 y3无符号限制 -4y1-3y2 72 2y1-6y2+5y3 =4 -6y1 -4y2+3y3 -3 1.1.2 1.1.2 原原问题与对偶问题与对偶问题的形式关系问题的形式关系第1节 性规划对偶问题的引入与数学模型对偶问题的提出 例：例：写出(P)问题的(D)问题max z=2x1+3x2-5x3+x4 s.t.4x1+x2-3x3+2x4 5 3x1-2x2 +7x4 4 -2x1+3x2+4x3+x4=6 x1 0,x2,x3 0,x4 无符号限制min w=5y1+4y2+6y3 s.t.4y1+3y2-2y3 2 y1-2y2+3y3 3 -3y1 +4y3 -5 2y1+7y2+y3=1 y1 0,y20,y3无符号限制1.1.2 1.1.2 原原问题与对偶问题与对偶问题的形式关系问题的形式关系第1节 性规划对偶问题的引入与数学模型对偶问题的提出 2 2对偶问题的基本性质 min Z=-CXs.t.-AX-bX 0对偶对偶问题的对偶是原问题。问题的对偶是原问题。min W=Y bs.t.YA C Y 0max Z=C Xs.t.AXb X 0对偶的定义对偶的定义max W=-Ybs.t.YA C Y 01.2.1 1.2.1 对称性对称性第1节 性规划对偶问题的引入与数学模型对偶问题的基本性质 设 和 分别是问题（P）和（D）的可行解，则必有1.2.2 1.2.2 弱弱对偶性对偶性第1节 性规划对偶问题的引入与数学模型对偶问题的基本性质 ZYX在Y=0的平面上鞍点是z=f(0,y)的极大值点XYZ在X=0的平面上鞍点是z=f(0,y)的极小值点1.2.2 1.2.2 弱弱对偶性对偶性第1节 性规划对偶问题的引入与数学模型对偶问题的基本性质 在一对对偶问题中，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。原问题对偶问题问题无界无可行解无可行解问题无界1.2.3 1.2.3 无无界性界性第1节 性规划对偶问题的引入与数学模型对偶问题的基本性质 和 分别是原问题和其对偶问题的最优解。若对偶变量 ，则原问题相应的约束条件若约束条件 ，则相应的对偶变量1.2.4 1.2.4 互补互补松弛性松弛性第1节 性规划对偶问题的引入与数学模型对偶问题的基本性质 例：例：给定线性规划问题min z=2x1+3x2+x3 3x1-x2+x3 1 x1+2x2 -3x3 2 x1,x2,x3 0已知对偶问题的最优解为y=（y1,y2）T=（1/7,11/7）试用互补松弛性质，求原问题的最优解。1.2.4 1.2.4 互补互补松弛性松弛性第1节 性规划对偶问题的引入与数学模型对偶问题的基本性质 解：解：先写出它的对偶问题max w=y1+2y2 3y1 +y2 2 -y1+2y2 3 y1 -3y2 1 y1,y2 0将最优解y=（y1,y2）T=（1/7,11/7）代入上面的线性规划中，第三个约束条件严格不等，说明x3=0,第一、二个约束条件严格取等，说明，x1=4/7,x2=5/71.2.4 1.2.4 互补互补松弛性松弛性第1节 性规划对偶问题的引入与数学模型对偶问题的基本性质 例例：已知线性规划问题 Min.Z=2x1+3x2+5x3+2x4 +3x5 S.t.x1+x2+2x3+x4+3x5 4 2x1 x2+3x3+x4+x5 3 xi 0(i=1,2,3,4,5)已知对偶问题的最优解为 y1=4/5,y2=3/5,试应用对偶理论解原问题。1.2.4 1.2.4 互补互补松弛性松弛性第1节 性规划对偶问题的引入与数学模型对偶问题的基本性质 221/5 317/557/5 23=3将y1、y2的值代入，得知、为严格不等式，于是由互补松弛定理知，必有x2=x3=x4=0；又因y1,y2 0，故原问题的两个约束必为紧约束，于是有：x1+3x5=4 2x1+x5 =3解之，x1=x5=1。Z(1,0,0,0,1)=5解解：写出对偶问题为：Max.S=4y1+3y2S.t.y1+2y2 2 y1 y2 3 2y1+3y2 5 y1+y2 2 3y1+y2 3 y1,y2 01.2.4 1.2.4 互补互补松弛性松弛性第1节 性规划对偶问题的引入与数学模型对偶问题的基本性质 例例：已知线性规划问题试通过求对偶问题的最优解来求解原问题的最优解。1.2.4 1.2.4 互补互补松弛性松弛性第1节 性规划对偶问题的引入与数学模型对偶问题的基本性质 用图解法求出：Y*=（1.3），W=11。将y*1=1，y*2=3 代入对偶约束条件，（1）（2）（5）式为紧约束，（3）（4）为松约束。令原问题的最优解为X*=（x1.x2.x3.x4.x5），则根据互补松弛条件，必有x3=x4=0(1.3)（1）（2）（3）（4）（5）解：解：对偶问题为1.2.4 1.2.4 互补互补松弛性松弛性第1节 性规划对偶问题的引入与数学模型对偶问题的基本性质 又由于y*10，y*2 0，原问题的约束必为等式，即化简为此方程组为无穷多解令x5=0,得到x1=1，x2=2 即X*1=（1.2.0.0.0）为原问题的一个最优解，Z=11。再令 x5=2/3，得到x1=5/3，x2=0 即X*2（5/3.0.0.0.2/3）也是原问题的一个最优解，Z=11。1.2.4 1.2.4 互补互补松弛性松弛性第1节 性规划对偶问题的引入与数学模型对偶问题的基本性质 例：例：已知线性规划问题及其对偶问题max z=2x1+3x2+0 x3+0 x4+0 x5 2x1+2x2+x3 =12 y1 4x1 +x4 =16 y2 5x2+x5=15 y3 xj0min w=-12y1-16y2-15y3+0y4+0y5 -2y1-4y2 +y4 =-2 x1 -2y1 -5y3 +y5=-3 x2 yi 0分别求解，得到如下两个最优单纯形表。1.2.4 1.2.4 互补互补松弛性松弛性第1节 性规划对偶问题的引入与数学模型对偶问题的基本性质 基 b原问题变量原问题松弛变量x1 x2 x3 x4 x5x1 31 01/2 0 -1/5x4 40 0-2 1 4/5x2 30 10 0 1/50 01 0 1/5 变量对偶问题的剩余变量对偶问题变量y4 y5y1 y2 y3基 b对偶问题变量对偶问题的剩余变量y1 y2 y3 y4 y5y1 11 2 0-1/2 0 y2 1/50 -4/5 1 1/5 -1/50 4 0 3 3变量原问题松弛变量原问题变量x3 x4 x5 x1 x21.2.4 1.2.4 互补互补松弛性松弛性第1节 性规划对偶问题的引入与数学模型对偶问题的基本性质 w1 wi wm wm+1 wm+j wn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量 对偶问题的松弛变量 原始问题的变量 原始问题的松弛变量 xjwm+j=0，wixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于01.2.4 1.2.4 互补互补松弛性松弛性第1节 性规划对偶问题的引入与数学模型对偶问题的基本性质 3 3影子价格我们首先采用单纯形法求解得王老板的家具生产模型（P）的最优解、最优基矩阵如下（P）的最优解为X*=（15，20，0，0）TB=（p2，p1）=341 2（D）的最优解为Y*=CBB-1=（5，15）CB=（C2，C1）=（30，50）B-1=1 -2-1/2 3/2（P）max Z=50 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1，x2 0Z*=1350Y*=(5,15)1.3.1 1.3.1 影子价格影子价格 （Shadow PriceShadow Price）定义）定义第1节 性规划对偶问题的引入与数学模型影子价格 王老板的家具生产模型的图解：x1x2P可行域1350=50 x1+30 x2（15，20）（P）max Z=50 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1，x2 0Z*=1350Y*=(5,15)2x1+x2=504x1+3x2=120L0：50 x1+30 x21.3.1 1.3.1 影子价格影子价格 （Shadow PriceShadow Price）定义）定义第1节 性规划对偶问题的引入与数学模型影子价格 影子价格的直观含义：x1x24x1+3x2=1202x1+x2=50 L0：50 x1+30 x2 P可行域2x1+x2=51 4x1+3x2=1211365=50 x1+30 x21355=50 x1+30 x21.3.1 1.3.1 影子价格影子价格 （Shadow PriceShadow Price）定义）定义第1节 性规划对偶问题的引入与数学模型影子价格 （P）max Z=50 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1，x2 0Z*=1350Y*=(5,15)影子价格是对偶解的一个十分形象的名称，它既表明对偶解是对系统内部资源在当前的最优利用配置下的一种客观估价，又表明它是一种虚拟的价格（或价值的影象）而不是真实的价格。特点1、影子价格是对系统资源的一种内部最优估价，只有当系统 达到最优状态时才可能赋予资源这种价值。系统资源的一种动态价格体系，影子价格的大小与系统的价值取向有关，并受系统状态变化的影响。系统环境的任何变化都可能会引起影子价格的变化。1.3.2 1.3.2 影子价格影子价格的特点的特点第1节 性规划对偶问题的引入与数学模型影子价格 特点2、影子价格是一种边际价值，其与经济学中的边际成本的概念相同。因而，在经济管理有中十分重要的应用价值。企业管理者可以根据资源在企业内部的影子价格的大小决定企业的经营策略。影子价格yi相当于在资源得到最优利用的生产条件下，资源bi每增加一个单位，目标函数z 的增量。特点3、影子价格的大小客观地反映资源在系统内的稀缺程度。如果某种资源在系统内供大于求，尽管它有实实在在的市场价格，但它在系统内的影子价格却为零，而影子价格越高，资源在系统内越稀缺。当影子价格高于市场价格，应该买进资源；当影子价格高于市场价格，应该买进资源；当影子价格低于市场价格，应该卖出资源当影子价格低于市场价格，应该卖出资源；设备A:y1=0设备B:y2=0.25调试C:y3=0.51.3.2 1.3.2 影子价格影子价格的特点的特点第1节 性规划对偶问题的引入与数学模型影子价格 特点4、表明生产过程中该种资源的影子价格不等于0，表明生产过程中资源得到充分利用。如果某种资源未得到充分利用，该种资源的影子价格=0；1.3.2 1.3.2 影子价格影子价格的特点的特点第1节 性规划对偶问题的引入与数学模型影子价格 特点5、从影子价格考察单纯形表的计算。Cj代表第j种产品的产值，是生产该种产品所消耗各项资源的影子价格的总和，即产品的隐含成本。当产品产值大于隐含成本时，表明生产该产品有利。当产品产值小于隐含成本时，表明用资源生产别的产品有利。1.3.2 1.3.2 影子价格影子价格的特点的特点第1节 性规划对偶问题的引入与数学模型影子价格 第2节 线性规划的对偶单纯形法1 1对偶单纯形法思路我们前面介绍的一般单纯形法，是从“可行”(右端项非负）开始，逐步地迭代运算，直到得出最优解。而应用对偶规划的性质，可以找到一种求解线性规划的新方法对偶单纯形法。对偶单纯形法则是从“不可行”(右端项含负）开始，在保持最优性之下逐步迭代，直到不可行变为可行，即得到可行最优解为止。当对偶问题的约束条件的数目较原问题为少时，应用对偶单纯形法求解较为方便。2.1.1 2.1.1 对偶单纯形法思路对偶单纯形法思路第2节 线性规划的对偶理论对偶单纯形法思路 2.1.2 2.1.2 对偶单纯形法思路图解对偶单纯形法思路图解第2节 线性规划的对偶理论对偶单纯形法思路 始终满足对偶可行性最优解最优解基本可行性基本可行性对偶可行性对偶可行性初始对偶可行解初始对偶可行解保持为基本可行解保持为基本可行解原问题原问题初始基本可行解初始基本可行解始终满足解的可行性保持对偶可行性保持对偶可行性2 2对偶单纯形法示例例：例：用对偶单纯形法解下列线性规划问题 min w=12y1+16y2+15y3s.t.2y1+4y2 2 2y1 +5y3 3 y1，y2，y3 0解：解：此题可用人工变量方法求，但也可用对偶单纯形法。max w=-12y1-16y2 15y3s.t.-2y1-4y2 +y4 =-2 -2y1 -5y3 +y5=-3 y1，y2，y3，y4，y5 02.2.1 2.2.1 对偶单纯形法示例一对偶单纯形法示例一第2节 线性规划的对偶理论对偶单纯形法示例 列初始单纯形表列初始单纯形表2.2.1 2.2.1 对偶单纯形法示例一对偶单纯形法示例一第2节 线性规划的对偶理论对偶单纯形法示例 Cj12161500CBXBby1y2y3y4y500y4y5-2-3-2-2-400-51001-12-16-1500单纯形表迭代单纯形表迭代1 1次次2.2.1 2.2.1 对偶单纯形法示例一对偶单纯形法示例一第2节 线性规划的对偶理论对偶单纯形法示例 Cj12161500CBXBby1y2y3y4y500y4y5-2-3-2-2-400-51001-12-16-15000-15y4y3-23/5-22/5-4001100-1/5-6-1600-32.2.1 2.2.1 对偶单纯形法示例一对偶单纯形法示例一第2节 线性规划的对偶理论对偶单纯形法示例 Cj12161500CBXBby1y2y3y4y500y4y5-2-3-2-2-400-51001-12-16-15000-15y4y3-23/5-22/5-4001100-1/5-6-1600-3-12-15y1y311/5102-4/501-1/21/50-1/50-40-3-3Y*=(1,0,1/5,0,0)单纯形表迭代单纯形表迭代2 2次次例：用对偶单纯形法求解：解:（1）将模型转化为求最大化问题，约束方程化为等式求出一组基本解，因为对偶问题可行，即全部检验数0（求max问题）。2.2.2 2.2.2 对偶单纯形法示例对偶单纯形法示例二二第2节 线性规划的对偶理论对偶单纯形法示例 cj-9-12-15000bcBxBx1x2x3x4x5x60 x4-2-2-1100-100 x5-2-3-1010-120 x6-1-1-5001-14(-9/-1.-12/-1.-15/-5)j-9-12-1500002.2.2 2.2.2 对偶单纯形法示例对偶单纯形法示例二二第2节 线性规划的对偶理论对偶单纯形法示例 cj-9-12-15000bcBxBx1x2x3x4x5x60 x4-9/5-9/5010-1/5-36/50 x5-9/5-14/5001-1/5-46/5-15x31/51/5100-1/514/5(-30/-9,-45/-14,-15/-1)-6-9000-3422.2.2 2.2.2 对偶单纯形法示例对偶单纯形法示例二二第2节 线性规划的对偶理论对偶单纯形法示例 cj-9-12-15000bcBxBx1x2x3x4x5x60 x4-9/14001-9/14-1/14-9/7-12x29/14100-5/141/1423/7(-3/-9,-45/-9,-33/-1)-15x31/140101/14-3/1415/7-3/14000-45/14-33/142.2.2 2.2.2 对偶单纯形法示例对偶单纯形法示例二二第2节 线性规划的对偶理论对偶单纯形法示例 cj-9-12-15000cBxBx1x2x3x4x5x6b-9x1100-14/911/92-12x20101-102-15x30011/90-2/92000-1/3-3-7/3原问题的最优解为：X*=（2,2,2,0,0,0），Z*=72 其对偶问题的最优解为：Y*=（1/3,3,7/3），W*=722.2.2 2.2.2 对偶单纯形法示例对偶单纯形法示例二二第2节 线性规划的对偶理论对偶单纯形法示例 例：例：用对偶单纯形法解下列线性规划问题 min S=x1+4x2+3x4 s.t.x1+2x2 -x3+x4 3 -2x1-x2+4x3+x4 2 x1，x2，x3，x4 0解：解：用对偶单纯形法。max S=-x1-4x2-3x4 s.t.-x1-2x2 +x3-x4+x5 =-3 2x1+x2 -4x3-x4 +x6=-2 x1，x2，x3，x4，x5，x6 02.2.3 2.2.3 对偶单纯形法示例三对偶单纯形法示例三第2节 线性规划的对偶理论对偶单纯形法示例 计算检验数全为非正，称为对偶可行；而常数项全是负数，称为原始不可行。常数项是负数且最小，确定出基变量x5。2.2.3 2.2.3 对偶单纯形法示例三对偶单纯形法示例三第2节 线性规划的对偶理论对偶单纯形法示例 用出基变量x5行的所有负数分别去除对应的检验数，最小值对应的为进基变量x1，交叉元素为主元（-1）主元运算：第一行乘（-1）2.2.3 2.2.3 对偶单纯形法示例三对偶单纯形法示例三第2节 线性规划的对偶理论对偶单纯形法示例 主元运算：第二行加上第一行（-2）计算检验数2.2.3 2.2.3 对偶单纯形法示例三对偶单纯形法示例三第2节 线性规划的对偶理论对偶单纯形法示例 确定出基变量X6确定进基变量X3，主元（-2）2.2.3 2.2.3 对偶单纯形法示例三对偶单纯形法示例三第2节 线性规划的对偶理论对偶单纯形法示例 主元运算：第二行乘（-1/2）主元运算：第一行加第二行2.2.3 2.2.3 对偶单纯形法示例三对偶单纯形法示例三第2节 线性规划的对偶理论对偶单纯形法示例 计算检验数：全为非正。但此时常数b已全大于零，最优解=（7，0，4，0）最优值 S =-7 S=72.2.3 2.2.3 对偶单纯形法示例三对偶单纯形法示例三第2节 线性规划的对偶理论对偶单纯形法示例 例例:用对偶单纯形法解下列线性规划问题 min S=x1+2x2 s.t.-x1+2x2 -x3 1 -x1-2x2 +x3 6 x1，x2，x3 0解：解：将原问题化成 max S=-x1-2x2 s.t.x1-2x2 +x3+x4 =-1 x1+2x2 -x3 +x5=-6 x1，x2，x3，x4，x5 02.2.4 2.2.4 对偶单纯形法示例四对偶单纯形法示例四第2节 线性规划的对偶理论对偶单纯形法示例 常数项最小出基变量X5，按比值无法比较。常数项次小出基变量X4，按比值X2为进基变量。主元（-2）2.2.4 2.2.4 对偶单纯形法示例四对偶单纯形法示例四第2节 线性规划的对偶理论对偶单纯形法示例 主元运算：第一行乘（-1/2）主元运算：第二行加第一行（-2）2.2.4 2.2.4 对偶单纯形法示例四对偶单纯形法示例四第2节 线性规划的对偶理论对偶单纯形法示例 计算检验数：全小于零。但常数项为负数的行元素全大于零，原问题无可行解。2.2.4 2.2.4 对偶单纯形法示例四对偶单纯形法示例四第2节 线性规划的对偶理论对偶单纯形法示例 例：例：用对偶单纯形法解下列线性规划问题解：解：先化为标准型约束条件两边同乘(-1)2.2.5 2.2.5 对偶单纯形法示例五对偶单纯形法示例五第2节 线性规划的对偶理论对偶单纯形法示例 Cj1524500CBXBbx1x2x3x4x500 x4x52105-6-2-1-11001-15-24-5002.2.5 2.2.5 对偶单纯形法示例五对偶单纯形法示例五第2节 线性规划的对偶理论对偶单纯形法示例 Cj1524500CBXBbx1x2x3x4x500 x4x52105-6-2-1-11001-15-24-500-45-240 x2x51/3-1/30-5101/6-2/3-1/6-1/301-150-1-402.2.5 2.2.5 对偶单纯形法示例五对偶单纯形法示例五第2节 线性规划的对偶理论对偶单纯形法示例 Cj1524500CBXBbx1x2x3x4x500 x4x52105-6-2-1-11001-15-24-500-45-240 x2x51/3-1/30-5101/6-2/3-1/6-1/301-150-1-4033/212-24-5x2x31/41/2-5/415/21001-1/41/21/4-3/2-15/200-7/2-3/2X*=(0,1/4,1/2)Y*=(7/2,3/2)2.2.5 2.2.5 对偶单纯形法示例五对偶单纯形法示例五第2节 线性规划的对偶理论对偶单纯形法示例 原始单纯形法对偶单纯形法前提条件所有 bi0所有 bi0?最优性检验所有所有换入、出基变量的确定先确定换入基变量后确定换出基变量先确定换出基变量后确定换入基变量原始基本解的进化可行 最优非可行 可行(最优)2.2.5 2.2.5 对偶单纯形法示例五对偶单纯形法示例五第2节 线性规划的对偶理论对偶单纯形法示例 对偶单纯形法与原始单纯形法的对应关系对偶单纯形法与原始单纯形法的对应关系第3节 灵敏度分析1 1价值系数 c 发生变化灵敏度分析一词的含义是指对系统或事物因周围条件变化显示出来的敏感程度的分析。在前面所讲的线性规划问题都假定了各系数cj,aij,bi等始终保持不变，是已知常数。而实际当中，这些系数通常是一些估计或预测数字。如果外界条件发生了变化，这些系数也会发生相应变化，这样以来，就会引出一些问题：这些系数中，如果有一些发生变化，问题的最优解会发生怎样的变化？如果发生变化，又将使用何种简便方法求出新的最优解？3.1.1 3.1.1 灵敏度分析灵敏度分析含义含义第3节 灵敏度分析价值系数 c 发生变化例：例：线性规划及最优单纯形表如下 max w=2x1+3x2+x3 1/3 x1+1/3 x2+1/3 x3 1 1/3 x1+4/3 x2+7/3 x3 3 x1,x2,x3 03.1.2 3.1.2 价值价值系数系数 c c 发生变化发生变化第3节 灵敏度分析价值系数 c 发生变化可得到c3 3 时，原最优解不变。当-3+c3 0最优解不变3.1.2 3.1.2 价值价值系数系数 c c 发生变化发生变化第3节 灵敏度分析价值系数 c 发生变化cj-2-3-400B-1bcBxBx1x2x3x4x5-3x201-1/5-2/51/52/5-2x1107/5-1/5-2/511/5j00-9/5-8/5-1/5-28/5例：例：线性规划及最优单纯形表如下 试求 c3 在多大范围内变动时，原最优解保持不变。3.1.2 3.1.2 价值价值系数系数 c c 发生变化发生变化第3节 灵敏度分析价值系数 c 发生变化可得到c3 9/5 时，原最优解不变。cj-2-3-4c300B-1bcBxBx1x2x3x4x5-3x201-1/5-2/51/52/5-2x1107/5-1/5-2/511/5j00-9/5+c3-8/5-1/5-28/53.1.2 3.1.2 价值价值系数系数 c c 发生变化发生变化第3节 灵敏度分析价值系数 c 发生变化下表为最优单纯形表（考虑基变量系数c1发生变化）-3+c1 0-5-4c1 0-1+c1 0最优解不变可得到-5/4 C1 1 时，原最优解不变。最优值将会出现相应的变化。3.1.2 3.1.2 价值价值系数系数 c c 发生变化发生变化第3节 灵敏度分析价值系数 c 发生变化Max Z=2x1+3x2+0 x3+0 x4+0 x5 x1+2x2+x3 =84x1 +x4 =16 4x2 +x5=12 x1,x2,x3,x4,x5 0 例例3.1.2 3.1.2 价值价值系数系数 c c 发生变化发生变化第3节 灵敏度分析价值系数 c 发生变化下表为最优单纯形表（考虑基变量系数c2发生变化）可得到-3c21 时，原最优解不变。3.1.2 3.1.2 价值价值系数系数 c c 发生变化发生变化第3节 灵敏度分析价值系数 c 发生变化例:已知线性规划的标准形式为其最优单纯形表如下Cj12100CBXBbX1x2x3x4x520 x2x56101310111101-Z-12-30-1-20问：(1)当C1由1变为4时，求新问题的最优解。(2)讨论C2在什么范围内变化时，原有的最优解仍是最优解。3.1.2 3.1.2 价值价值系数系数 c c 发生变化发生变化第3节 灵敏度分析价值系数 c 发生变化解：解：由表可知，C1是非基变量的价值系数，因此C1的改变只影响1，可见最优性准则已不满足，继续迭代Cj42100CBXBbx1x2x3x4x520 x2x56101310111101610/3-Z-1220-1-2024x2x18/310/301102/31/32/31/3-1/31/3-Z-56/300-5/3-8/3-2/33.1.2 3.1.2 价值价值系数系数 c c 发生变化发生变化第3节 灵敏度分析价值系数 c 发生变化（2）要使原最优解仍为最优解，只要在新的条件下满足0成立，因为x2是基变量，所以所有的值都将发生变化，即 则c2-1，所以当x2的系数c2-1时，原最优解仍能保持为最优解。3 c2 0 c2 0 c2 03.1.2 3.1.2 价值价值系数系数 c c 发生变化发生变化第3节 灵敏度分析价值系数 c 发生变化例：例：线性规划及最优单纯形表如下，问b3由12变为12+b3 最优性不变。Max Z=2x1+3x2+0 x3+0 x4+0 x5 x1+2x2+x3 =84x1 +x4 =16 4x2 +x5=12+b3 x1,x2,x3,x4,x5 0 3.2.1 3.2.1 右右端项端项 b b 发生变化发生变化第3节 灵敏度分析右端项 b 发生变化3.2.1 3.2.1 右右端项端项 b b 发生变化发生变化第3节 灵敏度分析右端项 b 发生变化比如第三个式子中，由4+b3 0，解得b3-4 时最优性不变 3.2.1 3.2.1 右右端项端项 b b 发生变化发生变化第3节 灵敏度分析右端项 b 发生变化若b 3=-8，则 4+（-8）=-4 0，改变了最优性，只要再继续迭代即可。3.2.1 3.2.1 右右端项端项 b b 发生变化发生变化第3节 灵敏度分析右端项 b 发生变化例：例：线性规划及最优单纯形表如下。求当b1在由8变动为12时，原最优性是否保持不变，若变动求出新的最优解。C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/2143 x2 011/2-1/802j00-3/2-1/80143.2.1 3.2.1 右右端项端项 b b 发生变化发生变化第3节 灵敏度分析右端项 b 发生变化3.2.1 3.2.1 右右端项端项 b b 发生变化发生变化第3节 灵敏度分析右端项 b 发生变化将b代入原最优单纯形表中，运用对偶单纯形法计算最优解。C i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/21-43 x2 011/2-1/804j00-3/2-1/80143.2.1 3.2.1 右右端项端项 b b 发生变化发生变化第3节 灵敏度分析右端项 b 发生变化将b代入原最优单纯形表中，运用对偶单纯形法计算最优解。经一次迭代后，求得新的最优解:(4 3 2 0 0)TC i23000B-1bCBXBx1x2x3x4x52 x1 1001/4040 x5 00-21/21-43 x2 011/2-1/804j00-3/2-1/80143/42 x1 1001/4040 x3 001-1/4-1/223 x2 01001/43j000-1/2-3/4173.2.1 3.2.1 右右端项端项 b b 发生变化发生变化第3节 灵敏度分析右端项 b 发生变化例：例：常山机械厂生产和两种产品。生产中需使用A、B、C三种设备进行加工，加工每件产品或产品所需的设备机时数、利润值及每种设备可利用机时数列于下表，请问：充分利用设备机台时，工厂应生产和产品各多少件才能获得最大利润？试列出相应的线性规划数学模型。ABC产品利润（元件）24022053设备可用机时数（工时）1216153.3.1 3.3.1 增加增加一个变量的一个变量的分析分析第3节 灵敏度分析增加一个变量的分析解：解：设、产品的生产数量分别为x1和x2，建立问题数学模型及最优单纯表如下：max z=2x1+3x2 2x1+2x212 4x1 16 5x2 15 xj0，j=1，23.3.1 3.3.1 增加增加一个变量的一个变量的分析分析第3节 灵敏度分析增加一个变量的分析若增加一个变量x6（新产品的生产数量）。试分析问题最优解的变化max z=2x1+3x2+4x6 2x1+2x2+2x612 4x1 +4x616 5x2+5x615 xj0，j=1,2,63.3.1 3.3.1 增加增加一个变量的一个变量的分析分析第3节 灵敏度分析增加一个变量的分析3.3.1 3.3.1 增加增加一个变量的一个变量的分析分析第3节 灵敏度分析增加一个变量的分析3.3.1 3.3.1 增加增加一个变量的一个变量的分析分析第3节