教案五 线性规划的对偶问题.docx

《教案五 线性规划的对偶问题.docx》由会员分享，可在线阅读，更多相关《教案五 线性规划的对偶问题.docx（45页珍藏版）》请在三一办公上搜索。

1、教案五 线性规划的对偶问题教案五 线性规划的对偶问题 教学内容 第四节 线性规划的对偶问题 1线性规划的对偶问题 2对偶单纯形法 3线性规划的灵敏度分析 4线性规划在卫生管理中的应用 教学学时 7学时 教学目标 1理解对偶问题的基本概念 2掌握对偶单纯形法 3掌握线性规划的灵敏度分析 4掌握线性规划在卫生管理中的应用 重点难点 重点是对偶问题的基本概念、对偶单纯形法线、灵敏度分析、线性规划在卫生管理中的应用。难点是对偶问题的基本概念和线性规划的灵敏度分析 教学手段 教师与学生互动 使用多媒体课件 教学过程 一、复习巩固 1单纯形法的基本原理 2单纯形解法 3大M法 二、讲授新课 1线性规划的对

2、偶问题 对偶问题的基本概念 对偶现象 每一个线性规划都伴随着另一个线性规划，两者有密切关系，互为对偶其中一个问题称为原问题，另一个问题称为其对偶问题两者间只要得到其中一个问题的解，那么也就得到了另一个问题的解 下面通过一个实例来解释对偶线性规划的概念 例2-12 以例2-1为例，我们讨论了一个制药厂的生产计划的数学模型及其解法 现在假定该制药厂决定在计划期内不生产药品、，而将生产设备的有效台时全部租给某公司，那么该公司应对设备A、B、C、D每小时付多少租金，才能使成本最小，而又能为制药厂所接受？ 从租用设备的公司的角度考虑，一是所付的租金越低越好；二是所付的租金总额能使制药厂接受，即租金应不低

3、于制药厂自己生产该两种药品所得利润，否则，制药厂宁可自己生产，而不租给公司 设公司租用该制药厂A、B、C、D四种设备的租金分别为y1、y2、y3和y4在考虑租用设备的定价时，能使该制药厂接受的条件是： 公司租用该制药厂用以生产每千克药品所需A、B、C、D四种设备的台时的租金不应少于200元，即 2y1+y2+4y3+0y4200 同样，公司租用该制药厂用以生产每千克药品所需A、B、C、D四种设备的台时的租金不应少于300元，即 2y1+2y2+0y3+4y4300 公司在考虑自身利益时，其目标是使付出的租金总额为最小，即 Min W=12y1+8y2+16y3+12y4 于是，上面的问题可以用

4、下列线性规划的数学模型表示： Min W=12y1+8y2+16y3+12y4 2y1+ y2+4y3+0y4200 s.t. 2y1+2y2+0y3+4y4300 y1,y2,y3,y40 若把制药厂利润最大的线性规划问题称为原问题，则想租用A、B、C、D四种设备的公司的租金最小的线性规划问题称为原问题的对偶问题；反之，若把租用A、B、C、D四种设备的公司的租金最小的线性规划问题称为原问题，则制药厂利润最大的线性规划问题称为原问题的对偶问题 影子价格 一般地，我们称对偶问题的最优解为原问题约束条件的影子价格，即对偶问题的解yi称为第i种资源的影子价格它并不是某种资源在市场上的价格，而是代表单

5、位资源在最优利用的条件下所产生的经济效果为了和市场价格相区别，我们才称它为影子价格它在经济上是一个很有意义的数据，通过它我们可以知道，当增加某种资源时，可以使利润增长的大小另外，影子价格还给出了是否应当购进某种资源以增加生产量，而获得更多利润的价格标准 对称的对偶线性规划 如果一个线性规划具备下面两个条件，则称它具有对称形式：所有的变量都是非负的；所有的约束条件都是不等式，而且在目标函数是求极大值的情况，不等式具有小于和等于的符号，在目标函数是求极小值的情况，不等式具有大于和等于的符号 对称形式的原问题和对偶问题叫做对称的对偶线性规划 原问题和对偶问题在形式上的对比 如果我们把线性规划 Max

