运筹学 第一二章-引言+线性规划

《运筹学》任课教师：邮箱：@163.com手机：1引言1.1“运筹”的含义最早出自《史记·高祖本纪》：“夫运筹帷幄之中，决胜千里之外，吾不如子房。”现代含义：运筹是对资源进行统筹安排，决策者进行决策提供最优解决方案，以达到最有效的管理。古代典故：齐王赛马，丁谓修皇宫，沈括运粮。1引言1.2《运筹学》的由来与发展起源于20世纪30年代二战时期，当时由数学、军事领域技术人员组成的小组，有效的解决了雷达布局、反潜深水炸弹爆炸深度、大小船只逃避轰炸等军事问题。20世纪40-50年代，战争期间研究数据逐渐公开。1951年P.M.Morse和G.E.Kimball书写的《运筹学方法》著作问世。1引言1.2《运筹学》的由来与发展20世纪50年代开始，各国陆续成立运筹学会，英国1948、美国1952、法国1956、中国1980。英国OperationalResearch，美国OperationsResearch，简称OR，是当前管理科学领域的主要基础理论课程。1引言1.2《运筹学》的由来与发展运筹学在中国的发展1956年钱学森和许国志在中国科学院力学所成立第1个运筹学小组；1959年大跃进时期在中国科学院数学所成立第2个运筹学研究部门；1960年两个部门合并；1963年在中国科学技术大学开设《运筹学》课程；1965年开始，“华罗庚小分队”走遍20多个省，使“优选法”“统筹法”广为流传；（打麦场选址、中国邮递员问题）1980年成立运筹学学会（系统工程学会、管理科学学会）。1引言1.3《运筹学》的应用目前运筹学以被广泛的应用到：生产计划、库存管理、运输问题、财政和会计、工程优化与设计等众多领域。运筹学研究领域重要奖项：①INFORMSFranzEdelman奖，1972年开始每年选择一个运筹学领域的杰出应用成果授奖。/Recognize-Excellence/Franz-Edelman-Award获奖华人：于刚2002年。②INFORMSJohnvonNeumannTheoryPrize自1975年每年1-2人/Recognize-Excellence/INFORMS-Prizes-Awards/John-von-Neumann-Theory-Prize获奖华人：叶荫宇2009年本章小结运筹学是在实行管理的领域，运用数学方法，对需要进行管理的问题统筹规划，作出决策的一门应用科学。运筹学其他定义：主要研究人类对各种资源的运用及筹划活动，以期通过了解和发展这种运用及筹划活动的基本规律，发挥有限资源的最大效益，达到总体最优的目标。当前《运筹学》已成为管理类、工业工程类等专业的重要基础课程。2线性规划和单纯性法2.1模型的构建（1）生产计划问题例题1：某工厂在计划期内要安排生产I，II两种产品，已知生产单位产品所需要的设备台时和A、B两种原材料的消耗，如表所示。该工厂每生产一件产品I可获利2元，II可获利3元，问如何安排生产计划使该工厂获利最多？产品I产品II现有资源量设备128台时原材料A4016kg原材料B0412kg2线性规划和单纯性法2.1模型的构建建模的思路：a设立决策变量；b构建目标函数；c构建约束条件。本问题模型：决策变量：表示生产产品I的数量；表示生产产品II的数量；目标函数：约束条件：约束条件Part1：条件约束约束条件Part2：非负约束目标函数z的优化方向，Max表示越大越好，反之Min，全称Maximize，Minimize。2线性规划和单纯性法2.1模型的构建污水处理问题例题2：已知工厂1和工厂2同属某企业集团，且工厂1和2日排污水量分别为2万立方米和1.4万立方米，环保要求污水含量不超过0.2%，工厂1的污水流至工厂2可以自然净化20%，工厂1和2处理污水成本分别为1000元/万立方米和800元/万立方米，请问工厂1和2应各处理多少污水，使总成本最低。工厂1工厂2500万立方米200万立方米2线性规划和单纯性法2.1模型的构建决策变量：表示工厂1处理污水量；表示工厂2处理污水量；目标函数：约束条件：条件1工厂1处理污水后水质达标：条件2工厂2处理污水后水质达标：条件3决策变量和应该满足的条件？2线性规划和单纯性法2.1模型的构建整理后模型：2线性规划和单纯性法2.1模型的构建租车问题例题3：山东科技大学(青岛)在2015年招生8000余人，根据预先反馈信息在2015年9月19日有4800人(包括家长和接站人员)会到达青岛火车站。学校为了做好迎新工作，打算租用某公司车辆为新生接站，已知租车公司有小客车70辆，大客车40辆可供学校租用；且小客车可载16人(不包含司机)，大客车可载32人；小客车每天往返5次，大客车每天往返3次；小客车每天租金1200元，大客车每天租金1400元；请问山东科技大学应该租用大小客车各多少辆？2线性规划和单纯性法2.1模型的构建租车问题模型：2线性规划和单纯性法2.1模型的构建下料问题例题4：设原材料7.4m长1根，现需要1.5m、2.1m、2.9m各100根，求需要的原材料根数。

