《管理运筹学》提纲Word文档下载推荐.docx
《《管理运筹学》提纲Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《《管理运筹学》提纲Word文档下载推荐.docx（44页珍藏版）》请在冰点文库上搜索。
管理科学的发展，定量越来越多。
但定量不可替代定性。
1.5运筹学的模型
♦模型：
真实事物的模仿，主要因素、相互关系、系统结构。
♦形象模型：
如地球仪、沙盘、风洞
♦模拟模型：
建港口，模拟船只到达。
学生模拟企业管理系统运行。
♦数学模型：
用符号或数学工具描述现实系统。
V=F（xi,yj,uk）G（xi,yj,uk）≥0
1.6运筹学的学科体系
♦规划论：
线性规划、非线性规划|、整数规划、目标规划、动态规划
♦图论与网络
♦存储论
♦排队论
♦决策论
♦对策论
♦计算机仿真
1.7运筹学的工作步骤
♦确定问题
♦搜集数据建立模型
♦检验模型
♦求解模型
♦结果分析
♦结果实施
1.8运筹学与计算机
♦计算机为运筹学提供解题工具。
♦本书有现成的程序可以利用
♦要学会解题的思路与方法，建立模型很重要。
第二章线性规划与单纯形法
♦2.1LP（linearprogramming）的基本概念
LP是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。
LP有一组有待决策的变量，
一个线性的目标函数，
一组线性的约束条件。
2.1.1LP的数学模型
例题1—生产计划问题
♦某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：
例题1建模
♦问题：
如何安排生产计划，使得获利最多？
♦步骤：
1、确定决策变量：
设生产A产品x1kg,B产品x2kg
2、确定目标函数：
maxZ=70X1+120X2
3、确定约束条件：
人力约束9X1+4X2≤360
设备约束4X1+5X2≤200
原材料约束3X1+10X2≤300
非负性约束X1≥0X2≥0
例题2——配方问题
♦养海狸鼠饲料中营养要求：
VA每天至少700克，VB每天至少30克，VC每天刚好200克。
现有五种饲料，搭配使用，饲料成分如下表：
例题2建模
♦设抓取饲料Ix1kg;
饲料IIx2kg;
饲料IIIx3kg……
♦目标函数：
最省钱minZ=2x1+7x2+4x3+9x4+5x5
♦约束条件：
3x2+2x2+x3+6x4+18x5≥700
营养要求：
x1+0.5x2+0.2x3+2x4+0.5x5≥30
0.5x1+x2+0.2x3+2x4+0.8x5=200
用量要求：
x1≤50,x2≤60,x3≤50,x4≤70,x5≤40
非负性要求：
x1≥0,x2≥0,x3≥0,x4≥0,x5≥0
例题3：
人员安排问题
♦医院护士24小时值班，每次值班8小时。
不同时段需要的护士人数不等。
据统计：
例题3建模
minZ=x1+x2+x3+x4+x5+x6
x1+x2≥70
x2+x3≥60
x3+x4≥50
x4+x5≥20
x5+x6≥30
非负性约束：
xj≥0,j=1,2,…6
归纳：
线性规划的一般模式
max（min）Z=c1x1+c2x2+c3x3+…+cnxn
a11x1+a12x2+a13x3+…+a1nxn≤（=≥）b1
a21x1+a22x2+a23x3+…+a2nxn≤（=≥）b2
…………
am1x1+am2x2+am3x3+…+amnxn≤（=≥）bn
x1≥0,x2≥0,…,xn≥0
2.1.2线性规划图解法
♦由中学知识可知：
y=ax+b是一条直线，同理：
Z=70x1+120x2→x2=70/120x1-Z/120也是一条直线，以Z为参数的一族等值线。
9x1+4x2≤360→x1≤360/9-4/9x2
是直线x1=360/9-4/9x2下方的半平面。
所有半平面的交集称之为可行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解。
例1图示
.
概念
♦概念：
1、可行解：
满足所有约束条件的解。
2、可行域：
即可行解的集合。
所有约束条件的交集，也就是各半平面的公共部分。
满足所有约束条件的解的集合，称为可行域。
3、基解：
约束条件的交点称为基解（直观）
4、基可行解：
基解当中的可行解。
5、凸集：
集合内任意两点的连线上的点均属于这个集合。
如：
实心球、三角形
结论
♦可行域是个凸集
♦可行域有有限个顶点
♦最优值在可行域的顶点上达到
♦无穷多解的情形
♦无界解情形
♦无解情形
2.1.3线性规划的标准型
♦代数式maxZ=c1x1+c2x2+…+cnxn
a11x1+a12x2+…+a1nxn=b1
a21x1+a22x2+…+a2nxn=b2
………
am1x1+am2x2+…+amnxn=bm
xj≥0j=1,2,…,n
线性规划的标准型
♦和式：
maxZ=∑cjxj
∑aijxj=bii=1,2,…,m
♦向量式：
maxZ=CX
∑pjxj=bii=1,2,…,m
C=（c1,c2,c3,…,cn）
X=（X1,X2,X3,…,Xn）T
♦矩阵式：
maxZ=CXAX=bX≥0
其中：
b=（b1,b2,…,bm）T
a11a12….a1n
A=a21a22…a2n
am1am2…amn
标准型的特征
♦目标函数极大化
♦约束条件为等式
♦决策变量非负
非标准型转化为标准型
♦目标函数极小化转为极大化：
minZ=－max（－Z），一个数的极小化等价于其相反数的极大化。
♦不等式约束的转化：
∑aijxj≤bi加入松弛变量
∑aijxj≥bi减去剩余变量
♦非正变量：
即xk≤0则令x’k=－xk
自由变量：
即xk无约束，令xk=x’k－x”k
非标准型转化举例之一
maxZ=70X1+120X2maxZ=70X1+120X2
9X1+4X2≤3609X1+4X2+X3=360
4X1+5X2≤2004X1+5X2+x4=200
3X1+10X2≤3003X1+10X2+x5=300
X1≥0X2≥0Xj≥0j=1,2,…,5
非标准型转化举例之二
minZ=x1+2x2-3x3maxZ’=x’1－2x2+3（x’3－x”3）
x1+x2+x3≤9－x’1+x2+x’3－x”3+x4=9
-x1-2x2+x3≥2x’1－2x2+x’3－x”3-x5=2
3x1+x2-3x3=5－3x’1+x2－3（x’3－x”3）=5
x1≤0x2≥0x3无约束x’1≥0x2≥0x’3≥0
x”3≥0x4≥0x5≥0
2.1.4基可行解
♦基的概念：
如前所述LP标准型
和式：
maxZ=∑cjxj∑aijxj=bixj≥0j=1,2,…,n
矩阵式：
maxZ=CXAX=bX≥0
约束方程的系数矩阵A的秩为m，且m<
n。
设A=B+N，B是A中mm阶非奇异子矩阵，则称B是LP的一个基，即：
B是A中m个线性无关向量组。
基解的概念
不失一般性,设B是A的前m列,即B=（p1,p2,…,pm）,其相对应的变量XB=（x1,x2,…,xm）T,称为基变量；
其余变量XN=（Xm+1,…,Xn）T称为非基变量。
令所有非基变量等于零,则X=（x1,x2,…xm,0,…,0）T称为基解。
基可行解的概念
♦基可行解：
基解可正可负，负则不可行（违背非负性约束条件），称满足所有约束条件的基解为基可行解。
♦退化的基可行解：
若某个基变量取值为零，则称之为退化的基可行解。
♦基解的数目：
最多Cmn=n!
/m!
（n-m）!
例题6基可行解说明
maxZ=70X1+120X2P1P2P3P4P5
9X1+4X2+X3=36094100
4X1+5X2+x4=200A=45010
3X1+10X2+x5=300310001
Xj≥0j=1,2,…,5
这里m=3,n=5。
Cmn=10
♦基（p3,p4,p5），令非基变量x1,x2=0，则基变量x3=360,x4=200,x5=300,可行解
♦基（p2,p4,p5）,令非基变量x1=0,x3=0基变量x2=90,x4=－250,x5=－600.非可行解
♦基（p2,p3,p4），令非基变量x1,x5=0，则基变量x2=30,x3=240,x4=50,可行解（P21图）
2.2单纯形法
♦2.2.1初始基可行解的确定
从系数矩阵中找到一个可行基B，不妨设B由A的前m列组成，即B=（P1,P2,……Pm）。
进行等价变换－－约束方程两端分别左乘B－1得
X1++a’1m+1xm+1+…+a’1nxn=b’1
x2++a’2m+1xm+1+…+a’2nxn=b’2
……………………………..
xm+a’mm+1xm+1+…+a’mnxn=b’m
令非基变量为0，得基可行解
X（0）=（b1’，b2’，……bm，0，……0）Tz0=∑cibi’
♦2.2.2最优性检验：
LP经过若干步迭代，成为如下形式：
X1++a’1m+1xm+1+…+a’1nxn=b’1x1=b’1-∑a’1jxj
x2++a’2m+1xm+1+…+a’2nxn=b’2x2=b’2-∑a’2jxj
……………………………..……………..
xm+a’mm+1xm+1+…+a’mnxn=b’mxm=b’m-∑a’mjxj
单纯形法
一般性表示：
xi=b’i-∑a’ijxji=1,2,…m将xi代入目标函数得：
Z=∑cjxj
=∑cixi+∑cjxj
=∑ci（b’i-∑a’ijxj）+∑cjxj
=∑cibi’+∑（cj-∑cia’ij）xj
令：
σj=cj-∑cia’ijz0=∑cibi’则Z=z0+∑σjxj
σj判别准则：
σj≤0时,达到最优解
♦2.2.2基变换
若存在σj≥0，则取max{σj}=σK，相应之非基变量XK若取非零，将使Z增加,故令XK进基。
令XK≠0，其余非基变量保持为零。
XK原是非基变量，取零值，若XK≠0将迫使某个原基变量为零，当XK取值超过任意b’i/a’ik时,将破坏非负性条件,于是令θ=min{b’i/a’ika’ik>
0}=b’L/a’Lk。
这时原基变量XL=0，由基变量变成非基变量，
a’Lk处在变量转换的交叉点上，称之为枢轴元素
单纯形法解题举例
单纯形表的格式：
2.2.3单纯形法的计算步骤
♦找到初始可行基，建立单纯形表
♦计算检验数，若所有σj≤0则得最优解，结束。
否则转下步
♦若某σK≥0而P’K≤0，则最优解无界，结束。
♦根据max{σj}=σK原则确定XK进基变量；
根据θ规则：
θ=min{b’i/a’ika’ik>
0}=b’L/a’Lk确定XL为出基变量
♦以a’Lk为枢轴元素进行迭代，回到第二步
2.3单纯形法的进一步探讨
♦2.3.1极小化问题直接求解：
检验数的判别由所有σj≤0即为最优，变为所有σj≥0则为最优。
♦人工变量法之一：
大M法人工变量价值系数M例
♦人工变量法之二：
构造目标函数，分阶段求解例
♦2.3.2无穷多最优解情形：
非基变量检验数σj=0
♦2.3.3退化解的情形：
有两个以上θ值相等
2.3.4单纯形法的计算机求解
♦程序说明
♦应用举例
例题1
例题2
2.5LP应用举例之一
♦例13合理下料问题
料长7.4米，截成2.9、2.1、1.5米各200根。
如何截取余料最少？
关键：
设变量。
应用举例之二
♦例14混合配方问题
A、B、C、D四种原料配制三种产品，三类约束：
技术要求、原料限量、市场容量。
已知产品价格和原料价格，求利润最大的配方。
应用举例之三
♦例15.滚动投资问题
兹有100万元闲钱，投资方向有四：
应用举例之四
♦例16动态生产计划问题
工厂做n个月的生产计划，第j月需求量dj、正常生产能力aj、加班生产能力bj、正常生产成本cj、加班生产成本ej、库存能力为I、库存费用hj，设期初、期末库存为零。
求费用最小的生产计划。
设第月正常生产xj件，加班生产件yj，存储zj件。
则：
本期生产+上期库存-本期库存=本期需求
第三章对偶问题与灵敏度分析
♦要求：
了解LP对偶问题的实际背景
了解对偶问题的建立规则与基本性质
掌握对偶最优解的计算及其经济解释
掌握LP的灵敏度分析
理解计算机输出的影子价格与灵敏度分析的内容
3.1对偶问题
♦3.1.1对偶问题的提出
回顾例题1：
现在A、B两产品销路不畅，可以将所有资源出租或外卖，现在要谈判，我们的价格底线是什么？
对偶模型
♦设每个工时收费Y1元，设备台时费用Y2元，原材料附加费Y3元。
出租收入不低于生产收入：
9y1+4y2+3y3≥70
4y1+5y2+10y3≥120
目标：
ω=360y1+200y2+300y3
出租收入越多越好？
至少不低于某数
原问题与对偶问题之比较
原问题：
对偶问题：
maxZ=70X1+120X2minω=360y1+200y2+300y3
9X1+4X2≤3609y1+4y2+3y3≥70
4X1+5X2≤200（3.1）4y1+5y2+10y3≥120（3.2）
3X1+10X2≤300y1≥0,y2≥0,y3≥0
X1≥0X2≥0
3.1.2对偶规则
原问题一般模型：
对偶问题一般模型：
maxZ=CXminω=Yb
AX≤bYA≥C
X≥0Y≥0
对偶规则
♦原问题有m个约束条件，对偶问题有m个变量
♦原问题有n个变量，对偶问题有n个约束条件
♦原问题的价值系数对应对偶问题的右端项
♦原问题的右端项对应对偶问题的价值系数
♦原问题的技术系数矩阵转置后为对偶问题系数矩阵
♦原问题的约束条件与对偶问题方向相反
♦原问题与对偶问题优化方向相反
对偶规则简捷记法
♦原问题标准则对偶问题标准
♦原问题不标准则对偶问题不标准
♦例题2maxω=7y1+4y2-2y3
minZ=3x1+2x2-6x3+x52y1+y2-y3≤3
2x1+x2-4x3+x4+3x5≥7y1+3y3≤2
x1+2x3-x4≤4-4y1+2y2≤-6
-x1+3x2-x4+x5=-2y1-y2-y3≥0
x1，x2，x3≥0;
3y1+y3=1
x4≤0;
x5无限制y1≥0y2≤0y3无约束
3.1.3对偶问题的基本性质
♦对称性：
对偶问题的对偶问题是原问题
♦弱对偶性：
极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值（鞍型图）
♦无界性：
原问题无界，对偶问题无可行解
♦对偶定理：
若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。
若原问题最优基为B，则其对偶问题最优解Y*=CBB-1
3.1.4对偶最优解的经济解释—影子价格
♦Z=ω=CX=YbZ/b=（Yb）’=Y
♦Z=Yb=∑yibi的意义：
Y是检验数的反数。
在Y确定的前提下，每增加一个单位的i种资源，对目标函数的贡献。
♦结合例题1讲解影子价格：
y1=0:
第一种资源过剩
y2=13.6：
设备台时最紧张，每增加一个台时，利润增加13.6元。
y3=5.2…
♦影子价格所含有的信息：
1、资源紧缺状况
2、确定资源转让基价
参见：
P403、取得紧缺资源的代价
3.2灵敏度分析
♦为什么进行灵敏度分析？
♦灵敏度分析的两把尺子：
σj=Cj-CBB-1pj≤0；
xB=B-1b≥0
3.2.1价值系数的灵敏度分析
Cj变化到什么程度可以保持最优基不变？
用
（参看P96）
例题4：
87.5≤C2≤233.33；
36≤C1≤96
灵敏度分析
♦右端项的灵敏度分析：
bi变化到什么程度可以保持最优基不变？
用尺度
xB=B-1b≥0
例题5：
1-3.121.16360
B-1b=00.4-0.2200≥0
0-0.120.16b3
b3的变化范围：
227.586≤b3≤400
其它形式的灵敏度分析
新产品的分析：
在资源结构没有变化的条件下，是否生产这种新产品，就看它的竞争力如何。
例题6：
新增一种C产品，单位利润110元，使用劳动力6工时，设备5台时，原材料7公斤，问要否调整产品结构？
先算检验数σj=Cj-CBB-1pj
σ6=C6-YP6=110-（0，13.6，5.2）（6，5，7）T=110-104.4=5.6大于零，有利可图，将P6左乘B-1，加入到末表之中，继续迭代，直到求得最优解。
3.3用计算机进行灵敏度分析
♦例题7参见P102
习题课：
♦P78——2.10
（1）唯一最优解：
H3≤0，H5≤0，H1≥0
（2）无穷多最优解：
H3=0，H1≥0，H50，H2>
或H5=0，H1≥0，H30，H4>
（3）无界解：
H5≥0，H40，H1≥0，H30
（4）退化最优解：
H1=0，H30，H50
（5）非最优解，X1进基，X2出基：
H1≥0，H3>
0，H2>
0，
♦P79——2.11
♦1、对2、错，可能有最优解3、对
♦4、对5、错6、错7、错在“可行”
♦8、对9、错
♦P81——2.16
♦设白天电视广告X1个，黄金时间电视广告X2个，广播广告X3个，杂志广告X4个
♦maxZ=40X1+90X2+50X3+2X4
8X1+15X2+6X3+3X4≤16
30X1+40X2+20X3+X4≥200
8X1+15X2≤10
X1≥3X2≥2
X3≥5X3≤10
X4≥5X4≤10Xj≥0j=1、2、3、4
♦P81——2.17
♦设A产品生产X1单位，B产品生产X2单位，C产品销毁X3单位
♦maxZ=5X1+10X2+3（2X2-X3）-1X3
♦2X1+3X2≤200
♦3X1+4X2≤240
♦2X2-X3≤10X1、X2、X3≥0
♦P107——3.2
♦1、对，根据若对偶性
♦2、对，同上
♦3、对，同上
♦4、对，因为影子价格是每增加一个单位的某种资源，对目标函数的贡献程度
♦5、对，根据强对偶定理
习题课
♦P107——3.5注：
目标函数为最大化
♦1、这是线性规划的逆运算
♦对偶问题最优解：
♦Y1=4、Y2=2、Y3=0、Y4=4、Y5=0
♦P109——3.8
♦1、原问题的最优解：
X1=6，X5=10，其余为零;
对偶问题最优解：
Y1=2,Y2=0
♦C1的变化范围：
以C1代入末表，C1≥1
♦右端项变化范围：
♦b1≥-6，b2≥-10
第四章运输问题
本章要求：
掌握运输问题的数学模型
掌握运输问题的求解方法
化产销不平衡问题为平衡问题
学会用计算机求解
4.1运输问题的数学模型
♦运输问题一般表述为：
某企业有m个产地（生产厂）Ai，其产量分别为ai,i=1,2,…m,n个销地（销售商）Bj，其销售量分别为bj,j=1,2,…n,从Ai到Bj的每单位物资的运费为Cij.要求拟定总运费最小的调运方案。
运输表
运输问题的数学模型
设从Ai到Bj的运输量为xij,（假定产销平衡）
则总运费：
minZ=∑∑Cijxij
产量约束：
∑xij=aii=1,2,…m,
销量约束：
∑xij=bjj=1,2,…n,
非负性约束：
xij≥0
4.2表上作业法
♦计算步骤：
1、给出初始方案
2、检验是否最优
3、调整调运方案,Goto2
例题1
♦某建材公司有三个水泥厂A1、A2、A3，四个经销商B1、B2、B3、B4，其产量、销量、运费如下表：
4.2.1求初始调运方案
♦用最小元素法（也可用西北角法或vogel法）给出初始基可行解：
在运费表中找出最小元素，尽最大可能用完一个厂的产量，或满足一个商家的销量。
得到满足者用线划去。
升级会员 