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…………………a

x1，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种种（甲、、乙、丙丙）产品品中原料料j的的含量量。这样样我们建建立数学学模型时时，要考考虑：对于甲：：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次当当年末才才可收回回投资故故第二年年年初的的资金为为x11，于是x21+x22+x24=1.1x11；第三年：：年初的的资金为为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=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≤100x

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、线性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、、线线性性规规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.32.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、运输输问问题（（3.1续）求解思路路是基本可行行解最优否结束否换基运输问题题基变量量的特点点*运运输问题题的基变变量共有有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、运输输问问题（（3.2）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四个地区区的农用化化肥。假设设效果相同