供应链系统优化方法,南京林业大学 彭红军 邮箱：armyp163.com,Chapter1 线性规划 (Linear Programming),LP的数学模型 图解法 LP模型的应用,本讲主要内容：,线性规划问题的数学模型,1. 规划问题,生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。,线性规划通常解决下列两类问题：,（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源 （如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标.,（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多 、利润最大）.,线性规划问题的数学模型,例1.1 某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？,线性规划问题的数学模型,解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：,线性规划问题的数学模型,2. 线性规划的数学模型由三个要素构成,决策变量 Decision variables 目标函数 Objective function 约束条件 Constraints,其特征是： （1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值； （2）问题的约束条件是一组多个决策变量的线性不等式或等式。,怎样辨别一个模型是线性规划模型？,线性规划问题的数学模型,目标函数：,约束条件：,3. 线性规划数学模型的一般形式,简写为：,线性规划模型的应用,一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。,要求解问题的目标函数能用数值指标来反映，且为线性函数 存在着多种方案 要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述,线性规划在管理中的应用,人力资源分配问题,例1.2 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：,设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少?,线性规划在管理中的应用,解：设xi表示第i班次时开始上班的司机和乘务人员人数。,此问题最优解：x150， x220， x350， x40， x520， x610，一共需要司机和乘务员150人。,线性规划在管理中的应用,生产计划问题,例1.3 某厂生产、三种产品，都分别经A、B两道工序加工。设A工序可分别在设备A1和A2上完成，有B1、B2、B3三种设备可用于完成B工序。已知产品可在A、B任何一种设备上加工；产品可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品只能在A2与B2设备上加工。加工单位产品所需工序时间及其他各项数据如下表，试安排最优生产计划，使该厂获利最大。,线性规划在管理中的应用,线性规划在管理中的应用,解：设xijk表示产品i在工序j的设备k上加工的数量。约束条件有：,线性规划在管理中的应用,目标是利润最大化，即利润的计算公式如下：,带入数据整理得到：,线性规划在管理中的应用,因此该规划问题的模型为：,LINGO软件求解线性规划,LINGO软件求解线性规划,实际问题中的线性规划模型,大型煤炭企业生产和供给问题 （Peng Hong-jun, Zhou Mei-hua. A Dynamic Optimization Model of an integrated Coal Supply Chain System and Its Application，Mining Science and Technology, 2009，19(6):842-846. (EI检索) ) 供应链是一种新的企业组织形态和运营方式,包括从客户需求开始经过原材料供应、生产批发零售等环节,到最后把产品送到最终用户的各项制造和商业活动。机电等供应物流运输客户市场原煤开配采洗选加工、配煤煤炭销售大型煤炭企业内部供应链物流/供应信息流资金流/需求信息流图1大型煤炭企业供应链框架,煤炭供应链中物流从上游向下游流动, 资金流从下游向上游流动, 而信息流的流动则是双向的。以上游供应企业作为大型煤炭企业原料供应商, 以煤炭企业作为原煤及精煤生产商, 再通过运输环节到达用户, 形成以物流为主线, 包括信息流及资金流的输入输出关系的煤炭供应链框架, 如图1所示。图中包含原煤开配采、煤炭洗选加工、煤炭销售等节点并用实线框起来，为大型煤炭企业供给系统内部供应链。大型煤炭企业的原煤开采、煤炭洗选加工和客户均为多点。,徐州矿务集团共11个矿井，其中9个矿井建有洗煤厂，各矿井生产情况如表1, 该企业有5个主要客户，各客户需求情况见表2。 煤炭企业除了追求整理利润外，还应该考虑客户满意度因素，特别是要尽量提高一些长期重要客户的满意度，以保证企业的可持续发展。影响煤炭企业客户满意度的因素主要有商品煤数量订单满足率、企业供给客户的商品煤质量等。请建立同时考虑利润和客户满意度的煤炭企业生产和供给的一般模型，并用模型对所给煤炭企业进行生产和供给决策。,表 徐州矿务集团各矿井生产情况表,表 徐州矿务集团客户需求情况,令i为矿井序号,i=1,2,I; j 为选煤厂序号，j=1,2,J; k 为客户序号，k=1,2,K;n为商品煤序号;n=1,2, ,N，不妨设主要洗选产品（精煤）序号为1，原煤序号为N.,复杂煤炭供应链系统矿井节点分析,输入变量： (%)为矿井i的原煤灰分,(吨) 为矿井i原煤生产能力。,决策变量： (吨)为矿井i原煤产量.,原煤生产能力约束：,复杂煤炭供应链系统洗煤厂节点分析输入变量：,（%）为洗煤厂j 生产的n种商品煤的灰分；,(吨) 为选煤厂j洗配能力；,(%) 为选煤厂j入洗原煤灰分。 决策变量：,（吨）选煤厂j入洗原煤量；,（%）为矿洗煤厂j对n种商品煤的产率。 洗煤厂洗选能力约束：,煤厂主要洗选产品产率与入洗原煤灰分和其他洗选产品产率有负相关关系，可以通过洗煤厂历史洗煤数据，用多元线性回归法建立各洗煤厂主要洗选产品产出率模型，则：,复杂煤炭供应链系统客户端需求分析 用户对煤炭的需求，不仅是煤炭品种和数量的要求，而且还有煤炭产品质量的要求，随着煤炭行业市场竞争态势的变化和客户导向意识的增强，煤炭企业需要关注和满足煤炭用户多方面的需求。,输入变量：,(吨) 为客户k对n种商品煤需求量；,(元/吨) 为客户k购买n种商品煤协议价格；,(%) 为煤炭企业确定的对客户k的n种商品煤最低的订单满足率；,（%）为煤炭企业向客户k销售的n种商品煤灰分标准.,复杂煤炭供应链系统物流分析输入变量：,（%)表示外购的l种商品煤的灰分,(吨)为煤矿企业供应链系统对外运输能力.,(吨) 为矿井i运往选煤厂 j的待洗原煤量,(吨) 为矿井i运往客户k的原煤量,（吨）为洗煤厂j运往客户k的n商品煤数量，n=1,2,N-1,(吨)为外购n种商品煤数量,(吨) 为外购n种商品煤运往客户k的数量,为运往客户k的外购煤数量,(吨)企业销售给客户k 的n种商品煤数量.,决策变量：,矿井原煤生产量公式：,洗煤厂原煤入洗量公式：,煤炭销售公式：,外购煤公式：,运输能力约束：,客户需求数量约束：,客户需求质量约束（灰分）：,复杂煤炭供应链资金流分析,(元/吨) 矿井i到选煤厂j单位重量运输成本,(元/吨)矿井i到客户k单位重量运输成本,(元/吨) 选煤厂j到客户k单位重量运输成本,(元/吨) 为外购n种商品煤报价,(元/吨)外购煤到客户k的单位重量运输成本,(元/吨) 为矿井i生产单位原煤成本,(元/吨) 为选煤厂j选洗单位原煤成本.,输入变量：,生产成本：,运输成本：,外购煤成本：,煤炭销售收入：,煤炭企业供应链系统资金流净值利润:,客户端是煤炭供应链系统信息流的来源，是煤炭企业供应链系统的决策的依据。煤炭企业决策目标除了系统经济利润最大化外,还要考虑客户满意度目标,利于企业可持续发展.论文通过确定不同客户相应的最低订单满足率和最低质量保证的方法, 建立煤炭供应链系统线性规划决策模型：,求解结果,根据该企业供应链原煤生产,洗选加工,运输情况以及客户需求等信息,建立该企业的供应链系统的动态优化模型,其中决策变量300余个. LINGO软件是用来求解线性和非线性优化问题的简易工具.用LINGO软件求解该模型,得出企业原煤生产、洗煤加工、运输和销售等系列决策，表中列出了该矿务集团内部供应链原煤生产和洗选生产等优化决策方案：,表 徐州矿务集团内部供应链系统优化决策,表 徐州矿务集团销售优化决策,Chapter2 运输规划 ( Transportation Problem ),运输规划问题的数学模型 运输问题的应用,本章主要内容：,运输规划问题的数学模型,例2.1 某公司从两个产地A1、A2将物品运往三个销地B1, B2, B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,运输规划问题的数学模型,解：产销平衡问题：总产量 = 总销量500 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表：,Min C = 6x11+ 4x12+ 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个销地；ai 表示产地Ai的产量； bj 表示销地Bj 的销量； cij 表示把物资从产地Ai运往销地Bj的单位运价。设 xij 为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型：,运输规划问题的数学模型,变化： 1）有时目标函数求最大。如求利润最大或营业额最大等； 2）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束)； 3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。,定理: 设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。,运输问题的应用,求极大值问题 目标函数求利润最大或营业额最大等问题。,运输问题的应用,例2.2 下列矩阵C是Ai（I=1，2，3）到Bj的吨公里利润,运输部门如何安排运输方案使总利润最大.,运输问题的应用,产销不平衡的运输问题 当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到。,当产大于销时，即：,数学模型为：,运输问题的应用,由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟销地Bn+1， bn+1作为一个虚设销地Bn+1的销量(即库存量)。各产地Ai到Bn+1的运价为零，即Ci,n+1=0,（i=1，m）。则平衡问题的数学模型为：,具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可,运输问题的应用,当销大于产时，即：,数学模型为：,由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为：,运输问题的应用,销大于产化为平衡问题的数学模型为 ：,具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。,运输问题的应用,例2.3 求下列表中极小化运输问题的最优解。,因为有：,运输问题的应用,所以是一个产大于销的运输问题。表中A2不可达B1，用一个很大的正数M表示运价C21