管理运筹学(修改稿6)ppt课件

1、.,开课前的话,1.课程及参考书 课程名：运筹学 课程类别：专业基础课, 必修. 教材:韩伯棠编著,管理运筹学, 高等教育出版社 参考书: 1)钱颂迪主编,运筹学 清华大学出版社，1990年第2版 2)韩大卫编著,管理运筹学, 大连理工大学出版社,.,2.讲授学时与内容 1) 学时：36 2) 讲授主要章节：第2章，第3章，第4章；第12章; 第13章;第16章等。另外还有1个案例。,.,3.学习及考试要求： 本课程重在36学时的学习，学了什么考什么，闭卷考试。故要求坚持听课；选择笔记；思考问题；认真作业。 4.最终成绩形成： 平时分0.4期末考试分0.6 + 回答问题分 平时成绩： 1)考勤

2、20分。 2)案例分析20分。 期末考试：下学期考。考讲了的题目。,.,管理运筹学属于管理（优化）方法课程 应用分四步骤： 1.把实际问题抽象成运筹学(有关分支)问题； 2.建立运筹学(有关分支)问题模型； 3.求解有关运筹学模型； 4.利用模型和求解的数据进行决策分析，达到优化目的。 第一章 线性规划模型及图解法 1 线性规划问题模型 2 图解法,.,1 线性规划问题模型,一、问题的提出-引例 例1.(2009高考题5分) 在家电下乡活动中, 某厂要将100台洗衣机运到某乡镇, 现有4辆甲型货车和8辆乙型货车可供使用,每辆甲型货车运费为400元, 可装20台洗衣机, 每辆乙型货车可装10台洗

3、衣机, 运费为300元,若每辆车至多可运一次,则该厂所花最小运费为: A. 2000元 B. 2200元 C. 2400元 D. 2800元,.,解：设y1辆为使用甲型货车，y2辆为使用乙型货车，则有 目标函数： Min f =400y1+300y2 约束条件： s.t. 20 y1 + 10 y2 100 y1 4 y2 8 y1 ，y20 这就是例1 的线性规划模型。,.,例2. 某工厂计划在某个月安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表： 问题： 1）工厂应分别生产多少、产品，才能使获总利润最多？,.,2）若工厂不生产产品，改出售资

4、源，应如何确定这三种资源的单位利润，使出售资源的总利润不低于出售产品的总利润？ 解： 1) 设x1，x2分别表示 、两产品的产销量，则有 目标(利润)函数： Max z = 50 x1 + 100 x2 约束条件：s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 0 这就是问题1的线性规划模型。 下面讨论问题2的线性规划模型,.,解：2) 设y1，y2，y3分别为设备、原料A、原料B的单位利润，则有 目标(利润)函数： Min f =300y1+400y2+250y3 约束条件： s.t. Y1 + 2y2 + 0y3 50 Y1 + y2 + y3

5、100 Y1，y2，y30 这就是问题2的线性规划模型,.,二、线性规划问题的一般模型 1.建模过程 1) 理解要解决的问题，了解解题的目标和条件； 2) 定义决策变量（ x1 ，x2 ， ，xn ），每一组值表示一个方案； 3) 用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标； 4) 用一组决策变量的等式或不等式，表示解决问题过程中必须遵循的约束条件。 2.线性规划模型三要素： 1) 决策变量 用符号来表示可控制的因素 2) 目标函数 Max Z 或 Min F 3) 约束条件 s.t. (subject to) 满足于,.,3. 线性规划模型一般形式(p12) 目标函数： M

6、ax （Min） z = c1 x1 + c2 x2 + + cn xn 约束条件：s.t. a11 x1 + a12 x2 + + a1n xn ( =, ）b1 a21 x1 + a22 x2 + + a2n xn ( =, ）b2 am1 x1 + am2 x2 + + amn xn ( =, ) bm x1 ，x2 ， ，xn 0,.,4. 几点注意 1) 目标函数与约束条件必须线性，否则是非线性规划； 2) 决策变量是连续分布的，否则可能是整数规划； 3) 目标是单一的，否则是多目标规划； 4) 决策变量的系数是确定的不变的.,.,2 图 解 法,一、几个名词 1.可行解(p11)

