9299.net
大学生考试网 让学习变简单
当前位置:首页 >> 工学 >>

第二章2[1].2.1 线性规划问题的图解法_图文

第二章2[1].2.1  线性规划问题的图解法_图文

一、 线性规划的图解法

---解的几何表示

1.什麽是图解法?
线性规划的图解法就是用几何作图 的方法分析并求出其最优解的过程。 求解的思路是:先将约束条件加以 图解,求得满足约束条件和非负条件的 解的集合(即可行域),然后结合目标 函数的要求从可行域中找出最优解。

2. 图解法举例 例2-1 max Z ? 2 x1 ? 3x2 ? x1 ? 2 x2 ≤ 8 ?4 x ≤ 16 ? 1 ? ?4 x2 ≤ 12 ? x1 , x2 ≥ 0 ? 实施图解法,以求出最优生产计 划(最优解), 给出最优值。

由于线性规划模型中只有两个决策 变量,因此只需建立平面直角坐标系就 可以进行图解了。
第一步:建立平面直角坐标系 标出坐标原点, 坐标轴的指向和单位 长度。用x1轴表示产品A的产量,用x2 轴表示产品B的产量。 第二步:对约束条件加以图解。 第三步:画出目标函数等值线,结合目标函数 的要求求出最优解:最优生产方案。

第四步:最优解带入目标函数,得出最优值。

约束条件的图解:
每一个约束不等式在平面直角坐标系中 都代表一个半平面,只要先画出该半平面的 边界,然后确定是哪个半平面。 怎麽画边界

?

怎麽确定 半平面

以第一个约束条件: x1 ? 2 x2 ≤ 8 为例, 说明图解过程。

x1 ? 2 x2 ≤ 8 代表一个半平面
其边界: x1+2 x2 =8
x2

x1+2 x2 =8 及x1,x2 ≥0 △ AOB 点A、B 连线AB △A0B

B
Q4

3 2 1

x1 ? 2x2 ? 8
A
1 2 x1

0

3

4

5

6

7

8

经济含义 ?

点A(8,0):
全部的设备都用来生产Ⅰ产品而不生产Ⅱ 产品,那么Ⅰ产品的最大可能产量为8台,计 算过程为: x1+2×0?8 ?x1?8

连接AB:
设备全部占用所生产 Ⅰ、Ⅱ数量对应的点 的集合。
x
2
Q4

B
x1 ? 2x2 ? 8

3 2 1

△A0 B:
设备没有全部占用所 生产Ⅰ、Ⅱ数量对应 的点的集合。

A
1 2 3 4 5 6 7 8

x
1

0

另两个约束条件的 边界直线CD、EF: 4x1≤16,4 x2 ≤12

x2

B
E

4x1 ? 16
F
C

3 2 1

4 x2 ? 12

x1 ? 2x2 ? 8
D

A

x1

约束条件及 0 1 2 3 4 5 6 7 8 非负条件x1,x2 ?0 代表的公共部分--图中阴影区,就是满足所 有约束条件和非负条件的点的集合,即可行域。 在这个区域中的每一个点都对应着一个可行的 生产方案。

令 Z=2x1+3x2=c, 其中c为任选的一个常 数,在图 中画出直线 2x1+3x2=c, 即对应着 一个可行的生产结果,即使两种产品的总利润 达到c。 这样的直线有无数条,且相互平行,称 这样的直线为目标函数等值线。只要画两条 目标函数等值线,如令 x2
B

4x1 ? 16
C

c=0和c=6,可看出目
3

E F

标函数值变化的方向,
2

4 x2 ? 12 最优点

即虚线 l1和l2,箭头为产 品的总利润递增的方向。

x1 ? 2x2 ? 8
D

1

A
5 6 7 8

x1

0

1

2

3

4

x2
3 2 1

B
E F

4x1 ? 16
C

4 x2 ? 12 最优点

x1 ? 2x2 ? 8
D

A
5 6 7 8

x1

0

1

2

3

4

? 沿着箭头方向平移目标函数等值线,达到可 行域中的最远点E, E点就是最优点;

? 对应坐标x1=4, x2=2 是最佳的产品组合, [4,2]T 就是线性规划模型的最优解
? 使产品的总利润达到最大值 maxZ=2?4+3?2=14就是目标函数最优值。

