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

运筹学灵敏度分析析价值系数C发生变化：：m考虑检验数数j=cj-∑criarijj=1,2,……,ni=11、若ck是非基变量量的系数：：设ck变化为ck+ckk’=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,……,nci,bj发生变化化——本段重点增加一约约束或变变量及A中元素发发生变化化—通过例题题学会处处理对于表格格单纯形形法，通通过计算算得到最最优单纯纯形表。。应能能够找到到最优基基B的逆矩阵阵B-1，B-1b以及B-1N，检验数数j等。3.灵敏度分分析价值系数数c发生变化化：m考虑检验验数j=cj-∑criarijj=1,2,………,ni=11.若ck是非基变变量的系系数：设ck变化为ck+ckk’=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.灵敏度分析例：最优单纯纯形表从表中看到σ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/asjasj>0}≤cs≤Min{j/asjasj<0}3.灵敏度分析例3.4:Maxz=2x1+3x2+0x3+0x4+0x5s.t.x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,x3,x4,x5≥03.灵敏度分析例:下表为最优单单纯形表,考虑基变量系数c2发生变化从表中看到σ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/airair>0}≤br≤Min{-bi/airair<0}3.灵敏度度分析析例3.5:上例最最优单单纯形形表如如下3.灵敏度度分析析00.250这里B-1=-20.510.5-0.1250各列分分别对对应b1、b2、b3的单一一变化化因此，，设b1增加4，则x1,x5,x2分别变变为：：4+0×4=4,4+(-2)×4=-4<0,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计算得得到用单纯纯形法法进一一步求求解，，可得得：x*=(1,1.5,0,0,0,2)Tf*=16.53.灵敏度度分析析增加一一个约约束增加约约束一一个之之后，，应把把最优优解带带入新的的约束束，若若满足足则最最优解解不变变，否否则填入最最优单单纯形形表作作为新新的一一行，，引入入一个新的的非负负变量量（原原约束束若是是小于于等于于形式可可引引入入非非负负松松弛弛变变量量，，否否则则引引入入非非负负人人工变变量量）），，并并通通过过矩矩阵阵行行变变换换把把对对应应基基变变量的的元元素素变变为为0，进进一一步步用用单单纯纯形形法法或或对对偶单单纯纯形形法法求求解解。。3.灵敏敏度度分分析析例3.7:例3.4增加加3x1+2x2≤15，原原最最优优解解不不满足足这这个个约约束束。。于是是3.灵敏敏度度分分析析经对对偶偶单单纯纯形形法法一一步步，，可可得得最最优优解解为为（（3.5,2.25,0,0,3,2)T，最最优优值值为为13.75A中元元素素发发生生变变化化(只讨讨论论N中某某一一列列变化化情情况况））与增增加加变变量量xn+1的情情况况类类似似，，假假设设pj变化化。。那么么，，重重新新计计算算出出B-1pjj=cj-∑∑criarij填入入最最优优单单纯纯形形表表，，若若j≤0则最最优解解不不变变；；否否则则，，进进一一步步用用单单纯纯形形法法求求解解。。（例例子子从从略略））3.灵敏敏度度分分析析Chapter5目标标规规划划(Goalprogramming)目标标规规划划问问题题及及其其数数学学模模型型目标标规规划划的的图图解解分分析析法法求求解解方方法法目标标规规划划应应用用举举例例本章主要内容：目标标规规划划问问题题及及其其数数学学模模型型问题题的的提提出出：：目标标规规划划是是在在线线性性规规划划的的基基础础上上，，为为适适应应经经济济管管理理多多目目标标决决策策的的需需要要而而由由线线性性规规划划逐逐步步发发展展起起来来的的一一个个分分支支。。由于于现现代代化化企企业业内内专专业业分分工工越越来来越越细细，，组组织织机机构构日日益益复复杂杂，，为为了了统统一一协协调调企企业业各各部部门门围围绕绕一一个个整整体体的的目目标标工工作作，，产产生生了了目目标标管管理理这这种种先先进进的的管管理理技技术术。。目目标标规规划划是是实实行行目目标标管管理理的的有有效效工工具具，，它它根根据据企企业业制制定定的的经经营营目目标标以以及及这这些些目目标标的的轻轻重重缓缓急急次次序序，，考考虑虑现现有有资资源源情情况况，，分分析析如如何何达达到到规规定定目目标标或或从从总总体体上上离离规规定定目目标标的的差差距距为为最最小小。。目标标规规划划问问题题及及其其数数学学模模型型例5.1某某企企业业计计划划生生产产甲甲，，乙乙两两种种产产品品，，这这些些产产品品分分别别要要在在A,B,C,D四四种种不不同同设设备备上上加加工工。。按按工工艺艺文文件件规规定定，，如如表表所所示示。。ABCD单件利润甲11402乙22043最大负荷1281612问该该企企业业应应如如何何安安排排计计划划，，使使得得计计划划期期内内的的总总利利润润收收入入为为最最大大？？目标标规规划划问问题题及及其其数数学学模模型型解：：设设甲甲、、乙乙产产品品的的产产量量分分别别为为x1，x2，建建立立线线性性规规划划模模型型：：其最最优优解解为为x1＝4，，x2＝2，，z＊＝14元元目标标规规划划问问题题及及其其数数学学模模型型但企企业业的的经经营营目目标标不不仅仅仅仅是是利利润润，，而而且且要要考考虑虑多多个个方方面面，，如如：：力求求使使利利润润指指标标不不低低于于12元；；考虑虑到到市市场场需需求求，，甲甲、、乙乙两两种种产产品品的的生生产产量量需需保保持持1:1的比比例例；；C和D为贵贵重重设设备备，，严严格格禁禁止止超超时时使使用用；；设备备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设备的的使用用限制制。对不严严格限限制的的约束束，连连同原原线性性规划划建模模时的的目标标，均均通过过目标标约束束来表表达。。1）例如如要求求甲、、乙两两种产产品保保持1:1的比例例，系系统约约束表表达为为：x1=x2。由于于这个个比例例允许许有偏偏差，，当x1<x2时，出出现负负偏差差d-，即：：x1+d-=x2或x1－x2+d-=0当x1>x2时，出出现正正偏差差d+，即：：x1-d+=x2或x1－x2-d+=0目标规规划问问题及及其数数学模模型∵正负负偏差差不可可能同同时出出现，，故总总有：：x1－x2+d--d+=0若希望望甲的的产量量不低低于乙乙的产产量，，即不不希望望d->0,用目标标约束束可表表为:若希望望甲的的产量量低于于乙的的产量量，即即不希希望d＋>0,用目标标约束束可表表为:若希望望甲的的产量量恰好好等于于乙的的产量量，即即不希希望d＋>0,也不希希望d->0用目标标约束束可表表为:目标规规划问问题及及其数数学模模型3）设备备B必要时时可加加班及及加班班时间间要控控制，，目标标约束束表示示为：：2）力求求使利利润指指标不不低于于12元，目目标约约束表表示为为：4）设备备A既要求求充分分利用用，又又尽可可能不不加班班，目目标约约束表表示为为：目标规规划问问题及及其数数学模模型3.目标的的优先先级与与权系系数在一个个目标标规划划的模模型中中，为为达到到某一一目标标可牺牺牲其其他一一些目目标，，称这这些目目标是是属于于不同同层次次的优优先级级。优优先级级层次次的高高低可可分别别通过过优先先因子子P1,P2,…表示。。对于于同一一层次次优先先级的的不同同目标标，按按其重重要程程度可可分别别乘上上不同同的权权系数数。权权系数数是一一个个个具体体数字字，乘乘上的的权系系数越越大，，表明明该目目标越越重要要。现假定定：第1优先级级P1———企业利利润；；第2优先级级P2———甲乙产产品的的产量量保持持1:1的比例例第3优先级级P3———设备A,B尽量不不超负负荷工工作。。其中中设备备A的重要要性比比设备备B大三倍倍。目标规规划问问题及及其数数学模模型上述目目标规规划模模型可可以表表示为为：目标规规划问问题及及其数数学模模型目标规规划数数学模模型的的一般般形式式达成函数目标约束其中：gk为第k个目标约束束的预期目目标值，和和为为pl优先因子对对应各目标标的权系数数。目标规划问问题及其数数学模型用目标规划划求解问题题的过程：：明确问题，，列出目标标的优先级级和权系数数构造目标规规划模型求出满意解解满意否？分析各项目目标完成情情况据此制定出出决策方案案NY目标规划的的图解分析析法目标规划的的图解法：：适用两个变变量的目标标规划问题题，但其操操作简单，，原理一目目了然。同同时，也有有助于理解解一般目标标规划的求求解原理和和过程。图解法解题题步骤：1.将所有约束束条件（包包括目标约约束和绝对对约束，暂暂不考虑正正负偏差变变量）的直直线方程分分别标示于于坐标平面面上。2.确定系统约约束的可行行域。3.在目标约束束所代表的的边界线上上，用箭头头标出正、、负偏差变变量值增大大的方向目标规划的的图解分析析法3.求满足最高高