1 主讲：寇继虹 2 线性规划及应用简介 线性规划是运筹学的一个最基本的分支， 它已成为帮助各级管理人员进行决策的 · 一 种十分重要的工具．是一种目前最常用而又 最为成功的定性分析和定量分析相结合的管 理优化技术。 其原因有三： 一、应用广泛．管理工作中的大量优化 问题可以用线性规划的模型来表达.

Presentation on theme: "1 主讲：寇继虹 2 线性规划及应用简介 线性规划是运筹学的一个最基本的分支， 它已成为帮助各级管理人员进行决策的 · 一 种十分重要的工具．是一种目前最常用而又 最为成功的定性分析和定量分析相结合的管 理优化技术。 其原因有三： 一、应用广泛．管理工作中的大量优化 问题可以用线性规划的模型来表达."— Presentation transcript:

1

2 1 主讲：寇继虹

3 2 线性规划及应用简介 线性规划是运筹学的一个最基本的分支， 它已成为帮助各级管理人员进行决策的 · 一 种十分重要的工具．是一种目前最常用而又 最为成功的定性分析和定量分析相结合的管 理优化技术。 其原因有三： 一、应用广泛．管理工作中的大量优化 问题可以用线性规划的模型来表达

4 3 三、求解方法采用成熟的单纯形法．目 前，用单纯形法解线性规划的计算机程 序已大量涌现，在计算机上求解此类问 题已十分容易 二、模型较为简单，容易建立，容易 学习和掌握．

5 4 线性规划的一种最大量、最普遍的应用就 是研究有限资源的合理利用问题，或说资源 的最优配置问题．资源分配问题有多种多样 的具体形式．例： 线性规划解决的问题： 1 、生产的合理安排问题 2 、投资决策问题 3 、运输问题

6 5 1.1 什么是线性规划 （ Linear Programming) 1.1.1 Lp 的简单例子和模型 （ 1 ） 数学模型 一个实际问题的数学模型，是依据客 观规律，对该问题中我们所关心的那些 量进行科学的分析后得出的反映这些量 之间本质联系的数学关系式。

7 6 单 位 单位 时耗 资源 一 二现有工 时 搅拌机 / 小时 3515 成形机 / 小时 215 烘箱 / 小时 2211 利润（百元 / 吨） 54 例 1.2-1 饼干生产问题

8 7 问题 ：如何制订生产计划， 才能使资源利用充分并使厂方获 最大利润。

9 8 解：设由 x 1 ， x 2 分别表示 1 ， 2 型饼干每 天的生产量。 max z=5x 1 +4x 2 s.t. 3x 1 +5x 2 ≤15, 2x 1 +x 2 ≤5, 2x 1 +2x 2 ≤11, x 1,x 2 ≥0. max —— maximize, s.t. —— subject to

10 9 单台 运费 B 1 (100) B 2 (80) B 3 (90,120) A 1 (200)152118 A 2 (150)162516 问题：如何调运才能即满足用户需要， 又使总运费最少？ 例 1.2-2 运输问题

11 10

12 11 1.1.2 线性规划数学模型的一般表示方式

13 12 1.1.3 线性规划数学模型的标准型

14 13 1 、标准型的几种不同的表示方式 1 ）和式

15 14 2 ）向量式

16 15 3 ）矩阵

17 16 1 ） A 的秩 r(A)=m, 且 m<n. （ m 个方 程彼此独立，没有多余方程，且方 程个数小于未知量个数） 若 r(A) < m ，则应先去掉多余方程。 2 ） b  0 2 、对标准型问题作出的假设 极大无关组包含向量的个数

18 17 最优解 – 使 z 达到最优的可行解就是最优解 – （有解（给定的 Lp 问题有最优解）、 否则无解）  可行解 满足约束条件和非负条件的解 X 称 为可行解，所有可行解组成的集合称之为可 行解集（可行域） 3 、 LP 问题解的几个基本概念

19 18 2. 第 i 个约束的 b i 为负值，则在 b i 所 在之方程的两边乘以 -1 。 4 、一般型变标准型的变换方法： 1. 目标函数为 min 型时，价值系数 一律反号。即令 z(x) = -z (x) = - CX

20 19 3. 第 i 个约束为  型，在不等式 左边增加一个非负的变量 x n+i ， 称为松弛变量（原有变量为构造 变量）；同时令 c n+i = 0 4. 第 i 个约束为  型，在不等式左 边减去一个非负的变量 x n+i ，称为 剩余变量；同时令 c n+i = 0