6、 Z=c1x1+c2x2+L+cnxn a11x1+a12x2+L+a1nxnb1 a21x1+a22x2+L+a2nxnb2 s.t. am1x1+am2x2+L+amnxnbm x1,x2,L,xn0 称为原问题，则必同时存在另一线性规划问题，我们称为对偶问题： Min W=b1y1+b2y2+L+bmym a11y1+a21y2+L+am1ymc1 a12y1+a22y2+L+am2ymc2 s.t. a1ny1+a2ny2+L+amnymcn y1,y2,L,ym0 而且 Min W=Max Z 用简缩形式表示： 原问题为 Max Z=cjxj j=1n aijxjbi i=1,2,L

7、,m s.t. j=1n xj0 j=1,2,L,n 对偶问题为 Min W=biyi i=1m aijyicj j=1,2,L,n s.t. i=1m yi0 i=1,2,L,m 矩阵形式表示： 原问题为 Max Z=CX AXb s.t. X0 对偶问题为 Min WYb YAC s.t. Y0 s.t.其中， C=(c1,c2,L,cn) a11aA= 21Lam1a12a22Lam2La1nLa2n LLLamnx1b1x2b2X= b= LLxbnm Y=(y1,y2,L,ym) 原问题与对偶问题之间的关系 1）原问题是求目标函数的最大值，对偶问题是求目标函数的最小值 2）原问题约束

8、条件的右端项变成对偶问题目标函数的系数原问题目标函数中的系数变成对偶问题约束条件的右端项 3）原问题约束条件是“”，对偶问题的约束条件则是“” 4）原问题约束条件的每一行正好对应于对偶问题的每一列，所以原问题中约束条件的数目等于对偶问题中变量的数目 5）原问题中约束条件的每一列正好对应于对偶问题的每一行，所以原问题中变量的数目正好等于对偶问题中的约束条件的数目 6）对偶问题的对偶规划正是原问题 例2-13 设原问题为： MiWn= 2x1+5x2 x1 4 s.t. x23 x1+2x28 x1,x20 试写出它的对偶问题 解 Max Z=4y1+3y2+8y3 y1 + y32 s.t. y

9、2+2y3 5 y1,y2,y30 非对称的对偶线性规划 对于我们经常遇到的非对称形式的线性规划，我们可首先将其化为等价的对称形式的线性规划问题，然后再按对称的对偶线性规划原问题与对偶问题之间的对应关系，将其化为对偶问题实际上，我们在考虑对称的对偶线性规划或非对称的对偶线性规划时，也可以按表2-13原问题与对偶问题之间的对应关系，直接进行变换，得到原问题或对偶问题 表2-13 原问题与对偶问题间的转换 原问题 目标函数对偶问题 目标函数 Min W 对偶变量数：m个 对偶变量yi0 MaxZ 约束条件数：m个 第i个约束条件为“” 第i个约束条件为“” 第i个约束条件为“=” 变量xj的数目：

10、n个 变量xj0 变量xj0 变量xj无非负条件 限定向量b 成本或利润向量C 系数矩阵A 对偶变量yi0 对偶变量yi无非负条件 约束条件数：n个 第j个约束条件为“” 第j个约束条件为“” 第j个约束条件为“” 成本或利润向量C 限定向量b 系数矩阵A T例2-14 原问题为： MaZx= 4x1+5x2 3x1+2x220 4x1-3x210 s.t. x1+ x2=5 x10，x2符号不限 可按表2-13的原则，将原问题直接转化成对偶问题： Min W=20y1+10y2+5y3 3y1+4y2+y34 s.t. 2y1-3y2+y3=5 y10，y20，y3符号不限 对偶问题的基本性

