当前位置：文档之家 › 运筹学 第二章 线性规划与单纯形法资料

运筹学 第二章 线性规划与单纯形法资料

  • 格式：ppt
  • 大小：4.35 MB
  • 文档页数：149

下载文档原格式

  / 149

合集下载

运筹学基本常考要点

运筹学基本常考要点
第三章 线性规划的对偶理论
1．1问题和对偶问题的对应关系：○1原问题目标函数求最大值，对偶问题目标函数求极小值；○2原问题约束条件的数目等于对偶问题决策变量的数目；○3原问题决策变量的树木等于对偶问题约束条件的数目；○4原问题的价值系数成为对偶问题的资源系数；○5原问题的资源系数成为对偶问题的价值系数；○6原问题的技术系数矩阵于对偶问题的技术系数矩阵互为专置；○7原问题约束条件问小于等于号，对偶问题约束条件为大于等于号；○8原问题决策变量大于等于零，对偶问题决策变量大于等于零。
1．2对偶单纯形法：○1构造初始单纯形表，要求检验书非负；○2判断约束条件右端项b是否全为非负，若是，则已得最优解；若b列还存在负分量，转下一步；○3选择出基变量：在b列的负分量中选取最小的分量min{bi|bi<0},该分量所在的行为主行，主行确定出基变量。○4选择入基变量：若主行中所有的元素均为非负，则问题无可行解；若主行中存在负元素，计算?=min{?j/-aij| aij<0}(这里的aij为主行中的元素)，最小比值发生的列所对应的变量即为入基变量；○5迭代运算：同单纯形发一样，对偶单纯形法的迭代过程也是一主元素为轴所进行的旋转运算。
方案的优化基本步骤：
在负检验数中找出最小的检验数，该检验数所对应的变量即为入基变量。在入基变量所处的闭合回路上，赋予入基变量最大的增量，即可完成方案的优化。在入基变量有最大增量的同时，一定存在原来的某一基变量减少为“0”，该变量即为出基变量。切记出基变量的“0”运量要用“空格”来表示，而不能留有“0”。
2．5增加一个新的变量的分析：○1将新增加变量的拘束系数向量P’反映进单纯形表，即P’=BB-1P；○2计算新增变量在最终单纯形表中的检验数?。○3若?非负则得最终形表，若为负则继续求解。

运筹学第二章-线性规划

运筹学第二章-线性规划

15
2023/10/4
.
线性规划问题的数学模型
（2）如何化标准形式
目标函数的转换
如果是求极小值即mzin cjxj ，则可将目标函数乘以
(-1)，可化为求极大值问题。
即 mza x z cjxj
也就是：令 z z，可得到上式。
变量的变换
若存在取值无约束的变量
x
，可令
j
xj xj xj
其中：xj, xj 0
10
2023/10/4
.
线性规划问题的数学模型
4. 建模步骤
(1) 确定决策变量：即需要我们作出决策或选择的量。一般 情况下，题目问什么就设什么为决策变量； (2) 找出所有限定条件：即决策变量受到的所有的约束； (3) 写出目标函数：即问题所要达到的目标，并明确是max 还是 min。
11
2023/10/4
B型 驳船 —
4 4 4
货运成本 （千元／队）
36 36 72 27
货运量 （千吨）
25 20 40 20
船只种类 拖轮 A型驳船 B型驳船
船只数
30 34 52
航线号
1 2
合同货运量
200 400
问：应如何编队，才能既完成合同任务，又使总货运成本为最小？
7
2023/10/4
.
线性规划问题的数学模型
.
线性规划问题的数学模型
6. 线性规划问题的标准形式
n
max Z cj xj j 1
特点： (1) 目标函数求最大值；
s.t
n j 1
aij
xj
bi ,i 1, 2,L, m
(2) 约束条件为等式方程， 且右端常数项bi都大于 或等于零；

《运筹学教程》胡云权 第五版 运筹学--线性规划--2单纯形法

《运筹学教程》胡云权 第五版 运筹学--线性规划--2单纯形法

