当前位置：文档之家 › 线性规划图解法

线性规划图解法

  • 格式：pptx
  • 大小：405.43 KB
  • 文档页数：63

下载文档原格式

  / 63

合集下载

线性规划图解法

线性规划图解法
第二节 线性规划的图解法
图解法 线性规划问题求解的 几种可能结果 由图解法得到的启示
上页
下页 继续
返回
例1的数学模型
目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x 1、 x 2 0
上页
下页
返回
图解法
9— 8—
x1+ 2x2=8 4x1 =16
4x1 16
C 4 x2 16
4 —B
3— 2— 1—
最优解 (4, 2)
D
x1 + 2x2 8
| 6 | 7 | 8 | 9 | 4
A
0
| 1
| 2
| 3
E
| 5
x1 下页 返回
上页
图解法求解步骤
• 由全部约束条件作图求出可行域； • 作目标函数等值线，确定使目标函数最
(d)无可行解
Max Z = 2x1 + 3x2 x1 +2 x2 8 4 x1 16 4x2 12 -2x1 + x2 4 x 1、 x 2 0
可行域为空集
上页 下页 返回
图解法的几点结论:
（由图解法得到的启示）
– 可行域是有界或无界的凸多边形。 – 若线性规划问题存在最优解，它一定可以在
优的移动方向； • 平移目标函数的等值线，找出最优点， 算出最优值。
上页
下页
返回
线性规划问题求解的 几种可能结果
(a) 唯一最优解
x2
6— 5— 4— 3— 2— 1— | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | x 9 1

运筹学线性规划图解法

运筹学线性规划图解法

引理1.线性规划问题的可行解X为基本可行解的充分 必要条件是X的正分量所对应的系数列向量是线性独立的. 证明:
必要性：已知X为线性规划的基本可行解，要证X的 正分量所对应的系数列向量线性独立。
因为X为基本解，由定义，其非零分量所对应的系数 列向量线性独立；又因为X还是可行解，从而其非零分量 全为正。
•有唯一解
例1： max z=2x1+ 3x2 s.t. x1+2x2≤8 4x1≤16 x1,x2≥0
画图步骤： 1、约束区域的确定 2、目标函数等值线 3、平移目标函数等值线求最优值
x2
可行域
(4,2) z=14
目标函数 等值线
x1
•有无穷多解
例2 max z =2x1+4x2 s.t. x1+2x2≤8 4x2 ≤ 12 3x1 ≤12 x1, x2 ≥0
X(0)=Σ α iX(i) α i0,Σ α i=1 记X(1),X(2), …,X(k)中满足max CX(i)的顶点为X(m)。于是，
k
k
CX (0) Ci X (i) Ci X (m) CX (m)
i 1
i 1
由假设CX(0)为最优解，所以CX(0)=CX(m)，即最优解可在顶点
充分性：已知可行解X的正分量所对应的系数列向量 线性独立，欲证X是线性规划的基本可行解。
若向量P1, P2,…, Pk线性独立,则必有k≤m；当k=m时， 它们恰构成一个基，从而X=（x1，x2,…,xk，0…0）为相 应的基可行解。K〈m时，则一定可以从其余的系数列向量 中取出m-k个与P1, P2,…, Pk构成最大的线性独立向量组， 其对应的解恰为X，所以根据定义它是基可行解。
§2 线性规划图解法

线性规划(图解法)

线性规划(图解法)

