,运筹学,
安徽水利水电职业技术学院刘舒教材
Operation(al) Research（简写 OR）
直译为：作战研究、运用研究
日本：运用学
中国：运筹学（意译）
教材
,运筹学,,清华大学出版社,运筹学,,
2000年教学目的与方法
教学目的：介绍运筹学各分支体系的基本模型、
求解方法；引导并锻练学生用运筹学知识定量分析与解决实际问题的能力。
教学方法
以各种实际问题为背景，引出各分支基本概念、
基本模型和基本方法，侧重各种方法及应用，回避繁复的数学理论推导。
运用软件教学，并让学生掌握这类软件。
分组进行案例分析与讨论教学内容
运筹学 ABC
线性规划问题
整数规划
目标规划
动态规划
网络规划
排队论
存贮论
对策论
决策论第一章 运筹学 ABC
运筹学 的发展：三个来源
运筹学的性质和特点
运筹学研究的问题与解决方法
运筹学的工作步骤运筹学的发展：三个来源
军 事
管 理
经 济军事：运筹学的主要发源地
古代军事运筹学思想
中国古代的“孙子兵法”在质的论断中渗透着量的分析（ 1981年美国军事运筹学会出版了一本书，
书中第一句话就是说孙武子是世界上第一个军事运筹学的实践家），中国古代运筹学思想的例子还有：田忌赛马、围魏救赵、行军运粮，等等。
国外历史上的阿基米德、伽利略研究过作战问题；
第一次世界大战时，英国的兰彻斯特（ Lanchester）
提出了战斗方程，指出了数量优势、火力和胜负的动态关系；美国的爱迪生为美国海军咨询委员会研究了潜艇攻击和潜艇回避攻击的问题。
运筹学的正式产生：第二次世界大战
鲍德西（ Bawdsey）雷达站的研究
1939年，以 Blackett为首的一个研究小组（代号
,Blackett 马戏团”），研究如何改进英国的空防系统，提高英国本土防空能力。
Blackett备忘录
1941年 12月,Blackett应盟国政府的要求，写了五份题为,Scientists at the Operational Level”的简短备忘录，建议在各大指挥部建立运筹学小组，此建议被迅速采纳。 据不完全统计，二战期间，仅在英、美和加拿大，参加运筹学工作的科学家超过 700名。
大西洋反潜战：研究如何打破德国对英吉利海峡的海上封锁
英国战斗机中队援法的决策管理
泰勒的时间动作研究、甘特的用于生产计划与控制的“甘特图”、吉尔布雷思夫妇的动作研究等
爱尔朗（ Erlong）的排队论公式
1909－ 1920年间，丹麦哥本哈根电话公司工程师爱尔朗陆续发表了关于电话通路数量等方面的分析与计算公式。尤其是 1909年的论文“概率与电话通话理论”，
开创了运筹学的重要分支－－排队论。
经济（数理经济学）
Von Neumann 与对策论
1932年,Von Neumann提出一个广义经济平衡模型； 1939年，提出了一个属于宏观经济优化的控制论模型； 1944年，与 Morgenstern共著的,对策论与经济行为,开创了对策论分支。
康托洛维奇与“生产组织与计划中的数学方法”
30年代，苏联数理经济学家康托洛维奇从事生产组织与管理中的定量化方法研究，取得了很多重要成果。 1939年，出版了堪称运筹学的先驱著作
－－,生产组织与计划中的数学方法,,其思想和模型被归入线性规划范畴。
运筹学的性质和特点
应用科学－“应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，
为决策者选择最优决策提供定量依据”。
运筹学的特点
定量化分析
多学科交叉，如综合利用了心理学、经济学、
物理、化学等方法
最优决策运筹学的研究对象
1）机器、工具、设备、人员等如何最佳利用问题方法有：线性规划、整数规划、网络图、动态规划、目标规划等
2）竞争现象如战争、投资、商品竞争方法是对策论
3）拥挤现象如公共汽车排队、打电话、买东西、飞机着陆、船舶进港等方法是排队论运筹学的工作步骤
1）提出和形成问题，
2）建立模型，
3）求解，
4）解的检验，
5）解的控制，
6）解的实施。
第二章 线性规划
线性规划问题
线性规划模型
线性规划的求解 ------单纯形方法线性规划问题
例 1(广告方式的选择 )中华家电公司推销一种新型洗衣机,有关数据见下表,销售部第一月的广告预算为 20000元,要求至少有 8电视商业节目,15家报纸广告 /电视广告费不得超过 12000元,电台广播至少隔日有一次,现问该公司销售部应当采用怎样的广告宣传计划,才能取得最好的效果?
表 1-1
广告方式 广告费用 (元 /
次 )
可用最高次数 /
月期望的宣传效果 /单位电视台 a(白天,1 分钟 )
500 16 50
电视台 b(晚上,30
钞 )
1000 10 80
每日晨报 /(半版 ) 100 24 30
星期日报 /(半版 ) 300 4 40
广播电台 /(1分钟 ) 80 25 15
解,设 54321
,,,,xxxxx
分别是第一个月内电视台 a,电视台
b,每日晨报,星期日报,广播电台进行广告宣传的次数,则其数学模型为,
m a x 54321
1540308050 xxxxx
s,t,
.0,,,,
,2515,4,24,10,16
,12 00 010 0050 0
,15
,8
,20 00 08030 010 010 0050 0
54321
54321
21
43
21
54321
xxxxx
xxxxx
xx
xx
xx
xxxxx
例 2 长成家电公司准备将一种新型电视机在三家商场进行销售，每一个商场的批发价和推销费及产品的利润如表所示。
由于该电视机的性能良好，各商场都纷纷争购，但公司每月的生产能力有限，
只能生产 1000台，故公司规定：铁路商场至少经销 300台，水上商场至少经销
200台，航空商场至少经销 100台，至多
200台。公司计划在一个月内的广告预算费为 8000元,推销人员最高可用工时数为
1500。同时，公司只根据经销数进行生产，试问公司下个月的市场对策？
表 1-2
经销商场 销售利润
(元 /台 )
广告费
(元 /台 )
推销工时
(小时 /台 )
航空商场 50 12 2
铁路商场 80 7 3
水上商场 70 8 4
解,设 321
,,xxx
分别是为航空,铁路,水上三家商场生产的电视机台数,则其数学模型为,
m a x
,708050
321
xxxz
s,t,
.0,,
,200,300,200100
,1 0 0 0
,1 5 0 0432
,8 0 0 08712
321
321
321
321
321
xxx
xxx
xxx
xxx
xxx
线性规划问题 ( LP ) 的一般形式为,
m i n (m a x)
2211
xcxcz
nn
xc?
s.t.
212111
xaxa
11
),( bxa
nn
222121
xaxa
22
),( bxa
nn
2211
xaxa
mm
mnmn
bxa ),(
,2,1,0 jx
j
n
线性规划问题的标准形式为,
m i n XCz
T
s,t,0?
X
bAX
( 假定 b 为非负 )
注,任何形式的线性规划问题均可化为标准型求解 --单纯形法
将所给问题化为标准形
找出一个初始可行基,建立初始单纯形表
检查所有检验数 (若全为非负,则已得到最优解,计算停止,否则继续下一步 )
考察是否无解 (若是,计算停止,否则继续下一步 )
确定入基变量,出基变量
对初始单纯形表进行单纯形变换第三章 对偶问题和灵敏度分析
原问题? 对偶问题
0
..
m ax
x
bAxts
cxz
0
..
m in
y
cyAts
by
T
0,0
1
553
232..
23m i n
31
321
21
321
321
xx
xxx
xx
xxxts
xxxz
0,0
13
25
332..
52m a x
21
31
321
321
321
yy
yy
yyy
yyyts
yyy?
对偶性质
原问题与对偶问题互为对偶
原问题与对偶问题或都有最优解 (最优值相同 ),两最优解之间存在一定的关系,或都 没有最优解可知,研究对偶问题可以简化计算 (当原问题很复杂时,可先求解对偶问题,再根据一定的关系得出原问题的最优解提出了新的求解方法,对偶单纯形法对偶变量的经济解释
对偶变量 yi在经济上表示原问题第 i种资源的边际贡献,即当第 i种资源增加一个单位时,相应的目标值 z的增量
对偶问题的最优解 yi*是原问题第 i种资源的影子价格应用,1.出租资源或设备时,租金价格的设定 (至少高于该资源在企业内的影子价格 )
2.企业内资源 I的存量设定 (当资源 I的影子价格 >=市场价格时,可买进该资源 ;否则卖出 )
3.调整资源的分配量以增加利润灵敏度分析
基本任务,确定参数的影响范围,即保持某
LP问题的最优基不变的条件下该参数单独变化的最大范围
一个参数的影响范围越小,最优基对这一参数的变化就越敏感,最优基对该参数而言就越不稳定
另一个任务,当最优解随参数变化时如何简便地求得新最优解第四章 运输问题收点 B1 B2 Bn 发量发点
A1 C11
x 11
C12x
12
… C1n
x1n
a1
…
Am Cm1
xm1
Cm2
xm2
Cmn
xmn
am
收量 b1 b2 bn
平衡运输问题的模型
Min z=
S.t,ij
m
i
n
j
ij xc
1 1
n
j
j
m
i
iij
j
m
i
ij
i
n
j
ij
baox
bx
ax
11
1
1
平衡运输问题的求解 ---表上作业法
找一个初始基可行解 ;
方法,最小元素法 /Vogel近似法 (VAM)
检验,若所有的检验数都小于零,最优解已得,否则继续下一步 ;
方法,位势检验法
调整,得到一个新的基可行解,重复第二步,
方法,闭回路法运输问题的实例
东风电机公司接到上海一家商场 (B1),青岛一家商场 (B2),西安一家商场 (B3)各一份订单,要求下月供应电机,B1的需求量为 100台,B2的需求量为
80台,而 B3要求供应 120台,该公司在北京和武汉设有两个仓库 (A1,A2),预计 A1,A2下月的库存量分别为 200台和 150台,已知每个仓库到每家商场运送 1 台电机的费用如表所示,问该公司应如何调运电机,才能既满足用户的需要又使总的运费最少?
B1 B2 B3
A1
15 21 18
A2
20 25 16
第五章 指派问题
设有 n 个人 A1,A2,…A n,要分派去做 n件事 B1,
B2… Bn,要求每一件事都 必须有一个人去做,而且不同的事由不同的人去做,已知每个人 Ai做每件事 Bj的效率 (如劳动工时或成本,或创造的价值等 )为 Cij,问应如何进行指派 (哪个人做哪件事 ),才能使 工作效益最好 (如工时最少,或成本最低,或创造的价值最大 )?
指派问题既可以说是运输问题的特殊情形,也可以说是整数规划的特殊情形,
指派问题的数学模型
Min z=
S.t,01 1 ij
n
i
n
j
ijij cxc
1/0
1
1
1
1
ij
n
i
ij
n
j
ij
x
x
x
举例
有 4 个工人,要指派他们分别完成 4 项工作,每人做各项工作所消耗的时间如下表,
问如何指派使总的消耗时间最小?
人 工作 A B C D
甲 15 18 21 24
乙 19 23 22 18
丙 26 17 16 19
丁 19 21 23 17
第六章 目标规划
多目标 的线性规划问题 (多目标 决策 ),而非单目标,
其模型是在线性模型的基础上,利用正负偏差变量 (d+,d-),优先因子 (pk,pk>>pk+1),权系数,
对同等级或不同等级的目标进行设置,
因其模型结构与线性规划的数学模型结构没有本质的区别,所以可用单纯形法求解,
举例
某商店有五位工作人员,经理 1人,主任 1人,售货员 3人,有关情况见下表,设广告费对销售额的贡献为其投入的 15倍,各工作人员的收入相当于其完成销售额的 5.5%.问如何安排才能达到以下的目标,P1保证全体人员正常工作时间 ;P2 至少完成销售额 70000元 ;P3主任的月收入不少于
1200元,售货员 A和 B的月收入不少于 600元和
400元 ;P4 全体人员加班时间不超过规定 ; P5广告费不超过 3000元,力争销售额增加 10000元,前者的重要性为后者的两倍,
每小时对销售额的贡献 (元 )
每月总工时每月加班限量 (工时 )
经理 144 200 24
主任 96 200 24
售货员 A 54 172 52
售货员 B 30 160 32
售货员 C 9 100 32
第七章 整数规划
最优解不是分数或小数,而是整数的情形,
整数规划的一种特殊情形是 0-1规划,如指派问题,
整数规划的解法有割平面法、分枝定界法。 0-1规划的解法有 0-1隐枚举法,
整数规划纯整数规划混合整数规划运用 0-1规划的实际问题
关于固定费用的问题
相互排斥的约束条件
投资场所的选定 ------相互排斥的计划
例,某公司拟在市东、西、南三区建立门市部,拟议中有 7个位置 Ai（ i=1,2,…7 ）可供选择,规定,在东区,由 A1,A2,A3三个点中至多选两个 ;在西区,由
A4,A5两个点中至少选一个 ;在南区,由 A6,A7两个点中至少选一个,如选用 Ai点设备投资估计为 bi元,每年可获利润估计为 ci元,但投资总额不能超过 B元,
问如何选择使年利润最大?
建模解,先引入 0-1变量,令于是,max z=
Xi=
1,当 Ai点被选用
0,当 Ai点没被选用
i
i
ixc?
7
1
,1
,1
1/0,2
,
76
54
321
7
1
xx
xx
xxxx
xb
i
i
i
i
第八章 图与网络分析
著名哥尼斯堡七桥问题,欧拉 (1736).
中国邮递员问题：中国管梅谷（ 1962）
C D
A A
C B
D
B
1 3 5
2 4 6
网络规划问题
最小支撑树问题 网络最大流问题
最短路问题 最小费用流问题将庞大复杂的工程系统和管理问题用图描述,可以解决工程设计和管理决策的最优化,
问题,如,完成任务的时间最少,距离最短,费用最省等等,
第九章 网络计划 (PERT技术 )
特别适用于生产技术复杂,工作项目繁多且联系紧密的一些跨部门的工作计划,如新产品开发、大型的工程项目,还可以应用在人力、物力、财力等资源的安排,
编制网络计划包括绘制网络图、计算时间参数、确定关键路线、网络优化等环节,
第十章 动态规划
解决多阶段决策过程最优化,
只是求解某类问题的一种方法,是考察问题的一种途径,而不是一种特殊算法 (如线性规划是一种算法 ),因而没有一个标准的数学表达式和明确定义的一组规则,
必须对具体问题进行具体分析处理,
动态规划方法的基本思想
动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件 (即基本方程 ).所以,必须先将问题的过程分成几个相互联系的阶段,恰当地选取状态变量和决策变量及定义最优值函数,从而把一个大问题化成一族同类型的子问题,然后逐个求解,
动态规划的应用 ------定价问题
例,某厂要确定一种新产品在今后五年内的价格,并已拟定只在 5,6,7,8元这四种单价中进行选择,据预测,今后五年不同价格下每年盈利 (万元 )如下表所示,但是各相邻年度价格不得超过 1元,问今后五年内每年定价各为多少,可预期五年总利润最大?
上表年价格
1 2 3 4 5
5 9 2 4 5 8
6 7 5 8 6 4
7 6 5 9 7 3
8 8 7 6 6 4
第十二章 决策论
决策过程
不确定型的决策
悲观主义决策准则、乐观主义决策准则、
等可能性准则、最小机会损失准则、折衷主义准则
风险决策
最大期望值决策准则、最小机会损失决策准则第十一章 对策论 (博弈论 )
二人或多人竞争或对抗活动
基本概念,局中人、策略集、支付函数
矩阵对策记为,G=｛ I,II;S1,S2;A｝或
G=｛ S1,S2;A｝,其中 A为某局中人的支付矩阵,
矩阵对策的解法
安徽水利水电职业技术学院刘舒教材
Operation(al) Research（简写 OR）
直译为：作战研究、运用研究
日本：运用学
中国：运筹学（意译）
教材
,运筹学,,清华大学出版社,运筹学,,
2000年教学目的与方法
教学目的：介绍运筹学各分支体系的基本模型、
求解方法；引导并锻练学生用运筹学知识定量分析与解决实际问题的能力。
教学方法
以各种实际问题为背景，引出各分支基本概念、
基本模型和基本方法，侧重各种方法及应用，回避繁复的数学理论推导。
运用软件教学，并让学生掌握这类软件。
分组进行案例分析与讨论教学内容
运筹学 ABC
线性规划问题
整数规划
目标规划
动态规划
网络规划
排队论
存贮论
对策论
决策论第一章 运筹学 ABC
运筹学 的发展：三个来源
运筹学的性质和特点
运筹学研究的问题与解决方法
运筹学的工作步骤运筹学的发展：三个来源
军 事
管 理
经 济军事：运筹学的主要发源地
古代军事运筹学思想
中国古代的“孙子兵法”在质的论断中渗透着量的分析（ 1981年美国军事运筹学会出版了一本书，
书中第一句话就是说孙武子是世界上第一个军事运筹学的实践家），中国古代运筹学思想的例子还有：田忌赛马、围魏救赵、行军运粮，等等。
国外历史上的阿基米德、伽利略研究过作战问题；
第一次世界大战时，英国的兰彻斯特（ Lanchester）
提出了战斗方程，指出了数量优势、火力和胜负的动态关系；美国的爱迪生为美国海军咨询委员会研究了潜艇攻击和潜艇回避攻击的问题。
运筹学的正式产生：第二次世界大战
鲍德西（ Bawdsey）雷达站的研究
1939年，以 Blackett为首的一个研究小组（代号
,Blackett 马戏团”），研究如何改进英国的空防系统，提高英国本土防空能力。
Blackett备忘录
1941年 12月,Blackett应盟国政府的要求，写了五份题为,Scientists at the Operational Level”的简短备忘录，建议在各大指挥部建立运筹学小组，此建议被迅速采纳。 据不完全统计，二战期间，仅在英、美和加拿大，参加运筹学工作的科学家超过 700名。
大西洋反潜战：研究如何打破德国对英吉利海峡的海上封锁
英国战斗机中队援法的决策管理
泰勒的时间动作研究、甘特的用于生产计划与控制的“甘特图”、吉尔布雷思夫妇的动作研究等
爱尔朗（ Erlong）的排队论公式
1909－ 1920年间，丹麦哥本哈根电话公司工程师爱尔朗陆续发表了关于电话通路数量等方面的分析与计算公式。尤其是 1909年的论文“概率与电话通话理论”，
开创了运筹学的重要分支－－排队论。
经济（数理经济学）
Von Neumann 与对策论
1932年,Von Neumann提出一个广义经济平衡模型； 1939年，提出了一个属于宏观经济优化的控制论模型； 1944年，与 Morgenstern共著的,对策论与经济行为,开创了对策论分支。
康托洛维奇与“生产组织与计划中的数学方法”
30年代，苏联数理经济学家康托洛维奇从事生产组织与管理中的定量化方法研究，取得了很多重要成果。 1939年，出版了堪称运筹学的先驱著作
－－,生产组织与计划中的数学方法,,其思想和模型被归入线性规划范畴。
运筹学的性质和特点
应用科学－“应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，
为决策者选择最优决策提供定量依据”。
运筹学的特点
定量化分析
多学科交叉，如综合利用了心理学、经济学、
物理、化学等方法
最优决策运筹学的研究对象
1）机器、工具、设备、人员等如何最佳利用问题方法有：线性规划、整数规划、网络图、动态规划、目标规划等
2）竞争现象如战争、投资、商品竞争方法是对策论
3）拥挤现象如公共汽车排队、打电话、买东西、飞机着陆、船舶进港等方法是排队论运筹学的工作步骤
1）提出和形成问题，
2）建立模型，
3）求解，
4）解的检验，
5）解的控制，
6）解的实施。
第二章 线性规划
线性规划问题
线性规划模型
线性规划的求解 ------单纯形方法线性规划问题
例 1(广告方式的选择 )中华家电公司推销一种新型洗衣机,有关数据见下表,销售部第一月的广告预算为 20000元,要求至少有 8电视商业节目,15家报纸广告 /电视广告费不得超过 12000元,电台广播至少隔日有一次,现问该公司销售部应当采用怎样的广告宣传计划,才能取得最好的效果?
表 1-1
广告方式 广告费用 (元 /
次 )
可用最高次数 /
月期望的宣传效果 /单位电视台 a(白天,1 分钟 )
500 16 50
电视台 b(晚上,30
钞 )
1000 10 80
每日晨报 /(半版 ) 100 24 30
星期日报 /(半版 ) 300 4 40
广播电台 /(1分钟 ) 80 25 15
解,设 54321
,,,,xxxxx
分别是第一个月内电视台 a,电视台
b,每日晨报,星期日报,广播电台进行广告宣传的次数,则其数学模型为,
m a x 54321
1540308050 xxxxx
s,t,
.0,,,,
,2515,4,24,10,16
,12 00 010 0050 0
,15
,8
,20 00 08030 010 010 0050 0
54321
54321
21
43
21
54321
xxxxx
xxxxx
xx
xx
xx
xxxxx
例 2 长成家电公司准备将一种新型电视机在三家商场进行销售，每一个商场的批发价和推销费及产品的利润如表所示。
由于该电视机的性能良好，各商场都纷纷争购，但公司每月的生产能力有限，
只能生产 1000台，故公司规定：铁路商场至少经销 300台，水上商场至少经销
200台，航空商场至少经销 100台，至多
200台。公司计划在一个月内的广告预算费为 8000元,推销人员最高可用工时数为
1500。同时，公司只根据经销数进行生产，试问公司下个月的市场对策？
表 1-2
经销商场 销售利润
(元 /台 )
广告费
(元 /台 )
推销工时
(小时 /台 )
航空商场 50 12 2
铁路商场 80 7 3
水上商场 70 8 4
解,设 321
,,xxx
分别是为航空,铁路,水上三家商场生产的电视机台数,则其数学模型为,
m a x
,708050
321
xxxz
s,t,
.0,,
,200,300,200100
,1 0 0 0
,1 5 0 0432
,8 0 0 08712
321
321
321
321
321
xxx
xxx
xxx
xxx
xxx
线性规划问题 ( LP ) 的一般形式为,
m i n (m a x)
2211
xcxcz
nn
xc?
s.t.
212111
xaxa
11
),( bxa
nn
222121
xaxa
22
),( bxa
nn
2211
xaxa
mm
mnmn
bxa ),(
,2,1,0 jx
j
n
线性规划问题的标准形式为,
m i n XCz
T
s,t,0?
X
bAX
( 假定 b 为非负 )
注,任何形式的线性规划问题均可化为标准型求解 --单纯形法
将所给问题化为标准形
找出一个初始可行基,建立初始单纯形表
检查所有检验数 (若全为非负,则已得到最优解,计算停止,否则继续下一步 )
考察是否无解 (若是,计算停止,否则继续下一步 )
确定入基变量,出基变量
对初始单纯形表进行单纯形变换第三章 对偶问题和灵敏度分析
原问题? 对偶问题
0
..
m ax
x
bAxts
cxz
0
..
m in
y
cyAts
by
T
0,0
1
553
232..
23m i n
31
321
21
321
321
xx
xxx
xx
xxxts
xxxz
0,0
13
25
332..
52m a x
21
31
321
321
321
yy
yy
yyy
yyyts
yyy?
对偶性质
原问题与对偶问题互为对偶
原问题与对偶问题或都有最优解 (最优值相同 ),两最优解之间存在一定的关系,或都 没有最优解可知,研究对偶问题可以简化计算 (当原问题很复杂时,可先求解对偶问题,再根据一定的关系得出原问题的最优解提出了新的求解方法,对偶单纯形法对偶变量的经济解释
对偶变量 yi在经济上表示原问题第 i种资源的边际贡献,即当第 i种资源增加一个单位时,相应的目标值 z的增量
对偶问题的最优解 yi*是原问题第 i种资源的影子价格应用,1.出租资源或设备时,租金价格的设定 (至少高于该资源在企业内的影子价格 )
2.企业内资源 I的存量设定 (当资源 I的影子价格 >=市场价格时,可买进该资源 ;否则卖出 )
3.调整资源的分配量以增加利润灵敏度分析
基本任务,确定参数的影响范围,即保持某
LP问题的最优基不变的条件下该参数单独变化的最大范围
一个参数的影响范围越小,最优基对这一参数的变化就越敏感,最优基对该参数而言就越不稳定
另一个任务,当最优解随参数变化时如何简便地求得新最优解第四章 运输问题收点 B1 B2 Bn 发量发点
A1 C11
x 11
C12x
12
… C1n
x1n
a1
…
Am Cm1
xm1
Cm2
xm2
Cmn
xmn
am
收量 b1 b2 bn
平衡运输问题的模型
Min z=
S.t,ij
m
i
n
j
ij xc
1 1
n
j
j
m
i
iij
j
m
i
ij
i
n
j
ij
baox
bx
ax
11
1
1
平衡运输问题的求解 ---表上作业法
找一个初始基可行解 ;
方法,最小元素法 /Vogel近似法 (VAM)
检验,若所有的检验数都小于零,最优解已得,否则继续下一步 ;
方法,位势检验法
调整,得到一个新的基可行解,重复第二步,
方法,闭回路法运输问题的实例
东风电机公司接到上海一家商场 (B1),青岛一家商场 (B2),西安一家商场 (B3)各一份订单,要求下月供应电机,B1的需求量为 100台,B2的需求量为
80台,而 B3要求供应 120台,该公司在北京和武汉设有两个仓库 (A1,A2),预计 A1,A2下月的库存量分别为 200台和 150台,已知每个仓库到每家商场运送 1 台电机的费用如表所示,问该公司应如何调运电机,才能既满足用户的需要又使总的运费最少?
B1 B2 B3
A1
15 21 18
A2
20 25 16
第五章 指派问题
设有 n 个人 A1,A2,…A n,要分派去做 n件事 B1,
B2… Bn,要求每一件事都 必须有一个人去做,而且不同的事由不同的人去做,已知每个人 Ai做每件事 Bj的效率 (如劳动工时或成本,或创造的价值等 )为 Cij,问应如何进行指派 (哪个人做哪件事 ),才能使 工作效益最好 (如工时最少,或成本最低,或创造的价值最大 )?
指派问题既可以说是运输问题的特殊情形,也可以说是整数规划的特殊情形,
指派问题的数学模型
Min z=
S.t,01 1 ij
n
i
n
j
ijij cxc
1/0
1
1
1
1
ij
n
i
ij
n
j
ij
x
x
x
举例
有 4 个工人,要指派他们分别完成 4 项工作,每人做各项工作所消耗的时间如下表,
问如何指派使总的消耗时间最小?
人 工作 A B C D
甲 15 18 21 24
乙 19 23 22 18
丙 26 17 16 19
丁 19 21 23 17
第六章 目标规划
多目标 的线性规划问题 (多目标 决策 ),而非单目标,
其模型是在线性模型的基础上,利用正负偏差变量 (d+,d-),优先因子 (pk,pk>>pk+1),权系数,
对同等级或不同等级的目标进行设置,
因其模型结构与线性规划的数学模型结构没有本质的区别,所以可用单纯形法求解,
举例
某商店有五位工作人员,经理 1人,主任 1人,售货员 3人,有关情况见下表,设广告费对销售额的贡献为其投入的 15倍,各工作人员的收入相当于其完成销售额的 5.5%.问如何安排才能达到以下的目标,P1保证全体人员正常工作时间 ;P2 至少完成销售额 70000元 ;P3主任的月收入不少于
1200元,售货员 A和 B的月收入不少于 600元和
400元 ;P4 全体人员加班时间不超过规定 ; P5广告费不超过 3000元,力争销售额增加 10000元,前者的重要性为后者的两倍,
每小时对销售额的贡献 (元 )
每月总工时每月加班限量 (工时 )
经理 144 200 24
主任 96 200 24
售货员 A 54 172 52
售货员 B 30 160 32
售货员 C 9 100 32
第七章 整数规划
最优解不是分数或小数,而是整数的情形,
整数规划的一种特殊情形是 0-1规划,如指派问题,
整数规划的解法有割平面法、分枝定界法。 0-1规划的解法有 0-1隐枚举法,
整数规划纯整数规划混合整数规划运用 0-1规划的实际问题
关于固定费用的问题
相互排斥的约束条件
投资场所的选定 ------相互排斥的计划
例,某公司拟在市东、西、南三区建立门市部,拟议中有 7个位置 Ai（ i=1,2,…7 ）可供选择,规定,在东区,由 A1,A2,A3三个点中至多选两个 ;在西区,由
A4,A5两个点中至少选一个 ;在南区,由 A6,A7两个点中至少选一个,如选用 Ai点设备投资估计为 bi元,每年可获利润估计为 ci元,但投资总额不能超过 B元,
问如何选择使年利润最大?
建模解,先引入 0-1变量,令于是,max z=
Xi=
1,当 Ai点被选用
0,当 Ai点没被选用
i
i
ixc?
7
1
,1
,1
1/0,2
,
76
54
321
7
1
xx
xx
xxxx
xb
i
i
i
i
第八章 图与网络分析
著名哥尼斯堡七桥问题,欧拉 (1736).
中国邮递员问题：中国管梅谷（ 1962）
C D
A A
C B
D
B
1 3 5
2 4 6
网络规划问题
最小支撑树问题 网络最大流问题
最短路问题 最小费用流问题将庞大复杂的工程系统和管理问题用图描述,可以解决工程设计和管理决策的最优化,
问题,如,完成任务的时间最少,距离最短,费用最省等等,
第九章 网络计划 (PERT技术 )
特别适用于生产技术复杂,工作项目繁多且联系紧密的一些跨部门的工作计划,如新产品开发、大型的工程项目,还可以应用在人力、物力、财力等资源的安排,
编制网络计划包括绘制网络图、计算时间参数、确定关键路线、网络优化等环节,
第十章 动态规划
解决多阶段决策过程最优化,
只是求解某类问题的一种方法,是考察问题的一种途径,而不是一种特殊算法 (如线性规划是一种算法 ),因而没有一个标准的数学表达式和明确定义的一组规则,
必须对具体问题进行具体分析处理,
动态规划方法的基本思想
动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件 (即基本方程 ).所以,必须先将问题的过程分成几个相互联系的阶段,恰当地选取状态变量和决策变量及定义最优值函数,从而把一个大问题化成一族同类型的子问题,然后逐个求解,
动态规划的应用 ------定价问题
例,某厂要确定一种新产品在今后五年内的价格,并已拟定只在 5,6,7,8元这四种单价中进行选择,据预测,今后五年不同价格下每年盈利 (万元 )如下表所示,但是各相邻年度价格不得超过 1元,问今后五年内每年定价各为多少,可预期五年总利润最大?
上表年价格
1 2 3 4 5
5 9 2 4 5 8
6 7 5 8 6 4
7 6 5 9 7 3
8 8 7 6 6 4
第十二章 决策论
决策过程
不确定型的决策
悲观主义决策准则、乐观主义决策准则、
等可能性准则、最小机会损失准则、折衷主义准则
风险决策
最大期望值决策准则、最小机会损失决策准则第十一章 对策论 (博弈论 )
二人或多人竞争或对抗活动
基本概念,局中人、策略集、支付函数
矩阵对策记为,G=｛ I,II;S1,S2;A｝或
G=｛ S1,S2;A｝,其中 A为某局中人的支付矩阵,
矩阵对策的解法
