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

2第二章线性规划图解法

  • 格式：ppt
  • 大小：991.00 KB
  • 文档页数：40

下载文档原格式

  / 40

合集下载

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

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


B、约束条件不是等式的问题：
若约束条件为 ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引进一个新的变量si ，使它等于约束右 边与左边之差 si=bi–(ai1 x1 + ai2 x2 + … + ain xn ) 显然，si 也具有非负约束，即si≥0， 这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn+si = bi
第二章 线性规划 的图解法
一、线性规划的概念 二、线性规划问题的提出 三、线性规划的数学模型 四、线性规划的图解法 五、线性规划解的情况 六、LP图解法的灵敏度分析
一、线性规划的概念
线性规划Linear Programming 简称LP，是一 种解决在线性约束条件下追求最大或最小的 线性目标函数的方法。 线性规划的目标和约束条件都可以表示成线 性的式子。
max z 3 x1 2 x2
2 x1 x2 ≤ 10 设备B台时占用 s.t. x1 x2 ≤ 8 x , x ≥ 0 产量非负 1 2
决策变量 （decision variable） 目标函数 （objective function） 约束条件 （subject to）

-ai1
x1-ai2 x2- … -ain xn = -bi 。
例1.3：将以下线性规划问题转化为标准形式 Min f = 3.6 x1 - 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 ≤15.7 4.1 x1 + 3.3 x3 ≥8.9 x1 + x2 + x3 = 38 x 1 , x 2 , x3 ≥ 0
管理运筹学第二章线性规划的图解法

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


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
详细描述
分配问题在实际生活中广泛存在，如物资 分配、任务分配等。通过图解法，可以将 分配问题转化为线性规划模型，并利用图 形直观地展示最优解的资源分配方案。在 分配问题中，通常需要考虑不同需求方的 重要性和优先级，以及资源的有限性等因 素，以实现整体效益的最大化。
管理运筹学_第二章_线性规划的图解法

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


线性规划中超过约束最低限的部分，称为剩余量。 记s1,s2为剩余变量，s3为松弛变量，则s1=0, s2=125,
s3=0，加入松弛变量与剩余变量后例2的数学模型变为 标准型： 目标函数： min f =2x1+3x2+0s1+0s2+0s3 约束条件： x1+x2-s1=350， x1-s2=125, 2x1+x2+s3=600, x1, x2, s1,s2,s3≥0.
阴影部分的每 一点都是这个线 性规划的可行解， 而此公共部分是 可行解的集合， 称为可行域。
B
X2=250
100
100
300
x1
B点为最优解， X1+X2=300 坐标为（50, 250）， Z=0=50x1+100x2 此时Z=27500。 Z=10000=50x1+100x2 问题的解： 最优生产方案是生产I产品50单位，生产Ⅱ产品250单位，可得 最大利润27500元。
Z=10000=50x1+50x2
线段BC上的所有点都代表了最优解，对应的最优值相 同： 50x1+50x2=15000。
10
3. 无界解，即无最优解的情况。对下述线性规划问题：
目标函数：max z =x1+x2 约束条件：x1 - x2≤1 -3x1+2x2≤6 x1≥0, x2≥0．
x2 -3x1+2x2=6 3
其中ci为第i个决策变量xi在目标函数中的系数， aij为第i个约束条件中第j个决策变量xj的系数， bj(≥0)为第j个约束条件中的常数项。
16
灵敏度分析
灵敏度分析：求得最优解之后，研究线性规划的
线性规划图解法

线性规划图解法


