第二章-最优化方法

第二章 最优化方法

运筹学简述

运筹学（Operations Research）

系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学(Management Science)。运筹学所研究的问题，可简单地归结为一句话：

“依照给定条件和目标，从众多方案中选择最佳方案”。 故有人称之为最优化技术。

最优化

最优化：

指针对决策问题，按照决策的目标，从多个可能的方

案中选择出最好的方案的过程。

最优化方法的主要研究对象是各种人类组织的管理问题和生产经营活动，其目的在于求得一个合理运用人力、物力和财力的方案，使资源的使用效益得到充分的发挥，最终达到最优目标。 运筹学的主要内容

? 数学规划（线性规划、整数规划、目标规划、动态规划等） ? 图论 ? 存储论 ? 排队论 ? 对策论

? 排序与统筹方法 ? 决策分析

运筹学在工商管理中的应用

运筹学在工商管理中的应用涉及几个方面：

生产计划 ? 运输问题 ? 人事管理 ? 库存管理 ? 市场营销

?

?

财务和会计

另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程

优化设计等。

第一节 线性规划

(Linear Programming)

线性规划问题的数学模型

1. 规划问题

线性规划问题的数学模型

例1.1 如图所示，如何截取x使铁皮所围成的容积最大？

线性规划问题的数学模型 线性规划问题的数学模型

解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：

线性规划问题的数学模型 线性规划问题的数学模型 线性规划问题的求解方法

线性规划问题的求解方法

图解法

max Z = 2X1 + X2

X1 + 1.9X2 ≥ 3.8 X1 - 1.9X2 ≤ 3.8 s.t. X1 + 1.9X2 ≤10.2

X1 - 1.9X2 ≥ -3.8 X1 ，X2 ≥ 0

图解法

单纯形法的计算步骤

例1.9 用单纯形法求解

单纯形法的计算步骤

在Excel中建立线性规划模型和求解的方法 在Excel中建立线性规划模型和求解的方法 在Excel中建立线性规划模型和求解的方法 在Excel中建立线性规划模型和求解的方法

线性规划模型的应用

一般而言，一个经济、管理问题凡是满足以下条件时，

才能建立线性规划模型。

线性规划在管理中的应用

?

人力资源分配问题

线性规划在管理中的应用

解：设xi表示第i班次时开始上班的司机和乘务人员人数。

线性规划在管理中的应用

2. 生产计划问题

线性规划在管理中的应用 线性规划在管理中的应用

解：设xijk表示产品i在工序j的设备k上加工的数量。约束条件有：

线性规划在管理中的应用

目标是利润最大化，即利润的计算公式如下：

线性规划在管理中的应用

因此该规划问题的模型为：

线性规划在管理中的应用 线性规划在管理中的应用 线性规划在管理中的应用

3. 套裁下料问题

线性规划在管理中的应用 线性规划在管理中的应用

4. 配料问题

线性规划在管理中的应用

解：设Xj 表示Bj 种食物用量

第二节 运输规划

运输规划问题的数学模型

例 某公司从两个产地A1、A2将物品运往三个销地B1, B2, B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？

运输规划问题的数学模型

解：产销平衡问题：总产量 = 总销量＝500

设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表：

运输规划问题的数学模型

运输问题的一般形式：产销平衡

运输规划问题的数学模型

产销不平衡的运输问题

当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。

运输规划问题的数学模型

由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟销地Bn+1， bn+1作为一个虚设销地Bn+1的销量(即库存量)。各产地Ai到Bn+1的运价为零，即Ci,n+1=0,（i=1，…，m）。则平衡问题的数学模型为：

运输规划问题的数学模型

?

当销大于产时，即：

运输规划问题的数学模型 运输规划问题的数学模型

例：求下列表中极小化运输问题的最优解

运输问题的应用

所以是一个产大于销的运输问题。表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180-160=20，Ci5=0，i=1,2,3,4，表的右边增添一列 ，得到新的运价表。

运输规划问题的数学模型

下表为计算结果。可看出：产地A4还有20个单位没有运出。

运输规划问题的Excel解法

例：设有某种物资共有三个产地A1、A2、A3，其产量分别为9、5、7个单位；另有四个销地B1、B2、B3、B4，期销量分别为3、8、4、6个单位。已知由产地Ai（i=1,2,3）运往销地Bj（j=1,2,3,4）的单位运价为Cij。问如何调运才能使总运费最省？

运输规划问题的Excel解法

MinZ=2x11+9 x12+10 x13+7x14+x21+3 x22

+4x23+2x24+8x31+4x32+2x33+5 x34 x11+x12+x13+x14=9 x21+x22+x23+x24=5 x31+x32+x33+x34=7 x11+x21+x31=3

x12+x22+x32=8 x13+x23+x33=4 x14+x24+x34=6

xij≥0（i=1,2,3；j=1,2,3,4）

运输规划问题的Excel解法 运输规划问题的Excel解法 运输规划问题的Excel解法 运输规划问题的Excel解法

例：某设备厂的非平衡运输问题。

某设备厂下设三个位于不同地点的分厂A、B、C，该三个分厂生产同一种设备，设每月的生产能力分别为25台、35台、45台。某设备厂有四个固定的用户，四个用户下月的设备需求量分别为20台，15台，23台，32台。设各分厂的生产成本相同，从各分厂到各用户的单位设备运输成本如下表，而且各分厂本月末的设备库存量为零。问该厂如何安排下月的生产与运输，才能在满足四个用户需求的前提下使总运输成本最低。

运输规划问题的Excel解法 运输规划问题的Excel解法 运输规划问题的Excel解法

第三节 分配问题

分配问题

指派问题的数学模型的标准形式：

分配问题

指派问题的数学模型为：

分配问题

例 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？

分配问题

不平衡的指派问题

分配问题

一个人可做几件事的指派问题

分配问题

某事一定不能由某人做的指派问题

分配问题

解：由于任务数多于人数，所以假定一名虚拟人，设为戊。因为工作E必须

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第二章-最优化方法在线全文阅读。