MBA运筹学培训课程

运筹学北京理工大学管理与经济学院吴祈宗教授1

1、绪论

2、线性规划

3、运输问题

4、动态规划

5、图与网络分析

6、排队论

7、教学日历运筹学——目录说明本教学课件是与教材紧密配合使用的，教材为：《运筹学》杨民助编著西安交通大学出版社，2000年6月参考书：《运筹学》清华大学出版社或其他的《运筹学》方面本科教材的相关内容下面所标注的页号，均为本课程教材的页号。例如：p123表示第123页p31-34表示从第31页到第34页2绪论

运筹学（OperationalResearch)直译为“运作研究”运筹学是运用科学的方法（如分析、试验、量化等）来决定如何最佳地运营和设计各种系统的一门学科。运筹学对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。

运筹学有广泛应用（可以自己找一些参考书看）运筹学的产生和发展（可以自己找一些参考书看）3运筹学解决问题的过程1）提出问题：认清问题2）寻求可行方案：建模、求解3）确定评估目标及方案的标准或方法、途径4）评估各个方案：解的检验、灵敏性分析等5）选择最优方案：决策6）方案实施：回到实践中7）后评估：考察问题是否得到完满解决1）2）3）：形成问题；4）5）分析问题：定性分析与定量分析。构成决策。4运筹学的分支线性规划非线性规划整数规划动态规划多目标规划随机规划模糊规划等图与网络理论存储论排队论决策论对策论排序与统筹方法可靠性理论等5运筹学在工商管理中的应用生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等库存管理：多种物资库存量的管理，库存方式、库存量等运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等财务和会计：预测、贷款、成本分析、定价、证券管理、现金管理等***设备维修、更新，项目选择、评价，工程优化设计与管理等6运筹学方法使用情况(美1983)（%）7运筹学方法在中国使用情况(随机抽样)（%）8运筹学的推广应用前景据美劳工局1992年统计预测:

