01 第一章 线性规划与单纯形法.pptx

第1页：例1生产计划问题与数据表

[eg.1] 生产计划问题：产品Ⅰ、Ⅱ各生产多少件，可使利润最大？设产品Ⅰ生产 x1 件、产品Ⅱ生产 x2 件。

目标函数：max z = 2x1 + 3x2

约束条件：x1 + 2x2 ≤ 8，4x1 ≤ 16，4x2 ≤ 12，x1、x2 ≥ 0。其中 z 为利润函数，max z 表示求 z 的最大值。

第2页：例2污水处理问题与数据表

[eg.2] 污水处理问题：环保要求河水含污低于 2‰，河水可自身净化 20%。问化工厂 1、2 每天各处理多少污水，使总费用最少？

设化工厂1处理污水 x1 万m3、化工厂2处理污水 x2 万m3。

目标函数：min z = 1000x1 + 800x2

• (2 − x1)/500 ≤ 2/1000
• [(1 − 0.2)(2 − x1) + 1.4 − x2] / (500 + 200) ≤ 2/1000
• x1 ≤ 2，x2 ≤ 1.4，x1、x2 ≥ 0

这里 min z 表示求 z 的最小值。

第3页：线性规划的数学模型

线性规划的数学模型（一般形式）：

max(min) z = c1x1 + c2x2 + … + cnxn

• a11x1 + a12x2 + … + a1nxn ≤ (=, ≥) b1
• a21x1 + a22x2 + … + a2nxn ≤ (=, ≥) b2
• ……
• am1x1 + am2x2 + … + amnxn ≤ (=, ≥) bm
• x1，x2，…，xn ≥ 0

第4页：线性规划三要素说明

决策变量

x1，x2，…，xn。一组决策变量表示为问题的一个方案。

目标函数

max(min) z，z 为决策变量的线性函数。

约束条件

一组线性不等式。

其中 cj 为价值系数，bi 为资源，aij 为技术系数（i = 1,…,m；j = 1,…,n）。

第5页：例3图解法求解步骤

1.2 图解法　[eg.3] 用图解法求 eg.1：max z = 2x1 + 3x2。

• x1 + 2x2 ≤ 8　①
• 4x1 ≤ 16　②
• 4x2 ≤ 12　③
• x1，x2 ≥ 0

解：

1. 建立 x1 − x2 坐标；
2. 约束条件的几何表示；
3. 目标函数的几何表示。

第6页：图解法最优解与最大值

首先取 z = 0，然后使 z 逐渐增大，直至找到最优解所对应的点。可见在 Q2 点 z 取到最大值，Q2 点坐标为 (4，2)，即 x1 = 4、x2 = 2。

• 最优解：x1* = 4，x2* = 2
• 最大值：max z = z* = 2x1 + 3x2 = 14（元）

第7页：唯一最优解与无穷多最优解

讨论：

（1）唯一最优解

max z = z* 时解唯一，如上例。

（2）无穷多最优解

[eg.4] 对 eg.1，若目标函数 z = 2x1 + 4x2，此时表示目标函数的直线与表示条件①的直线平行，最优点在线段 Q3Q2 上，即存在无穷多最优解。图中 Q2(4,2)、Q3(2,3)。

第8页：例5无界解

（3）无界解　[eg.5] max z = 2x1 + 3x2，约束 4x1 ≤ 16，x1、x2 ≥ 0，则 x2 → ∞，z → ∞，即存在无界解。在实际问题中，可能是缺少约束条件。

第9页：例6无可行解

（4）无可行解　[eg.6] max z = 2x1 + 3x2，约束 2x1 + 4x2 ≥ 8，x1 + x2 ≤ 1，x1、x2 ≥ 0。两约束无公共部分，无可行域，即无可行解。在实际问题中，可能是关系错。

第10页：线性规划的标准型

1.3 线性规划的标准型　1、标准型：

max z = c1x1 + c2x2 + … + cnxn

