供应链系统优化方法演示文稿

供应链系统优化方法演示文稿目前一页\总数一百四十五页\编于十一点Chapter1线性规划

(LinearProgramming)LP的数学模型图解法LP模型的应用本讲主要内容：目前二页\总数一百四十五页\编于十一点线性规划问题的数学模型1.规划问题生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。线性规划通常解决下列两类问题：（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标.（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大）.目前三页\总数一百四十五页\编于十一点线性规划问题的数学模型例1.1某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？设备产品ABCD利润（元）甲21402乙22043有效台时1281612目前四页\总数一百四十五页\编于十一点线性规划问题的数学模型解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12目前五页\总数一百四十五页\编于十一点线性规划问题的数学模型2.线性规划的数学模型由三个要素构成决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints其特征是：（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式。怎样辨别一个模型是线性规划模型？目前六页\总数一百四十五页\编于十一点线性规划问题的数学模型目标函数：约束条件：3.线性规划数学模型的一般形式简写为：目前七页\总数一百四十五页\编于十一点线性规划模型的应用 一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。要求解问题的目标函数能用数值指标来反映，且为线性函数存在着多种方案要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述目前八页\总数一百四十五页\编于十一点线性规划在管理中的应用人力资源分配问题例1.2某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：班次时间所需人员16:00——10:0060210:00——14:0070314:00——18:0060418:00——22:0050522:00——2:002062:00——6:0030设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少?目前九页\总数一百四十五页\编于十一点线性规划在管理中的应用解：设xi表示第i班次时开始上班的司机和乘务人员人数。此问题最优解：x1＝50，x2＝20，x3＝50，x4＝0，x5＝20，x6＝10，一共需要司机和乘务员150人。目前十页\总数一百四十五页\编于十一点线性规划在管理中的应用生产计划问题 例1.3某厂生产Ⅰ、Ⅱ、Ⅲ三种产品，都分别经A、B两道工序加工。设A工序可分别在设备A1和A2上完成，有B1、B2、B3三种设备可用于完成B工序。已知产品Ⅰ可在A、B任何一种设备上加工；产品Ⅱ可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品Ⅲ只能在A2与B2设备上加工。加工单位产品所需工序时间及其他各项数据如下表，试安排最优生产计划，使该厂获利最大。目前十一页\总数一百四十五页\编于十一点线性规划在管理中的应用设备产品设备有效台时设备加工费（元/小时）ⅠⅡⅢ27910000321B168124000250B247000783B37114000200原料费（万元/每件）0.250.350.5售价（万元/每件）1.252.002.8目前十二页\总数一百四十五页\编于十一点线性规划在管理中的应用解：设xijk表示产品i在工序j的设备k上加工的数量。约束条件有：目前十三页\总数一百四十五页\编于十一点线性规划在管理中的应用目标是利润最大化，即利润的计算公式如下：带入数据整理得到：目前十四页\总数一百四十五页\编于十一点线性规划在管理中的应用因此该规划问题的模型为：目前十五页\总数一百四十五页\编于十一点LINGO软件求解线性规划目前十六页\总数一百四十五页\编于十一点LINGO软件求解线性规划目前十七页\总数一百四十五页\编于十一点实际问题中的线性规划模型大型煤炭企业生产和供给问题（PengHong-jun,ZhouMei-hua.ADynamicOptimizationModelofanintegratedCoalSupplyChainSystemandItsApplication，MiningScienceandTechnology,2009，19(6):842-846.(EI检索))

