9299.net
大学生考试网 让学习变简单
当前位置:首页 >> 管理学 >>

北京理工大学运筹学 吴祈宗 第2章

北京理工大学运筹学 吴祈宗 第2章


第二章
线性规划建模及单纯形法
本章内容重点
? 线性规划模型与解的主要概念
? 线性规划的单纯形法,线性规

划多解分析
? 线性规划应用——建模
1

1.线性规划的概念
例2.1:某工厂拥有 A 、 B 、 C 三种类型 的设备,生产甲、乙两种产品。每件产品 在生产中需要占用的设备机时数,每件产 品可以获得的利润以及三种设备可利用的 时数如下表所示:
产品甲 设备A 设备B 设备C 利润(元/件) 3 2 0 1500 产品乙 2 1 3 2500
2

设备能力 (h) 65 40 75

1.线性规划的概念
问题:工厂应如何安排生产可获得最 大的总利润? 解:设变量 xi 为第 i 种(甲、乙) 产品的生产件数(i=1,2)。根据题意, 我们知道两种产品的生产受到设备能力 (机时数)的限制。对设备 A :两种产品 生产所占用的机时数不能超过65,于是我 们可以得到不等式:3 x1 + 2 x2 ≤ 65; 对设备 B :两种产品生产所占用的机 时数不能超过40,于是我们可以得到不等 式:2 x1 + x2 ≤ 40;
3

1.线性规划的概念
对设备 C :两种产品生产所占用的 机时数不能超过75,于是我们可以得到 不等式:3x2 ≤75 ;另外,产品数不可 能为负,即 x1 ,x2 ≥0。 同时,我们有一个追求目标,即获 取最大利润。于是可写出目标函数z为相 应的生产计划可以获得的总利润: z = 1500x1 + 2500x2 综合上述讨论,在加工时间以及利 润与产品产量成线性关系的假设下,把 目标函数和约束条件放在一起,可以建 立如下的线性规划模型:

4

1.线性规划的概念
目标函数 Max z =1500x1+2500x2 约束条件 s.t. 3x1 + 2x2 ≤ 65

2x1 + x2 ≤ 40
3x2 ≤ 75

x1 ,x2 ≥ 0
5

1.线性规划的概念
这是一个典型的利润最大化的生 产计划问题。其中,“Max”是英文单 词“Maximize”的缩写,含义为“最 大化”;“s.t.”是“subject to”的 缩写,表示“满足于…”。因此,上 述模型的含义是:在给定条件限制下, 求使目标函数 z 达到最大的x1 ,x2 的 取值。
6

1.线性规划的概念
?一般形式
?目标函数:
Max(Min)z = c1x1 + c2x2 + … + cnxn ?约束条件: a11x1+a12x2+…+a1nxn≤( =, ≥ )b1 a21x1+a22x2+…+a2nxn≤( =, ≥ )b2 . . . am1x1+am2x2 +…+amnxn≤( =, ≥ )bm x1 ,x2 ,… ,xn ≥ 0
7

?标准形式

1.线性规划的概念

?目标函数:

Max z = c1x1 + c2x2 + … + cnxn ?约束条件: A11x1 + a12x2 + … + a1nxn = b1 a21x1 + a22x2 + … + a2nxn = b2 . . . am1x1 + am2x2 + … + amnxn = bm
x1 ,x2 ,… ,xn
≥ 0
8

1.线性规划的概念
可以看出,线性规划的标准 形式有如下四个特点:目标最大 化、约束为等式、决策变量均非 负、右端项非负。 对于各种非标准形式的线性 规划问题,我们总可以通过以下 变换,将其转化为标准形式:
9

1.线性规划的概念
1.极小化目标函数的问题: 设目标函数为 Min f = c1x1 + c2x2 + … + cnxn 则可以令 z = -f ,该极小化问 题与下面的极大化问题有相同的最优 解,即 Max z = -c1x1 - c2x2 - … - cnxn 但必须注意,尽管以上两个问题 的最优解相同,但他们最优解的目标 函数值却相差一个符号,即 Min f = - Max z

10

1.线性规划的概念
2、约束条件不是等式的问题: 设约束条件为 ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引进一个新的变量s ,使它等 于约束右边与左边之差 s =bi–(ai1 x1 + ai2 x2 + … + ain xn ) 显然,s 也具有非负约束,即s≥0, 这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn+s = bi
11

1.线性规划的概念
当约束条件为 ai1 x1+ai2 x2+ … +ain xn ≥ bi 时,类似地令 s =(ai1 x1+ai2 x2+ … +ain xn)- bi 显然, s 也具有非负约束,即 s≥0, 这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn-s = bi
12

1.线性规划的概念

为了使约束由不等式成为等式 而引进的变量 s 称为“松弛变量”。 如果原问题中有若干个非等式约束, 则将其转化为标准形式时,必须对 各个约束引进不同的松弛变量。

13

1.线性规划的概念
例2.2:将以下线性规划问题转化为标 准形式

Min f = s. t. 2.3 4.1 x1 +

3.6 x1 - 5.2 x2 + 1.8 x3 x1 + 5.2 x2 - 6.1 x3 ≤15.7 x1 + 3.3 x3 ≥8.9 x2 + x3 = 38

x1 , x2 , x3 ≥ 0

解:首先,将目标函数转换成极大化: 令 z= -f = -3.6x1+5.2x2-1.8x3 14

1.线性规划的概念
其次考虑约束,有2个不等式约束,引进 松弛变量x4,x5 ≥0。 于是,我们可以得到以下标准形式的线性 规划问题: Max z = - 3.6 x1 + 5.2 x2 - 1.8 x3 s.t. 2.3x1+5.2x2-6.1x3+x4= 15.7 4.1x1+3.3x3-x5= 8.9 x1+x2+x3= 38 x1 ,x2 ,x3 ,x4 ,x5 ≥ 0
15

1.线性规划的概念
3. 变量无符号限制的问题: 在标准形式中,必须每一个变量均有 非负约束。当某一个变量 xj没有非负 约束时,可以令 xj = xj’- xj” 其中 xj’≥0,xj”≥0 即用两个非负变量之差来表示一个无 符号限制的变量,当然xj 的符号取决 于xj’和xj”的大小。
16

1.线性规划的概念
4.右端项有负值的问题: 在标准形式中,要求右端项必须每一 个分量非负。当某一个右端项系数为 负时,如 bi<0,则把该等式约束两 端同时乘以-1,得到: -ai1 x1-ai2 x2- … -ain xn = -bi

17

1.线性规划的概念
例2.3:将以下线性规划问题转化为 标准形式
Min f= -3 x1 + 5 x2 + 8 x3 - 7 x4 s.t. 2 x1 - 3 x2 + 5 x3 + 6 x4 ≤ 28 4 x1 + 2 x2 + 3 x3 - 9 x4 ≥ 39 6 x2 + 2 x3 + 3 x4 ≤ - 58 x1 , x3 , x 4 ≥ 0

18

1.线性规划的概念

解:首先,将目标函数转换成极大化: 令 z = -f = 3x1–5x2–8x3+7x4 ; 其次考虑约束,有3个不等式约 束,引进松弛变量x5 ,x6 ,x7 ≥0 ; 由于x2 无非负限制,可令x2=x2’-x2”, 其中 x2’≥0,x2”≥0 ; 由于第3个约束右端项系数为-58, 于是把该式两端乘以-1 。 于是,我们可以得到以下标准形 式的线性规划问题:
19

