《运筹学LPIL》PPT课件.ppt

运筹学模型（运筹学模型（1）运筹学模型（运筹学模型（2）运筹学模型（运筹学模型（3）提示提示1：如果只需要截：如果只需要截2.9米的米的100根，如何下料？根，如何下料？提示提示2：如果需要截：如果需要截2.9米和米和2.1米的各米的各100根，又如何下料？根，又如何下料？有八种方法截取有八种方法截取l 123456782.9m211100002.1m021032101.5m00130134x1x2x3x4x5x6x7x8lMf=x1+x2+x3+x4+x5+x6+x7+x8l2x1+x2+x3+x4=100l 2x2+3x3 +3x5+2x6+x7=100l x3+3x4 +x6+3x7+x8=100lXj=0且为整数且为整数 j=1,2,3,8运筹学模型（运筹学模型（4）J段段时间段时间段需人数需人数12-6226-105310-1410414-1812518-226622-27lXj-j时段初形成得人数时段初形成得人数 j=1,2,3,4,5,6lMinf=x1+x2+x3+x4+x5+x6lX1+x6=2lX1+x2=5lX2+x3=10lX3+x4=12lX4+x5=6lX5+x6=7运筹学模型（运筹学模型（5）第一章第一章 线性规划线性规划图解法（图解法（1 1）唯一最优解唯一最优解图解法（图解法（2 2）基本概念基本概念 可行解可行解 不可行解不可行解 可行解集可行解集（可行区域可行区域）最优解最优解 最优目标函数值最优目标函数值 基本可行解基本可行解 基本最优解基本最优解图解法（图解法（3 3）无穷多最优解无穷多最优解图解法（图解法（4 4）解无界解无界图解法（图解法（5 5）无可行解无可行解图解法（图解法（6 6）结论结论线性规划问题的解有四种情况线性规划问题的解有四种情况1有唯一最优解有唯一最优解2有无穷多最优解有无穷多最优解3有可行解，但无最优解（解无界）有可行解，但无最优解（解无界）4无可行解无可行解 单纯型法单纯型法线性规划问题的标准形式线性规划问题的标准形式(一一)1 1目标函数求最大目标函数求最大目标函数求最大目标函数求最大2 2约束条件取等号约束条件取等号约束条件取等号约束条件取等号3 3变量为非负变量为非负变量为非负变量为非负线性规划问题的标准形式（二）线性规划问题的标准形式（二）单纯型法（一）单纯型法（一）某工厂计划在一个生产周期内生产甲、乙两种产品，这某工厂计划在一个生产周期内生产甲、乙两种产品，这某工厂计划在一个生产周期内生产甲、乙两种产品，这某工厂计划在一个生产周期内生产甲、乙两种产品，这两种产品分别需要经过两种产品分别需要经过两种产品分别需要经过两种产品分别需要经过AA、BB两道工序加工。已知每件产品两道工序加工。已知每件产品两道工序加工。已知每件产品两道工序加工。已知每件产品在每道工序上加工所需的机时及生产每件产品可以获得的在每道工序上加工所需的机时及生产每件产品可以获得的在每道工序上加工所需的机时及生产每件产品可以获得的在每道工序上加工所需的机时及生产每件产品可以获得的利润如下表，如何安排生产，才能使总利润最大？利润如下表，如何安排生产，才能使总利润最大？利润如下表，如何安排生产，才能使总利润最大？利润如下表，如何安排生产，才能使总利润最大？甲甲乙乙可用机时可用机时工序工序A2480工序工序B3260单位利润单位利润6050单纯型法（二单纯型法（二）（0，20）CB（10，15）（0，0）OA（20，0）单纯型法（三单纯型法（三）（0，20）CB（10，15）（0，0）OA（20，0）单纯型法（四单纯型法（四）单纯型法（五单纯型法（五）基变量基变量基变量基变量“非自由变量非自由变量非自由变量非自由变量”，记号，记号，记号，记号xxBB非基变量非基变量非基变量非基变量“自由变量自由变量自由变量自由变量”，记号，记号，记号，记号基基基基 所有基变量下标的集合，记号所有基变量下标的集合，记号所有基变量下标的集合，记号所有基变量下标的集合，记号BB典式典式典式典式 约束等式是基变量由非基变量表示；约束等式是基变量由非基变量表示；约束等式是基变量由非基变量表示；约束等式是基变量由非基变量表示；目标函数中不含有基变量目标函数中不含有基变量目标函数中不含有基变量目标函数中不含有基变量单纯形表单纯形表单纯形表单纯形表基可行解典式的表格化基可行解典式的表格化基可行解典式的表格化基可行解典式的表格化检验数检验数检验数检验数入基变量入基变量入基变量入基变量出基变量出基变量出基变量出基变量转轴点转轴点转轴点转轴点单纯型法（六）单纯型法（六）解：引进松弛变量解：引进松弛变量x3,x4,x5，把线性规划问题化为标准形，把线性规划问题化为标准形单纯型法（七）单纯型法（七）基变量基变量基变量基变量X XBB=(x=(x33,x,x44,x,x55)，可以得到对应的单纯形表如下：，可以得到对应的单纯形表如下：，可以得到对应的单纯形表如下：，可以得到对应的单纯形表如下：xBx1x2x3x4x5x3101004x4010103x5120018-2-500001单纯型法（八）单纯型法（八）单纯表矩阵计算公式：单纯表矩阵计算公式：单纯型法（九）单纯型法（九）例1.16解：化成标准形解：化成标准形单纯型法（十）单纯型法（十）例1.17解：化成标准形解：化成标准形单纯型法（十一）单纯型法（十一）例1.17两阶段法（两阶段法（1）例例1.8解：引入人工变量解：引入人工变量x6,x7构造辅助问题构造辅助问题两阶段法（两阶段法（2）例例1.8x1x2x3x4x5x6x7x61-16-10102x71120-1011-20-81100-3502100000 xBx1x2x3x4x5x6x7x60-1/21-1/41/41/4-1/41/4x11201/2-3/2-1/23/21/20000011001/2011/49/4-11/4-9/4-31/4对偶规划（对偶规划（1）对偶规划（对偶规划（2）对偶规划（对偶规划（3）对偶规划（对偶规划（4）原问题原问题对偶问题对偶问题有最优解有最优解解无界解无界无可行解无可行解有最优解有最优解解无界解无界无可行解无可行解对偶单纯形法（对偶单纯形法（1）对偶单纯形法（对偶单纯形法（2）影子价格（影子价格（1）影子价格（影子价格（2）影子价格（影子价格（3）影子价格（影子价格（4）灵敏度分析（灵敏度分析（1）灵敏度分析（灵敏度分析（2）灵敏度分析（灵敏度分析（3）目标规划（目标规划（1）从市场信息反馈可知，对甲、乙两种产品需要量的比例大致是从市场信息反馈可知，对甲、乙两种产品需要量的比例大致是1 1；计划期内的设备能力有一点机动的余地。如设备计划期内的设备能力有一点机动的余地。如设备B必要时可以加班，当然不希望加班；必要时可以加班，当然不希望加班；设备设备A既要充分利用，又尽可能不加班；既要充分利用，又尽可能不加班；企业决策者认识到不考虑附加条件，才使利润指标达到企业决策者认识到不考虑附加条件，才使利润指标达到14。所以这是一个偏高的指标，决定降低为。所以这是一个偏高的指标，决定降低为12 目标规划（目标规划（2）l偏差变量偏差变量 d+正偏差正偏差 d-负偏差负偏差l目标约束与系统约束目标约束与系统约束 系统约束系统约束不可松动的严格约束不可松动的严格约束 目标约束目标约束可以松动的约束可以松动的约束l目标优先级与权系数目标优先级与权系数 优先级优先级P1、P2、P3 权系数权系数系数大小表示同一优先级中目标的重要程度系数大小表示同一优先级中目标的重要程度第二章第二章 运输问题运输问题130+210+360=230（百元）（百元）130+210+1060=650（百元）（百元）240+530+1030=530（百元）（百元）第一节第一节 运输问题及其特征（运输问题及其特征（2）一、运输问题一、运输问题第一节第一节 运输问题及其特征（运输问题及其特征（2）二、运输问题的特征二、运输问题的特征l特征特征1：运输问题一定有可行解；：运输问题一定有可行解；l特征特征2：运输问题一定有最优解；：运输问题一定有最优解；l特征特征3：运输问题每一组基对应运输问题每一组基对应m+n-1个基变量；个基变量；l特征特征4：运输问题的：运输问题的m+n-1个基变量不构成闭回路；个基变量不构成闭回路；l特征特征5：任意一个非基变量和：任意一个非基变量和m+n-1个基变量组成的变个基变量组成的变量集合中必定存在一条并且只存在唯一一条量集合中必定存在一条并且只存在唯一一条闭回路闭回路；l特征特征6：如果运输问题中的供应量和需求量都是整数，：如果运输问题中的供应量和需求量都是整数，则任一基本解中各变量的取值也都是整数则任一基本解中各变量的取值也都是整数约束方程的系数矩阵：闭回路闭回路第二节第二节 运输问题的表上作业法运输问题的表上作业法第一步：编制初始调运方案，也就是寻找第一个基本可行解；第一步：编制初始调运方案，也就是寻找第一个基本可行解；l求解初始调运方案的方法有很多种，像求解初始调运方案的方法有很多种，像西北角法西北角法、最小元素法最小元素法、伏格尔法等都是非常有效的。本书主要介绍最常用的前两种方法。伏格尔法等都是非常有效的。本书主要介绍最常用的前两种方法。第二步：求出相对应的检验数；第二步：求出相对应的检验数；l求检验数的方法也不止一种，本书主要介绍求检验数的方法也不止一种，本书主要介绍位势法位势法和和闭回路法闭回路法。第三步：检验调运方案是否是最优方案；第三步：检验调运方案是否是最优方案；如果已经是最优，则算法结束，问题已经解决；如果已经是最优，则算法结束，问题已经解决；如果还不是最优，则进入第四步；如果还不是最优，则进入第四步；第四步：调整非最优的调运方案，获得更好的调运方案，也就是进第四步：调整非最优的调运方案，获得更好的调运方案，也就是进行换基迭代；行换基迭代；l改进调运方案，一般采用改进调运方案，一般采用闭回路调整法闭回路调整法。西北角法西北角法C 1=23+96+32+43+21+56=110 最小元素法最小元素法C 2=95+74+13+22+43+24=100 用西北角法和最小元素法求下列问题的初始方案：用西北角法和最小元素法求下列问题的初始方案：求检验数的闭回路法（求检验数的闭回路法（1）求检验数的闭回路法（求检验数的闭回路法（2）求检验数的位势法（求检验数的位势法（1）求检验数的位势法（求检验数的位势法（2）闭回路调整法闭回路调整法闭回路上所有标“+”号的xij加上 所有标“-”号的xij减去 第三节第三节 不平衡的运输问题不平衡的运输问题ll供过于求的运输问题供过于求的运输问题供过于求的运输问题供过于求的运输问题ll供不应求的运输问题供不应求的运输问题供不应求的运输问题供不应求的运输问题第三章第三章 整数规划整数规划第一节第一节 整数线性规划问题整数线性规划问题一一、整数线性规划问题、整数线性规划问题二、二、整数规划的分类整数规划的分类l纯整数规划纯整数规划 所有变量都取非负整数的线性规划所有变量都取非负整数的线性规划l混合整数规划混合整数规划 部分变量取非负整数的线性规划部分变量取非负整数的线性规划l0101规划规划 变量的值只限制取变量的值只限制取0或或1的线性规划的线性规划第三节第三节 01规划规划 第三节第三节 01规划规划 第三节第三节 01规划规划 第四节第四节 分配问题分配问题 分配问题分配问题 分配问题分配问题 系数矩阵的定义与性质系数矩阵的定义与性质匹匹 配配甲甲蝶泳蝶泳乙乙蛙泳蛙泳 丙丙自由自由泳泳丁丁仰泳仰泳甲甲蛙泳蛙泳乙乙自由泳自由泳 丙丙蝶泳蝶泳丁丁仰泳仰泳分配问题的匈牙利解法分配问题的匈牙利解法 分配问题的匈牙利解法分配问题的匈牙利解法 分配问题的匈牙利解法分配问题的匈牙利解法 分配问题的匈牙利解法分配问题的匈牙利解法 第一步：给系数矩阵第一步：给系数矩阵“制造制造”0元素：元素：1.从系数矩阵的每行元素减去该行的最小元素；从系数矩阵的每行元素减去该行的最小元素；2.从系数矩阵的每列元素减去该列的最小元素。从系数矩阵的每列元素减去该列的最小元素。第二步：找第二步：找 n 个独立的个独立的“0”元素元素：如果个数达到如果个数达到n个，则结束，已经的最优解；个，则结束，已经的最优解；否则，转第三步。否则，转第三步。第三步第三步 增加系数矩阵中的增加系数矩阵中的0元素：元素：1.找最少直线覆盖效率矩阵中的所有找最少直线覆盖效率矩阵中的所有0元素元素（1）对没有）对没有0*行的行打行的行打，（2）对打）对打 的行上所有有的行上所有有0元素的列打元素的列打，（3）对打）对打 列的上所有有列的上所有有0*元素的行打元素的行打，（4）重复（）重复（2）（）（3）步，到过程结束）步，到过程结束（5）对没有打）对没有打 的行画横线，所有打的行画横线，所有打 的列画垂线，的列画垂线，找到了覆盖所有找到了覆盖所有0元素的最少直线。元素的最少直线。分配问题的匈牙利解法分配问题的匈牙利解法分配问题的匈牙利解法分配问题的匈牙利解法2.增加增加0元素元素（1）在系数矩阵中没有被覆盖的元素中找最小）在系数矩阵中没有被覆盖的元素中找最小元素元素；（2）对没有被直线覆盖的行，减去最小元素）对没有被直线覆盖的行，减去最小元素，对被直线覆盖的列，加上最小元素对被直线覆盖的列，加上最小元素；转第二步。转第二步。分配问题的匈牙利解法分配问题的匈牙利解法 最大值问题最大值问题 匈牙利法实质上一种求最小值的方法，匈牙利法实质上一种求最小值的方法，如果给我们的是系数矩阵，如果给我们的是系数矩阵，a ij表示表示的是第的是第 i 个个人员完成第人员完成第 j 项任务的收益，则要求我们如何项任务的收益，则要求我们如何分配某人完成某项任务，使总收益最大。这种分配某人完成某项任务，使总收益最大。这种求最大值的分配问题如何求解呢。求最大值的分配问题如何求解呢。分配问题的匈牙利解法分配问题的匈牙利解法系数矩阵不是方阵系数矩阵不是方阵 在实际问题中，往往遇到有些任务没有人去在实际问题中，往往遇到有些任务没有人去做，或某些人没有分配到任务的情况。对系数做，或某些人没有分配到任务的情况。对系数矩阵来说，表现为系数矩阵不是方阵，而用匈矩阵来说，表现为系数矩阵不是方阵，而用匈牙利法求解时，系数矩阵为方阵是必要条件。牙利法求解时，系数矩阵为方阵是必要条件。分配问题的匈牙利解法分配问题的匈牙利解法 某工厂订购了三台机器（某工厂订购了三台机器（A,B,C），有四），有四各位置可供机器安装（位置一，二，三，四），各位置可供机器安装（位置一，二，三，四），但但B机器不能安装在第二号位置。由于这四个机器不能安装在第二号位置。由于这四个安装位置离工厂中心的远近不同，所需要的原安装位置离工厂中心的远近不同，所需要的原料运送费用也就不同，想要求总的原料运送费料运送费用也就不同，想要求总的原料运送费用达到最小，问这些机器安装在哪几个位置最用达到最小，问这些机器安装在哪几个位置最适合？适合？分配问题的匈牙利解法分配问题的匈牙利解法分配问题的匈牙利解法分配问题的匈牙利解法分配问题的匈牙利解法分配问题的匈牙利解法 某单位有四项任务，而有五个员工都能胜任这四项某单位有四项任务，而有五个员工都能胜任这四项任务，但是由于技术水平不同，完成任务的时间也不同，任务，但是由于技术水平不同，完成任务的时间也不同，问如何分配任务使总时间最少？问如何分配任务使总时间最少？