运筹学复习大纲.doc
11页
运筹学课程的知识体系吴思杰计算生物所运筹学是系统工程的最重要的理论基础之一运筹学所研究的问题，可简单地归结为一句话：“依照给定条件和目标，从众多方案中选择最佳方案”故有人称之为最优化技术运筹学在工商管理中的应用涉及几个方面：生产计划，运输问题，人事管理，库存管理，市场营销，财务和会计，另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等运筹学的具体内容包括：规划论（包括线性规划、非线性规划、整数规划和动态规划）、图论、决策论、对策论、排队论、存储论、可靠性理论等对于规划问题，来源于生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大.）规划问题数学模型有三个要素:1.决策变量，2.目标函数，3.约束条件接下来将介绍规划论中的线性规划、非线性规划、整数规划和动态规划线性规划线性规划：运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。
为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据线性规划的特征：（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式线性回归的数学模型：max（min）Z=工exjjj=1工ax<（=・>）b（i=1・2・・・m）ijjij=1x>0（j=1-2…n）j线性规划问题的求解方法：1）图解法:两个变量、直角坐标个变量、立体坐标其优点：只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点缺点是只适用于两个变量2）单纯形法：适用于任意变量、但必需将一般形式变成标准形式线性规划问题的标准形式：maxZ=l^cxj=1^^ax=bijjii=1,2,…,m特点：x>0,j=1,2,...,n目标函数求最大值(有时求最小值)约束条件都为等式方程，且右端常数项b都大于或等于零i(1) 决策变量xj为非负j具体步骤：(1) 将问题化为标准型，加入松驰变量x3、x4则标准型为:(2) 求出线性规划的初始基可行解，列出初始单纯形表进行最优性检验:如果表中所有检验数b.<0，则表中的基可行解就是问题的最优解,计算停止。
否则继续下一步j从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表确定换入基的变量选择b.>0，对应的变量X.作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即：bk=max{b.1b.>0}，其对应的xKJJk作为换入变量确定换出变量根据下式计算并选择e，选最小的e对应基变量作为换出变量0=minA-a>0»Laikik用换入变量xk替换基变量中的换出变量，得到一个新的基对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表3) 重复(3)、(4)步直到计算结束为止单纯形法的进一步讨论：人工变量法：通过引入人工变量获得初始可行基解的判别：(1) 唯一最优解判别：最优表中所有非基变量的检验数非零,则线规划具有唯一最优解2) 多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解(或无穷多最优解)3) 无界解判别：某个入k>0且a“W0(i=1,2,…,m)则线性规划具有无界解4) kik无可行解的判断：当用大M单纯形法计算得到最优解并且存在Ri〉0时，则表明原线性规划无可行解5) 退化解的判别：存在某个基变量为零的基本可行解。
3) 对偶单纯形法是求解线性规划的另一个基本方法它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法不要简单理解为是求解对偶问题的单纯形法对偶单纯形法基本思路：找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断X是否可行(X为非负)，BB若否，通过变换基解，直到找到原问题基可行解(即X为非负)，这时原问题与对偶问题B同时达到可行解，则可得最优解线性规划的限制：一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型1) 要求解问题的目标函数能用数值指标来反映，且为线性函数2) 存在着多种方案3) 要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述线性规划在管理中的应用：人力资源分配问题，生产计划问题，套裁下料问题，配料问题运输规划问题运输问题:在经济建设中，经常碰到大宗物资调运问题如煤，钢铁，木材，粮食等物资，在全国有若干个生产基地，根据已有的交通网，应如何制订调运方案，将这些物质运到各消费地点，而总运费最小这一类问题的属于特殊的线性规划问题，它们的约束方程组的系数矩阵具有特殊的结构，具有比单纯形法更为简便的求解方法运输规划问题的数学模型:A、A、…、A表示某物资的m个产地；B、B、…、B表示某物质的n个销地；a表12m12ni示产地A的产量；b表示销地B的销量；c表示把物资从产地A运往销地B的单位运ijjijij价。
设x为从产地A运往销地B的运输量，得到下列一般运输量问题的模型：iimnminz=乙乙cxi=1j=1Ex=aijis.«Ex=bi=1x>0,ijijiji=1,…,mj=1,…,ni=1,…,m;j=1,…,n变化：（1）有时目标函数求最大如求利润最大或营业额最大等；（2）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束）；（3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）运输问题求解方法：运输问题属于特殊的线性规划问题，它们的约束方程组的系数矩阵具有特殊的结构，具有比单纯形法更为简便的求解方法：表上作业法表上作业法是一种求解运输问题的特殊方法其实质是单纯形法歩骤描述方法第一步求初始基行可行解（初始调运方案）最小元素法*兀索差额法、第二步求检验数并判断是否得到最优解当非基变量的检验数硯全都非负时得到最优解，若存在检脸数5产6说明还没有达到最优’转第二步.闭回路法和位势法第三步调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转人第二步表上作业法计算中的问题：若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取o<0中最小者对应的变量为换入ij变量。
无穷多最优解：产销平衡的运输问题必定存最优解如果非基变量的O=0,则该问题ij有无穷多最优解运输问题的应用：生产与储存问题，产销不平衡的运输问题目标规划目标规划：目标规划是性规划的基础上，为适应经济管理多目标决策的需要而由线性规划逐步发展起来的一个分支由于现代化企业内专业分工越来越细，组织机构日益复杂，为了统一协调企业各部门围绕一个整体的目标工作，产生了目标管理这种先进的管理技术目标规划是实行目标管理的有效工具，它根据企业制定的经营目标以及这些目标的轻重缓急次序，考虑现有资源情况，分析如何达到规定目标或从总体上离规定目标的差距为最小线性规划模型相比于目标规划存在的局限性：(1) 要求问题的解必须满足全部约束条件，实际问题中并非所有约束都需要严格满足2) 只能处理单目标的优化问题实际问题中，目标和约束可以相互转化3) 线性规划中各个约束条件都处于同等重要地位，但现实问题中，各目标的重要性即有层次上的差别，同一层次中又可以有权重上的区分4) 线性规划寻求最优解，但很多实际问题中只需找出满意解就可以因此，针对这种缺陷，在应对目标规划问题中，进行如下改善：(1) 设置偏差变量，用来表明实际值同目标值之间的差异。
d+超出目标的偏差，称正偏差变量d-未达到目标的偏差，称负偏差变量正负偏差变量两者必有一个为02) 当实际值超出目标值时：d+〉0,d-=0;当实际值未达到目标值时：d+=0,d->0;当实际值同目标值恰好一致时：d+=0,d-=0;故恒有d+Xd-=0统一处理目标和约束对有严格限制的资源使用建立系统约束，数学形式同线性规划中的约束条件对不严格限制的约束，连同原线性规划建模时的目标，均通过目标约束来表达若希望甲的产量不低于乙的产量，即不希望d->0，用目标约束可表为：min{d-}
目标规划数学模型：minZ=工P(为①一d-+w+d+)厂l=1llkkk=1lkk工CX+d——d+=g(k=1.2…K)kjjkkkj=1<工ax<(=.>)b(i=1.2…m)ijjij=1x>0(j=1.2…n)jd+.d->0(k=1.2…K)kk其中：gk为第k个目标约束的预期目标值，®l-和①；为r优先因子对应各目标的权系数klklkl目标规划求解方法：1) 图解法：图解法适用两个变量的目标规划问题，但其操作简单，原理一目了然同时，也有助于理解一般目标规划的求解原理和过程图解法解题步骤：(1) 将所有约束条件(包括目标约束和绝对约束，暂不考虑正负偏差变量)的直线方程分别标示于坐标平面上2) 确定系统约束的可行域3) 在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向求满足最高优先等级目标的解转到下一个优先等级的目标，再不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解重复(5)，直到所有优先等级的目标都已审查完毕为止确定最优解和满意解单纯形法整数规划整数规划：在前面讨论的线性规划问题中，有些最优解可能是分数或者小数，对对于某些具体的问题，常要求解答必须是整数的情形。
例如，所求解是机器的台数，完成工作的人数或者装货的车数等这类问题需要将决策变量限制为整数规划要求一部分或全部决策变量取整数值的规划问题称为整数规划不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题若该松弛问题是一个线性规划，则称该整数规划为整数线性规划整数线性规划数学模型：maxZ(或minZ)=工cxjjj=1工ax=b(i=1.2…m)vijjij=1x>0(j=1.2…n)且部分或全部为整数j整数线性规划问题的种类：1) 纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划2) 混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划3) 0-1型整数线性规划：决策变量只能取值0或1的整数线性规划整数规划问题的求解方法：分支定界法和割平面法分支定界法的解题步骤：(1) 求整数规划的松弛问题最优解；(。
