当前位置：文档之家 › 运筹学 单纯形法 应用举例

运筹学 单纯形法 应用举例

  • 格式：ppt
  • 大小：2.65 MB
  • 文档页数：31

下载文档原格式

  / 31

合集下载

15单纯形法(运筹学)

15单纯形法(运筹学)
几点说明： 几点说明： (1)、 (1)、例 maxZ=X1 +2X2 X1 ≤ 4 X2 ≤ 3 X1+2X2 ≤ 8 X1 , X2 ≥0 X1+X3 = 4 X2+X4 = 3 X1+2X2+X5= 8 X1 … X5 ≥0
1
2
3
4
X(1)= (2,3) X(2)= (4,2)
全部解： 全部解：X=α
(1) -4 0 1 -2 0
14
15
本问题无界。 本问题无界。 X2
O
X1
Z=0
16
1.5.4 初始基本可行解的求法 (一)、大M法： 一、 法 例1 ： maxZ= 6X1 +4X2 2X1 +3X2 ≤ 100 4X1 +2X2 ≤ 120 X1 X1 X2 ≥0
=14
X2 ≥ 22
17
λj <0
8
(3)、 (3)、maxZ=10X1 + 12X2 3X1+4X2 ≤ 6 4X1+ X2 ≤ 2 3X1 +2X2 ≤ 3 X1 , X2 ≥0
9
10
X =(0, 3/2, 0, 1/2, 0)T Zmax=18
退化解
*
11
例：maxZ= -3/4X4+20X5 -1/2X6+6X7 X1+1/4X4 -8X5 -X6+9X7 =0 X2+1/2X4-12X5 -1/2X6+3X7 =0 X3+X6 =1 X1 … X7 ≥0 (P1 P2 P3) → (P4 P2 P3) → (P1 P2 P3) → (P4 P5 P3) → (P6 P5 P3) → (P6 P7 P3) → (P1 P7 P3)

运筹学及其应用4.3 对偶单纯形法

运筹学及其应用4.3 对偶单纯形法
3
min w= 2x1+3x2+4x3+0x4+0x5 x1+2x2+ x3-x4＝ 1 2x1- x2+3x3– x5＝4 x1,x2,x3,x4,x5≥ 0
min w= 2x1+3x2+4x3+0x4+0x5 -x1-2x2- x3+x4＝ -1 -2x1+x2-3x3+x5＝ -4 x1,x2,x3,x4,x5≥ 0
4
234 000
0
x1 x2 x3 x4 -1 -2 -1
x4 x5 b 1 0 -1
max

2 −2
4 ，
−3

=
−1
0 x5 -2* 1 -3 0 1 -4
σ 234 000
0 x4 0 -2.5 0.5 1 -0.5 1
2 x1 1 -0.5 1.5 0 -0.5 2
σ 0 4 1 0 1 -4
步骤：(1)保持σj ≥ 0，j= 1,···,n，确定XB，建立计算表格； (2)判别XB = B-1b ≥ 0是否成立？ ①若成立，XB为最优基变量； ②若不成立，转(3)；
1
步骤：(1)保持σj ≥ 0，j= 1,···,n，确定XB，建立计算表格；
(2)判别XB = B-1b ≥ 0是否成立？ ①若成立，XB为最优基变量； ②若不成立，转(3)；
5
• 作业 • P81 1.12(1)
6
§3 对偶单纯形法
单纯形法：由 XB = B-1b ≥ 0，使σj ≥ 0，j = 1,···,m 对偶单纯形法：由σj ≥ 0(j= 1,···,n)，使XB = B-1b ≥ 0 相同点：都用于求解原问题

管理运筹学 第6章 目标规划

管理运筹学 第6章 目标规划

