当前位置：文档之家 › 第 1.2 节 线性规划问题的几何意义

第 1.2 节 线性规划问题的几何意义

  • 格式：ppt
  • 大小：245.00 KB
  • 文档页数：10

下载文档原格式

  / 10

合集下载

第1.2节 线性规划问题的图解法

第1.2节 线性规划问题的图解法

x1 20 * x 2 100
* * z 1240
27
2 规划问题求解的几种可能结果
2）无穷多最优解
max z 12 x1 8 x2 2 x1 x2 160 1 1 x1 x2 40 3 3 3 x1 2 x2 260 x1 , x2 0
max z 12 x1 10 x2 2 x1 x2 160 1 1 x x2 40 1 3 3 3 x1 2 x2 260 x1 , x2 0
23
x2 160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 0
max z 12 x1 10 x2 2 x1 x2 160 1 1 x1 x2 40 3 3 3 x1 2 x2 260 x1 , x2 0
工序 花瓶种类 占用材料 （盎司） 艺术加工 （小时） 储存空间 （一单位） 利润值 （元）
大花瓶
1/3x1+1/3x2=40 (60,40)
x1
22
160 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10 图1 花瓶问题的图解法
图解法的基本步骤：
（4）确定最优解。最优解是可行域中使目标
函数值达到最优的点，当目标函数直线由原点 开始沿法线方向向右上方移动时，z 值开始增 大，一直移到目标函数直线与可行域相切时为 止，切点即为最优解。
18
图解法的基本步骤：
（3）作出目标函数。由于
z 是一个待求的目 标函数值，所以目标函数常用一组平行虚线表 示，离坐标原点越远的虚线表示的目标函数值 越大。

最优化方法-线性规划

最优化方法-线性规划

引言
对线性规划贡献最大的是美国数学家G.B.Dantig(丹捷格)，他 在1947年提出了求解线性规划的单纯形法（Simple Method），并同时给出了许多很有价值的理论，为线性规划 奠定了理论基础。在1953年，丹捷格又提出了改进单纯形法， 1954年Lemke(兰母凯)提出了对偶单纯形法（dual simplex method）。 在1976年， R. G. Bland 提出避免出现循环的方法后，使线 性规划的理论更加完善。但在1972年，V. Klee和G .Minmty 构造了一个例子，发现单纯形法的迭代次数是指数次运算，不 是好方法——并不是多项式算法（多项式算法被认为是好算 法），这对单纯形法提出了挑战。
B2
B3
70
50 60
A2
60 110 160
[解] 设xij 表示 Ai运往Bj的运量（万块） minS=50x11+60x12+70x13+60x21+110x22+160x23 S.t. x11+x12+x13=23 x21+x22+x23=27 x11+x21=17 x12+x22=18 x13+x23=15 xij≥0, i=1,2、j=1,2,3
2.线性规划问题的几何意义
2.1基本概念 凸集：设k为n维欧氏空间的一点集，任取X,Y∈K,若 连接X,Y的线段仍属于K,则称K为凸集。即任取α ,0<α <1 α X+(1-α )Y∈K 称K为凸集。 顶点（极点）：设K是凸集，X∈K,若X不能用不同的两
点 X(1) ∈K,X2) ∈K 的线性组合表示为 X=α X(1)+(1-α )X(2) (0<α <1) 则称X为极点。

第一章_线性规划

第一章_线性规划

