智能制造系统设计 课件2.4 运筹学

运筹学--智能制造系统的器官1运筹学概念2运筹学内容——十大分支3运筹学应用——与智能制造的关系智能制造框架

运筹学与智能制造关系

动态规划智能制造生态圈智能排产PLMERPAPSLIMSSRM企业供应方工厂实验数据研发工艺工艺仿真物料采购单与物料供应计划排产发布MES运筹学非线性规划网络分析排队论决策分析对策论WMS物料配送存储论一一对应运输问题线性规划动态规划和整数规划运筹学释义与发展简史运筹学释义

运筹学(operationalresearch)一词起源于第二次世界大战时期的英国。运筹学在不同的领域有不同的释义,从其性质与特点可定义为:

运筹学是一门以数学为主要工具,用系统的观念,多学科的综合,应用模型技术,为经济、军事、管理等部门提供最优的决策方案。“夫运筹帷幄之中，决胜前里之外”，朴素的运筹学思想在我国古代文献中有不少记载。如齐王赛马和北宋丁渭修复皇宫等事例。

现代运筹学名词源于1938年英国，为解决空袭的

早期预警中的协调配合问题。英军成立了由P.M.S.Blackett领导的“operationalresearch”小组。由于综合应用了科学方法和技术，纠正了人们一些直观想象的错误，有效解决了当时战争中的一些新问题。运筹学的发展趋势：(1)运筹学理论研究将会进一步系统深入发展．(2)运筹学将向一些新的研究领域发展．(3)运筹学分散融化于其他学科，并结合于其他学科一起发展．(4)运筹学沿原有的各学科分支向前发展．(5)运筹学中建立模型的问题将日益受到重视．(6)运筹学的发展将进一步依赖计算机的应用和发展．工业生产优化1940二战期间的军事应用交通运输的应用融合大数据人工智能结合计算机技术19702000195019802020深度运筹时间线

运筹学将不同的实际问题归结为不同的数学模型，不同的模型构成了运筹学的各个分支，主要的分支有：1.线性规划（linearprogramming)——PLM

2.非线性规划（nonlinearprogramming)——PLM3.动态规划（dynamicprogramming)——MES4.整数规划（Integerprogramming——SCM5.网络分析（networkanalysis)——ERP6.运输问题（Transportationproblem）7.存储论（inventorytheory)——WMS8.排队论（queueingtheory)——APS9.对策论（gametheory)——CRM10.决策分析（decisiontheory)——CRM运筹分析基本步骤运筹学的核心方法为智能制造系统提供了强有力的决策支持与优化方案。这些方法不仅在理论上精致而全面，也在实际应用中证明了其高效与可行性。问题的分析和确立深入分析，并准确表述问题的本质和目标模型的建立以形式化的方式描述问题结构和关系模型的求解和优化数学方法和算法对建立的模型进行求解模型的验证和修正确保解在实际应用中的有效性和可行性解的有效控制将优化的方案转化为实际行动，实施并监控方案的执行过程方案的实施

确保模型的准确性和可靠性在多元化的经济活动中，巧妙地利用手中有限的资源，以精心的统筹安排实现总体效益的最大化，或是在既定的任务目标下，如何以最小的资源消耗达成目标，这些都是我们面临的关键问题。这类问题，我们通常称之为规划问题。而当这类问题被转化为数学语言进行表述时，如果目标（函数）以及资源的约束条件均呈现为线性函数的形式，那么我们便称之为线性规划问题。第一章线性规划

在考虑资源的合理分配时，还要兼顾效益的最大化线性规划问题的数学模型，其一般形式是：

线性规划问题及其数学模型min(或max)z=CTX

≤(≥,=)bX≥0其中:

向量形式:线性规划问题及其数学模型min(或max)Z=CTXAX≤(≥,=)bX≥0其中:矩阵和向量形式:线性规划问题及其数学模型例如对三个资源的约束，构建二维坐标系。考虑目标函数，在可行域上找到使得目标函数达到最大值的方案。资源1资源2资源3等值线12340123456789图2-75

三个资源的二维坐标系图解法对模型中只含2个变量的LP，可通过在平面坐标系中作图求解。其步骤概括为：1.在平面建立直角坐标系；2.图示约束条件，找出可行域；3.图示目标函数和寻求最优解。

