第二章线性规划 第一讲 数学模型与图解法

运筹学Operations Research

Chapter 2 线性规划Linear Programming2.1 LP的数学模型 2.2 图解法 2.3 标准型 2.4 基本概念 2.5 单纯形法 Mathematical Model of LP

Graphical MethodStandard form of LP

Basic Concepts Simplex Method

2.1 数学模型Mathematical Model

2.1 线性规划的数学模型 Mathematical Model of LP

Chapter 2 线性规划 Linear Programming

案例分析 某企业在计划期内计划生产甲、乙、丙三种产品。 这些产品分别需要在设备 A、B上加工，需要消耗材料 C、D,按工艺资料规定，单件产品在不同设备上加工 及所需要的资源如表2.1所示。已知在计划期内设备的 加工能力各为200台时，可供材料分别为360、300公斤； 每生产一件甲、乙、丙三种产品，企业可获得利润分 别为 40 、 30 、 50 元，假定市场需求无限制。企业决策 者应如何安排生产计划，使企业在计划期内总的利润 收入最大？

2.1 线性规划的数学模型 Mathematical Model of LP

Chapter 2 线性规划 Linear Programming

表2.1 产品资源消耗 产品 资源 甲 乙 丙 现有资源

设备A设备B

32

12

24

200200

材料C材料D

42

53

15

360300

利润(元/件)

40

30

50

2.1 线性规划的数学模型 Mathematical Model of LP

Chapter 2 线性规划 Linear Programming

【解】 设x1、x2、x3 分别为甲、乙、丙三种产品的产 量, 则 数学模型为：

max Z 40 x1 30 x2 50 x3 3x1 x2 2 x3 200 2 x 2 x 4 x 200 1 2 3 4 x1 5 x2 x3 360 2 x 3x 5 x 300 2 3 1 x1 0,x2 0,x3 0最优解X=(50,30,10); Z=3400产品 甲资源 设备A 设备B 材料C 材料D 3 2 4 2 1 2 5 3 2 4 1 5 200 200 360 300

乙

丙

现有 资源

利润(元/ 件)

40

30

50

Chapter 2 线性规划 Linear Programming

结 论 如何求解，难点是什么？关键在那里？

线性规划模型的建立、模型的特征、 模型的求解思路和过程。

线性规划问题的概念 1. 规划问题

Chapter 2 线性规划 Linear Programming

生产和经营管理中经常提出如何合理安排，使人力、 物力等各种资源得到充分利用，获得最大的效益， 这就是规划问题。 线性规划通常解决下列两类问题： (1)当任务或目标确定后，如何统筹兼顾，合理安排，用 最少的资源 (如资金、设备、原标材料、人工、时间等) 去完成确定的任务或目标 (2)在一定的资源条件限制下，如何组织安排生产获得最 好的经济效益(如产品量最多 、利润最大.)

Chapter 2 线性规划 Linear Programming

例2.1 如图所示，如何截取x使铁皮所围 成的容积最大？v a 2 x x2

x a

dv 0 dx

2(a 2 x ) x ( 2) (a 2 x )2 0a x 6

2.1 线性规划的数学模型 Mathematical Model of LP

Chapter 2 线性规划 Line

ar Programming

【例 2.2】某商场决定：营业员每周连续工作 5 天后连续 休息2天， 轮流休息。根据统计，商场每天需要的营业 员如表2.2所示。星期 一 二 表2.2 营业员需要量统计表 需要人数 星期 需要人数 300 300 五 六 480 600

三四

350400

日

550

问：商场人力资源部应如何安排每天的上班人数，使商 场总的营业员最少？ 【解】 设

x j ( j=1,2,…,7)为休息2天后星期一到星

期日开始上班的营业员，则这个问题的线性规划模型为

2.1 线性规划的数学模型 Mathematical Model of LP

Chapter 2 线性规划 Linear Programming

星期 一 二 三 四

需要人数 300 300 350 400

星期 五 六 日

需要人数 480 600 550

min Z x1 x2 x3 x4 x5 x6 x7 x1 x4 x5 x6 x7 300 x x x x x 300 2 5 6 7 1 x1 x2 x3 x6 x7 350 x1 x2 x3 x4 x7 400 x1 x2 x3 x4 x5 480 x2 x3 x4 x5 x6 600 x3 x4 x5 x6 x7 550 x 0, j 1,2, ,7 j

2.1 线性规划的数学模型 Mathematical Model of LP

Chapter 2 线性规划 Linear Programming

2.1.2 线性规划的一般模型 一般地，假设线性规划数学模型中,有m个约束,有n个决策变量 xj(j=1,2…,n),目标函数的变量系数用cj表示, cj称为价值系数。 约束条件的变量系数用 aij 表示 ， aij 称为工艺系数 。 约束条件右 端的常数用 bi 表示 ，bi 称为资源限量 。则线性规划数学模型的 一般表达式可写成

