线性规划ppt课件

1、数学建模,1,第二讲 线性规划,2,2.1 引言 线性规划是运筹学的重要分枝，也是运筹学最基本的部分。 20 世纪 30 年代末，前苏联学者康托洛维奇首先研究了线性规划问题。1939 年，他撰写的生产组织与计划中的数学方法一书，是线性规划应用于工业生产问题的经典著作。 然而这项工作长期不为人们所知。,3,第二次世界大战期间，由于战争的需要，柯勃门(T. C. Koopmans)重行、独立地研究了运输问题。 后来丹西格(G. B. Dantzig)于 1947 年发现了单纯形方法，并将其应用于与国防有关的诸如人员的轮训、任务的分派等问题。 此后，线性规划的理论和方法日渐趋于成熟。,4,线性规划所

2、研究的对象属于最优化的范畴，本质上是一个极值问题。和其它最优化问题一样，在建立线性规划问题的数学模型时，应首先明确三个基本要素： 决策变量(decision variables)：它们是决策者(你)所控制的那些数量，它们取什么数值需要决策者来决策，问题的求解就是找出决策变量的最优值。,5,约束条件(constraints)：它们是决策者在现实世界中所受到的限制，或者说决策变量在这些限制范围之内才有意义。 目标函数(objective function)：它代表决策者希望对其进行优化的那个指标。目标函数是决策变量的函数。 线性规划问题的特征是目标函数和约束条件中的函数都是决策变量的线性函数，并且

3、约束是必不可少的(否则不存在有实际意义的解)。,6,2.2 引例：食用油加工计划 加工一种食用油需要精炼若干种原油并把它们混合起来。原油来源有两类共 5 种： 植物油：VEG1，VEG2 非植物油：OIL1，OIL2，OIL3 购买每种原油的价格(镑/吨)见表 2.2.1：,7,表 2.2.1：,最终产品以 150 镑/吨价格出售。 植物油和非植物油需要在不同的生产线上进行精炼。每月能够精炼的植物油不超过 200吨，非植物油不超过 250 吨；在精炼过程中，重量没有损失，精炼费用可忽略不计。,8,最终产品要符合硬度的技术条件。按照硬度计量单位，它必须在 36 之间。假定硬度的混合是线性的，而原

4、油的硬度见表 2.2.2： 表 2.2.2 问：为使利润最大，应该怎样制定它的月采购和加工计划？,9,要建立表述这个问题的数学模型，首先需要确定它的三个要素。 1确定决策变量 设 x1, , x5 分别代表需要采购的 5 种原油的吨数，y 代表需要加工的成品油的吨数。,10,2确定约束条件 生产能力限定： x1 + x2 200(植物油 200 吨) x3 + x4 + x5 250 (非植物油 250 吨) 技术指标(硬度)限定： 8.8x1 + 6.1x2 + 2x3 + 4.2x4 + 5x5 6y 8.8x1 + 6.1x2 + 2x3 + 4.2x4 + 5x5 3y 连续性(均衡性

5、)：x1 + x2 + x3 + x4 + x5 = y 非负性：xi 0(i =1, , 5)，y 0,11,3确定目标函数 目标是使利润最大，即出售产品的收入扣除原油成本之后所得最大： 150y 110 x1 120 x2 130 x3 110 x4 115x5 最大,12,显然这是一个线性规划问题，可以用下面的数学模型来表述这个问题：,13,2.3 线性规划模型 2.3.1 线性规划模型的一般形式 线性规划问题有各种不同形式，其目标函数可以是实现最大化，也可以是实现最小化；约束条件可以是“”，也可以是“”，还可以是“=”的形式；决策变量可以非负，也可以是无符号限制。,14,归纳起来，线性

6、规划问题的数学模型的一般形式为：,15,或者：,这里“s.t.”是“subject to”的 缩写，即“满足于”的意思。,16,如果我们设,线性规划一般形式也可用矩阵形式描述为：,17,2.3.2 线性规划模型的标准形式 为理论研究之便，人们规定线性规划模型的标准形式为：,18,若给定问题的目标函数是求 min Z = CTX，则可化为求 max Z = CTX；,若给定问题的约束条件中含有不等式： ai1x1 ai2x2 ainxn (或 )bi， 则可等价地化为： ai1x1 ai2x2 ainxn xn+1 = bi，xn+1 0 或 ai1x1 ai2x2 ainxn xn+1 = b