图解法一、图解法的步骤：二、线性规划问题求解的几种可能的结局

无穷多最优解：目标函数与某约束条件对应成比例。无界解：可行域无界无解或无可行解：无可行域1.解的情况有：唯一最优解；无穷多最优解；无界解；无可行解。2.若LP的可行域存在，则可行域是一凸集。3.若线性规划问题的最优解存在,则最优解或最优解之一(如有无穷多)一定是可行域的某个顶点。4.解题思路,先找出可行域的某个顶点，计算其目标函数值。比较相邻顶点的目标函数值，直至找出使目标函数值最大的顶点。图解法三、从图解法得到的启示：

通过建立一个目标函数和一系列线性约束来寻找最优解。在智能制造的大背景下，线性规划与PLM的结合，不仅强化了对生产流程的智能化管理，还促进了制造系统中资源配置的精准化和科学化，为企业的可持续发展提供了有力的决策支持。通过对生产计划的优化，企业可以更灵活地应对市场变化，实现生产效率和产品质量的双重提升，从而在激烈的市场竞争中占据有利地位。产品外观图产品加工路线生产物料清单产品设计产品工艺设计产品生产制造产品服务产品设计图设计物料清单产品库存信息客户需求信息客户需求产品的形成过程产品资料与信息

运输是WMS和SCM中的一类重要问题。供应链是一个由物流系统和该供应链中的所有单个组织或企业相关活动组成的网络。为满足供应链中各方的需求，需要对物品、服务及相关信息，从产地到消费地高效率、低成本地流动及储存进行规划、执行和控制。运筹学中对运输模型的研究为达到上述目的提供了相应的理论和方法论基础。第二章运输问题图2-77

运输网

运输问题即研究物资运输的调度问题。其典型的情况是：设某种物品有m个产地A1,A2,……,Am，各产地的产量分别为a1,a2,……am;有n个销地B1,B2,…,Bn，各销地的销量分别为b1,b2,……,bn，假定从产地Ai（i=1,2……m)向销地Bj（j=1,2,……,n）运输单位物品的运价是cij，如图所示，问怎样调运这些物品才能使总运费最少？运输问题及数学模型产销平衡问题的数学模型为：或用表格表示：运输问题及数学模型运输问题一定有有限最优解运输问题的约束系数矩阵⑴的元素等于０或１。⑵运输问题的约束系数矩阵的每一列有两个非零元素。对产销平衡问题有：⑶所有约束都是等式约束。⑷产量等于总销量。运输问题及数学模型运输问题数学模型的特点运输问题的解运输问题的解X＝（xij）代表一种运输方案。xij的值表示从Ai调运数量为xij的物品到Bj。解X必须满足模型中所有约束条件。基变量对应的约束方程组的系数列向量线性无关。运输问题模型中的约束条件个数为m+n个，但因为总产量=总销量，故只有m+n-1个是线性独立的，所以解X中非零变量的个数不能大于m+n-1个。为使迭带过程能顺利进行，基变量在迭代过程中应保持为m+n-1个。运输问题及数学模型最小元素法：产大于销，划掉列；产小于销，划掉行销产B1B2B3B4产量A141241116A22103910A38511622销量8141214②⑤⑥81410268681026①③④⑦运输问题的最小元素法前面讨论的线性规划问题，有些最优解可能是分数或小数，这是因为线性规划是连续变量的优化问题。在实际问题中，常有要求问题的解必须是整数的情形（整数解），如人员、设备配置等。线性规划中如果所有的变量都限制为（非负）整数，就称之为纯整数线性规划或称为全整数线性规划。第三章整数规划整数规划的数学模型及解的特点整数线性规划的分类：纯整数线性规划：指全部决策变量都必须取值的整数线性规划。也称全整数规划。混合整数线性规划：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的线性规划。0-1型整数线性规划：指决策变量只能取值0或1的整数线性规划。整数规划的数学模型及解的特点整数规划数学模型为：去掉整数约束后的数学模型称为整数规划的松弛问题整数规划及其松弛问题，从解的特点看，二者间既有密切的联系，又有本质的区别。松弛问题的可行域是一凸集，整数规划的可行域（非凸集）是它的松弛问题的可行解集的一个子集。由于整数规划的可行解一定是它的松弛问题的可行解(反之则不一定)。所以整数规划的最优解的目标函数值≤其松弛问题的目标函数值。在一般情况下，松弛问题的最优解不会刚好满足整数约束条件，自然就不是整数规划的最优解。解的特点：整数规划的数学模型及解的特点整数规划并不是线性规划取整。求解整数规划可用分支定界法和割平面解法。分支定界解法，就是只检查可行的整数部分，就能定出最优的整数解，可用于解纯整数或混合的整数规划问题。整数规划的求解例图2-76

