运筹学胡运权第五版课件分析.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,运 筹,学,(,Operations Research,),一、古代朴素的运筹学思想,例如：田忌赛马,二、运筹学的起源,国外,英文原名,Operations Research,简称,“,O.R.”,直译为：运用研究或作业研究,正式出现于,1938,年,7,月英国一份关于防空作战系统运行的研究报告中,绪 论,国内,1956,年成立第一个运筹学小组,1957,年从,“,夫运筹策帷幄之中，决胜于千里之外,”,中摘取,“,运筹,”,二字，将,O.R.,正式翻译为,“,运筹学,”,三、运筹学的定义,研究工具：数学，计算机科学及其他相关科学,研究目的：对有限资源进行合理规划、使用，并提供,优化决策方案。,研究对象：复杂系统的组织和管理,参考,大英百科全书,、,辞海,、,中国企业管理百科全书,等。,四、运筹学研究的基本特点,系统的整体优化,多学科的配合,模型方法的应用,五、运筹学研究的基本步骤,分析与表述问题,建立数学模型,对问题求解,对模型和模型导出的解进行检验,建立对解的有效控制,方案的实施,第一章 线性规划及单纯形法,Linear Programming and Simplex Method,x,a,此为无约束的极值问题,1.1,一般线性规划问题的数学模型,1-1,问题的提出,例,1,用一块边长为,a,的正方形铁皮做一个无盖长方体容器，应如何裁剪可使做成的容器的容积最大？,例,2,常山机器厂生产,I,、,II,两型产品。这两型产品都分别要在,A,、,B,、,C,三种不同设备上加工。按工艺规定，生产每件产品,I,需占用各设备分别为,2h,、,4h,、,0h,，生产每件产品,II,需占用各设备分别为,2h,、,0h,、,5h,。己知各设备计划期内用于生产这两种产品的能力分别为,12h,、,16h,、,15h,，又知每生产一件产品,I,企业能获利,2,元利润，每生产一件产品,II,企业能获利,3,元利润，问该企业应安排生产两种产品各多少件，使总的利润收入为最大。,1-2,线性规划问题的数学模型,原型,模型,数学模型,提炼,数学工具,1,、,原型,：现实世界中人们关心、研究的实际对象。,模型,：将某一部分信息简缩、提炼而构造的原型替代物。,数学模型,：对现实世界的一个特定对象，为达到一定目的，根据内在规律做出必要的简化假设,并运用适当数学工具得到的一个数学结构。,3,、规划问题数学模型的三要素,（,2,）,目标函数,：问题要达到的目标要求，表示为决策变量的函数。用,z,=,f,(,x,1,，,x,2,，,，,x,n,),表示。,（,1,）,决策变量,：决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。用,x,1,，,x,2,，,，,x,n,表示。,（,3,）,约束条件,：决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。,2,、规划问题,即求目标函数在若干约束条件下的最值。,4,、线性规划问题（,Linear Programming,）的数学模型,（,2,）,一般形式,：,（,1,）,条件,：决策变量为可控的连续变量，目标函数和约束条件都是线性的。简记为,“,L.P.”,max,(,或,min,)z=c,1,x,1,+c,2,x,2,+,+,c,n,x,n,s.t,.,a,11,x,1,+a,12,x,2,+a,1n,x,n,（,=,，,）,b,1,a,21,x,1,+a,22,x,2,+a,2n,x,n,（,=,，,）,b,2,a,m1,x,1,+a,m2,x,2,+,a,mn,x,n,（,=,，,）,b,m,x,1,x,2,x,n,0,（,3,）,其他形式,：,连加形式,1-3,线性规划问题的标准形式,1,、标准形式,或,2,、条件,目标函数求极大值,约束条件全是等式（线性方程组）,决策变量全非负,右端常数全非负,3,、标准化方法,（,1,）若目标函数求极小值，即,则令,转化为,（,2,）若约束条件为不等式，,则依次引入松弛变量或剩余变量（统称为松弛变量），,转化为等式约束条件。,注意,：松弛变量在目标函数中系数全为,0,。,约束为不等式，减去松弛变量，化为等式约束条件；,约束为不等式，加上松弛变量，化为等式约束条件。,多退少补,例：,max,z,=2,x,1,+3,x,2,2,x,1,+2,x,2,12,4,x,1,16,5,x,2,15,x,1,0,，,x,2,0,s.t,.,标准化,（,3,）若决策变量,x,j,0,，则令,（,4,）若决策变量,x,j,取值无限制，则令,（,5,）若约束等式的右端常数,b,i,0,，则,其中,（“一分为二”）,等式两边同时乘以“,-1”,。,例,3,：,将下列线性规划模型化为标准形式。,例,4,：在下述线性规划问题中，列出全部基、基解、基可行解，并指出最优解。,解：系数矩阵为,若取基为,B=(P,1,P,2,P,3,),则基变量为,x,1,x,2,x,3,非基变量为,x,4,x,5,令,x,4,=x,5,=0,，代入约束方程组,解得,x,1,=4,x,2,=3,x,3,=-2,从而得到一个基解,X,=(4,3,-2,0,0),T,这个基解不是基可行解！,该,L.P.,共有,8,个基解。,若取基为,B=(P,3,P,4,P,5,)=I,3,则基变量为,x,3,x,4,x,5,非基变量为,x,1,x,2,令,x,1,=x,2,=0,，代入约束方程组,从而得到一个基解,X,=(0,0,12,16,15),T,这个基解是基可行解！,（注意：选择单位矩阵为基可以较方便的求出一个基可行解。）,同理可得其他基解,.,基,B,基解,是基可行解？,目标函数值,x,1,x,2,x,3,x,4,x,5,P,1,P,2,P,3,4,3,-2,0,0,否,17,P,1,P,2,P,4,3,3,0,4,0,是,15,P,1,P,2,P,5,4,2,0,0,5,是,14,P,1,P,3,P,5,4,0,4,0,15,是,8,P,1,P,4,P,5,6,0,0,-8,15,否,12,P,2,P,3,P,4,0,3,6,16,0,是,9,P,2,P,4,P,5,0,6,0,16,-15,否,18,P,3,P,4,P,5,0,0,12,16,15,是,0,（最优基）,（最优解）,（最优目标函数值）,4,、线性规划问题各种解之间的关系,约束方程的,解空间,基解,可行解,非可行解,基可行解,最优解,1.2,图解法,1,、适用范围：仅含两个决策变量的,L.P.,2,、步骤：,（,1,）作平面直角坐标系，标上刻度；,（,2,）作出约束方程所在直线，确定可行域；,（,3,）作出一组目标函数的等值线，判定优化方向；,（,4,）沿优化方向移动，确定与可行域相切的点，确定最优解，并计算最优目标函数值。,例：用图解法求解下列线性规划问题。,（,1,）,max z=2x,1,+3x,2,s.t,.2x,1,+2x,2,12 -,4x,1,16 -,5x,2,15 -,x,1,0,x,2,0,x,1,x,2,2,2,4,6,8,4,6,0,2,x,1,+2,x,2,=,12,5,x,2,=,15,4,x,1,=,16,Z=6,Z=0,A(3,3),Z,max,有,唯一最优解,，,当,x,1,=x,2,=,3,时，,Z,max,=15,C(4,0),D(0,3),(0,0),B(4,2),顶点,基可行解,A,（,3,3,）,（,3,3,0,4,0,）,B,（,4,2,）,（,4,2,0,0,5,）,C,（,4,0,）,（,4,0,4,0,15,）,D,（,0,3,）,（,0,3,6,16,0,）,O,（,0,0,）,（,0,0,12,16,15,）,一一对应,（,2,）,（,3,）,无穷多最优解,无界解,x,1,x,1,x,2,x,2,x,1,x,2,无可行解,（,4,）,3,、线性规划问题解的类型,（,1,）唯一最优解：只有一个解为最优解,（,2,）无穷多最优解：有无穷多个解为最优解,（,3,）无界解：目标函数的取值无界,（,4,）无可行解：可行域为空集，即存在互相矛盾的约束条件。,4,、可行域的特征,（,1,）若,L.P.,的可行域不是空集，则可行域为凸集。,（,2,）若,L.P.,有最优解，则一定可以在可行域的顶点上找到最优解。,（,3,）,L.P.,的顶点与基可行解一一对应。,3-1,预备知识：凸集与顶点,1.3,单纯形法,（,Simplex Method,）,原理,（,1,）凸集：对于集合,C,中任意两点连线段上的点，若全在,C,内，则称集合,C,为凸集。,直观特征：图形从内部向外部凸出。,凸集,非凸集,（,2,）顶点：凸集中不在任意两点的连线段内部的点。,X,1,X,4,X,3,X,5,X,2,单纯形法的计算步骤：,初始基可行解,使目标函数值增大的新的基可行解,是否最优解？,结束,是,否,1.4,单纯形法的计算步骤,1,、前提：标准化的线性规划问题的系数矩阵含有单位子矩阵。,不妨假设,A,中前,m,列对应的子矩阵是单位矩阵，取其为基,B,，得到初始基可行解,m+,3,行,n+,4,列,第,1,行：价值行,c,j,第,2,行：变量行,x,j,最后一,行：检验数行,j,第,1,列：基价值列,C,B,第,2,列,：基变量列,X,B,第,3,列,：基解列,b,最后一,列：,比值,列,主体：系数矩阵,A,m,n,2,、单纯形表的结构,例,5,：用单纯形法求解下列线性规划问题,.,max,z,=2,x,1,+3,x,2,2,x,1,+2,x,2,12,4,x,1,16,5,x,2,15,x,1,0,，,x,2,0,s.t,.,解：先标准化,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,0,X,3,0,X,4,0,X,5,12,16,15,2 2 1 0 0,4 0 0 1 0,0 5 0 0 1,再列初始单纯形表：,6,-,3,2 3 0 0 0,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,0,X,3,0,X,4,0,X,5,12,16,15,2 2 1 0 0 6,4 0 0 1 0 -,0 5 0 0 1 3,2 3 0 0 0,以,5,为主元进行初等行变换,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,0,X,3,0,X,4,3,X,2,6,16,3,2 0 1 0 -2/5 3,4 0 0 1 0 4,0 1 0 0 1/5 -,2 0 0 0 -3/5,x,1,为换入变量,下面开始单纯形法迭代：,x,5,为换出变量,x,2,为换入变量,以,2,为主元进行初等行变换,x,3,为换出变量,主元化为,1,，主元列的其他元素化为,0,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,2,X,1,0,X,4,3,X,2,3,4,3,1 0,0 -1/5,0 0 -2 1 4/5,0 1 0 0 1/5,0 0 -1 0 -1/5,此时得到唯一最优解,X,*,=(3,3),T,Z,max,=15,。,6,、单纯形法中存在的问题,（,1,）存在两个以上的最大正检验数。,任取一个最大正检验数对应的变量作为换入变量。,（,2,）,出现两个以上相同的最小值。,任取一个最小,对应的变量作为换出变量。,此时,L.P.,问题出现退化现象。,(1),当所有,j,0,，表示有,唯一最优解,；,(2),当所有,j,0,，且,存在某个非基变量的检验数,k,=,0,，则该线性规划模型具有,无穷多最优解,；,(3),若存在某个,j,0,，但对应的第,j,列系数全非正，即,a,ij,0,，则线性规划模型具有,无界解,。,3-5,解的判别,练习 用单纯形法求解下列线性规划问题,解：先标准化,2 1 0 0,5,4,x,3,x,4,0,0,x,1,x,2,x,3,x,4,b,x,B,c,B,2 1 0 0,c,j,24,15,3,5,1,0,6,2,0,1,0 0,x,3,x,1,0,2,x,1,x,2,x,3,x,4,b,x,B,c,B,2 1 0 0,c,j,4,3,0,1,4,1,0,1/3,-1/2,1/6,1/3,-1/3,3/4,12,0 0 -1/12 -7/24,x,2,x,1,1,2,x,1,x,2,x,3,x,4,b,x,B,c,B,2 1 0 0,c,j,15/4,3/4,0,1,1/4,-1/8,1,0,-1/12,5/24,唯一最优解,5-1,人工变量法（大,M,法）,1.5,单纯形法的进一步讨论,例,6,：用单纯形法求解下列线性规划问题。,说明：,若表中所有,j,0,，但存在非,0,的人工变量，则该模型,无可行解,。,采用大,M,法求解线性规划模型时，如果模型中各个系数与,M,的值非常接近或相差很大，若用手工计算不会出现问题。但是若利用计算机求解，则容易引起混淆，使得机器判断出错，从而使大,M,法失效。,在这种情况下，可采用下面的两阶段法进行计算。,5-2,两阶段法,(,将,L.P.,问题分成两个阶段来考虑,),第一阶段,:,判断原,L.P.,问题是否存在可行解。,给原,L.P.,问题加入人工变量，并构造仅含人工变量的目标函数,w,（,人工变量在,w,中的系数一般取为,1,）并求,w,的最小值；然后用单纯形法求解。若求得,w,min,=0,，则该问题有可行解，进入第二阶段，否则该问题无可行解，结束。,第二阶段：将第,一,阶段得到的最终表去掉人工变量，并将目标函数还原为原,L.P.,问题的目标函数（即修改最终表中的第一行和第一列），以此作为第二阶段的初始表，继续用单纯形法求解。,例：用两阶段法求解下列线性规划问题。,标准化,引入人工变量,z,(1),第一阶段，构造判断是否存在可行解的模型：,用单纯形法求解这个问题，先标准化为；,C,j,x,1,x,2,x,3,x,4,X,B,b,C,B,1 1 -1 1 0 1 2 0 0 1,0 0 0 -,1,-,1,34,x,4,x,5,-,1,-1,c,j,-,z,j,2,3,-1,0,3/1=3,4/2=2,1/2 0 -1 1 -1/2 1/2 1 0 0 1/2,x,4,x,2,12,c,j,-,z,j,1/2,0,-1,0,-3/2,-1,0,24,1 0 -2 2 -1 0 1 1 -1 1,x,1,x,2,21,c,j,-,z,j,0 0 0 -1,-1,0 0,x,5,0,最优解,本问题有可行解，进入第二阶段,(2),第二阶段,先在第一阶段的最终单纯形表去掉人工变量，再还原原目标函数，即,max z,=-2,x,1,-3,x,2,+0,x,3,，,继续迭代：,C,j,x,1,x,2,x,3,X,B,b,C,B,1 0 -2 0 1 1,-2 -3 0,21,x,1,x,2,-2,-3,c,j,-,z,j,0,0,-1,唯一最优解,故,z,min,=,7,注意：两阶段法中不再出现大,M,，但需要解两个线性规划问题，要注意目标函数系数的变化。,5-3,关于解的判别,用最终单纯形表判断线性规划问题解的类型：,解的类型,最终表的特征,无可行解,有非,0,的人工变量,有,可,行,解,唯一最优解,无,非,0,的人,工变量，非基变量的检验数全为负数,无穷多最优解,无非,0,的人工,变量，非基变量的检验数全非正，且有某个非基变量的检验数为,0,无界解,无非,0,的,人工变量，有某个非基变量的检验数为正数，但该变量对应的系数全为非正数,例：用单纯形法求解下列线性规划问题,.,max,z,=2,x,1,+3,x,2,2,x,1,+2,x,2,12,4,x,1,16,5,x,2,15,x,1,0,，,x,2,0,s.t,.,解：先标准化,5-4,单纯形法计算的向量、矩阵描述,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,0,X,3,0,X,4,0,X,5,12,16,15,2 2 1 0 0,4 0 0 1 0,0 5 0 0 1,得到初始单纯形表：,6,-,3,2 3 0 0 0,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,2,X,1,0,X,4,3,X,2,3,4,3,1 0,0 -1/5,0 0 -2 1 4/5,0 1 0 0 1/5,0 0 -1 0 -1/5,最终单纯形表：,X,4,0,1,0,X,4,0,1,0,可以验证：,三要素,决策变量,约束条件,目标函数,两,个,三个,以上,x,j,0,x,j,无,约束,x,j,0,b,i,0,b,i,0,=,maxZ,minZ,x,s,x,a,标准化,图解法、,单纯形法,单纯形法,不,处,理,令,x,j,=,x,j,-,x,j,x,j,0,x,j,0,令,x,j,=-,x,j,不,处,理,约束条件两端同乘以,-1,加松弛变量,x,s,加人工变量,x,a,减,去,x,s,加入,x,a,不,处,理,令,z,=-,Z,0,-M,根据上表可以列出初始单纯形表,5-5,单纯形法小结,个数,取值限制,右端常数,约束方向,要求,系数,列初始表,1.7,应用举例,一般而言，一个经济、管理问题要满足以下条件，才能建立线性规划模型：,.,需要求解问题的目标能用数值指标来反映，且能用线性函数来描述目标的要求；,.,为达到这个目标存在多种方案；,.,要求达到的目标是在一定条件下实现的，这些条件可用线性等式或不等式来描述。,（一）、混合配料问题,例：某糖果厂用原料,A,、,B,、,C,加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中各种原料的含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费用及售价如下表所示。问该厂每月生产这三种牌号糖果各多少千克，能使该厂获利最大。请建立这个问题的线性规划模型。,甲,乙,丙,原料成本（元,/kg,）,每月限制用量（,kg,）,A,B,C,60,20,30,50,60,2.00,1.50,1.00,2000,2500,1200,加工费（元,/kg,）,0.50,0.40,0.30,售价（元,/kg,）,3.40,2.85,2.25,解：,用,i,=1,2,3,表示原料,A,、,B,、,C,；,用,j,=1,2,3,表示糖果甲、乙、丙；,设,x,ij,为生产第,j,种糖果使用的第,i,种原料的质量，,则该问题的数学模型为：,s.t,.,原料供应限制,含量要求条件,用单纯形法求得：,即每月生产甲糖果,kg,，乙糖果,kg,，不生产丙糖果，可获得最大利润为,5450,元。,（二）、投资项目组合问题,例：兴安公司有一笔,30,万元的资金，考虑今后三年内用于下列项目的投资：,1,、三年内每年年初均可投资，每年获利为投资额的,20%,，其本利可一起用于下一年投资；,2,、只允许第一年初投入，于第二年末收回，本利合计为投资额的,150%,但此类投资限额不超过,15,万元；,3,、允许于第二年初投入，于第三年末收回，本利合计为投资额的,160%,，但限额投资,20,万元；,4,、允许于第三年初投入，年末收回，可获利,40%,，但限额为,10,万元,.,试为该公司确立一个使第三年末本利和最大的投资组合方案，,请建立这个问题的线性规划模型。,解：用,x,ij,表示第,i,年初投放到第,j,个项目的资金数，则建立如下线性规划模型：,1,2,3,4,一,二,三,第,i,年初,投入第,j,个项目,用单纯形法求得：,1,2,3,4,一,166666.7,133333.3,二,0,200000,三,100000,100000,第三年末本利和,=580000,综上投资组合方案如下：,