灵敏度分析

nullnull 灵敏度分析 灵敏度分析是在建立数学模型和求得最优解之后，研究线性规划的一些系数Cj、aij、bi变化时，对最优解产生什么影响？maxZ（或minZ）＝c1x1十c2x2十……十cnxn； a11x1＋a12x2十……十a1nxn≤b1 a21x1＋a22x2十……十a2nxn≤b2 am1x1＋am2x2十……十amnxn≤bm xj≥0 (j＝l、2、……，n) null 当线性规划问中的一个或几个参数变化时．可以用单纯形法从头计算，看最优解有无变化．但这样做既麻烦又没有必要。因为单纯形法的迭代计算是从一组基向量变换为另一组基向量，表中每步迭代得到的数字只随基向量的不同选择而改变，因此可把个别参数的变化直接在计算得到最优解的单纯形表上反映出来。这样就不需要从头计算，而直接对计算得到最优解的单纯形表进行审查，看一些数字变化后，是否仍满足最优解的条件，如果不满足的话，再从这个表开始进行迭代计算，求得最优解。null1. 灵敏度分析的基本原理 maxZ = CX; AX = b; (LP) s.t. X≥0. 对于选定的基B，不妨设 B = ( P 1, P 2,…, P m ). 将问题（LP）化为关于基B的典式 maxZ = CBB-1b + (CN — CBB-1N)XN ; XB + B-1NXN = B-1b ; s.t. XB, XN ≥0.null列出单纯形表 基本解 X = XB = B-1b 是最优解的条件是 XN 0 XB =B-1b ≥0 （1） 称为(原始)可行性条件 σN = CN — CBB-1N≤0 （2） 称为(原始)最优性条件 在实际问题中，下面这些数据或条件是会经常发生变化的： (1)目标函数系数cj的变化； (2)右端常数b的变化； (3)消耗系数aij的变化(包括增加新增变量和增加新的约束条件)．null 灵敏度分析是： (1)为了保持现有的最优解或最优基不变，找出这些数据变化的范围．即所谓数据的稳定性区间． (2)当这些数据的变化超出了(1)的范围时，如何在原有最优解或最优基的基础上，作微小的调整，尽快求出新的最优解或最优基． 由表可以看出，某些数据只和表中的某些块有关，因而当这些数据发生变化时，只需对上表中的某些块进行修改，便可得到新问题的单纯形表，从而能够进行判别和迭代，而不必从头开始计算线性规划问题，这正是单纯形法的优点之一． 下面分别讨论这些变化对最优解或最优解的影响．XB =B-1b ≥0 （1） σN = CN — CBB-1N≤0 （2） null 一、目标函数系数的灵敏度 1. 非基变量xj的价值系数cj的变化 cj改变为c’j=cj +Δcj 变化后的检验数为 σ‘j =cj +Δcj — CBB-1Pj. 要保持原有最优解不变，则必须 σ’j =cj + Δcj — CBB-1Pj ≤0 即 cj — CBB-1Pj cj + Δcj=σj + Δcj ≤0 所以即： Δcj ≤ —σj　　　null这就是保持原最优解不变时，非基变量xj的目标系数cj的变化范围．当超出这个范围时，原最优解将不再是最优解了，为了求新的最忧解，必须在原最优单纯形表的基础上，继续往下迭代以求得新的最优解．null2.基变量xj的价值系数cj的变化 某基变量xr的价值系数cr 改变为 c’r =cr + Δcj，因cr ∈CB，则 (CB +ΔCB) B-1A =CB B-1A+ (0,…, Δcr,…,0) B-1A = CBB-1A + Δcr(a‘r1, a‘r2,…, a‘r n) 其中(a‘r1, a‘r2,…, a‘r n)是矩阵B-1A的第r行 变化后的检验数为： σ’j =cj — CBB-1Pj —Δcra‘rj =σj —Δcra‘rj （j=1，2，…，n）。 若要最优解不变，则必须满足，即 σ’j =σj —Δcra‘rj ≤0 （ j = 1，2，…，n）。 由此导出 当a‘rj<0时，有Δcr≤σj / a‘rj； 当a‘rj>0时，有Δcr≥σj / a‘rj；null当a‘rj<0时，有Δcr≤σj / a‘rj； 当a‘rj>0时，有Δcr≥σj / a‘rj； 因此，Δc允许变化范围是 σj σj max ︱a‘rj >0 ≤ Δcr ≤ min ︱ a‘rj<0 . j a‘rj j a‘rj null 尽管我们可以推导确定cj可变范围上下限的一些，但不需要去记忆此类公式。 例1 　　　null求其中目标函数系数C2的可变范围。 解：原问题加入松弛变量X3 ， X4 ， X5 ，化为型后，可将该问题的初始单纯形表列出如表示。null经过求解的最后单纯形表如下。null在最优单纯形表中，x2的目标函数系数c2的当前值为120。现把这个系数的值用符号c2代替。此时，相应的单纯形表如表所示。null 为使问题的最优解不变，即c2要满足不等式组： 　　　 -28+0.12c2≤0 　　　 14-0.16c2≤0 由此可得到c2的可变范围： 87.5≤c2≤233.33 或 87.5≤120＋Δc2≤233.33 原c2＝120 即 87.5－120≤Δc2≤233.33－120 -32.5≤Δc2≤113.33 nullMax{-5.2/0.16}≤ Δc2≤ min{-13.6/(-0.12)}即： -32.5≤Δc2≤113.33Max{-32.5}≤ Δc2≤ min{113.33}或利用公式求解null 其他目标函数系数的可变范围都可依此法求出。 若c2的值超出可变范围，则最优性条件遭到破坏，这时，需利用单纯形表求出新的最优解 null例2 maxZ = x1 + 5x2 + 3x3 +4 x4 ; 2x1 + 3x2 + x3 +2 x4 ≤800; s.t. 5x1 + 4x2 + 3x3 +4 x4 ≤1200; 3x1 + 4x2 + 5x3 +3 x4 ≤1000; xj≥0 (j=1.2.3.4) 最优单纯形表如表所示。（1）为保持现有最优解不变，求非基变量x1 的系数c1 的变化范围。 （2）当c1变为5时，求新的最优解。null Δc1≤13/4 即当 c‘1 = c1+Δc1≤ 1+ 1 3 / 4 = 17/ 4 原最优解不变。null(2)当c‘1 =5>17/4 已经超出了c1的变化范围，最优解要变。 新的最优解可用下面的求得。首先求出新的检验数 1/4 σ’1 = c1— CBB-1P1 = 5 — （0，4，5，） 2 =3/4 >0 故x1应进基。 -3/4 用新的检验数 σ’1 = 3/4代替原来的检验数σ1 = — 1 3/ 4， 其余数据不变，得新的单纯形表Ⅰ,并继续迭代得表Ⅱ。求得新的最优解 X*=(100, 175, 0, 0, 75)T 及新的目标函数最优值Z*=1375.nullnull 例 巳知线性规划问题 用单纯形法求解得最终单纯形表如表所示maxZ =2x1+ x2 5x2≤15; 6x1+ 2x2≤24; s.t. x1+ x2≤5; x1, x2, ≥ 0. null试确定： (1)当目标函数变为Max z＝5x1＋1.5x2时．最优解会出现什么变化； (2)目标函数变为maxz＝(2＋λ1) x1＋x2时， λ1在什么范围内变化，最优解不变。 原最优解解 (1)将目标函数系数的变化直接反映到最终单纯形表中 null即新的解为 xl＝4， x2＝0 表中变量x5的检验数为正，继续迭代计算得下表(1)当目标函数变为Max z＝5x1＋1.5x2时． 替换原表数据得null(2)目标函数变为maxz＝(2＋λ1) x1＋x2时 原最优解原表目标函数变为 maxz＝(2＋λ1) x1＋x2时 将目标函数系数的变化直接反映到最终单纯形表中， 见下表所示。 null即有为使表中解为最优．应有替换原表数据得null二、约束方程右端常数灵敏度分析 由于XB = B-1b，Z= CBB-1b 右端常数b的变化, 会影响到原最优解的可行性与目标函数值。XB =B-1b ≥0 （1） σN = CN — CBB-1N≤0 （2） null 设某一个右端常数变为br＝br十Δbr，并假设原问题中的其它系数不变，则使最终表中原问题的解相应地变为 0 . X’B = B-1(b+Δb)= B-1b +B-1Δb = B-1b + B-1 Δbr .. 0 b’1 a’1rΔbr b’1+ a’1rΔbr . . . . = b’i + a’irΔbr = b’i+ a’irΔbr . . . b’m amrΔbr b’m+ a’mrΔbr XB =B-1b ≥0 nullnull b’1 a’1rΔbr b’1+ a’1rΔbr . . . . X’B = b’i + a’irΔbr = b’i+ a’irΔbr . . . b’m amrΔbr b’m+ a’mrΔbr 其中（ a’1r，a’2r，…，a’mr）T为逆矩阵B-1中的第r列。若要求最优基B不变，则必须X’B≥0, 即 b’i+ a’irΔbr ≥ 0 ( i =1,2,…,m). 由此可以导出 当a’ir >0时, 有Δbr ≥- b’i/ a’ir ; 当a’ir <0时, 有Δbr ≤ - b’i/ a’ir ;null因此，Δbr 的允许变化范围是 b’i b’i max -－ a’ir >0 ≤Δbr ≤ min - － a’ir < 0 . a’ir a”ir 当b’改变为b+Δb以后，若最优基不变，则目标函数变为 Z’= CBB-1(b+Δb)= Z *+ CBB-1Δb null【例】求例中线性规划问题右端项常数b3的可变范围。 解：此题的最终单纯形表如表所示：nullb发生变化，表中除b列发生变化，其他数据不变由此可得到不等式组 1×360+（－3.12）×200+1.16b3≥0 0×360+0.4×200+（-0.2）b3≥0 0×360+（-0.12）×200+0.16b3≥0 由 360 84 b ＝B－1 200 ＝ 20 300 24 360 b’ ＝B－1 200 b3 360 b’ ＝B－1 200 b3 得 227.586≤b3≤400null最后解得： 227.586≤b3≤400。这就是最优基变量保持不变的范围，也就是说b3在这个范围内变化其对偶价格不变。 例 已知线性规划问题 maxZ = x1 + 5x2 + 3x3 +4 x4 ; 2x1 + 3x2 + x3 －2 x4 ≤800; 5x1 + 4x2 + 3x3 +4 x4 ≤1200; 3x1 + 4x2 + 5x3 +3 x4 ≤1000; xj ≥0 (j=1.2.3.4)最优解如表 1 1/4 －1 = 0 1/4 －1 0 -3/4 1 B-1null（1）求b3的变化范围 1 1/4 －1 B-1 = 0 1/4 －1 0 -3/4 1 X‘B＝B-1（b+Δb）＝ 1 1/4 －1 800 0 1/4 －1 1200 0 -3/4 1 1000＋Δb3maxZ = x1 + 5x2 + 3x3 +4 x4 ; 2x1 + 3x2 + x3 －2 x4 ≤800; 5x1 + 4x2 + 3x3 +4 x4 ≤1200; 3x1 + 4x2 + 5x3 +3 x4 ≤1000解得 －100≤△b3 ≤100nullMax｛-100/1｝≤△b3 ≤min｛-100/(-1), -200/(-1)｝ b’i b’i max- － a’ir >0 ≤Δbr ≤min -－ a’ir < 0 . a’ir a”ir 解得 －100≤△b3 ≤100或利用公式求解 1 1/4 －1 B-1 = 0 1/4 －1 0 -3/4 1 null(2)当△b3 =-150时，已经超出△b3 的变化范围（-100，100），因而原最优基不可行。又 x5 1 1/4 -1 800 X’B= x4 = B-1(b+ △b) = 0 1 1 1200 x2 0 -3/4 1 1000－150 250 = 350 -50用这些数据去替换前表中的相应数据，其余数据不变，再用对偶单纯形法进行迭代maxZ = x1 + 5x2 + 3x3 +4 x4 ; 2x1 + 3x2 + x3 －2 x4 ≤800; 5x1 + 4x2 + 3x3 +4 x4 ≤1200; 3x1 + 4x2 + 5x3 +3 x4 ≤1000null原最优解替换原表数据得用对偶单纯形法求解nullX’*= ( 0, 0, 0, 850/3, 700/3, 200/3, 0)T 基目标函数最优值 Z’*=3400/3null [例] 在前例中 (1)若第2个约束条件的右端项增大到32，分析最优解的变化； (2)若第2个约束条件变为6x1＋2x2≤24＋λ 2，分析λ 2在什么范围内变化，表中基为最优基。因由公式，有maxZ = 2x1+ x2 5x2≤15; 6x1+ 2x2≤24; s.t. x1+ x2≤5; x1, x2, ≥ 0. 0 0 △b = 32 – 24 = 8 0 0 1 5/4 -15/2 0 △b* = 0 1/4 -1/2 8 ＝ 0 -1/4 3/2 0 原最优解10 2 -2 解 (1)因null将其加到原最终单纯形表的基变量b这一列数字上得因表中原问题为非可行解，故用对偶单纯形法继续计算得下表 10 △b* = 2 -2 原最优解原表新表null即新的最优解为，xl＝5，z＝2 × 5＝10。最优表null将其加到表基变量b这一列数字上得表 1 5/4 -15/2 0 5/4 λ2 △b* = 0 1/4 -1/2 λ2 = 1/4 λ2 0 -1/4 3/2 0 -1/4 λ2 (2)若第2个约束条件变为6x1＋2x2≤24＋λ 2，分析λ 2在什么范围内变化，表中基为最优基。 0 △b = λ2 0 由公式有原最优解null表中基为最优基的条件为： 即应有5/2+5/4λ2≥0→λ2 ≥－6 7/2+1/4λ2 ≥0→λ2 ≥－14 3/2-1/4λ2 ≥0 →λ2 ≤6－6 ≤ λ2 ≤6null 三、技术系数的灵敏度分析 实际问题会产生诸如增加新变量、增加新约束条件等灵敏度分析。其处理方法是从原问题的最优单纯形表出发，适当修改后继续进行迭代以获得变化后的问题的最优解。 1. 增加新变量的灵敏度分析 增加一个变量在实际问题中反映为增加一种新的产品。 如果增加一个新的变量xn+1，它对应的价值系数为cn+1 ， 系数列向量为P n+1 ＝(a1 n+1 a2 n+1 …… am n+1 )T． 则把xn+1看成非基变量 计算 σn+1 = c n+1 - CBB-1P n+1 若σn+1 ≤0，则原问题最优解不变； 若σn+1 ＞0，计算P’ n+1 ＝B－1 P n+1 在原来的最优单纯形表中增加一列P’ n+1 得到新问题的单纯形表．继续用单纯形法迭代求解 null【例】原例所示的线性规划模型中，假定原目标函数系数不变，而是企业除了生产产品A、B外，还设计了一种新产品C。已知产品C的单位利润为110元；生产一单位产品C需使用劳动力6工时，设备5小时，消耗7公斤原材料。问该企业是否应生产产品C和生产多少？null解：令x6表示产品C的产量。根据题意，在原来的最优单纯形表中增加变量x6（新增加一列）， x6的目标函数系数为110， x6对应的列为null下表null最优目标函数值 z=4466.667 即新的最优生产为： 生产产品B 6.667单位 产品C 33.333单位 不生产产品A 总利润为4466.67元 比原计划增加了（4466.67-4280）=186.67元。 如果决策者只想知道新产品C是否应该投产 则从检验数σ6>0即可得出投产有利的结论nullnull 前例中，若增加一个变量x6，有c6＝3， P6＝(3，4，2)T，试 分析最优解的变化。 解： 原最优解例原表null 将其反映到最终单纯形表中，得σ6 = c6－YP6 3 = 3-（0，1/4，1/2） 4 2 1 5/4 -15/2 3 －7 P’6 = B-1P6= 0 1/4 -1/2 4 = 0 0 -1/4 3/2 2 2=1 ＞0原最优解null因σ6＝2＞0，故用单纯形法继续计算得表由此新的解为即X1=7/2，X6=3/4， Z＊=2×7/2+3×3/4=37/4null 2. 增加新约束条件的灵敏度分析 增加一个约束条件，在实际问题中相当于增添一道工序。分析的方法是先将原来问题的最优解变量取值代入这个新增的约束条件中，如满足．说明新增约束末起到限制作用，原最优解不变。否则，将新增约束直接反映到最终表中．再进行分析。 若在原线性规划问题中，再增加一个新的约束条件 am+1,1x1+am+1,2x2+…+am+1,nxn≦bm+1 其中am+1,j(j=1,2,…,n)及bm+1均为已知常数，则首先把已求得的原问题的最优解 X＊=(x1＊,x2＊,…,xn＊)T 代入新增加的约束条件，如果满足，则问题的最优解X＊仍为新问题的最优解，计算停止。 如果不满足，则将新的约束条件加入系统，继续求解nullnull 例 设在前例中增添一个约束条件3x1＋2x2≤12，试分析最优解的变化。 解 先将原问题最优解变量值代入，因有 3× 7/2+2×3／2＝27／2＞12 不满足 故将约束条件写成 3x1＋2x2+x6＝12 并取x6为基变量，直接反映到原最终单纯形 表中原最终单纯形表maxZ =2x1+ x2 5x2≤15; 6x1+ 2x2≤24; s.t. x1+ x2≤5; x1, x2, ≥ 0.null原最终单纯形表3x1＋2x2+x6＝12 增加一行一列加入将x1、x2所在列转化为单位向量，即作线性变换null 为使x1、x2列系数变换为单位向量，对表进行变换。新表中① ‘ ② ‘ ③ ‘行同原表数值不变，新表中第④行由以下初等变换得到 ④’＝④—3×②—2×③ 即作线性变换后得用对偶单 纯形法迭 代计算null用对偶单纯形法迭代计算得表由表知新的最优解为x1＝4， x2＝0，z*＝2×4＝8null四、技术系数的灵敏度分析（一）个别技术系数的的变化 根据变动的系数aij处于矩阵A中的哪一列又可分为两种情况来考虑： aij处于非基变量列中； aij处于基变量列中． 1.非基变量aij的系数列向量Pj的变化 若对于最优基而盲，非基变量xj的系数列向量Pj改变为Pj‘ =Pj十ΔPj 则变化后的检验数为 σj’＝cj—CBB-1Pj’= cj —CBB-1(Pj+ Δ Pj )’=σj—YΔPj ，(j＝1，…n） 其中Y ＝ CBB-1为对偶可行解．要使原最优基保待不变， 则必须σj’ ≤0，即 YΔPj≥ σj (j＝1，2， …… ，m)． 特别，当ΔPj ＝(0，…，Δaij…，0)T时，则可得null 2．基变量aij的系数列向量Pj的变化 对于最优基B而言，当基变量xj的系数列向量Pj发生变化时，对基及其逆矩阵B-1都有影响，即不仅影响现行最优解的可行性，也影响到它的最优性．这种情况建议按具体的最优化表格进行分析． 0 . (y1…… yi …… ym ) Δaij ＝ yi Δaij ≥σj 0 由此可以导出 当yi >0时, 有Δaij≥ σj / yi ; 当yi < 0时, 有Δaij ≤σj / yi ; 当给定aij的变换值，则也可看做是增加一新产品null例1 在前例中(1)为保持现有最优解不变，分别求非基变量x1、x3的系数的变化范围； 1 1 (2)若非基变量x3 的系数由 3 变为 4 ，考察原最优解是否仍 5 1 然保持最优？若不是，该怎么办？原最优解 maxZ = x1 + 5x2 + 3x3 +4 x4 ; 2x1 + 3x2 + x3 －2 x4 ≤800; 5x1 + 4x2 + 3x3 +4 x4 ≤1200; 3x1 + 4x2 + 5x3 +3 x4 ≤1000; xj ≥0 (j=1.2.3.4) null解： （1）由最优表可以查得 y1 =0, y2=1/4, y3 =1, 且 y2>0, y3>0.故 Δa21≥σ1 / y2 = (-13/4)/（1/4）= -13, Δa31≥σ1 / y3= (-13/4)/1 = -13/4; Δa23≥σ3 / y2 = (-11/4)/（1/4）= -11; Δa33≥σ3 / y3 = (-11/4)/1 = -11/4. 1 1 (2)当x3的系数由P3 = 3 变为 4 时 5 1原最优解maxZ = x1 + 5x2 + 3x3 +4 x4 ; 2x1 + 3x2 + x3 －2 x4 ≤800; 5x1 + 4x2 + 3x3 +4 x4 ≤1200; 3x1 + 4x2 + 5x3 +3 x4 ≤1000; xj ≥0 (j=1.2.3.4)nullnull 或 Y=（0，1/4，1） 检验数 1 σ’3 = c3 - CBB-1P3’ = 3 - （0，-1/ 4，-1） 4 = 1>0。 -1 故取x3为进基变量．再计算 1 1/4 -1 1 1 P3’= B－1P3 = 0 1 -1 4 = 3 0 -3/4 1 1 -2null 1 P3’= 3 -2 用P3’去替换前最优表中的第3列 继续迭代得最优 解及最优值 Z*＝4100／3得表原最优表新表null继续迭代。求得最优解 X* = （ 0， 700/3， 200/3， 0， 100/3， 0， 0）T 及最优值Z* = 4100/3 null 在例1中，若基变量x2的技术系数列向量由P2 = （3，4，4）T变为P’2 = （4，5，6）T，而它的目标函数中的系数由c2 =5变为c‘2 =6。试求变化后的最优解。 解 为便于利用最优表进行分析，首先要计算在最优表中对应于x2的列向量 1 1/4 -1 4 -3/4 B-1P’2.= 0 1 -1 5 = -1 0 -3/4 1 6 9/4 同时计算出x2的检验数 -3/4 σ’2 = c‘2 - CBB-1P’2= 6 - （0，4，6） -1 = -7/2 9/4 注意，由于数据发生变化，在最终表上，原基变量x2的系数列向量不再是单位列向量，检验数σ’2 也不再为0。但如果我们仍然想保持原最优基不变，即还把 x2作为基变量看待，则须将以上计算结果填入最终表x2的列向量位置，得表null 这 并不是一个正规的单纯形表，因为没有单位矩阵I。为了得到一个单位短阵，注意到x 2仍为第3个基变量，故必须将x 2所在列变成单位列向量，同时将σ’2＝一7／2变为0，即以a’32＝ 9／4为主元进行矩阵的初等变换(这种变换没有换基， x 2仍为基变量)，得表原最优解将 -3/4 B-1P’2.= -1 9/4 σ’2 = -7/2 代入null得新的最优解 X*B =（0，400/9，0，2200/9，400/3，0，0）T 目标函数最优值 Z*=11200/9 例如：－11/2－（11/9）×（7/2）＝－11/9null解*假如xij在最终表中为基变量，则aij的变化将使最终表中的B－1变 化，因此有可能出现原问题与对偶问题均为非可行解的情况。 若基变量系数的变化导致原始可行性条件和对偶可行性条件均被破坏，即产生了对原问题和对偶问题均为非可行性解时，这就需要引入人工变量重新求解。 [例] 若在前例中c2＝3，x2的系数向量变为P2＝(8，4，1）T，试分析最优解的变化。先将其作为一个新的变量x’2列入最终单纯形表中，见表 8 σ2 = 3－（0，1/4，1/2） 4 =3/2 1 1 5/4 -15/2 8 11/2 P’2= 0 1/4 -1/2 4 = 1/2 0 -1/4 3/2 1 1/2maxZ =2x1+ x2 5x2≤15; 6x1+ 2x2≤24; s.t. x1+ x2 ≤5; x1, x2, ≥ 0.null原最优解替换后null 因表中原问题与其对偶问题均为非可行解，由前表知，通过引进入工变量原问题转化为可行解，再用单纯形法继续计算。 上表的第一行可写成 X3十4X4—24x5＝一9 因右端项为负值，故先将等式两端乘“—1”，再加上人工变量x6得 一X3—4x4十24x5十x6＝9 将上式替换上表的第一行，得表null用单纯形法迭代计算得表由表知，新的最优解为 X1 = 11/4，X’2 = 15/8，Z＊ = 2×11/4+3×15/8 = 89/8nullnull 已知线性规划问题 的最优单纯形表 试分别就下列情况进行灵敏度分析，并求新的最优解： （1） b2＝95 例maxZ =－5 x1 + 5x2 +1 3x3 －x1 + x2 + 3x3 ≤20; 12 x1 +4x2 + 10x3 ≤90; xj ≥0 (j=1.2.3)null (2)第1个约束条件的右端常数变为61；45 (3)目标函数中岛的系数变为Q；8； (4＞目标函数中均的系数变为‘2＝63 (5)变量cI的系数(包括目标函数)变为 卜1 卜g＝ 卜j (6)变量c，的系数(包括目标函数)变为 (7)增加一个新变量x‘，其系数为 (8)tB加一个新约束条件2A十3A代A＜50l (9)策2个约束条件变为10A十422十12‘，考I oo． 4。s 51，2l，5J null （1） b2＝95 解 因为 max( 一10/1)≤Δb2 ＜min(20/0) 即 一10≤Δb2 ＜∞ 现Δb2＝95—90＝5未超出上述范围，故最优基及不变，新的最优解为 b’i b’i max- － a’ir >0 ≤Δbr ≤min -－ a’ir < 0 . a’ir a”ir 1 0 20 20 = = - 4 1 95 15 即X*=(0,20,0,0,15)T,新的最优值 20 Z*= CBXB* =( 5,0 ) = 100. 15 X2* XB*= X5* . null因为 max[一20/1]≤Δb1 ＜min[-10/(-4)] 即 一20≤Δb1 ＜ 5/2， 故Δb2 =45 – 20 =25已超出上述范围，故最优基要变。 这时的基本解为 X2* 1 0 45 45 XB= = B-1b= = X5* -4 1 90 -90 b’i b’i max- － a’ir >0 ≤Δbr ≤min-－ a’ir < 0 . a’ir a”ir 即X＝(0，45，0，0，一90)T，它不是可行解，继续用对偶单纯形法迭代求解(见表1).null 表1由表4．11(Ⅲ )可知新的最优解为 X*＝(0，0，9，18，0)T． 新的最优值Z*=117．null(3)因为Δc3 ≤一(一2)＝2．现Δc3 ＝8一13＝一5，未超出变化范围，故现最优解不变。 (4)因为 max { -2/3, -5/1 } ≤ Δc2 ≤min{0/( - 1)}即 -2/3 ≤ Δc2≤0。 现Δc2=6-5=1，已经超出变化范围，故最优解要变，新的最优解可通过下表（表2）迭代求得maxZ =－5 x1 + 5x2 +1 3x3 －x1 + x2 + 3x3 ≤20; 12 x1 +4x2 + 10x3 ≤90; xj ≥0 (j=1.2.3)null由表2（ Ⅱ）可知新的最优解为 X*= ( 5/8, 165/8, 0, 0, 0 )T 及最优值Z* = 965/8.表2null（5）非基变量的系数变化仅影响最优性．故应重新计算x1的检验数 σ1= c1— CBB-1P1 1 0 0 = — 2 —(5,0) = —2 < 0, - 4 1 5 所以原最忧解X*＝(0，20，0，0，10)T不变． null(6)基变量的系数变化既影响解的可行性，又影响解的最优性. 为了便于利用最优表进行分析，首先要计算在最终表中对应于x2的列向量 1 0 2 2 B-1P’2 = = -4 1 5 -3 及相应的检验数 2 σ’2= c‘1— CBB-1P’2 = 6 — ( 6, 0 ） = — 6。 -3 将上述数据替换原表的第2列，得表3(I).null 表4.13(Ⅰ)由于表3(Ⅰ )没有单位矩阵,故应将x2所在的列向量变为 1 单位列向量 0 ，得表3（II）。 0null表3（Ⅱ）由表3（Ⅱ）再迭代一次，得表3（ Ⅲ），则已求得最优解 X* =(0, 0, 20/3,0,70/3)T 及最优值Z* =260/3. null (7)增加一个新变量x6以后，应首先求 1 0 3 σ6＝c6 — CBB-1P6＝10一(5,0) ＝一5＜0，