三个约束的二维坐标系1234056781234678959x1+8x2=567x1+22x2=70z=x1+x2①

分支定界解法分支定界解法整数规划的求解迭代过程图整数规划的求解②

割平面解法先利用单纯形法解其松弛问题，若最优解中X*的所有分量均为整数，则原问题得到最优解，否则，从X*的非整数分量中选一个，用于构造一个线性约束条件，将其加入最终单纯形表中在继续求解．重复上述步骤，直到获得整数最优解为止。现实生活中经常遇到这样的问题，如某单位需要完成n项任务，有n个人可承担这些任务。由于每个人专长不同，各人完成任务不同（或所耗费时间），效率也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高（或所需总时间最小）的问题。这类问题被称为指派（分配）问题（assignment

problem）。整数规划的求解问题要求极小化时的数学模型是：整数规划的求解约束条件②说明第j项任务只能一人完成：约束条件③说明第i人只能完成一项任务。约束条件②~④的可行解可写成表格或矩阵形式，称为解矩阵。整数规划的求解第一步：使指派问题的系数矩阵经变换，在各行各列都出现0元素。整数规划的求解反复进行前两步直到0元素都被圈出和划掉为止这表明，甲加工D，乙加工B，丙加工A，丁加工C，所需总时间最少。

第一步：变换系数矩阵。第二步：用最少的直线覆盖系数矩阵中的零元素，若直线数等于矩阵阶数n，则已得到最优解，可用画圈的方法确定独立零元素。否则转第三步。第三步：对于系数矩阵中未被直线覆盖的元素选取最小者θ

，所有未被直线覆盖的元素都减去θ，而被一条直线覆盖的元素不变，被两条直线覆盖的元素加上θ

，转第二步。

整数规划的求解匈牙利解法的一般步骤:→-1-7-6-6-6-4-3因为可以覆盖所有０元素的最少直线为４条，小于矩阵阶数，故独立０元素个数小于阶数，非最优。转下一步调整。

整数规划的求解→

整数规划的求解→-1-1+1

C’’已有５个独立的０元素，故可以确定最优的指派方案X。在很多管理情境中，企业面临着多阶段（可以体现为空间、时间等维度）的决策问题，每一阶段的最优决策不仅受制于当时的实际情况（比如当时具备的资源)，而且要考虑到该决策对未来的影响。因此，不同阶段的决策是彼此关联的。动态规划提供了一种解决多阶段决策过程最优化的数学方法。第四章动态规划多阶段决策过程的最优化所谓多阶段决策问题是指这样一类活动过程:它可以分为若干个互相联系的阶段(称为时段)，在每一阶段都需要作出决策。这个决策不仅决定这一阶段的效益,而且决定下一阶段的初始状态。每个阶段的决策确定以后,就得到一个决策序列,称为策略。多阶段决策问题求一个策略,使得整个活动过程的整体效果最优。243254354735358235724332图2-78

简单的线路网图动态规划的基本概念：

⑴

阶段：将所给问题的过程，按时间或空间特征分解为若干相互联系的阶段，以便按次序去求每一阶段的解。用k表示阶段变量。⑵状态：各阶段开始时的客观条件叫做状态。描述各阶段的客观条件的变量称为状态变量sk

，状态变量sk的取值集合称为状态集合,用Sk表示。

状态应具有如下性质：当某阶段状态给定后，在这阶段以后过程的发展不