供应链是一种新的企业组织形态和运营方式,包括从客户需求开始经过原材料供应、生产批发零售等环节,到最后把产品送到最终用户的各项制造和商业活动。机电等供应物流运输客户市场原煤开配采洗选加工、配煤煤炭销售大型煤炭企业内部供应链物流/供应信息流资金流/需求信息流图1大型煤炭企业供应链框架．目前十八页\总数一百四十五页\编于十一点煤炭供应链中物流从上游向下游流动,资金流从下游向上游流动,而信息流的流动则是双向的。以上游供应企业作为大型煤炭企业原料供应商,以煤炭企业作为原煤及精煤生产商,再通过运输环节到达用户,形成以物流为主线,包括信息流及资金流的输入输出关系的煤炭供应链框架,如图1所示。图中包含原煤开配采、煤炭洗选加工、煤炭销售等节点并用实线框起来，为大型煤炭企业供给系统内部供应链。大型煤炭企业的原煤开采、煤炭洗选加工和客户均为多点。目前十九页\总数一百四十五页\编于十一点供应商物流运输客户市场原煤开配采洗选加工煤炭销售复杂煤炭企业内部供应链物流/供应信息流资金流/需求信息流图1复杂煤炭企业多层供应链框架外购煤目前二十页\总数一百四十五页\编于十一点徐州矿务集团共11个矿井，其中9个矿井建有洗煤厂，各矿井生产情况如表1,该企业有5个主要客户，各客户需求情况见表2。煤炭企业除了追求整理利润外，还应该考虑客户满意度因素，特别是要尽量提高一些长期重要客户的满意度，以保证企业的可持续发展。影响煤炭企业客户满意度的因素主要有商品煤数量订单满足率、企业供给客户的商品煤质量等。请建立同时考虑利润和客户满意度的煤炭企业生产和供给的一般模型，并用模型对所给煤炭企业进行生产和供给决策。目前二十一页\总数一百四十五页\编于十一点表徐州矿务集团各矿井生产情况表矿井名称原煤能力（吨）原煤成本（元/吨）洗煤能力（吨）洗煤成本（元/吨）洗煤产品宅城850003040----夹河1100003459600025冶炼精煤、混煤庞庄22500031011000022冶炼精煤、混煤韩桥650003080----三河尖560002983000038冶炼精煤、混煤卧牛山180003161600030其他类炼焦精煤、混煤张双楼1180003071800023其他类炼焦精煤、混煤权台1660002895000017其他类炼焦精煤、混煤旗山1480002939000018其他类炼焦精煤、混煤义安330003693000028其他类炼焦精煤、混煤张集870003933500032其他类炼焦精煤、混煤合计1111000--475000--其他类炼焦精煤、混煤目前二十二页\总数一百四十五页\编于十一点

表徐州矿务集团客户需求情况序号原煤冶炼精煤其他精煤混煤最低订单满足率需求量价格需求量价格需求量价格需求量价格12500004500--0--1000005200.820--800006500--800005300.630--60000670800007000--0.641000004600--60000720600005450.55600004700--30000750400005600合计410000140000170000280000目前二十三页\总数一百四十五页\编于十一点令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软件求解该模型,得出企业原煤生产、洗煤加工、运输和销售等系列决策，表中列出了该矿务集团内部供应链原煤生产和洗选生产等优化决策方案：目前三十四页\总数一百四十五页\编于十一点表徐州矿务集团内部供应链系统优化决策矿井名称原煤产量入洗原煤量商品原煤量冶炼精煤量其他精煤量混煤产量宅城85000--85000----夹河9600096000057814--2139庞庄2250001100001150000--85750韩桥17000--17000----0三河尖47000300004700026186--0卧牛山180001600018000--125230张双-151980权台16600050000116000--412430旗山1480009000058000--587700义安30000300000--028241张集35000350000--262600合计88500047500041000084000153994116130目前三十五页\总数一百四十五页\编于十一点表徐州矿务集团销售优化决策客户序号原煤销售量冶炼精煤销售量其他精煤销售量洗混煤销售量1250000----800002--48000--480003--3600063994--4100000--6000030000560000--300000合计41000084000153994158000目前三十六页\总数一百四十五页\编于十一点Chapter2运输规划

