2014-10-20 《运筹学》Ⅰ 史慧萍 18
40
10
15
0

调整后的调运计划：x13=50,x22=50,x31=40,x32=5,x33=10,x34=20. 其余xij=0。
2014-10-20 《运筹学》Ⅰ 史慧萍 19

计算检验数（非基变量的检验数） ：σij=cij－(ui+vj)得 σ11=5，σ12=2，σ14=7，σ21= 5，σ24=4，σ33=1。其余σij=0。当所 有检验数大于或等于零时，该可行解为最优。调整后的最优 调运计划：x13=50,x22=40,x23=10,x31=40,x32=15,x34=20.其余xij=0。 最优值565。
2014年4月10日
作业2：



某电视机厂装配黑白和彩色两种电视机，每装配一台电视 机需占用装配线1小时，装配线每周计划开动40小时预计 市场每周彩色电视机的销量是24台，每台可获利80元；黑 白电视机的销量是30台，每台可获利40元。该产确定目标 为： 第一优先级：充分利用装配线每周计划开动40小时； 第二优先级：允许装配线加班，但加班时间尽量不超过10 小时； 第三优先级：装配电视机的数量尽量满足市场需要。因彩 色电视机利润高，取其权系数为2。
2014/3/27
《运筹学》Ⅱ史慧萍
2
2014/3/27
《运筹学》Ⅱ史慧萍
3
第四章：生产安排多目标问题业1
单位利润 生产时间（小时） （元） 一车间 二车间 产品A 产品B 80 100 2 1.5 50 1 2 40
每周生产时间限制
目标：（1）产品B的产量不超过10单位。 （2）利润不低于1600元。 （3）尽量利用二车间生产时间又不加班。
2014-10-20
《运筹学》第六章史慧萍
《运筹学》Ⅱ史慧萍 2014-10-20
7
7

2.橡树山游泳俱乐部的经理正策划该俱乐部的游泳队项目。 第一次分队练习安排在5月1日。以下是所有活动、活动 的的前期活动及活动时间估计（以星期计算）。
时间（周） 活动 A B C D E F 描述 与董事会商议 雇教练 预订泳池 宣布安排 与教练见面 订泳衣 前期工作 乐观的 — A A B,C B A 1 4 2 1 2 1 最可能的 1 6 4 2 3 2 悲观的 2 8 6 3 4 3
第一章作业
• P47 • 1.1（建立线性规划模型并试用图解法求出最优解）
小结：第二章


整数规划是一类特殊的规划问题，其特点是决策变量部分 或全部是整数。如果部分要求是整数，该问题就是混合整 数规划；部分要求全部是整数，该问题就是纯整数规划。 本章介绍了一般整数规划模型及其算法，并重点介绍了分 枝定界法的思想和方法。在此基础上，介绍了特殊的0-1 整数规划模型及其枚举算法及0-1规划问题的具体应用， 包括0-1变量的正确引入，指派问题及匈牙利算法。 作业：2.3、2.4、2.5
《运筹学》Ⅱ史慧萍
2014-10-20
9