11、质 1）对偶问题的对偶是原问题 2）若X和Y分别是原问题和对偶问题的可行解，则CXYb 3）设X和Y分别是原问题和对偶问题的可行解，当两者目标函数值相等，即CXYb时，X，Y分别是原问题和对偶问题的最优解 4）若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等 5）若X和Y分别是原问题和对偶问题的可行解，则X和Y为原问题及对偶问题最优解的充分条件为： vX0和Yu0 其中，u(u1,u2,L,um)T, u1,u2,L,um是原问题的松弛变量，v, v1,v2,L,vn是对偶问题的剩余变量 此性质在线性规划中有广泛应用如从已知的原问题最优解求取对偶问题最优解；验证原问题的可行解是否最优

12、解等等 6）原问题的检验数对应于对偶问题的一个基本解 由对偶性质可知，在求解原问题的过程中，利用单纯形表每一次迭代所得的检验数与对偶问题的基本解仅仅相差一个符号，于是原问题获得最优解时对应的单纯形表中检验数的相反数，即为对偶问题的最优解 例2-15 设原问题为： Max Z=x1+2x2+3x3+4x4 x1+2x2+2x3+3x420 s.t. 2 x1+ x2+3x3+2x420 x1,x2,x3,x40 已知其对偶问题的最优解为y1*1.2，y2*0.2，相应的目标函数最小值W28，试利用对偶性质求该问题的最优解 解 原问题的对偶问题为： Min W=20y1+20y2 * y1+2y2

13、1 2y1+ y22 s.t. 2y1+3y23 3y1+2y24 y1,y20 由松弛互补性质可知，在最优条件下，vX0和Yu0，即 *u1y10，u2y20，v1x10，v2x20，v3x30，v4x40；这里ui*，vj*分别为原问题的松弛变量及对偶问题的剩余变量 由y1* 1.20，可以推出u1* =0；由y2* 0.20，可推出u2* =0 由对偶约束y1*+2y2* =1.61，知v1* 0,于是x1* =0；同理，由2y1*+y2* =2.62，知v20,于是x2=0 根据上述结果，原约束可以转化成二元一次线性方程组： 2x3* +3x4* =20 3x3* +2x4* =20

14、解方程得x3* =x4* =4 综上所得，原问题的最优解为X* =(0044)，相应的目标函数最优值T* * 为Z=28 由对偶性质还可以推论： 1）若原问题可行，但有无界解，则对偶问题不可行；若对偶问题可行，但有无界解，则原问题不可行； 2）若原问题可行，而对偶问题不可行，则原问题有无界解；若对偶问题可行，而原问题不可行，则对偶问题有无界解 2对偶单纯形法 前面已叙述原问题与对偶问题的解之间的对应关系在用单纯形法进行迭代时，在b列中得到的是原问题的基本可行解，而在检验数行得到的是对偶问题基本解的相反数通过逐步迭代，当在检验数行得到的对偶问题的解也是可行解时，原问题和对偶问题都达到了最优解所以

15、，单纯形法的特点是保持原问题解的可行性，通过逐步迭代，使对偶问题的解由基本解变成基本可行解，这时原问题和对偶问题都达到了最优解 * 那么根据对偶问题的对称性，我们也可以这样来处理：保持对偶问题的解是可行解，而原问题则从非可行解开始，通过迭代，逐步达到基本可行解这样，也使原问题和对偶问题都达到了最优解 事实上，对偶单纯形法并不是解对偶问题的单纯形法，而是应用对偶原理来求解原问题的最优解的一种方法 对偶单纯形法的要点 例2-16 用对偶单纯形法求解下列线性规划问题 Min W=1600x1+2500x2+400x3 2x1+ 5x2+x34 3 s.t. 2x1+2.5x2 x1,x2,x30 解