D
max Z
可行域
（7.6，2） ， ）
34.2 = 3X1+5.7X2
X1 + 1.9X2 = 3.8(≥) X1 - 1.9X2 = 3.8 (≤) L0： 0=3X1+5.7X2
oபைடு நூலகம்
x1
图解法
min Z=5X1+4X2 x2
X1 + 1.9X2 = 10.2 (≤)
Page 18
43=5X1+4X2 8=5X1+4X2 此点是唯一最优解 （0，2） ， ）
图解法
线性规划问题的求解方法 一般有 两种方法 图解法 单纯形法 两个变量、 两个变量、直角坐标 三个变量、 三个变量、立体坐标
Page 1
适用于任意变量、 适用于任意变量、但必需将 一般形式变成标准形式
下面我们分析一下简单的情况—— 下面我们分析一下简单的情况—— 只有两个决策 变量的线性规划问题， 变量的线性规划问题，这时可以通过图解的方法来 求解。图解法具有简单、直观、 求解。图解法具有简单、直观、便于初学者窥探线 性规划基本原理和几何意义等优点。 性规划基本原理和几何意义等优点。
• 有效与无效 紧与松)约束：与最优解相关的约束为有效 有效与无效(紧与松 约束 紧与松 约束： (紧)约束。 紧 约束 约束。 • 最优解：总是在可行域的边界上，一般由可行域的顶 最优解：总是在可行域的边界上， 点表示。 点表示。 • 可行域：由约束平面围起来的凸多边形区域，可行域 可行域：由约束平面围起来的凸多边形区域， 个可行解。 内的每一个点代表一 个可行解。
20
无可行解(即无最优解 无可行解 即无最优解) 即无最优解
10
O
10

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

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

02
图解法的基本原理
图解法的概念
图解法是一种通过图形来直观展示线性规划问题解的方法。它通过在坐标系中绘 制可行域和目标函数，帮助我们理解问题的结构和最优解的位置。
图解法适用于线性规划问题中变量和约束条件较少的情况，能够直观地展示出最 优解的几何意义。
图解法的步骤
确定决策变量和目标函数
明确问题的决策变量和目标函数，以便在图 形中表示。
目标函数是要求最小化或最大化的函数，通常表示为 $f(x) = c_1x_1 + c_2x_2 + ldots + c_nx_n$。
04
约束条件是限制决策变量取值的条件，通常表示为 $a_1x_1 + a_2x_2 + ldots + a_nx_n leq b$或 $a_1x_1 + a_2x_2 + ldots + a_nx_n = b$。
LINDO是一款开源的线性规划求解器，用 户可以免费使用。
软件工具的使用方法
Excel
用户需要先在Excel中设置好线性规划模型，然后使 用“数据”菜单中的“规划求解”功能进行求解。
Gurobi/CPLEX/LINDO
这些软件通常需要用户先在软件界面中输入线性规划 模型，然后通过点击“求解”按钮进行求解。
实例三：分配问题
总结词
分配问题是指如何根据一定的分配原则 或目标，将有限的资源分配给不同的需 求方，以最大化整体效益。
VS
详细描述
分配问题在实际生活中广泛存在，如物资 分配、任务分配等。通过图解法，可以将 分配问题转化为线性规划模型，并利用图 形直观地展示最优解的资源分配方案。在 分配问题中，通常需要考虑不同需求方的 重要性和优先级，以及资源的有限性等因 素，以实现整体效益的最大化。

线性规划问题的图解法

线性规划问题的图解法
第二十四页，共51页。
单纯形法的计算(jìsuàn)步骤
单纯形法的思路(sīlù)
找出一个(yī ɡè)初始可行解
4x1
16
可行(kěxíng)域
单纯形法的进一步讨论(tǎolùn)－人工变量法
第四十三页，共51页。
单纯形法的计算(jìsuàn)步骤
是否最优 故人(gùrén)为添加两个单位向量，得到人工变量单纯形法数学模型：
量作为换出变量。
L
min
bi a ik
a ik
0
第二十九页，共51页。
单纯形法的计算(jìsuàn)步骤
③ 用换入变量(biànliàng)xk替换基变量(biànliàng)中的换出变量 (biànliàng)，得到一个新的基。对应新的基可以找出一个新的基可 行解，并相应地可以画出一个新的单纯形表。
： X (1) K和X (2) K
X X (1) (1 ) X (2) (0 1)
则X为顶点(dǐngdiǎn).
(wèntí)
的 几
第四页，共51页。
凸组合(zǔhé)：
意线 义性
规 划 问 题 的 几 何
设X（1) ,..., X (k)是n维向量空间中的k个点,
若存在1,..., k ,且0 i 1, i 1,2,..., k,
A
1 域2 3
D
| E|
45
4 x2 16 x1 + 2x2 8
|||| 6789
x1
第九页，共51页。
❖图解法
目标(mùbiāo)函数 Max Z = 2x1 + 3x2
x2 9—
8—
7—
6—
5—
4—

