2016运筹学总复习

1、运筹学,复习,第1章 绪论,用科学方法分析管理及工程问题，为决策提供依据。 目标：在企业经营内外环境的限制下，实现资源效用最大。,第2章线性规划及单纯形法,一般线性规划的数学模型 图解法 单纯形法,线性规划的一般模型,标准形式,可行解 可行域 最优解 基 基向量 非基向量 基变量 非基变量 基解 基可行解,建立坐标系 找出可行域 绘出目标函数图形 求出最优解,图解法步骤,唯一最优解 无穷多最优解 无界解（或无最优解） 无可行解,线性规划问题解的情况,凸集和顶点 线性规划问题的基可行解X对应线性规划问题可行域（凸集）的顶点。 若线性规划问题有最优解，一定在一某个顶点得到。,单纯形法步骤： 确定初

2、始基可行解； 从初始基可行解转换为另一基可行解； 最优性检验和判别。,1、线性规划的标准形式,目标函数： 约束条件：,目标系数,决策变量,技术系数,右端项,1、min Z=CX max Z= -CX 2、约束条件为“” 转换为“=”方法： 在s.t.中左端加上一个“松弛变量”，使“”变为“=”。同时，在目标函数中，令松弛变量的目标系数为0。 3、约束条件为“”转换为“=”方法： 在s.t.中左端减去一个“剩余变量”，使“”变为“=”。同时，在目标函数中，令剩余变量的目标系数为0。,2、非标准形式的标准化方法,4、决策变量xi0 xj = - xi 5、决策变量的符号不受限制 xj = xj-

3、xj， xj，xj 0.,2020/9/3,14,3、图解法,对于只含有两个变量的线性规划问题，可通过在平面上作图的方法求解。其步骤如下：,建立平面直角坐标系； 图示约束条件，找出可行域； 图示目标函数，即为一条直线； 将目标函数直线沿其法线方向在可行域边界平移直至函数达到最优值为止，目标函数达到最优值的点就为最优点。,4、单纯形法的计算步骤,（1）将问题化为标准型； （2）求出线性规划的初始基可行解，列出初始单纯形表； （3）进行最优性检验： 如果表中所有检验数 ，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。,（4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯

4、形表。,确定换入基的变量。选择 ，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即： 其对应的xk作为换入变量。 确定换出变量。根据下式计算并选择，选最小的对应基变量作为换出变量。,用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。 （5）重复（3）、（4）步直到计算结束为止。,对偶规则表,对偶理论：,则其对偶问题的一般形式为,对称形式的线性规划原问题的一般形式为,对称形式对偶问题,一对对偶问题的关系，只能有下面三种情况之一： 1. 都有最优解； 2.一个问题无界，则另一个问题无可行解

5、； 3. 两个都无可行解.,对偶规划可以用线性规划的单纯形法求解。 由对偶原理可见，原问题与对偶问题之间有紧密联系，因此我们能够通过求解原问题来找出对偶问题的解，反之依然。 互补松弛条件就可以解决由原问题的最优解直接求出对偶问题的最优解。,对偶问题解的求法,对偶单纯形法是求解线性规划的另一个基本方法，它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。 不要简单地将对偶单纯形法理解为求解对偶问题的单纯形法。,第4章 运输问题,1、运输问题的数学模型的建立； 2、产销平衡下运输问题的基变量个数与产地、销地之间的关系（m+n-1），即（m+n-1）个独立约束方程； 3、约束方程都是

6、等式。,一、确定初始基可行解,运输问题的初始方案的确定主要有：,最小元素法,伏格尔法,运输问题,找出初始基可行解，即在产销平衡表上有（m+n-1）个数字格。,1、最小元素法的精髓（就近供应，从单位运价表中最小的运价开始确定供销关系，依次类推，只到给出全部方案为止）； 2、Vogel法的核心（最大差额处，优先按最小运价进行调整）； 3、位势法求检验数、闭回路法进行调整； 4、产销不平衡时的调整方法。,第5章 目标规划,1、目标规划的组成与特点； 2、目标规划的模型（如何建立目标函数、目标约束建立等）； 3、目标函数中偏差变量的取舍（利润型目标、成本型目标和合同型目标中偏差变量的取舍）； 4、掌握