21 20 6. 若 x j 无符号限制，令 x j = x j - x j  ， x j  0 ， x j   0 ，代入非标准型 5. 若 x j  0 ，令 x j = -x j ，代入非标准 型，则有 x j  0

22 21 原非标准型： max z=5x 1 +4x 2 s.t. 3x 1 +5x 2 ≤15, 2x 1 +x 2 ≤5, 2x 1 +2x 2 ≤11, x 1,x 2 ≥0. 5 、 变换举例 例 1.

23 22 标准型： max z=5x 1 +4x 2 s.t. 3x 1 +5x 2 +x 3 = 15, 2x 1 +x 2 + x 4 = 5, 2x 1 +2x 2 +x 5 = 11, x 1 ， x 2 ， x 3 ， x 4 ， x 5 ≥0.

24 23 例2例2

25 24 标准型： max f(x)=-3x 1 +2x 2 -4x 3 ´+4x 3 ´´ +0x 4 +0x 5 +0x 6 s.t. 2x 1 +3x 2 + 4x 3 ´-4x 3 ´´- x 4 = 300, x 1 +5x 2 + 6x 3 ´-6x 3 ´´ + x 5 = 400, x 1 +x 2 + x 3 ´-x 3 ´´ +x 6 = 200, x 1,x 2, x 3 ´,x 3 ´´, x 4, x 5, x 6 ≥0.

26 25 1.2 求解 LP 问题的基本定理 1.2.1 LP 的图解法 对于只有两个决策变量的线性规划问题， 可以在平面直角坐标系上作图表示线性规 划问题的有关概念，并求解。 如：

27 26 例 1.3 Maxz = 50 x 1 + 100 x 2 s.t. x 1 + x 2 ≤ 300 2 x 1 + x 2 ≤ 400 x 2 ≤ 250 x 1 、 x 2 ≥0

28 27 采用图 解 法 (1) 分别取决策变量 X 1, X 2 为坐标向量建立直 角坐标系。在直角坐标系里，图上任意一点 的坐标代表了决策变量的一组值，例 1.3 的 每个约束条件都代表一个半平面。 x2x2 x1x1 X2≥0X2≥0 X 2 =0 x2x2 x1x1 X1≥0X1≥0 X 1 =0

29 28 （ 2 ）对每个不等式 ( 约束条件 ) ，先取其等 式在坐标系中作直线，然后确定不等式 所决定的半平面。 100 200 300 100 200300 x 1 +x 2 ≤300 x 1 +x 2 =300 100 200 2x 1 +x 2 ≤400 2x 1 +x 2 =400 300 200 300 400

30 29 （ 3 ）把五个图合并成一个图，取各约束条件 的公共部分，如 P 7 图 1-2 所示。 100 x 2 ≤250 x 2 =250 200300 200 300 x1x1 x2x2 x 2 =0 x 1 =0 x 2 =250 x 1 +x 2 =300 2x 1 +x 2 =400 图 1-2

31 30 （ 4 ）目标函数 z=50x 1 +100x 2 ，当 z 取某一固定值时得 到一条直线，直线上的每一点都具有相同的目标函 数值，称之为 “ 等值线 ” 。平行移动等值线，当移动到 B 点时， z 在可行域内实现了最大化。 A ， B ， C ， D ， E 是可行域的顶点，对有限个约束条件则其可行域的 顶点也是有限的。 x1x1 x2x2 z=20000=50x 1 +100x 2 图 1-3 z=27500=50x 1 +100x 2 z=0=50x 1 +100x 2 z=10000=50x 1 +100x 2 C B A D E x 1 +x 2 =300

32 31 得到最优解： x 1 = 50 ， x 2 =250 最优目标值 z=27500

33 32 若在上例模型中中引入松弛变量 s 1 s 2 s 3 模型化为： Max z = 50x 1 +100x 2 +0s 1 +0s 2 +0s 3 s.t. x 1 +x 2 +s 1 = 300 2x 1 +x 2 +s 2 = 400 x 2 +s 3 = 250 x 1,x 2,s 1,s 2,s 3 ≥0 可求解得其最优解为： x 1 =50 x 2 = 250 s 1 = 0 s 2 =50 s 3 = 0 说明：生产 50 单位Ⅰ产品和 250 单位Ⅱ产品将消耗完所 有资源 1 和 3 ，但资源 2 还剩余 50 。

34 33 max z=5x 1 +4x 2 1.1 s.t. 3x 1 +5x 2 ≤15, 1.2 2x 1 +x 2 ≤5, 1.3 2x 1 +2x 2 ≤11, 1.4 x 1,x 2 ≥0. 1.5 无需化标准形 例 1.2-1 求解饼干生产问题

