运筹学胡运权五版PPT课件

.,1,运筹学,(OperationsResearch),.,2,一、古代朴素的运筹学思想,例如：田忌赛马,二、运筹学的起源,国外英文原名OperationsResearch简称“O.R.”直译为：运用研究或作业研究正式出现于1938年7月英国一份关于防空作战系统运行的研究报告中二战后运筹学的发展经历了三个阶段,绪论,.,3,国内1956年成立第一个运筹学小组1957年从“夫运筹策帷幄之中，决胜于千里之外”中摘取“运筹”二字，将O.R.正式翻译为“运筹学”,三、运筹学的定义,研究工具：数学，计算机科学及其他相关科学,研究目的：对有限资源进行合理规划、使用，并提供优化决策方案。,研究对象：复杂系统的组织和管理,参考大英百科全书、辞海、中国企业管理百科全书等。,.,4,四、运筹学研究的基本特点,系统的整体优化多学科的配合模型方法的应用,五、运筹学研究的基本步骤,分析与表述问题建立数学模型对问题求解对模型和模型导出的解进行检验建立对解的有效控制方案的实施,.,5,六、本课程的主要学习内容,第一章线性规划及单纯形法第二章线性规划的对偶理论第三章运输问题第四章整数规划与分配问题第六章图与网络分析,.,6,第一章线性规划及单纯形法,LinearProgrammingandSimplexMethod,.,7,x,a,此为无约束的极值问题,1.1一般线性规划问题的数学模型,1-1问题的提出,例1用一块边长为a的正方形铁皮做一个无盖长方体容器，应如何裁剪可使做成的容器的容积最大？,解：如图设四个角上减去的小正方形边长为x，则容器体积为：,时，容积最大,.,8,例2常山机器厂生产I、II两型产品。这两型产品都分别要在A、B、C三种不同设备上加工。按工艺规定，生产每件产品的单位利润、消耗三种设备的工时以及各种设备工时的限额如下表：,如何安排生产才能使总的利润最大？,.,9,解：设计划期内两种产品的数量分别为x1，x2，则总利润为：,maxz=2x1+3x2,2x1+2x212,4x116,5x215,x10，x20,简记为：,s.t.（约束于：）,z=2x1+3x2,在满足限制条件下求z的最大值。,此为有约束极值问题,.,10,1-2线性规划问题的数学模型,原型,模型,数学模型,提炼,数学工具,1、原型：现实世界中人们关心、研究的实际对象。模型：将某一部分信息简缩、提炼而构造的原型替代物。数学模型：对现实世界的一个特定对象，为达到一定目的，根据内在规律做出必要的简化假设,并运用适当数学工具得到的一个数学结构。,.,11,3、规划问题数学模型的三要素,（2）目标函数：问题要达到的目标要求，表示为决策变量的函数。用z=f(x1，x2，xn)表示。,（1）决策变量：决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。用x1，x2，xn表示。,（3）约束条件：决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。,2、规划问题,即求目标函数在若干约束条件下的最值。,.,12,4、线性规划问题（LinearProgramming）的数学模型,（2）一般形式：,（1）条件：决策变量为可控的连续变量，目标函数和约束条件都是线性的。简记为“L.P.”,max(或min)z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn（=，）b1a21x1+a22x2+a2nxn（=，）b2am1x1+am2x2+amnxn（=，）bmx1,x2,xn0,.,13,（3）其他形式：,连加形式,.,14,向量形式,其中,称为价值行向量；,决策列向量,系数列向量,右端列向量,.,15,矩阵形式,其中,称为价值行向量；,决策列向量,右端列向量,约束矩阵或系数矩阵,.,16,1-3线性规划问题的标准形式,1、标准形式,或,.,17,2、条件,目标函数求极大值,约束条件全是等式（线性方程组）,决策变量全非负,右端常数全非负,.,18,3、标准化方法,（1）若目标函数求极小值，即,则令,转化为,.,19,（2）若约束条件为不等式，,则依次引入松弛变量或剩余变量（统称为松弛变量），转化为等式约束条件。,注意：松弛变量在目标函数中系数全为0。,约束为不等式，减去松弛变量，化为等式约束条件；约束为不等式，加上松弛变量，化为等式约束条件。,多退少补,例：maxz=2x1+3x2,2x1+2x212,4x116,5x215,x10，x20,s.t.,标准化,.,20,（3）若决策变量xj0，则令,（4）若决策变量xj取值无限制，则令,（5）若约束等式的右端常数bi0，则等式两边同时乘以“-1”。,其中,（“一分为二”）,.,21,例：将下列线性规划模型化为标准形式。,.,22,则问题化为标准形式：,并引入松弛变量x4,x5,.,23,1-4线性规划问题的解,已知线性规划的标准形式：,或,1、求解线性规划问题：,从满足（2）、（3）的方程组中找出一个解使目标函数（1）达到最大值。,.,24,2、可行解：,所有可行解的集合。,可行域：,满足约束条件（2）、（3）的解。记做,最优解：,使目标函数达到最大值的可行解。,.,25,（1）基：设A为线性规划问题约束条件的mn系数矩阵（m0，有如下结论：,(1)若对所有jm+1，有j0，则z（1）z（0），即z（0）为最优函数值，X（0）为唯一最优解；(2)若对所有jm+1，有j0，且存在某个非基变量的检验数k=0，则将Pk作为新的基向量得出新的基可行解X（1），满足z（1）=z（0），故z（1）也为最优函数值，从而X（1）也为最优解，X（0）、X（1）连线上所有点均为最优解，因此该线性规划模型具有无穷多最优解；(3)若存在某个j0，但对应的第j列系数全非正，即aij0，则当+时，有z（1）+，该线性规划模型具有无界解。,.,51,1.4单纯形法的计算步骤,1、前提：标准化的线性规划问题的系数矩阵含有单位子矩阵。,不妨假设A中前m列对应的子矩阵是单位矩阵，取其为基B，得到初始基可行解,.,52,m+3行,n+4列,第1行：价值行cj,第2行：变量行xj,最后一行：检验数行j,第1列：基价值列CB,第2列：基变量列XB,第3列：基解列b,最后一列：比值列,主体：系数矩阵Amn,2、单纯形表的结构,.,53,.,54,3、初始单纯形表：含初始基可行解的单纯形表,最优单纯形表：含最优解的单纯形表,4、单纯形法（SimplexMethod）：利用单纯形表求解线性规划问题的方法。,.,55,5、单纯形法的计算步骤,(1)化L.P.问题为标准形式,建立初始单纯形表；,(3)计算,以alk为主元素(简称主元，用表示)，进行线性方程组的初等行变换，将主元列Pk化为单位向量得到新的单纯形表，转入(2)。,（最大正检验数决定换入变量）,（最小比值决定换出变量）,.,56,例：用单纯形法求解下列线性规划问题.,maxz=2x1+3x2,2x1+2x212,4x116,5x215,x10，x20,s.t.,解：先标准化,.,57,再列初始单纯形表：,6,-,3,23000,.,58,以5为主元进行初等行变换,x1为换入变量,下面开始单纯形法迭代：,x5为换出变量,x2为换入变量,以2为主元进行初等行变换,x3为换出变量,主元化为1，主元列的其他元素化为0,.,59,此时得到唯一最优解X*=(3,3)T,Zmax=15。,.,60,6、单纯形法中存在的问题,（1）存在两个以上的最大正检验数。任取一个最大正检验数对应的变量作为换入变量。,（2）出现两个以上相同的最小值。任取一个最小对应的变量作为换出变量。此时L.P.问题出现退化现象。,.,61,练习用单纯形法求解下列线性规划问题,解：先标准化,.,62,.,63,1/3,-1/2,1/6,1/3,-1/3,3/4,12,.,64,唯一最优解,.,65,5-1人工变量法（大M法）,1.5单纯形法的进一步讨论,例：用单纯形法求解下列线性规划问题。,.,66,解：先标准化为,系数矩阵,但是A中没有单位矩阵，在A中人为的增加两列,此时,对应的约束方程组为：,该问题新增加了两个变量：x4,x5（称为人工变量）,A有单位子矩阵，选择这个单位矩阵作为基（称为人工基）。,.,67,为使,必须保证在可行解中人工变量x4=x5=0，故令x4，x5在目标函数中的系数为M（其中M表示任意大的正数），这种添加人工变量求解LP的方法称为人工变量法,计算过程中出现了M，这种方法也称为大M法。,等价于,.,68,于是，这个线性规划问题转化为：,以下可用单纯形法继续求解。,.,69,Cj,x1,x2,x3,x4,XB,b,CB,11-11012001,-2-30-M-M,34,x4x5,-M-M,cj-zj,-2+2M,-3+3M,-M,0,3/1=3,4/2=2,1/20-11-1/21/21001/2,x4x2,12,cj-zj,-1/2+M/20-M03/2-3M/2,-M-3,24,10-22-1011-11,x1x2,21,cj-zj,00-11-M1-M,-2-3,x5,0,唯一最优解,故zmin=7,注意：此时人工变量x4=x5=0,.,70,说明：若表中所有j0，但存在非0的人工变量，则该模型无可行解。,采用大M法求解线性规划模型时，如果模型中各个系数与M的值非常接近或相差很大，若用手工计算不会出现问题。但是若利用计算机求解，则容易引起混淆，使得机器判断出错，从而使大M法失效。在这种情况下，可采用下面的两阶段法进行计算。,.,71,5-2两阶段法(将L.P.问题分成两个阶段来考虑),第一阶段:判断原L.P.问题是否存在可行解。给原L.P.问题加入人工变量，并构造仅含人工变量的目标函数w（人工变量在w中的系数一般取为1）并求w的最小值；然后用单纯形法求解。若求得wmin=0，则该问题有可行解，进入第二阶段，否则该问题无可行解，结束。,第二阶段：将第一阶段得到的最终表去掉人工变量，并将目标函数还原为原L.P.问题的目标函数（即修改最终表中的第一行和第一列），以此作为第二阶段的初始表，继续用单纯形法求解。,.,72,例：用两阶段法求解下列线性规划问题。,标准化,引入人工变量,z,.,73,(1)第一阶段，构造判断是否存在可行解的模型：,用单纯形法求解这个问题，先标准化为；,.,74,Cj,x1,x2,x3,x4,XB,b,CB,11-11012001,000-1-1,34,x4x5,-1-1,cj-zj,2,3,-1,0,3/1=3,4/2=2,1/20-11-1/21/21001/2,x4x2,12,cj-zj,1/20-10-3/2,-10,24,10-22-1011-11,x1x2,21,cj-zj,000-1-1,00,x5,0,最优解,本问题有可行解，进入第二阶段,.,75,(2)第二阶段先在第一阶段的最终单纯形表去掉人工变量，再还原原目标函数，即maxz=-2x1-3x2+0 x3，继续迭代：,Cj,x1,x2,x3,XB,b,CB,10-2011,-2-30,21,x1x2,-2-3,cj-zj,0,0,-1,唯一最优解,故zmin=7,注意：两阶段法中不再出现大M，但需要解两个线性规划问题，要注意目标函数系数的变化。,.,76,5-3关于解的判别,用最终单纯形表判断线性规划问题解的类型：,.,77,已知线性规划问题形如：,5-4单纯形法计算的向量、矩阵描述,引入松弛变量xs,记X=(XB,XN,XS)T其中，XS为松弛变量，在初始表中是基变量；XB为最终表中基变量；XN表示既不是初始表的基变量又不是最终表的基变量。注意：XS和XB允许有公共变量。,（2）A=(B,N,I)B,N,I分别为XB、XN、XS在初始表中对应的矩阵。,则（1）C=(CB,CN,0)CB,CN,0分别为XB、XN、XS在目标函数中的系数。,（3）A=(I,N,B-1)I,N,B-1分别为XB、XN、XS在最终表中对应的矩阵。,.,78,约束方程组两端同时左乘B-1，则可得如下表达式：,初始单纯形表,最终单纯形表,.,79,用单纯形表表示如下：,XSb,BNI,XBbINB-1,初始表XBXNXS,cj-zj0,0NS=（-y1,-y2,-ym）=-YT,最终表XBXNXS,cj-zjBN0,0,比较得：b=B-1bN=B-1N或者Pj=B-1PjS=-CBB-1=-YTN=CN-CBB-1N=CN-YTN或者j=Cj-CBB-1Pj,其中B-1为初始表中基变量在最终表对应的系数矩阵，B为最终表中基变量在初始表对应的系数矩阵。,.,80,例：用单纯形法求解下列线性规划问题.,maxz=2x1+3x2,2x1+2x212,4x116,5x215,x10，x20,s.t.,解：先标准化,.,81,得到初始单纯形表：,6,-,3,23000,最终单纯形表：,X4010,X4010,可以验证：,.,82,根据上表可以列出初始单纯形表,5-5单纯形法小结,个数,取值限制,右端常数,约束方向,要求,系数,.,83,列初始表,.,84,1.7应用举例,一般而言，一个经济、管理问题要满足以下条件，才能建立线性规划模型：.需要求解问题的目标能用数值指标来反映，且能用线性函数来描述目标的要求；.为达到这个目标存在多种方案；.要求达到的目标是在一定条件下实现的，这些条件可用线性等式或不等式来描述。,.,85,（一）、混合配料问题,例：某糖果厂用原料A、