运筹学第一章 1.5 线性规划的应用

1.5 线性规划的应用 一、使用线性规划方法处理实际问题 必须具备的条件(建模条件) 必须具备的条件(建模条件):

1) 优化条件 问题的目标有极大化或极小化 优化条件---问题的目标有极大化或极小化的要求, 的要求,而且能用决策变量的线性函数来表 示。

2) 选择条件 有多种可供选择的可行方案， 选择条件---有多种可供选择的可行方案 有多种可供选择的可行方案，以便从中选取最优方案。 以便从中选取最优方案。

3)限制条件 达到目标的条件是有一定限制的 )限制条件---达到目标的条件是有一定限制的 比如， 资源的供应量有限度等) ( 比如 ， 资源的供应量有限度等 ) , 而且这 些限制可以用决策变量的线性等式或线性不 等式表示出来。 等式表示出来。 此外， 描述问题的决策变量相互之间应 此外 ， 有一定的联系， 有可能建立数学关系， 有一定的联系 ， 有可能建立数学关系 ， 即这 些变量之间是内部相关的。 些变量之间是内部相关的。

二、建模步骤： 二、建模步骤：第一步：设置要求解的决策变量。 第一步：设置要求解的决策变量。决策变量 选取得当， 选取得当，不仅能顺利地建立模型而且能方便 地求解，否则很可能事倍功半。 地求解，否则很可能事倍功半。 第二步：找出所有的限制，即约束条件，并 第二步：找出所有的限制，即约束条件， 用决策变量的线性方程或线性不等式来表示。 用决策变量的线性方程或线性不等式来表示。 当限制条件多，背景比较复杂时， 当限制条件多，背景比较复杂时，可以采用图 示或表格形式列出所有的已知数据和信息， 示或表格形式列出所有的已知数据和信息，以 避免“遗漏” 重复”所造成的错误。 避免“遗漏”或“重复”所造成的错误。

第三步： 明确目标要求， 第三步 ： 明确目标要求 ， 并用决策变量 的线性函数来表示， 的线性函数来表示，确定对函数是取极大还 是取极小的要求。 是取极小的要求。 决策变量的非负要求可以根据问题的实 际意义加以确定。 际意义加以确定。

三、 经济管理领域中

几类典型的LP问题

(一) 生产组织与计划问题1. 产品计划问题 2. 产品配套问题 3. 人力资源问题

1、产品计划问题 、问题的一般提法： 用若干种原材 问题的一般提法 ： 料 ( 资源 ) 生产某几种产品 ， 原材 资源) 生产某几种产品， 或资源) 供应有一定限制， 料 ( 或资源 ) 供应有一定限制 ， 要 求制定一个产品生产计划， 求制定一个产品生产计划 ， 使其在 一定数量的资源限制条件下能得到 最大的收益。 最大的收益。

如果用 B1 , B2 , L , Bm 种资源 如果

用 ， 生产 A1,A2, An 种产品 L 单位产品所需资源数(如原材料、人 单位产品所需资源数(如原材料、 )、所得利润及可供应的资源 力、时间等)、所得利润及可供应的资源 时间等)、 总量已知，根据有关信息， 总量已知，根据有关信息，问应如何组织 生产才能使利润最大？ 生产才能使利润最大？

产品计划问题有关信息表单位 产品 所需 资源 资源 产 品

A1

A2

L

An

可供应资源

B1 B2 M Bm

a11 a21 L am1

a12 a21 L am2

L L L L

a1n a2n L amn

b1 b2 M bm

单位产品所得利润

c1

c2

L

cn

设出产品的计划数， 可列出这类问 设出产品的计划数 ， 题的数学模型如下： 题的数学模型如下：MaxZ = ∑ c j x jj =1 n

n (i = 1,2,Lm) ∑ a ijx j ≤ b i j = 1 s.t. (生产各种产品所需资源B j的总数不能超过可供应总量) (j = 1, L n) 2, x j ≥ 0 (产品计划生产数不能是负数)