第二章 线性规划的图解法
在管理中一些典型的线性规划应用 • 合理利用线材问题：如何在保证生产的条
件下，下料最少 • 配料问题：在原料供应量的限制下如何获
取最大利润 • 投资问题：从投资项目中选取方案，使投
资回报最大
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
第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-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 ➢ 最优解为： x1 ＝15 ，x2＝10 40 ➢ 最优值为：z*＝2500×15+1500×10
➢
30
＝52500
3x2＝75
20
（15，10）
10
O
10
20
30
40
50 X1
3x1+2x2＝65
2x1+x2＝40
五、线性规划问题解的情况
➢ 例1.5的最优解只有一个，这是线性规划问题 最一般的解的情况，但线性规划问题解的情 况还存在其它特殊的可能：无穷多最优解、 无界解或无可行解。
... am1x1+am2x2 +…+amnxn≤( =, ≥ )bm x1 ，x2 ，… ，xn ≥ ( ≤) 0 或无约束
xj为待定的决策变量； cj为目标函数系数，或价值系数、费用系数； aij为技术系数； bj为资源常数，简称右端项； 其中i＝1，2，…m； j＝1，2，…n
可以看出，一般LP模型的特点： A、决策变量x1，x2，x3，……xn表示要寻求
O
100 200 300
X1
3、无界解的情况
➢若将例1.5的线性规划模型中约束条件1、2的 不等式符号改变，则线性规划模型变为：
➢ 目标函数：Max z= 50x1+100 x2 约束条件：x1+x2 ≥ 300 2x1+x2 ≥ 400 x2≤250 x1 ≥0， x2 ≥0
B、定义决策变量；
C、用决策变量的线性函数形式写出所要追求 的目标，即目标函数；
D、用一组决策变量的等式或不等式来表示在 解决问题过程中所必须遵循的约束条件。
三、线性规划的数学模型
1、LP模型的一般形式 目标函数：
线性规划的图解法

线性规划的图解法


s.t.
32xx11'' 3x1'
+ + +
2
x2 x2 x2
+ x3' − x3'' + 2x3' − 2x3'' + 3x3' − 3x3''
+
x4
−
x5
= 9 = 4 = 6
x1'
,
2
x2
,
x3' ,
x3'' ,
x4 ,
x5
≥
0
2.1问题的提出
例7 将以下线性规划问题转化为标准形式。
min f =−3x1 + 5x2 + 8x3 − 7x4
x5
≥
20
x5 xj
+ ≥
x6 0,
≥ 30 j = 1, 2, ,
6
2.1问题的提出
所谓线性规划问题
就是求一组变量 (x1,x2,…,xn)的值，它们在满足一组线 性等式或不等式的限制条件下，使某一线性函数的值达到 极大或极小。而线性规划就是研究并解决这类问题的一门 理论和方法。
线性规划模型是由决策变量、目标函数和约束条件三要素 组成。
例2 某昼夜服务的公交线路每天各时间区段内所需的工
作人员数量如下：
时段
时间
所需人数
1
6:00~10:00
60
2
10:00~14:00
70
3
14:00~18:00
60
4
18:00~22:00
50
5
22:00~2:00
20
第二章 线性规划的图解法(简)

第二章 线性规划的图解法(简)


第二节 图解法
在线性规划中，对一个约束条件中没使用的资源或能力的大小称 之为松弛量。记为Si。
第二节 图解法
像这样把所有的约束条件都写成等式 ，称为线性规划模型的标准化，所得结果 称为线性规划的标准形式。
第二节 图解法
同样对于≥约束条件中，可以增加一些代表
最低限约束的超过量，称之为剩余变量，把≥约
第二章 线性规划的图解法
主要内容：
§1 问题的提出 （什么是线性规划） §2 图解法 §3 图解法的灵敏度分析
重点和难点
重点： （1）线性规划问题的主要概念 （2）线性规划问题的数学模型 （3）线性规划图解法的过程 （4）阴影价格的定义和灵敏度分析 难点： 灵敏度分析
第一节 问题的提出
约束条件对偶价格小于零时，约束条件
右边常数增加一个单位，就使得最优目
标函数值减少一个其对偶价格。
第三节 图解法的灵敏度分析
对目标函数值求最小值的情况下， 当对偶价格大于零时，约束条件右边常数增加 一个单位就使其最优目标函数值减少一个其对 偶价格； 当对偶价格等于零时，约束条件右边常数增加 一个单位，并不影响其最优目标函数值； 当对偶价格小于零时，约束条件右边常数增加 一个单位，就使得其最忧目标函数值增加一个 其对偶价格。
具有上述3个特征的问题为线性规划问题。
第一节 问题的提出
我们的仸务就是要选择一组或多组方案，使目
标函数值最大或最小。从选择方案的角度说，
这是规划问题。从使目标函数值最大或最小的
角度说，就是优化问题。
线性规划数学模型的一般表示方式
max(min) f ( x) c1 x1 c2 x2 cn xn a11 x1 a12 x2 a1n xn a x a x a x 21 1 22 2 2n n s.t. a x a x a x m2 2 mn n m1 1 x1 , x2 , , xn n : 变量个数 ; m : 约束行数 ; n m : 线性规划问题的规模 c j : 价值系数 ; b j : 右端项; aij : 技术系数 (, )b1 (, )b2 (, )bm 0
[高三数学]第2章 线性规划的图解法