• a11x1 + a12x2 + … + a1nxn = b1
• a21x1 + a22x2 + … + a2nxn = b2
• ……
• am1x1 + am2x2 + … + amnxn = bm
• x1，x2，…，xn ≥ 0

第11页：标准型的向量表示

线性规划标准型可用向量表示：约束条件写为 Σ xj pj = b，其中 pj 为决策变量 xj 对应的系数列向量，b 为资源向量。

本页以公式与矩阵图示为主，源文件文字提取较少，建议对照原课件图片核对向量符号。

第12页：标准型的矩阵描述

用矩阵描述为：max z = CX，AX = b，X ≥ 0。

X

X = (x1, x2, …, xn)T

C

C = (c1, c2, …, cn)

b

b = (b1, b2, …, bm)T

第13页：标准型的化法

2、标准型的化法

（1）min → max

因 min z = cx = −max(−z)，故 max(−z) = −min z = −cx。令 z′ = −z，则 max z′ = −cx。

（2）不等式（≤，≥）

对「≤」情况，在左边加上一个松弛变量（非负），变为等式；对「≥」情况，在左边减去一个剩余变量（非负），变为等式。注意：松弛变量、剩余变量在目标函数中的价值系数为 0。

（3）无约束变量

令 xk = xk′ − xk″，xk′、xk″ ≥ 0，代入即可。

第14页：例7化为标准型

[eg.7] 将下述问题化为标准型：

min z = −x1 + 2x2 − 3x3

• x1 + x2 + x3 ≤ 7　①
• x1 − x2 + x3 ≥ 2　②
• −3x1 + x2 + 2x3 = 5　③
• x1、x2 ≥ 0，x3 无约束

解：令 x3 = x3′ − x3″（x3′、x3″ ≥ 0）；①式加上一个松弛变量 x4；②式减去一个剩余变量 x5；令 z′ = −z。

• max z′ = x1 − 2x2 + 3(x3′ − x3″) + 0x4 + 0x5
• x1 + x2 + (x3′ − x3″) + x4 = 7
• x1 − x2 + (x3′ − x3″) − x5 = 2
• −3x1 + x2 + 2(x3′ − x3″) = 5
• x1、x2、x3′、x3″、x4、x5 ≥ 0

第15页：可行解、最优解与基

1.4 线性规划解的概念　设线性规划为 max z = CX ①，AX = b ②，X ≥ 0 ③，A 为 m×n 矩阵，n > m，RankA = m（A 为行满秩矩阵）。

可行解

满足条件②、③的 X。

最优解

满足条件①的可行解。

基

取 B 为 A 中的 m×m 子矩阵，RankB = m，则称 B 为线性规划问题的一个基。取 B = (p1, p2, …, pm)，其中 pj = (a1j, a2j, …, amj)T，则称 x1, x2, …, xm 为基变量，其它为非基变量。

第16页：基解的矩阵表达

4、基解：取 B = (p1, p2, …, pm)，将约束方程组按基变量与非基变量分块写成矩阵形式，令 xm+1 = … = xn = 0（非基变量为 0），则 BX_B = b，由此求得基变量取值。

本页以分块矩阵图示为主，源文件文字提取有限，建议对照原课件图片核对矩阵元素下标。

第17页：基可行解与可行基

基可行解

满足③式（X ≥ 0）要求的基解。如图所示，各边交点 O、Q1、Q2、Q3、Q4 均为基可行解；而其延长线的交点 Q5 为基解，但不是基可行解。

可行基

基可行解对应的 B 为可行基。

各点坐标：O(0,0)、Q1(4,0)、Q2(4,2)、Q3(2,3)、Q4(0,3)、Q5(4,3)。解的集合关系：基解分为基可行解与非可行解，可行解分为基可行解与非可行解。

第18页：§2几何意义与凸集定义

§2 线性规划问题的几何意义　2.1 基本概念

凸集

设 K 为 En（n 维欧式空间）的一点集，X(1) ∈ K，X(2) ∈ K。若 αX(1) + (1 − α)X(2) ∈ K（0 < α < 1），则称 K 为凸集。

