当前位置：文档之家 › 第二章五LP问题的几何解释

第二章五LP问题的几何解释

  • 格式：ppt
  • 大小：473.50 KB
  • 文档页数：12

下载文档原格式

  / 12

合集下载

2 线性规划

2 线性规划

第一节 线性规划问题及其数学模型
可加性假定：每个决策变量对目标函数和约
束方程的影响是独立于其他变量的，目标函 数值是每个决策变量对目标函数贡献的总和 连续性假定：线性规划问题中的决策变量应 取连续值。 确定性假定：线性规划问题中的所有参数都 是确定的参数。线性规划问题不包含随机因 素。
约 束 方 程
约束条件
变量约束
第一节 线性规划问题及其数学模型
线性规划问题隐含的假定： 比例性假定 可加性假定 连续性假定 确定性假定
比例性假定：决策变量变化引起的目标函数
的改变量和决策变量的改变量成比例，同样， 每个决策变量的变化引起约束方程左端值的 改变量和该变量的改变量成比例
≥0
=
≥0
第一节 线性规划问题及其数学模型
标准型的简缩形式
max Z
c x
j j 1
n
j
s .t
n aij x j bi , i 1,2 , , m j 1 x j 0 , i 1,2 , , m

第一节 线性规划问题及其数学模型
或
松弛变量
a i 1 x 1 a i 2 x 2 a in x n bi
a i 1 x1 a i 2 x 2 a in x n x p bi , x p 0
剩余变量
练习
例:将下列线性规划问题划为标准形式： min Z = x1+3x2
s.t.
6x1+7x28 -x1+3x2-6 x1-x2=3 x10
可行域无界
x1+2x2 10 x2 0 x1
可行域无界
x2
x1 0

第3讲 LP图解法讲解

第3讲 LP图解法讲解
• 3. 若线性规划问题有最优解（不论可行域非空还 是无界），其最优解必可以在某个顶点上面达到。 最优解的个数或者唯一，或者有无穷多个。
关于线性规划问题
⑴线性规划问题的如果有解，则可行域为凸集；
⑵线性规划问题最优解存在，那么唯一最优解一定是 可行域凸集的某个顶点；无穷最优解一定是可行域的 某个边或某个面；
5
x1 0, x2 0
注：x3无约束
作业
• 复习：LP的图解方法与标准型。 • 预习： 单纯形法与对偶理论。 • 作业：习题 3.1；习题 3.2
谢 谢！ 再 见！
max Z c1x1 c2 x2 cn xn a11x1 a12 x2 a1n xn b1
s.t.a21x1 a22x2 a2nxnb2 am1x1 am2 x2 amn xn bm x j 0, j 1,2,, n
s.t.
x1 x1

2x2 4

8

x2

3
x1 0, x2 0
关于可行域与解的性质
• 1. 若可行域非空且有界，则可行域是一个凸多边 形，其顶点个数为有限个；若可行域非空且无界， 其顶点个数也只有有限个。
• 2. 若可行域非空且有界则必有最优解；若可行域 非空且无界，则可能有最优解，也可能无最优解。x1 x2 3源自s.t.x1x1
2
x2
1
x1 0, x2 0
图解法求解（3）
max Z x1 x2
2x1 x2 4
s.t.x1 x2 2

x1

0,
x2

0
图解法求解（4）
max Z 2x1 4x2

04第二章 线性规划的图解法 管理运筹学课件

04第二章 线性规划的图解法 管理运筹学课件
50 40 30 B 20 10
③
10
20
30
40
50
x1
一、目标函数中的系数的灵敏度分析
• -， • 0 ≤ c1≤3750，最优解不变
•当c1 =1500不变时，
• 1000 ≤ c2，最优解不变
二、约束条件中常数项的灵敏度分析
max Z=1500x1+2500x2 s.t. 3x1+2x2 65 ① 2x1+ x2 40 ② 3x2 75 ③ 30 x1,x2 0 ④ 3x1+2x2 66 20 x1=16/3 x2=25 Z=70500 可见资源A每增加一个单 位就可以多获得500元的 利润.
n
i 1,2,… , m j 1,2,… , n
2、矩阵式
…… …… ………………... ……
… … …
3、向量式
…
…
…
…
…
当z值不断增加时，该直线
§2
线性规划的图解法
②
50 40
x2 = -（3/5）x1 +Z/2500
沿着其法线方向向右上方移 动。
唯一最优解
max Z=1500x1+2500x2 ① 30 s.t. 3x1+2x2 65 ① 2x1+ x2 40 ② 3x2 75 ③ x1,x2 0 ④ 20 由图示可知最优点为B （5，25），最优值为70000 10 可行域、可行解 最优解、最优值
线性规划问题解的特点和几种 可能情况：
• 线性规划问题的可行解的集合是凸集
• 凸集的极点（顶点）的个数是有限的 • 最优解如果存在只可能在凸集的极点上取 得，而不可能发生在凸集的内部 • 线性规划问题的解可能是：唯一解、无穷 多最优解、无界解和无可行解(无解)

