当前位置：文档之家 › 01线性规划及单纯形法2

01线性规划及单纯形法2

  • 格式：ppt
  • 大小：1.95 MB
  • 文档页数：75

下载文档原格式

  / 75

合集下载

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

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

第一章
工厂需要的原棉存放在三个仓库中，现将原棉运往工 厂以满足工厂生产的需求。已知原棉运到各个工厂的单位 运费如表所示。问使总运费最小的运输方案？
仓库\工厂
1 2 3 需求
1
2 2 3 40
2
1 2 4 15
3
3 4 2 35
库存
50 30 10
2．线性规划数学模型
解：设xij为i 仓库运到 j工厂的原棉数量(i =1,2,3
1．线性规划介绍
第一章
线性规划研究的主要问题： 有一定的人力、财力、资源条件下，如何 合理安排使用，效益最高?
某项任务确定后，如何安排人、财、物， 使之最省?
2．线性规划数学模型
第一章
例1 美佳公司计划制造I，II两种家电产品。已知各 制造一件时分别占用的设备A、B的台时、调试时间及A、 B设备和调试工序每天可用于这两种家电的能力、各售出 一件时的获利情况如表I—l所示。问该公司应制造A、B两 种家电各多少件，使获取的利润为最大？
第一章
j =1,2,3)
minZ= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33 x11 +x12+x13 x21+x22+x23 x31+x32+x33 50 30 10 40
st.
x11 +x21+x31 =
x12 +x22+x32 =
x13 +x23+x33 = xij 0
15
35
2．线性规划数学模型
第一章
练习4 连续投资10万元 A：从第1年到第4年每年初投资，次年末回收本利1.15； B：第3年初投资，到第5年末回收本利1.25，最大投资4万元； C：第2年初投资，到第5年末回收本利1.40，最大投资3万元； D：每年初投资，每年末回收本利1.11。 求：使5年末总资本最大的投资方案。 分析： A 1 x1A 2 x2A x2C x1D x2D x3D x4D x5D 3 x3A 4 x4A 5

第二章 图解法与单纯形法

第二章 图解法与单纯形法

表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)目标函数的直线怎样平行移动

1-1线性规划问题及模型

1-1线性规划问题及模型
史新峰
西安邮电大学 现代邮政学院
Xi'an post and telecommunications university modern post College
第一章 线性规划与单纯形法
1.1线性规划问题及模型 运 筹 学
主要内容
01 线性规划问题
运
02 线性规划模型及特征
筹
学
一 线性规划问题
二 线性规划模型
2.线性规划模型的一般形式
运 筹 学
二 线性规划模型
简写式
运 筹 学
n
max（或 min）Z c j x j j 1
s.t.
n
aij x j
(或 ，)bi
j1
xj 0
i 1,，m j 1,, n
二 线性规划模型
运向量式 筹 学
max（或 min ） Z CX
星期 需要人数 星期 需要人数
运
一
300
五
480
筹
二
300
六
600
学
三
350
日
550
四
400
应如何安排每天的上班人数，使商场总的营业员最少。
一 线性规划问题
在上班 周 周 周 周 周 周 周 一二三四五六日
开始上班
周一
周二
运
周三
筹
周四
学
周五 周六
周日
一 线性规划问题
解：设xj(j=1，2，…，7)为休息2天后星期一到星
期日开始上班的营业员，则这个问题的线性规划模型为
min Z x1 x2 x3 x4 x5 x6 x7
x1 x4 x5 x6 x7 300
x1

第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 .

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

第二章 线性规划与单纯形法
max z =2x1+3x2 2x1+2x2+x3=12 x1+2x2+x4=8 4x1+x5=16 4x2+x6=12 x1-6≥0
图解法
第2节 解
例8：求下述线性规划的所有基解、基可行 解及最优解。 max z =3x1+x2+3x3 x1+x2+x3＝2 x1+2x2+4x3＝6 x1，x2，x3≥0
第1节 线性规划问题及其数学模型
要求：将下列线性规划问题转化为标准型。 例4：min z =x1+2x2+3x3 -2x1+x2+x3≤9 -3x1+x2+2x3≥4 3x1-2x2-3x3=-6 x1≤0，x2≥0，x3取值无约束
第1节 线性规划问题及其数学模型
例4： x x , x x xz , z 解：令 1 13 3 3 max z′=x1′-2x2-3x3′+3x3〞+0x4+0x5 2x1′+x2+x3′-x3〞+x4=9 3x1′+x2+2x3′-2x3〞-x5=4 3x1′+2x2+3x3′-3x3〞=6 x1′，x2，x3′，x3〞，x4，x5≥0
第3节 图解法
三、图解法解的类型 唯一最优解：仅有一点使目标函数值取得最大 （小）值 无穷多（多重）最优解：线段（射线）上任意 一点都使目标函数值取得相同的最大（小）值 无界解：可行域无界，目标函数值可以增大到 无穷大 无可行解：可行域为空集 无界解和无可行解统称为无最优解