第2章 线性规划图解法

第2章 线性规划图解法
-8
x2
6
4
可行域
6
0
x1
23
3. 画出目标函数的图形(通常可画出当目 标函数值为零时的(基准)目标函数图)，确 定目标函数平行移动的方向，并沿目标函 数直线的法向用小箭头标出。
例1. max Z = x1+3x2 s.t. x1+ x2≤6 -x1+2x2≤8 x ≥0, x ≥0 1 2
大轿车座椅的限制： 非负限制：
5 x1 2.5 x2 2500 x1 400 x1 0, x2 0
分析：问题是如何安排生产使得工厂获利最大？
项目 产品 生产能力 5 (小时 ⁄ 辆) 2.5 (小时 ⁄ 辆) 2500 (小时 ⁄ 年) 钢材 (吨 ) 装配座椅 (辆 ⁄ 年 ) 利润 (千元 ⁄ 辆)
4
§2.1
线性规划问题的提出
线性规划研究的内容和问题
线性规划是研究在线性不等式或等式的限 制条件下，使得某一个线性目标函数取得最大 （或最小）的问题。常见的线性规划问题有： （一） 运输问题 （二） 生产的组织与计划问题 （三） 合理下料问题 （四） 配料问题 （五） 布局问题 （六） 分派问题
5
7
例1. 某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产， 已知生产单位产品所需的设备台时及A、B两种原材料的 消耗、资源的限制，如下表：
设备 原料 A 原料 B 单位产品获利 Ⅰ 1 2 0 50 元 Ⅱ 1 1 1 100 元 资源限制 300 台时 400 千克 250 千克
问题:工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获 利最多？
6
§2.1
线性规划问题的提出
线性规划发展前景
另一方面，以线性规划为基础而发展起 来的多部门的线性规划 , 多时期的线性规划， 模糊线性规划，随机线性规划，以及整数规 划，非线性规划，目标规划等等，为现代管 理中各类实际问题的解决提供了科学的方法。 目前线性规划的理论研究仍十分活跃，其应 用前景也越来越广阔，它已成为国家重点推 广的现代管理方法之一。

第1章 2 线性规划问题的图解法


其中c 令 Z=2x1+3x2=c, 其中c为任选的一个常 数 ， 在图中画出直线 2x1+3x2=c, 即对应着一 组可行的生产结果， 组可行的生产结果，使两种产品的总利润达到 c。 。 这样的直线有无数条， 且相互平行， 这样的直线有无数条 ， 且相互平行 ， 称 只要画两条 这样的直线为目标函数等值线。只要画两条 目标函数等值线 等值线， 目标函数等值线，如令 x2 c＝0和c=6，可看出目 ＝ 和 ，可看出目
x2
4x1 ≤ 16 C D
| 1 | 2 | 3 | 4
4 x2 ≤ 16
最优解 (4, 2)
x1 + 2x2 ≤ 8
| 6 | 7 | 8 | 9
A
0
E
| 5
x1
图解法求解步骤
由全部约束条件作图求出可行域； 由全部约束条件作图求出可行域； 作目标函数等值线，确定使目标函数 作目标函数等值线， 最优的移动方向； 最优的移动方向； 平移目标函数的等值线，找出最优点， 平移目标函数的等值线，找出最优点， 算出最优值。 算出最优值。
练习1答案
max z=x1+3x2 s.t. x1+ x2≤6 -x1+2x2≤8 x1 ≥0, x2≥0
x2 6
最优解（4/3，14/3）
4
可行域
-8 0
目标函数等值线
6
x1
练习2 某公司由于生产需要，共需要A， 练习 ：某公司由于生产需要，共需要 ， B两种原料至少 两种原料至少350吨（A，B两种材料有 两种原料至少 吨 ， 两种材料有 一定替代性），其中A原料至少购进 ），其中 原料至少购进125 一定替代性），其中 原料至少购进 但由于A， 两种原料的规格不同 两种原料的规格不同， 吨。但由于 ，B两种原料的规格不同， 各自所需的加工时间也是不同的， 各自所需的加工时间也是不同的，加工每 原料需要2个小时 吨A原料需要 个小时，加工每吨 原料需 原料需要 个小时，加工每吨B原料需 小时， 个加工小时。 要1小时，而公司总共有 小时 而公司总共有600个加工小时。 个加工小时 又知道每吨A原料的价格为 万元，每吨B 原料的价格为2万元 又知道每吨 原料的价格为 万元，每吨 原料的价格为3万元 万元， 原料的价格为 万元，试问在满足生产需 要的前提下，在公司加工能力的范围内， 要的前提下，在公司加工能力的范围内， 如何购买A， 两种原料 两种原料， 如何购买 ，B两种原料，使得购进成本 最低？ 最低？