第 一 节 线性规划问题及其数学模型
一、线性规划问题的数学模型
线性规划问题主要解决以下两类问题： 1、任务确定后，如何统筹安排，做到应用尽量少的人 力和物力资源来完成任务； 2、在一定量的人力、物力资源的条件下，如何安排、 使用他们，使完成的任务最多。
在生产管理和经济活动中，经常会遇到线性规划问 题，如何利用线性规划的方法来进行分析，下面举例 来加以说明。
表1－2
成分
产品来源
分析：很明显，该厂可以有多种不同的方案从A，B 两处采购原油，但最优方案应是使购买成本最小的一 个，即在满足供应合同单位的前提下，使成本最小的 一个采购方案。
解：设分别表示从A，B两处采购的原油量（单位：万 吨），建立的数学模型为：
m in S 200 x1 290 x2
3. 若存在无非负要求的变量。即有某一个变 量 xj 取正值或负值都可以。这时为了满足标准型 对变量的非负要求，可令 xj = xjˊ- xj〞, 其中： xjˊ、 xj〞 0 ，由于xjˊ可能大于也可能小于xj〞，故 xj 可以为正也可以为负。
上述的标准型具有如下特点： （1）目标函数求最大值； （2）所求的变量都要求是非负的； （3）所有的约束条件都是等式； （4）常数项非负。 综合以上的讨论可以说明任何形式的线
max Z x1 2x2 3x4 3x5 0x6 0x7
x1 x2 x4 x5 x6 7
x13x1x2
x4 x2
x5 2x4
x7 2 2x5 5
x1, x2, x4, , x7 0
第二节 线性规划问题的图解法及几何意义
例1－1：（计划安排问题）某工厂在计划期内安排 生产Ⅰ、Ⅱ两种产品，已知生产单位产品所占用的 设备A、B的台时、原材料的消耗及两种产品每件 可获利润见表所示：

线性规划问题的图解法

线性规划问题的图解法
bm 0 1 am ,m 1 amn m
j
0 0 j c j c i a ij
bi 其中： i a kj 0 a kj
单纯形法的计算步骤
例1.8 用单纯形法求下列线性规划的最优解
max Z 3 x1 4 x 2 2 x1 x 2 40 x1 3 x 2 30 x , x 0 1 2
A
0
E
| 5
| 6
| 7
| 8
| 9
x1
图解法
9— 8—
目标函数 Max Z = 2x1 + 3x2
约束条件 x1 + 2x2 8
4x1 16 4x2 12 x1、 x2 0
x2
7—
6— 5—
4x1 16
C 4 x2 16
4 —B
3— 2— 1—
D
| 1 | 2 | 3 | 4
4—
3— 2— 1— 0
x1
图解法
9— 8—
目标函数 Max Z = 2x1 + 3x2
约束条件 x1 + 2x2 8
4x1 16 4x2 12 x1、 x2 0
x2
7—
6— 5—
4x1 16 4 x2 12 x1 + 2x2 8
4—
3— 2— 1— 0
可行域
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
x2
X1 + 1.9X2 = 11.4 (≤)
8=5X1+4X2 此点是唯一最优解 （ 0， 2）
D
43=5X1+4X2
可行域

线性规划问题的几何意义

线性规划问题的几何意义

第2节 结束
• 实心圆，实心球体，实心立方体等都是凸集， 圆环不是凸集。从直观上讲，凸集没有凹入 部分，其内部没有空洞。图1-7中的(a)(b)是凸 集，(c)不是凸集。 • 图1-2中的阴影部分 是凸集。
• 任何两个凸集的交集是凸集，见图1-7(d)
2. 凸组合
• 设 X(1) ， X(2) ， … ， X(k) 是 n 维欧氏空间 E 中的 k 个点。 若存在μ1，μ2，…，μk，且0≤μi≤1, i=1,2,…，k;
引理2 若K是有界凸集，则任何一点X∈K 可表示为K的顶点的凸组合。
• 本引理证明从略，用以下例子说明这引理。
• 例5 设X是三角形中任意一点，X(1),X(2)和X(3) 是三角形的三个顶点，试用三个顶点的坐标 表示X(见图1-8)
解 任选一顶点X(2)，做一条连线XX(2)；并延长交于 X(1)、X(3)连接线上一点X′。因X′是X(1)、X(3)连线 上一点，故可用X(1)、X(3)线性组合表示为
运筹学
（第二版）
刁在筠等 编
第1章 线性规划 与单纯形 法
第2 节 线性规划问 题的几何意 义
高等教育出版社
第1章 线性规划与单纯形法
第2节线性规划问题的几何意义
• 2.1 基本概念 • 2.2 几个定理
2.1 基本概念
1. 凸集 2. 凸组合 3. 顶点
1.凸集
• 设K是n维欧氏空间的一点集，若任意两点X(1)∈K， X(2)∈K 的 连 线 上 的 所 有 点 αX(1)+(1-α)X(2)∈K ， (0≤α≤1)；则称K为凸集。 • 图1-7
• 根据引理 1 ，若 X 不是基可行解，则其正分量 所对应的系数列向量 P1，P2，… ，Pm线性相关， 即存在一组不全为零的数α i,i=1,2,…,m使得