16、 此问题可用大M法去解，但用大M法求解很麻烦，现在用对偶单纯形法求解先将原问题化为标准形式，为此引入剩余变量x4，x5，令Z=-W，得 Max Z=-1600x1-2500x2-400x3 2x1+ 5x2+ x3 -x4 =4 s.t. 2x1+2.5x2 -x5=3 x1,x2,x3,x4,x50 然后将约束条件等式的两边都乘以，得到 Max Z=-1600x1-2500x2-400x3 -2x1- 5x2- x3+x4 =-4 +x5=-3 s.t. -2x1-2.5x2 x1,x2,x3,x4,x50 建立这个问题的初始单纯形表，见表2-14： 表2-14 对偶单纯形法求解例2-16

17、cj xj -1600 -2500 -400 0 0 b CB x1 XB 0 -2 x2 -5 x3 x4 1 x5 x4 -1 0 -4 0 x5 Cj -2 -1600 -5 20 -400 0 0 1 0 -3 -2500 Z=0 在这个初始单纯形表中，x4、x5是基本变量，初始单纯形表所对应的基本解为X(000-4-3)，它是一个不可行解而全部检验数Cj-Zj0，T即所对应的对偶问题的一个基本解也是一个可行解, yi0，i=1,2,L,5下面的迭代是在保持检验数小于等于零的条件下，逐步使xj0，j=1,2,L,5为了满足上面要求，迭代的要点是： 1）首先确定换出变量：选择具有负数的基

18、本变量中绝对值最大的基本变量为换出变量 2）确定换入变量：用换出变量那一行具有负值的系数分别去除同列的检验数，取最小商数所对应的变量为换入变量；如果换出变量那一行无负值的系数，则原问题无可行解 3）把换出变量的那一行除以枢元位置的系数，使枢元位置变为1 4）进行行变换，使除枢元外的其他枢列位置变为0 5）进行最优解检查如果所得的基本解都是非负的，则此解即为最优解如果基本解中还有负的数值，则重复第1步继续迭代，直到所有基本变量为非负的数值为止 表解形式的对偶单纯形法 按上述迭代的要点，对表2-14继续运算，见表2-15 表2-15 对偶单纯形法求解例2-16 cj xj -1600 -2500

19、-400 0 0 CB b x1 XB 0 -2 x2 -5 x3 x4 1 x5 x4 -1 0 -4 0 x5 Cj -2 -1600 800 -5 20 -400 400 1 0 0 1 0 0 -1 20 0 -1 0 -400 -1 0 -400 400 12-1 0 0 1 0 2 -2 5-3 -2500 500 5 5 -2Z=0 4 -3 q -400 0 x3 x5 2 -2 -800 400 Cj -500 200 0 1 0 0 1 0 Z=-1600 -2 65q -400 -2500 x3 x2 -2 45Cj -400 200 -200 -1 25Z=-2200

20、1 25q -1600 -2500 x1 1 0 0 x2 252 5Cj -200 -200 -600 Z=-2600 表2-15中b列数字全为非负，检验数全为非正，故问题的最优解为 X* =(10.4000)T，最优值W* 2600 若对应两个约束条件的对偶变量分别为y1和y2，则对偶问题的最优解为 Y* =(20060000200)，最优值2600 对偶单纯形法的优点及用途 1）初始解可以是非可行解，当检验数都是小于等于零时，就可以进行基变换，这样就避免了增加人工变量，使运算简化 2）对变量较少，而约束条件很多的线性规划问题，可先将其变为对偶问题，再用对偶单纯形法求解，简化计算 3）用于

21、灵敏度分析 3线性规划的灵敏度分析 在上述讨论线性规划问题时，假定aij，bi，cj都是精确的数据，然而在大多数实际问题中，这些系数往往是估计值和预测值，而且它们也随着某些条件的变化而变化因此很自然会想到，当这些系数中的一个或几个发生变化时，已求得的规划问题的最优解会发生什么变化？如果最优解发生了变化，又怎样用最简单的方法找到新的最优解？这就是线性规划灵敏度分析的任务 单纯形法的矩阵表达式 设有一线性规划问题，用矩阵表示为 Max Z=CX AXb s.t. X0 式中，A为mn矩阵，C为1n行向量，X为n1列向量，b为m1列向量，0为n1列向量 现引入松弛变量 xn+1xTXS=n+2=xn

