最优化理论第3章线性规划PPT课件.ppt

第第 三三 章章线线 性性 规规 划划13.1 3.1 线性规划模型线性规划模型 例例: :某某工工厂厂拥拥有有A A、、B B、、C C 三三种种类类型型的的设设备备，，生生产产甲甲、、乙乙两两种种产产品品每每件件产产品品在在生生产产中中需需要要占占用用的的设设备备机机时时数数，，每每件件产产品品可可以以获获得得的的利润以及三种设备可利用的时数如下表所示：利润以及三种设备可利用的时数如下表所示： 产品甲产品乙设备能力（h）设备A3 32 26565设备B2 21 14040设备C0 03 37575利润（元/件）1500150025002500 2 问题：工厂应如何安排生产可获得最大的总利润？ 解：设变量xi为第i种（甲、乙）产品的生产件数（i＝1，2）根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制对设备A，两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3 x1 + 2 x2 ≤ 65； 对设备B，两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2 x1 + x2 ≤ 40；3.1 3.1 线性规划模型线性规划模型3 对对设设备备C C，，两两种种产产品品生生产产所所占占用用的的机机时时数数不不能能超超过过7575，，于于是是我我们们可可以以得得到到不不等等式式：：3 3x x2 2 ≤75 ≤75 ；；另另外外，，产产品品数数不不可可能能为为负负，，即即 x x1 1 ,x,x2 2 ≥0≥0。

同同时时，，我我们们有有一一个个追追求求目目标标，，即即获获取取最最大大利利润润于于是是可可写写出出目目标标函函数数z z为为相相应应的的生生 产产 计计 划划 可可 以以 获获 得得 的的 总总 利利 润润 ：：z z=1500=1500x x1 1+2500+2500x x2 2 综综合合上上述述讨讨论论，，在在加加工工时时间间以以及及利利润润与与产产品品产产量量成成线线性性关关系系的的假假设设下下，，把把目目标标函函数数和和约约束束条条件件放放在在一一起起，，可可以以建建立立如下的线性规划模型：如下的线性规划模型：3.1 3.1 线性规划模型线性规划模型4目标函数 Max z =1500x1+2500x2 约束条件 s.t. 3x1+2x2≤ 65 2x1+x2≤ 40 3x2≤ 75 x1 ,x2 ≥0  3.1 3.1 线性规划模型线性规划模型5 这是一个典型的利润最大化的生产计划问题其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于……”。

因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1 ,x2 的取值3.1 3.1 线性规划模型线性规划模型6•一般形式 •目标函数：Max(Min)z = c1x1 + c2x2 + … + cnxn •约束条件： a11x1+a12x2+…+a1nxn≤( =, ≥ )b1a21x1+a22x2+…+a2nxn≤( =, ≥ )b2 . . . am1x1+am2x2 +…+amnxn≤( =, ≥ )bm x1 ，x2 ，… ，xn ≥ 03.1 3.1 线性规划模型线性规划模型7•标准形式•目标函数：Max z = c1x1 + c2x2 + … + cnxn •约束条件：a11x1 + a12x2 + … + a1nxn = b1a21x1 + a22x2 + … + a2nxn = b2 . . .am1x1 + am2x2 + … + amnxn = bm x1 ，x2 ，… ，xn ≥ 03.1 3.1 线性规划模型线性规划模型8 可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。

对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式: 3.1 3.1 线性规划模型线性规划模型9 1.极小化目标函数的问题： 设目标函数为 Min f = c1x1 + c2x2 + … + cnxn 则可以令z ＝ -f ，该极小化问 题与下面的极大化问题有相同的最优 解，即 Max z = -c1x1 - c2x2 - … - cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 Min f ＝ - Max z3.1 3.1 线性规划模型线性规划模型10 2、约束条件不是等式的问题： 设约束条件为 ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引进一个新的变量s ，使它等于约束右边与左边之差 s=bi–(ai1 x1 + ai2 x2 + … + ain xn ) 显然，s 也具有非负约束，即s≥0， 这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn+s = bi3.1 3.1 线性规划模型线性规划模型11 当约束条件为 ai1 x1+ai2 x2+ … +ain xn ≥ bi 时，类似地令 s=(ai1 x1+ai2 x2+ … +ain xn)- bi 显然，s 也具有非负约束，即s≥0，这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn-s = bi 3.1 3.1 线性规划模型线性规划模型12 为了使约束由不等式成为等式而引进的变量s称为“松弛变量”。