12345678需求1.5m001123341002.1m321021001002.9m01120010100余料（m）01.4x1x2x3x4x5x6x7x82线性规划和单纯性法2.1模型的构建下料问题模型：最优方案：z=90根。其中，x2=50，x4=10，x7=30，其他决策变量均为0。2线性规划和单纯性法2.1模型的构建项目连续投资问题例题5：某部门在今后五年内考虑给下列项目投资，已知：设当前有资金10万，请问如何投资这些项目，使到第5年年末拥有的资金最大？

项目投资方式本利%项目周期A第1-4年年初投资，于次年年末收回1152年B第3年年初投资，于第5年末收回，至多投资4万1253年C第2年年初投资，于第5年末收回，至多投资3万1404年D每年年初投资，于当年年末收回1061年2线性规划和单纯性法2.1模型的构建设决策变量。

项目第1年初第2年初第3年初第4年初第5年初Ax1Ax2Ax3Ax4ABx3BCx2CDx1Dx2Dx3Dx4Dx5D

项目第1年初第2年初第3年初第4年初第5年初第6年初A1.15x1A1.15x2A1.15x3A1.15x4AB1.25x3BC1.4x2CD1.06x1D1.06x2D1.06x3D1.06x4D1.06x5D投资表收益表2线性规划和单纯性法2.1模型的构建连续投资问题模型：2线性规划和单纯性法2.2图解法（1）适用条件：模型中仅有2个决策变量的简单模型如例题1：模型2线性规划和单纯性法2.2图解法（2）图解法步骤第一步：建立以x1为横坐标轴的直角坐标系，x2为纵坐标轴；第二步：根据约束条件，在坐标系中确定可行解的集合，即可行域；第三步：根据目标函数，在可行域中找到最优解。概念：解（方案）可分为（1）可行解（可行方案）；（2）不可行解（不可行方案）。满足所有约束条件的解为可行解，否则为不可行解。最优解：可行解中能够使目标函数取得最大（或最小）值的解。2线性规划和单纯性法2.2图解法（2）图解法基础知识直线方程，y=kx+b，其中k为斜率，b为截距；线性不等式在直角坐标系中代表的几何含义，如y>-x+1代表什么几何含义？xy11先画出边界直线y=-x+1再根据特殊点（不在边界直线上）法，确定线性不等式代表的半个平面2线性规划和单纯性法2.2图解法（3）例题1实例求解步骤一：建立直角坐标系；步骤二：确定可行域；步骤三：根据目标函数确定最优解。x1x232112344(2,3)(4,2)x1+2x2=84x2=124x1=162线性规划和单纯性法2.2图解法（4）图解法注意问题①横坐标轴为x1，纵坐标轴x2；②准确判断不等式约束条件代表的半平面区域，确定可行域；③区分目标函数直线束与约束条件边界直线的陡峭程度。如：斜率为1和2的直线，后者更陡峭；那么斜率为-1和-2的呢？注：斜率为同符号的，绝对值越大越陡峭。2线性规划和单纯性法2.2图解法（5）图解法的其他3种情况情况1：将例题1的模型修改如下：这种情况属于无穷多最优解x1x232112344(2,3)(4,2)线段上所有的点均为最优解。2线性规划和单纯性法2.2图解法（5）图解法的其他3种情况情况2：图解法求如下模型：这种情况属于无界解x1x232112344继续移动，目标函数可以无限制增大。2线性规划和单纯性法2.2图解法（5）图解法的其他3种情况情况3：图解法求如下模型：这种情况属于无可行解x1x232112344没有可行域。2线性规划和单纯性法2.2图解法（6）练习题污水处理问题模型；P55页，2.1题（1）-（4）2线性规划和单纯性法2.3线性规划问题的标准型（1）标准模型特点1：目标函数最大化特点2：约束条件均为等式特点3：等式右边常数均≥0特点4：所有决策变量均≥02线性规划和单纯性法2.3线性规划问题的标准型（2）标准模型的矩阵形式价值向量决策变量向量资源向量系数矩阵m＜n2线性规划和单纯性法2.3线性规划问题的标准型（2）标准模型的矩阵形式2线性规划和单纯性法2.3线性规划问题的标准型（3）非标准型模型的标准化练习P55-2.2（1）2线性规划和单纯性法2.3线性规划问题的标准型（4）相性规划问题的相关概念①可行解——满足所有约束条件(包括非负约束)的解②基——是标准模型系数矩阵A中，选择m列构成的m阶非奇异方阵，用B表示。如模型：2线性规划和单纯性法2.3线性规划问题的标准型（4）相性规划问题的相关概念