[高三数学]第2章 线性规划的图解法


2
线性规划的组成： 目标函数 Max F 或 Min F 约束条件 s.t. (subject to) 满足于 决策变量 用符号来表示可控制的因素

3
例1. 某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生 § 1 问题的提出 产，已知生产单位产品所需的设备台时及 A、B两 种原材料的消耗、资源的限制，如下表：
300 400 250 0 0
(A) (B) (C) (D) (E)
得到最优解： x1 = 50， x2 = 250
最优目标值 z = 27500
8
§2 图 解 法
(1)分别取决策变量X1 , X2 为坐标向量建立直角坐标系。
在直角坐标系里，图上任意一点的坐标代表了决策变量的 x2 x2 一组值，例 1的每个约束条件都代表一个半平面。
7
§2
对于只有两个决 策变量的线性规划问 题，可以在平面直角 坐标系上作图表示线 性规划问题的有关概 念，并求解。 下面通过例1详细 讲解其方法：
图解法
例1.目标函数： Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + 2 x1 +
x2 x2 x2 x1 x2
≤ ≤ ≤ ≥ ≥
5
§1 问题的提出

建模过程
1.理解要解决的问题，了解解题的目标和条件； 2.定义决策变量（ x1 ，x2 ，… ，xn ），每一组值 表示一个方案； 3.用决策变量的线性函数形式写出目标函数，确定 最大化或最小化目标；
4ቤተ መጻሕፍቲ ባይዱ用一组决策变量的等式或不等式表示解决问题过 程中必须遵循的约束条件
6

一般形式
目标函数： Max （Min） z = c1 x1 + c2 x2 + … + c n xn
第二章 线性规划的图解法

第二章 线性规划的图解法

x2
AB
z
C
D
z=0=50x1+100x2
E
x1
图2-2
12
❖ 目标函数：Maxz = 50 x1 + 100 x2
❖ 约束条件：s.t. x1 + x2 ≤ 300
❖
2 x1 + x2 ≤ 400
❖
x2 ≤ 250
❖
x1 , x2 ≥ 0
❖最优解： x1 =50 x2 = 250
❖例2：某工厂在计划期内要安排生产Ⅰ、Ⅱ 两种产品，已知生产单位产品所需的设备台
- (c1 / c2 ) ， 当 -1 - (c1 / c2 ) 0 （*） 时，原最优解仍是最优解。
❖假设产品Ⅱ的利润100元不变，即 c2 = 100，代到式（*）并整理得 0 c1 100
❖假设产品Ⅰ的利润 50 元不变，即 c1 = 50 ，代到式（*）并整理得 50 c2 +
▪ 4.无可行解。若在例1的数学模型中 再增加一个约束条件4x1+3x2≥1200， 则可行域为空域，不存在满足约束条 件的解，当然也就不存在最优解了。
例3.某公司由于生产需要，共需要A，B两种原料至 少350吨（A，B两种材料有一定替代性），其中A原 料至少购进125吨。但由于A，B两种原料的规格不同 ，各自所需的加工时间也是不同的，加工每吨A原料 需要2个小时，加工每吨B原料需要1小时，而公司总 共有600个加工小时。又知道每吨A原料的价格为2万 元，每吨B原料的价格为3万元，试问在满足生产需 要的前提下，在公司加工能力的范围内，如何购买A ，B两种原料，使得购进成本最低？
❖-ai1 x1-ai2 x2- … -ain xn = -bi。