尽管最优点的对应坐标可以直接从图中 给出,但是在大多数情况下,对实际问题精 确地看出一个解答是比较困难的。所以,通 常总是用解联立方程的方法求出最优解的精 确值。 比如C点对应的坐标值我们可以通过求 解下面的联立方程,即求直线AB和CD的交 点来求得。 直线AB: x1+2x2=8 直线CD: 4x1=16

max Z ? 2 x1 ? 3x2
? x1 ? 2 x2 ≤ 8 ?4 x ≤ 16 ? 1 ? ?4 x2 ≤ 12 ? x1 , x2 ≥ 0 ?
x2

B
E F

4x1 ? 16

3

4 x2 ? 12
C

最优点

2

x1 ? 2x2 ? 8
D

1

A
5 6 7 8

x1

0

1

2

3

4

结果
有唯一最优解 可行域是一个非空有界区域

讨论

可行域有几种可能 ? 解有几种可能 ?

用图解法求解线性规划的各种可能的结果

唯一最优解
例2-3 将例2-1中目标要求改为极小化,
目标函数和约束条件均不变,则可行域与 例1-1相同,目标函数等值线也完全相同,

只是在求最优解时,应沿着与箭头相反的
方向平移目标函数等值线,求得的结果是 有唯一最优解x1=4,x2=2,对应着图2-6中 的坐标原点。

无穷多个最优解
max Z ? 2 x1 ? 3x2
x2

{c1,c2}

max Z ? x1 ? 2 x 2

? x1 ? 2 x2 ≤ 8 ?4 x ≤ 16 ? 1 ? ?4 x2 ≤ 12 ? x1 , x2 ≥ 0 ?

B
3

A
2 1

x1 ? 2 x2 ? 8
x1

0

1

2

3

4

5

6

7

8

沿着箭头的方向平移目标函数等值线, 发现平移的最终结果是目标函数等值线将 与可行域的一条边界线段AB重合。

结果表明,该线性规划有 无穷多个

最优解--线段AB上的所有点都是最优
点,它们都使目标函数取得相同的最大值 Zmax=14。

无界解
max Z ? x1 ? x2
??2 x1 ? x2 ≤ 4 ? ? x1 ? x2 ≤ 2 ?x , x ≥ 0 ? 1 2
x2

6

4

2

x1

0

1

2

3

4

5

如图中可行域是一个无界区域,如阴影区所示。 虚线为目表函数等值线,沿着箭头指的方向平移可 以使目标函数值无限制地增大,但是找不到最优解。 这种情况通常称为无“有限最优解” 或“最优

解无界”。
如果一个实际问题抽象成像例1-4这样的线性规 划模型,比如是一个生产计划问题,其经济含义就是 某些资源是无限的,产品的产量可以无限大。此时应 重新检查和修改模型,否则就没有实际意义。 注意,对于无界可行域的情况,也可能有唯一 最优解或无穷多个最优解。


推荐相关:

第二章2.2.1 线性规划问题的图解法.ppt

第二章2.2.1 线性规划问题的图解法 隐藏>> 、 线性规划的图解法 ---解的几何表示 1.什麽是图解法?线性规划的图解法就是用几何作图 的方法分析并求出其...


第二章-线性规划2.1-2_图文.ppt

1/2.2 (Linear Programming) 第2章 线性规划 2.1线性规划的模型与图解法 2.2单纯形法 2.1 线性规划的模型与图解法 2.1.1问题的引入 (1)生产安排问题 ...


第2章 线性规划与单纯形法(1)_图文.ppt

图解法及结果的讨论 线性规划问题标准型式 线性规划问题解的有关概念 单纯形法 小结 管 理 运 筹 学 1 §2.1 线性规划问题及其数学模型 线性规划是运筹学的...


2.1 线性规划问题的标准型_图文.ppt

第2章 线性规划单纯形法 线性规划单纯形法 2.1 线性规划问题的标准型 2.2 2.3 2.4 改进的单纯形法和对偶问题线性规划问题的应用案例 单纯形法的原理 2.5 ...


第一章1.2.1 线性规划问题的图解法..ppt

一章1.2.1 线性规划问题的图解法._幼儿读物_幼儿教育_教育专区。第一章1.2.1 线性规划问题的图解法. 、 线性规划的图解法 ---解的几何表示 1.什麽...


第2章线性规划(第1节)_图文.ppt

