[宝典]运筹学3

[宝典]运筹学3 第三章对偶规划和灵敏度 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 教学目的和要求: 目的:使学生了解对偶规划的基本知识及具有进行简单的灵敏度分析的能力。 要求:理解对偶规划的概念，掌握对偶 规则 编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf ，了解对偶原理，掌握对偶单纯形法，理解影子 价格概念，掌握灵敏度分析的方法以及参数规划的方法。 重点:对偶规划，对偶单纯形法，灵敏度分析法。 难点:对偶原理，灵敏度分析法。 教学方法:讲授法，习题法。 学时分配:8学时 作业安排:见教材P71. 第一节对偶规划和对偶原理 每一种形式的线性规划，都有称作为它的对偶规划的线性规划与之对应，这两个规划在形式结构上， 求解，实际经济意义等方面有密切的关联，因此有必要对两个互为对偶的线性规划进行比较研究。 一、线性规划的对偶规划 1.对偶规划问题的提出: 例1.对外加工定价问题 某工厂利用甲、乙、丙、丁四种设备生产A、B、C三种产品，具体数据如下表所示。 A、B、C单位产品 的利润分别是4.5、5、7(百元)。如果工厂用甲、乙、丙、丁四种设备承担对外加工业务，工厂收取加工费， 那么每种设备的每工时应如何定价才是合适的,这一问题与第二章第一节例1 (生产 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 问题)是对应的。 产品 A B C 设备可供工时(h) 设备 甲 2 2 4 800 乙 1 2 3 650 丙 4 2 3 850 丁 2 4 2 700 单位利润 4.5 5 7 ---- 解:设y(i=1,2,3,4)分别表示设备甲、乙、丙、丁单位工时对外加工定价(单位为百元),显然将原生产1i 件产品A的工时用于对外加工，所收取的加工费，不应低于生产1件产品A所获利润， 即2y+y+4y+2y?4.5,同理有2y+2y+2y+4y?5, 4y+3y+3y+2y?7; 123412341234 总的收费为W=800y+650y+850y+700y ，考虑到市场竞争，加工费应尽量定得低，但不减少总收1234 入(与生产计划问题相比)，故W取最小值。 以上对外加工定价问题可用 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 模型表述如下: Min W=800y+650y+850y+700y 1234 满足 2y+y+4y+2y?4.5 1234 2y+2y+2y+4y?5 1234 4y+3y+3y+2y?7 1234 y?0(i=1,2,3,4) i 这个线性规划称为生产计划问题线性规划的对偶规划,它们互为对偶规划。 Max Z=4.5X+5X+7X123 满足 2X+2X+4X?800 123 X+2X+3X?650 123 4X+2X+3X?850 123 2X+4X+2X?700 123 X?0 (j=1,2,3) j 2.对偶规划的一般定义 (一)对称形式的对偶规划 设原线性规划问题是Max Z=CX 满足AX?b X?0…(3-3)， TT TTTT则定义其对偶规划为Min W=Yb 满足YA?C Y?0…(3-4)或写成MinW=bY满足AY?C Y?0， TTY=(Y……Y) X=(X……X) b=(b……b) C=(C……C)以上两个线性规划的对偶关系称为对称型1m1n1m1n 的对偶关系，它们互为对偶规划，本章称求极大化为原规划。 例2.求线性规划Max Z=2X+3X12 满足 X+2X?9 12 2X+X?10 12 4X?16 1 4X?12 2 X?0 (j=1,2)的对偶规划 j 解:对偶规划为MinW=9y+10y+16y+12y 1234 满足 y+2y+4y?2 123 2y+y+4y?3 12 4 y?0(i=1,2,3,4) i (二)非对称形式的对偶规划 若原规划是求目标函数极大化，但约束条件中出现“=”或“?”约束条件，决策变量中出现无非负要求或非正要求(?0)的决策变量，则其对偶规划称为非对称形式的对偶规划。在这种情况下，先把原规划化成对称的形式，再按对称形式的对偶关系写出其对偶规划，再整理便得非对称形式的对偶规划。 1)若原规划第k个约束条件是等式即aX+ aX+…+aX=bk11k22knnk 则可化为 aX+ aX+…+aX?b 即 aX+ aX+…+aX?bk11k22knn kk11k22knn k aX+ aX+…+aX?b-aX- aX-…-aX?-bk11k22knn k k11k22knn k 故原规划变为极大化Z=CX+CX+…+CX1122nn 满足 aX+ aX+…+aX?b i=1,2, …,k-1 i11i22inn i aX+ aX+…+aX?b k11k22knn k -aX- aX-…-aX?-bk11k22knn k aX+ aX+…+aX?b i= k+1, …,m i11i22inn i X?0,j=1,2, …,n j 极小化W=by+…+b(y'-y'')+…+by由对称形式的对偶关系可得其对偶规划:11kkkmm 满足ay+…+ a(y'-y'')+ …+ay?Cj=1,2, …,n 1j1kjkkmjm j y?0,i=1,2, …,m i?k y', y''?0，令y=y'-y'' , 则y无非负要求 ikkkkkk 故对偶规划变为极小化W=by+…+by+…+by11kkmm 满足ay+…+ ay+ …+ay?C , j=1,2, …,n y无非负要求， 1j1kjkmjm jky?0,i=1, …,k-1,k+1, …,m i 因此若原规划第k个约束条件是等式，则对偶规划第k个决策变量无非负要求。 2)若原规划第L个约束条件是“?”即 aX+ aX+ …+aX?bL11L22Lnn L 则可化为 -aX- aX- …-aX?-bL11L22Lnn L 故原规划变为极大化Z=CX+CX+…+CX1122nn 满足 aX+aX+…+aX?b, i=1,2,…,L-1 i11i22inn i -aX-aX-…-aX?-bL11L22Lnn L aX+aX+ …+aX?b ,i=L+1,…,m i11i22inn i X?0,j=1,2, …,n j 由对称形式的对偶关系可得其对偶规划 极小化W=by+…+(-b) y'+…+by11LLmm， 满足 ay+…+ (-a) y'+ …+ay?C j=1,2, …,n 1j1LjLmjm j y?0,i=1,2, …,m ， i?L , y' ?0令y=-y' , 则y?0 iLLLL 故对偶规划变为极小化W=by+…+by+…+by11LLmm 满足ay+…+ ay+ …+ay?C , j=1,2, …,n y?0 ，1j1LjLmjm jLy?0,i=1, …,L-1,L+1, …,m i 因此若原规划第L个约束条件是?，则对偶规划第L个决策变量y具有非正要求(?0 )。L 3)如果原规划的第S个决策变量无非负要求，那么对偶规划的第S个约束条件是等式。 4)如果原规划的第t个决策变量要求满足非正要求?0，那么对偶规划的第t个约束条件是?不等式。 对偶规则表3-5 原(对偶)规划:极大化Z 对偶(原)规划:极小化W m:约束条件数 决策变量数 n:决策变量数 约束条件数 A:约束条件系数矩阵 约束条件系数矩阵转置 b:约束条件右端常数向量 目标函数系数向量 C:目标函数系数向量 约束条件右端常数向量 原(对偶)规划第k个约束条件是等式 对偶(原)规划第k个决策变量是无非负要求 “?”不等式 ?0 “?”不等式 ?0 原(对偶)规划第S个决策变量是 对偶(原)规划第S个约束条件是 无非负要求 等式 ?0 “?”不等式 ?0 “?”不等式 例3.写出线性规划Min Z=-7X+14X+3X123 满足 X+6X+28X?5 123 -2X+3X-17X?6 123 X+ X- 4X=7 123 -X-7X+2X=-4 X, X?0, X无非负要求,的对偶规划解:1 2 3231 对偶规划为Max W=5y+6y+7y-4y 1234 满足 y-2y+y-y=-7 1234 6y+3y+y-7y?14 1234 28y-17y-4y+2y?3 1234 y?0, y?0, y, y无非负要求 1234 二、对偶规划的性质和原理 因非对称型的问题能转化为等价的对称型问题，故下面以对称型的对偶规划为基础 定理1.对称型定理 对偶规划的对偶规划是原规划。 TT 证:对偶规划式(3-4)可化为Max (-W)=-bY TTTT满足-AY?-C, Y?0,则由对称型式的对偶关系可得其对偶规划为 TTTTTTMin Z'=X(-C)满足X(-A)?-b,X?0 ,令Z=-Z'， 则可化为Max Z=CX,满足AX?b,X?0,此对偶规划即原规划定理2.弱对偶性定理 若X,Y分别是原规划和对偶规划的可行解,则必有CX?Yb. 证:因为AX?b, X?0, YA?C, Y?0.所以YAX?Yb, YAX?CX, 故CX?Yb. 定理3.若原(对偶)规划具有可行无界解(有可行解但无最优解),则其对偶(原)规划无可行解。由定理2,用反证法即可得定理结论,这个定理的逆不成立。 定理4.若X和Y分别是原规划和对偶规划的可行解，且CX,Yb，则X，Y必分别 是原规划和对偶规划的最优解。 定理5.强对偶性定理 若原规划和对偶规划都有可行解，则两者都有最优解，且最优值相等。 X和Y，U和V定理6.互补松弛定理 若原规划及其对偶规划分别有可行解分别为它们相应的松弛变量和 即AX，U,b,YA-V,C,X,0,Y,0,U,0,V,0,则X和Y剩余变量，分别是原规划和对偶规划的最优解的 VX,0,YU,0成立。必要充分条件是 (0)(0)(0)T(0) (0)定理7.设X=(X, X)是原规划的一个基可行解，B和U是相应的基和松弛向量，即X = BN0B-1(0)(0) (0) (0) (0)(0) Bb, A X+ U=b, X?0, U?0,则X和U的检验数是对偶规划的一个基本解。0 定理6和定理7说明原规划和对偶规划之间还有如下对偶关系: 原规划 对偶规划 n个决策变量 n剩余变量 m个松弛变量 m个决策变量 基可行解 基本解的检验数 基可行解的检验数 基本解 定理6还表明，在最优解中原(对偶)规划中不为0的变量在对偶(原)规划中对应变量一定等于0. 例4.运用互补松弛定理求解线性规划 Max Z=2X+3X12 满足 X+2X?9 12 2X+X?10 12 4X?16 1 4X?12 2 X?0 (j=1,2)的对偶规划， j 已知原规划的最优解X=11/3, X=8/3;最优值Z=46/3. 12 解:设U(j=1,2,3,4)是原规划的松弛变量.把最优解代入第一个约束条件，得11/3+2×8/3+U=9, 故U=0,j11 同理可得U=0, U=4/3,U=4/3设V,V是对偶规划的剩余变量,Y(i=1,2,3,4)是决策变量,由互补松弛定理23412i可得V=0, V=0, Y=0,Y=0,1234 原规划的对偶规划为:Min W=9y+10y+16y+12y 1234 满足 y+2y+4y?2 123 2y+y+4y?3 12 4 y?0(i=1,2,3,4) i 把V=0, V=0, Y=0, Y=0, 代入对偶规划约束条件, 1234 得y+2y=2， 2y+y=3 ，所以对偶规划的最优解为y=4/3, y=1/3,最优值W=46/3. 121212 第二节对偶单纯形法和影子价格 讨论对偶单纯形法能深化对单纯形法的理解，影子价格能为企业管理者提供重要的经济信息和组织管 理的数量依据。 一、对偶单纯形法 根据上节讨论的对偶原理，在原规划的单纯形表迭代中，是保持b列的非负，逐步使检验数成为非负，或 者称为保持可行性，实现最优性条件。根据对偶性，单纯形法的迭代过程也可以这样看，保持检验数全部 非负(原规划b列是对偶规划非基变量的检验数，基变量的检验数全部为0),将不可行的基本解逐步变为基 可行解，或者称为保持最优性条件，实现可行性条件，从而得到了最优解。这就是对偶单纯形法的基本思 路。 1.对偶单纯形法的步骤 只要检验数符合最优性条件(即全部非负)，可以从一个不可行的基本解开始，逐步消除基本解的不可行性， 从而得到最优解，这个方法称为对偶单纯形法。 -11)找一个检验数全部非负的初始基本解，列出初始单纯形表，若基变量的取值X=Bb?0,则初始基本解即B为最优解，否则转入下一步进行基本解的转换。 -1-1-12)确定出基变量，由Min{(Bb)|(Bb)，0}=(Bb)=确定X为出基变量。 b,iirrr 3)确定进基变量,若X所在行的各元素a全部非负(?0),则无可行解， rrj 否则计算,=Min{,,|a| |a，0}= ,,|a| ,确定X为进基变量，a是主元。 jrjrjkrkkrk br,4)以元素a为中心进行迭代，即a'=a/a，j=1,2, …,n, b,, rkrjrjrkrark barik'=a-(aa),a, i?r, j=1,2, …,n，a,'=,- (a,),a?0, j=1,2, …,n,b,b,,i,r,ijijrjikrkjjrjkrk iiark 5)在基变量X列用X取代X， X成为基变量，若b列中即基变量取值仍有负的，则重复2) ~ 4),直到Bkrk b列中不含负的元素，即得最优解。 例5.用对偶单纯形法求解Min W=9y+10y+16y+12y 1234 满足 y+2y+4y?2 123 2y+y+4y?3 y?0(i=1,2,3,4) 12 4i 解:为了找到一个检验数全部非负的初始基本解，将线性规划化为下面的形式，令W'=-W, Max W'=-9y-10y-16y-12y 1234 满足 -y-2y-4y+y=-2 123 5 -2y-y-4y+y=-3 12 4 6 y?0(i=1,2,3,4,5,6) i 用单纯形表求解如下表 Cj -9 -10 -16 -12 0 0 b CB YB Y1 Y2 Y3 Y4 Y5 Y6 0 Y5 -1 -2 -4 0 1 0 -2 0 Y6 -2 -1 0 [-4] 0 1 -3? 9 10 16 12 0 0 W'=0 ,j 0 Y5 [-1] -2 -4 0 1 0 -2 ? -12 Y4 1/2 1/4 0 1 0 -1/4 3/4 3 7 16 0 0 3 W'=-9 ,j -9 Y1 1 2 4 0 -1 0 2 -12 Y4 0 [-3/4] -2 1 1/2 -1/4 -1/4? 0 1 4 0 3 3 W'=-15 ,j -9 Y1 1 0 -4/3 8/3 1/3 -2/3 4/3 -10 Y2 0 1 8/3 -4/3 -2/3 1/3 1/3 0 0 4/3 4/3 11/3 8/3 W'=-46/3 ,j 2.对偶单纯形法的特点 1)先确定出基变量，后确定进基变量 2)初始基本解可以是不可行的，只要检验数符合最优性条件，就可以进行基的转换，不需要增添人工变量，计算大为简化。 3)若原规划的决策变量很少，但约束条件较多，可转用对偶单纯形法求解其对偶规划，再利用对偶原理可得原规划解，可简化计算。 4)在灵敏度分析中，许多运算用对偶单纯形法求解比较方便， 但在一般情况下，大多数非对称型的线性规划及其对偶规划，都较难找到一个检验数全部非负的初始基本 解，因而在求一般线性规划时较少使用对偶单纯形法。 二、影子价格 影子价格是对偶规划解的一个经济学解释，它能告诉决策者，在现有生产情况下，哪种资源最为关键,企业以什么样的价格买进或卖出某种资源才是合适的。设B=(P P … P)是原规划Max Z=CX，满足12m**-1-1AX=b，X?0，的最优基，则目标函数最优值Z=CBb，y=CB是对偶规划的最优解。由于BB********-1Z=CBb=yb= yb+ yb+ …+yb, 由此解得,Z/,b=y,i=1,2, …,m,所以y(i=1,2, …,m)表示在其B1122mmiii*它条件不变的情况下，第i种资源变化一个单位时，所导致的目标函数值的变化，即Z对b的变化率。i * 1.影子价格的含义y(i=1,2, …,m)的值代表在现有生产情况下，企业对第i种资源的估价，这种估价是i 针对具体企业的具体产品、具体情况而存在的一种特殊价格，称为影子价格。 2.影子价格的作用 1)在市场经济情况下，影子价格对市场和企业的生产有调节作用，当某种资源的市场价格低于企业的影子价格时，企业应购进一定数量的资源来扩大生产;当市场价格高于企业的影子价格时，企业应卖出资源。 2)影子价格可为管理者提供新产品定价的依据, 例如在生产计划问题中，如果有一种新产品生产时，每单位需要耗用设备甲、乙、丙、丁的工时数分别为 T、0、2、4,则新产品的定价一定不能少于(19/14, 0, 3/14, 13/28)(2, 0, 2, 4)=5百元，工厂才能比现有收益有2 所增加，否则不考虑生产。 第三节灵敏度分析 在线性规划模型中，C称为价值系数，b称为资源数量,a称为消耗系数。灵敏度分析就是研究当这jiij 些数据中某个或n个变动时，对最优解的影响;以及要使生产有个较稳定的计划，这些数据应控制在什么范围;如果数据的变动使得最优解改变，那么怎样利用原有的结果求新的最优解等等问题。 一、价值系数C的变化 j -1-1设B是求目标函数极大化线性规划的最优基，由于X=Bb - BNX ， BN -1-1Z=CX=CX+CX=CBb - (CBN-C)X ， BBNNBBNN -1-1-1-1,= CBN-C，,= CBB-C，,= CBA-C，Z =CBb，C的改变将影响最优性条件是否仍NBN BBB ABBj 然满足，及是否影响目标函数值。 1.非基变量X的系数C的改变 jj -1C'=C+?C，此时,'= CBP-C'=,-?C，若,'?0,则原最优解不变，即?C?,是使原最优解仍为最优jjjjBjjj jjjj 解的条件，此时最优值也不变。若?C,,，则,',0,B不再是最优基，在原最优单纯形表中，C变为C'，jjjjj ,变为,'，按单纯形法迭代直到得最优解。 jj 例7.线性规划Max Z=X+5X+3X+4X1234 满足 2X+3X +X+2X?800 1234 5X+4X+3X+4X?1200 1234 3X+4X+5X+3X?1000 1234 X?0 (j=1,2,3,4)的最优单纯形表如表3-9. j Cj 1 5 3 4 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 X7 0 X5 1/4 0 -13/4 0 1 1/4 -1 100 4 X4 2 0 -2 1 0 1 -1 200 5 X2 -3/4 1 11/4 0 0 -3/4 1 100 ,j 13/4 0 11/4 0 0 1/4 1 1300 求1)若保持最优解不变，则非基变量X，X的系数C，C各应控制在什么范围。 1313 2)当?C=4时，线性规划的最优解是否改变, 1 解:1)由表3-9看到，要使最优解保持不变，则?C?13/4,即C要满足C?1+13/4=17/4,类似可求出111C?3+11/4=23/4. 3 2)当C=1+4=5时，由(1)的结果知道，最优解要改变.将表3-9的C改为5, ,改为4×2，5×(,4/3),5=,1113/4,按单纯形法进行迭代，得表3-10 Cj 5 5 3 4 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 X7 0 X5 1/4 0 -13/4 0 1 1/4 -1 100 4 X4 [2] 0 -2 1 0 1 -1 200 5 X2 -3/4 1 11/4 0 0 -3/4 1 100 ,j -3/4 0 11/4 0 0 1/4 1 1300 0 X5 0 0 -3 -1/8 1 1/8 -7/8 75 5 X1 1 0 -1 1/2 0 1/2 -1/2 102 5 X2 0 1 2 3/8 0 -3/8 5/8 175 ,j 0 0 2 3/8 0 5/8 5/8 1375 2.基变量X的系数C的改变 ii 当基变量X(1?i?m)的价值系数C改变为C+?C时，有C'=C+?C，其中?C=(0…0 ?C 0…0),iiiiBBBBi -1-1a此时,'= C'BP-C=,，?CBP= ,，?C, j=m+1…n, ijjBjjjBjji aa其中是在最优单纯形表中，基变量X所在行与非基变量X所在列交点处元素，若,'= ,，?C?0， ijijijjji j=m+1…n, 则原最优基不变，从而得使原最优基保持不变的?C的范围为: i ,,,,σσ,,,,jj-1最优解X=Bb,X=0也不变，但最优值改变,,,/a,0,ΔC,,/a,0？(3,5)BN,,,,ijiijmaxmin,,aa,,,,jjijij,,,, -1-1b了，新的最优值为Z'=C'Bb= CBb +?CBBi i 例8.在表3-9中，求使最优基不变的C，C的变化范围. 24 解:X是基变量，由式(3-5),保持最优基不变的?C的范围是22 11/4113/41/4,,,,,,,,ΔC,,,,-1??C?1/3, ,,,,22maxmin11/41,3/4,3/4,,,, 1/413/411/41,,,,同理，可求得保持最优基不变的?C的范围是,,,,ΔC,,,,4,,,,4maxmin12,2,1,,,, -1/4 ??C?1, 15/4 ?C?5. 44 例9.在表3-9中，如果?C=1,求例7所示线性规划的最优解。 2 解:因?C?[-1.1/3]，最优基保持不变,故当?C=1时.最优基将改变。在表3-9中，将C改为5+1=6,以222及非基变量的检验数， ,'=13/4+1×(-3/4)=5/2, ,'=11/4+1×11/4=11/2, ,'=1/4，1×(-3/4)=,1/2, ,'=1，1=2. 1367其实，检验数,'可以利用单纯形表直接计算然后按单纯形法迭代(见表3-11),得最优解为X=250,X=X= j21 3 X=0,最优值Z=1500. 4 Cj 1 6 3 4 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 X7 0 X5 1/4 0 -13/4 0 1 1/4 -1 100 4 X4 2 0 -2 1 0 [1] -1 200 6 X2 -3/4 1 11/4 0 0 -3/4 1 100 ,j 5/2 0 11/2 0 0 -1/2 2 1400 0 X5 -1/4 0 -11/4 -1/4 1 0 -3/4 100 0 X6 2 0 -2 1 0 1 -1 200 6 X2 3/4 1 5/4 3/4 0 0 1/4 100 ,j 7/2 0 9/2 1/2 0 0 3/2 1500 二、右端常数b的变化 i -1-1b的改变只影响原最优解的可行性及目标函数值X=Bb，Z= CBb，设b'= b，?b(1?K?m)则BBKKK T ?b=(0…?b…0)K bb …b11 121m -1又设B= b b …b21222m …………………… b b …b m1m2mm 若原最优基不变，则需满足: βΔb,,b，βΔb,,1kk11kk,,,, βΔbb，βΔb2kk,,11122kk,,,,,,,X,Bb,Bb，BΔb,b，,,0由上式得到，使原最优基不变的B,,,,？？,,,,,,,,βΔbb，βΔbmkkmmkk,,,,?b的范围是: K ,,,,bbii,/β,0,Δb,,/β,0？(3,6)但最优解改变为 ,,,,ik kikmaxminββii,,,,ikik m,1,1,,, X,Bb,最优值也改变为 Z,Z，(Cβ),b即Z,Z，CBΔb.,Biik kBi,1 例10.在例7所示线性规划中，求使最优基保持不变的b,b,b的变动范围。 123 ,112311/4,1，，，， ,,,,,1B,044,01,1-9得到解:由表3 ,,,, ,,,,03403/41,，，，， 由式(3-6)求得使最优基不变的?b, ?b, ?b的范围分别是 123 -100??b,-200??b?400/3, -100??b?100,即当各种资源在以下各范围内变动时， 123 最优基不变700?b,1000?b?4000/3，900?b?100. 123 例11.在例7所示线性规划中， 如果?b=,150，那么线性规划的最优基是否改变, 3 解:从例10的结果看到，b'=1000-150=850时,最优基要改变,因为: 3 11/4,1800250，，，，，， ,,,,,,,1,TBb,01,11200 ,350所以，B不再是可行基，将表3-9中b列由(100 ,200 ,100),,,,,, ,,,,,,0,3/41850,50，，，，，， T改为(250 ,350 ,-50)按对偶单纯形法消除不可行性，得最优解(见表3-12): X=X= X=0, X=850/31 234最优值Z=3400/3. Cj 1 5 3 4 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 X7 0 X5 1/4 0 -13/4 0 1 1/4 -1 250 4 X4 2 0 -2 1 0 1 -1 350 5 X2 -3/4 1 11/4 0 0 [-3/4] 1 -50 ,j 13/4 0 11/4 0 0 1/4 1 1150 0 X5 0 1/3 7/3 0 1 0 -2/3 700/3 4 X4 1 4/3 5/3 1 0 0 1/3 850/3 0 X6 1 -4/3 -11/3 0 0 1 -4/3 200/3 ,j 3 1/3 11/3 0 0 0 4/3 3400/3 三、约束条件矩阵元素a的改变 ij 1.非基变量X的系数向量P的改变 kk -1-1-1当P'= P+?P, ,'=CBP'–C= CB(P+?P) ,C= ,+CB?P要使原最优基不变，则,'kkkk Bk kBkkkkBk k -1?0,即CB?P=π?P?,,,…(3-7)否则将出现,',0可按单纯形法进行迭代。Bkkk k TTTT例12.在例7所示的线性规划中，X的系数向量?由(1 3 5)改变为(1 2 3);?由(1 3 5)改变为(1 3 2)3 考察原最优基是否改变，如果改变，求出新的最优解来。 TTT解:1)?P=(1,2,3)-(1,3,5)=(0,-1,-2).由表3-9看到π=(0,1/4,1)。 3 T因π?P=(0,1/4,1)(0,-1,-2)=,9/4，,11/4，故最优解不变。 3 TTP2) P改变为(1 3 2)后，?P=(0 0 -3)， π?P=,3,-11/4,故最优基改变。在表3-9中的X列改变33333 11/4,11,1/4，，，，，， ,,,,,,1,,,P,BP,01,13,1: 为 33,,,,,, ,,,,,,0,3/412,1/4，，，，，， T,'=, (0,1/4,1)(0, 0, -3)=11/4,3=,1/4然后按单纯形法进行迭代得最优解X=X=0,X=150,X=200,33+1 423最优值Z=1350. Cj 1 5 3 4 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 X7 0 X5 1/4 0 -1/4 0 1 1/4 -1 100 4 X4 2 0 [1] 1 0 1 -1 200 5 X2 -3/4 1 -1/4 0 0 -3/4 1 100 ,j 13/4 0 -1/4 0 0 1/4 1 Z=1300 0 X5 3/4 0 0 1/4 1 1/2 -5/4 150 3 X3 2 0 1 1 0 1 -1 200 5 X2 -1/4 1 0 1/4 0 -1/2 3/4 150 ,j 15/4 0 0 1/4 0 1/2 3/4 Z=1350 2.基变量X的系数向量P的改变:因P是B的一列，所以P的改变也就是B的改变，在最优单纯iiii 形表中所有元素都要改变，原最优表已无法利用，重新应用单纯形法求解。 3.增加新的决策变量Xn+1 T在原来的约束条件系数矩阵A中，增加列向量P=(a……a)同时目标函数中增加CXn+11n+1mn+1n+1n+1 -1项，对原最优表来说X是非基变量，故只要,= CBP- C?0，则最优解不变，若,,0,n+1n+1Bn+1n+1 n+1 -1则将原最优表中增加X列，其系数向量为BP=P,检验数为,，然后按单纯形法进行迭代。n+1n+1n+1n，1 T例13.在例7所示线性规划中，增加决策变量X,且P=(2 5 3),C分别等于4和5时，原最优解是否改变,888 (1)T解:当C=4时,由于,=(0 1/4 1)(2 5 3)-4=1/4，0,所以最优解不变,仍为X=0,X=100，X=0，X=200;881234 (2)T当C=5时，由于,=(0 1/4 1)(2 5 3)-5=-3/4,0,原最优解不再符合最优性。在表3-9上增添X列，888 -1其中=BP=(1/4,2,-3/4),,,=,3/4,然后进行迭代,得到最优解为X=X=X=0,X=175,X=100.P88134288 Cj 1 5 3 4 0 0 0 5 b CB XB X1 X2 X3 X4 X5 X6 X7 X8 0 X5 1/4 0 -13/4 0 1 1/4 -1 1/4 100 4 X4 2 0 -2 1 0 1 -1 [2] 200 5 X2 -3/4 1 11/4 0 0 -3/4 1 -3/4 100 ,j 13/4 0 11/4 0 0 1/4 1 -3/4 1300 0 X5 0 0 -3 -1/8 1 1/8 -7/8 0 75 5 X8 1 0 -1 1/2 0 1/2 -1/2 1 100 5 X2 0 1 2 3/8 0 -3/8 5/8 0 175 4 0 2 3/8 0 5/8 5/8 0 1375 ,j 4.增加新的约束条件: 若最优解能满足增加的约束条件，最优解不变，新增条件不起作用,否则，调整最优表，用对偶单纯形法迭 代。设新增条件为kX+kX，…，kX?b又设最优表中所示的约束条件为1122nn m+1 在新约束中增添松弛变量X?0,变为等式，X，aX，aX，？，aX,b i,1？mn+1 iim，1m，1im，2m，2innimm k(X，aX，？，aX)kb,则新增约束条件为，，,,并且从左边减去右边减iiim1m1innii,,i1i1 mm,,,,aX，aX，？aX，X,b,kb？(3-8),a,k,ka,j,m，1？n,，，，，，，，，，，,,m1m1m1m1m2m2m1nnn1m1iim1jjiij,,i1i1m因原来的最优解不满足新增条件，故在原最优表中增添X列,以及X中的X行，b,b,kb,0，，n，1Bn，1,m1m1ii,i1TX列的元素是(0，，0，1)是m1维的列向量，σ0,X行的元素是00,a,，a,，a,，1，b？？？，,n，1n，1n，1m，1m，1m，1m，2m，1nm，1 见表3-15,然后按对偶单纯形法，消除不可行性，得最优解。 例14.在例7所示线性规划中，增加约束条件:(?) 4X+4X+2X+2X?700 1234(?) 2X+3X +X?500,问表3-9所示的解X=0，X=100，X=0，X=200还是最优解吗,1241234 解:将原最优解代入约束条件(?) 和 (?)那么分别为800?700，500?500，所以约束条件(?) 是不起作用 的。对于(?) 增添松弛变量X,新约束(?) 成为4X+4X+2X+2X+X=700…(?)在(?)的左边减去812348 4[(-3/4)X+X+(11/4)X-(3/4)X+X)]+2(2X-2X+X+X-X)，右边减去4×100+2×200=800得到(?)3X12367134671 ,5X+X,2X+X=,100…(?)将(?)添入表3-9,得表3-16,按对偶单纯形法迭代得新最优解。3678 Cj 1 5 3 4 0 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 X7 X8 0 X5 1/4 0 -13/4 0 1 1/4 -1 0 100 4 X4 2 0 -2 1 0 1 -1 0 200 5 X2 -3/4 1 11/4 0 0 -3/4 1 0 100 0 X8 3 0 -5 0 0 1 [-2] 1 -100 13/4 0 11/4 0 0 1/4 1 0 1300 ,j Cj 1 5 3 4 0 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 X7 X8 0 X5 -5/4 0 -3/4 0 1 -1/4 0 -1/2 150 4 X4 1/2 0 1/2 1 0 1/2 0 -1/2 250 5 X2 3/4 1 1/4 0 0 -1/4 0 1/2 50 0 X7 -3/2 0 5/2 0 0 -1/2 1 -1/2 50 19/4 0 1/4 0 0 3/4 0 1/2 1250 ,j 第四节参数规划 灵敏度分析是研究单个或几个数据改变对线性规划最优解的影响;参数规划则是研究数据依某个参数而连续变化时，最优解的变动情况。本节讨论的只限于数据线性变化情形，因此又称线性参数规划。 参数规划求解的主要步骤是: 1)对含参数t的参数规划，先令t=0，用单纯形法求出最优解; 2)将t直接反映到最优单纯形表中，并用灵敏度分析的方法进行分析; 3)当t连续变化时，观察b列和检验数行各元素的变化，若b列出现负分量，则按对偶单纯形法消除不可行性，如果检验数出现负的，则用单纯形法进行迭代; 4)在迭代后的单纯形表上令t继续变化，重复步骤3),直到b不出现负值，检验数不出现负值为止。 一、目标函数系数向量C的变化 数学模型为:极大化Z(t)=(C+tC')X 满足AX=b,X?0其中C'是给定的n维行向量，t是参数。 例15.求解参数规划，其中参数t，0. T 极大化Z(t)=[(3 5)+t(2 –1)](X X)12 满足 X ?4 1 2X ?12 2 3X，2X ?18 12 X、 X ?0 12 解:令t=0，求解线性规划(表3-17),将参数t直接反映到表3-17中， Cj 3 5 0 0 0 b CB XB X1 X2 X3 X4 X5 0 X3 0 0 1 1/3 -1/3 2 5 X2 0 1 0 1/2 0 6 3 X1 1 0 0 -1/3 1/3 2 ,j 0 0 0 3/2 1 Z=36 得表3-18， Cj+tC' 3+2t 5-t 0 0 0 b CB XB X1 X2 X3 X4 X5 0 X3 0 0 1 1/3 -1/3 2 5-t X2 0 1 0 1/2 0 6 3+2t X1 1 0 0 -1/3 1/3 2 0 0 0 3/2-t7/6 1+t2/3 Z=36-2t ,j (1)T当t由0增大时，只要t?(3/2)/(7/6)=9/7，则检验数不会出现负值，因此，最优解都是X=(2 6 2 0 0)，t=9/7 是第一临界点。当t，9/7时，,,0,这时确定X为进基变量，用单纯形法迭代(表3-19)，44 Cj+tC' 3+2t 5-t 0 0 0 b CB XB X1 X2 X3 X4 X5 0 X4 0 0 3 1 -1 6 5-t X2 0 1 -3/2 0 1/2 3 3+2t X1 1 0 1 0 0 4 0 0 -9/2+t7/2 0 5/2-t/2 Z=27+5t ,j (2)T当9/7?t?(5/2)/(1/2)=5时，检验数全部非负这时最优解是X=(4 3 0 6 0),最优值Z=27+5t;t=5是第二临界 点。当t，5时，,,0, X成为进基变量，用单纯形法迭代，得表3-20， 55 Cj+tC' 3+2t 5-t 0 0 0 b CB XB X1 X2 X3 X4 X5 0 X4 0 2 0 1 0 12 0 X5 0 2 -3 0 1 6 3+2t X1 1 0 1 0 0 4 ,j 0 -5+t 3+2t 0 0 Z=12+8t T令t继续增大,恒有,?0,(j=1, …,5),所以当t ?5时,最优解为(4 0 0 12 6),最优值Z=12+8t。j 二、资源向量b的变化 数学模型为:极大化Z(t)=CX 满足AX=b+tb'，X?0,其中b'是给定的m维列向量，t是参数。 由灵敏度分析已经知道，t的变化会改变原最优解的可行性，但不会改变检验数行的元素，故只要 -1-1TB(b+tb')?0，则(B(b+tb'), 0)就是最优解。 例16.求解参数规划 极大化Z(t)=3X+2X+5X123 满足 X +2X+3X ?430+t 123 3X+ 2X ?460-4t 13 X， 4X ?420-4t 12 X、 X 、X?0 123 T解:在本例中，b'=(1 –4 –4)，t是参数。令t=0， 用单纯形法求解，得表3-21 Cj 3 2 5 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 2 X2 -1/4 1 0 1/2 -1/4 0 100 5 X3 3/2 0 1 0 1/2 0 230 0 X6 2 0 0 -2 1 1 20 4 0 0 1 2 0 1350 ,j 1/2,1/40t(3/2)t，，，，，，计算:将计算结果直接反映在表3-21上，即把b,,,,,,,1,B(tb),01/20,4t,,2t,,,,,,,,,,,,,211,4t,10t，，，，，， 230-2t、20-10t得表3-22 列的元素改为100+(3/2)t、 Cj 3 2 5 0 0 0 b+tb' CB XB X1 X2 X3 X4 X5 X6 2 X2 -1/4 1 0 1/2 -1/4 0 100 +(3/2)t 5 X3 3/2 0 1 0 1/2 0 230-2t 0 X6 2 0 0 -2 1 1 20-10t ,j 4 0 0 1 2 0 Z=1350-7t T从表3-22中看到，当-200/3?t?2时，最优解为X=(0,100 +(3/2)t,230-2t, 0, 0, 20-10t)，最优值Z=1350-7t。 当t，2时，基变量X=20-10t,0,按对偶单纯形法消除其不可行性，得表3-23 6 Cj 3 2 5 0 0 0 b+tb' CB XB X1 X2 X3 X4 X5 X6 2 X2 1/4 1 0 0 0 1/4 105-t 5 X3 3/2 0 1 0 1/2 0 230-2t 0 X4 -1 0 0 1 -1/2 -1/2 -10+5t 5 0 0 0 5/2 1/2 Z=1360-12t ,j T从表3-23中得到，当2?t?105时，最优解为X=(0, 105-t, 230-2t, -10+5t, 0, 0),最优值Z=1360-12t。 当t， 105时，基变量X=105-t，0,但在表3-23中，X行中的系数没有负的元素。所以原问题当t，105时没有22 可行解。从表3-22看到， 当t，-200/3时，基变量X=100+(3/2)t，0, 按对偶单纯形法消除不可行性，得2 表3-24. Cj 3 2 5 0 0 0 b+tb' CB XB X1 X2 X3 X4 X5 X6 0 X5 1 -4 0 -2 1 0 -400-6t 5 X3 1 2 1 1 0 0 430+t 0 X6 1 4 0 0 0 1 420-4t ,j 2 8 0 5 0 0 Z=2150+5t T从表3-24中得到，当-430?t?-200/3时,最优解为X=(0,0,430+t,0,-400-6t,420-4t),最优值Z=2150+5t。当t，-430时，基变量X=430+t，0,但表3-24中的X行中没有负的元素，所以当t，-430时，原规划没有可行33 解。 综上所述，该参数规划的临界点是-430、-200/3、2、105。