1.线性规划的概念
Max z = 3x1–5x2’+5x2”–8x3 +7x4 s.t. 2x1–3x2’+3x2”+5x3+6x4+x5= 28 4x1+2x2’-2x2”+3x3-9x4-x6= 39 -6x2’+6x2”-2x3-3x4-x7 = 58 x1 ,x2’,x2”,x3 ,x4 ,x5 ,x6 ,x7 ≥ 0

20

2.线性规划的图解法
线性规划的图解法(解的几 何表示): 对于只有两个决策变量的 线性规划问题,可以二维直角 坐标平面上作图表示线性规划 问题的有关概念,并求解。 图解法求解线性规划问题 的步骤如下:
21

2.线性规划的图解法
(1)建立直角坐标系:
分别取决策变量x1 ,x2 为坐标向量。

22

2.线性规划的图解法
(2)绘制可行域:

对每个约束(包括非负约束)条 件,作出其约束半平面(不等式)或 约束直线(等式)。
各半平面与直线交出来的区域若 存在,其中的点为此线性规划的可行 解。称这个区域为可行集或可行域。 然后进行下步。否则若交为空,那么 该线性规划问题无可行解。
23

2.线性规划的图解法
(3)绘制目标函数等值线,并移动 求解:

目标函数随着取值不同,为一 族相互平行的直线。 首先,任意给定目标函数一个 值,可作出一条目标函数的等值线 (直线); 然后,确定该直线平移使函数 值增加的方向; 最后,依照目标的要求平移此 直线。

24

2.线性规划的图解法
? 结果

若目标函数等值线能够移动 到既与可行域有交点又达到最 优的位置,此目标函数等值线 与可行域的交点即最优解(一 个或多个),此目标函数的值 即最优值。 否则,目标函数等值线与可 行域将交于无穷远处,此时称 无有限最优解。
25

2.线性规划的图解法
例2.4:某工厂拥有 A 、 B 、 C 三种 类型的设备,生产甲、乙两种产品。 每件产品在生产中需要占用的设备机 时数,每件产品可以获得的利润以及 三种设备可利用的时数如下表所示:
产品甲 设备A 设备B 设备C 利润(元/件) 3 2 0 1500 产品乙 2 1 3 2500
26

设备能力 (h) 65 40 75

2.线性规划的图解法
问题:工厂应如何安排生产可获得 最大的总利润?用图解法求解。

解:设变量xi 为第i种(甲、乙)产 品的生产件数(i=1,2)。根据前面分 析,可以建立如下的线性规划模型: Max z = 1500 x1 + 2500 x2
s.t. 3x1+ 2x2 ≤ 65 (A)

2x1+ x2 ≤ 40
3x2 ≤ 75

(B)
(C)

x1 , x2 ≥ 0

(D, E)

27

2.线性规划的图解法

例题作图(1)

按照图解法的步骤: (1)以决策变量x1 ,x2 为坐标向量 作平面直角坐标系;

28

2.线性规划的图解法
(2)对每个约束(包括非负约 束)条件作出直线(A、B、C、 D、E),并通过判断确定不等 式所决定的半平面。 各约束半平面交出来的区 域即可行集或可行域如下图阴 影所示。

29

2.线性规划的图解法
?

例题作图(2)

第2步图示(1) 分别作出各约束半平面
3x1+ 2x2 ≤ 65

2x1+ x2 ≤ 40

3x2 ≤ 75

x1 ≥ 0

X2 ≥ 0

30

2.线性规划的图解法
?

例题作图(3)

第2步图示(2) 各约束半平面的交-可行域

31

2.线性规划的图解法
(3)任意给定目标函数一个值(例 如37500)作一条目标函数的等值 线,并确定该等值线平移后值增加 的方向(向上移动函数值增大), 平移此目标函数的等值线,使其达 到既与可行域有交点又不可能使值 再 增 加 的 位 置 , 得 到 交 点 (5,25)T ,即最优解。此目标函数 的值为70000。
32

2.线性规划的图解法
?第3步图示
函数值增大

例题作图(4)

作出目标函数等值线

2.线性规划的图解法
?

例题作图(5)

第3步图示(2) 求出最优解

2.线性规划的图解法
根据上面的过程

我们得到这个线性规划的 最优解 x1=5、x2=25, 最优值 z = 70000 即最优方案为生产甲产品5件、 乙产品25件,可获得最大利润 为70000元。
35

2.线性规划的图解法
?

线性规划的解有如下几种情况: 1、存在有限最优解:
唯一最优解;无穷多个最优解

2、无有限最优解(无界解) 3、无可行解(可行域空)

36

2.线性规划的图解法
例2.5:在例2.4的线性规划模型 中,如果目标函数变为: Max z = 1500 x1 + 1000 x2 那么,最优情况下目标函数的等值线 与直线(A)重合。这时,最优解有 无 穷 多 个 , 是 从 点 (5,25)T 到 点 (15,10)T 线段上的所有点,最优值为 32500。如下图所示:
37

2.线性规划的图解法
(15, 10)T

无穷多解的情况

38

2.线性规划的图解法
例2.6:在例2.4的线性规划模型中, 如果约束条件(A)、(C)变为: 3 x1 + 2 x2 ≥ 65 3 x2 ≥ 75 (A’) (C’)

并且去掉(D、E)的非负限制。那么, 可行域成为一个上无界的区域。这时, 没有有限最优解,如下图所示:
39

2.线性规划的图解法

无有限解的情况

40

2、线性规划的图解法
例2.7:在例2.4的线性规划模型中, 如果增加约束条件(F)为: x1 + x2 ≥ 40 (F) 那么,可行域成为空的区域。这时, 没有可行解,显然线性规划问题无 解。如下图所示:

41

2.线性规划的图解法

无可行解的情况

42

2.线性规划的图解法
根据以上例题,进一步分析讨 论可知线性规划的可行域和最优解 有以下几种可能的情况 1.可行域为封闭的有界区域 (a)有唯一的最优解; (b)有无穷多个最优解; 2.可行域为封闭的无界区域 (c)有唯一的最优解;
43

2.线性规划的图解法

(d)有无穷多个最优解; (e)目标函数无界(即虽有可行解, 但在可行域中,目标函数可以无限增 大或无限减少),因而没有有限最优解。 3.可行域为空集 (f)没有可行解,原问题无最优解

44

2.线性规划解的概念
熟悉下列一些解的概念
? 可行解、可行解集(可行域) ? 最优解、最优值 ? 基、基变量、非基变量 ? 基本解、基本可行解 ? 可行基、最优基
45

2.线性规划解的概念
线性规划的基、基本解与基本可行解
在一般情况下,由于图解法无法解决三个 变量以上的线性规划问题,对于n个变量的线 性规划问题,我们必须用解方程的办法来求 得可行域的极点。再来进一步考察前例。 例2.8 把例2.1的线性规划模型标准化, 引入松驰变量 x3 ,x4 ,x5 ≥ 0,得到
46

