北航运筹学(最优化方法)第二章 线性规划的基本理论与方法

?????????????0??????????x?x?取值无约束321321321321321063244239232minxxxxxxxxxxxxxz03???x??????????3?3?1???3??3x???1????3??3???1????3x??3???1????3?x?3???1??06332442239200332max54225242542xxxxxxxxxxxxxxxxxxxxxxxzzz??11?xx??33?3x??xx??令03??x其中并按上述规则该问题的标准形式为
厂排出的工业污水流到第二化工厂以前， 20%可以自然净化。 厂排出的工业污水流到第二化工厂以前，有 20%可以自然净化。根 据环保要求，河流中工业污水的含量不应大于 0.2%。这两个工厂 据环保要求， .2%。 都需各自处理一部分工业污水。第一化工厂处理工业污水的成本 都需各自处理一部分工业污水。
3 3 是 1000 元/万 m ， 第二化工厂处理工业污水的成本是 800 元/万 m 。 3 3
例1：（产品组合问题） ：（产品组合问题） 产品组合问题
某厂利用A 两种原料，生产甲、乙两种产品，有关数据如下： 某厂利用A、B两种原料，生产甲、乙两种产品，有关数据如下：
单位产 品消耗 原料 原料名称 产品名称
甲
乙
可供利用的原料 数量（T/日 数量（T/日） 6 8
A B
千元/T /T） 产品售价 （千元/T）
设 x1, x2分别代表每粒胶丸 中甲、 中甲、乙两种原料的用量
例4、合理下料问题 、
长的钢筋， 用7.4m长的钢筋，分别截取 长的钢筋 分别截取2.9m、2.1m、1.5m各至少 、 、 各至少 100根，要求用料最少。 根 要求用料最少。
分别代表采用切割方案1~8所需 所需7.4米的 设 xj 分别代表采用切割方案 所需 米的 钢筋的数量。 钢筋的数量。

ij m n
1
m
则模型可表示为
Maxz CX
s .t
.
AX X
0
b
2020/11/9
运筹学 第二章 线性规划
LP OPTIMUM FOUND AT STEP 2
OBJECTIVE FUNCTION VALUE
1) 428.0000
VARIABLE VALUE X1 20.000000 X2 24.000000
A
B
CD
0.1
0
0.1 0.2
0
0.1
0.2 0.1
0.4
0.6
2.0 1.7
试决定买M与N二种饲料各多少公斤而使支出的总费用为 最少？
运筹学 第二章 线性规划
2020/11/9
解：设购买M、N饲料各为 x , x ，则
1
2
M 1 i x 1 n 0 4 x 2 z
0.1x1 0 x 2 0.4
第二章 线性规划（Linear Programming）
第一节 线性规划的模型与图解法 第二节 单纯形法 第三节 对偶问题与灵敏度分析 第四节 运输问题 第五节 线性整数规划
2020/11/9
运筹学 第二章 线性规划
第一节 线性规划的模型与图解法
一、线性规划问题及其数学模型
在生产管理和经营活动中经常需要解决：如何 合理地利用有限的资源，以得到最大的效益。
2020/11/9
运筹学 第二章 线性规划
2020/11/9
例1 某工厂可生产甲、乙两种产品，需消耗 煤、电、油三种资源。现将有关数据列表如下：
资源单耗 产 品
资源 煤 电 油
单位产品价格
甲乙

基解：令所为 有 0， 非求 基出 变的 (1量 .2)的 满解 足 称为基解。
基可行解与可行 足基 (1.3)： 的满 基解称为基可 对应基可行解的 为基 可， 行称 基。基 显可 然 解的数目 基解的数 C目 nm
基本最优解与最优基 满： 足(1.1) 的基可行解称为基本 优最 解，
对应m,如果 B是矩A中 阵的一 mm个 阶非奇异 (|B子 |0)矩 ,则阵 称 B是线性规 题的一个基。
基向量与非基向B量 中： 的基 列向量称为，基向 矩阵A中除B之外各列即为非，基 A中 向共 量 有nm个非基向量。
基变量与非基 基变 向P量 j量 对： 应与 的xj变 称量 为基变量；否 基则 变称 量为 。非
将文件存储并命名后，选择菜单 “Solve” 并对提示 “ DO RANGE(SENSITIVITY)ANALYSIS? ”回答“是”，即 可得到如下输出：
“资源” 剩余 为零的约束为 紧约束（有效 约束）
OBJECTIVE FUNCTION VALUE
1)
3360.000
VARIABLE VALUE REDUCED COST
可行解 基 解
基可行解
1.4 线性规划问题的图解法
下面结合例1的求解来说明图解法步骤。
例1
max Z 4 x1 3 x2
2 x1 3 x2 24
s. t 3 x1 2 x2 26
x2
x1, x2 0
Q3(6,4)
第一步：在直角坐标系中分
别作出各种约束条件，求出
3x1+2x2=26
Q2(6,4)
B
条 件
3x1 100
x1,x2 0
l3:3x1 100 l4
l4:x10,l5:x200