目标函数求最大值 函数约束条件全为等式 决策变量全为非负 函数约束条件右端项全为非负

水资源系统分析第2章线性规划与单纯形法ppt课件

水资源系统分析第2章线性规划与单纯形法ppt课件
原材料的合理利用等生产组织问题。 – 二战期间开始应用于军事规划
(英、美)。1947年， Dantzig 美国空军----斯坦福大学教授，
提出了单纯形法求解线性规划问题。 “线性规划之父”。
精选编辑ppt
10
Dantzig 「配餐问题」
美国空军为了保证士兵的营养，规定每餐的食 品中，要保证一定的营养成份，例如蛋白质、 脂肪、维生素等等，都有定量的规定。
x11,x12…x23≥0
精选编辑ppt
8
1.2 数学模型
规划模型的要素 决策变量：规划的措施、方案，是需要 确定的未知变量。 目标函数：规划的目的和用要求 约束条件：决策变量的取值范围 线性目标和约束组成线性规划模型
精选编辑ppt
9
产生和发展
– 19世纪，法国科学家Fourier提出线性规划。 – 1939年苏联数学家康托维奇：机器负荷分配、
这些营养成份可以由各种不同的食物来提供 (例如牛奶提供蛋白质和维生素，黄油提供蛋 白质和脂肪，胡萝卜提供维生素，等等)。
由於战争条件的限制，食品种类有限，又要尽
量降低成本，於是在一盒套餐中，如何决定各
种食品的数量，使得既能满足营养成份的需要，
又可以降低成本----最佳的配餐方案。
精选编辑ppt
11
线性规划一般形式:
第二章 线性规划
精选编辑ppt
1
1 一般数学模型
1.1 问题的提出
例1 长度100米的钢材，需要截成3 米、8米、11米短材。如何截取使剩料 最少？要求：3米的最少2根，最多9根； 8米的最少4根，11米的最少1根，最多 8根。
精选编辑ppt
2
例2 某灌区在年初估算可供水量为360万m3, 计划灌溉小麦、玉米两种.总面积1000hm2,

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

第一章线性规划及单纯形法6.6单纯形法小结Drawingontheexampl,thetwoaxisinterceptsareplotted.2、求初始基可行解并进行最优性检验Cj比值CBXBb 检验数?jx1x2x3x4x53500081010012020103634001x3x4x5000035000令非基变量x1=0，x2=0，找到一个初始基可行解：x1=0，x2=0，x3=8，x4=12，x5=36，σj＞0，此解不是最优（因为z=3x1+5x2+0x3+0x4+0x5)即X0=(0,0,8,12,36)T，此时利润Z=03、寻找另一基可行解Cj比值CBXBb检验数?jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9主元首先确定入基变量再确定出基变量检验数?j81010060101/2012300-21x3x2x5050-30300-5/20Cj比值CBXBb检验数?jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9令x1=0，x4=0，得x2=6，x3=8，x5=12，即得基可行解X1=(0,6,8,0,12)T此时Z＝30σ1=3＞0，此解不是最优迭代4、寻找下一基可行解Cj比值CBXBb检验数?jx1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4检验数?j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1令x4=0，x5=0，得x1=4，x2=6，x3=4，即X0=(4,6,4,0,0)T?j＜0最优解:X=(4,6,4,0,0)T最优值:Z=42小结：单纯形表格法的计算步骤①将线性规划问题化成标准型。

②找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。

2 最优化方法-线性规划-单纯形法