2.线性规划解的概念
Max z = 1500 x1 + 2500 x2 s.t. 3x1+2x2+x3= 65 (A) 2x1+x2+x4= 40 (B) 3x2+x5= 75 (C) x1 ,x2 ,x3 ,x4 ,x 5 ≥ 0 用(D)(E)(F)(G)(H) 分别表示x1 = 0、x2 = 0、x3 = 0、 x4 = 0、x5 = 0 。 这里一共有8个约束条件,其中3个等 式约束
47

2.线性规划解的概念
(一般情况下,等式约束的个 数少于决策变量的个数),5个变 量非负约束(与决策变量个数相 同)。每5个方程若线性无关可解 得一个点,我们可以看到前例图解 法得到的区域中每两条直线的交点 与此例的各个方程有如下关系:见 下图。
48

2.线性规划解的概念

平面上各不等式约束半平面得交点

49

2.线性规划解的概念

由上图可以看出: 直线A、B的交点对应于约束条件(A)、(B)、 (C)、(F)、(G)的解,即: x(1) = (15,10,0,0,45)T 直线A、C的交点对应于约束条件(A)、(B)、 (C)、(F)、(H)的解,即: x(2) = (5,25,0,5,0)T 直线A、D的交点对应于约束条件(A)、(B)、 (C)、(D)、(F)的解,即: x(3) = (0,32.5,0,7.5,-22.5)T
50

2.线性规划解的概念
直线A、E的交点对应于约束条件(A)、(B)、 (C)、(E)、(F)的解,即: x(4) = (65/3,0,0,-10/3,75)T 直线 B、C 的交点对应于约束条件(A)、( B)、 (C)、(G)、(H)的解,即: x(5) = (7.5,25,-7.5,0,0)T 直线 B、 D 的交点对应于约束条件(A)、( B)、 (C)、(D)、(G)的解,即: x(6) = (0,40,-15,0,-45)T
51

? ? ? ?

2.线性规划解的概念
直线B、E的交点对应于约束条件(A)、(B)、 (C)、(E)、(G)的解,即: x(7) = (20,0,5,0,75)T 直线C、D的交点对应于约束条件(A)、(B)、 (C)、(D)、(H)的解,即: x(8) = (0,25,15,15,0)T 直线C、E无交点(C、E相互平行) 直线D、E的交点对应于约束条件(A)、(B)、 (C)、(D)、(E)的解,即: x(9) = (0,0,65,40,75)T
52

2.线性规划解的概念

上图各约束直线的交点是由以下方 法得到:在标准化的等式约束中,令其中 某两个变量为零,得到其他变量的唯一解, 这个解就是相应交点的坐标,如果某一交 点的坐标 (x1 , x2 , x3 , x4 , x5 )T全为 非负,则该交点就对应于线性规划可行域 的一个极点(如A、B,A、C,B、E,C、D 和D、E的交点);如果某一交点的坐标中 至少有一个分量为负值(如A、D,A、E, B、C和B、D的交点),则该交点不是可行 域的极点。
53

2.线性规划解的概念
由上图可知,A、B交点对应于 x3 = 0, x4 = 0,在等式约束中令x3 = 0,x4 = 0,得 到x1 =15,x2 = 10,x5 = 45。即A、B交点对 应于极点x= (x1 ,x2 ,x3 ,x4 ,x5)T =(15, 10,0,0,45)T。由于所有分量都为非负, 因此A、B交点是可行域的极点。又知,B、C 交点对应于 x4= 0,x5= 0,在等式约束中令 x4 = 0,x5 = 0,得到x1 =7.5,x2 = 25,x3 = -7.5。即B、C交点对应于点 x = (x1 ,x2 , x3 , x4, , x5)T=(-7.5,25,-7.5,0,0)T。 由于有负分量,因此B、C交点不是可行域的 极点。我们同样可以讨论其他交点的情况。
54

2.线性规划解的概念
下面讨论线性规划标准形式的基、基 本解、基本可行解的概念。 考虑线性规划标准形式的约束条件: Ax=b,x≥0 其中A为m×n的矩阵,n>m,秩(A) = m, b ? Rm 。在约束等式中,令n维空间的解 向量: x = (x1,x2,…,xn)T
55

2.线性规划解的概念

中n-m个变量为零,如果剩下的m个变量 在线性方程组中有唯一解,则这n个变量 的值组成的向量x就对应于n维空间Rn中若 干个超平面的一个交点。当这n个变量的 值都是非负时,这个交点就是线性规划可 行域的一个极点。 根据以上分析,我们建立以下概念: (1)线性规划的基:对于线性规划 的约束条件 Ax=b, x≥0
56

2.线性规划解的概念
设B是A矩阵中的一个非奇异(可逆)的 m×m子矩阵,则称B为线性规划的一个基。 用前文的记号,A=( p1 ,p2 ,…,pn ) , 其中 pj=( a1j ,a2j ,…,amj )T ? Rm , 任取A中的m个线性无关列向量 pj ? Rm 构成矩阵 B=( pj1 ,pj2 ,…,pjm )。那 么B为线性规划的一个基。 我 们 称 对 应 于 基 B 的 变 量 xj1 , xj2 ,…, xjm 为基变量;而其他变量称为 非基变量。
57

2.线性规划解的概念
可以用矩阵来描述这些概念。 设B是线性规划的一个基,则A可以表示为 A=[ B , N ] x也可相应地分成

xB

x=
xN
其中xB为m维列向量,它的各分量称为基变量, 与基 B 的列向量对应; xN 为 n-m 列向量,它的各 分量称为非基变量,与非基矩阵N的列向量对应。 这时约束等式Ax=b可表示为
58

2.线性规划解的概念
xB

B,N
xN

= b

或 如果对非基变量 xN取确定的值,则xB有唯 一的值与之对应
xB = B-1b - B-1NxN

BxB + NxN = b

特别,当取xN = 0,这时有xB=B-1b。关于 这类特别的解,有以下概念。
59

2.线性规划解的概念
(2)线性规划问题的基本解、基 本可行解和可行基: 对于线性规划问题,设矩阵 B = ( pj1 , pj2 ,…, pjm ) 为一个基,令 所有非基变量为零,可以得到m个关于 基变量 xj1 ,xj2 , … ,xjm 的线性方程, 解这个线性方程组得到基变量的值。 我们称这个解为一个基本解;若得到 的基变量的值均非负,则称为基本可 行解,同时称这个基B为可行基。
60

2.线性规划解的概念
矩阵描述为,对于线性规划的解

xB x= xN
=

B-1b
0

称为线性规划与基 B 对应的基本解。若 其中 B-1b?0,则称以上的基本解为一基 本可行解,相应的基B称为可行基。
61

2.线性规划解的概念
我们可以证明以下结论:线性规 划的基本可行解就是可行域的极点。 这个结论被称为线性规划的基本定 理,它的重要性在于把可行域的极点 这一几何概念与基本可行解这一代数 概念联系起来,因而可以通过求基本 可行解的线性代数的方法来得到可行 域的一切极点,从而有可能进一步获 得最优极点。
62

2.线性规划解的概念
例2.9: 考虑例2.8的线性规划模型

Max z = 1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75

x1 , x2 , x3 , x4 , x5 ≥ 0
注意,线性规划的基本解、基本可行 解(极点)和可行基只与线性规划问 题标准形式的约束条件有关。
63