第2章线性规划(第1节)_数学_自然科学_专业资料。第二章 ? 线性规划(第1节) 线性规划问题 线性规划模型 线性规划解的基本概念 线性规划的图解 利用EXCEL求解...


2线性规划图解法和单纯形法_图文.ppt

Chapter1 线性规划 (Linear Programming) 本章主要内容: LP的数学模型 图解法 ...x1=3.8, x2=1.2, z=22.8 线性规划问题的数学模型例1.3 已知资料如下表...


2.1线性规划问题及其数学模型_图文.ppt

Chapter2 线性规划与单纯形法本章主要内容: §2.1 线性规划问题及其数学模型 §2.2 线性规划问题的几何意义 §2.3 单纯形法§2.4 单纯形法的计算步骤 §2.5...


2.1线性规划方法应用的典型情况2.2线性规划问题及其数(....ppt

第2章 2.1 2.2 2.3 2.4 2.5 2.6 2.7 线性规划模型和图解法 线性规划方法应用的典型情况 线性规划问题及其数学模型 简单最大化问题的图解法求解 简单最小...


第二章 线性规划问题解的性质.ppt

两个变量的线性规划问题的图解法一般过程 对于仅具有两个变量的线性规划问题,利用 作图的方法求最优解,简单、直观。 例2.1 max s = 2x1+5x2 ? x1 ? 4 ...


管理运筹学第2章_线性规划[1]_图文.ppt

管理运筹学第2章_线性规划[1] - 本章学习的目的使学员掌握线性规划问 题的一般定义和数学模型的特征。掌握两 个变量的线性规划问题的几何作图求解方 法。重点是...


最优化理论_第2章_1_线性规划、单纯形_图文.ppt

2.1 线性规划及数学模型的建立、什么是线性规划? ? 当求解一般线性规划问题的单纯形法出 现后,线性规划才得到更进一步发展, 应用也越来越广泛。 ? 例1.某...


运筹学第2章线性规划与单纯形法R5_图文.ppt

第二章 线性规划与单纯形法本章主要内容: LP的数学模型 图解法 单纯形法单纯...2x1 ? 3x2 ? x3 2.1 线性规划问题的数学模型从而该线性规划模型为: Page ...


第二章 线性规划在电力系统中应用 [2011]_图文.ppt

m1 1 m 2 2 ? ? x1 , x2 , …, xn ? 0. 2016/7/21 Southeast University 11 2.1.3 两个变量问题的图解法 ? 对于只有两个决策变量的线性规划问题...


《线性规划》092第一章1[1][1].3图解法=下 第二章2.1基....ppt

《线性规划》092第一章1[1][1].3图解法=下 第二章2.1基可行解=第三次课_理学_高等教育_教育专区。第一章 线性规划问题 第一章 线性规划问题 1.3 二...


2-1线性规划引论-(1) [运筹学]_图文.pdf

2-1线性规划引论-(1) [运筹学]_理学_高等教育_教育专区。第二章 线性规划...? ? ? 能根据实际问题列出线性规划的数学模型 掌握线性规划的图解法及其几何...


线性规划问题及其数学模型_图文.ppt

线性规划与目标规划第1章 线性规划与单纯形法 第2章 对偶理论与灵敏度分析 第...? ? ? 1.1 1.2 1.3 1.4 问题的提出 图解法 线性规划问题的标准形式 ...


管理运筹学 第二章 线性规划_图文.ppt

(万元) 第2章 线性规划 I 1 2 4 3 II 2 1 3 2 每周可使用量 5 4 ...2.2 线性规划的图解法对只包含两个决策变量的线性规划问题,可以用图解法 来...


C类运筹学 第2章 线性规划1_图文.ppt

C类运筹学 第2章 线性规划1_管理学_高等教育_教育专区。第一章 线性规划与单纯形法 1947年G.B.Dantzig 提出单纯形法 第一节 线性规划问题及其数学 模型 问题...


第1章 线性规划及其扩展1.2_图文.ppt

第1章 线性规划及其扩展1.2_经济学_高等教育_教育专区。运筹学 §1.2 线性规划的解与性质 1.2.1 两个变量线性规划问题的图解法对于只有两个变量的线性规划...

网站首页 | 网站地图
All rights reserved Powered by 大学生考试网 9299.net
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@qq.com