下载文档原格式
运筹学知识点要求运筹学知识点要求第一部分结论1、运筹学的特点（1）以最优性或合理性为核心。
（2）以数量化、模型化为基本方法。
（3）具有强烈的系统性、交叉性特征。
（4）以计算机为重要的技术支持。
2、运筹学模型求解方法：知道迭代算法的原理步骤。
3、运筹学模型（1）运筹学模型：使用较多的是符号或数学模型，大多数为优化模型。
（2）模型的一般结构（3）模型的三大要素决策变量、目标函数及优化方向、约束条件。
（4）了解模型的分类4、建立优化模型解决实际问题（1）要求能对较简单的实际问题建立优化模型。
主要涉及：一般线性规划模型，整数（特别是0－1规划）规划模型。
5、了解运筹学运用领域。
第二部分线性规划1、线性规划模型的几种表示形式及特点2、线性规划模型的标准形式及如何标准化3、线性规划问题各种解的概念及关系（关系图示）（可行解、非可行解、基本解、基本可行解、最优解，基本可行解的个数小于等于）4、线性问题有关解的基本定理（主要是概念理解）（1）不一定都有最优解（2）若有，一定会在基本可行解上达到（3）基本可行解的个数有限小于等于（4）并非所有最优解都是基本可行解（5）了解凸集与凸组合的概念，理解两个最优解的凸组合都是最优解。
（6）可行解为基本可行解的充要条件5、线性规划单纯形法（1）制作初始单纯表（注意非基变量检验系数的求法，特别注意求有待定系数时的检验系数）（2）各种解的判别条件，对于最大化目标函数问题，包括：唯一最优解：有最优解无穷多最优解存在一个k 有：（或称之为线性规划问题存在可择最优解）无界解，存在k 有：（3）线性规划问题求解结果中解的情况有最优解（唯一最优解、无穷多最优解），无界解，无可行解（4）基变换中入基变量的确定A 、入基变量的必要条件（）B 、最速上升准则的理解，不是使目标函数改进最大，而是使目标函数改进速度最大。
m nC m nC 0<j σ0≤j σ0≤j σ0=j σ0,0'≤>k k p 且σ0≥j σ（5）最小比值确定出基变量的目的：保证基变换后新的基本解是可行的。
《运筹学》教案-目标规划数学模型第一章：目标规划概述1.1 目标规划的定义与意义1.2 目标规划与其他规划方法的区别1.3 目标规划的应用领域1.4 目标规划的发展历程第二章：目标规划的基本原理2.1 目标规划的基本假设2.2 目标规划的数学模型2.3 目标规划的求解方法2.4 目标规划的评估与决策第三章：目标规划的数学模型3.1 单一目标规划模型3.2 多目标规划模型3.3 带约束的目标规划模型3.4 动态目标规划模型第四章：目标规划的求解方法4.1 线性规划求解方法4.2 非线性规划求解方法4.3 整数规划求解方法4.4 遗传算法求解方法第五章：目标规划的应用案例5.1 生产计划目标规划案例5.2 人力资源规划目标规划案例5.3 投资组合目标规划案例5.4 物流配送目标规划案例第六章：目标规划的高级应用6.1 目标规划在供应链管理中的应用6.2 目标规划在项目管理中的应用6.3 目标规划在金融管理中的应用6.4 目标规划在能源管理中的应用第七章：目标规划的软件工具7.1 目标规划软件工具的介绍7.2 常用目标规划软件工具的操作与应用7.3 目标规划软件工具的选择与评估7.4 目标规划软件工具的发展趋势第八章：目标规划在实际问题中的应用8.1 目标规划在制造业中的应用案例8.2 目标规划在服务业中的应用案例8.3 目标规划在政府决策中的应用案例8.4 目标规划在其他领域的应用案例第九章：目标规划的局限性与挑战9.1 目标规划的局限性分析9.2 目标规划在实际应用中遇到的问题9.3 目标规划的发展趋势与展望9.4 目标规划的未来研究方向10.1 目标规划的意义与价值10.2 目标规划在国内外的发展现状10.3 目标规划在未来的发展方向10.4 对运筹学领域的发展展望重点和难点解析重点环节一：目标规划的数学模型补充和说明：在讲解目标规划的数学模型时，重点关注单一目标规划模型和多目标规划模型的构建。
运筹学的基本理论与方法运筹学（Operations Research）是一门应用数学学科，旨在通过量化建模和优化方法，解决实际问题和做出最优决策。
本文将介绍运筹学的基本理论与方法，包括问题建模、优化模型、经典算法等方面。
一、问题建模运筹学的第一步是把实际问题转化为数学模型，以便进行分析和求解。
问题建模通常涉及以下几个方面：1. 目标：明确问题的目标是什么，如最大化利润、最小化成本、优化资源利用率等。
2. 决策变量：确定可以控制或调整的变量，即决策变量，如生产数量、采购量、分配方案等。
3. 约束条件：考虑问题的限制条件，如资源限制、技术限制、时间限制等。
二、优化模型基于问题建模的基础上，可以建立相应的优化模型，常见的几种常用优化模型如下：1. 线性规划：线性规划是最经典的优化模型之一，目标函数和约束条件都是线性的。
线性规划可以通过诸如单纯形法、内点法等算法求解。
2. 整数规划：整数规划是线性规划的拓展，决策变量需要取整数值。
整数规划一般通过分支定界法、割平面法等算法求解。
3. 动态规划：动态规划适用于具有决策阶段和状态转移的问题，通过将问题分解为子问题，利用最优子结构性质，建立递推关系来求解。
4. 近似算法：对于复杂优化问题，精确求解往往是不可行的，此时可以采用近似算法，如启发式算法、模拟退火算法、遗传算法等。
三、经典算法运筹学中有一些经典的算法常用于求解各类优化问题，下面介绍几个典型的算法：1. 单纯形法：单纯形法是一种求解线性规划问题的经典算法，通过不断在可行域内移动以达到最优解。
2. 分支定界法：分支定界法通常用于解整数规划问题。
通过不断划分问题的可行域，并对每个子问题求解，最终得到整数规划的最优解。
3. 模拟退火算法：模拟退火算法是一种全局优化算法，通过模拟金属退火过程来避免陷入局部最优解。
4. 遗传算法：遗传算法是一种模拟生物进化过程的优化算法，通过选择、交叉、变异等操作来搜索最优解。
四、应用领域运筹学方法在各个领域都有广泛应用，包括但不限于以下几个方面：1. 生产与物流：优化生产计划、供应链管理、仓储布局等，以提高生产效率和降低成本。
1、污水处理问题环保要求河水含污低于2‰，河水可自身净化20%。
问：化工厂1、2每天各处理多少污水，使总费用最少？分析：化工厂1处理污水x1万m3, 化工厂2处理污水x2万m3。
min z = 1000x1 + 800x2(2 - x1)/500 ≤ 2/1000 [(1 - 0.2)(2 - x1) + 1.4 - x2]/(500 + 200) ≤ 2/1000 x1 ≤ 2 x2 ≤ 1.4 x1，x2 ≥ 0这里min z:表示求z 的最小值。
松弛变量:在线性规划中，一个“≤”约束条件中没有使用的资源或能力称之为松弛变量 位于直线①、 ②的交点上，故可知设备台时和材料A 的松弛变量都为0；交点不在直线③上，材料B 的松弛变量大于0.剩余变量:在线性规划中，对于“≥”约束条件，可以增加一些代表最低限约束的超过量，称之为剩余变量。
化为标准型min z = -x1+2x2-3x3x1+ x2+ x3 ≤ 7 ① x1- x2+ x3 ≥ 2 ② -3x1+ x2+2x3 = 5 ③ x1,x2 ≥ 0，x3无约束 令x3 = x3’-x3”，x3’,x3” ≥ 0；①式加上一个松弛变量x4；②式减去一个剩余变量x5； 令z ’ = -zmax z ’ = x1- 2x2 + 3(x3’ - x3”) + 0x4 + 0x5 x1 + x2 + (x3’ - x3”) + x4 = 7 x1 - x2 + (x3’ - x3”) - x5 = 2 -3x1 + x2 + 2(x3’ - x3”) = 5 x1,x2,x3’,x3”,x4,x5 ≥ 0在约束条件常数项中增加一个单位而使最优目标函数值得到改进的数量称之为这个约束条件的对偶价格。
当某约束条件中的松弛变量（或剩余变量）不为零时，这个约束条件的对偶价格就为0.200万m3 500万m32万m3 1.4万化工厂1 化工厂2 1000元/万m3800元/万m32、人力资源分配的问题例1．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?解：设xi 表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。
教材习题答案1.2工厂每月生产A、B、C三种产品，单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表 1 —22所示.表1 —22【解】设X I、X2、X3分别为产品A、B、C的产量，则数学模型为1.3建筑公司需要用6m长的塑钢材料制作A、B两种型号的窗架. 两种窗架所需材料规格及数量如表1 —23所示：第二步：建立线性规划数学模型设X j (j=1,2, ••,• 14)为第j种方案使用原材料的根数，则(1)用料最少数学模型为用单纯形法求解得到两个基本最优解X ⑴=(50 ,200 ,0 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=534X ⑵=(0 ,200 ,100 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,150 ,0 ,0 );Z=534(2)余料最少数学模型为用单纯形法求解得到两个基本最优解X ⑴=(0 ,300 ,0 ,0,50 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料550 根X(2)=( 0 ,450 ,0 ,0,0 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料650 根显然用料最少的方案最优。
1.7图解下列线性规划并指出解的形式：maxZ 2x1 x2X x2 1X 3X2 1X1,X 2 0【解】最优解X =( 1/2, 1/2);最优值Z= —1/2【解】最优解X =( 3/4, 7/2);最优值Z= — 45/4min Z3x 1 2x 2x 12x 2 11 x1 4x2 10(3)12x 1 x 2 7x 13x 2 1 x 1,x 2 0【解】 最优解 X =(4, 1)；最优值 Z=—10 maxZ x 1 x 2 3x 1 8x 2 12(4)x 1 x 2 2 2x 1 3 x 1,x 2 0【解】 最优解 X =( 3/2, 1/4)；最优值 Z=7/4 minZ x 1 2x 2 x 1 x 2 2(5)x 1 3 【解】 最优解 X =( 3, 0)；最优值 Z=3x 2 6 x 1,x 2 0 maxZ x 1 2x 2 x 1 x 2 2(6)x 1 3 x 2 6 x 1,x 2 0【解】 无界解。
第四章 运筹学模型本章教学重点是： 线性规划模型 目标规划模型 运输模型及其应用 图论模型 最小树问题 最短路问题 最大流问题与最小割 复习要求1．进一步理解基本建模过程，掌握类比法、图示法以及问题分析、合理假设的内涵。
2．进一步理解数学模型的作用与特点。
本章复习重点是线性规划模型、运输问题模型和目标规划模型。
具体说来，要求大家会建立简单的线性规划模型，把实际问题转化为线性规划模型的方法要掌握，当然比较简单。
运输问题模型主要要求善于将非线性规划模型转化为运输规化模型，这种转化后求解相当简单。
你至少把一个很实际的问题转化为用表格形式写出的模型，至于求解是另外一回事，一般不要求。
目标模型一般是比较简单的线性规模模型在提出新的要求之后转化为目标规划模型。
这是主要的考虑方向。
另外，关于图模型的问题涉及到最短路问题，具体说来用双标号法来求解一个最短路模型。
这之前恐怕要善于将一个实际问题转化为图模型。
还有一个最小数的问题，该如何把一个网络中的最小数找到。
另外在个别场合可能会涉及一笔划问题。
1．营养配餐问题的数学模型为n n x C x C x C Z 211m in),,2,1(0,,,22112222212111212111n j x b x a x a x a b x a x a x a b x a x a x a t s j mn mn m m n n n n或更简洁地表为nj j jx CZ 1min),,2,1,,2,1(01n j m i x b x a t s jnj i j ij 其中的常数C j 表示第j 种食品的市场价格，a ij 表示第j 种食品含第i 种营养的数量，b i 表示人或动物对第i 种营养的最低需求量.例1 医院为病人配制营养餐，要求每餐中含有铁不低于50单位，蛋白质不低于40单位，钙不低于42单位．假设仅有两种食品A 和B 可供配餐，相关数据见下表．试问，如何购买两种食品进行搭配，才能即使病人所需营养达到需求，又使总花费最低？解：设购买食品A和B依次为x1和x2（kg），则有营养最低要求满足：10x1+5x2≥50 （铁含量）5x1+8x2≥40 （蛋白质含量）6x1+5x2≥42 （钙含量）总花费数记为Z，则有数学模型2134min xxZs.t.,)3.3(,4256)2.3(,4085)1.3(,5051021212121xxxxxxxx用图解法求解上述问题．首先以x1,x2为坐标轴，建立平面直角坐标系（如图3-10），由于x1,x2均非负，故只画出了第一象限．其次，将其余约束条件几何化．条件（3.1）表示的是一个半平面，先画出直线10x1+5x2=50,因为10x1+5x2≥50，故直线（3.1）的上方区域即条件（3.1）所满足的x1,x2的取值范围；同理将条件（3.2）、（4.3）也几何化，并注意到几个条件要同时满足，便求得一个以顶点A、B、C、D为顶点的右上方无界的五边形区域1x ABCD2x.这个区域内的任一点（x1,x2）都是图3—10图3—11最后，为了求出最优解，将目标函数也进行几何化，有11)4.3(33412Z x x称为目标函数直线族，因为其中的Z 作为参数出现.易见，随着Z 的逐渐增大，目标函数直线（3.4）向右上方平行移动．也就是说，随着目标函数直线的逐渐往右上方平移，Z 的值越来越大，反之，Z 的值越来越小（如图3-11）.又原问题是求函数Z 的最小值，故应令目标函数直线尽可能往左下方平移．但这种平移是有限制的，即点（x 1,x 2）必须在可行域内.于是两者的结合便可确定本例的最优解.通过上述斜率关系分析可知目标函数直线与直线（3.1）和直线（3.3）的交点（顶点C ）相切，即直线（3.1）与直线（3.3）的交点即最优解点.于是问题就变成了求解方程组.4256,505102121x x x x 易解得x 1=2,x 2=6为最优解，通常记作：Tx )6,2(62对应的目标函数值称为最优值，记作 Z *=262．运输问题模型运输问题也是一种线性规划问题，只是决策变量设置为双下标变量. 假如问题具有m 个产地和n 个销地, 第i 个产地用A i 表示,其产量为a i (i =1,2,…，m )，第j 个销地用B j 表示,其销量为b j (j =1,2,…,n ), 从A i 运往B j 的运价为c ij , 而mi nj jiba11表示产销平衡。
那么产销平衡运输问题的一般模型可以写成为mi nj ij ij x c Z 11minn j m i x b x a x t s ij mi j ij nj i ij ,,2,1,,2,1011例2 某公司经营的一种产品拥有四个客户，由公司所辖三个工厂生产，每月产量分别为3000，5000，4000件。
该公司已承诺下月出售4000件给客户1，出售3000件给客户2以及至少1000件给客户3。
客户3与客户4都想尽可能多购剩下的产品。
已知各工厂运销一件产品给客户1、2、3、4可得到的净利润是：工厂1为65、63、62、64元；工厂2为68、67、65、62元；工厂3为63、60、59、60元。
问该公司应如何拟订运销方案，才能在履行诺言的前提下获利最多？上述问题是否可以转化为运输模型加以处理？若是，请写出对应的表格形式的运输模型（即产销平衡运价表），否则说明理由。
解：可以。
产销平衡表如下：例3 设有一批产品要从三个生产地A 1、A 2和A 3运往四个销售地B 1、B 2、B 3和B 4（生产地和销售地以后简称为产地和销地）。
三个产地运往四个销地的运价，三个产地的产量和四个销地的需求量如下表所示，试策划一个运输方案，使得在满足需求条件下，总运输费用最少。
解：以x ij 表示从第i 个产地运送到第j 个销地的运量,则依供需关系有下列约束条件: 供给方面: 714131211 x x x x424232221 x x x x 934333231x x x x 需求方面: 3312111 x x x 6322212 x x x 5332313 x x x 6342414 x x x非负性: x ij ≥0 4,3,2,1;3,2,1 j i 总运费: 3412115113m in x x x Z将上述目标函数与约束条件合在一起便构成所谓具有三个产地和四个销地的产销平衡运输问题的数学模型.下面用表上作业法求解。
首先，用最小元素法确定初始方案。
表x.如表4－5所示的运价中,由于1最小,于是决定由A2供应B1，于是第一个基变量被确定为21再看供求关系,B1需要3吨,而A2产量为4吨,于是尽量满足需求,由A2供应B13吨.在运价1的右下角写上③.由于B1的需求已满足,故A1,A3不必再向B1供应,于是在运价3与7右下角打×,表示变量x11与x31被确定为非基变量.在剩下的9个运价中再找最小运价为2,并按上述方法确定第二个基变量x23=1，同时变量x22与x24被确定为非基变量.依此类推，便可确定4个基变量和6个非基变量如表4－4此时，只有两个变量x14和x34未被确定，但它们必须成为基变量.于是根据产销平衡关系确定10下画③，5下画③.终于得到初始基变量组及其取值为:x13=4, x14=3, x21=3, x23=1, x32=6, x34=3, 其余x ij=0即为初始运输方案(表4－8),其总运费也在表上计算为Z(0)=3×4+10×3+1×3+2×1+4×6+5×3=86(拾元)其次，方案的最优性检验——闭回路法检验一个方案的最优性说到底是看此方案是否还有改进的余地.而方案是否有改进余地，关键是看非基变量中是否有能转变为基变量（取值大于零）而使目标值进一步改善，若有，则称这个变量为进基变量. 如x11增加1, 按照产销平衡原则, x13必须减值为3, 否则与产量为7矛盾.而当x13减值为3时, x23必须增值一个单位, 否则又与销量为5矛盾, 依此又知, x21需减少一个单位.以上变化导至总运费发生的变化值为λ11=3－３+2－１=1＞0这就是说,令x11变为基变量,总运费将增加1个单位,故此举不合适。
由此可知,λ11具有检验x11进基是否能改善目标值的作用,称为非基变量x11的检验数.如果非基变量的检验数大于零,则该变量进基不合适;若检验数等于零, 则该变量进基也无助于目标值的改进.由此可推出:若所有非基变量的检验数均≥0, 则目前这个方案便没有改进的余地, 即已是最优方案.反之,若至少有一个非基变量的检验数＜0, 则目前的方案便非最优方案.这就是运输问题的方案最优性检验原理.值得注意的是,在求非基变量x 11的检验数时,恰好是在不存在闭回路的基变量组内引进一个非基变量后所形成的唯一闭回路中进行的相应运算:以进基变量为第一个顶点,按逆时针(或顺时针)将闭回路的奇数顶点运价赋以“+”号,偶数顶点运价赋以“－”号所形成的代数和便是该变量的检验数.按此法则,可求得所有非基变量的检验数如下: λ11=3－３+2－1＞0, λ12=11－10+5－4＞0λ22=9－2+3－10+5－４＞0,λ24=８－10+３－２＝－１＜0 λ31=7－5+10－3+2－1＞0, λ33=10－5+10－3＞0 由于λ14＜0,故初始方案非最优方案.然后，用闭回路法调整方案由λ24＜0,故令x 24进基,按产销平衡原则在相应的闭回路上进行调整.注意到基变量总数量m +n -1个,则应令原基变量组成员之一出基(取值为0).易见,令x 24=min{该闭回路上偶数顶点运量}={1,3}=1,便知新基变量x 24取值为1,被保留下来的基变量为 x 13=4+1=5,x 14=3－1=2,x 21=3,x 32=6,x 34=3,其余为非基变量,其中x 23=1－1=0为新增非基变量.重新画一张表4－9,标上新基变量及其取值,便得新运输方案表,总运费为z =3×5+10×2+1×3+8×1+4×6+5×3=85(拾元).那么这个方案是否最优方案?返回2)步再检验即可. 表４－6现求新方案中非基变量的检验数:λ11=3－10+8－1=0, λ12=11－10+5－4＞0, λ22=9－8+5－４＞0, λ31=7－1+8－5＞0, 33=10－5+10－3＞0, λ23=2－8+10－3＞0,可见所有λij ≥0,故表4－9所给方案已是最优方案, 用运销图画在下面:A 1 A 2 A 3图4-13．目标规划模型例4 某工厂生产两种产品A 、B 分两班生产，每周生产总时间为80小时，两种产品的预测销售量、生产率和赢利如下表2 B3 5B 43 1 B 1 B4 6 3 B 2 B 4制定一合理的生产方案，要求依次满足下列目标： （1）充分利用现有能力，避免设备闲置； （2）周加班时间限制在10小时以内；（3）两种产品周生产品量应满足预测销售，满足程度的权重之比等于它们单位利润之比；（4）尽量减少加班时间． 解： （1）建立模型设：①每班上班时间为8小时，在上班时间内只能生产一种产品； ②周末加班时间内生产哪种产品不限；③生产A 产品用x 班，生产B 产品用y 班，周加班时生产A 产品用x 1小时，生产B 产品用y 1小时．则有且为整数0,,,101:2148:987084581011111111y x y x y x x x y y x x y y y x （2）求解现在求满足（1）中第2，3个方程可看出：8 x ，5 y ； 将（1）中的第1个方程代入第4个方程得：1179720128y x y 现在就是在满足5 y ，1011 y x 条件下，使上式两端的取值尽量接近．显然5 y ，01 x ，101 y因此 5 x制定方案为，生产A ，B 两种产品所占总时间各一半，周加班10小时全用于生产产品B ．4．最短路问题的数学模型许多实际问题都归结为最短路问题，例如两地间的管道铺设，线路安装，道路修筑，运路选取等等；再如工厂布局，设备更新等问题也可转化为最短路问题。