自由变量 松弛(slack)/盈余(surplus)变量；
例5. 化成标准形
等 价 表 示 为
基本解与基变量
其中 满秩假定： m×n矩阵A满足m<n，且A的行向量线性无关 • 在满秩假定下，方程组Ax=b总有解，且至少有一个基本 解
定义： 给定含有n个变量，m个方程的线性方程组Ax=b， 设B是由A 的列组成的任一非奇异m×m子阵，则如果置x 的所有与B无关的n-m个分量为零后，所得方程组的解是 Ax=b关于基B的基本解(basic solution) ，称x中与基B对应 的分量为基变量(basic variables)
进基变量：最小相对费用系数规则；出基变量：最小指标规则！
例1.
化标准形
得标准形的初始表格/第一张单纯形表
转 轴
0
↓
转 轴
-2 ↓
转 轴
-4 ↓ -27/5
最优解： 最优值：
原问题的极大值：
退化(degenerate)与循环(cycling)
◎退化问题
⊙ 单纯形法可能出现循环！ ⊙ 实际中经常碰到退化问题，但很少出现循环 ⊙ 避免出现循环的措施：摄动法、Bland法则、字典序法
以
为转轴元，转轴后即得新基对应的数据！
例1
a2进基，计算y2. 计算表格如下：
计算
a1进基，计算y1. 得如下表格：
最优值：
最优解：
利用两阶段单纯形过程求解
实用优化方法
线性规划：单纯形法
线性规划
线性规划：目标函数是线性的，约束条件是 线性等式或不等式
线性规划的历史
• 渊源要追溯到Euler、Liebnitz、Lagrange等
• George Dantzig, Von Neumann(Princeton)和 Leonid Kantorovich在1940’s创建了线性规划

数学建模 - 第二章 线性规划及单纯形法

p j a1 j , a2 j ,, amj 为A的第j列向量
T
max s.t.
p
j 1
n
j
xj b
x0
13
§2 线性规划问题的图解法
max s.t.
z cx Ax b x0
(1) (2) (3)
定义1 在LP 问题中，凡满足约束条件(2)、(3)的 解 x = (x1,x2,…,xn)T 称为LP 问题的可行解， 所有可行解的集合称为可行解集（或可行域）。 记作 D={ x | Ax = b ,x≥0 }。 定义2 设LP问题的可行域为D，若存在x*∈D，使得 对任意的x∈D 都有c x*≥c x，则称x*为LP 问题
设 xj 没有非负约束，若 xj ≤0，可令 xj = - xj’ ，
则 xj’ ≥0；
又若 xj 为自由变量，即 xj 可为任意实数，
可令 xj = xj’ - xj’’，且 xj’ , xj’’ ≥0
11
第二章
线性规划及单纯形法
max z’= x1-2x2+3x4- 3x5 s.t. x1+x2+x4-x5+x6=7 x1-x2+x4-x5-x7=2 3x1-x2-2x4+2x5=5 x1,x2,x4,x5,x6,x7≥0
x2
2x1 x2 2
x1 4x2 4
max z = 2x1 + 2x2 s.t. 2x1 – x2 ≥ 2 -x1 + 4x2≤ 4 x1，x2 ≥ 0
Note:
可行域为无界区域，
目标函数值可无限
增大，即解无界。
(１,0)
O
A
x1
称为无最优解。

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


标准形式
目标函数： 目标函数： 约束条件： 约束条件： 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
两种家电各生产多少, 可获最大利润? 两种家电各生产多少, 可获最大利润
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

