1、管管 理理 运运 筹筹 学学1上节回顾上节回顾 4.退化问题（求出基变量过程中存在两个以上的最小比值，这样在下一次迭代就有一个或多个基变量等于零，造成的后果是：最优值在经过了一次或几次迭代而没有改善，降低了单纯型算法的效率） 5.针对退化问题，讲解了一个迭代循环的例子，引出了勃兰特法则： 按照决策变量、松弛变量、人工变量顺序排序。不管是检验数相等，还是比值相等，都选下标最小的为入基变量或出基变量。 时间问题，习题没有做。管管 理理 运运 筹筹 学学2第六章第六章 单纯形法的灵敏度分析与对偶问题单纯形法的灵敏度分析与对偶问题 1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 2 2线性规划的对偶问
2、题线性规划的对偶问题 3 3对偶规划的基本性质对偶规划的基本性质 4 4对偶单纯形法对偶单纯形法管管 理理 运运 筹筹 学学3单纯形表单纯形表管管 理理 运运 筹筹 学学41 1单纯形表的灵敏度分析单纯形表的灵敏度分析一、目标函数中变量系数Ck灵敏度分析（在什么范围内变化，最优解不变，与第二章，第三章联系起来） 在线性规划的求解过程中，目标函数系数的变动将会影响检验数的取值，但是，当目标函数的系数的变动不破坏最优判别准则时，原最优解不变，否则，原最优解将发生变化，要设法求出新的最优解。下面我们具体的分析 1.在最终的单纯形表里，X k是非基变量 由于约束方程系数增广矩阵在迭代中只是其本身的行的
3、初等变换与Ck没有任何关系， 所以当Ck变成Ck+ Ck时，在最终单纯形表中其系数的增广矩阵不变，又因为Xk是非基变量，所以基变量的目标函数的系数不变，即CB不变，可知Zk也不变，只是Ck变成了Ck+ Ck。这时 K= Ck-Zk就变成了Ck+ Ck- Zk= K+ Ck。要使原来的最优解仍为最优解，只要 K+ Ck0即可，也就是Ck的增量 Ck- K。 管管 理理 运运 筹筹 学学5 2.在最终的单纯形表中， X k是基变量 当Ck变成Ck+ Ck时，最终单纯形表中约束方程的增广矩阵不变，但是基变量的目标函数的系数CB变了，则ZJ(J=1,2,.,N)一般也变了，不妨设CB=(CB1, CB
4、2。, Ck,， CBm),当CB变成=(CB1, CB2。,Ck+ Ck,CBm),则： ZJ=(CB1, CB2。, Ck,，CBm)(a1j , a2j , aKj , amj) ZJ=(CB1, CB2。, Ck+ Ck,，CBm)(a1j , a2j , aKj , amj) = ZJ + Ck aKj T管管 理理 运运 筹筹 学学61 1单纯形表的灵敏度分析单纯形表的灵敏度分析根据上式可知 检验数 J (J=1,2,.,M)变成了 J,只要当J K时，有 J=CJ-ZJ= J- CK aKj 。要使最优解不变，J 0，就可求出 的取值范围，也就是使得第K个约束条件的对偶价格不变的
5、bk的变化范围。 ，-1-1-1BXB .(bb)BbBb 。kbmkk3kk2kk1kk1-21kdb.dbdbdbbB,.D则mkkkdddmkk2kk1kk21BBdb.dbdb.XXBmBBXXX有新的最优解为管管 理理 运运 筹筹 学学211 1单纯形表的灵敏度分析单纯形表的灵敏度分析（k的取值固定的值，i的取值是1到m）下面我们仍以第二章例1在最终单纯形表上对b1进行灵敏度分析。最终单纯形表如下所示：BkkX00bMax|0bMin|0BiBiikikikikxxdddd 要使也就是各个分量均不小于 ，用一个数学式子来表示 的允许变化范围是迭代次数基变量CBX1 X2 S1 S2
6、S3b50 100 0 0 02X1501 0 1 0 -150 S200 0 -2 1 150 X21000 1 0 0 1250 ZJ50 100 50 0 5027500CJ -ZJ0 0 -50 0 -50管管 理理 运运 筹筹 学学221 1单纯形表的灵敏度分析单纯形表的灵敏度分析 我们对b1进行灵敏度分析，因为在第一个约束方程中含有松弛变量S1, 实际意义可以描述为：设备台时数在250与325之间变化，则设备台时数的对偶价格不变，都为每台设备台时50元。的第一列。就是），纯形表中的系数列（所以松弛变量在最终单-1TB021 变。约束条件的对偶价格不第一个即故有当而可以因为325bb
7、250,25b50,252500|Min501500|Max,50X,50X, 02d, 01d11111212111iiBiiiBiddxddx管管 理理 运运 筹筹 学学231 1单纯形表的灵敏度分析单纯形表的灵敏度分析三、约束方程系数矩阵三、约束方程系数矩阵A A灵敏度分析（约束条件改变，对最优解的影响，比如灵敏度分析（约束条件改变，对最优解的影响，比如有新产品要生产、生产工艺改进等）有新产品要生产、生产工艺改进等）下面分两种情况讨论 1.在最终单纯形表上在最终单纯形表上Xk是非基变量：在初始单纯形表上的变量是非基变量：在初始单纯形表上的变量Xk的系数列的系数列Pk改变为改变为Pk经过迭
8、代后，在最终单纯形表上经过迭代后，在最终单纯形表上Xk是非基变量。是非基变量。 由于单纯形表的迭代是约束方程的增广矩阵的行变换，Pk变成Pk仅仅影响最终单纯形表上第k列数据，包括Xk的系数列、Zk以及 k，这时最终单纯形表上的Xk的系数列就变成了B-1Pj,而Zk就变成CBB-1Pk，新的检验数 k=Ck-CBB-1Pk。若 k0，则原最优解仍然为最优解。若 k 0，则继续进行迭代以求出最优。 例例 以第二章例1为基础，设该厂除了生产，种产品外，现在试制成一个新产品，已知生产产品,每件需要设备2台时，并消耗A原料0.5公斤。B原料1.5公斤，获利150元，问该厂应该生产该产品多少？解：这是一个
9、增加新变量的问题。我们可以把它认为是一个改变变量X3在初始表上的系数列的问题，管管 理理 运运 筹筹 学学241 1单纯形表的灵敏度分析单纯形表的灵敏度分析., 0,25,150255 . 11005 . 050,5 . 125 . 05 . 15 . 02111010021PB）1.5，0.5，2（）1.5，0.5，2（）0，0，0（6666661 -333TT见表题的最优解可知原最优解就是新问这时新变量如下表所示这时就变成了上是非基变量，在最终表之后的第六列上，显然把它放在的一列，上添上新的一列变量，。这样在原来的最终表变成从ZCZXSX迭代次数基变量CBX1 X2 S1 S2 S3 X3
10、 b50 100 0 0 0 150X1501 0 1 0 -1 0.550 S200 0 -2 1 1 -250 X21000 1 0 0 1 1.5250 ZJ50 100 50 0 50 17527500CJ -ZJ0 0 -50 0 -50 -25管管 理理 运运 筹筹 学学251 1单纯形表的灵敏度分析单纯形表的灵敏度分析例 假设上例题中产品的工艺结构有了改进，这时生产1件产品需要使用1.5台设备 ，消耗原料A为2千克，原料B为1千克，每件产品的利润为160元，问该厂的生产计划是否要修改。 解：首先求出X3在最终表上的系数列 61PB填入下表,35,125100.5(50,0,100
11、),105 . 0125 . 1111010021PB66661ZCzj迭代次数基变量CBX1 X2 S1 S2 S3 X3 b50 100 0 0 0 1602X1501 0 1 0 -1 0.55050/0.5 S200 0 -2 1 1 050 X21000 1 0 0 1 1250250/1 ZJ50 100 50 0 50 12527500CJ -ZJ0 0 -50 0 -50 35管管 理理 运运 筹筹 学学261 1单纯形表的灵敏度分析单纯形表的灵敏度分析接下来又可以有新的迭代S3进基，6310,3,XX由于可知此解不是最优解 我们要进行第 次迭代 选为入基变量，为出基变量迭代次
12、数基变量CBX1 X2 S1 S2 S3 X3 b50 100 0 0 0 1503X31602 0 2 0 -2 1100- S200 0 -2 1 1 05050/1 X2100-20 1 -2 0 3 0150250/3 ZJ120 100 120 0 -20 16031000CJ -ZJ-70 0 -120 0 20 0管管 理理 运运 筹筹 学学271 1单纯形表的灵敏度分析单纯形表的灵敏度分析接上页 可知此规划的最优解X1=0, X2=0, S1=0, S2=0, S3=50, X3=200,此时，最大目标函数为32000元。也就是说，该厂的新的生产计划为不生产、产品，生产产品20
13、0件, 可获得最大利润32000元。迭代次数基变量CBX1 X2 S1 S2 S3 X3 b50 100 0 0 0 1504X31602 0 2 0 -2 1200- S300 0 -2 1 1 05050/1 X2100-2 1 4 -3 0 00250/3 ZJ120 100 80 20 0 16032000CJ -ZJ-70 0 -80 -20 0 0管管 理理 运运 筹筹 学学281 1单纯形表的灵敏度分析单纯形表的灵敏度分析 2.最终表上最终表上XK是基变量：在初始表上的变量是基变量：在初始表上的变量XK的系数的系数PK改变为改变为PK，经过迭代后，在最终表上，经过迭代后，在最终表
14、上XK是基变量，是基变量，（比如（比如X1，X2，制作产品，制作产品1，产品，产品2的工艺有改善，在这种的工艺有改善，在这种情况下原最优解的可行性和最优解都可能被破坏，问题十情况下原最优解的可行性和最优解都可能被破坏，问题十分复杂）一般不去修改最终单纯形表，而是重新用单纯形分复杂）一般不去修改最终单纯形表，而是重新用单纯形法计算。法计算。管管 理理 运运 筹筹 学学291 1单纯形表的灵敏度分析单纯形表的灵敏度分析四、增加一个约束条件的灵敏度分析（增加一个约束条件对最优解的影响） 在原线性规划中增加一个约束条件时,（1）先将原问题的最优解的变量值代入新增的约束条件，如满足则说明新增的条件没有起
15、到限制作用，故原最优解不变，停止计算。（2）否则将新增的约束添入原最终单纯形表上，进一步求解。 下面仍以第三章例1为例来加以说明。 例：假如该工厂除了在设备台时，原材料A、B上对该厂的生产有限制外，还有电力供应上的限制。最高供应电量为5000度，而生产一个产品需要用电10度，而生产一个产品需要用电30度。试分析此时该厂获得最大利润的生产计划？ 管管 理理 运运 筹筹 学学301 1单纯形表的灵敏度分析单纯形表的灵敏度分析 1x2x解：先将原问题的最优解=50=50，=250代入用电量的约束条件得：1050+30250=500+75005000,所以原题的最优解不是本题的最优解。在用电量的约束条
16、件中加入松驰变量S4后得：12410 x +30 x +s =5000把这个约束条件加入到原最终单纯形表上，其中S4为基变量，得表如下：BC1x2x1s2s3s4s1x2s2x4sjz迭代迭代次数次数基变量基变量b b比值比值50501001000 00 00 00 050501 10 01 10 0-1-10 050500 00 00 0-2-21 11 10 050501001000 01 10 00 01 10 02502500 0101030300 00 00 01 150005000505010010050500 050500 0275027500 00 00 0-50-500 0-
17、50-500 0jjjcz1210305000 xx管管 理理 运运 筹筹 学学311 1单纯形表的灵敏度分析单纯形表的灵敏度分析 在上表中的X1，X2不是单位向量，故进行行的线性变换，得迭代迭代次数次数基变量基变量C CB Bx x1 1x x2 2s s1 1s s2 2s s3 3s s4 4b b比值比值50501001000 00 00 00 0 x x1 150501 10 01 10 0-1-10 05050s s2 20 00 00 0-2-21 11 10 05050 x x2 21001000 01 10 00 01 10 0250250s s4 40 00 00 0-10
18、-100 0-20-201 1-3000-3000z zj j505010010050500 050500 027500275000 00 0-50-500 0-50-500 0把上表中的S4行的约束可以写为：13410203000sss 上式两边乘以（-1），再加上人工变量a1得：134110203000sssa用上式替换上表中的S4行，得下表：jjjcz管管 理理 运运 筹筹 学学321 1单纯形表的灵敏度分析单纯形表的灵敏度分析迭代迭代次数次数基变基变量量x x1 1x x2 2s s1 1s s2 2s s3 3s s4 4a a1 1b b比值比值50501001000 00 00
19、00 0-M-Mx x1 150501 10 01 10 0-1-10 00 05050s s2 20 00 00 0-2-21 1(1)(1)0 00 05050 x x2 21001000 01 10 00 01 10 00 0250250s s4 4-M-M0 00 0-10-100 0-20-201 11 130003000z zj j505010010050-10M50-10M0 050-20M50-20M0 0-M-M0 00 010M-5010M-500 020M-5020M-500 00 0 x x1 150501 10 0-1-11 10 00 00 0100100s s3
20、30 00 00 0-2-21 11 10 00 05050 x x2 21001000 01 12 2-1-10 00 00 0200200s s4 4-M-M0 00 05050-20-200 0-1-11 120002000z zj j5050100100150-50M150-50M20M-5020M-500 0M M-M-M0 050M-15050M-15050-20M50-20M0 0-M-M0 0 x x1 150501 10 00 03/53/50 0-1/50-1/501/501/50140140s s3 30 00 00 00 01/51/51 1-2/50-2/502/50
21、2/50130130 x x2 21001000 01 10 0-1/5-1/50 02/502/50-2/50-2/50120120s s4 40 00 00 01 1-2/5-2/50 0-1/50-1/501/501/504040z zj j50501001000 010100 03 3-3-30 00 0-10-100 0-3-3-M+3-M+3jjjczjjjczjjjcz管管 理理 运运 筹筹 学学331 1单纯形表的灵敏度分析单纯形表的灵敏度分析 由上表可知，最优解为：1212311401200 xxsssa 即该工厂在添加了用电限量以后的最优生产计划为产品生产140件，产品生产
22、120件。管管 理理 运运 筹筹 学学34上节回顾上节回顾单纯形法的灵敏度分析1.目标函数系数Cj的灵敏度2.常数项bj的灵敏度分析3.系数矩阵A的灵敏度分析 在初始表上的变量XK的系数PK改变为PK，经过迭代后，在最终表上XK是基变量，（比如X1，X2，制作产品1，产品2的工艺有改善，在这种情况下原最优解的可行性和最优解都可能被破坏，问题十分复杂）一般不去修改最终单纯形表，而是重新用单纯形法计算。4.增加一个约束条件的灵敏度分析 （1）先将原问题的最优解的变量值代入新增的约束条件，如满足则说明新增的条件没有起到限制作用，故原最优解不变，停止计算。 （2）否则将新增的约束添入原最终单纯形表上，
23、进一步求解。管管 理理 运运 筹筹 学学35对偶单纯形法： 对偶单纯形法也是解决线性规划问题的一种方法。对偶单纯形法是在保持原有问题的所有检验数都小于0的情况下，通过迭代使得所有的约束都大于等于0，最后求得最优解。 优点：简化计算是对偶单纯形法的优点 例子： 缺点：但是它在使用上有很大的局限，这主要是 大多数线性规划问题很难找到初始解使得其所有检验数都小于0。 适用目标函数的特点： A.max f= -M1*X1-M2*X2.的形式 B.用在灵敏度分析中（增加约束条件的）。 上节回顾上节回顾5021 xx管管 理理 运运 筹筹 学学36 1.对偶问题的定义 2.原问题与对偶问题的关系 3.如何
24、根据原问题的结果去找对偶问题的答案 4.如何将原问题转化成对偶问题 5.对偶规划的基本性质2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学37任何一个求极大化的线性规划问题都有一个求极小化的线性规划问题与之对应，反之亦然，如果任何一个求极大化的线性规划问题都有一个求极小化的线性规划问题与之对应，反之亦然，如果我们把其中一个叫原问题，则另一个就叫做它的对偶问题，并称这一对互相联系的两个问题为一我们把其中一个叫原问题，则另一个就叫做它的对偶问题，并称这一对互相联系的两个问题为一对对偶问题。对对偶问题。例题例题1 1 某工厂在计划期内安排、两种产品，生产单位产品所需设备A、B
25、、C台时如表所示 该工厂每生产一单位产品 可获利50元，每生产一单位产品可获利100元，问工厂应分别生产多少 产品和产品，才能使工厂获利最多？解：设 为产品 的计划产量， 为产品的计划产量，则有目标函数： Max z z=50X1 +100 x2约束条件： ， 资源限量 设备 A 1 1 300 台时 设备 B 2 1 400 台时 设备 C 0 1 250 台时 1x2x30021 xx400221 xx2x2502x1x02 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学38 现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备A、B、C，那么该厂
26、的厂长应该如何来确定合理的租金呢？ 设 分别为设备A、B、C的每台时的租金。租金定价的原则是： 出租者：生产一个单位的 产品需消耗1个单位的设备A、2个单位的设备B、0个单位的设备C，获利50个单位；那么，将这些资源（设备台时）全部转让时所获得的利润 应不少于50个单位，否则就不出租还是用于生产 产品以获利50元；同样把生产一个单位 产品所需各设备的台时的总租金也不应当低于原利润100元， 即，否则这些设备台时就不出租，还是用于生产 产品以获利100元。3,21,yyy50221 yy100321yyy2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学39对于租用者，他要
27、求在满足上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好，即min ，这样我们得到了该问题的数学模型： 目标函数： 约束条件： 这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题原问题，而另外一个叫对偶问对偶问题题。321250400300yyy321250400300minyyyf0,10050232132121yyyyyyyy管管 理理 运运 筹筹 学学40 如果我们把求目标函数最大值的线性规划问题看成原问题，则求目标函数最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数
28、学模型上的关系。 1 求目标函数最大值的线性规划问题中有n 个变量 m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有m个变量n个约束条件，其约束条件都为大于等于不等式。 2 原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第i个变量的系数就等于对偶问题中的第i个约束条件的右边常数项。 3 原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第i个约束条件的右边常数项就等于零对偶问题的目标函数中的第i个变量的系数。 2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学
29、414 对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置。 设 A=则 mnmmnaaaaaa.2111211mnnnmTaaaaaaA2112111管管 理理 运运 筹筹 学学42如果我们用矩阵形式来表示，则有原问题： 其中A是 矩阵m*n，该问题有m个约束条件n个变量，x= ,b= , c= 对偶问题： 其中 是A的转置， 是b的转置, 是c的转置, y= 现在我们用单纯形法求对偶问题的解。0,maxxbAxcxz).,.,(21ncccTmbbb),.,(21TATbTCTmyyy),.,(210.minycyAybfTTT2 2 线性规划的对偶问题线性规划的对偶问题Tnxxx,21
30、管管 理理 运运 筹筹 学学43 加上剩余变量 和人工变量 ，把此问题化成标准型如下：把上述数据填入单纯形表计算。21,ss1a1321500400300)max(Mayyyf0,10050212132123211121assyyysyyyasyy2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学44迭代变量基变量 b比值-300-400-25000-M 1-M1 0 -1 0 15050/2-250 1 1 1 0 -1 0 100100/1-M-250-2M-250-250M250-M-50M-25000M-2502M-1500-M-25002-4001/210-1/
31、201/225-2501/2011/2-1-1/275-325-400-25075250-75-287502500-75-250-M+753-300120-10150-2500-111-1-150-300-350-25050250-50-275000-500-50-250-M+50bc1y2y3y2s1s1a1a3yjzjjzc 2y3y2/1752/125jzjjzc 1y3yjzjjzc 2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学45 由上表，最优解：由上表，最优解： =50， -f 的最大值为的最大值为-27500，即目标函数，即目标函数f的最大值为的最大值
32、为f=27500元。元。 从上面可知租金：从上面可知租金：A设备为设备为50元，元，B设备为设备为0元，元，C设备为设备为50元。这样把工元。这样把工厂的所有设备出租可共得租金厂的所有设备出租可共得租金27500元。对出租者来说这租金是出租者愿意出元。对出租者来说这租金是出租者愿意出租设备的最小费用，因为这是目租设备的最小费用，因为这是目 标函数的最小值。标函数的最小值。 通过比较，我们发现：对偶问题的最优解即最佳租金恰好等于原问题各通过比较，我们发现：对偶问题的最优解即最佳租金恰好等于原问题各种种设备的对偶价格。设备的对偶价格。 对于两个有对偶关系的线性规划的问题，我们只要求得了对于两个有对
33、偶关系的线性规划的问题，我们只要求得了其中一个最优解，就可以从这个问题的对偶价格而求得其对偶问题的最优其中一个最优解，就可以从这个问题的对偶价格而求得其对偶问题的最优解，知道其中一个最优值也就找到了其对偶问题的最优值，因为这两个最解，知道其中一个最优值也就找到了其对偶问题的最优值，因为这两个最优值相等。优值相等。 1y0, 0, 0,50, 012132assyy2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学46 下面来阐述如何写出一个线性规划问题的对偶问题。为了便于阐述，我们不妨以下面的线性规划为例，写出它的对偶问题。 S.T. 321643maxxxxz0,200
34、35,10046,440632321321321321xxxxxxxxxxxx2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学47 这是一个求最大值的线性规划问题，为了写出它的对偶问题，我们不妨把它的约束条件都变换成取小于号的不等式。显然第一个约束条件已符合要求，不要做任何变动，而第二个约束条件，我们只要两边都乘以（-1），使不等号方向改变即可，得 这样第二个约束条件也就符合要求。对于第三个约束条件，我们可以用小于等于和大于等于两个约束条件来替代它。即有 显然，这两个约束条件与原来第三个约束条件是等价的，我们再把其中的两边都乘以（-1），得 10046321xxx200
35、3520035321321xxxxxx20035321xxx20035321xxx2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学48 通过上面的一些变换，我们得到了一个和原线性规划等价的线性规划问题： s.t. 321643maxxxxz0,2003520035,10046,440632321321321321321xxxxxxxxxxxxxxx2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学49 这个求最大值的线性规划问题的约束条件都取小于等于号，我们马上可以写出其对偶问题： s.t.3 321200200100440minyyyyf, 0,
36、 66, 43343, 355623 3213 3213 3213 321yyyyyyyyyyyyyyyy2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学50 这里 和 一样都是不同的决策变量，为了表示这两个决策变量都来源于原问题的第三个约束条件，记为 。 因为在该对偶问题中 和 的系数只相差一个符号，我们可以把上面的对偶问题化为： s.t.3 3, yy21, yy3y3 y)(200100440min3 321yyyyf, 0, 6)(6, 4)(343, 3)(5623 3213 3213 3213 321yyyyyyyyyyyyyyyy2 2 线性规划的对偶问题
37、线性规划的对偶问题3 3, yy管管 理理 运运 筹筹 学学51 进一步，我们可以令 ，这时当 时， ，当 时， 。这也就是说，尽管 但 的取值可以为正，可以为0，可以为负，即 没有非负限制。 这样我们把原规划的对偶问题化为 s.t. 没有限制。 对照原线性规划问题，我们可以知道： 当原线性规划问题的第当原线性规划问题的第i个约束条件取等号时，则其对偶问题的个约束条件取等号时，则其对偶问题的 i个决策变量没有非个决策变量没有非负限制。负限制。 如果当原线性规划问题中的第如果当原线性规划问题中的第 i个决策变量个决策变量 没有非负限制时，我们也可以用没有非负限制时，我们也可以用 进行替换，这里进
38、行替换，这里 ， ，用类似的方法知道其对偶问题中第，用类似的方法知道其对偶问题中第 i个个约束条件取等号。约束条件取等号。3 33yyy3 3yy 0y3 3yy 03y, 0,3 3yy3y3y321200100440minyyyf, 0, 66, 4343, 356221321321321yyyyyyyyyyy3yixiiixxx 0ix0 ix2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学52 原线性规划问题为： s.t. 无非负限制。321493minxxxf, 0,24035,6032,180322121321321xxxxxxxxxx3x2 2 线性规划的
39、对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学53上节回顾 1.对偶问题的定义 任何一个求极大化的线性规划问题都有一个求极小化的线任何一个求极大化的线性规划问题都有一个求极小化的线性规划问题与之对应，反之亦然，如果我们把其中一个叫性规划问题与之对应，反之亦然，如果我们把其中一个叫原问题，则另一个就叫做它的对偶问题，并称这一对互相原问题，则另一个就叫做它的对偶问题，并称这一对互相联系的两个问题为一对对偶问题。联系的两个问题为一对对偶问题。 2.原问题与对偶问题的关系a 求目标函数最大值的线性规划问题中有求目标函数最大值的线性规划问题中有n 个变量个变量 m个约束条个约束条件，它的约束条件
40、都是小于等于不等式。而其对偶则是求件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有目标函数为最小值的线性规划问题，有m个变量个变量n个约束条个约束条件，其约束条件都为大于等于不等式。件，其约束条件都为大于等于不等式。b 原问题的目标函数中的变量系数为对偶问题中的约束条件原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项。的右边常数项。c 原问题的约束条件的右边常数项为对偶问题的目标函数中原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。的变量的系数。d 对偶问题的约束条件的系数矩阵对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置
41、。是原问题约束矩阵的转置。管管 理理 运运 筹筹 学学54 3.如何根据原问题的结果去找对偶问题的答案 对于两个有对偶关系的线性规划的问题，我们只对于两个有对偶关系的线性规划的问题，我们只要求得了其中一个最优解，就可以从这个问题的要求得了其中一个最优解，就可以从这个问题的对偶价格而求得其对偶问题的最优解，知道其中对偶价格而求得其对偶问题的最优解，知道其中一个最优值也就找到了其对偶问题的最优值一个最优值也就找到了其对偶问题的最优值 4.如何将原问题转化成对偶问题 当原线性规划问题的第当原线性规划问题的第i个约束条件取等号时，则个约束条件取等号时，则其对偶问题的其对偶问题的 i个决策变量没有非负限
42、制。个决策变量没有非负限制。 如果当原线性规划问题中的第如果当原线性规划问题中的第 i个决策变量没有非个决策变量没有非负限制时，其对偶问题中第负限制时，其对偶问题中第 i个约束条件取等号。个约束条件取等号。 5.对偶规划的基本性质管管 理理 运运 筹筹 学学553 3对偶规划的基本性质对偶规划的基本性质对偶规划的基本性质对偶规划的基本性质 1对称性对称性。即对偶问题的对偶是原问题。 2弱对偶性弱对偶性。即对于原问题（）和对偶问题（）的可行解 都有C bT 。 由弱对偶性，可得出以下推论： （1）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问
43、题目标函数值的上界。 （2）如原问题有可行解且目标函数值无界（或具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。 （3）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。YX,XY管管 理理 运运 筹筹 学学563 3对偶规划的基本性质对偶规划的基本性质3最优性最优性。如果 是原问题()的可行解， 是对偶问题()的可行解，并且 C = bT ，则 和 分别为原问题()和对偶问题(
44、)的最优解。4强对偶性强对偶性。即若原问题()及其对偶问题()都有可行解，则两者都有最优解；且它们的最优解的目标函数都相等。5互补松弛性互补松弛性。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零也即 若yi*0,则有 若 ，则有yi*=0XXYXYnjijijbxa1*njijijbxa1*Y管管 理理 运运 筹筹 学学57例子 已知LP问题 max z=x1+2x2+3x3+4x4 S.t. x1+2x2+2x3+3x4=20 2x1+x2+ 3x3+2x4=0其对偶问题的最优解为：y1=1
45、.2 y2=0.2 最优值为28.试用互补松弛性定理确定LP问题的最优解。 管管 理理 运运 筹筹 学学584 4对偶单纯形法对偶单纯形法 对偶单纯形法也是解决线性规划问题的一种方法。对偶单纯形法是在保持原有问题的所有检验数都小于0的情况下，通过迭代使得所有的约束都大于等于0，最后求得最优解。 简化计算是对偶单纯形法的优点，但是它在使用上有很大的局限，这主要是大多数线性规划问题很难找到初始解使得其所有检验数都小于0。但是在灵敏度分析中，有时需要对偶单纯形法，这样可以简化处理。下面以第二节例一为例。 上节分析中已知当250b1325时第一个约束条件的对偶价格不变，现在b1=300变成b1=350
46、，请问这时第一个约束方程的对偶价格应为多少呢？ 解：求出在第二次迭代表上的常数列 。带入第二次迭代表25050100022505050XX111bbbbbB管管 理理 运运 筹筹 学学594 4对偶单纯形法对偶单纯形法迭代次数基变量CBX1 X2 S1 S2 S3b50 100 0 0 02X1501 0 1 0 -1100 S200 0 -2 1 1-50 X21000 1 0 0 1250 ZJ50 100 0 50 50CJ -ZJ0 0 -50 0 -50为主元得到新表本题以得到新表运算按照单纯形法进行迭代为主元以基变量求出其中最小值作为入计算所有对应的可行解，如果有负数，则无如果都大
47、于所在行的各个函数变量在单纯形表中检查出基确定出基变量23k,3.,0),.2 , 1(X,. 2aaanjakjkjjkj1.确定出基变量，在常数列中找一个最小的负常量，把这个常量所在行作为出基变量管管 理理 运运 筹筹 学学60精品课件精品课件！管管 理理 运运 筹筹 学学61精品课件精品课件！管管 理理 运运 筹筹 学学624 4对偶单纯形法对偶单纯形法 4.检查常数列值，若已经都非负结束迭代，即为最优，如果还有负数重复1-4步。迭代次数基变量CBX1 X2 S1 S2 S3b50 100 0 0 02X1501 0 1 1/2 -1/275 S200 0 -2 -1/2 -1/225 X21000 1 0 0 1250 ZJ50 100 0 25 7528750CJ -ZJ0 0 0 -25 -75