图中给出凸集与非凸集的对比：非凸集内两点的连线会部分落在集合之外，凸集则不会。

第19页：顶点与凸组合

顶点

X ∈ K，X(1) ∈ K，X(2) ∈ K（任意两点）。若 X 不能用 αX(1) + (1 − α)X(2) 表示（0 < α < 1），则称 X 为 K 的一个顶点。注：顶点所对应的解是基可行解。

凸组合

设 X(i) ∈ En，若存在 0 < μi < 1（i = 1,2,…,k），使 X = Σ μi X(i)，则称 X 为 X(i)（i = 1,2,…,k）的凸组合。

第20页：可行域凸性与三个基本定理

2.2 基本定理

定理1

若线性规划存在可行域，则可行域 D = {X | AX = b，X ≥ 0} 为凸集。

证明：设 X(1) = (x1(1), x2(1), …, xn(1))T ∈ D，X(2) = (x1(2), x2(2), …, xn(2))T ∈ D，且 X(1) ≠ X(2)，有 AX(1) = b，AX(2) = b。令 X = αX(1) + (1 − α)X(2)（0 < α < 1），则 AX = αAX(1) + (1 − α)AX(2) = αb + (1 − α)b = b；又因 α > 0、1 − α > 0，故 X ≥ 0，即 D 为凸集。

定理2

线性规划的基可行解对应于可行域的顶点。

定理3

若线性规划有解，则一定存在基可行解为最优解。

第21页：§3单纯形法与松弛基

§3 单纯形法　基本思路：从可行域的一个顶点到另一个顶点迭代求最优解。

3.1 初始基可行解的确定　1、松弛基（松弛变量对应的 B）。

[eg.8] max z = x1 + 3x2，约束 x1 + 2x2 ≤ 3，2x1 + 3x2 ≤ 4，x1、x2 ≥ 0。

化标准型：max z = x1 + 3x2 + 0x3 + 0x4，x1 + 2x2 + x3 = 3，2x1 + 3x2 + x4 = 4，x1、x2、x3、x4 ≥ 0。取 x3、x4 为基变量，令非基变量 x1 = x2 = 0，得初始基可行解 X(0) = (0 0 3 4)T。

第22页：例9观察法

2、观察法　[eg.9] max z = x1 + 3x2 + 2x3 + x4，约束 x1 + 2x2 + 3x3 = 3，3x2 + x3 + x4 = 4，x1、x2、x3、x4 ≥ 0。

选 X_B = (x1 x4)T，令 x2 = x3 = 0，则初始基可行解 X(0) = (3 0 0 4)T。

第23页：例10人工基

3、人工基　[eg.10] max z = x1 + 2x2 + 3x3，约束 x1 + 3x2 + 2x3 = 3，2x1 + x2 + x3 = 4，x1、x2、x3 ≥ 0。

分析：A = [1 3 2; 2 1 1]，因找不到单位矩阵基，故引入人工变量作为初始基变量（2 个）。

第24页：最优性的检验与解的判别

3.2 最优性的检验与解的判别。本页为小节标题页，检验数的计算公式与解的三条判别准则见后续页图示。

第25页：检验数判别式

本页为公式推导的承接页，源文件仅提取到「则」等少量文字。内容为检验数 σj 判别式的推导过渡，建议对照原课件图片核对公式。

第26页：解的判别准则

解的判别：

1. 若所有检验数 σj ≤ 0，则此时的基可行解为最优解；
2. 若存在某个非基变量的检验数 σk > 0，且其系数列向量 Pk ≤ 0，则该线性规划问题具有无界解（或称无最优解）；
3. 若所有 σj ≤ 0，又存在某个非基变量的检验数 σk = 0，则该线性规划问题具有无穷多最优解。

第27页：基变换

3.3 基变换。本页为小节标题页，入基变量与出基变量的确定规则见相邻页的图示与算例。

第28页：旋转运算（消元运算）