7、：满足所有约束条件的解称为该线性规划问题的可行解(或可行方案)。 2.最优解、最优值：使目标函数值达最大(或最小)的可行解称为该线性规划问题的最优解，此目标函数值称为最优值。 3.可行域(p12) 线性规划问题可行解的集合称为可行域。 二、图解举例 对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图求解。 下面通过例1详细讲解其方法：,.,例1. 目标函数： Max z = 50 x1 + 100 x2 约束条件(s.t.) ： x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E) 得到最优解：x1 = 50，

8、 x2 = 250 最优目标值 z = 27500,.,第一步 确定可行域 (1)作直角坐标系：分别取决策变量X1 , X2 为坐标向量建立平面直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值。 （2）作直线：对每个不等式，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。 （3）确定可行域：把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。 第二步 确定最优解和最优值 (1)改写目标函数为： x2=-(50/100) x1+z/100,.,(2)以Z为参数作平行线族：当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”

9、。平行移动等值线得到以Z为参数的平行线族，当移动到B点时，z在可行域内实现了最大化。 (3)确定最优解和最优值：B(50,250) Z=27500。,.,三、线性规划的标准化内容之一：引入松驰变量（含义是资源的剩余量p15） 例1 中引入 s1， s2， s3 模型化为 目标函数： Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3 约束条件：s.t. x1 + x2 + s1 = 300 2 x1 + x2 + s2 = 400 x2 + s3 = 250 x1 , x2 , s1 , s2 , s3 0 此例最优解的实际意义：对于最优解 x1 =50 x

10、2 = 250 ， s1 = 0 s2 =50 s3 = 0 说明：生产50单位产品和250单位产品将消耗完所有的设备台时数及原料B，但对原料A则还剩余50千克。,.,四、线性规划问题解的几种情况(p15)： 1.唯一最优解。例1 2.无穷多个最优解。若将例1中的目标函数变为 max z=50 x1+50 x2 则线段BC上的所有点都代表了最优解； 3.无界解(无最优解)。即可行域无界，目标函数值可以无穷大或无穷小。一般来说，这可能是忽略了一些必要约束条件，因实际问题不可能有如此宽松的环境； 4.无可行解(无解)。若在例1的数学模型中再增加一个约束条件4x1+3x21200，则可行域为空域，不

11、存在满足约束条件的解。如果实际问题出现这种情况，说明约束过紧或无可行决策方案。,.,五、目标函数最小化举例 例2 某公司计划用A、B两种原料配制79-1消毒液350吨，技术规定其中A原料至少需要125吨。现生产每吨A原料需要2小时，生产每吨B原料需要1小时，生产成本分别为，每吨A原料2万元，每吨B原料3万元，而公司计划期最多能提供600个小时生产A、B原料。 问：计划期应如何配制方能使生产A与B的总成本最低? 解：目标函数： Min f = 2x1 + 3 x2 约束条件(s.t.) ： x1 + x2 350 x1 125 2 x1 + x2 600 x1 , x2 0,.,采用图解法。得Q

12、点坐标（250，100）为最优解。,最优值Min f=22503 100=800 A(125，350) f=1300 B(125，225) f=925 Q(250，100) f=800 A B,.,3 线性规划模型标准形式及图解法的灵敏度分析,一、标准形式(p17) 目标函数 Max z = c1 x1 + c2 x2 + + cn xn 约束条件： a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0，bi 0 可以看出，线性

13、规划的标准形式有如下四个特点： 1)目标函数最大化； 2)结构约束为等式； 3)决策变量均非负； 4)结构约束右端项非负。 对于各种非标准形式的线性规划问题，我们总可 以通过以下变换，将其转化为标准形式:,.,二、化一般形式为标准形式 1.极小化目标函数的问题： 设目标函数为 Min f = c1x1 + c2x2 + + cnxn (可以)令 z -f ， 则该极小化问题与下面的极大化问题有相同的最优解， 即 Max z = - c1x1 - c2x2 - - cnxn 但必须注意，尽管以上两个问题的最优解相同，但它们 最优解的目标函数值却相差一个符号，即 Min f - Max z,.,2

14、、约束条件不是等式的问题： 设约束条件为 ai1 x1+ai2 x2+ +ain xn bi 可以引进一个新的变量s ，使它等于约束右边与左 边之差 s=bi(ai1 x1 + ai2 x2 + + ain xn ) 显然，s 也具有非负约束，即s0， 这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn+s = bi,.,当约束条件为 ai1 x1+ai2 x2+ +ain xn bi 时， 类似地令 s=(ai1 x1+ai2 x2+ +ain xn)- bi 显然，s 也具有非负约束，即s0，这时新的约 束条件成为 ai1 x1+ai2 x2+ +ain xn-s = bi