线性规划问题的几何意义

线性规划问题的几何意义

重要结论
根据以上讨论，可以得到以下结论： 线性规划问题的可行域是凸集（定理3.1）；凸集的 每个顶点对应一个基可行解（定理3.2），基可行解个数 是有限的，当然凸集的顶点也是有限的；若线性规划有最 优解，必在可行域某顶点上达到（定理3.3），亦即在有 限个基可行解中间存在最优解。因此，我们可以在有限个 基可行解中去找最优解。这就是下节将介绍的单纯形法的 理论依据，该方法就是一种在基可行解中搜索最优解的算 法。
因此，对于j=k+1,k+2,…,n，应有 k 1 2 0 ，由于P1,P2,…,Pk线性无关， 并且 pj xj xj 故 xj1 xj2 ,j=1,2,…,k.这就得到了x（1）=x（2）之矛盾。

2 1 xj xj 0







i1
i1
由X（0）的任意性,知线性规划在顶点X（m）处达到最优。

显然θ>0。 取x（1）=(x1+θα 1,x2+θα 2,…,xk+θα k,0,…,0)T x（2）=(x1-θα 1,x2-θα 2,…,xk-θα k,0,…,0)T
易于验证x（1）∈D，x（2） ∈D，x（1）≠x（2）且
1 2 1 1 X X X ，此与X是D的顶点矛盾，因而X是基可行解。 2 2 充分性：←设X是问题的基可行解，不妨设x1＞0,x2＞ 0,…,xk＞0, xk+1=…=xn=0（k≤m），于是P1,P2,…,Pk必线 性无关。若X不是D的顶点，则存在x（1）∈D，x（2） ∈D， x（1）≠x（2）及α ∈（０，１），有

1.2线性规划问题的图解法及几何意义


2
①
可行域
1
Z增大方向
-1
0
1
②
2
3 x1
图解法（总结三个特点）
从图解法可以看出一般情况下： 从图解法可以看出一般情况下： （1）具有两个变量的线性规划问题的可行域是凸多边形。 具有两个变量的线性规划问题的可行域是凸多边形。 凸多边形 顶点得到 （2）若线性规划存在最优解，它一定在可行域的某个顶点得到。 若线性规划存在最优解，它一定在可行域的某个顶点得到。 （3）若在两个顶点上同时得到最优解，则在这两点的连线上的任 若在两个顶点上同时得到最优解， 意一点都是最优解； 意一点都是最优解； 虽然图解法只能求解包含两个变量的问题，作为算法， 虽然图解法只能求解包含两个变量的问题，作为算法，没有 太大价值，但是上述结论却非常有意义。它将搜索最优解的范围 太大价值，但是上述结论却非常有意义。 从可行域的无穷多个点缩小到有限几个顶点。 从可行域的无穷多个点缩小到有限几个顶点。这就开启了人们的 思路。 思路。而后面我们要介绍的求解多维线性规划的单纯形法就是在 此结论的基础上推广得到的。 此结论的基础上推广得到的。
无可行域的情况将会出现， 这时不存在可行解， 时 ， 无可行域的情况将会出现 ， 这时不存在可行解 ， 即 该线性规划问题无解。 该线性规划问题无解。
无有限最优解（可行域无界，目标值不收敛） 无有限最优解（可行域无界，目标值不收敛）：
线性规划问题的可行域无界， 线性规划问题的可行域无界 ， 是指最大化问题中的目标 函数值可以无限增大， 函数值可以无限增大 ， 或最小化问题中的目标函数值可 以无限减少。 以无限减少。
1.2 线性规划问题的图解法 及几何意义
如何求解线性规划模型是本章讨论的中心问题。 如何求解线性规划模型是本章讨论的中心问题。首先介绍 只有两个决策变量的线性规划的图解法， 只有两个决策变量的线性规划的图解法，该方法能够对线性规 划的解法从几何直观上给我们以启迪。 划的解法从几何直观上给我们以启迪。 对于两个决策变量的每一组取值， 对于两个决策变量的每一组取值，都可以看作平面直角坐标 系中一个点的坐标，因此， 系中一个点的坐标，因此，我们可以把满足约束条件的点在平 面直角坐标系中表示出来。 面直角坐标系中表示出来。