解析几何第二章第一二节

解析几何第二章第一二节
规定： 0 r ,
0 2,
z
( M ( x, y, z )) M (r, , z )
z .
x
o

r
P(r , )

y
如图，三坐标面分别为
圆柱面； 为常数 半平面； z 为常数 平 面． 柱面坐标与直 角坐标的关系为 x r cos , y r sin , z z.
y
y
作业：P52
3,5,7
§2 平面的方程
1.1平面的参数方程和一般方程 1.2 两平面的相关位置 1.3三平面恰交于一点的条件
M 0 ( x0 , y0 , z 0 ) ，向量 1 ( X 1 ,Y1 , Z1 ) 和向量 ) 2( X 2 ,Y2 , Z 2，其中 1 与 2 不共线， 求由点 M 0 和 1 2 确定的平面 的方程。 z M x , y , z 在平面上 点 2 M M0 M 0 M 与v1 ,v2 共面 e3 e 2 1 v1 // v2 o y e1 M 0 M , v1 , v2共面,则存在唯一的一对实数 x , 使得： M 0 M v1 v2 .
三元二次方程：Ax By Cz Dxy Eyz Fzx Gx Hy Kz L 0 若A B C 0, D E F 0，整理得：
2 2 2
x y z 2b1 x 2b2 y 2b3 z c 0;
2 2 2
( x b1 ) ( y b2 ) ( z b3 ) b1 b2 b3 c .
2. 如果取u, v (a≤u≤b, c≤v≤d)的一切可能 取值，向量 r ( u, v ) x( u, v )e1 y( u, v )e2 z(u, v )e3 的终点 M 总在一个曲面上；反过来， 在这个曲面上的任意点M总对应着以它为 终点的向量, 且该向量可由u, v的值通过 (a≤u≤b, c≤v≤d)完全决定； 那么我们就把上式叫做曲面的向量式参 数方程，其中u, v为参数.

第二章三LP的标准形式(SLP)四LP的解

第二章三LP的标准形式(SLP)四LP的解

n! 基矩阵 的个 数为 C = ： m!(n m)!
2、基解 令非基变量为零，求解由基变量组成的 方程组所得到的解。
如 例 BX B = b 上 ： 1 3 x1 6 增广矩阵 1 3 6 1 - 2 x = 4 1 - 2 4 2
初 变 等 换
1 3 6 0 - 5 - 2
第四节 LP问题的解
一、可行解 满足LP模型的约束条件且满足非负条件的解。 例：
m z = 3x1 + 2x2 ax s.t
x1 + 3x2 ≥ 6 x1 2x2 ≤ 4 x1, x2 ≥ 0
判断 X = 5 1 T，X = 1 3 T，X = 2 1 T （ ） （ ） （ ） 是否 为可行 解？
s.t
′ ′′ ′ x1 (x2 x2 ) + x3 x5 = 4
′ ′′ x1 + (x2 x2 ) + x4 = 7
x1 ≥ 0, x2无非负约束
′ x3 + x6 = 5 ′ ′′ ′ x1, x2, x2, x3, x4, x5, x6 ≥ 0
令 z = 3x1 + 2x2 - x3 , ： ′ ′′ ′ x2 = x2 x2, x3 = x3 1
解： 2 1)基矩阵：B = 1 1 5 2 1 4 B2 = 1- 3 B3 = 2 3 4 1 5 1 B4 = 2 - 3 B5 = 3- 3
=X
(3)
5 3
2)基解：X X
(2)
（） 1
= 180 0 0 -10 X 7 7
(
=X
(5)
)
= (0 0 10 0)（退化解）
x4为松 弛变 (c4 = 0) 量
2、约束方程为≥

五点共圆问题与Clifford链定理

五点共圆问题与Clifford链定理