[管理学]第2章 线性规划的图解法

2 x1 + x2 ≤ 400 （原料A数量约束） x2 ≤ 250 （原料B数量约束）
x1 , x2 ≥ 0
h
管理运筹学
3
§1 问题的提出
• 建模过程
1.理解要解决的问题，了解解题的目标和条件；
2.定义决策变量（ 案；
x1
，x2
，…
，xn
），每一组值表示一个方
3.用决策变量的线性函数形式写出目标函数，确定最大化或最 小化目标；
坐标系上作图表示线 性规划问题的有关概 念，并求解。
下面通过例1详细 讲解其方法：
s.t.
x1 + x2 ≤ 300 (A) 2 x1 + x2 ≤ 400 (B)
x2 ≤ 250 (C) x1 ≥ 0 (D) x2 ≥ 0 (E) 得到最优解：
x1 = 50， x2 = 250 最优目标值 z = 27500
4.用一组决策变量的等式或不等式表示解决问题过程中必须遵 循的约束条件
• 一般形式
目标函数： 约束条件：
Max （Min） z = c1 x1 + c2 x2 + … + cn xn
s.t.
a11 x1 + a12 x2 + … + a1n xn a21 x1 + a22 x2 + … + a2n xn
说明：生产50单位Ⅰ产品和250单位Ⅱ产品将消耗完所有
可能的设备台时数及原料B，但原料A则还剩余50千克。
h
管理运筹学
10
§2 图 解 法
• 重要结论：
– 如果线性规划有唯一最优解，则一定有一个可 行域的顶点对应最优解；
– 无穷多个最优解。若将例1中的目标函数变为 max z=50x1+50x2，则线段BC上的所有点都代表 了最优解；

《管理运筹学》第二版习题答案(韩伯棠教授)1

3第 2 章 线性规划的图解法1、解：x 26A B1O 01C6x 1a.可行域为 OABC 。

b.等值线为图中虚线所示。

12c.由图可知，最优解为 B 点，最优解： x 1 = 769 。