max(min) Z 目标函数：

c1 x1 c2 x2 L cn xn

a11 x 1 a12 x2 L a1n xn (或 , )b1 a x a x L a x (或 , )b 2n n 2 21 1 22 2 约束条件： S .T . L L L L L L L L L L L L L L L a x a x L a x (或 , )b mn n m m1 1 m 2 2 x j 0, j 1, 2, L , n

2.1 线性规划的数学模型 Mathematical Model of LP

Chapter 2 线性规划 Linear Programming

为了书写方便，上式也可写成：

max(min) Z c j x jj 1

n

aij x j (或 , )bi i 1, 2, L , m S .T . j 1 x 0, j 1, 2, L , n j n

在实际中一般xj≥0, 但有时 xj≤0或 xj 无符号限制。

Chapter 2 线性规划 Linear Programming

2. 线性规划的数学模型由三个要素构成决策变量 Decision variables

目标函数

Objective function

约束条件 Constraints 怎样辨别一个模型是线性规划模型？ 其特征是：

(1)问题的目标函数是多个决策变量的线性函数， 通常是求最大值或最小值；(2)问题的约束条件是一组多个决策变量的线性不 等式或等式。 建立一个问题的线性规划模型的一般步骤：

(1)确定决策变量； (3)确定约束条件；

(2)确定目标函数； (4)

确定变量是否有非负约束。

Chapter 2 线性规划 Linear Programming

向量形式： m ax (min) z CX

p j x j ( ) B X 0其中： C (c1 c 2 c n ) x1 X xn

a1 j Pj a mj

b1 B bm

Chapter 2 线性规划 Linear Programming

矩阵形式：

max(min) Z CX AX ( ) B X 0

其中： C (c1 c 2 c n )

a11 a1 n A a m 1 a mn

x1 X xn

b1 B bm

Chapter 2 线性规划 Linear Programming

例2.3 某企业计划生产甲、乙两种产品。这些产品分别 要在A、B、C、D、四种不同的设备上加工。按工艺资 料规定，单件产品在不同设备上加工所需要的台时如下 表所示，企业决策者应如何安排生产计划，使企业总的 利润最大？

设 备产 品 甲

A2

B1

C4

D0

利润(元)2

乙 有效台时

2 12

2 8

0 16

4 12

3

Chapter 2 线性规划 Linear Programming

解：设x1、x2分别为甲、乙两种产品的产量，则数 学模型为：max Z = 2x1 + 3x2

2x1 + 2x2 ≤ 12x1 + 2x2 ≤ 8 s.t. 4x1 ≤ 16

4x2 ≤ 12 x1 ≥ 0 , x2 ≥ 0

练习 1 运输问题

Chapter 2 线性规划 Linear Programming

设有两个砖厂 A1、A2 。其产量分别为23万块与27万

块。它们的砖供应3个工地。其需要量分别为17万块、18万块、和15万块。而自各产地到各工地的运价列表

如下(运价元/万块) :工地 砖厂 B1 B2 B3

A1A2

5060

60110

70160

问如何调运，才使总运费最省？

Chapter 2 线性规划 Linear Programming

解：设 xi j 表示由砖厂Ai 运往工地 Bj 的砖的数量(单位：万块)(i =1 , 2 ; j=1 , 2 , 3),现列表如下： 工地 砖厂 A1 A2 收量(万块) B1 B2 B3 发量 (万块) 23 27 50

x11 x21 17

x12 x22 18

x13 x23 15

因为由砖厂A1 运往三个工地砖的总数应为A1的产量23万块 ,即: x11+ x12+ x13=23 。 同理由砖厂A2 运往三个工地砖的总数应为A2的产量27万块 , 即: x21+ x22+ x23=27 。

Chapter 2 线性规划 Linear Programming

另一方面，两个砖厂运往B1工地的砖的数量应等于B1的需要量17

万块，即： x11+ x21=17;同理可得： x12+ x22=18 ; x13+ x23=15 。 因此调运方案就是求满足前面所有约束条件的x11、 x12、 x13、 x21、 x22、 x23一组变量的非负值。显然，可行的调运方案有很多， 我们就是在这很多个调运方案中，找一个运费最少的方案，所求 数学模型为：

Chapter 2 线性规划 Linear Programming

Minz =50 x11+60 x12+70 x13+60 x21+110 x22

+160 x23s.t. x11+ x12+ x13=23 x21+ x22+ x23=27 x11+ x21=17 x12+ x22=18

x13+ x23=15x11、 x12、 x13、 x21、 x22、 x23 0

本文来源：https://www.bwwdw.com/article/l114.html