x1, x2, …, xn ≥ 0
其中bi ≥0 ，i = 1, 2, …, m
右端项非负
线性规划的求解方法——图解法
Max Z= x1 + 2 x2 2 x1 + 2 x2 ≤ 8 2 x1 + 2 x2 = 8
4
Z=6 3
最优解：x1=2, x2=2
最优值：Z=6
0 x1 + 2 x2 ≤ 4
线性规划问题数学模型的一般形式
Z c1x1 c2 x2 cn xn 目标函数： max(min)
三要素
a11 x1 a12 x2 a1n xn (, )b1 约束条件： a21 x1 a22 x2 a2 n xn (, )b2 a x a x a x (, )b mn n m m1 1 m 2 2 x1 , x2 ,, xn 0
x1 , x2 ≥ 0
2
2 x2 = 4
图解法步骤：
Z=2 1 o 1 2 3 4 x1
1、建立直角坐标系；
2 、图示约束条件，判断可行域；
3 、图示目标函数和寻找最优解；
解的重要概念
可行解（或可行点） ：满足所有约束条件的向量 x ( x1 , x2 , xn ) 可行域：所有的可行解的全体
1 x1 2 x2 x3 x4 3 2 x1 x2 x , x , x , x 0 1 2 3 4
6个基，最多 C m 个 n
线性规划标准型解的概念
基解：当A中的基B取定后，不妨设B表示A中的前m列，则可 记 A (B N ) ，相应地X ( X B X N )T , 约束条件AX=b可表示为 X B ，即 X B1b B1NX ，当取 X 0 时，则 X B1b B N AX ( B N ) b N B

管理运筹学 第2章 线性规划与单纯形法

