管理运筹学电子教案完整版

1管理运筹学管理运筹学2管理运筹学第一章绪论§1§2§3§4决策、定量分析与管理运筹学运筹学的分支运筹学在工商管理中的应用学习管理运筹学必须使用相应的计算机软件，必须注重学以致用的原则3管理运筹学第一章绪论运筹学（OperationalResearch）运筹学直译为“运作研究”，是应用分析、试验、量化的，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优，以实现最有效的管理。运筹学的产生和发展运筹学产生于第二次世界大战，主要用于解决如何在与德军的对抗中最大限度地杀伤敌人、减少损失。二战以后，运筹学得到了快速的发展，形成了许多分支，丹捷格提出的求解线性规划问题的单纯形法是运筹学发展史上最重大的进展之一。而计算机的应用极大地推进了运筹学的普及与应用。运筹学的广泛应用运筹学不仅在军事上，而且在生产、决策、运输、存储等经济管理领域有着广泛的应用。4管理运筹学§1决策、定量分析与管理运筹学决策过程（解决问题的过程）（1）认清问题。（2）找出一些可供选择的方案。（3）确定目标或评估方案的。（4）评估各个方案：解的检验、灵敏性分析等。（5）选出一个最优的方案：决策。（6）执行此方案：回到实践中。（7）进行后评估：考察问题是否得到圆满解决。（1）（2）（3）形成问题。（4）（5）分析问题：定性分析与定量分析，构成决策。5管理运筹学运筹学的分支此外，还有多目标规划、随机规划、模糊规划等。§2线性规划整数线性规划图与网络模型存储论排队论排序与统筹方法决策分析动态规划对策论预测目标规划6管理运筹学§3运筹学在工商管理中的应用生产：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等，追求利润最大化和成本最小化。库存管理：多种物资库存量的管理，某些设备的库存方式、库存量等的确定。运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等。人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等。市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等。财务和会计：预测、贷款、成本分析、定价、证券管理、现金管理等。此外，还有设备维修、更新，项目选择、评价，工程优化与管理等。7管理运筹学§3运筹学在工商管理中的应用由国际运筹与管理科学协会（INFORMS）及其下属的管理科学实践学会（CollegeforthePracticeoftheManagementSciences）主持评定的弗兰茨·厄德曼（FranzEdelman）奖久负盛名，该奖是为奖励运筹学在管理中的应用的卓越成就设立的，该奖每年评选一次，在对大量富有竞争力的入围者进行认真的评审后，一般有六位优胜者获奖。这些获奖项目的文章都会在第二年发表在著名刊物Interface新年第一期上，表1-1列出了发表在该期刊上的部分获奖项目。8管理运筹学§3运筹学在工商管理中的应用表1-1组织应用Interface期刊号每年节支（美元）施乐公司标准品牌公司联合航空公司Citgo石油公司荷马特发展公司（HomartDevelopmentCo.）AT&TMerit青铜制品公司Delta航空公司宝洁公司法国国家铁路公司IBM通过战略调整，缩短维修机器的反应时间和改进维修人员的生产率控制成品库存（制定最优再订购点和订购量，确保安全库存）满足乘客需求前提下，以最低成本进行订票及安排机场工作班次优化炼油程序及产品供应、配送及营销优化商业区和办公楼销售程序优化商业用户的电话销售中心选址安装统计销售预测和成品库存管理系统，改进客户服务进行上千个国内航线的飞机优化配置来实现最大化利润重新设计北美生产和分销系统以降低成本并加快了市场进入速度制定最优铁路时刻表并调整铁路日运营量重组全球供应链，保持最小库存的同时满足客户需求11/1975第二部分12/19811-2/19861-2/19871-2/19871-2/19901-2/19931-2/19941-2/19971-2/19981-2/2000生产率提高50%以上380万600万7000万4000万4.06亿，销售额大幅增加更优质的服务1亿2亿1500万，更多年收入第一年7.5亿9管理运筹学§3运筹学在工商管理中的应用运筹学方法使用情况（美国，1983）图1-110管理运筹学§3运筹学在工商管理中的应用运筹学方法使用情况（中国，1998）图1-211管理运筹学§4学习管理运筹学必须使用相应的计算机软件，必须注重学以致用的原则学习运筹学要结合实际的应用，不要被一些概念、理论的困难吓倒。学习运筹学要把注意力放在“结合实际问题建立运筹学模型”和“解决问题的方案或模型的解”两头，中间的计算过程尽可能让计算机软件去完成。本书附有运筹学教学软件，使用方法简单。学生可以借助它来学好本课程。学习运筹学是为了应用，为了解决实际问题。12管理运筹学§4学习管理运筹学必须使用相应的计算机软件，必须注重学以致用的原则例如，有人要从北京去乌鲁木齐。在一百多年以前，我们应该告诉他如何配备粮草、银两、衣物，如何选购马匹、马车，挑选马夫和保镖，如何根据天气、地理条件和社会诸因素来确定行车路线和行程，更重要的是如何在几个月的行程中处理吃穿住行，应付突发事件等问题；但是现在我们只需要告诉他如何去北京机场和出乌鲁木齐机场，其余的问题交给航空公司和机组人员就行了。完全没有必要为了一次旅行攻读空气动力学、喷气发动机设计和制造、飞行器驾驶手册等。13管理运筹学第二章线性规划的图解法§1§2§3问题的提出图解法图解法的灵敏度分析14管理运筹学第二章线性规划的图解法一些典型的线性规划在管理上的应用合理利用线材问题：如何在保证生产的条件下，下料最少；配料问题：在原料供应量的限制下如何获取最大利润；投资问题：从投资项目中选取方案，使投资回报最大；产品生产计划：合理利用人力、物力、财力等，使获利最大；劳动力安排：用最少的劳动力来满足工作的需要；运输问题：如何制定调运方案，使总运费最小。线性规划的组成目标函数：maxf或minf；约束条件：s.t.(subjectto)，满足于；决策变量：用符号来表示可控制的因素。15管理运筹学§1问题的提出例1.某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，生产单位产品所需的设备台时及A、B两种原材料的消耗以及资源的限制，如表2-1所示。表2-1ⅠⅡ资源限制300台时400kg250kg设备原料A原料B单位产品获利12050元111100元问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？线性规划模型目标函数：max约束条件：s.t.z=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1,x2≥016管理运筹学§1问题的提出建模过程（1）理解要解决的问题，明确在什么条件下，要追求什么目标。（2）定义决策变量（x1，x2，…，xn），每一组值表示一个方案。（3）用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标。（4）用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件。一般形式目标函数：max（min）z=c1x1+c2x2+…+cnxn约束条件：s.t.a11x1+a12x2+…+a1nxn≤（=,≥）b1a21x1+a22x2+…+a2nxn≤（=,≥）b2……am1x1+am2x2+…+amnxn≤（=,≥）bmx1，x2，…，xn≥017管理运筹学§2对于只包含两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细介绍图解法的解题过程图解法例1目标函数：maxz=50x1+100x2约束条件：s.t.（A）（B）（C）（D）（E）x1+x2≤3002x1+x2≤400x2≤250x1≥0x2≥0得到最优解：x1=50，x2=250最优目标值z=2750018§2图解法（1）分别取决策变量x1，x2为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面（如图2-1所示）。图2-1管理运筹学19§2图解法（2）对每个不等式（约束条件），先取其等式在坐标系中作直线，然后确定不等式所决定的半平面（如图2-1所示）。图2-1管理运筹学20§2图解法（3）把五个图合并成一个图，取各约束条件的公共部分（如图2-1（f）所示）。图2-1管理运筹学21§2图解法（4）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A、B、C、D、E是可行域的顶点，有限个约束条件其可行域的顶点也是有限的。图2-2管理运筹学22管理运筹学§2图解法线性规划的标准化内容之一—引入松弛变量（资源的剩余量）例1中引入s1，s2，s3，模型变化为：目标函数：max约束条件：s.t.z=50x1+100x2+0s1+0s2+0s3x1+x2+s1=3002x1+x2+s2=400x2+s3=250x1,x2,s1,s2,s3≥0对于最优解x1=50，x2=250，s1=0，s2=50，s3=0说明：生产50单位Ⅰ产品和250单位Ⅱ产品将消耗完所有可能的设备台时数及原料B，但原料A还剩余50千克。23管理运筹学§2图解法重要结论—如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；—无穷多个最优解。若将例1中的目标函数变为maxz=50x1+50x2，则线段BC上的所有点都代表了最优解；—无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；—无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x2≥1200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。24管理运筹学§2图解法无界解线性规划存在无界解，即无最优解的情况。对下述线性规划问题：目标函数：maxz=x1+x2；约束条件：x1-x2≤1-3x1+2x2≤6x1≥0，x2≥025§2图解法无界解用图解法求解结果，如图2-3所示，可以看到，该问题可行域无界，目标函数值可以无穷大，成为无界解，即无最优解。图2-3管理运筹学26管理运筹学§2图解法进一步讨论例2某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种原料有一定替代性），其中原料A至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨原料A需要2个小时，加工每吨原料B需要1小时，而公司总共有600个加工小时。又知道每吨原料A的价格为2万元，每吨原料B的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？27§2图解法进一步讨论解：目标函数：minf=2x1+3x2管理运筹学约束条件：x1+x2≥350x1≥1252x1+x2≤600x1,x2≥0采用图解法，如图2-4所示，得Q点坐标（250，100）为最优解。图2-428管理运筹学图解法的灵敏度分析§3线性规划的标准化*一般形式目标函数：max（min）z=c1x1+c2x2+…+cnxn约束条件：s.t.a11x1+a12x2+…+a1nxn≤（=,≥）b1a21x1+a22x2+…+a2nxn≤（=,≥）b2……am1x1+am2x2+…+amnxn≤（=,≥）bmx1，x2，…，xn≥0*标准形式目标函数：max约束条件：s.t.z=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2……am1x1+am2x2+…+amnxn=bmx1，x2，…，xn≥0，bi≥029管理运筹学§3图解法的灵敏度分析线性规划的标准形式有四个特点：—目标最大化；—约束为等式；—决策变量均非负；—右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过变换，将其转化为标准形式。30管理运筹学§3图解法的灵敏度分析极小化目标函数的问题设目标函数为：minf=c1x1+c2x2+…+cnxn令z=−f，则该极小化问题与下面的极大化问题有相同的最优解，maxz=−c1x1−c2x2−…−cnxn但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个负号，即minf=−maxz31管理运筹学§3图解法的灵敏度分析约束条件不是等式的问题设约束条件为ai1x1+ai2x2+…+ainxn≤bi，可以引进一个新的变量s，使它等于约束右边与左边之差，s=bi–(ai1x1+ai2x2+…+ainxn)显然，s也具有非负约束，即s≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn+s=bi32管理运筹学§3图解法的灵敏度分析约束条件不是等式的问题当约束条件为ai1x1+ai2x2+…+ainxn≥bi时，类似地，令s=(ai1x1+ai2x2+…+ainxn)−bi显然，s也具有非负约束，即s≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn−s=bi为了使约束由不等式成为等式而引进的变量s，当不等式为“小于等于”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量或剩余变量。33管理运筹学§3图解法的灵敏度分析右端项有负值的问题在标准形式中，要求每一个右端项分量非负。当某一个右端项系数为负时，如bi＜0，则把该等式约束两端同时乘以−1，得到：−ai1x1−ai2x2−…−ainxn=−bi。34管理运筹学§3图解法的灵敏度分析例3．将以下线性规划问题转化为标准形式。mins.t.f=2x1−3x2+4x33x1+4x2−5x3≤62x1+x3≥8x1+x2+x3=−9x1,x2,x3≥0解：首先，将目标函数转换成极大化，令z=−f=−2x1+3x2−4x3其次，考虑约束，有两个不等式约束，引进松弛变量或剩余变量x4，x5≥0。第三个约束条件的右端值为负，在等式两边同时乘−1。35管理运筹学§3图解法的灵敏度分析通过以上变换，可以得到以下标准形式的线性规划问题：maxz=−2x1+3x2−4x3s.t.3x1+4x2−5x3+x4=62x1+x3−x5=8−x1−x2−x3=9x1,x2,x3,x4,x5≥0注：变量无符号限制的问题在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令xj=xj'-xj"其中xj'≥0，xj"≥0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj'和xj"的大小。36管理运筹学§3图解法的灵敏度分析灵敏度分析：在建立数学模型和求得最优解之后，研究线性规划的一个或多个参数（系数）ci,aij,bj变化时，对最优解产生的影响。一、目标函数中的系数ci的灵敏度分析考虑例1的情况，ci的变化只影响目标函数等值线的斜率，目标函数z=50x1+100x2在z=x2（x2=z斜率为0）到z=x1+x2（x2=−x1+z斜率为−1）之间时，原最优解x1=50，x2=100仍是最优解。一般情况：z=c1x1+c2x2写成斜截式x2=−(c1/c2)x1+z/c2目标函数等值线的斜率为−(c1/c2)，当-1≤-(c1/c2)≤0（*）时，原最优解仍是最优解。37管理运筹学§3图解法的灵敏度分析假设产品Ⅱ的利润100元不变，即c2=100，代到式（*）并整理得0≤c1≤100假设产品Ⅰ的利润50元不变，即c1=50，代到式（*）并整理得50≤c2假若产品Ⅰ、Ⅱ的利润均改变，则可直接用式（*）来判断。假设产品Ⅰ、Ⅱ的利润分别为60元、55元，则−2≤−(60/55)≤−1那么，最优解为z=x1+x2和z=2x1+x2的交点x1=100，x2=200。38管理运筹学§3图解法的灵敏度分析二、约束条件中常数项bj的灵敏度分析当约束条件中常数项bj变化时，线性规划的可行域发生变化，可能引起最优解的变化。考虑例1的情况：假设设备台时增加10个台时，即b1变化为310，这时可行域扩大，最优解为x2=250和x1+x2=310的交点x1=60，x2=250。变化后的总利润−变化前的总利润=增加的利润(50×60+100×250)−(50×50+100×250)=500，500/10=50（元）说明在一定范围内每增加（或减少）1个台时的设备能力就可增加（或减少）50元利润，这称为该约束条件的对偶价格。39管理运筹学§3图解法的灵敏度分析假设原料A增加10千克，即b2变化为410，这时可行域扩大，但最优解仍为x2=250和x1+x2=300的交点x1=50，x2=250。此变化对总利润无影响，该约束条件的对偶价格为0。解释：原最优解没有把原料A用尽，有50千克的剩余，因此增加10千克只增加了库存，而不会增加利润。在一定范围内，当约束条件中常数项增加1个单位时，（1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好）；（2）若约束条件的对偶价格小于0，则其最优目标函数值受到影响（变坏）；（3）若约束条件的对偶价格等于0，则其最优目标函数值不变。40管理运筹学第三章线性规划问题的计算机求解§1§2“管理运筹学”软件的操作方法“管理运筹学”软件的输出信息分析41管理运筹学第三章线性规划问题的计算机求解随书软件为“管理运筹学”2.5版（Windows版），是“管理运筹学”2.0版（Windows版）的升级版。它包括：线性规划、运输问题、整数规划（0-1整数规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法，共15个子模块。42管理运筹学§1“管理运筹学”软件的操作方法软件使用演示：（演示例1）第一步：点击“开始”→“程序”→“管理运筹学2.5”，弹出主窗口，如图3-1所示。图3-1例1.目标函数：maxz=50x1+100x2约束条件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1≥0x2≥0（A）（B）（C）（D）（E）43管理运筹学§1“管理运筹学”软件的操作方法第二步：选择所需子模块，点击主窗口中的相应按钮。本题中选用“线性规划”方法，点击按钮弹出如图3-2所示界面：图3-244管理运筹学§1“管理运筹学”软件的操作方法第三步：点击“新建”按钮，输入数据。本题中共有2个变量、3个约束条件、目标函数取MAX。点击“确定”后，在表中输入Cj,bi和aij等值，并确定变量的正负约束。输入数值后的界面如图3-3所示。在输入中要注意以下两点：输入的系数可以是整数、小数，但不能是分数，要把分数先化为小数再输入；输入前先要合并同类项。图3-345管理运筹学§1“管理运筹学”软件的操作方法第四步：点击“解决”按钮，得出计算过程。计算过程界面输出如图3-4所示。图3-446管理运筹学§1“管理运筹学”软件的操作方法第五步：关闭计算过程界面，得出输出结果。本题的运行结果界面如图3-5所示。图3-5在“管理运筹学”2.5版软件中，线性规划问题的结果输出部分增加了线性规划的逐步运算过程，将使读者更容易掌握线性规划计算的全过程，为方便软件计算，本线性规划使用了大M法以及数值分析方法。47管理运筹学§2“管理运筹学”软件的输出信息分析分析软件输出的信息——————上题中目标函数的最优值是27500，x1=50,x2=250。相差值表示相应的决策变量的目标系数需要改进的数量，使得决策变量为正值，当决策变量已为正数时，相差数为零。松弛/剩余变量的数值表示还有多少资源没有被使用。如果为零，则表示与之相对应的资源已经全部使用。对偶价格表示其对应的资源每增加一个单位，将增加多少个单位的最优值。目标函数系数范围表示最优解不变的情况下，目标函数的决策变量系数的变化范围。当前值是指当前的最优解中的系数取值。常数项范围是指约束条件的右端常量。上限值和下限值是指当约束条件的右端常量在此范围内变化时，与其对应的约束条件的对偶价格不变。当前值是指现在的取值。以上计算机输出的目标函数系数和约束条件右端值的灵敏度分析都是在其他系数值不变，只有一个系数变化的基础上得出的。48管理运筹学§2“管理运筹学”软件的输出信息分析当有多个系数变化时，需要进一步讨论。百分之一百法则：对于所有变化的目标函数决策系数（约束条件右端常数值），当其所有允许增加的百分比与允许减少的百分比之和不超过100%时，最优解不变（对偶价格不变，最优解仍是原来几个线性方程的解）。****允许增加量=上限-现在值c1的允许增加量为100-50=50b1的允许增加量为325-300=25允许减少量=现在值-下限c2的允许减少量为100-50=50b3的允许减少量为250-200=50允许增加的百分比=增加量/允许增加量允许减少的百分比=减少量/允许减少量49管理运筹学§2“管理运筹学”软件的输出信息分析例如：c1变为74，c2变为78，则（74-50）/50+（100-78）/50=92%，故最优解不变。b1变为315，b3变为240，则（315-300）/25+（250-240）/50=80%，故对偶价格不变（最优解仍是原来几个线性方程的解）。在使用百分之一百法则进行灵敏度分析时，要注意以下几方面。（1）当允许增加量（允许减少量）为无穷大时，则对任意增加量（减少量），其允许增加（减少）百分比均看作零。（2）百分之一百法则是充分条件，但非必要条件；也就是说超过100%，最优解或对偶价格并不一定变化。（3）百分之一百法则不能用于目标函数决策变量系数和约束条件右边常数值同时变化的情况。这种情况下，只能重新求解。50管理运筹学§2“管理运筹学”软件的输出信息分析下面用“管理运筹学”软件来分析第二章的例2，其数学模型如下。目标函数：f=2x1+3x2min约束条件：s.t.x1+x12x1+x1,x2≥350≥125x2≤600x2≥0图3-6从图3-6可知，当购进原料A250t，原料B100t时，购进成本最低，为800万元。51管理运筹学§2“管理运筹学”软件的输出信息分析在松弛/剩余变量栏中，约束条件2的值为125，它表示对原料A的最低需求，即对A的剩余变量值为125；同理可知约束条件1的剩余变量值为0；约束条件3的松弛变量值为0。在对偶价格栏中，约束条件3的对偶价格为1万元，也就是说如果把加工时数从600小时增加到601小时，则总成本将得到改进，由800万元减少到799万元。也可知约束条件1的对偶条件为-4万元，也就是说如果把购进原料A和B的总量下限从350t增加到351t，那么总成本将增加，由800万元增加到804万元。当然如果减少对原料A和B的总量的下限，那么总成本将得到改进。在常数项范围一栏中，知道当约束条件1的常数项在300到475范围内变化，且其他约束条件不变时，约束条件1的对偶价格不变，仍为-4；当约束条件2的常数项在负无穷到250范围内变化，且其他约束条件的常数项不变时，约束条件2的对偶价格不变，仍为0；当约束条件3的常数项在475到700范围内变化，且其他约束条件的常数项不变时，约束条件3的对偶价格不变，仍为1。52管理运筹学“§2“管理运筹学”软件的输出信息分析注意（1）当约束条件中的常数项增加一个单位时，最优目标函数值增加的数量称为影子价格。在求目标函数最大值时，当约束条件中的常数项增加一个单位时，目标函数值增加的数量就为改进的数量，此时影子价格等于对偶价格；在求目标函数最小值时，改进的数量就是减少的数量，此时影子价格即为负的对偶价格。（2）管理运筹学”软件可以解决含有100个变量50个约束方程的线性规划问题，可以解决工商管理中大量的问题。如果想要解决更大的线性规划问题，可以使用由芝加哥大学的L.E.Schrage开发的LINDO计算机软件包的微型计算机版本LINDO/PC。53管理运筹学第四章线性规划在工商管理中的应用§1§2§3§4§5人力资源分配的问题生产计划的问题套裁下料问题配料问题投资问题54管理运筹学§1人力资源分配的问题例1．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如表4-1所示。表4-1班次时间所需人数1234566：00——10：0010：00——14：0014：00——18：0018：00——22：0022：00——2：002：00——6：00607060502030设司机和乘务人员分别在各时间段一开始时上班，并连续工作8h，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又使配备最少司机和乘务人员的人数最少？55管理运筹学§1人力资源分配的问题解：设xi表示第i班次时开始上班的司机和乘务人员数，这样我们建立如下的数学模型。目标函数：minx1+x2+x3+x4+x5+x6约束条件：s.t.x1+x6≥60x1+x2≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30x1，x2，x3，x4，x5，x6≥0*最优解：x1=50，x2=20，x3=50，x4=0，x5=20，x6=10*一共需要司机和乘务人员150人。56管理运筹学§1人力资源分配的问题例2．一家中型的百货商场对售货员的需求经过统计分析如表4-2所示。为了保证售货员充分休息，要求售货员每周工作五天，休息两天，并要求休息的两天是连续的。问应该如何安排售货员的休息日期，既满足工作需要，又使配备的售货员的人数最少？表4-2时间所需售货员人数星期一星期二星期三星期四星期五星期六星期日1524251931282857管理运筹学§1人力资源分配的问题解：设xi(i=1，2，…，7)表示星期一至星期日开始休息的人数,这样我们建立如下的数学模型。目标函数：minx1+x2+x3+x4+x5+x6+x7约束条件：s.t.x1+x2+x3+x4+x5≥28x2+x3+x4+x5+x6≥15x3+x4+x5+x6+x7≥24x4+x5+x6+x7+x1≥25x5+x6+x7+x1+x2≥19x6+x7+x1+x2+x3≥31x7+x1+x2+x3+x4≥28x1，x2，x3，x4，x5，x6，x7≥0*最优解：x1=12，x2=0，x3=11，x4=5，x5=0，x6=8，x7=0*我们可以配备36个售货员，使目标函数最小。58管理运筹学§1人力资源分配的问题往往一些服务行业的企业对人力资源的需求一周内像例4-2所描述的那样变化，而每天的各时间段的需求又往往像例4-1描述的那样变化，在保证工作人员每天工作8h，每周休息两天的情况下，如何安排能使人员的编制最小呢？59管理运筹学§2生产计划的问题例3．某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，这三种产品都需要经过铸造、机加工和装配三道工序。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表4-3所示。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和外包协作各应多少件？表4-3甲乙丙资源限制80001200010000铸造工时（小时/件）机械加工工时（小时/件）装配工时（小时/件）自产铸件成本（元/件）外协铸件成本（元/件）机械加工成本（元/件）装配成本（元/件）产品售价（元/件）56335232310425612187824--321660管理运筹学§2生产计划的问题解：设x1，x2，x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5分别为由外包协作铸造再由本公司进行机械加工和装配的甲、乙两种产品的件数。每件产品的利润如下：产品甲全部自制的利润产品甲铸造外协，其余自制的利润产品乙全部自制的利润产品乙铸造外协，其余自制的利润产品丙的利润=23-(3+2+3)=15元=23-(5+2+3)=13元=18-(5+1+2)=10元=18-(6+1+2)=9元=16-(4+3+2)=7元可得到xi（i=1,2,3,4,5）的利润分别为15元、10元、7元、13元、9元。61管理运筹学§2生产计划的问题通过以上分析,可建立如下的数学模型。目标函数：max15x1+10x2+7x3+13x4+9x5约束条件：s.t.5x1+10x2+7x3≤80006x1+3x1+4x2+8x3+2x2+2x3+6x4+4x5≤120003x4+2x5≤10000x1,x2,x3,x4,x5≥0*该公司的最大利润为29400元*最优的生产计划为全部由自己生产的产品甲1600件，铸造工序外包而其余工序自行生产的产品乙600件。62管理运筹学§2生产计划的问题例4．永久机械厂生产Ⅰ、Ⅱ、Ⅲ三种产品，均要经过A、B两道工序加工。设有两种规格的设备A1、A2能完成A工序；有三种规格的设备B1、B2、B3能完成B工序。产品Ⅰ可在A、B的任何规格的设备上加工；产品Ⅱ可在工序A的任何一种规格的设备上加工，但对B工序，只能在B1设备上加工；产品Ⅲ只能在A2与B2设备上加工。数据如表4-4所示。问：为使该厂获得最大利润，应如何制定产品加工方案？表4-4设备A1A2Ⅰ57产品单件工时Ⅱ109Ⅲ12设备的有效台时600010000满负荷时的设备费用300321400070004000250783200B1B2B3原料（元/件）售价（元/件）6470.251.2580.352.00110.502.8063管理运筹学§2生产计划的问题解：设xijk表示第i种产品，在第j种工序上的第k种设备上加工的数量。建立如下的数学模型。s.t.5x111+10x211≤6000（设备A1）9x212+12x3128x221+11x3227x112+6x121+4x1227x123≤10000≤4000≤7000≤4000（设备A2）（设备B1）（设备B2）（设备B3）x111+x112-x121-x122-x123=0（Ⅰ产品在A、B工序加工的数量相等）x211+x212-x221=0（Ⅱ产品在A、B工序加工的数量相等）x312-x322=0（Ⅲ产品在A、B工序加工的数量相等）xijk≥0,i=1，2，3；j=1，2；k=1，2，364管理运筹学§2生产计划的问题目标函数为计算利润最大化，利润的计算公式为：利润=[（销售单价−原料单价）×产品件数]之和−（每台时的设备费用×设备实际使用的总台时数）之和。这样得到目标函数：max(1.25−0.25)(x111+x112)+(2−0.35)(x211+x212)+(2.80−0.5)x312–300/6000(5x111+10x211)-321/10000(7x112+9x212+12x312)-250/4000(6x121+8x221)-783/7000(4x122+11x322)-200/4000(7x123).经整理可得：max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4474x122-1.2304x322-0.35x123*该厂的最大利润为1146.6005元。65§3套裁下料问题例5.某工厂要做100套钢架，每套用长为2.9m，2.1m，1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？解：共可设计下列8种下料方案，如表4-5所示。表4-5ⅠⅡⅢⅣⅤⅥⅦⅧ2.92.11.5合计/m料头/m1037.402017.30.10227.20.21207.10.30136.60.81116.50.90306.31.100461.4设x1,x2,x3,x4,x5,x6,x7,x8分别为上面8种方案下料的原材料根数。这样我们建立如下的数学模型。目标函数：minx1+x2+x3+x4+x5+x6+x7+x8约束条件：s.t.x1+2x2+x4+x6≥1002x3+2x4+x5+x6+3x7≥1003x1+x2+2x3+3x4+x6+4x8≥100x1,管x2,理运x3,筹x4,x5,学x6,x7,x8≥066管理运筹学§3套裁下料问题用管理运筹学软件计算得出最优下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。即x1=30;x2=10；x3=0；x4=50；x5=0；x6=x7=x8=0只需90根原材料就可制造出100套钢架。注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。67管理运筹学§3套裁下料问题若可能的下料方案太多，可以先设计出较好的几个下料方案。首先要求每个方案下料后的料头较短；其次方案总体能裁下所有各种规格的圆钢，且不同方案有着不同的各种所需圆钢的比。这样套裁即使不是最优解，也是次优解，也能满足要求并达到省料目的。如我们用前5种下料方案供套裁用，进行建模求解，也可得到上述最优解。68管理运筹学§3套裁下料问题像例5那样在一个给定长度的原料上裁出不同长度的产品，是一个线裁问题；如果在一个一给定形状的面积上，裁出不同形状的产品，这是一个面裁问题，当然类似地还有体裁问题。例5告诉我们用套裁下料的方法解决线裁优化的问题，是否可以推广到面裁、体裁呢。答案是肯定的，我们只要像例5那样，设计出一些较好的下料方案，然后用类似的线性规划模型，即可解决这些问题。69管理运筹学§4例6．某工厂要用三种原料配料问题表4-61、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如表4-6和表4-7所示。问：该厂应如何安排生产，使利润最大？解：设xij表示第i种（甲、乙、丙）产品中原料j的含量。这样我们建立数学模型时，要考虑：表4-7对于甲：x11，x12，x13；对于乙：x21，x22，x23；对于丙：x31，x32，x33；对于原料1：x11，x21，x31；对于原料2：x12，x22，x32；对于原料3：x13，x23，x33；目标函数：利润最大，利润=收入−原料支出约束条件：规格要求4个；供应量限制3个。产品名称甲乙丙规格要求原材料1不少于50%，原材料2不超过25%原材料1不少于25%，原材料2不超过50%不限单价（元/kg）503525原材料名称每天最多供应量11002100360单价（元/kg）65253570管理运筹学§4配料问题利润=总收入-总成本=甲、乙、丙三种产品的销售单价×产品数量−甲、乙、丙使用的原料单价×原料数量。故有：目标函数：max50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33）−65（x11+x21+x31）−25（x12+x22+x32）−35（x13+x23+x33）=−15x11+25x12+15x13−30x21+10x22−40x31−10x33约束条件：从表4-6中可知x11≥0.5（x11+x12+x13）x12≤0.25（x11+x12+x13）x21≥0.25（x21+x22+x23）x22≤0.5（x21+x22+x23）71管理运筹学§4配料问题从表4-7中可知，生产甲、乙、丙的原材料不能超过原材料的供应限额，故有x11+x21+x31≤100x12+x22+x32≤100x13+x23+x33≤6072管理运筹学§4配料问题通过整理，得到以下模型：目标函数：maxz=-15x11+25x12+15x13-30x21+10x22-40x31-10x33约束条件：s.t.0.5x11-0.5x12-0.5x13≥0（原材料1不少于50%）-0.25x11+0.75x12-0.25x13≤0（原材料2不超过25%）0.75x21-0.25x22-0.25x23≥0（原材料1不少于25%）-0.5x21+0.5x22-0.5x23≤0（原材料2不超过50%）x11+x12+x13+x21+x22+x23+x31≤100x32≤100x33≤60（供应量限制）（供应量限制）（供应量限制）xij≥0,（i=1,2,3;j=1,2,3）73管理运筹学§4配料问题例7线性规划的计算机解为x11=100，x12=50，x13=50，其余的xij=0，也就是说每天只生产产品甲200kg，分别需要用第1种原料100kg，第2种原料50kg，第3种原料50kg。74管理运筹学§4配料问题例8汽油混合问题。一种汽油的特性可用两种指标描述，用“辛烷数”来定量描述其点火特性，用“蒸汽压力”来定量描述其挥发性。某炼油厂有1、2、3、4的4种标准汽油，其特性和库存量列于表4-8中，将这四种标准汽油混合，可得到标号为1、2的2种飞机汽油，这两种汽油的性能指标及产量需求列于表4-9中。问应如何根据库存情况适量混合各种标准汽油，既满足飞机汽油的性能指标，又使2号飞机汽油满足需求，并使得1号飞机汽油产量最高？表4-8辛数标准汽油1234烷107.593.087.0108.0蒸汽压力(g/cm2)7.11×10−211.38×10−25.69×10−228.45×10−2库存量(L)380000265200408100130100表4-9飞机汽油辛烷数蒸汽压力(g/cm2)产量需求（L）12不小于91不小于100不大于9.96×10−2不大于9.96×10−2越多越好不少于25000075管理运筹学§4配料问题解：设xij为飞机汽油i中所用标准汽油j的数量(L)。目标函数为飞机汽油1的总产量：x11+x12+x13+x14库存量约束为：x11+x21≤380000x12+x22≤265200x13+x23≤408100x14+x24≤130100产量约束为飞机汽油2的产量：x21+x22+x23+x24≥250000nj=12.85x11−1.42x12+4.27x13−18.49x14≥02.85x21−1.42x22+4.27x23−18.49x24≥0同样可得有关辛烷数的约束条件为：16.5x11+2.0x12−4.0x13+17.0x14≥07.5x21−7.0x22−13.0x23+8.0x24≥0⎜x11+x21⎜⎜x12+x22≤265200⎜x+x≤130100⎜2.85x21−1.42x22+4.27x23−18.49x24≥0⎜16.5x+2x−4x+17x≥0⎜⎜x≥0,(i=1,2;j=1,2,3,4)76管理运筹学§4配料问题综上所述，得该问题的数学模型为：maxx11+x12+x13+x14⎛x21+x22+x23+x24≥250000≤380000⎜⎜x13+x23≤408100⎜1424⎜2.85x11−1.42x12+4.27x13−18.49x14≥0⎜11121314⎜7.5x21−7x22−13x23+8x24≥0⎝ijs.t.77管理运筹学§4配料问题由管理运筹学软件求解得：maxx11+x12+x13+x14=933399.938x11=261966.078x12=265200x13=315672.219x14=90561.688x21=118033.906x22=0x23=92427.758x24=39538.30978管理运筹学§5投资问题例9某部门现有资金200万元，今后五年内考虑给以下的项目投资。项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：第三年年初需要投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：第二年年初需要投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。据测定每次投资1万元的风险指数如右表4-10所示问：表4-10项目ABCD风险指数（次/万元）1345.5（1）应如何确定这些项目每年的投资额，使得第五年年末拥有资金的本利金额最大？（2）应如何确定这些项目每年的投资额，使得第五年年末拥有资金的本利在330万元的基础上总的风险系数最小？79管理运筹学§5投资问题解（1）确定决策变量：连续投资问题设xij（i=1～5，j=1～4）表示第i年初投资于A（j=1）、B（j=2）、C（j=3）、D（j=4）项目的金额。这样我们建立如下的决策变量：x51ABx11x12x21x22x31x32x41x42x33CDx24（2）约束条件第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是x11+x12=200；第二年：B次年末才可收回投资，故第二年年初有资金1.1x11，于是x21+x22+x24=1.1x11；第三年：年初有资金1.1x21+1.25x12，于是x31+x32+x33=1.1x21+1.25x12；第四年：年初有资金1.1x31+1.25x22，于是x41+x42=1.1x31+1.25x22；第五年：年初有资金1.1x41+1.25x32，于是x51=1.1x41+1.25x32；B、C、D的投资限制：xi2≤30(i=1，2，3，4)，x33≤80，x24≤100（3）目标函数及模型①maxz=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+x12=200x21+x22+x24=1.1x11；x31+x32+x33=1.1x21+1.25x12；x41+x42=1.1x31+1.25x22；x51=1.1x41+1.25x32；xi2≤30(i=1，2，3，4)，x33≤80，x24≤100xij≥0(i=1，2，3，4，5；j=1，2，3，4)80管理运筹学§5投资问题②所设变量与问题①相同，目标函数为风险最小，有minf=x11+x21+x31+x41+x51+3(x12+x22+x32+x42)+4x33+5.5x24在问题①的约束条件中加上“第五年末拥有资金本利在330万元”的条件，于是模型如下。minf=(x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24s.t.x11+x12=200x21+x22+x24=1.1x11；x31+x32+x33=1.1x21+1.25x12；x41+x42=1.1x31+1.25x22；x51=1.1x41+1.25x32；xi2≤30(i=1，2，3，4)，x33≤80，x24≤1001.1x51+1.25x42+1.4x33+1.55x24≥330xij≥0（i=1，2，3，4，5；j=1、2、3、4）运用“管理运筹学”软件求得此问题的解为：x5A=33.5，x4B=30，x3C=80，x2D=100，x1A=170，x1B=30，x2A=57，x2B=30，x3A=0，x3B=20.2，x4A=7.5。81管理运筹学第五章单纯形法§1§2§3§4单纯形法的基本思路和原理单纯形法的表格形式求目标函数值最小的线性规划问题的单纯形表解法几种特殊情况82管理运筹学§1单纯形法的基本思路和原理单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是，则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解，直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。一、找出一个初始基本可行解下面通过第二章例1的求解来介绍单纯形法。在加上松弛变量之后我们可得到此线性规划的标准形式。目标函数：max50x1+100x2约束条件：x1+x2+s1=300，2x1+x2+s2=400，x2+s3=250，xi≥0（i=1,2），sj≥0（j=1,2,3）。83管理运筹学⎝⎠§1单纯形法的基本思路和原理它的系数矩阵为：⎛11100⎞,p,p,p,p21010⎜01001⎟其中pj为系数矩阵A第j列的向量。A的秩为3,A的秩m小于此方程组的变量的个数n，为了找到一个初始基本可行解，先介绍以下几个线性规划的基本概念。基：已知A是约束条件的m×n系数矩阵，其秩为m。若B是A中m×m阶非奇异子矩阵（即可逆矩阵），则称B是线性规划问题中的一个基。基向量：基B中的一列即称为一个基向量。基B中共有m个基向量。非基向量：在A中除了基B之外的一列则称之为基B的非基向量。基变量：与基向量pi相应的变量xi叫基变量，基变量有m个。84管理运筹学⎝⎠§1单纯形法的基本思路和原理非基变量：与非基向量pj相应的变量xj叫非基变量，非基变量有n‒m个。由线性代数的知识知道，如果我们在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零，再求解这个m元线性方程组就可得到唯一的解了，这个解我们称之为线性规划的基本解。⎛110⎞100⎜101⎟为零。这时约束方程就变为基变量的约束方程。85管理运筹学§1单纯形法的基本思路和原理x2+s1=300，x2=400，x2+s3=250.求解得到此线性规划的一个基本解：x1=0，x2=400，s1=−100，s2=0，s3=−150由于在这个基本解中s1=−100，s3=−150，不满足该线性规划s1≥0，s3≥0的约束条件，显然不是此线性规划的可行解，一个基本解可以是可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解是否满足非负的条件。我们把满足非负条件的一个基本解叫做基本可行解，并把这样的基叫做可行基。86管理运筹学⎝⎠§1单纯形法的基本思路和原理一般来说判断一个基是否是可行基，只有在求出其基本解以后，当其基本解所有变量的解都大于等于零时，才能断定这个解是基本可行解，这个基是可行基。那么我们能否在求解之前，就找到一个可行基呢？也就是说我们找到的一个基能保证在求解之后得到的解一定是基本可行解呢？由于在线性规划的标准型中要求bj都大于等于零，如果我们能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成（至于各列向量的前后顺序是无关紧要的事）例如：⎛001⎞100⎜010⎟那么显然所求得的基本解一定是基本可行解，这个单位矩阵或由单位矩阵各列向量组成的基一定是可行基。实际上这个基本可行解中的各个变量或等于某个bj或等于零。87管理运筹学⎝⎠§1单纯形法的基本思路和原理在本例题中我们就找到了一个基是单位矩阵。⎛100⎞010⎜001⎟在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成，称之为初始可行基，其相应的基本可行解叫初始基本可行解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基，我们将构造初始可行基。88管理运筹学§1单纯形法的基本思路和原理二、最优性检验所谓最优性检验就是判断已求得的基本可行解是否是最优解。1．最优性检验的依据——检验数σj一般来说目标函数中既包括基变量，又包括非基变量。现在我们要求只用非基变量来表示目标函数，这只要在约束等式中通过移项等处理就可以实现，然后用非基变量的表示式代替目标函数中的基变量，这样目标函数中只含有非基变量了，或者说目标函数中基变量的系数都为零了。此时目标函数中所有变量的系数即为各变量的检验数，把变量xi的检验数记为σi。显然所有基变量的检验数必为零。在本例题中目标函数为50x1+100x2。由于初始可行解中x1，x2为非基变量，所以此目标函数已经用非基变量表示了，不需要再代换出基变量了。这样我们可知σ1=50，σ2=100，σ3=0，σ4=0，σ5=0。89管理运筹学§1单纯形法的基本思路和原理2．最优解判别定理数对于求最大目标函数的问题中，对于某个基本可行解，如果所有检验σj≤0，则这个基本可行解是最优解。下面我们用通俗的说法来解释最优解判别定理。设用非基变量表示的目标函数为如下形式z=z0+∑σjxjj∈J由于所有的xj的取值范围为大于等于零，当所有的σj都小于等于零时，可知∑σjxj是一个小于等于零的数，要使z的值最大，显然∑σjxjj∈Jj∈J只有为零。我们把这些xj取为非基变量（即令这些xj的值为零），所求得的基本可行解就使目标函数值最大为z0。注：对于求目标函数最小值的情况，只需把σj≤0改为σj≥0。90管理运筹学§1单纯形法的基本思路和原理三、基变换通过检验，我们知道这个初始基本可行解不是最优解。下面介绍如何进行基变换，找到一个新的可行基，具体的做