第七讲 插值方法与数据拟合

第二讲 线性规划

§ 2.1 引言

线性规划是运筹学的重要分枝，也是运筹学最基本的部分。20世纪30年代末，前苏联学者康托洛维奇（Д.

В.Канторович ）首先研究了线性规划问题。1939年，他撰写的《生产组织与计划中的数学方法》一书，是线性规划应用于工业生产问题的经典著作。然而这项工作长期不为人们所知。第二次世界大战期间，由于战争的需要，柯勃门（T. C. Koopmans）重行、独立地研究了运输问题。后来丹西格（G. B. Dantzig）于1947年发现了单纯形方法，并将其应用于与国防有关的诸如人员的轮训、任务的分派等问题。此后，线性规划的理论和方法日渐趋于成熟。

线性规划所研究的对象属于最优化的范畴，本质上是一个极值问题。和其它最优化问题一样，在建立线性规划问题的数学模型时，应首先明确三个基本要素：

决策变量（decision variables）：它们是决策者（你）所控制的那些数量，它们取什么数值需要决策者来决策，问题的求解就是找出决策变量的最优值。

约束条件（constraints）：它们是决策者在现实世界中所受到的限制，或者说决策变量在这些限制范围之内才有意义。

目标函数（objective function）：它代表决策者希望对其进行优化的那个指标。目标函数是决策变量的函数。 线性规划问题的特征是目标函数和约束条件中的函数都是决策变量的线性函数，并且约束是必不可少的（否则不存在有实际意义的解）。

§ 2.2 引例：食用油加工计划

加工一种食用油需要精炼若干种原油并把它们混合起来。原油来源有两类共5种： 植物油：VEG1，VEG2

非植物油：OIL1，OIL2，OIL3 购买每种原油的价格（镑/吨）见表2.2.1：

表2.2.1 VEG1 VEG2 OIL1 OIL2 OIL3 110 120 130 110 115

最终产品以150镑/吨价格出售。

植物油和非植物油需要在不同的生产线上进行精炼。每月能够精炼的植物油不超过200吨，非植物油不超过250吨；在精炼过程中，重量没有损失，精炼费用可忽略不计。

最终产品要符合硬度的技术条件。按照硬度计量单位，它必须在3—6之间。假定硬度的混合是线性的，而原油的硬度见表2.2.2：

表2.2.2 VEG1 VEG2 OIL1 OIL2 OIL3 8.8 6.1 2.0 4.2 5.0

问：为使利润最大，应该怎样制定它的月采购和加工计划？ 要建立表述这个问题的数学模型，首先需要确定它的三个要素。 1．确定决策变量

设x1，…，x5分别代表需要采购的5种原油的吨数，y代表需要加工的成品油的吨数。 2．确定约束条件

关于植物油：x1 + x2 ? 200

关于非植物油：x3 + x4 + x5 ? 250

硬度上限：8.8x1 + 6.1x2 + 2x3 + 4.2x4 + 5x5 ? 6y 硬度下限：8.8x1 + 6.1x2 + 2x3 + 4.2x4 + 5x5 ? 3y 连续性（均衡性）：x1 + x2 + x3 + x4 + x5 = y 非负性：xi ? 0（i =1, …, 5），y ? 0 3．确定目标函数

目标是使利润最大，即出售产品的收入扣除原油成本之后所得最大：150y ? 110x1 ? 120x2 ? 130x3 ? 110x4 ? 115x5 ?最大。

显然这是一个线性规划问题，可以用下面的数学模型来表述这个问题：

max Z = 150y ? 110x1 ? 120x2 ? 130x3 ? 110x4 ? 115x5 s.t. x1 + x2 ? 200

x3 + x4 + x5 ? 250

8.8x1 + 6.1x2 + 2x3 + 4.2x4 + 5x5 ? 6y ? 0

8.8x1 + 6.1x2 + 2x3 + 4.2x4 + 5x5 ? 3y ? 0 (2.2.1) x1 + x2 + x3 + x4 + x5 ? y = 0 xi ? 0（i =1, …, 5） y ? 0

§ 2.3 线性规划模型

§ 2.3.1 线性规划模型的一般形式

线性规划问题有各种不同形式，其目标函数可以是实现最大化，也可以是实现最小化；约束条件可以是

