管理运筹学 全套课件-文档资料.ppt

,管理运筹学,数学的魅力与实质,数学的本质是处理抽象对象，是比语言更精炼、更严谨的符号系统。是人类理性的集中体现。数学的方法是建立一个牢不可破的公理体系，并以演绎推理的方法去构建和扩展整个学科体系。,应用,演绎方法,公理体系,数学大厦,数学的魅力与实质,数学方法在自然科学体系中无处不在，并取得了光辉的成就。19世纪以后，数学被广泛深入地应用于社会科学领域。经济学、管理学领域的许多大师具有高超的数学技能。,数学的魅力与实质,本门课程不仅要学习一门课程，一套方法，更重要的是要学会理性分析问题的方法。培养逻辑思维能力和抽象思维能力。数学在发展的过程中遇到过许多问题，而且也并非确切无疑，大家要敢于质疑，敢于提问题。,数学的魅力与实质,一个例子：S=1-1+1-1+1请问S等于多少？,数学的魅力与实质,至少有三种解法：1、S=（1-1）+（1-1）+（1-1）2、S=1+（-1+1）+（-1+1）3、1-S=1-(1-1+1-1)=1-1+1-1+1-1=S得到2S=1，从而S=1/2。,数学的魅力与实质,事实上，这是一个争论未定的题目，反映了人类对自然认识的不足。无穷的概念存在许多不足之处，而且并非绝对精确。不同的学派对无穷有着不同的认识。,考核方法,平时成绩占20%，每位同学的初始成绩都是60分（按100分为满分计算）。每次作业交上加1分，不交不加不减，拷贝别人作业一次扣2分。上课主动回答问题每次加2分。提出有价值问题或发现老师错误每次加5分。,运筹学的体系和发展历史,定义运筹学是一门应用于管理有组织系统的科学它为掌管这类系统的人提供决策目标和数量分析的工具运筹学应用分析、实验、量化的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理正式起源与二次世界大战，被称为Operationsresearch,日本人翻译为运做学，台湾人翻译为作业研究,运筹学的体系和发展历史,田忌赛马萌芽在20世纪初，Lanchester战斗方程。丹麦工程师爱尔朗研究电话通讯系统时提出了一些排队论的公式。30年代，数学家列温逊运用运筹思想分析商业广告、顾客心理。,运筹学的体系和发展历史,二次世界大战中，英美科学家研究如何有效运用雷达，研究船队遇到袭击如何减少损失，以及如何使用深水炸弹等紧迫问题。应用：德国潜艇被摧毁数增加到400%，船只中弹数由47%减少到29%。结果：打赢了空战和海战，保证了二次世界大战的最终胜利。,运筹学在现实生活中的例子,企业安排生产计划库存管理公交系统优化食堂窗口设置电脑游戏，帝国时代、魔兽争霸等。,运筹学的学科体系,规划论：包括线性规划、非线性规划、整数规划等。1947年，Danzig提出单纯形法，随后规划方法得到了广泛的应用。图论与网络分析：图是研究离散事物之间关系的一种分析模型。例：有甲、乙、丙、丁、戊、己6名同学参加ABCDEF六个项目的比赛，下表是各运动员报名参赛的项目，问6个项目顺序如何安排，作到每名运动员不连续参加两项比赛。,运筹学的学科体系,运筹学的学科体系,排队论：研究公共服务系统的运行与优化的数学理论方法。决策论：研究不确定情况以及风险情况下的决策。存储论：研究企业的库存计划，进货周期等。博弈论：研究竞争环境下决策者行为的数学方法。,运筹学的工作步骤,提出和形成问题：弄清问题的目标，可能的约束，问题的可控变量，相关参数等。建立模型：把问题中的可控变量、参数、目标、约束之间的关系用一定的模型表示出来。求解：用计算或实验方法求出问题的解。解的检验：检查求解过程，检查解能否反映现实问题。解的实施：将解运用到实际问题中。,第一章线性规划,本章内容,线性规划模型线性规划问题的图解法单纯形法非标准形线性规划的解法,线性规划模型,规划问题：就是否合理利用有限资源的问题。线性规划：线性的规划问题。两个意思：1、目标函数是线性的2、约束条件是线性的,线性规划模型,生产决策问题某汽车工厂生产大轿车和载重汽车两种型号的汽车,已知每辆汽车所用的钢材都是2吨/辆，该工厂每年供应的钢材为1600吨；工厂的生产能力是每2.5小时可生产一辆载重汽车，每5小时可生产一辆大轿车，工厂全年的有效工时为2500小时；已知供应给该厂大轿车用的座椅每年可装配400辆。据市场调查，出售一辆大轿车可获利4000元，出售一辆载重汽车可获利3000元。如何安排生产才能使工厂获利最大？,线性规划模型,建模型如下：设大轿车数量为x1,载重汽车数量为x2。,s.t.是subjectto的简写，表示受限制于。,线性规划模型,某工厂在计划期间内生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示：,已知、两种产品每单位分别可以获利50元、100元，问工厂应该如何安排生产才能使工厂获利最多。,线性规划模型,设置变量：生产产品x1个，产品x2个目标函数是利润最大化：资源是有限的，第一个限制是设备台时的限制：,线性规划模型,第二个限制是原材料A的限制：第三个限制是原材料B的限制：显然，产量不可能为负数：,线性规划模型,建模型如下：设生产产品x1件,产品x2件。,线性规划模型,（1），（2）分别被称为目标函数和约束条件。目标函数中变量的系数被称为价值系数，约束条件不等号右端称为资源向量或限定系数，约束条件左端变量的系数被称为技术系数。目标函数和约束条件都是一次幂函数，或称线性函数，因此这类规划问题被称为线性规划问题。,线性规划模型,例3：生产卷烟的主要原材料包括烟叶和烟梗。国家规定每千克焦油含量不超过15mg，烟气烟碱含量不超过1.4mg，现在知道每千克烟叶含焦油12mg，烟气烟碱1.5mg，烟梗含焦油18mg，烟气烟碱0.3mg，烟叶每千克50元，烟梗每千克20元，问如何搭配使生产成本最小。,线性规划模型,设每千克卷烟用烟叶x1千克，烟梗x2千克，模型如下：,这是目标函数一个求最小化的问题。,线性规划的标准形,为求解方便，一般线性规划都可以转化成如下标准形式：,要求,线性规划的标准形,目标函数为求最小化时，等式两端同乘以-1，变为求最大化。约束条件为=时，减一个剩余变量。资源变量为负数时，等式两端同乘以-1。变量为0即可。如果bk的变化使得B-1b+B-1b0，这时最优解的基就要发生变化，这种情况下用对偶单纯形法继续求出新的最优解。,资源向量的灵敏度分析,例：课本P6例1-1中，如果钢材的供应数量发生变化，请问1、钢材供应量在什么范围内变化时，最优基不会发生改变？2、当钢材的供应量增加到2200吨时，应当如何安排生产计划？,资源向量的灵敏度分析,如果例1-1中的钢材供应数量变为1600+b1，最终解将变为：xB=B-1b=B-1(b+b）=,资源向量的灵敏度分析,要保证最优基不改变，要求b中所有向量大于等于0，即：从（1）式中可得：b1-400，从（2）式中可得：b1-600，从（3）式中可得：b1400，得到-400b1400，也就是说，钢材供应量在1200到2000之间时，最优基不发生变化。,资源向量的灵敏度分析,资源向量在一定范围内变化时，最优基虽然不会发生变化，但最优解则会发生变化。最优基不变时，可以直接将发生变化的资源向量代入B-1b中，得到新的最优解的值。例如，当钢材供应量变为2000时，新的最优解的求解如下：,资源向量的灵敏度分析,资源向量的灵敏度分析,当钢材的供应量增加到2200吨时：资源向量出现负数，不再是可行解，需要继续迭代，用对偶单纯形法。,资源向量的灵敏度分析,最终单纯形表变为：,资源向量的灵敏度分析,以主元素为中心进行迭代运算：,趣味数学,一个富有的律师拥有11辆古董汽车，每辆值5000美元。律师死时留下了一个奇怪的遗嘱。他说他的11辆古董汽车分给他的三个儿子。把其中的一半分给长子，1/4分给次子，1/6分给小儿子。同时规定不能把车卖掉。律师去世后，儿子为了这个遗嘱争论不休，这时一个数学家开了一辆汽车来悼念老朋友。三个儿子把他们的难题告诉了数学家，数学家沉思片刻后说，我有办法了。请问，他该怎么分配这些汽车？,约束方程系数矩阵的灵敏度分析,从前边的分析中，我们知道，单纯形法的实质是找到一个能得到最优解的基xB，在约束条件中用其系数矩阵左乘一个B-1，同时令非基变量为0，得到最优解向量xB=B-1b。从而我们可以得到如下结论，最终单纯形表中xi的系数列向量pi事实上就是其初始系数列向量pi左乘以B-1，既pi=B-1pi。根据以上分析，我们可以得到约束方程技术系数变化时灵敏度分析的方法。,约束方程系数矩阵的灵敏度分析,例如，在例1-1中，列向量x4的系数列向量(用p4表示）在最终单纯形表中为（用p4表示）：,约束方程系数矩阵的灵敏度分析,根据以上分析我们可以得到系数矩阵灵敏度分析的思路。当基变量系数列向量改变时，用初始系数列向量左乘以B-1后代入原最终单纯形表，在新的单纯形表中继续进行运算，得到最优解。当新加入决策变量时，意味着约束方程组中增加了列向量，将这个列向量左乘以B-1后添加到原最终单纯形表中，继续运算得到最优解。,约束方程系数矩阵的灵敏度分析,在例1-1，为了增加安全性，当每辆大轿车使用钢材由2吨变为3吨时，求最优解有什么变化？工厂具备了生产旅行车的技术，每辆旅行车用钢材1.5吨，工时1.25小时，座椅0.25套，利润为每辆3千元，问该不该投产，如果投产有利可图，应该如何安排新的生产计划？,约束方程系数矩阵的灵敏度分析,当大轿车使用钢材变为3吨时，x1在最终单纯形表中的系数列向量变为：,约束方程系数矩阵的灵敏度分析,最终单纯形表变为：,约束方程系数矩阵的灵敏度分析,由于x1对应的列向量尚未化为单位向量，先进行迭代运算：,1800,约束方程系数矩阵的灵敏度分析,检验数仍然有负数，继续迭代：,约束方程系数矩阵的灵敏度分析,第二问，新增加一种产品，模型中增加了一个新列，设新产品产量为x6，增加的系数列向量在最终单纯形表中变为：,约束方程系数矩阵的灵敏度分析,最终单纯形表变为：,约束方程系数矩阵的灵敏度分析,检验数中存在负数，继续迭代：,约束方程系数矩阵的灵敏度分析,仍不是最优解，继续运算：,x1x2x3x4x5x6,xCj,zj,012000,zj-cj,430003,0210-2102.501-501-0.5-0.2501.50,b,442003,3200,约束方程系数矩阵的灵敏度分析,求得最优解为：x1=200，x2=0，x3=0，x4=500，x5=0，x6=800，Z=3200。可见，生产旅行车是有利可图的，新的生产方案为：生产大轿车200辆，生产旅行车800辆，剩余工时500小时，利润为3200千元。,灵敏度分析小结,价值系数发生变化时：1、如果是非基变量的系数发生变化，则只要该变量对应的检验数zj-cj在cj变化后仍然大于等于0，则最优解不发生任何变化。2、如果是基变量的价值系数发生变化，则需要重新计算所有检验数，如果所有检验数仍然保持大于等于0，则最优基不变，但最优解一般会发生变化。如果有检验数变为负数，则在原最终单纯形表中继续迭代，求出最优解。,灵敏度分析小结,当资源向量发生改变时，用公式xB=B-1b+B-1b=xB+B-1b（其中b=(0,0,bk,0)T）计算新的b列的值，如果新的b列的值仍然全部大于等于0，则最优基不变，但最优解的值一般会发生变化。如果计算出来的新的b列的值出现负数，则说明该解是不可行解，用对偶单纯形法继续进行迭代运算，求出新的最优解。,灵敏度分析小结,当基变量技术系数发生变化时，求出用公式pi=B-1pi求出发生变化的系数所在列的数值，代替最终单纯形表中原来的列。然后用高斯消元法将该列化为单位向量，计算新的检验数。1、如果检验数不为负数，则最优基不变。2、如果新的检验数变为负数，则最优基将发生变化，用单纯形法继续迭代，求出新的最优解。,趣味数学,你作为幸运观众参加了一个节目，节目中你面对三个门，其中一个门后一辆汽车，另外两个门后各有一只羊。主持人请你选择一扇门，门后的物品将做为你的奖品。当你选择后，主持人先不打开门，而是打开一扇门后有羊的门，然后问你改变不改变你的选择，请问，你该不该改变你的选择？,作业,某公司制作三种产品A、B、C，需要劳动力和原材料两种资源，要求制订生产计划使总利润最大化。三种产品所需的资源和产生的利润如下表所示：,作业,1、请建立模型，解决最优生产计划问题。2、求出使得最优解不变的产品A的单位利润变动范围，问A产品的利润变为2时最优解变不变？3、假定原材料的市场价格是10元每单位，可以购买15个单位，问以10元的价格采购15单位原材料是否合算？4、请问原材料的供应在什么范围内变化时，不必改变生产计划？,作业,5、厂家研制出了一种新产品D，生产一单位D需要劳动力4单位，原材料3单位，而每单位的新产品D的利润为3元。请问：生产计划是否需要修改？为什么？该如何修改？,第三章运输问题,主要内容,运输问题的背景运输问题的模型运输问题的表上作业法运输问题的应用,运输问题的背景,在经济建设中，经常碰到大宗物资调运问题，如煤炭、钢铁、粮食等等。主产区和主销区往往不同，需要大规模的调运，将物资从产地供应到销地。大型企业有多个生产基地，销售遍及全国乃至全世界，如何分配供应计划使经济效益最好。,运输问题模型,运输问题解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，且各地运输单价已知的前提下，如何确定一个使总的运输费用最小的方案。,运输问题模型,例1.某公司从两个产地A1,A2,将货物运往三个销地B1,B2,B3,各产地的产量、各销地的销量和各产地运往各销地的每件货物的运费如下表。问题：应如何调运，才能使得总运输费用最小？,运输问题模型,这是一个产销平衡的运输问题把A1，A2的产量全部分配给B1，B2，B3，,单位运价表,运输问题模型,设决策变量xij:产地Ai调运到Bj的运输量（i=1,2;j=1,2,3),产销平衡表,运输问题模型,线性规划模型,运输问题模型,一般线性规划模型Ai表示某种物资的第i个产地Bj表示某种物资的第j个销地si表示产地Ai的产量dj表示销地Bj的销量cij表示把物资从产地Ai运到销地Bj的单位运价决策变量xij表示产地Ai调运到销地Bj的运输量,运输问题模型,xj0,(i=1,2,m;j=1,2,n),运输问题模型,其他的运输问题模型产销平衡的运输问题:当时求目标函数最大的运输问题考虑利润最大、营业额最大具有能力限制的运输问题运输线路的能力限制产销不平衡的运输问题产大于销：假设销地销大于产：假设产地,运输问题模型,从模型中看，运输问题属于线性规划问题的一种。其特殊之处在于：约束条件系数矩阵全部为0-1元素，而且结构比较松散。系数矩阵中对应xij的系数向量，其分量中除第i个和第m+j个为1以外，其余的都为0。以例1的模型为例，考察其约束条件系数矩阵：,运输问题模型,表上作业法,表上作业法,表上作业法解决运输问题的单纯形法针对运输问题变量多，结构独特的特点，简化了运算假设问题为产销平衡的运输问题求解步骤1.找出初始的基可行解运输问题有m+n-1个基变量在（mn）产销平衡表上给出m+n-1个数字格其相应的调运量就是基变量，格子中填写的值为基变量的值,表上作业法,2.求各非基变量的检验数在表上计算除了m+n-1个数字格以外的空格的检验数判别是否达到最优解如已是最优解,则停止计算,否则转下步3.确定进基变量和出基变量找出新的基可行解在表上用闭回路法调整4.重复第2、3步骤，直至得到最优解,表上作业法,产销平衡表,B1B2BjBn产量限制,表上作业法,确定初始基可行解西北角法最小元素法西北角法从左上角的变量x11开始分配运输量，并使x11的取值尽可能大依次类推，直至给出全部方案为止例2.喜庆食品公司有三个生产面包的分厂A1,A2,A3,有四个销售公司B1,B2,B3,B4,其各分厂每日的产量、各销售公司每日的销量以及各分厂到各,表上作业法,销售公司的单位运价如下表。产量与销量的单位为吨，运价的单位为百元/吨。问该公司应如何调运产品在满足各销点需求量的前提下，使总运费最少？,表上作业法,可行方案为:x11=3,x12=4,x22=2,x23=2,x33=3,x34=6,minf=135,3,0,4,4,0,2,2,0,2,2,3,0,3,0,6,6,0,0,表上作业法,最小元素法西北角法是对西北角的变量分配运输量最小元素法是就近供应,对单位运价最小的变量分配运输量用最小元素法求的初始基可行解比西北角法的总运费要小通常迭代的次数可能会少,表上作业法,可行方案为:x13=4,x14=3,x21=3,x23=1,x32=6,x34=3,minf=86,3,0,1,1,4,0,4,0,6,3,0,3,3,0,3,3,0,0,表上作业法,注意当取定xij的值之后,会出现Ai的产量与Bj的销量都为零的情况,只能划去Ai行或Bj列,不能同时划去用最小元素法时,可能会出现只剩一行或一列的所有格均未填数或未划掉的情况,此时在这一行或这一列中除去已填上的数外均填上零,不能将空格划掉这样可保证填过数或行的格为m+n-1个,即基变量的个数为m+n-1个,表上作业法,最优解的判定检验已得到的运输方案是否为最优方案闭回路法位势法闭回路法闭回路的构成在已给出的调运方案的运输表上，从代表非基变量的一个空格出发沿水平或垂直方向前进，只有碰到代表基变量的有数字的格才能向左或右转直到回到出发的空格,表上作业法,1,x11为非基变量的闭回路,表上作业法,检验数的计算：从（A1，B1）出发，增加一单位调运量（从A1运到B1），为保持产销平衡，依次做调整：在（A1，B3）处减少1吨，（A2，B3）处增加1吨，（A2，B1）处减少1吨。调整方案使运费增加：1*3+（-1）*3+1*2+（-1）*1=1，可见这样调整将每单位增加运费1，将1填入（A1，B1）。,所有非基变量的闭回路及检验数,表上作业法,空格,闭回路,检验数,x11,x11-x13-x23-x21-x11,x12-x14-x34-x32-x12,x12,x22,x24,x31,x33,x22-x23-x13-x14-x34-x32-x22,x24-x23-x33-x14-x24,x31-x34-x14-x13-x23-x21-x31,x33-x34-x14-x13-x33,1,2,1,-1,10,12,表上作业法,闭回路法在以空格为始点和终点，其他顶点均为数字点的闭回路上将该空格的运输量调整为1，则其他顶点在保持供销平衡的基础上，运输量增加或减少1计算出该回路的总费用的变化值该变化值作为该非基变量的检验数若所有检验数都大于零，则原基可行解为最优解否则进一步迭代找出最优解用闭回路法求检验数要对每一个空格找一条闭回路当产销点多时，较繁杂,表上作业法,位势法将运输表上的每一行赋予值ui,每一列赋予值vjxij为基变量，则满足cij-ui-vj=0令u1=0，可先计算出ui和vj的值xij为非基变量，则利用ui和vj的值，计算出其检验数ij=cij-ui-vj若所有检验数ij均大于零，则原基可行解为最优解否则进一步迭代找出最优解,表上作业法,例1中检验数的计算：令u1=0，将基变量的检验数列出：由基变量x14，有c14(u1+v4)=0由基变量x13，有c13(u1+v3)=0由基变量x21，有c21(u2+v1)=0由基变量x23，有c23(u2+v3)=0由基变量x32，有c32(u3+v2)=0由基变量x34，有c34(u3+v4)=0,表上作业法,即：8(u1+v4)=0，5(u1+v3)=01(u2+v1)=0，4(u2+v3)=03(u3+v2)=0，10(u3+v4)=0又知u1=0，所以得到：u1=0，u2=-1，u3=-5，v1=2,v2=9,v3=3,v4=10。因非基变量的检验数ij=cij-ui-vj，已知所有ui、vj的值，可以在表格中计算所有非基变量的检验数。,表上作业法,表上作业法,改进运输方案的方法闭回路调整法选最小的负检验数，以它对应的非基变量为进基变量找出以该非基变量空格xij为出发点的闭回路尽量增加xij的运输量将该回路中的偶数顶点调运量的最小值取为xij的运输量将所有回路中的偶数顶点的调运量减去该值，而奇数顶点加上该值，得到新的调运方案,表上作业法,表上作业法,销地,产地,A14（+1）3（-1）7,A231（-1）（+1）4,销量3656,B1B2B3B4产量,A3639,表上作业法,调整后的运输方案如下,表上作业法,用位势法再计算出检验数如下表：所有检验数都大于零，最小费用为85元,表上作业法,如何找多个最优方案识别是否有最优方案的方法与单纯形法一样只需检查最优方案中是否存在非基变量的检验数为零将检验数为零的非基变量进入基，对运输方案进行调整，就可得到另一个最优方案见下例,表上作业法,由前面的表中可知：x11的检验数11=0令x11进入基，调整的运输方案为另一个最优方案,表上作业法,此时的最小运费仍为85,销地,产地,A1257,A2134,B1B2B3B4产量,A3639,销量3656,产销不平衡的运输问题,对于产大于销的运输问题，可以用增加一个虚拟销地的方法转化为产销平衡的运输问题，任何一个产地运往虚拟销地的运费均设为0。对于销大于产的运输问题，可以用增加一个虚拟产地的方法转化为产销平衡的运输问题，虚拟产地运往任何一个销地的运费均设为0。,产销不平衡的运输问题,例2：某产品的供求表如下，请给出最佳调运方案。,产销不平衡的运输问题,首先转化为产销平衡的运输问题：,产销不平衡的运输问题,用最小元素法求出初始可行解：,产销不平衡的运输问题,用位势法求出非基变量的检验数得：,产销不平衡的运输问题,检验数存在负数，用闭回路法调整：,产销不平衡的运输问题,调整后的运输方案为：,产销不平衡的运输问题,运输费用为：80最优方案为:x13=4,x15=3,x21=3,x23=1,x24=3，x32=6,x34=3。,产销不平衡的运输问题,思考题：产销不平衡的运输问题转化为产销平衡的运输问题后，虚拟产地运出的产品或运往虚拟销地的产品的单位运输费用均设为0，为什么？如果设为M行不行？设为任意数值行不行？为什么？,运输问题作业,1、求解运输问题：,B1B2B3产量（吨）,销地,运费单价,产地,A1201624300,A210108500,销量(吨)200400300,900,900,A3801810100,运输问题作业,1、求解运输问题：,B1B2B3产量,销地,运费单价,产地,A110163215,A21422407,销量12820,A322243416,第四章整数规划,主要内容,整数规划的特点整数规划的图解法整数规划的计算机解法整数规划的分枝定界法整数规划的应用,整数规划的特点,问题的提出在一般的线性规划中，最优解往往是分数或小数在许多实际问题中，要求全部或部分变量的取值必须是整数安排上班的人数裁剪钢材的根数生产机器的台数分类纯整数规划：所有变量为非负整数01规划：所有变量取值为0、1混合整数规划：部分变量为非负整数,整数规划的特点,求解方法四舍五入法或凑整法变量取值很大时，此方法得到的解与最优解差别不大但当问题规模较大时，计算工作量很大如,最优解为(4.6,5.5)；10个变量要比较次，最优解不一定在这些组合中,整数规划的特点,比较(4,3),(4,2),(3,3)不是可行解(3,2)是可行解,不是最优解z=13最优解(4,1),z=14,1,2,3,x1,1,2,3,0,2x1+3x2=14,x2,4,x1+0.5x2=4.5,4,5,6,7,5,6,7,8,9,(3.25,2.5),整数规划的特点,常用方法二变量的图解法分枝定界方法割平面法分配问题的匈牙利方法0-1型整数规划的隐枚举法,整数规划的特点,例1.有一份说明书,要分别翻译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各个的专长不同，所需时间如表所示。问应如何分配，使这四个人分别完成这四项任务总的时间最小？,人,工作,英文,日文,德文,俄文,甲乙丙丁,21097,154148,13141611,415139,整数规划的特点,引入0-1逻辑变量,整数规划的图解法,基本思想在可行域中寻找使目标值达到最大的整数解不使用四舍五入或截尾取整法例2.某公司拟用集装箱托运甲、乙两种货物，每件货物的体积、重量、利润及托运限制如下表,体积（立方英尺）,利润（百元）,甲,乙,托运限制,195,273,1365（立方英尺）,4,40,140（百千克）,2,3,货物,重量（百千克）,整数规划的图解法,甲种货物至多托运4件，问两种货物各托运多少件可使获利最大？这是一个整数规划问题模型为maxz=2x1+3x2195x1+273x213654x1+40 x2140 x14x1，x20，且为整数,整数规划的图解法,用图解法解该整数规划问题,2x1+3x2=14,1,2,3,x1,1,2,3,x2,4,4,2x1+3x2=6,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,2x1+3x2=14.66,该问题的线性规划的最优解为x1=2.44,x2=3.26,目标函数的最优值为14.66该解不是整数规划的可行解平移目标函数等直线,相交于整数规划的可行点x1=2,x2=4,目标函数的最优值为14,*,整数规划的图解法,用四舍五入或截尾法得到的线性规划的整数解不是整数规划的最优解或可行解如,x1=2,x2=3,目标函数值为13,不是最优解x1=3,x2=3,或x1=2,x2=4;x1=3,x2=4,都不是整数规划的可行解性质整数规划的最大目标值不会超过线性规划的最大目标值即整数规划的最小目标值不会小于线性规划的最小目标值,分枝定界法,意义和作用求解整数线性规划的有效方法既能解决纯整数规划,又能解决混合整数规划大多数软件都是基于该方法实施思路先求出相应线性规划的最优解定界:若该解不符合整数条件,求出整数规划的上下界分枝:把线性规划的可行域分成子区域，再求解这些子区域上的线性规划问题不断缩小整数规划上下界的距离,最后求出最优解,分枝定界法,分枝定界过程不断缩小最优目标函数值的上界和下界的距离通过分枝使得上界越来越小，而下界越来越大最优解的存在性当时，整数规划的最优解已求出即，最优解为其目标值取此下界的对应的线性规划的整数可行解,分枝定界法,例3.用分枝定界方法求解例2.的整数规划,maxz=2x1+3x2195x1+273x213654x1+40 x2140 x14x1，x20，且为整数,分枝定界法,先求出相应的线性规划1的解线性规划1.,maxz=2x1+3x2195x1+273x213654x1+40 x2140 x14x1，x20,分枝定界法,最优解为x1=2.44,x2=3.26目标函数的最优值为z1=14.66x1=2.44,x2=3.26不是整数规划的最优解确定整数规划最优目标值的初始上界和下界由性质1.知,用观察法求出该整数规划的一个可行解,将其目标值作为用截尾法对线性规划的最优解进行处理得到x1=2,x2=3是整数规划的可行解令其目标值为,即,分枝定界法,分枝:将线性规划1分为两枝任取x1=2.44,x2=3.26中的一个或选取最远离整数的那一个,如,x1=2.44如x1取整数,则可在x12或x13中取值将线性规划1分成两枝:线性规划2和线性规划3,maxz=2x1+3x2195x1+273x213654x1+40 x2140 x14x12x1，x20,maxz=2x1+3x2195x1+273x213654x1+40 x2140 x14x13x1，x20,分枝定界法,求解线性规划2最优解为x1=2,x2=3.30目标函数的最优值为z2=13.90,maxz=2x1+3x2195x1+273x213654x1+40 x2140 x14x12x1，x20,分枝定界法,求解线性规划3最优解为x1=3,x2=2.86目标函数的最优值为z3=14.58,maxz=2x1+3x2195x1+273x213654x1+40 x2140 x14x13x1，x20,分枝定界法,修改整数规划最优目标值的上界和下界将,修改为定下界:用截尾法分别求出线性规划2和3的整数规划的可行解x1=2,x2=3,和x1=3,x2=2其目标值分别为13和12令在线性规划2和3中,选择上界最大的线性规划3进行分枝线性规划3的最优解为x1=3,x2=2.86将x2=2.86分成x22和x23两种情况将线性规划3分成两枝:线性规划4和线性规划5,分枝定界法,求解线性规划4最优解为x1=4,x2=2目标函数的最优值为z4=14,maxz=2x1+3x2195x1+273x213654x1+40 x2140 x14x13x22x1，x20,分枝定界法,求解线性规划5无可行解,maxz=2x1+3x2195x1+273x213654x1+40 x2140 x14x13x23x1，x20,分枝定界法,进一步修改整数规划最优目标值的上界和下界将的值修改为线性规划2的整数可行解为x1=2,x2=3,目标值为13线性规划4的整数可行解为,目标值为14令此时,且线性规划4的目标值为14,最优解为x1=4,x2=2,分枝定界法,线性规划1z1=14.66x1=2.44,x2=3.26,线性规划2z2=13.90 x1=2x2=3.30,x12,线性规划3z3=14.58x1=3x2=2.86,x13,线性规划4z4=14x1=4x2=2,线性规划5无可行解,x22,x23,分枝定界法,求解步骤第一步：求解问题BB没有可行解，则A也没有可行解，求解过程停止B有最优解，且符合A的整数条件，则B的最优解即为A的最优解B有最优解，但不符合A的整数条件，记其目标值为z1,A,B,整数规划问题,线性规划问题,分枝定界法,第二步：确定A的最优目标值的上、下界上界用观察法找出A的一个整数可行解，其目标值作为的下界第三步：最优性判断如果，则终止，否则，转下步第四步：构造分枝条件在B的最优解中选一个最远离整数要求的变量，设为xj=bj,令bj为bj的下整数两个约束条件为,分枝定界法,第五步：求解分枝B1、B2修改问题A的最优目标值的上、下界取B1、B2最优目标值的最大值为新的上界的值用观察法求出B1、B2问题中的各一个整数解，选其中最大的为新的下界的值第六步：比较与剪枝将各分枝最优目标值中小于的分枝剪去返回第三步,整数规划的应用,分配或指派问题(Assignmentproblem)问题现有n项任务分配给n个人去完成,并指定每人完成其中的一项,每项只交给一个人去完成,应任何分配使总的效率为最高模型引入0-1逻辑变量,整数规划的应用,第五章图与网络模型,主要内容,引言图与网络的基本概念最短路问题最小树问题中国邮递员问题最大流问题最小费用最大流问题,引言,起源18世纪，多数问题围绕着游戏而产生1736年，欧拉解决了有名的哥尼斯堡七桥问题一笔画问题,引言,一笔画问题,引言,著名的问题Hamilton问题1859年，Hamilton发明了一种游戏在一个实心的12面体的20个顶点上标上世界上有名的城市的名字要求游戏者从某一城市出发，遍及各城市一次且仅一次，最后回到出发点,引言,四色猜想问题在一个平面或球面上的任何地图上只能用四种颜色着色使得任何两个相邻的国家都具有不同的颜色两个国家相邻是指具有一段公共的边界1976年，三位美国人，用1200个小时证明了该猜想，但不理想,引言,基尔霍夫用图代替电网络并发展了树的理论凯莱应用图论解决了化学的分子结构问题中国邮递员问题发展阶段第一阶段：18世纪中叶19世纪中叶图论的萌芽时期第二阶段：19世纪中叶20世纪中叶图论的大量问题出现第三阶段：20世纪中叶以后飞速发展时期,基本概念,图（无向图）表明研究对象和这些对象之间的相互联系用点表示研究对象，记为V用边表示研究对象之间的相互关系，记为E图可用点边的集合表示为G=（V，E）有向图表明从点v1到v2之间的关系可用弧表示D=（V，A）如，家谱图,基本概念,链无向图G中点边交错的序列(v1,e1,v2,e2,vk,ekvk+1)vivj,ei=vi,vi+1圈在一条链中.若v1=vk+1连通图若图G中任意两个不同点之间至少存在一条链,基本概念,路有向图D中点边交错的序列(v1,a1,v2,a2,vk,akvk+1)aiaj,ai=vi,vi+1回路v1=vk+1的路赋权图无向图G中的每一条边对应了一个数值wij有向图D中的每一条弧对应了一个数值cij,v1,v2,v5,v4,v3,a1,a7,a2,a3,a4,a5,a6,基本概念,网络赋权图D中,指定发点、收点。其余点为中间点赋权数cij为容量,最短路问题,最短路问题在一个赋权的有向图D(或无向图）中找到一条从点vs到vt的路，使得这条路上所有弧（边）的权数的总和最小Dijkstra算法适用于cij0的情况双标号法对图中的点vj赋予两个标号（lj，kj）lj表示从起点vs到点vj的最短路的长度Kj表示在vs到点vj的最短路上vj前面一个邻点的下标,最短路问题,算法基本步骤对始点vs赋予标号(0,s)表示从v1到v1的距离为0,v1为起点找出已标号的点的集合I，未标号的点的集合J及弧集合H=(vi,vj)/viI,vjJ若H为空集，则算法结束。若vt已标号(lt,kt),则vs到vt的最短路的长度为lt,可从标号kt反向追踪到起点vs得到最短路若vt未标号，则不存在从vs到vt的最短路若H不为空集，则转下步。对任意的(vi,vj)H，计算sij=li+cij,最短路问题,令scd=minsij,给该弧标号(scd,c),返回步骤2例1.求出下图的从v1到v6的最短路,v1,v2,v3,v4,v5,v6,3,5,2,7,2,5,1,5,3,1,(0,s),(2,1),I,(3,1),(3,3),(8,4),最短路问题,例2.电信公司准备在甲、乙两地沿路假设一条光缆线，问如何架设使其光缆线路最短？（甲(v1)、乙(v2)两地交通图）,(0,s),(10,1),(13,3),(14,3),(18,5),(16,5),(22,6),最短路问题,最短路应用例2.设备更新问题某公司使用一台设备，在每年年初公司都要决定是购买新设备还是继续使用旧设备。若购买新设备就要支付一定的购置费，但维修费低。若继续使用旧设备可省去购置费，但维修费高。现在需制定一个五年的设备更新计划，使得五年内购置费和维修费总的支付费用最小。该设备每年年初的价格及使用不同时间（年）的设备维修费如下表所示。,最短路问题,最短路问题,把该问题转化为最短路问题设vi表示第i年初购进一台新设备，i=1,2,3,4,5v6表示第5年底弧(vi,vj)表示在第i年年初购进的设备一直使用到第j年初，即，第j-1年年底,v1,v2,v3,v4,v5,v6,59,41,30,22,16,16,17,17,18,22,30,41,23,31,23,最小生成树问题,问题的背景通讯网络的优化设计几个城市之间需架设通讯网络，已知每两个城市之间的距离为wij，试设计一个架设方案使得任两个城市之间可通话总的架设线路最短铁路网络的优化设计几个城市之间需铺设铁路，已知每两个城市之间铺设的费用为wij，试设计一个铺设方案使得任两个城市之间可通火车总的铺设费用最少,最小生成树问题,树一个无圈连通图n个顶点的树具有n-1条边在树图上任加一条边就会构成圈,v3,v2,v4,最小生成树问题,图G的生成子图G1G=（V，E），若G1=(V,E1),且E1E图G的生成树(支撑树)T1若图G的生成子图T1是树最小生成树问题在一个赋权的连通无向图G中找出一个生成树,并使得该生成树的所有边的权树之和最小求最小生成树的方法破圈法避圈法,最小生成树问题,破圈法在给定的连通图中任找一圈在该圈中去掉一条权最大的边,直至该图中无圈为止避圈法在给定的连通图中,先选出一条权最小的边在未选边中选出与已选边不构成圈的最小边直至达到顶点数减一条边为止,最小生成树问题,某大学准备对其所属的7个学院办公室计算机联网，如图所示。设计一个网络联通7个办公室，使总的线路长度最短。,v3,中国邮递员问题,问题现有一名邮递员从邮局出发,走遍所管辖的街区至少一次,返回邮局1962年,管梅谷提出欧拉圈与欧拉图在一个连通图中,若存在一个圈,经过每边一次仅一次,则称该圈为欧拉圈含有欧拉圈的图成为欧拉图连通图是欧拉图图中的点全为偶点,最大流问题,许多系统包含了最大流问题公路系统的车辆流通讯系统的信息流供水系统的水流金融系统的现金流最大流问题给定了一个带收发点的网络，在不超过每条弧容量的前提下，求出从发点到收点的最大流量通常只研究一个收点和发点的情况,最大流问题,多个收点和发点的网络虚设一个总发点和一个收点将其分别与各收点和发点连起来转化为只含一个发点和收点的情况,最大流问题,流流：加在网络各条弧上的一组负载量弧(vi,vj)上的流记为fij可行流容量限制：对所有的弧中间点平衡条件：以v(f)表示网络从st流量，有任何网络一定存在可行流，因为零流为可行流,最大流问题,增广链存在收点到发点的一条链在前向弧（指向为st)上,存在在后向弧（指向为ts)上,存在当增广链存在时，令,最大流问题,令显然仍是一个可行流与可行流f相比，