(TransportationProblem)运输规划问题的数学模型运输问题的应用本章主要内容：目前三十七页\总数一百四十五页\编于十一点运输规划问题的数学模型例2.1某公司从两个产地A1、A2将物品运往三个销地B1,B2,B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？B1B2B3产量A1646200A2655300销量150150200目前三十八页\总数一百四十五页\编于十一点运输规划问题的数学模型解：产销平衡问题：总产量=总销量＝500设xij为从产地Ai运往销地Bj的运输量，得到下列运输量表：B1B2B3产量A1x11x12x13200A2x21x22x23300销量150150200MinC=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥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的吨公里利润,运输部门如何安排运输方案使总利润最大.销地产地B1B2B3产量A12589A2910710A365412销量8149目前四十三页\总数一百四十五页\编于十一点运输问题的应用产销不平衡的运输问题 当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到。当产大于销时，即：数学模型为：目前四十四页\总数一百四十五页\编于十一点运输问题的应用由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟销地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求下列表中极小化运输问题的最优解。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20603545180160因为有：目前四十八页\总数一百四十五页\编于十一点运输问题的应用所以是一个产大于销的运输问题。表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180-160=20，Ci5=0，i=1,2,3,4，表的右边增添一列，得到新的运价表。B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180目前四十九页\总数一百四十五页\编于十一点运输问题的应用下表为计算结果。可看出：产地A4还有20个单位没有运出。B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180目前五十页\总数一百四十五页\编于十一点运输问题的应用3.生产与储存问题例2.4某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。季度生产能力/台单位成本/万元Ⅰ2510.8Ⅱ3511.1Ⅲ3011Ⅳ1011.3目前五十一页\总数一百四十五页\编于十一点运输问题的应用解：设xij为第i季度生产的第j季度交货的柴油机数目，那么应满足：交货：x11=10生产：x11+x12+x13+x14≤25

x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10目标：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x44

把第i季度生产的柴油机数目看作第i个生产厂的产量；把第j季度交货的柴油机数目看作第j个销售点的销量。构造下列产销平衡问题：目前五十二页\总数一百四十五页\编于十一点运输问题的应用jiⅠⅡⅢⅣ产量Ⅰ10.810.9511.111.2525ⅡM11.1011.2511.4035ⅢMM11.0011.1530ⅣMMM11.3010销量1015252010070由于产大于销，加上一个虚拟的销地D，化为平衡问题，即可应用表上作业法求解。目前五十三页\总数一百四十五页\编于十一点运输问题的应用该问题的运输平衡表：jiⅠⅡⅢⅣD产量Ⅰ10.810.9511.111.25025ⅡM11.1011.2511.40035ⅢMM11.0011.15030ⅣMMM11.30010销量1015252030100100目前五十四页\总数一百四十五页\编于十一点运输问题的应用jiⅠⅡⅢⅣD产量Ⅰ1015025Ⅱ053035Ⅲ25530Ⅳ1010销量1015252030100100最优生产决策如下表，最小费用z＝773万元。目前五十五页\总数一百四十五页\编于十一点下面给出一些例题，可作为建模的练习：例2.5石家庄北方研究院有一、二、三，三个区。每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价如下表。由于需大于供，经院研究决定一区供应量可减少0--400吨，二区必须满足需求量，三区供应量不少于1700吨，试求总费用为最低的调运方案。运输问题例题目前五十六页\总数一百四十五页\编于十一点运输问题例题解：根据题意，作出产销平衡与运价表，取M代表一个很大的正数，其作用是强迫相应的x31、x33、x34取值为0。目前五十七页\总数一百四十五页\编于十一点LINGO软件求解运输规划目前五十八页\总数一百四十五页\编于十一点LINGO软件求解运输规划目前五十九页\总数一百四十五页\编于十一点Chapter3整数规划

