运筹学4

x23
2,12 2 a2’’=0 b3’=10 第2行
x13
16,10 10 a1’=6 b3’’=0 第3列
产量 16 10 22
新产量 新销量 划去
14
销量
8
14
12
14
西北角法步骤 运价表中找出西北角(左上角)运价cij 在该处确定运量xij=min(ai,bj) 计算剩余产量ai’=ai-xij和剩余销量bj’=bj-xij，则出现 (1)ai’=0，bj’≠0——划去第i行运价； (2)ai’≠0，bj’=0——划去第j列运价； (3)ai’=0，bj’=0——划去第i行或第j列运价 重复上述，直到获得(m+n-1)个运输数量
例2：某部门三个工厂生产同一产品的产量、四个销售点的 销量及单位运价如下表。求最低运输费的运输方案。
产地 A1 A2 A3 销量
B1 4 2 8 4
B2 12 10 5 3
B3 4 3 11 5
B4 11 9 6 6
产量 8 5 9
解答
由于总产量=8+5+9=22，总销量=4+3+5+6=18，总产量>总销 量，属于产大于销的产销不平衡运输问题。增加一个销地， 销量b5=22-18=4；运价为0。得到产销平衡表如左表。表上作 业法结果见右表。 产地 B1 B2 B3 A1 4 12 4 A2 2 10 3 A3 8 5 11 销量 4 3 5 B4 11 9 6 6 B5 产量 0 8 0 5 0 9 4 产地 B1 A1 1 A2 4 A3 10 销量 4 B2 3 3 B3 4 1 9 5 B4 0 6 6 B5 产量 4 8 1 5 5 9 4
设xij为从Ai运输到Bj的产品数量，若Σai=Σbj，则称为产销平衡 的运输规划问题，数学模型为 min f=c11x11+…+c1nx1n+c21x21+…+cmnxmn xi1+xi2+…+xin=ai (i=1,2,…,m) x1j+x2j+…+xmj=bj (j=1,2,…,n) xij≥0 (i=1,2,…,m;j=1,2,…,n)

0 x3 1 0 0 0
0 x4 0 1 0 0
0 x5 0 0 1 0
θi
(min)
12/2-6 16/0-∞ 15/5-3
X5为输出量 为输出量
钶 0 0 3
XB x3 x4 x2 σj
Cj b 12 16 15/5
(max)
课外作业
题1： ：maxZ = 2x1 + x2 题2： maxz = 2x ：
5x2 ≤ 15 6x + 2x ≤ 24 2 1 x1 + x2 ≤ 5 x1, x2 ≥ 0
1
+ 3x2
2x1 + 2x2 ≤ 12 4x ≤ 16 1 s.t 5x2 ≤ 15 x1、x2 ≥ 0
x1 ﹣ 2x2 + 4x1 = ８ ﹣ x３ = 16 ﹣ x4 = 12﹣４x2 12﹣
x５ 令 x３= x５ =0 则可以得到: 则可以得到: x１=４， x２=２, x５=４,; =１４ １４. 此时 Z =１４.
我们得到了最优解。 我们得到了最优解。
基可行解说明
令非基变量x ⑴基（p3, p4, p5） ，令非基变量 1, x2=0，则基变 ， １６, 量x3=８, x4=１６ x5=1２, 可行解 ８ １６ 1 ），令非基变量 令非基变量x ⑵基（p2, p3, p4），令非基变量 1=0, x5=0基变量 基变量 x2=３, x3=２, x4=１６ １６. ３ ２ １６ 非可行解 ⑶基（p1, p2, p4），令非基变量 3=0, x5=0基变量 ），令非基变量x 基变量 令非基变量 x1=２, x2=３, x4=８. ２ ３ ８ 非可行解 ），令非基变量 令非基变量x ⑷基（ p1, p2, p5），令非基变量 3, x4=0，则基变 ， 量x1=４, x２=２, x5=４, ４ ２ ４ 可行解

a4
-140 -90 -40 10 60 60
a5
-175 -125 -75 -25 25 75
计算不同购买量盈利大于30元的概率

设 为购进量a而卖出量θ这一事件， 通过计算可得相应的概率如下表
B( , a)
a
a0 a1 a2 a3
0
a4 a5
P( B( , a) 30) 0

0.9 0.84 0.5 0.2 4 4 4
3 (差)
-12 -10 -8
方案
P(1 ) 0.3 P( 2 ) 0.5 P(3 ) 0.2
A1(大批量) 20 A2(中批量) 16 A3(小批量) 12
一、什么是风险性决策

决策环境不确定 决策信息不完全 可估得未来环境发生的概率 设计了多个方案，并已知在不


不确定性决策—不知环境变量的分布 风险性决策—已知环境变量的分布 贝叶斯决策—可得环境变量的后验概率 分布 效用函数决策—用决策者关于目标结果 的效用函数作为损益值 层次分析法—定性的系统分析方法 多目标决策—目标规划（第二章）
按其它因素分类




例5-1的决策树
9.6 A1 9.6 决 策
好0.3 一般0.5 差0.2
20 12 -12 16 10 -10 12 6 -8
7.8 A1
好0.3 一般0.5 差0.2
5 A1
好0.3 一般0.5 差0.2
例5-3求建厂方案

为生产某产品，计划建厂，建大厂，投资300 万元，小厂投资160万元，都是使用10年。每 年的损益值如下表所示。
可 靠 性 分 析
发 现 问 题

A1 A2 A3 销量
B1
B2
B3
B4
1
32
11 4 3
3 10
3 1 3 9 1 2 -1 8
4
7
6 4 12 10 3 5
3
6
5
6
产量
7 4 9 20
检验数<0表示：例如（A2,B4）如果增加A2到B4的1单位产 品，将会降低1单位的运费，所以，该解不是最优解。
13
解的改进
（1）以 xij 为换入变量，找出它在运输表中的闭回路；
B2 4 11 29
4
6
B3 3
22
3 10
5
B4 产量 10 7
8
4
65
9
5
6
20
求平衡运输问题初始解方法—西北角方法
西
B1
B2
B3
B4 产量
北 角
A1 3
34
11
3
10 7
方
A2
12
92
2
8
4
法
A3
7
43
10 6 5
9
初 始
需求量
3
6
5
6
20
解
x11 3, x12 4, x22 2, x23 2, x33 3, x34 6
min cij xij
s.t.
n
xij si
j 1
m
xij d j
i 1
xij 0
目标函数
n表示物资的n个销地 m表示物资的m个产地
供给约束
需求约束
非负约束
18
问题分析
决策变量 目标函数 约束条件：产量约束、销量约束、非负