OPERATIONSRESEARCH运筹学怎样把事情做到最好课件

OPERATIONSRESEARCH

运筹学Ⅰ——怎样把事情做到最好郝英奇OR11OPERATIONSRESEARCH

运筹学Ⅰ——怎第一章绪论1.1题解Operations汉语翻译工作、操作、行动、手术、运算OperationsResearch日本——运用学港台——作业研究中国大陆——运筹学OperationalResearch原来名称，意为军事行动研究——历史渊源OR12第一章绪论1.1题解OR12绪论1.2运筹学的历史早期运筹思想：田忌赛马丁渭修宫沈括运粮Erlang1917排队论Harris1920存储论Levinson1930零售贸易康脱洛维奇1939LP

OR13绪论1.2运筹学的历史OR13绪论1.2运筹学的历史军事运筹学阶段德军空袭防空系统Blackett运输船编队空袭逃避深水炸弹轰炸机编队OR14绪论1.2运筹学的历史OR14绪论1.2运筹学的历史管理运筹学阶段战后人员三分:军队、大学、企业大学：课程、专业、硕士、博士企业：美国钢铁联合公司英国国家煤炭局运筹学在中国：50年代中期引入华罗庚推广优选法、统筹法中国邮递员问题、运输问题

OR15绪论1.2运筹学的历史OR151.3学科性质应用学科Morse&Kimball定义：运筹学是为决策机构在对其控制的业务活动进行决策时提供的数量化为基础的科学方法。Churchman定义：运筹学是应用科学的方法、技术和工具，来处理一个系统运行中的问题，使系统控制得到最优的解决方法。中国定义：运筹学是应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。OR161.3学科性质应用学科OR161.4定性与定量例：店主进货两者都是常用的决策方法定性是基础，定量是工具，定量为定性服务。定性有主观性也有有效性，定量有科学性也有局限性。管理科学的发展，定量越来越多。但定量不可替代定性。OR171.4定性与定量例：店主进货OR171.5运筹学的模型模型：真实事物的模仿，主要因素、相互关系、系统结构。形象模型：如地球仪、沙盘、风洞模拟模型：建港口，模拟船只到达。学生模拟企业管理系统运行。数学模型：用符号或数学工具描述现实系统。V=F（xi,yj,uk)G(xi,yj,uk)≥0OR181.5运筹学的模型模型：真实事物的模仿，主要因素、相互关系、1.6运筹学的学科体系规划论：线性规划、非线性规划|、整数规划、目标规划、动态规划图论与网络存储论排队论决策论对策论计算机仿真OR191.6运筹学的学科体系规划论：线性规划、非线性规划|、整数规1.7运筹学的工作步骤确定问题搜集数据建立模型检验模型求解模型结果分析结果实施OR1101.7运筹学的工作步骤确定问题OR1101.8运筹学与计算机计算机为运筹学提供解题工具。本书有现成的程序可以利用要学会解题的思路与方法，建立模型很重要。OR1111.8运筹学与计算机计算机为运筹学提供解题工具。OR111第二章线性规划与单纯形法2.1LP(linearprogramming)的基本概念LP是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。LP有一组有待决策的变量，一个线性的目标函数，一组线性的约束条件。OR112第二章线性规划与单纯形法2.1LP(linea2.1.1LP的数学模型

例题1—生产计划问题某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：产品A产品B资源限量劳动力设备原材料9434510360200300利润元/kg70120OR1132.1.1LP的数学模型

例题1例题1建模问题：如何安排生产计划，使得获利最多？步骤：1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：人力约束9X1+4X2≤360设备约束4X1+5X2

≤200原材料约束3X1+10X2

≤300

非负性约束X1≥0X2≥0OR114例题1建模问题：如何安排生产计划，使得获利最多？OR114例题2——配方问题养海狸鼠饲料中营养要求：VA每天至少700克，VB每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表：饲料VaVbVc价格元/KGIIIIIIIVV32161810.50.220.50.510.220.827495营养要求70030200OR115例题2——配方问题养海狸鼠饲料中营养要求：VA每天至少7例题2建模设抓取饲料Ix1kg;饲料IIx2kg;饲料IIIx3kg……目标函数：最省钱minZ=2x1+7x2+4x3+9x4+5x5约束条件：3x2+2x2+x3+6x4+18x5≥700营养要求：x1+0.5x2+0.2x3+2x4+0.5x5≥300.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≥0OR116例题2建模设抓取饲料Ix1kg;饲料IIx2kg;饲料I例题3：人员安排问题医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计：

序号时段最少人数安排人数106—1060X1210—1470X2314—1860X3418—2250X4522—0220X5602—0630x6OR117例题3：人员安排问题医院护士24小时值班，每次值班8小时。不例题3建模目标函数：minZ=x1+x2+x3+x4+x5+x6约束条件：x1+x2

≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30非负性约束：xj

≥0,j=1,2,…6OR118例题3建模目标函数：minZ=x1+x2+x3+x4+x5归纳：线性规划的一般模式目标函数：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≥0OR119归纳：线性规划的一般模式目标函数：max(min)Z=c1x2.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下方的半平面。所有半平面的交集称之为可行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解。OR1202.1.2线性规划图解法由中学知识可知：y=ax+b是一条直例1图示.9080604020020406080100x1

x29x1+4x2

≤3604x1+5x2

≤2003x1+10x2

≤300ABCDEFGHIZ=70x1+120x2OR121例1图示.908060概念概念：1、可行解：满足所有约束条件的解。2、可行域：即可行解的集合。所有约束条件的交集，也就是各半平面的公共部分。满足所有约束条件的解的集合，称为可行域。3、基解：约束条件的交点称为基解（直观）4、基可行解：基解当中的可行解。5、凸集：集合内任意两点的连线上的点均属于这个集合。如：实心球、三角形OR122概念概念：OR122结论可行域是个凸集可行域有有限个顶点最优值在可行域的顶点上达到无穷多解的情形无界解情形无解情形OR123结论可行域是个凸集OR1232.1.3线性规划的标准型代数式maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2………am1x1+am2x2+…+amnxn=bmxj

≥0j=1,2,…,nOR1242.1.3线性规划的标准型代数式maxZ=c1x1+c2x2线性规划的标准型和式：maxZ=∑cjxj

∑aijxj=bii=1,2,…,mxj≥0

j=1,2,…,nj=1nnj=1OR125线性规划的标准型和式：maxZ=∑cjxjj=1nnj=1O线性规划的标准型向量式：maxZ=CX

∑pjxj=bi

i=1,2,…,m

xj≥0j=1,2,…,nC=(c1,c2,c3,…,cn)

X=(X1,X2,X3,…,Xn)Tnj=1OR126线性规划的标准型向量式：maxZ=CXnj=1OR126线性规划的标准型矩阵式：maxZ=CXAX=bX≥0

其中：b=(b1,b2,…,bm)T

a11

a12….a1nA=a21

a22…a2n………

am1

am2…amnOR127线性规划的标准型矩阵式：maxZ=CXAX=b标准型的特征目标函数极大化约束条件为等式决策变量非负OR128标准型的特征目标函数极大化OR128非标准型转化为标准型目标函数极小化转为极大化：minZ=－max(－Z)，一个数的极小化等价于其相反数的极大化。不等式约束的转化：∑aijxj≤bi加入松弛变量

∑aijxj≥bi减去剩余变量非正变量：即xk

≤0则令x’k=－xk

自由变量：即xk无约束，令xk=x’k－x”kOR129非标准型转化为标准型目标函数极小化转为极大化：OR129非标准型转化举例之一maxZ=70X1+120X2maxZ=70X1+120X29X1+4X2≤3609X1+4X2+X3=3604X1+5X2

≤2004X1+5X2+x4=2003X1+10X2

≤3003X1+10X2+x5=300

X1≥0X2≥0Xj≥0j=1,2,…,5OR130非标准型转化举例之一maxZ=70X1+120X2非标准型转化举例之二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=23x1+x2-3x3=5－3x’1+x2－3(x’3－

x”3

)=5x1≤0x2≥0x3无约束

x’1≥0x2≥0x’3≥0x”3≥0x4≥0

x5≥0

OR131非标准型转化举例之二minZ=x1+2x2-3x32.1.4基可行解基的概念：如前所述LP标准型和式：maxZ=∑cjxj

∑aijxj=bi

xj

≥0

j=1,2,…,n

矩阵式：maxZ=CXAX=bX≥0

约束方程的系数矩阵A的秩为m，且m<n。设A=B+N，B是A中mm阶非奇异子矩阵，则称B是LP的一个基，即：B是A中m个线性无关向量组。nj=1nj=1OR1322.1.4基可行解基的概念：如前所述LP标准型nj=1nj=基解的概念不失一般性,设B是A的前m列,即B=(p1,p2,…,pm）,其相对应的变量XB=(x1,x2,…,xm)T,称为基变量；其余变量XN=(Xm+1,…,Xn)T称为非基变量。令所有非基变量等于零,则X=（x1,x2,…xm,0,…,0)T称为基解。OR133基解的概念不失一般性,设B是A的前m列,即B基可行解的概念基可行解：基解可正可负，负则不可行（违背非负性约束条件），称满足所有约束条件的基解为基可行解。退化的基可行解：若某个基变量取值为零，则称之为退化的基可行解。基解的数目：最多Cmn=n!/m!(n-m)!OR134基可行解的概念基可行解：基解可正可负，负则不可行（违背非负性例题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=10OR135例题6基可行解说明maxZ=70X1+120X2例题6基可行解说明基（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图）OR136例题6基可行解说明基（p3,p4,p5），令非基变量x2.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’OR1372.2单纯形法2.2.1初始基可行解的确定OR1372.2单纯形法2.2.2最优性检验：LP经过若干步迭代，成为如下形式：X1++a’1m+1xm+1+…+a’1nxn=b’1

x1=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’mjxjOR1382.2单纯形法2.2.2最优性检验：LP经过若干步迭代，成为单纯形法一般性表示：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

时,达到最优解OR139单纯形法一般性表示：xi=b’i-∑a’ijxj单纯形法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处在变量转换的交叉点上，称之为枢轴元素σj≥0OR140单纯形法2.2.2基变换σj≥0OR140单纯形法解题举例单纯形表的格式：CjC1C2…Cn

θiCBXBbx1

x2….xn

C1C2

…Cmx1x2…xmb1b2…bma11a12…a1na21a22…a2n………am1am2…amnθ1θ2…θm

σjσ1σ2…σnOR141单纯形法解题举例单纯形表的格式：CjC1CjC1C2…CnCBXBbX1

X2

X3X4X5θj000X3X4X536020030094100

45010310001904030σj0

7012000000120X3X4X224050

307.8010-0.42.5001-0.50.31000.130.7620100σj360034000-12701200X3X1X2842024001-3.121.161000.4-0.2010-0.120.16σj4280

000-13.6-5.2OR142CjC1C2…CnCBXBb2.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

为枢轴元素进行迭代，回到第二步OR1432.2.3单纯形法的计算步骤

找到初始可行基，建立单纯形表O2.3单纯形法的进一步探讨2.3.1极小化问题直接求解：检验数的判别由所有σj≤0

即为最优，变为所有σj≥0则为最优。人工变量法之一：大M法人工变量价值系数M例人工变量法之二：构造目标函数，分阶段求解例2.3.2无穷多最优解情形：非基变量检验数σj=02.3.3退化解的情形：有两个以上θ值相等OR1442.3单纯形法的进一步探讨2.3.1极小化问题直接求解：检验2.3.4单纯形法的计算机求解程序说明应用举例例题1例题2OR1452.3.4单纯形法的计算机求解程序说明OR1452.5LP应用举例之一例13合理下料问题料长7.4米，截成2.9、2.1、1.5米各200根。如何截取余料最少？关键：设变量。方案料型123456782.9米2.1米1.5米120101000022113031203104合计残料7.47.37.27.16.66.56.36.000.10.20.30.80.91.11.4OR1462.5LP应用举例之一例13合理下料问题应用举例之二例14混合配方问题A、B、C、D四种原料配制三种产品，三类约束：技术要求、原料限量、市场容量。已知产品价格和原料价格，求利润最大的配方。关键：设变量。OR147应用举例之二例14混合配方问题OR147应用举例之三例15.滚动投资问题兹有100万元闲钱，投资方向有四：

第四年第一年第二年第三年A项目110%B项目135%C项目125%D项目104%第五年各年投资什么项目，使第五年末资本总额为最大？OR148应用举例之三例15.滚动投资问题第四年第一年第二年第三年A项应用举例之四例16动态生产计划问题工厂做n个月的生产计划，第j月需求量dj、正常生产能力aj、加班生产能力bj、正常生产成本cj、加班生产成本ej、库存能力为I、库存费用hj，设期初、期末库存为零。求费用最小的生产计划。设第月正常生产xj件，加班生产件yj，存储zj件。则：本期生产+上期库存-本期库存=本期需求OR149应用举例之四例16动态生产计划问题OR149第三章对偶问题与灵敏度分析要求：了解LP对偶问题的实际背景了解对偶问题的建立规则与基本性质掌握对偶最优解的计算及其经济解释掌握LP的灵敏度分析理解计算机输出的影子价格与灵敏度分析的内容OR150第三章对偶问题与灵敏度分析要求：OR1503.1对偶问题3.1.1对偶问题的提出回顾例题1：现在A、B两产品销路不畅，可以将所有资源出租或外卖，现在要谈判，我们的价格底线是什么？产品A产品B资源限制劳动力设备原材料9434510360200300单位利润70120OR1513.1对偶问题3.1.1对偶问题的提出产品A产品B对偶模型设每个工时收费Y1元，设备台时费用Y2元，原材料附加费Y3元。出租收入不低于生产收入：9y1+4y2+3y3≥704y1+5y2+10y3

≥120目标：ω=360y1+200y2+300y3出租收入越多越好？至少不低于某数OR152对偶模型设每个工时收费Y1元，设备台时费用Y2元，原材料附加原问题与对偶问题之比较原问题：对偶问题：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≥0X1≥0X2≥0OR153原问题与对偶问题之比较原问题：3.1.2对偶规则原问题一般模型：对偶问题一般模型：maxZ=CXminω=YbAX

≤bYA≥CX≥0Y≥0OR1543.1.2对偶规则原问题一般模型：对偶问题一对偶规则原问题有m个约束条件，对偶问题有m个变量原问题有n个变量，对偶问题有n个约束条件原问题的价值系数对应对偶问题的右端项原问题的右端项对应对偶问题的价值系数原问题的技术系数矩阵转置后为对偶问题系数矩阵原问题的约束条件与对偶问题方向相反原问题与对偶问题优化方向相反OR155对偶规则原问题有m个约束条件，对偶问题有m个变量OR155对偶规则.原问题对偶问题目标函数maxmin目标函数约束条件

≤

≥=≥变量≤无约束

≥变量符号≤

无约束≥

≤约束条件=OR156对偶规则.原问题对偶问题目对偶规则简捷记法原问题标准则对偶问题标准原问题不标准则对偶问题不标准例题2maxω=7y1+4y2-2y3minZ=3x1+2x2-6x3+x52y1+y2-y3

≤32x1+x2-4x3+x4+3x5

≥7y1+3y3≤2x1+2x3-x4≤

4-4y1+2y2

≤-6-x1+3x2-x4+x5=-2y1-y2-y3

≥

0x1，x2，x3

≥0;3y1+y3=1x4≤

0;x5无限制y1

≥0y2≤0y3

无约束

OR157对偶规则简捷记法原问题标准则对偶问题标准OR1573.1.3对偶问题的基本性质对称性：对偶问题的对偶问题是原问题弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值(鞍型图)无界性：原问题无界，对偶问题无可行解对偶定理：若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。若原问题最优基为B，则其对偶问题最优解Y*=CBB-1OR1583.1.3对偶问题的基本性质对称性：对偶问题的对偶问题是原问3.1.4对偶最优解的经济解释—影子价格Z=ω=CX=YbZ/b=(Yb)’=YZ=Yb=∑yibi的意义：Y是检验数的反数。在Y确定的前提下，每增加一个单位的i种资源，对目标函数的贡献。结合例题1讲解影子价格：y1=0:第一种资源过剩y2=13.6：设备台时最紧张，每增加一个台时，利润增加13.6元。y3=5.2…影子价格所含有的信息：1、资源紧缺状况2、确定资源转让基价参见：P403、取得紧缺资源的代价OR1593.1.4对偶最优解的经济解释—影子价格Z=ω=CX=Yb3.2灵敏度分析为什么进行灵敏度分析？灵敏度分析的两把尺子：

σj=Cj-CBB-1pj≤0；xB=B-1b≥03.2.1价值系数的灵敏度分析

Cj变化到什么程度可以保持最优基不变？用（参看P96）例题4：87.5≤C2≤233.33；36≤C1

≤96OR1603.2灵敏度分析为什么进行灵敏度分析？OR160灵敏度分析右端项的灵敏度分析：bi变化到什么程度可以保持最优基不变？用尺度

xB=B-1b≥0例题5：1

-3.12

1.16360

B-1b=00.4-0.2200≥00-0.120.16b3b3的变化范围：227.586≤b3≤400OR161灵敏度分析右端项的灵敏度分析：OR161其它形式的灵敏度分析

新产品的分析：在资源结构没有变化的条件下，是否生产这种新产品，就看它的竞争力如何。例题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，加入到末表之中，继续迭代，直到求得最优解。OR162其它形式的灵敏度分析新产品的分析：OR1623.3用计算机进行灵敏度分析例题7参见P102OR1633.3用计算机进行灵敏度分析例题7参见P102OR习题课：P78——2.10（1）唯一最优解：H3≤0，H5≤0

，H1

≥0（2）无穷多最优解：H3=0，H1

≥0，H5

0，H2>0或H5=0，H1

≥0，H30，H4>0（3）无界解：H5≥0，H40

，

H1

≥0，H3

0（4）退化最优解：H1=0

，H3

0

，H5

0（5）非最优解，X1进基，X2出基：

H1

≥0，H3>0，H2>0，5H2<H17OR164习题课：P78——2.105H2<H17OR164习题课：P79——2.111、对2、错，可能有最优解3、对4、对5、错6、错7、错在“可行”8、对9、错OR165习题课：P79——2.11OR165习题课：P81——2.16设白天电视广告X1个，黄金时间电视广告X2个，广播广告X3个，杂志广告X4个maxZ=40X1+90X2+50X3+2X4

8X1+15X2+6X3+3X4

≤1630X1+40X2+20X3+X4

≥2008X1+15X2

≤10X1

≥3X2≥2X3≥5X3

≤10X4

≥5X4

≤10X

j≥0j=1、2、3、4OR166习题课：P81——2.16OR166习题课：P81——2.17设A产品生产X1单位，B产品生产X2单位，C产品销毁X3单位maxZ=5X1+10X2+3（2X2-X3）-1X32X1+3X2

≤2003X1+4X2≤2402X2-X3≤10X1、X2、X3

≥0OR167习题课：P81——2.17OR167习题课：P107——3.21、对，根据若对偶性2、对，同上3、对，同上4、对，因为影子价格是每增加一个单位的某种资源，对目标函数的贡献程度5、对，根据强对偶定理OR168习题课：P107——3.2OR168习题课P107——3.5注：目标函数为最大化1、这是线性规划的逆运算对偶问题最优解：Y1=4、Y2=2、Y3=0、Y4=4、Y5=0OR169习题课P107——3.5注：目标函数为最大化OR1习题课P109——3.81、原问题的最优解：X1=6，X5=10，其余为零;对偶问题最优解：Y1=2,Y2=0C1的变化范围：以C1代入末表，C1≥1右端项变化范围：xB=B-1b≥0b1≥-6，b2≥-10OR170习题课P109——3.8OR170OPERATIONSRESEARCH

运筹学Ⅰ——怎样把事情做到最好郝英奇OR171OPERATIONSRESEARCH

运筹学Ⅰ——怎第一章绪论1.1题解Operations汉语翻译工作、操作、行动、手术、运算OperationsResearch日本——运用学港台——作业研究中国大陆——运筹学OperationalResearch原来名称，意为军事行动研究——历史渊源OR172第一章绪论1.1题解OR12绪论1.2运筹学的历史早期运筹思想：田忌赛马丁渭修宫沈括运粮Erlang1917排队论Harris1920存储论Levinson1930零售贸易康脱洛维奇1939LP

OR173绪论1.2运筹学的历史OR13绪论1.2运筹学的历史军事运筹学阶段德军空袭防空系统Blackett运输船编队空袭逃避深水炸弹轰炸机编队OR174绪论1.2运筹学的历史OR14绪论1.2运筹学的历史管理运筹学阶段战后人员三分:军队、大学、企业大学：课程、专业、硕士、博士企业：美国钢铁联合公司英国国家煤炭局运筹学在中国：50年代中期引入华罗庚推广优选法、统筹法中国邮递员问题、运输问题

OR175绪论1.2运筹学的历史OR151.3学科性质应用学科Morse&Kimball定义：运筹学是为决策机构在对其控制的业务活动进行决策时提供的数量化为基础的科学方法。Churchman定义：运筹学是应用科学的方法、技术和工具，来处理一个系统运行中的问题，使系统控制得到最优的解决方法。中国定义：运筹学是应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。OR1761.3学科性质应用学科OR161.4定性与定量例：店主进货两者都是常用的决策方法定性是基础，定量是工具，定量为定性服务。定性有主观性也有有效性，定量有科学性也有局限性。管理科学的发展，定量越来越多。但定量不可替代定性。OR1771.4定性与定量例：店主进货OR171.5运筹学的模型模型：真实事物的模仿，主要因素、相互关系、系统结构。形象模型：如地球仪、沙盘、风洞模拟模型：建港口，模拟船只到达。学生模拟企业管理系统运行。数学模型：用符号或数学工具描述现实系统。V=F（xi,yj,uk)G(xi,yj,uk)≥0OR1781.5运筹学的模型模型：真实事物的模仿，主要因素、相互关系、1.6运筹学的学科体系规划论：线性规划、非线性规划|、整数规划、目标规划、动态规划图论与网络存储论排队论决策论对策论计算机仿真OR1791.6运筹学的学科体系规划论：线性规划、非线性规划|、整数规1.7运筹学的工作步骤确定问题搜集数据建立模型检验模型求解模型结果分析结果实施OR1801.7运筹学的工作步骤确定问题OR1101.8运筹学与计算机计算机为运筹学提供解题工具。本书有现成的程序可以利用要学会解题的思路与方法，建立模型很重要。OR1811.8运筹学与计算机计算机为运筹学提供解题工具。OR111第二章线性规划与单纯形法2.1LP(linearprogramming)的基本概念LP是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。LP有一组有待决策的变量，一个线性的目标函数，一组线性的约束条件。OR182第二章线性规划与单纯形法2.1LP(linea2.1.1LP的数学模型

例题1—生产计划问题某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：产品A产品B资源限量劳动力设备原材料9434510360200300利润元/kg70120OR1832.1.1LP的数学模型

例题1例题1建模问题：如何安排生产计划，使得获利最多？步骤：1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：人力约束9X1+4X2≤360设备约束4X1+5X2

≤200原材料约束3X1+10X2

≤300

非负性约束X1≥0X2≥0OR184例题1建模问题：如何安排生产计划，使得获利最多？OR114例题2——配方问题养海狸鼠饲料中营养要求：VA每天至少700克，VB每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表：饲料VaVbVc价格元/KGIIIIIIIVV32161810.50.220.50.510.220.827495营养要求70030200OR185例题2——配方问题养海狸鼠饲料中营养要求：VA每天至少7例题2建模设抓取饲料Ix1kg;饲料IIx2kg;饲料IIIx3kg……目标函数：最省钱minZ=2x1+7x2+4x3+9x4+5x5约束条件：3x2+2x2+x3+6x4+18x5≥700营养要求：x1+0.5x2+0.2x3+2x4+0.5x5≥300.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≥0OR186例题2建模设抓取饲料Ix1kg;饲料IIx2kg;饲料I例题3：人员安排问题医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计：

序号时段最少人数安排人数106—1060X1210—1470X2314—1860X3418—2250X4522—0220X5602—0630x6OR187例题3：人员安排问题医院护士24小时值班，每次值班8小时。不例题3建模目标函数：minZ=x1+x2+x3+x4+x5+x6约束条件：x1+x2

≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30非负性约束：xj

≥0,j=1,2,…6OR188例题3建模目标函数：minZ=x1+x2+x3+x4+x5归纳：线性规划的一般模式目标函数：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≥0OR189归纳：线性规划的一般模式目标函数：max(min)Z=c1x2.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下方的半平面。所有半平面的交集称之为可行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解。OR1902.1.2线性规划图解法由中学知识可知：y=ax+b是一条直例1图示.9080604020020406080100x1

x29x1+4x2

≤3604x1+5x2

≤2003x1+10x2

≤300ABCDEFGHIZ=70x1+120x2OR191例1图示.908060概念概念：1、可行解：满足所有约束条件的解。2、可行域：即可行解的集合。所有约束条件的交集，也就是各半平面的公共部分。满足所有约束条件的解的集合，称为可行域。3、基解：约束条件的交点称为基解（直观）4、基可行解：基解当中的可行解。5、凸集：集合内任意两点的连线上的点均属于这个集合。如：实心球、三角形OR192概念概念：OR122结论可行域是个凸集可行域有有限个顶点最优值在可行域的顶点上达到无穷多解的情形无界解情形无解情形OR193结论可行域是个凸集OR1232.1.3线性规划的标准型代数式maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2………am1x1+am2x2+…+amnxn=bmxj

≥0j=1,2,…,nOR1942.1.3线性规划的标准型代数式maxZ=c1x1+c2x2线性规划的标准型和式：maxZ=∑cjxj

∑aijxj=bii=1,2,…,mxj≥0

j=1,2,…,nj=1nnj=1OR195线性规划的标准型和式：maxZ=∑cjxjj=1nnj=1O线性规划的标准型向量式：maxZ=CX

∑pjxj=bi

i=1,2,…,m

xj≥0j=1,2,…,nC=(c1,c2,c3,…,cn)

X=(X1,X2,X3,…,Xn)Tnj=1OR196线性规划的标准型向量式：maxZ=CXnj=1OR126线性规划的标准型矩阵式：maxZ=CXAX=bX≥0

其中：b=(b1,b2,…,bm)T

a11

a12….a1nA=a21

a22…a2n………

am1

am2…amnOR197线性规划的标准型矩阵式：maxZ=CXAX=b标准型的特征目标函数极大化约束条件为等式决策变量非负OR198标准型的特征目标函数极大化OR128非标准型转化为标准型目标函数极小化转为极大化：minZ=－max(－Z)，一个数的极小化等价于其相反数的极大化。不等式约束的转化：∑aijxj≤bi加入松弛变量

∑aijxj≥bi减去剩余变量非正变量：即xk

≤0则令x’k=－xk

自由变量：即xk无约束，令xk=x’k－x”kOR199非标准型转化为标准型目标函数极小化转为极大化：OR129非标准型转化举例之一maxZ=70X1+120X2maxZ=70X1+120X29X1+4X2≤3609X1+4X2+X3=3604X1+5X2

≤2004X1+5X2+x4=2003X1+10X2

≤3003X1+10X2+x5=300

X1≥0X2≥0Xj≥0j=1,2,…,5OR1100非标准型转化举例之一maxZ=70X1+120X2非标准型转化举例之二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=23x1+x2-3x3=5－3x’1+x2－3(x’3－

x”3

)=5x1≤0x2≥0x3无约束

x’1≥0x2≥0x’3≥0x”3≥0x4≥0

x5≥0

OR1101非标准型转化举例之二minZ=x1+2x2-3x32.1.4基可行解基的概念：如前所述LP标准型和式：maxZ=∑cjxj

∑aijxj=bi

xj

≥0

j=1,2,…,n

矩阵式：maxZ=CXAX=bX≥0

约束方程的系数矩阵A的秩为m，且m<n。设A=B+N，B是A中mm阶非奇异子矩阵，则称B是LP的一个基，即：B是A中m个线性无关向量组。nj=1nj=1OR11022.1.4基可行解基的概念：如前所述LP标准型nj=1nj=基解的概念不失一般性,设B是A的前m列,即B=(p1,p2,…,pm）,其相对应的变量XB=(x1,x2,…,xm)T,称为基变量；其余变量XN=(Xm+1,…,Xn)T称为非基变量。令所有非基变量等于零,则X=（x1,x2,…xm,0,…,0)T称为基解。OR1103基解的概念不失一般性,设B是A的前m列,即B基可行解的概念基可行解：基解可正可负，负则不可行（违背非负性约束条件），称满足所有约束条件的基解为基可行解。退化的基可行解：若某个基变量取值为零，则称之为退化的基可行解。基解的数目：最多Cmn=n!/m!(n-m)!OR1104基可行解的概念基可行解：基解可正可负，负则不可行（违背非负性例题6基可行解说明

maxZ=70X1+120X2P1P2P3P4P5

9X1+4X2+X3=36094100

4X1+5X2+x4=200A=45010

3X1+10X2+x5=300310001