s
.t.
n j 1
aij
x
j
bi
x
j
0
(i 1,2,, m) ( j 1,2,, n)12.12.2020 Nhomakorabea9
(LP)一般形式向标准形式的转化
(LP)一般形式向标准形转化的情况：
① 目标函数是求极小值； ② 约束条件为不等式“”的情形（松弛变量，例2）； ③ 约束条件为不等式“” 的情形（剩余变量，例3）； ④ 取值无约束的变量； ⑤ 某个变量 xj 0
从满足约束条件（2）和非负条件 （3）的方程组中，找到使目标函 数（1）取得最大值的解。
可行解和可行域 满足约束和非负条件的解x。
最优解
基、基向量、基变量 设A=(aij)mn，r(A) = m，称A的 一个m阶满秩子矩阵B称为(LP) 问题的的一个基。
基解 由基矩阵B确定的m个基变量， 并上非基变量取0的解。
0501 5 0103 0103
x B (3 ,3 ,4 )T ,x (3 ,3 ,0 ,4 ,0 )T
12.12.2020
12
§2 图解法求最优解
什么时候用图解法？ (LP)模型仅含两个决策变量。
求解方法和根据：
① 根据约束画出求解区域，一般为第一象限的凸多边形 (有界或无界)，标记出顶点坐标；
x1 x1
2 x
x
2
2 5
2
x1 0 , x 2 0
x2
l1
D(0,2) O
C(1,4)
l3
l2
A(2,0)
B(4,1)
x1
最大值点 x* = (1,4), Zmax = 3；最小值点 x* = (4,1), Zmin = 3；
12.12.2020
15
图解法的其他情形 – 无穷多最优解
无穷多最优解(书，P16，见下图) 问题1：什么情况下发生？
基(本)可行解 同时是可行解的基解。
可行基
12.12.2020
11
利用初等变换求基可行解
例4. 教材14页，列出(LP)问题的全部基，基解、基可行解并指 出最优解。
问题: I) 如何判断一个解是基可行解；
II）表1-1中为何少了两行？ 利用p1,p2, p4 求基解的过程
2201 2 2006 1003 B (p 1 p 2 p 4 b )40116 40116 0014
② 求目标函数的梯度：设目标函数是 z=c1x1+c2x2，则 n = grad z = (c1,c2) 为等值线c1x1+c2x2= h的法线方向，沿n的方向 函数值增加的最快，沿-n方向函数值减少的最快。
③ 移动等值线 c1x1+c2x2= h 在区域顶点或边界达到最大最小值。
书中的方法是把目标函数z当做参数处理。
线性规划问题数学模型的定义
线性规划模型组成的三要素：
① 决策变量 ② 目标函数 ③ 约束条件
定义1 在线性规划数学模型中，如果决策变量为可控的连 续变量，目标函数和约束条件都是线性的，称这类模型为 线性规划问题的数学模型。
问题：例一中的问题是否为线性规划模型？
12.12.2020
6
线性规划问题数学模型的一般形式
max z 3 x 1 3 x 2
2 x 1 2 x 2 12
s.t.
4
x1
16 5 x 2 15
x 1 0 , x 2 0
x2
x1 = 4
D
C(3,3)
x2 = 3
B(4,2)
O
A
2x1 + 2x2
x1 12
问题2：这个最优解如何表示？
12.12.2020
16
图解法的其他情形 – 无界解(无最优解)
s.t.
a21x1
a22x2
a2nxn
,b2
或
am1x1
am2x2 amnxn ,bm xj 0,j 1,2,n
n
max(min)z cj xj j1
s.t.
n j1
aij
x
j
(,)bi
xj 0
(i 1,2,,m) ( j 1,2,,n)
12.12.2020
7
线性规划数学模型向量和矩阵形式
b2 bm
a11 Aa 21
a12 a22
a1n a2n
一般要 r(A求 )m
am1 am2 amn
12.12.2020
8
线性规划问题的标准形式
什么是(LP)问题的标准形式？ 满足如下条件：
① 目标函数是求极大值； ② 约束条件全为等式；
③ bi和xj全为非负数。
n
max z c j x j j 1
(LP)向量形式
max(min) z cx
n
s .t.
p
j 1
jxj
(, )b
x 0
(LP)矩阵形式
max(min) z cx Ax (, )b
s.t.x 0
c (c1 , c2 , , cn )
x1
a1 j
b1
x
x2 xn
, p j
a2 j amj
, b
求下面规划问题的最优解。
min z 2 x1 x 2
x1 x2 1
s.t.
x
1
3x2
3
x1 0 , x 2 0
x2
x1 3x2 -3
n
B(0,1) x1 x2 1
n
O A(1,0)
x1
问题1：如果目标函数是求极大，是否有最优解？ 问题2：能否定量说明 z 是无下界的？
12.12.2020
17
图解法的其他情形 –无可行解
求下面规划问题的最优解。
12.12.2020
13
一般情况求解区域的确定
约束一般都可化成 ax1+bx2+c = 0 (a > 0，b 0)的形式[特殊情形？]
12.12.2020
14
一个用图解法求极值的例子
用图解法求如下线性规划问题的极值。
max(min) z x1 x 2
2 x1 x2 2
s.t.
⑥ 问题：某个变量有上下界限制，比如l xj u，如何处理？
例3. 见书P12。
12.12.2020
10
线性规划问题解的若干重要概念
n
(LP)max z cj xj
(1)
j1
s.t.
n j1
aij
x
j
bi
xj 0
(i 1,2,,m) (2) ( j 1,2,,n) (3)
线性规划问题的任务
关于幻灯片中的数学符号：
➢ 小写斜体字母表示实数，如a,b,c,x,x1,y,z等
➢ 小写黑体字母表示向量，如x,y,z等
➢ 大写黑体字母表示矩阵，如 A, B,C等
线性规划(LP)数学模型的一般形式
max z c (1 x 1 m c 2 x 2 i n )c nx n
a11x1 a12x2 a1nxn , b1