目标规划问题及模型
∵正负偏差不可能同时出现，故总有：
x1－x2+d--d+ =0
若希望甲的产量不低于乙的产量，即不希望d->0,用目标约束可
表为:
min{d }
x1
x2
d
d
0
若希望甲的产量低于乙的产量，即不希望d＋>0,用目标约束可
表为:
min{d }
x1
x2
d
d
0
若希望甲的产量恰好等于乙的产量，即不希望d＋>0,也不希望
2x1 2x2 12
s.t
4
x1 x1
2x2
8 16
4x2 12
x1 , x2 0
其最优解为x1＝4，x2＝2，z＊＝14元
目标规划问题及模型
但企业的经营目标不仅仅是利润，而且要考虑多个方面，如： (1) 力求使利润指标不低于12元； (2) 考虑到市场需求，甲、乙两种产品的生产量需保持1:1的比
标决策的需要而由线性规划逐步发展起来的一个分支。 由于现代化企业内专业分工越来越细，组织机构日益复
杂，为了统一协调企业各部门围绕一个整体的目标工作，产 生了目标管理这种先进的管理技术。目标规划是实行目标管 理的有效工具，它根据企业制定的经营目标以及这些目标的 轻重缓急次序，考虑现有资源情况，分析如何达到规定目标 或从总体上离规定目标的差距为最小。
min Z = f（ d ++ d - ）
（2） 要求不超过目标值，但允许达不到目标值，即只有使 正偏差量要尽可能地小（实现最少或为零）
min Z = f（ d +）
目标规划问题及模型
例1. 某企业计划生产甲，乙两种产品，这些产品分别要在 A,B,C,D四种不同设备上加工。按工艺文件规定，如表所示。

单纯形法及应用举例

单纯形法及应用举例

θ
11/1
1 -1
/
1 -1
10/2
1 -1 56/10
1
2
1
4
第3节 解目标规划的单纯形法
② 取k=1，检查检验数的P1行，因该行无负检验数，故转(5)。 ③ 因k(=2)＜K(=3)，置k=k+1=3，返回到(2)。 ④ 查出检验数P2行中有−1、 − 2；取min(− 1, − 2)= − 2。它对应
❖ 力求总运费最省
34
cij xij d13 d13 2950
i1 j1
❖ 目标函数为：
min z P1d 4 P2d 5 P3(d6 d 7 d 8 d 9)

P4d
10

P5
d
11
P6 (d
12
d
12)

Hale Waihona Puke P7d 1317第4节 应用举例
200 100
300
200
200
250 150 400
100 100
销量
200 100 450 250 1000/1000 14
第4节 应用举例
❖ 供应约束
x11+x12+x13+x14≤300 x21+x22+x23+x24≤200 x31+x32+x33+x34≤400 ❖ 需求约束：
x11+x21+x31+d1−− d1+=200
❖ 计算结果，得到满意调运方案见表5-10。
销地 B1
产地
B2
B3
B4 产量
A1
100
200 300

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

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

第一章
工厂需要的原棉存放在三个仓库中，现将原棉运往工 厂以满足工厂生产的需求。已知原棉运到各个工厂的单位 运费如表所示。问使总运费最小的运输方案？
仓库\工厂
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

运筹学第5章 单纯形法

运筹学第5章 单纯形法

0 0 1
在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的 各列向量所组成，称之为初始可行基，其相应的基本可行解叫初始基 本可行解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作 为初始可行基，我们将构造初始可行基，具体做法在以后详细讲述。
8Leabharlann §1 单纯形法的基本思路和原理
二、 最优性检验 所谓最优性检验就是判断已求得的基本可行解是否是最优解。
5
§1 单纯形法的基本思路和原理
线性规划解之间的关系：
1.可行解与最优解： 最优解一定是可行解，但可行解不一定是最优解。
2. 可行解与基本解： 基本解不一定是可行解，可行解也不一定是基本解。
3. 可行解与基本可行解： 基本可行解一定是可行解，但可行解不一定是基本可行解。
4. 基本解与基本可行解： 基本可行解一定是基本解， 但基本解不一定是基本可行解。
9
§1 单纯形法的基本思路和原理
2.最优解判别定理
对于求最大目标函数的问题中，对于某个基本可行解，如
果所有检验数 j≤0，则这个基本可行解是最优解。 下面我
们用通俗的说法来解释最优解判别定理。设用非基变量表示
的目标函数为: z z0 j xj jJ 由于所有的xj的取值范围为大于等于零，当所有的 j都小
由线性代数的知识知道，如果我们在约束方程组系数矩阵中找
到一个基，令这个基的非基变量为零，再求解这个m元线性方程组就
可得到唯一的解了，这个解我们称之为线性规划的基本解。
在此例中我们不妨找到
1 1 0 B3 1 0 0
为A的一个基，令这个基的非
1 0 1
基变量x１，s2为零。这时约束方程就变为基变量的约束方程：
第五章 单 纯 形 法

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