问题描述
线性规划问题通常由三个基本部分组成，即决策变量、约束条件 和目标函数。决策变量是问题中需要求解的未知数，约束条件是 限制决策变量取值的条件，目标函数是要求最大或最小的函数。
线性规划的应用领域
01
02
03
04
生产计划
在制造业中，线性规划可以用 于制定最优的生产计划，以最 大化利润或最小化成本。
02
线性规划的基本概念
线性方程组
线性方程组是由多个线性方程组成的数学模型，描 述了多个变量之间的线性关系。
线性方程组可以用矩阵和向量表示，通过矩阵运算 和代数方法求解。
线性方程组有多种解法，如高斯消元法、LU分解、 迭代法等。
约束条件与目标函数
02
01
03
约束条件是限制变量取值的条件，通常表示为变量的 上界、下界或等式约束。
目标函数是描述问题目标的数学表达式，通常是最小 化或最大化的线性或非线性函数。
约束条件和目标函数共同构成了线性规划问题的数学 模型。
线性规划的解
线性规划的解是指满足 所有约束条件并使目标 函数取得最优值的变量 取值。
线性规划问题可能有多 个解，也可能无解或无 界解。
最优解的性质包括最优 性、可行性和唯一性。
最优解可以通过求解线 性方程组或使用专门的 优化软件获得。
03
线性规划的求解方法
单纯形法
01
基本概念
单纯形法是一种求解线性规划问题的迭代算法，通过 不断迭代寻找最优解。
02 1. 初始化 选择一个初始可行解，并确定初始基可行解。
03
2. 迭代
根据目标函数系数和约束条件系数，计算出单纯形表 格，然后进行迭代更新。
运筹学基础-线性规划(方法)

D≠ F 时但目标函数无下界时,称线性规划(LP) 无界或无最优解; D≠ F 时若目标函数有下界,可以证明线性规 划(LP)必有最优解.
27Leabharlann 可行域为凸集定理2.2.1线性规划问题 min cTx (LP) s.t. Ax=b x≥0 的可行域D为凸集.
对任意的a ∈ [0,1],设 z=ax+(1-a)y,则z≥0,且 Az=A(ax+(1-a)y) =aAx+(1-a)Ay =ab+(1-a)b =b 证明 任取x,y ∈ D,则有 因此z ∈ D Ax=b,x≥0, Ay=b,y≥0 D为凸集.
15
凸函数的性质
2
1
0
-1
-2 -1.5 -1 -0.5 0 0.5 1 1.5 16
凸函数的判断
定理2.1.1 设f(x)定义在凸集D Rn上,x,y∈D. 令F (t)=f (tx+(1-t)y), t ∈ [0,1],则 (i) f(x)是凸集D上的凸函数的充要条件是对任 意的x,y∈ D,一元函数F (t)为[0,1]上的凸函 数. (ii) f(x)是凸集D上的严格凸函数的充要条件是 对任意的x,y ∈ D(x≠y),一元函数F (t)为[0,1] 上的严格凸函数. 该定理的几何意义是:凸函数上任意两点之间 的部分是一段向下凸的弧线.
5
凸集的性质
(i)有限个(可以改成无限)凸集的交集为凸集. 即:若Dj(j ∈ J)是凸集,则它们的交集 D={x|x ∈ Dj,j ∈ J } 是凸集. (ii)设D是凸集,b是一实数,则下面集合是凸集 b D={y | y =b x, x ∈ D}.
6
凸集的性质
(iii)设D1,D2是凸集,则D1与D2的和集 D1+D2={y|y=x+z,x ∈ D1,z ∈ D2}是凸集. 注:和集与并集有很大的区别,凸集的并集未必 是凸集, 而凸集的和集是凸集. 例:D1={(x,0)T|x ∈ R}表示 x 轴上的点, D2={(0,y)T|y ∈R},表示 y 轴上的点. 则D1∪D2表示两个轴的所有点,它不是凸集; D1+D2=R2是凸集