“?”，也可以是“?”，还可以是“=”的形式；决策变量可以非负，也可以是无符号限制。归纳起来，线性规划问题的数学模型的一般形式为：

max (min) Z = c1x1 ? c2x2 ? … ? cnxn，

s.t. a11x1 ? a12x2 ? … ? a1nxn ? ( =, ? ) b1

a21x1 ? a22x2 ? … ? a2nxn ? ( =, ? ) b2

???????????? (2.3.1) am1x1 ? am2x2 ? … ? amnxn ? ( =, ? ) bm xi ? 0（i =1, …, n）

或

max (min) s.t.?cxjnj?aj?1j?1nijxj?(or?,?) bi (i?1,?,m) (2.3.2)

xj?0 (j?1,?,n)这里“s.t.”是“subject to”的缩写，即“满足于”的意思。如果我们设

?a11?aA??21????am1a12a22?am2?a1n??b1??x1??c1??b??x??c??a2n??，b??2?，C??2?，X??2?， ????????????????????amn?bc?m??xn??n?那么，(3.1) 和 (3.2) 式也可用矩阵形式描述为：

max (min)Z?CTX s.t.AX?(or?,?) b (2.3.3)

X?0

§ 2.3.2 线性规划模型的标准形式

为理论研究之便，人们规定线性规划模型的标准形式（SLP：standard linear programming）为：

maxZ?CTX s.t.AX?b (2.3.4)

X?0若给定问题的目标函数是求min Z = CTX，则可化为求max Z' = ?CTX；若给定问题的约束条件中含有不等式：

ai1x1 ? ai2x2 ? … ? ainxn ? (或 ? ) bi，

则可等价地化为：

ai1x1 ? ai2x2 ? … ? ainxn ? xn +1 = bi，xn +1 ? 0，

或

ai1x1 ? ai2x2 ? … ? ainxn ? xn +1 = bi，xn +1 ? 0。

称新增加的变量xn +1为松弛变量。

§ 2.3.3 线性规划问题解的概念

对于线性规划问题，我们定义：

可行解（feasible solution）：满足全部约束条件的决策向量X?R n。 可行域：全部可行解构成的集合。（它是n维欧氏空间R n中的点集，而且是一个“凸多面体”。） 最优解：使目标函数达到最优值（最大值或最小值，并且有界）的可行解。

无界解：若求极大化则目标函数在可行域中无上界；若求极小化则目标函数在可行域中无下界。 性规划问题的最优解有下列几种情况：

(1) 有最优解时，可能有唯一最优解，也可能有无穷多个最优解。如果最优解不唯一，最优解一定有无穷多个，不可能为有限个。最优解的目标函数值均相等。

(2) 没有最优解时，也有两种情形。一是可行域为空集，二是目标函数值无界（求最大时无上界，求最小时无下界）。

定理：当线性规划问题有最优解时，一定可以在可行域的某个顶点上取到。当有唯一解时，最优解就是可行域的某个顶点。当有无穷多个最优解时，其中至少一个是可行域的一个顶点。

§ 2.3.4 几何解释

在这部分，我们给出一种求解两个变量的线性规划问题的几何方法，目的是阐明线性规划问题的基本原理及其直观的几何意义。

例2.3.1 求解线性规划问题

max Z = x1 ? x2， s.t. 2x1 ? 3x2 ? 6

3x1 ? 2x2 ? 6 xi ? 0（i =1, 2）

我们把x1，x2看成坐标平面上的坐标，则满足约束条件的点集，即可行域，如图2.3.1阴影部分所示。

目标函数x1 + x2 = c在坐标平面上是一簇平行线，称为目标函数的等值线，在同一等值线上目标值相等。

箭头表示目标函数值增大的方向，其方向与目标函数 x1 + x2 = c

图2.3.1 的梯度方向 (1, 1)T相同。

由于是求最大值问题，目标函数的等值线应沿梯

度方向移动，到临界状态，即可行域的顶点 (6/5, 6/5) 处，目标函数取得最大值12/5。继续沿梯度方向上升，目标函数值会更大，但与可行域无交点，即找不到满足所有约束条件的点使得目标值比12/5大。

因此，线性规划问题的最优解为临界等值线与可行域的交点：x* = (6/5, 6/5)，最优值为12/5。

