运筹学

陈建华

目录

  • 1 第一章    绪论
    • 1.1 第一节 运筹学的定义与发展简史
    • 1.2 第二节 运筹学的基本特点和工作步骤
    • 1.3 第三节 运筹学的主要分支
    • 1.4 第四节 运筹学的应用
  • 2 第二章  线性规划
    • 2.1 第一节 线性规划概述
    • 2.2 第二节 线性规划问题及其数学模型
    • 2.3 第三节 线性规划图解法及其几何意义
    • 2.4 第四节 线性规划单纯形法与单纯形表
    • 2.5 第五节 单纯形法的矩阵描述
    • 2.6 第六节 人造基下的单纯形法
    • 2.7 第七节 线性规划典型例题及应用
  • 3 第三章 运输问题
    • 3.1 第一节 运输问题的数学模型及其特征
    • 3.2 第二节 运输模型的求解---表上作业法
    • 3.3 第三节 运输问题的推广
  • 4 第四章 整数规划
    • 4.1 第一节 整数规划概念与特点
    • 4.2 第二节 分枝定界法
    • 4.3 第三节 割平面法
    • 4.4 第四节 0—1规划与隐枚举法
    • 4.5 第五节 指派问题与匈牙利法
    • 4.6 第六节 典型例题及应用
  • 5 第五章 图与网络
    • 5.1 第一节 图的基本概念
    • 5.2 第二节 树
    • 5.3 第三节 最短路问题
    • 5.4 第四节 网络最大流问题
    • 5.5 第五节 Euler图
    • 5.6 第六节 中国邮递员问题
  • 6 第六章 网络计划
    • 6.1 第一节 网络计划图
    • 6.2 第二节 网络计划图的时间参数
    • 6.3 第三节 网络计划的优化
  • 7 第七章 排队论
    • 7.1 第一节 排队论的基本概念
    • 7.2 第二节 排队系统常用分布
    • 7.3 第三节 单服务台模型
  • 8 第八章 存储论
    • 8.1 第一节 存储论基础
    • 8.2 第二节 确定性库存模型
    • 8.3 第三节 确定性库存模型的参数分析
    • 8.4 第四节 随机型存储模型
  • 9 第九章 决策论
    • 9.1 第一节 决策论基本问题
    • 9.2 第二节 完全不确定型决策
    • 9.3 第三节 风险型决策
    • 9.4 第四节 效用理论在决策中的应用
第二节 确定性库存模型

第二节确定性库存模型

本节假定在单位时间内(或称计划期)的需求量为已知常数,货物供应速率、订货费、缺货费已知,其订货策略是将单位时间分成等分的时间区间,在每个区间开始订购或生产货物量,形成循环存储策略。存储问题是确定何时需要补充和确定应当补充多少量,因为需求率是常数,可采用当库存水平下降到某一订购点时订购固定批量的策略。为此先要建立一个数学模型,将目标函数通过决策变量表示出来,然后确定订购量和订购间隔时间,使费用最小。

8.2.1瞬时供货,不允许缺货的经济批量模型

为进行存储状态分析,特作如下假定:

需求是连续均匀的,设需求速率为

当存储量降至零时,可立即补充,不会造成缺货(即认为供应速率为无穷)

每次订货费为,单位货物的存储费为,都为常数;

每次订货量都相同,均为

存储状态的变化图如下。

8-1 经济批量模型

表示一个运行周期开始后经时间后的库存量,为一个运行周期,[)

在一个周期内的平均库存量为

上述公式也可由求三角型面积得到。由于,所以一个周期长度为

设货物的单价或生产成本为,所以一个运行周期内(订货一次)货物存储费用为,货物的买价为,储存费用为(为一个周期内单位货物的储存费)。由于不存在缺货,所以一个运行周期的总成本为存储费用、买价、储存费用之和。

设在计划期内共订货次,由知计划期内总费用最小的储存模型为:

                               (8-1)

由微分学知识,处有极值的必要条件为,因此有:

解之并舍去负根,得:                                   (8-2)

易于验证在此点,故为模型(8-1)的最优解。

模型(8-1)求的是总费用最小的订货批量,通常称为经济订货批量(Economic Ordering Quantity),缩写其为EOQ模型。

此模型还可由初等数学求解,利用,等式仅当时成立,也得(8-2)

当采用最佳批量时,计划期应采购的次数为

                         (8-3)

(8-3)非整时,采购次数可选用[][]+1两个整数中使采购费用较少者作为最优选择,其理论基础来自于下面的几何解释。

(8-1)中略去常数项后,记

从上图看出:在处,。当时,;当时,。这说明左侧,成本递减,在右侧,成本递增,处成本最小。

8.1】设大华工厂全年需甲料1200吨,每次订货的成本为100元,每吨材料年平均储存成本为150元,每吨材料买价为800元,要求计算经济批量及全年最小总成本。

已知=1200   =800   =100    =150

经济批量==40()

全年共采购30次,总成本为()

8.2.2瞬时供货,允许缺货的经济批量模型

