运筹学课件3

格式：pdf
大小：98.19 KB
文档页数：31

用单纯形法求解的过程见下表。
max z = −3 x1 + x3 + 0 x4 + 0 x5 − Mx 6 − Mx 7 =4 x1 + x2 + x3 + x4 − 2 x + x − x − x5 + x 6 =1 1 2 3 + x7 = 9 3 x 2 + x3 x j ≥ 0( j = 1, L ,7 )
x1
0 0 1
x2
0 1 0
x 33
0 1/ 3
[2//3 ] 3
x4
1 0 0
x5
x6
x7
0 0
0 3 1
j
−1/ 2 −1/ 2 −1/ 2 0 0 1/3
1/ 2 −1/ 2 1/ 6 3/ 2 −M−3/2 −M+1/2
−3
c
j
− z
0
0 0
0
0 1 0 0
0 0 1
c
j
x4 x2 x3
− z
max z = −3 x1 + x3 + 0 x4 + 0 x5 − Mx 6 − Mx 7 max z = −3 x1 + x3 + 0 x4 + 0 x5 − Mx 6 − Mx 7 =4 x 2 + x3 + x 4 x 1 + x + x + x + x =4 4 − 2 x 1 + x 2 − x 3 − x5 + =1 x − 2 x1 + x2 − x3 6 + x − x =1 6 1 2 3 5 +x + =9 3x x2 + x3 x 9 7 = 3 + x 2 3 7 x j ≥ 0( j = 1, L ,7 )
2 1 −1 0 4 0 4M +1 0 0 1 1/ 3 ] 0 [2//3 3 0 3
−1
3
0
1 0 0
3M −4M 0
−1/ 2 −1/ 2 −1/ 2 0 0 1/3
1/ 2 −1/ 2 1/ 6 3/ 2 −M−3/2 −M+1/2
0
c
C
B
j
→
b
x4 x2 x 11
−3
0
1
0
0
−M
−M
基
z = − 3 x1 + x 3 x1 + x 2 + x 3 ≤ 4
max z = − 3 x 1 + x1 + x 2 + x 3 − 2 x + x − x 1 2 3 3 x2 + x3 x1 , x 2 , x 3 ≥ 0
x3 ≤ 4 ≥1 = 9
（2）目标函数的变化目标函数中人工变量的系数为绝对值任意大的一个负值，设为“-M”，只要人工变量的取值不为零，目标函数就不可能极大化。因此，最优解中人工变量的取值必须为零。大M法
x x
4 2
0 5/ 2
x 3 3/ 2
0 0 −1/ 2 3/ 2
−3/ 2
cj − z
j
1 0 用Lingo 0 求解 x5 x2 x3 x4 max z = − 3 x 1 + x 3 0 0 1/2x ≤ 4 x 1 + 1x 2 − + 3 1 1/ 3 0 0 − 2 x x x3 ≥ 1 + − 1 2 0 2/ 3 0 1/2 3 x2 + x3 = 9 0 3 0 3/ 2 x1 , x 2 , x 3 ≥ 0 0 0 1 −1/ 2 1 0 −1/ 4 0 0 0 3/ 4 1 0 0 −3/4 0
c
j
0
1 x3
0 1/ 3 2/ 3
0
0
0
0 x5
−1/2
−1
−1
→
−3
0
x2
0 1 0
CB
0 0 −3
基
x x
4 2
b
0 3 1
x1
0 0 1
x4
1 0 0
0 1/2
x1
cj − zj
0
0
3
0
3/ 2
c
j
→
− 3
CB
0 0 −3
基
x x
4 2
b
0 3 1
x1
0 0 1

x1
cj − zj
0 0 1
0 x2
1 1 3
4
0 x3
1
−1 1
0 x4
1 0 0
0 −1 x5 x6
0
−1
−1 x7
0 0 1
0
0 1 0
0
0
−1
cj − z
x x
4 2
−2
0
0
0 1/ 3 2/ 3
0
1 0 0
0
0 0 1
0 1 0
−1/2
x1
3 1
0 1/2
11/ 2 −1/ 2 0 1/ 3
−1/ 2
1/ 6
cj − zj
1 3 1
24
3 5
4
6 5
7
=4 max z =-3x1+0x2+ x3+ 0x4+ 0x5 x1 + x2 + x3 + x4 − 2 x + x − x − x5 + x6 =1 1 2 3 再从上表出发， + x7 = 9 3x2 + x3 继续用单纯形法计算， x j ≥ 0( j = 1,L,7) 求解过程见下表。
x2 2
1 0 [1 ] 0 3
1
x3
21
0
x4
1
0
x5
0 1 −1 3 0 −M 1 −1 3
−M
x6
01 − 1
− 03
−M
x7
0 0 1
CB 基
0 −M −M
c
j
x x
4
x 66 x
7
− z
0 0 −M
c
j
x4 x2
x 77
3 1 6
j
− z
0 −1 6 0 0 41 −3− 2M 4 M 1 0 3 0 1 2 −2 1 0 −1 [ 6] 0 0 4 6M −3 0 4M +1 0
c
j
→
CB
0 0 0
基
x x
4 2
b
0 3 1
0 x1
0 0 1
0 x2
0 1 0
0 x3
0 1/ 3 2/ 3
0 x4
1 0 0
0 −1 x5 x6
−1/2
−1 x7
0 1/2
11/ 2 −1/ 2 0 1/ 3
−1/ 2
x1
1/ 6
c zj = − z3jx1+0x2+ x3+ 0 0x4+ 0 max － 0x5
1.图解法 2.单纯形法
max
z =
∑
n
j =1
c jx
j
max z =
∑c
j =1
n
j
x j + 0 ⋅ ∑ x si
i =1
m
n ∑ a ij x j ≤ b i j =1 xj ≥ 0 j = 1, L , n i = 1, L , m
n ∑ a ij x j + x si = bi j =1 x j ≥ 0 j = 1, L , n i = 1, L , m
0
0
0
0
0
−1
−1
c
j
→
CB
0 0 0
基
x x
4 2
b
0 3 1
0 x1
0 0 1
0 x2
0 1 0
0 x3
0 1/ 3 2/ 3
0 x4
1 0 0
0 −1 x5 x6
−1/2
−1 x7
0 1/2
11/ 2 −1/ 2 0 1/ 3
−1/ 2
x1
1/ 6
cj − zj
0
0
0
0
0
−1
−1
第二阶段是将上表中的人工变量x6 、x7 除去，目标函数改为: +x +0 − Mx maxmax z = −z 3x x +0 x 0− =-3 xx+ + x0+ x Mx + 0x
c
j
→
CB
0
−1 −1
基
x x x
4 6 7
b
4 1 9
j
0 x1
1
0 x2
1 1 3
0 x3
1
−1 1
0 x4
1 0 0
0 −1 x5 x6
0 0 1 0
−1 x7
0 0 1
0
−2
0
−1
0
−1
cj − z
−2
4
0
0
0
c
j
→
CB
0
−1 −1
0 0 0
基
x x x
4 6 7
b
4 1 9
j
0 x1
1
−2
max z = −3 x1 + x3 + 0 x4 + 0 x5 − Mx 6 − Mx 7 =4 x1 + x2 + x3 + x4 − 2 x + x − x − x5 + x 6 =1 1 2 3 + x7 = 9 3 x 2 + x3 x j ≥ 0( j = 1, L ,7 )

运筹学课件ch3运输问题

i 1,......m
j1
m
x i j b j j 1 , . . . . . . n
i1
2019/7/21

x ij

0

运筹学课件
将约束方程式展开可得
x11 x1n
a1

x21 x2n
a2

x11

x21
xm1 xm1
m
n
供不应求：即产量小于销量时有 ai bj
1
1
m
n
供过于求：即产量大于销量时有ai bj
1
1
这两种情形都 a可 i 以 bj的化形为式来
求解
2019/7/21
运筹学课件
二.运输问题的模型
产销平衡问题模型
m
n
M i n z a i j x i j
1
1

n
x ij a i
技术系数矩阵
A
=

1
1

1 1 1

2019/7/21
运筹学课件
1
1
1
系数矩阵的特点: (1)约束条件的系数矩阵的元素只有两个:0,1. (2)元素 xij 对应于每一个变量在前m个约束方程中(第i个方程中)出现一次,在后n个约束方程中(第m+j 个方程中) 也出现一次. (3)产销平衡问题为等式约束. (4)产销平衡问题中各产地产量之和与各销售地点的销量之和相等.
bn；且产销平衡，即
m
n
。 ai bj
i1
j 1

运筹学课件第三节不确定型决策方法

S4
7 9 5 8 5
A1 A2 A3 A4 A5
u( A3 ) 0.8 7 0.2 3 6.2
u( A4 ) 0.8 8 0.2 3 7.0
u( A5 ) 0.8 5 0.2 3 4.6
运筹学教程
例5 设某决策问题的决策收益表为
状态方案
③ 存在两个或两个以上的自然状态，但是既不能确定未来和
中自然状态必然发生，又无法得到各种自然状态在未来发身个概率。 ④每个行动方案在不同自然状态下的益损值可以计算出来。对于不确定型决策问题，由一些常用的决策方法，或称为不
确定型决策准则。对于具有不同心理状态、冒险精神的人，
运筹学教程
一、悲观准则（max-min 准则）悲观准则又称华尔德准则或保守准则，按悲观准则决策时，决策者是非常谨慎保守的，为了“保险”，从每个方案中选择最坏的结果，在从各个方案的最坏结果中选择一个最好的结果，该结果所在的方案就是最优决策方案。例5 设某决策问题的决策收益表为
运筹学教程
1 E ( A1 ) (4 5 6 7) 5.50 4 1 E ( A2 ) (2 4 6 9) 5.25 4 1 E ( A3 ) (5 7 3 5) 5.00 4 1 E ( A4 ) (3 5 6 8) 5.50 4 1 E ( A5 ) (3 5 5 5) 4.50 4
运筹学教程
问题2：方案A2：稳获10000元；方案B2: 用掷硬币的方法，直到掷出正面为止，记所
掷次数为N，则当正面出现时，可获2N元.
当你遇到这两类问题时，如何决策？大部分会选择 A1 和 A2。但不妨计算一下其期望值：方案B1的收益为随机变量Y1。则其期望收益为：

运筹学教学课件第三章运输问题

7 4 9 3 6 5 6
2.1 确定初始基可行解
• 这与一般线性规划问题不同，产销平衡的运输问题总是存在可行解。因有
b a
i 1 j i 1
m
m
i
d
必存在 0≤ xij,i=1,…,m,j=1,…,n 是可行解。又因 0≤xij≤min(a1,bj) • 故运输问题的可行解和最优解必存在。 • 确定初始可行解的方法有很多，一般希望的方法即简便又尽可能接近最优解。下面介绍两种方法：最小元素法和伏格尔（Vogel）法。（其它如西北角法等）
例1
• 某公司经销甲产品，它下设三个加工厂。每日的产量分别为： • A1——7吨，A2——4吨，A3——9吨。该公司把这些产品分别运往四个销售点。各销售点每日的销量为：B1——3吨，B2——6吨， • B3——5吨，B4——6吨。已知从各工厂到各销售点的单位产品的运价为表3-3所示，问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。
运价表与行差和列差的计算
表3-10 伏格尔法
伏格尔法基可行解，总运费为85，恰好得到最优解
销地 B1 B2 B3 B4 行产差量产地
销地 B1 B2 B3 B4 产地 A1 A2
A1
A2 A3
3
1 7
11 3
9 4 5 6 2 1 5
10 0
8 3 6 1 1
7
4 9
10 5
列差 2 销量 3
A3
表3-13
B1 销地加工厂 A1 A2 A3 销量 ห้องสมุดไป่ตู้2 B3 B4 产量
5 3 6 3 6 5
2 1 3 6
7 4 9