(IntegerProgramming)整数规划的特点及应用本章主要内容：目前六十页\总数一百四十五页\编于十一点整数规划的特点及应用整数规划（简称：IP） 要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。整数线性规划数学模型的一般形式：目前六十一页\总数一百四十五页\编于十一点整数规划的特点及应用整数线性规划问题的种类：纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。0-1型整数线性规划：决策变量只能取值0或1的整数线性规划。目前六十二页\总数一百四十五页\编于十一点如1.变量是人数、机器设备台数或产品件数等都要求是整数2.对某一个项目要不要投资的决策问题，可选用一个逻辑变量x，当x=1表示投资，x=0表示不投资；3.人员的合理安排问题，当变量xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去做j工作。逻辑变量也是只允许取整数值的一类变量。整数规划的特点及应用目前六十三页\总数一百四十五页\编于十一点整数规划的特点及应用整数规划的典型例子例3.1工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij，见下表：B1B2B3B4年生产能力A12934400A28357600A37612200A44525200年需求量350400300150工厂A3或A4开工后，每年的生产费用估计分别为1200万或1500万元。现要决定应该建设工厂A3还是A4，才能使今后每年的总费用最少。目前六十四页\总数一百四十五页\编于十一点整数规划的特点及应用解：这是一个物资运输问题，特点是事先不能确定应该建A3还是A4中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入0-1变量：再设xij为由Ai运往Bj的物资数量，单位为千吨；z表示总费用，单位万元。则该规划问题的数学模型可以表示为：目前六十五页\总数一百四十五页\编于十一点整数规划的特点及应用混合整数规划问题目前六十六页\总数一百四十五页\编于十一点整数规划的特点及应用例3.2现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj（j＝1,2,..,n），此外由于种种原因，有三个附加条件：若选择项目1，就必须同时选择项目2。反之不一定项目3和4中至少选择一个；项目5,6,7中恰好选择2个。应该怎样选择投资项目，才能使总预期收益最大。目前六十七页\总数一百四十五页\编于十一点整数规划的特点及应用解：对每个投资项目都有被选择和不被选择两种可能，因此分别用0和1表示，令xj表示第j个项目的决策选择，记为：投资问题可以表示为：目前六十八页\总数一百四十五页\编于十一点整数规划的特点及应用例3.3指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。工作人员ABCD甲85927390乙95877895丙82837990丁86908088目前六十九页\总数一百四十五页\编于十一点整数规划的特点及应用设数学模型如下：要求每人做一项工作，约束条件为：目前七十页\总数一百四十五页\编于十一点整数规划的特点及应用每项工作只能安排一人，约束条件为：变量约束：目前七十一页\总数一百四十五页\编于十一点整数规划与LINGO软件目前七十二页\总数一百四十五页\编于十一点整数规划与LINGO软件目前七十三页\总数一百四十五页\编于十一点整数规划与LINGO软件目前七十四页\总数一百四十五页\编于十一点【例3.4】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表4-1所示。问两种物品各装多少件，所装物品的总价值最大？表4-1【解】设甲、乙两种物品各装x1、x2件，则数学模型为：(4.1)物品重量（公斤/每件）体积（m3/每件）价值(元/每件)甲乙1.20.80.0020.002543整数规划应用目前七十五页\总数一百四十五页\编于十一点【例3.5】在例4.10中，假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02m3。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品价值最大。（1）所装物品不变；（2）如果选择旅行箱，则只能装载丙和丁两种物品，价值分别是4和3，载重量和体积的约束为整数规划应用目前七十六页\总数一百四十五页\编于十一点【解】此问题可以建立两个整数规划模型，但用一个模型描述更简单。引入0－1变量（或称逻辑变量）yi，令i=1,2分别是采用背包及旅行箱装载。整数规划应用目前七十七页\总数一百四十五页\编于十一点（1）

由于所装物品不变，式(4.1)约束左边不变，整数规划数学模型为整数规划应用目前七十八页\总数一百四十五页\编于十一点（2）

由于不同载体所装物品不一样，数学模型为整数规划应用目前七十九页\总数一百四十五页\编于十一点【例3.6】企业计划生产4000件某种产品，该产品可自己加工、外协加工任意一种形式生产．已知每种生产的固定费用、生产该产品的单件成本以及每种生产形式的最大加工数量（件）限制如表4－2所示，怎样安排产品的加工使总成本最小．表4－2固定成本（元）变动成本（元／件）最大加工数（件）本企业加工50081500外协加工Ⅰ80052000外协加工Ⅱ6007不限整数规划应用目前八十页\总数一百四十五页\编于十一点【解】设xj为采用第j（j=1,2,3）种方式生产的产品数量，生产费用为整数规划应用式中kj是固定成本，cj是单位产品成本．设0－1变量yj，令目前八十一页\总数一百四十五页\编于十一点数学模型为