3.办公自动化有限公司设计了一份引进一种新的计算机化 办公系统的建议书，这个系统将改善文字处理及办公室内 部交流。该项目书包含了一系列要完成该新办公系统项目 的关键活动。利用以下与活动相关的信息。
描述
计划需求
活动
A
前期活动
—
时间（周） 正常 10 紧缩 8
花费（1000美元） 正常 30 紧缩 70
B
C D E F
订货
装机器 建培训室 管理培训课程 测试系统
A
B A D C,E
8
10 7 10 3
6
7 6 8 3
120
100 40 50 60
150
160 50 75 —
《运筹学》Ⅱ史慧萍
2014-10-20
10
a.设计一个项目网络图。 b.设计一个活动日程表。 c.关键活动有哪些？期望完成时间是多少？ d.假设公司想在6个月或26周之内完成该项目，提出你 关于如何做出紧缩决定的建议，以使项目能够按时间 完成并费用最少？ e.为紧缩项目设计一个活动安排表。 f.要在6个月内完成该项目，要增加多少花费？
第四章 5
2014年4月10日
1.考虑下面这个项目网络图和活动时间（用星期表示）
活动 活动时间 A 5 B 3 C 7 D 6 E 7 F 3 G 10 H 8
C
H
A
开 始
D
F
完 成
B E
G
《运筹学》Ⅱ史慧萍 2014-10-20 6
a.找出关键线路。 b.完成该项目需要多少时间？ c.活动D能否被延期而又不使整个项目受到影响，如果可 以的话，能延期多久？ d.活动C能否被延期而又不使整个项目受到影响，如果可 以的话，能延期多久？ e.活动E的日程表怎样？
G
H I
注册泳员
收费 制定一次训练计划
D
G E,H,F
1
1 1
《运筹学》Ⅱ史慧萍
2
2 1
2014-10-20
3
3 1
8
a.画出一个项目网络图。 b.做一个活动日程表。 c.关键活动有哪些？该项目的期望完成时间是多少？ d.如果该俱乐部经理计划2月1日开始该项目，该项目按 规定时间5月1日（13个星期）完工的可能性有多大？ 该经理是否应该在2月1日前就开始策划该游泳项目？
20+6=26
6
0+10=10
A
10+10=20
10
5 4
20+13=33
13
D
(A,0)
14
(C,19)
0+14=14
C
19+4=23
7
F 4
(E,23)
H
(G,28)
14+5=19
5
5
9 19+8=28 G
(A,14)
14+5=19
(C,19)
由D氏算法可知最短路为：A─C─G─H,最短路长为28。
《运筹学》Ⅱ史慧萍
2014-10-20
11
作业：第七章

1.用D氏算法求出A点到H点的最短路。
10 B 10 10 4 A D 7 F 4 9 5 G 5 E 13
6
H
14
5
C
2014-10-20
《运筹学》Ⅰ 史慧萍
12
解:D氏算法如下
(A,10)
B 10 10 10+10=20 E
(B,20)
A1 A2 A3 销量
2014-10-20
《运筹学》Ⅰ 史慧萍
16
5 50
45 45 15 35
0
5
15
初始调运计划：x12=50,x22=5,x23=45,x31=40,x33=15,x34=20.其 余xij=0。
2014-10-20 《运筹学》Ⅰ 史慧萍 17
0
50
5
10
调整后的调运计划：x12=5,x13=45,x22=50,x31=40,x33=15,x34=20. 其余xij=0。
2014-10-20 《运筹学》Ⅰ 史慧萍 20
2014-10-20 《运筹学》Ⅰ 史慧萍 13

2.v0是一仓库，v9是商店，要求用D（Dijkstra狄克斯屈） 氏算法求出从v0到v9的最短路。
v
1
11 2 5 2 5 4 3 7 9
v
2
2 11 v
011 v3来自3v4
6 3 v 9 6
9
7 4
6 v
6
v
5
4 8
14
v
7 2014-10-20 《运筹学》Ⅰ 史慧萍
(0,0)
0
7
v (0,7)
4+3=7
5
5
6 v
6
v
9
9 11+9=20 (5,11) 6
13+6=19
4
0+4=4
3
7
4+7=11
11+4=15
4
v
7
9
4+9=13
(7,13) (0,4) 由D氏算法可知最短路为：v0─v7─v8─v9,最短路长为19。
2014-10-20 《运筹学》Ⅰ 史慧萍 15
8

4.设有某种物资，需要从A1，A2，A3调往需求地B1，B2，B3， B4，其运价表如下，试制定一个方案（产销平衡），使运费最 小。并求出运费最小方案。
销地(j) 运价(元/吨) 产地(i)
B1 3 7 2 40
B2 1 3 3 55
B3 4 8 9 60
B4 5 6 2 20
产量 50 50 75 175
解:D氏算法如下
(0,2)
v
1
11
2+11=13
v
2
(1,13)
13+6=19
0+2=2
2
2+11=13
11
(0,11)
211+2=13 5 2 4
7+4=11
13+3=16
3
(2,16)
3
6
11 v
v
3
v
11+5=16 11+2=13
4
(8,19)
16+3=19
0+11=11 7+5=12 0+7=7