运筹学(1)

1一、绪论§1运筹学的简史运筹学作为科学名称出现于20世纪30年代末。英、美对付德国空袭，采用雷达，技术上可行，实际运用不好用。如何合理运用雷达？“运用研究”（OperationalResearch）,我国1956年用“运用学”名词，1957年正式定名为运筹学。运筹学小组在英、美军队中成立，研究：护航舰队保护商船队的编队问题、当船队遭受德国潜艇攻击时如何使船队损失最小问题、反潜深水炸弹的合理爆炸深度（德国潜艇被摧毁数增到400%）、船只在受敌机攻击时的逃避方法（大船急转向、小船缓转向，中弹数由47%降到29%）。运筹学组织在英、美军队（RAND）中成立，研究：战略性问题、未来武器系统的设计和合理运用方法、美国空军各种轰炸机系统的评价、未来武器系统和未来战争战略、苏联军事能力及未来预报、苏联政治局计划的行动原则和未来战争的战略、到底发展哪种洲际导弹（50年代）、战略力量的构成和数量（60年代）。运筹学在工业、农业、经济、社会问题等领域有应用。运筹数学：数学规划（线性规划（丹捷格（G.B.Dantzig）1947，单纯形法；康托洛维奇1939解乘数法，1960《最佳资源利用的经济计算》，诺贝尔奖；列昂节夫1932投入产出模型；冯.诺意曼）、非线性规划、整数规划、目标规则、动态规划、随机规划等）、图论与网络、排队论（随机服务系统理论）(丹麦工程师爱尔朗（Erlang）1917提出一些著名公式)、存贮论、对策论（冯.诺意曼和摩根斯坦，1944《对策论与经济行为》）、决策论、维修更新理论、搜索论、可靠性和质量管理等。运筹学领域的诺贝尔奖得主：阿罗、萨谬尔逊、西蒙（经济学家）、多夫曼、胡尔威茨、勃拉凯特（Blackett,美，物理学家）。运筹学会的建立：英国（1948年）、美国（1952年）、法国（1956年）、日本（1957年）、印度（1957年）、中国（1980年），38个国家和地区。国际运筹学联合会（IFORS）的成立：1959年，英、美、法发起成立，中国1982年加入。欧洲运筹学协学（EURO）的成立：1976年。亚太运筹学协学（APORS）的成立：1985年。运筹学在我国的引入：20世纪50年代中期，钱学森、许国志、华罗庚，推广应用运筹学：投入产出表、质量控制（质量管理）。§2运筹学的性质和特点运筹学的定义：“为决策机构在对其控制下业务活动进行决策时，提供以数量化为基础的科学方法”-——（莫斯(P.M.Morse)和金博尔(G.E.Kimball)）。“运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据”“运筹学是一种给出问题坏的答案的艺术，否则的话问题的结果会坏。”运筹学的特点：多学科交叉、强调量化和最优（次优、满意）、为决策（管理）服务、解决实际问题。应用运筹学的六原则：合作原则（相互配合）、催化原则（改善心智模式）、互相渗透原则（系统全局考虑问题）、独立原则（不受政策左右、独立从事工作）、宽容原则（思路宽、方法多、不局限特定方法）、平衡原则（考虑矛盾与关系平衡）。§3运筹学的工作步骤2提出和形成问题。弄清问题目标、约束、可控变量、参数，搜集资料。建立模型。把问题可控变量、参数、目标、约束的关系用模型表示。求解。用各种手段将模型求解，得最优解、次优解、满意解，借助计算机，精度由决策者定。解的检验。检查求解步骤程序有无错误、解是否反映现实问题。解的控制。控制解的变化过程决定对解是否作一定改娈。解的实施。向实际部门讲清解的用法、在实施中可能产生的问题和修改。§4运筹学的模型模型：是研究者对客观现实经过思维抽象后用文字、图表、符号、关系式、实体模样描述所认识到的客观对象。模型的三种基本形式：形象模型、模拟模型、符号或数学模型。构模的方法和思路：直接分析法、类比法、数据分析法、试验分析法、想定（构想）法（Scenario）。模型的一般数学形式：目标的评价准则：),,(kjiyxfU约束条件：0),,(kjiyxg其中ix为可控变量；jy为已知参数；k为随机因素。§5运筹学的应用运筹学的应用领域：市场销售、生产计划、库存管理、运输问题、财政和会计、人事管理、设备维修更新和可靠性项目选择和评价、工程优化设计、计算机和信息系统、城市管理。趋向大规模复杂问题，与系统工程难于分解。§6运筹学的展望运筹学应在三个领域发展：运筹学应用、运筹科学、运筹数学，强调发展前两者，整体协调发展。——美国前运筹学会主席邦特（S.Bonder）要从运筹学到系统分析，与未来学紧密结合。建立模型提出和形成问题解的检验解的实施解的控制求解3层次分析法（AHP）——沙旦（T.L.Saaty）20世纪70年代末提出。采用软系统思考方法，以“易变性”概念看待所得“解”。——切克兰特（P.B.Checkland）决策支持系统是使运筹学发展的好机会。运筹学在不断发展，新思想、观点、方法在不断出现。二、线性规划与目标规划线性规则：运筹学重要分支，1947年丹捷格（G.B.Dantzig）提出，给出“单纯形法”解法。目标规则：1961年查恩斯（A.charns）与库伯(W.W.Cooper)提出，艾吉利（Y.Ijiri）提出用优先因子处理多目标问题，斯.姆.李(S.M.Lee)与杰斯开来尼(V.Jaaskelainen)用计算机处理多目标问题。第一章线性规则与单纯形法§1线性规则问题及其数学模型1.1问题提出如何合理利用有限人力、物力、财力资源，以便得到最好经济效果。例1某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需设备台时及A、B两种原材料的消耗如表1-1所示。问：应如何安排计划使工厂获利最多？设1x、2x分别为生产Ⅰ、Ⅱ两种产品的产量，则0,12416482..32max21212121xxxxxxtsxxz例2靠近某河流有两个化工厂（见图1-1），流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为每天200万m3支流。第一化工厂每天排放含某种有毒物质的工业污水2万m3，第二化工厂每天排放含这种工业污水1.4万m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可自然净化。根据环保要求，河水中工业污水的含量应不大于0.2%。这两个工厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成本是1000元/万m3，第二化工厂处理工业污水的成本是800元/万m3。问：在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总处理工业污水费用最小？ⅠⅡ设备128台时原材料A4016kg原材料B0412kg单位获利2元/件3元/件表1-140,4.126.18.01..8001000min212121121xxxxxxxtsxxz共同特征：用一组决策变量),,,(21nxxx表示方案，这组决策变量值表示具体方案，变量取值非负；存在约束条件（一组线性等式或线性不等式）；有一个要达到的目标，目标函数是决策变量的线性函数，要求目标函数实现最大或最小。线性规划的数学模型：目标函数：nnxcxcxcz2211max(min)(1.1)满足约束条件：)3.1(0,,),()2.1(),(),(2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxa1.2图解法0,12416482..32max21212121xxxxxxtsxxz（4，2）；z=14工厂2工厂1200万m3500万m3图1-150,4.126.18.01..8001000min212121121xxxxxxxtsxxz一般线性规划问题求解结果出现的情况：（1）无穷多最优解（多重解）；0,12416482..42max21212121xxxxxxtsxxz（2）无界解；0,242..max21212121xxxxxxtsxxz（3）无可行解；0,4212416482..32max2121212121xxxxxxxxtsxxz（2）、（3）情况出现，一般模型有误：（2）缺必要约束条件，（3）有矛盾约束条件。直观结论：当线性规划问题可行域非空时，它是有界或无界凸多边形。若线性规划问题存在最优解，它一定在可行域的某个顶点得到；若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即有无穷多最优解。1.3线性规划问题的标准型式nnxcxcxcz2211maxs.t.6(M1)0},,2,1{0,,2122112222212111212111inmnmnmmnnnnbmixxxbxaxaxabxaxaxabxaxaxa规定对njjjxcz1maxs.t.('1M)0},,2,1{,,2,10,2,11ijnjijijbminjxmibxa规定对用向量与矩阵表述：CXzmaxs.t.(1M)0,,2,101bnjxbxPjnjjj规定其中),,,(21ncccC；nxxxX21；njjjjaaaP21；mbbbb21；向量jP对应决策变量jx。用矩阵矩阵描述：CXzmaxs.t.bAX,0X.其中nmijaA=),,,(21nPPP；10000n；称A为约束条件的nm维系数矩阵，nm；0,nm；b为资源向量；C为价值向量；X为决策变量向量。7如何将各种线性规划问题的数学模型化为标准型：（1）若要求目标函数实现最小化，即CXzmin。将目标函数最小化变为目标函数最大化：令zz'，得CXz'max。（2）约束方程为不变式。（ⅰ）约束方程为“”不变式：在“”不变式左端加入（+）非负松驰变量。（ⅱ）约束方程为“”不变式：在“”不变式左端减去（-）非负剩余（松驰）变量。(3)若存在取值无约束的变量kx，可令'kkkxxx，其中0,'kkxx。例3将0,12416482..32max21212121xxxxxxtsxxz化为标准型。例4将为无约束321321321321321,0,52327..32minxxxxxxxxxxxxtsxxxz化为标准型。1.4线性规划问题的解的概念njjjxcz1maxs.t.('1M)0},,2,1{,,2,10,2,11ijnjijijbminjxmibxa规定对(1.5)(1.6)(1.4)8可行解：满足约束条件(1.5)、(1.6)的解TnxxxX),,,(21称为线性规划问题的可行解，使目标函数达到最大值的可行解叫最优解。基：设A为约束方程的nm维系数矩阵，其秩为m。B是A中mm阶非奇异子矩阵（0B），则称B是线性规划问题的一个基。B由m个线性无关（独立）的列向量组成。不妨设),,,(212111211mmmmmmPPPaaaaaaB，称jP（mj,,2,1）为基向量，与基向量jP相应的变量jx（mj,,2,1）为基变量。设nm，则nmjjjmjjjxPbxP11（1.7）;),,,(21mBxxxX是对应基B的基变量；在（1.7）中令非基变量0)0,,0,0(),,(21nmmNxxxX，用高斯消元法，求出解TmxxxX)0,0,0,,,,(21