上式中是处理xj与yj一对变量之间逻辑关系的特殊约束，当xj>0时yj=1,当xj＝0时，为使Z最小化，有yj=0。整数规划应用目前八十二页\总数一百四十五页\编于十一点Chapter4目标规划

(Goalprogramming)目标规划问题及其数学模型目标规划应用举例本章主要内容：目前八十三页\总数一百四十五页\编于十一点目标规划问题及其数学模型问题的提出： 目标规划是在线性规划的基础上，为适应经济管理多目标决策的需要而由线性规划逐步发展起来的一个分支。 由于现代化企业内专业分工越来越细，组织机构日益复杂，为了统一协调企业各部门围绕一个整体的目标工作，产生了目标管理这种先进的管理技术。目标规划是实行目标管理的有效工具，它根据企业制定的经营目标以及这些目标的轻重缓急次序，考虑现有资源情况，分析如何达到规定目标或从总体上离规定目标的差距为最小。目前八十四页\总数一百四十五页\编于十一点线性规划模型的特征是在满足一组约束条件下，寻求一个目标的最优解（最大值或最小值）。而在现实生活中最优只是相对的，或者说没有绝对意义下的最优，只有相对意义下的满意。1978年诺贝尔经济学奖获得者.西蒙(H.A.Simon-美国卡内基-梅隆大学,1916-)教授提出“满意行为模型要比最大化行为模型丰富得多”，否定了企业的决策者是“经济人”概念和“最大化”行为准则，提出了“管理人”的概念和“令人满意”的行为准则，对现代企业管理的决策科学进行了开创性的研究

目标规划问题及其数学模型目前八十五页\总数一百四十五页\编于十一点目标规划问题及其数学模型例4.1某企业计划生产甲，乙两种产品，这些产品分别要在A,B,C,D四种不同设备上加工。按工艺文件规定，如表所示。ABCD单件利润甲11402乙22043最大负荷1281612问该企业应如何安排计划，使得计划期内的总利润收入为最大？目前八十六页\总数一百四十五页\编于十一点目标规划问题及其数学模型解：设甲、乙产品的产量分别为x1，x2，建立线性规划模型：其最优解为x1＝4，x2＝2，z＊＝14元目前八十七页\总数一百四十五页\编于十一点目标规划问题及其数学模型但企业的经营目标不仅仅是利润，而且要考虑多个方面，如：力求使利润指标不低于12元；考虑到市场需求，甲、乙两种产品的生产量需保持1:1的比例；C和D为贵重设备，严格禁止超时使用；设备B必要时可以加班，但加班时间要控制；设备A即要求充分利用，又尽可能不加班。要考虑上述多方面的目标，需要借助目标规划的方法。目前八十八页\总数一百四十五页\编于十一点目标规划问题及其数学模型线性规划模型存在的局限性：1）要求问题的解必须满足全部约束条件，实际问题中并非所有约束都需要严格满足。2）只能处理单目标的优化问题。实际问题中，目标和约束可以相互转化。3）线性规划中各个约束条件都处于同等重要地位，但现实问题中，各目标的重要性即有层次上的差别，同一层次中又可以有权重上的区分。4）线性规划寻求最优解，但很多实际问题中只需找出满意解就可以。目前八十九页\总数一百四十五页\编于十一点目标规划问题及其数学模型目标规划怎样解决上述线性规划模型建模中的局限性？1.设置偏差变量，用来表明实际值同目标值之间的差异。偏差变量用下列符号表示：d+——超出目标的偏差，称正偏差变量d-——未达到目标的偏差，称负偏差变量正负偏差变量两者必有一个为0。当实际值超出目标值时：d+>0,d-=0;当实际值未达到目标值时：d+=0,d->0;当实际值同目标值恰好一致时：d+=0,d-=0;故恒有d+×d-=0目前九十页\总数一百四十五页\编于十一点目标规划问题及其数学模型2.统一处理目标和约束。对有严格限制的资源使用建立系统约束，数学形式同线性规划中的约束条件。如C和D设备的使用限制。对不严格限制的约束，连同原线性规划建模时的目标，均通过目标约束来表达。1）例如要求甲、乙两种产品保持1:1的比例，系统约束表达为：x1=x2。由于这个比例允许有偏差，当x1<x2时，出现负偏差d-，即：x1+d-