受以前各段状态的影响。这种特性称为状态的无后效性。多阶段决策过程的最优化⑶决策和策略：当个阶段的状态取定后，就可以做出不同的决策（或选择），从而确定下一阶段的状态，这种决定称为决策，表示决策的变量称为决策变量，用uk（sk)表示。而当各阶段的决策确定后，从初始阶段开始一直到最后一个阶段结束就构成一个决策序列，每一可能的决策序列称为一个策略。用p1,n{u1(s1),u2(s2)…un(sn)}表示。⑷状态转移方程：动态规划中本阶段的状态往往是上一阶段状态和上一阶段的决策结果.它们的关系可用sk+1=T(sk,uk)表示由于它表示了由k阶段到k+1阶段的状态转移规律,所以称为状态转移方程。多阶段决策过程的最优化动态规划中用于衡量所选定策略的优劣的数量指标称为指标函数。指标函数的最优解（最大值或最小值）称为最优值函数，它表示从第k阶段状态采用最优策略到过程终止时的最佳效益值，即例1生产与存储问题

某工厂每月需供应市场一定数量的产品,并将所余的产品存入仓库。一般某月适当增加产量可降低生产成本，但超产部分存入仓库会增加库存费用。要求制定一个逐月的生产计划，在满足需求的条件下，使得一年的生产与存储费用之和最小。

该问题可以看成每月一个决策阶段，全年12个阶段逐次进行决策。

多阶段决策过程的最优化例2投资决策问题某公司现有现金Q万元，在今后5年内考虑给A、B、C、D4个项目投资，这些项目的投资的回收期限、回报率均不同，问该公司应如何确定这些项目的每一年的投资额，使得到第五年末拥有资金的本利总额最大。

该问题可以看成每年一个决策阶段,共5个阶段逐次进行决策。例3设备更新问题企业在使用设备时都要考虑设备的更新问题。因为设备越存旧所需的维护维修费用越多，但购买新设备则要一次性支付较大的费用。现某企业要决定一台设备未来8年的更新计划，已预测了第j年购买设备的价格为Kj，设Gj为经过j年后的残值，Cj为设备连续使用j-1年后在第j年的维修费用（j=1,2,……,8)。问应在那些年更新设备可使得总费用最小。

这是一个8阶段决策问题，每年年初要做出决策，是继续使用旧设备，还是购买新设备。

多阶段决策过程的最优化例4最短路问题逆序解法状态转移方程确定了由一个状态到另一个状态的演变过程，记为图2-78

简单的线路网图243254354735358235724332

多阶段决策过程的最优化第一步:

k=5第二步:

k=4

路径：D1→E1→F路径：D2→E2→F路径：D3→E1→F图2-78

简单的线路网图243254354735358235724332

多阶段决策过程的最优化

多阶段决策过程的最优化第三步：k=3第四步：k=2第五步：k=1决策序列图2-78

简单的线路网图243254354735358235724332将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数，把问题化成一簇同类型的子问题，然后逐个求解。求解时从边界开始，逆（顺）过程行进方向，逐段递推寻优。在每一个子问题求解时，都利用前段已求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。动态规划方法就是把当前一段与未来各段分开，又把当前效益与未来效益结合起来考虑的一种最优算法，因此每段的最优决策是从全局考虑的。动态规划的基本思想：

多阶段决策过程的最优化从需要管理的任务的总进度着眼，以任务中各工作所需要的工时为时间因素，按照工作的先后顺序和相互间的关系作出网络图，以反映任务全貌，实现管理过程的模型化。然后进行时间参数计算，找出计划中的关键工作和关键路线，对任务的各项工作所需的人、财、物通过改善网络计划作出合理的安排，得到最优方案并付诸实施。第五章网络分析

网络图网络就是与点或边有关的带有某种数量指标的图（赋权图）。网络图又称箭头图，由带箭头的线和节点组成。箭线表示工作（或工序、活动），节点表示事项。工作是组成整个任务的各个局部任务，需要一定的时间与资源，而事项则是表示一个或若干个工作的开始或结束，与工作相比，事项不需要时间或所用时间可以忽略不计。图2-79

简单网络

当ERP系统在网络环境中运行时，会产生大量的数据。这些数据不仅包含了企业的运营状况，还记录了用户的行为、网络流量等关键信息。通过网络分析，企业可以深入了解这些数据背后的含义，发现潜在的问题和机会。网络图中的时间参数，主要目的是找出关键路线，为网络计划的优化、调整和执行提供明确的时间概念。网络图的时间参数包括工作所需时间、事项最早、最迟时间、工作最早、最迟时间及时差等。212683574453242314