线性规划几何意义

目标函数几何意义在变化线性规划是高中数学的重要内容之一，它是本质是“以形助数”即主要利用形的直观性来解决问题．由于目标函数在不断地变呈动，现出多样性和隐蔽性，所以我们要认真研究目标函数的几何意义，使目标函数具体化和明朗化．下面举例说明：一、目标距离化．例1．已知实数x，y满足,则的最大值是分析，目标函数的几何意义是表示可行域内的点到点（1，1）的距离的平方，画出可行域可求得解：如图，作出可行域，则可知行域内点（4，1）到可点（1，1）的距离最大，从图形中可只是3，故．例2．已知实数满足，求的最大值．分析：这个目标函数就显得有点“隐蔽”了，注意到目标函数有个绝对值符号，联想到点到直线的距离公式的结构特点，那么就可顺利解决了．，也是说表示为可行域内的点到直线距离的倍．解：作出可行域，（如上图）可知可行域内的点（7，9）到直线的距离最大，所以二、目标角度化．已知为直角坐标系原点，的坐标均满足不等式组，则的最小值等于．分析：作出相应的可行域，可知越大，则越小，所以可知在（1，7）（4，3）此时与原点O的张角最大解：画出可行域，不失一般性，不妨设P（1，7），Q（4，3）；则，，则，所以．三、目标斜率化．例4．已知变量满足约束条件，则的取值范围是_____.分析，观察的结构特征，令人想到平面内的两点间的斜率公式，可得表示可行域内的点与原点之间的斜率，结个可行域可得其取值范围是，具体的过程留给聪明的读者．四、目标投影化．例5．已知点（O为原点）的最大值为．分析：这个目标函数更为隐蔽了，表示的是是方向上的投影．解：作出可行域，则可知P（5，2），则=（5，2），则在上的投影是PQ，可看作点P到直线是距离五、目标面积化．例6已知实数满足，求的最大值．分析：表示可行域内的点（正好在第一象限）到两坐标轴距离的乘积的两倍，即过该点作两坐标轴的垂线，长线段与两坐标轴所围成的面积的2倍，可知当时取得最大值，最大值是同学们应该知道目标函数是直线的截距的这种类型的基础上，还要知道距离、投影、斜率、角度、面积等几种常见的形式．这样我们的在解决线性规划问题上才能心中有“形”．下面提供部分习题请同学们完成．（1）若函数是定义在上的函数，则函数的值域是（）A．B．C．D．（2）约束条件，目标函数的最小值是（3）已知（是坐标原点）的最大值为答案：（1）D （2）0 （3）5。

线性规划图解法几何意义


4.基: 设系数矩阵Am×n(n>m)其秩为m,B是矩阵A中
的一个m×m阶的满秩子矩阵,称B是线性规划问
题的一个基。
一. 线性规划问题解的概念（2）
不妨设基为
a11 ... a1m
B ... .... .....

a
m1
...
amm

=(P1,P2,...,Pm)
基向量： B中的每一列向量Pj(j=1,2,...m)称为基向量
AX=b的解 若非基变量为0
B是A的m阶子矩阵 若|B|0
基解 若基变量取非负
基B 当B-1b0
基可行解 若对应目标函数 值最优
可行基B
基最优解
最优基B
三. 线性规划问题解的关系图（2） 非可行解
可
基
行
可
基
解
行
解
解
基 可最 行优 基基
第2节 线性规划问题的几何意义
• 2.1 基本概念 • 2.2 几个定理
凸组合:设 X (1) , X (2) ,..., X (k) 是n维欧氏空间中的k个点
X 1 X (1) 2 X (2) ... k X (k ) 1 i 0, i 1
则称X是 X (1) , X (2) ,..., X (k) 的凸组合
凸集的概念：
凸集
顶点
一.凸集与顶点 凸集: 如果集合K中任意两个点X(1),X(2),其连线上的所
有点也都是集合K中的点,则称集合K为凸集. 或K={X|X=αX(1)+(1-α)X(2), X(1)K,X(2)K,0≤α≤1}
定理: D＝｛ x∈Rn| Ax=b,x≥0}是凸集
定理: 有限个凸集的交集还是凸集

§1-2 线性规划问题的几何意义