管理运筹学 第2章 线性规划与单纯形法
产，已知生产单位产品所需的设备台时及A、B两种 原材料的消耗，以及资源的限制如下表所示：
甲 乙 设备 1 1 原料A 2 1 原料B 0 1 单件利润 50（元/件） 100（元/件）
Байду номын сангаас
资源限制 300台时 400千克 250千克
问:工厂应分别生产多少个产品甲、乙才能使工厂获利最多？
设生产甲产品x1个，生产乙产品x2个
j 1
n
n aij x j (或 ， ）bi (i 1, 2, , m) s.t. j 1 x 0( j 1, 2, , n) j
n j 1 n p j x j (或 ， ）b s.t. j 1 x 0( j 1, 2, , n) j
x2 B
C z=27500=50x1+100x2 z=20000=50x1+100x2 D z=0=50x1+100x2 E
A
z=10000=50x1+100x2
x1
图2-2
解的几种可能结果
唯一最优解解 无穷多个最优解 无界解(可行域无界，常为模型遗漏了某些 必要的约束条件) 无可行解（可行域为空集，约束条件自相矛 盾,资源满足不了人们的需求）
(2) MinZ Max(Z ) 3 y1 5 x2 y2 y3
(3) 3 y1 2 x2 y2 y3 6
3 y1 2 x2 y2 y3 6
(4)在第一、第三约束左端加上松弛变量 x4,x6≥0 ，在第二约束左端减去剩余变量 x5≥0
解:
2x1+x2=400 x2=250
100
100 200 300
x2≤250

运筹学 第二章线性规划 第三讲 单纯形法

运筹学 第二章线性规划 第三讲 单纯形法
1 -2 4 2
[1] 1 2 -1↑
1 0 0 0
1 0 0 0
1 -1 -2 1
0 1 0 0
0 1 0 0
0 0 1 0
0 0 1 0
5→ 6 21
5 1 11
5 6 21/2
表中λj≥0( j=1,2,…,5), 所以最优解为X=(0,5,0,1,11 )T , 最 优值 Z=2x1－2x2－x4=－2×5－1=－11。
大值，因此原问题只要有可行解，新的线性规划问
题的最优解中人工变量的取值一定为0， 这种方
法称为大M单纯形法（简称大M法）。
2.5 单纯形法 Simplex Method
Chapter 1 线性规划 Linear Programming
大M法中加入人工变量后新的线性规划问题为
max Z’=c1x1+c2x2+…+cnxn –Mxn+1 – … –Mxn+m
【解】首先将数学模型化为标准形式
2.5 单纯形法 Simplex Method
Chapter 1 线性规划 Linear Programming
max Z 3x1 2 x 2 x3
式中x4，x5为松弛变量，x5可 4 x1 3x 2 x3 x 4 4 作为一个基变量，第一、三 x x 2 x x 10 约束中分别加入人工变量x6 、 1 2 3 5 x7 ， 目 标 函 数 中 加 入 2 x1 2 x 2 x3 1 ―Mx6―Mx7一项，得到人工 x j 0, j 1,2,,5 变量单纯形法数学模型
0 0 1
Z＝2 x1 2 x2 (6 x1 x2 ) 6 x1 x2

第2章 线性规划与单纯形法(2)

第2章 线性规划与单纯形法(2)

max z = 20 x1 + 30 x2 3 x1 + 10 x2 ≤ 150, x1 ≤ 30, x1 + x2 ≥ 40, x1 , x2 ≥ 0.
管
max z = 20 x1 + 30 x2 − Mx6 3x1 + 10 x2 + x3 = 150, x1 + x4 = 30, x1 + x2 − x5 + x6 = 40, xi ≥ 0, i = 1, 2,..., 6
管
理
运
筹
学
4
要注意到人工变量是与松弛、剩余变量不同的。 松弛变量、剩余变量它们可以取零值，也可以取 正值，而人工变量只能取零值。一旦人工变量取 正值，那么有人工变量的约束方程和原始的约束 方程就不等价了，这样所求得的解就不是原线性 规划的解了。为了竭尽全力地要求人工变量为零， 我们规定人工变量在目标函数中的系数为－M， M 这里M为任意大的数。这样为了使目标函数实现 最大就必须把人工变量从基变量中换出。如果一 直到最后，人工变量仍不能从基变量中换出，也 就是说人工变量仍不为零，则该问题无可行解。 以下讨论如何解含有人工变量的线性规划问题
• 由于不存在单位矩阵,在第1,2个约束条件加上 一个人工变量x6,x7,并在目标函数中加上-Mx6Mx7得到的线性规划问题：
max f ' = −2 x1 − 3 x2 + 0 x3 + 0 x4 + 0 x5 − Mx6 − Mx7
x1 + x 2 − x 3 + x 6 = 3 5 0, x1 − x 4 + x 7 = 1 2 5, 2 x1 + x 2 + x 5 = 6 0 0, x1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 ≥ 0 .

运筹学第二章单纯形法


方法前提：模型化为标准型
天津大学管理与经济学部 /
第二章 线性规划
例：1 Max Z=7 x1 +12x2 9 x1 +4x2≤360 2. 确定一基可行解 令 B=(P3,P4,P5)，得: x3 =360- 9 x1 -4x2 x4 =200- 4 x1 -5x2 x5 =300- 3 x1 -10x2 (1)
1 1
1 0 1 0 1 1 ,B b , 0 1 0 1 3 3
1
相应于基B 的基本解为X (0,0,1,3) , 是基本可行解。 1 2 1 2 7 5 5 5 5 1 5 1 2 B ,B ,B b , 2 1 2 1 1 3 2 - 1 - - - 5 5 5 5 5 7 1 相应于基B 的基本解为X ( ,- ,0,0) , 不是基本可行解。 5 5 / 天津大学管理与经济学部
x1 2 x2 2 x3 x4 8 2 x x x x5 x6 4 1 2 3 x3 x7 2 x1 xi 0(i 1,2,3,4,5,6,7)
天津大学管理与经济学部
Maxz 4 x1 3 x2 2 x3 x1 2 x2 2 x3 x4 8 2 x x x x5 4 1 2 3 x3 2 x1 xi 0(i 1,2,3,4,5)
正，目标函数有改进的可能 /
s.t.
4x1 +5x2
3 x1 +10x2 x1 ,…,x5≥0
+x4
= 200
+x5 = 300
天津大学管理与经济学部
第二章 线性规划

第二章 线性规划及单纯形法


标准形式
目标函数： 目标函数： 约束条件： 约束条件： Max z = c1 x1 + c2 x2 + … + cn xn 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，bi ≥0 ，
（一）一般式
Max(min)Z=C1X1+ C2X2+…+CnXn a11X1+ a12X2+…+ a1nXn ≥(=, ≤)b1 a21X1+ a22X2+…+ a2nXn ≥(=, ≤)b2 … … … am1X1+ am2X2+…+ amnXn ≥(=, ≤)bm Xj ≥0(j=1,…,n) 0( )
三、线性规划问题的标准形式 线性规划问题的标准形式
2、约束条件不是等式的问题： 约束条件不是等式的问题： 设约束条件为
ai1 x1+ai2 x2+ … +ain xn ≤ bi
可以引进一个新的变量s ，使它等于约束右边与左 边之差
s=bi–(ai1 x1 + ai2 x2 + … + ain xn ) (
一、问题提出
Ⅰ 设备A 设备 设备B 设备 调试工序 利润 0 6 1 2
例1生产计划问题
Ⅱ 5 2 1 1 每天可用能力 15 24 5
两种家电各生产多少, 可获最大利润? 两种家电各生产多少, 可获最大利润

运筹学第四版第二章线性规划及单纯形法


方案的制定受到那些现实条件制约：
确定约束条件
人力资源（劳动力）的限制： 9x1 4x2 360
设备工时的限制：
4x1 5x2 200
原材料资源的限制：
3x1 10x2 300
此外，决策变量的取值不应为负值即 x1 0, x2 0
6
综上所述，我们得到了这个问题的数学模型
目标函数 约束条件
大？
项目
Ⅰ
设备A (h)
0
设备B (h)
6
调试工序(h) 1
利润（元） 2
Ⅱ 每天可用能力
5
15
2
24
表1-2
1
5
1
12
其数学模型为：
max Z 2x1 x2
5x2 15
6xx11
2x2 x2
24 5
x1, x2 0
13
例3：捷运公司在下一年度的1～4月份的4个月内拟租用仓库
堆放物资。已知各月份所需仓库面积列于下表1-3。仓库租
借费用随合同期而定，期限越长，折扣越大，具体数字见表
1-4。租借仓库的合同每月初都可办理，每份合同具体规定
租用面积和期限。因此该厂可根据需要，在任何一个月初办
理租借合同。每次办理时可签一份合同，也可签若干份租用
面积和租用期限不同的合同。试确定该公司签订租借合同的
最优决策，目的是使所租借费用最少。
14
max Z 70 x1 120 x2
9x1 s.t. 43xx11
x1,
4x2 5x2 10x2 x2 0
360 200 300
资源约束
非负约束
其中 约束条件可记 s.t (subject to), 意思为“以… 为条件“、”假定“、”满足“之意。

运筹学之线性规划的标准型及单纯形法

下步
• 4、根据max {σj } = σK 原则确定XK 进基变量；根
据θ规则 θ = min {b’i / a’ik a’ik >0} = b’l/ a’lk 确定XL出 基变量
• 5、以a’lk 为枢轴元素进行迭代
• 6、重复第二步到第五步
30
单纯形法的进一步探讨
• 极小化问题直接求解：检验数的判别由σj ≤0
0 0 0 -13.6 -5.2
θi
90 40 30
30.76 20 100
28
Cj
CB XB b
3 X1 12 -3 X2 1 -1 X5 27
6
5 X4 6 -3 X2 1 -1 X5 9
18
3 -3 0 5 -1
X1 X2 X3 X4 X5
1 0 -2 [ 2] 0 0 1 -2 0 0 0 0 -4 3 1
• 基（ p2,p3,p4 ），令非基变量x1,x5=0，则 基变量x2=30, x3=240, x4=50,可行解（P21图）
20
• （SLP）的基可行解对应于其可行域的顶 点（极点）
• 若（SLP）有最优解，则必有最优基可行 解
• 可行基解——迭代——更优的可行基解— —最优基解（单纯形法的原理）
• 假设：约束方程组的系数矩阵A的秩为m （R(A)=m）,m<n
15
基
•基的概念：如前所述LP标准型
和式：maxZ= ∑cjxj ∑aijxj=bi xj ≥0 j=1,2,…,n
矩阵式：maxZ=CX AX=b X ≥0 约束方程的系数矩阵A的秩为m，且m<n。设 A=B+N ，B是A中mxm阶非奇异子矩阵，则称B是 LP的一个基，即：B是A中m个线性无关向量组。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2．当一项任务量确定以后，研究如何统筹安排，才 能使完成任务耗费的资源量为最小。
第一节 线性规划及其数学模型
一、实例
【例1-1】某工厂在计划期内要安排生产 Ⅰ、Ⅱ两种产品，已知生产单位产品所 需的设备台时及A、B两种原材料的消耗， 如表1-2所示。
资源 产 品 设备 原材料 A 原材料 B
表1-1
线性规划及其数学模型 图解法和解的性质 单纯形法 单纯形法的进一步讨论 线性规划应用举例
本章学习目的和要求
通过本章的学习，要求学员掌握如何建立 线性规划模型，了解线性规划的图解法，深刻 理解单纯形法的解题思路，熟练掌握其运算步 骤，并能在实际问题中加以运用。
主要研究
1．已有一定数量的人力、物力、财力资源，研究如 何充分合理地使用才能使完成的任务量最大。
n
aij x j
(, )bi
j1
x
j
0
i 1, 2, , m j 1, 2, , n
向量形式：
矩阵和向量形式：
max(min)z CX
n
Pj x j (, )b
j1
x1, , xn 0
max(min)z CX
AX (, )b
X
0
式中：X=（x1，x2，…，xn）T C=（c1，c2，…，cn） b=（b1，b2，…，bm）T Pj=（a1j，a2j，…，amj）T A=（aij）m×n
化工厂1每天排放含有某种有害物质的工业污水2万 立方米，化工厂2每天排放的工业污水为1.4万立方米。 从化工厂1排出的污水流到化工厂2前，有20%可自然 净化。根据环保要求，河流中工业污水的含量应不 大于0.2%。因此两个工厂都需处理一部分工业污水。 化工厂1处理污水的成本是1000元/万立方米,化工厂2 处理污水的成本是800元/万立方米。问:
二、 线形规划问题的标准形式
n
max z j bi
j1
x
j
0
i 1, 2, , m j 1, 2, , n
称为线性规划问题的标准形式（其中常数b1， b2，…，bm≥0（若bi < 0 ，两边乘-1））。
起源
• 运筹学问题典型模式：给出一个目标 函数及一批约束条件, 要在约束条件 的限制下求目标函数的最优值。
• 当目标函数是线性的，而且约束条件 是线性的等式或不等式时, 称为线性 规划。当其中有非线性函数时则称为 非线性规划。当须求其整数解时,则 称为整数规划。
第一章 线性规划与单纯形法
第一节 第二节 第三节 第四节 第五节
（3）有一个需要优化的目标，它也是变量的线性函 数。
具备以上三个特点的数学模型称为线性规划 （Linear Programming，简记为LP）。
线性规划模型的一般形式：
max(min)z c1x1 c2 x2 cn xn （1-1）
a11x1 a12 x2 a21x1 a22 x2
4、（1-2）为技术约束，系数aij称为技术系数
5、满足全部约束条件的变量值（x1，…xn） 称为可行解，其集合称为可行域，记为R；
6、使目标函数取得最大（最小）值的可行解 （x1，…xn）称为最优解。
采用求和符号Σ，线性规划的一般 形式可以简写为：
n
max(min)z cj x j j 1
在满足环保要求的条件下，每厂各应处理多少工业污水， 使两个工厂处理工业污水的总费用最小。
得到本问题的数学模型为：
目标函数 min z 1000x1 800x2
约束条件
x1 1
0.8x1 x2 1.6
x1 2
x2 1.4
x1 , x2 0
【课堂练习】 某厂生产P、Q两种产品，主要消 耗A、B、C三种原料，已知单位产品的原料消 耗数量等资料如表所示。
运
决
筹
胜
帷 线性规划与单纯 千
幄 之
形法
里 之
中
外
起源
• 1939年苏联康托洛维奇（ H.B.Kahtopob ）、美国希奇柯克（ F.L.Hitchcock）提出
• 1947年，旦茨格，单纯形方法 • 1951年由库恩（H.W.Kuhn）和塔克
（A.W.Tucker），非线性规划 • 到了70年代，数学规划发展迅速
Ⅰ
Ⅱ
1
2
4
0
0
4
拥有量 8台时 16 kg 12 kg
每生产一件产品Ⅰ可获利2元，每生产 一件产品Ⅱ可获利3元，问应如何安排 计划使该工厂获利最多?
用数学关系式描述这个问题
•设 x1, x2分别表示计划生产 I,II产品的数量， 称它们为决策变量。 • 生产x1,x2的数量多少，受资源拥有量的限制, 这是约束条件。即x1 2x2 8;4x1 16;4x2 12
•生产的产品不能是负值 ,即x1, x2 0
• 如何安排生产，使利润最大,这是目标。
得到本问题的数学模型为:
目标函数 max z 2x1 3x2
x1 2x2 8
约束条件
:
4 x1
16 4x2 12
x1 ,x2 0
【例1-2】靠近某河流有两个化工厂，流经第一化工厂 的河流流量为每天500万立方米，在两个工厂之间有一 条流量为每天200万立方米的支流。
问题的数学模型为：
max z 2x1 5x2
x1 2x2 8
5x1
2 x2 4 x2
20 12
x1, x2 0
上述三个问题属于同一类型的决策优化问题，它 们具有下列共同特点：
（1）每个行动方案可用一组变量（x1，…，xn）的 值表示，这些变量一般取非负值；
（2）变量的变化要受某些限制，这些限制条件用一 些线性等式或不等式表示；
产品 单位消耗 原料
A B C 产品利润
P
1 5 0 2万元
Q
2 2 4 5万元
原料总量/吨
8 20 12
要求确定P、Q的产量，使利润最大。
产品 单位消耗 原料
A B C 产品利润
P
1 5 0 2万元
Q
原料总量/吨
2
8
2
20
4
12
5万元
解：设P、Q的产量分别为x1，x2，即决策变量 目标函数？ 约束条件？
a1n xn (, )b1 a2n xn (, )b2
（1-2）
am1x1 am2 x2 amn xn (, )bm
x1, x2 , , xn 0
（1-3）
1、变量x1，x2，…，xn称为决策变量
2、目标函数中变量系数cj称为价值系数
3、bi称为右端常数，约束条件（1-3）称为非 负约束