7、i，xn+1 0 我们称新增加的变量 xn+1 为松弛变量。,19,2.3.3 线性规划问题解的概念 对于线性规划问题，我们定义： 可行解：满足全部约束条件的决策向量。 可行域：全部可行解构成的集合(它是 n 维欧氏空间 Rn 中的点集，而且是一个“凸多面体”)。 最优解：使目标函数达到最优值(最大值或最小值，并且有界)的可行解。 无界解：若求极大化则目标函数在可行域中无上界；若求极小化则目标函数在可行域中无下界。,20,线性规划问题的最优解有下列几种情况： (1) 有最优解时，可能有唯一最优解，也可能有无穷多个最优解。如果最优解不唯一，最优解一定有无穷多个，不可能为有限个。最优解的目标函数值

8、均相等。 (2) 没有最优解时，也有两种情形。一是可行域为空集，二是目标函数值无界(求最大时无上界，求最小时无下界)。,21,定理：当线性规划问题有最优解时，一定可以在可行域的某个顶点上取到。当有唯一解时，最优解就是可行域的某个顶点。当有无穷多个最优解时，其中至少一个是可行域的一个顶点。,22,2.3.4 几何解释 在这部分，我们给出一种求解两个变量的线性规划问题的几何方法，目的是阐明线性规划问题的基本原理及其直观的几何意义。,23,例 2.3.1 求解线性规划问题 max Z = x1 x2 s.t. 2x1 3x2 6 3x1 2x2 6 xi 0(i = 1, 2) 我们把 x1, x2

9、 看成坐标平面上的坐标，则满足约束条件的点集，即可行域，如图 2.3.1 阴影部分所示。,24,图 2.3.1,可行域,25,目标函数 x1 + x2 = c 在坐标平面上是一簇平行线，称为目标函数的等值线，在同一等值线上目标值相等。箭头表示目标函数值增大的方向，其方向与目标函数的梯度方向 (1, 1)T 相同。,26,由于是求最大值问题，目标函数的等值线应沿梯度方向移动，到临界状态，即可行域的顶点 (6/5, 6/5) 处，目标函数取得最大值 12/5。继续沿梯度方向上升，目标函数值会更大，但与可行域无交点，即找不到满足所有约束条件的点使得目标值比 12/5 大。,27,图 2.3.1,28

10、,因此，线性规划问题的最优解为临界等值线与可行域的交点：x* = (6/5, 6/5)，最优值为12/5。,29,例 2.3.2 求解线性规划问题 max Z = 2x1 3x2 s.t. 2x1 3x2 6 3x1 2x1 6 xi 0(i = 1, 2),线性规划问题的可行域仍如图 2.3.1 所示；目标函数的等值线为 2x1 3x2 = c；目标函数的梯度方向为 (2, 3)T。,30,图 2.3.1,31,由于是求最大值问题，目标函数的等值线应沿梯度方向推进，临界等值线为 2x1 3x2 = 6 与可行域交于一线段 PQ，其中 P(0, 2)，Q(6/5, 6/5)，最优解为 PQ 上

11、任一点，最优值为 6。,32,图 2.3.1,33,例 2.3.3 求解线性规划问题 min Z = 2x1 x2， s.t. x1 x2 2 x1 4x2 2 xi 0(i = 1, 2),线性规划问题的可行域如图 2.3.2 所示，目标函数的梯度方向为 (2, 1)T。由于是求最小值问题，目标函数的等值线应沿负梯度方向推进，可一直进行下去，得不到临界等值线，此问题目标值无下界，无最优解。,34,35,例 2.3.4 求解线性规划问题 min Z = 2x1 5x2， s.t. x1 x2 2 x1 x2 3 xi 0(i = 1, 2),线性规划问题的可行域如图 2.3.3 所示，是一空集

12、。此问题无最优解。,36,37,2.4 用 Matlab 解线性规划 在 Matlab 软件的优化工具箱中，求解线性规划的函数为：linprog。其调用格式为 x = linprog(c, A, b, Aeq, beq, xLB, xUB),38,适用模型为：,其中 Aeq、beq 表示约束条件中的等式约束部分AeqX = beq 的系数矩阵和常数向量。,使用 Matlab 求解线性规划问题， 必须是这样的“标准形式”。,39,例 2.4.1 在2.2 的引例中，我们对食用油加工计划问题建立了如下的线性规划模型：,40,将上述模型改写成 Matlab 适用的模型，其形式为：,41,建立 M 文