如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量  3.1 3.1 线性规划模型线性规划模型13 例2.2：将以下线性规划问题转化为标准形式  Min f = 3.6 x1 - 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 ≤15.7 4.1 x1 + 3.3 x3 ≥8.9 x1 + x2 + x3 = 38 x1 , x2 , x3 ≥ 0  3.1 3.1 线性规划模型线性规划模型 解：首先,将目标函数转换成极大化：令 z= -f = -3.6x1+5.2x2-1.8x3 14其次考虑约束，有2个不等式约束，引进松弛变量x4，x5 ≥0于是，我们可以得到以下标准形式的线性规划问题： Max z = - 3.6 x1 + 5.2 x2 - 1.8 x3s.t. 2.3x1+5.2x2-6.1x3+x4= 15.7 4.1x1+3.3x3-x5= 8.9 x1+x2+x3= 38 x1 ,x2 ,x3 ,x4 ,x5 ≥ 03.1 3.1 线性规划模型线性规划模型15 3. 变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。

当某一个变量xj没有非负约束时，可以令 xj = xj’- xj”其中 xj’≥0，xj”≥0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj’和xj”的大小3.1 3.1 线性规划模型线性规划模型16 4.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负当某一个右端项系数为负时，如 bi<0，则把该等式约束两端同时乘以-1，得到：-ai1 x1-ai2 x2- … -ain xn = -bi 3.1 3.1 线性规划模型线性规划模型17例2.3：将以下线性规划问题转化为标准形式 Min f= -3 x1 + 5 x2 + 8 x3 - 7 x4s.t. 2 x1 - 3 x2 + 5 x3 + 6 x4 ≤ 28 4 x1 + 2 x2 + 3 x3 - 9 x4 ≥ 39 6 x2 + 2 x3 + 3 x4 ≤ - 58 x1 , x3 , x4 ≥ 03.1 3.1 线性规划模型线性规划模型18解：首先，将目标函数转换成极大化： 令 z = -f = 3x1–5x2–8x3+7x4 ； 其次考虑约束，有3个不等式约束，引进松弛变量x5 ,x6 ,x7 ≥0 ；由于x2无非负限制，可令x2=x2’-x2”,其中x2’≥0，x2”≥0 ； 由于第3个约束右端项系数为-58，于是把该式两端乘以-1 。

于是，我们可以得到以下标准形式的线性规划问题： 3.1 3.1 线性规划模型线性规划模型19 Max z = 3x1–5x2’+5x2”–8x3 +7x4 s.t. 2x1–3x2’+3x2”+5x3+6x4+x5= 28 4x1+2x2’-2x2”+3x3-9x4-x6= 39 -6x2’+6x2”-2x3-3x4-x7 = 58 x1 ,x2’,x2”,x3 ,x4 ,x5 ,x6 ,x7 ≥ 0 3.1 3.1 线性规划模型线性规划模型203.1 3.1 线性规划模型线性规划模型矩阵形式：矩阵形式：线性规划的标准形式：线性规划的标准形式： Max cTx(LP) s.t. Ax = b x≥0其中其中, c , x  Rn b  Rm A m n 矩阵矩阵213.1 3.1 线性规划模型线性规划模型l线性规划的规范形式：线性规划的规范形式： Max cTx (P) s.t. Ax ≤ b x≥0其中其中, c , x  Rn b  Rm A m n 矩阵矩阵223.2 3.2 线性规划的单纯形法线性规划的单纯形法线性规划的理论：线性规划的理论：线性规划的理论：线性规划的理论：考虑考虑(LP)的最优性条件的最优性条件约束多面体约束多面体 S = { x Rn Ax = b , x≥0 }的极点和极方向的极点和极方向定理定理 考虑考虑(LP)及上述多面体及上述多面体S，设，设 A满秩，满秩，x(1),x(2) , …,x(k)为所有极点，为所有极点， d(1),d(2) , …,d(l)为所有极方向。

那么，为所有极方向那么， 1) (LP)存在有限最优解存在有限最优解  cTd(j) ≤0,  j . 2) 若若(LP)存在有限最优解存在有限最优解, 则最优解可以则最优解可以在某个极点达到在某个极点达到 .233.2 3.2 线性规划的单纯形法线性规划的单纯形法线性规划的理论线性规划的理论线性规划的理论线性规划的理论定理定理 考虑考虑(LP) , 条件同上，设条件同上，设 x* 为极为极点点, 存在分解存在分解 A = [ B , N ]，其中，其中B为为m阶阶非奇异矩阵，使非奇异矩阵，使 xT = [ xBT, xNT ], 这里这里 xB = B-1b≥0, xN =0，， 相应相应 cT = [ cBT, cNT ] 那么， 1）若）若 cNT- cBT B-1N≤0, 则则 x* -- opt. 2）若）若 cj- cBT B-1pj > 0, 且且 B-1pj≤0, 则则 (LP) 无有界解无有界解 .243.2 3.2 线性规划的单纯形法线性规划的单纯形法表格单纯形法表格单纯形法1、原理及算法过程、原理及算法过程 Max cTx(LP) s.t. Ax = b x≥0其中其中, c , x  Rn b  Rm A m n 矩阵，秩（矩阵，秩（A））= m253.2 3.2 线性规划的单纯形法线性规划的单纯形法单纯形法原理及算法过程单纯形法原理及算法过程单纯形法原理及算法过程单纯形法原理及算法过程l算法过程算法过程 (考虑一般步考虑一般步, k = 0,1,2,… )设设 x(k) 为极点为极点, 对应分解对应分解 A = [ B , N ]，使，使 xT = [ xBT, xNT ], 这里这里 xB = B-1b>0, xN =0，， 相应相应 cT = [ cBT, cNT ] 。