本模型允许缺货,但缺货损失可以定量计算,其余条件和模型(8-1)相同。缺货时存储量为零,由于允许缺货,所以可以减少订货和存储费用;但缺货会影响生产与销售,造成直接与间接损失。因此当本模型确定最优存储策略时,应综合这两方面的损失,使总费用达到最小。

此时的存储状态如图8-3所示。

8-3允许缺货的经济批量模型

假设周期为周期内的最大存储量,为周期内的最大缺货量,并设单位时间缺货费用为,则为存储量为正的时间周期,为存储量为负的时间周期(缺货周期)。采用缺货预约存储策略,所以在一个周期内的订货量仍为,在内有存量,需求为,在内缺货量为,不难看出

    (8-4)

与模型(8.2.1)的推导类似,在一个周期内的平均存量为,平均缺货量为,或者表示为。在一个周期内的费用为存储费,缺货费,订货费,买价

得计划期内总费用最小的存储模型为:

   (8-5)

将其视为的函数,式(8-5)变为:

     (8-6)

由极值必要条件

                              (8-7)

解之得:

                           (8-8)

可验证此为最优解。与不允许缺货的模型(8-1)相比,可以看出此模型有如下特点:

订货周期延长,订货次数在减少。

订货量在增加。

总费用在减少。此时

如让,此相当于不允许缺货,,则两模型最优解一致。

8.2】设某工厂全年按合同向外单位供货10000件,每次生产的准备结束费用为1000元,每件产品年存储费用为4元,每件产品的生产成本40元,如不按期交货每件产品每月罚款0.5元,试求总费用最小的生产方案。

解:以一年为计划期,=10000=40=1000=4=120.5=6,由公式(8.2.8)

0.2886()103.92()

2886.75()

1732.05()

1154.70()

0.1732()62.35()

=406928.20()

即工厂每隔104天组织一次生产,产量为2887件,最大存储量为1732件,最大缺货量为1155件。如果不允许缺货,总费用为

=408944.27()

比允许缺货多了2016.07()

8.2.3供应速度有限的不缺货库存问题

这种模型的特征是:物货的供应不是不是瞬时完成的,也不是成批的,而是以速率()均匀连续地逐渐补充,不允许缺货。在生产过程中的在制品流动就属于这种存储模型,这类模型也称为生产批量模型。存储量变化情况可用下图描述。

8-4生产批量模型

为一个供货周期,为其内生产时间,设货物供应速度为,消耗速度为,在内货物消耗(需要量),显然,即生产量与需求量相等。当存量为零时开始生产,库存量以速率增加,库存量达到最大时停止生产,然后库存量以速率减少,直到库存量为零时又开始下个周期的生产内的生产。

在一个周期内最高存储量为,平均存储量为,订货量为,存储费为(为一个周期单位存货存储费),订货手续费为,货物的生产成本(购置费),则在计划期内的总费用最小的存储模型为:

                            (8-9)

由极值的必要条件:

解之得

                              (8-10)

由于

而当,此最优解与瞬时供货无缺货模型的最优解相同。

8.3】某机加工车间计划加工一种零件,这种零件需先在车床上加工,然后在铣床上加工。每月车床上可加工500件,每件生产成本10.铣床上每月要耗用100件,组织一次车加工的准备费用为5元,车加工后的在制品保管费为0.5元/月一件,要求铣加工连续生产,试求车加工的最优生产计划?

解:此为连续加工不允许缺货的模型,以一个月为计划期。

已知=500=100=10=5=0.5

==50()

==0.5()

==0.1()

==1020()

车床上加工15天组织一次(一个周期),每次生产3天生产50件,够铣床上15天加工.

8.2.4供应速度有限允许缺货的库存问题

此模型与模型(8-5)的区别是供应速度有限,而模型(8-5)供应速度可认为为无限;与模型(8-9)的区别在于允许缺货,其他的假设同模型(8-1)

存储量变化如图所示。

8-5允许缺货的生产批量模型

在周期内,长度为+的时期是生产期。在的生产时期内,储存量的增量为,刚好弥补最大缺货量,最大缺货量为;在的生产时期内的生产量内的消耗量;故最高存储量为

由此得:

==

=

=

=                              (8-11)

在一个周期内,平均储存量:;平均缺货量:。计划期内有关的总费用有储存费、缺货费、订货费(生产准备费)、货物的买价(生产成本)

仍采用以前的符号得模型:

(8.2.11)代入得

             (8-12)

利用极值的必要条件:

解之,并得最优解

                                   (8-13)

此最大存储量及最大缺货量的计算:

若令,退化为模型(8-5)(瞬时供货,允许缺货);若,退化为模型(8-9)(供应速度有限,不允许缺货);若令:,同时,退化为模型(8-1)。所以,前面模型为模型(8-1)的特例。

8.4】在前面加工中,允许选铣加工中断,但造成每件每月1.5元损失费,求其最优方案。

57.73()

=0.5773()17.32()

=0.4330()12.99()

+1000=1017.32()

=34.641()=11.547()

17天组织一次生产,批量为58件,有库存为13天,最大库存为35件,最大缺货为12件,费用较前减少。