22、+1,xn+2,L,xn+m)Lxn+m化为标准型 Max Z=CX+0 XS AX+IXS=b s.t. X0，XS0 X其中，I是mm阶单位矩阵，约束条件也可写成(A,I)X=b和 SXX0，0有m+n个元素 S如果我们把系数矩阵A分为两块，A=(B,N)，B也称基矩阵，对应于B的变量xB1,xB2,L,xBm是基本变量，用向量XB=(xB1,xB2,L,xBm)T表示，其他的变量则为非基本变量，于是将X也分为两块： XB XN0 向量C也可分为两块C=(CB,CN)，其中CB是目标函数中基本变量向量XB的系数行向量，CN是目标函数中非基本变量向量XN的系数行向量所以 XBX(C,0)()

23、=C,C,0XN=CBXB+CNXN+0XSBNXSXSXBX(A,I)=(B,N,I)XN=BXB+NXN+IXSXSXS于是线性规划问题可以写成 Max Z=CBXB+CNXN+0 XS s.t. BXB+NXN+IXS=b XB,XN,XS0 在单纯形法的每次迭代中，是用行变换的方法将基矩阵变成单位矩阵用矩阵方法，则将上述约束方程的两边乘以基矩阵B的逆矩阵B-1,于是可得 B-1BXB+B-1NXN+B-1IXS=B-1b 即: IXB+B-1NXN+B-1XS=B-1b 所以 XB=B-1b-B-1NXN-B-1XS 将式代入目标函数可得 Z=CBB-1b-CBB-1NXN-CBB-1

24、XS+CN XN Z=CBB-1b+(CN-CBB-1N)XN-CBB-1XS 或者 Z+(CBB-1N-CN)XN+CBB-1XS=CBB-1b 从式可知，在单纯形表每次迭代后,每个变量的系数列向量是B的逆阵B-1乘以该变量的原始列向量而得到的，右端常数的列向量是B的逆阵B-1乘以右端常数的原始列向量而得到的从式可见，其松弛变量的系数矩阵正好是基矩阵的逆阵B-1更一般地理解，在任一单纯形表中相应于初始基本变量的那些列给出了相应于该表格的基矩阵的逆阵 例如第二章第三节的例2-8中，表2-4、表2-5、表2-6和表2-7给出了单纯形法的计算过程，其中表2-7为最优解单纯形表，其基本变量是x3,x

25、1，x6和x2对应于表2-7的基矩阵 11-1-41004=10-2211-02800 1010B=002140000122-1 B04所以对应于表2-7的x1列向量是 1-10 BP100-10-212-1414121-820011040 1000式中P1为原始单纯形表中对应于x1的列向量. 对应于表2-7的x4列向量是 10B-1P400-10-212-1414121-8-1001000-2 11020式中P4为原始单纯形表中对应于x4的列向量. 对应于表2-7的b列向量是 1-10Bb00-10-212-1414121-81200840164 11220式中b为原始单纯形表中右端列向量.

26、 对应于表2-7的非基本变量的检验数是CN-CBB-1N，松弛变量的检验数是-CBB-1 系数变化的灵敏度分析 系数变化的灵敏度分析是在决策变量和约束条件数目不变时，研究各种系数的变化对最优解的影响它主要考虑两种情况：一是这些系数在什么范围内变化时，已得到的最优解保持不变，或者最优解的基本变量保持不变；二是如果某些系数的变化引起最优解的变化，如何用最简便的方法求出新的最优解 目标函数中cj变化范围的确定 假设其他参数不变，仅目标函数中xj的系数cj变成cjDcj，现求不改变最优解的Dcj的大小这分两种情况： 1）cj是非基本变量xj的成本或利润系数 因为 Cj=cj-Zj =CBPj Zj=c