那么，那么， 1）若）若 cNT- cBT B-1N≤0, 则则 x(k) – opt，停；，停； 2）否则，存在）否则，存在 cj- cBT B-1pj > 0, a））若若 B-1pj≤0, 则则 (LP) 无有界解，停；无有界解，停； b）若存在）若存在 (B-1pj)i > 0, 取取 α = min{(B-1b)i / (B-1pj)i | (B-1pj)i >0} = (B-1b)r /(B-1pj)r >0 263.2 3.2 线性规划的单纯形法线性规划的单纯形法单纯形法原理及算法过程单纯形法原理及算法过程单纯形法原理及算法过程单纯形法原理及算法过程l(续续) 得到得到 x(k+1) = x(k) + αd 是极点是极点其中其中, dT = [ dBT, dNT ], 这里这里 j dB = -B-1pj , dN = (0, ... , 1, … ,0)T有有, cTx(k+1) = cTx(k) + α cTd = cTx(k) + α (cj - cBTB-1pj) > cTx(k) 所以，所以，x(k+1) 比比 x(k) 好好 重复这个过程，直到停机。

重复这个过程，直到停机273.2 3.2 线性规划的单纯形法线性规划的单纯形法 表格单纯形法表格单纯形法表格单纯形法表格单纯形法2、单纯形表：、单纯形表：设设 x 为初始极点为初始极点, 相应分解相应分解 A = [ B , N ]fxBTxNTRHS目标行目标行1cBTcNT01行行约束行约束行0BNbM行行1列列m列列n-m列列1列列作变换，使前作变换，使前m+1列对应的列对应的m+1阶矩阵变为单位矩阶矩阵变为单位矩阵相当于该表左乘阵相当于该表左乘 1 cBT -1 1 - cBT B-1 0 B 0 B-1 =283.2 3.2 线性规划的单纯形法线性规划的单纯形法表格单纯形法表格单纯形法表格单纯形法表格单纯形法得到：得到： 检验数检验数fxBTxNTRHS目标行目标行10TcNT - cBT B-1cBTB-1 b1行行 xB0IB-1NB-1bM行行1列列m列列n-m列列1列列为了计算方便，我们对规范形式建立如为了计算方便，我们对规范形式建立如下单纯形表：下单纯形表：（（注：引入了注：引入了m个松弛变量个松弛变量））293.2 3.2 线性规划的单纯形法线性规划的单纯形法l表格单纯形法表格单纯形法l考虑：考虑： bi > 0 i = 1 , … , m Max z = c1 x1 + c2 x2 + … + cn xn s.t. a11 x1 + a12 x2 + … + a1n xn ≤ b1 a21 x1 + a22 x2 + … + a2n xn ≤ b2 …… …… am1 x1 + am2 x2 + … + amn xn ≤ bm x1 ，x2 ，… ，xn ≥ 0303.2 3.2 线性规划的单纯形法线性规划的单纯形法l加入松弛变量：加入松弛变量： Max z = c1 x1 + c2 x2 + … + cn xn s.t. a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2 …… …… am1 x1 + am2 x2 + … + amn xn+ xn+m = bm x1 ，x2 ，… ，xn ，xn+1 ，… ，xn+m ≥ 031显然，显然，xj = 0 j = 1, … , n ; xn+i = bi i = 1 , … , m 是基本可行解 对应的基是单位矩阵。

