1、 线性规划及数学模型 线性规划是运筹学的一个重要分支。线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。1.1 问题的提出 从一个简化的生产计划安排问题开始例 1 某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表所示。资源 产 品 拥有量设 备1 2 8台时原材料 A 40 16 kg原材料 B04 1
2、2 kg续例1 该工厂每生产一件产品可获利2元，每生产一件产品可获利3元，问应如何安排计划使该工厂获利最多? 如何用数学关系式描述这问题，必须考虑称它们为决策变量。产品的数量，分别表示计划生产设III,21xx12416482212121x;x;xx,x ,x这是约束条件。即有量的限制的数量多少，受资源拥生产021x,x,即生产的产品不能是负值这是目标。最大如何安排生产，使利润,数学模型 0124164823221212121x,xxxxx:xxzmax约束条件目标函数例2. 简化的环境保护问题 靠近某河流有两个化工厂（见图1），流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一
3、条流量为每天200万立方米的支流。 图1续例2 第一 化工厂每天排放含有某种有害物质的工业污水2万立方米，第二化工厂每天排放这种工业污水1.4万立方米。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可自然净化。根据环保要求，河流中工业污水的含量应不大于0.2%。这两个工厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成本是1000元/万立方米，第二化工厂处理工业污水的成本是800元/万立方米。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。建模型之前的分析和计算设设：第一化工厂每天处理工业污水量为x1万立方米，第二化工厂每天处理工业
4、污水量为x2万立方米 100027004128021000250022211)x.()x(.)x(工厂后的水质要求：经第工厂前的水质要求：经第数学模型 0,4 . 126 . 18 . 018001000min212121121xxxxxxxxxz约束条件目标函数共同的特征(1)每一个线性规划问题都用一组决策变量 表示某一方案，这组决策变量的值就代表一个具体方案。一般这些变量取值是非负且连续的；(2)要有各种资源和使用有关资源的技术数据，创造新价值的数据；nx,x,x21)n,j;m,i (c;ajij11共同的特征（继续）(3) 存在可以量化的约束条件，这些约束条件可以用一组线性等式或线性不
5、等式来表示;(4) 要有一个达到目标的要求，它可用决策变量的线性函数(称为目标函数)来表示。按问题的不同，要求目标函数实现最大化或最小化。线性规划的一般模型形式 1 12211 11221121 1222221 12212max(min)( , )( , )( , ),0nnnnnnmmmnmnzc xc xc xa xa xa xba xa xa xba xaxa xbx xx 目标函数目标函数约束条件约束条件 存储论 存储论的基本概念 确定性存储模型 随机性存储模型 存储论的基本概念一 存储问题的提出 人们在生产和日常生活活动中往往将所需的物资、用品和食物暂时地储存起来，以备将来使用或消费
6、。这种储存物品的现象是为了解决供应（生产）与需求（消费）之间的不协调的一种措施，这种不协调性一般表现为供应量与需求量和供应时期与需求时期的不一致性上，出现供不应求或供过于求。人们在供应与需求这两环节之间加入储存这一环节，就能起到缓解供应与需求之间的不协调，以此为研究对象，利用运筹学的方法去最合理、最经济地解决，就是储存问题。例如 (1) 水电站在雨季到来之前，水库应蓄水多少? (2) 工厂生产需用原料，如没有储存一定数量的原料，会发生停工待料现象。 (3) 在商店里若存储商品数量不足，会发生缺货现象，失去销售机会而减少利润；如果存量过多，一时售不出去，会造成商品积压，占用流动资金过多而且周转不
7、开，这样也会给商家造成经济损失。 专门研究这类有关存储问题的科学，构成运筹学的一个分支，叫作存储论(inventory)，也称库存论。 本章所介绍的存储问题，模型并不复杂，原理也容易掌握，应用这些原理可以从一个方面改善企业的经营管理，以达到节约资金，获得更多利润的目的。二 存储论的基本概念1.需求 对存储来说，由于需求，从存储中取出一定的数量，使存储量减少，这就是存储的输出。有的需求是间断式的，有的需求是连续均匀的。 图1和图2分别表示t时间内的输出量皆为 S-W，但两者的输出方式不同。图1表示输出是间断的，图2表示输出是连续的。 有的需求是确定性的，如钢厂每月按合同卖给电机厂矽钢片10吨。有
8、的需求是随机性的，如书店每日卖出去的书可能是1000本，也可能是800本。但是经过大量的统计以后，可能会发现每日售书数量的统计规律，称之为有一定的随机分布的需求。图 1，22 补充(订货或生产)存储由于需求而不断减少，必须加以补充，否则最终将无法满足需求。补充就是存储的输入。补充的办法可能是向其他工厂购买，从订货到货物进入“存储”往往需要一段时间，我们把这段时间称为备货时间（即工厂的生产时间和运输时间）。从另一个角度看，为了在某一时刻能补充存储，必须提前订货，那么这段时间也可称之为提前时间提前时间(leadtime)。备货时间可能很长，也可能很短，可能是随机性的，也可以是确定性的。存储论要解决
9、的问题是：多少时间补充一次，每次补充的数量应该是多少。决定多少时间补充一次以及每次补充数量的策略称为存储策略存储策略。存储策略的优劣如何衡量呢?最直接的衡量标准，是计算该策略所耗用的平均费用多少。为此有必要对费用进行详细的分析。3 费用 （主要包括以下费用）(1) 存储费C1，包括货物占用资金应付的利息以及使用仓库、保管货物、货物损坏变质等支出的费用。(2) 订货费，包括两项费用，一项是订购费用C3 （固定费用，或一次性费用）如手续费、电信往来、派人员外出采购等费用。订购费与订货次数有关，而与订货数量无关。另一项是可变费用，它与订货数量及货物本身的价格，运费等有关。如货物单价为K元，订购费用为
10、C3元，订货数量为Q，则订货费用为：C3+KQ。(3) 生产费，补充存储时，如果不需向外厂订货，由本厂自行生产，这时仍需要支出两项费用。一项是准备、结束费用，如更换模、夹具需要工时，或添置某些专用设备等属于这项费用；它是一次性的费用，或称为固定费用，也用C3表示。另一项是与生产产品的数量Q有关的费用如材料费、加工费等（可变费用），总生产费用也是C3+KQ。(4) 缺货费C2，当存储供不应求时所引起的损失。如失去销售机会的损失、停工待料的损失以及不能履行合同而缴纳罚款等。 在不允许缺货的情况下，在费用上处理的方式是缺货费为无穷大。4 存储策略如前所述，决定何时补充，补充多少数量的办法称之为存储策
11、略，常见的策略有三种类型。(1) t0循环策略，每隔t0时间补充存储量Q。(2) (s,S)策略，每当存储量xs时不补充。当xs时补充存储。补充量Q=S-x(即将存储量补充到S)。(3) (t,s,S)混合策略，每经过t时间检查存储量x，当xs时不补充。当xs时，补充存储量使之达到S。 一个好的存储策略，既可以使总费用最小，又可避免因缺货影响生产（或对顾客失去信用）存储模型的两大类型： 一类叫作确定性模型，即模型中的数据皆为确定的数值； 另一类叫作随机性模型，即模型中含有随机变量，而不是确定的数值。 由于具体条件有差别，制定存储策略时又不能忽视这些差别，因而模型也有多种类型。本章将按确定性存储
12、模型及随机性存储模型两大类，分别介绍一些常用的存储模型，并从中得出相应的存储策略。三 确定性存储模型 模型一：不允许缺货，备货时间很短 假设：(1) 缺货费用无穷大；(2) 当存储降至零时，可以立即得到补充（即备货时间或拖后时间很短，可以近似地看作零）；(3) 需求是连续的、均匀的，设需求速度R（单位时间的需求量）为常数，则t时间的需求量为Rt；(4) 每次订货量不变，订购费不变（每次备货量不变，装配费不变）；(5) 单位存储费不变。分析模型一其存储量的变化情况用右图表示假定每隔t时间补充一次存储，那么订货量必须满足t时间的需求Rt，记订货量为Q，Q=Rt，订购费为C3，货物单价为K，则订货费
13、为C3+KRt；t时间的平均订货费为 t 时间内的平均存储量为(此结果由上页图中利用几何知识易得出，平均存储量为三角形高的二分之一)单位时间内单位物品的存储费用为C1，) 1 (RtC21KRtC) t (C13t 时间内所需平均存储费用为1/2 (RtC1）。t 时间内总的平均费用为C(t） 对(1)式利用微积分求最小值的方法可求出令费用最少时的订货时间和数量。0RC21tCdt) t (dC123令：)2(RC2Ct得：130经济批量公式0dt) t (Cd22)3(CR2CRtQ1300因得即存储论中著名的经济订购批量(economic ordering quantity)公式。简称为E
14、.O.Q公式，也称平方根公式，或经济批量(economic lot size)公式。 所以，C(t0)为最小值由于Q0、t0皆与K无关，所以此后在费用函数中略去KR这项费用。如无特殊需要不再考虑此项费用， (1)式改写为)4(RtC21tC) t (C13) 1 (RtC21KRtC) t (C13最佳费用公式)5(RC2CRC2CRC212CRCC)t (CC3113131300将t 0代入(4)式得出最佳费用RtC211存贮费用曲线)4(RtC21tC) t (C总费用曲线13从费用曲线也可以求出t0，Q0，C0费用曲线C(t)曲线的最低点(min C(t)的横坐标t0与存储费用曲线、订购
15、费用曲线交点横坐标相同。即例例1 某厂按合同每年需提供D个产品，不许缺货。假设每一周期工厂需装配费C3元，存储费每年每单位产品为C1元，问全年应分几批供货才能使装配费，存储费两者之和最少。 解 设全年分n批供货，每批生产量Q=D/n，周期为1/n年(即每隔1/n年供货一次)。公式公式说明说明 从例1中还看到这些公式在实际应用时还会有一点问题，因为t0（或Q0，n0）不一定是整数。假设t0=16.235（天）。很明显，小数点后面的数字对实际订货间隔的时间是没有意义的，这时可以取近似的整数。取t016或t017都可以。 为了精确起见，可以比较C(16)、C(17)的大小，再决定t0=16或t0=1
16、7。例例2 某轧钢厂每月按计划需产角钢3000吨，每吨每月需存储费5.3元，每次生产需调整机器设备等，共需准备费2500元。 若该厂每月生产角钢一次，生产批量为3000吨。 每月需总费用 5.31/23000+25000=10450(元/月) 全年需费用 1045012=125400(元/年) 然后按E.O.Q公式计算每次生产批量计算批量和批次)(16825.3300025002C)(D)(C2Q130吨（存储费）需求速度装配费计算需要的数据计算需要的数据 两次生产相隔的时间t0=（365/21.4）17(天) 17天的单位存储费(5.3/30)17=3.00(元/吨)， 共需费用5.3/30
17、171682+25005025(元)。 按全年生产21.5次(两年生产43次)计算，全年共需费用502521.5=108037(元/年)。 两者相比较，该厂在利用E.O.Q公式求出经济批量进行生产即可每年节约资金 125400 108037=17363(元)模型二：不允许缺货，生产需一定时间模型二：不允许缺货，生产需一定时间 本模型的假设条件，除生产需要一定时间的条件外，其余皆与模型一的相同。 设生产批量为Q，所需生产时间为T，则生产速度为P=Q/T。 已知需求速度为R，（RP）。生产的产品一部分满足需求，剩余部分才作为存储，这时存储变化如图所示。 在0，T区间内，存储以(P-R)速度增加，在
18、T，t区间内存储以速度R减少。 T与t皆为待定数。从上图易知(P-R)T=R(t-T)，即PT=Rt(等式表示以速度P生产T时间的产品等于t时间内的需求)，并求出 公式公式公式例例3 某厂每月需甲产品100件，每月生产率为500件，每批装配费为50元，每月每件产品存储费为4元，求E.O.Q及最低费用。 解解 已知C3=50，C1=4，P=500，R=100，将各值代入公式(7)及(8)得例例4 某商店经售甲商品成本单价某商店经售甲商品成本单价500元，年存元，年存储费用为成本的储费用为成本的20%，年需求量，年需求量365件，需求件，需求速度为常数。甲商品的定购费为速度为常数。甲商品的定购费为
19、20元，提前元，提前期为期为10天，求天，求E.O.Q及最低费用。及最低费用。 解解 此例题从表面上看，似乎应按模型二处理。因为拖后时间似乎与生产需一定时间意义差不多。其实不然，现将本题存储变化情况用图表示之(见下页图)，并与模型一、模型二的图相比较，可看到与模型一完全相同。本题只需在存储降至零时提前10天订货即可保证需求。计算订货点订货点 由于提前期为t1=0天，10天内的需求为10单位甲商品，因此只要当存储降至10单位时，就要订货。一般设t1为提前期，R为需求速度，当存储降至L=Rt1的时候即要订货。 L称为“订购点”(或称订货点)。 确定多少时间订一次货，虽可以用E.O.Q除以R得出to
20、(to=Qo/R)，但求解的过程中并没有求出to，只求出订货点L即可，这时存储策略是：不考虑to，只要存储降至L即订货，订货量为Qo，称这种存储策略为定点定点定货定货。相对地每隔to时间订货一次称为定时订货定时订货，每次订货量不变则称为定量订货定量订货。 模型三：允许缺货，备货时间很短模型三：允许缺货，备货时间很短 模型一、模型二是在不允许缺货的情况下推导出来的。本模型是允许缺货，并把缺货损失定量化来加以研究。由于允许缺货，所以企业可以在存储降至零后，还可以再等一段时间然后订货。这就意味着企业可以少付几次订货的固定费用，少支付一些存储费用。一般地说当顾客遇到缺货时不受损失，或损失很小，而企业除
21、支付少量的缺货费外也无其他损失，这时发生缺货现象可能对企业是有利的。本模型的假设条件除允许缺货外，其余条件皆与模型一相同。 设设 单位时间单位物品存储费用为C1，每次订购费为C3，缺货费为C2(单位缺货损失)，R为需求速度。求最佳存储策略，使平均总费用最小(见下图)。假设最初存储量为S 公式公式公式公式公式将(10)式，(11)式代入C(t,S)由于模型三中允许缺货由于模型三中允许缺货在允许缺货情况下，存储量只需达到S0即可，显然Q0S0，它们的差值表示在to时间内的最大缺货量。)CC(CC2RC)CC(CCC2RCCCCCCCC2RC)CC(CC2RCCCCC2RCSQ21231212113
22、212221132113222113oo说明说明 在允 许缺货条件下，经过研究而得出的存储策略是 ：每隔to时间订货一次，订货量为Qo，用Qo中的一部分补足所缺货物，剩余部分So进入存储。很明显，在相同的时间段落里，允许缺货的订货次数比不允许缺货时订货次数减少了。例例5 已知需求速度已知需求速度R=100件，件，C1=4元，元，C2=1.5元，元，C3=50元，求元，求S0及及C0。 解解 利用(12)式，(13)式即可计算模型一、二、三存储策略之间的差别模型一、二、三存储策略之间的差别 可以看到不允许缺货生产需要时间很短条件下可以看到不允许缺货生产需要时间很短条件下得出的存储策略：最大存储量
23、得出的存储策略：最大存储量S0=Q03012C RQ(3)C3012Ct(2)C R在不允许缺货、生产需一定时间条件下，在不允许缺货、生产需一定时间条件下，得出存储策略得出存储策略3012CPt(6)C RPR3o12CPQ(7)CPR3o12C RPRS(9)CP在允许缺货、生产需时间很短条件在允许缺货、生产需时间很短条件下，得出存储策略下，得出存储策略32o1122C RCSCCC(12)312o122RCCCQ(14)CC312o132CCCt(11)C RC模型二、三只是以模型一的存储策略乘上相应的因子，这样可以便于记忆，再有都是同一个数值，这样就得出它们之间的差别与内在联系。 模型四
24、：允许缺货（需补足缺货）、生模型四：允许缺货（需补足缺货）、生产需一定时间产需一定时间 假设条件除允许缺货生产需一定时间外，其余条件皆与模型一相同，其存储变化如图所示 分析图分析图 取0，t为一个周期，设t1时刻开始生产。 0,t2时间内存储为零，B表示最大缺货量。 t1,t2时间内除满足需求外，补足0,t1时间内的缺货。 t2,t3时间内满足需求后的产品进入存储，存储量以(P-R)速度增加。 S表示存储量，t3时刻存储量达到最大，t3时刻停止生产。 t3,t时间存储量以需求速度 R 减少。由图易知：由图易知： 最大缺货量最大缺货量B=Rt1，或，或 B=(P-R)(t2-t1)；即；即Rt1
25、=(P-R)(t2-t1)，得，得12PRtt(15)P最大存储量 S=(P-R)(t3 - t2)，或S=R(t - t3)即(P-R)(t3 - t2)=R(t - t3)，得322Rtt(tt )(16)P在在0，t时间内所需费用：时间内所需费用： 存储费：存储费：将(16)式代入消去t 3，得 222tPR-PRC21在在0，t时间内所需费用：时间内所需费用： 缺货费： 将(15)式代入消去t 1，得 在在0，t时间内所需费用：时间内所需费用：装配费：装配费：C3 在在0,t时间内总平时间内总平均费用为：均费用为：为了得到最佳公式，分别求偏导数：为了得到最佳公式，分别求偏导数： 223
26、211222C(t,t )tCt1 (PR)RC(CC )()(17)2Ptt222112C(t,t )tt1 (PR)R-2C2(CC )(18)2Pt推导 由(18)式得 ，1212Ctt(19)CC由(17)式得 推导：将推导：将(19)式代入上式消去式代入上式消去t2得得由由(19)有有公式312o122CCCPt(20)C RCPRoo31212QRt2C RCCP(21)CCPRS0（最大存储量）（最大存储量）oo2ooo1ooo122o1222112RPRSR(tt )R(ttt )PPCRPRR tttPPCCCPRRtPCC2C RCPR(22)CCCPB0（最大缺货量）（最
27、大缺货量）o112122R(PR)BRttP2C C RPR(23)(CC )CP最小费用：最小费用： o2o1312minC(t ,t )CCPR2C C RCCP(24)四四 随机性存储模型随机性存储模型 随机性存储模型的重要特点是需求为随机的，其概率或分布为已知。在这种情况下，前面所介绍过的模型已经不能适用了。例如商店对某种商品进货500件，这500件商品可能在一个月内售完，也有可能在两个月之后还有剩余。商店如果想既不因缺货而失去销售机会，又不因滞销而过多积压资金，这时必须采用新的存储策略 与确定性模型不同的特点有： 不允许缺货的条件只能从概率的意义方面理解，如不缺货的概率为0.9等。存
28、储策略的优劣通常以赢利的期望值的大小作为衡量的标准。 为了讲清楚随机性存储问题的解法，先通过一个例题介绍求解的思路。例例 某商店拟在新年期间出售一批日历画片，每售出一千张可赢利700元。如果在新年期间不能售出，必须削价处理，作为画片出售。由于削价，一定可以售完，此时每千张赔损400元。根据以往的经验，市场需求的概率见下表。每年只能订货一次，问应订购日历画片几千张才能使获利的期望值最大?解解 如果该店订货4千张，我们计算获利的可能数值订购量为4千张时获利的期望值： EC(4)=(-1600)0.05 +(-500)0.10+6000.25 +17000.35+28000.15 +28000.10
29、 =1315(元)上述计算法及结果列于下表获利期望值最大者标有(*)记号，为1440元。可知该店订购3000张日历画片可使获利期望值最大。 从相反的角度考虑求解 当订货量为Q时，可能发生滞销赔损（供过于求的情况），也可能发生因缺货而失去销售机会的损失（求过于供的情况）。把这两种损失合起来考虑，取损失期望值最小者所对应的Q值。订购量为2千张时，损失的可能值：当订货量为2千张时，缺货和滞销两种损失之和的期望值 EC(2)=(-800)0.05 + (-400)0.10+00.25 +(-700)0.35+(-1400)0.15 +(-2100)0.10 = 745(元) 按此算法列出下表。比较表中
30、期望值以-485最大，即485为损失最小值。该店订购3000张日历画片可使损失的期望值最小。这结论与前边得出的结论一样，都是订购3000张。这说明对同一问题可从两个不同的角度去考虑：一是考虑获利最多，一是考虑损失最小。这是一个问题的不同表示形式。五五 需求是随机离散的需求是随机离散的 报童问题：报童每日售报数量是一个随机变量。报童每售出一份报纸赚k元。如报纸未能售出，每份赔h元。每日售出报纸份数r的概率P(r)根据以往的经验是已知的，问报童每日最好准备多少份报纸? 这个问题是报童每日报纸的订货量Q为何值时，赚钱的期望值最大?反言之，如何适当地选择Q值，使因不能售出报纸的损失及因缺货失去销售机会
31、的损失，两者期望值之和最小。现在用计算损失期望值最小的办法求解。解解 设售出报纸数量为r，其概率P(r)为已知 设设 报童订购报纸数量为Q。 供过于求时(rQ)，这时报纸因不能售出而承担的损失，其期望值为： 供不应求时(rQ)，这时因缺货而少赚钱的损失，其期望值为：综合，两种情况，当订货量为Q时，损失的期望值为：要从式中决定Q的值，使C(Q)最小。 由于报童订购报纸的份数只能取整数，r是离散变量，所以不能用求导数的方法求极值。为此设报童每日订购报纸份数最佳量为Q，其损失期望值应有： C(Q)C(Q+1) C(Q)C(Q-1)从出发进行推导有 由出发进行推导有 hkk) r (P1 -Q0r报童应准备的报纸最佳数量Q应按下列不等式确定：Q-1Qr 0r 0kP(r)P(r)kh 当需求rQ时, 赢利的期望值为： 当需求rQ时，报童因为只有Q份报纸可供销售，赢利的期望值为 无滞销损失。 以下从赢利最大来考虑报童应准备的报纸数量。设报童订购报纸数量为Q，获利的期望值为C(Q)，其余符号和前面推导时表示的意义相同。由以上分析知赢利的期望值： 为使订购Q赢利的期望值最大，应满足下列关系式： C(Q+1)C(Q) C(Q-1)C(Q) 从式推导，经化简后得同理从推导出 综上，可用以下不等式确定Q的值，这一公式与由损失期望值推导结果完全相同。