2、人力资源问题 、某商场对一周内客流量进行统计分析， 例1-13 某商场对一周内客流量进行统计分析， 按照服务定额得知一周中每天售货人员需求量 。若 售货员每周工作5天 休息2天 售货员每周工作 天，休息 天，并要求休息时间是 连续的，商场应如何安排售货人数， 连续的，商场应如何安排售货人数，才能够既满足 工作需要，又使配备的售货人员最少？ 工作需要，又使配备的售货人员最少？

时间星期 售货人数

日 28

一 15

二 24

三 25

四 19

五 31

六 28

为星期i开始休息的人数 设：x为星期 开始休息的人数，星期日记为 7,则每一天 为星期 开始休息的人数，星期日记为x 工作的人数应为下一日开始休息的人员直至由下一日算起 的第5个工作日 亦即非当日、前天休息的人员总和。 个工作日， 的第 个工作日，亦即非当日、前天休息的人员总和。日 一 二

星期日 一 二 三 四 五 六

三

四

五

六

x7

x7 x1

x1 x2

x2 x3

x3 x4

x4 x531

x628 15 24 25 19

x5 x628

人数

min Z = x1 + x2 + x3 + x4 + x5 + x6 + x7 x1 + x2 + x3 + x4 + x5 ≥ 28 x2 + x3 + x4 + x5 + x6 ≥ 15 x3 + x4 + x5 + x6 + x7 ≥ 24 x1 + x4 + x5 + x6 + x7 ≥ 25 x1 + x2 + x5 + x6 + x7 ≥ 19 x1 + x2 + x3 + x6 + x7 ≥ 31 x1 + x2 + x3 + x4 + x7 ≥ 28 x ≥ 0 i = 1, 2,L , 7 ( ) i

3、产品配套问题 、例1-9 某产品由两个零件I和三个 某产品由两个零件 和三个 零件II组成，每个零件均可由三个车间 零件 组成， 组成 各自生产， 各自生产，但各车间的生产效率和总工 时限制各不相同，根据有关信息， 时限制各不相同，根据有关信息，试确 定各车间生产每种零件的工作时间， 定各车间生产每种零件的工作时间，使 生产产品的件数最多。 生产产

品的件数最多。

例1-9有关信息表 有关信息表生产效率( 小时 小时) 生产效率(件/小时) 车 间 1 2 3 总 工 时 100 50 75 零件 I 8 10 16 零件 II 6 15 21 生产工时数 零件 I 零件 II

x11 x 21 x31

x12 x 22 x32 6 x12 + 15x 22 + 21x32

分析： 分析： 生产出两种零件的数量分别是 组装成的产品数为 z= min

8x11 + 10x 21 + 16x31 ,

8x11 + 10x 21 + 16x31 6 x12 + 15x 22 + 21x32 , 2 3

其中： 表示第i个车间生产第 个车间生产第j个零件的时间 其中：xij表示第 个车间生产第 个零件的时间

注意——Z是非线性表达式！ 是非线性表达式！ 注意 是非线性表达式

Y ① 引入一个新变量 ，

处 理

令 Y=

8 x + 10 x + 16 x + + 21x32 11 21 31 6 x12 15 x 22 min , 2 3

则目标要求可以写成： 则目标要求可以写成： Max Z = Y

② 把 Y 的表达式改写成两个不等式增添到约束条件中去8X11 +10X21 +16X31 Y≤ , 2 6X12 +15X22 + 21X32 Y≤ ; 3

于是得到该问题的LP模型为： 于是得到该问题的 模型为： 模型为Max Z=Y

x11 + x21 ≤ 100 x + x ≤ 50 21 22 x + x ≤ 75 s.t. 31 32 8 x11 + 10 x21 + 16 x31 ≥ 2 y 6 x + 15 x + 21x ≥ 3 y 22 32 12 x11, x12, x 21, x 22, x31, x32, y ≥ 0