运筹学 第二章线性规划 第三讲 单纯形法
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

运筹学-单纯形-2012

运筹学-单纯形-2012

§1.4 线性规划问题的几何解释对于只有两个变量的线性规划问题，可以在二维直角坐标平面上表示线性规划问题。

例1.8max z= x 1 +3x 2s.t. x 1 +x 2 ≤6 (1) -x 1 +2x 2 ≤8 (2) x 1, x 2 ≥0其中满足约束(1)的点⎥⎦⎤⎢⎣⎡=21x x X 位于坐标平面上直线x 1+x 2=6靠近原点的一侧。

同样，满足约束(2)的点位于坐标平面上直线 -x 1+2x 2=8的靠近原点的一侧。

而变量x 1，x 2的非负约束表明满足约束条件的点同时应位于第一象限内。

这样，以上几个区域的交集就是满足以上所有约束条件的点的全体。

我们称满足线性规划问题所有约束条件（包括变量非负约束）的向量 X =(x 1，x 2，…，x n )T为线性规划的可行解（Feasible Solution ），称可行解的集合为可行域（Feasible Region ）。

例1.8的线性规划问题的可行域如图1.2中阴影部分所示。

为了在图上表示目标函数，令z=z 0为某一确定的目标函数值，取一组不同的z 0值，在图上得到一组相应的平行线，称为目标函数等值线。

在同一条等值线上的点，相应的可行解的目标函数值相等。

在图1.2中，给出了z=0，z=3，z=6，…，z=15.3等一组目标函数等值线，对于目标函数极大化问题，这一组目标函数等值线沿目标函数增大而平行移动的方向（即目标函数梯度方向）就是目标函数的系数向量C=(c 1,c 2,…,…,c n )T ；对于极小化问题，目标函数则沿-C 方向平行移动。

在以上问题中，目标函数等值线在平行移动过程中与可行域的最后一个交点是B 点，这就是线性规划问题的最优解，这个最优解可以由两直线x 1+ x 2=6 -x 1+2x 2=8 的交点求得314x ,34x 21==最优解的目标函数值为346314334x 3x z 21=⨯+=+= 为了将以上概念推广到一般情况，我们给出以下定义： 定义1.1 在n 维空间中，满足条件a i1x 1+a i2x 2+…+a in x n =b i的点集X =(x 1，x 2，…，x n )T称为一个超平面。

运筹学(3)1-3_单纯形法第1部分

运筹学(3)1-3_单纯形法第1部分
运 筹 学
运 筹 帷 幄 之 中
Operations Research
决 胜 千
线性规划
Linear Programming
里 之 外
第四节 单纯形法
线性规划单纯形(Simplex)法
单纯形法(Simplex Method)是美国人丹捷 格 (G.Dantzig)1947年创建的 这种方法简捷、规范，是举世公认的解决线 性规划问题行之有效的法。 单纯形法的表现形式：
⑤根据max{j｜j＞0}=k原则，确定xk为换入变量(进基 变量)，再按规则计算：=min{bi/aik| aik ＞0}=bl/ aik 确定xBl为换出变量。建立新的单纯形表，此时基变量 中xk取代了xBl的位置。
⑥以aik为主元素进行迭代，把xk所对应的列向量变为单位列 向量，即a 变为1，同列中其它元素为0，转第③ 步。

Z
( 0)
0
(x4=3，x5=9), 三种产品的总利润为0！
第四步：分析两个基本表达式，看看目 标函数是否可以改善？
① 分析用非基变量表示目标函数的表达式
Z 2 x1 3x2 3x3
非基变量前面的系数均为正数，所以任何一 个非基变量进基都能使Z值增加 通常把非基变量前面的系数叫“检验数”；
Z 2 x1 3 x2 3x3 2(3 x2 x3 x4 ) 3 x2 3 x3 6 x2 x3 x4
可得相应的目标函数值为Z（1）=6
检验数仍有正的
返回①进行讨论。
Z c j x j c j x j cni xni c j x j cni (bi aij x j )
m
令Z 0 cnibi ,
i 1