2.线性规划解的概念
3 2 1 0 0 A = [P1 ,P2 ,P3 ,P4 ,P5] = 2 1 0 1 0 0 3 0 0 1 A矩阵包含以下10个3×3的子矩阵: B1=[p1 ,p2 ,p3] B2=[p1 ,p2 ,p4] B3=[p1 ,p2 ,p5] B4=[p1 ,p3 ,p4] B5=[p1 ,p3 ,p5] B6=[p1 ,p4 ,p5] B7=[p2 ,p3 ,p4] B8=[p2 ,p3 ,p5] B9=[p2 ,p4 ,p5] B10=[p3 ,p4 ,p5]

64

其中?B4?= 0,因而B4不是该线性规划问题的基。 其余均为非奇异方阵,因此该问题共有9个基。 对于基 B3=[p1 ,p2 ,p5],令非基变量 x3 = 0, x4 = 0,在等式约束中令x3 = 0,x4 = 0,解线性 方程组: 3 x1 + 2 x2 + 0 x5 = 65 2 x1 + x2 + 0 x5 = 40 0 x1 + 3 x2 + x5 = 75 得到x1 =15,x2 = 10,x5 = 45,对应的基本可行 解: x=(x1 , x2 , x3 , x4 , x5)T=(15 , 10 , 0 , 0 , 45)T。于是对应的基B3是一个可行基。
65

2.线性规划解的概念

2.线性规划解的概念
类似可得到 x(2) = (5,25,0,5,0)T (对应B2) x(7) = (20,0,5,0,75)T (对应B5) x(8) = (0,25,15,15,0)T (对应B7) x(9) = (0,0,65,40,75)T (对应B10) 是基本可行解; 而x(3)= (0,32.5,0,7.5,-22.5)T(对应B9) x(4)= (65/3,0,0,-10/3,75)T (对应B6) x(5)= (7.5,25,-7.5,0,0)T (对应B1) x(6) = (0,40,-15,0,-45)T (对应B8) 是基本解。

66

2.线性规划解的概念
因此,对应基本可行解(极点) 的 B2 B3 B5 B7 B10都是可行基。 这里指出了一种求解线性规划问题的可 能途径,就是先确定线性规划问题的基, 如果是可行基,则计算相应的基本可行解 以及相应解的目标函数值。由于基的个数 是有限的(最多个),因此必定可以从有 限个基本可行解中找到最优解。

67

3.单 纯 形 法
利用求解线性规划问题基本可行 解(极点)的方法来求解较大规模的 问题是不可行的。单纯形法的基本思 路是有选择地取基本可行解,即是从 可行域的一个极点出发,沿着可行域 的边界移到另一个相邻的极点,要求 新极点的目标函数值不比原目标函数 值差。
68

3.单 纯 形 法

由上节的讨论可知,对于线性规划的一 个基,当非基变量确定以后,基变量和目标 函数的值也随之确定。因此,一个基本可行 解向另一个基本可行解的移动,以及移动时 基变量和目标函数值的变化,可以分别由基 变量和目标函数用非基变量的表达式来表示。 同时,当可行解从可行域的一个极点沿着可 行域的边界移动到一个相邻的极点的过程中, 所有非基变量中只有一个变量的值从0开始 增加,而其他非基变量的值都保持0不变。
69

3.单 纯 形 法
初始基本可行解

是否最优解或 无限最优解? Y

N

沿边界找新 的基本可行解

结束
单纯形法的基本过程
70

3.单 纯 形 法
考虑标准形式的线性规划问题: Max z = c1x1 + c2x2 + … + cnxn s.t. a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 . 2 + … + a2n xn = b2 x . . am1 x1 + am2 x2 + … + amn xn = bm x1 , x2 , … , xn ≥ 0

x= .
.

x1 x2
xn

C= .
.

c1 c2
cn

B= .
.

b1 b2
bn

A= .
.

a11 a12..a1n a21 a22..a2n
. . . .

am1 am2..amn 71

3.单 纯 形 法

这里,矩阵A表示为: A = ( p1 ,p2 ,…,pn ) , 其中 pj = ( a1j ,a2j ,…,amj )T ? Rm。 若找到一个可行基,无防设 B = ( p1 ,p2 ,…,pm ) ,则m个基变量 为 x1 , x2 , …, xm ,n-m 个非基变量为 xm+1 ,xm+2 ,…,xn 。通过运算,所有的 基变量都可以用非基变量来表示:
72

