Operation_research数模(运筹学).ppt

数学规划的建模原则之一:简单性原则容易理解建立的模型不但要求建模者理解，还应当让有关人员理解。这样便于考察实际问题与模型的关系，使得到的结论能够更好地应用于解决实际问题。容易查找模型中的错误这个原则的目的显然与(1)相关。常出现的错误有：书写错误、公式错误。容易求解对线性规划来说，容易求解问题主要是控制问题的规模，包括决策变量的个数和约束条件的个数。这条原则的实现往往会与(1)发生矛盾，在实现时需要对两条原则进行统筹考虑。,建立数学规划模型的四个步骤明确问题，确定决策变量；决策变量是构成解决方案的要素或单元，决策变量的组合构成一个可行解决方案。明确约束条件并用决策变量的等式或不等式表示；尽可能分类描述，防止差错和遗漏用决策变量的函数表示目标，并确定是求极大（Max）、极小（Min）还是特定值；根据决策变量的物理性质研究变量是否有非负性或上下界。,例3.物流网络配送问题,例3.物流网络配送问题,我们要解决的是各条路线最优运输量，引入变量fij表示由vi经过路线(vi,vj)运输到vj的产品数。问题的目标是总运输成本最小化，总运输成本可表示为：总运输成本=7.5f15+3f14+8.2f25+3.5f24+2.3f45+3.4f34+2.3f46+9.2f36,例3.物流网络配送问题,相应的约束条件包括对网络中的每个节点的供求平衡约束。对生产节点v1、v2、v3来说，由某一节点运出的产品数量等于其产量，即：f15+f14=100f25+f24=80f34+f36=70,例3.物流网络配送问题,对配送中心v4，运进的产品数量等于运出的产品数量：f14+f24+f34=f45+f46对仓库v5、v6，运进的产品数量等于其需求量f15+f25+f45=120f46+f36=130,例3.物流网络配送问题,此外，对网络中有运输容量限制的路线的约束是：该路线上的运输产品数量不超过该线路的运输能力，即：f1480，f2480，f3480，f4590，f4690。并且，所有fij0（非负约束）。,例3.物流网络配送问题,共同的特征,从以上几个例子可以看出，线性规划问题有如下共同的特征：每个问题都用一组决策变量（x1,x2,.,xn），这组决策变量的值都代表一个具体方案；有一个衡量决策方案优劣的函数，它是决策变量的线性函数，称为目标函数。按问题不同，要求目标函数实现最大化或最小化；存在一些约束条件，这些约束条件包括函数约束，可以用一组决策变量的线性函数（称为约束函数）大于等于“”、小于等于“”或等于“=”一个给定常数（称为右端项）；决策变量的非负约束。,一般形式,线性规划的一般形式为：,资源分配问题一般形式,资源分配问题是将有限的资源分配从事各种活动的线性规划问题，其一般形式可以描述为：管理层计划用m种资源去从事n种活动，通过收集每种资源的总量和每种活动单位资源使用量以及单位贡献等数据如表1-4所示，来确定活动的数量使得在资源许可的条件下贡献最大。,资源分配问题一般形式,资源分配问题一般形式,我们用表示xj第j种活动的数量(水平)，则目标函数最大化。对于第i种资源，我们有约束条件：即资源消耗量不超过的资源总量,资源分配问题一般形式,因此，这类问题的数学模型为：,成本效益平衡问题一般形式,例2中所讨论的成本效益平衡问题是通过选择各种活动水平的组合，从而以最小的成本实现最低可接受的各种效益水平。该问题的一般形式可描述为：管理层计划用n种活动去提高m种效益的水平，通过调查得知每种活动对各种效益的单位贡献、每种活动的单位成本以及每种效益的最低可接受水平如表,成本效益平衡问题一般形式,成本效益平衡问题一般形式,我们用表示xj第j种活动的数量(水平)，则目标函数最小化。对于第i种效益，我们有,成本效益平衡问题一般形式,因此，这类问题的数学模型为：,物流网络配送问题一般形式,物流网络配送问题一般形式可描述为：假定在一n个顶点m条弧（线路）的运输网络中，有若干发点发送一定数量的物资流，同时又有若干收点接收这些物资流。由于每条弧运输费用不同，运输能力也有一定限制，管理者希望以最小的运输成本完成由发点到收点的运输配送。,物流网络配送问题一般形式,我们用fij表示由vi经过路线(vi,vj)运输到vj的流量，Cij表示线路(vi,vj)的最大运输能力（容量限制），wij表示由顶点vi沿线路(vi,vj)流向vj的单位流量成本。,物流网络配送问题一般形式,物流网络配送问题模型为:,线性规划的计算机求解,线性规划的计算机求解,例1.农场灌溉问题,某公司有四个农场，每个农场的耕地作物需要用水灌溉，因灌溉条件限制，农场的最大水资源供应量有一定限制，各农场的总耕地面积与最大水资源供应量如表2-1所示。该地区适合种植的农作物有棉花、玉米和高粱，三种农作物每种作物每单位种植面积的净收入和耗水量以及每种作物最大允许种植面积如表2-2所示。由于水资源短，公司统一调配水资源规定每个农场受灌溉面积占农场总耕地面积的比例相同，公司管理层面临的决策问题还是如何确定各农场种植各种作物的面积，使得公司总收入最大。,例1.农场灌溉问题,例1.农场灌溉问题,我们首先建立此问题的线性规划模型。由于此问题是决定四个农场中每个农场种植三种农作物的面积，我们引入决策变量xij（i=1，2，3，4；j=1，2，3）表示第i个农场种植第j种作物的面积，目标是使总收入Z=800(x11+x21+x31+x41)+600(x12+x22+x32+x42)+450(x13+x23+x33+x43)最大化,例1.农场灌溉问题,满足下列约束条件：1).农场的耕地面积约束x11+x12+x134000(农场1)x21+x22+x236000(农场2)x31+x32+x335000(农场3)x41+x42+x434500(农场4),例1.农场灌溉问题,2).农场最大供水量约束2x11+1.5x12+x136000(农场1)2x21+1.5x22+x239000(农场2)2x31+1.5x32+x335500(农场3)2x41+1.5x42+x435000(农场4),例1.农场灌溉问题,3)农作物的种植面积约束x11+x21+x31+x416000（农作物1，棉花）x12+x22+x32+x425500（农作物2，玉米）x13+x23+x33+x435000（农作物3，高粱）即各农作物种植面积不超过最大允许种植面积。,例1.农场灌溉问题,4)种植作物面积占总耕地面积比例约束即各农场种植作物面积（灌溉面积）占总耕地面积的比例相同。5)决策变量的非负约束xij0，i=1，2，3，4；j=1，2，3。,例1.农场灌溉问题,例2.证券投资问题,一证券投资者将1000万元资金用于证券投资，已知各种证券（A、B、C、D、E、F）的评级、到期年限、每年税后收益如表2-3所示。管理层对该投资者提出下列要求：国债投资额不能少于300万元；投资证券的平均评级不超过1.5；投资证券的平均到期年限不超过5年。问：每种证券投资多少可以使得税后收益最大？,例2.证券投资问题,例2.证券投资问题,引入决策变量xA、xB、xC、xD、xE、xF分别表示证券A、B、C、D、E、F的投资金额（单位：万元），相应的目标函数（税后收益）为：Z=90.043xA+120.044xB+50.032xC+40.03xD+30.032xE+40.045xF约束条件为：资金总额约束：xA+xB+xC+xD+xE+xF1000国债投资额约束：xC+xD300,例2.证券投资问题,证券平均评级约束：这是一个非线性约束，容易转化为以下线性约束：0.5xA+0.5xB0.5xC0.5xD+2.5xE+3.5xF0证券平均到期年限约束：它等价于线性约束：4xA+7xBxD2xExF0非负约束:xA0，xB0，xC0，xD0，xE0 xF0,例2.证券投资问题,例3.话务员排班问题,某寻呼公司雇用了多名话务员工作，他们每天工作3节，每节3小时，每节开始时间为午夜、凌晨3点钟、凌晨6点钟，上午9点、中午12点、下午3点、6点、9点，为方便话务员上下班，管理层安排每位话务员每天连续工作3节，根据调查，对于不同的时间，由于业务量不同，需要的话务员的人数也不相同，公司付的薪水也不相同，有关数据见表2-4。,例3.话务员排班问题,问：如何安排话务员才能保证服务人数，又使总成本最低？,例3.话务员排班问题,解：这个问题实际上是一个成本效益平衡问题。管理层在向客户提供满意服务水平的同时要控制成本，因此必须寻找成本与效益的平衡。由于每节工作时间为3小时，一天被分为8班，每人连续工作3节，各班时间安排如下（见表2-5）：,例3.话务员排班问题,例3.话务员排班问题,为了建立数学模型，对应于一般成本效益平衡问题，我们首先必须明确包含的活动数目，活动一个单位是对应于分派一个话务员到该班次收，效益的水平对应于时段。收益水平就是该时段里上下班的话务员数目，各活动的单位效益贡献就是在该时间内增加的在岗位话务员数目。我们给出下列成本效益平衡问题参数表（见表2-6）：,例3.话务员排班问题,例3.话务员排班问题,决策变量Xi表示分派到第班的话务员人数（i=1，2，3，4，5，6，7，8），约束条件为：0-3时间段：3-6时间段：6-9时间段：9-12时间段：12-15时间段：,例3.话务员排班问题,15-18时间段：18-21时间段：21-0时间段：非负约束：目标函数为最小化成本：,例3.话务员排班问题,例4.多阶段生产安排问题,南方机电制造公司为全国各地生产一种大型机电设备，按照公司的订单合同，不久要交付使用一定数量的机电设备，所以有必要制定为期6个月的设备生产计划。根据合同，公司必须在未来6个月中每个月底交付一定数量的机电设备，由于原料价格、生产条件、保修和维修工作等安排不同，每月的生产能力和生产成本也不同，当然，可以在成本较低的月份多生产一些设备，但在供给客户之前必须存放，需要付一定的存贮费用。管理层需要制定出一个逐月生产计划，使生产和存贮的总成本达到最小。,例4.多阶段生产安排问题,管理科学小组通过调查收集到每单位生产成本、每月单位存贮费、每月需求量、最大生产能力等数据（见表2-7）。,例4.多阶段生产安排问题,解：管理层需要作出的决策是每个月生产多少台设备，因此我们引入决策变量xj表示第个月生产机电设备的台数（j=1，2，3，4，5，6）。为了建立此问题的一般数学模型，我们用dj表示第j月的需求量；用lj表示第j月的最大生产能力；用cj表示第j月的单位生产成本；用hj表示第j月的单位存贮成本；用fj表示第j月的最大存贮量。,例4.多阶段生产安排问题,由最大生产能力限制，我们容易得到约束：xjlj,j=1，2，3，4，5，6用Ij表示第月底的库存量（j=1，2，3，4，5，6），由最大存贮量约束，我们有：Ijfj,j=1，2，3，4，5，6各个月份之间生产量、需求量和存贮量之间的关系可由下图（图2-15）表示：,例4.多阶段生产安排问题,容易得到下列约束：,例4.多阶段生产安排问题,另外有非负约束：xj0,Ij0，j=1，2，3，4，5，6目标为总成本最小化:,例4.多阶段生产安排问题,例5.下料问题,某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？,解:考虑下列各种下料方案（按一种逻辑顺序给出）,把各种下料方案按剩余料头从小到大顺序列出,假设x1,x2,x3,x4,x5分别为上面前5种方案下料的原材料根数。我们建立如下的数学模型。目标函数：Minz=x1+x2+x3+x4+x5约束条件：s.t.x1+2x2+x41002x3+2x4+x51003x1+x2+2x3+3x5100 x1,x2,x3,x4,x50,模型1,假设x1,x2,x3,x4,x5,x6,x7,x8分别为上面前8种方案下料的原材料根数。我们建立如下的数学模型。目标函数：Minz=0.1x1+0.3x2+0.9x3+1.1x5+0.2x6+0.8x7+1.4x8约束条件：s.t.2x1+x2+x3+x41002x2+x3+3x5+2x6+x7100 x1+x3+3x4+2x6+3x7+4x8100 x1,x2,x3,x4,x5,x6,x7,x80，整数,模型2,假设x1,x2,x3,x4,x5,x6,x7,x8分别为上面前8种方案下料的原材料根数。我们建立如下的数学模型。目标函数：Minz=x1+x2+x3+x5+x6+x7+x8约束条件：s.t.2x1+x2+x3+x41002x2+x3+3x5+2x6+x7100 x1+x3+3x4+2x6+3x7+4x8100 x1,x2,x3,x4,x5,x6,x7,x80，整数,模型3,医药公司的中草药配方问题,安康医药公司考虑配制一种中成药;市场上有八种中草药材包含该中成药所需要的特定成份,公司准备采购一些中草药来配制这种中成药，要求配制后的中成药所包含三种特定成份(不妨设为成份A、成份B和成份C)分别为39、36、38。由于每种中草药材包含的成份不同,采购成本也不同;公司管理层希望以最低的成本来完成中成药的配制;,各个中草药材(每单位)包含的三种成份含量及单位采购成本,数学建模,决策变量Xi表示第种草药在中成药中的使用量（i=1，2，3，4，5，6,7,8）。为了使成本最低我们有:目标函数Z=10 x1+8x2+16x3+11x4+15x5+10 x6+9x7+12x8求极小化,约束条件,2x1+5x2+5x3+4x4+5x5+4x6+3x7+7x8=393x1+3x2+2x3+2x4+4x5+2x6+2x7+3x8=364x1+3x2+3x3+3x4+4x5+3x6+x7+2x8=38Xi0,i=1,2,3.8.,安康医药公司的中草药配方问题的Excel规划求解,讨论:为什么8种中草药,最优方案只选了三种呢?(草药1,草药2和草药7),事实上,由于这个问题只有三个函数约束(成份A、成份B和成份C),三个等式约束看作一个线性方程组:2x1+5x2+5x3+4x4+5x5+4x6+3x7+7x8=393x1+3x2+2x3+2x4+4x5+2x6+2x7+3x8=364x1+3x2+3x3+3x4+4x5+3x6+x7+2x8=38,讨论:为什么8种中草药,最优方案只选了三种呢?,若将第i种草药三种成份含量看作一个三维向量Pi则:由线性代数知识我们知道向量组P1,P2,P7线性无关且构成三维向量空间的一个极大无关组;任何一个三维向量P可由的线性组合来表示出来,即:存在唯一的一组数,k1,k2,k3,使得:P=k1P1+k2P2+k3P3,讨论,例如:对于第5种草药三种成份含量,可以表示为一个三维向量P5,讨论,这就意味着一个单位的第5种草药,其成份等价于0.5个单位的第1种草药+0.5个单位的第2种草药+0.5个单位的第7种草药;即:一个单位的第5种草药,可由0.5个单位的第1种草药,0.5个单位的第2种草药和0.5个单位的第7种草药组合而成;由于这种组合的成本为0.5X10+0.5X8+0.5X9=13.5元,低于第5种草药的单位成本(15元);因此,从成本最低的角度出发中成药的最优方案中不会选用第5种草药.,讨论,由于此问题的约束条件个数为3,方程组每个变量系数向量的维数为3,因而,极大无关组包含向量的个数一定是3个;不管有多少候选草药,最终只需要选3种,其它草药的成份都可以由这三种“组合”而成.在方程组中，只要选定了哪三种，意味着同时确定了其余的均不在选择之列,讨论,令没有入选的其余5种草药在中成药中的数量为零，即:x3=x4=x5=x6=x8=0此时方程组变为只含三个变量的方程组:2x1+5x2+3x7=393x1+3x2+2x7=364x1+3x2+x7=38,讨论,可以求解得到其唯一解:X1=6.5,x2=2.5,x7=4.5.这就是我们的最优配方.因此,只要我们能确定是哪三种中草药入围最优配方,通过解一个方程组就可以得到最优方案了.但是,我们有8种候选草药,如果选三种来“组合”,最多可能有种,为什么最优的方案是第1种草药、第2种草药和第7种草药,而不是其它的三种呢?,讨论,其它草药i成份含量向量由线性组合来表出后,组合代替的成本不高于草药i的单位采购成本.例如:本例中第5种草药的单位成本为12元时(低于13.5元的组合成本),第1种草药、第2种草药和第7种草药这种“组合”就不是为最优的选择了;我们重新用Excel“规划求解”来解这个问题,得到最优解，x1=4,x5=5,x7=2最优的方案是第一种草药4单位、第五种草药5单位和第七种草药2单位就可以满足三种成份需要，这样的方案成本可达到最低，是118元。,灵敏度分析(what-if分析),在实际问题中，我们首先收集有关数据，建立线性规划模型，用Excel求解.管理科学人员在向管理层提出该问题的最优解（最优方案）之后，任务并未完全结束.管理层还希望知道，当各种假设条件变化时，各种管理方法可能产生的结果，并通过对各种结果进行分析，来指导管理层做出最终决策。,灵敏度分析(what-if分析),如果未来的情况有变化的话，最优解将会如何变化？(实际问题中获得所需的数据是相当困难的，有时只能得到所需的数据的估计值)。管理层在做出最终决策之前，必然想知道如果这些估计量与实际情况有一定的误差时最优解将会如何变化，或估计值在什么范围内变化时，不会影响最优解,灵敏度分析(what-if分析),分别讨论下列数据或条件变化时对于最优基（最优解）的灵敏度分析：1)目标函数系数C的变化；2)右端常数的b变化；3)增加新变量和新的约束条件的变化；使用Excel电子表格进行灵敏度分析,运输问题与指派问题,运输问题的一般提法是这样的：某种物资有若干个产地和销地，若已知各个产地的产量、各个销地的销量以及各产地到各销地的单位运价（或运输距离）。问应如何组织调运，才能使总运费（或总的运输量）最省？,运输问题与指派问题,假定有个m产地，n个销地，ai第i产地的供应量，i=1，2，m，。bj第j销地的需求量，j=1，2，n，。cij从产地i到销地j的单位运费.决策变量Xij产地i到销地j的调运数量。i=12，m;j=1，2，n，。使总的运输费用达到最少.1)当=时，为平衡型运输问题；minZ=,运输问题与指派问题,=ai,i=1，2，m，=bj;j=1，2，n，Xij0,运输问题与指派问题,2)当时，为不平衡运输问题约束条件要稍作改变;显然，当供应总量等于需求总量时，运输问题有可行解，且有最优解。并且，当供应量和需求量均为整数时，必存在决策变量均为整数的最优解。运输问题的方程总数为m+n个，对于平衡型的运输问题，当确定其中的m+n-1个方程后，剩下的一个方程也就确定了.,运输问题与指派问题,用Excel电子表格求解运输问题很方便,调用函数sum()或sumproduct().运输悖论:运量增加,单位运输成本不变,有时总运费反而下降,为什么?运输问题并非仅仅用来解决实际的运输问题，许多应用和运输并没有什么直接联系，只要能转化为一个运输问题进行分析，就可以通过它获得解决方案.,运输问题与指派问题,某汽车发动机制造厂拟计划生产一批发动机来满足未来四个月汽车安装的需要。为了给出最优的进度安排，使总成本最小，有关人员已收集数据如下表：,运输问题与指派问题,例.某市开办三所小学，需要为该市内的所有小学重新划定服务区域。该市大致分6个城区，每一城区内小学生数量以及到各小学的近似距离见表。学校的招生数量视具体情况可在一定范围内变动。服务区域的划分目标是使学生到学校的平均距离最短。试求最优划分方案。,运输问题与指派问题,运输问题与指派问题,解该问题产地为各城区的学生数，供应量为各城区的学生数量；销地为各学校就读的学生数，需求量在各学校的最大招生数和最小招生数之间。单位成本在这里是距离学校的里程。Xij-决策变量，表示城区i到学校j就读的学生数。建立EXCEL电子表格模型,运输问题与指派问题,指派问题是一种特殊的运输问题问题，它属于0-1整数规划问题，也可以把它归纳为运输问题。典型的指派问题是将n项工作交给n个人去做，由于每个人做每一项工作所用的时间等成本不同，所以指派问题的目标是如何安排工作，使总的时间等成本最小（或使总的收益最大）。在指派问题中完成工作的也不一定是人，也可能是其它工具，比如机器、汽车、工厂，甚至是要做工作的时间段。,运输问题与指派问题,典型指派问题要满足以下假设：执行工作的人（执行者）数和要完成的工作数量是相同的（一般我们用n来表示）；每个人只能做一件工作；每件工作只能由一个人来完成；第i(i=1,2,.n)个人完成第j(j=1,2,.,n)项工作所需的成本是cij，（或创造效益pij）；目标是如何分配工作，使总的成本最小（或总效益最大）。,运输问题与指派问题,典型指派问题的数学模型一般使用下面的决策变量：第i个人做第j项工作其它其中i=1,2,.n，j=1,2,.,n，所以，每个xij都是一个0-1变量。我们用Z来表示总成本，那么指派问题目标为最小化时的一般模型是：,运输问题与指派问题,Minimizes.t.,图与网络规划,最小费用流问题假定在一n个顶点m条弧（线路）的网络中，有若干发点发送一定数量流，同时又有若干收点接收这些流。由于每条弧运费不同，能力也有一定限制，管理者希望以最小的成本完成由发点到收点的运输流我们用fij表示由vi经过路线(vi,vj)到vj的流量，Cij表示线路(vi,vj)的最大运输能力（容量限制），wij表示由顶点vi沿线路(vi,vj)流向vj的单位流量成本。,网络最大流问题,网络最大流问题许多系统包含了流量问题。例如，公路系统中有车辆流，控制系统中有信电流，供水系统中有水流，金融系统中有现金流等等。实际问题中往往希望系统达到某种流量最大，将此问题转化为图论问题，就是所谓网络最大流问题。,网络最大流问题,在有向网络N=(V、A、C)中，指定两类顶点集Vs、Vt，分别称之为起点和终点，其余的顶点称为中间点。C是弧集对应的容量向量。此问题的一般线性规划模型为:maxZ=r其中Sj中=-r,(当j=s),Sj=r,(当j=t)案例BMZ公司的最大流问题(P249),最短路问题,最短路问题图与网络规划中的一个基本问题,许多管理问题与最短路问题有关，它在通讯、石油管线铺设、公路网等实际问题中有着广泛的应用。最小费用流的特例,起点看作出发点,往终点运送一个单位的流,路长对应费用.,最短路问题数学模型,整数规划问题,在实际应用问题中，我们会常遇到要求问题的决策变量全部或部分是整数的情况，如问题的决策变量表示的是人数、汽车量数、机器台数、以及对事物的逻辑判断等，我们把这样的规划问题称为整数规划问题（IntegerProgramming,IP）,特别地，当这个问题是线性规划问题时就称为整数线性规划问题（IntegerLinearProgramming,ILP）。本章只讲整数线性规划问题.,整数规划问题,