27、iaiji=1m所以改变非基本变量的成本或利润系数，Zj不变，但Cj=cj-Zj变为新的检验数Cj：Cj=cj+Dcj-Zj=Cj+Dcj 要想保持极大化问题最优解不变，即Cj=Cj+Dcj0，则： Dcj-Cj2）cj是基本变量xj的成本或利润系数 因为 Cj=(cj+Dcj)-Zj=(cj+Dcj)-(ci+Dci)aiji=1m =cj-ciaij+Dcj-Dciaiji=1i=1mm =Cj+Dcj-Dciaij=Cj+Dcj-DCBPji=1m要保持极大化问题最优解不变，则Cj=Cj+Dcj-DCBPj0 对于基本变量检验数总为零，而对于非基本变量xj，因Dcj=0，所以要求检验数小

28、于等于0变为： Cj-DCBPj0 例2-17 以例2-8的最终计算表为例设基本变量x2在目标函数中的系数c2变化了Dc2；这时表2-7的最终计算表便成为表2-16所示 表2-16 基本变量利润系数变化的灵敏度分析 cj xj XB 200 300Dc2 0 0 0 0 CB b x1 0 200 0 300Dc2 0 1 0 0 0 x2 0 0 0 1 0 x3 x4 -1 0 -2 12x5 1 4x6 x3 x1 1 0 0 0 -0 0 1 0 0 0 4 4 2 1412x6 x2 -1 8Cj 0 -150-1Dc 22-251+Dc2 28Z=14002Dc2 这时要保持最优解

29、不变，则必须满足下列不等式： -110-150-(000Dc2)=-150-Dc20 -22121-41251-25-(000Dc2)4=-+Dc20 128221-8-300Dc2100 即c2可在0,400间变动，不影响原来的生产计划安排，但制药厂收益变化了 在约束条件中bi变化范围的确定 初始单纯形表中bi的变化，除了影响最优解的数值之外，不影响最终单纯形表中的其他系数所以只要保证最后的解仍是可行解，那么它仍然是最优解即 b=B-1(b+Db)=B-1b+B-1Db=b+B-1Db0 式中，b为右端常数变化后，最终单纯形表右端常数向量；b为右端常数未变化时，最终单纯形表右端常数向量 例2

30、-18 在例2-8中，如果第三个约束条件b3发生变化，变化量为Db3，为了使最后的解仍为可行解，Db3应满足下列不等式： 101-1-44100b+B-1Db=440-2122012-181-Db30040104Db30 Db4413Db1223010-Db381-Db344+1Db30 414+Db3212-Db38Db30 Db3-16 Db3-8 Db316 -8Db30 所以Db3在8,0之间变动时，原来最优解的基本变量不变，但最优解的值发生变化例如，Db3为2时，则 11-1-041400-1b=b+BDb440-212211-028110-Db30421004+Db37 42Db3

31、1314+Db3209102-Db3487最优解X2*941*003，最优值Z1375，见表2-17 2T表2-17 右端常数变化后的最优解 cj xj XB 200 300 0 0 0 0 CB b q x1 0 200 0 1 x2 0 0 x3 x4 -1 0 x5 1 4x6 1272x3 x1 1 0 -0 0 140 300 x6 x2 Cj 0 0 0 0 1 0 0 0 0 -2 1212- 1 0 0 3 941 825 2-150 -Z=1375 如果Db3的变化超出了8,0的范围，这时最优解的基本变量就发生变化在这种情况下要用对偶单纯形法继续求出新的最优解 例如Db3为2

32、时，则 1040-1b=b+BDb4200-10-212-1414121-81100-Db32404+1Db9032 4Db351104+Db3721402-Db38则最终单纯形表变为表2-18 表2-18 右端常数变化后的对偶单纯形法求解 cj 200 300 0 0 0 0 CB xj XB b x1 x2 0 0 0 1 0 0 x3 x4 -1 0 -2 12x5 1 -41412-x6 1 20 200 0 300 x3 x1 0 1 0 0 0 1 0 0 0 0 -4 0 0 1 0 0 0 -92x6 x2 Cj 5 741 8252-150 150 4 - Z=1425 2