Ｃａ ｓ ｌｕ 随手在黑板上 画出了五 点共 圆问题的推
ｒ．
江泽 民视察 澳门濠江 中学， 兴致勃 勃地 出了一
道 “ 点共 圆 ’ 五 的几 何题 ．
江泽 民先生随后给数学家和数学教 育家 张
２０ 年底，华东师范大学 张奠宙先生在澳 ０６ 门组织 的高级研讨班邀 请我去做报告， 报告刚 好在濠江 中学举行．濠江 中学校方与我们会面 时介绍 了当年江泽 民主席 的视察．我一下子想
描过来． 还是 由于年代过 于久远， 大英图书馆将 刊有这篇 文章的杂志收在一个 乡间的书库．付
维普资讯
２０ 年第 ９ ０７ 期
数 学教 学
９ 一
Hale Waihona Puke 过的钱被退 了回来， 原文 的扫描和复印件都不能 提供， 原因无可奉告． 因为没有见到原文， 我今天 讲的证 明， 基
确定一个圆， 有四个这样 的圆， 共 则这 四个圆共 点． 此点被称为 Ｗａｌ ｅ ｌ ｃ 点． ａ
们＝ ４
十九世纪下半叶和二十世纪初， 我国正处于 清朝末年， 尚未进入近代数学的研究领域． 将数 学基础研究首先 引入中国的是我国著名 的数学 家， 我国近代数学教育的先驱傅种孙先生． 他在 二十年代翻译 了希尔伯特的 《 几何基础》 倾其 ， 毕生精力在北京师范大学， 师大 附中教书， 引进 国外教材 ， 培训 中学教师． 正因为我国的近代数学研究起步较 晚， 对当
去搜索 Ｃｉｏｄ ｌ ｒ 所有文章的 目录， ｆ 找到了他关于 这个 问题 的 文章 ： ｑ ｅ’ｔｅｒｍ． ＯｎＭｉｕｌ ｈ ｏｅ 遗憾 的 Ｓ 是年代过 于久远， 我们的北京 图书馆， 中科院图
五边形五顶点外的交点共有五个， 证明这五点共

第二讲 线性规划图解法几何意义


单纯形法
单纯形法引例
Max Z = 2x1 + Байду номын сангаасx2 + 0x3 + 0x4 + 0x5 考虑线性规划问题： 考虑线性规划问题： =8 x1 + 2x2 + x3 4x (LP) + x4 =16 1 S.T. 4x2 + x5 =12 x1, x2 , x3, x4 , x5 ≥ 0
例1：用图解法解
m ax z = 2 x1 + 3 x 2 x1 + 2 x 2 ≤ 8 4x ≤ 16 1 4 x 2 ≤ 12 x1 , x 2 ≥ 0
目标值在（4，2）点，达到最大值14
目标函数
max z = 2 x1 + 3x2
2 z x2 = x1 + 3 3 表示一簇平行线
最优解唯一的
最优解无穷多
有无界最优解
无可行解
线性规划图解法（由图解法得到的启示 ） 求解线性规划问题时， 1.求解线性规划问题时，解的情况有：有唯一最优解； 求解线性规划问题时 解的情况有：有唯一最优解； 有无穷多最优解；无界解（ 有无穷多最优解；无界解（即有可行解但无最优 无可行解。 解）；无可行解。 2．若线性规划问题有可行解， ．若线性规划问题有可行解， 则可行域（或可行解集）是凸集。 则可行域（或可行解集）是凸集。 3．若线性规划问题有最优解， ．若线性规划问题有最优解， 一定有最优解在可行域的某个顶点上取得。 则一定有最优解在可行域的某个顶点上取得。 4．解题思路 先找出可行域的任一顶点 ， 计算在顶点 ． 解题思路:先找出可行域的任一顶点 先找出可行域的任一顶点， 处的目标函数值。 处的目标函数值。比较周围相邻顶点的目标函数值是 否比这个大，如果否，则该顶点就是最优解的点， 否比这个大，如果否，则该顶点就是最优解的点，否 则转到比这个点的目标函数值更大的另一顶点， 则转到比这个点的目标函数值更大的另一顶点，重复 上述过程，直到找出最优解。 上述过程，直到找出最优解。

运筹学

运筹学第2章单纯形法 2.1 单纯形法的基本思想该方法简捷、规范，是举世公认的解决LP问，题行之有效单纯形法（Simplex Method）是美国著名运筹学家丹捷格（Dantzig）1947年首先提出的通用方法。

单纯形法不仅是解决LP问题的最基本的算法之一，而且成为解决整数规划和非线性规划某些算法的基础。

2、单纯形法的3种形式——方程组形式（代数形式）、表格形式、矩阵形式3、单纯形法的基本思路——基于LP问题的标准形，先设法找到某个基本可行解（称为初始基本可行解）；开始实施从这个基本可行解向另一个基本可行解的转换，要求这种转换不仅容易实现，而且能改善（至少保持）目标函数值；继续寻找更优的基本可行解，进一步改进目标函数值。

当某一个基本可行解不能再改善时，该解就是最优解。

（或者是出现无可行解、无最优解、无穷多最优解的情况）2.1.1 方程组形式的单纯形法例1 一个企业需要同一种原材料生产甲、乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，获得的利润也不相同（如下表）。

请问，该企业应如何安排生产计划，才能使获得的利润达到最大？解：该问题的LP模型为：将该问题的LP模型化为标准形⎪⎩⎪⎨⎧≥≤+≤++=,1202410032..4621212121xxxxxxt sxxzm ax函数约束的增广矩阵为：很显然 R （A ） = R （A ，b ）= 2 < 5，即该方程组有无穷多组解。