切线法（一维牛顿法） 设函数f(x)在(a,b)内有二阶连续导数
求解思路是：在初始探索点xk 处用泰勒展式作 f(x)的二次近似函 数g(x) ，再用 g(x) 的最小点作新的探索点。即
f ( x0 ) 令x0 a或b, x1 x0 为第1次探索点, , f ( x0 ) f ( xk ) xk 1 xk 为第k次探索点 f ( xk ) 则对给定的误差 ,当 f ( xk ) 时, 1 xk 1 xk f ( xk )
k
λk 1 2 3
ф′ (λk) 2 -3.5357 13.95
1／ф″(λk ) 1.1071 -1.2952 不收敛。 5 13.50
插值法： 用ф(λ)在2 或3 个点的函数值或导数值，构造2 次或 3次多项式作为ф(λ)的近似值，以这多项式的极小点 为新的迭代点。 3点2次，2点2次，4点3次，3点3次，2点3次等 以3点2次为例： 取λ 1，λ 2，λ3，求出ф(λ1)， ф(λ2)， ф(λ3)
x1 则把（2）代入上式得 若 x2
x1 a a (1 )(b a ) a (1 )(b a ) 2 (b a ) 5 1 2 2 (1 ) ,即 1 0 0.618 2
所以第 k 探索点的取法为
( x1 x2 ) g ( x3 ) ( x2 x3 ) g ( x1 ) ( x3 x1 ) g ( x2 ) ( x1 x2 )( x2 x3 )( x3 x1 )
( x1 x2 ) g ( x3 ) ( x2 x3 ) g ( x1 ) ( x3 x1 ) g ( x2 ) ( x1 x2 )( x2 x3 )( x3 x1 )

Z=CBB-1b+(σm+1,
σm+k ,
xm+1
σn
)
CB B-1b+σ m+k
xn
因为 m+k 0，故当λ→+∞时，Z→+∞。
用初等变换求改进了的基本可行解
假设Ｂ是线性规划 maxZ=CX,AX=b,X 0的可行基，则
AX=b
(BN)
XB XN
b
(I,B-1 N)
➢ 若在化标准形式前，m个约束方程都是“≤”的形式， 那么在化标准形时只需在一个约束不等式左端都加上一个松弛变 量xn+i (i=12…m)。
➢ 若在化标准形式前，约束方程中有“≥”不等式， 那么在化标准形时除了在方程式左端减去剩余变量使不等式变 成等式以外，还必须在左端再加上一个非负新变量，称为 人工变量．
单纯形法简介
考虑到如下线性规划问题 maxZ=CX AX=b X 0
其中Ａ一个m×n矩阵，且秩为m，ｂ总可以被调整为一 个m维非负列向量，Ｃ为n维行向量，Ｘ为n维列向量。
根据线性规划基本定理： 如果可行域Ｄ={ Ｘ∈Ｒn / ＡＸ=ｂ，Ｘ≥0}非空有界， 则Ｄ上的最优目标函数值Ｚ=ＣＸ一定可以在Ｄ的一个顶 点上达到。 这个重要的定理启发了Dantzig的单纯形法， 即将寻优的目标集中在D的各个顶点上。
非基变量所对应的价值系数子向量。
要判定 Z=CBB-1b 是否已经达到最大值，只需将
XB =B-1b-B-1NX N 代入目标函数，使目标函数用非基变量
表示，即：
Z=CX=(CBCN
)
XB XN
=CBXB +CNXN =CB (B-1b-B-1NXN )+CNXN

