北邮运筹学1

©管理与人文学院忻展红1999，4运筹学OperationalResearch运筹帷幄，决胜千里史记《张良传》2目录第一章线性规划问题及单纯型解法第二章线性规划的对偶理论及其应用第三章运输问题数学模型及其解法第四章整数规划第五章动态规划第六章图与网路分析第七章随机服务理论概论第八章生灭服务系统第九章特殊随机服务系统第十章存储理论3绪论一、运筹学的起源与发展二、运筹学的特点及研究对象三、运筹学解决问题的方法步骤四、运筹学与其它学科之间的关系4第一章线性规划问题及单纯型解法1.1线性规划问题及其一般数学模型1.1.1线性规划问题举例例1、多产品生产问题（Max,）设x1,x2分别代表甲、乙两种电缆的生产量，.36)(max,6,2:0,78102..46)(max:21212212121xfxxxxxxxxxtsxxxfOBJ最优解产量不允许为负值产量约束铅资源约束铜资源约束5例2、配料问题（min,)原料甲原料乙最低含量VA0.50.52VB11.00.33VB20.20.61.2VD0.50.22单价0.30.5设x1,x2分别代表每粒胶丸中甲、乙两种原料的用量6例3、合理下料问题设xj分别代表采用切割方案1~8的套数，方案2.9m2.1m1.5m合计余料12017.30.121207.10.331116.50.941037.4050306.31.160227.20.271.1.2线性规划数学模型的一般表示方式技术系数右端项价值系数线性规划问题的规模约束行数变量个数:;:;::;:;:0,,,),(),(),(..)(max(min)21221122222121112121112211ijjjnmnmnmmnnnnnnabcmnmnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcxf81、和式njxmibxatsxcxfjinjjijnjjj,,2,1,0,,2,1,..)(max1192、向量式103、矩阵式111.1.3线性规划的图解法1187654322x1876543O109x2ABCEDFGH123f(x)=0f(x)=12.36)(max,6,2:0,78102..46)(max21212212121xfxxxxxxxxxtsxxxf最优解1187654322x1876543O109x2ABCEDFGH12312线性规划问题的几个特点：•线性规划问题的可性解的集合是凸集•线性规划问题的基础可行解一般都对应于凸集的极点•凸集的极点的个数是有限的•最优解只可能在凸集的极点上，而不可能发生在凸集的内部131.2线性规划问题的单纯型解法1.2.1线性规划问题的标准形式为了使线性规划问题的解法标准，就要把一般形式化为标准形式njxmibxatsxcxfjinjjijnjjj,,2,1),,0(0,,2,1,),(..)(max(min)11不限njmixbmibxatsxcxfjiimnjjijmnjjj,,2,1,,2,1,0,,,2,1,..)(max1114变换的方法：•目标函数为min型，价值系数一律反号。令f(x)=-f(x)=-CX,有minf(x)=-max[-f(x)]=-maxf(x)•第i个约束的bi为负值，则该行左右两端系数同时反号，同时不等号也要反向•第i个约束为型，在不等式左边增加一个非负的变量xn+i，称为松弛变量；同时令cn+i=0•第i个约束为型，在不等式左边减去一个非负的变量xn+i，称为剩余变量；同时令cn+i=0•若xj0，令xj=-xj，代入非标准型，则有xj0•若xj不限，令xj=xj-xj，xj0，xj0，代入非标准型15变换举例：0,,20040065300432..423)(min:213321321321321xxxxxxxxxxxxtsxxxxf不限原非标准型0,,,,,,2004006653004432..0004423)(max:65433216332153321433216543321xxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxf标准型16关于标准型解的若干基本概念：•标准型有n+m个变量，m个约束行•“基”的概念–在标准型中，技术系数矩阵有n+m列，即A=(P1,P2,…,Pn+m)–A中线性独立的m列，构成该标准型的一个基，即B=(P1,P2,…,Pm)，|B|0–P1,P2,…,Pm称为基向量–与基向量对应的变量称为基变量，记为XB=(x1,x2,…,xm)T，其余的变量称为非基变量，记为XN=(xm+1,xm+2,…,xm+n)T，故有X=XB+XN–最多有个基mnmC17关于标准型解的若干基本概念：•可行解与非可行解–满足约束条件和非负条件的解X称为可行解，满足约束条件但不满足非负条件的解X称为非可行解•基础解–令非基变量XN=0，求得基变量XB的值称为基础解即XB=B1b–XB是基础解的必要条件为XB的非零分量个数m•基础可行解–基础解XB的非零分量都0时，称为基础可行解，否则为基础非可行解–基础可行解的非零分量个数m时，称为退化解18线性规划标准型问题解的关系约束方程的解空间基础解可行解非可行解基础可行解退化解19可行解、基础解和基础可行解举例.36)(max,6,2:0,,,,78102..46)(max21543215242132121xfxxxxxxxxxxxxxxxtsxxxf最优解1187654322x1876543O109x2ABCEDFGH123f(x)=36K非基变量基变量图中的点解x1,x2x3=10x4=8x5=7O基础可行解x1,x3x2=10x4=-2x5=-3F基础解x1,x4x2=8x3=2x5=-1E基础解x1,x5x2=7x3=3x4=1A基础可行解x2,x3x1=5x4=3x5=7D基础可行解x2,x4x1=8x3=-6x5=7H基础解x3,x4x1=2x2=6x5=1C基础可行解最优解x3,x5x1=1.5x2=7x4=-0.5G基础解x4,x5x1=1x2=7x3=1B基础可行解x1=2,x2=2,x3=4,x4=4,x5=3K可行解201.2.2单纯型法的基本思路确定初试基础可行解求最优解的目标函数值确定改善方向求新的基础可行解检查是否为最优解？是否211.2.3单纯型表及其格式IVIIIIIIx1x2…xnxn+1xn+2…xn+mCBXBbc1c2…cncn+1cn+2…cn+mc1=cn+1xn+1b1a11a12…a1n10…0c2=cn+2xn+2b2a21a22…a2n01…0cm=cn+mxn+mbmam1am2…amn00…1OBJz1z2…znzn+1zn+2…zn+mc1-z1c2-z2…cn-zncn+1-zn+1cn+2-zn+2…cn+m-zn+m22例1.2.2试列出下面线性规划问题的初始单纯型表0,,12023310032..244540)(max321321321321xxxxxxxxxtsxxxxfx1x2x3x4x5CBXBb404524000x4100231100x512033201OBJ=0zj00000cj-zj4045240023关于检验数的数学解释•设B是初始可行基，则目标函数可写为两部分(1)•约束条件也写为两部分，经整理得XB的表达式(2)，注意XB中含有非基变量作参数•把XB代入目标函数，整理得到(3)式•第j个非基变量的机会成本如(4)式•若有cjzj0,则未达到最优(5)(4))3()()()((2))((1))(1'jjmiijijNN1BN1BNN1BNNNN1BNNBBNNBBNNzcaczXABCCbBCXAbBCXCxfXAbBXXAbBXbBXXAXCXCxf检验数机会成本241.2.4标准型的单纯型算法1找初试基础可行基–对于(max,)，松弛变量对应的列构成一个单位阵–若有bi0，则单位阵也不能构成一个可行基2检验当前基础可行解是否为最优解–所有检验数cjzj0，则为最优解，否则3确定改善方向–从(cjzj)0中找最大者，选中者称为入变量，xj*–第j*列称为主列4确定入变量的最大值和出变量–最小比例原则(1.2.4)0min**ijijiiaab251.2.4标准型的单纯型算法4确定入变量的最大值和出变量–设第i*行使最小，则第i*行对应的基变量称为出变量，第i*行称为主行5迭代过程–主行i*行与主列j*相交的元素ai*j*称为主元，迭代以主元为中心进行–迭代的实质是线性变换，即要将主元ai*j*变为1，主列上其它元素变为0，变换步骤如下：(1)变换主行nmjaaajijiji,,2,1****261.2.4标准型的单纯型算法5迭代过程(2)变换主列除主元保留为1，其余都置0(3)变换非主行、主列元素aij(包括bi)四角算法公式：数据表示当前单纯型表中的的数据表示上一个单纯型表中,(1.2.5b)(1.2.5a)********ijijijiijjiijijjiijiiiaabaaaaaaabbb271.2.4标准型的单纯型算法5、迭代过程(4)变换CB，XB(5)计算目标函数、机会成本zj和检验数cjzj6、返回步骤2aijai*jaij*ai*j*主行主列主元四角算法图示28表1.2.4例1.2.2单纯型表的迭代过程x1x2x3x4x5序号CBXBb40452400bi/aij*0x41002(3)110(33.3)0x51203320140OBJ=000000I初始解cj-zj4045240045x2100/32/311/31/30500x520(1)0111(20)OBJ=1500304515150IIcj-zj100915045x220011/312/340x12010111OBJ=1700404525510III最优解cj-zj001510答：最优解为x1=20,x2=20,x3=0,OBJ=170029单纯型表中元素的几点说明–任何时候，基变量对应的列都构成一个单位矩阵–当前表中的b列表示当前基变量的解值，通过变换B1b得到(资源已变成产品)–当前非基变量对应的向量可通过变换B1AN得到，表示第j个变量对第i行对应的基变量的消耗率–非基变量的机会成本由给出–注意基变量所对应的行x1x2x3x4x5序号CBXBb40452400bi/aij*45x2100/32/311/31/30500x520(1)0111(20)OBJ=1500304515150IIcj-zj1009150ijamiijijacz1'301.3人工变量的引入及其解法1.3.1当约束条件为“”型，引入剩余变量和人工变量•由于所添加的剩余变量的技术系数为1，不能作为初始可行基变量，为此引入一个人为的变量（注意，此时约束条件已为“=”型），以便取得初始基变量，故称为人工变量•由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。罚系数的取值视解法而定•两种方法–大M法–二阶段法311.3.2大M法的求解过程例1.3.132表1.3.1例1.3.1的单纯型表迭代过程x1x2x3x4x5x6序号CBXBb108700Mbi/aij*Mx