网络图可见第4条路线所需时间最长。通常把网络图中所需时最长的路称为关键路，关键路上的工作称为关键工作。212683574453242314上图有４条路线：１２３５８４６７１２８１２６７８１２３４６７８4+5+1+3=134+3+4+2+4=174+2+2+4=124+5+2+4+2+4=21

网络图存储论研究的基本问题是：对于特定的需求类型，以怎样的方式进行补充，才能最好地实现存储管理的目标。储存物品的现象是为了解决供应（生产）与需求（消费）之间的不协调问题，这种不协调性一般表现为供应量与需求量和供应时期与需求时期的不一致性（供不应求或供过于求）。在供应与需求之间加入储存这一环节，能够起到缓解供应与需求之同不协调的作用。第六章存储论根据需求和补充过程中是否包含随机性因素，存储问题分为确定型和随机型两种。存储管理中常常以经济性作为管理目标，所以费用分析是存储论研究的基本方法。确定型库存模型可分为经济订货批量模型、带有提前期的经济订货批量模型、存在数量折扣的库存模型。随机型库存模型分为随机离散需求报童模型和随机连续需求报童模型。存储问题经济订货批量模型不允许缺货，补充时间极短因为Q=Rt，所以订货费为C3+KRt，t时间内的平均订货费为：

t时间内的平均存储量为：因此t时间内的平均存储费为：t时间内平均费用为：经济批量公式（EOQ）：图2-81

模型一的存储状态图提前期的经济订货批量模型允许缺货的情况，且补充时间较长图2-82

模型二的存储状态图

补充周期内的生产速度P大于需求速度R，这意味着在补货期间，库存水平会逐渐上升，直至达到设定的再订货点。

由于生产速度恒定，且P>R，可以预测库存将在一个补货周期内先减少到零（如果需求量足够大），然后进入缺货状态，直至新的补货到达。需要考虑缺货成本（C2）、存储成本（C1）、订货成本（C3）。开始生产时间：结束生产时间：随机储存模型当每天准备Q份报纸时，报童每天的损失期望值为：

由于C(Q)是离散的，故采用边际分析法：排队论也称随机服务系统理论，就是为解决排队时，如机械故障、存储调节、增添服务等问题而发展起来的一门学科。排队系统的优化问题分为两类：系统的最优设计和最优控制，即静态最优问题和动态最优问题。在一般情况下，提高服务水平可以减少顾客的等待费用，但却常常增加了服务机构的成本。因此优化的目标之一就是使得这两者的费用之和为最小。第七章排队论图2-84

排队系统排队论是研究由于随机因素的影响而产生拥挤现象的科学，也称随机服务系统理论。排队系统的优化问题分为两类:系统的最优设计和最优控制,即静态最优问题和动态最优问题。在具体实践中，可以通过建立数学模型来描述排队系统的运作过程，并利用数学工具进行求解。常见的排队系统模型有M/M/1、M/M/c、M/G/1等，它们分别描述了不同的服务过程和顾客到达过程。M/M/1/k模型服务水平服务费用总费用等待费用费用

构建M/M/1/k模型：在平稳状态下，单位时间内到达并进入系统的平均顾客数为

，它即是单位时间内实际服务完的平均顾客数，设每服务一顾客服务机构的收入为G元，于是单位时间内输入的期望值是

元，故利润为：

排队论可以帮助APS系统建立精确的生产模型，包括工作站的排队情况和资源利用率。通过排队论的模型，APS可以预测工作站的瓶颈和可能的等待时间，从而调整生产计划和资源分配，以最大化生产效率。排队论提供了对物流系统的详细分析，例如等待时间、服务率、AGV小车利用率等。今日最后期限今日最后期限CEADBCEADB对策论（GameTheory），又名博弈论，乃是一门专注于研究具有对抗性或竞争性特征的数学理论和方法。它不仅作为现代数学的一个崭新分支熠熠生辉，更是运筹学领域的重要一环。第八章对策论齐王策略α|齐王的赢得|田忌策略ββ1（上中下）α2（上下中）α3（中上下）α4（中下上）α5（下中上）α6（下上中）α1（上中下）31111-1α2（上下中）1311-11α3（中上下）1