7、目标规划应用方法（不用求解）。,1、目标规划的特点,约束一般包括目标约束、系统约束、非负约束三个部分； 最终目标转换为求偏离多个期望目标值的偏差和最小； 目标及约束仍为线性。,（1）对于利润型目标，要求是可能实现值超过目标值越多越好，即d+越大越好，则在目标函数中，不能对d+求最小； （2）对于成本型目标，要求可能实现值低于目标值越多越好，即d-越大越好，则在目标函数中不能对d-求最小； （3）对于合同型目标，要求跟目标保持一致，不超过也不短缺，即要求d+和d-都最小，则在目标函数中应将两者综合考虑。,2、目标函数中偏差变量的优化,第6章 整数规划,分支定界法 割平面法 指派问题及匈牙利法,分

8、枝定界法：将原整数规划问题分枝分为两个子规划,再解子规划的伴随规划通过求解一系列子规划的伴随规划及不断地定界。最后得到原整数规划问题的整数最优解。,从(LP)的最优解中，任选一个不为整数的分量xr,将最优单纯形表中该行的系数arj和 br分解为整数部分和非负真分数部分之和， 并以该行为源行，按作割平面方程。,将所得的割平面方程，作为一个新的约束条件置于最优单纯形表中同时增加一个单位列向量），用对偶单纯形法求出新的最优解。,割平面法,匈牙利算法。 算法主要依据以下事实：如果将系数矩阵C=（Cij）中一行（或一列）的每一元素都加上或减去同一个数，得到一个新矩阵B=（bij），则以C和B为系数矩阵的

9、指派问题具有相同的最优指派。 系数矩阵中独立 0 元素的最多个数等于能覆盖所有 0 元素的最少直线数。,指派问题,Step 1、先对效率矩阵进行列变换，使其各行各列中都出现 0 元素。,效率矩阵变换方法为： 从效率矩阵 C 的每行元素中减去该行的最小元素,得矩阵 B ；从矩阵 B 中每列元素中减去该列的最小元素得矩阵 C1 。,min 0 0 5 0,Step 2、确定C1中线性独立的0元素.,从第一行开始，若该行只有一个0元素，就对这个0元素加圈，然后划去其所在列的其它0元素;若该行没有其它0元素或有两个以上0元素（已划去的不计），转下一行；直到最后一行为止。,然后，从第一列开始，若该列只有

10、一个0元素，就对这个0元素加圈（同样不考虑已划的）,再划去其所在行的其它0元素；若该列没有0元素或有两个以上0元素，则转下列直到最后一列为止。,重复上述步骤。,上述步骤可能出现三种情况,情况一：矩阵每行都有一个打圈的 0 元素。此时得到问题的最优解。,情况二：有多于两行或两列存在两个以上的未处理的 0 元素，即出现 0 元素的闭回路。此时，可从中任选一个 0元素加圈，划掉其同行同列的 0 元素，再重复上述两个步骤。,情况三：矩阵中所有 0 元素或被加圈，或被划去，而已加圈的 0 元素m小于矩阵的行数n。即矩阵中至少存在有一行不含加圈的 0 元素。转步骤三。,Step 3 寻找能覆盖C1中所有0

11、元素的最小直线数,(1)按照从上到下、从左到右的顺序对C1没有加圈的0元行打号； (2)对已打号的行中未加圈0元的列打号； (3)对已打号的列中加圈0元的行打号； (4)重复下去，直到找不出打号的行、列为止。,(5)对没打号的行划一横线，对打号的列划一纵线，这就是覆盖矩阵C1中所有0元素的最小直线数.,Step 4、改进C1,(1)寻找 C1 没有被直线覆盖的所有元素中的最小元素； 例中= 2。 (2)在已打号的行中减去； (3)在已打号的列中加上； 得到一个新矩阵 C2。,用 C2 代替 C1，返回步骤 2。,即最优分配方案：,确定C2中线性独立的0元素.,第7章 动态规划,1、熟悉关于动态

12、规划的一些基本概念； 2、状态转移方程的建立方法； 3、动态规划的解题步骤； 4、动态规划的求解方法（确定型、逆序法，P169例7-3之类）；,第8章 图与网络,图的基本概念 树和图的最小支撑树 最短路问题 网络最大流问题 最小费用最大流问题,概念 定义（前向弧和后向弧）:在任意一顶点之处，凡离开vi的有向弧称为vi的前向弧，凡进入vi的有向弧称为vi的后向弧。,vi,vj,a,称有向弧a为vi点的前向弧， vj点的后向弧。,v0,vn,v2,v1,定义（道路或通路）在任意一网络中，凡从始点v0（发点）开始到终点vn（收点）结束的一系列前向弧集合称为道路。,如果N表示某网络中所有点的集合，将N