由于B是非奇异矩阵，所以是一个基。2线性规划和单纯性法2.3线性规划问题的标准型（4）相性规划问题的相关概念③基变量、非基变量基中系数列向量，对应的变量为基变量，其他的为非基变量。因此，一个基对应一种基变量和非基变量的划分方式，以上基显然，x3、x4、x5为基变量，x1，x2为非基变量。2线性规划和单纯性法2.3线性规划问题的标准型（4）相性规划问题的相关概念④基解、基可行解、基不可行解、可行基一个基会唯一对应一个基解；求本基对应的基解方式，在标准模型等式约束中，令非基变量x1，x2为0，解方程组求出所有的基变量x3、x4、x5。2线性规划和单纯性法2.3线性规划问题的标准型（4）相性规划问题的相关概念令非基变量x1，x2为0，解方程组求出所有的基变量x3、x4、x5。得到B对应的一个基解由于X中所有的变量值，也满足模型中的非负约束，因此为基可行解（此时可知B为可行基），否则为基不可行解。2线性规划和单纯性法2.3线性规划问题的标准型（4）相性规划问题的相关概念一个m×n的系数矩阵A，至多有多少个基？可行解、非可行解，基可行解，基不可行解的关系。练习题P55-2.3（1）（2）基可行解基不可行解可行解不可行解2线性规划和单纯性法2.3线性规划问题的标准型（4）相性规划问题的相关概念⑤凸集凸集的定义：如果在一个区域中（n维）的任意两个不同点之间的连线也同属于该区域，那么该集合为凸集。证明一个区域是凸集的方法，任取两个不同点，证明连线上的点均属于该区域。2线性规划和单纯性法2.3线性规划问题的标准型（4）相性规划问题的相关概念线性规划模型的可行域为凸集；凸集的“角”：一个点如果找不到两个不同的点，连一条线，使该点在连线上（不含连线端点），那么该点为角。基可行解与可行域凸集的角一一对应。如果一个线性规划问题有最优解，那么一定可以在基可行解中找到最优解。2线性规划和单纯性法2.4单纯形法（1）单纯形方法由于线性规划问题的最优解一定可以在基可行解中找到，那么穷举所有的基可行解一定可以找到最优解。但是遗憾的是当n和m足够大时会非常大。2线性规划和单纯性法2.4单纯形法（2）单纯形方法本质由美国著名运筹学家GeorgeBernardDantzig在1947年提出。单纯形方法本质：由任何一个基可行解开始，根据单纯形法规则可以找到下一个更优的基可行解，再不断重复单纯形法规则，直到找到最优的基可行解，即问题的最优解。单纯形法在线性规划领域的出现，就好比帮助一群迷路的登山者，找到了一条通往山顶的阶梯（可以保证每一步后都更接近目标）。2线性规划和单纯性法2.4单纯形法（3）单纯形方法适用于求解任何线性规划问题标准模型。2线性规划和单纯性法2.4单纯形法（3）单纯形方法步骤一：找到标准模型中的初始基可行解。如果标准模型系数矩阵中包括1个m阶单位矩阵，那么可以找到一个显见的基可行解。因此显见的基可行解为2线性规划和单纯性法2.4单纯形法（3）单纯形方法步骤二：基于当前的基可行解，找到下一个更优的基可行解。本步骤的内容是对等式约束条件和目标函数变形，即用非基变量和常数表示基变量和目标z。本例变形：选择系数为正数，且最大的非基变量。2线性规划和单纯性法2.4单纯形法（3）单纯形方法步骤二：基于当前的基可行解，找到下一个更优的基可行解。重新用当前非基变量和常数表示基变量和目标z。2线性规划和单纯性法2.4单纯形法（3）单纯形方法步骤二：基于当前的基可行解，找到下一个更优的基可行解。重新用当前非基变量和常数表示基变量和目标z。2线性规划和单纯性法2.4单纯形法（3）单纯形方法步骤二：基于当前的基可行解，找到下一个更优的基可行解。重新用当前非基变量和常数表示基变量和目标z。找不到系数大于0的非基变量，说明？2线性规划和单纯性法2.4单纯形法（3）单纯形方法步骤三：如果所有非基变量在目标函数中的系数小于等于0，说明找到最优解。2线性规划和单纯性法2.4单纯形法（3）单纯形方法将上述标准模型，修改。2线性规划和单纯性法2.4单纯形法（3）单纯形方法步骤一：找到标准模型中的初始基可行解。如果标准模型系数矩阵中包括1个m阶单位矩阵，那么可以找到一个显见的基可行解。因此显见的基可行解为2线性规划和单纯性法2.4单纯形法（3）单纯形方法步骤二：基于当前的基可行解，找到下一个更优的基可行解。本步骤的内容是对等式约束条件和目标函数变形，即用非基变量和常数表示基变量和目标z。本例变形：选择系数为正数，且最大的非基变量。2线性规划和单纯性法2.4单纯形法（3）单纯形方法步骤二：基于当前的基可行解，找到下一个更优的基可行解。重新用当前非基变量和常数表示基变量和目标z。2线性规划和单纯性法2.4单纯形法（3）单纯形方法步骤二：基于当前的基可行解，找到下一个更优的基可行解。重新用当前非基变量和常数表示基变量和目标z。2线性规划和单纯性法2.4单纯形法（3）单纯形方法步骤二：基于当前的基可行解，找到下一个更优的基可行解。重新用当前非基变量和常数表示基变量和目标z。2线性规划和单纯性法2.4单纯形法（3）单纯形方法步骤三：如果所有非基变量在目标函数中的系数小于等于0，说明找到最优解，如果还存在非基变量检验数等于0，说明有无穷个解。为什么求得两个不同基可行解，就可以确定得到无穷个最优解？证明：引理：如果可行域中线段端点使目标函数值相等，那么线段上的点目标函数值与端点相同。2线性规划和单纯性法2.4单纯形法（3）单纯形方法用单纯形法求解以下模型。2线性规划和单纯性法2.4单纯形法（3）单纯形方法此模型为无界解。说明x1可以无限制增加，x3和x4也不会取负数。2线性规划和单纯性法2.4单纯形法（4）单纯形表形式-唯一解单纯形表格式ci23000CBXBbx1x2x3x4x5zz000x3x4x5812100164001012040010002343x23x4x3000301001/4164001021010-1/20002-3/424-92线性规划和单纯性法2.4单纯形法（4）单纯形表形式-唯一解单纯形表格式ci23000CBXBbx1x2x3x4x5zx23x4x300301001/4164001021010-1/20002-3/424-92x1410000x5400-213x22010z14000x12x23x4021010-1/2800-412301001/4000-20-2×1-0×(-4)-3×0=-21/4-412z131/21/41/2-1/8-1/8-3/2目标Max：非基变量检验数，均小于0。2线性规划和单纯性法2.4单纯形法ci23000CBXBbx1x2x3x4x5-z000x3x4x58121001640010120400100023430ci23000CBXBbx1x2x3x4x5x23x4x300301001/4164001021010-1/20002-3/424-9z2线性规划和单纯性法2.4单纯形法（5）单纯形表-无穷多最优解ci24000CBXBbx1x2x3x4x5ci23000CBXBbx1x2x3x4x541000400-212011/201600-20x24x5x120zx12x24x4021010-1/2800-412301001/4000-20-412z161/41/2-1/80目标Max：非基变量检验数，均小于等于0，且至少有一个非基变量的检验数等于0。2线性规划和单纯性法2.4单纯形法2线性规划和单纯性法2.4单纯形法2线性规划和单纯性法2.4单纯形法（5）无穷最优解判断ci-2400CBXBbx1x2x3x40x34-121020x41-11011z0-24000x32101-224x21-1101-z4200-4-2x12101-24x23011-1z800-202线性规划和单纯性法2.4单纯形法（5）无穷最优解判断x1x232112344(2,3)射线上的点均为最优解2线性规划和单纯性法2.4单纯形法（6）单纯形表-无界解ci1100CBXBbx1x2x3x40x31-11100x44-1201z01100目标Max：存在某非基变量检验数大于0，且对应当前表中系数列向量元素均小于等于0。2线性规划和单纯性法2.4单纯形法思考与练习题如果目标函数为Min，单纯形表的唯一解、无穷解和无界解如何判断？唯一最优解无穷最优解无界解练习题P55页2.1（3）、P56页2.5和2.8题。目标Max：非基变量检验数，均小于0。目标Min：非基变量检验数，均大于0。目标Max：非基变量检验数，均小于等于0，且至少有一个非基变量的检验数等于0。目标Min：非基变量检验数，均大于等于0，且至少有一个非基变量的检验数等于0。目标Max：存在某非基变量检验数大于0，且对应当前表中系数列向量元素均小于等于0。目标Min：存在某非基变量检验数小于0，且对应当前表中系数列向量元素均小于等于0。2线性规划和单纯性法2.4单纯形法（7）大M和两阶段法2线性规划和单纯性法2.4