系数矩阵为：决策变量向量为：选取 为基，则 为基变量， 为非基变量令非基变量 ，则可以得到一基本 可行解为： 下面的计算都是以它为初始点逐次实施转换，故将其称为初始基本可行解。

此时，Z=0，其经济含义为：该企业没 有安排甲、乙两种产品的生产，当然也就没有利润可言。

条典☐ 初始基本可行解所对应的可行基是一个m 阶的单位阵； ☐ 目标函数表达式中所有的基变量的系数全部为0。

☐ 这是单纯形法所必需的！！！ ☐ 分析目标函数表达式☐ 非基变量的系数都是正数，若将它们转换为基变量，目标函数值则就会可能增加。

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

C 100 50
B(30,80) l2 l1 150 x1
O
50
A100
结论：以z为参数的直线族与可行域某一条边平行， 最终重合，则该LP存在多个解。
2、LP问题无可行解
ax 例： m z = 10x1 +12x2
x2 150
s.t 2x1 + 3x2 ≤ 300 l1 100 5x1 + 6x2 ≥ 900 l2 x1, x2 ≥ 0
（） 1 （） 2
则称K为凸集。
判断：圆、五角星是否为凸集。
可行域的性质
●线性规划的可行域是凸集 ●线性规划的最优解在极点上
凸集
极点
凸集
不是凸集
二、几种特殊情况 1、LP存在多个解
x2 150
Hale Waihona Puke 例： m z = 10x1 +15x2 ax s.t 2x1 + 3x2 ≤ 300 l1 2x1 +1.5x2 ≤ 180 l2 x1, x2 ≥ 0
小结
1、可行域为封闭的有界区域
x
2
x
2
C
z
C
z B
x
1
x
1
唯一最优解
多个最优解
2、可行域为非封闭的无界区域
x2 x2 x2
z
z
Z
x1
x1
x1
唯一最优解
多个最优解
无界解
3、可行域为空集
x2
空集 x1
无可行解
x2 Min z=2x1+3x2 s.t. x1+ x2≤4 （1） 2x1+5x2 ≥ 10 （2） -x1+ x2 ≤ 1 （3） x1，x2 ≥0 约束条件（1）、（2）、 （3）的松弛变量或剩余 变量分别为x3、x4、x5
150
z = 500 10x1 +12x2 = 500
z =1000 10x1 +12x2 =1000
最优解
l1 : x1 = 0, x2 =100 x1 =150, x2 = 0 l2 : x1 = 0, x2 =120 x1 = 90, x2 = 0
可行域
C 100
B (30,80)
50
z=1260
O
50
z=500
A 100
z=1000
150
x1 l1
l2
结论：若LP问题存在最优解，则必在 可行域的某个极点(角点)上找到。
极点——基可行解
前提：可行域是个凸集。 凸集：设K是n维欧氏空间的一点集，若任 (1) ( 2) 意两点 X ∈K, X ∈K的所有点
αX + 1α）X ∈K， ≤ α ≤ 1), （ (0
4 I
x5=0
3 G D 2
x1=0
H
x3=0
1E F -1
x2=0
O
1
2
C x =0 4 A 4 3
B 5 x1
Z=9 Z=6
以上问题中，有 3 个基变量， 2 个非基变量； 基解为 A B C D E F G H I O ；基可行解为 C D H； 最优解为 D 。
思考题
已 LP问 知 题如 ： 下 z = c1x1 + c2 x2 m ax .t s 5x2 ≤ 15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1, x2 ≥ 0 讨 c1, c2的 论 值如 变化 该LP 可 域 每个 点依 何 ， 行 的 角 次 使 标 数 到 目 函 达 最优 。
50 O 50 l2 100 l1 150 x1
结论：若LP的可行域为空集，则该LP问题 无可行解。
3、LP问题存在无界解
例： m z = 3x1 + 4x2 ax s.t x1 ≤ 3 x1, x2 ≥ 0 l1 x1 x2 ≤ 1 l2
x2
3 2 1
z
l1
l2
C B
2 3 4
O
A1
x1
判断：若LP的可行域无界，则该LP存在 无界解。 错！
第五节 LP问题的几何解释 一、二个决策变量LP问题的图解法
例 m z = 10x1 +12x2 ： ax s.t 2x1 + 3x2 ≤ 300 l1 2x1 +1.5x2 ≤ 180 l2 x1, x2 ≥ 0
例： m z = 10x1 +12x2 ax s.t 2x1 + 3x2 ≤ 300 l1 2x1 +1.5x2 ≤ 180 l2 x2 x1, x2 ≥ 0