33、q 0 50 1 x5 0 200 0 300 x1 1 0 0 0 0 0 1 0 1 2 -1 2-1 -4 1 -100 0 0 0 0 0 1 0 0 4 4 2 x6 x2 Cj -50 Z=1400 新的最优解X*(420024)，最优值Z*1400 T矩阵A中的系数改变对最优解的影响 当对应于Pj的变量xj为非基本变量的系数时，它的变化不会改变基矩阵B和它的逆阵B-1，所以只需修改单纯形表中所对应xj的列就可以了 Pj=B-1Pj Cj=Cj-CBB-1Pj 若极大化问题Cj0,则得到的还是新问题的最优单纯形表，最优解和最优值不变，否则可用单纯形法求解 当对应于Pj的变量xj为基

34、本变量的系数时，它的变化会改变基矩阵B和它的逆阵B-1，所以会影响到最终单纯形表的右端向量和非基本变量对应的列下面就举例讨论此种基本变量的系数变化情况 例2-19 以例2-1为例，若计划生产的药品的工艺结构有了改进，相应地生产单位药品所需设备A、B、C、D的台时改为，它的利润也提高到每千克400元试分析已求得的最优计划有何变化？ 解 当x1的系数列向量变化后,原最终单纯形表中x1的系数列向量变成: 1101-1-434150002=4 -14 P=BP115110-21222113-00288原最终单纯形表变成表2-19： 表2-19 决策变量系数改变对最优解的影响 cj xj XB 400

35、300 0 0 0 0 b CB x1 -1 4x2 0 0 0 1 x3 1 0 0 0 x4 -1 0 -2 12x5 -1 4x6 0 0 1 0 0 400 0 300 x3 x1 0 4 4 2 54121412x6 x2 Cj 3 8-1 8由x1的系数列向量可知，到此尚未完成行变换，所以需继续使x1的系数列向量变成单位列向量，于是得到表2-20 表2-20 决策变量系数改变对最优解的影响 cj xj XB 400 300 0 0 0 0 CB b x1 0 400 0 1 x2 0 0 x3 x4 -1 0 x5 1 5x6 45x3 x1 1 0 -0 0 1 516 50 3

36、00 x6 x2 Cj 0 0 0 0 1 0 0 0 0 -2 1225- 1 0 0 12 5451 5-150 -20 Z=1520 因为Cj0，所以新的最优解X*=(3.20.80.8002.4)，最优值ZT*1520元. 4线性规划在卫生管理中的应用 放射科的业务安排 A医院放射科可以开展X线平片检查和CT检查业务，现拟购买磁共振仪，以增设磁共振检查业务为此A医院收集了有关信息，以决策是否购买磁共振仪 A医院估计今后放射科如果开展此3项业务，在现有放射科医务人员力量和病人需求的情况下，每月此3项业务的最多提供量为1800人次平均每人次检查时间、每月机器实际可使用时间、平均每人次检查利

37、润如下表2-25 表2-25 放射科3项检查时间与利润及机器可使用时间 项 目 平均每人次检查时间 每月机器实际可使用时间 平均每人次检查利润 设每月X线平片检查、CT检查和磁共振检查的业务量分别为x1,x2和x3人次，则使A医院放射科此3项业务收入最多的线性规划模型如下： 放射科业务 X线平片检查 CT检查 磁共振检查 0.1 300 20 0.25 120 60 0.5 120 10 Max Z=20x1+60x2+10x3 300 0.1x1 0.25x2 120 s.t. 0.5x1 120 x1+ x2+ x31800 x1,x2,x30 利用单纯形法可得最终单纯形表 表2-26 放射科业务安排最终单纯形表 CB cj xj XB 20 60 10 0 0 0 0 b x1 0 60 0 20 x4 x2 x6 x1 Cj