《[企业管理]MBA运筹学2第二五章线性规划.ppt》由会员分享，可在线阅读，更多相关《[企业管理]MBA运筹学2第二五章线性规划.ppt（61页珍藏版）》请在三一办公上搜索。
1、第二三四五章 线性规划,2.1 线性规划问题与标准形式2.2 线性规划问题的几何解释2.3 单纯型法方法,问题的提出（1）,【例】派公司是一个生产高尔夫器材的小型公司，公司决定生产中高价位的高尔夫袋。产品的生产过程有四个程序：切割并印染原材料、缝合、成型、检查和包装，不同价位高尔夫袋生产程序的耗时信息如下表，表中还列出了派公司在本轮生产过程中每个部门的最大生产时间。,问题的提出（2）,会计部门的数据表明，生产一个标准袋的利润是10美元，生产一个高级袋的利润是9美元。如何安排两种产品的生产才能使公司获得最大利润？,问题的提出（3）,设x1、x2分别为两种高尔夫袋的生产量，则该计划问题可用如下数学
2、模型表示为：,2.1 线性规划问题与标准形式 典例1-生产计划问题,例2.某工厂在计划期内要生产产品I和产品II这两种产品，已知生产单位产品所需的设备台时及A、B两种设备计划期的有效台时，如下表：问如何安排生产最有利？,解设产品I和产品II的产量分别为x1和x2件,利润为Z,则:,Z=x1+2 x2,Max,目标函数,2 x1+2 x2 8 0 x1+2 x2 4 x1,x2 0,约束条件S.t.,非负条件,above,典例2-配料问题,Z=3x1+2 x2,Min,目标函数,12 x1+3 x2 4 2 x1+3 x2 2 3 x1+15 x2 5 x1+x2=1 x1,x2 0,约束条件S
3、.t.,典例3-食谱问题,例3,问在满足营养的条件下,如何安排食谱最有利?,解:设每人每周食用大米、白菜、鸡蛋、猪肉的数量分别为x1、x2、x3、x4,Z=C1x1+C2x2+C3x3+C4x4,Min,a11x1+a12x2+a13x3+a14x4 b1,=,a21x1+a22x2+a23x3+a24x4=b2a31x1+a32x2+a33x3+a34x4=b3x1,x2,x3,x4 0,食谱问题的拓展,问在满足营养的条件下,如何安排食谱最有利?,Z=C1x1+C2x2+C3x3+C4x4+.+Cnxn,Min,a11x1+a12x2+a13x3+a14x4+.+a1nxn=b1,a21x1
4、+a22x2+a23x3+a24x4+.+a2nxn=b2a31x1+a32x2+a33x3+a34x4+.+a3nxn=b3am1x1+am2x2+am3x3+am4x4+.+amnxn=bmx1,x2,x3,.xn 0,数学模型,New Bedford Steel炼焦煤供应问题,New Bedford Steel(NBS)是一家小型的炼钢企业。炼焦煤(coking coal)是NBS公司炼钢时所必需的一种原材料，每年的需求量是100至150万吨。现在到了该公司计划明年生产的时候了，他们收到了来自八家供应商的报价。,New Bedford Steel炼焦煤供应问题,根据对未来的形势估计和生产
5、现状的考察，NBS计划明年要定购1,225千吨的炼焦煤。这些炼焦煤的平均可燃率至少要达到19%。为了不影响劳工关系，NBS决定至少50%的炼焦煤要来自于工会煤矿。另外，每年由火车运输的炼焦煤量至多不超过650千吨，而由卡车运输的炼焦煤量至多不超过720千吨。现在要解决以下问题：为了使炼焦煤的成本最小，应该从各个供应商处定购多少吨炼焦煤？NBS的总供应成本是多少？NBS的平均供应成本是多少？,NBS供应问题的数学表达,变量：A=从 Ashley 处定购的炼焦煤量（千吨）B=从 Bedford 处定购的炼焦煤量（千吨）C=从 Consol 处定购的炼焦煤量（千吨）D=从 Dunby 处定购的炼焦煤
6、量（千吨）E=从 Earlam 处定购的炼焦煤量（千吨）F=从 Florence处定购的炼焦煤量（千吨）G=从 Gaston 处定购的炼焦煤量（千吨）H=从 Hopt 处定购的炼焦煤量（千吨）,供应成本成：49.5A+50B+61C+63.5D+66.5E+71F+72.5G+80H供应约束：A+B+C+D+E+F+G+H=1,225工会煤矿的约束：A+B C+D E+F G H 0卡车运输量约束：B+D+E+F 720火车运输量约束：A+C+G+H 650平均可燃率约束：可改写成：4A 3B C+D+2E+3F+4G+6H 0各煤矿的炼焦煤供应量约束：A 300，B 600，C 510，D
7、655，E 575，F 680，G 450，H 490非负约束：A 0，B 0，C 0，D 0，E 0，F 0，G 0，H 0,NBS的炼焦煤供应问题的线性最优化模型,MINIMIZE COST=49.5A+50B+61C+63.5D+66.5E+71F+72.5G+80HSUBJECT TO：SUPPLY：A+B+C+D+E+F+G+H=1,225UNION：A+B C+D E+F G H 0TRUCK：B+D+E+F 720RAIL：A+C+G+H 650VOL：4A 3B C+D+2E+3F+4G+6H 0ACAP：A 300BCAP：B 600CCAP：C 510DCAP：D 655E
8、CAP：E 575FCAP：F 680GCAP：G 450HCAP：H 490NONNEGATIVITY CONDITIONS：A0,B0,C0,D0,E0,F0,G0,H0,NBS的炼焦煤供应问题的线性最优化模型,求解，得：A=55千吨，B=600千吨，C=0千吨，D=20千吨，E=100千吨，F=0千吨，G=450千吨，H=0千吨；最小成本=73,267.50千美元；平均供应成本=73,267.50/1,225=59.81美元/吨,二、线性规划数学模型的几种表达形式,一般形式目标函数：Max（Min）z=c1 x1+c2 x2+cn xn 约束条件：s.t.a11 x1+a12 x2+a1
9、n xn（=,）b1 a21 x1+a22 x2+a2n xn（=,）b2 am1 x1+am2 x2+amn xn（=,）bm x1，x2，xn 0,简写形式目标函数：Max（Min）z=约束条件：s.t.（=,）bi,i=1,2,.m xj 0,j=1,2,.n,向量形式C=(c1,c2,cn)价值向量,二、线性规划数学模型的几种表达形式,限定向量,变量xj对应的系数列向量,二、线性规划数学模型的几种表达形式,矩阵形式,约束条件系数矩阵,第二节 线性规划问题的标准形式,一、标准形式目标函数：Max z=c1 x1+c2 x2+cn xn 约束条件：s.t.a11 x1+a12 x2+a1n
10、 xn=b1 a21 x1+a22 x2+a2n xn=b2 am1 x1+am2 x2+amn xn=bm x1，x2，xn 0,或,即:同时满足如下四个条件:目标函数求极大约束条件全为等式约束条件右端常数项全为非负变量取值全为非负,2.1 线性规划问题与标准形式,为了今后讨论的方便，我们称以下两种形式的线性规划问题为线性规划的规范形式（Canonical Form）：minzCTXs.t.AXb X0maxzCTX s.t.AXbX0,2.1 线性规划问题与标准形式,而称以下的形式为标准形式（Standard Form）：max zCTXs.t.AXb X0 对于各种非标准形式的线性规划问
11、题，我们总可以通过以下的变换，将其转化为标准形式。1 极小化目标函数的问题2 约束条件不是等式的问题3 变量无符号限制的问题,1 极小化目标函数的问题,设目标函数为,令zz，则以上极大化问题和极小化问题有相同的最优解，即,但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即,minzmax z,2 约束条件不是等式的问题,设约束条件为(i=1,2,m)可以引进一个新的变量xn+i，使它等于约束右边与左边之差显然xn+I也具有非负约束，即xn+i0，这时新的约束条件成为当约束条件为,2 约束条件不是等式的问题,时，类似地令,则同样有xn+i0，新的约束条件成为,为
12、了使约束由不等式成为等式而引进的变量xn+i称为“松弛变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。,3 变量无符号限制的问题,在标准形式中，每一个变量都有非负约束。当一个变量xj没有非负约束时，可以令xj=xj-xj”其中xj0，xj”0 即用两个非负变量之差来表示一个无符号限制的变量，当xj的符号取决于xj和xj”的大小。,2.2 线性规划问题的几何解释,对于只有两个变量的线性规划问题，可以在二维直角坐标平面上表示线性规划问题。,Max z=x1+3x2s.t x1+x26-x1+2x28 x1,x2 0,例1.4.1的线性规划问题的可行
13、域如图1.4.1中阴影部分所示。,2.2 线性规划问题的几何解释,2.2 线性规划问题的几何解释,在以上问题中，目标函数等值线在平行移动过程中与可行域的最后一个交点是B点，这就是线性规划问题的最优解，这个最优解可以由两直线x1+x2=6-x1+2x2=8的交点求得,最优解的目标函数值为,2.2 线性规划问题的几何解释,定义1.4.3 设S是n维空间中的一个点集。若对任意n维向量X1S，X2S，且X1X2，以及任意实数（01），有X=X1+(1-)X2S则称S为n维空间中的一个凸集。点X称为点X1和X2的凸组合。以上定义有明显的几何意义，它表示凸集S中的任意两个不相同的点连线上的点（包括这两个端
14、点），都位于凸集S之中。图1.4.2表示二维平面中一些凸集和非凸集的例子。,2.2 线性规划问题的几何解释,(a)凸集,(b)凸集,(c)凸集,(d)非凸集,(e)非凸集(d)非凸集,(f)非凸集,2.2 线性规划问题的几何解释,定义1.4.4 设S为一凸集，且XS，X1S，X2S。对于01，若X=X1+(1-)X2则必定有X=X1=X2，则称X为S的一个极点。,运用以上的定义，线性规划的可行域以及最优解有以下性质：1、若线性规划的可行域非空，则可行域必定为一凸集。2、若线性规划有最优解，则最优解至少位于一个极点上。,这样，求线性规划最优解的问题，从在可行域内无限个可行解中搜索的问题转化为在其
15、可行域的有限个极点上搜索的问题。最后，来讨论线性规划的可行域和最优解的几种可能的情况。1、可行域为封闭的有界区域,2、可行域为非封闭的无界区域,2.2 线性规划问题的几何解释,3、可行域为空集，因而没有可行解。以上几种情况的图示如下：,(a)可行域有界,(b)可行域有界,(c)可行域无界,唯一最优解,唯一最优解,唯一最优解,2.2 线性规划问题的几何解释,(d)可行域无界(e)可行域无界,(f)可行域为空集,多个最优解 目标函数无界 无可行解,图1.4.3线性规划可行域和最优解的几种情况,2.3 单纯形法方法,设线性规划的约束条件为AX=bX0其中A为mn的矩阵，nm，秩A=m，b为m1向量。
16、定义2.6 线性规划的基(Basis)设B是A矩阵中的一个非奇异的mm子矩阵，则称B为线性规划的一个基(矩阵).定义2.7设B是线性规划的一个基（矩阵），线性规划的解:称为线性规划与基B对应的基础解。若其中B-1b0，则称以上的基础解为一基础可行解，相应的基B称为可行基。定理2.1 线性规划的基础可行解就是可行域的极点。,2.3 单纯形法方法,1 单纯形原理的矩阵描述 2 单纯形表 3 初始基础可行解 4 退化和循环,1 单纯形原理的矩阵描述,设标准的线性规划问题为max z=CTXs.t.AX=b(1.6.1)X0并设A=a1，a2，an其中a j(j=1，2，n)是A矩阵的第j个列向量。B
17、=a1，a2，am是A的一个基。,1 单纯形原理的矩阵描述,这样，矩阵A可以分块记为A=B，N，相应地，向量X和C可以记为,并设R为非基变量的下标集合。利用以上的记号，（1.6.1）中的等式约束AX=b可以写成BXB+NXN=b即XB=B-1b-B-1NXN(1.6.2)这就是在约束条件中，基变量用非基变量表出的形式。,1 单纯形原理的矩阵描述,对于一个确定的基B，目标函数z可以写成,将(1.6.2)式代入以上目标函数表达式，得到目标函数z用非基变量表出的形式,1 单纯形原理的矩阵描述,(1.6.2)和(1.6.3)式表示，非基变量的任何一组确定的值，基变量和目标函数都有一组确定的值与之对应。
18、特别，当XN=0时，相应的解,就是对应于基B的基础解。如果B是一个可行基，则有,1 单纯形原理的矩阵描述,下面我们来详细说明如何实现以上步骤。步骤1、获得初始基础可行解的一般化的方法将在下一节中叙述。在这里，我们假定已经获得了一个初始的可行基B，基B对应的基础解为,当前的目标函数值为,1 单纯形原理的矩阵描述,步骤2、确定进基的非基变量xk由(1.6.1)可知，当前目标函数值用非基变量用非基变量表出的形式是,令,1 单纯形原理的矩阵描述,则,如果对于所有jR，有zj-cj0，则任何非基变量xj的值由0开始增加都不会使z减少，因此当前基B已是最优基，相应的基础可行解,如果有kR，使zk-ck0，
19、则非基变量xk的增加将会使目标函数值减少。为了使目标函数值下降得快一些，一般选取满足,1 单纯形原理的矩阵描述,的非基变量xk为进基变量。由于除xk以外的非基变量的值均保持为0不变，这时目标函数可以表示为,步骤3、确定基变量中离基的变量xBr在(1.6.2)中，令,1 单纯形原理的矩阵描述,则(1.6.2)可以表示为,当进基变量xk的值由0增加到某一正值，其余非基变量均保持为0时，上式成为,1 单纯形原理的矩阵描述,即,1 单纯形原理的矩阵描述,在(1.6.6)中，有以下几种情形：（1）如果向量Yk中所有的分量yik0，则xk的增加将不会使任何xBi(i=1，2，.，m)减少，这时xk可无限增
20、加，同时所有的基变量仍保持非负。同时由于xk在目标函数中的系数zk-ck0，由(1.6.5)可知当xk增加时目标函数将无限减少，即目标函数无界。（2）如果向量Yk中至少有一个分量yik0，则xk由0开始增加将会使相应的基变量xBi的值由当前的值bi开始减少。当xk增加到,1 单纯形原理的矩阵描述,相应的基变量xBr=0，而其余的基变量xBi0（i=1，2，.，m，ir），这时基变量xBr离基，它在基B中相应的列向量aBr将换出基矩阵，进基变量xk在A矩阵中相应的列向量ak将取代基矩阵B中aBr的位置，得到新的可行基,B=aB1，aB2，aBr-1，ak，aBr+1，aBm新的基B相应的基变量的
21、值为,1 单纯形原理的矩阵描述,B相应的非基变量的值为XN=0B对应的目标函数值为,步骤4、由新的基B重新确定非基变量集合R，并重新计算(1.6.4)以判定B是否为最优基。若不是，计算(1.6.4)(1.6.8)以实现进一步的基变换。,2 单纯形表,单纯形算法的实质是将非基变量视为一组参数，并将目标函数和基变量都表示成为由非基变量表示的形式。即（1.6.2）和（1.6.3）两式。这样就可以讨论当非基变量变化时，目标函数和基变量随之变化的情况。我们可以用一个矩阵来表示单纯形法迭代中所需要的全部信息，这就是所谓的单纯形表。设线性规划问题为,max z=CTXs.t.AX=b(1.7.1)X0并设B
22、是A的一个可行基，并记A=B，N，相应地将目标函数系数向量C以及变量X表示为,2 单纯形表,则(1.7.1)可表为,即,2 单纯形表,将(1.7.3)的系数写成矩阵形式，有,2 单纯形表,称以上矩阵为线性规划问题的系数矩阵（并不是单纯形表）。为了将约束中的基变量用非基变量表出，用B-1左乘以上系数矩阵的后m行，得到,为了将第一行中的目标函数z用非基变量XN表出，在矩阵的后m行左乘CBT后加到第一行上，消去基变量在目标函数中的系数，得到,2 单纯形表,以上矩阵的第一行与(1.6.3)完全等价，后m行与(1.6.2)完全等价。这一矩阵称为与基B对应的单纯形表。单纯形表可以由系数矩阵经过一系列行变换
23、得到，这些行变换使得系数矩阵中的基矩阵变为单位矩阵I，而将基变量在目标函数中的系数全消为零。,2 单纯形表,利用上一节中的记号，可以将表1.7.3的单纯形表用分量的形式表示如表1.7.4。,可以看出，单纯形表中直接包含了单纯形迭代所需要的一切信息。,2 单纯形表,用单纯形表求解线性规划问题的步骤可以归纳如下：1、写出线性规划问题的系数矩阵表；2、找到一个可行基B，对系数矩阵进行变换，使得：（1）基矩阵成为单位矩阵；（2）基变量在目标函数中的系数为零。从而得到以B为基的单纯形表。3、根据单纯形表，确定进基变量x k和离基变量x r，并根据列指标k和行指标r确定主元y r k；4、以y r k为主
24、元进行行变换（称为以y r k为主元的旋转运算），使得单纯形表中y r k所在的列中其他元素为0，y r k本身为1；重复步骤3、4，直至获得最优解或确定目标函数无界。,3 初始基础可行解,设线性规划问题为min z=CTXs.t.AX=b X0(2.14)第一阶段：引进人工变量Xa=(xn+1，xn+2，xn+m)T，构造辅助问题(2.15),3 初始基础可行解,求解辅助问题。若辅助问题的最优基B全部在A中，即Xa全部是非基变量（min z=0），则B为(2.14)的一个可行基。转第二阶段。若辅助问题的最优目标函数值min z0，则至少有一个人工变量留在第一阶段问题最优解的基变量中，这时(2
25、.14)无可行解。,第二阶段：以第一阶段(2.15)的最优基B作为(1.8.4)的初始可行基，求解(2.14)，得到(2.14)的最优基和最优解。,4 退化和循环,如何防止出现循环作了大量研究。1952年Charnes提出了“摄动法”，1954年Dantzig，Orden和Wolfe又提出了“字典序法”。这些方法都比较复杂，同时也降低了叠代的速度。1976年，Bland提出了一个避免循环的新方法，其原则十分简单。仅在选择进基变量和离基变量时作了以下规定：1、在选择进基变量时，在所有zj-cj0的非基变量中选取下标最小的进基；2、当有多个变量同时可作为离基变量时，选择下标最小的那个变量离基。这样就可以避免出现循环。当然，用Bland的方法，由于选取进基变量时不再考虑zj-cj绝对值的大小，将会导致收敛速度的降低。,
