《管理运筹学》提纲Word文档下载推荐.docx

1、管理科学的发展，定量越来越多。但定量不可替代定性。1.5运筹学的模型 模型：真实事物的模仿，主要因素、相互关系、系统结构。 形象模型：如地球仪、沙盘、风洞 模拟模型：建港口，模拟船只到达。学生模拟企业管理系统运行。 数学模型：用符号或数学工具描述现实系统。V=F（xi,yj,uk） G（xi,yj,uk）01.6运筹学的学科体系 规划论：线性规划、非线性规划|、整数规划、目标规划、动态规划 图论与网络 存储论 排队论 决策论 对策论 计算机仿真1.7运筹学的工作步骤 确定问题 搜集数据建立模型 检验模型 求解模型 结果分析 结果实施1.8运筹学与计算机 计算机为运筹学提供解题工具。 本书有现成

2、的程序可以利用 要学会解题的思路与方法，建立模型很重要。第二章 线性规划与单纯形法 2.1 LP（linear programming）的基本概念 LP是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。LP有一组有待决策的变量， 一个线性的目标函数， 一组线性的约束条件。2.1.1 LP的数学模型 例题1生产计划问题 某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：例题1建模 问题：如何安排生产计划，使得获利最多？ 步骤：1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23

3、、确定约束条件：人力约束 9X1+4X2360 设备约束 4X1+5X2 200 原材料约束3X1+10X2 300 非负性约束X10 X20例题2配方问题 养海狸鼠 饲料中营养要求：VA每天至少700克，VB每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表：例题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.

4、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建模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归纳：线性规划的一般模式max（min）Z=c1x1+c2x2+c3x3+cnxna11x1+a12x2+a13x3+a1nxn （= ）b1 a21x1+a22x2+a23

5、x3+a2nxn （= ）b2 am1x1+am2x2+am3x3+amnxn （= ）bnx1 0,x2 0,xn 02.1.2线性规划图解法 由中学知识可知：y=ax+b是一条直线，同理：Z=70x1+120x2x2=70/120x1-Z/120 也是一条直线，以Z 为参数的一族等值线。 9x1+4x2 360 x1 360/9-4/9x2 是直线 x1=360/9-4/9x2 下方的半平面。所有半平面的交集称之为可行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解。例1图示.概念 概念：1、可行解：满足所有约束条件的解。2、可行域：即可行解的集合。所有约束条件的交集，也就是

6、各半平面的公共部分。满足所有约束条件的解的集合，称为可行域。3、基解：约束条件的交点称为基解（直观）4、基可行解：基解当中的可行解。5、凸集：集合内任意两点的连线上的点均属于这个集合。如：实心球、三角形结论 可行域是个凸集 可行域有有限个顶点 最优值在可行域的顶点上达到 无穷多解的情形 无界解情形 无解情形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线性规划的标准型 和式：maxZ=cjxj aijxj=bi i=1

7、,2,m 向量式：maxZ=CX pjxj=bi i=1,2,m C=（c1,c2,c3,cn） X=（X1,X2,X3,Xn） T 矩阵式： maxZ=CX AX=b X 0 其中： b=（b1,b2,bm）T a11 a12 .a1n A= a21 a22 a2n am1 am2 amn标准型的特征 目标函数极大化 约束条件为等式 决策变量非负非标准型转化为标准型 目标函数极小化转为极大化： minZ=max（Z） ，一个数的极小化等价于其相反数的极大化。 不等式约束的转化： aijxjbi 加入松弛变量 aijxjbi 减去剩余变量 非正变量：即xk 0 则令xk = xk 自由变量：即

8、xk无约束，令xk= xkx”k非标准型转化举例之一maxZ=70X1+120X2 maxZ=70X1+120X2 9X1+4X2360 9X1+4X2+X3=360 4X1+5X2 200 4X1+5X2 +x4=200 3X1+10X2 300 3X1+10X2+x5 =300 X10 X20 Xj0 j=1,2,5非标准型转化举例之二minZ=x1+2x2-3x3 maxZ=x12x2+3（x3x”3） x1+x2+x3 9 x1+x2+x3 x”3 + x4=9 -x1-2x2+x3 2 x12x2+x3 x”3 - x5= 2 3x1+x2-3x3=5 3x1+x23（x3 x”3

9、）=5 x1 0 x2 0 x3无约束 x1 0 x2 0 x3 0 x”3 0 x40 x50 2.1.4基可行解 基的概念：如前所述LP标准型和式：maxZ= cjxj aijxj=bi xj 0 j=1,2,n 矩阵式：maxZ=CX AX=b X 0 约束方程的系数矩阵A 的秩为m ，且m0 =bL/ aLk 。 这时原基变量XL=0，由基变量变成非基变量，aLk处在变量转换的交叉点上，称之为枢轴元素单纯形法解题举例单纯形表的格式：2.2.3单纯形法的计算步骤 找到初始可行基，建立单纯形表 计算检验数，若所有j 0 则得最优解，结束。否则转下步 若某K 0而PK 0 ，则最优解无界，结

10、束。 根据max j = K 原则确定XK 进基变量；根据规则 ： = min bi / aik aik 0 = bL/ aLk 确定XL为出基变量 以aLk 为枢轴元素进行迭代，回到第二步2.3单纯形法的进一步探讨 2.3.1极小化问题直接求解：检验数的判别由所有j 0 即为最优， 变为所有j 0 则为最优。 人工变量法之一：大M法 人工变量价值系数M例 人工变量法之二：构造目标函数，分阶段求解例 2.3.2无穷多最优解情形：非基变量检验数 j= 0 2.3.3退化解的情形：有两个以上 值相等2.3.4单纯形法的计算机求解 程序说明 应用举例例题1例题22.5LP应用举例之一 例13合理下料

