运筹学复习资料

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章 线性规划及单纯形法Linear Programming and Simplex Method,内容提要:线性规划问题及其数学模型 线性规划解的概念 单纯形法原理及算法步骤 线性规划应用建模,学习要求：,掌握线性规划根本概念和单纯形法原理,运用单纯形法求解线性规划问题,了解线性规划在经济和管理中的根本应用,1,第二节 图解法,图解法可求解只有两个变量的线性规划。,一、图解法的步骤,(1)取决策变量x1,x2为坐标向量建立直角坐标系。,2找可行域。对每个约束包括非负约束条件确定其所决定的半平面。各约束半平面的公共区域假设存在，其中的点解表示此线性规划的可行解。这些符合约束限制的点集合，称为可行集或可行域。转步骤3。否那么该线性规划无可行解。,3确定最优解。任意作一条目标函数的等值线。按目标函数优化方向平移此等值线，至可行域的临界位置(有时交于无穷远处，此时称无有限最优解。假设有交点时，此交点即最优解一个或无限多个，而目标函数的值即最优值。,2,例3续例:略,解：问题的线性规划模型：,max z=1500 x1+2500 x2,s.t.3x1+2x2 65 (A),2x1+x2 40 (B),3x2 75 (C),x1,x2 0 (D,E),3,按照图解法的步骤，各约束半平面公共区域即可行域。,给目标函数一个值，作目标函数的等值线，并确定等值线平移优化的方向。平移目标函数等值线，其与可行域的临界点(5,25)即为最优解，目标函数值为70000。,4,二,、线性规划问题求解的几种可能结局,无穷多解的情况,例4 在例3中，如果目标函数变为：,max z=,那么，最优情况下目标函数的等值线与直线A重合。这时，最优解有无穷多个，是从点 到点 线段上的所有点，最优值为32500。,5,无有限解的情况,例5 在例1中,如果约束条件A和C变为：,3 +2 65,3 75,并且去掉D、E的非负限制。那么，可行域成为一个上无界的区域。这时，没有有限最优解。,6,无可行解的情况,例6 在例1的线性规划模型中，如果增加约束条件：,40F,那么，可行域成为空域。这时，没有可行解，显然线性规划问题无解。,7,根据以上例题可知，线性规划的可行域和最优解有以下几种可能的情况：,1.可行域为封闭的有界区域,(a)有唯一的最优解,(b)有无穷多个最优解,2.可行域为无界区域,(c)有唯一的最优解,(d)有无穷多个最优解,(e)目标函数无界，无有限最优解。(虽有可行解，但在可行域中目标函数可以无限增大或减少),3.可行域为空集,(f)没有可行解，原问题无最优解,8,三、由图解法得到的启示,线性规划的解可能是：唯一最优解；无穷多最优解；无界解；无可行解。,假设线性规划的可行域存在，那么可行域是一个凸集。,假设线性规划的最优解存在，那么可行域中一定存在某个顶点是最优解。,求解线性规划的思路：先找到可行域的某个顶点，比较它和相邻顶点的目标函数值。如果它最优，那么它就是最优解；如果它不是最优，那么用目标函数值比它优的一个顶点取代它。重复上述过程，直到找到最优解。,9,第三章 运输问题,运输问题与有关概念,运输问题的求解表上作业法,运输问题应用,10,第一节 运输问题及其数学模型,例1 从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地产量、各销地销量和各产地运往各销地每单位物品的运费如表。问：应如何调运可使总运输费用最小？,解 这是一个产销平衡问题：总产量=总销量=500。,设 xij 为从产地Ai运往销地Bj的运输量，得到以下单,位运费和运输量表：,销地B,j,产地A,i,B,1,B,2,B,3,产量a,i,A,1,6 x,11,4 x,12,6 x,13,200,A,2,6 x,21,5 x,22,5 x,23,300,销量b,j,150,150,200,11,数学模型：,Min,f,=6,x,11,+4,x,12,+6,x,13,+6,x,21,+5,x,22,+5,x,23,s.t.x11+x12+x13 =200,x21+x22+x23=300,x11 +x21 =150,x12 +x22 =150,x13 +x23=200,xij 0(i=1,2；j=1,2,3,1 1 1 0 0 0,0 0 0 1 1 1,1 0 0 1 0 0,0 1 0 0 1 0,0 0 1 0 0 1,1.共有,m,+,n,行，分别表示各产地和销地；,m,n,列，分别表 示各决策变量；,2.每列只有两个 1，其余为 0，分别表示只有一个产地和一个销地被使用。,系数矩阵：,12,一般运输问题的提法：,假设Ai(i=1,2,m)表示某物资的m个产地；,Bj(j=1,2,n)表示某物资的n个销地；ai表示产,地 Ai 的产量；bj 表示销地 Bj 的销量；cij 表,示把物资从产地 Ai 运往销地 Bj 的单位运价。,求满足产销关系的总运费最小的运输方案。,如果 a1+a2+am=b1+b2+bn,那么称该运输问题为产销平衡问题；否那么，称产,销不平衡的运输问题又可分为供过于求和供不应求两种情况。,13,对于产销平衡问题，可得到以下运输模型：,14,产销平衡问题运输表:,销地,B,j,产地,A,i,B,1,B,2,B,n,产量,a,i,A,1,c,11,x,11,c,12,x,12,c,1n,x,1n,a,1,A,2,C,21,x,21,C,22,x,22,C,2n,x,2n,a,2,A,m,C,m,1,x,m,1,C,m,2,x,m,2,C,mn,x,mn,a,m,销量,b,j,b,1,b,2,b,n,15,运输问题系数矩阵的秩为m+n-1，故有m+n-1 个基变量，基变量所在格称为基格或称数字格；有m n-m+n-1个非基变量，非基变量所在格称为空格或称非基格。,在运输表中，从一个空格出发，沿水平方向或垂直方向前进，在某个基格处转90度，如此继续，直到回到该空格。这样的一条闭合折线称为该空格非基变量的闭回路。,对每一个空格非基变量，必有闭回路，且唯一不考虑方向。,闭回路是表上作业法的根底，利用闭回路计算非基变量的检验数，确定改进运输方案。,16,第二节 用表上作业法求解运输问题,表上作业法是特殊形式的单纯形法，即首先确定一个,初始根本可行解，然后根据最优性判别准那么来检查它是否,最优。如是那么计算结束；如不是那么换基迭代进行改进。,一、给出运输问题的初始基可行解初始调运方案,1西北角法：从西北角左上角格开始，在格内的,右下角标上可能的最大运输量。假设某行列的产量销,量已满足，那么把该行列划去。如此继续，直至得到,一个根本可行解。,2最小元素法：从运价最小的格开始，在格内的右下,角标上可能的最大运输量。假设某行列的产量销量,已满足，那么把该行列划去。如此继续，直至得到一个,根本可行解。,注:每次填完数，都只划去一行或一列，但最后一次同时,划去剩下的一行和一列。,17,二、解的最优性检验,当所有检验数都大于或等于零时该调运方案就是最优方案；否,那么就不是最优，需要进行调整。下面介绍两种求检验数的方法。,1、闭回路法,例：以非基变量 x22 为起始顶点的闭回路,销,产,B,1,B,2,B,3,B,4,产量,3,11,3,4,10,3,7,1,3,9,2,1,8,4,7,4,6,10,5,3,9,销量,3,6,5,6,20(产销平衡),A,1,A,2,A,3,当,x,22,增加一个单位时，由于供需平衡关系，闭回路上各顶点运输量将发生连锁调整，总的结果就是对目标函数的边际影响，即检验数,22,。因此,22,=9 2+3 10+5 4 1,18,了解整数规划在经济和管理中的根本应用方法。,第五章 整数规划,Integer Programming,教学要求：,掌握线性整数规划的建模方法，特别是0-1变量的运用；,了解分支定界求解方法的根本原理；,了解割平面求解方法的根本原理；,19,整数规划是一类要求变量取整数值的数学规划，可分成线性和非线性两类。整数规划是数学规划中一个较弱的分支，目前只能解中等规模的线性整数规划问题，而非线性整数规划问题，还没有好的方法。第一节 整数规划的数学模型及解的特点一、整数规划数学模型(Integer programming models)混合整数规划 Mixed integer programming 纯整数规划 Pure integer programming 0-1 整数规划 0-1 integer programming,20,纯整数规划,max z=,j=1,2,n,c,j,x,j,s.t.,j=1,2,n,a,ij,x,j,=b,i,i=1,2,m,x,j,0,x,j,integer,j=1,2,n,0-1 整数规划,max z=,j=1,2,n,c,j,x,j,s.t.,j=1,2,n,a,ij,x,j,=b,i,i=1,2,m,x,j,=0 or 1,j=1,2,n,第二节 解纯整数规划的割平面法,第三节 分支定界法,21,例11 Stockco现有资金$14,000，6个投资方案所需的现金和财务净现值累计(NPV)如下表，想使他的NPV最大，问最优策略是什么？,Max 16x,1,+22x,2,+12x,3,+8x,4,+11x,5,+19x,6,5x,1,+7x,2,+4x,3,+3x,4,+4x,5,+6x,6,14,x,j,e,0,1,，for each j=1 to 6,投资项目,1,2,3,4,5,6,需要现金,$5,$7,$4,$3,$4,$6,NPV,$16,$22,$12,$8,$11,$19,22,正好选择三种股票,如果选择股票2，必须也选择股票1,如果选择股票1，那就不能选择股票3,股票4和股票5只能选其一,必须选择股票1，除非NPV累计超过$42000,x,1,+x,2,+x,3,+x,4,+x,5,+x,6,=3,x,1,x,2,x,1,+x,3,1,x,4,+x,5,=1,If NPV=0,只要将Dijkstra算法中的“2看作每一个使vk,vjA，且vjSj的点vj改变为“2看作每一个使vk,vjE，且vjSj的点vj而其他的条件不变，同样可以求出从vs到各点的最短路对于无向图叫做最短链。,作为习题，将例8.6中所示的赋权有向图的箭头去掉，然后求出无向图中从vs到各点的最短路。,39,1,3,2,5,4,6,4,3,3,2,3,2,2,第,0,步：,P(1)=0,T(i)=+,；,第,1,步：与,1,相连的标号为,2,3,，均是,T,标号，修改,2,3,的标号，,T(2)=minT(2),P(1)+w,12,=4,T(3)=3,；在所有的,T,标号中，,3,的标号最小，改,3,的标号,P(3)=3,；,第,2,步：修改与,3,相连的,T,标号；在所有剩下的,T,标号中，,2,的标号最小，改为,P(2)=4,；,第,3,步：修改与,2,相连的,T,标号；在所有剩下的,T,标号中，,5,的标号最小，改为,P(5)=6,；,第,4,步：修改与,5,相连的,T,标号；在所有剩下的,T,标号中，,4,的标号最小，改为,P(4)=7,；,第,5,步：修改与,4,相连的,T,标号；只剩下节点,6,是,T,标号，修改,6,的标号，,P(6)=8,。,从节点,6,开始回退，得到最短路。,P(1)=0,T(3)=+,T(2)=+,T(3)=3,T(5)=+,P(3)=3,T(5)=6,T(2)=4,T(4)=+,T(6)=+,P(2)=4,T(4)=7,P(5)=6,T(6)=8,P(4)=7,P(6)=8,P(6)=8,P(5)=6,P(3)=3,P(1)=0,例：,40,例：一辆车每年的维护费用和旧车的价格依赖于年初时的车龄，具体费用见右表。假设任何时间新车的价格均为12000美元。希望今后5年内的净费用最小。,净费用=购置价+维护价-售出价。,车龄,年维护费,售出价,0,1,2,3,4,5,2000,4000,5000