01运筹学-灵敏度分析目标规划

运筹学灵敏度分析价值系数C发生变化：m考虑检验数j=cj-∑criarijj=1,2,……,ni=11、若ck是非基变量的系数：设ck变化为ck+ckk’=ck+ck-∑criarik=k+ck只要k’≤0，即ck≤-k，则最优解不变；否则，将最优单纯形表中的检验数k用k’取代，继续单纯形法的表格计算。例:MaxZ=-2x1-3x2-4x3S.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥02、线性规划问题的进一步研究（2.3）进一步理解最优单纯性表中各元素的含义考虑问题Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2...am1x1+am2x2+…+amnxn=bmx1，x2，…，xn≥03.灵敏度分析3、灵敏度分析无防设，xj=0j=m+1,…,n;xi=bi’i=1,…,m是基本可行解,对应的目标函数典式为：z=-f+m+1xm+1+…+nxn以下是初始单纯形表：mm其中：f=-∑cibi’j=cj-∑ciaij’为检验数。向量b’=B-1bi=1i=1A=[p1,p2,…,pn],pj’=B-1pj,pj’=(a1j’,a2j’,…,amj’)T，j=m+1,…,nc1…cmcm+1…cnCBXBx1…xmxm+1…xnθic1x1b1'1…0a'1m+1…a'1nθ1c2x2b2'0…0a'2m+1…a'2nθ2┇┇┇┇┇┇┇┇┇┇cmxmbm'0…1a'mm+1…a'mnθm-zf0…0σm+1…σnci,bj发生变化——本段重点增加一约束或变量及A中元素发生变化—通过例题学会处理对于表格单纯形法，通过计算得到最优单纯形表。应能够找到最优基B的逆矩阵B-1，B-1b以及B-1N，检验数j等。3.灵敏度分析价值系数c发生变化：m考虑检验数j=cj-∑criarijj=1,2,……,ni=11.若ck是非基变量的系数：设ck变化为ck+ckk’=ck+ck-∑criarik=k+ck只要k’≤0,即ck≤-k，则最优解不变；否则，将最优单纯形表中的检验数k用k’取代，继续单纯形法的表格计算。3.灵敏度分析例3.3:Maxz=-2x1-3x2-4x3S.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥03.灵敏度分析例：最优单纯形表CI-2-3-400CBXBbX1X2X3X4X5-3X22/501-1/5-2/51/5-2X111/5107/5-1/5-2/5σj00-9/5-8/5-1/5CI-2-3-4+Δc300CBXBbX1X2X3X4X5-3X22/501-1/5-2/51/5-2X111/5107/5-1/5-2/5σj00-9/5+Δc3-8/5-1/5从表中看到σ3=c3+Δc3-(c2×a13+c1×a23)可得到Δc3≤9/5时，原最优解不变。3.灵敏度分析2、若cs是基变量的系数：设cs变化为cs+cs，那么j’=cj-∑criarij-(cs+cs)asj=j-csasj，i≠s对所有非基变量，只要对所有非基变量j’≤0，即j≤csasj，则最优解不变；否则，将最优单纯形表中的检验数j用j’取代，继续单纯形法的表格计算。Max{j/asjasj0}≤cs≤Min{j/asjasj0}3.灵敏度分析例3.4:Maxz=2x1+3x2+0x3+0x4+0x5s.t.x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,x3,x4,x5≥03.灵敏度分析例:下表为最优单纯形表,考虑基变量系数c2发生变化Ci23000CBXBBX1X2X3X4X52X141001/400X5400-21/213X22011/2-1/80σj00-1.5-1/80Ci23+ΔC2000CBXBBX1X2X3X4X52X141001/400X5400-21/213+ΔC2X22011/2-1/80σj00-1.5-ΔC2/2-1/8+ΔC2/80从表中看到σj=cj-(c1×a1j+c5×a5j+(c2+Δc2)×a2j)j=3,4可得到-3≤Δc2≤1时，原最优解不变。3.灵敏度分析右端项b发生变化设分量br变化为br+br，根据第1章的讨论，最优解的基变量xB=B-1b，那么只要保持B-1(b+b)≥0，则最优基不变，即基变量保持，只有值的变化；否则，需要利用对偶单纯形法继续计算。对于问题(LP)Maxz=cTxs.t.Ax≤bx≥03.灵敏度分析最优单纯形表中含有B-1=(aij）i=1,…,m;j=n+1,…,n+m那么新的xi=(B-1b)i+brairi=1,…,m。由此可得，最优基不变的条件是Max{-bi/airair0}≤br≤Min{-bi/airair0}3.灵敏度分析例3.5:上例最优单纯形表如下Ci23000CBXBBX1X2X3X4X52X141001/400X5400-21/213X22011/2-1/80σj00-1.5-1/803.灵敏度分析00.250这里B-1=-20.510.5-0.1250各列分别对应b1、b2、b3的单一变化因此，设b1增加4，则x1,x5,x2分别变为：4+0×4=4,4+(-2)×4=-40,2+0.5×4=4用对偶单纯形法进一步求解，可得：x*=(4,3,2,0,0)Tf*=173.灵敏度分析增加一个变量增加变量xn+1则有相应的pn+1,cn+1。那么计算出B-1pn+1,n+1=cn+1-∑criarin+1填入最优单纯形表,若n+1≤0则最优解不变；否则，进一步用单纯形法求解。3.灵敏度分析例3.6:例3.4增加x6,p6=(2,6,3)T,c6=5计算得到Ci230005CBXBbX1X2X3X4X5X62X141001/401.50X5400-21/21[2]3X22011/2-1/800.25σj00-1.5-1/801.25用单纯形法进一步求解，可得：x*=(1,1.5,0,0,0,2)Tf*=16.53.灵敏度分析增加一个约束增加约束一个之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为0，进一步用单纯形法或对偶单纯形法求解。3.灵敏度分析例3.7:例3.4增加3x1+2x2≤15，原最优解不满足这个约束。于是Ci230000CBXBbX1X2X3X4X5X62X141001/4000X5400-21/2103X22011/2-1/8000X6-100-1-1/201σj00-1.5-1/8003.灵敏度分析经对偶单纯形法一步，可得最优解为（3.5,2.25,0,0,3,2)T，最优值为13.75A中元素发生变化(只讨论N中某一列变化情况）与增加变量xn+1的情况类似，假设pj变化。那么，重新计算出B-1pjj=cj-∑criarij填入最优单纯形表，若j≤0则最优解不变；否则，进一步用单纯形法求解。（例子从略）3.灵敏度分析Chapter5目标规划(Goalprogramming)目标规划问题及其数学模型目标规划的图解分析法求解方法目标规划应用举例本章主要内容：目标规划问题及其数学模型问题的提出：目标规划是在线性规划的基础上，为适应经济管理多目标决策的需要而由线性规划逐步发展起来的一个分支。由于现代化企业内专业分工越来越细，组织机构日益复杂，为了统一协调企业各部门围绕一个整体的目标工作，产生了目标管理这种先进的管理技术。目标规划是实行目标管理的有效工具，它根据企业制定的经营目标以及这些目标的轻重缓急次序，考虑现有资源情况，分析如何达到规定目标或从总体上离规定目标的差距为最小。目标规划问题及其数学模型例5.1某企业计划生产甲，乙两种产品，这些产品分别要在A,B,C,D四种不同设备上加工。按工艺文件规定，如表所示。ABCD单件利润甲11402乙22043最大负荷1281612问该企业应如何安排计划，使得计划期内的总利润收入为最大？目标规划问题及其数学模型解：设甲、乙产品的产量分别为x1，x2，建立线性规划模型：0,124164821222.32max2121212121xxxxxxxxtsxxz其最优解为x1＝4，x2＝2，z＊＝14元目标规划问题及其数学模型但企业的经营目标不仅仅是利润，而且要考虑多个方面，如：(1)力求使利润指标不低于12元；(2)考虑到市场需求，甲、乙两种产品的生产量需保持1:1的比例；(3)C和D为贵重设备，严格禁止超时使用；(4)设备B必要时可以加班，但加班时间要控制；设备A即要求充分利用，又尽可能不加班。要考虑上述多方面的目标，需要借助目标规划的方法。目标规划问题及其数学模型线性规划模型存在的局限性：1）要求问题的解必须满足全部约束条件，实际问题中并非所有约束都需要严格满足。2）只能处理单目标的优化问题。实际问题中，目标和约束可以相互转化。3）线性规划中各个约束条件都处于同等重要地位，但现实问题中，各目标的重要性即有层次上的差别，同一层次中又可以有权重上的区分。4）线性规划寻求最优解，但很多实际问题中只需找出满意解就可以。目标规划问题及其数学模型目标规划怎样解决上述线性规划模型建模中的局限性？1.设置偏差变量，用来表明实际值同目标值之间的差异。偏差变量用下列符号表示：d+——超出目标的偏差，称正偏差变量d-——未达到目标的偏差，称负偏差变量正负偏差变量两者必有一个为0。当实际值超出目标值时：d+0,d-=0;当实际值未达到目标值时：d+=0,d-0;当实际值同目标值恰好一致时：d+=0,d-=0;故恒有d+×d-=0目标规划问题及其数学模型2.统一处理目标和约束。对有严格限制的资源使用建立系统约束，数学形式同线性规划中的约束条件。如C和D设备的使用限制。12416421xx对不严格限制的约束，连同原线性规划建模时的目标，均通过目标约束来表达。1）例如要求甲、乙两种产品保持1:1的比例，系统约束表达为：x1=x2。由于这个比例允许有偏差，当x1x2时，出现负偏差d-，即：x1+d-=x2或x1－x2+d-=0当x1x2时，出现正偏差d+，即：x1-d+=x2或x1－x2-d+=0目标规划问题及其数学模型∵正负偏差不可能同时出现，故总有：x1－x2+d--d+=00}min{21ddxxd若希望甲的产量不低于乙的产量，即不希望d-0,用目标约束可表为:若希望甲的产量低于乙的产量，即不希望d＋0,用目标约束可表为:0}min{21ddxxd若希望甲的产量恰好等于乙的产量，即不希望d＋0,也不希望d-0用目标约束可表为:0}min{21ddxxdd目标规划问题及其数学模型3）设备B必要时可加班及加班时间要控制，目标约束表示为：82}min{21ddxxd2）力求使利润指标不低于12元，目标约束表示为：1232}min{21ddxxd4）设备A既要求充分利用，又尽可能不加班，目标约束表示为：1222}min{21ddxxdd目标规划问题及其数学模型3.目标的优先级与权系数在一个目标规划的模型中，为达到某一目标可牺牲其他一些目标，称这些目标是属于不同层次的优先级。优先级层次的高低可分别通过优先因子P1,P2,…表示。对于同一层次优先级的不同目标，按其重要程度可分别乘上不同的权系数。权系数是一个个具体数字，乘上的权系数越大，表明该目标越重要。现假定：第1优先级P1——企业利润；第2优先级P2——甲乙产品的产量保持1:1的比例