3.4 旋转运算（消元运算）：以主元 a_lk′ 为中心，把入基变量对应的系数列向量 P_k′ 消元化为单位列向量（除主元位置外，其余元素均化为 0）。

由此得到新的基可行解，重复 3.2—3.4，直至求出最优解。

第29页：单纯形表的结构

3.5 单纯形表　展开如下：

• a11x1 + a12x2 + … + a1nxn + xn+1 = b1（−cn+1）
• a21x1 + a22x2 + … + a2nxn + xn+2 = b2（−cn+2）
• ……
• am1x1 + am2x2 + … + amnxn + xn+m = bm（−cn+m）
• c1x1 + c2x2 + … + cnxn + cn+1xn+1 + … + cn+mxn+m − z = 0
• σ1x1 + σ2x2 + … + σnxn + 0xn+1 + … + 0xn+m − z = Z0

第30页：例11建立单纯形表

建立单纯形表的表头：依次列出 c_B（基变量价值系数）、x_B（基变量）、b（右端常数）、θ（最小比值）以及 x1…xn、xn+1…xn+m 各变量列，最下方为检验数行 σj 与 −z 列（Z0）。

[eg.11] 用单纯形法求解：max z = x1 + 3x2，约束 x1 + 2x2 ≤ 8，4x1 ≤ 16，4x2 ≤ 12，x1、x2 ≥ 0。

第31页：例11初始单纯形表

解：① 标准化，建立单纯形表。引入松弛变量 x3、x4、x5 为初始基变量：

• max z = x1 + 3x2 + 0x3 + 0x4 + 0x5
• x1 + 2x2 + x3 = 8
• 4x1 + x4 = 16
• 4x2 + x5 = 12
• x1、x2、x3、x4、x5 ≥ 0

表中 c_B 列均为 0，基变量取值为 x3 = 8、x4 = 16、x5 = 12。此时的解：X(0) = (0 0 8 16 12)T，z(0) = 0。

第32页：例11判别与基变换

② 解的判别：因 σ1 = 1、σ2 = 3 > 0，故 X(0) 非最优解。

③ 基变换：max{σ1, σ2} = 3 = σ2，故 x2 入基；min{8/2, --, 12/4} = 12/4，故 x5 出基。表中对应 θ 值：x3 行为 8/2，x4 行为「--」，x5 行为 12/4。

第33页：例11最优解与最大值

迭代过程：第一次迭代后 X(1) = (0 3 2 16 0)T，z(1) = 9，X(1) 非最优；继续令 x1 入基、x3 出基（θ 值分别为 2/1 与 16/4）。

此时的解：X(2) = (2 3 0 8 0)T，z(2) = 11，X(2) 为最优解。

• 最优解：x* = (2 3 0 8 0)T
• 最大值：z* = 11

第34页：迭代过程与顶点对应关系

单纯形法迭代的每一步，对应可行域上的一个顶点：

第35页：§4人工变量法与大M法

§4 单纯形法的进一步讨论　4.1 人工变量法　1、大M法（M 为很大的正数）。

法则：对于 max 问题，人工变量在目标函数中的价值系数为 −M；对于 min 问题，人工变量在目标函数中的价值系数为 M。

[eg.12] min z = x1 + 5x2 + 0x3 + 0x4，约束 2x1 + 3x2 + x3 = 6，2x1 + x2 − x4 = 1，x1、x2、x3、x4 ≥ 0。

解：化为 min z = x1 + 5x2 + 0x3 + 0x4 + Mx5（x5 为人工变量），约束 2x1 + 3x2 + x3 = 6，2x1 + x2 − x4 + x5 = 1，变量均非负，列单纯形表求解。

第36页：例12初始单纯形表

对 min z = x1 + 5x2 + 0x3 + 0x4 + Mx5，约束 2x1 + 3x2 + x3 = 6、2x1 + x2 − x4 + x5 = 1，建立初始单纯形表。

