一、绪论§1 运筹学的简史运筹学作为科学名称出现于20世纪30年代末。

英、美对付德国空袭，采用雷达，技术上可行，实际运用不好用。

如何合理运用雷达？“运用研究”（Operational Research）,我国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 运筹学的工作步骤提出和形成问题。

弄清问题目标、约束、可控变量、参数，搜集资料。

建立模型。

把问题可控变量、参数、目标、约束的关系用模型表示。

求解。

用各种手段将模型求解，得最优解、次优解、满意解，借助计算机，精度由决策者定。

解的检验。

检查求解步骤程序有无错误、解是否反映现实问题。

解的控制。

控制解的变化过程决定对解是否作一定改娈。

解的实施。

向实际部门讲清解的用法、在实施中可能产生的问题和修改。

§4 运筹学的模型模型：是研究者对客观现实经过思维抽象后用文字、图表、符号、关系式、实体模样描述所认识到的客观对象。

模型的三种基本形式：形象模型、模拟模型、符号或数学模型。

构模的方法和思路：直接分析法、类比法、数据分析法、试验分析法、想定（构想）法（Scenario ）。

模型的一般数学形式：目标的评价准则：),,(k j i y x f U ξ= 约束条件：0),,(≥k j i y x g ξ其中i x 为可控变量；j y 为已知参数；k ξ为随机因素。

§5 运筹学的应用运筹学的应用领域：市场销售、生产计划、库存管理、运输问题、财政和会计、人事管理、设备维修更新和可靠性项目选择和评价、工程优化设计、计算机和信息系统、城市管理。

趋向大规模复杂问题，与系统工程难于分解。

§6 运筹学的展望运筹学应在三个领域发展：运筹学应用、运筹科学、运筹数学，强调发展前两者，整体协调发展。

——美国前运筹学会主席邦特（S. Bonder ）要从运筹学到系统分析，与未来学紧密结合。

层次分析法（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..32max 21212121x x x x x x t s x x z例2 靠近某河流有两个化工厂（见图1-1），流经第一化工厂的河流流量为每天500万m 3，在两个工厂之间有一条流量为每天200万m 3支流。

第一化工厂每天排放含某种有毒物质的工业污水2 万m 3，第二化工厂每天排放含这种工业污水1.4 万m 3。

从第一化工厂排出的工业污水流到第二化工厂以前，有20%可自然净化。

根据环保要求，河水中工业污水的含量应不大于0.2%。

这两个工厂都需各自处理一部分工业污水。

第一化工厂处理工业污水的成本是1000元/ 万m 3，第二化工厂处理工业污水的成本是800元/ 万m 3。

问：在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总处理工业污水费用最小？表1-1⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤≤≥+≥+=0,4.126.18.01..8001000min 212121121x x x x x x x t s x x z共同特征：用一组决策变量),,,(21n x x x 表示方案，这组决策变量值表示具体方案，变量取值非负； 存在约束条件（一组线性等式或线性不等式）；有一个要达到的目标，目标函数是决策变量的线性函数，要求目标函数实现最大或最小。

线性规划的数学模型：目标函数：n n x c x c x c z ++=2211max(min) ( 1.1)满足约束条件：⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥≥=≤++≥=≤++≥=≤++)3.1(0,,),()2.1(),(),(2122112222212*********n m n mn m m n n n n x x x b x a x a x a bx a x a x a b x a x a x a1.2图解法⎪⎪⎩⎪⎪⎨⎧≥≤≤≤++=0,12416482..32max 21212121x x x x x x t s x x z （4，2）；z=14工厂1图1-1⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤≤≥+≥+=0,4.126.18.01..8001000min 212121121x x x x x x x t s x x z一般线性规划问题求解结果出现的情况：（1）无穷多最优解（多重解）；⎪⎪⎩⎪⎪⎨⎧≥≤≤≤++=0,12416482..42max 21212121x x x x x x t s x x z （2）无界解；⎪⎩⎪⎨⎧≥≤-≤+-+=0,242..max 21212121x x x x x x t s x x z（3）无可行解；⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥+-≤≤≤++=0,4212416482..32max 2121212121x x x x x x x x t s x x z （2）、（3）情况出现，一般模型有误：（2）缺必要约束条件，（3）有矛盾约束条件。

直观结论：当线性规划问题可行域非空时，它是有界或无界凸多边形。

若线性规划问题存在最优解，它一定在可行域的某个顶点得到；若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即有无穷多最优解。

1.3线性规划问题的标准型式n n x c x c x c z ++=2211maxs.t.(M 1 ) ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥∈≥=++=++=++0},,2,1{0,,2122112222212111212111i n m n mn m m n n n n b m i x x x b x a x a x a bx a x a x a b x a x a x a 规定对∑==nj j j x c z 1max s.t. ('1M ) ⎪⎪⎪⎩⎪⎪⎪⎨⎧≥∈=≥==∑=0},,2,1{,,2,10,2,11i j nj ij ij b m i n j x m i b x a 规定对 用向量与矩阵表述：CX z =max s.t. ("1M ) ⎪⎪⎪⎩⎪⎪⎪⎨⎧≥=≥=∑=0,,2,101b n j x b x P j nj j j 规定其中 ),,,(21n c c c C =；⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=n x x x X 21； ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=nj jj j a a a P 21；⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=m b b b b 21；向量j P 对应决策变量j x 。

用矩阵矩阵描述：CX z =max s.t. b AX =, 0≥X .其中()nm ij a A ⨯==),,,(21n P P P ；10000⨯⎪⎪⎪⎪⎪⎭⎫⎝⎛=n ；称A 为约束条件的n m ⨯维系数矩阵，n m <；0,>n m ；b 为资源向量；C 为价值向量；X 为决策变量向量。

如何将各种线性规划问题的数学模型化为标准型： （1） 若要求目标函数实现最小化，即CX z =min 。