《线性规划 课件.ppt》由会员分享，可在线阅读，更多相关《线性规划 课件.ppt（62页珍藏版）》请在三一办公上搜索。
1、线性规划,线性规划,数学建模,线性规划,第二讲线性规划,线性规划,2.1 引言 线性规划是运筹学的重要分枝，也是运筹学最基本的部分。 20 世纪 30 年代末，前苏联学者康托洛维奇首先研究了线性规划问题。1939 年，他撰写的生产组织与计划中的数学方法一书，是线性规划应用于工业生产问题的经典著作。 然而这项工作长期不为人们所知。,线性规划,第二次世界大战期间，由于战争的需要，柯勃门(T. C. Koopmans)重行、独立地研究了运输问题。 后来丹西格(G. B. Dantzig)于 1947 年发现了单纯形方法，并将其应用于与国防有关的诸如人员的轮训、任务的分派等问题。 此后，线性规划的理论
2、和方法日渐趋于成熟。,线性规划,线性规划所研究的对象属于最优化的范畴，本质上是一个极值问题。和其它最优化问题一样，在建立线性规划问题的数学模型时，应首先明确三个基本要素： 决策变量(decision variables)：它们是决策者(你)所控制的那些数量，它们取什么数值需要决策者来决策，问题的求解就是找出决策变量的最优值。,线性规划,约束条件(constraints)：它们是决策者在现实世界中所受到的限制，或者说决策变量在这些限制范围之内才有意义。 目标函数(objective function)：它代表决策者希望对其进行优化的那个指标。目标函数是决策变量的函数。 线性规划问题的特征是目标函
3、数和约束条件中的函数都是决策变量的线性函数，并且约束是必不可少的(否则不存在有实际意义的解)。,线性规划,2.2 引例：食用油加工计划 加工一种食用油需要精炼若干种原油并把它们混合起来。原油来源有两类共 5 种： 植物油：VEG1，VEG2 非植物油：OIL1，OIL2，OIL3购买每种原油的价格(镑/吨)见表 2.2.1：,线性规划,表 2.2.1：,最终产品以 150 镑/吨价格出售。 植物油和非植物油需要在不同的生产线上进行精炼。每月能够精炼的植物油不超过 200吨，非植物油不超过 250 吨；在精炼过程中，重量没有损失，精炼费用可忽略不计。,线性规划,最终产品要符合硬度的技术条件。按照
4、硬度计量单位，它必须在 36 之间。假定硬度的混合是线性的，而原油的硬度见表 2.2.2： 表 2.2.2 问：为使利润最大，应该怎样制定它的月采购和加工计划？,线性规划,要建立表述这个问题的数学模型，首先需要确定它的三个要素。 1确定决策变量 设 x1, , x5 分别代表需要采购的 5 种原油的吨数，y 代表需要加工的成品油的吨数。,线性规划,2确定约束条件生产能力限定： x1 + x2 200(植物油 200 吨) x3 + x4 + x5 250 (非植物油 250 吨)技术指标(硬度)限定： 8.8x1 + 6.1x2 + 2x3 + 4.2x4 + 5x5 6y 8.8x1 + 6
5、.1x2 + 2x3 + 4.2x4 + 5x5 3y连续性(均衡性)：x1 + x2 + x3 + x4 + x5 = y非负性：xi 0(i =1, , 5)，y 0,线性规划,3确定目标函数 目标是使利润最大，即出售产品的收入扣除原油成本之后所得最大：150y 110 x1 120 x2 130 x3 110 x4 115x5 最大,线性规划,显然这是一个线性规划问题，可以用下面的数学模型来表述这个问题：,线性规划,2.3 线性规划模型2.3.1 线性规划模型的一般形式 线性规划问题有各种不同形式，其目标函数可以是实现最大化，也可以是实现最小化；约束条件可以是“”，也可以是“”，还可以是
6、“=”的形式；决策变量可以非负，也可以是无符号限制。,线性规划,归纳起来，线性规划问题的数学模型的一般形式为：,线性规划,或者：,这里“s.t.”是“subject to”的缩写，即“满足于”的意思。,线性规划,如果我们设,线性规划一般形式也可用矩阵形式描述为：,线性规划,2.3.2 线性规划模型的标准形式 为理论研究之便，人们规定线性规划模型的标准形式为：,线性规划,若给定问题的目标函数是求 min Z = CTX，则可化为求 max Z = CTX；,若给定问题的约束条件中含有不等式：ai1x1 ai2x2 ainxn (或 )bi，则可等价地化为：ai1x1 ai2x2 ainxn xn
7、+1 = bi，xn+1 0或ai1x1 ai2x2 ainxn xn+1 = bi，xn+1 0 我们称新增加的变量 xn+1 为松弛变量。,线性规划,2.3.3 线性规划问题解的概念 对于线性规划问题，我们定义： 可行解：满足全部约束条件的决策向量。 可行域：全部可行解构成的集合(它是 n 维欧氏空间 Rn 中的点集，而且是一个“凸多面体”)。 最优解：使目标函数达到最优值(最大值或最小值，并且有界)的可行解。 无界解：若求极大化则目标函数在可行域中无上界；若求极小化则目标函数在可行域中无下界。,线性规划,线性规划问题的最优解有下列几种情况： (1) 有最优解时，可能有唯一最优解，也可能有
8、无穷多个最优解。如果最优解不唯一，最优解一定有无穷多个，不可能为有限个。最优解的目标函数值均相等。 (2) 没有最优解时，也有两种情形。一是可行域为空集，二是目标函数值无界(求最大时无上界，求最小时无下界)。,线性规划,定理：当线性规划问题有最优解时，一定可以在可行域的某个顶点上取到。当有唯一解时，最优解就是可行域的某个顶点。当有无穷多个最优解时，其中至少一个是可行域的一个顶点。,线性规划,2.3.4 几何解释 在这部分，我们给出一种求解两个变量的线性规划问题的几何方法，目的是阐明线性规划问题的基本原理及其直观的几何意义。,线性规划,例 2.3.1 求解线性规划问题 max Z = x1 x2
9、 s.t. 2x1 3x2 6 3x1 2x2 6 xi 0(i = 1, 2) 我们把 x1, x2 看成坐标平面上的坐标，则满足约束条件的点集，即可行域，如图 2.3.1 阴影部分所示。,线性规划,图 2.3.1,可行域,线性规划,目标函数 x1 + x2 = c 在坐标平面上是一簇平行线，称为目标函数的等值线，在同一等值线上目标值相等。箭头表示目标函数值增大的方向，其方向与目标函数的梯度方向 (1, 1)T 相同。,线性规划,由于是求最大值问题，目标函数的等值线应沿梯度方向移动，到临界状态，即可行域的顶点 (6/5, 6/5) 处，目标函数取得最大值 12/5。继续沿梯度方向上升，目标函
10、数值会更大，但与可行域无交点，即找不到满足所有约束条件的点使得目标值比 12/5 大。,线性规划,图 2.3.1,线性规划,因此，线性规划问题的最优解为临界等值线与可行域的交点：x* = (6/5, 6/5)，最优值为12/5。,线性规划,例 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。,线性规划,图 2.3.1,线性规划,由于是求最大值问题，目标函数的等值线应沿梯度方向
11、推进，临界等值线为2x1 3x2 = 6与可行域交于一线段 PQ，其中 P(0, 2)，Q(6/5, 6/5)，最优解为 PQ 上任一点，最优值为 6。,线性规划,图 2.3.1,线性规划,例 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。由于是求最小值问题，目标函数的等值线应沿负梯度方向推进，可一直进行下去，得不到临界等值线，此问题目标值无下界，无最优解。,线性规划,线性规划,例 2.3.4 求解线性规划问题 min Z
12、= 2x1 5x2， s.t. x1 x2 2 x1 x2 3 xi 0(i = 1, 2),线性规划问题的可行域如图 2.3.3 所示，是一空集。此问题无最优解。,线性规划,线性规划,2.4 用 Matlab 解线性规划 在 Matlab 软件的优化工具箱中，求解线性规划的函数为：linprog。其调用格式为x = linprog(c, A, b, Aeq, beq, xLB, xUB),线性规划,适用模型为：,其中 Aeq、beq 表示约束条件中的等式约束部分AeqX = beq 的系数矩阵和常数向量。,使用 Matlab 求解线性规划问题，必须是这样的“标准形式”。,线性规划,例 2.4
13、.1 在2.2 的引例中，我们对食用油加工计划问题建立了如下的线性规划模型：,线性规划,将上述模型改写成 Matlab 适用的模型，其形式为：,线性规划,建立 M 文件，编写 Matlab 程序：c = 110; 120; 130; 110; 115; -150A = 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 = in
14、f*ones(6, 1);x = linprog(c, A, b, Aeq, beq, xLB, xUB);x，Profit=c*x,线性规划,运行上述 Matlab 程序，计算得：,x = 159.2593 40.7407 0.0000 250.0000 0 450.0000Profit = -1.7593e+004,线性规划,于是月采购与生产计划为：,线性规划,2.5 灵敏度分析与参数线性规划,2.5.1 线性规划问题的灵敏度分析 灵敏度分析是指对系统因周围条件变化显示出来的敏感程度的分析。,线性规划,在前面讨论线性规划问题时，我们都设定aij, bi, cj 是常数。但在许多实际问题中，
15、包括大型线性规划问题，这些系数往往是估计值或预测值，经常有少许的变动。例如在2.2 的引例中，如果市场条件发生变化，cj 值就会随之变化；生产工艺条件发生改变，会引起 bi 变化，aij 也会由于种种原因产生改变。,线性规划,因此提出这样两个问题： 当线性规划模型中的参数有一个或几个发生不大的变化时，已求得的线性规划问题的最优解会有什么变化； 或者这些参数在什么范围内变化时，线性规划问题的最优解不变。 这涉及解的稳定性问题。,线性规划,当然，有一套理论方法可以进行灵敏度分析(参见1,2)，这里就不讨论了。 但在实际应用中，对于不同的参数值重复求解线性规划问题，不失为一种可用的方法，特别是使用计
16、算机求解时。,线性规划,2.5.2 参数线性规划 参数线性规划是研究 aij, bi, cj 这些参数中某一参数连续变化时，使最优解发生变化的各临界点的值。即把某一参数作为参变量，而目标函数在某区间内是这参变量的线性函数，含这参变量的约束条件是线性等式或不等式。 当然，在实际应用中，给定参变量一个步长重复求解线性规划问题，以观察最优解变化情况，也是一种可用的数值方法。,线性规划,2.6 范例 载货问题：有一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如下面表 2.6.1 所示。,线性规划,现有三种货物待运，已知有关数据列于下面表 2.6.2。,线性规划,又为了航运安全，要求前、中、
17、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系。具体要求前、后舱分别与中舱之间载重量比例上偏差不超过 15%，前、后舱之间不超过 10%。 问该货轮应装载 A、B、C 各多少件，运费收入为最大？,线性规划,解：(1) 确定决策变量 因为 A、B、C 三种商品在货轮的前、中、后舱均可装载，令 i = 1, 2, 3 分别代表商品 A、B、C，用 j = 1, 2, 3 分别代表前、中、后舱。 设决策变量 xij 为装于 j 舱位的第 i 种商品的数量(件)。,线性规划,(2) 确定目标函数 商品 A 的件数为：x11 + x12 + x13，即装于货轮前、中、后舱商品 A 的件数之和；
18、商品 B 的件数为：x21 + x22 + x23，即装于货轮前、中、后舱商品 B 的件数之和； 商品 C 的件数为：x31 + x32 + x33，即装于货轮前、中、后舱商品 C 的件数之和。 为使运费总收入最大，目标函数为 max Z = 1000(x11 + x12 + x13) + 700(x21 + x22 + x23) + 600(x31 + x32 + x33),线性规划,(3) 确定约束条件 前、中、后舱位载重量限制为： 8x11 + 6x21 + 5x31 2000 8x12 + 6x22 + 5x32 3000 8x13 + 6x23 + 5x33 1500 前、中、后舱位
19、体积限制为： 10 x11 + 5x21 + 7x31 4000 10 x12 + 5x22 + 7x32 5400 10 x13 + 5x23 + 7x33 1500,线性规划, A、B、C 三种商品数量限制为： x11 + x12 + x13 600 x21 + x22 + x23 1000 x31 + x32 + x33 800 根据各舱实际载重量大体应保持各舱最大允许载重量的比例关系，且前、后舱分别与中舱之间载重量比例上偏差不超过 15%，前、后舱之间不超过 10%，可得舱体平衡条件为：,线性规划, 且各决策变量要求非负，即 xij 0，i = 1, 2, 3，j = 1, 2, 3。 综上所述，该问题的线性规划模型如下：,线性规划,线性规划,为了应用 Matlab 求解上述线性规划问题，将上述模型改写成 Matlab 适用的模型，其形式为：,线性规划,线性规划,最后解得：总费用为：8.01105。,
