运筹学课程总结.docx
- 文档编号:14799388
- 上传时间:2023-06-27
- 格式:DOCX
- 页数:19
- 大小:70.06KB
运筹学课程总结.docx
《运筹学课程总结.docx》由会员分享,可在线阅读,更多相关《运筹学课程总结.docx(19页珍藏版)》请在冰点文库上搜索。
运筹学课程总结
运筹学课程总结
总结内容:
一、运筹学简述
(一)运筹学定义
(二)运筹学工作步骤
(三)运筹学的应用
二、运筹学相关理论与方法
(一)线性规划
(二)运输问题
(三)目标规划
(四)整数规划
(五)动态规划三、运筹学应用案例分析(用matlab求解)
、运筹学简述
(一)运筹学的定义
运筹学是一门应用科学,至今还没有统一且确切的定义。
莫斯和金博尔曾对运筹学的定义是:
“为决策机构在对其控制下业务活动进行决策时,提供以数量化为基础的科学方法。
”它强调科学方法,以量化为基础。
另一定义是:
“运筹学是一门应用科学,它广泛应用现有的科学技术知识和
数学方法,解决实际中提出的专门问题,为决策者选择最优决策提供定量依据。
’
中国百科全书给出的定义是:
“运筹学是用数学方法研究经济、民政和国防等部门在内外环境约束的条件下合理分配人力、物力、财力等资源,使实际系统
有效运行的技术科学,它可以用来预测发展趋势,制定行动规划或优选可行方案。
”
如论如何定义,都表明着,运筹学是为提供最优化方法、最佳解决方案的科学。
(二)运筹学的工作步骤
1建立数学模型:
认清目标和约束;
2、寻求可行方案:
求解;
3、评估各个方案:
解的检验、灵敏度分析等;
4、选择最优方案:
决策;
5、方案实施:
回到实践中;
6、后评估:
考察问题是否得到完满解决。
(三)运筹学的应用
运筹学在各个领域的应用非常广泛,主要有以下几个方面:
1、生产计划:
生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等;
2、库存管理:
多种物资库存量的管理,库存方式、库存量等;
3、运输问题:
确定最小成本的运输线路、物资的调拨、运输、工具的调度
以及建厂地址的选择等;
4、人事管理:
对人员的需求和使用的预测,确定人员编制、人员合理分配,
建立人才评价体系等;
5、市场营销:
广告预算、媒介选择、定价、产品开发与销售、计划制定等;
6财务和会计:
预测、贷款、成本分析、定价、证券管理、现金管理等;
7、设备维修、更新,项目选择、评价,工程优化设计与管理等
二、运筹学相关理论与方法
(一)线性规划
1简述
线性规划是运筹学的一个重要分支,它是现代科学管理的重要手段之一,在合理利用一定规格的原材料、不同成分原材料的合理配比、运输方案的优化选择以及劳动力安排等方面有非常广泛的应用。
线性规划问题一般包括两个方面的问题,即求最大值(max)和求最小值(min)。
2、线性规划的数学模型结构
(1)变量:
决策系统中或实际问题中有待确定的未知因素;
(2)目标函数:
决策者对决策问题目标的数学描述,变量的线性函数;
(3)约束条件:
实现目标的限制因素,变量的线性等式或线性不等式,一般为:
大于或等于(》)、等于(=)和小于或等于(《)。
线性规划数学模型的一般形式为:
max(min)z=clxl+c2x.h—+cnx}1—目标函数
约束条
件
(71]x1+al2x2+-+[
如兀i+a22x2+…+如斗<(=,>)*2
……>
%叫+a^x2+…+amnxn<(=,>)bm
片工“>(<)0.free-
〒价值系数,口旷技术系数,歼限额茶数。
3、线性规划问题的求解方法
(1)图解法
图解法这种方法仅适用于只有两个变量的线性规划问题。
它的特点是直观而
易于理解,但实用价值不大。
(2)单纯形法
单纯形法对于多变量的线性规划问题,是一种常用解法。
它是通过一系列数学迭代过程,逐步求得线性规划问题的最优解。
单纯形法常见形式有两种:
大M法和两阶段法。
利用单纯形法求解线性规划问题可以分两种:
求最大值和求最小值。
①单纯形法的基本思路
②单纯形法的基本求解步骤:
a.引入辅助变量,将现行规划模型转换成标准形式;
b.确定基础可行解,列出初始单纯形表;
c.确定迭代变量,进行迭代变换。
(3)对偶单纯形法
对偶单纯形法是运用对偶原理求解原问题的一种方法,而不是求解对偶问题的单纯形法。
它和单纯形法的主要区别在于:
单纯形法在整个迭代过程中,始终保持原问题的可行性,即常数列》0,而检验数由负分量逐步变为全部》0,即同时得到原问题和对偶问题的最优解。
对偶单纯形法则是在整个迭代过程中,始终保持对偶问题的可行性,即全部检验数》0,而常数列由有负分量逐步变为全部》0,即同时得到原问题和对偶问题的最优解。
(二)运输问题
1简述
一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地,在
每个产地的供应量与每个销地的需求量已知,并知道各地之间的运输单价的前提
下,如何确定一个使得总的运输费用最小的方案。
2、运输问题的数学模型结构
(1)决策变量;
(2)约束条件;(3)目标函数
①在产销平衡的条件下,运费最小的调运方案的数学模型为:
mn
minz_''CijXj
i4j
*m
EXj=bjj=1,2,…,n
i」
n
s.t.«送Xjj=aii=1,2,…,m
j二
Xj>0
②当产大于销时,v-bj,运费最小的数学模型为:
iAj吕
n
为Xij
j二
m
“送Xij
i二
XjKo
(i=12,m)
(j72,…,n)
mn
③当产小于销时,'•abj,数学模型为:
i占jd
Z
Xij—ai,
(i二1,2,
m)
jA
m
z
Xij=bj,
(j=1,2,
n)
i=1
Xij
-0
n
3、运输问题的求解方法:
表上作业法
表上作业法是一种求解运输问题的特殊的方法,其实质是单纯形法,
运输问题变量多,结构独特的情况,大大简化了计算过程的求解方法
表上作业法的基本思路和步骤:
①找出初始基可行解。
方法有:
西北角法、最小元素法、伏格尔法。
它针对
2最优解的判别。
方法有,闭回路法、位势法
(确定初始基可行解J
+一、
「*
「西誉角法一)(最上元素法)(一沃格尔法一)
(闭回路法)C位势法)
C得到新的基可哲解J(确定变量)i广*代
(「沿回路调整运量j
(确定离基变量)
当产销不平衡时,这时就需要通过增加一个假象仓库或者假象生产地来化成产销平衡的问题。
(三)线性目标规划
i简述
目标规划是线性规划的一种特殊应用,能够处理单个主目标与多个目标并存,以及多个主目标与多个次目标并存的问题,在现有的资源条件下,在多个目标中去寻求满意解,使得实际目标完成的总体结果与事先制定目标的差距最小。
2、目标规划的数学模型
LK
目标函数:
minz=EP正㈣+创帀力
满足约束条件:
丨=1kz!
「门
送CkjXj+d厂一dk+=gk,k=1,…,Kj二
n
比ajXj兰(=,耳b,i=1,…,m
jd:
XjAO,j=:
…,n
血匸血,k=:
2,3
3、求解方法:
图解法和单纯形法
(四)整数规划
1简述
整数规划指整数线性规划,即要求部分变量或全部变量为整数的线性规划
分为纯整数规划与混合整数规划两大类
2、整数规划的一般形式
n
max(min)z-'cjxj
j4
n
'ajXj乞(=,_)b(i=1,,m)
j二
Xj-0(j",,m)
xj中部分或全部取整数
3、整数规划的求解方法
(1)分支定界法:
用于解纯整数或混合的整数规划。
步骤:
a.分支:
将原问题分为两个子问题;
b.定界:
确定最优目标范围以减少搜索次数。
(2)割平面法
通过增加新的约束来切割可原问题伴随规划的可行域,使它在不断缩小的过程中,将原问题的整数最优解逐渐暴露且趋于可行域极点的位置,这样就有可能用单纯形法求出。
步骤:
a用单纯形法解松弛问题,得到最优单纯形表;
b.求一个割平面方程,加到最优单纯形表中,用对偶单纯形法继续求解;
c.若没有得到整数最优解,则继续作割平面方程,转第二步。
(五)动态规划
1、简述
动态规划是运筹学的一个分支,它是解决多阶段决策过程最优化的一种数学方法。
动态规划是求解某类问题的一种方法,是考查问题的一种途径,而不是一种特殊算法(如线性规划是一种算法)。
因而,它不像线性规划那样有一个标准的数学表达式和明确定义的一组规则,而必须对具体问题进行具体分析处理。
动态规划应用广泛,可以用来解决最优路劲问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题等等,所以它是现代企业管理中的一种重要的决策方法。
2、动态规划方法的基本思想
(1)动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件。
要做到这一点,必须先将问题的过程分成几个相互联系的阶段,恰当地选取状态变量和决策变量及定义最优值函数,从而把一个大问题化成一族同类型的子问题,然后逐个求解。
即从边界条件开始,逐段递推寻优,在每个子问题的求解中,均利用了前面的子问题的最优化结果,依次进行,最后一个问题所得的最优解,就是整个问题的最优解。
(2)在多阶段决策过程中,动态规划方法是既把当前一段和未来各段分开,
又把当前效益和未来效益结合起来考虑的一种最优化方法。
因此,每段决策的选
取是从全局来考虑的,与改段的最优选择答案一般是不同的。
(3)在整个问题的最优策略时,由于初始状态是已知的,而每段的决策都是该段状态的函数,故最优策略所经过的各段状态便可逐次变换得到,从而确定了最优路线。
三、运筹学应用案例举例
(一)线性规划应用案例分析
某棉纺织厂需要拟定一种针织纱的混棉配方方案。
已知原棉共有品种6个,
他们的物理性能、单价、质量指标等如下表所以。
现要求在满足质量指标的前提下,拟定一个新的配棉方案(各种原棉在混棉中所占的百分比),使混棉的成本
最低。
项目
原棉品种
质量要求
A1
A2
A3
A4
A5
A6
品质1
200
270
260
210
230
250
》230
品质2
600
550
610
580
660
590
》580
品质3
130
100
60
100
80
80
《100
品质4
15
17
16
13
16
16
《15
单价(元/千克)
300
300
330
310
300
300
最小
混用上限(%)
20
20
15
20
25
20
解:
1、设定变量
设方案中各种原棉的配比为Xi,其中i=1,2,3,4,5,6,即表示上表中所列的原
棉品种A1,A2,A3,A4,A5,A6的百分比,共6个变量。
2、确定目标函数
设新方案的混棉单位成本为C,则
C=300xi+300x2+330x3+310x4+300x5+300x6
3、建立约束条件
(1)品质指标的约束:
①品质指标约束1:
200xi+270x2+260x3+210x4+230x5+250x6》230
2品质指标约束2:
600x1+550x2+610x3+580x4+660x5+590x6》580
3品质指标约束3:
130xi+100x2+60x3+100x4+80x5+80x6《100
4品质指标约束4:
15x1+17x2+16x3+13x4+16x5+16x6《16
(2)配比比例的约束条件:
配比之和为100%
X1+X2+X3+X4+X5+X6=100%
(3)各种原棉配比的比例上限:
X1《20%;X2《20%;X3《15%;X4《20%;X5《25%;X6《20%
xi>0(i=1,2,3,4,5,6)
贝U,该线性规划的数学模型为:
MinC=300x什300x2+330x3+310x4+300x5+300x6
200x1十270x2十260x^210x4+230x5+250x6X230
600x1+550x2+610x3+580x4+660x5+590x6>580
130x1+100x2+60x3+100x4+80x5+80x6<100
15X1+17x2+16x3+13x4+16x5+16x6兰16
X1+X2+X3+X4+X5+X6=1
刃_0.2
X2兰0.2
X3兰0.15
X4兰0.2
X5兰0.25
X6兰0.2
/1,X2,X3,X4,X5,X6Z0
用matlab求解该线性规划问题:
1、输入下列数据
(1)系数矩阵:
A=〔-200-270-260-210-230-25Q-600-550-610-580-660-590;130100601008080151716131616100000;010000;001000;000100;000010;000001〕
(2)系数矩阵:
Aeq=〔111111〕
(3)成本矢量:
f=〔300;300;330;310;300;300〕
(4)右端矢量:
b=〔-230;-580;100;16;0.2;0.2;0.15;0.2;0.25;
(5)右端矢量:
beq=〔1〕
(6)变量下界:
lb=〔0;0;0;0;0;0;0〕
2、调用函数
〔x,fva,exitflag〕=linprog(f,A,b,Aeq,beq,lb,〔〕)
输入的命令为:
»A=[-2Q0-270-260-210-23Q-250;-500-550-610-5S0-660-590:
13010Aeq=[lII1I1]
f=|[300;300:
330;310:
300:
300]
b=[-230;-580;100;16;0.2;0.2;0.15;0.2;0.25;0,21
beq=[l]
lb=[000000]
[x3fvaljexitflag]=linprog(fAjb,Aeq,beq,lbj,[]j
得出结果:
当x满足xi=0.2,X2=0.2,X3=0,X4=0.15,X5=0.25,x6=0.2时,成本最低,且成本C=301.5
(2)运输问题应用案例分析
某地有三个有色金属矿A1、A2、A3,生产同一种金属矿石,A1矿的年产量为100万千克,A2矿为80万千克,A3矿为50万千克。
矿石全部供应四个冶炼厂,B1厂的全部需求量为50万千克,B2为70万千克,B3为80万千克,B4为30万千克。
总产量恰好等于总需求量,矿石由各矿山运到冶炼厂的单位运价见下表。
如何安排运输,使各矿山的矿石运到冶炼厂,满足各厂的需要,且总运费最小?
运价表单位:
元/千克
B1
B2
B3
B4
A1
1.5
2
0.3
3
A2
7
0.8
1.4
2
A3
1.2
0.3
2
2.5
解:
该问题为产销平衡的运输问题,需要制定最优运输计划使总运输费最小。
1、设定变量
设xij表示第i个矿山运到第j个冶炼厂的矿石量(万千克),见下表所列
B1
B2
B3
B4
r产量
A1
X11
X12
X13
X14
100
A2
X21
X22
X23
X24
80
A3
X31
X32
X33
X34
50
需要量
50
70
80
30
230
2、确定目标函数
问题的目标是求总运输费用最小,设Z表示总运输费用,则
MinZ=1.5Xii+2Xi2+0.3Xi3+3Xi4+7X2i+0.8X22+1.4X23+2X24+1.2X3i+0.3X32+2
X33+2.5X34
3、确定约束条件
X1什X12+X13+X14=100
X21+X22+X23+X24=80
X31+X32+X33+X34=50
X11+X21+X31=50
X12+X22+X32=70
X13+X23+X33=80
X14+X24+X34=30
Xij》0,i=1,2,3;j=1,2,3,4
该运输问题的数学模型为:
MinZ=1.5X11+2X12+0.3X13+3X14+7X21+0.8X22+1.4X23+2X24+1.2X31+0.3X32+2X33+2.5X34
X1什X12+X13+X14=100
X21+X22+X23+X24=80
X31+X32+X33+X34=50
X11+X21+X31=50
X12+X22+X32=70
X13+X23+X33=80
X14+X24+X34=30
Xij》0,i=1,2,3;j=1,2,3,4
用matlab求解该运输问题
输入命令:
f=[1.520.3370.81.421.20.322.5]
Aeq=[111100000000
000011110000
000000001111
100010001000
010001000100
001000100010
000100010001]
beq=[100805050708030]
lb=[000000000000]
[x,fval,exitflag,output,lambda]=linprog(f,[],[],Aeq,beq,lb)
输出数据为:
x-
20.0000
0,0000
80.0000
0.0000
0,0000
50.0000
0.0000
30.0000
30.0000
20.0000
0.0000
0.0000
fval=
196.0000
exitflag二
1
当x满足
X11=20,X12=0,X13=80,X14=0,X21=0,X22=50,X23=0,X24=30,X31=30,X32=20,
X33=0,X34=0时,运输总费用最小,费用为Z=196
(三)线性规划问题
某公司生产甲、乙两种产品,均需在ABC三种不同的设备上加工,产品加工所需工时单耗、产品销售后能获得的利润及设备可用工时数如下表。
问:
如何
安排生产计划,才能使该公司获得的总利润最大?
产品生产基础数据表
A
B
C
利润(元/千克)
30
3
5
9
70
乙
9
5
3
限制工时
540
450
720
解:
1、设定变量
设甲、乙产品产量分别为Xi,X2(千克)
2、确定目标函数
MaxZ=70xi+30X2
3、约束条件
3xi+9X2=540
5xi+5X2=450
9xi+3X2<720
X1,X2>0
因此,该问题的数学模型为
MaxZ=70x计30X2转换成标准格式:
MinZ=-70xi-30X2
3xi+9X2<540
5xi+5X2<450
9xi+3X2<720
Xi,X2>0
用matlab求解该问题
输入命令:
>>f=[-70;-30]
A=[39;55;93]
b=[540;450;720]
lb=[0;0]
[x,fval,exitflag]=linprog(f,A,b,[],[],lb)
输出数据:
75.0000
15.0000
fval二
IDOOfi+03
exitflas=
1
当甲产品安排生产75千克,乙产品安排生产15千克,可使公司获得最大利
润5700元。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 课程 总结