15、 为了使约束由不等式成为等式而引进的变量s,当不等式为“小于等于”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量和剩余变量。,.,3.右端项有负值的问题： 在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi0,则有 若 ，则有yi*=0,.,第六章 运 输 问 题,1 运 输 模 型 2运输问题的应用 3运输问题计算机求解 4 运输问题的表上作业法,.,第一节 运输问题模型,运输问题是特殊的线性规划问题 一、特点 1.广泛的应用性 运输问题涉及到公路、铁路、航空、

16、水运、管道、线路等，加之还有些问题可转换为运输问题(如供产销问题) 2.特殊性 在模型三要素中,决策变量的含意一般是运输量；目标函数多是求总运输费最小；约束条件在很多情况下是线性方程组。 模型形式还可以是表格。,.,二、引例 例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示。 问：应如何调运可使总运输费用最小？,.,解： 这是一个 产销平衡运输问题。设Xij 为从产地Ai运往销地Bj的运输量；目标函数为求最小总运费 ；约束条件为：总产量 = 总销量 其线性规划模型如下： Min f = 6X11+ 4X12

17、+ 6X13+ 6X21+ 5X22+ 5X23 s.t. X11+ X12 + X13 = 200 X21 + X22+ X23 = 300 X11 + X21 = 150 X12 + X22 = 150 X13 + X23 = 200 Xij 0 ( i = 1、2；j = 1、2、3）,.,三、产销平衡运输问题一般模型 先给一些符号约定： A1、 A2、 Am 表示某物资的m个产地； B1、B2、Bn 表示某物资的n个销地； si 表示产地Ai的产量； dj 表示销地Bj 的销量； cij 表示把物资从产地Ai运往销地Bj的单位运价； xij 为从产地Ai运往销地Bj的运输量。 得到下列

18、产销平衡运输问题一般模型： 1.平衡运输问题线性规划模型,.,m n Min f = cij xij i = 1 j = 1 n s.t. xij = si i = 1,2,m j = 1 m xij = dj j = 1,2,n i = 1 xij 0 (i = 1,2,m ; j = 1,2,n),.,2.平衡运输问题表格模型,.,例1的表格模型,.,四、有关结论及注意事项 结论：产销平衡运输问题模型必有最优解。 注意1 有些求最大值的实际问题,可以转换为运输问题来建模,这需要将目标函数由求极大转换为求极小； 注意2 运输问题线性规划模型的约束条件可以出现不等式，但表格模型的产销量不可以不

19、平衡； 注意3 在以下的讨论中，我们利用运输问题的特殊性，总把运输问题建成表格模型。,.,3 运输问题的应用,一、供需不平衡的运输问题 1.供小于需的运输问题 例2、石家庄北方研究院有一、二、三，三个区。每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价为：,.,问题1. 求一个总运费最小的调运方案 。 问题2. 由于供小于需，经院研究决定一区供应量可减少0-300吨，二区必须满足需求量，三区供应量不少于1500吨，试求总费用为最低的调运方案。 解1. 建立表格模型如下：,.,解2： 根据题意，作出产销

20、平衡与运价表： 这里 M 代表一个很大的正数，其作用是强迫相应的 x31、 x33、 x34取值为0。,.,例3、设有A、B、C三个化肥厂供应1、2、3、4，四个地区的农用化肥。假设效果相同，有关数据如下表： 试求总费用为最低的化肥调拨方案。,.,解： 根据题意，作出产销平衡与运价表：,.,因为最低需求必须满足，这样，为了防止虚构产地的产量运往最低需求，我们把虚构产地运往最低需求销地的运费取定为充分大的正数M ，从而可使最低需求得到真正的满足。而最高需求与最低需求的差，可由实产地运送也可由虚产地运送，当由虚产地运送时，把相应的虚产地运费取定为 0 。对应 4”的销量50 是考虑问题本身取定的数

21、据，根据产销平衡要求确定 D的产量为 50。,.,2. 供大于需的运输问题 例4. 某资料如下：,.,解：虚设一个假想的销地B4，可建模如下： 问1. 运往虚拟销地的运价是多少? 问2. 若A2产地不允许库存，那么A2运往B4的运价是多少?,.,二、生产与储存问题 例5、某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如下表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。,.,.,解：把第 i 季度看作第i个工厂，其生

22、产的柴油机数目看作第 i 个工厂的产量；把第 j 季度看作第j个销售中心，其合同交货的柴油机数目看作第 j 个销售点的销量；单位成本加储存、维护等费用看作单位运价；并设 xij为第 i 季度生产的柴油机、第 j 季度交货的数目。则该生产、库存与交货问题可转换为运输问题，并可建立下列产销平衡运输问题模型：,.,.,例6、光明仪器厂生产电脑绣花机是以销定产的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表：,.,已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元,每台机器每月的平均仓储费、维护费为0.2万元。在7

23、-8月份销售淡季，全厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万元。 问应如何安排1-6月份的生产计划，可使总的生产费用（包括生产、运输、仓储、维护）最少？,.,解： 这个生产存储问题可化为运输问题来做。考虑：各月生产与交货分别视为产地和销地 1）1-6月份合计生产能力（包括正常、加班生产能力和上年末储存量）为743台，销量为707台。设一假想销地销量为36； 2）上年末库存103台，只有仓储费和运输费，把它列为第0行； 3）6月份的需求除70台销量外，还要80台库存，其需求应为70+80=150台； 4）1-6表示1-6月份正常生产情况， 1，-6

24、表示1-6月份加班生产情况。 产销平衡与运价表如下：,.,.,用“管理运筹学”软件解得的结果：1-6月最低生产费用为8307.5万元，每月的销售安排如下表：,.,2运输问题计算机求解,例子：,.,4 运输问题的表上作业法,表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。但如果用单纯形表求解则有mn个方程，mn个变量，表格会很大。如当m=20，n=30时就有50个约束条件，在单纯形表中至少有600个(考虑人工变量)变量。这样，即使用计算机求解，输入数据也会很复杂。表上作业法则可避免这种复杂性。 平衡运输问题表格模型的表上作业法的步骤如下：,.,1.求初始基本可行解 从产销平衡的运输问题

25、的线性规划模型的约束条件可知，其系数矩阵A的前m(个产地)行之和等于后n(个销地)行之和，即A的行向量组线性相关；同理增广矩阵的行向量组也是线性相关的(第126页例1的线性规划模型可说明这一点)。 实际上有理论保证：在平衡运输问题模型约束条件中，线性方程组的系数矩阵的秩与增广矩阵的秩相等，均为mn1，这意味着基本可行解所含基变量的个数必为mn1。 具体操作步骤是在mn的产销平衡表上给出m+n-1个数字格，其相对应的调运量的值即为基变量的值。,.,2. 求各非基变量的检验数。即除了上述m+n-1个基变量以外的空格的检验数，判别是否达到最优解，如果已是最优，停止计算，否则转到下一步。 3. 确定入

26、基变量和出基变量，找出新的基本可行解。在表上用闭回路法调整。 4. 重复2、3直到得到最优解。,.,例10.喜庆食品公司有三个生产面包的工厂A1，A2，A3，有四个销售公司B1，B2，B3，B4，其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的单位运价如表所示，在表中产量与销量的单位为吨，运价的单位为百元/吨。问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少？ 这是一个产销平衡的运输问题，因此不需要再设假想产地和销地了。 表格模型如下：,.,.,一、确定初始基本可行解 为了把初始基本可行解与运价区分开，我们把运价放在每一栏的右上角，每一栏的中间写上初始基本可行解（调

27、运量）。 1.西北角法：先从表的左上角（即西北角）的变量x11开始分配运输量，并使x11取尽可能大的值，即x11=min(7,3)=3,则x21与x31必为零。同时把B1的销量与A1的产量都减去3填入销量和产量处，划去原来的销量和产量。同理可得余下的初始基本可行解。,.,.,2.最小元素法 西北角法是对西北角的变量分配运输量，而最小元素法是就近供应，即对单位运价最小的变量分配运输量。在表上找到单位运价最小的x21，并使x21取尽可能大的值，即x21=min(4,3)=3,把A1的产量改为1，B1的销量改为0，并把B1列划去。在剩下的33矩阵中再找最小运价，同理可得其他的基本可行解。 一般来说用

28、最小元素法求得的初始基本可行解比西北角法求得的初始基本可行解好。这样从用最小元素法求得的初始基本可行解出发求最优解的迭代次数可能少一些。,.,.,在求初始基本可行解时要注意的两个问题： 1.当我们取定xij的值之后，会出现Ai的产量与Bj的销量都改为零的情况，这时只能划去Ai行或Bj列，但不能同时划去Ai行与Bj列。 2.用最小元素法时，可能会出现只剩下一行或一列的所有格均未填数或未被划掉的情况，此时在这一行或者一列中除去已填上的数外均填上零，不能按空格划掉。这样可以保证填过数或零的格为m+n-1个，即保证基变量的个数为m+n-1个。,.,二、最优解的判别 1.计算检验数 （位势法） 位势法介

29、绍： 结论1. 用表上作业法求解运输问题模型时，Xij的检验数ij可由公式ij=Cij-(ui+vj)得到。(i=1,2,m，j=1,2,n) 结论2.将所有的基变量的检验数ij = 0代入公式ij = Cij-(ui+vj)，可构成一个方程组，再求解，可求出结论1中的ui，vj(i=1,2,m，j=1,2,n) 现对该例149页的表729所提供的信息进行计算如下：,.,由 0=13=3-u1-v3 得 u1+v3=3 由 0=14=10-u1-v4 得 u1+v4=10 由 0=21=1-u2-v1 得 u2+v1=1 由 0=23=2-u2-v3 得 u2+v3=2 由 0=32=4-u3

30、-v2 得 u3+v2=4 由 0=34=5-u3-v4 得 u3+v4=5 这是一个具有6个方程，7个未知量的方程组，他有无穷多解。现以u1为自由未知量，并令u1=0，则求得ui，vj如下表：,.,3,11,3,10,8,5,10,2,9,4,7,1,.,三、求下一个基本可行解 改进运输方案的办法闭回路调整法 闭回路：是指在已给出的调运方案的运输表上，从一个非基变量的空格出发，沿水平或垂直方向前进，若遇到代表基变量的填入数字的格，则向左或右（当然也可以不改变方向）转90度，继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。一个空格存在唯一的闭回路。 看下例：,.,

31、.,闭回路调整法：当表中的某个检验数小于零时，方案不为最优，需要调整。方法是：选取所有负检验数最小的非基变量作为入基变量，以求尽快实现最优。本例中取24 = -1 ，表明增加一个单位的x24运输量，可使得总运费减少1。在以x24为出发点的闭回路中，找出所有偶数的顶点的调运量：x14=3，x23=1，取x24=min(3,1)=1。把闭回路上所有为偶数顶点的运输量都减少这个值，奇数顶点的运输量都增加这个值(见下表)。,.,3,11,3,10,8,5,10,2,9,4,7,1,.,.,对上表再用位势法计算检验数并进行最优性检验，如下表，可知已获得最优解。,3,10,8,5,10,2,4,7,1,3

32、,11,9,.,四、如何找多个最优方案 识别是否有多个最优解的方法和单纯形表法一样，只需看最优方案中是否存在非基变量的检验数为零。如在本题中给出的最优运输方案中x11的检验数为0，可知此运输问题有多个最优解。只要把x11作为入基变量，调整运输方案，就可得到另一个最优方案。,.,.,.,第七章 整数线性规划,整数规划可分为整数线性规划和整数非线性规划，本章我们讨论的是整数线性规划。 整数线性规划又可分为： 1. 纯整数线性规划（所有变量都为非负整数）； 2. 混合整数线性规划（只有一部份变量为非负整数）； 3. 0-1线性规划（变量的取值只限于0和1）。,.,7.1整数线性规划的应用 例1 :京

33、成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟定有10个位置 Aj (j1，2，3，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：在东区有A1 、A2 、A3 三个点至多选择两个；在西区有A4 、 A5 两个点至少选一个；在南区有A6 、A7 两个点至少选一个；在北区有A8 、 A9 、A10 三个点至少选两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示 (单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?,.,解：设： xi = 1 (Ai 点被选用）或 0 (Ai 点没被选用）。 这样我

34、们可建立如下的数学模型： Max z =36x1+40 x2+50 x3+22x4+20 x5 +30 x6+25x7+48x8+58x9+61x10 s.t. 100 x1+120 x2+150 x3+80 x4+70 x5+90 x6 +80 x7+140 x8+160 x9+180 x10 720 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xj 0 且xj 为0-1变量，i = 1,2,3,10,.,例2 某企业在 A1 地已有一个工厂，其产品的生产能力为 30 千箱，为了扩大生产，打算在 A2，A3，A4，A5地中再选择几个地

35、方建厂。已知在 A2 ， A3，A4，A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外， A1的生产能力及A2，A3，A4，A5建成厂后的生产能力，建成厂后销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。 问:应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?,.,解： 设 xij为从Ai 运往Bj 的运输量(单位千箱)， yk = 1(当Ak 被选中时)或0（当Ak 没被选中时),k =2,3,4,5 Minz=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23

36、+4x31+3x32+4x33+9x41 +7x42+5x43+10 x51 +4x52+2x53 s.t. x11+ x12+ x13 30 x21+ x22+ x23 10y2 x31+ x32+ x33 20y3 x41+ x42+ x43 30y4 x51+ x52+ x53 40y5 x11+ x21+ x31+ x41 + x51 = 30 x12+ x22+ x32+ x42 + x52 = 20 x13+ x23+ x33+ x43 + x53 = 20 xij 0，i = 1,2,3,4,5； j = 1,2,3， yk 为0-1变量，k =2,3,4,5。,.,（指派问题）

37、有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把 n 项任务指派给 n 个人，使得完成 n 项任务的总的效率最高，这就是指派问题。 例3有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。,.,解： xij = 1(当指派第 i人去完成第j项工作时)或0（当不指派第 i人去完成第j项工作时) Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24 +26x31+17x3

38、2+16x33+19x34+19x41 +21x42+23x43+17x44 s.t. x11+ x12+ x13+ x14= 1 (甲只能干一项工作) x21+ x22+ x23+ x24= 1 (乙只能干一项工作) x31+ x32+ x33+ x34= 1 (丙只能干一项工作) x41+ x42+ x43+ x44= 1 (丁只能干一项工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干) x14+ x24+ x34+ x44= 1

39、( D工作只能一人干) xij 为0-1变量，i,j = 1,2,3,4,.,例4. p168例5 7.2整数线性规划的计算机求解 例1、例2、例3、例4.,.,第八章 统筹方法,第一节 车间作业计划模型 车间作业计划是指一个工厂生产工序的计划和安排。 一、一台机器、n个零件的排序问题 二、两台机器、n个零件的排序问题,.,1 车间作业计划模型,一、一台机器、n个零件的排序问题 例1.某车间只有一台高精度的磨床，常常出现很多零件同时要求这台磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间如下表所示。 应该按照什么样的加工顺序来加工这六个零件， 才能使得这六个零件在车间里停留的平

40、均时间为最少？,.,1 车间作业计划模型,例1解：如果我们用Pi表示安排在第i位加工的零件所需的时间，用Tj表示安排在第j位加工的零件在车间里总的停留时间，则有 Tj = P1 + P2 + Pj-1 + Pj = 不同的加工顺序得到不同的各零件的平均停留时间，如何得到一个使得各零件的平均停留时间最少的排序呢？这就是我们最后要解决的优化问题，而且我们要设法找到一种简便的算法。 对于某种加工顺序，我们知道安排在第j位加工的零件在车间里总的停留时间为Tj ， Tj = 可知这六个零件的停留时间为： T1 + T2 + T3 + T4 + T5 + T6 P1 + ( P1 + P2 ) + (P1

41、 + P2 + P3 ) + (P1 + P2 + P3 + P4 ) + (P1 + P2 + P3 + P4 + P5) + (P1 + P2 + P3 + P4 + P5 + P6 ) 6 P1 + 5 P2 + 4P3 + 3P4 + 2P5 + P6. 那么各个零件平均停留时间为 从上式可知，对于一台机器n个零件的排序问题，只要系数越大，配上加工时间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。,.,1 车间作业计划模型,可知这六个零件的停留时间为： T1 + T2 + T3 + T4 + T5 +

42、T6 P1 + ( P1 + P2 ) + (P1 + P2 + P3 ) + (P1 + P2 + P3 + P4 ) + (P1 + P2 + P3 + P4 + P5) + (P1 + P2 + P3 + P4 + P5 + P6 ) 6 P1 + 5 P2 + 4P3 + 3P4 + 2P5 + P6. 那么各个零件平均停留时间为 从上式可知，对于一台机器n个零件的排序问题，只要系数越大，配上加工时间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。,.,1 车间作业计划模型,二、两台机器、n个零件 例2.

43、某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在 磨床上加工，每台机器上各零件加工时间如表12-5所示。 表12-5 应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为最少？ 解：由于每个零件必须先进行车床加工，再进行磨床加工，所以在车床上加 工零件的顺序与在磨床上加工零件的顺序是一样的。 如果这些零件在车床上和磨床上加工顺序都为1，2，3，4，5。我们用图12-1 中的线条图来表示各零件加工的开始时间与完成时间，这种图是由一根时间轴和 车床、磨床在每个时间段的状况的图形所构成。,.,1 车间作业计划模型,图 12-1 从上图中我们可以看出，加工时间的延长主要

44、是由于磨床的停工待料 造成的，只要减少磨床的停工待料的时间就能减少整个加工任务的总时间。为了减少磨床的停工待料，我们应该一方面把在车床上加工时间越短的零件越早在车床上安排加工，减少磨床等待的时间；另一方面把在磨床上加工时间越短的零件越晚在车床上安排加工，以便充分利用磨床前面的时间。,.,为了减少磨床的停工待料，我们应该一方面把在车床上加工时间越短的零件越早在车床上安排加工，减少磨床等待的时间；另一方面，把在磨床上加工时间越短的零件越晚在车床上安排加工，以便充分利用磨床前面的时间。具体做法是：（1）在加工所需时间表上选出最短加工时间tij，这是第i工序加工j零件所需时间，当i=1时，将零件j的顺

45、序尽量靠前，若i=2时，将零件j的顺序尽量靠后。(2)在表上划去零件j的所在行，回到步骤1。 这样我们就得到了使完成全部零件加工任务所需总时间最少的零件排序方法。,.,1 车间作业计划模型,寻找例2的最优解：我们在表12-5中找到所列出的最短加工时间是0.25,它是第二道工序磨床加工零件2的所需时间，由于这个时间与磨床有关，故我们把零件2放在加工顺序的末尾，即第五位，并在表中划去零件2 所在行。如表12-6中红色线条所示。 接着，我们又找到最短加工时间为0.5，这一时间与磨床（第二工序）有关，我们把 磨床加工时间为0.5的零件1放到除第五外的加工顺序的末尾，即第四位加工，同时把 表中的零件1所

46、在的行划去。如表12-6中黄色线条所示。,表12-6,.,下一个最短加工时间为0.75，这个加工时间是车床（第一工序）加工零件5的所需时间，故把零件5排在加工顺序的第一位上，同时把表中的零件5所在的行划去。如表12-6中蓝色线条所示。 同样，下一个最短加工时间为1，这是车床加工零件3的所需时间，故把零件3排在第二位上，同时把零件3所在的行划去。如表12-6中黑色线条所示。 这样就得到了最优加工顺序：5，3，4，1，2。一共只需7个小时就能完成全部加工。 从例2中我们可以归纳出关于两台机器n个零件的排序问题，使得全部任务总的时间 最短的排序算法。 （1)在加工所需时间表上选出最短加工时间tij，

47、这是第i工序加工j零件所需时间，当i=1时，将零件j的顺序尽量靠前，若i=2时，将零件j的顺序尽量靠后。(2)在表上划去零件j的所在行，回到步骤1。,1 车间作业计划模型,.,例1. 某公司研制新产品的部分活动与所需时间以及它们之间的相互关系如下表所示，请绘出其网络图。,.,解：（如图）箭线表示一个活动，箭线的方向是从活动开始指向活动的结束，箭线上是各活动的代号，下面标以完成此活动所需的时间。结点用圆圈表示，结点不消耗资源也不占用时间，他只表示一个或若干个活动开始或结束的时点，圆圈里的数字表示结点的编号。下图有两条线路。,5,15,20,10,a,b,c,d,e,60,13,8,38,15,图

48、12-4,.,2. 网络图模型三要素。网络图模型由活动(工序)、结点(事件)、线路组成。 活动：网络图中用箭线表示活动，箭线的方向是从活动开始指向活动的结束，完成一项活动需要消耗资源，同时也需要占用一定的时间。箭线上面是各活动的代号，箭线下面是完成此活动所需的时间。 结点：网络图中用圆圈表示结点，结点不消耗资源也不占用时间，他只表示一个或若干个活动开始或结束的时点，圆圈里的数字表示结点的编号。,.,线路：从网络图始结点开始至终结点结束，由一些箭线和中间结点连成的一条通路 。 3. 建模举例：,.,例4. 把例3的工序进度表做一些扩充，如下表，请建立其统筹方法的网络图模型。,.,解：我们把工序直

49、接进行扩充会发生问题，由于是的紧前工序，故的结束应该是的开始，所以代表的箭线的起点应该是，由于工序的结束也是，所以工序也成了工序的紧前工序，与题意不符。为此我们设立虚工序。虚工序是实际上并不存在而虚设的工序，用来表示相邻工序的逻辑关系，不消耗人力、物力等资源与时间。,1,5,2,6,4,3,a,60,b,15,8,e,10,13,d,c,38,f,图12-5,.,在网络图上添加、工序得网络图如下： 在统筹方法的网络图中不允许两个点之间多于一条弧，因此需增加一个点和虚工序如图：。,1,2,5,6,7,3,4,a,60,15,b,e,c,13,d,38,8,h,5,10,f,g,16,.,在绘制统

50、筹方法的网络图时，要注意图中不能有回路。,1,2,5,7,8,3,4,a,60,15,b,e,c,13,d,38,8,h,5,10,f,6,16,g,.,课堂作业：,.,二、网络时间的计算与确定 在绘制出网络图之后，还要计算下列网络时间： 1. 确定工序时间；2.计算结点时间；3.计算 每道工序最早开始与最早结束时间；计算每道工序最迟开始与最迟结束时间；4. 计算工序时差； 5. 确定关键工序和关键路线。下面结合例子讲解。 例3.某公司拟安装一条生产线，有关资料如下表。 试计算: 1. 各工序时间 2. 各结点的最早与最迟时间； 3. 各工序的最早开始与结束，最迟开始与结束时间； 4. 各工序

51、时差； 5. 关键工序和关键路线(工程工期)。,.,.,解：据表绘制网络图如下：,1,2,3,4,6,7,8,5,a,60,45,e,C,h,j,35,i,g,10,30,d,20,40,25,f,18,15,b,.,工序的最早 开始时间,工序的最早 结束时间,1,a ， ， ,60,结点最早 时间,结点最迟 时间,2,工序 时差, ， ,工序的最迟 开始时间,工序的最迟 结束时间,.,1. 确定工序时间 1) 单一时间估计 2) 三点时间估计 2. 计算结点时间 结点不占用时间与空间。结点时间是指某工序从该结点开始或到该结点结束的一个时刻，可分为结点最早时间和最迟时间。 1) 计算结点最早时