第二章 图解法与单纯形法


表1-4 XB
基变量 x1 x2
进基列 x3
bi /ai2，ai2>0 x4 b
将3化为1
(1)
θi 40 10
出 基 行
x3
x4
2
1 3
1
3 4
1
0 0
0
1 0
40
30
σj
x3
乘 以 1/3 后 得 到
5/3
0 1 0 0 1
1 0 0 3/5 -1/5
-1/3 1/3 -4/3 -1/5 2/5
x2
40
例题
2 x1 x2 40 x1 1.5x2 30
(15,10)
max Z 3x1 4x2 2 x1 x2 40
30
x1 1.5 x2 30 x1 0, x2 0
20
最优解X=(15,10) 最优值Z=85
10
O
10
20
30
40
x1
2.1 线性规划问题的图解法
θ M 20
0 λj
0 2 λj 1 2 λj
x5
x4 x2 x1 x2
1/3 1
3 1/3 1/3 1 0 0
1 2
0 1 0 0
5 1
17 5 －9 17/3
0 0
1 0 0 1/3
1 0
3 1 －2 1
20
75 20 25
25 60
1 0
28/9 －1/9 2/3 －98/9 －1/9 －7/3
1.通过图解法了解线性规划有几种解的形式 2.作图的关键有三点 (1)可行解区域要画正确 (2)目标函数增加的方向不能画错 (3)目标函数的直线怎样平行移动

线性规划的图解法


x2
30
20
A
10
B C D 20
0
10
30
图4-5
x1
线性规划的图解法
求最优解
x2
Z=40x1+50x2 0=40x1+50x2 (0,0)， (10,-8)
C点： x1+2x2 =30 3x1+2x2 =60 最优解：x* = (15,7.5) Zmax =975
30
20
A
10
B C D 20
求：最大利润的生产计划。
线性规划数学模型
解:设产品A, B产量分别为变量x1 ， x2 max Z= 40x1 +50x2 约束条件：x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0
线性规划的图解法
图解法的步骤：
1、在平面上建立直角坐标系； 2、图示约束条件，找出可行域； 3、图示目标函数和寻找最优解。
0
10
30
x1
图4-6
4．线性规划的图解法
例4-3、 maxZ=40x1+ 80x2 x2 x1+2x2 30 3x1+2x2 60 2x2 24 x1 , x2 0 A 解: 最优解：BC线段 0 B点 C点 x(1)=(6,12) x(2)=(15,7.5) x= x(1)+(1-) x(2) (0 1) B
8
产品产量最优组合的确定
PA/ PB= QB/QA 图4-4
QB E 产 品 B
o
QA
产品A
9
第2 节
产品产量最优组合决策的实用方法 ——线性规划法
10

线性规划问题的图解法