3.单 纯 形 法
x1=b’1-(a’1m+1xm+1+a’1m+2xm+2+…+a’1nxn) x2=b’2-(a’2m+1xm+1+a’2m+2xm+2+…+a’2nxn)( 2-11 )
.` . .

xm=b’m-(a’mm+1xm+1+a’mm+2xm+2+…+a’mnxn)
把它们代入目标函数,得 z = z’+?m+1xm+1+?m+2xm+2+…+?nxn ( 2-12 ) 其中 ?j=cj-(c1a’1j + c2a’2j + … + cm a’mj) 我们把由非基变量表示的目标函数形式称为基 B相应的目标函数典式。
73

3.单 纯 形 法
单纯形法的基本步骤可描述如下:
(1)寻找一个初始的可行基和相 应基本可行解(极点),确定基变量、 非基变量以及基变量、非基变量(全 部等于0)和目标函数的值,并将目标 函数和基变量分别用非基变量表示;

74

3.单 纯 形 法
(2)在用非基变量表示的目标函 数表达式(2-12)中,我们称非基变 量xj的系数(或其负值)为检验数记为 ?j 。若 ?j > 0,那么相应的非基变量 xj ,它的值从当前值0开始增加时,目 标函数值随之增加。这个选定的非基 变量 xj 称为“进基变量”,转(3)。 如果任何一个非基变量的值增加都不 能使目标函数值增加,即所有 ?j 非正, 则当前的基本可行解就是最优解,计 算结束;
75

3.单 纯 形 法
(3)在用非基变量表示的基变量 的表达式(2-11)中,观察进基变量 增加时各基变量变化情况,确定基变 量的值在进基变量增加过程中首先减 少到0的变量xr ,满足, ?=min?b’i /a’ij ?a’ij > 0? = b’r /a’rj 这个基变量 xr 称为“出基变量”。当 进基变量的值增加到 ? 时,出基变量 xr的值降为0时,可行解就移动到了相 邻的基本可行解(极点),转(4)。
76

3.单 纯 形 法

如果进基变量的值增加时,所有基变量 的值都不减少,即所有 a’ij 非正,则表 示可行域是不封闭的,且目标函数值随 进基变量的增加可以无限增加,此时, 不存在有限最优解,计算结束; (4)将进基变量作为新的基变量, 出基变量作为新的非基变量,确定新的 基、新的基本可行解和新的目标函数值。 在新的基变量、非基变量的基础上重复 (1)。
77

3.单 纯 形 法
例2.10:用单纯形法的基本思路 解例2.8的线性规划问题 Max z = 1500 x1 + 2500 x2

s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75

x1 , x2 , x3 , x4 , x5 ≥ 0
78

3.单 纯 形 法
第一次迭代: (1)取初始可行基 B10= (p3 , p4 , p5), 那么x3 ,x4 ,x5为基变量,x1 ,x2为非 基变量。将基变量和目标函数用非基变 量表示: z=1500x1+2500x2 x3 = 65 - 3 x1 - 2 x2 x4 = 40 - 2 x1 - x2 x5 = 75 - 3 x2 当非基变量 x1 ,x2=0时,相应的基变量 和目标函数值为x3=65,x4=40,x5= 75, z = 0,得到当前的基本可行解: x=(0,0,65,40,75)T,z = 0 。这个解对 79 应于图2-7的D、E交点。

3.单 纯 形 法
(2)选择进基变量。在目标函数 z = 1500 x1 + 2500 x2 中,非基变量 x1 , x2的系数都是正数,因此 x1 ,x2进基都 可以使目标函数 z 增大,但 x2 的系数为 2500,绝对值比 x1 的系数1500大,因此 把x2作为进基变量可以使目标函数z增加 更快。选择x2为进基变量,使x2的值从0 开始增加,另一个非基变量 x1保持零值 不变。
80

3.单 纯 形 法 (3)确定出基变量。在约束条件
x3 = 65 - 3 x1 - 2 x2 x4 = 40 - 2 x1 - x2 x5 = 75 - 3 x2 中,由于进基变量x2在3个约束条件中的 系数都是负数,当x2的值从0开始增加时, 基变量x3 、x4 、x5的值分别从当前的值 65、40和75开始减少,当 x2 增加到25时, x5首先下降为0成为非基变量。这时,新 的基变量为x3 、x4 、x2 ,新的非基变量 为x1 、x5 ,当前的基本可行解和目标函
数值为: x = (0,25,15,15,0)T , z = 62500。 81 这个解对应于图中的C、D交点。

3.单 纯 形 法
第二次迭代: (1)当前的可行基为B7 = (p2 , p3 , p4),那么x2 ,x3 ,x4为基变量,x1 ,x5 为非基变量。将基变量和目标函数用非 基变量表示: z = 62500 + 1500 x1 – (2500/3) x5 x2 = 25 – (1/3) x5 x3 = 15 - 3 x1 + (2/3) x5 x4 = 15 - 2 x1 + (1/3) x5
82

3.单 纯 形 法
(2)选择进基变量。在目标函数 z = 62500 + 1500 x1 – (2500/3) x5 中,非基变量 x1 的系数是正数,因此 x1进基可以使目标函数 z增大,于是选 择 x1 进基,使 x1 的值从0开始增加, 另 一个非基变量x5保持零值不变。 (3) 确 定 出 基 变 量 。 在 约 束 条 件 x2 = 25 – (1/3) x5 x3 = 15 - 3 x1 + (2/3) x5 x4 = 15 - 2 x1 + (1/3) x5
83

3.单 纯 形 法
中,由于进基变量 x1 在两个约束条件 中的系数都是负数,当x1的值从0开始 增加时,基变量 x3 、x4 的值分别从当 前的值15、15开始减少,当x1增加到5 时,x3首先下降为0成为非基变量。这 时,新的基变量为x1 、x2 、x4 ,新的 非基变量为 x3 、x5 ,当前的基本可行 解和目标函数值为: x = (5,25,0,5,0)T , z = 70000。 这个解对应于图中的A、C交点。
84

3.单 纯 形 法
第三次迭代: (1)当前的可行基为 B2 = (p1 , p2 , p4 ),那么 x1 ,x2 ,x4 为基变 量, x3 ,x5 为非基变量。将基变量 和目标函数用非基变量表示: z = 70000 – 500 x3 – 500 x5 x1 = 5 – (1/3) x3 + (2/9) x5 x2 = 25 – (1/3) x5 x4 = 5 + (2/3) x3 – (1/9) x5
85

3.单 纯 形 法
(2)选择进基变量。在目标函数 z = 70000 – 500 x3 – 500 x5 中,非 基变量 x3 、 x5 的系数均不是正数,因 此进基都不可能使目标函数z增大,于 是得到最优解,x* = (5,25,0,5, 0)T ,最优目标值为 z* = 70000。这个 解对应于图2-7的A、C交点。我们也称 相应的基B2 = (p1 , p2 , p4)为最优基。 计算结束。
86

3、 单 纯 形 法
?
?

表格单纯形法
考虑: bi > 0 i = 1 , … , m

Max z = c1 x1 + c2 x2 + … + cn xn s.t. a11 x1 + a12 x2 + … + a1n xn ≤ b1 a21 x1 + a22 x2 + … + a2n xn ≤ b2 …… …… am1 x1 + am2 x2 + … + amn xn ≤ bm x1 ,x2 ,… ,xn ≥ 0
87

3、 单 纯 形 法
?

加入松弛变量:
Max z = c1 x1 + c2 x2 + … + cn xn s.t. a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2 …… …… am1 x1 + am2 x2 + … + amn xn+ xn+m = bm x1 ,x2 ,… ,xn ,xn+1 ,… ,xn+m ≥ 0
88

3、 单 纯 形 法
显然,xj = 0 j = 1, … , n ; xn+i = bi i = 1 , … , m 是基本可行解 对应的基是单位矩阵。
以下是初始单纯形表:

CB

XB b1 b2 ┇ bm f

cn+1 xn+1 cn+2 xn+2 ┇ ┇ cn+m xn+m -z
其中:f = -∑ cn+i bi
i=1

c1 x1 a11 a21 ┇ am1 σ1

… … … … ┇ … …
m
i=1

cn cn+1 xn xn+1 a1n a1n+1 a2n a2n+1 ┇ ┇ amn amn+1 σn 0

… … … … ┇ … …

cn+m xn+m θ i a1n+m θ 1 a2n+m θ 2 ┇ ┇ amn+m θ m 0

m

?j = cj -∑ cn+i aij
i , j = 1, … , m

为检验数

cn+i = 0

i= 1,…,m

an+i,i = 1 , an+i,j = 0 ( j≠i )

89

3、 单 纯 形 法
例2.10。化标准形式: Max z =1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 ≥ 0
0 x3 1 0 0 0 1 0 0 0 1/3 -2/3 0 -500 0 x4 0 1 0 0 0 1 0 0 0 1 0 0 0 x5 0 0 1 0 -2/3 -1/3 1/3 -2500/3 -2/ 9 1/9 1/3 -500 θ i 32.5 40 25 5 7. 5 1500 2500 x1 X2 65 3 2 40 2 1 75 0 (3) 0 1500 2500* 15 (3) 0 15 2 0 25 0 1 -62500 1500* 0 5 1 0 5 0 0 25 0 1 -70000 0 0

CB 0 0 0 -z 0 0 2500 -z 1500 0 2500 -z

XB x3 x4 x5 x3 x4 x2 x1 x4 x2

最优解 x1 = 5 x2 = 25 最优值 z* = 70000

x4 = 5(松弛标量,表示B设备有5个机时的剩余)

90

3、 线 性 规 划
?

注意:单纯形法中, 1、每一步运算只能用矩阵初等行 变换; 2、表中第3列的数总应保持非负 (≥ 0); 3、当所有检验数均非正(≤ 0) 时,得到最优单纯形表。

91

3.单 纯 形 法
一般情况的处理及注意事项的强 调:主要是讨论初始基本可行解不明显 时,常用的方法。要弄清它的原理,并 通过例题掌握这些方法,同时进一步熟 悉用单纯形法解题。 考虑一般问题: bi > 0 i = 1 , … , m
92

3.单 纯 形 法
Max z = c1x1 + c2x2 + … + cnxn s.t. a11x1+a12x2 +…+a1nxn = b1 a21x1+a22x2 +…+a2nxn = b2 . . . am1x1+am2x2+…+amnxn = bm x1 ,x2 ,… ,xn ≥ 0
93

大M法:

3.单 纯 形 法

引入人工变量 xn+i ≥ 0 (i = 1 , … , m)及充分大正数 M 。得到: Max z = c1x1 +c2x2 +…+cnxn -Mxn+1 -…-Mxn+m s.t. a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2 . . . am1 x1 + am2 x2 + … + amn xn + xn+m = bm x1 ,x2 ,… ,xn ,xn+1 ,… ,xn+m ≥0
94

3.单 纯 形 法
显然,xj = 0 j=1, … , n ; xn+i = bi i =1 , … , m
是基本可行解。 对应的基是单位矩阵。 结论:若得到的最优解满足 xn+i = 0 i = 1 , … , m 则是原问 题的最优解;否则,原问题无可行解。

95

3.单 纯 形 法
? ? ?

两阶段法: 构造: Max z = - xn+1 - xn+2 - … - xn+m
a11x1+a12x2+ … +a1nxn+xn+1 = b1 a21x1+a22x2+ … +a2nxn+xn+2 = b2
. . .

引入人工变量 xn+i ≥ 0,i = 1 ,…, m;

s.t.

am1x1+am2x2+ … +amnxn+xn+m = bm x1,x2 ... xn ,xn+1,…,xn+m ≥ 0
96

3.单 纯 形 法
第一阶段求解上述问题:

显然,xj = 0 j=1, … , n ;
xn+i = bi i =1 , … , m
是基本可行解,它对应的基 是单位矩阵。

结论:若得到的最优解满足 xn+i=0 i=1 , … , m 则是原问题的基本可行
解;否则,原问题无可行解。 得到原问题的基本可行解后,第二 阶段求解原问题。

97

3.单 纯 形 法
例2.11:(LP) Max z = 5x1 + 2x2 + 3x3 - x4 s.t. x1 + 2x2 + 3x3 = 15 2x1 + x2 + 5x3 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x 2 , x3 , x4 ≥ 0
98

3.单 纯 形 法
Max z = 5x1+2x2+3x3-x4-Mx5-Mx6 s.t. x1+2x2+3x3+x5 =15 2x1+x2+5x3+x6 =20 x1+2x2+4x3+x4 =26 x1 ,x2 ,x3 ,x4 ,x5 ,x6 ≥ 0
99

3.单 纯 形 法
?大M法
CB -M -M -1 -z -M 3 -1 -z 2 3 -1 -z 2 5 -1 -z x2 x1 x4 x2 x3 x4 x5 x3 x4 XB x5 x6 x4

(LP - M)
3 x3 3 (5) 4 8M+7 0 1 0 0 0 1 0 0 1/3 7/3 1 -25/3 -1 x4 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 -M -M x5 x6 1 0 0 1 0 0 0 0 1 -3/5 0 1/5 0 -4/5 0 -8/5M-7/5 5/7 -3/7 -1/7 2/7 -6/7 -2/7 -M-13/7 -M-2/7 2/3 -1/3 -1/3 2/3 -1 0 -M-2/3 -M+8/3 θ i 5 4 6.5 15/7 20 25/3

5 2 x1 x2 15 1 2 20 2 1 26 1 2 35M+26 3M+6 3M+4 3 -1/5 (7/5) 4 2/5 1/5 10 -3/5 6/5 3M-2 -M/5+16/5 7/5M+13/5 15/7 -1/7 1 25/7 (3/7) 0 52/7 -3/7 0 -53/7 25/7 0 10/3 0 1 25/3 1 0 11 0 0 -112/3 0 0

25/3

? 得到最优解:(25/3,10/3,0,11)T ? 最优目标值:112/3

100

3.单 纯 形 法
第一阶段问题(LP - 1) Max z = - x5 - x6 s.t. x1 + 2x2 + 3x3 + x5 = 15 2x1 + x2 + 5x3 + x6 = 20 x1 + 2x2 + 4x3 + x4 = 26


x1 , x2 , x3 , x4 , x5 , x6

0
101

3.单 纯 形 法
?第一阶段
CB -1 -1 0 -z -1 0 0 -z 0 0 0 -z x2 x3 x4 x5 x3 x4 XB x5 x6 x4 15 20 26 35 3 4 10 3 15/7 25/7 52/7 0 0 x1 1 2 1 3 -1/5 2/5 -3/5 -1/5 -1/7 3/7 -3/7 0

(LP - 1)
0 x2 2 1 2 3 (7/5) 1/5 6/5 7/5 1 0 0 0 0 x3 3 (5) 4 8 0 1 0 0 0 1 0 0 0 x4 0 0 1 0 0 0 1 0 0 0 1 0 -1 x5 1 0 0 0 1 0 0 0 5/7 -1/7 -6/7 -1 -1 x6 0 1 0 0 -3/5 1/5 -4/5 -8/5 -3/7 2/7 -2/7 -1 θi 5 4 6.5 15/7 20 25/3

25/3

? 得到原问题的基本可行解:
(0,15/7,25/7,52/7)T
102

3.单 纯 形 法
?第二阶段
CB 2 3 -1 -z 2 5 -1 -z x2 x1 x4 XB x2 x3 x4 15/7 25/7 52/7 -53/7 10/3 25/3 11 -112/3

把基本可行解填入表中
5 x1 -1/7 (3/7) -3/7 25/7 0 1 0 0 2 x2 1 0 0 0 1 0 0 0 3 x3 0 1 0 0 1/3 7/3 1 -25/3 -1 x4 0 0 1 0 0 0 1 0 θ
i

25/3

? 得到原问题的最优解:(25/3,10/3,0,11)T

?最优目标值:112/3

103

3.单 纯 形 法
注意:单纯形法中
1、每一步运算只能用矩阵初等行变换; 2、表中第3列(b列)的数总应保持非负 (≥0); 3、当所有检验数均非正(≤0)时,得到 最优单纯形表。若直接对目标求最h,要求所有 检验数均非负; 4、当最优单纯形表存在非基变量对应的检 验数为零时,可能存在无穷多解;

104

3.单 纯 形 法
5、关于退化和循环。如果在一个基 本可行解的基变量中至少有一个分量 xBi=0 (i=1,2,…,m),则称此基本可行解 是退化的基本可行解。一般情况下,退 化的基本可行解(极点)是由若干个不 同的基本可行解(极点)在特殊情况下 合并成一个基本可行解(极点)而形成 的。退化的结构对单纯形迭代会造成不 利的影响。

105

3.单 纯 形 法
可能出现以下情况:① 进行进基、出 基变换后,虽然改变了基,但没有改变基 本可行解(极点),目标函数当然也不会 改进。进行若干次基变换后,才脱离退化 基本可行解(极点),进入其他基本可行 解(极点)。这种情况会增加迭代次数, 使单纯形法收敛的速度减慢。② 在特殊情 况下,退化会出现基的循环,一旦出现这 样的情况,单纯形迭代将永远停留在同一 极点上,因而无法求得最优解。
106

3.单 纯 形 法
在单纯形法求解线性规划问题时,一 旦出现这种因退化而导致的基的循环,单 纯形法就无法求得最优解,这是一般单纯 形法的一个缺陷。但是实际上,尽管退化 的结构是经常遇到的,而循环现象在实际 问题中出现得较少。尽管如此,人们还是 对如何防止出现循环作了大量研究。1952 年Charnes提出了“摄动法”,1954年 Dantzig,Orden和Wolfe又提出了“字典序 法”,
107

3.单 纯 形 法
这些方法都比较复杂,同时也降低了 迭代的速度。1976年,Bland提出了一个 避免循环的新方法,其原则十分简单。仅 在选择进基变量和出基变量时作了以下规 定:① 在选择进基变量时,在所有 ?j > 0的非基变量中选取下标最小的进基;② 当有多个变量同时可作为出基变量时,选 择下标最小的那个变量出基。这样就可以 避免出现循环,当然,这样可能使收敛速 度降低。
108

4.线性规划应用
一、线性规划--合理利用线材问题:如何下 料使用材最少。 配料问题:在原料供应量的 限制下如何获取最大利润。 投资问题:从投资项目中选 取方案,使投资回报最大。
109

4.线性规划应用
产品生产计划:合理利用人 力、物力、财力等,使获利最 大。 劳动力安排:用最少的劳动 力来满足工作的需要。 运输问题:如何制定调运方 案,使总运费最小。
110

4.线性规划应用
数学规划的建模有许多共同点, 要遵循下列原则: (1)容易理解。建立的模型不但 要求建模者理解,还应当让有关人员 理解。这样便于考察实际问题与模型 的关系,使得到的结论能够更好地应 用于解决实际问题。 (2)容易查找模型中的错误。这 个原则的目的显然与(1)相关。常出 现的错误有:书写错误和公式错误。

111

4.线性规划应用
(3)容易求解。对线性规划来说, 容易求解问题主要是控制问题的规 模,包括决策变量的个数和约束条 件的个数。这条原则的实现往往会 与(1)发生矛盾,在实现时需要对两 条原则进行统筹考虑。

112

4.线性规划应用
建立线性规划模型的过程可以分 为四个步骤: (1)设立决策变量; (2)明确约束条件并用决策变量的 线性等式或不等式表示; (3)用决策变量的线性函数表示目 标,并确定是求极大(Max)还是极 小(Min); (4)根据决策变量的物理性质研究 变量是否有非负性。

113

人力资源分配的问题
时间段内所需司机和乘务人员数如下:
班次 1 2 3 4 5 6 时间 6:00 —— 10:00 10:00 —— 14:00 14:00 —— 18:00 18:00 —— 22:00 22: —— 2:00 2:00 —— 6:00 所需人数 60 70 60 50 20 30

例2.12:某昼夜服务的公交线路每天各

设司机和乘务人员分别在各时间段一开始时 上班,并连续工作8h,问该公交线路怎样安 排司机和乘务人员,既能满足工作需要,又 114 配备最少司机和乘务人员?

人力资源分配的问题
解:设 xi 表示第i班次时开始上班的司机和乘 务人员数,这样我们建立如下的数学模型。 目标函数:Min x1 + x2 + x3 + x4 + x5 + x6 约束条件:s.t. x1 + x6 ≥ 60 x1 + x2 ≥ 70 x2 + x3 ≥ 60 x3 + x4 ≥ 50 x4 + x5 ≥ 20 x5 + x6 ≥ 30 x1,x2,x3,x4,x5,x6 ≥ 0
115

套裁下料问题
方案 1 2 0 1 7.3 0.1 方案 2 1 2 0 7.1 0.3 方案 3 1 1 1 6.5 0.9 方案 4 1 0 3 7.4 0 方案 5 0 3 0 6.3 1.1 方案 6 0 2 2 7.2 0.2 方案 7 0 1 3 6.6 0.8 方案 8 0 0 4 6.0 1.4

例2.13:某工厂要做100套钢架,每套用长为2.9 m, 2.1m, 1.5m的圆钢各一根。已知原料每根长7.4 m, 问:应如何下料,可使所用原料最省? 解:考虑下列各种下料方案(按一种逻辑顺序给出)
2.9 m 2.1 m 1.5 m 合计 剩余料头

把各种下料方案按剩余料头从小到大顺序列出
2.9 m 2.1 m 1.5 m 合计 剩余料头 方案 1 1 0 3 7.4 0 方案 2 2 0 1 7.3 0.1 方案 3 0 2 2 7.2 0.2 方案 4 1 2 0 7.1 0.3 方案 5 0 1 3 6.6 0.8 方案 6 1 1 1 6.5 0.9 方案 7 0 3 0 6.3 1.1 方案 8 0 0 4 6.0 1.4
116

套裁下料问题
2.9 m 2.1 m 1.5 m 合计 剩余料头 方案 1 1 0 3 7.4 0 方案 2 2 0 1 7.3 0.1 方案 3 0 2 2 7.2 0.2 方案 4 1 2 0 7.1 0.3 方案 5 0 1 3 6.6 0.8

假设 x1,x2,x3,x4,x5 分别为上面前 5 种方案下料的 原材料根数。我们建立如下的数学模型。 目标函数: Min x1 + x2 + x3 + x4 + x5 约束条件: s.t. x1 + 2x2 + x4 ≥ 100 2x3 + 2x4 + x5 ≥ 100 3x1 + x2 + 2x3+ 3x5 ≥ 100 x1,x2,x3,x4,x5 ≥ 0

117

生产计划的问题
例2.14:明兴公司生产甲、乙、
丙三种产品,都需要经过铸造、机加 工和装配 三个车间。甲、乙两种 产品的铸件可以外包协作,亦可以自 行生产,但产品丙必须本厂铸造才能 保证质量。数据如下表。问:公司为 了获得最大利润,甲、乙、丙三种产 品各生产多少件?甲、乙两种产品的 铸造中,由本公司铸造和由外包协作 各应多少件?
118

生产计划的问题
铸造工时(小时/件) 机加工工时(小时/件) 装配工时(小时/件) 自产铸件成本(元/件) 外协铸件成本(元/件) 机加工成本(元/件) 装配成本(元/件) 产品售价(元/件) 甲 5 6 3 3 5 2 3 23 乙 10 4 2 5 6 1 2 18 丙 7 8 2 4 -3 2 16 资源限制 8000 12000 10000

解:设 x1 ,x2 ,x3 分别为三道工序都由本公司 加工的甲、乙、丙三种产品的件数,x4, x5 分别
为由外协铸造再由本公司机加工和装配的甲、乙 119 两种产品的件数。

生产计划的问题
求 xi 的利润:利润 = 售价 - 各成 本之和可得到 xi(i=1,2,3,4,5)的利润 分别为15、10、7、13、9元。 这样我们建立如下数学模型: 目标函数: Max 15x1+10x2+7x3+13x4+9x5 约束条件: s.t. 5x1+10x2+7x3 ≤ 8000 6x1+4x2+8x3+6x4+4x5 ≤12000 3x1+2x2+2x3+3x4+2x5 ≤ 10000 x1,x2,x3,x4,x5 ≥ 0
120

生产计划的问题
例2.15:永久机械厂生产Ⅰ、Ⅱ、Ⅲ三 种产品,均要经过 A、B 两道工序加工。假 设有两种规格的设备A1、A2能完成 A 工序; 有三种规格的设备B1、 B2 、B3能完成 B 工 序。Ⅰ可在 A、B的任何规格的设备上加工; Ⅱ 可在任意规格的A设备上加工,但对B工 序,只能在B1设备上加工;Ⅲ 只能在A2与B2 设备上加工;数据如下表。问:为使该厂获 得最大利润,应如何制定产品加工方案?
121

生产计划的问题
设备 A1 A2 B1 B2 B3 原料(元/件) 售价(元/件) 产品单件工时 Ⅰ Ⅱ Ⅲ 5 10 7 9 12 6 8 4 11 7 0.25 0.35 0.50 1.25 2.00 2.80 设备的 有效台时 6000 10000 4000 7000 4000 满负荷时的 设备费用 300 321 50 783 200

解:设 xijk 表示第 i 种产品,在第 j 种工序上的第 k 种设备上加工的数量.
利润 = [(销售单价 - 原料单价)× 产品件 数]之和 - (每台时的设备费用×设备实际使 用的总台时数)之和。
122

生产计划的问题
这样我们建立如下的数学模型: Max

0.75x111+0.7753x112+1.15x211+1.3611x212+1.91 48x312-0.375x121-0.5x221-0.4475x1221.2304x322-0.35x123
设备 设备 设备 设备 设备

s.t

5x111+10x211≤6000 ( 7x112+9x212+12x312≤10000( 6x121+ 8x221≤ 4000 ( 4x122+11x322≤700 ( 7x123 ≤ 4000 (

A1 A2 B1 B2 B3

) ) ) ) )

123

生产计划的问题
x111+ x112- x121- x122- x123 = 0 (Ⅰ产品在A、B工序加工的数量相等) x211+ x212- x221 = 0 (Ⅱ产品在A、B工序加工的数量相等) x312 - x322 = 0 (Ⅲ产品在A、B工序加工的数量相等) xijk≥0, i=1,2,3; j=1,2; k=1,2,3
124

例2.14:某工厂要用三种原料1、2、3混 合调配出三种不同规格的产品甲、乙、丙, 数据如下表。问:该厂应如何安排生产,使 利润收入为最大?
产品名称 规格要求 单价(元/kg) 50 甲 原材料 1 不少于 50%,原材料 2 不超过 25% 35 乙 原材料 1 不少于 25%,原材料 2 不超过 50% 25 丙 不限 原材料名称 1 2 3 每天最多供应量 100 100 60 单价(元/kg) 65 25 35 125

配料问题

配料问题
解:设 xij 表示第 i 种(甲、乙、丙) 产品中原料 j 的含量。这样我们建立数学 模型时,要考虑:

对于甲: x11,x12,x13; 对于乙: x21,x22,x23; 对于丙: x31,x32,x33; 对于原料1: x11,x21,x31; 对于原料2: x12,x22,x32; 对于原料3: x13,x23,x33;

126

配料问题
目标函数:
利润最大,利润 = 收入 - 原料支出 约束条件:规格要求 4 个; 供应量限制 3 个。 Max
z = -15x11+25x12+15x13-30x21+10x22-40x31-10x33

127

s.t.

0.5 x11-0.5 x12 -0.5 x13 ≥ 0 (原材料1不少于50%) -0.25x11+0.75x12 -0.25x13 ≤ 0 (原材料2不超过25%) 0.75x21-0.25x22 -0.25x23 ≥ 0 (原材料1不少于25%) -0.5 x21+0.5 x22 -0.5 x23 ≤ 0 (原材料2不超过50%) x11+x21+x31≤ 100 (供应量限制) x12+x22+x32≤ 100 (供应量限制) x13+x23+x33≤ 60 (供应量限制) xij≥0 ,i = 1,2,3; j = 1,2,3
128

配料问题

投资问题

例2.17:某部门现有资金200万元,今 后五年内考虑给以下的项目投资。已知:项 目A :从第一年到第五年每年年初都可投资, 当年末能收回本利110%;项目B:从第一年到 第四年每年年初都可投资,次年末能收回本 利125%,但规定每年最大投资额不能超过30 万元;项目C:需在第三年年初投资,第五年 末能收回本利140%,但规定最大投资额不能 超过80万元;项目D:需在第二年年初投资, 第五年末能收回本利155%,但规定最大投资 额不能超过100万元。
129

投资问题
据测定每万元每次投资的风 险指数如下表:
项目 A B C D 风险指数(次/万元) 1 3 4 5.5
130

投资问题
问:
a)应如何确定这些项目的每年投 资额,使得第五年年末拥有资金的本 利金额为最大? b)应如何确定这些项目的每年投 资额,使得第五年年末拥有资金的本 利在330万元的基础上使得其投资总的 风险系数为最小?
131

投资问题
解:1)确定决策变量:连续投资问题 设 xij ( i = 1—5,j = 1、2、3、4)表示 第 i 年初投资于A(j=1)、B(j=2)、C(j=3)、 D(j=4)项目的金额。这样我们建立如下决 策变量:

A B C D

x11 x21 x31 x12 x22 x32 x33 x24

x41 x42

x51

132

第一年:A当年末可收回投资,故第一年年初 应把全部资金投出去,于是: x11+ x12 = 200 第二年:B次年末才可收回投资故第二年年初 的资金为1.1x11,于是: x21 + x22+ x24 = 1.1x11 第三年:年初的资金为1.1x21+1.25x12,于是 : x31 + x32+ x33 = 1.1x21+ 1.25x12 第四年:年初的资金为1.1x31+1.25x22,于是: x41 + x42 = 1.1x31+ 1.25x22 第五年:年初的资金为1.1x41+1.25x32,于是: x51 = 1.1x41+ 1.25x32 B、C、D的投资限制: xi2 ≤ 30 ( i=1,2,3, 4 ),x33 ≤ 80,x24 ≤ 100
133

投资问题 2)约束条件:

投资问题
3)目标函数及模型: a) Max z=1.1x51+1.25x42+1.4x33+1.55x24 s.t.x11+ x12 = 200 x21 + x22+ x24 = 1.1x11 x31 + x32+ x33 = 1.1x21+ 1.25x12 x41 + x42 = 1.1x31+ 1.25x22 x51 = 1.1x41+ 1.25x32 xi2 ≤ 30 ( i =1、2、3、4 ), x33 ≤ 80,x24 ≤ 100 xij≥0(i=1,2,3,4,5;j=1,2,3,4)

134

b) Min

投资问题

f = (x11+x21+x31+x41+x51)+ 3(x12+x22+x32+x42)+4x33+5.5x24 s.t. x11+ x12 ≤ 200 x21 + x22+ x24 ≤ 1.1x11 x31 + x32+ x33 ≤ 1.1x21+ 1.25x12 x41 + x42 ≤ 1.1x31+ 1.25x22 x51 ≤ 1.1x41+ 1.25x32 xi2 ≤ 30 ( i =1、2、3、4 ), x33 ≤ 80,x24 ≤ 100 1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 ≥ 330 xij≥0(i=1,2,3,4,5;j = 1,2,3,4)
135


推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 大学生考试网 9299.net
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@qq.com