当前位置：文档之家 › 第一章 线性规划及单纯形法教材课程

第一章 线性规划及单纯形法教材课程

  • 格式：ppt
  • 大小：1.39 MB
  • 文档页数：85

下载文档原格式

  / 85

合集下载

PPT】第 1 章 线性规划模型和单纯形法

PPT】第 1 章 线性规划模型和单纯形法


2 x4
0
3 X3
117.0732
4x1 x3 2x4 2x5 2x6 0 4x3 x5 2x6 2x7 2x8 0
4 X4 5 X5 6 X6
0 52.0325
0
4
x5
x7
2x 8 2x9
0
x j 0, j 1, 2, ,9
7 X7 8 X8 9 X9
208.1301 0 0
(5x1 4x2 ) (9x1 10x2 ) 60
目标函数线性化。产品的产量y等价于
整理得到线性规划模型
max Z y
y
1 2
x1
y
1 3
x2
y
1 2
x1 ,
y
1 3
x2
59
x1 x1
4 x2 960 10 x2 1440
－4 x1－6 x2 60
4 x1 6 x2 60
42
x1 x1
2 x2 5x2
4x3 200 x3 360
2x1 3x2 5x3 300
x1 0，x2 0，x3 0
最优解X=(50,30,10);Z=3400
产品 甲 乙
资源
设备A 设备B 材料C 材料D 利润（元/ 件）
31 22 45 23 40 30
丙 现有资 源
2 200 4 200 1 360 5 300 50
运筹学
Operations Research
第 1 章 线性规划模型和单纯形法
Linear Programming and Simplex Method
1.1 LP的数学模型及标准型 1.2 图解法 1.3 单纯形法
1. 理解什么是线性规划模型，掌握线性规划在管 理及生产中的应用 2. 掌握线性规划数学模型的组成及其特征 3. 清楚线性规划数学模型的一般表达式。
第一章线性规划建模及单纯形法ppt课件

第一章线性规划建模及单纯形法ppt课件

ai1 x1+ai2 x2+ … +ain xn+s = bi 11
1.线性规划的概念
当约束条件为
ai1 x1+ai2 x2+ … +ain xn ≥ bi
时，类似地令
s=(ai1 x1+ai2 x2+ … +ain xn)- bi 显然，s 也具有非负约束，即s≥0，
这时新的约束条件成为
ai1 x1+ai2 x2+ … +ain xn-s = bi
生产所占用的机时数不能超过65，于是我
们可以得到不等式：3 x1 + 2 x2 ≤ 65； 对设备B，两种产品生产所占用的机
时数不能超过40，于是我们可以得到不等
式：2 x1 + x2 ≤ 40； 3
1.线性规划的概念
对设备C，两种产品生产所占用的
机时数不能超过75，于是我们可以得到
不等式：3x2 ≤75 ；另外，产品数不可 能为负，即 x1 ,x2 ≥0。同时，我们有
4x1+2x2’-2x2”+3x3-9x4-x6= 39 -6x2’+6x2”-2x3-3x4-x7 = 58 x1 ,x2’,x2”,x3 ,x4 ,x5 ,x6 ,x7 ≥ 0
20
2.线性规划的图解法
线性规划的图解法(解的几何 表示)对于只有两个变量的线性规 划问题，可以二维直角坐标平面 上作图表示线性规划问题的有关 概念，并求解。图解法求解线性 规划问题的步骤如下：
x2=25，最优值z
划 =
的 最 优 解 x1=5 、
70000。即最优方
案为生产甲产品5件、乙产品25件，
可获得最大利润为70000元。
第1章-线性规划及单纯形法-课件(1)

第1章-线性规划及单纯形法-课件(1)