以下是初始单纯形表： m m其中：f = -∑ +i bi j = cj -∑ cn+i aij 为检验数 cn+i = 0 i= 1,…,m i = 1 i = 1 an+i,i = 1 , an+i,j = 0 ( j≠i ) i , j = 1, … , m建立实用单纯形表建立实用单纯形表32 利用求解线性规划问题基本可行解（极点）的方法来求解较大规模的问题是不可行的单纯形法的基本思路是有选择地取基本可行解，即是从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差 3.2 3.2 线性规划的单纯形法线性规划的单纯形法33单单 纯纯 形形 法法初始基本可行解初始基本可行解是否最优解或是否最优解或无限最优解无限最优解? ?结束结束沿边界找新沿边界找新的基本可行解的基本可行解NY单纯形法的基本过程34 例：用单纯形法的基本思路解前例的线性规划问题 Max z = 1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 ≥ 03.2 3.2 线性规划的单纯形法线性规划的单纯形法353.2 3.2 线性规划的单纯形法线性规划的单纯形法最优解最优解 x1 = 5 x2 = 25 x4 = 5（松弛标量，表示（松弛标量，表示B设备设备有有5个机时的剩余）个机时的剩余） 最优值最优值 z* = 70000 36l注意：单纯形法中，注意：单纯形法中， 1、每一步运算只能用矩阵初等行、每一步运算只能用矩阵初等行变换；变换； 2、表中第、表中第3列的数总应保持非负列的数总应保持非负（（≥ 0）；）； 3、当所有检验数均非正（、当所有检验数均非正（≤ 0））时，得到最优单纯形表。

时，得到最优单纯形表3.2 3.2 线性规划的单纯形法线性规划的单纯形法37 一般情况的处理及注意事项的强调：主要是讨论初始基本可行解不明显时，常用的方法要弄清它的原理，并通过例题掌握这些方法，同时进一步熟悉用单纯形法解题 考虑一般问题： bi > 0 i = 1 , … , m3.2 3.2 线性规划的单纯形法线性规划的单纯形法38Max z = c1x1 + c2x2 + … + cnxn s.t. a11x1+a12x2 +…+a1nxn = b1 a21x1+a22x2 +…+a2nxn = b2 . . . am1x1+am2x2+…+amnxn = bm x1 ，x2 ，… ，xn ≥ 03.2 3.2 线性规划的单纯形法线性规划的单纯形法39大大M M法：法： 引入人工变量 xn+i ≥ 0 （i = 1 , … , m）及充分大正数 M 。

得到：Max Max z = c1x1 +c2x2 +…+cnxn -Mxn+1 -…-Mxn+m s.t. s.t. a11 x1 + a12 x2 + … + a1n xn + xn+1 = = b1 a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2 . . . . . . am1 x1 + am2 x2 + … + amn xn + xn+m = bm x1 ，x2 ，… ，xn ，xn+1 ，… ，xn+m ≥≥0 03.2 3.2 线性规划的单纯形法线性规划的单纯形法40显然，显然，x xj j = 0 = 0 j j=1, … , =1, … , n n ; ; x xn+in+i = = b bi i i i =1 , … , =1 , … , m m 是基本可行解是基本可行解对应的基是单位矩阵。

对应的基是单位矩阵 结论：结论：若得到的最优解满足若得到的最优解满足 x xn+in+i = 0 = 0 i i = 1 , … , = 1 , … , m m 则是原问题则是原问题的最优解；否则，原问题无可行解的最优解；否则，原问题无可行解单单 纯纯 形形 法法41l 两阶段法：l 引入人工变量 xn+i ≥ 0，i = 1 ,…, m；l 构造: Max z = - xn+1 - xn+2 - … - xn+m s.t. a11x1+a12x2+ … +a1nxn+xn+1 = b1 a21x1+a22x2+ … +a2nxn+xn+2 = b2 . . . am1x1+am2x2+ … +amnxn+xn+m = bm x1,x2 ... xn ,xn+1,…,xn+m ≥ 0单单 纯纯 形形 法法42 第一阶段求解上述问题：第一阶段求解上述问题： 显然，显然，x xj j = 0 = 0 j j=1, … , =1, … , n n ; ; x xn+in+i = = b bi i i i =1 , … , =1 , … , m m 是基本可行解是基本可行解, ,它对应的基它对应的基 是单位矩阵。