=x2或x1－x2+d-

=0当x1>x2时，出现正偏差d+，即：x1-d+

=x2或x1－x2-d+

=0目前九十一页\总数一百四十五页\编于十一点目标规划问题及其数学模型∵正负偏差不可能同时出现，故总有：x1－x2+d--d+

=0若希望甲的产量不低于乙的产量，即不希望d->0,用目标约束可表为:若希望甲的产量低于乙的产量，即不希望d＋>0,用目标约束可表为:若希望甲的产量恰好等于乙的产量，即不希望d＋>0,也不希望d->0用目标约束可表为:目前九十二页\总数一百四十五页\编于十一点目标规划问题及其数学模型3）设备B必要时可加班及加班时间要控制，目标约束表示为：2）力求使利润指标不低于12元，目标约束表示为：4）设备A既要求充分利用，又尽可能不加班，目标约束表示为：目前九十三页\总数一百四十五页\编于十一点目标规划问题及其数学模型3.目标的优先级与权系数 在一个目标规划的模型中，为达到某一目标可牺牲其他一些目标，称这些目标是属于不同层次的优先级。优先级层次的高低可分别通过优先因子P1,P2,…表示。对于同一层次优先级的不同目标，按其重要程度可分别乘上不同的权系数。权系数是一个个具体数字，乘上的权系数越大，表明该目标越重要。现假定：第1优先级P1——企业利润；第2优先级P2——甲乙产品的产量保持1:1的比例第3优先级P3——设备A,B尽量不超负荷工作。其中设备A的重要性比设备B大三倍。目前九十四页\总数一百四十五页\编于十一点目标规划问题及其数学模型上述目标规划模型可以表示为：目前九十五页\总数一百四十五页\编于十一点目标规划问题及其数学模型目标规划数学模型的一般形式达成函数目标约束其中：gk为第k个目标约束的预期目标值，和为pl优先因子对应各目标的权系数。目前九十六页\总数一百四十五页\编于十一点【例4.2】最优生产计划问题。某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要要在设备A、B上加工，需要消耗材料C、D，按工艺资料规定，单件产品在不同设备上加工及所需要的资源如表5.1所示。已知在计划期内设备的加工能力各为200台时，可供材料分别为360、300公斤；每生产一件甲、乙、丙三种产品，企业可获得利润分别为40、30、50元，假定市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？目标规划问题及其数学模型目前九十七页\总数一百四十五页\编于十一点产品

资源甲

乙丙现有资源设备A312200设备B224200材料C451360材料D235300利润（元/件）403050表5.1产品资源消耗目标规划问题及其数学模型目前九十八页\总数一百四十五页\编于十一点最优解X＝（50，30，10），Z＝3400目标规划问题及其数学模型目前九十九页\总数一百四十五页\编于十一点

