运筹学第01章线性规划

1、1运筹学2运筹学的历史与发展 国际上运筹学的思想可追溯到1914年，当时的兰彻斯特提出了军事运筹学的作战模型。1917年，丹麦工程师埃尔朗在研究自动电话系统中通话线路与用户呼叫的数量关系问题时，提出了埃尔朗公式，研究了随机服务系统中的系统排队与系统拥挤问题。存储论的最优批量公式是在20世纪20年代初提出的。 运筹学作为科学名字出现在20世纪30年代。当时英美对付德国的空袭，雷达作为防空系统的一部分，从技术上是可行的，但实际运用时却并不好用。为此一些科学家研究如何合理运用雷达开始进行新一类问题的研究。因为它与研究技术问题不同，就称之为“运用研究”(Operational Research)。 为

2、了进行运筹学研究，在英美军队中成立了一些专门小组，开展了护航舰队保护商船队的编队问题和当船队遭到德国舰艇攻击时，如何使船队损失最少的问题。3 研究了反潜深水炸弹的合理爆炸深度后，使德国潜艇被摧毁的数量增加到400%； 研究了船只在受敌机攻击时，提出大船应急转向和小船应缓慢转向的逃避方法，结果船只中弹数由47%降到29%。 在生产管理方面的应用，最早是1939年前苏联的数学家康托洛维奇提出了生产组织与计划中的线性规划问题，并给出解乘数法的求解方法，出版了第一部关于线性规划的著作生产组织与计划中的数学方法。 线性规划提出后很快受到经济学家重视，如二次世界大战中从事运输模型研究的美国经济学家库普曼斯

3、(T.C.Koopmans)，他很快看到了线性规划在经济中应用的意义，并呼吁年轻的经济学家要关注线性规划。其中阿罗、萨谬尔逊、西蒙、多夫曼和胡尔威茨等都获得了诺贝尔奖。 但当时并没有引起重视，直到1960年康托洛维奇再次出版了最佳资源利用的经济计算，才受到国内外的一致重视，为此康托洛维奇获得了诺贝尔经济学奖。 50年代中期，钱学森、许国志等教授在国内全面介绍和推广运筹学知识，1956年，中国科学院成立第一个运筹学研究室，1957年运筹学运用到建筑和纺织业中，1958年提出了图上作业法，山东大学的管梅谷教授提出了“中国邮递员问题”，1970年，在华罗庚教授的直接指导下，在全国范围内推广统筹方法和

4、优选法。 在中国，最早的运筹学思想有战国时期的田忌赛马，它是对策论的一个典型例子，北宋时期的丁渭造皇宫，它是统筹规划的一个例子。第一章 线性规划(Linear Programming)线性规划问题及其数学模型线性规划图解法线性规划问题解的性质 单纯形法 单纯形法的其他问题讨论 线性规划应用举例 WinQSB软件应用第一节 线性规划问题及其数学模型 产 品资 源 甲乙每天可用于产品生产的资源量设备1116材料A3236材料B565利润（元）9070 【例1-1】已知某企业生产资料如下表所示，问如何安排生产才能企业使利润最大？数学模型：一、线性规划问题的提出设甲产品的生产量为 x1 ,乙产品的生产

5、量为 x2 ，则：约束条件： 【例1-2】设某种动物每天需要摄入的蛋白质、矿物质、维生素的最低量及A、B、C、D、E五种饲料每公斤营养成分的含量及单位价格如下表所示。要求既满足该种动物每天营养成分的需要量，又使总的费用最省。 目标函数： 约束条件： ABCDE每天最低摄入量(克)蛋白质(克)矿物质(克)维生素(克)310.520.5110.20.2622180.50.870030100价格(元/千克)27438设 为第 j 种饲料的每天使用量，则： 线性规划问题数学模型的组成要素： 二、线性规划问题数学模型的一般形式 (1)变量，或称决策变量，它们是问题中所要解决的未知量，表明规划中用数量表示

