下载文档原格式
OPERATIONS RESEARCH运筹学Ⅰ——怎样把事情做到最好第一章绪论♦1.1题解Operations 汉语翻译工作、操作、行动、手术、运算Operations Research日本——运用学港台——作业研究中国大陆——运筹学Operational Research原来名称，意为军事行动研究——历史渊源绪论♦1.2 运筹学的历史早期运筹思想：田忌赛马丁渭修宫沈括运粮Erlang 1917 排队论Harris 1920 存储论Levinson 1930 零售贸易康脱洛维奇1939 LP绪论♦1.2运筹学的历史军事运筹学阶段德军空袭防空系统Blackett运输船编队空袭逃避深水炸弹轰炸机编队绪论♦1.2运筹学的历史管理运筹学阶段战后人员三分:军队、大学、企业大学：课程、专业、硕士、博士企业：美国钢铁联合公司英国国家煤炭局运筹学在中国：50年代中期引入华罗庚推广优选法、统筹法中国邮递员问题、运输问题1.3学科性质▪应用学科▪Morse&Kimball定义：运筹学是为决策机构在对其控制的业务活动进行决策时提供的数量化为基础的科学方法。
▪Churchman定义：运筹学是应用科学的方法、技术和工具，来处理一个系统运行中的问题，使系统控制得到最优的解决方法。
▪中国定义：运筹学是应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。
1.4定性与定量♦例：店主进货♦两者都是常用的决策方法♦定性是基础，定量是工具，定量为定性服务。
♦定性有主观性也有有效性，定量有科学性也有局限性。
管理科学的发展，定量越来越多。
但定量不可替代定性。
1.5运筹学的模型♦模型：真实事物的模仿，主要因素、相互关系、系统结构。
♦形象模型：如地球仪、沙盘、风洞♦模拟模型：建港口，模拟船只到达。
学生模拟企业管理系统运行。
♦数学模型：用符号或数学工具描述现实系统。
第一章绪论一运筹学的发展历史1学科起源：二战期间英美等国军事部门集中多学科人员，研究提高武器系统效能，如反空袭雷达控制系统，使雷达和高炮相配合。
诺将物理学家布莱克特（Blackett）领导研究小组“Operational Research”，多学科构成（布莱克特马戏团）。
战争结束后专家转移到企业和院校——学科形成。
2我国古代的运筹思想：齐王赛马——齐王“上中下”，田忌“下上中”丁渭修皇宫——北宋真宗宰相丁渭（澶chan州之盟的主和派），主持皇宫失火后的修复。
宫前大街取土、引汴河运料、完工后回填废土。
3我国近代以来：50年代开始钱学森、许志国等引进运筹学理论，华罗庚教授回国后从事优选法和统筹法研究推广（烧茶壶的故事）4翻译：来自汉高祖“夫运筹帷幄之中,决胜千里之外,吾不如子房;填国家,抚百姓,给饷馈,不绝粮道,吾不如萧何;连百万之众,战必胜,攻必取,吾不如韩信。
”台湾地区直译为“运作研究”。
二运筹学的特点运筹学存在多种定义，如“依照给定目标和条件，从众多方案中选择最优方案的最优化技术”，学科特点：最优化、定量化1 多种专家的协作2 科学的方法：从实际情况出发，通过假设的模型打到一个符合实际的结论3 目的在于解决实际问题。
4 需要系统的信息资料5 需要建立模型——运筹学的核心问题就是通过合适的模型分析系统的未来情况6 对于复杂问题，需要计算机三运筹学的模型运筹学的主要特点是通过模型来描述和分析所认定范围内的系统状态。
分析过程包括：1 系统分析和问题描述。
认定问题的实质——社会经济问题复杂性、不可重复性，不同于具有可控性的物理模型（提高企业效益：开发市场？增加设备？加强研发？）。
明确系统的主要目标（利润最大化、市场占有率最大化、销售收入最大化？GDP增长、可持续协调增长？）、找出系统主要变量和参数、变化范围、相互关系及其对目标的影响。
分析问题的可行性：技术可行性—有无现成的运筹学方法？经济可行性—研究的成本和预期的效果，考虑运筹决策的时间和代价，要对研究问题的深度和广度作出一定限制操作可行性—研究人员的配备2 建立数学模型——要尽可能简单；要能完整的描述所研究的系统。
运筹学讲义《管理运筹学》1、运筹学的工作步骤(1)提出和形成问题．(2)建立模型．(3)求解．(4)解的检验．(5)解的控制．(6)解的实施.2、运筹学模型三种基本形式：(1)形象模型(2)模拟模型(3)符号或数学模型构模的五种方法和思路： (1)直接分析法 (如线性规划)(2)类比法（手机的普及与电视机的普及）(3)数据分析法（如汽车销售量预测模型）(4)试验分析法（销售量与价格之间的关系模型）(5)想定(构想)法（销售与心理）3、如何将线性规划问题的一般形式化为标准形式：1.如果问题是求目标函数的最小值，求min f＝∑Cjxj则可先将目标函数乘（-1），化为求极大值问题，即求 max Z=－f=－∑Cjxj2.如果有某个bk≤0，则可将该等式两边均乘以(－1)，使右端常数项bk=－bk≥03.如果第k个约束条件是∑akjxj≤bk,引入松弛变量sk≥0 , 将它写成∑akjxj+sk＝bk如果第l个约束条件是∑aljxj≥bl则引入剩余变量(也可称为松弛变量)sl≥0，将它写成∑aljxj—sl=bl 且使松弛变量和剩余变量在目标函数中的系数为零。
4.如果对某个变量xj没有非负限制(这种变量称为自由变量或无约束变量)，则引进两个非负变量xj′，xj″，令xj＝xj′－xj″代人目标函数和约束条件中，可将它化为对全部变量都有非负限制的问题。
4、①目标函数为变量的线性函数，约束条件也为变量的线性等式或不等式的模型称之为线性规划。
②如果目标函数是变量的非线性函数，或约束条件中含有变量非线性的等式或不等式的数学模型则称之为非线性规划。
③满足所有约束条件的解称为该线性规划的可行解。
④把使得目标函数值最大(即利润最大)的可行解称为该线性规划的最优解,此目标函数值称为最优目标函数值，简称最优值5、图解法的启示1．最优解：如果某一个线性规划问题有最优解，则一定有一个可行域的顶点对应一个最优解。
（一般为封闭可行域凸集）2．无穷多个最优解：若将上例中的目标函数变为求maxZ=50x1+50x2则代表目标函数的直线平移到最优位置后将和直线x1+x2=300重合。
运筹学课程讲义第一部分 线性规划 第一章 线性规划的基本性质 1.1 线性规划的数学模型一、 线性规划问题的特点胜利家具厂生产桌子和椅子两种家具。
桌子售价50元/个，椅子售价30元/个。
生产桌子和椅子需木工和油漆工两种工种。
生产一个桌子需要木工4小时，油漆工2小时。
生产一个椅子需要木工3小时，油漆工1小时。
该厂每月可用木工工时为120小时，油漆工工时为50小时。
问该厂如何组织生产才能使每月的销售收入最大？213050m ax x x z +=⎪⎩⎪⎨⎧≥≤+≤+0,50212034212121x x x x x x 例：某工厂生产某一种型号的机床。
每台机床上需要 2.9m 、2.1m 、1.5m 的轴，分别为1根、2根和1根。
这些轴需用同一种圆钢制作，圆钢的长度为74m 。
如果要生产100台机床，问应如何安排下料，才能用料最省？二、 数学模型的标准型 1. 繁写形式 2. 缩写形式 3. 向量形式 4. 矩阵形式三、 任一模型如何化为标准型？1. 若原模型要求目标函数实现最大化，如何将其化为最小化问题？2. 若原模型中约束条件为不等式，如何化为等式？3. 若原模型中变量x k 是自由变量，如何化为非负变量？4. 若原模型中变量x j 有上下界，如何化为非负变量？⎪⎪⎩⎪⎪⎨⎧≥≤-=--≤+--≥-+----=无约束321321321321321,0,052010651535765max x x x x x x x x x x x x x x x z 令'''3'3''3'331'1,0,,,Z Z x x x x x x x =-≥-=-=⎪⎪⎩⎪⎪⎨⎧≥-=+-++=+-+-=+-+-+--+-++-=0,,,,,,,5201010651533507765min 7654''3'32'17''3'32'15''3'32'164''3'32'1765''3'32'1'x x x x x x x x x x x x x x x x x x x x x x x x Mx Mx x x x x x z 1. 2图解法该法简单直观，平面作图适于求解二维问题。
运筹学课程讲义第一部分 线性规划 第一章 线性规划的基本性质 1.1 线性规划的数学模型一、 线性规划问题的特点胜利家具厂生产桌子和椅子两种家具。
桌子售价50元/个，椅子售价30元/个。
生产桌子和椅子需木工和油漆工两种工种。
生产一个桌子需要木工4小时，油漆工2小时。
生产一个椅子需要木工3小时，油漆工1小时。
该厂每月可用木工工时为120小时，油漆工工时为50小时。
问该厂如何组织生产才能使每月的销售收入最大？213050max x x z +=⎪⎩⎪⎨⎧≥≤+≤+0,50212034212121x x x x x x 例：某工厂生产某一种型号的机床。
每台机床上需要 2.9m 、2.1m 、1.5m 的轴，分别为1根、2根和1根。
这些轴需用同一种圆钢制作，圆钢的长度为74m 。
如果要生产100台机床，问应如何安排下料，才能用料最省？二、 数学模型的标准型 1. 繁写形式 2. 缩写形式 3. 向量形式 4. 矩阵形式三、 任一模型如何化为标准型？1. 若原模型要求目标函数实现最大化，如何将其化为最小化问题？2. 若原模型中约束条件为不等式，如何化为等式？3. 若原模型中变量x k 是自由变量，如何化为非负变量？4. 若原模型中变量x j 有上下界，如何化为非负变量？⎪⎪⎩⎪⎪⎨⎧≥≤-=--≤+--≥-+----=无约束321321321321321,0,052010651535765max x x x x x x x x x x x x x x x z 令'''3'3''3'331'1,0,,,Z Z x x x x x x x =-≥-=-=⎪⎪⎩⎪⎪⎨⎧≥-=+-++=+-+-=+-+-+--+-++-=0,,,,,,,5201010651533507765min 7654''3'32'17''3'32'15''3'32'164''3'32'1765''3'32'1'x x x x x x x x x x x x x x x x x x x x x x x x Mx Mx x x x x x z 1. 2图解法该法简单直观，平面作图适于求解二维问题。
使用该法求解线性规划问题时，不必把原模型化为标准型。
一、 图解法步骤1. 由全部约束条件作图求出可行域2. 作出一条目标函数的等值线3. 平移目标函数等值线，作图求解最优点，再算出最优值二、 从图解法看线性规划问题解的几种情况1. 有唯一最优解2. 有无穷多组最优解3. 无可行解4. 无有限最优解（无界解）⎪⎩⎪⎨⎧≥≥+≥++=0,23431246min 21212121x x x x x x x x z 最优解)0,21(，最优值3直观结论：1）线性规划问题的可行域为凸集，特殊情况下为无界域（但有有限个顶点）或空集；2）线性规划问题若有最优解，一定可以在其可行域的顶点上得到。
1.3 线性规划的基本概念和基本定理一、 线性规划问题的基与解 可行解 最优解 基 基向量 非基向量 基变量 非基变量 基本解基本可行解 最优基本可行解 退化的基本解二、 几何意义上的几个基本概念 1. 凸集 2. 凸组合 3. 顶点三、 线性规划问题的基本定理定理1：若线性规划问题存在可行域，则其可行域是凸集。
引理1：线性规划问题的可行解T n x x x X ),,,(21 =为基本可行解的充要条件是X 的正分量对应的系数列向量是线性无关的。
定理2：线性规划问题的基本可行解对应于可行域的顶点。
引理2：K 是有界凸集，则任何一点X ∈K 可表示为K 的顶点的凸组合。
定理3：如果线性规划问题有有限最优解，则其目标函数最优值一定可以在可行域的顶点上达到。
四、 求解线性规划问题的基本思路在有限个基本可行解中寻找最优基本可行解。
找一个基本可行解（m 个线性无关的系数列向量），由其换到另一个基本可行解。
实质即为换基。
前提是保证新的基本可行解的目标函数值比原来的更优而不是更劣。
第二章 单纯形法它是求解线性规划最为成熟的算法。
胜利家具厂生产桌子和椅子两种家具。
桌子售价50元/个，椅子售价30元/个，生产桌子和椅子需要木工和油漆工两种工种。
生产一个桌子需要木工4小时，油漆工2小时。
生产一个椅子需要木工3小时，油漆工1小时。
该厂每月可用木工工时为120小时，油漆工工时为50小时。
问该厂如何组织生产才能使每月的销售收入最大？ 213050max x x z +=⎪⎩⎪⎨⎧≥≤+≤+0,50212034212121x x x x x x 将其变形，得⎪⎩⎪⎨⎧≥=++=++0,,,502120344321421321x x x x x x x x x x 将43,x x 对应的单位矩阵作为初始可行基。
令43,x x 为基变量，21,x x 为非基变量。
原模型变形为 213050max x x z +=⎪⎩⎪⎨⎧≥--=--=0,,,250341204321214213x x x x x x x x x x 如果令非基变量21,x x 等于零，得一个基本可行解（0，0，120，50），对应的目标函数值z = 0最优性检验：该解是否最优？显然不是。
经济意义分析：21,x x 等于零意味着家具厂不开工生产，销售收入为零，资源未得到充分利用。
数学角度分析：非基变量21,x x 前的系数都为正，表明目标函数值有增加的可能。
只要将系数为正的非基变量与某一基变量对换，当换入变量的值增加时，目标函数值就可能增加。
换基迭代：寻找下一个可行解需要进行换基迭代。
换基后需满足：（1）新的解仍是基本可行解；（2）目标函数得到改善。
选择入基变量：21,x x 系数均为正。
对求目标函数极大化的问题，我们希望目标值增加得越快越好，因此应选系数最大的1x 入基。
选择出基变量：1x 入基后，其值从零增加并引起其他变量取值的变化。
由问题的典则表达式和变量必须取正值的条件，得下列不等式关系：x -2x -50x 03x -4x -120x 214213≥=≥=因迭代后2x 仍为取零值的非基变量，上式可简化为2500412011≥-≥-x x很明显，只有选()252/50,4/120min 1==x 时，才能使上述不等式成立，并使基变量4x 变为零，正好满足非基变量必须为零的条件，所以可令4x 出基，新的典则方程变为42123150231204x x x x x x --=-=+化简后得4234212205.05.025x x x x x x +-=--=代入目标函数可得 4222551250x x z -+=得到下一个基本可行解（25，0，20，0），并完成了第一次迭代。
新解是最优解吗？需进行最优检验。
由于目标函数中2x 的系数仍为正，说明多生产椅子仍有利可图，该解仍不是最优解。
再次迭代。
2x 入基，3x 出基，换基后典则形式变为4324314332205.15.0151551350x x x x x x x x z +-=-+=--=第三个基本可行解为（15，20，0，0），松弛变量都已为零，表明资源已得到充分利用；非基变量在目标函数中的系数全为负值，说明目标函数已无法进一步改善，因此该解已是最优解。
2.1 单纯形法原理一、 构造初始可行基1. 引入附加变量，把数学模型化为标准型2. 若约束条件中附加变量的系数是-1或原约束即为等式，则必须引入人工变量，以构成初始可行基3. 目标函数中，附加变量的系数为0，而人工变量的系数为M （很大的正数）二、 求出一个基本可行解1. 用非基变量表示基变量和目标函数式()()5524313212252834x x x M x x x M x x x +--++--+++ ()()()M Mx Mx x M x M x M 7383454321+++-+-+-= 2. 求出一个基本可行解及相应的z 值三、 最优性检验1. 最优性检验的依据—检验数j σ2. 最优解判别定理：若在极小化问题中，对于某个基本可行解，所有检验数j σ≥0，且人工变量为0，则这个基本可行解是最优解。
对于极大化问题，只要把上述定理中的j σ≥0改成j σ≤0即可。
这里的检验数j σ即为（c j -z j ）。
3. 无穷多最优解判别定理：若在极小化问题中，对于某个基本可行解，所有检验数j σ≥0，又存在某个非基变量的检验数为0，且人工变量为0，则线性规划问题有无穷多最优解。
4. 无可行解情况若在极小化问题中，对于某个基本可行解，所有检验数j σ≥0，但人工变量≠0，则该线性规划问题无可行解。
四、 基变换1. 基本可行解的改进定理2. 换入变量的确定3. 换出变量的确定最小非负比值规则 θ=b r /a rk =imin {b i /a ik |a ik >0} 在单纯形法迭代中，基变换带来可行域顶点的变换，且相邻两次迭代所对应的顶点也是相邻的。
4. 无有限最优解（无界解）判定定理：若在极小化问题中，对于某个基本可行解，有一个非基变量的检验数k σ<0，但P k 列中没有正元素，且人工变量为0，则线性规划问题无有限最优解（具有无界解）。
2.2 单纯形法的表格形式一、 构造初始可行基，并计算检验数j σj σ =c j -z jz j =(c 1,c 2,…,c m )•P j =(C B )•P 'j二、 从表中找到基本可行解和相应目标函数值 三、 最优性检验 四、 基变换1. 换入变量的确定 负检验数中最小2. 换出变量的确定 最小非负比值规则3. 主元素的确定 换入元素所在列和换出元素所在行交点处的元素4. 取主变换通过矩阵行的初等变换，把换入向量变换为单位列向量。
即基变换，亦即单纯形法的一次迭代。
2. 3 大M 法和两阶段法根据处理人工变量的方法不同，单纯形法的两种常见形式。
大M 法也叫罚函数法，前已介绍。
两阶段法将线性规划问题的求解分为两个阶段。
第一阶段：判断原线性规划问题是否有可行解。
该阶段所要求解的线性规划问题的约束条件即原问题的约束条件，而目标函数取全部人工变量之和，求其最小值。
若求解结果是上述目标函数的最小值为0，则说明所有人工变量都能退出基，原问题有可行解，且第一阶段的最终单纯型表上的基本可行解就是原问题的一个基本可行解。
若求解的结果是上述目标函数的最小值大于0，则说明最终人工变量不能完全退出基，原问题无可行解，应停止计算。
第二阶段：求解原线性规划问题的最优解。
以第一阶段的最终单纯型表为基础，去掉其中的人工变量列，把目标函数换成原问题的目标函数，并修正因c j 改变而改变的(C B )T 、j σ和-z 。