13、分成两个子集A与A，使得发点v0在A内，收点vn在A 内，则称（A，A）为分离发点与收点的截集。,截集定义,从 A 中各顶点到 A中各顶点全部容量之和称为截集的容量（截量）。,截集的容量,v0,vn,v2,v1,a,截集a：v0v1，v0v2，v0vn,截量: Ca=C01+C02+C0n,v0,vn,v2,v1,截集v1vn，v2vn，v0vn,截量: Cb=C1n+C2n+C0n,v0,vn,v2,v1,d,S,S,在截集d中边v1v2是反向的，其容量视为零。,截集：v0v1，v1v2，v2v1，v2vn，v0vn,截量： Cd=C01+C21+ C2n+ C0n,在将网络分成发集与收集的

14、所有分法中，容量最小的截集称为最小截集。,如果链满足以下条件： （1）在弧（vi,vj）+上，有0fijcij， 即+中的每一条弧是非饱和弧。 （2）在弧（vi,vj）-上，有0fij cij， 即-中的每一条弧是非零流弧。 则称这样的链为增广链 。,增广链,练习题,1、最早运用运筹学理论的是（ ） A 二次世界大战期间，英国军事部门将运筹学运用到军事战略部署； B 美国最早将运筹学运用到农业和人口规划问题上； C 二次世界大战期间，英国政府将运筹学运用到政府制定计划； D 50年代，运筹学运用到研究人口，能源，粮食，第三世界经济发展等问题上。,单项选择题,2、在产销平衡运输问题中，设产地为个

15、，销地为个，那么基可行解中非零变量的个数（ ） A. 不能大于(m+n-1)； B. 不能小于(m+n-1)； C. 等于(m+n-1)； D. 不确定。,3、在求解运输问题的过程中运用到下列哪些方法（ ） A 最小元素法 B 位势法 C 闭回路法 D 伏格尔法 E 以上都是,53,图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。 LP模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。 LP问题的每一个基解对应可行域的一个顶点。 如LP问题存在最优解，则最优解一定对应可行域边界上的一个点。,判断下列说法是否正确,54,6. 任何LP问题

16、存在并具有唯一的对偶问题。 7. 对偶问题的对偶问题一定是原问题。 8. 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解。,5. 线性规划问题的可行解如为最优解，则该可行解一定是基可行解；,因为基可行解可行解。,9.运输问题数学模型的（m+n）个约束中 最多只有（m+n-1）个是独立的。,10.产销平衡的运输问题解的情况有四种：无可行解；无界解；唯一最优解；无穷多最优解。,错 P102,11.运输问题的所有结构约束条件都是等式约束。,对,填空题,1、用大M法求解Max型线性规划时，人工变量在目标中的系数均为 ,若最优解的 中含有人工变

17、量，则原问题无可行解。,（-M） 基变量,2、若某种资源的影子价格为零，则表明该种资源 （应该或不应该）被买进；又当资源的影子价格不为零时，说明该种资源消耗 （完毕或剩余）,不应该 完毕,3、线性规划原问题中的变量个数与其对偶问题中的 个数相等。因此，当原问题增加一个变量时，对偶问题就增加一个 ，从而对偶可行域将可能变 (小还是大)。,小,约束条件,约束条件,4、用表上作业法求解m个产地n个销地的平衡运输问题，其方案表上数字格的个数为 个；,m+n-1,建立线性规划模型（利润最大或者成本最小） 线性规划化为标准型 写出问题的对偶规划,建立模型,某人每天食用甲、乙两种食物（如猪肉、鸡蛋）， 如表

18、。问两种食物各食用 多少，才能既满足需要、 又使总费用最省？,设：X1 、X2 表示甲、乙种食物的用量。,甲 乙,初 始 表,最终表,原问题 的变量,原问题的 松弛变量,对偶问题的 剩余变量,对偶问题 的变量,由表可知，原问题最优解： X*=（50/7，200/7，0，0，0），Z=4100/7 对偶问题的最优解： Y*=（0，32/7，6/7，0，0），W=4100/7,B-1,8,3,2,2,v1,v6,用避圈法或破圈法求下图所示最小支撑树。,4,v4,5,4,3,3,v7,v8,v3,v5,v2,2,4,2,2,2,2,2,8,3,解法一：用避圈法 W(T*)=2+2+2+2+2+2+3=15,解法二：用破圈法,v1,v6,4,v4,5,4,3,3,v7,v8,v3,v5,2,4,2,2,2,7个村庄要在他们之间架设电话线，要求任何两个村庄都可以互相通电话(允许中转)，并且电话线根数最少？,村庄2,村庄1,村庄4,村庄3,村庄6,村庄5,村庄7,类似的问题都是求最小支撑树,用动态规划逆序法解