现在决策者根据企业的实际情况和市场需求，需要重新制定经营目标，其目标的优先顺序是：（1）利润不少于3200元（2）产品甲与产品乙的产量比例尽量不超过1.5（3）提高产品丙的产量使之达到30件（4）设备加工能力不足可以加班解决，能不加班最好不加班（5）受到资金的限制，只能使用现有材料不能再购进【解】设甲、乙、丙产品的产量分别为x1、x2、x3。如果按线性规划建模思路，最优解实质是求下列一组不等式的解目标规划问题及其数学模型目前一百页\总数一百四十五页\编于十一点目标规划问题及其数学模型目前一百零一页\总数一百四十五页\编于十一点通过计算不等式无解，即使设备加班10小时仍然无解．在实际生产过程中生产方案总是存在的，无解只能说明在现有资源条件下，不可能完全满足所有经营目标．这种情形是按事先制定的目标顺序逐项检查，尽可能使得结果达到预定目标，即使不能达到目标也使得离目标的差距最小，这就是目标规划的求解思路，对应的解称为满意解．下面建立例4.1的目标规划数学模型．目标规划问题及其数学模型目前一百零二页\总数一百四十五页\编于十一点设d1-未达到利润目标的差值,d1+为超过目标的差值当利润小于3200时,d1－＞０且d1＋＝0,有40x1+30x2+50x3+d1－=3200成立当利润大于3200时，d1＋＞０且d1－＝０，有40x1+30x2+50x3-d1+=3200成立当利润恰好等于3200时，d1－=０且d1+=0,有40x1+30x2+50x3=3200成立实际利润只有上述三种情形之一发生，因而可以将三个等式写成一个等式40x1+30x2+50x3+d1－－d1+=3200目标规划问题及其数学模型目前一百零三页\总数一百四十五页\编于十一点（2）设分别为未达到和超过产品比例要求的偏差变量,则产量比例尽量不超过1.5的数学表达式为：（3）设d3ˉ、d３＋分别为品丙的产量未达到和超过30件的偏差变量，则产量丙的产量尽可能达到30件的数学表达式为：（1）利润不少于3200理解为达到或超过3200，即使不能达到也要尽可能接近3200,可以表达成目标函数｛d1－｝取最小值，则有目标规划问题及其数学模型目前一百零四页\总数一百四十五页\编于十一点（4）

设d4ˉ