11、问题料长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件。则： 本期生产+

12、上期库存-本期库存=本期需求第三章 对偶问题与灵敏度分析 要求： 了解LP对偶问题的实际背景 了解对偶问题的建立规则与基本性质 掌握对偶最优解的计算及其经济解释 掌握LP的灵敏度分析 理解计算机输出的影子价格与灵敏度分 析的内容3.1 对偶问题 3.1.1 对偶问题的提出 回顾例题1： 现在A、B两产品销路不畅，可以将所有资源出租或外卖，现在要谈判，我们的价格底线是什么？对偶模型 设每个工时收费Y1元，设备台时费用Y2元，原材料附加费Y3元。 出租收入不低于生产收入： 9y1+4y2+3y3 70 4y1+5y2+10y3 120 目标：=360y1+200y2+300y3 出租收入越多越好？

13、至少不低于某数 原问题与对偶问题之比较原问题： 对偶问题：maxZ=70X1+120X2 min=360y1+200y2+300y3 9X1+4X2360 9y1+4y2+3y3 70 4X1+5X2 200 （3.1） 4y1+5y2+10y3 120 （3.2） 3X1+10X2 300 y1 0, y2 0, y3 0X10 X203.1.2对偶规则原问题一般模型： 对偶问题一般模型：maxZ=CX min =Yb AX b YA C X 0 Y 0对偶规则 原问题有m个约束条件，对偶问题有m个变量 原问题有n个变量，对偶问题有n个约束条件 原问题的价值系数对应对偶问题的右端项 原问题的

14、右端项对应对偶问题的价值系数 原问题的技术系数矩阵转置后为对偶问题系数矩阵 原问题的约束条件与对偶问题方向相反 原问题与对偶问题优化方向相反对偶规则简捷记法 原问题标准则对偶问题标准 原问题不标准则对偶问题不标准 例题2 max =7y1+4y2-2y3minZ=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 无约束 3

15、.1.3对偶问题的基本性质 对称性：对偶问题的对偶问题是原问题 弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值 （鞍型图） 无界性：原问题无界，对偶问题无可行解 对偶定理：若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。若原问题最优基为B，则其对偶问题最优解Y*=CBB-13.1.4对偶最优解的经济解释影子价格 Z= =CX=Yb Z/ b=（Yb）=Y Z=Yb= yibi的意义：Y是检验数的反数。在Y确定的前提下，每增加一个单位的i种资源，对目标函数的贡献。 结合例题1讲解影子价格：y1=0:第一种资源过剩 y2=13.6：设备台时最紧张

16、，每增加一个台时， 利润增加13.6元。y3=5.2 影子价格所含有的信息： 1、资源紧缺状况 2、确定资源转让基价参见：P40 3、取得紧缺资源的代价3.2灵敏度分析 为什么进行灵敏度分析？ 灵敏度分析的两把尺子： j =Cj-CBB-1pj 0 ； xB= B-1b 03.2.1 价值系数的灵敏度分析 Cj变化到什么程度可以保持最优基不变？用 （参看P96） 例题4 ： 87.5 C2 233.33 ；36 C1 96灵敏度分析 右端项的灵敏度分析： bi变化到什么程度可以保持最优基不变？用尺度 xB= B-1b 0 例题5 ： 1 -3.12 1.16 360 B-1b= 0 0.4 -

17、0.2 200 0 0 -0.12 0.16 b3 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习题课： P782.1

18、0（1）唯一最优解：H3 0 ，H5 0 ， H1 0（2）无穷多最优解： H3=0， H1 0， H5 0 ， H2 或 H5=0， H1 0， H3 0， H4（3）无界解： H50， H4 0 ， H1 0， H3 0（4）退化最优解： H1=0 ， H3 0 ， H5 0（5）非最优解，X1进基，X2出基： H1 0， H30 ， H20， P792.11 1、对 2、错，可能有最优解 3、对 4、对 5、错 6、错 7、错在“可行” 8、对 9、错 P812.16 设白天电视广告X1个，黄金时间电视广告X2个，广播广告X3个，杂志广告X4个 maxZ=40X1+90X2+50X3+2

19、X4 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 j0 j=1、2、3、4 P812.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 P1073.2 1、对，根据若对偶性 2、对，同上 3、对，同上 4、对，因为影子价格是每增加一个单位的某种资源，对目标函数的贡献程度 5、对，根据强对偶定理习题课 P

20、1073.5 注：目标函数为最大化 1、这是线性规划的逆运算 对偶问题最优解 ： Y1=4、Y2=2、Y3=0、Y4=4、Y5=0 P1093.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

21、, j=1,2,n,从Ai到Bj的每单位物资的运费为Cij.要求拟定总运费最小的调运方案 。 运输表 运输问题的数学模型设从Ai 到Bj的运输量为xij,（假定产销平衡）则总运费： minZ= Cij xij 产量约束： xij = ai i=1,2,m, 销量约束： xij = bj j=1,2,n, 非负性约束： xij 0 4.2表上作业法 计算步骤：1、给出初始方案2、检验是否最优3、调整调运方案 , Go to 2例题1 某建材公司有三个水泥厂A1、A2、A3，四个经销商B1、B2、B3、B4，其产量、销量、运费如下表：4.2.1求初始调运方案 用最小元素法（也可用西北角法或vogel法）给出初始基可行解： 在运费表中找出最小元素，尽最大可能用完一个厂的产量，或满足一个商家的销量。得到满足者用线划去。