每周资源总量 160 15
定义x1为生产甲种药品的计划产量数，x2为生产乙种药品的计划产量数。 数学模型为
m ax Z = 5 x 1 + 2 x 2
s.t. （subject to) (such that)
30x1 20x 2 160 5x1 x 2 15 x1 4 x 0, x 0 1 2
Z Z Z= ， 2 = （ 5 ，） x1 x 2
B( 2, 5) 5 5x1+2x2=5 ▽Z O 1 A 30x1+20x2=160
5
10
15
x1
图解法的几种可能结果
(1）有唯一最优解，如例1。 （2）有无穷多最优解 如例1中的目标函数设为 maxZ=10x1+2x2
工厂1 工厂2
500万m3
200万m3
12
决策变量：x1、x2——分别代表工厂1和工厂2处理 污水的数量(万m3)。
则目标函数：min z=1000x1+800x2 约束条件： 第一段河流（工厂1——工厂2之间）： (2－x1)/500 ≤0.2% 第二段河流：[ 0.8(2－x1) +(1.4－x2)]/700≤0.2% 此外有： x1≤2； x2≤1.4 化简有： min z=1000x1+800x2 x1 ≥1 0.8x1 + x2 ≥1.6 x1 ≤2 x2≤1.4 x1、x2≥0 称之为上述问题的数学模型。
3
佳林· 库普曼斯(1910年—1985年)，美国人 ，1910 年8月28日生于荷兰，1940年离开荷兰移居美国。1975 年，他和康托罗维奇同时获得诺贝尔经济学奖。线性规 划经济分析法的创立者。

第二章 线性规划
应用模型举例 线性规划的数学模型 线性规划的标准型 线性规划的解和基本定理 单纯型法 大M法
线性规划（Linear Programming,缩写为LP） 是运筹学的重要分支之一，在实际中应用得较广泛，
其方法也较成熟，借助计算机，使得计算更方便，应用领 域更广泛和深入。
线性规划通常研究资源的最优利用、设备最佳运行等 问题。例如，当任务或目标确定后，如何统筹兼顾，合理 安排，用最少的资源（如资金、设备、原标材料、人工、 时间等）去完成确定的任务或目标；企业在一定的资源条 件限制下，如何组织安排生产获得最好的经济效益（如产 品量最多 、利润最大）等等。
x3 x3 x3,其中x3, x3 0
(2) 第一个约束条件是≤号，在≤左端 加入松驰变量 (slack variable) x4，
min Z x1 x2 3x3
x4≥0,化为等式； (3)第二个约束条件是≥号，在≥ 左端
2x1 x2 x3 8
x13x1x2
x3 x2
2
3 x3

5
(1) (2) (3)
减去剩余变量(Surplus variable)x5， x1 0、x2 0、x3无符号要求
x5≥0。也称松驰变量
(4)第三个约束条件是≤号且常数项为负数，因此在≤左边加入松 驰变量x6，x6≥0，同时两边乘以－1。
综合起来得到下列标准型
构成。称为三个要素。
其特征是： 1．解决问题的目标函数是多个决策变量的线性函数，通常是 求最大值或 最小值； 2．解决问题的约束条件是一组多个决策变量的线性不等式或 等式。
由此可以抽象出线性规划问题的数学模型。
一般地，假设线性规划数学模型中，有m个约束，有n个决策

1 1
1 0
0 1
0 0
6 2 0 0 1
1 0 0
则
B 0
1
0
的列是线性无关的，即
1
0
0 0 1
p3 0, p4 1 0 0
•
0
p5 0 是线性无关，因此 1
x3
x4
x5
是, 0
p2
1 2
不在这个基中，所以x1,
x2为非基变量。
定义10：使目标函数达到最优值的基本可行解，称为基
本最优值。
• 例4：（SLP)如例3，试找一个基本可行解。
1 1 0
解：B1
1
0
0
是其一个基矩阵.p1,p3, p5是一个基。
6 0 1
则 x1 , x3, x5为基变量。X2, x4为非基变量。令 x2=x4=0. 得x1=2, x3=3, x5=9. 故 x1=(2,0,3,0,9)是原问题的一个基本 可行解，B1为基可行基。
•当 由0连续变动到1时，点z由y沿此直线连续的变动到x，且 因z-y平行x-y，则有：z y (x y) 于是有：
z x (1 ) y
•这说明当 0 1 时，x (1 ) y表示以x.y为端点的直线段
上的所有点，因而它代表以 x.y为端点的直线段。 一般地，如果x.y是n维欧氏空间Rn中的两点，则有如下定义：
• 定义14：设R是Rn中的一个点集，（即R Rn），对于任意 两点x R, y R 以及满足0 1 的实数 ,恒有
x (1 )y R
则称R为凸集。
• 根据以上定义12及13可以看到，凸集的几何意义是：连接凸 集中任意两点的直线段仍在此集合内。
其可行域如上图，可行解（3，1，0，0）T。用x1, x2 表示则为图上点（3，1）。由图可见这不是可行域的 顶点。而我们将证明基本可行解是可行域的顶点。而 在例4中p1,p3线性无关，所以B=(p1,p3)是一个基矩阵， 对应的基本解为（4，0，0，0）T。用坐标x1, x2表示则 为平面上的点（4，0），是上图可行域的顶点。