✓ x1、 x2 0
IБайду номын сангаас
设备
1
原材料 A 4
原材料 B 0
利润
2
II 资源限量
2 8 台时
0
16kg
4
12kg
3
第一章 线性规划及单纯形法 运筹学
该计划的数学模型
✓ 目标函数 ✓ 约束条件
Max Z = 2x1 + 3x2
x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0
x1
✓ 美国航空公司关于哪架飞机用于哪一航班和哪些 机组人员被安排于哪架飞机的决策。
✓ 美国国防部关于如何从现有的一些基地向海湾运 送海湾战争所需要的人员和物资的决策。
✓ ……
第一章 线性规划及单纯形法 运筹学
二、线性规划问题的数学模型
✓ 1、一般形式 ✓ 2、简写形式 ✓ 3、表格形式 ✓ 4、向量形式 ✓ 5、矩阵形式
1、唯一最优解
max Z 2 x 1 3 x 2
2 x 1 2 x 2 12 ⑴
x1 4 x1
2 x2
8 16
⑵ ⑶
4 x 2 12 ⑷
x 1 0 , x 2 0
1 234 56
x2
⑶ ⑷
(4，2)
0 1 234 5678
x1
⑵
⑴
✓最优解：x1 = 4,x2 = 2，有唯一最优解Z=14。
第一章 线性规划及单纯形法 运筹学
三、线性规划模型的标准形式
✓ 1、标准形式 ✓ 2、转换方式
第一章 线性规划及单纯形法 运筹学
1、标准形式
maZx cjxj
xj
aijxj 0
bi
第一章线性规划与单纯形法ppt课件

第一章线性规划与单纯形法ppt课件


x2
解，也不存在最优解。
x11.5x2 8
目 标 函 数 m ax z 2 x1 3x2
4x1=16
x1 2 x2 8
约
束
条
件
:
4 x1
16 4x2 12
3
4x2=12
x1 , x2 0
原可行 域
0
无可行解
增加一个新的约束条件
x1+2x2=8
8
x1
x11.5x28
23
经营者提供商品或者服务有欺诈行为 的，应 当按照 消费者 的要求 增加赔 偿其受 到的损 失，增 加赔偿 的金额 为消费 者购买 商品的 价款或 接受服 务的费 用
Q3
x1 , x2 0
3
Q2
可行域
4x2=12
0
x1+2x2=8
x1
4
8
无穷多最优解（多重最优解）
20
经营者提供商品或者服务有欺诈行为 的，应 当按照 消费者 的要求 增加赔 偿其受 到的损 失，增 加赔偿 的金额 为消费 者购买 商品的 价款或 接受服 务的费 用
x2
可行 域
max z 2 x1 3x2
8—
x1 + x2 5
7—
x2 = -2x1 6 —
5— 4— 3—
x1、 x2 0
6x1 +2x2 24
6x1+ 2x2=24 x1+ x2=5
5
x2
15
最优解
2—
(3.5,1.5)
1—
x1 + x2 5
0
|| | | || | | | 12 3 4 5 6 7 8 9
x1
第1章 3 线性规划及单纯形法

第1章 3 线性规划及单纯形法


