运筹学期末复习提纲.ppt

运筹学复习,1 线性规划,线性规划问题及其数学模型图解法单纯形法原理单纯形法计算步骤单纯形法的进一步讨论,线性规划的概念,目标能表成求 MAX 或 MIN达到目标有多种方案实现目标有一定条件目标和条件都能用线性函数表示,例如，对于线性规划问题,其系数矩阵为,则下面两个矩阵都是该线性规划问题的基。,和,还能找出其它基吗？,基解：令非基变量等于0的解。基可行解：基解+可行解,例如，对于上面的线性规划问题，如果取x1，x2为基变量，则令非基变量x3，x4为零，约束方程组为,解之得。故我们得到基解注意到这个基解还是一个可行解。,是否所有的基解都是基可行解？（选x1,x3作为基变量）,解的概念,解,2.3(1),(2),线性规划要注意的几点,图解法 对只包含两个决策变量的线性规划问题，可以用图解法来求解。图解法顾名思义就是通过作图来求解的方法，它简单直观、并有助于说明一般线性规划问题求解的基本原理。,线性规划的标准形式,它具有如下四个特征：目标函数求max；约束方程符号取“=”；bi非负；所有决策变量xj非负。,线性规划解的存在性,线性规划问题的所有可行解构成的集合是凸集，也可能为无限集。他们有有限个顶点，线性规划问题的每个基可行解对应可行域一个顶点，反之亦然。若线性规划问题有最优解，必在某顶点达到。,大M法,将人工变量在目标函数中反映出来得到如下形式的线性规划：,因此最优解为,最优目标函数值为,需要说明的是，如果在用大M法求解线性规划问题时，最终表的基变量中还含有人工变量，那么这个最终表并没有给出原来问题的基可行解，从而没有给出原来的线性规划问题最优解。这时原来线性规划问题为无可行解。,用EXCEL执行该计算过程,故原来问题的最优解为,最优目标函数值,这一结果与大M法得到的结果是一致的。,无可行解的判别：在用大M法求解线性规划问题时，若最终单纯形表的基变量中含人工变量；或用两阶段法求解时，第一阶段最终表的基变量中含非零的人工变量，也就是第一阶段最优目标函数值不等于零，则线性规划问题无可行解。,2.8 单纯形法小结,2 线性规划对偶理论及其应用,规范形式的线性规划与对偶规划问题,原问题（LP）,对偶问题（DLP）,对偶规划的基本性质,3.2.2 弱对偶性定理：如果X、Y分别是原问题和对偶问题的一个可行解，则其对应的原问题的目标函数值不大于对偶问题的目标函数值，也即,证明：因为X、Y分别是原问题（3.1）与对偶问题（3.2）的可行解，故：,所以,推论一：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是起原问题目标函数值的上界。推论二：如果原问题存在无界解，则对偶问题一定无可行解；反之，如果对偶问题存在无界解，原问题也一定不存在可行解。注意，该推论的逆反定理并不成立。注意，该推论的逆反定理并不成立。推论三：如果原问题无解，且对偶问题有可行解，则对偶问题具有无解解，；反之，如果对偶问题无解，且原问题有可行解，则对偶问题具有无界解。,最优性定理,互补松弛定理,约束 方程 也分为两种情况：，约束条件比较松；，约束条件比较紧；,yi=0,分为两种情况：yi0，约束条件比较松；yi=0，约束条件比较紧；,互补松弛定理的解释,变量同其对偶问题的约束方程之间至多只能够有一个取松弛的情况，当其中一个取松弛的情况时，另外一个比较紧，即取严格等号。,例已知下面的LP1和LP2为一组对偶规划，且已知LP1的最优解为X=（1.5，1）。试运用互补松弛定理求出对偶问题的最优解Y。,生产计划问题（LP1）,资源定价问题（LP2）,解：由X=（1.5，1）得,联立求解得：,解：由X=（1.5，1）得,联立求解得：,解：由X=（1.5，1）得,联立求解得：,灵敏度分析,约束条件右端向量b的变化,3 目标规划,目标规划基本概念,（1）偏差变量 d+：正偏差变量，表示决策值超出目标值的部分 d-：负偏差变量，表示决策值未达到目标值的部分 按定义有：d+0，d-0，d+d-=0（2）绝对约束和目标约束 绝对约束（硬约束）：必须严格满足的约束条件 目标约束（软约束）：目标规划特有（3）优先因子（P）和权系数（W）优先因子用P1，P2，Pl表示，规定 Pl Pl+1，表示Pl比Pl+1有更大的优先权。（4）目标函数 决策值=目标值 min f(d+d-)决策值目标值 min f(d-),目标规划模型的建立,例4.1 某企业计划生产甲、乙两种产品。已知有关数据见表4-1。问如何安排生产使获得的总利润最大？,表 4-1,设x1、x2分别表示计划生产产品甲、乙的产量，它的数学模型为：,它的最优解为x1=4，x2=3，最大目标函数值为62。,但企业的经营目标不仅是利润，企业还考虑了以下问题：（1）根据市场信息，产品甲开始出现滞销现象，故考虑产品甲的产量应不超过产品乙；（2）超过计划供应的原材料需高价采购，应避免过量消耗；（3）应尽可能充分利用设备台时，但不希望加班；（4）应尽可能达到并超过计划利润指标56元。,例4.2 例4.1的决策者经过综合考虑，决策者的目标分别为：首先原材料使用限额不能突破；其次产品甲的产量不大于产品乙；再次充分利用设备台时，不希望加班；最后利润额不少于56元。问应如何安排生产？解：原材料使用限额的约束是绝对约束，其他三个约束是属于目标约束，分别赋予这三个目标的优先因子为P1，P2，P3。这问题的数学模型为：,2x1+x2 11 x1-x2+d1-d1+=0 x1+2x2+d2-d2+=108x1+10 x2+d3-d3+=56 x1,x2,di-,di+0 i=1,2,3,min P1 d1+,P2(d2-+d2+),P3 d3-,s.t.,目标规划模型的一般形式：,目标规划模型的一般形式：,当总产量=总销量，称为产销平衡问题 当总产量总销量，称为产销不平衡问题,4 运输问题,产销平衡的运输问题的数学模型如下,运输问题含有mn个变量，m+n个约束方程。其系数矩阵的结构比较特殊，对应变量xij的系数向量，其分量中除第i个和第m+j个为1以外，其余的都为零 模型中只有个相互独立的约束方程。因此，运输问题的任一基可行解都有m+n-1个基变量。,运输问题的表上作业法,2)沃格尔法,6,3,3,5,1,2,1,11=c11-c13+c23-c21=3-3+2-1=1,解的最优性检验 1)闭回路法,对偶变量法（位势法）,6,3,3,4,1,3,0,3,10,-1,-5,2,9,1,2,1,-1,10,12,基变量：cij=ui+vj,非基变量：ij=cij(ui+vj),产销不平衡运输问题,1.一般产销不平衡运输问题,1)总产量 总销量,假想一销地Bn+1，令销量为,运价c=0,5 整数规划,5.1 整数规划实例及一般模型5.2 分支定界法5.3 0-1整数规划5.4 指派问题,整数规划的类型,纯整数规划：xj全部是整数混合整数规划：xj部分是整数0-1型整数规划：xj=0或1,整数线性规划问题解的特点,整数规划的可行解集合是它的松弛问题可行解集合的一个子集，即整数规划的可行解一定是其松弛问题的可行解（反之不然）整数规划问题的最优目标函数值不会优于其松弛问题最优解的目标函数值若松弛问题的可行解满足整数约束，则它也是整数规划的可行解整数规划问题的最优解不能由其松弛问题最优解经过简单取整得到,如用“舍入取整法”可得到4个点即(2，2),(2，3),(3，2),(3，3)。显然，它们都不可能是整数规划的最优解。,松弛问题最优解,整数规划最优解,例,不能通过舍入取整地方法，由松弛问题的解得到整数规划的最优解,6 动态规划,6.1 动态规划的基本概念6.2 最优化原理6.3 经济管理问题举例,多阶段决策过程,动态规划的分类：离散确定型 离散随机型 连续确定型 连续随机型,决策1,决策2,决策n,1、阶段，阶段数阶段变量：k;阶段数记作n。,无后效性：如果某阶段的状态给定，这阶段以后过程的发展不受这阶段以前各阶段状态的影响,3、决策 某阶段状态确定后，为确定下一阶段的状态，所作出的决定（选择）。决策变量：u k(s k)表示第k阶段状态为s k时的决策 允许决策集合：D k(s k),动态规划的基本概念,2、状态每个阶段开始时所处的自然状态或客观条件状态变量：s k状态集合：S k,4、策略：由决策组成的序列称为策略。p 1,n u 1(s 1),u 2(s 2),u n(s n)允许策略集合：P1,n最优策略：p*1,n 子策略：5、状态转移方程 s k+1=T k(s k,u k)6、效益(指标)函数:Vkn(sk,pkn(sk)阶段效益函数：wk(sk,uk(sk)最优效益函数：fk(sk)最优策略:pkn*,全过程的最优效益函数,标号法求解最短路问题,0,7,6,8,16,14,14,16,21,20,22,26,所以最短路为AB1C2D2E，最短路长为26。,最优化原理,动态规划的基本方程（逆序法）：,f k(sk)表示从第k阶段状态sk到终点F的最短距离,如果一个策略是最优策略，则其子策略也一定是最优策略；如果两段子策略都是最优策略，则连起来是否是最优策略呢？,动态规划的基本方程（顺序法）：,7 网络优化模型,图与网络的基本概念 最短路径问题 最大流问题 最小费用最大流问题,图与网络的基本概念,5、连通图：,圈：无向图G=（V,E）中起点和终点重合的链称为圈,初等、简单圈：没有重复点的圈称为初等圈，没有重复边的圈称为简单圈。(v1,e1,v2,e6,v4,e3,v3,e5,v1),图与网络的基本概念,6、子图与生成子图：,子图：图G=(V,E)，E是E的子集，V是V的子集，且E 的边与V的顶点想关联，G=(V,E)是图G的一个子图。生成子图：若V=V，则G是G的生成子图,图与网络的基本概念,7.1.2 树的概念及性质,1、树（T）：无圈的连通图称为树 树叶 分枝点,图与网络的基本概念,7.1.2 树的概念及性质,2、树的性质性质7.1 树中任意两点之间有且只有一条链。性质7.2 如图G中任意两点之间，有且只有一条链，则该图G是一个树。性质7.3 一个树，则m=n-1。性质7.4 树中任意两个不相邻的点之间增加一条边，则形成唯一的圈。性质7.5 一个树如果去掉任何一条边，该图就不再连通。,图与网络的基本概念,7.1.2 树的概念及性质3、图的生成树,生成树（支撑树）：图G的生成子图是一棵树，则称该树为G的生成树图G中属于生成树的边称为树枝，不属于生成树的边称为弦定理7.3：图G=（V,E）,有生成树的充分必要条件为G是连通图,4、最小生成树：图G=(V，E)的生成树所有树枝上的权数的总和,称为生成树的权。权数最小的生成树称为最小生成树。,寻找最小生成树的方法：避圈法、破圈法,最小生成树权=11,