Chapter01.线性规划及单纯形法

17
图解法的其他情形 –无可行解
求下面规划问题的最优解。
min z 2 x1 x 2
x1 x2 1
s.t.
x
1
3x2
4
x1 0 , x 2 0
x2
B(0,1)
x1 3x2 -4 x 1x
2 1
O A(1,0)
x1
2020/7/9
18
§3 单纯形基本原理 – 预备知识
凸集 定义1.1：如果集合C中任意两点x(1)，x(2)，其连线上的所 有点也在集合C中，即对任何x(1)C， x(2)C，0<<1，都有 x(1)+(1) x(2) C，则称C为凸集。
0501 5 0103 0103
x B (3 ,3 ,4 )T ,x (3 ,3 ,0 ,4 ,0 )T
2020/7/9
12
§2 图解法求最优解
什么时候用图解法？ (LP)模型仅含两个决策变量。
求解方法和根据：
① 根据约束画出求解区域，一般为第一象限的凸多边形 (有界或无界)，标记出顶点坐标；
第1章 线性规划及单纯形法
姚明臣 2019年3月
中国科技网到中国电信网络线路使用分析报告
reserved
All rights
本次课程要求掌握的内容
会建立简单的线性规划问题的数学模型； 理解并记忆线性规划模型的各种形式；
1. 分量形式 2. 向量形式 3. 矩阵形式
会将一般线性规划模型化成标准型； 有关线性规划问题解的若干重要概念
可行解、最优解、基、基(本)解、基可行解等。 熟练掌握含两个决策变量问题的图解法； 1. 凸集的相关概念和单纯形法若干基本定理。
2020/7/9
2
§1 线性问题的数学模型
问题的提出
例1. 用一块边长为a的正方形 铁皮做一个容器，应如何裁 剪，才能使做成容器的容积 最大？
解：利用高等数学的知识
V=(a - 2x)2 x
2020/7/9
4
线性规划的数学模型
问题的提出 – 例子之三(合理 下料问题) 现有一批10m长的贵重钢筋， 需要截取3m和4m长的钢筋各 50根，试问如何截取，才能使 原料最省？
问题分析：
① 先确定截取方案 ② 建立数学规划模型
截取方案 I II III 3m钢筋 2 3 0 4m钢筋 1 0 2 废料长 0m 1m 2m
问题：例一中的问题是否为线性规划模型？
2020/7/9
6
线性规划问题数学模型的一般形式
关于幻灯片中的数学符号：
➢ 小写斜体字母表示实数，如a,b,c,x,x1,y,z等
➢ 小写黑体字母表示向量，如x,y,z等
➢ 大写黑体字母表示矩阵，如 A, B,C等
线性规划(LP)数学模型的一般形式
max z c (1 x 1 m c 2 x 2 i n )c nx n
n
max z c j x j j 1
s
.t.
n j 1
aij
x
j
bi
x
j
0
(i 1,2,, m) ( j 1,2,, n)
2020/7/9
9
(LP)一般形式向标准形式的转化
(LP)一般形式向标准形转化的情况：
① 目标函数是求极小值； ② 约束条件为不等式“”的情形（松弛变量，例2）； ③ 约束条件为不等式“” 的情形（剩余变量，例3）； ④ 取值无约束的变量； ⑤ 某个变量 xj 0
引理1.2 En中的点集为凸集的充要条件是对任何正整数m, 中任意m 个点x(1), x(2) ,, x(m)的凸组合x都在内。
充分性：利用定义证凸集；必要性：数学归纳法+凸集定义。
2020/7/9
22
单纯形法的基本定理 - 顶点表示定理
引理1.3 设(LP)问题的可行域C有界，则任何可行解xC都可以表示成 C的顶点的凸组合。 (证明略，图解示意，考虑x的三种情况：顶点、边界点和内点)
x(1)
x
x(2)
x'
x(3)
解：连接x(1)和x交x(2) x(3) 于x，因三角形是凸集, x = x(1) + (1 ) x (1) x = x(2) + (1 ) x(3) (2) 0< , <1 (2)代入(1)得： x = x(1) + (1 ) x(2) + (1 ) (1 ) x(3) ， 验证组合系数之和为1即可。
基(本)可行解 同时是可行解的基解。
可行基
2020/7/9
11
利用初等变换求基可行解
例4. 教材14页，列出(LP)问题的全部基，基解、基可行解并指 出最优解。
问题: I) 如何判断一个解是基可行解；
II）表1-1中为何少了两行？ 利用p1,p2, p4 求基解的过程
2201 2 2006 1003 B (p 1 p 2 p 4 b )40116 40116 0014
从pk+1,p2, ,pn中必可以选出mk列，和p1,p2, ,pk共同组成一个基，
这样一定可以办到(为什么？) ，其对应基解恰为x。这样的x称为退化 的基可行解。
2020/7/9
21
单纯形法的基本定理 – 凸组合性质
凸组合 定义1.3 设x(1), x(2) ,, x(m)是En中的m个向量， 而1, 2, , m 是满足1+ 2+ + m=1，i0的m个实数，称向量x = 1x(1)+ 2 x(2) + + m x(m)为x(1), x(2) ,, x(m)的凸组合。 问题：凸组合和普通线性组合有什么区别？
② 求目标函数的梯度：设目标函数是 z=c1x1+c2x2，则 n = grad z = (c1,c2) 为等值线c1x1+c2x2= h的法线方向，沿n的方向 函数值增加的最快，沿-n方向函数值减少的最快。
③ 移动等值线 c1x1+c2x2= h 在区域顶点或边界达到最大最小值。
书中的方法是把目标函数z当做参数处理。
引理1.1 (LP)问题可行解x为基可行解的充要条件是x的非零 分量所对应的系数列向量是线性独立的。 利用基可行解的定义证明。
定理1.2 (LP)问题的可行解x是可行域(凸集)顶点的充要条件 是x为一个基可行解。 利用分块矩阵的形式，结合引理1.1利用反证法 (较长,最后证)。
2020/7/9
20
引理1.1的证明
v(4)
v(5)
x
v(6) y(1) v(1)
d y(2)
x = 1v(1) + 0v(2) + 3v(3)+ 4v(4) + 0v(5)+ 6v(6) v(3)
v(2)
2020/7/9
23
一个顶点表示的例子
例 设x是三角形中任意一点， x(1), x(2) , x(3) 是三角形的三个顶点，试将x 表示为x(1), x(2) 和x(3) 的凸组合。
引理1.1 (LP)问题可行解x为基可行解的充要条件是x的非零 分量所对应的系数列向量是线性独立的。
证明：充分性 设x为一可行解，不妨设其非零分量(正分量)为前k个， 即x = (x1 , x2 , , xk , 0,,0)T， xi > 0 (1 i k), 若x是基可行解，则必 有 k m(为什么？)，由可行基的定义，部分向量组 p1,p2, ,pk 必线性 无关。 必要性 若x为可行解(同上假设)，其对应系数列向量 p1,p2, ,pk 线性 独立(无关)，同样 k m (为什么？)。 (1)、若k = m, 则 p1,p2, ,pk 刚好构成一个基矩阵，而x = (x1 , x2 , , xk , 0,,0)T为对应基可行解。 (2)、若k < m ，则可以利用p1,p2, ,pk构造一个基，因为rank(A) = m,
顶点 定义1.2：如果凸集C中不存在任何两个不同的点x(1)、x(2) ， 使x成为x(1)和x(2)连线上的某个点，这样的x称为C的顶点。 （问题：书上的数学描述是否妥当？）
2020/7/9
19
单纯形法的基本定理
定理1.1 若(LP)问题有可行解，则问题的可行域为凸集。 利用凸集的定义，结合LP的矩阵形式[P8]证明。
max z 3 x 1 3 x 2
2 x 1 2 x 2 12
s.t.
4
x1
16 5 x 2 15
x 1 0 , x 2 0
x2
x1 = 4
D
C(3,3)
x2 = 3
B(4,2)
O
A
2x1 + 2x2
x1 12
问题2：这个最优解如何表示？
2020/7/9
16
图解法的其他情形 – 无界解(无最优解)
2020/7/9
7
线性规划数学模型向量和矩阵形式
(LP)向量形式
max(min) z cx
n
s .t.
p
j 1
jxj
(, )b
x 0
(LP)矩阵形式
max(min) z cx Ax (, )b
s.t.x 0
c (c1 , c2 , , cn )
x1
a1 j
b1
x
x2 xn
min z x1 2x2
s.t.2x1x1 3x2 2x3
50 50
x1 , x2 , x3
0
问题：模型是否有别的形式？
2020/7/9
5
线性规划问题数学模型的定义
线性规划模型组成的三要素：
① 决策变量 ② 目标函数 ③ 约束条件
定义1 在线性规划数学模型中，如果决策变量为可控的连 续变量，目标函数和约束条件都是线性的，称这类模型为 线性规划问题的数学模型。