运筹学应用分析人员需求从1990年到2005年的增长百分比预测为73%,增长速度排到各项职业的前三位.结论:运筹学在国内或国外的推广前景是非常广阔的工商企业对运筹学应用和需求是很大的在工商企业推广运筹学方面有大量的工作要做9学习运筹学要把重点放在分析、理解有关的概念、思路上。在自学过程中，应该多向自己提问，如一个方法的实质是什么，为什么这样做，怎么做等。自学时要掌握三个重要环节：1、认真阅读教材和参考资料，以指定教材为主，同时参考其他有关书籍。一般每一本运筹学教材都有自己的特点，但是基本原理、概念都是一致的。注意主从，参考资料会帮助你开阔思路，使学习深入。但是，把时间过多放在参考资料上，会导致思路分散，不利于学好。2、要在理解了基本概念和理论的基础上研究例题，注意例题是为了帮助你理解概念、理论的。作业练习的主要作用也是这样，它同时还有让你自己检查自己学习的作用。因此，做题要有信心，要独立完成，不要怕出错。因为，整个课程是一个整体，各节内容有内在联系，只要学到一定程度，知识融会贯通起来，你做题的正确性自己就有判断。3、要学会做学习小结。每一节或一章学完后，必须学会用精炼的语言来该书所学内容。这样，你才能够从较高的角度来看问题，更深刻的理解有关知识和内容。这就称作“把书读薄”，若能够结合自己参考大量文献后的深入理解，把相关知识从更深入、广泛的角度进行论述，则称之为“把书读厚”在建数学模型时要结合实际应用，要学会用计算机软件解决问题。如何学习运筹学课程返回目录10各章节节的重重点、、难点点及及注意意事项项111、线线性性规规划划线性规规划模模型：：目标函函数：：Maxz=50x1+100x2约束条条件：：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0**看看p7--9例例1-1，1-2例1.某工厂厂在计计划期期内要要安排排甲、、乙两两种产产品的的生产产，已已知生生产单单位产产品所所需的的设备备台时时及A、B两种种原材材料的的消耗耗以及及资源源的限限制，，如下下表：：问题：：工厂厂应分分别生生产多多少单单位甲甲、乙乙产品品才能能使工工厂获获利最最多？？121、线线性性规规划划（（续续1.1））1.1线线性规规划的的概念念线性规规划的的组成成：目标函函数Maxf或或Minf约束条条件s.t.(subjectto)满满足足于决策变变量用用符符号来来表示示可控控制的的因素素一般形形式(p10--p11)目标函函数：：Max（（Min））z=c1x1+c2x2+……+cnxn约束条条件：：s.t.a11x1+a12x2+……+a1nxn≤（（=,≥≥））b1a21x1+a22x2+……+a2nxn≤（（=,≥≥））b2………………am1x1+am2x2+……+amnxn≤（（=,≥≥））bmx1，x2，…，，xn≥0标准形形式(p11--p15，，例1-3)目标标函函数数：：Maxz=c1x1+c2x2+……+cnxn约束束条条件件：：s.t.a11x1+a12x2+……+a1nxn=b1a21x1+a22x2+……+a2nxn=b2…………………am1x1+am2x2+……+amnxn=bmx1，x2，……，，xn≥0**练练习习：：p68--70习习题题11-1，，1-2131、、线线性性规规划划（（续续1.2））1.2线线性性规规划划问问题题解解的的概概念念及及性性质质熟悉悉下下列列一一些些解解的的概概念念（（p15--16））可行行解解、、可可行行解解集集（（可可行行域域）），，最最优优解解、、最最优优值值，，基基、、基基变变量量、、非非基基变变量量，，基基本本解解、、基基本本可可行行解解，，可可行行基基、、最最优优基基。。图解解方方法法及及各各有有关关概概念念的的意意义义（（p16--20））看：：图图解解法法步步骤骤，，例例1-4，，1-5，，1-6，，1-7，，1-8，，1-9下一一页页是是一一个个图图解解法法解解题题的的一一个个例例子子，，右右图图中中的的阴阴影影部部分分为为可可行行域域。。单纯纯形形法法的的理理论论基基础础（（p20--30））1.2.3段段要要求求看看懂懂，，了了解解如如何何直直接接通通过过对对约约束束矩矩阵阵的的分分析析求求出出基基本本可可行行解解1.2.4,1.2.5两两段段应应注注重重结结论论的的了了解解，，如如单单纯纯形形法法思思想想和和关关于于线线性性规规划划解解的的四四个个定理理，，而而对对证证明明过过程程则则可可根根据据自自己己的的数数学学基基础础来来掌掌握握：：基础础很很好好，，可可要要求求掌掌握握；；否否则则，，也也可可略略去去不不看看。。**习习题题：：p70习习题题11-3，，1-4141、、线线性性规规划划（（续续1.2））例1.目标标函函数数：：Maxz=50x1+100x2约束束条条件件：：s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到到最最优优解解：：x1=50，，x2=250最优优目目标标值值z=27500151、、线线性性规规划划（（续续1.3））1.3单单纯纯形形法法利用用单单纯纯形形表表的的方方法法求求解解线线性性规规划划————重重点点(p30--451.3.1,1.3.2,1.3.3)此项项内内容容是是本本章章的的重重点点，，学学习习中中应应注注意意掌掌握握表表格格单单纯纯形形法法求求解解线线性性规规划划问问题题的的基基本本过过程程。。要要通通过过读读懂懂教教材材内内容容以以及及大大量量练练习习来来掌掌握握。。161、线线性规规划划（续续1.3）表格单纯纯形法(p40--p45)考虑：bi>0i=1,……,mMaxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2………………am1x1+am2x2+…+amnxn≤bmx1，x2，…，，xn≥0加入松弛弛变量：：Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+xn+2=b2………………am1x1+am2x2+…+amnxn+xn+m=bmx1，x2，…，，xn，xn+1，…，，xn+m≥017显然，xj=0j=1,……,n;xn+i=bii=1,…,m是基本可可行解对应的基基是单位位矩阵。。以下是初初始单纯纯形表：：mm其中：f=-∑cn+ibij=cj-∑cn+iaij为检验数数cn+i=0i=1,…,mi=1i=1an+i,i=1,an+i,j=0(j≠i)i,j=1,……,m1、线线性规规划划（续续1.3）181、线线性规规划划（续续1.3单纯形形法解题题例）例1。化化标准形形式：Maxz=50x1+100x2s.t.x1+x2+x3=3002x1+x2+x4=400x2+x5=250x1,x2,x3,x4,x5≥0最优解x1=50x2=250x4=50（松松弛标量量，表示示原料A有50个单位位的剩余余）19注意：单单纯形法法中，1、每一一步运算算只能用用矩阵初初等行变变换；2、表中中第3列列的数总总应保持持非负（（≥0）；3、当所所有检验验数均非非正（≤≤0））时，得得到最优优单纯形形表。1、线线性规规划划（续续1.3）201、线线性规规划划（续续1.3）一般情况况的处理理及注意意事项的的强调（（p45--55）1.3.4段主主要是讨讨论初始始基本可可行解不不明显时时，常用用的方法法。要弄弄清它的的原理，，并通过过例1-14~例例1-17掌握握这些方方法，同同时进一一步熟悉悉用单纯纯形法解解题。考虑一般般问题：：bi>0i=1,……,mMaxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2………………am1x1+am2x2+…+amnxn=bmx1，x2，…，，xn≥0211、线线性规规划划（续续1.3）大M法：：引入人工工变量xn+i≥0i=1,…,m;充充分分大正数数M。。得得到到，Maxz=c1x1+c2x2+…+cnxn+Mxn+1+…+Mxn+ms.t.a11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+xn+2=b2………………am1x1+am2x2+…+amnxn+xn+m=bmx1，x2，…，，xn，xn+1，…，，xn+m≥0显然，xj=0j=1,……,n;xn+i=bii=1,……,m是基本可可行解对应的基基是单位位矩阵。。结论：若若得到的的最优解解满足xn+i=0i=1,…,m则是原问问题的最最优解；；否则，，原问题题无可行行解。221、线线性规规划划（续续1.3）两阶段法法：引入人工工变量xn+i≥0，，i=1,……,m；构构造，Maxz=-xn+1-xn+2-…-xn+ms.t.a11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+xn+2=b2………………am1x1+am2x2+……+amnxn+xn+m=bmx1，x2，…，，xn，xn+1，…，，xn+m≥0第一阶阶段求求解上上述问问题：：显然，，xj=0j=1,……,n;xn+i=bii=1,……,m是基本本可行行解对应的的基是是单位位矩阵阵。结论：：若得得到的的最优优解满满足xn+i=0i=1,……,m则是原原问题题的基基本可可行解解；否否则，，原问问题无无可行行解。。得到原原问题题的基基本可可行解解后，，第二二阶段段求解解原问问题。。231、线线性性规规划划（（续续1.3））例题题例：（（LP）Maxz=5x1+2x2+3x3-x4s.t.x1+2x2+3x3=152x1+x2+5x3=20x1+2x2+4x3+x4=26x1,x2,x3,x4≥0大M法法问题题（LP-M））Maxz=5x1+2x2+3x3-x4-Mx5-Mx6s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x6≥0两阶段段法：：第第一阶阶段问问题（（LP-1）Maxz=-x5-x6s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x6≥0241、线线性性规规划划（（续续1.3））大M法例例大M法（LP-M）得到最优解解：(25/3，10/3，，0，11)T最优目标值值：112/3251、线性性规划划（续续1.3））两阶段法法例第一阶段（LP-1）得到原问题题的基本可可行解：(0，15/7，25/7，，52/7)T261、线性性规划划（续续1.3））两阶段法法例第二阶段把基本可行行解填入表表中得到原问题题的最优解解：(25/3，10/3，，0，11)T最优目标值值：112/3271、线性性规划划（续续1.3））1.3.5矩矩阵描述———此段段为选读，，有困难者者可不看。。1.3.6段段单纯形迭迭代过程中中的几点注注意事项是是对有关内内容的强调调和补充，，要认真学学习、理解解。**习题：：p70--71习习题11-5，1-6281.4线线性性规划应用用——建建模（p55--68）本节介绍了了些线性规规划应用的的例子，这这些例子从从多个方面面介绍建模模对未来是是很有用的的，应认真真对待。除了教材上上的例子之之外，还有有许多其它它应用：*合理利利用线材问问题：如何何下料使用用材最少*配料问问题：在原原料供应量量的限制下下如何获取取最大利润润*投资问问题：从投投资项目中中选取方案案，使投资资回报最大大*产品生生产计划：：合理利用用人力、物物力、财力力等，使获获利最大*劳动力力安排：用用最少的劳劳动力来满满足工作的的需要*运输问问题：如何何制定调运运方案，使使总运费最最小**下面是是一些建模模的例子，，有兴趣者者，可作为为练习。这这些例子有有一定的难难度，做起起来会有一一些困难。。**习题：：p72--73习习题11-7，1-8，1-9，1-101、线性性规划划（续续1.4））返回目录29例．某昼夜夜服务的公公交线路每每天各时间间段内所需需司机和乘乘务人员数数如下：设司机和乘乘务人员分分别在各时时间段一开开始时上班班，并连续续工作八小小时，问该该公交线路路怎样安排排司机和乘乘务人员，，既能满足足工作需要要，又配备备最少司机机和乘务人人员?例：人力资资源分配的的问题30解：设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例：人力资资源分配的的问题（续续）31例、明明兴公司生生产甲、乙乙、丙三种种产品，都都需要经过过铸造、机机加工和装装配三个车车间。甲、、乙两种产产品的铸件件可以外包包协作，亦亦可以自行行生产，但但产品丙必必须本厂铸铸造才能保保证质量。。数据如下下表。问：：公司为了了获得最大大利润，甲甲、乙、丙丙三种产品品各生产多多少件？甲甲、乙两种种产品的铸铸造中，由由本公司铸铸造和由外外包协作各各应多少件件？例：生产计计划的问题题32解：设x1,x2,x3分别为三道道工序都由由本公司加加工的甲、、乙、丙三三种产品的的件数，x4,x5分别为由外外协铸造再再由本公司司机加工和和装配的甲甲、乙两种种产品的件件数。求xi的利润：利利润=售售价-各成本本之和可得到xi（i=1,2,3,4,5））的利润分分别为15、10、、7、13、9元。。这样我们建建立如下的的数学模型型。目标函数：：Max15x1+10x2+7x3+13x4+9x5约束条件：：s.t.5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0例：生产计计划的问题题（续）33例、永久久机械厂生生产Ⅰ、ⅡⅡ、Ⅲ三种种产品，均均要经过A、B两两道工序加加工。假设设有两种规规格的设备备A1、A2能完成A工序；；有三种规规格的设备备B1、B2、B3能完成B工工序。Ⅰ可可在A、B的的任何规格的的设备上加工工；Ⅱ可在在任意规格的的A设备上加加工，但对B工序，只能能在B1设备上加工；；Ⅲ只能在A2与B2设备上加工；；数据如下表表。问：为使使该厂获得最最大利润，应应如何制定产产品加工方案案？例：生产计划划的问题（续续）34解：设xijk表示第i种种产品，在在第j种种工序上的第第k种设设备上加工的的数量。利润=[（销售单价价-原料料单价）*产产品件数]之和-（（每台时的的设备费用*设备实际使使用的总台时时数）之和。。这样我们建立立如下的数学学模型:Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123s.t.5x111+10x211≤6000（（设备A1）7x112+9x212+12x312≤10000（（设备A2）6x121+8x221≤4000（（设备B1）4x122+11x322≤7000（（设备B2）7x123≤4000（（设备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,3例：生产计划划的问题（续续）35例、某工厂要要做100套套钢架，每套套用长为2.9m,2.1m,1.5m的圆钢各一一根。已知原原料每根长7.4m，，问：应如何何下料，可使使所用原料最最省？解：设计计下列5种种下料方案案假设x1,x2,x3,x4,x5分别为上面前前5种方方案下料的原原材料根数。。这样我们建建立如下的数数学模型。目标函数：Minx1+x2+x3+x4+x5约束条件：s.t.x1+2x2+x4≥1002x3+2x4+x5≥1003x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥0例：套裁下料料问题36例6．某工厂厂要用三种原原料1、2、、3混合调配配出三种不同例：配料问题题37例：配料问题题（续）解：设xij表示第i种种（甲、对于甲：x11，x12，x13；对于乙：x21，x22，x23；对于丙：x31，x32，x33；对于原料1：x11，x21，x31；对于原料2：x12，x22，x32；对于原料3：x13，x23，x33；目标函数：利润最大，利润=收入-原料支出约束条件：规格要求4个；供应量限制3个。38Maxz=-15x11+25x12+15x13-30x21+10x22-40x31-10x33s.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+x21+x31≤100(供应应量限制）x12+x22+x32≤100(供应应量限制）x13+x23+x33≤60(供应应量限制）xij≥0,i=1,2,3;j=1,2,3例：配料问题题（续）39例8．某部门门现有资金200万元，，今后五年内内考虑给以下下的项目投资资。已知：项项目A：从第一一年到第五年年每年年初都都可投资，当当年末能收回回本利110%；项目B：从第一年到第四年年每年年初都都可投资，次次年末能收回回本利125%，但规定定每年最大投投资额不能超过30万元；项目目C：需在第第三年年初投投资，第五年年末能收回本本利140%，但规定最大投资额额不能超过80万元；项项目D：需在在第二年年利155%，但规定最大投资额不能超过100万元；据测定每万元每次投资的风险指数如右表：问：a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？解：1）确定决策变量量：连续投资资问题设xij(i=1-5，j=1、2、3、4)表示示第i年年初投资于A(j=1)、B(j=2)、C(j=3)、、D(j=4)项目的金金额。这样我我们建立如下下的决策变量量：Ax11x21x31x41x51Bx12x22x32x42Cx33Dx24例：投资问题题402）约束条件件：第一年：A当当年末可收回回投资，故第第一年年初应应把全部资金金投出去，于于是x11+x12=200；；第二年：B次次当年末才可可收回投资故第三年：年初的资金为x21+x12，于是x31+x32+x33=1.1x21+1.25x12；第四年：年初的资金为x31+x22，于是x41+x42=1.1x31+1.25x22；第五年：年初的资金为x41+x32，于是x51=1.1x41+1.25x32；B、C、D的投资限制：xi2≤30(I=1、2、3、4)，x33≤80，x24≤1003）目标函数及模型：a)Maxz=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+x12=200

x21+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≤100

xij≥0(i=1、2、3、4、5；j=1、2、3、4）

b)Minf=(x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24s.t.x11+x12=200

x21+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≥330

xij≥0(i=1、2、3、4、5；j=1、2、3、4）例：投资问题题（续）412、线性规划划问题的进一一步研究（2.1）2.1对对偶原理1、对偶问题题：考虑前文例1若设备和原料料都用于外协协加工，工厂厂收取加工费费。试问：设设备工时和原原料A、B各各如何收费费才最有竞争争力？设y1，y2，y3分别为每设备备工时、原料A、B每单位的收收取费用Maxz=50x1+100x2Minf=300y1+400y2+250y3s.t.x1+x2≤300s.t.y1+2y2+≥502x1+x2≤400（不少于甲产产品的利润））x2≤250y1+y2+y3≥100x1,x2≥0y1,y2,y3≥0422、对偶定义义对称形式：互互为对偶(LP)Maxz=cTx(DP)Minf=bTys.t.Ax≤≤bs.t.ATy≥cx≥0y≥0“Max--≤””““Min--≥”一般形式：若一个问题的的某约束为等等式，那么对对应的对偶问问题的相应变变量无非负限限制；反之，，若一个问问题的某变量量无非负限制制，那么对应应的对偶问题题的相应约束束为等式。2、线性规划划问题的进一一步研究（2.1）433、对偶定理理（原问题题与对偶问题题解的关系））考虑（LP））和（DP））定理2-1（（弱对偶定定理）若x,y分分别为（LP）和（DP）的可行解解，那么cTx≤bTy。推论若（LP）可行，，那么（LP）无有限最最优解的充分分必要条件是是（LD）无无可行解。定理2-2（（最优性准准则定理）若若x,y分别为（（LP）和（（DP）的可可行解，且cTx=bTy，那么x,y分分别为（LP）和（DP）的最优解解。定理2-3（（主对偶定定理）若（LP）和（DP）均可行行，那么（LP）和（DP）均有最最优解，且最最优值相等。。以上定理、推推论对任意形形式的相应线线性规划的对对偶均有效**习题：p99习习题22-12、线性规划划问题的进一一步研究（2.1）444、影影子价价格——是是一一个向向量，，它的的分量量表示示最优优目标标值随随相应应资源源数量量变化化的变变化率率。若x*,y*分别为为（LP））和（（DP）的的最优优解，，那么，，cTx*=bTy*。根据f=bTy*=b1y1*+b2y2*++bmym*可知f/bi=yi*yi*表示bi变化1个单单位对对目标标f产产生的的影响响，称称yi*为bi的影子子价格格。注意：：若B是是最最优基基，y*=(BT)-1cB为影子子价格格向量量。2、线线性规规划问问题的的进一一步研研究（（2.1））455、由由最优优单纯纯形表表求对对偶问问题最最优解解第1章章例1。化化标准准形式式：Maxz=50x1+100x2s.t.x1+x2+x3=300，，2x1+x2+x4=400x2+x5=250，，x1,x2,x3,x4,x5≥0IOB=(p1,p4,p2)(BT)-1cBB-1最优解解x1=50x2=250x4=50（松松弛标标量，，表示示原料料A有有50个单单位的的剩余余）影子价价格y1=50y2=0y3=50,B-1对应的的检验验数(BT)-1cB。2、线线性规规划问问题的的进一一步研研究（（2.1））462.2对对偶偶单纯纯形法法对偶单单纯形形法在在什么么情况况下使使用：：应用前前提：：有一一个基基，其其对应应的基基本解解满足足①单单纯形形表的的检验验数行行全部部非正正（对对偶可可行））；②变变量取取值可可有负负数（（非可可行解解）。。**注注：通通过矩矩阵行行变换换运算算，使使所有有相应应变量量取值值均为为非负负数即即得到到最优优单纯纯性表表。2、线线性规规划问问题的的进一一步研研究（（2.2））472、线线性规规划问问题的的进一一步研研究（（2.2））对偶单单纯形形法求求解线线性规规划问问题过过程：：1、建建立初初始对对偶单单纯形形表，，对应应一个个基本本解，，所有有检验验数均均非正正，转转2；；2、若若b’’≥0，，则得得到最最优解解，停停止；；否则则，若若有bk<0则则选k行行的的基变变量为为出基基变量量，转转3；；3、若若所有有akj’≥0(j=1,2,……,n)，则则原问问题无无可行行解，，停止止；否否则，，若有有akj’<0则则选=min{j’/akj’┃akj’<0}=r’/akr’那么么r为为进基基变量量，转转4；；4、以以akr’为转转轴元元，作作矩阵阵行变变换使使其变变为1，，该列列其他他元变变为0，，转2。48例：求解线线性规规划问问题：：Minf=2x1+3x2+4x3S.t.x1+2x2+x3≥32x1-x2+x3≥4x1,x2,x3≥0标准化化：MaxZ=-2x1-3x2-4x3S.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥02、线线性规规划问问题的的进一一步研研究（（2.2））49表格对对偶单单纯形形法**习习题：：p100习习题22-2，2-32、线线性规规划问问题的的进一一步研研究（（2.2））502.3灵灵敏度度分析析进一步步理解解最优优单纯纯形表表中各各元素素的含含义考虑问问题Maxz=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn≤b1a21x1+a22x2+……+a2nxn≤b2………………am1x1+am2x2+……+amnxn≤bmx1，x2，…，，xn≥0引入m个个松松弛变变量后后，通通过计计算得得到最最优单单纯形形表。。应-1-1能够找找到最最优基基B的逆逆矩阵阵B，，以以及BN，检检验数数等。。2、线线性规规划问问题的的进一一步研研究（（2.3））512、线线性规规划问问题的的进一一步研研究（（2.3））最优单单纯形形表B-1(BT)-1cBIO52价值系系数C发生生变化化：m考虑检验数数j=cj-∑criarijj=1,2,……,ni=11、若ck是非基变量量的系数：：设ck变化为ck+ckk’=ck+ck-∑criarik=k+ck只要k’≤0，，即ck≤-k，则最优解不不变；否则则，将最优优单纯形表表中的检验验数k用k’取代，继续续单纯形法法的表格计计算。例:MaxZ=-2x1-3x2-4x3S.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥02、线性规规划问题的的进一步研研究（2.3）53例：最优单单纯形表从表中看到到σ3=C3+ΔC3-（C2*a13+C1*a23）可得到ΔΔC3≤9/5时时，原最优优解不变。。2、线性规规划问题的的进一步研研究（2.3）542、若cs是基变量的的系数：设设cs变化为cs+cs，那么j’=cj-∑criarij-(cs+cs)asj=j-csasj，对所有非非基变量i≠s只要对所有有非基变量量j’≤0，，即j≤csasj，则最优解不不变；否则则，将最优优单纯形表表中的检验验数j用j’取代，继续续单纯形法法的表格计计算。Max{j/asjasj>0}≤cs≤Min{j/asjasj<0}例:MaxZ=2x1+3x2+0x3+0x4+0x5S.t.x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,x3,x4,x5≥02、线性规规划问题的的进一步研研究（2.3）55例、下表为为最优单纯纯形表，考考虑基变量量系数c2发生变化从表中看到到σj=Cj-（C1*a1j+C5*a5j+（C2+ΔC2）*a2j）j=3、、4可得到-3≤≤ΔC2≤1时时，原原最优解不不变。2、线性规规划问题的的进一步研研究（2.3）56右端项b发生变变化设分量br变化为br+br，根据第1章的讨论论，最优解解的基变量量xB=B-1b，那么只只要保持B-1(b+b)≥0，则最最优基不变变，即基变变量保持，，只有值的的变化；否否则，需要要利用对偶偶单纯形法法继续计算算。对于问题(LP)Maxz=cTxs.t.Ax≤bx≥0最优单纯形形表中含有有B-1=（aij）i=1,……,m;j=n+1,……,n+m那么，新的的xi=(B-1b)i+brairi=1,…,m。。由此可得得，最优基基不变的条条件是Max{-bi/airair>0}≤br≤Min{-bi/airair<0}2、线性规规划问题的的进一步研研究（2.3）57例、上例最最优单纯形形表如下00.250这里B-1=-20.51各各列分别别对应b1、b2、b3的单一0.5-0.1250变化。因此此，设b1增加4，，则x1,x5,x2分别变为：：4+0*4=4，4+(-2)*4=-4<0，，2+0.5*4=4用对偶单纯纯形法进一一步求解，，可得：x*=(4,3,2,0,0)Tf*=172、线性规规划问题的的进一步研研究（2.3）58增加一个变变量增加变量xn+1则有相应的的pn+1，cn+1。那么，计计算出B-1pn+1n+1=cn+1-∑criarin+1填入最优单单纯形表，，若n+1≤0则最优解不不变；否则则，进一步步用单纯形形法求解。。例、前例增增加x6，p6=(2,6,3)T，c6=5。。计算得到到2、线性规规划问题的的进一步研研究（2.3）用单纯形法法进一步求求解，可得得：x*=(1,1.5,0,0,0,2)Tf*=16.559增加一个约约束增加约束一一个之后，，应把最优优解带入新新的约束，，若满足则则最优解不不变，否则则填入最优优单纯形表表作为新的的一行，引引入1个新新的非负变变量（原约约束若是小小于等于形形式可引入入非负松弛弛变量，否否则引入非非负人工变变量），并并通过矩阵阵行变换把把对应基变变量的元素素变为0，，进一步用用单纯形法法或对偶单单纯形法求求解。例、前例增增加3x1+2x2≤15，原原最优解不不满足这个个约束。于于是2、线性规规划问题的的进一步研研究（2.3）60A中元素发发生变化（只讨论N中某某一列变化化情况）与增加变量量xn+1的情况类似似，假设pj变化。那那么，重新新计算出B-1pjj=cj-∑criarij填入最优单单纯形表，，若j≤0则最优解不不变；否则则，进一步步用单纯形形法求解。。2、线性规规划问题的的进一步研研究（2.3）可得最优解解：x*=(3.2,0.8,0,0,2.4)Tf*=15.2612、线性规规划问题的的进一步研研究（2.3）2.3灵灵敏度分分析(内内容，为重重点)2.3.1Ci发生变化2.3.2Bj发生变化2.3.3增增加一个变变量2.3.4增增加一个约约束2.3.5A中元素发发生变化**习题：：p100习习题22-4返回目录623.1运运输问问题模型与与性质运输模型例、某公司从两两个产地A1、A2将物品运往往三个销地地B1、B2、B3，各产地的的产量、各各销地的销销量和各产产地运往个个销地每件件物品的运运费如下表表所示，问问：应如何何调运可使使总运输费费用最小？？3、运输输问问题（（3.1）63解：产销平衡衡问题：：总产产量=总销销量设xij为从产地地Ai运往销地地Bj的运输量量，得到到下列运运输量表表：Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1、、2；j=1、2、3））3、运输输问问题（（3.1）64系数矩阵阵111000000111100100010010001001特点：1、共有m+n行，分别别表示产地和和销地；mn列分别表示示各变量；2、每列只有有两个1，，其余为0，分别表示示只有一个产产地和一个销销地被使用；；3、运输问问题（3.1）65设xij为从产地Ai运往销地Bj的运输量，得得到下列一般般运输量问题题的模型：mnMinf=cijxiji=1j=ins.t.xij=sii=1,2,…,mj=1mxij=djj=1,2,…,ni=1xij≥0(i=1,2,……,m;j=1,2,…,n)一般运输模型型：产销平衡A1、A2、…、Am表示某物资的的m个产地；；B1、B2、…、Bn表示某物质的的n个销地；；si表示产地Ai的产量；dj表示销地Bj的销量；cij表示把物资为为从产地Ai运往销地Bj的单位运价。。3、运输问问题（3.1续）663、运输问问题（3.1续）变化：1）有时目标标函数求最大大，如求利润润最大或营业业额最大等；；2）当某些运运输线路上的的能力有限制制时，模型中中可直接加入入（等式或不不等式）约束束；3）产销不平673、运输问问题（求解思路是基本可行解最优否结束否换基运输问题基变变量的特点*运输问问题的基变量量共有m+n-1个，A的秩为m+n-1。*运输问问题的m+n-1个变量量构成基变量量的充分必要要条件是不含含闭回路。要弄清下列概概念：闭回回路、闭回路路的顶点。683.2运运输问题的表表上作业法——本章重重点1、初始基本本可行解的确确定：（1）西北角角法：从西北角（左左上角）格开开始，在格内内的右下角标标上允许取得的最大数。然然后按行（列列）标下一格格的数。若某某行（列）的的产量（销量量）已满足，，则把该行（（列）的其他他格划去。如如此进行下去去，直至得到到一个基本可可行解。（2）最小元元素法：从运价最小的的格开始，在在格内的右下下角标上允许取得的最大数。然然后按运价从从小到大顺序序填数。若某某行（列）的的产量（销量量）已满足，，则把该行（（列）的其他他格划去。如如此进行下去去，直至得到到一个基本可可行解。注：应用西北角法法和最小元素素法，每次填填完数，都只只划去一行或或一列，只有有最后一个元元例外（同时时划去一行和和一列）。当当填上一个数数后行、列同同时饱和时，，也应任意划划去一行（列列）在保留的的列（行）任任意没被划去去的格内标一一个0。3、运输问问题（3.2）69*3、运输问问题（3.2）70*3、运输问712、最优性检检验：因为求最小，，当所有检验验数均大于等等于0时为最最优解（1）位势法法求检验数：：位势：设对应基变量量xij的m+n-1个ij，存在ui,vj满足ui+vj=cij，i=1,…,m;j=1,…,n.称称这些ui,vj为该基本可行行解对应的位位势。由于有m+n个个变量（ui,vj），m+n-1个方程（（基变量个数数），故有一一个自由变量量，位势不唯唯一。利用位势求检检验数：ij=cij-ui-vji=1,…,m;j=1,…,n3、运输问问题（3.2）72前例，位势法法求检验数：：step1从任意基变量量对应的cij开始，任取ui或vj，然后利用公公式cij=ui+vj依次找出m+n个个ui,vj；从c14=10开开始step2计算非基变量量的检验数ij=cij-ui-vj；填入圆圈内3、运输问问题（3.2）733、主元变换换：（1）选负检检验数中最小小者rk，那么xrk为主元，作为为进基变量；；（上页图中x24）（2）以为xrk起点找一条闭闭回路，除xrk外其余顶点必必须为基变量量格；（上页图中蓝蓝色回路））（3）为闭回回路的每一个个顶点标号，，xrk为1，沿一一个方向依次次给各顶点标标号；（4）求=min{xijxij对应闭回路上上的偶数标号号格}=xpq那么确确定xpq为出基基变量量，为调整整量；；（5））对闭闭回路路的各各奇标标号顶顶点xij+，对各各偶标标号顶顶点xij-，特别别xpq-=0，变为为非基基变量量；3、运运输输问问题题（3.2）重复2、3步，，直到到所有有检验验数均均非负负，得得到最最优解解。74主元变变换：：由前面面得到到=1，于是是3、运运输输问问题题（3.2）ij≥0，得得到最最优解解x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其其余余xij=0;最优费费用：：f*=3*5+10*2+1*3+8*1+4*6+5*3=85**习习题：：p123习习题33-1,3-2753.3产产销销不平平衡的的运输输问题题1、产产量大大于销销量例例、、某公司司从两两个产产地A1、A2将物品品运往往三个个销地地B1、B2、B3，各产产地的的产量量、各各销地地的销销量和和各产产地运运往个个销地地每件件物品品的运运费如如下表表所示示，问问：应应如何何调运运可使使总运运输费费用最最小？？解：增加加一个个虚设设的销销地运运输费费用为为03、运运输输问问题题（3.3）762、销销量大大于产产量例、某公司司从两两个产产地A1、A2将物品品运往往三个个销地地B1、B2、B3，各产产地的的产量量、各各销地地的销销量和和各产产地运运往个个销地地每件件物品品的运运费如如下表表所示示，问问：应应如何何调运运可使使总运运输费费用最最小？？解：增加加一个个虚设设的产产地运运输费费用为为03、运运输输问问题题（3.3）77下面给给出一一些例例题，，可作作为建建模的的练习习：例、石家庄庄北方方研究究院有有一、、二、、三，，三个个区。。每年年分别别需要要用煤煤3000、1000、、2000吨，，由河河北临临城、、山西西盂县县两处处煤矿矿负责责供应应，价价格、、质量量相同同。供供应能能力分分别为为1500、4000吨吨，运运价如如下表表。由由于需需大于于供，，经院院研究究决定定一区区供应应量可可减少少0--200吨，，二区区必须须满足足需求求量，，三区区供应应量不不少于于1700吨，，试求求总费费用为为最低低的调调运方方案。。3、运运输输问问题题（例例题））78解：根据题题意，，作出出产销销平衡衡与运运价表表：取M代代表一一个很很大的的正数数，其其作用用是强强迫相相应的的x31、x33、x34取值为为0。。3、运运输输问问题题（例例题））79例、设有A、B、C三个个化肥肥厂供供应1、2、3、4四个个地区区的农农用化化肥。。假设设效果果相同同，有有关数数据如如下表表。试试求总总费用用为最最低的的化肥肥调拨拨方案案。3、运运输输问问题题（例例题））80解：根据题意意，作出出产销平平衡与运运价表：：最低要求求必须满满足，因因此把相相应的虚虚设产地地运费取取为M，而而最高要要求与最最低要求求的差允允许按需需要安排排，因此此把相应应的虚设设产地运运费取为为0。。对应应4””的销量量50是考考虑问题题本身适适当取的的数据，，根据产产销平衡衡要求确确定D的产量量为50。3、运输输问问题（（例题））81例、某厂按合合同规定定须于当当年每个个季度末末分别提提供10、15、25、20台同一一规格的的柴油机机。已知知该厂各各季度的的生产能能力及生生产每台台柴油机机的成本本如下表表。如果果生产出出来的柴柴油机当当季不交交货，每每台每积积压一个个季度需需储存、、维护等等费用0.15万元。。试求在在完成合合同的情情况下，，使该厂厂全年生生产总费费用为最最小的决决策方案案。3、运输输问问题（（例题））82解：设xij为第i季度度生产的的第j季度度交货的的柴油机机数目，，那末应应满足：：交货：x11=10生生产：x11+x12+x13+x14≤25x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10把第i季度度生产的的柴油机机数目看看作第i个个生产厂厂的产量量；把第第j季季度交交货的柴柴油机数数目看作作第j个销销售点的的销量；；成本加加储存、、维护等等费用看看作运费费。可构构造下列列产销平平衡问题题：目标函数数：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x443、运输输问问题（（例题））83例、光明仪器器厂生产产电脑绣绣花机是是以产定定销的。。已知1至6月月份各月月的生产产能力、、合同销销量和单单台电脑脑绣花机机平均生生产费用用见下表表已知上年年末库存存103台绣花花机，如如果当月月生产出出来的机机器当月月不交货货，则需需要运到到分厂库库房，每每台增加加运输成成本0.1万元元,每台台机器每每月的平平均仓储储费、维