6、的方案、措施，可由决策者决定和控制； (2)目标函数，是决策变量的函数，按问题的目标不同分别在这个函数前加上max或min； (3)约束条件，由一组含决策变量的等式或不等式组成，表明决策变量取值时所受到的各种资源条件的限制。 假定线性规划问题中含有 n 个决策变量 xj (j1，n)， 在目标函数中 xj 的系数为 cj (cj 通常称为价值系数)； 有m 种资源的限制，每种资源数量用 bi(i=1,.m)表示； 用 aij表示变量 xj 取值为1个单位时所消耗或含有的第 i 种资源的数量，通常称 aij 为技术系数或消耗系数。 目标函数：约束条件：线性规划问题的数学模型的一般形式：为目标函数

7、；为资源约束；为非负约束。xj决策变量；cj价值系数；aij技术（消耗）系数；bi资源常量，bi0线性规划模型的简写形式为：用向量形式表达时，模型可写为：式中：矩阵形式为：其中：A为约束方程组（约束条件）的系数矩阵。三、线性规划问题的标准形式化一般形式为标准形式的方法： 1、目标函数为求极小值，即为:因为求Min z，等价于求Max(-z)，令z=-z，即化为：2右端项 bi0又Pj0，对应的变量 xj 就可作为换入基的变量，当有一个以上检验数大于零时，一般从中找出最大一个s。作为进基变量(也称换入变量)确定进基变量确定离基变量根据最小的规则确定： 确定是离基的变量(也称换出变量)。元素 决定

8、了从一个基可行解到相邻基可行解的转移去向，取名主元素。 以 ahs ，为主元素进行迭代。 迭代计算 第4步：重复第2，3两步，直到所有的检验数小于等于0时，计算结束。【例1-5】用单纯形法求解线性规划问题 解：将上述问题化为标准形式有： 其约束条件系数矩阵为： 列出初始单纯形表为： cj cBxBb x1 x2 x3 x4 x5j 36/316/19070000111003201005001x3x4x500016366590700000900 x3x1x5 j0651215001001/32/370900 x2x1x5 j401/31-1/300100-30012181312013-10500

9、-1551410-2100-300-200【例】用单纯形法求解线性规划问题 解：将上述问题化为标准形式有： 列出初始单纯形表为： cj cBxBb x1 x2 x3 x4 x5 j 906000011100201005001x3x4x500016366536/316/10900 x3x1x5 j90060000651215001001/32/360900 x2x1x5 j401/31-1/30000-3001218131201-10500-1551410-210000-30033max z2xl+x2 0,21xx52x2461x1552x+22xx1+例：利用单纯形法求解下列问题化为标准型0

10、,54321xxxxx=+15532xx=+ 552xxx1+=+24641xx+2x2cj 2 1 0 0 0 cBxBb x1 x2 x3 x4 x5000 x3x4x515245 0 5 1 0 0 6 2 0 1 0 1 1 0 0 1j 24/65/1020 x3x1x5 j2010001412/30-1/61001/61/3021x3x1x2 j150510001/30-1/303123/215/20015/4-15/23/2010-1/43/27/21001/4-1/2000-1/4-1/2建立初始单纯形表如下：第五节 单纯形法的其他问题讨论一、关于标准形为最小化问题目标函数为最

11、小化的标准形式，最优性检验的判别定理 ： 定理1.7（最优解）设 为对应于基B的一个基可行解，且对于一切 有 ，则 为线性规划问题的最优解。 定理1.8（无穷多最优解）设 为对应于基B的一个基可行解，且对于一切 有 ，同时又存在某个非基变量的检验数 ，则线性规划问题存在无穷多最优解。 定理1.9（无界解）设 为对应于基B的一个基可行解，存在某个非基变量的检验数 ，且有 ，则线性规划问题具有无界解。二、人工变量法 【例1-6】用单纯形法求解线性规划问题 解：将其化成标准形式有 上述标准化模型中，不存在单位矩阵，为构造单位矩阵，则需要通过添加人工变量的方法，人为构造一个单位矩阵，该方法即所谓的人工