例2.3.2 求解线性规划问题 max Z = 2x1 ? 3x2，

s.t. 2x1 ? 3x2 ? 6

3x1 ? 2x2 ? 6 xi ? 0（i =1, 2）

线性规划问题的可行域仍如图2.3.1所示，目标函数的梯度方向为 (2, 5)T。由于是求最大值问题，目标函数的等值线应沿梯度方向推进，临界等值线为2x1 ? 3x2 = 6，与可行域交于一线段PQ。P(0, 2)，Q(6/5, 6/5)，最优解为PQ上任一点，最优值为6。

例2.3.3 求解线性规划问题 min Z = ?2x1 ? x2，

s.t. ?x1 ? x2 ? 2

x1 ? 4x2 ? 2 xi ? 0（i =1, 2）

线性规划问题的可行域如图2.3.2所示，目标函数的梯度方向为 (?2, 5)T。由于是求最小值问题，目标函数的等值线应沿负梯度方向推进，可一直进行下去，得不到临界等值线为，此问题目标值无下界，无最优解。

例2.3.4 求解线性规划问题 min Z = ?2x1 ? 5x2，

s.t. ?x1 ? x2 ? 2

?x1 ? x2 ? 3 xi ? 0（i =1, 2）

线性规划问题的可行域如图2.3.3所示，是一空集。此问题无最优解。

图2.3.2

图2.3.3

§ 2.4 用Matlab解线性规划

在Matlab软件的优化工具箱中，求解线性规划的函数为：lp。其调用格式为

X = lp(c, A, b, VLB, VUB, X0) 或X = lp(c, A, b, VLB, VUB, X0, n)，

适用模型为：

minZ?cTX s.t.AX?bVLB?X?VUB其中X0为初始点，n表示AX ? b中前n个约束是等式约束。

例2.4.1 在 § 2.2的引例中，我们对食用油加工计划问题建立了如下的线性规划模型：

max Z = 150y ? 110x1 ? 120x2 ? 130x3 ? 110x4 ? 115x5 s.t. x1 + x2 ? 200

x3 + x4 + x5 ? 250

8.8x1 + 6.1x2 + 2x3 + 4.2x4 + 5x5 ? 6y ? 0

8.8x1 + 6.1x2 + 2x3 + 4.2x4 + 5x5 ? 3y ? 0 x1 + x2 + x3 + x4 + x5 ? y = 0 xi ? 0（i =1, …, 5） y ? 0

将上述模型改写成Matlab适用的模型，其形式为：

min Z = 110x1 + 120x2 + 130x3 + 110x4 + 115x5 ?150y s.t. x1 + x2 + x3 + x4 + x5 ? y = 0

x1 + x2 ? 200 x3 + x4 + x5 ? 250

8.8x1 + 6.1x2 + 2x3 + 4.2x4 + 5x5 ? 6y ? 0

? 8.8x1 ? 6.1x2 ? 2x3 ? 4.2x4 ? 5x5 + 3y ? 0 xi ? 0（i =1, …, 5） y ? 0

建立M文件，编写Matlab程序：

c = [110; 120; 130; 110; 115; -150] A = [1, 1, 1, 1, 1, -1; 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 = [0; 200; 250; 0; 0] xLB = zeros(6, 1) xUB = inf*ones(6, 1) x0 = 0*ones(6, 1) n = 1

x = lp(c, A, b, xLB, xUB, x0, n); x

Profit=c'*x

运行上述Matlab程序，计算得：

x =

159.2593 40.7407 0.0000 250.0000 0 450.0000 Profit =

-1.7593e+004

于是月采购与生产计划为： VEG1 VEG2 原油 159.2593 40.7407 采购量 生产量：450

参考文献：

[1] 卢开澄，单目标、多目标与整数规划，清华大学出版社，1999。 [2] 束金龙，闻人凯，线性规划理论与模型应用，科学出版社，2003。 [3] 叶其孝，大学生数学建模竞赛辅导教材，湖南教育出版社，1993。 [4] 傅鹏等，数学实验，科学出版社，2000。 [5] 谢云荪，数学实验，科学出版社，2000。

[6] 赵静，但琦，数学建模与数学实验，高等教育出版社，2000。

OIL1 0 OIL2 250 总利润：1.7593?104 OIL3 0

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