第四章物流系统优化重点内容：重点内容：4.1系统优化方法概述P99一、优化方法的产生和发展发展：二次大战后，军转民（工农业生产、国民经济）50年代以后，出现规划论、排队论、存贮论、决策论等。西蒙：“管理就是决策，决策就是运筹！”运筹帷幄，决策千里！二、最优化方法的研究对象和特点（几个代表性定义）优化方法的特点：(1)研究和解决问题的基础是优化技术，并强调系统整体最优。(2)优势是应用各学科交叉的方法，具有综合性。(3)具有显著的系统分析特点，其各种方法的运用，几乎都需要建立数学模型和利用计算机求解。(4)具有强烈的实践性和应用的广泛性。三、优化模型及其研究方法2.分析和求解优化模型的步骤Step1:提出并形成问题（系统诊断、系统分析）Step2:建立优化模型Step3:分析并求解模型Step4:检验并评价模型Step5:应用或实践模型的解重点内容：4.2线性规划设x1,x2分别表示在计划内产品Ⅰ、Ⅱ的产量，则目标函数：满足的条件：这就是该计划问题的线性规划模型。本问题是一个总产量等于总销量的运输问题，通常称为“产销平衡问题”。设Ai运到Bj的物资数量为xij(i=1,2,3;j=1,2,3,4),总运费为f，则数学模型为：目标函数：约束条件：(1)Ai运到B1,B2,B3,B4的物资数量之和应等于Ai的产量，即约束条件：(2)从A1,A2,A3运到Bj的物资数量之和应等于Bj的需要量，即(3)在不允许有倒运的条件下，运量必须非负，即[例三]指派问题设Cij表示第i个推销员到第j个地区获得的利润，则数学模型为：目标函数：约束条件：[例四]非线性规划设该公司计划经营第一种设备x1件，第二种设备x2件，则由题意，其营业额为重点内容：4.3.1引言整数规划是一类要求变量取整数值的数学规划，可分成线性和非线性两类。根据变量的取值性质，又可以分为全整数规划，混合整数规划，0-1整数规划等。整数规划是数学规划中一个较弱的分支，目前只能解中等规模的线性整数规划问题，而非线性整数规划问题，还没有好的办法。例4.3-1：一登山队员做登山准备，他需要携带的物品有：食品，氧气，冰镐，绳索，帐篷，照相机和通讯设备，每种物品的重要性系数和重量如下：假定登山队员可携带最大重量为25公斤。序号解：如果令xi=1表示登山队员携带物品i，xi=0表示登山队员不携带物品i，则问题表示成0-1规划:MaxZ=20x1+15x2+18x3+14x4+8x5+4x6+10x7s.t.5x1+5x2+2x3+6x4+12x5+2x6+4x725xi=1或xi=0i=1,2,….7例4.3-2背包问题(KnapsackProblem)一个旅行者,为了准备旅行的必须用品,要在背包内装一些最有用的东西,但有个限制,最多只能装b公斤的物品,而每件物品只能整个携带,这样旅行者给每件物品规定了一个“价值”以表示其有用的程度,如果共有n件物品,第j件物品aj公斤,其价值为cj.问题变成:在携带的物品总重量不超过b公斤条件下,携带哪些物品,可使总价值最大?解：如果令xj=1表示携带物品j，xj=0表示不携带物品j，则问题表示成0-1规划:MaxZ=Σcjxjs.t.Σajxjbxj=0或1数学模型整数规划(IP)的一般数学模型:Max(min)Z=Σcjxjs.t.Σaijxjbi(i=1,2,…m)xj0且部分或全部是整数解法概述当人们开始接触整数规划问题时，常会有如下两种初始想法：因为可行方案数目有限，因此经过一一比较后，总能求出最好方案，例如，背包问题充其量有2n-1种方式；连线问题充其量有n!种方式；实际上这种方法是不可行。设想计算机每秒能比较1000000个方式，那么要比较完20!（大于2*1018）种方式，大约需要800年。比较完260种方式，大约需要360世纪。先放弃变量的整数性要求，解一个线性规划问题，然后用“四舍五入”法取整数解，这种方法，只有在变量的取值很大时，才有成功的可能性，而当变量的取值较小时，特别是0-1规划时，往往不能成功。例4.3-3求下列问题：MaxZ=3x1+13x2s.t.2x1+9x24011x1-8x282x1,x20,且取整数值X12假如放弃整数要求后，用单纯形法求得最优解，恰好满足整数性要求，则此解也是原整数规划的最优解。以上描述了目前解整数规划问题的两种基本途径。特殊约束的处理互斥约束矛盾约束在建立数学模型时，有时会遇到相互矛盾的约束，模型只要求其中的一个约束起作用。例4.3-4：下面两个约束是相互矛盾f(x)-50(1)f(x)0(2)引入一个整数变量来处理-f(x)+5M（