运筹学第1章.

-1-ChinaUniversityofMiningandTechnology运筹学§1线性规划问题及其模型§2线性规划问题几何意义§3单纯形法§4单纯形法计算步骤§5单纯形法进一步讨论§6应用举例第一章线性规划-2-ChinaUniversityofMiningandTechnology运筹学线性规划（LinearProgramming）是运筹学的一个重要分支，是研究较早、理论较完善、应用最广泛的一个学科。由前苏联经济学家康托洛维奇于1939年提出，而此人也因此获得1960年的诺贝尔经济学奖。1947年，G.B.Dantzig提出求线性规划的单纯形法，理论上趋向成熟，实际上的应用也越来越广泛。-3-ChinaUniversityofMiningandTechnology运筹学因此，线性规划是求一组变量的值，使它满足一组线性式子，并使一个线性函数的值最大（或最小）的数学方法。线性规划不仅仅是一种数学理论和方法，而且已成为现代管理工作中帮助管理者做出科学决策的重要手段。•线性规划所研究的问题主要包括两个方面：•一是在一项任务确定后，如何以最低成本（如人力、物力、资金和时间等）去完成这一任务；•二是如何在现有资源条件下进行组织和安排，以产生最大收益。-4-ChinaUniversityofMiningandTechnology运筹学§1线性规划问题及其数学模型-5-ChinaUniversityofMiningandTechnology运筹学1.1问题的提出在生产管理和经营活动中经常需要解决：如何合理地利用有限的资源，以得到最大的效益。我们先通过几个实际问题来认识什么是线性规划.1.1问题的提出-6-ChinaUniversityofMiningandTechnology运筹学【例1】某企业生产A1,A2,A3三种产品，这些产品分别需要甲、乙两种原料.生产每种产品一吨所需原料和每天原料总限量及每吨不同产品可获利润情况如表1.1所示.（生产计划问题）利润最大化问题试问：该企业怎样安排生产才会使每天的利润最大？表1.1企业生产数据表1.1问题的提出-7-ChinaUniversityofMiningandTechnology运筹学解设该企业每天生产产品的数量分别为（单位：吨），则总利润的表达式为321734xxxf我们希望在现有资源条件下总利润最大.现有资源的限制为12322100xxx（原料甲的限制）12333100xxx（原料乙的限制）此外，由于未知数（我们称之为决策变量）是计划产量，应有为非负的限制，即321,,xxx321,,xxx123,,AAA3,2,1,0jxj1.1问题的提出-8-ChinaUniversityofMiningandTechnology运筹学由此得到问题的数学模型为123123123max437s.t.22100,33100,0(1,2,3).jfxxxxxxxxxxj其中s.t.为英文“subjectto”的缩写，表示决策变量xj(j=1,2,3)受它后面的条件约束.1.1问题的提出-9-ChinaUniversityofMiningandTechnology运筹学决策变量：需决策的量，即待求的未知数；目标函数：需优化的量，即欲达的目标，用决策变量的表达式表示；约束条件：为实现优化目标需受到的限制，用决策变量的等式或不等式表示。线性规划模型的三要素1.1问题的提出-10-ChinaUniversityofMiningandTechnology运筹学练习1某企业要在计划期内安排生产甲、乙两种产品，这个企业现有的生产资料是：设备18台时，原材料A4吨，原材料B12吨；已知单位产品所需消耗生产资料及利润如表1。问应如何确定生产计划使企业获利最多。产品资源甲乙资源量设备/机时3218原料A/吨104原料B/吨0212单位赢利/万元351.1问题的提出-13-ChinaUniversityofMiningandTechnology运筹学成本最小化问题【例2】某钢铁厂熔炼一种新型不锈钢，需要4种合金T1T2T3T4为原料经测定这4种原料关于元素铬（Cr）、锰（Mn）和镍（Ni）的质量分数（%）、单价以及这种新型不锈钢所需铬、锰和镍的最低质量分数，情况如表2.3所示.假设熔炼时质量没有损耗，问：要熔炼100吨这样的不锈钢，应选用原料T1T2T3T4各多少吨，能够使成本最小？1.1问题的提出-14-ChinaUniversityofMiningandTechnology运筹学表1.2生产某种不锈钢的相关数据表1.1问题的提出-15-ChinaUniversityofMiningandTechnology运筹学解:设选用原料T1、T2、T3、T4的量分别为x1、x2、x3、x4（单位：吨）.由于追求的目标是成本最小，故有最小成本表达式：1234min11.59.78.27.6fxxxx1234100xxxx又因该不锈钢所需铬、锰和镍的最低质量分数是由4种合金T1、T2、T3、T4对相应元素的质量分数构成，注意到要熔炼该种不锈钢100吨，于是得到铬、锰和镍的质量分数满足的不等式依次为以下分析约束条件.由于假设熔炼时质量没有损耗，熔炼该种不锈钢100吨，它由原料T1、T2、T3、T4熔炼而成，故有等式约束1.1问题的提出-16-ChinaUniversityofMiningandTechnology运筹学1234123412343.214.532.191.763.20100,2.041.123.574.332.10100,5.823.064.272.734.30100.xxxxxxxxxxxx此外，各种合金的加入量以整吨为单位，即有限制x1、x2、x3、x4≥0且为整数.综合上述讨论，我们得到该问题的数学模型为1234,,,0xxxx123412341234123412341234min11.59.78.27.6..3.214.532.191.76320,2.041.123.574.33210,5.823.064.272.73430,,,,0100,且均为整数.，fstxxxxxxxxxxxxxxxxxxxxxxxx这类问题也称为混合配料问题.1.1问题的提出-19-ChinaUniversityofMiningandTechnology运筹学运输问题【例3】某建材公司有三个水泥厂，四个销地，其产量、销量、运费见表1.4.123,,AAA1234,,,BBBB1.4如何制定调运方案，使总的运费或总货运量最小？1.1问题的提出-20-ChinaUniversityofMiningandTechnology运筹学解设由水泥厂Ai运到销地Bj的货运量为xij(i=1,2,3;j=1,2,3,4)，则得到问题的数学模型为111213142122232431323334111213142122232431323334112131122232132333142434min87324752496s.t.2000,10000,4000,3000,2000,4000,5000,fxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx0(1,2,3;1,2,3,4),且为整数.ijij1.1问题的提出-23-ChinaUniversityofMiningandTechnology运筹学练习2某公司要运销一种物资。该物资有甲、乙两个产地，产量分别是2000吨、1000吨；另有A、B、C三个销地，销量分别是1700吨、1100吨、200吨。已知该物资的单位运价如下表。问应如何确定调运方案，才能使在产销平衡的条件下，总运费最低？ABC产量甲212572000乙5151371000销量170011002001.1问题的提出-24-ChinaUniversityofMiningandTechnology运筹学【例4】设某单位现有n个人员A1,A2,……,An来完成n项工作B1,B2,……,Bn。按工作要求，每个人员需干一项工作，每项工作也需一人去完成。已知人员Ai做工作Bj的效率是cij。问应如何分配，才使总效率最好。在本例中决策变量：xij表示分配人员Ai完成工作Bjxij=1表示分配Ai干工作Bjxij=0表示不分配Ai干工作Bj人员分配问题1.1问题的提出-25-ChinaUniversityofMiningandTechnology运筹学对工作Bj；要求一人员去完成：nixnjij,,2,1,11niijnjx1,,2,1,1对人员Ai；要求承担一项工作：派工方案的总效益ninjijijxcz11按问题要求，每人要做一项工作，每项工作需一人去做。建立该问题的数学模型的过程：1.1问题的提出-26-ChinaUniversityofMiningandTechnology运筹学1111max1..10,1nnijijijnijjmijiijzcxxstxx分配问题的数学模型1.1问题的提出-27-ChinaUniversityofMiningandTechnology运筹学•从前面对实际问题建立数学模型的过程，可以得到一般线性规划问题建模过程如下：第1步理解要解决的问题.第2步定义决策变量.第3步确定约束条件.第4步列出目标函数.1.1问题的提出-28-ChinaUniversityofMiningandTechnology运筹学1122max(min)nnzcxcxcx11112211211222221122120,0,,0nnnnmmmnnmnaxaxaxbaxaxaxbaxaxaxbxxx共同表现：线性规划的数学模型1.1问题的提出-30-ChinaUniversityofMiningandTechnology运筹学1.2线性规划问题的图解法图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，而是在于能够直观地说明线性规划解的一些重要性质。图解法的步骤可概括为：在平面上建立直角坐标系；图示约束条件，找出可行域；图示目标函数和寻找最优解。1.2线性规划问题的图解法-31-ChinaUniversityofMiningandTechnology运筹学①先做约束的图形先做非负约束的图形；再做资源约束的图形。以练习1为例，其约束为0,12241823212121xxxxxx02468x1x286420x1=42x2=123x1+2x2=18可行域QQ0(0,0)Q1(0,6)Q2(2,6)Q3(4,3)Q4(4,0)1.2线性规划问题的图解法-32-ChinaUniversityofMiningandTechnology运筹学函数任给二不同的值，便可做出相应的二直线，用虚线表示。例1中，其目标为z=3x1+5x2，分别令z=20和z=36，做出相应的二直线，便可看出增大的方向。②再做目标图形02468x1x286420可行域QQ0(0,0)Q1(0,6)Q2(2,6)Q3(4,3)Q4(4,0)3x1+5x2=z=363x1+5x2=z=203x1+5x2=z=01.2线性规划问题的图解法-33-ChinaUniversityofMiningandTechnology运筹学③求出最优解将目标直线向使目标z优化的方向移，直至可行域的边界为止，这时其与可行域的“切”点X*即最优解。02468x1x286420Q2(2,6)3x1+5x2=z=36练习1中，X*是可行域的一个角点。X*1.2线性规划问题的图解法-34-ChinaUniversityofMiningandTec