7 2、解：15 x 2 =7， 最优目标函数值：a x 210.60.1O0.1 0.6x 1有唯一解x 1 = 0.2函数值为 3.6x 2 = 0.6b 无可行解c 无界解d 无可行解e 无穷多解1 2 2 1 2f 有唯一解20 x 1 =3 8函数值为 92 33、解：a 标准形式：b 标准形式：c 标准形式：x 2 = 3max fmax f= 3x 1 + 2 x 2 + 0s 1 + 0s 2 + 0s 3 9 x 1 + 2x 2 + s 1 = 303x 1 + 2 x 2 + s 2 = 13 2 x 1 + 2x 2 + s 3 = 9 x 1 , x 2 , s 1 , s 2 , s 3 ≥= −4 x 1 − 6x 3 − 0s 1 − 0s 23x 1 − x 2 − s 1 =6x 1 + 2x 2 + s 2 = 10 7 x 1 − 6 x 2 = 4x 1 , x 2 , s 1 , s 2 ≥max f = −x ' + 2x ' − 2 x ''− 0s − 0s'''− 3x 1 + 5x 2 − 5x 2 + s 1 = 70 2 x ' − 5x ' + 5x '' = 50122' ' ''3x 1 + 2 x 2 − 2x 2 − s 2 = 30'' ''4 、解：x 1 , x 2, x 2, s 1 , s 2 ≥ 0标准形式： max z = 10 x 1 + 5x 2 + 0s 1 + 0s 23x 1 + 4 x 2 + s 1 = 9 5x 1 + 2 x 2 + s 2 = 8 x 1 , x 2 , s 1 , s 2 ≥ 0s 1 = 2, s 2 = 0标准形式： min f = 11x 1 + 8x 2 + 0s 1 + 0s 2 + 0s 310 x 1 + 2x 2 − s 1 = 203x 1 + 3x 2 − s 2 = 18 4 x 1 + 9x 2 − s 3 = 36 x 1 , x 2 , s 1 , s 2 , s 3 ≥ 0s 1 = 0, s 2 = 0, s 3 = 136 、解：b 1 ≤c 1 ≤ 3c 2 ≤ c 2 ≤ 6d x 1 = 6 x 2 = 4e x 1 ∈ [4,8]x 2 = 16 − 2x 1f 变化。

2.3 线性规划的图解法


1984年印度的Karmarkar提出“投影梯度法”
线性规划是研究线性不等式组的理论，或者 说是研究（高维空间中）凸多面体的理论，是线 性代数的应用和发展。
线性规划问题的一般形式： Max(Min)S=c1x1+c2x2+…..+cnxn s.t. a11x1+a12x2+….+a1nxn (=, )b1
20
10
10
20
Q1（25，0） 30 40
x1
解的讨论：
无界解：
例：max S=x1+x2 s.t. -2x1+x2 40 x1-x2 20 x1,x2 0
x2 50
40 30
该可行域无界，目标函 数值可增加到无穷大， 称这种情况为无界解或 无最优解。
20
10
10
20
30
40
x1
例2.1的数学模型 max S=50x1+30x2 s.t. 4x1+3x2 120 2x1+x2 50 x1,x2 0
x2 50 由 4x1+3x2 120 x1 0 40 30 x2 0 围成的区域
20
10
4x1+3x2 120
10
20
30
40
x1
x2 50
40 30
x2 50
40 30
20 可行域 10
目标函数是同约束 条件：4x1+3x2 120 平行的直线 x2 = S/30-（4/3）x1
10
20
30
40
x1
x2 50
40 30
当S的值增加时，目 标函数同约束条件： 4x1+3x2 120

第二节 线性规划解的概念、性质及图解法

5
2.线性规划的图解法 2.线性规划的图解法
例 2.4: 某工厂拥有 A 、 B 、 C 三种 类型的设备，生产甲、乙两种产品。 类型的设备，生产甲、乙两种产品。 每件产品在生产中需要占用的设备机 时数， 时数，每件产品可以获得的利润以及 三种设备可利用的时数如下表所示：
产品甲 设备A 设备B 设备C 利润（元/件） 3 2 0 1500 产品乙 2 1 3 2500
无可行解的情况
22
2.线性规划的图解法 2.线性规划的图解法
根据以上例题，进一步分析讨 论可知线性规划的可行域和最优解 有以下几种可能的情况 1.可行域为封闭的有界区域 1.可行域为封闭的有界区域 (a)有唯一的最优解； (a)有唯一的最优解； (b)有无穷多个最优解； (b)有无穷多个最优解； 2.可行域为封闭的无界区域 2.可行域为封闭的无界区域 (c)有唯一的最优解； (c)有唯一的最优解；
31
2.线性规划解的概念 2.线性规划解的概念
直线B、E的交点对应于约束条件(A)、（B）、 的交点对应于约束条件( （C）、（E）、（G）的解，即： 的解， x(7) = (20,0,5,0,75)T 20, 75) 直线C、D的交点对应于约束条件(A)、（B）、 的交点对应于约束条件( （C）、（D）、（H）的解，即： 的解， x(8) = (0,25,15,15,0)T 25,15,15, 直线C、E无交点（C、E相互平行） 无交点（ 相互平行） 直线D、E的交点对应于约束条件(A)、（B）、 的交点对应于约束条件( （C）、（D）、（E）的解，即： 的解， x(9) = (0,0,65,40,75)T 65,40,75)
26
2.线性规划解的概念 2.线性规划解的概念
Max z = 1500 x1 + 2500 x2 s.t. 3x1+2x2+x3= 65 (A) (B) 2x1+x2+x4= 40 3x2+x5= 75 (C) x1 ,x2 ,x3 ,x4 ,x5 ≥ 0 用（D）（E）（F）（G）（H） 分别表示x1 = 0、x2 = 0、x3 = 0、 x4 = 0、x5 = 0 。 这里一共有8个约束条件，其中3个等 式约束

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


i
i
MinZ e1i e2i
i
i
s.t.eβ10i-,eβ21i无 符yi 号 β限0 制β1xi
e1i , e2i 0,i 1,2,, n
还可以加上一些特定的需求.例如,要求必须过某 一点.
16
线性规划问题的应用举例(回归分析)
新标准:最小化最大绝对误差.
–整数规划问题
• 考虑短期排班的问题
–对午休换班进行建模
• 考虑每个工人
–允许工人有不同的偏好
29
套裁下料问题
例某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢
各一根。已知原料每根长7.4 m，问：应如何下料，可使所
用原料最省？
方案 1 方案 2 方案 3 方案 4 方案 5 方案 6 方案 7 方案 8
产品名称
规格要求
单价（元/kg）
甲 原材料 1 不少于 50%，原材料 2 不超过 25%
50
乙 原材料 1 不少于 25%，原材料 2 不超过 50%
35
丙
不限
25
原材料名称
1 2 3
每天最多供应量
100 100 60
单价（元/kg） 65 25 35
9
线性规划应用举例
解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。 这样我们建立数学模型时，要考虑：
x1 + x2 ≥ 70 x2 + x3 ≥ 60 x3 + x4 ≥ 50 x4 + x5 ≥ 20 x5 + x6 ≥ 30 x1,x2,x3,x4,x5,x6 ≥ 0
20
关于决策变量的选择的启示
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
11
2.2 图解法
唯一解 无穷多个最优解 无界解 无可行解
12
Example 1: A Maximization Problem
LP Forபைடு நூலகம்ulation
Max z= 5x1 + 7x2
s.t.
x1
<6
2x1 + 3x2 < 19
x1 + x2 < 8
x1, x2 > 0
13
Example 1: Graphical Solution
3
2
(7, 0)
1
12 3 4
56
78
9 10
x1
19
Example 1: Graphical Solution
Optimal Solution
x2
Objective Function
8
5x1 + 7x2 = 46
7
6
Optimal Solution
5
(x1 = 5, x2 = 3)
4
3
2
1
12 3 4
4
2.1 线性规划问题
生产计划问题
例1：某厂生产两种产品，需要三种资源， 已知各产品的利润、各资源的限量和各产品 的资源消耗系数如下表：
劳动力 设备 原材料
产品A
9 4 3
产品B
4 5 10
资源限制
360工时 200台时 300公斤
单位产品利润
70
120
（元）
5
问题：如何安排生产计划，使得获利最多？ 步骤：
7
2.1 线性规划问题
例2：高尔夫球袋
标准袋
切割印染
7/10
缝合
1/2
完成
1
检查包装
1/10
单位产品利
9
润（美元）
高档袋
1 5/6 2/3 1/4 10
资源限制 630小时 600小时 708小时 135小时
8
2.1 线性规划问题
决策变量 目标函数 约束条件
设产品标准袋、高档袋分别生产X1、X2个
O : S (0,0) 0.
26
2.4 计算机求解
某厂生产两种产品，需要三种资源，已知各 产品的利润、各资源的限量和各产品的资源 消耗系数如下表：
劳动力 设备 原材料
产品A
9 4 3
产品B
4 5 10
资源限制
360工时 200台时 300公斤
单位产品利润（
70
120
元）
27
2.4 计算机求解
1、确定决策变量：设生产A产品x1kg,B产品 x2kg
8
2x1 + x2 > 8
4
4x1 + 3x2 < 12
34
x1
36
无界解
Max z=3x1 + 4x2 s.t. x1 + x2 > 5
3x1 + x2 > 8 x1, x2 > 0
37
无界解
x2
3x1 + x2 > 8
8
Max z=3x1 + 4x2
5 x1 + x2 > 5
2.67 5
x1
2、Obj： maxZ=70X1+120X2 3、S.t.： 人力约束 9X1+4X2≤360
设备约束 4X1+5X2 ≤200 原材料约束 3X1+10X2 ≤300 非负性约束 X1≥0 X2≥0
28
2.4 计算机求解
线性规划示意图
maxZ=70X1+120X2 9X1+4X2≤360 4X1+5X2 ≤200 3X1+10X2 ≤300 X1≥0 X2≥0
Constraints Graphed x2
Feasible Region
5
4x1 - x2 > 12
4
x1 + x2 > 4
3
2x1 + 5x2 > 10
2
1
1
2
3
4
56
x1
31
Example 2: Graphical Solution
Objective Function Graphed x2
5 4
29
2.5 最小化问题
Example 2: A Minimization Problem LP Formulation
Min z=5x1 + 2x2 s.t. 2x1 + 5x2 > 10
4x1 - x2 > 12 x1 + x2 > 4
x1, x2 > 0
30
Example 2: Graphical Solution
x1 2x2 8,
x2 3,
x1 0, x2 0.
A(0,3)
B(2,3) C(4,2)
O
A(0,3)S (0,3) 12,
D(6,0)
B(2,3) : S (2,3) 18,
C (4,2) : S (4,2) 20, 当x1 4, x2 2时，Smax 20. D(6,0) : S (6,0) 18,
38
无穷多最优解
？？？？
39
问题？
作 业：
P53-54 1（不用化为整数，图解），2（选作） ，3（不用化为整数，用软件求解）
40
运筹学
Operations Research
1
第2章
线性规划图解法
2
第2章 线性规划图解法
2.1 线性规划问题 2.2 图解法 2.3 极点和最优解 2.4 计算机求解 2.5 最小化问题 2.6 特例
3
2.1 线性规划问题
在一定的约束条件（限制条件）下，使得 某一目标函数取得最大（或最小）值，当 规划问题的目标函数与约束条件都是线性 函数，便称为线性规划。 Linear programming （LP）
3
2x1 + 5x2 > 10
2
Optimal: x1 = 16/5
1
x2 = 4/5
1
2
3
4
56
x1
33
2.6 特例
无可行解 无界解 无穷多最优解
34
无可行解
Max z= 2x1 + 6x2 s.t. 4x1 + 3x2 < 12
2x1 + x2 > 8 x1, x2 > 0
35
无可行解
x2
Feasible
2
Region
1
12 3 4
56
78
9 10
x1
18
Example 1: Graphical Solution
Objective Function Line x2
8
7
(0, 5)
6
5
4
Objective Function max Z= 5x1 + 7x2 5x1 + 7x2 = 35
3
2
(9 1/2, 0)
1
12 3 4
56
78
9 10
x1
15
Example 1: Graphical Solution
Constraint #3 Graphed x2 (0, 8)
8
7
x1 + x2 < 8
6
5
4
3
2
1
(8, 0)
12 3 4
56
78
9 10
x1
16
Example 1: Graphical Solution
1、确定决策变量：设生产A产品x1kg,B产品x2kg
2、确定目标函数：maxZ=70X1+120X2 3、确定约束条件： 人力约束 9X1+4X2≤360
设备约束 4X1+5X2 ≤200 原材料约束3X1+10X2 ≤300 非负性约束X1≥0 X2≥0
6
线性规划示意图
maxZ=70X1+120X2 9X1+4X2≤360 4X1+5X2 ≤200 3X1+10X2 ≤300 X1≥0 X2≥0
Obj: maxZ=9X1+10X2
S.t. 0.7X1+
X2 ≤ 630
0.5X1+0.83333X2 ≤ 600
1X1+0.33333X2 ≤ 708
0.1X1+ 0.25X2 ≤ 135
X1≥0
X2≥0 9
2.1 线性规划问题
一般形式 目标函数：Objective Function Max(min)z=c1x1+c2x2+…+cnxn 约束条件：Constraint
7
6
Optimal Solution
5
(x1 = 5, x2 = 3)
4
3
2
1
12 3 4
56
78
9 10
x1
22
图解法求最大化问题概要
确定每个约束条件的可行解的图 确定可以满足全部约束条件的可行解的范 围 根据特殊的目标函数的值，画两条目标函 数线 通过平行移动目标函数线，使目标函数值 增大，直到可行域全在直线的一侧 在目标函数线上，使目标函数的值最大的 解就是最优解
23
二维线性规划的几何特征
若可行域非空，它是一个凸集
若线性规划存在最优解（最优解之一），它
一定在可行域的某个（某几个）顶点（极点 ）得到