12、变量法。 1.大M法 大 M 法又称惩罚法，其基本思想是：约束条件加入人工变量后，为使目标函数取值不受影响，给定它们在求最大值(max)的目标函数中的系数为(-M)(称为惩罚因子，M为任意大的正数)，以作为对基变量中存在人工变量的惩罚，从而迫使人工变量从基变量中分离出来，否则目标函数将不能实现最大化。 添加人工变量后，例1-6的数学模型形式变为： 列出初始单纯形表如下： cj32-100- M- McBxBbx1x2x3x4x5x6x7- Mx64-431-10100 x5101-120100- Mx712-210001j-Mx60 x5- 1x3j38-60-101-1-330010-2-2

13、100011- 2M5-6M5M-M000213/58/32x20 x5-1x3j-6/53/510-1/501/5-1/531/5003/51-3/5-7/511/5-2/501-2/502/53/550000-M1-M53/531/32x21301012-1-33x131/310015/3-1-7/3-1x319/300102/30-1/3j000-5-25/35-M38/3-M-M2+M2M-13-2M000451 计算机处理数据时，只能用很大的数代替M,可能造成计算机上的错误，故多采用两阶段法。 2、两阶段法第一阶段：添加人工变量，重新构造目标函数 将原问题加入人工变量，构造仅含人工变

14、量的新的目标函数，并要求实现最小化。新的目标函数形式如下： 求解上述线性规划问题。若 w =0，则原线性规划问题存在基可行解，计算转入第二阶段；若 w 0，则原线性规划问题无可行解，计算停止。 第二阶段：对原目标函数求解 在第一阶段的最终单纯形表中，将 cj 行的数字换为原目标函数的系数，并且去掉表中含有人工变量的列，继续求解。 将例1-6问题利用两阶段法进行求解。 第一阶段：添加人工变量，重新构造目标函数。例1-6用两阶段法求解时，第一阶段的线性规划问题可写为： 将上述数学模型标准化后，用单纯形法求解过程见下表： cj00000- 1-1cBxBbx1x2x3x4x5x6x7- 1x64-4

15、31-101040 x5101-1201005- 1x712-2100011j-212-1000-1x60 x50 x3j38-60-101-1-330010-2-210001-2-65-1000213/58/30 x20 x50 x3j-6/53/510-1/501/5-1/531/5003/51-3/5-7/511/5-2/501-2/502/53/500000-1-153/5可以看出：W=0，该问题有解；转入第二阶段。cj32-100cBxBbx1x2x3x4x52x23/5-6/510-1/500 x531/53/5003/51-1x311/5-2/501-2/50j500002x21

16、3010123x131/310015/3-1x319/300102/3j000-5-22/3第二阶段： 得最优解。 将第一阶段得到的最终单纯形表的人工变量列去掉，将目标Cj行换为原目标函数的系数，再进行迭代。31/3三、单纯形法计算中退化与循环问题 单纯形法计算中按最小比值来确定离基变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就会出现一个或多个基变量等于零的情形，这就出现了所谓的退化解。当存在退化解时，就有可能出现迭代计算的循环。 勃兰特规则： (1)当存在多个 且相等时，选取 中下标值最小的变量作为进基变量； (2)当按规则计算出现两个或两个以上相同的最小比值时，选取下标值最小

17、的变量作为离基变量。 第六节 线性规划应用举例一、混合配料问题 【例1-7】某工厂要用三种原材料C、P、H混合调配出三种不同规格的产品A、B、D。已知产品的规格、产品单价、每天能供应的原材料数量及原材料单价如表1-10、表1-11所示。表1-1025不限D原材料P不超过50%35原材料C不少于25%B原材料P不超过25%50原材料C不少于50%A单价(元/kg)规格要求产品名称表1-113560H25100P65100C单价(元/kg)每天最大供应量(kg)原材料名称 问该厂如何安排生产，利润收入最大？解：设Ac表示A产品中C的成分，其数量用x1表示； AP表示A产品中P的成分，其数量用x2表