20 40
.
即B点坐标为20 ，40，代入目标函数可得最优值Smax 50 20 30 40 2 200 .
线性规划问题的图解法
例2
解
1. 求可行域（如图7 - 2所示）
（1）建立直角坐标系Ox1x2 . （2）满足条件 x1 x2 2 的所有点均落在直线 x2 2 x1 的右下半平面内； （3）满足条件 x1 x2 2 的所有点均落在直线 x2 2 x1 的右上半平面内. 由约束条件可知，无界区域ABCD是其可行域 .
3 截距最大的点即为最优解，其对应的S值就是最优值 .因此，我们可以把过原点且斜率 5的直
3 线作为参照直线，然后在可行域里进行平移，直到找到最优解 .
显然，斜率为 5的直线在可行域里平移时过B点的纵截距最大，求B点的坐标，联立 3
方程
x2 x2
Hale Waihona Puke 80 2x1 40，解得
x1 x2
图7-2
线性规划问题的图解法
2. 求最优解 把目标函数 S x1 2x2 中的S看作参数，当S 0时，目标函数S x1 2x2是一条过原点 的直线，在坐标系内画出这样的直线（用虚线表示），然后再将该直线向可行域内平移 . 在平移
时，7-2中B点是满足该约束条件的S最小值，其坐标为2 ，0，于是得到该线性规划问题的最
于是从约束条件知，由l1 ，l2 ，l3以及x1轴围成的区域 ABCD是该线性规划问题的可行域，如图7-1所示 .
图7-1
线性规划问题的图解法
2.求最优解 可行域的点满足约束条件，但并非使得目标函数 max S 50x1 30x2 取得最大值的解， 且该目标函数对应的图象也是一条直线，其斜率为 5，可行域里能使该直线与y轴的纵
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第二章 线性规划的图解法
在管理中一些典型的线性规划应用 • 合理利用线材问题：如何在保证生产的条
件下，下料最少 • 配料问题：在原料供应量的限制下如何获
取最大利润 • 投资问题：从投资项目中选取方案，使投
资回报最大
3
第二章 线性规划的图解法
• 产品生产计划：合理利用人力、物力、财 力等，使获利最大
第二章 线性规划的图解法
• 对于只有两个变量的简单的线性规划问 题，一般采用图解法求解。这种方法仅 适用于只有两个变量的线性规划问题。 它的特点是直观而易于理解，但实用价 值不大。
第二章 线性规划的图解法
1.基本概念 （1）可行解：满足约束条件的决策变量的取值 （2）可行域：可行解的全体 （3）最优解：使目标函数取得最优值的可行解 （4）最优值：最优解代入目标函数所得到的值
决策变量为可控的连续变量。
x 1 ≥ 0，x 2 ≥ 0
x 1 =0,1,2,3…n
目标函数和约束条件都是线性的。
Maxf 7x1 12x2
9x1 4x2 360
s.t.34xx11
5x2 10 x
2
2 ln
x2
1 x3
第二章 线性规划的图解法
9x1 4x2 360
s
.t
.43
x1 x1
5x2 10x
200 2 300
x1, x2 0
第二章 线性规划的图解法
★线性规划模型的三个基本要素： （也是所有规划问题的三个基本要素）：
（1）决策变量：甲、乙产品的产量x1 ，x2 决策变量：需要决策的量，即等待求解的未知数。
（2）目标函数：总收入最大，Max f = 7 x 1 +12 x 2
8—
点）都是可行解。此区域是就是
s.t
.43
x1 x1
5x2 10x
200 2 300
x1, x2 0
Max （maximize最大化）
Min
(minimum)
s.t. (subject to受制于)
第二章 线性规划的图解法
解：设安排甲、乙产量分别为x1 ，x2 ,总收入为
f ， 则该问题的数学模型为：
Maxf 7x1 12x2
s.t. a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1 a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2 …… …… am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm x1 ，x2 ，… ，xn ≥ 0
第二章：线性规划的图解法
第一节：线性规划问题的提出 第二节：线性规划的图解法 第三节：图解法的灵敏度分析
本章的重点和难点：
1：线性规划的图解法 2：图解法的灵敏度分析
第二章 线性规划的图解法
线性规划的定义
• 求线性目标函数在线性约束条件下的最 大值或最小值的问题，统称为线性规划 问题。
• 满足线性约束条件的解叫做可行解，由 所有可行解组成的集合叫做可行域。决 策变量、约束条件、目标函数是线性规 划的三要素.
例2.某工厂在计划期内要安排Ⅰ、Ⅱ两种产 品的生产，已知生产单位产品所需的设备台 时及A、B两种原材料的消耗、资源的限制， 如下表：
设备 原料 A 原料 B 单位产品获利
Ⅰ 1 2 0 50 元
Ⅱ 1 1 1 100 元
资源限制 300 台时 400 千克 250 千克
问题：工厂应分别生产多少单位Ⅰ、Ⅱ 产品才能使工厂获利最多？
• 劳动力安排：用最少的劳动力来满足工作 的需要
• 运输问题：如何制定调运方案，使总运费 最小
第二章 线性规划的图解法
问题1:某工厂计划生产甲、乙两种产品， 生产1kg的甲需耗煤9t、电力4kw.h、油3t； 生产1kg的乙需耗煤4t、电力5kw.h、油10t； 该厂现有煤360t、电力200kw.h、油300t。 已知甲产品每千克的售价为7万元、乙产品每
第二章 线性规划的图解法
例3.用图解法对下列线性规划模型进行求解。
Max Z=2x1+ 3x2 s.t. x1+ 2x2 ≤8
4x1 ≤16 x2 ≤12
x1, x2 ≥0
第二章 线性规划的图解法
图解法求解的步骤： 分别取决策变量X1 , X2 为坐标向量
建立直角坐标系。在直角坐标系里，图 上任意一点的坐标代表了决策变量的一 组值。
千克的售价为12万元。 在上述条件下决定生产方案，使得总收入最
大。
第二章 线性规划的图解法
问题1具体数据如表所示：
资源 单耗
产品
资源 煤(t)
电(kw.h) 油(t)
单位产品价格
甲乙
9
4
4
5
3 10
7 12
资源限量
提出和形成问题
建立模型
360
200
求解
300
结果的分析和应用
第二章 线性规划的图解法
在本例中
决策变量： 甲、乙产品的计划产量，记为x1 ，x2；
总收入记为f,则 f=7x1 +12x2 ，为体现对其求极大化，
目标函数：
在f 的前面冠以极大号Max，
也就是： Maxf 7x1 12x2
资源煤、电、油的数量是有限的，对产品甲
和乙的生产量构成了约束，表示为：
约束条件：
9x1 4x2 360
目标函数：想要达到的目标，用决策 变量的表达式表示。
（3）约束条件：
约束条件：由于资源有限，为了实现 目标有哪些资源限制，用决策变量的 等式或不等式表示。
9x1 4x2 360
s.t.34xx11
5x2 10 x
200 2 300
x1, x2 0
第二章 线性规划的图解法
什么是线性规划模型：
第二章 线性规划的图解法
• 目标函数：Maxz = 50 x1 + 100 x2
• 约束条件：s.t. x1 + x2 ≤ 300
•
2 x1 + x2 ≤ 400
•
x2 ≤ 250
•
x1 , x2 ≥ 0
第二章 线性规划的图解法 • 一般形式 目标函数：Max （Min）z = c1 x1 + c2 x2 + … + cn xn 约束条件：
17
第二章 线性规划的图解法
x2
x1 + 2x2 8
9—
4x1
16
8—
4x2 12
7—
x1、 x2 0
6—
4x1 16
5—
4—
3—
4 x2 12
2—
x1 + 2x2 8
1—
0
|| | | || | | | 12 3 4 5 6 7 8 9
x1
可行解：满足约束条件的解。红
9—
色区域中的每一个点（包括边界