、d4+为设备A的使用时间偏差变量,d5ˉ、d5+为设备B的使用时间偏差变量，最好不加班的含义是d4+和d5+同时取最小值，等价于d4++d5+取最小值，则设备的目标函数和约束为：（5）材料不能购进表示不允许有正偏差，约束条件为小于等于约束．目标规划问题及其数学模型目前一百零五页\总数一百四十五页\编于十一点式中：Pj（j=1,2,3,4）称为目标的优先因子，第一目标优于第二目标，第二目标优于第三目标等等，其含义是按P1、P2、…的次序分别求后面函数的最小值.由于目标是有序的并且四个目标函数非负，因此目标函数可以表达成一个函数：目标规划问题及其数学模型目前一百零六页\总数一百四十五页\编于十一点则问题的目标规划数学模型为：目标规划问题及其数学模型目前一百零七页\总数一百四十五页\编于十一点约束实际偏差目标1C13220=32002C2－2=03C330=304C4164=2005C5216=2006C6242－118<=3607C7266－34<=3001X1282X2203X3304d1-05d1+206d2-27d2+08d3-09d3+010d4-3611d4+012d5-013d5+16满意解：约束分析：目前一百零八页\总数一百四十五页\编于十一点（1）目标规划数学模型的形式有：线性模型、非线性模型、整数模型、交互作用模型等（2）一个目标中的两个偏差变量di-、di+至少一个等于零，偏差变量向量的叉积等于零：d－×d＋=0（3）一般目标规划是将多个目标函数写成一个由偏差变量构成的函数求最小值，按多个目标的重要性，确定优先等级，顺序求最小值说明目标规划问题及其数学模型目前一百零九页\总数一百四十五页\编于十一点（4）按决策者的意愿，事先给定所要达到的目标值当期望结果不超过目标值时，目标函数求正偏差变量最小;当期望结果不低于目标值时，目标函数求负偏差变量最小;当期望结果恰好等于目标值时，目标函数求正负偏差变量之和最小目标规划问题及其数学模型目前一百一十页\总数一百四十五页\编于十一点（5）由目标构成的约束称为目标约束，目标约束具有更大的弹性，允许结果与所制定的目标值存在正或负的偏差，如例1中的5个等式约束；如果决策者要求结果一定不能有正或负的偏差，这种约束称为系统约束，如例1的材料约束；（6）目标的排序问题。多个目标之间有相互冲突时，决策者首先必须对目标排序。排序的方法有两两比较法、专家评分等方法，构造各目标的权系数，依据权系数的大小确定目标顺序；目标规划问题及其数学模型目前一百一十一页\总数一百四十五页\编于十一点（7）合理的确定目标数。目标规划的目标函数中包含了多个目标，决策者对于具有相同重要性的目标可以合并为一个目标，如果同一目标中还想分出先后次序，可以赋予不同的权系数，按系数大小再排序。例如，在例1中要求设备B的加班时间不超过设备A的时间，目标函数可以表达为,表示在中先求最小再求最小。目标规划问题及其数学模型目前一百一十二页\总数一百四十五页\编于十一点（8）多目标决策问题．多目标决策研究的范围比较广泛，在决策中，可能同时要求多个目标达到最优．例如，企业在对多个项目投资时期望收益率尽可能最大，投资风险尽可能最小，属于多目标决策问题，本章的目标规划尽管包含有多个目标，但还是按单个目标求偏差变量的最小值，目标函数中不含有决策变量，目标规划只是多目标决策的一种特殊情形．目标规划问题及其数学模型目前一百一十三页\总数一百四十五页\编于十一点（9）目标规划的一般模型．设xj（j=1,2,…,n）为决策变量式中pk为第k级优先因子,k=1、2、……K；wkl-、wkl+，为分别赋予第l个目标约束的正负偏差变量的权系数；gl为目标的预期目标值，l=1,…L．(4.1b)为系统约束,（4.1c）为目标约束目标规划问题及其数学模型目前一百一十四页\总数一百四十五页\编于十一点【例4.3】车间计划生产I、II两种产品，每种产品均需经过A、B两道工序加工．工艺资料如表4－3所示．产品工序产品甲产品乙每天加工能力(小时)A22120B12100C2.20.890产品售价(元/件)5070产品利润(元/件)108（1）车间如何安排生产计划，使产值和利润都尽可能高（2）如果认为利润比产值重要，怎样决策表5-3目标规划问题及其数学模型目前一百一十五页\总数一百四十五页\编于十一点【解】设x1、x2分别为产品甲和产品乙的日产量，得到线性多目标规划模型：目标规划问题及其数学模型目前一百一十六页\总数一百四十五页\编于十一点（1）将模型化为目标规划问题．首先，通过分别求产值最大和利润最大的线性规划最优解．产值最大的最优解：X(1)＝（20，40），Z1＝3800利润最大的最优解：X(2)＝（30，30），Z2＝540目标确定为产值和利润尽可能达到3800和540，得到目标规划数学模型：目标规划问题及其数学模型目前一百一十七页\总数一百四十五页\编于十一点．,等价于（2）给d2-赋予一个比d1-的系数大的权系数,如，约束条件不变.权系数的大小依据重要程度给定，或者根据同一优先级的偏差变量的关系给定，例如，当利润d2-减少一个单位时，产值d1-减少3个单位，则赋予d2-权系数3，则目标函数为目标规划问题及其数学模型目前一百一十八页\总数一百四十五页\编于十一点

大型煤炭企业生产和供给问题

目标规划应用举例目前一百一十九页\总数一百四十五页\编于十一点

大型煤炭企业生产和供给问题

目标规划应用举例彭红军,周梅华.大型煤炭供应链集成决策模型及应用,计算机集成制造系统，2009，15（9）:1738-1742.(EI检索)目前一百二十页\总数一百四十五页\编于十一点供应商物流运输客户市场原煤开配采洗选加工煤炭销售复杂煤炭企业内部供应链物流/供应信息流资金流/需求信息流图1复杂煤炭企业多层供应链框架外购煤