18、示； AH表示A产品中H的成分，其数量用x3表示； BC表示B产品中C的成分，其数量用x4表示； BH表示B产品中H的成分，其数量用x6表示； BP表示B产品中P的成分，其数量用x5表示； DC表示D产品中C的成分，其数量用x7表示； DH表示D产品中H的成分，其数量用x9表示. DP表示D产品中P的成分，其数量用x8表示； 依据题意，得： 依据产品规格要求得： 整理得： 25不限D原材料P不超过50%35原材料C不少于25%B原材料P不超过25%50原材料C不少于50%A单价(元/千克)规格要求产品名称依据原材料每天供应量限制得：该问题的线性规划数学模型为： 3560H25100P65100

19、C单价每天最大供应量原材料二、生产计划安排问题 【例1-8】某厂生产、三种产品，都分别经A、B两道工序加工。设A工序可分别在设备A1或A2上完成，有B1、B2、B3三种设备可用于完成B工序。已知产品可在A、B任何一种设备上加工；产品可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品只能在A2与B2设备上加工。加工单位产品所需工序时间及其它各项数据见下表：2.802.001.25售价（元/件）0.500.350.25原料费(元/件)0.0540007B30.117000114B20.06400086B10.03100001297A20.056000105A1设备加工费设备有效

20、台时产品设备 试安排最优生产计划，使该厂获利最大。 解：设产品、的产量分别为x1,x2,x3件 工厂的盈利为产品售价减去相应的原料费和设备加工费。产品加工量只受设备有效台时的限制。故可建立如下线性规划模型： 产品有6种加工方案，分别利用设备(A1,B1)(A1,B2)(A1,B3)(A2，B1)(A2,B2)(A2,B3)，各方案加工的产品数量用 xll，x12，x13，x14，x15，x16 表示； 产品有2种加工方案，即(A1,B1)(A2,B1)，加工数量用 x21，x22 表示； 产品只有1种加工方案(A2,B2)，加工数量等于 x3。 2.802.001.25售价（元/件）0.500

21、.350.25原料费（元/件）0.0540007B30.117000114B20.06400086B10.03100001297A20.056000105A1设备加工费设备有效台时产品设备三、生产与存贮问题 解：设 xij 为 i 种产品 j 月份在正常时间内生产的数量， 为第 i 种产品 j 月份在加班时间内生产的数量。该厂盈利总额为生产的5种产品销售价减去成本和库存费用。问题的限制条件有两项：一是各个月的正常和加班的允许工时，二是满足交货要求。本例的线性规划模型可表示为: 【例1-9】某厂签订了5种产品(i1，5)上半年的交货合同。已知各产品在第j月(j1，6)的合同交货量Dij，该月售价

22、 sij 、成本价 cij 及生产1件时所需工时 aij 。该厂第j月的正常生产工时为 tj ，但必要时可加班生产，第j月允许的最多加班工时不超过 ，并且加班时间内生产出来的产品每件成本增加额外费用 元；若生产出来的产品当月不交货，每件库存1个月交存贮费 pi 元。试为该厂设计一个保证完成合同交货，又使上半年预期盈利总额为最大的生产计划安排。 解：设 为 i 种产品 j 月份在正常时间内生产的数量， 为第 i 种产品 j 月份在加班时间内生产的数量。本例的线性规划模型可表示为: 四、人力资源分配问题 【例1-10】某医院护士值班班次及每班所需要的护士人数如下表所示。 班次工作时间所需人数(人)

23、1 6:0010:0060210:0014:0070314:0018:0060418:0022:0050522:00 2:00206 2:00 6:0030 若该医院值班护士分别在各时间段开始时上班，并连续工作8小时。问该医院最少需要多少护士，才能满足工作需要？ 解：设 xi 表示第 i 班开始时上班的护士人数。根据题意，该问题的数学模型为： 班次工作时间所需人数(人)1 6:0010:0060210:0014:0070314:0018:0060418:0022:0050522:00 2:00206 2:00 6:0030五、连续投资问题 【例1-11】某部门今后五年内考虑给以下项目投资，已知：项目A，从第一年到第四年每年年初需要投资，并于次年末收回本利115%； 项目B，第三年初需要投资，到第五年末收回本利125%，但规定最大投资额不超过4万元； 项目C，第二