35 34 图中的 OABC 即为满足约束条件的可行解集 S, 需在 S 中 找出最优解, 若 z 为一常数 z 0 则 z 0 =5x 1 +4x 2 为目标函数 等值线（ x 1 =10/7,x 2 =15/7,z * =110/7) 。

36 练习题 max z=x 1 +2x 2 s.t. x 1 +x 2 ≤3, -x 1 +x 2 ≥ 5, x 1,x 2 ≥0. 35

37 36 例 1.2-2 假设上例中的目标函数变为 z=3x 1 +5x 2 此时最优目标函数等值线与 AB 边重合， AB 上每一点均为最优解（无穷个） 例 1.2-3 可行解集为一无界集合 见 P 18 图 1.3 若是求目标函数最小值， 则有最优解。若是求目标函数最大值， 则无最优解。 若可行解集为空集，则无解， P 19 图 1.4

38 37 求解 LP 问题的重要规律： 一、解的存在性问题 二、解的结构问题 三、关于最优解的获得方法问题 （在可行解集的某些 “ 顶点 ” 得到）

39 38 关于 LP 问题求解的一些基本概念 和特点： 1 、两个基本概念 凸集 : 实向量空间 E 中任意两点连线 上的一切点仍属于 E( 见 P 20 ) 极点就是不能成为 E 中任何线段的内 点的那种点

40 39 2 、 Lp 问题的几个特点 ( 相关证明请看 1.7 节 ) ：  最优解只可能在凸集的极点上，而不可能 发生在凸集的内部  线性规划问题的可行解集 S 是凸集  设 X 属于 S, 若 x=0, 则一定为极点；若 x  0 ，则为极点的充要条件是： x 的正分 量所对应的系数列向量线性无关。  只要存在可行解，就一定存在极点  极点的个数是有限的

41 40 2 、 “ 基 ” 的概念 在标准型中，技术系数矩阵有 n+m 列，即 A = ( P 1, P 2, …, P n, P n+1,, P n+2,..P n+m ) 因 r(A)=m, 所以 A 的极大无关组含有 m 个 线性无关的向量。 关于标准型解的若干基本概念： 1 、标准型有 n+m 个变量， m 个约束行

42 41 基、基变量、非基变量 —— 技术系数矩阵 A （标准线性规 划模型）中 m 个线性无关的列向量所对应的 m 个变量，构 成该 LP 问题的一个基，这 m 个变量的系数列向量组成的矩 阵称为基阵，记为 B 。基中的每个变量称为基变量, 记为 X B 。 其余的变量即为非基变量, 记为 X N 。 如： Max z = 50 x 1 + 100 x 2 s.t. x 1 +x 2 + s 1 = 300 2x 1 +x 2 + s 2 = 400 x 2 + s 3 = 250 x 1,x 2,s 1,s 2,s 3 ≥0 基解 : 令非基变量 X N = 0 ，求得基变量 X B 的值称为基解. 基可行解：若基解中所有的 X B 都 ≥0 时，称为基可行 解.

43 42 若基可行解的所有基变量均取正值， 则称为非退化的基可行解，如果某些 基变量取零值，则为退化的基可行解。

44 43 可行解、基解和基可行解举例

45 44 可行解、基础解和基础可行解举例

46 45 X 是极点的充分必要条件是：它是基 可行解。由此，有关极点的结果可转 到基可行解上： 只要存在可行解，就一定存在基可行 解；基可行解的个数是有限的；若 LP 问 题有最优解，则最优解一定可以在基可 行解中找到。

47 46 1.3 单纯型法的基本思路 确定初始基可行解 是否为最优 确定改善方向 求新的基可行解 求最优解的目标函数值 是 否

48 47 (1) 单纯形表的组成及形式  设 B 是初始可行基向量，则目 标函数可写为两部分 (1)  约束条件也写为两部分，经整 理得 X B 的表达式 (2) ，注意 X B 中 含有非基变量作参数  把 X B 代入目标函数，整理得到 (3) 式  若所有非基变量的检验数 σ i  0, 则达到最优

49 48 单纯形表

50 49 例 1.1 试列出下面线性规划问题的 初始单纯形表

51 50 1 找初 始基础可行基 – 对于 (max,  ) ，松弛变量对应的列构成一个单 位阵 – 若有 b i <0 ，则单位阵也不能构成一个可行基 2 检验当前基础可行解是否为最优解 – 所有检验数 σ j  0 ，则为最优解，否则 1.3.2 标准型的单纯型法基本步骤