b, x 0,
(1) j
j 1, 2,, n j 1, 2,, n
7
Pj x (2) b, x (2) 0, j j
Operational Research
定理1（续）
令X=(x1, x2, …, xn)T为X (1), X(2)连线上的任意一点， 即 X=X(1)+(1-)X(2) (0≤≤1) X的每一个分量是
9
Operational Research
引理1 引理 1 线性规划问题的可行解X=(x1, x2, …, xn)T
为基可行解的充要条件是X的正分量所对应的系数列向
量是线性独立的。 证 必要性：由基可行解的定义可知。
充分性：若向量P1, P2, …, Pk线性独立，则必有 k≤m； 当k=m时，它们恰构成一个基，从而X=(x1, x2, …, xk, 0, …, 0)为相应的基可行解。当k＜m时，则一定 可以从其余的列向量中取出m-k个与P1, P2, …, Pk构成 最大的线性独立向量组，其对应的解恰为X，所以根据 定义它是基可行解。
现取
X (1) [( x1 1 ), ( x2 2 ) ( xm m ), 0,, 0] X (2) [( x1 1 ), ( x2 2 ) ( xm m ), 0,, 0]
由X(1), X(2)可以得到
1 (1) 1 (2) X X X ，即X是 2 2
是顶点，且目标函数在X(0)处达到最优z*=CX(0) （标准
型是z=max z）。 因X(0)不是顶点，所以它可以用D的顶点线性表示 为
X (0) i xi(i ) , i 0,
i 1 k

i 1
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

• 定理1 行域 若线性规划问题存在可行域，则其可
DX Pj x j b, x j 0 j 1
n
பைடு நூலகம்
是凸集。 证明：
定理2 线性规划问题的基可行解 X 对应于可行域 D 的顶点。
引理1 线性规划问题的可行解 X = (x1, x2,…，xn)T 为基可行解的充要条件是 X 的正分量所对应的系数列向量是线 性独立的。
定理 3 若可行域有界，线性规划问题的目 标函数一定可以在其可行域的顶点上达到 最优。
引理2 若 K 是有界凸集，则任何一点 X∈K 可表示为 K 的顶点的凸组合。
• 例5 设 X 是三角形中任意一点，X(1), X(2)和 X(3)是三角形的三个顶点，试用三个顶点的坐 标表示 X (见图1-8)
第1章 线性规划与单纯形法
第2节线性规划问题的几何意义
1.凸集
• 设 K 是 n 维欧氏空间的一点集，若任意两点 X(1)∈K， X(2)∈K 的连线上的所有点 X(1) + (1 )X(2)∈K，(0≤≤1)； 则称 K 为凸集。
•
图1-7
• 实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。 从直观上讲，凸集没有凹入部分，其内部没有空洞。图1-7中 的(a)(b)是凸集，(c)不是凸集。
• 结论
–线性规划问题的所有可行解构成的集合是凸集， 也可能为无界域，它们有有限个顶点，线性规划 问题的每个基可行解对应可行域的一个顶点；若 线性规划问题有最优解，必在某顶点上得到。虽 然顶点数目是有限的(它不大于个)，若采用“枚 举法”找所有基可行解，然后一一比较，最终可 能找到最优解。但当 n, m 较大时，这种办法是 行不通的，所以要继续讨论，如何有效地找到最 优解，有多种方法，这里只介绍单纯形法。
3. 顶点
• 设 K 是 凸 集 ， X∈K ； 若 X 不 能 用 不 同 的 两 点 X(1)∈K 和 X(2)∈K 的线性组合表示为 • X = X(1)+(1-)X(2)，(0＜＜1) • 则称 X 为 K 的一个顶点(或极点)。 • 图中0，Q1,2,3,4都是顶点。
2.2 几个定理
• 任何两个凸集的交集是凸集。
2. 凸组合
• 设 X(1)，X(2)，…，X(k) 是 n 维欧氏空间 E 中的 k 个点。 若存在 1，2，…，k，且0≤i≤1, i=1,2,…，k;

i 1
k
i
1
• 使 X = 1X(1) + 2X(2) + … + kX(k) • 则称 X 为 X(1)，X(2)，…，X(k) 的凸组合。(当 0＜i＜ 1 时，称为严格凸组合).