52、间。结点最早时间是指从该结点开始的各工序，最早可能开始工作的时间(刻)。它从网络始点开始，用定义法计算。在图上用“ ” 表示。如图：,.,2)计算结点最迟时间。结点最迟时间是指到该结点结束的各工序，最迟必须结束(完工)的时刻。它从网络终点开始，逆箭线计算。在图上用 “ ” 表示。如图： 3.计算各工序的最早开始与结束时间(ES与EF)。有了各结点的最早时间和工序时间，就可以计算各工序的最早开始与结束时间了。如图，用“ ， ”表示在箭线的上方。 4.计算各工序的最迟开始与结束时间(LS与LF)。有了各结点的最迟时间和工序时间，就可以计算各工序的最迟开始与结束时间了。如图，用“ ， ”表示在箭线的

53、下方。,.,5. 计算工序时差。工序时差：在不影响工程工期条件下，工序最早开始时间与最迟开始时间之差(或工序最早结束与最迟结束时间之差)。用Ts表示：Ts = LS ES = LF EF 。如图所算： 6.确定关键工序和关键线路 1)确定关键工序。工序时差为0的工序称为关键工序。 2)确定关键线路。网络图所有线路中,线路时间(线路上各工序时间之和)最长的那条线路称为关键线路。 (1)时差法。时差为0的工序所组成的线路就是关键线路。,.,(2)定义法。,1,2,7,8,8,1,2,3,7,8,1,2,4,6,7,1,2,4,5,7,1,2,5,7,8,8,45,60,60,35,18,10-,6

54、0,35,20,20,15,30,0,25,60,35,60,35,15,40,35,150,130,170,123,140,.,注： (1)共用时差与专用时差的概念。 (2)关键工序与关键线路都是相对存在的，当工序时差用完之后，非关键工序也成了关键工序；有些非关键线路也成了关键线路。,.,1,2,3,6,7,8,5,a0,60,60,b60,105,45,e60,100,c60,70,h100,115,j135,170,35,i110,135,g80,110,30,d60,80,20,40,25,f70,88,18,4,10,15,0,60,70,0,60,117,80,110,135,170,120,170,80,110,135,100,0,.,0 60 80 110 135 170 a d g l j e 10 h 40 c f 47 b 30,1,2,3,6,7,8,5,a0,60,0,600,60,b60,105,30,4590,135,e60.70,50,c60,70,47,h80,95,40,j135,170,0,35135,170,i110.135,0,g80,110,0,3080,110,d60.80,0,2060,80,10110,120,25110,135,f70,88,47,18117,135,4,10107,117,15120,135,.,最后将上