13、件，编写 Matlab 程序： c = 110; 120; 130; 110; 115; -150 A = 1, 1, 0, 0, 0, 0; 0, 0, 1, 1, 1, 0; 8.8, 6.1, 2, 4.2, 5, -6; -8.8, -6.1, -2, -4.2, -5, 3; b = 200; 250; 0; 0; Aeq =1, 1, 1, 1, 1, -1; beq = 0; xLB = zeros(6, 1); xUB = inf*ones(6, 1); x = linprog(c, A, b, Aeq, beq, xLB, xUB); x，Profit=c*x,42,运行上述

14、 Matlab 程序，计算得：,x = 159.2593 40.7407 0.0000 250.0000 0 450.0000 Profit = -1.7593e+004,43,于是月采购与生产计划为：,44,2.5 灵敏度分析与参数线性规划,2.5.1 线性规划问题的灵敏度分析 灵敏度分析是指对系统因周围条件变化显示出来的敏感程度的分析。,45,在前面讨论线性规划问题时，我们都设定aij, bi, cj 是常数。但在许多实际问题中，包括大型线性规划问题，这些系数往往是估计值或预测值，经常有少许的变动。例如在2.2 的引例中，如果市场条件发生变化，cj 值就会随之变化；生产工艺条件发生改变，会

15、引起 bi 变化，aij 也会由于种种原因产生改变。,46,因此提出这样两个问题： 当线性规划模型中的参数有一个或几个发生不大的变化时，已求得的线性规划问题的最优解会有什么变化； 或者这些参数在什么范围内变化时，线性规划问题的最优解不变。 这涉及解的稳定性问题。,47,当然，有一套理论方法可以进行灵敏度分析(参见1,2)，这里就不讨论了。 但在实际应用中，对于不同的参数值重复求解线性规划问题，不失为一种可用的方法，特别是使用计算机求解时。,48,2.5.2 参数线性规划 参数线性规划是研究 aij, bi, cj 这些参数中某一参数连续变化时，使最优解发生变化的各临界点的值。即把某一参数作为参

16、变量，而目标函数在某区间内是这参变量的线性函数，含这参变量的约束条件是线性等式或不等式。 当然，在实际应用中，给定参变量一个步长重复求解线性规划问题，以观察最优解变化情况，也是一种可用的数值方法。,49,2.6 范例 载货问题：有一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如下面表 2.6.1 所示。,50,现有三种货物待运，已知有关数据列于下面表 2.6.2。,51,又为了航运安全，要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系。具体要求前、后舱分别与中舱之间载重量比例上偏差不超过 15%，前、后舱之间不超过 10%。 问该货轮应装载 A、B、C 各多少件，

17、运费收入为最大？,52,解：(1) 确定决策变量 因为 A、B、C 三种商品在货轮的前、中、后舱均可装载，令 i = 1, 2, 3 分别代表商品 A、B、C，用 j = 1, 2, 3 分别代表前、中、后舱。 设决策变量 xij 为装于 j 舱位的第 i 种商品的数量(件)。,53,(2) 确定目标函数 商品 A 的件数为：x11 + x12 + x13，即装于货轮前、中、后舱商品 A 的件数之和； 商品 B 的件数为：x21 + x22 + x23，即装于货轮前、中、后舱商品 B 的件数之和； 商品 C 的件数为：x31 + x32 + x33，即装于货轮前、中、后舱商品 C 的件数之和。

18、 为使运费总收入最大，目标函数为 max Z = 1000(x11 + x12 + x13) + 700(x21 + x22 + x23) + 600(x31 + x32 + x33),54,(3) 确定约束条件 前、中、后舱位载重量限制为： 8x11 + 6x21 + 5x31 2000 8x12 + 6x22 + 5x32 3000 8x13 + 6x23 + 5x33 1500 前、中、后舱位体积限制为： 10 x11 + 5x21 + 7x31 4000 10 x12 + 5x22 + 7x32 5400 10 x13 + 5x23 + 7x33 1500,55, A、B、C 三种商品数量限制为： x11 + x12 + x13 6