运筹学5-单纯形法

运筹学5-单纯形法



Max Z C B B 1b C N C B B 1 N X N X B B 1 NX N B 1b s .t X B 0 , X N 0
令 x3 0 x4 0
6 x1 2 x2 24
15 3 X 0 0 4 4
T
为基本可行解，B12为可行基
则
3 1 对于基阵 B13 6 0 3x1 x3 15
令 x2 0 x4 0
为基本可行解，B13为可行基
6 x1 24
X1
X(1)
单纯形法小结： 单纯形法是这样一种迭代算法——如下图… 当Zk中非基变量的系数的系数全为负值时，这时的基本可 行解Xk即是线性规划问题的最优解，迭代结束。
X1
保持可行性
X2
保持可行性
X3
保持可行性 ...
保持可行性
Xk
保持单调增
保持单调增
保持单调增
保持单调增 ...
Z1
Z2
Z3
Zk
当Zk 中非基变量的系数的系数全为负值时，这时的 基本可行解Xk 即是线性规划问题的最优解，迭代结束。
第五章 单纯形法
1. 线性规划问题的解 2 单纯形法 3 求初始基的人工变量法
1.线性规划问题的解
Max
(1) 解的基本概念
Z CX AX b X 0
1 2 3
s.t
定义 在线性规划问题中，约束方程组(2)的系 m m 数矩阵A(假定 m n )的任意一个 阶的非奇异(可逆)的子方阵B(即 )， B 0 称为线性规划问题的一个基阵或基。
XB Z CX C B C N X CB X B CN X N N C B B 1b B 1 NX N C N X N

单纯形法基本原理及实例演示

单纯形法基本原理及实例演示
②找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。
③计算各非基变量xj的检验数j=Cj-CBPj ′，若所有j≤0，则问题已得
到最优解，停止计算，否则转入下步。
④在大于0的检验数中，若某个k所对应的系数列向量Pk≤0，则此问
题是无界解，停止计算，否则转入下步。
⑤根据max{j｜j＞0}=k原则，确定xk为换入变量(进基变量)，再按 规则计算：=min{bi/aik| aik＞0}=bl/ aik 确定xBl为换出变量。建 立新的单纯形表，此时基变量中xk取代了xBl的位置。
⑥以aik为主元素进行迭代，把xk所对应的列向量变为单位列向量，即 aik变为1，同列中其它元素为0，转第③ 步。
线性规划的例子
max z 4x1 3x2 2x1 2x2 1600 5x1 2.5x2 2500 x1 400 x1, x2 0
线性规划--标准化
● 引入变量：s1,s2,s3
检验系数区
Z=CBB-1b
初始单纯形表
迭代 基变 次数 量
CB
x1
x2
s1
s2
s3
50 100 0 0 0
比值
b bi ai 2
1 Zj=CBNj j cj zj
Z=CBB-1b
初始单纯形表
基
迭代 次数
变
CB
x1
X2
s1
s2 S3
量
50 100 0 0 0
比值
b bi ai 2
1 1 1 0 0 300
C向量
max z 50 100 0 0
CB
CN
x1
x2
0•

1 1 1
1 0 0
0 1 0

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

运筹学基础及应用第五版胡运权第一章
问题的提出 某企业计划生产Ⅰ、Ⅱ两种产品。这两种产品都要分别在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)

运筹学单纯形法应用举例