B2=（p1 ，p2 ，p4） B4=（p1 ，p3 ，p4） B6=（p1 ，p4 ，p5） B8=（p2 ，p3 ，p5） B10=（p3 ，p4 ，p5）
经计算可知：对应A系数矩阵可找出8个
基（除B4 、B8 以外都是基）。
AX b
1 2 1 0 0x1 b1
4
0
0
1
0x2
LP的可行域一定是凸集，但是凸集不
一定成为LP的可行域，而非凸集一定 不会是LP的可行域。
线性规划的基本可行解与可行域的顶
点是一一对应的
在可行域中寻找LP的最优解可以转
化为只在可行域的顶点中找，从而把一 个无限的问题转化为一个有限的问题。
若已知一个LP有两个或两个以上最
优解，那麽就一定有无穷多个最优解。
1、 凸集——设K是n维欧氏空间 的一个点集，若任意两点X（1）∈K， X（2）∈K的连线上的一切点：
αX（1）+（1-α）X（2） ∈ K
（0<α<1），则称K为凸集。
凸集 非凸集
2、 凸组合 设X（1）,X（2）, … ,X（k）是n维欧氏
空间中的K个点,若存在k个数μ1, μ2 , … ,μk ,满足
注意，线性规划的基本解、基本可行解和可行 基只与线性规划问题标准形式的约束条件有关。
32100
A = （P1 ,P2 ,P3 ,P4 ,P5）= 2 1 0 1 0
03001
A矩阵包含以下10个3×3的子矩阵：
B1=（p1 ，p2 ，p3 ） B3=（p1 ，p2 ，p5） B5=（p1 ，p3 ，p5） B7=（p2 ，p3 ，p4） B9=（p2 ，p4 ，p5）
性方程组：
3 x1 + 2 x2 = 65 2 x1 + x2 = 40 3 x2 + x5 = 75 得到x1 =15，x2 = 10，x5 = 45，对应的基本解： x（3）=(x1 ，x2 ，x3 ，x4 ，x5)T=(15，10，0，0，
线性规划图解法和单纯形法PPT课件

线性规划图解法和单纯形法PPT课件


aij x j bi
aij x j xni bi
xni 0 称为剩余变量
常量 bi＜0 的变换:约束方程两边乘以（－1）
线性规划问题的数学模型
例1.6 将下列线性规划问题化为标准形式
min Z 2 x1 x2 3 x3
5 x1 x2 x3 7
x1 x2 4 x3 2 3 x1 x2 2 x3 5
36 36 72 27
货运量 （千吨）
25 20 40 20
船只种类 拖轮 A型驳船 B型驳船
船只数 30 34 52
航线号 1 2
合同货运量 200 400
问：应如何编队，才能既完成合同任务，又使总货运成本为最小？
线性规划问题的数学模型
解： 设：xj为第j号类型船队的队数（j = 1，2，3，4），
Chapter1 线性规划
(Linear Programming)
本章主要内容：
LP的数学模型 图解法
单纯形法的进一步讨论－人工变量法 LP模型的应用
线性规划问题的数学模型
1. 规划问题 生产和经营管理中经常提出如何合理安排，使人力、 物力等各种资源得到充分利用，获得最大的效益， 这就是规划问题。
AX ( ) B
X
0
其中： C (c1 c2 cn )
a11 a1n
A
am1 amn
x1
X
xn
b1
B
bm
线性规划问题的数学模型
6. 线性规划问题的标准形式
n
max Z cj xj j 1
s.t
n
aij x j
j 1
bi
i 1, 2, , m
即 max z z c j x j
第1章 线性规划单纯形法aPPT课件

第1章 线性规划单纯形法aPPT课件

5
线性规划问题解的概念
• 基解：将上述线性规划约束方程AX＝b改写如
下形式，即
(B，N)(XB，XN)T＝b
从而有 BXB＝b－NXN
令
XN＝0
得到线性方程组 BXB＝b
由此得到XB＝(x10,x20个基
本解
X0＝(XB, XN)T＝(x10,x20,…,xm0,0,0, …,0)T。
21
• 定理1 若线性规划存在可行域，则其可行域 R={X|AX=b,X≥0}是凸集。
证明 有
则 且
即 故
X (1) R , X ( 2 ) R , 及 0 a 1 AX (1) b 且 X (1) 0 AX ( 2 ) b 且 X ( 2 ) 0 X aX (1) (1 a ) X ( 2 ) 0 AX A ( aX (1) (1 a ) X ( 2 ) )
• 基向变变量量量 ； ，： 与记之相 为对X应B应的=(的向x1,变量x2,量P…1,,xx1Pm,x2),2T…,…；, ,Pxmm称称为为基基 • 非基变量：其余的向量为非基向量，记
为非基N=变(P量m+，1,, 记Pm为+2,X…N,=P(xn)m；+1其,xm余+2,的…变,xn量)T 为。
可行域的极点 目标函数等值线： 一组平行线
代数概念
满足一个等式约束的解 满足一个不等式约束的解 满足一组不等式约束的解
基解 基可行解 目标函数值等于一个常 数的解
19
线性规划问题的几何意义
• 凸集 如果集合K中任意两个点的连线上的所有点也属 于这个集合，那么称K为凸集。
• 设K是n维欧氏空间的一个点集，若任意两点X(1)∈K, X(2)∈K均有
第1章 线性规划－单纯形法
运筹学基础及应用第五版胡运权第一章

运筹学基础及应用第五版胡运权第一章

问题的提出 某企业计划生产Ⅰ、Ⅱ两种产品。这两种产品都要分别在A、B、C、D四种不同设备上加工。生产每件产品Ⅰ需占用各设备分别为2、1、4、0h，生产每件产品Ⅱ，需占用各设备分别为2、2、0、4h。已知各设备计划期内用于生产这两种产品的能力分别为12、8、16、12h，又知每生产一件产品Ⅰ企业能获得2元利润，每生产一件产品Ⅱ企业能获得3元利润，问企业应安排生产两种产品各多少件，使总的利润收入为最大。
xi 0
aij
aLj
xL 0
i
∴ P1 , P2,······,PL-1, PL+1,······ Pm, Pj 线性无关。
∴ X1 也为基本可行解。
四、最优性检验和解的判别
令
，其中 随基的改变而改变
X1 = (x1 0- a1j ,x2 0- a2j ,···,xm 0- amj ,0,···,,···,0)T
必要性：X非基本可行解 X非凸集顶点 不失一般性，设X=(x1,x2,······,xm,0,0,······,0)T，为非基本可行解， ∵ X为可行解，
证：等价于 X非基本可行解X非凸集顶点
又 X是非基本可行解， ∴ P1,P2,······,Pm线性相关，即有 1P1+2P2+······+mPm=0， 其中1，2，······，m不全为0，两端同乘≠0，得 1P1+2P2+······+mPm=0，······（2）
∵ >0, 1->0 ，当xj=0， 必有yj=zj=0
∴
pjyj =
j=1
n
pjyj=b ······(1)
j=1
r
pjzj =
j=1
n
pjzj=b ······(2)
运筹学Chapter线性规划及其单纯形法PPT课件

运筹学Chapter线性规划及其单纯形法PPT课件


st.4x1x1 20x2x2816
0x1x,1x2
4x2 0
12
第4页/共61页
例2
捷运公司拟在下一年度的1～4月份的4个月内租用仓库堆放物资。已知各月份 所需仓库面积数。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字如 表1-2所示。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。 因此，该厂可根据需要，在任何一个月初办理租借合同。每次办理可签一份，也可 签若干份租用面积和租借期限不同的合同，试确定该公司签定租借合同的最优决策， 目的是使所付租借费用最小。
D：每年初投资，每年末回收1.11。
求：5年末总资本最大
目标函数： 约束条件
组成线性规划模型的三个要素
max Z＝2x1＋x2 56xxxx11＋，21≤＋xx12225≤≥x052≤24
（3）约束条件： 指决策变量取值时受到的各种资源条件的 限制，通常用等式或不等式来表达。 其中，xij≥0叫做非负约束。
一是严格的比例性，即某种产品 对资源的消耗量和可获得的利润与其 生产数量严格成比例。
二是可迭加性。即生产多种产品
对某种资源的消耗量等于各产品对该
2021/6/1
项资源的消耗量之和。
7
第7页/共61页
二、线性规划模型的一般形式
假设线性规划问题中含有n个变量，m个约束方程。则
线性规划模型的一般形式为：
令非基变量xm+1＝xm+2＝…＝xn＝0，得
可解得m个基变量的唯一解为：
a11 a12
2021/6/1
3
第3页/共61页
24021/6/1
产品 资源
设备A（h） 设备B（h） 设备C（h） 设备D（h） 利润（元/件）
线性规划及单纯形法PPT课件

线性规划及单纯形法PPT课件


图
1.建立平面直角坐标系，标出坐标原点,
解
坐标轴的指向和单位长度。
法
2.对约束条件加以图解，找出可行域。 3.画出目标函数等值线。
4.结合目标函数的要求求出最优解。
图
max z 2 x1 x 2
5 x 2 15
s
.t
.
6 x
x
1
1
x
2
2
x2
5
24
x1 , x 2 0
(1.1a) (1.1b)
xj(j1,2, ,n) 称为决策变量
非负约束
cj(j1,2, ,n) 称为价值系数或目标函数系数
bi(i1,2, ,m) 称为资源常数或约束右端常数
aij0 (i=1 ,..,m ;j=1 ,..,n ) 称为技术系数或约束系数
概 念 和 模 型
紧缩形式：
n
max（或min）Z c j x j j 1 n
若线性规划问题的可行域存在， 则可行域是一个凸集。
若线性规划问题的最优解存在， 则最优解或者最优解之一（如果 有无穷多的话）一定是可行域的 凸集的某个顶点。
解题思路是，先找出凸集的任一 顶点，计算在顶点处的目标函数 值。
线性 规划 及单 纯形
法
❖ 线性规划问题及数学模型 ❖ 图解法 ❖ 单纯形法原理 ❖ 单纯形法计算步骤 ❖ 单纯形法进一步讨论 ❖ 数据包络分析 ❖ 其他应用例子
§3单 纯 形 法 原 理
线性规划问题的解的概念 凸集及其顶点 几个基本定理
线性规划问题
n
max z c j x j j 1
s.t.
n j 1
a ij x j
bi
(i 1,.., m )
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第13页
②小于等于约束条件转化为等号约束
2x1+3x2-4x3≤5
引进松弛变量(Slack variable) x4≥0
广 西
2x1+3x2-4x3+x4=5
工 学
如果有一个以上小于等于约束，要引进不同的松弛变量。 院
例如：
财 政
2x1+3x2-4x3≤5
经 济
例如，对于以下两个线性规划问题
财 政
Max z=2x1+3x2 s.t. x1+x2≤3
Min z’=-2x1-3x2
经 济
s.t. x1+x2≤3
系
x2≤1
(A)
x2≤1
(B)
冯 金
x1, x2≥0
x1, x2≥0
丽
它们的最优解都是x1=2, x2=1，但(A)的最大化的目标函数值为max z=7，(B)的最小化的目标函数值为min z’=-7
第4页
例：美佳公司的生产计划问题
美佳公司生产Ⅰ、Ⅱ两种家电，单件利润分别为2
千元、1千元。两种产品生产过程中均要使用A 、B和C 广
三种原材料，已知生产一件产品Ⅰ，消耗A 、B和C分
西 工
别为0、6、1个单位，已知生产一件产品Ⅱ ，消耗A 、 学
B和C分别为5、2、1个单位，而三种原材料每天的供应
第12页
①极小化目标函数问题转化为极大化目标函数
min z=2x1-3x2+x3 令 z’=-z，z’=-2x1+3x2-x3 新的目标函数
max z’=-2x1+3x2-x3
广 西
取得极小化的最优解时，这个最优解同时使原目标函数值取得最大 化的最优解。但两个问题最优解的目标函数值相差一个负号。
工 学 院
xn
广 西
a 11a 12a 1 nx1 a 1x 11a 1x 22 a 1 nxn A X a 21a 22 a 2n x2 a2x 11a2 x 22 a2nxn
am 1 am 2 am n xn am 1x1am 2x2 amxn n
工 学 院 财 政 经 济
因此，线性规划模型可以写成如下矩阵和向量的形式
min
z
=
3
x
2 1
+
2x1x2
系
变量的线性函数，约束条件必须 是变量的线性等式或不等式。如 右的问题就不是线性规划问题：
s.t.
2x1 +
x2 + x3 x1
≤8
x1 + x2 + 4x3 ≤9
冯 金 丽
x1, x2, x3 ≥0
第7页
2.线性规划的标准形式
目标函数为极大化，约束条件全部为等号约束，所有
冯 金 丽
第8页
3.线性规划模型用矩阵和向量表示
价
值
max z=c1x1+c2x2+……+cnxn
系 数
s.t. a11x1+a12x2+……+a1nxn a21x1+a22x2+……+a2nxn ……
＝b1 ＝b2
am1x1+am2x2+……+amnxn ＝bm
c1 T
c
c
2
c n
x1
工 学
院
掌握单纯形法原理
财 政
经
掌握运用单纯形表计算线性规划问题的步骤及解法
济 系
能用二阶段法和大M法求解线性规划问题。
冯 金
丽
第2页
1.1线性规划问题及其数学模型
一般线性规划问题及数学模型
广
线性规划数学模型的标准形式
西 工
学
院
财
政
经
济
系
冯 金 丽
第3页
广 西 工 学 院 财 政 经 济 系 冯 金 丽
s.t. a11x1+a12x2+……+a1nxn ≥ (≤, ＝)b1
广
a21x1+a22x2+……+a2nxn ≥ (≤, ＝)b2
西 工
……
学
院
am1x1+am2x2+……+amnxn ≥ (≤, ＝)bm x1, x2, ……, xn ≥0 (≤, Free)
财 政 经
济
线性规划模型的目标函数必须是
变量全部是非负的，这样的线性规划模型称为标准形式
广
西
Max z=c1x1+c2x2+……+cnxn
工 学
s.t. a11x1+a12x2+……+a1nxn ＝b1
院 财
a21x1+a22x2+……+a2nxn ＝b2
政 经
……
济 系
am1x1+am2x2+……+amnxn ＝bm x1, x2, ……, xn ≥0
X
x2
x n
广 西 工 学 院 财
x1, x2, ……, xn ≥0
资
政 经
工艺系数矩阵
源
济
a11 a12 a1n
Aa 21Байду номын сангаас
a22
a 2n
P1
P2
Pn
am1
am2
amn
b1
b
b
2
约 束
b m
系 冯 金 丽
第9页
线性规划模型用矩阵和向量表示（续）
x1
ZCXc1 c2 cn x2c1x1c2x2cnxn
第一章 线性规划及单纯形法
1.1 线性规划问题及其数学模型
广
西
1.2 图解法
工 学
院
1.3 单纯形法原理
财 政
经
1.4 单纯形法计算步骤
济 系
1.5 单纯形法进一步讨论
冯 金
丽
1.6 应用举例
第1页
本章学习要求
能建立实际问题的数学规划模型
理解线性规划模型的特点，标准型
广 西
掌握线性规划的图解法及其几何意义
决策变量 x1 x2
6x1+2x2≤24
0
5
约束条件 6
2
x1+ x2≤ 5 x1 ≥0,x2≥0
1
1
目标函数 2
1
3、分析目标——是利润最大化
MaxZ=2x1+x2
广
西
工
学
院
财
政
限制条件
经 济
15
系
24
冯
5
金
max 丽
第6页
二、线性规划模型标准形式
1.一般形式
min(max) z=c1x1+c2x2+……+cnxn
学
X ()0,Free 院
财
政
经
济
MaxZ =CX
系
s.t. AX=b
冯
X≥0
金 丽
第11页
5.线性规划问题的标准化
①极小化目标函数转化为极大化
②小于等于约束条件转化为等号约束
广 西
工
③大于等于约束条件转化为等号约束
学 院
财
④变量没有符号限制（Free）的标准化
政 经
济
⑤变量小于等于0的标准化
系
冯 金 丽
院 财
量分别为15、24、5个单位。请制定美佳公司的最佳生 产方案，使该公司总利润最大。
政 经 济
系
冯 金 丽
第5页
数学模型的建立
1、确定决策变量——通常由目标问题分解
设x1代表生产Ⅰ种家电数量；
x2代表生产Ⅱ种家电数量；
2、分析并表达限制条件，包括约束条件—
—通常由等式或不等式表示。
0x1+5x2≤15
系
冯
MaxZ =CX
金 丽
s.t. AX=b
X≥0
第10页
4.线性规划模型总结
线性规划模型的结构 目标函数 ：max，min 约束条件：≥,=,≤ 变量符号：：≥0, ≤0, Free
线性规划的标准形式 目标函数：max 约束条件 ：= 变量符号 ：≥0
max(min)z CX
广 西
s.t.
AX(,)b 工