运筹学课件
- 1. OR1*OPERATIONS RESEARCH 运筹学Ⅰ——怎样把事情做到最好 郝英奇
- 2. OR1*第一章 绪论1.1题解 Operations 汉语翻译 工作、操作、行动、手术、运算 Operations Research 日本——运用学 港台——作业研究 中国大陆——运筹学 Operational Research原来名称，意为军事行动研究——历史渊源
- 3. OR1*绪论1.2 运筹学的历史 早期运筹思想：田忌赛马 丁渭修宫 沈括运粮 Erlang 1917 排队论 Harris 1920 存储论 Levinson 1930 零售贸易 康脱洛维奇 1939 LP
- 4. OR1*绪论1.2运筹学的历史 军事运筹学阶段 德军空袭 防空系统 Blackett 运输船编队 空袭逃避 深水炸弹 轰炸机编队
- 5. OR1*绪论1.2运筹学的历史 管理运筹学阶段 战后人员三分:军队、大学、企业 大学：课程、专业、硕士、博士 企业：美国钢铁联合公司 英国国家煤炭局 运筹学在中国：50年代中期引入 华罗庚推广 优选法、统筹法 中国邮递员问题、运输问题
- 6. OR1*1.3学科性质应用学科 Morse&Kimball定义：运筹学是为决策机构在对其控制的业务活动进行决策时提供的数量化为基础的科学方法。 Churchman定义：运筹学是应用科学的方法、技术和工具，来处理一个系统运行中的问题，使系统控制得到最优的解决方法。 中国定义：运筹学是应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。
- 7. OR1*1.4定性与定量例：店主进货 两者都是常用的决策方法 定性是基础，定量是工具，定量为定性服务。 定性有主观性也有有效性，定量有科学性也有局限性。管理科学的发展，定量越来越多。但定量不可替代定性。
- 8. OR1*1.5运筹学的模型模型：真实事物的模仿，主要因素、相互关系、系统结构。 形象模型：如地球仪、沙盘、风洞 模拟模型：建港口，模拟船只到达。学生模拟企业管理系统运行。 数学模型：用符号或数学工具描述现实系统。V=F（xi,yj,uk) G(xi,yj,uk)≥0
- 9. OR1*1.6运筹学的学科体系规划论：线性规划、非线性规划|、整数规划、目标规划、动态规划 图论与网络 存储论 排队论 决策论 对策论 计算机仿真
- 10. OR1*1.7运筹学的工作步骤确定问题 搜集数据建立模型 检验模型 求解模型 结果分析 结果实施
- 11. OR1*1.8运筹学与计算机计算机为运筹学提供解题工具。 本书有现成的程序可以利用 要学会解题的思路与方法，建立模型很重要。
- 12. OR1*第二章 线性规划与单纯形法2.1 LP(linear programming)的基本概念 LP是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。 LP有一组有待决策的变量， 一个线性的目标函数， 一组线性的约束条件。
- 13. OR1*2.1.1 LP的数学模型 例题1—生产计划问题某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：产品A产品B资源限量劳动力 设 备 原材料9 4 34 5 10360 200 300利润元/kg70120
- 14. OR1*例题1建模问题：如何安排生产计划，使得获利最多？ 步骤： 1、确定决策变量：设生产A产品x1kg,B产品x2kg 2、确定目标函数：maxZ=70X1+120X2 3、确定约束条件：人力约束 9X1+4X2≤360 设备约束 4X1+5X2 ≤200 原材料约束3X1+10X2 ≤300 非负性约束X1≥0 X2≥0
- 15. OR1*例题2——配方问题养海狸鼠 饲料中营养要求：VA每天至少700克，VB每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表：饲料VaVbVc价格元/KGI II III IV V3 2 1 6 181 0.5 0.2 2 0.50.5 1 0.2 2 0.82 7 4 9 5营养要求70030200
- 16. OR1*例题2建模设抓取饲料I x1kg;饲料II x2kg;饲料III x3kg…… 目标函数：最省钱 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
- 17. OR1*例题3：人员安排问题医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计： 序号时段最少人数安排人数106—1060X1210—1470X2314—1860X3418—2250X4522—0220X5602—0630x6
- 18. OR1*例题3建模目标函数：min Z=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
- 19. OR1*归纳：线性规划的一般模式目标函数：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
- 20. OR1*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 下方的半平面。所有半平面的交集称之为可行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解。
- 21. OR1*例1图示. 90 80 60 40 20 0 20 40 60 80 100x1 x29x1+4x2 ≤ 3604x1+5x2 ≤200 3x1+10x2 ≤300ABCDEFGHIZ=70x1+120x2
- 22. OR1*概念概念： 1、可行解：满足所有约束条件的解。 2、可行域：即可行解的集合。所有约束条件的交集，也就是各半平面的公共部分。满足所有约束条件的解的集合，称为可行域。 3、基解：约束条件的交点称为基解（直观） 4、基可行解：基解当中的可行解。 5、凸集：集合内任意两点的连线上的点均属于这个集合。如：实心球、三角形
- 23. OR1*结论可行域是个凸集 可行域有有限个顶点 最优值在可行域的顶点上达到 无穷多解的情形 无界解情形 无解情形
- 24. OR1*2.1.3线性规划的标准型代数式maxZ=c1x1+c2x2+…+cnxn a11x1+a12x2+…+a1nxn=b1 a21x1+a22x2+…+a2nxn=b2 … … … am1x1+am2x2+…+amnxn=bm xj ≥0 j=1,2,…,n
- 25. OR1*线性规划的标准型和式：maxZ=∑cjxj ∑aijxj=bi i=1,2,…,m xj ≥0 j=1,2,…,n j=1nnj=1
- 26. OR1*线性规划的标准型向量式：maxZ=CX ∑pjxj=bi i=1,2,…,m xj ≥0 j=1,2,…,n C=(c1,c2,c3,…,cn) X=(X1,X2,X3,…,Xn) Tnj=1
- 27. OR1*线性规划的标准型矩阵式： maxZ=CX AX=b X ≥0 其中： b=(b1,b2,…,bm)T a11 a12 ….a1n A= a21 a22 … a2n … … … am1 am2 …amn
- 28. OR1*标准型的特征目标函数极大化 约束条件为等式 决策变量非负
- 29. OR1*非标准型转化为标准型目标函数极小化转为极大化： minZ=－max(－Z) ，一个数的极小化等价于其相反数的极大化。 不等式约束的转化： ∑aijxj≤bi 加入松弛变量 ∑aijxj≥bi 减去剩余变量 非正变量：即xk ≤0 则令x’k =－ xk 自由变量：即xk无约束，令xk= x’k－x”k
- 30. OR1*非标准型转化举例之一maxZ=70X1+120X2 maxZ=70X1+120X2 9X1+4X2≤360 9X1+4X2+X3=360 4X1+5X2 ≤200 4X1+5X2 +x4=200 3X1+10X2 ≤300 3X1+10X2+x5 =300 X1≥0 X2≥0 Xj≥0 j=1,2,…,5
- 31. OR1*非标准型转化举例之二minZ=x1+2x2-3x3 maxZ’=x’1－2x2+3(x’3－x”3) x1+x2+x3 ≤9 －x’1+x2+x’3－ x”3 + x4=9 -x1-2x2+x3 ≥2 x’1－2x2+x’3 －x”3 - x5= 2 3x1+x2-3x3=5 － 3x’1+x2－3(x’3 － x”3 )=5 x1 ≤0 x2 ≥0 x3无约束 x’1 ≥ 0 x2 ≥0 x’3 ≥0 x”3 ≥0 x4≥0 x5≥0
- 32. OR1*2.1.4基可行解基的概念：如前所述LP标准型
和式：maxZ= ∑cjxj ∑aijxj=bi xj ≥0 j=1,2,…,n
矩阵式：maxZ=CX AX=b X ≥0
约束方程的系数矩阵A的秩为m，且m
- 33. OR1*基解的概念 不失一般性,设B是A的前m列,即B=(p1,p2,…,pm）,其相对应的变量XB=(x1,x2,…,xm)T,称为基变量；其余变量XN=(Xm+1,…,Xn)T称为非基变量。令所有非基变量等于零,则X=（x1,x2,…xm,0,…,0)T称为基解 。
- 34. OR1*基可行解的概念基可行解：基解可正可负，负则不可行（违背非负性约束条件），称满足所有约束条件的基解为基可行解。 退化的基可行解：若某个基变量取值为零，则称之为退化的基可行解。 基解的数目：最多Cmn=n!/m!(n-m)!
- 35. OR1*例题6 基可行解说明 maxZ=70X1+120X2 P1 P2 P3 P4 P5 9X1+4X2+X3=360 9 4 1 0 0 4X1+5X2 +x4=200 A= 4 5 0 1 0 3X1+10X2+x5 =300 3 10 0 0 1 Xj≥0 j=1,2,…,5 这里m=3,n=5。 Cmn=10
- 36. OR1*例题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图）
- 37. OR1*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）T z0=∑cibi’
- 38. OR1*2.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’2 x2=b’2- ∑a’2jxj …………………………….. …………….. xm+a’mm+1xm+1+…+a’mnxn=b’m xm=b’m- ∑a’mjxj
- 39. OR1*单纯形法一般性表示：xi=b’i- ∑a’ijxj i=1,2,…m 将xi代入目标函数得：Z= ∑ cjxj = ∑ cixi+ ∑ cjxj = ∑ci（ b’i- ∑a’ijxj ） + ∑ cjxj = ∑cibi’+ ∑(cj- ∑ cia’ij)xj 令：σj= cj- ∑ cia’ij z0=∑cibi’ 则Z=z0+ ∑ σj xj σj判别准则 ： σj ≤0 时,达到最优解
- 40. OR1*单纯形法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’ik a’ik >0 } =b’L/ a’Lk 。 这时原基变量XL=0，由基变量变成非基变量， a’Lk处在变量转换的交叉点上，称之为枢轴元素σj ≥ 0
- 41. OR1*单纯形法解题举例单纯形表的格式： CjC1 C2 … Cn θi CBXBbx1 x2 …. xn C1 C2 … Cmx1 x2…xmb 1 b2 … bma11 a12 … a1n a21 a22 … a2n … … … am1 am2… amn θ1 θ2 … θm σj σ1 σ2 … σn
- 42. OR1* CjC1 C2 … CnCBXBbX1 X2 X3 X4 X5θj 0 0 0X3 X4 X5360 200 300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1 90 40 30σj0 70 120 0 0 0 0 0 120X3 X4 X2240 50 30 7.8 0 1 0 -0.4 2.5 0 0 1 -0.5 0.3 1 0 0 0.130.76 20 100σj3600 34 0 0 0 -1270 1200X3 X1 X284 20 24 0 0 1 -3.12 1.16 1 0 0 0.4 -0.2 0 1 0 -0.12 0.16σj4280 0 0 0 -13.6 -5.2
- 43. OR1*2.2.3单纯形法的计算步骤 找到初始可行基，建立单纯形表 计算检验数，若所有σj ≤0 则得最优解，结束。否则转下步 若某σK ≥ 0而P’K ≤0 ，则最优解无界，结束。否则转下步 根据max {σj } = σK 原则确定XK 进基变量；根据θ规则 ：θ = min {b’i / a’ik a’ik >0} = b’L/ a’Lk 确定XL为出基变量 以a’Lk 为枢轴元素进行迭代，回到第二步
- 44. OR1*2.3单纯形法的进一步探讨2.3.1极小化问题直接求解：检验数的判别由所有σj ≤0 即为最优，变为所有σj ≥ 0则为最优。 人工变量法之一：大M法 人工变量价值系数M例 人工变量法之二：构造目标函数，分阶段求解例 2.3.2无穷多最优解情形：非基变量检验数 σj= 0 2.3.3退化解的情形：有两个以上 θ值相等
- 45. OR1*2.3.4单纯形法的计算机求解程序说明 应用举例 例题1 例题2
- 46. OR1*2.5LP应用举例之一例13合理下料问题 料长7.4米，截成2.9、2.1、1.5米各200根。如何截取余料最少？关键：设变量。 方案 料型 1 2 3 4 5 6 7 8 2.9米 2.1米 1.5米 1 2 0 1 0 1 0 0 0 0 2 2 1 1 3 0 3 1 2 0 3 1 0 4 合计 残料 7.4 7.3 7.2 7.1 6.6 6.5 6.3 6.0 0 0.1 0.2 0.3 0.8 0.9 1.1 1.4
- 47. OR1*应用举例之二 例14混合配方问题 A、B、C、D四种原料配制三种产品，三类约束：技术要求、原料限量、市场容量。已知产品价格和原料价格，求利润最大的配方。关键：设变量。
- 48. OR1*应用举例之三例15.滚动投资问题 兹有100万元闲钱，投资方向有四： 第四年第一年第二年第三年A项目110%B项目135%C项目125%D项目104%第五年各年投资什么项目，使第五年末资本总额为最大？
- 49. OR1*应用举例之四例16动态生产计划问题 工厂做n个月的生产计划，第j月需求量dj、正常生产能力aj、加班生产能力bj、正常生产成本cj、加班生产成本ej、库存能力为I、库存费用hj，设期初、期末库存为零。求费用最小的生产计划。 设第月正常生产xj件，加班生产件yj，存储zj件。则： 本期生产+上期库存-本期库存=本期需求
- 50. OR1*第三章 对偶问题与灵敏度分析要求： 了解LP对偶问题的实际背景 了解对偶问题的建立规则与基本性质 掌握对偶最优解的计算及其经济解释 掌握LP的灵敏度分析 理解计算机输出的影子价格与灵敏度分 析的内容
- 51. OR1*3.1 对偶问题3.1.1 对偶问题的提出 回顾例题1： 现在A、B两产品销路不畅，可以将所有资源出租或外卖，现在要谈判，我们的价格底线是什么？ 产品A产品B资源限制劳动力 设备 原材料 9 4 3 4 5 10 360 200 300单位利润 70 120
- 52. OR1*对偶模型设每个工时收费Y1元，设备台时费用Y2元，原材料附加费Y3元。 出租收入不低于生产收入： 9y1+4y2+3y3 ≥70 4y1+5y2+10y3 ≥120 目标：ω=360y1+200y2+300y3 出租收入越多越好？至少不低于某数
- 53. OR1*原问题与对偶问题之比较原问题： 对偶问题： maxZ=70X1+120X2 minω=360y1+200y2+300y3 9X1+4X2≤360 9y1+4y2+3y3 ≥70 4X1+5X2 ≤200 (3.1) 4y1+5y2+10y3 ≥120 (3.2) 3X1+10X2 ≤300 y1 ≥0, y2 ≥0, y3 ≥0 X1≥0 X2≥0
- 54. OR1*3.1.2对偶规则原问题一般模型： 对偶问题一般模型： maxZ=CX min ω=Yb AX ≤b YA ≥C X ≥0 Y ≥0
- 55. OR1*对偶规则原问题有m个约束条件，对偶问题有m个变量 原问题有n个变量，对偶问题有n个约束条件 原问题的价值系数对应对偶问题的右端项 原问题的右端项对应对偶问题的价值系数 原问题的技术系数矩阵转置后为对偶问题系数矩阵 原问题的约束条件与对偶问题方向相反 原问题与对偶问题优化方向相反
- 56. OR1*对偶规则. 原问题 对偶问题目标函数 max min 目标函数约束条件 ≤ ≥ =≥ 变量 ≤ 无约束 ≥ 变量符号 ≤ 无约束≥ ≤ 约束条件 =
- 57. OR1*对偶规则简捷记法原问题标准则对偶问题标准 原问题不标准则对偶问题不标准 例题2 max ω=7y1+4y2-2y3 minZ=3x1+2x2-6x3+x5 2y1+ y2- y3 ≤3 2x1+x2-4x3+x4+3x5 ≥7 y1 +3y3 ≤2 x1+ 2x3 -x4 ≤ 4 -4y1+ 2y2 ≤-6 -x1+3x2 -x4+ x5 =-2 y1 -y2 -y3 ≥ 0 x1，x2，x3 ≥0; 3y1 +y3=1 x4 ≤ 0;x5无限制 y1 ≥ 0y2 ≤ 0y3 无约束
- 58. OR1*3.1.3对偶问题的基本性质对称性：对偶问题的对偶问题是原问题 弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值 (鞍型图) 无界性：原问题无界，对偶问题无可行解 对偶定理：若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。若原问题最优基为B，则其对偶问题最优解Y*=CBB-1
- 59. OR1*3.1.4对偶最优解的经济解释—影子价格Z= ω=CX=Yb Z/ b=(Yb)’=Y Z=Yb= ∑yibi的意义：Y是检验数的反数。在Y确定的前提下，每增加一个单位的i种资源，对目标函数的贡献。 结合例题1讲解影子价格：y1=0:第一种资源过剩 y2=13.6：设备台时最紧张，每增加一个台时， 利润增加13.6元。y3=5.2… 影子价格所含有的信息： 1、资源紧缺状况 2、确定资源转让基价 参见：P40 3、取得紧缺资源的代价
- 60. OR1*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
- 61. OR1*灵敏度分析右端项的灵敏度分析： bi变化到什么程度可以保持最优基不变？用尺度 xB= B-1b ≥0 例题5： 1 -3.12 1.16 360 B-1b= 0 0.4 -0.2 200 ≥0 0 -0.12 0.16 b3 b3的变化范围：227.586 ≤ b3 ≤ 400
- 62. OR1*其它形式的灵敏度分析 新产品的分析： 在资源结构没有变化的条件下，是否生产这种新 产品，就看它的竞争力如何。 例题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，加入到末表之中，继续迭代，直到求得最优解。
- 63. OR1*3.3用计算机进行灵敏度分析例题7 参见P102
- 64. OR1*习题课：P78——2.10 （1）唯一最优解：H3 ≤ 0 ，H5≤ 0 ， H1 ≥0 （2）无穷多最优解： H3=0， H1 ≥0， H5 0 ， H2>0 或 H5=0， H1 ≥0， H3 0， H4>0 （3）无界解： H5≥0， H4 0 ， H1 ≥0， H3 0 （4）退化最优解： H1=0 ， H3 0 ， H5 0 （5）非最优解，X1进基，X2出基： H1 ≥0， H3>0 ， H2>0，5H2
- 65. OR1*习题课：P79——2.11 1、对 2、错，可能有最优解 3、对 4、对 5、错 6、错 7、错在“可行” 8、对 9、错
- 66. OR1*习题课：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 ≥3 X2 ≥2 X3 ≥5 X3 ≤10 X4 ≥5 X4 ≤10 X j≥0 j=1、2、3、4
- 67. OR1*习题课：P81——2.17 设A产品生产X1单位，B产品生产X2单位，C产品销毁X3单位 maxZ=5X1+10X2+3（2X2-X3）-1X3 2X1+3X2 ≤200 3X1+4X2 ≤240 2X2-X3 ≤10 X1、X2、X3 ≥0
- 68. OR1*习题课：P107——3.2 1、对，根据若对偶性 2、对，同上 3、对，同上 4、对，因为影子价格是每增加一个单位的某种资源，对目标函数的贡献程度 5、对，根据强对偶定理
- 69. OR1*习题课P107——3.5 注：目标函数为最大化 1、这是线性规划的逆运算 对偶问题最优解 ： Y1=4、Y2=2、Y3=0、Y4=4、Y5=0
- 70. OR1*习题课P109——3.8 1、原问题的最优解：X1=6，X5=10，其余为零;对偶问题最优解：Y1=2,Y2=0 C1的变化范围：以C1代入末表， C1 ≥1 右端项变化范围： xB= B-1b ≥0 b1 ≥-6，b2≥-10
相关PPT