运筹学单纯形法应用举例
《运筹学》
1
要制作100套钢筋架子，每套有长2.9m、2.1 m和1.5m的钢筋各一根。已知原材料长7.4m，
应如何切割，使用原材料最节省。 解：所谓合理利用原材料，就是要使料头总 长最少。表1.14是节省材料的几种较好方案。
2010年8月
管理工程学院
《运筹学》
2
设按Ⅰ种方案下料的原材料数x1根，方案Ⅱ 用x2根，方案Ⅲ用x3根，方案Ⅳ用x4根，方 案Ⅴ用x5根， 根据表1-14可列出约束条件：
= -15x11+25x12+15x13-30x21+10x22-40x31-10x33
约束条件： 从第1个表中有：
x11≥0.5(x11+x12+x13) x12≤0.25(x11+x12+x13) x21≥0.25(x21+x22+x23) x22≤0.5(x21+x22+x23)
2010年8月
约束条件：
s.t.
0.5 x11-0.5 x12 -0.5 x13 ≥ 0 （原材料1不少于50%） -0.25x11+0.75x12 -0.25x13 ≤ 0 （原材料2不超过25%） 0.75x21-0.25x22 -0.25x23 ≥ 0 （原材料1不少于25%） -0.5 x21+0.5 x22 -0.5 x23 ≤ 0 （原材料2不超过50%）
x11+ x21 + x31 ≤ 100 (供应量限制） x12+ x22 + x32 ≤ 100 (供应量限制） x13+ x23 + x33 ≤ 60 (供应量限制）
xij ≥ 0 , i = 1,2,3; j = 1,2,3

5运筹学之单纯型法应用举例

5运筹学之单纯型法应用举例

3
75
16
21
生产工时数
车间
零件1
零件2
1
x11
x12
2
x21
x22
3
x31
x32
例1-19
车间1工时约束
x11＋x12≤100
车间2工时约束
x21＋x22≤50
车间3工时约束
x31＋x32≤75
零件1生产数量 8x11+10x21+16x31
零件2生产数量 6x12+15x22+21x32
非负约束
为了得到初始解，在约束条件中加入松弛变量x10～x16， 得到数学模型：
例11的线性规划模型
目标函数 约束条件
max z 15x1 25x2 15x3 30x4 10x5 40x7 10x9
0 x10 x11 x12 x13 x14 x15 x16
1 2
x1
1 2
x2
用若干种原材料（资源）生产某几种
产品，原材料（或某种资源）供应
有一定的限制，要求制定一个产品
生产计划，使其在给定资源限制条 件下能得到最大收益。
单耗 产品 A1 ……..
资源
An 资源 可供量
B1
a11 …… a1n
b1
B2 ……
a21 …… a2n …… …… ……
b2 ……
Bm
am1 …… amn
表1-11 套裁方案
下料根数
长度(m) 2.9 2.5 1.5 合计 料头
方
案
Ⅰ
Ⅱ
Ⅲ
Ⅳ
Ⅴ
1
2
1
0
2
2
1
3

湖北工业大学运筹学 单纯形法

湖北工业大学运筹学 单纯形法

湖北工业大学
HuBei University of Technology
，为 m n 阶系数矩阵（ n m），其秩为 m。
a11, a12 ,..., a1m a21, a22 ,..., a2 m B .................... am1, am 2 ,..., amm
a x a x ... a x （= ,）b1 12 2 1n n 11 1 （= ,）b2 a21x1 a22 x2 ... a2 n xn s.t. ........................................................ （= ,）bm am1x1 am2 x2 ... amn xn x1, x2 ,..., xn 0
第1章 线性规划及单纯形法
1.1 线性规划问题及数学模型
湖北工业大学
HuBei University of Technology
1.1.2 LP问题的数学模型 从以上例子可以看出，线性规划问题的数学模型包含三个要素： 1.决策变量：问题中要确定的未知量。每个问题用一组决策量表示，一组决策 量的值代表一个方案。 2.约束条件：决策变量受到各种可用资源的限制，表示为含决策变量的线性等 式或线性不等式。 3.目标函数：问题要达到的目标，表示为决策变量的函数。 满足以上三个条件的数学模型为线性规划的数学模型。 一般LP问题的数学模型：（ n 个决策变量，m 个约束条件）
湖北工业大学
HuBei University of Technology
规划问题：如何合理利用有限的人力、物力、财力等资源，获得最大的收益。
例1：运输问题：已知几个地方生产同一种产品，而另一些地方需要该产品， 在已知各地运价情况下，如何组织运输才能满足需求并使总运费最少？

(参考资料)运筹学单纯形法例题

(参考资料)运筹学单纯形法例题

1
1
= 40
0
1
0
x4
30
1
[3]
0
σ
(1) j
=cj
− CB
⋅ Pj
3
4
0
30
1
= 10
3
0
0
x3
30
5 3
0
1
1
−
3
4
x2
10
1 3
1
0
1 3
σ
(2) j
=cj
− CB
⋅ Pj
5
4
0
0
−
3
3
这时，非基变量的检验数 σ1
=
5 3
,σ 4
=
−
4 3
，其中 σ 1
>
0
，所以该基可行解不是最优解。
（7）接下来，我们的任务就是找另一个基可行解。即转回到步骤（5）。
然不想干，怎么办呢？为了计算简便，我们期待 B2 = [P3 ,P 2 ] = I ，目前我们只是期待而已。
3
4
0
0
CB
XB
b
x1
x2
x3
x4
bi aik
40
0
x3
40
2
1
1
= 40
0
1
0
x4
30
1
[3]
0
σ
(1) j
=cj
− CB
⋅ Pj
3
4
0
0
x3
0
1
4
x2
1
0
1
30 = 10
3
0
第3页共9页

1.2-4 单纯性法及应用

1.2-4 单纯性法及应用

系数矩阵中不存在 单位矩阵，无法建 立初始单纯形表。
单纯形法的进一步讨论－人工变量法
max Z 3 x1 2 x 2 x 3－Mx 6 Mx 7 4 x1 3 x 2 x 3 x 4 x 6 4 x1 x 2 2 x 3 x 5 10 2 x1 2 x 2 x 3 x 7 1 x j 0, j 1,2, ,7
一. 几个概念 • 基：设A为约束条件 AX=b 的m×n阶系数矩阵(m<n)， 其秩为m，B是矩阵A中m阶可逆子矩阵（∣B∣≠0），称 B是规划问题的一个基。
a11 A am1
a1n amn
线性规划问题的数学模型
设：
Page 3
a11 B am1
1. 以上的换基迭代过程保证基的可行性； 2. 迭代后的目标函数值不会减少。
单纯形法的计算步骤
单纯形法步骤：
Page 17
1. 将LP问题化为标准型，确定初始的基可行解；
2. 检验是否为最优解；（判别准则）
3. 寻找更好的一个基可行解；（换基迭代）
4. 重复2,3，直到达到最优。
单纯形法的计算步骤
cB c j1
XB B b x j1 1
1
c j2 c jm
x j2 x jm
c1 c2 x1 x2 11 12 21 22
m1 m 2
cn xn 1n 2n
mn
i
1 m

m
1
2
B-1b (1, 2 ,
n
其中： B-1 A (ij )mn
单纯形法的进一步讨论－人工变量法
例5 用大M法解下列线性规划
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2010年8月 管理工程学院
《运筹学》 运筹学》
6
表示第j个计划阶段新购的工具数 个计划阶段新购的工具数； 用xj表示第 个计划阶段新购的工具数； 表示第j阶段末送去慢修的工具数 阶段末送去慢修的工具数； yj表示第 阶段末送去慢修的工具数； zj表示第 阶段末送去快修的工具数； 表示第j阶段末送去快修的工具数 阶段末送去快修的工具数； sj表示 阶段木工具的存储数。 表示j阶段木工具的存储数 阶段木工具的存储数。 则每个阶段需用的工具数r 则每个阶段需用的工具数 j有以下关系式 rj= yj+ zj + sj + sj-1 (j=1,…,n) rj= xj (j=1,…,q+1) rj= xj+ zj-q-1 (j=q+2,…,p+1) rj= xj+ zj-q-1 +yj-p-1 (j=p+2,…,n) 且yn-p= yn-p+1=…= yn=0 zn-q= zn-q+1=…= zn=0
管理工程学院
xj,， yj ， zj ， sj ≥0
2010年8月
《运筹学》 运筹学》
8 ◆ 混合配料问题。某糖果厂用原料A、B、C 混合配料问题。某糖果厂用原料 、 、 加工成三种不用牌号的糖果甲、 加工成三种不用牌号的糖果甲、乙、丙。已知各 种牌号中A、 、 含量 原料成本， 含量， 种牌号中 、B、C含量，原料成本，各种原料的 每月限制用量，三种牌号糖果各多少公斤， 每月限制用量，三种牌号糖果各多少公斤，使该 厂获利最大。建立问题的线性规划模型。 厂获利最大。建立问题的线性规划模型。
17
x1 3 + x 2 3 ≤ 4 0 8 1 0 0 x1 4 + x 2 4 ≤ 1 3 0 1 0 0
x 产量约束为飞机汽油2的产量： 21 + x22 + x23 + x24 ≥ 250000
P 由物理中的分压定律， V =
∑
n
2.85 x11 − 1.42 x12 + 4.27 x13 − 18.49 x14 ≥ 0 2.85 x 21 − 1.42 x 22 + 4.27 x 23 − 18.49 x 24 ≥ 0 同样可得有关辛烷数的约束条件16.5x11 + 2.0 x12 − 4.0 x13 + 17.0 x14 ≥ 0
x11+ x12+ x13+
x21 + x22 + x23 +
x31 ≤ 100 x32 ≤ 100 x33 ≤ 60
(供应量限制） (供应量限制） 供应量限制 (供应量限制） (供应量限制） 供应量限制 (供应量限制） (供应量限制） 供应量限制
xij ≥ 0 , i = 1,2,3; j = 1,2,3
蒸汽压力(g/cm2) 产量需求 于9.96 ×10-2 于9.96 ×10-2 于 250000 管理工程学院
100 2010年8月
《运筹学》 运筹学》
解：设xij为飞机汽油i中所用标准汽油j的数量(L)。 x 目标函数为飞机汽油1的总产量： 11 + x12 + x13 + x14 库存量约束为： x 1 1 + x 2 1 ≤ 3 8 0 0 0 0 x1 2 + x 2 2 ≤ 2 6 5 2 0 0
管理工程学院
《运筹学》 运筹学》
9
分别代表原材料A、 、 解：用i=1,2,3分别代表原材料 、B、C ，用 分别代表原材料 j=1,2,3分别代表甲、乙、丙。设xij为生产第 分别代表甲、 为生产第j 分别代表甲 种糖果使用的第i种原料的公斤数 种原料的公斤数， 种糖果使用的第 种原料的公斤数，则问的 数学模型为： 数学模型为：
《运筹学》 运筹学》
1
第七节 应用举例
◆熟悉建立模型的方法步骤
2010年8月
管理工程学院
《运筹学》 运筹学》
2
建模是运筹学方法的核心和精髓。 建模是运筹学方法的核心和精髓。一个经 管理问题要抽象为数学模型， 济、管理问题要抽象为数学模型，须满足 下列几个条件： 下列几个条件： ①问题的目标能用某种效 益指标度量大小程度， 益指标度量大小程度，并能用线性函数描 述目标的要求； 述目标的要求； 达到目标有多种方案； ②达到目标有多种方案； ③要达到目标的约束条件可用线性等式或 不等式来描述。 不等式来描述。 工业原料的合理利用。 ◆工业原料的合理利用。
甲 A B C ≥60％ ％ ≤20％ ％ 乙 ≥30％ ％ ≤50％ ％ 0.40 2.85
2010年8月
丙
≤60％ ％ 0.30 2.25
成本 (元/kg) 2.00 1.50 1.00
月限制 用量(kg) 用量(kg) 2000 2500 1200
加工费(元 加工费 元/kg) 0.50 售价(元 售价 元/kg) 3.40
《运筹学》 运筹学》
5
方案选择。 ◆ 方案选择。 某厂计划期分为n各阶段 在第j(j=1,…,n)个 各阶段， 某厂计划期分为 各阶段，在第 个 阶段，生产上要用r 个专用工具。到阶段末， 阶段，生产上要用 j个专用工具。到阶段末， 凡在这个阶段内使用过的工具都应该送去修 理后才能再使用。修理分两种，一是慢修， 理后才能再使用。修理分两种，一是慢修， 即等某种规格工具积压到一定批量后集中修， 即等某种规格工具积压到一定批量后集中修， 每件b元 需要p个阶段能取回 个阶段能取回。 每件 元，需要 个阶段能取回。二是送去后 立即修，这样费用贵一些，每件c(c>b)元， 立即修，这样费用贵一些，每件 元 q(q>p)个阶段可取回。新购一个这样的工具 个阶段可取回。 个阶段可取回 需a(a>c)元。 元
2010年8月
管理工程学院
《运筹学》 运筹学》
4
设按Ⅰ种方案下料的原材料数 方案Ⅱ 设按Ⅰ种方案下料的原材料数x1根，方案Ⅱ 方案Ⅲ 方案Ⅳ 用x2根，方案Ⅲ用x3根，方案Ⅳ用x4根，方 根据表1-14可列出约束条件： 可列出约束条件： 案Ⅴ用x5根， 根据表 可列出约束条件
目标是使用料最少，即
2010年8月 管理工程学院
解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。这样 我们建立数学模型时，要考虑： 对于甲： x11，x12，x13； 对于乙： x21，x22，x23； 对于丙： x31，x32，x33； 对于原料1： x11，x21，x31； 对于原料2： x12，x22，x32； 对于原料3： x13，x23，x33； 目标函数： 利润最大，利润 = 收入 - 原料支出 约束条件： 规格要求 4 个； 供应量限制 3 个。
过原材料的供应限额， 过原材料的供应限额，故有 (x11+x21+x31)≤100 (x12+x22+x32)≤100 (x13+x23+x33)≤60 通过整理，得到以下模型： 通过整理，得到以下模型：
2010年8月
管理工程学院
《运筹学》 运筹学》
15
目标函数： 目标函数：Max z = -15x11+25x12+15x13-30x21+10x22-40x31-10x33 约束条件： 约束条件： s.t. 原材料1不少于50% 50%） 0.5 x11-0.5 x12 -0.5 x13 ≥ 0 （原材料1不少于50%） 原材料2不超过25% 25%） -0.25x11+0.75x12 -0.25x13 ≤ 0 （原材料2不超过25%） 原材料1不少于25% 25%） 0.75x21-0.25x22 -0.25x23 ≥ 0 （原材料1不少于25%） -0.5 x21+0.5 x22 -0.5 x23 ≤ 0 （原材料2不超过50%） 原材料2不超 运筹学》
例．某工厂要用三种原料1、 某工厂要用三种原料1 2、3混合调配出三种不同规格的 产品甲、 数据如右表。 产品甲、乙、丙，数据如右表。 该厂应如何安排生产， 问：该厂应如何安排生产，使利 润收入为最大？ 润收入为最大？
12
产品名称 规格要求 单价（元/kg） 50 甲 原材料 1 不少于 50%，原材料 2 不超过 25% 35 乙 原材料 1 不少于 25%，原材料 2 不超过 50% 25 丙 不限 原材料名称 1 2 3 每天最多供应量 100 100 60 单价（元/kg） 65 25 35
50（ +35（ +25（ Max 50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33） 25（ 35（ -65（x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33） 65（ = -15x11+25x12+15x13-30x21+10x22-40x31-10x33
2010年8月 管理工程学院
《运筹学》 运筹学》
7
所以上述问题可描述为下面线性规划模型： 所以上述问题可描述为下面线性规划模型：
xj= rj xj+ zj-q-1= rj
(j=1,…,q+1) (j=q+2,…,p+1)
xj+ zj-q-1 +yj-p-1 = rj (j=p+2,…,n) yj+ zj + sj + sj-1 = rj (j=1,…,n) yj=0 zj=0 (j≥n -p) (j≥n-q)
2010年8月 管理工程学院
《运筹学》 运筹学》
3
要制作100套钢筋架子，每套有长2.9m、2.1 套钢筋架子，每套有长 要制作 套钢筋架子 、 m和1.5m的钢筋各一根。已知原材料长 的钢筋各一根。 和 的钢筋各一根 已知原材料长7.4m， ， 应如何切割，使用原材料最节省。 应如何切割，使用原材料最节省。 解：所谓合理利用原材料，就是要使料头总 所谓合理利用原材料， 长最少。 是节省材料的几种较好方案。 长最少。表1.14是节省材料的几种较好方案。 是节省材料的几种较好方案