优点：简单易行，适用于各种线性规划问题，特别是大规模问题。
缺点：对于某些问题，可能存在计算量大、时间长、易陷入局部最优解等问题。
改进方向：研究更高效的算法，如内点法、梯度法等；结合启发式算法，如遗传算法、模拟退火算法等，以寻找更好的解。
章节副标题
线性规划的应用案例
生产计划问题
具体案例：以某企业为例，通过线性规划的方法制定生产计划，实现了生产效率的提高和成本的降低。
最优化问题面临的挑战与未来发展前景
单击此处输入你的正文，请阐述观点
未来发展前景：利用人工智能技术、优化算法改进、拓展应用领域等 最优化问题的实际应用与挑战
最优化问题的实际应用与挑战
单击此处输入你的正文，请阐述观点
挑战：处理大规模问题、考虑各种约束条件、处理不确定性等 最优化与线性规划
最优化与线性规划
单击此处输入你的正文，请阐述观点
线性规划问题定义：在给定约束条件下，寻找一组变量的最优解，使得目标函数为线性函数
单击此处输入你的正文，请阐述观点
单击此处输入你的正文，请阐述观点
最优化与线性规划的应用：生产计划、资源分配、物流优化、金融投资等
单击此处输入你的正文，请阐述观点
Thank you
学院
感谢观看
线性规划问题中的约束条件是等式或不等式约束。
章节副法的基本原理
线性规划问题的定义和求解目标
单纯形表和最优解的确定方法
单纯形法的收敛性和计算效率
单纯形法的基本思路和迭代过程
单纯形法的算法步骤
确定初始基本可行解
确定最优解所在的迭代方向
确定迭代步长
更新基本可行解
单纯形法的优缺点及改进方向
资源分配问题的数学模型和求解方法

其中 向量表示：
给定，变量是
定义标准形 有必要吗?
其中
给定，变量是
标准形的特征：极小化、等式约束、变量非负
第 2 章 线性规划: 基本理论与方法
数学规划基础
LHY-SMSS-BUAA
例4. 化成标准形
等 价 于
最优化问题的等价表述指 两个问题的最优值相等、差一个常数、或者互为相反数， 由其中一个问题的最优解可以得到另一个的最优解。
cT
( x* )T
( 1, 1)
( 0, 0)
( 0, 1) (x1, 0), x1 ≥ 0 ( 1, 0) (0, x2), x2∈[0,1] (-1, -1) 没有 有限 解
解的几何特征
惟一的顶点 一条边 一条边 无(下)界
第 2 章 线性规划: 基本理论与方法
数学规划基础
LHY-SMSS-BUAA
只要有 m 个单位列 e1 , e2 , … , em 即可，次序可以打乱！
◎ 规范形的系数的一种解释
yj B1aj aj y1ja1 y2 ja2 ymjam
规范形第 j 列的系数是用当前基表示 aj 时的系数！
第 2 章 线性规划: 基本理论与方法
数学规划基础
LHY-SMSS-BUAA
第 2 章 线性规划: 基本理论与方法
数学规划基础
LHY-SMSS-BUAA
线性规划问题解的几种情况
提示: 学习单纯形法之前,请务必学习并理解书上 p.19, 例2.2.1.
第 2 章 线性规划: 基本理论与方法
数学规划基础
LHY-SMSS-BUAA
2.2 单纯形法
• 适用形式：标准形(基本可行解等价于极点) • 理论基础：线性规划的基本定理！ • 基本思想：从约束集的某个极点/BFS开始，依次