52 51 4 确定出基变量 最小比例原则 3 确定入基变量 从 σ j > 0 中找最大者，选中者称为 入基变量 x j* 第 j* 列称为主列

53 52 设第 i* 行使  最小，则第 i* 行对应的基 变量称为出基变量，第 i* 行称为主行 5 迭代过程 主行 i* 行与主列 j* 相交的元素 a i*j* 称为 主元，迭代以主元为中心进行 迭代的实质是线性变换，即要将主元 a i*j* 变为 1 ，主列上其它元素变为 0 ，变换 步骤如下： (1) 变换主行

54 53 (2) 变换主列 除主元保留为 1 ，其余都置 0 (3) 变换非主行、主列元素 a ij ( 包括 b i ) (4) 变换 C B ， X B (5) 计算目标函数、机会成本 z j 和检验数 c j  z j 6 、返回步骤 2

55 54 例 1.1 单纯形表的迭代过程 答：最优解为 x 1 =20, x 2 =20, x 3 =0, OBJ=1700

56 55 1.3.3 基可行解的判别和改进 定理 1.6 若所有检验数 σ j  0 ，则为最优解 定理 1.7 若存在某一个检验数 >0 ，而它所对应 的列向量的全部分量  0 ，则所给问题无 最优解 除上述两种情况外，若每个正检验数所 对应的列向量中都有正分量，则为确定最 优解需要进行基的变换（换基）

57 56 请查看教材 P 29 中单纯形表的组成形式。

58 57 当约束条件为 “  ” 型，引入剩余 变量和人工变量 1.4 人工变量的引入及其解法

59 58 由于所添加的剩余变量的技术系 数为  1 ，不能作为初始可行基变量， 为此引入一个人为的变量（注意， 此时约束条件已为 “ = ” 型），以便取 得初始基变量，故称为人工变量. 两种方法：大 M 法 两阶段法

60 59 由于人工变量在原问题的解中是不能 存在的，应尽快被迭代出去, 使其取值 为 0 ，因此人工变量在目标函数中对应 的价值系数应具有惩罚性，称为罚系 数。罚系数的取值视解法而定. 两种方法 大 M 法和二阶段法

61 60 1.4.1 大 M 法的求解过程 罚系数的取值为一充分大的正数，在 最大化问题中（ - ），在最小化问题中 （ + ）

62 61 例 1.4.1

63 62 化标准型：

64 63 答：最优解为 x 1 =2, x 2 =2, x 3 =0, OBJ=36 例 1.4.1 的单纯形表迭代过程

65 64 多个基础可行解都是最优解，这 些解在同一个平面上，且该平面 与目标函数等值面平行 最优单纯形表中有非基变量的检 验数为 0 1.5 单纯形法应用的特例 1.5.1 关于多重解问题

66 65

67 66 例 1.5.1 的单纯形表及其迭代过程

68 67 在单纯形法计算过程中，确定 出基变量时有时存在两个以上的相 同的最小比值，即同时有多个基变 量可选作出基变量，这样在下一次 迭代中就有了一个或几个基变量等 于零，这称之为退化。 1.5.2 关于退化问题

69 68 例 1.5.2 用单纯形表求解下列线性规划问题

70 69 迭代次数迭代次数 基变量基变量 CBCB b x 1 x 2 x 3 s 1 s 2 s 3 比值 2 0 3/2 0 0 0 0 s1s2s3s1s2s3 000000 243243 1 -1 0 1 0 0 2 0 1 0 1 0 1 1 1 0 0 1 2/1 4/2 3/1 02 0 3/2 0 0 0 1 x1s2s3x1s2s3 200200 201201 1 -1 0 1 0 0 0 2 1 -2 1 0 0 2 1 -1 0 1 — 0/2 1/2 40 2 3/2 -2 0 0 ……

71 70 约束条件互相矛盾，无可行域 1.5.3 关于无可行解问题

72 71

73 72 可行区域不闭合 单纯形表中入基变量 x j* ( 其对 应检验数大于 0) 对应的列中所有 1.5.4 关于无界解问题

74 73

75 74 X1X1 X2X2 1.5.4 图解示意

76 75  例 1.5.4 的单纯形表及其迭代过程

77 76 （ 1 ） 掌握线性规划数学模型的基本特征和标准 形式，以及线性规划问题数学模型的建立方法， 学会用图解法求解简单的线性规划问题。 本章小结： （ 3 ） 理解求解线性规划问题的单纯形法 （ 2 ） 理解线性规划问题的解的概念