是单位矩阵 结论：结论：若得到的最优解满足若得到的最优解满足 x xn+in+i=0=0 i i=1 , … , =1 , … , m m 则是原问题的基本可行则是原问题的基本可行解解; ;否则，原问题无可行解否则，原问题无可行解 得到原问题的基本可行解后，第二得到原问题的基本可行解后，第二阶段求解原问题阶段求解原问题单单 纯纯 形形 法法43例（LP）Max z = 5x1 + 2x2 + 3x3 - x4 s.t. x1 + 2x2 + 3x3 = 15 2x1 + x2 + 5x3 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x2 , x3 , x4 ≥ 03.2 3.2 线性规划的单纯形法线性规划的单纯形法44 Max z = 5x1+2x2+3x3-x4-Mx5-Mx6 s.t. x1+2x2+3x3+x5 =15 2x1+x2+5x3+x6 =20 x1+2x2+4x3+x4 =26 x1 ,x2 ,x3 ,x4 ,x5 ,x6 ≥ 03.2 3.2 线性规划的单纯形法线性规划的单纯形法45•大大M M法法 （LP - M）• 得到最优解：(25/3，10/3，0，11)T • 最优目标值：112/33.2 3.2 线性规划的单纯形法线性规划的单纯形法46 第一阶段问题（LP - 1） Max z = - x5 - x6 s.t. x1 + 2x2 + 3x3 + x5 = 15 2x1 + x2 + 5x3 + x6 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 ≥ 03.2 3.2 线性规划的单纯形法线性规划的单纯形法47•第一阶段第一阶段 (LP - 1）• 得到原问题的基本可行解: (0，15/7，25/7，52/7)T 3.2 3.2 线性规划的单纯形法线性规划的单纯形法48•第二阶段第二阶段 把基本可行解填入表中• 得到原问题的最优解:(25/3，10/3，0，11)T •最优目标值：112/33.2 3.2 线性规划的单纯形法线性规划的单纯形法493.3 3.3 线性规划的对偶线性规划的对偶 对偶原理 对偶问题定义—— 线性规划问题写出其对偶问题，要掌握在对称形式和非对称情况下由原问题写出对偶问题的方法。

对偶定理—— 只需了解原问题与对偶问题解的关系，证明从略50 1.对偶问题： 若3.1中的例题的设备都用于外协加工，工厂收取加工费试问：设备 A、B、C 每工时各如何收费才最有竞争力？ 设 y1 ，，y2 ，，y3 分别为每工时设备 A、B、C 的收取费用3.3 3.3 线性规划的对偶线性规划的对偶51线性规划原问题线性规划原问题 例例: :某某工工厂厂拥拥有有A A、、B B、、C C 三三种种类类型型的的设设备备，，生生产产甲甲、、乙乙两两种种产产品品每每件件产产品品在在生生产产中中需需要要占占用用的的设设备备机机时时数数，，每每件件产产品品可可以以获获得得的的利利润润以以及及三三种种设设备备可可利利用用的的时时数数如下表所示求获最大利润的方案如下表所示求获最大利润的方案 产品甲产品乙设备能力（h）设备A3 32 26565设备B2 21 14040设备C0 03 37575利润（元/件）1500150025002500 52 Max z = 1500x1 + 2500x2 s.t. 3x1 + 2x2 ≤ 65 2x1 + x2 ≤ 40 原问题原问题 3x2 ≤ 75 x1 ,x2 ≥ 0 Min f = 65y1+ 40y2 + 75y3 s.t. 3y1+2y2 ≥1500 （不少于甲产品的利润） 2y1+y2+3y3 ≥2500 对偶问题对偶问题 （不少于乙产品的利润） y1, y2 , y3 ≥ 03.3 3.3 线性规划的对偶线性规划的对偶53 2、对偶定义 对称形式： 互为对偶 (LP) Max z = cT x (DP) Min f = bT y s.t. Ax ≤ b s.t. AT y ≥ c x ≥ 0 y ≥ 0 “Max -- ≤ ” “Min-- ≥”3.3 3.3 线性规划的对偶线性规划的对偶54 一对对称形式的对偶规划之间具有下面的对应关系。

(1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式即“max，≤”和“min，≥”相对应3.3 3.3 线性规划的对偶线性规划的对偶55 (2)(2)从从约约束束系系数数矩矩阵阵看看：：一一个个模模型型中中为为ＡＡ，，则则另另一一个个模模型型中中为为A AT T一一个个模模型型是是m m个个约约束束，，n n个个变变量量，，则则它它的的对偶模型为对偶模型为n n个约束，个约束，m m个变量 (3)(3)从从数数据据b b、、C C的的位位置置看看：：在在两两个规划模型中，个规划模型中，b b和和C C的位置对换的位置对换 (4)(4)两两个个规规划划模模型型中中的的变变量量皆皆非非负3.3 3.3 线性规划的对偶线性规划的对偶56 非对称形式非对称形式的对偶规划的对偶规划 一一般般称称不不具具有有对对称称形形式式的的一一对对线线性性规划为非对称形式的对偶规划规划为非对称形式的对偶规划 对对于于非非对对称称形形式式的的规规划划，，可可以以按按照照下面的对应关系直接给出其对偶规划。

下面的对应关系直接给出其对偶规划 （（1 1））将将模模型型统统一一为为“max“max，，≤”≤”或或“min“min，，≥” ≥” 的的形形式式，，对对于于其其中中的的等等式式约约束束按按下下面面（（2 2））、、（（3 3））中中的方法处理；的方法处理； 3.3 3.3 线性规划的对偶线性规划的对偶57 （（2 2））若若原原规规划划的的某某个个约约束束条条件件为为等等式式约约束束，，则则在在对对偶偶规规划划中中与与此此约约束束对对应应的的那那个个变变量量取取值值没没有有非非负负限限制；制； （（3 3））若若原原规规划划的的某某个个变变量量的的值值没没有有非非负负限限制制，，则则在在对对偶偶问问题题中中与与此此变量对应的那个约束为等式变量对应的那个约束为等式 3.3 3.3 线性规划的对偶线性规划的对偶583.3 3.3 线性规划的对偶线性规划的对偶 例例 写出下面线性规划的对偶规划模型写出下面线性规划的对偶规划模型解 先将约束条件变形为“≤”形式593.3 3.3 线性规划的对偶线性规划的对偶 再根据非对称形式的对应关系，直接写出对偶规划603.3 3.3 线性规划的对偶线性规划的对偶61l对偶定理对偶定理(原问题与对偶问题解的关系）考虑（LP）和（DP） 定理定理3-13-1 ( (弱对偶定理）弱对偶定理） 若 x, y 分别为（LP) 和（DP）的可行解，那么cTx ≤ bTy。

推论推论 若（LP）可行，那么（LP）无有限最优解的充分必要条件是（LD）无可行解3.3 3.3 线性规划的对偶线性规划的对偶62 定理定理3-23-2 ( (最优性准则定理最优性准则定理) ) 若x,y分别(LP),(DP)的可行解,且cTx=bTy ，那么x,y分别为(LP)和(DP)的最优解 定理定理3-33-3 ( (主对偶定理主对偶定理) ) 若(LP)和(DP)均可行 那么(LP)和(DP)均有最优解,且最优值相等 以上定理、推论对任意形式的相以上定理、推论对任意形式的相应性规划的对偶均有效应性规划的对偶均有效3.3 3.3 线性规划的对偶线性规划的对偶63影子价格影子价格 —— —— 是一个向量，它的分量表示是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率最优目标值随相应资源数量变化的变化率 若若x x* *, ,y y* * 分别为（分别为（LPLP）和（）和（DPDP）的最优解，）的最优解， 那么，那么， c cT T x x* * = = b bT T y y* * 根据根据 f f = = b bT Ty y* *= =b b1 1y y1 1* *+ +b b2 2y y2 2* *+ ++ +b bm my ym m* * 可知可知  f f / /  b bi i = = y yi i* * y yi i* * 表示表示 b bi i 变化变化1 1个单位对目标个单位对目标 f f 产生的产生的影响，称影响，称 y yi i* * 为为 b bi i的影子价格。

的影子价格 注意：注意：若若 B B 是最优基，是最优基， y y* * = ( = (B BT T) )-1-1 c cB B 为影子价格向量为影子价格向量3.3 3.3 线性规划的对偶线性规划的对偶64 影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手这样可以用较少的局部努力，获得较大的整体效益3.3 3.3 线性规划的对偶线性规划的对偶65 需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化另外，影子价格的经济含义（2），是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增加这个问题还将在灵敏度分析一节中讨论3.3 3.3 线性规划的对偶线性规划的对偶66由最优单纯形表求对偶问题最优解由最优单纯形表求对偶问题最优解 标准形式：标准形式： Max z = 50 x1 + 100 x2 s.t. x1 + x2 + x3 = 300 2x1 + x2 + x4 = 400 x2 + x5 = 250 x1 ,x2 ,x3 ,x4 ,x5 ≥ 03.3 3.3 线性规划的对偶线性规划的对偶67- -c cB BT TB B-1-1I IB B=(p p1 1, p, p4 4,p,p2 2 )oTB B-1-1最优解 x1 = 50 x2 = 250 x4 = 50影子价格影子价格 y y1 1 = 50 = 50 y y2 2 = 0 = 0 y y3 3 = 50 , = 50 , B B-1-1对应的检验数对应的检验数  T T = = c cB BT TB B-1-1 。

3.3 3.3 线性规划的对偶线性规划的对偶68   对偶单纯形法的基本思想对偶单纯形法的基本思想 对对偶偶单单纯纯形形法法的的基基本本思思想想是是：：从从原原规规划划的的一一个个基基本本解解出出发发，，此此基基本本解解不不一一定定可可行行，，但但它它对对应应着着一一个个对对偶偶可可行行解解（（检检验验数数非非正正）），，所所以以也也可可以以说说是是从从一一个个对对偶偶可可行行解解出出发发；；然然后后检检验验原原规规划划的的基基本本解解是是否否可可行行，，即即是是否否有有负负的的分分量量，，如如果果有有小小于于零零的的分分量量，，则则进进行行迭迭代代，，求求另另一一个个基基本本解解，，此此基基本本解解对对应应着着另另一一个个对偶可行解（检验数非正）对偶可行解（检验数非正）对偶单纯形法对偶单纯形法69 如果得到的基本解的分量皆非负则该基本解为最优解也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原 规划的最优解对偶单纯形法对偶单纯形法70 对偶单纯形法在什么情况下使用对偶单纯形法在什么情况下使用 ：： 应用前提：应用前提：有一个基，其对应的基有一个基，其对应的基满足满足: : ① ① 单纯形表的检验数行全部非正单纯形表的检验数行全部非正（对偶可行）；（对偶可行）； ② ② 变量取值可有负数（非可行解）。

变量取值可有负数（非可行解） 注：注：通过矩阵行变换运算，使所有通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单相应变量取值均为非负数即得到最优单纯形表对偶单纯形法对偶单纯形法71l 1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2； 2.若b’≥0,则得到最优解,停止;否则,若有bk<0则选k行的基变量为出基变量,转3 3.若所有akj’≥0( j = 1,2,…,n )，则原问题无可行解,停止;否则,若有akj’<0 则选 =min{j’ / akj’┃akj’<0}=r’/akr’那么 xr为进基变量,转4； 4.以akr’为转轴元,作矩阵行变换使其变为1,该列其他元变为0,转2 对偶单纯形法求解线性规划问题对偶单纯形法求解线性规划问题过程：过程：对偶单纯形法对偶单纯形法72例：例：求解线性规划问题：求解线性规划问题： 标准化：标准化： Max z = - 2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4= -3 -2x1+x2-3x3+x5= -4 x1,x2,x3,x4,x5 ≥ 0Min f = 2x1 + 3x2 + 4x3 S.t. x1 + 2x2 + x3 ≥ 3 2x1 - x2 + x3 ≥ 4 x1 , x2 , x3 ≥ 0 对偶单纯形法对偶单纯形法73表格对偶单纯形法表格对偶单纯形法74单纯形法和对偶单纯形法步骤单纯形法和对偶单纯形法步骤是是是是否否否否所有所有得到最优解计算计算典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数所有所有计算计算以为中心元素进行迭代以为中心元素进行迭代停没有最优解没有最优解单纯形法对偶单纯形法<75单纯形表的理解（例题）单纯形表的理解（例题）上表中6个常数 a1 , a2 , a3 , b , 1 , 2 取值在什么范围可使1、现可行解最优，且唯一？何时不唯一？2、现基本解不可行；3、问题无可行解；4、无有限最优解；5、现基本解可行，由 x1 取代 x6 目标函数可改善。

76 进一步理解最优单纯性表中各元素进一步理解最优单纯性表中各元素的含义考虑问题的含义考虑问题 Max Max z = c1 x1 + c2 x2 + … + cn xn s.t. a11x1 + a12x2 + … + a1nxn = b1 a21x1 + a22x2 + … + a2nxn = b2 . . . am1x1 + am2x2 + … + amnxn = bm x1 ，x2 ，… ，xn ≥ 03.4 3.4 灵敏度分析灵敏度分析773.4 3.4 灵敏度分析灵敏度分析无防设，无防设，xj = 0 j = m+1, … , n ; xi = bi’ i = 1 , … , m 是基本可行解, 对应的目标函数典式为：z = -f + m+1xm+1+…+ nxn以下是初始单纯形表： m m其中：f = -∑ ci bi’ j = cj -∑ ci aij’ 为检验数。

向量 b’ = B-1 b i = 1 i = 1 A= [ p1, p2, …, pn ], pj’ = B-1 pj, pj’ = ( a1j’ , a2j’ , … , amj’ )T ， j = m+1, … , n78内容：内容： c ci , b bj发生变化 增加一约束或变量 对于表格单纯形法，通过计算得到最优单纯形表 应能够找到最优基 B B 的逆矩阵 B B-1 ， B B-1b b 以及 B B-1N N，检验数 j 等3.4 3.4 灵敏度分析灵敏度分析79价值系数价值系数c c发生变化：发生变化： m 考虑检验数 j = cj -∑ cri arij j =1,2,……,n i = 1 1. 若若c ck k是非基变量的系数：是非基变量的系数： 设ck变化为 ck + ck k’= ck + ck -∑cri arik = k+ ck 只要 k’≤ 0 ,即 ck ≤ - k ，则 最优解不变；否则，将最优单纯形表 中的检验数 k 用 k’取代，继续单 纯形法的表格计算。

3.4 3.4 灵敏度分析灵敏度分析80例: Max z = -2x1 - 3x2 - 4x3 S.t. -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1 ,x2 ,x3 ,x4 ,x5 ≥03.4 3.4 灵敏度分析灵敏度分析81 例：最优单纯形表 从表中看到σ3= c3+Δc3-(c2×a13+c1×a23 ) 可得到Δc3 ≤ 9/5 时，原最优解不变3.4 3.4 灵敏度分析灵敏度分析82 2、若 cs 是基变量的系数： 设 cs 变化为 cs + cs ，那么 j’= cj -∑cri arij - ( cs + cs ) asj = j - cs asj ， i ≠ s 对所有非基变量，只要对所有非基变量 j’≤ 0 ，即 j ≤ cs asj ，则最优解 不变；否则，将最优单纯形表中的检验数 j 用 j’取代，继续单纯形法的表格计算。

Max{j/asjasj>0}≤cs≤Min{j/asjasj<0} 3.4 3.4 灵敏度分析灵敏度分析83例 MaxMax z z = 2 = 2x x1 1 + 3 + 3x x2 2 + 0+ 0x x3 3 + 0 + 0x x4 4+ 0+ 0x x5 5 s.t.s.t. x x1 1 + 2 + 2x x2 2 + + x x3 3 = 8= 8 4 4x x1 1 + + x x4 4 = 16 = 16 4 4x x2 2 + + x x5 5 = = 1212 x x1 1 , , x x2 2 , , x x3 3 , , x x4 4 , , x x5 5 ≥ ≥ 0 0 3.4 3.4 灵敏度分析灵敏度分析84 例: 下表为最优单纯形表,考虑 基变量系数c2发生变化从表中看到σj=cj-(c1×a1j+c5 × a5j+(c2+Δc2) ×a2j)j=3,4可得到 -3≤Δc2≤1时，原最优解不变。

3.4 3.4 灵敏度分析灵敏度分析85 右端项 b 发生变化 设分量 br 变化为 br + br ，根据第1章的讨论，最优解的基变量 xB = B B-1b，那么只要保持 B B-1(b + b) ≥ 0 ，则最优基不变，即基变量保持，只有值的变化；否则，需要利用对偶单纯形法继续计算 对于问题 (LP) Max z = cT x s.t. A Ax ≤ b x ≥ 0 3.4 3.4 灵敏度分析灵敏度分析86最优单纯形表中含有B B-1=( aij ）i=1,…,m; j=n+1,…,n+m 那么新的xi=(B B-1b)i+brair i=1,…, m 由此可得，最优基不变的条件是Max {-bi/airair>0}≤br≤Min{-bi/airair<0}3.4 3.4 灵敏度分析灵敏度分析87 例3.5: 上例最优单纯形表如下 3.4 3.4 灵敏度分析灵敏度分析88 0 0.25 0 这里 B B-1 = -2 0.5 1 0.5 -0.125 0 各列分别对应 b1、b2、b3 的单一变化因此，设 b1 增加 4，则 x1 ,x5 ,x2分别变为：4+0×4=4, 4+(-2)×4=-4<0, 2+0.5×4=4用对偶单纯形法进一步求解，可得：x* = ( 4, 3, 2, 0, 0 )T f* = 173.4 3.4 灵敏度分析灵敏度分析89 增加一个变量 增加变量 xn+1 则有相应的pn+1 ,cn+1 。

那么 计算出B B-1pn+1 , n+1=cn+1-∑cri ari n+1 填入最优单纯形表, 若 n+1 ≤ 0 则 最优解不变； 否则，进一步用单纯形法求解3.4 3.4 灵敏度分析灵敏度分析90例:前例增加x6 , p6=( 2, 6, 3 )T, c6=5 计算得到用单纯形法进一步求解，可得：x* = ( 1,1.5,0,0,0,2 )T f* = 16.53.4 3.4 灵敏度分析灵敏度分析91 增加一个约束增加一个约束 增加约束一个之后，应把最优解带增加约束一个之后，应把最优解带入新的约束，若满足则最优解不变，否则入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入一填入最优单纯形表作为新的一行，引入一个新的非负变量（原约束若是小于等于形个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变工变量），并通过矩阵行变换把对应基变量的元素变为量的元素变为0 0，进一步用单纯形法或对，进一步用单纯形法或对偶单纯形法求解。

偶单纯形法求解3.4 3.4 灵敏度分析灵敏度分析92例:前例增加3x1+ 2x2≤15，原最优解不满足这个约束于是3.4 3.4 灵敏度分析灵敏度分析经对偶单纯形法一步，可得最优解为（3.5, 2.25, 0, 0, 3, 2 )T，最优值为 13. 7593个人观点供参考，欢迎讨论。