对于 min 问题，若 min{σj < 0} = σk，则 xk 为入基变量。这里 x1 为入基变量，x5 为出基变量，a21 = 2 为主元。表中 θ 值：x3 行 6/2，x5 行 1/2；检验数行含 5 − M 与 1 − 2M。

本页单纯形表在源文件中数字粘连严重，无法安全切分为标准单元格，已按文字表述保留，建议对照原课件图片人工还原表格。

第37页：例12迭代单纯形表

进一步迭代：x1 换入基后，基变量为 x3 与 x1，表中相应行的系数为 1/2、−1/2 等，检验数行更新为 M + 1/2、1/2、0、9/2、0。

本页单纯形表在源文件中数字粘连严重，无法安全切分为标准单元格，已按文字表述保留，建议对照原课件图片人工还原表格。

第38页：例12最优解与两阶段法引入

因为所有 σj ≥ 0，于是得问题的最优解：

• 最优解：X* = (x1 x2 x3 x4 x5)T = (1/2 0 5 0 0)T
• 目标函数最小值：Z* = 1/2

2、两阶段法：由于大 M 不是一个确定的数，大M法适宜于手工计算而不适合编程求解，为此引入两阶段法。

第一阶段：给线性规划加入人工变量，并构造辅助规划，辅助规划的目标函数为 min w = xn+1 + …… + xn+m（xn+1,…,xn+m 为人工变量）。

第39页：两阶段法的计算步骤

以人工变量为初始基变量，列表计算。

1. 若本阶段（第一阶段）无最优解，表示原线性规划无解，停止计算；
2. 若有最优解，则转第二阶段。

第二阶段：在第一阶段最优表中，去掉人工变量，换上原问题目标函数，作为本阶段初始表，以此用单纯形法进行迭代运算，求出结果。

第40页：例13第一阶段辅助规划

例13 用两阶段法求解：min z = x1 + 5x2，约束 2x1 + 3x2 ≤ 6，2x1 + x2 ≥ 1，x1、x2 ≥ 0。

解：第一阶段：将问题化为等式约束，引进人工变量 x5，得辅助规划：

• min w = x5
• 2x1 + 3x2 + x3 = 6
• 2x1 + x2 − x4 + x5 = 1
• x1、x2、x3、x4、x5 ≥ 0

原问题目标函数记为 min z = x1 + 5x2 + 0x3 + 0x4。

第41页：例13第一阶段单纯形表

对 min w = x5，约束 2x1 + 3x2 + x3 = 6、2x1 + x2 − x4 + x5 = 1，列表计算：初始基为 x3、x5，θ 值 6/2 与 1/2，主元为 [2]；迭代后基变量为 x3 与 x1，检验数行为 1、0、0、0。

第一阶段有最优解。

本页单纯形表在源文件中数字粘连严重，无法安全切分为标准单元格，已按文字表述保留，建议对照原课件图片人工还原表格。

第42页：例13第二阶段最优解

第二阶段：去掉人工变量，换上原线性规划目标函数（见下表）。

• 最优解：X* = (1/2 0 5 0)T
• 目标函数最小值：Z* = 1/2

表中基变量为 x3 与 x1，取值分别为 5 与 1/2，检验数行为 0、9/2、0。

本页单纯形表在源文件中数字粘连严重，无法安全切分为标准单元格，已按文字表述保留，建议对照原课件图片人工还原表格。

第43页：退化解与计算循环

4.2 几个问题　若存在两个以上相同的最小比值，就会出现退化解。理论上讲，退化解可能使计算出现循环，从而得不到最优解。然而，实际问题中很少出现这种情况。

第44页：Bland规则

当计算中出现最小比值相同的情况时，可按 Bland 规则来计算。

Bland 规则：

1. 在 σj > 0 中，选下标小的非基变量入基；
2. 对相同的最小比值，选下标小的基变量出基。

注：min 问题中 σj 与 θi 的计算同 max 问题。

第45页：第一章习题

习题　P45，1.4　分别用图解法和单纯形法求解下列线性规划，并指出单纯形法迭代的每一步相当于图形上的哪一个顶点？